[llvm-bugs] [Bug 42085] New: JumpThreading: invalid transformation

[via llvm-bugs]

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

            Bug ID: 42085
           Summary: JumpThreading: invalid transformation
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Windows NT
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: serguei.katkov at azul.com
                CC: llvm-bugs at lists.llvm.org

The following IR:
====================================================================
declare void @foo(i32)

define i32 @test(i32 %A, i32 %B, i32 %C) {
entry:
  br label %header.1

header.1:
  %v.1.h = phi i32 [%A, %entry], [%v.h, %header]
  %w.1.h = phi i32 [%C, %entry], [%w.h, %header]
  br i1 false, label %header, label %bad

header:
  %v.h = phi i32 [%v.1.h, %header.1], [%v.inc, %cont]
  %w.h = phi i32 [%w.1.h, %header.1], [%v.inc, %cont]
  %cmp3 = icmp sgt i32 %w.h, 100
  br i1 %cmp3, label %header.1, label %bad

bad:
  %v = phi i32 [%v.1.h, %header.1], [%v.h, %header]
  %w = phi i32 [%w.1.h, %header.1], [%w.h, %header]
  %v.inc = add i32 %v, 1
  %cmp2 = icmp eq i32 %B, 0
  br i1 %cmp2, label %exit2, label %loop

loop:
  call void @foo(i32 %v.inc)
  %cmp = icmp sgt i32 %v.inc, 170
  br i1 %cmp, label %exit, label %cont

cont:
  br label %header

exit:
  ret i32 %w

exit2:
  ret i32 0

}
====================================================================
is incorrectly transformed

opt -passes=jump-threading ./test.ll -o test.opt.ll -S
-debug-only=jump-threading
Jump threading on function 'test'
  In block 'header.1' folding terminator:   br i1 false, label %header, label
%bad
IN BB:
bad:                                              ; preds = %header.1, %header
  %v = phi i32 [ %v.1.h, %header.1 ], [ %v.inc, %header ]
  %w = phi i32 [ %w.1.h, %header.1 ], [ %v.inc, %header ]
  %v.inc = add i32 %v, 1
  %cmp2 = icmp eq i32 %B, 0
  br i1 %cmp2, label %exit2, label %loop
  BB 'bad': FOUND condition = i1 false for pred 'header'.
  Threading edge from 'header' to 'loop' with cost: 2, across block:

bad:                                              ; preds = %header.1, %header
  %v = phi i32 [ %v.1.h, %header.1 ], [ %v.inc, %header ]
  %w = phi i32 [ %w.1.h, %header.1 ], [ %v.inc, %header ]
  %v.inc = add i32 %v, 1
  %cmp2 = icmp eq i32 %B, 0
  br i1 %cmp2, label %exit2, label %loop

JT: Renaming non-local uses of:   %w = phi i32 [ %w.1.h, %header.1 ]

JT: Renaming non-local uses of:   %v.inc = add i32 %v, 1

IN BB:
loop:                                             ; preds = %bad.thread, %bad
  %v.inc4 = phi i32 [ %v.inc1, %bad.thread ], [ %v.inc, %bad ]
  %w3 = phi i32 [ %v.inc1, %bad.thread ], [ %w.1.h, %bad ]
  call void @foo(i32 %v.inc4)
  %cmp = icmp sgt i32 %v.inc4, 170
  br i1 %cmp, label %exit, label %header
  BB 'loop': FOUND condition = i1 false for pred 'bad.thread'.
  Not threading across block BB 'loop' to dest loop header BB 'header' - it
might create an irreducible loop!
IN BB:
loop:                                             ; preds = %bad.thread, %bad
  %v.inc4 = phi i32 [ %v.inc1, %bad.thread ], [ %v.inc, %bad ]
  %w3 = phi i32 [ %v.inc1, %bad.thread ], [ %w.1.h, %bad ]
  call void @foo(i32 %v.inc4)
  %cmp = icmp sgt i32 %v.inc4, 170
  br i1 %cmp, label %exit, label %header
  BB 'loop': FOUND condition = i1 false for pred 'bad.thread'.
  Not threading across block BB 'loop' to dest loop header BB 'header' - it
might create an irreducible loop!

to 
====================================================================
; ModuleID = './test.ll'
source_filename = "./test.ll"

declare void @foo(i32)

define i32 @test(i32 %A, i32 %B, i32 %C) {
entry:
  br label %bad

header:                                           ; preds = %loop
  %cmp3 = icmp sgt i32 %v.inc4, 100
  br i1 %cmp3, label %bad, label %bad.thread

bad.thread:                                       ; preds = %header
  %v.inc1 = add i32 %v.inc4, 1
  br label %loop

bad:                                              ; preds = %entry, %header
  %v.1.h = phi i32 [ %A, %entry ], [ %v.inc4, %header ]
  %w.1.h = phi i32 [ %C, %entry ], [ %v.inc4, %header ]
  %v.inc = add i32 %v.1.h, 1
  %cmp2 = icmp eq i32 %B, 0
  br i1 %cmp2, label %exit2, label %loop

loop:                                             ; preds = %bad.thread, %bad
  %v.inc4 = phi i32 [ %v.inc1, %bad.thread ], [ %v.inc, %bad ]
  %w3 = phi i32 [ %v.inc1, %bad.thread ], [ %w.1.h, %bad ]
  call void @foo(i32 %v.inc4)
  %cmp = icmp sgt i32 %v.inc4, 170
  br i1 %cmp, label %exit, label %header

exit:                                             ; preds = %loop
  ret i32 %w3

exit2:                                            ; preds = %bad
  ret i32 0
}
====================================================================

In thee orginal program in
  ret i32 %w
%w is always less than %v.inc (which is an argument of call) by one.

In the result program return value is always equal to argument to call.

-- 
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/20190531/5ff5a22f/attachment.html>