[llvm-bugs] [Bug 51669] New: LoopIdiomRecognize: Overflow in ctlz shifting loop

[via llvm-bugs]

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

            Bug ID: 51669
           Summary: LoopIdiomRecognize: Overflow in ctlz shifting loop
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Keywords: miscompilation
          Severity: enhancement
          Priority: P
         Component: Loop Optimizer
          Assignee: unassignedbugs at nondot.org
          Reporter: nunoplopes at sapo.pt
                CC: lebedev.ri at gmail.com, llvm-bugs at lists.llvm.org,
                    zhuhan7737 at gmail.com

Test: Transforms/LoopIdiom/X86/arithmetic-right-shift-until-zero.ll

LoopIdiom creates expressions that overflow and produce incorrect result.
e.g. this instruction:
add nsw i8 %val.numactivebits, %0

overflows and yields poison. Even removing nsw doesn't fix the issue; see
counterexample below.


----------------------------------------
define i8 @p0(i8 %val, i8 %start, i8 %extraoffset) {
%entry:
  br label %loop

%loop:
  %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  %nbits = add nsw i8 %iv, %extraoffset
  %val.shifted = ashr i8 %val, %nbits
  %val.shifted.iszero = icmp eq i8 %val.shifted, 0
  %iv.next = add i8 %iv, 1
  call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1
%val.shifted.iszero, i8 %iv.next)
  br i1 %val.shifted.iszero, label %end, label %loop

%end:
  %iv.res = phi i8 [ %iv, %loop ]
  %nbits.res = phi i8 [ %nbits, %loop ]
  %val.shifted.res = phi i8 [ %val.shifted, %loop ]
  %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
  %iv.next.res = phi i8 [ %iv.next, %loop ]
  call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1
%val.shifted.iszero.res, i8 %iv.next.res)
  ret i8 %iv.res
}
=>
define i8 @p0(i8 %val, i8 %start, i8 %extraoffset) {
%entry:
  %val.numleadingzeros = ctlz i8 %val, 0
  %val.numactivebits = sub nsw nuw i8 8, %val.numleadingzeros
  %0 = sub i8 0, %extraoffset
  %val.numactivebits.offset = add i8 %val.numactivebits, %0
  %iv.final = smax i8 %val.numactivebits.offset, %start
  %loop.backedgetakencount = sub nsw i8 %iv.final, %start
  %loop.tripcount = add nsw nuw i8 %loop.backedgetakencount, 1
  br label %loop

%loop:
  %loop.iv = phi i8 [ 0, %entry ], [ %loop.iv.next, %loop ]
  %loop.iv.next = add nsw nuw i8 %loop.iv, 1
  %loop.ivcheck = icmp eq i8 %loop.iv.next, %loop.tripcount
  %iv = add nsw i8 %loop.iv, %start
  %nbits = add nsw i8 %iv, %extraoffset
  %val.shifted = ashr i8 %val, %nbits
  %iv.next = add i8 %iv, 1
  call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %loop.ivcheck,
i8 %iv.next)
  br i1 %loop.ivcheck, label %end, label %loop

%end:
  %iv.res = phi i8 [ %iv.final, %loop ]
  %nbits.res = phi i8 [ %nbits, %loop ]
  %val.shifted.res = phi i8 [ %val.shifted, %loop ]
  %val.shifted.iszero.res = phi i1 [ %loop.ivcheck, %loop ]
  %iv.next.res = phi i8 [ %iv.next, %loop ]
  call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1
%val.shifted.iszero.res, i8 %iv.next.res)
  ret i8 %iv.res
}
Transformation doesn't verify!

ERROR: Source is more defined than target

Example:
i8 %val = #x80 (128, -128)
i8 %start = #x78 (120)
i8 %extraoffset = #x88 (136, -120)

Source:
i8 %iv = #x78 (120)
i8 %nbits = #x00 (0)
i8 %val.shifted = #x80 (128, -128)
i1 %val.shifted.iszero = #x0 (0)
i8 %iv.next = #x79 (121)

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 >       size: 0 align: 1        alloc type: 0
Block 1 >       size: 0 align: 1

Target:
i8 %val.numleadingzeros = #x00 (0)
i8 %val.numactivebits = #x08 (8)
i8 %0 = #x78 (120)
i8 %val.numactivebits.offset = #x80 (128, -128)
i8 %iv.final = #x78 (120)
i8 %loop.backedgetakencount = #x00 (0)
i8 %loop.tripcount = #x01 (1)
i8 %loop.iv = #x00 (0)
i8 %loop.iv.next = #x01 (1)
i1 %loop.ivcheck = #x1 (1)
i8 %iv = #x78 (120)
i8 %nbits = #x00 (0)
i8 %val.shifted = #x80 (128, -128)
i8 %iv.next = #x79 (121)
i8 %iv.res = #x78 (120)
i8 %nbits.res = #x00 (0)
i8 %val.shifted.res = #x80 (128, -128)
i1 %val.shifted.iszero.res = #x1 (1)
i8 %iv.next.res = #x79 (121)

-- 
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/20210830/6183d408/attachment-0001.html>