[LICM] Fix a crash when sinking instructions w/token operands

[reames]

Summary

It is not legal to form a phi node with token type. The generic LCSSA construction code handles this correctly - by not forming LCSSA for such cases - but the adhoc fixup implementation in LICM did not.

This was noticed in the context of PR49607, but can be demonstrated on ToT with the tweaked test case. This is not specific to gc.relocate btw, it also applies to usage of the preallocated family of intrinsics as well.

[lebedev.ri]

It is not legal to form a phi node with token type.

Can PHINode::Create() assert that?

[reames]

In D98728#2629764, @lebedev.ri wrote:

It is not legal to form a phi node with token type.

Can PHINode::Create() assert that?

The verifier already catches this pretty promptly. I don't really see the value in this, but also have no problem landing a separate change to add the assert if desired.

[fhahn]

LGTM given that we already do not create LCSSA phis during regular LCSSA construction.

llvm/lib/Transforms/Scalar/LICM.cpp

1515

It might be helpful for future readers of the code if the token-type check would be separate & with a brief comment (perhaps an early continue). I'm fine either way, please feel free to disregard the comment.

[reames]

llvm/lib/Transforms/Scalar/LICM.cpp

1515

I played with a couple variations, and everything I came up with was harder to read and lengthened the code a lot. I ended up slightly rewording the comments describing the actions being done and left it at that.

[reames]

llvm/lib/Transforms/Scalar/LICM.cpp

1515

Thought about this a bit further, and came up with 31764ea295. Landed it because it seemed straight forward, but let me know what you think. I can always revert if you dislike the direction.

[fhahn]

llvm/lib/Transforms/Scalar/LICM.cpp

1515

I think that's a great improvement, thanks!

llvm/lib/Transforms/Scalar/LICM.cpp

if (NewMemAcc) {
         MSSAU->insertDef(MemDef, /*RenameUses=*/true);
       else {
         auto *MemUse = cast<MemoryUse>(NewMemAcc);
         MSSAU->insertUse(MemUse, /*RenameUses=*/true);
       }
     }
   }
 
-  // Build LCSSA PHI nodes for any in-loop operands. Note that this is
-  // particularly cheap because we can rip off the PHI node that we're
+  // Build LCSSA PHI nodes for any in-loop operands (if legal).  Note that
+  // this is particularly cheap because we can rip off the PHI node that we're
   // replacing for the number and blocks of the predecessors.
   // OPT: If this shows up in a profile, we can instead finish sinking all
   // invariant instructions, and then walk their operands to re-establish
   // LCSSA. That will eliminate creating PHI nodes just to nuke them when
   // sinking bottom-up.
   for (Use &Op : New->operands())
     if (Instruction *OInst = dyn_cast<Instruction>(Op))
       if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
-        if (!OLoop->contains(&PN)) {
+        if (!OLoop->contains(&PN) && !Op->getType()->isTokenTy()) {
           PHINode *OpPN =
               PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
                               OInst->getName() + ".lcssa", &ExitBlock.front());
           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
             OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
           Op = OpPN;
         }
   return New;
