[RFC,v1,22/43] helper-to-tcg: PrepareForTcgPass, remove functions w. cycles

Commit Message

Anton Johansson Nov. 21, 2024, 1:49 a.m. UTC

Functions with cycles are removed for two primary reasons:

  * as a simplifying assumption for register allocation which occurs down
    the line, and;

  * if a function contains cycles post-optimization neither unrolling or
    loop vectorization were beneficial, and the function _might_ be
    better suited as a helper anyway.

Cycles are detected by iterating over Strongly Connected Components
(SCCs) which imply the existence of cycles if:
  - a SCC contains more than one node, or;
  - it has a self-edge.

Signed-off-by: Anton Johansson <[e-mail]>
---
 .../PrepareForTcgPass/PrepareForTcgPass.cpp   | 32 +++++++++++++++++++
 1 file changed, 32 insertions(+)

Patch

diff --git a/subprojects/helper-to-tcg/passes/PrepareForTcgPass/PrepareForTcgPass.cpp b/subprojects/helper-to-tcg/passes/PrepareForTcgPass/PrepareForTcgPass.cpp
index f0ef1abd17..ccbe3820a0 100644
--- a/subprojects/helper-to-tcg/passes/PrepareForTcgPass/PrepareForTcgPass.cpp
+++ b/subprojects/helper-to-tcg/passes/PrepareForTcgPass/PrepareForTcgPass.cpp
@@ -16,10 +16,42 @@ 
 //
 
 #include <PrepareForTcgPass.h>
+#include <llvm/ADT/SCCIterator.h>
+#include <llvm/IR/Function.h>
+#include <llvm/IR/Module.h>
 
 using namespace llvm;
 
+static void removeFunctionsWithLoops(Module &M, ModuleAnalysisManager &MAM)
+{
+    // Iterate over all Strongly Connected Components (SCCs), a SCC implies
+    // the existence of loops if:
+    //   - it has more than one node, or;
+    //   - it has a self-edge.
+    SmallVector<Function *, 16> FunctionsToRemove;
+    for (Function &F : M) {
+        if (F.isDeclaration()) {
+            continue;
+        }
+        for (auto It = scc_begin(&F); !It.isAtEnd(); ++It) {
+#if LLVM_VERSION_MAJOR > 10
+            if (It.hasCycle()) {
+#else
+            if (It.hasLoop()) {
+#endif
+                FunctionsToRemove.push_back(&F);
+                break;
+            }
+        }
+    }
+
+    for (auto *F : FunctionsToRemove) {
+        F->deleteBody();
+    }
+}
+
 PreservedAnalyses PrepareForTcgPass::run(Module &M, ModuleAnalysisManager &MAM)
 {
+    removeFunctionsWithLoops(M, MAM);
     return PreservedAnalyses::none();
 }