GVN-hoist: use a DFS numbering of instructions (PR28670)

[sebpop]

Summary

Instead of DFS numbering basic blocks we now DFS number instructions that avoids the costly operation of which instruction comes first in a basic block.

Patch mostly written by Daniel Berlin.

[• dberlin]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

787

Oh, this is the part i forgot :)
Oh well.

One thought:

If we are always inserting at the end of a block (i didn't look), btw, we'd be better off having a per-block numbering.

If we make "I" (here) a member variable called LastDFSNumber, we can then just update the per-block numberings by using ++LastDFSNumber as the number for the hoisted instruction. This avoids walking the instruction stream again on every iteration.

llvm/test/Transforms/GVN/hoist.ll

638

So wait, this hoists more than we did before?

[sebpop]

llvm/lib/Transforms/Scalar/GVNHoist.cpp

787

Yes, that would work.
I was also thinking along the lines of how we locally update the MSSA, we could also locally update the DFS numbers.
In that case we should compute both a DFS for BBs that will not change with hoisting, and then a DFS for instructions local to a BB and we could locally patch when hoisting instructions.

llvm/test/Transforms/GVN/hoist.ll

638

No. I added this missing gep because I changed the CHECK into a CHECK-NEXT, and we now pattern match all the basic block where we hoist.

[• dberlin]

Gotcha.
We should land this and then update the DFS numbers in the patch where do you MSSA updates.

llvm/lib/Transforms/Scalar/GVNHoist.cpp

static cl::opt<int> MaxDepthInBB(
     cl::desc("Hoist instructions from the beginning of the BB up to the "
              "maximum specified depth (default = 100, unlimited = -1)"));
 
 namespace {
 
 // Provides a sorting function based on the execution order of two instructions.
 struct SortByDFSIn {
 private:
-  DenseMap<const BasicBlock *, unsigned> &DFSNumber;
+  DenseMap<const Value *, unsigned> &DFSNumber;
 
 public:
-  SortByDFSIn(DenseMap<const BasicBlock *, unsigned> &D) : DFSNumber(D) {}
+  SortByDFSIn(DenseMap<const Value *, unsigned> &D) : DFSNumber(D) {}
 
   // Returns true when A executes before B.
   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);
 
-    const BasicBlock *BA = A->getParent();
-    const BasicBlock *BB = B->getParent();
-    unsigned NA = DFSNumber[BA];
-    unsigned NB = DFSNumber[BB];
-    if (NA < NB)
-      return true;
-    if (NA == NB) {
-      // Sort them in the order they occur in the same basic block.
-      BasicBlock::const_iterator AI(A), BI(B);
-      return std::distance(AI, BI) < 0;
-    }
-    return false;
+    unsigned ADFS = DFSNumber.lookup(A);
+    unsigned BDFS = DFSNumber.lookup(B);
+    assert (ADFS && ADFS);
+    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;
 // An invalid value number Used when inserting a single value number into
 // VNtoInsns.

 // cases reduce critical path (by exposing more ILP).
 class GVNHoist {
 public:
   GVN::ValueTable VN;
   DominatorTree *DT;
   AliasAnalysis *AA;
   MemoryDependenceResults *MD;
   const bool OptForMinSize;
-  DenseMap<const BasicBlock *, unsigned> DFSNumber;
+  DenseMap<const Value *, unsigned> DFSNumber;
   BBSideEffectsSet BBSideEffects;
   MemorySSA *MSSA;
   int HoistedCtr;
 
   enum InsKind { Unknown, Scalar, Load, Store };
 
   GVNHoist(DominatorTree *Dt, AliasAnalysis *Aa, MemoryDependenceResults *Md,
            bool OptForMinSize)
for (auto It = df_begin(A), E = df_end(A); It != E;) {
       // Increment DFS traversal when not skipping children.
       ++It;
     }
 
     return true;
   }
 
   /* Return true when I1 appears before I2 in the instructions of BB.  */
-  bool firstInBB(BasicBlock *BB, const Instruction *I1, const Instruction *I2) {
-    for (Instruction &I : *BB) {
-      if (&I == I1)
-        return true;
-      if (&I == I2)
-        return false;
-    }
+  bool firstInBB(const Instruction *I1, const Instruction *I2) {
+    assert (I1->getParent() == I2->getParent());
+    unsigned I1DFS = DFSNumber.lookup(I1);
+    unsigned I2DFS = DFSNumber.lookup(I2);
+    assert (I1DFS && I2DFS);
+    return I1DFS < I2DFS;
 
-    llvm_unreachable("I1 and I2 not found in BB");
-  }
   // Return true when there are users of Def in BB.
   bool hasMemoryUseOnPath(MemoryAccess *Def, const BasicBlock *BB,
                           const Instruction *OldPt) {
     const BasicBlock *DefBB = Def->getBlock();
     const BasicBlock *OldBB = OldPt->getParent();
 
     for (User *U : Def->users())
       if (auto *MU = dyn_cast<MemoryUse>(U)) {
         BasicBlock *UBB = MU->getBlock();
         // Only analyze uses in BB.
         if (BB != UBB)
           continue;
 
         // A use in the same block as the Def is on the path.
         if (UBB == DefBB) {
           assert(MSSA->locallyDominates(Def, MU) && "def not dominating use");
           return true;
         }
 
         if (UBB != OldBB)
           return true;
 
         // It is only harmful to hoist when the use is before OldPt.
-        if (firstInBB(UBB, MU->getMemoryInst(), OldPt))
+        if (firstInBB(MU->getMemoryInst(), OldPt))
           return true;
       }
 
     return false;
   }
 
   // Return true when there are exception handling or loads of memory Def
   // between OldPt and NewPt.
bool safeToHoistLdSt(const Instruction *NewPt, const Instruction *OldPt,
     MemoryAccess *D = U->getDefiningAccess();
     BasicBlock *DBB = D->getBlock();
     if (DT->properlyDominates(NewBB, DBB))
       // Cannot move the load or store to NewBB above its definition in DBB.
       return false;
 
     if (NewBB == DBB && !MSSA->isLiveOnEntryDef(D))
       if (auto *UD = dyn_cast<MemoryUseOrDef>(D))
-        if (firstInBB(DBB, NewPt, UD->getMemoryInst()))
+        if (firstInBB(NewPt, UD->getMemoryInst()))
           // Cannot move the load or store to NewPt above its definition in D.
           return false;
 
     // Check for unsafe hoistings due to side effects.
     if (K == InsKind::Store) {
       if (hasEHOrLoadsOnPath(NewPt, OldPt, D, NBBsOnAllPaths))
         return false;
     } else if (hasEHOnPath(NewBB, OldBB, NBBsOnAllPaths))
void partitionCandidates(SmallVecImplInsn &InstructionsToHoist,
     for (++II; II != InstructionsToHoist.end(); ++II) {
       Instruction *Insn = *II;
       BasicBlock *BB = Insn->getParent();
       BasicBlock *NewHoistBB;
       Instruction *NewHoistPt;
 
       if (BB == HoistBB) {
         NewHoistBB = HoistBB;
-        NewHoistPt = firstInBB(BB, Insn, HoistPt) ? Insn : HoistPt;
+        NewHoistPt = firstInBB(Insn, HoistPt) ? Insn : HoistPt;
       } else {
         NewHoistBB = DT->findNearestCommonDominator(HoistBB, BB);
         if (NewHoistBB == BB)
           NewHoistPt = Insn;
         else if (NewHoistBB == HoistBB)
           NewHoistPt = HoistPt;
         else
           NewHoistPt = NewHoistBB->getTerminator();
public:
   }
 
   bool run(Function &F) {
     VN.setDomTree(DT);
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;
 
-    unsigned I = 0;
-    for (const BasicBlock *BB : depth_first(&F.getEntryBlock()))
-      DFSNumber.insert({BB, ++I});
-
     // FIXME: use lazy evaluation of VN to avoid the fix-point computation.
     while (1) {
       // FIXME: only compute MemorySSA once. We need to update the analysis in
       // the same time as transforming the code.
       MemorySSA M(F, AA, DT);
       MSSA = &M;
 
+      // Perform DFS Numbering of instructions.
+      unsigned I = 0;
+      for (const BasicBlock *BB : depth_first(&F.getEntryBlock()))
+        for (auto &Inst: *BB)
+          DFSNumber.insert({&Inst, ++I});
+
       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 in order to be able to hoist all
         // scalars dependent on the hoisted loads. Same for stores.
         VN.clear();
       }
       Res = true;
+
+      // DFS numbers change when instructions are hoisted: clear and recompute.
+      DFSNumber.clear();
     }
 
     return Res;
   }
 };
 
 class GVNHoistLegacyPass : public FunctionPass {
 public:

llvm/test/Transforms/GVN/hoist.ll

if.end:
   %add = fadd float %tmax.0, %tmin.0
   ret float %add
 }
 
 ; Check that we hoist stores: all the instructions from the then branch
 ; should be hoisted.
 ; CHECK-LABEL: @hoistStores
 ; CHECK: zext
-; CHECK: trunc
-; CHECK: getelementptr
-; CHECK: load
-; CHECK: getelementptr
-; CHECK: store
-; CHECK: load
-; CHECK: load
-; CHECK: zext
-; CHECK: add
-; CHECK: store
-; CHECK: br
+; CHECK-NEXT: trunc
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: load
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: store
+; CHECK-NEXT: load
+; CHECK-NEXT: load
+; CHECK-NEXT: zext
+; CHECK-NEXT: add
+; CHECK-NEXT: store
+; CHECK-NEXT: br
 ; CHECK: if.then
 ; CHECK: br
 
 %struct.foo = type { i16* }
 
 define void @hoistStores(%struct.foo* %s, i32* %coord, i1 zeroext %delta) {
 entry:
   %frombool = zext i1 %delta to i8