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() {

[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 :
   //   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