GVN-hoist: compute DFS numbers once

[sebpop]

Summary

With this patch we compute the DFS numbers of instructions only once and update them during the code generation when an instruction gets hoisted.
Passes check and test-suite on x86_64-linux.

llvm/trunk/lib/Transforms/Scalar/GVNHoist.cpp

public:
   bool operator()(const Instruction *A, const Instruction *B) const {
     // FIXME: libc++ has a std::sort() algorithm that will call the compare
     // function on the same element.  Once PR20837 is fixed and some more years
     // pass by and all the buildbots have moved to a corrected std::sort(),
     // enable the following assert:
     //
     // assert(A != B);
 
-    unsigned ADFS = DFSNumber.lookup(A);
-    unsigned BDFS = DFSNumber.lookup(B);
+    const BasicBlock *BA = A->getParent();
+    const BasicBlock *BB = B->getParent();
+    unsigned ADFS, BDFS;
+    if (BA == BB) {
+      ADFS = DFSNumber.lookup(A);
+      BDFS = DFSNumber.lookup(B);
+    } else {
+      ADFS = DFSNumber.lookup(BA);
+      BDFS = DFSNumber.lookup(BB);
+    }
     assert (ADFS && BDFS);
     return ADFS < BDFS;
   }
 };
 
 // A map from a pair of VNs to all the instructions with those VNs.
 typedef DenseMap<std::pair<unsigned, unsigned>, SmallVector<Instruction *, 4>>
     VNtoInsns;
GVNHoist(DominatorTree *Dt, AliasAnalysis *Aa, MemoryDependenceResults *Md,
         HoistingGeps(OptForMinSize), HoistedCtr(0) {}
   bool run(Function &F) {
     VN.setDomTree(DT);
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;
     MemorySSA M(F, AA, DT);
     MSSA = &M;
-
-    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
-    while (1) {
-      // Perform DFS Numbering of instructions.
+    unsigned BBI = 0;
+    for (const BasicBlock *BB : depth_first(&F.getEntryBlock())) {
+      DFSNumber[BB] = ++BBI;
       unsigned I = 0;
-      for (const BasicBlock *BB : depth_first(&F.getEntryBlock()))
-        for (auto &Inst: *BB)
-          DFSNumber.insert({&Inst, ++I});
+        DFSNumber[&Inst] = ++I;
+    }
 
+    // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
+    while (1) {
       auto HoistStat = hoistExpressions(F);
       if (HoistStat.first + HoistStat.second == 0)
         return Res;
 
       if (HoistStat.second > 0)
         // To address a limitation of the current GVN, we need to rerun the
         // hoisting after we hoisted loads or stores in order to be able to
         // hoist all scalars dependent on the hoisted ld/st.
         VN.clear();
 
       Res = true;
-
-      // DFS numbers change when instructions are hoisted: clear and recompute.
-      DFSNumber.clear();
     }
 
     return Res;
   }
 private:
   GVN::ValueTable VN;
   DominatorTree *DT;
   AliasAnalysis *AA;
for (const HoistingPointInfo &HP : HPL) {
         // When not HoistingGeps we need to copy the GEPs now.
         // The order in which hoistings are done may influence the availability
         // of operands.
         if (!allOperandsAvailable(Repl, HoistPt) && !HoistingGeps &&
             !makeGepOperandsAvailable(Repl, HoistPt, InstructionsToHoist))
           continue;
 
         // Move the instruction at the end of HoistPt.
-        Repl->moveBefore(HoistPt->getTerminator());
+        Instruction *Last = HoistPt->getTerminator();
+        Repl->moveBefore(Last);
+
+        DFSNumber[Repl] = DFSNumber[Last]++;
       }
 
       MemoryAccess *NewMemAcc = nullptr;
       if (MemoryAccess *MA = MSSA->getMemoryAccess(Repl)) {
         if (MemoryUseOrDef *OldMemAcc = dyn_cast<MemoryUseOrDef>(MA)) {
           // The definition of this ld/st will not change: ld/st hoisting is
           // legal when the ld/st is not moved past its current definition.
           MemoryAccess *Def = OldMemAcc->getDefiningAccess();