[SimplifyCFG] avoid crash on degenerate loop

[spatel]

Summary

I'm not sure how to describe the code pattern in the test based on:
https://llvm.org/PR50638
...but if the IfCond is itself the phi that we are trying to remove, then the loop at line 2835 can end up with something like:

%cmp = select i1 %cmp, i1 false, i1 true

And that can then lead to an assert somewhere else (although I'm still not seeing that locally in my release + asserts build). I think this can only happen with unreachable code.

[lebedev.ri]

And what happens when there's more than one PHI node in the block?
I think the extra missing check is !isa<Instruction>(IfCond) || cast<Instruction>(IfCond)->getParent() != BB.

[lebedev.ri]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2710

(1) If you change IfCond's type to AssertingVH<Value> ...

2849

(3) ... so here on the second loop iteration IfCond is use-after-free.

2852

(2) ... the backtrace will tell you that the handle goes bad here ...

[lebedev.ri]

In D104063#2811595, @lebedev.ri wrote:

And what happens when there's more than one PHI node in the block?
I think the extra missing check is !isa<Instruction>(IfCond) || cast<Instruction>(IfCond)->getParent() != BB.

And thinking about it more, this should even be PHINode, not Instruction.

[spatel]

In D104063#2811595, @lebedev.ri wrote:

And what happens when there's more than one PHI node in the block?

If I'm seeing the code correctly, we can't get into trouble on anything other than the pattern in the test. That's because we limit the transform to a block with at most 2 phis (line 2723). If the problematic phi was 2nd, we'd escape without trying to touch the freed instruction.

But it's a valid concern (the assumption of 2 phis could change some day), so I agree, we should do better...

I think the extra missing check is !isa<Instruction>(IfCond) || cast<Instruction>(IfCond)->getParent() != BB.

But this won't work unless I've misunderstood the suggestion - the condition could be a function argument. Here's the first failing test that I found with that check:

define i32 @FoldTwoEntryPHINode(i1 %C, i32 %V1, i32 %V2, i16 %V3) {
entry:
        br i1 %C, label %then, label %else, !prof !0, !unpredictable !1
then:
        %V4 = or i32 %V2, %V1
        br label %Cont
else:
        %V5 = sext i16 %V3 to i32
        br label %Cont
Cont:
        %V6 = phi i32 [ %V5, %else ], [ %V4, %then ]
        call i32 @FoldTwoEntryPHINode( i1 false, i32 0, i32 0, i16 0 )
        ret i32 %V1
}

We still want that to fold to:

; CHECK-LABEL: @FoldTwoEntryPHINode(
; CHECK-NEXT:  entry:
; CHECK-NEXT:  %V5 = sext i16 %V3 to i32
; CHECK-NEXT:  %V4 = or i32 %V2, %V1
; CHECK-NEXT:  %V6 = select i1 %C, i32 %V4, i32 %V5, !prof !0, !unpredictable !1
; CHECK-NEXT:  %0 = call i32 @FoldTwoEntryPHINode(i1 false, i32 0, i32 0, i16 0)
; CHECK-NEXT:  ret i32 %V1

[spatel]

Patch updated:
Make the bailout more general and try to explain the problem pattern in a code comment.

[lebedev.ri]

In D104063#2813104, @spatel wrote:

Patch updated:
Make the bailout more general and try to explain the problem pattern in a code comment.

Thanks, that's precisely what i meant.
Thanks.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2718

I think we only need to care about PHI nodes

[spatel]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

2718

Sounds good - I'll change that on final commit.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   // statement", which has a very simple dominance structure.  Basically, we
   // are trying to find the condition that is being branched on, which
   // subsequently causes this merge to happen.  We really want control
   // dependence information for this check, but simplifycfg can't keep it up
   // to date, and this catches most of the cases we care about anyway.
   BasicBlock *BB = PN->getParent();
 
   BasicBlock *IfTrue, *IfFalse;
   Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse);
   if (!IfCond ||
       // Don't bother if the branch will be constant folded trivially.
       isa<ConstantInt>(IfCond))
     return false;
 
+  // Don't try to fold an unreachable block. For example, the phi node itself
+  // can't be the candidate if-condition for a select that we want to form.
+  if (auto *IfCondPhiInst = dyn_cast<PHINode>(IfCond))
+    if (IfCondPhiInst->getParent() == BB)
+      return false;
+
   // Okay, we found that we can merge this two-entry phi node into a select.
   // Doing so would require us to fold *all* two entry phi nodes in this block.
   // At some point this becomes non-profitable (particularly if the target
   // doesn't support cmov's).  Only do this transformation if there are two or
   // fewer PHI nodes in this block.
   unsigned NumPhis = 0;
   for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I)
     if (NumPhis > 2)
static bool FoldTwoEntryPHINode(PHINode *PN, const TargetTransformInfo &TTI,
   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
     if (isa<FPMathOperator>(PN))
       Builder.setFastMathFlags(PN->getFastMathFlags());
 
     // Change the PHI node into a select instruction.
     Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse);
     Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue);
 
     Value *Sel = Builder.CreateSelect(IfCond, TrueVal, FalseVal, "", InsertPt);
     PN->replaceAllUsesWith(Sel);
     Sel->takeName(PN);
     PN->eraseFromParent();
   }
 
   // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement
   // has been flattened.  Change DomBlock to jump directly to our new block to
   // avoid other simplifycfg's kicking in on the diamond.
   Instruction *OldTI = DomBlock->getTerminator();
   Builder.SetInsertPoint(OldTI);
   Builder.CreateBr(BB);

llvm/test/Transforms/SimplifyCFG/two-entry-phi-return.ll

bb:
   br label %UnifiedReturnBlock
 
 UnifiedReturnBlock:
   %result = phi i1 [ 0, %entry ], [ %t15, %bb ]
   ret i1 %result
 
 }
 
+@a = external dso_local global i32, align 4
+
+define i32 @PR50638() {
+; CHECK-LABEL: @PR50638(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store i32 0, i32* @a, align 4
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  store i32 0, i32* @a, align 4
+  br label %pre.for
+
+pre.for:
+  %tobool.not = phi i1 [ false, %for ], [ true, %entry ]
+  br i1 %tobool.not, label %end, label %for
+
+for:
+  %cmp = phi i1 [ true, %pre.for ], [ false, %post.for ]
+  %storemerge = phi i32 [ 0, %pre.for ], [ 1, %post.for ]
+  store i32 %storemerge, i32* @a, align 4
+  br i1 %cmp, label %post.for, label %pre.for
+
+post.for:
+  br label %for
+
+end:
+  ret i32 0
+}
+
 !0 = !{!"branch_weights", i32 4, i32 64}