[SimplifyCFG] Improve the way hoisting skips over non-matching instructions

[foad]

Summary

D129370 introduced the idea that hoisting could skip over non-matching
instructions and continue to look for matching (hoistable) instructions,
but certain types of mismatch still aborted the whole hoisting attempt.

Fix this by splitting out some of the instruction matching checks into a
helper function.

Also forbid hoisting allocas past stacksave/stackrestore, completing the
fix started in D133730, to avoid regressing tests.

[foad]

llvm/test/Transforms/SimplifyCFG/hoist-common-skip.ll

394 ↗

(On Diff #517654)

This looks wrong since this alloca was hoisted past a stacksave. D133730 was supposed to prevent this, according to its description, but in fact it only seems to prevent the converse: hoisting a stacksave past an alloca. @aeubanks

[efriedma]

llvm/test/Transforms/SimplifyCFG/hoist-common-skip.ll

394 ↗

(On Diff #517654)

Forbidding hoisting allocas past side-effects seems appropriate, yes. Should be straightforward.

[foad]

Forbid hoisting allocas past stacksave/stackrestore.

[nikic]

LG

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 static bool isSafeToHoistInstr(Instruction *I, unsigned Flags) {
   // Don't reorder a store over a load.
   if ((Flags & SkipReadMem) && I->mayWriteToMemory())
     return false;
 
   // If we have seen an instruction with side effects, it's unsafe to reorder an
   // instruction which reads memory or itself has side effects.
   if ((Flags & SkipSideEffect) &&
-      (I->mayReadFromMemory() || I->mayHaveSideEffects()))
+      (I->mayReadFromMemory() || I->mayHaveSideEffects() || isa<AllocaInst>(I)))
     return false;
 
   // Reordering across an instruction which does not necessarily transfer
   // control to the next instruction is speculation.
   if ((Flags & SkipImplicitControlFlow) && !isSafeToSpeculativelyExecute(I))
     return false;
 
   // Hoisting of llvm.deoptimize is only legal together with the next return
if (auto *J = dyn_cast<Instruction>(Op))
         return false;
   }
 
   return true;
 }
 
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified = false);
 
