[SimplifyCFG] Fix a crash when folding PHIs

[davide]

Summary

This fixes a crash found by @zhendongsu when running SimplifyCFG.
This is the gist:

We enter MergeBlockIntoPredecessor with a block looking like this:

for.inc.us-lcssa:                                 ; preds = %cond.end
  %k.1.lcssa.ph = phi i32 [ %conv15, %cond.end ]
  %t.3.lcssa.ph = phi i32 [ %k.1.lcssa.ph, %cond.end ]
  br label %for.inc, !dbg !66

[note the first arg of the PHI being a PHI].

FoldSingleEntryPHINodes gets rid of both PHIs (calling, eraseFromParent).
But right before we call the function, we push into IncomingValues the only argument of the PHIs, and shortly after we try to iterate over something which has been invalidated before :(

The way I propose(d) to fix this is that of not pushing into IncomingValues if PN.getIncomingValue(0) isa<PHINode>.
It seems enough to cover all the cases. Eli proposed to move the debug info handling in the function which takes care of folding the phi, although this is a little tricky because we remove the redundant dbg.values post slice (so it's left as a follow up).

An attempt to fix:
http://llvm.org/bugs/show_bug.cgi?id=37300 and rdar://problem/39910460

The thing that worries me the most is the testcase (as it's admittedly, insane). I spent some time trying to reduce it but I was never able to get to something manageable in size (or something which doesn't screw up debug info). bugpoint itself doesn't seem to help much here. Ideas on how to reduce further are appreciated :)

[aprantl]

That testcase is huge. Do all instructions need !dbg locations?

[davide]

In D46568#1090802, @aprantl wrote:

That testcase is huge. Do all instructions need !dbg locations?

I can probably limit the number of !dbg location attached to the instructions, and that could shrink the test a bit [but still crashing], if you're fine with it.
I was mainly worried about feeding something which is different from what the frontend/previous passes provide.

[davide]

Got it down to 350 lines ~ with your suggestion, but still I'm not happy if I look at the size
https://reviews.llvm.org/P8079

[davide]

I think I found a better (but slow :() way to reduce it. I'll send an updated testcase tomorrow.

[aprantl]

I've slowly come to always prefer the smallest possible test case, since anything else makes it impossible for future readers to determine what the test is supposed to be testing and it is very easy to end up with cargo-cult testcases that don't test anything interesting after a while.

[davide]

Reduced again: https://reviews.llvm.org/P8080

[aprantl]

Thanks, the new test looks much better!

[vsk]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

155 ↗

(On Diff #145602)

Would it be safe/worthwhile to allow incoming values which are phi nodes from a block other than BB? These should not be invalidated by FoldSingleEntryPHINodes(). If the goal is to eliminate duplicate dbg.values for incoming values, then it might make sense.

Apologies if this is off-base, I'm not familiar with this code.

[efriedma]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

152 ↗

(On Diff #145602)

AssertingVH? (This would also make it easier to reduce the testcase, by turning undefined behavior into a simple assertion failure.)

155 ↗

(On Diff #145602)

Maybe !isa<PHINode>(PN.getIncomingValue(0)) || cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB, or something like that, so we preserve debug info in more cases?

[davide]

Addressed comments. Thanks!

[vsk]

This seems sensible to me! It'd be great if someone more familiar with simplifyCfg could +1.

[efriedma]

LGTM

llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp

bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
 
   // Can't merge if there is PHI loop.
   for (PHINode &PN : BB->phis())
     for (Value *IncValue : PN.incoming_values())
       if (IncValue == &PN)
         return false;
 
   // Begin by getting rid of unneeded PHIs.
-  SmallVector<Value *, 4> IncomingValues;
+  SmallVector<AssertingVH<Value>, 4> IncomingValues;
   if (isa<PHINode>(BB->front())) {
     for (PHINode &PN : BB->phis())
-      if (PN.getIncomingValue(0) != &PN)
+      if (!isa<PHINode>(PN.getIncomingValue(0)) ||
+          cast<PHINode>(PN.getIncomingValue(0))->getParent() != BB)
         IncomingValues.push_back(PN.getIncomingValue(0));
     FoldSingleEntryPHINodes(BB, MemDep);
   }
 
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();
 
   // Make all PHI nodes that referred to BB now refer to Pred as their
   // source...
   BB->replaceAllUsesWith(PredBB);
 
   // Move all definitions in the successor to the predecessor...
   PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
 
   // Eliminate duplicate dbg.values describing the entry PHI node post-splice.
-  for (auto *Incoming : IncomingValues) {
-    if (isa<Instruction>(Incoming)) {
+  for (auto Incoming : IncomingValues) {
+    if (isa<Instruction>(*Incoming)) {
       SmallVector<DbgValueInst *, 2> DbgValues;
       SmallDenseSet<std::pair<DILocalVariable *, DIExpression *>, 2>
           DbgValueSet;
       llvm::findDbgValues(DbgValues, Incoming);
       for (auto &DVI : DbgValues) {
         auto R = DbgValueSet.insert({DVI->getVariable(), DVI->getExpression()});
         if (!R.second)
           DVI->eraseFromParent();

llvm/trunk/test/Transforms/SimplifyCFG/fold-debug-info.ll

+;; Check that we don't crash. PR37300.
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+define void @patatino() {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    ret void
+;
+bb:
+  %tmp = icmp eq i32 7, 0
+  br label %bb3
+bb3:                                              ; preds = %bb2, %bb
+  br label %bb36
+bb5:                                              ; preds = %bb4
+  %tmp7 = icmp ne i32 7, 0
+  %tmp8 = and i1 true, %tmp7
+  br i1 %tmp8, label %bb16, label %bb14
+bb9:                                              ; preds = %bb33, %bb10
+  br label %bb18
+bb10:                                             ; preds = %bb19, %bb13
+  %tmp11 = add nsw i32 2, 1
+  %tmp12 = icmp eq i32 %tmp11, 0
+  br i1 %tmp12, label %bb17, label %bb9
+bb13:                                             ; preds = %bb18, %bb13
+  br label %bb10
+bb14:                                             ; preds = %bb17, %bb6, %bb5
+  br label %bb35
+bb16:                                             ; preds = %bb6
+  br label %bb31
+bb17:                                             ; preds = %bb32, %bb10
+  br label %bb14
+bb18:                                             ; preds = %bb9
+  br label %bb13
+bb21:                                             ; preds = %bb31, %bb23
+  %tmp22 = phi i32 [ 0, %bb23 ], [ 0, %bb31 ]
+  br label %bb27
+bb23:                                             ; preds = %bb29, %bb28, %bb26
+  %tmp24 = add nsw i32 %tmp22, 1
+  %tmp25 = icmp eq i32 %tmp24, 0
+  br i1 %tmp25, label %bb32, label %bb21
+bb27:                                             ; preds = %bb21
+  br label %bb30
+bb28:                                             ; preds = %bb30
+  br label %bb23
+bb30:                                             ; preds = %bb30, %bb27
+  br label %bb28
+bb31:                                             ; preds = %bb16
+  br label %bb21
+bb32:                                             ; preds = %bb23
+  br label %bb17
+bb35:                                             ; preds = %bb14
+  br label %bb3
+bb36:                                             ; preds = %bb3, %bb3
+  br label %bb37
+bb37:                                             ; preds = %bb36
+  %tmp39 = and i1 %tmp, true
+  br i1 %tmp39, label %bb40, label %bb67
+bb40:                                             ; preds = %bb38
+  br i1 %tmp, label %bb42, label %bb41
+bb41:                                             ; preds = %bb40
+  br label %bb43
+bb42:                                             ; preds = %bb40
+  br label %bb66
+bb43:                                             ; preds = %bb41
+  br label %bb44
+bb44:                                             ; preds = %bb61, %bb43
+  %tmp45 = phi i32 [ 0, %bb61 ], [ 0, %bb43 ]
+  %tmp46 = phi i32 [ %tmp62, %bb61 ], [ 0, %bb43 ]
+  br label %bb51
+bb48:                                             ; preds = %bb47
+  br label %bb49
+bb49:                                             ; preds = %bb48
+  %tmp50 = phi i32 [ 0, %bb48 ]
+  br label %bb61
+bb51:                                             ; preds = %bb44
+  br label %bb52
+bb52:                                             ; preds = %bb55, %bb51
+  %tmp53 = phi i32 [ %tmp46, %bb51 ], [ 0, %bb55 ]
+  br label %bb55
+bb54:                                             ; preds = %bb52
+  br label %bb55
+bb55:                                             ; preds = %bb54, %bb52
+  %tmp56 = phi i32 [ 0, %bb54 ], [ 0, %bb52 ]
+  %tmp57 = shl i32 %tmp56, 16
+  br i1 false, label %bb52, label %bb58
+bb58:                                             ; preds = %bb55
+  %tmp59 = phi i32 [ 0, %bb55 ]
+  %tmp60 = phi i32 [ %tmp53, %bb55 ]
+  br label %bb61
+bb61:                                             ; preds = %bb58, %bb49
+  %tmp62 = phi i32 [ %tmp59, %bb58 ], [ %tmp50, %bb49 ]
+  %tmp63 = add nsw i32 %tmp45, 1
+  %tmp64 = icmp eq i32 %tmp63, 0
+  br i1 %tmp64, label %bb65, label %bb44
+bb65:                                             ; preds = %bb61
+  br label %bb66
+bb66:                                             ; preds = %bb65, %bb42
+  br label %bb67
+bb67:                                             ; preds = %bb66, %bb38
+  ret void
+}