This is an archive of the discontinued LLVM Phabricator instance.

[LazyValueInfo] Insert an Overdefined placeholder to prevent infinite recursion
ClosedPublic

Authored by guopeilin on Apr 25 2021, 7:27 PM.

Details

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.

Diff Detail

Event Timeline

guopeilin created this revision.Apr 25 2021, 7:27 PM
guopeilin requested review of this revision.Apr 25 2021, 7:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 25 2021, 7:27 PM
This comment was removed by guopeilin.
guopeilin added a comment.EditedApr 25 2021, 7:31 PM

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.

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

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?

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.

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 added a reviewer: nikic.Apr 26 2021, 3:21 AM
nikic added a subscriber: 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 updated this revision to Diff 341051.Apr 27 2021, 6:56 PM
guopeilin retitled this revision from [JumpThreading] Set KeepOneInputPHIs to be true when DeleteDeadBlocks to [LazyValueInfo] Insert an Overdefined placeholder to prevent infinite recursion.
guopeilin edited the summary of this revision. (Show Details)

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

@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 added inline comments.Apr 28 2021, 12:56 AM
llvm/lib/Analysis/LazyValueInfo.cpp
1167–1168

It should be possible to drop this code now.

1189

It's not really invalid IR...

1193

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 updated this revision to Diff 341386.Apr 28 2021, 7:25 PM

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

lattner resigned from this revision.Apr 28 2021, 9:17 PM
nikic accepted this revision.Apr 29 2021, 9:48 AM

LGTM

llvm/test/Transforms/JumpThreading/keep-one-input-phis.ll
1 ↗(On Diff #341386)

The name of this test is outdated now.

This revision is now accepted and ready to land.Apr 29 2021, 9:48 AM
guopeilin updated this revision to Diff 343296.May 5 2021, 11:38 PM
guopeilin edited the summary of this revision. (Show Details)May 5 2021, 11:44 PM