+/// Helper function for HoistThenElseCodeToIf. Return true if identical
+/// instructions \p I1 and \p I2 can and should be hoisted.
+static bool shouldHoistCommonInstructions(Instruction *I1, Instruction *I2,
+                                          const TargetTransformInfo &TTI) {
+  // If we're going to hoist a call, make sure that the two instructions
+  // we're commoning/hoisting are both marked with musttail, or neither of
+  // them is marked as such. Otherwise, we might end up in a situation where
+  // we hoist from a block where the terminator is a `ret` to a block where
+  // the terminator is a `br`, and `musttail` calls expect to be followed by
+  // a return.
+  auto *C1 = dyn_cast<CallInst>(I1);
+  auto *C2 = dyn_cast<CallInst>(I2);
+  if (C1 && C2)
+    if (C1->isMustTailCall() != C2->isMustTailCall())
+      return false;
+
+  if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
+    return false;
+
+  // If any of the two call sites has nomerge or convergent attribute, stop
+  // hoisting.
+  if (const auto *CB1 = dyn_cast<CallBase>(I1))
+    if (CB1->cannotMerge() || CB1->isConvergent())
+      return false;
+  if (const auto *CB2 = dyn_cast<CallBase>(I2))
+    if (CB2->cannotMerge() || CB2->isConvergent())
+      return false;
+
+  return true;
+}
+
 /// Given a conditional branch that goes to BB1 and BB2, hoist any common code
 /// in the two blocks up into the branch block. The caller of this function
 /// guarantees that BI's block dominates BB1 and BB2. If EqTermsOnly is given,
 /// only perform hoisting in case both blocks only contain a terminator. In that
 /// case, only the original BI will be replaced and selects for PHIs are added.
 bool SimplifyCFGOpt::HoistThenElseCodeToIf(BranchInst *BI, bool EqTermsOnly) {
   // This does very trivial matching, with limited scanning, to find identical
   // instructions in the two blocks.  In particular, we don't want to get into
for (;;) {
     // broken BB), instead clone it, and remove BI.
     if (I1->isTerminator() || I2->isTerminator()) {
       // If any instructions remain in the block, we cannot hoist terminators.
       if (NumSkipped || !I1->isIdenticalToWhenDefined(I2))
         return Changed;
       goto HoistTerminator;
     }
 
-    if (I1->isIdenticalToWhenDefined(I2)) {
+    if (I1->isIdenticalToWhenDefined(I2) &&
         // Even if the instructions are identical, it may not be safe to hoist
         // them if we have skipped over instructions with side effects or their
         // operands weren't hoisted.
-      if (!isSafeToHoistInstr(I1, SkipFlagsBB1) ||
-          !isSafeToHoistInstr(I2, SkipFlagsBB2))
-        return Changed;
-
-      // If we're going to hoist a call, make sure that the two instructions
-      // we're commoning/hoisting are both marked with musttail, or neither of
-      // them is marked as such. Otherwise, we might end up in a situation where
-      // we hoist from a block where the terminator is a `ret` to a block where
-      // the terminator is a `br`, and `musttail` calls expect to be followed by
-      // a return.
-      auto *C1 = dyn_cast<CallInst>(I1);
-      auto *C2 = dyn_cast<CallInst>(I2);
-      if (C1 && C2)
-        if (C1->isMustTailCall() != C2->isMustTailCall())
-          return Changed;
-
-      if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
-        return Changed;
-
-      // If any of the two call sites has nomerge or convergent attribute, stop
-      // hoisting.
-      if (const auto *CB1 = dyn_cast<CallBase>(I1))
-        if (CB1->cannotMerge() || CB1->isConvergent())
-          return Changed;
-      if (const auto *CB2 = dyn_cast<CallBase>(I2))
-        if (CB2->cannotMerge() || CB2->isConvergent())
-          return Changed;
-
+        isSafeToHoistInstr(I1, SkipFlagsBB1) &&
+        isSafeToHoistInstr(I2, SkipFlagsBB2) &&
+        shouldHoistCommonInstructions(I1, I2, TTI)) {
       if (isa<DbgInfoIntrinsic>(I1) || isa<DbgInfoIntrinsic>(I2)) {
         assert(isa<DbgInfoIntrinsic>(I1) && isa<DbgInfoIntrinsic>(I2));
         // The debug location is an integral part of a debug info intrinsic
         // and can't be separated from it or replaced.  Instead of attempting
         // to merge locations, simply hoist both copies of the intrinsic.
         BIParent->splice(BI->getIterator(), BB1, I1->getIterator());
         BIParent->splice(BI->getIterator(), BB2, I2->getIterator());
       } else {

llvm/test/Transforms/SimplifyCFG/convergent.ll

 ; NOSINK:       if.end:
 ; NOSINK-NEXT:    ret void
 ;
 ; SINK-LABEL: @test_02(
 ; SINK-NEXT:  entry:
 ; SINK-NEXT:    [[TMP0:%.*]] = tail call i32 @tid()
 ; SINK-NEXT:    [[REM:%.*]] = and i32 [[TMP0]], 1
 ; SINK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i32 [[REM]], 0
+; SINK-NEXT:    [[IDXPROM4:%.*]] = zext i32 [[TMP0]] to i64
+; SINK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i32, ptr [[Y_COERCE:%.*]], i64 [[IDXPROM4]]
 ; SINK-NEXT:    br i1 [[CMP_NOT]], label [[IF_ELSE:%.*]], label [[IF_THEN:%.*]]
 ; SINK:       if.then:
 ; SINK-NEXT:    [[TMP1:%.*]] = tail call i32 @mbcnt(i32 -1, i32 0)
 ; SINK-NEXT:    [[TMP2:%.*]] = tail call i32 @mbcnt(i32 -1, i32 [[TMP1]])
 ; SINK-NEXT:    [[AND_I:%.*]] = shl i32 [[TMP2]], 2
 ; SINK-NEXT:    [[ADD_I:%.*]] = and i32 [[AND_I]], -256
 ; SINK-NEXT:    [[SHL_I:%.*]] = or i32 [[ADD_I]], 16
 ; SINK-NEXT:    [[TMP3:%.*]] = tail call i32 @bpermute(i32 [[SHL_I]], i32 [[TMP0]])
 ; SINK-NEXT:    br label [[IF_END:%.*]]
 ; SINK:       if.else:
 ; SINK-NEXT:    [[TMP4:%.*]] = tail call i32 @mbcnt(i32 -1, i32 0)
 ; SINK-NEXT:    [[TMP5:%.*]] = tail call i32 @mbcnt(i32 -1, i32 [[TMP4]])
 ; SINK-NEXT:    [[AND_I11:%.*]] = shl i32 [[TMP5]], 2
 ; SINK-NEXT:    [[ADD_I12:%.*]] = and i32 [[AND_I11]], -256
 ; SINK-NEXT:    [[SHL_I13:%.*]] = or i32 [[ADD_I12]], 8
 ; SINK-NEXT:    [[TMP6:%.*]] = tail call i32 @bpermute(i32 [[SHL_I13]], i32 [[TMP0]])
 ; SINK-NEXT:    br label [[IF_END]]
 ; SINK:       if.end:
 ; SINK-NEXT:    [[DOTSINK:%.*]] = phi i32 [ [[TMP6]], [[IF_ELSE]] ], [ [[TMP3]], [[IF_THEN]] ]
-; SINK-NEXT:    [[IDXPROM4:%.*]] = zext i32 [[TMP0]] to i64
-; SINK-NEXT:    [[ARRAYIDX5:%.*]] = getelementptr inbounds i32, ptr [[Y_COERCE:%.*]], i64 [[IDXPROM4]]
 ; SINK-NEXT:    store i32 [[DOTSINK]], ptr [[ARRAYIDX5]], align 4
 ; SINK-NEXT:    ret void
 ;
 entry:
   %0 = tail call i32 @tid()
   %rem = and i32 %0, 1
   %cmp.not = icmp eq i32 %rem, 0
   br i1 %cmp.not, label %if.else, label %if.then