[llvm-bugs] [Bug 33357] New: jump-threading creating dead loop, causing LazyValueInfo to recurse infinitely

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=33357

            Bug ID: 33357
           Summary: jump-threading creating dead loop, causing
                    LazyValueInfo to recurse infinitely
           Product: new-bugs
           Version: unspecified
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: mikael.holmen at ericsson.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 18592
  --> https://bugs.llvm.org/attachment.cgi?id=18592&action=edit
reproducer

I've stumbled on a case where LazyValueInfo recurses infinitely and crashes due
to a rewrite done by jump-threading.

Reproduce with the following bugpoint reduced reproducer:

opt -S -Os -O1 -o - reduced.ll

I have so far failed to reproduce it when only invoking opt with
-jump-threading but I suppose it should be possible.



Short version of the problem:
-----------------------------

Should LavyValueInfo be able to handle

  %0 = and i1 %0, %tobool5

placed in a loop that is dead due to a jump-threading rewrite, or shouldn't
jump-threading call LazyValueInfo on instructions in the dead loop at all?


Details:
-----------------------------

(bugpoint-reduced) Input to jump-threading:

define void @f4(i32 %p1) local_unnamed_addr #1 {
entry:
  %cmp = icmp eq i32 %p1, 0
  br i1 undef, label %if.end16, label %for.cond.preheader

for.cond.preheader:                               ; preds = %entry
  %conv12 = trunc i32 %p1 to i16
  br label %for.cond

for.cond:                                         ; preds = %if.end,
%if.then14, %for.cond.preheader
  %f.0.in = phi i1 [ %cmp, %for.cond.preheader ], [ %0, %if.then14 ], [ %0,
%if.end ]
  %call4 = tail call i16 @f1()
  %tobool5 = icmp ne i16 %call4, 0
  %0 = and i1 %f.0.in, %tobool5
  br i1 %0, label %if.then11, label %if.end

if.then11:                                        ; preds = %for.cond
  store i16 %conv12, i16* @a, align 1
  br label %if.end

if.end:                                           ; preds = %if.then11,
%for.cond
  br i1 %cmp, label %for.cond, label %if.then14

if.then14:                                        ; preds = %if.end
  store i16 1, i16* @b, align 1
  br label %for.cond

if.end16:                                         ; preds = %entry
  ret void
}

Then

entry:
  %cmp = icmp eq i32 %p1, 0
  br i1 undef, label %if.end16, label %for.cond.preheader

is quickly replaced with

entry:
  %cmp = icmp eq i32 %p1, 0
  br label %if.end16

due to the original condition being undef:

  In block 'entry' folding undef terminator:   br i1 undef, label %if.end16,
label %for.cond.preheader

The function now looks like:

define void @f4(i32 %p1) local_unnamed_addr #1 {
entry:
  %cmp = icmp eq i32 %p1, 0
  br label %if.end16

for.cond.preheader:                               ; No predecessors!
  %conv12 = trunc i32 %p1 to i16
  br label %for.cond

for.cond:                                         ; preds = %if.end,
%if.then14, %for.cond.preheader
  %f.0.in = phi i1 [ %cmp, %for.cond.preheader ], [ %0, %if.then14 ], [ %0,
%if.end ]
  %call4 = tail call i16 @f1()
  %tobool5 = icmp ne i16 %call4, 0
  %0 = and i1 %f.0.in, %tobool5
  br i1 %0, label %if.then11, label %if.end

if.then11:                                        ; preds = %for.cond
  store i16 %conv12, i16* @a, align 1
  br label %if.end

if.end:                                           ; preds = %if.then11,
%for.cond
  br i1 %cmp, label %for.cond, label %if.then14

if.then14:                                        ; preds = %if.end
  store i16 1, i16* @b, align 1
  br label %for.cond

if.end16:                                         ; preds = %entry
  ret void
}

Note that for.cond.preheader is dead, no predecessors anymore.
Jump-threading therefore removes it:

  JT: Deleting dead block 'for.cond.preheader' with terminator:   br label
%for.cond

and the edge from for.cond.preheader to for.cond is also removed, leaving
for.cond like:

for.cond:                                         ; preds = %if.end, %if.then14
  %call4 = tail call i16 @f1()
  %tobool5 = icmp ne i16 %call4, 0
  %0 = and i1 %0, %tobool5
  br i1 %0, label %if.then11, label %if.end

Especially notice the instruction:

  %0 = and i1 %0, %tobool5

Operand 1 of the instruction was previously the result of a phi node, but since
we removed the dead block the phi could be simplified and removed, and we now
have an instruction referencing itself.

This instruction is later examined by LazyValueInfo and we end up in:

static LVILatticeVal
getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
                      DenseMap<Value*, LVILatticeVal> &Visited) {
  auto I = Visited.find(Cond);
  if (I != Visited.end())
    return I->second;

  auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited);
  Visited[Cond] = Result;
  return Result;
}

For an "and", getValueFromConditionImpl in turn will call getValueFromCondition
on both its operands. Since operand 1 of it is the "and" itself, we have
infinite recursion.

getValueFromCondition does have a visited list, but instructions are only
inserted in that after the instruction has been fully examined, so it doesn't
help us in this case.

Who's to blame?

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170608/f75db2f7/attachment.html>