Subzero: Loop Invariant Code Motion

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 0bcda2b0525b6e9225e2b61029249e3b6ba26d8b..9d629f05a67b07f6cb936886b7c566ec7f67fb6b 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -640,6 +640,98 @@ void Cfg::localCSE() {
   }
 }
 
+void Cfg::loopInvariantCodeMotion() {

[John, 2016/07/08 21:04:46]

please create a helper function named "findLoopInvariantInstructions" (or
something similar) and move the first half of this code over.

+  TimerMarker T(TimerStack::TT_loopInvariantCodeMotion, this);
+  // Does not introduce new nodes as of now.
+  for (auto &Pair : LoopInfo) {
+    CfgNode *Header = Nodes[Pair.first];
+    if (Header->getLoopNestDepth() < 1)
+      continue;
+    assert(Header);
+    CfgNode *PreHeader = nullptr;
+    for (auto *Pred : Header->getInEdges()) {
+      if (Pred->getLoopNestDepth() == Header->getLoopNestDepth() - 1) {
+        if (PreHeader == nullptr) {
+          PreHeader = Pred;
+        } else {
+          PreHeader = nullptr;
+          break;
+          // Do not consider cases with two incoming edges.
+          // Will require insertion of nodes.
+        }
+      }
+    }
+    if (PreHeader == nullptr || PreHeader->getInsts().size() == 0) {
+      continue; // to next loop
+    }
+
+    // Detect invariant instructions
+    CfgUnorderedSet<Inst *> InvariantInsts;

[John, 2016/07/08 21:04:46]

Given that this is a set, this will probably not help much, but how about
hoisting this declaration to the top of this function, and then invoke "clear()"
on them here?

[manasijm, 2016/07/08 21:09:31]

This is why I was advocating a stack allocator :) 

+    CfgUnorderedSet<Variable *> InvariantVars;

[John, 2016/07/08 21:04:46]

please create a helper function named "findLoopInvariantInstructions" (or
something similar) and move the next loops to that function.

[manasijm, 2016/07/08 21:09:31]

Will do.

+    for (auto *Var : getArgs()) {
+      InvariantVars.insert(Var);
+    }
+    bool Changed = false;
+    do {

[John, 2016/07/08 21:04:46]

I tend to prefer using worklist-based iteration instead of this solution. Your
call.

+      Changed = false;
+      for (auto NodeIndex : Pair.second) {
+        auto *Node = Nodes[NodeIndex];
+        CfgVector<std::reference_wrapper<Inst>> Insts(Node->getInsts().begin(),
+                                                      Node->getInsts().end());
+
+        for (auto &InstRef : Insts) {
+          auto &Inst = InstRef.get();
+          if (Inst.isDeleted() ||
+              InvariantInsts.find(&Inst) != InvariantInsts.end())
+            continue;
+          switch (Inst.getKind()) {
+          case Inst::InstKind::Alloca:
+          case Inst::InstKind::Br:
+          case Inst::InstKind::Ret:
+          case Inst::InstKind::Phi:
+          case Inst::InstKind::Call:
+          case Inst::InstKind::IntrinsicCall:
+          case Inst::InstKind::Load:
+          case Inst::InstKind::Store:
+          case Inst::InstKind::Switch:
+            continue;
+          default:
+            break;
+          }
+
+          bool IsInvariant = true;
+          for (SizeT i = 0; i < Inst.getSrcSize(); ++i) {
+            if (auto *Var = llvm::dyn_cast<Variable>(Inst.getSrc(i))) {
+              if (InvariantVars.find(Var) == InvariantVars.end()) {
+                IsInvariant = false;
+              }
+            }
+          }
+          if (IsInvariant) {
+            Changed = true;
+            InvariantInsts.insert(&Inst);
+            Node->getInsts().remove(Inst);
+            if (Inst.getDest() != nullptr) {
+              InvariantVars.insert(Inst.getDest());
+            }
+          }
+        }
+      }
+    } while (Changed);
+
+    auto &Insts = PreHeader->getInsts();
+    auto &LastInst = Insts.back();

[John, 2016/07/08 21:04:46]

Why the special handling of Insts.back?

[manasijm, 2016/07/08 21:09:31]

It is a control flow instruction, can not insert other stuff after it.

+    Insts.pop_back();
+    CfgVector<Inst *> InstVector(InvariantInsts.begin(), InvariantInsts.end());
+    std::sort(InstVector.begin(), InstVector.end(),
+              [](Inst *A, Inst *B) { return A->getNumber() < B->getNumber(); });
+    for (auto *Inst : InstVector) {
+      PreHeader->appendInst(Inst);
+    }
+    PreHeader->appendInst(&LastInst);
+  }
+}
+
 void Cfg::shortCircuitJumps() {
   // Split Nodes whenever an early jump is possible.
   // __N :
@@ -1338,10 +1430,9 @@ void Cfg::genFrame() {
       getTarget()->addEpilog(Node);
 }
 
-void Cfg::computeLoopNestDepth() {
+void Cfg::generateLoopInfo() {
   TimerMarker T(TimerStack::TT_computeLoopNestDepth, this);
-  LoopAnalyzer LA(this);
-  LA.computeLoopNestDepth();
+  LoopInfo = LoopAnalyzer(this).getLoopInfo();
 }
 
 // This is a lightweight version of live-range-end calculation. Marks the last