[LazyValueInfo] Insert an Overdefined placeholder to prevent infinite recursion

[guopeilin]

Summary

getValueFromCondition() uses a Visited set to record the intermediate value.
However, it uses a postorder way to compute the value first and update the
Visited set later. Thus it will be trapped into an infinite recursion if there
exists IRs that use no dominated by its def as in this example:

    
"%tmp3 = or i1 undef, %tmp4"
"%tmp4 = or i1 undef, %tmp3"

To prevent this, we can insert an Overdefined placeholder into the set
before computing the actual value.

[guopeilin]

This comment was removed by guopeilin.

[guopeilin]

The bug is reported in https://bugs.llvm.org/show_bug.cgi?id=50119

This bug is generated in the following logic:
Firstly, we can see that this function has a loop that contains the two red basic blocks. And this loop's preheader is for.body.i.us.1.preheader. After we ProcessBlock, the preheader becomes dead, then we decide to DeleteDeadBlock.
And within the functions DeleteDeadBlock, we visit the dead block's successors and remove the successors from its predecessor. That is we just detach the dead block and the unreachable blocks still remain within the function.
What's more, for those successors, we also try to simplify their phi nodes. In this case, the loop that has two red blocks, its loop header for.body.i.us.1 has a PHI node, which has two incoming values, one from the preheader(predecessor),
the other one from the loop exit. Now that we have removed the header from its predecessor, we can remove the incoming value from its predecessor and replace the phi node use with another incoming value.
After the DeleteDeadBlock, the loop might become this:

for.body.i.us.1:                                  ; preds = %lor.end.i.us.1
  br i1 %spec.select44.i.us.1, label %lor.end.i.us.1, label %lor.rhs.i.us.1

lor.rhs.i.us.1:                                   ; preds = %for.body.i.us.1
  %conv5.i.us.1 = trunc i32 undef to i8
  br label %lor.end.i.us.1

lor.end.i.us.1:                                   ; preds = %lor.rhs.i.us.1, %for.body.i.us.1
  %.b31.i.us.1 = or i1 undef, %spec.select44.i.us.1
  %spec.select44.i.us.1 = or i1 undef, %.b31.i.us.1
  br i1 undef, label %for.end18.loopexit42.i.1.loopexit, label %for.body.i.us.1

So in the block lor.end.i.us.1, there exists some invalid IRs that the use not dominated by its def in a self-loop.
Further, when we try to ProcessBlock lor.end.i.us.1, if we want to getValueFromCondition, we will trapped in a recusive loop cause the condition %spec.select44.i.us.1 and %.b31.i.us.1 use each other.

[guopeilin]

Right now this patch set the argument KeepOneInputPHIs of function DeleteDeadBlocks to be true, that is we only allow replacing the phi node with its incoming value if this incoming value is a constant

[lattner]

I *think* that the current behavior is ok. Dominance is not defined in unreachable code, so cyclic references etc are allowed (by the verifier etc). What is the problem that this is causing?

[guopeilin]

https://bugs.llvm.org/show_bug.cgi?id=50119
The bug is that we will be trapped into an infinite loop when we doing jump threading pass, and finally exhaust the stack.
The Jump Threading call function getValueFromCondition() of LazyValueInfo, and this function will recursively call itself in a way shown in the fowllowing:

BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
Value *BL = BO->getOperand(0);
Value *BR = BO->getOperand(1);

if (BL == Cond || BR == Cond)
  return ValueLatticeElement::getOverdefined();

return intersect(getValueFromCondition(Val, BL, isTrueDest, Visited),
                 getValueFromCondition(Val, BR, isTrueDest, Visited));

At some time, let's consume that the condition is %spec.select44.i.us.1 = or i1 undef, %.b31.i.us.1, its second operand is %.b31.i.us.1.
And, %.b31.i.us.1's second is %spec.select44.i.us.1 again.
So we will be trapped here, with %.b31.i.us.1 and %spec.select44.i.us.1 appear alternately.
I guess the root reason is that we generate invalid IRs that use do not dominated by its def.

In D101273#2715865, @lattner wrote:

I *think* that the current behavior is ok. Dominance is not defined in unreachable code, so cyclic references etc are allowed (by the verifier etc). What is the problem that this is causing?

[nikic]

@guopeilin getValueFromCondition() uses a Visited set that should be used to prevent this. You need to insert an Overdefined placeholder into the set before computing the actual value.

[guopeilin]

Fix bugs in Lazy Value Info analysis rather in Jump Threading pass

[guopeilin]

In D101273#2716235, @nikic wrote:

@guopeilin getValueFromCondition() uses a Visited set that should be used to prevent this. You need to insert an Overdefined placeholder into the set before computing the actual value.

A new patch updated, please review.

[nikic]

llvm/lib/Analysis/LazyValueInfo.cpp

1173 ↗

