[GVNHoist] Fix: PR35222 gvn-hoist incorrectly erases load in case of a loop

[efriedma]

There are a bunch of places in GVNHoist which call dominates (as opposed to properlyDominates), and some of them seem dubious. Are you going to audit them?

[sebpop]

This change looks good.

For the other uses of dominates, you could add an assert(dominates == properlyDominates) that would allow you to automate the extraction of testcases with bugpoint when that is not the case.
We would then have to reason on a case by case whether dominates should be changed.

[efriedma]

Ping.

[hiraditya]

In D41453#961313, @efriedma wrote:

There are a bunch of places in GVNHoist which call dominates (as opposed to properlyDominates), and some of them seem dubious. Are you going to audit them?

I'll audit them, thanks for the comment. If you can point which looks dubious to you, that'd help as well. I'll push this patch as it is and add followup patches if changes are required.

[efriedma]

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

823

This looks suspicious... specifically, it isn't clear what's supposed to happen when Inst->getParent() == HoistPt. Granted, I'm not sure that can happen.

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

for (auto Pred : predecessors(BB)) {
       for (auto It = VCHI.begin(), E = VCHI.end(); It != E;) {
         CHIArg &C = *It;
         if (!C.Dest) {
           auto si = RenameStack.find(C.VN);
           // The Basic Block where CHI is must dominate the value we want to
           // track in a CHI. In the PDom walk, there can be values in the
           // stack which are not control dependent e.g., nested loop.
           if (si != RenameStack.end() && si->second.size() &&
-              DT->dominates(Pred, si->second.back()->getParent())) {
+              DT->properlyDominates(Pred, si->second.back()->getParent())) {
             C.Dest = BB;                     // Assign the edge
             C.I = si->second.pop_back_val(); // Assign the argument
             DEBUG(dbgs() << "\nCHI Inserted in BB: " << C.Dest->getName()
                          << *C.I << ", VN: " << C.VN.first << ", "
                          << C.VN.second);
           }
           // Move to next CHI of a different value
           It = std::find_if(It, VCHI.end(),
private:
   // Return true when all operands of Instr are available at insertion point
   // HoistPt. When limiting the number of hoisted expressions, one could hoist
   // a load without hoisting its access function. So before hoisting any
   // expression, make sure that all its operands are available at insert point.
   bool allOperandsAvailable(const Instruction *I,
                             const BasicBlock *HoistPt) const {
     for (const Use &Op : I->operands())
       if (const auto *Inst = dyn_cast<Instruction>(&Op))
         if (!DT->dominates(Inst->getParent(), HoistPt))
           return false;
 
     return true;
   }
 
   // Same as allOperandsAvailable with recursive check for GEP operands.
   bool allGepOperandsAvailable(const Instruction *I,
                                const BasicBlock *HoistPt) const {

llvm/trunk/test/Transforms/GVNHoist/pr35222-hoist-load.ll

 ; RUN: opt -S -gvn-hoist < %s | FileCheck %s
+; CHECK-LABEL: build_tree
 ; CHECK: load
 ; CHECK: load
 ; Check that the load is not hoisted because the call can potentially
 ; modify the global
 
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 @heap = external global i32, align 4
 
 define i32 @build_tree() unnamed_addr {
 entry:
   br label %do.body
 
 do.body:                                          ; preds = %do.body, %entry
   %tmp9 = load i32, i32* @heap, align 4
   %cmp = call i1 @pqdownheap(i32 %tmp9)
   br i1 %cmp, label %do.body, label %do.end
 
 do.end:                                           ; preds = %do.body
   %tmp20 = load i32, i32* @heap, align 4
   ret i32 %tmp20
 }
 
 declare i1 @pqdownheap(i32)
+
+@i = external hidden unnamed_addr global i32, align 4
+@j = external hidden unnamed_addr global [573 x i32], align 4
+@v = external global i1
+
+; CHECK-LABEL: test
+; CHECK-LABEL: do.end
+; CHECK: load
+; Check that the load is not hoisted because the call can potentially
+; modify the global
+
+define i32 @test() {
+entry:
+  br label %for.cond
+
+for.cond:
+  %a3 = load volatile i1, i1* @v
+  br i1 %a3, label %for.body, label %while.end
+
+for.body:
+  br label %if.then
+
+if.then:
+  %tmp4 = load i32, i32* @i, align 4
+  br label %for.cond
+
+while.end:
+  br label %do.body
+
+do.body:
+  %tmp9 = load i32, i32* getelementptr inbounds ([573 x i32], [573 x i32]* @j,
+i32 0, i32 1), align 4
+  %tmp10 = load i32, i32* @i, align 4
+  call void @fn()
+  %a1 = load volatile i1, i1* @v
+  br i1 %a1, label %do.body, label %do.end
+
+do.end:
+  %tmp20 = load i32, i32* getelementptr inbounds ([573 x i32], [573 x i32]* @j,
+i32 0, i32 1), align 4
+  ret i32 %tmp20
+}
+
+declare void @fn()