Subzero: Loop Invariant Code Motion

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 622 matching lines @@
             if (auto *Var = llvm::dyn_cast<Variable>(Opnd)) {
               Dependency[Var].push_back(&Instr);
             }
           }
         }
       }
     }
   }
 }
 
+void Cfg::loopInvariantCodeMotion() {
+  TimerMarker T(TimerStack::TT_loopInvariantCodeMotion, this);
+  // Does not introduce new nodes as of now.
+  for (auto &Pair : LoopInfo) {
+    CfgNode *Header = Nodes[Pair.first];
+    assert(Header);
+    if (Header->getLoopNestDepth() < 1)
+      continue;
+    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
+    }
+
+    auto &Insts = PreHeader->getInsts();
+    auto &LastInst = Insts.back();
+    Insts.pop_back();
+
+    for (auto *Inst : findLoopInvariantInstructions(Pair.first)) {
+      PreHeader->appendInst(Inst);
+    }
+    PreHeader->appendInst(&LastInst);
+  }
+}
+
+Ice::CfgVector<Inst *>
+Cfg::findLoopInvariantInstructions(Ice::SizeT LoopHeaderIndex) {
+  CfgUnorderedSet<Inst *> InvariantInsts;
+  CfgUnorderedSet<Variable *> InvariantVars;
+  for (auto *Var : getArgs()) {
+    InvariantVars.insert(Var);
+  }
+  bool Changed = false;
+  do {
+    Changed = false;
+    for (auto NodeIndex : LoopInfo[LoopHeaderIndex]) {
+      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);
+
+  CfgVector<Inst *> InstVector(InvariantInsts.begin(), InvariantInsts.end());
+  std::sort(InstVector.begin(), InstVector.end(),
+            [](Inst *A, Inst *B) { return A->getNumber() < B->getNumber(); });
+  return InstVector;
+}
+
 void Cfg::shortCircuitJumps() {
   // Split Nodes whenever an early jump is possible.
   // __N :
   //   a = <something>
   //   Instruction 1 without side effect
   //   ... b = <something> ...
   //   Instruction N without side effect
   //   t1 = or a b
   //   br t1 __X __Y
   //
@@ skipping 678 matching lines @@
 
 // Compute the stack frame layout.
 void Cfg::genFrame() {
   TimerMarker T(TimerStack::TT_genFrame, this);
   getTarget()->addProlog(Entry);
   for (CfgNode *Node : Nodes)
     if (Node->getHasReturn())
       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
 // use of only those variables whose definition and uses are completely with a
 // single block. It is a quick single pass and doesn't need to iterate until
 // convergence.
 void Cfg::livenessLightweight() {
   TimerMarker T(TimerStack::TT_livenessLightweight, this);
   getVMetadata()->init(VMK_Uses);
   for (CfgNode *Node : Nodes)
@@ skipping 328 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice