GVN-hoist: use DFS numbers instead of walking the instruction stream

[sebpop]

Summary

The patch replaces a function that walks the IR with a call to firstInBB() that uses the DFS numbering.

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

bool allOperandsAvailable(const Instruction *I,
     for (const Use &Op : I->operands())
       if (const auto *Inst = dyn_cast<Instruction>(&Op))
         if (!DT->dominates(Inst->getParent(), HoistPt))
           return false;
 
     return true;
   }
 
-  Instruction *firstOfTwo(Instruction *I, Instruction *J) const {
-    for (Instruction &I1 : *I->getParent())
-      if (&I1 == I || &I1 == J)
-        return &I1;
-    llvm_unreachable("Both I and J must be from same BB");
-  }
-
   bool makeOperandsAvailable(Instruction *Repl, BasicBlock *HoistPt,
                              const SmallVecInsn &InstructionsToHoist) const {
     // Check whether the GEP of a ld/st can be synthesized at HoistPt.
     GetElementPtrInst *Gep = nullptr;
     Instruction *Val = nullptr;
     if (auto *Ld = dyn_cast<LoadInst>(Repl))
       Gep = dyn_cast<GetElementPtrInst>(Ld->getPointerOperand());
     if (auto *St = dyn_cast<StoreInst>(Repl)) {
std::pair<unsigned, unsigned> hoist(HoistingPointList &HPL) {
     unsigned NI = 0, NL = 0, NS = 0, NC = 0, NR = 0;
     for (const HoistingPointInfo &HP : HPL) {
       // Find out whether we already have one of the instructions in HoistPt,
       // in which case we do not have to move it.
       BasicBlock *HoistPt = HP.first;
       const SmallVecInsn &InstructionsToHoist = HP.second;
       Instruction *Repl = nullptr;
       for (Instruction *I : InstructionsToHoist)
-        if (I->getParent() == HoistPt) {
+        if (I->getParent() == HoistPt)
           // If there are two instructions in HoistPt to be hoisted in place:
           // update Repl to be the first one, such that we can rename the uses
           // of the second based on the first.
-          Repl = !Repl ? I : firstOfTwo(Repl, I);
-        }
+          if (!Repl || firstInBB(I, Repl))
+            Repl = I;
 
       if (Repl) {
         // Repl is already in HoistPt: it remains in place.
         assert(allOperandsAvailable(Repl, HoistPt) &&
                "instruction depends on operands that are not available");
       } else {
         // When we do not find Repl in HoistPt, select the first in the list
         // and move it to HoistPt.