class LoopPromoter : public LoadAndStorePromoter {
   MemorySSAUpdater *MSSAU;
   LoopInfo &LI;
   DebugLoc DL;
   int Alignment;
   bool UnorderedAtomic;
   AAMDNodes AATags;
   ICFLoopSafetyInfo &SafetyInfo;
 
+  // We're about to add a use of V in a loop exit block.  Insert an LCSSA phi
+  // (if legal) if doing so would add an out-of-loop use to an instruction
+  // defined in-loop.
   Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
     if (Instruction *I = dyn_cast<Instruction>(V))
       if (Loop *L = LI.getLoopFor(I->getParent()))
-        if (!L->contains(BB)) {
+        if (!L->contains(BB) && !I->getType()->isTokenTy()) {
           // We need to create an LCSSA PHI node for the incoming value and
           // store that.
           PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
                                         I->getName() + ".lcssa", &BB->front());
           for (BasicBlock *Pred : PredCache.get(BB))
             PN->addIncoming(I, Pred);
           return PN;
         }

llvm/test/Transforms/LICM/gc-relocate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -basic-aa -licm < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i8 addrspace(1)* @test(i8 addrspace(1)* %arg) #0 gc "statepoint-example" personality i32* ()* @wobble {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[TMP:%.*]] = call token (i64, i32, i32 (i32, i8 addrspace(1)*, i32, i32, i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32i32p1i8i32i32i32f(i64 1, i32 16, i32 (i32, i8 addrspace(1)*, i32, i32, i32)* nonnull @zot, i32 5, i32 0, i32 undef, i8 addrspace(1)* undef, i32 undef, i32 undef, i32 undef, i32 0, i32 0) [ "deopt"(i32 0, i32 0, i32 0, i32 235, i32 3, i32 32, i32 0, i32 0, i8 addrspace(1)* undef, i32 3, i32 undef, i32 3, float undef, i32 0, i8 addrspace(1)* undef, i32 7, i8* null, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 0, i8 addrspace(1)* undef, i32 4, double undef, i32 7, i8* null, i32 0, i8 addrspace(1)* undef, i32 3, float undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* null, i32 3, i32 -15108, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null), "gc-live"(i8 addrspace(1)* [[ARG:%.*]]) ]
-; CHECK-NEXT:    [[RES:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[TMP]], i32 0, i32 0)
 ; CHECK-NEXT:    br i1 false, label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[RES_LCSSA:%.*]] = phi i8 addrspace(1)* [ [[RES]], [[BB1]] ]
-; CHECK-NEXT:    ret i8 addrspace(1)* [[RES_LCSSA]]
+; CHECK-NEXT:    [[RES_LE:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[TMP]], i32 0, i32 0) #[[ATTR2:[0-9]+]]
+; CHECK-NEXT:    ret i8 addrspace(1)* [[RES_LE]]
 ;
 bb:
   br label %bb1
 
 bb1:
   %tmp = call token (i64, i32, i32 (i32, i8 addrspace(1)*, i32, i32, i32)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i32i32p1i8i32i32i32f(i64 1, i32 16, i32 (i32, i8 addrspace(1)*, i32, i32, i32)* nonnull @zot, i32 5, i32 0, i32 undef, i8 addrspace(1)* undef, i32 undef, i32 undef, i32 undef, i32 0, i32 0) [ "deopt"(i32 0, i32 0, i32 0, i32 235, i32 3, i32 32, i32 0, i32 0, i8 addrspace(1)* undef, i32 3, i32 undef, i32 3, float undef, i32 0, i8 addrspace(1)* undef, i32 7, i8* null, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 3, i32 undef, i32 0, i8 addrspace(1)* undef, i32 4, double undef, i32 7, i8* null, i32 0, i8 addrspace(1)* undef, i32 3, float undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* undef, i32 0, i8 addrspace(1)* null, i32 3, i32 -15108, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null, i32 7, i8* null), "gc-live"(i8 addrspace(1)* %arg) ]
-  %res = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %tmp, i32 0, i32 0)
+  %res = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %tmp, i32 0, i32 0) readnone
   br i1 undef, label %bb1, label %bb2
 
 bb2:
   ret i8 addrspace(1)* %res
 }
 
 declare i32* @wobble()
 declare i32 @zot(i32, i8 addrspace(1)*, i32, i32, i32)
 declare token @llvm.experimental.gc.statepoint.p0f_isVoidi32f(i64, i32, void (i32)*, i32, i32, ...)
 
 ; Function Attrs: nounwind readnone
 declare i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token, i32, i32) #0
 declare token @llvm.experimental.gc.statepoint.p0f_i32i32p1i8i32i32i32f(i64, i32, i32 (i32, i8 addrspace(1)*, i32, i32, i32)*, i32, i32, ...)
 
 attributes #0 = { nounwind readnone }