[LICM] Use per-block hoist points when rehoisting instructions

[john.brawn]

Summary

In some cases the order that we hoist instructions in means that when rehoisting (which uses the same order as hoisting) we can rehoist to a block A, then a block B, then block A again. This currently causes an assertion failure as it expects that when changing the hoist point it only ever moves to a block that dominates the hoist point being moved from.

Fix this by having per-block hoist points, which means we can do away with the assertion.

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

810 ↗

(On Diff #176613)

If we replace HoistPoint->getParent() != Dominator with DT->dominates(Dominator, HoistPoint->getParent()), will it solve your problem?

[mkazantsev]

The entire algorithm looks non-deterministic and depends on traversal order of uses. I suggest making it deterministic (I think my comment inline should help).

[john.brawn]

Adjust according to review comments, and also add some more tests.

[mkazantsev]

LGTM

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

bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
   // that we rehoist instructions before the instructions that use them.
   Instruction *HoistPoint = nullptr;
   if (ControlFlowHoisting) {
     for (Instruction *I : reverse(HoistedInstructions)) {
       if (!llvm::all_of(I->uses(),
                         [&](Use &U) { return DT->dominates(I, U); })) {
         BasicBlock *Dominator =
             DT->getNode(I->getParent())->getIDom()->getBlock();
-        LLVM_DEBUG(dbgs() << "LICM rehoisting to " << Dominator->getName()
-                          << ": " << *I << "\n");
-        if (!HoistPoint || HoistPoint->getParent() != Dominator) {
+        if (!HoistPoint || !DT->dominates(HoistPoint->getParent(), Dominator)) {
           if (HoistPoint)
             assert(DT->dominates(Dominator, HoistPoint->getParent()) &&
                    "New hoist point expected to dominate old hoist point");
           HoistPoint = Dominator->getTerminator();
         }
+        LLVM_DEBUG(dbgs() << "LICM rehoisting to "
+                          << HoistPoint->getParent()->getName()
+                          << ": " << *I << "\n");
         moveInstructionBefore(*I, *HoistPoint, *SafetyInfo);
         HoistPoint = I;
         Changed = true;
       }
     }
   }
 
   // Now that we've finished hoisting make sure that LI and DT are still valid.

llvm/trunk/test/Transforms/LICM/hoist-phi.ll

 if.then3:
   %e = getelementptr inbounds i32, i32* %g, i64 %phi2
   store i32 1, i32* %e, align 4
   br label %loop.backedge
 
 loop.backedge:
   br label %loop
 }
+
+; The order that we hoist instructions from the loop is different to the textual
+; order in the function. Check that we can rehoist this correctly.
+; CHECK-LABEL: @rehoist_wrong_order_1
+define void @rehoist_wrong_order_1(i32* %ptr) {
+; CHECK-LABEL: entry
+; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+; CHECK-DAG: %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
+; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
+entry:
+  br label %loop
+
+; CHECK-ENABLED: [[IF1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
+
+; CHECK-ENABLED: [[ELSE1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
+
+; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
+; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
+
+; CHECK-ENABLED: [[IF3_LICM]]:
+; CHECK-ENABLED: br label %[[END_LICM]]
+
+; CHECK-ENABLED: [[END_LICM]]:
+; CHECK: br label %loop
+
+loop:
+  br i1 undef, label %if1, label %else1
+
+if1:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+  store i32 0, i32* %gep1, align 4
+  br label %loop.backedge
+
+else1:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+  store i32 0, i32* %gep2, align 4
+  br i1 undef, label %if2, label %loop.backedge
+
+if2:
+  br i1 undef, label %if3, label %end
+
+if3:
+  %gep3 = getelementptr inbounds i32, i32* %ptr, i64 3
+  store i32 0, i32* %gep3, align 4
+  br label %end
+
+end:
+  br label %loop.backedge
+
+loop.backedge:
+  br label %loop
+
+}
+
+; CHECK-LABEL: @rehoist_wrong_order_2
+define void @rehoist_wrong_order_2(i32* %ptr) {
+; CHECK-LABEL: entry
+; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+; CHECK-DAG: %gep3 = getelementptr inbounds i32, i32* %gep2, i64 3
+; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
+entry:
+  br label %loop
+
+; CHECK-ENABLED: [[IF1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM:.*]]
+
+; CHECK-ENABLED: [[ELSE1_LICM]]:
+; CHECK-ENABLED: br label %[[LOOP_BACKEDGE_LICM]]
+
+; CHECK-ENABLED: [[LOOP_BACKEDGE_LICM]]:
+; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
+
+; CHECK-ENABLED: [[IF3_LICM]]:
+; CHECK-ENABLED: br label %[[END_LICM]]
+
+; CHECK-ENABLED: [[END_LICM]]:
+; CHECK: br label %loop
+
+loop:
+  br i1 undef, label %if1, label %else1
+
+if1:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+  store i32 0, i32* %gep1, align 4
+  br label %loop.backedge
+
+else1:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+  store i32 0, i32* %gep2, align 4
+  br i1 undef, label %if2, label %loop.backedge
+
+if2:
+  br i1 undef, label %if3, label %end
+
+if3:
+  %gep3 = getelementptr inbounds i32, i32* %gep2, i64 3
+  store i32 0, i32* %gep3, align 4
+  br label %end
+
+end:
+  br label %loop.backedge
+
+loop.backedge:
+  br label %loop
+}
+
+; CHECK-LABEL: @rehoist_wrong_order_3
+define void @rehoist_wrong_order_3(i32* %ptr) {
+; CHECK-LABEL: entry
+; CHECK-DAG: %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+; CHECK-DAG: %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+; CHECK-ENABLED: br i1 undef, label %[[IF1_LICM:.*]], label %[[ELSE1_LICM:.*]]
+entry:
+  br label %loop
+
+; CHECK-ENABLED: [[IF1_LICM]]:
+; CHECK-ENABLED: br label %[[IF2_LICM:.*]]
+
+; CHECK-ENABLED: [[ELSE1_LICM]]:
+; CHECK-ENABLED: br label %[[IF2_LICM]]
+
+; CHECK-ENABLED: [[IF2_LICM]]:
+; CHECK-ENABLED: %phi = phi i32* [ %gep1, %[[IF1_LICM]] ], [ %gep2, %[[ELSE1_LICM]] ]
+; CHECK-ENABLED: %gep3 = getelementptr inbounds i32, i32* %phi, i64 3
+; CHECK-ENABLED: br i1 undef, label %[[IF3_LICM:.*]], label %[[END_LICM:.*]]
+
+; CHECK-ENABLED: [[IF3_LICM]]:
+; CHECK-ENABLED: br label %[[END_LICM]]
+
+; CHECK-ENABLED: [[END_LICM]]:
+; CHECK: br label %loop
+
+loop:
+  br i1 undef, label %if1, label %else1
+
+if1:
+  %gep1 = getelementptr inbounds i32, i32* %ptr, i64 1
+  store i32 0, i32* %gep1, align 4
+  br label %if2
+
+else1:
+  %gep2 = getelementptr inbounds i32, i32* %ptr, i64 2
+  store i32 0, i32* %gep2, align 4
+  br i1 undef, label %if2, label %loop.backedge
+
+if2:
+  %phi = phi i32* [ %gep1, %if1 ], [ %gep2, %else1 ]
+  br i1 undef, label %if3, label %end
+
+if3:
+  %gep3 = getelementptr inbounds i32, i32* %phi, i64 3
+  store i32 0, i32* %gep3, align 4
+  br label %end
+
+end:
+  br label %loop.backedge
+
+loop.backedge:
+  br label %loop
+}