(On Diff #341051)

It should be possible to drop this code now.

1198 ↗

(On Diff #341051)

It's not really invalid IR...

1202 ↗

(On Diff #341051)

You are performing two successive DenseMap accesses here. Instead you can use Visited.try_emplace(Cond, ValueLatticeElement::getOverdefined()) which check .second for whether it's a pre-existing cache entry.

[guopeilin]

@nikic Thanks a lot so your suggesstion. A new patch updated, please review.

[nikic]

LGTM

llvm/test/Transforms/JumpThreading/keep-one-input-phis.ll

2

The name of this test is outdated now.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (auto &BB : F) {
       if (pred_empty(&BB)) {
         // When processBlock makes BB unreachable it doesn't bother to fix up
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
-        DeleteDeadBlock(&BB, DTU);
+        // After ProcessBlock, we might generate some unreachable loops,
+        // thus we need to set the argument KeepOneInputPHIs to be true
+        // to avoid generating invalid IRs that use not dominated by its
+        // def in a self-loop.
+        DeleteDeadBlock(&BB, DTU, true);
         Changed = true;
         continue;
       }
 
       // processBlock doesn't thread BBs with unconditional TIs. However, if BB
       // is "almost empty", we attempt to merge BB with its sole successor.
       auto *BI = dyn_cast<BranchInst>(BB.getTerminator());
       if (BI && BI->isUnconditional()) {

llvm/test/Transforms/JumpThreading/keep-one-input-phis.ll

+; RUN: opt -jump-threading -S < %s | FileCheck %s
+@a = common dso_local local_unnamed_addr global i16 0, align 2
+
+; Function Attrs: nofree norecurse nounwind
+define internal fastcc void @s() unnamed_addr {
+; CHECK-LABEL: @s(
+; CHECK-NEXT:  for.cond1.preheader.lr.ph:
+; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER:%.*]]
+; CHECK:       for.cond1.preheader:
+; CHECK-NEXT:    [[DOTPR_I_19:%.*]] = phi i32 [ undef, [[FOR_COND1_PREHEADER_LR_PH:%.*]] ], [ 0, [[FOR_INC_SPLIT_1:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i16 [ undef, [[FOR_COND1_PREHEADER_LR_PH]] ], [ [[INC9:%.*]], [[FOR_INC_SPLIT_1]] ]
+; CHECK-NEXT:    [[TOBOOL4_I:%.*]] = icmp eq i32 [[DOTPR_I_19]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL4_I]], label [[FOR_INC_SPLIT_1]], label [[FOR_BODY_LR_PH_I:%.*]]
+; CHECK:       for.body.lr.ph.i:
+; CHECK-NEXT:    ret void
+; CHECK:       for.cond.for.end10_crit_edge:
+; CHECK-NEXT:    ret void
+; CHECK:       for.inc.split.1:
+; CHECK-NEXT:    [[INC9]] = add i16 [[TMP0]], 1
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i16 [[INC9]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[FOR_COND_FOR_END10_CRIT_EDGE:%.*]], label [[FOR_COND1_PREHEADER]]
+;
+for.cond1.preheader.lr.ph:
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.inc.split.1, %for.cond1.preheader.lr.ph
+  %.pr.i.19 = phi i32 [ undef, %for.cond1.preheader.lr.ph ], [ 0, %for.inc.split.1 ]
+  %0 = phi i16 [ undef, %for.cond1.preheader.lr.ph ], [ %inc9, %for.inc.split.1 ]
+  %tobool4.i = icmp eq i32 %.pr.i.19, 0
+  br i1 %tobool4.i, label %t.exit, label %for.body.lr.ph.i
+
+for.body.lr.ph.i:                                 ; preds = %for.cond1.preheader
+  ret void
+
+t.exit:                                           ; preds = %for.cond1.preheader
+  br label %for.inc.split
+
+for.inc.split:                                    ; preds = %t.exit
+  %tobool4.i.1 = icmp eq i32 %.pr.i.19, 0
+  br i1 %tobool4.i.1, label %for.inc.split.1, label %for.body.lr.ph.i.1
+
+for.cond.for.end10_crit_edge:                     ; preds = %for.inc.split.1
+  ret void
+
+for.body.lr.ph.i.1:                               ; preds = %for.inc.split
+  br label %for.body.lr.ph.split.i.1
+
+for.body.lr.ph.split.i.1:                         ; preds = %for.body.lr.ph.i.1
+  br label %for.body.preheader.i.1
+
+for.body.preheader.i.1:                           ; preds = %for.body.lr.ph.split.i.1
+  br label %for.body.i.us.1.preheader
+
+for.body.i.us.1.preheader:                        ; preds = %for.body.preheader.i.1
+  br label %for.body.i.us.1
+
+for.body.i.us.1:                                  ; preds = %lor.end.i.us.1, %for.body.i.us.1.preheader
+  %.b.i.us.1 = phi i1 [ %spec.select44.i.us.1, %lor.end.i.us.1 ], [ undef, %for.body.i.us.1.preheader ]
+  br i1 %.b.i.us.1, label %lor.end.i.us.1, label %lor.rhs.i.us.1
+
+lor.rhs.i.us.1:                                   ; preds = %for.body.i.us.1
+  %conv5.i.us.1 = trunc i32 undef to i8
+  br label %lor.end.i.us.1
+
+lor.end.i.us.1:                                   ; preds = %lor.rhs.i.us.1, %for.body.i.us.1
+  %.b31.i.us.1 = or i1 undef, %.b.i.us.1
+  %spec.select44.i.us.1 = or i1 undef, %.b31.i.us.1
+  br i1 undef, label %for.end18.loopexit42.i.1.loopexit, label %for.body.i.us.1
+
+for.end18.loopexit42.i.1.loopexit:                ; preds = %lor.end.i.us.1
+  br label %for.end18.loopexit42.i.1
+
+for.end18.loopexit42.i.1:                         ; preds = %for.end18.loopexit42.i.1.loopexit
+  br label %for.inc.split.1
+
+for.inc.split.1:                                  ; preds = %for.end18.loopexit42.i.1, %for.inc.split
+  %inc9 = add i16 %0, 1
+  %tobool = icmp eq i16 %inc9, 0
+  br i1 %tobool, label %for.cond.for.end10_crit_edge, label %for.cond1.preheader
+}