[InstCombine] Teach PromoteCastOfAllocation to not insert a bitcast into the middle of a group of allocas

[craig.topper]

Summary

Alloca's are usually grouped together at the top of the entry block. We shouldn't insert other instructions between them.

Fixes the weird IR seen in the stack coloring pass here http://lists.llvm.org/pipermail/llvm-dev/2020-May/141421.html StackColoring should probably also be fixed to handle this better too, but I didn't look into it any further.

[jdoerfert]

FWIW, I don't think we have the alloca grouping as a rigorous requirement. Without doing that, which basically means teaching the verifier and putting it the lang ref, this might be(come) a long term game of whack-a-mole.

That said, I don't have a problem with the patch, just want to mention that this might not be the way we want to go. I mean, let's go all in on the grouping or not at all.

[efriedma]

I'm not sure we really want to go down this path. We can't reliably guarantee that all static allocas are at the beginning of the entry block; this fix will just make it slightly hard to trip over any resulting issues.

[craig.topper]

FWIW, there's another place in InstCombine that does something like this, simplifyAllocaArraySize in InstCombineLoadStoreAlloca.cpp So I thought maybe this was desired behavior.

[jdoerfert]

In D79956#2037134, @craig.topper wrote:

FWIW, there's another place in InstCombine that does something like this, simplifyAllocaArraySize in InstCombineLoadStoreAlloca.cpp So I thought maybe this was desired behavior.

I saw multiple places over the years. I also heard from people they think there is some kind of guarantee or canonical form that the allocas are in the beginning and grouped. I don't think there is, e.g., I checked the other day and SROA scans the entire entry block.

Personally, I'd say we need to fix the passes to deal with this. But I do not have a strong opinion.

[craig.topper]

So for the originally reported issue, it looks like in StackColoring::remapInstructions To is later than From in the basic block. And there's a use of From between them. So when From is replaced with To we create bad IR. So we need to move To to From if From is earlier? Or if there is a user of From that's earlier than To? I think the code does walk all uses of From already.

[jdoerfert]

In D79956#2037264, @craig.topper wrote:

So for the originally reported issue, it looks like in StackColoring::remapInstructions To is later than From in the basic block. And there's a use of From between them. So when From is replaced with To we create bad IR. So we need to move To to From if From is earlier? Or if there is a user of From that's earlier than To? I think the code does walk all uses of From already.

It is not wrong for StackColoring to "just" move allocas to the beginning of a block (first insert point probably), even eagerly. Or, less invasive, maybe something like this:

    const AllocaInst *From = MFI->getObjectAllocation(SI.first);
    const AllocaInst *To = MFI->getObjectAllocation(SI.second);
✚   if (!From->comesBefore(To))                                                                                                                                                                   
✚    const_cast<AllocaInst*>(From)->moveBefore(const_cast<AllocaInst*>(To));

EDIT: Without looking at the rest of the code, the order property is not "directly" tied to the grouping property. So while one might imply the other it seems to be a safer way to really test/ensure the property we need here.

[craig.topper]

Will try to fix stack coloring instead

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,
   New->setUsedWithInAlloca(AI.isUsedWithInAlloca());
 
   // If the allocation has multiple real uses, insert a cast and change all
   // things that used it to use the new cast.  This will also hack on CI, but it
   // will die soon.
   if (!AI.hasOneUse()) {
     // New is the allocation instruction, pointer typed. AI is the original
     // allocation instruction, also pointer typed. Thus, cast to use is BitCast.
+
+    // Scan to the end of the allocation instructions, to avoid inserting
+    // in the middle of a block of allocas.
+    BasicBlock::iterator It(New);
+    while (isa<AllocaInst>(*It))
+      ++It;
+    Builder.SetInsertPoint(&*It);
+
     Value *NewCast = Builder.CreateBitCast(New, AI.getType(), "tmpcast");
     replaceInstUsesWith(AI, NewCast);
     eraseInstFromFunction(AI);
   }
   return replaceInstUsesWith(CI, New);
 }
 
 /// Given an expression that CanEvaluateTruncated or CanEvaluateSExtd returns

llvm/test/Transforms/InstCombine/alloca.ll

 ; ALL-LABEL: @test11(
 ; ALL: %y = alloca i32
 ; ALL: call void (...) @use(i32* nonnull @int) [ "blah"(i32* %y) ]
 ; ALL: ret void
   %y = alloca i32
   call void (...) @use(i32* nonnull @int) [ "blah"(i32* %y) ]
   ret void
 }
+
+%struct.pluto = type { [4 x float] }
+%struct.bar = type { [4 x i32*] }
+
+; Make sure we put the TMPCAST bitcast  after the allocas not between.
+define void @test12(<2 x float> %arg) {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP1:%.*]] = alloca { <2 x float>, <2 x float> }, align 8
+; CHECK-NEXT:    [[TMP:%.*]] = alloca [[STRUCT_BAR:%.*]], align 8
+; CHECK-NEXT:    [[TMPCAST:%.*]] = bitcast { <2 x float>, <2 x float> }* [[TMP1]] to %struct.pluto*
+; CHECK-NEXT:    [[TMP5:%.*]] = getelementptr inbounds { <2 x float>, <2 x float> }, { <2 x float>, <2 x float> }* [[TMP1]], i64 0, i32 0
+; CHECK-NEXT:    store <2 x float> [[ARG:%.*]], <2 x float>* [[TMP5]], align 8
+; CHECK-NEXT:    call void @snork(%struct.bar* nonnull [[TMP]], %struct.pluto* nonnull [[TMPCAST]])
+; CHECK-NEXT:    ret void
+bb:
+  %tmp1 = alloca %struct.pluto, align 4
+  %tmp = alloca %struct.bar, align 8
+  %tmp2 = bitcast %struct.pluto* %tmp1 to i8*
+  %tmp3 = getelementptr inbounds %struct.pluto, %struct.pluto* %tmp1, i32 0, i32 0
+  %tmp4 = bitcast [4 x float]* %tmp3 to { <2 x float>, <2 x float> }*
+  %tmp5 = getelementptr inbounds { <2 x float>, <2 x float> }, { <2 x float>, <2 x float> }* %tmp4, i32 0, i32 0
+  store <2 x float> %arg, <2 x float>* %tmp5, align 4
+  call void @snork(%struct.bar* %tmp, %struct.pluto* %tmp1)
+  ret void
+}
+
+declare { <2 x float>, <2 x float> } @zot(<2 x float>)
+
+declare void @snork(%struct.bar* sret, %struct.pluto*)