[LICM] Store sink and indirectbr instructions

[bruno]

Summary

Loop simplify skips exit-block insertion when exits contain indirectbr instructions. This
leads to an assertion in LICM when trying to sink stores out of non-dedicated loop exits
containing indirectbr instructions. This patch fix this issue by re-checking for dedicated
exits in LICM prior to store sink attempts.

[hfinkel]

LGTM, thanks!

Maybe LoopSimplify should create a dedicated exit block for loops like this, but that's another matter, and this seems like a reasonable change regardless (we shouldn't be sinking stores into non-dedicated exit blocks).

[bruno]

Hi Hal,

Agreed. As a side note, this all happens because LoopSimplify avoids dealing with indirectbr instructions at all and therefore won't create dedicated exit blocks nor pre-headers in their presence. Haven't check yet but it's likey a similar crash will happen for loads when indirectbr is involved since there won't be a preheader to hoist out.

Thanks for the review!

[bruno]

Commited in r 222927

lib/Transforms/Scalar/LICM.cpp

void LICM::PromoteAliasSet(AliasSet &AS,
 
   SmallVector<Instruction*, 64> LoopUses;
   SmallPtrSet<Value*, 4> PointerMustAliases;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   unsigned Alignment = 1;
   AAMDNodes AATags;
+  bool HasDedicatedExits = CurLoop->hasDedicatedExits();
 
   // Check that all of the pointers in the alias set have the same type.  We
   // cannot (yet) promote a memory location that is loaded and stored in
   // different sizes.  While we are at it, collect alignment and AA info.
   for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
     Value *ASIV = ASI->getValue();
     PointerMustAliases.insert(ASIV);
 
for (User *U : ASIV->users()) {
       } else if (StoreInst *store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
         assert(!store->isVolatile() && "AST broken");
         if (!store->isSimple())
           return;
+        // Don't sink stores from loops without dedicated block exits. Exits
+        // containing indirect branches are not transformed by loop simplify,
+        // make sure we catch that.
+        if (!HasDedicatedExits)
+          return;
 
         // Note that we only check GuaranteedToExecute inside the store case
         // so that we do not introduce stores where they did not exist before
         // (which would break the LLVM concurrency model).
 
         // If the alignment of this instruction allows us to specify a more
         // restrictive (and performant) alignment and if we are sure this
         // instruction will be executed, update the alignment.

test/Transforms/LICM/sinking.ll

 ; CHECK:       exit:
 ; CHECK-NEXT:    %[[LCSSAPHI:.*]] = phi i64 [ %iv, %l4.latch ], [ %iv, %l4.body ]
 ; CHECK-NEXT:    %l.le = trunc i64 %[[LCSSAPHI]] to i32
 ; CHECK-NEXT:    ret i32 %l.le
 
   ret i32 %lcssa
 }
 
+; Can't sink stores out of exit blocks containing indirectbr instructions
+; because loop simplify does not create dedicated exits for such blocks. Test
+; that by sinking the store from lab21 to lab22, but not further.
+define void @test12() {
+; CHECK-LABEL: @test12
+  br label %lab4
+
+lab4:
+  br label %lab20
+
+lab5:
+  br label %lab20
+
+lab6:
+  br label %lab4
+
+lab7:
+  br i1 undef, label %lab8, label %lab13
+
+lab8:
+  br i1 undef, label %lab13, label %lab10
+
+lab10:
+  br label %lab7
+
+lab13:
+  ret void
+
+lab20:
+  br label %lab21
+
+lab21:
+; CHECK: lab21:
+; CHECK-NOT: store
+; CHECK: br i1 false, label %lab21, label %lab22
+  store i32 36127957, i32* undef, align 4
+  br i1 undef, label %lab21, label %lab22
+
+lab22:
+; CHECK: lab22:
+; CHECK: store
+; CHECK-NEXT: indirectbr i8* undef
+  indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]
+}
+
 declare void @f(i32*)
 
 declare void @g()