[llvm-bugs] [Bug 42175] New: [SCEV] computeMaxBECountForLT() returns wrong result

[via llvm-bugs]

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

            Bug ID: 42175
           Summary: [SCEV] computeMaxBECountForLT() returns wrong result
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: zhaoshiz at quicinc.com
                CC: htmldeveloper at gmail.com, llvm-bugs at lists.llvm.org

$ cat loop-small-runtime-upperbound.ll 
target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"

@global = dso_local local_unnamed_addr global i32 0, align 4
@global.1 = dso_local local_unnamed_addr global i8* null, align 4

define dso_local void @hoge(i8 %arg) {
entry:
  %x = load i32, i32* @global, align 4
  %0 = icmp ult i32 %x, 17
  br i1 %0, label %loop, label %exit

loop:
  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
  %iv.next = add nuw i32 %iv, 8
  %1 = load i8*, i8** @global.1, align 4
  %2 = getelementptr inbounds i8, i8* %1, i32 1
  store i8* %2, i8** @global.1, align 4
  store i8 %arg, i8* %1, align 1
  %3 = icmp ult i32 %iv.next, 17
  br i1 %3, label %loop, label %exit

exit:                                             ; preds = %bb12, %bb
  ret void
}


$ opt loop-small-runtime-upperbound.ll -analyze -scalar-evolution
Printing analysis 'Scalar Evolution Analysis' for function 'hoge':
Classifying expressions for: @hoge
  %x = load i32, i32* @global, align 4
  -->  %x U: full-set S: full-set
  %iv = phi i32 [ %x, %entry ], [ %iv.next, %loop ]
  -->  {%x,+,8}<nuw><%loop> U: full-set S: full-set             Exits: ((8 *
((16 + (-1 * %x)) /u 8))<nuw> + %x)                LoopDispositions: { %loop:
Computable }
  %iv.next = add nuw i32 %iv, 8
  -->  {(8 + %x),+,8}<nuw><%loop> U: full-set S: full-set               Exits:
(8 + (8 * ((16 + (-1 * %x)) /u 8))<nuw> + %x)            LoopDispositions: {
%loop: Computable }
  %1 = load i8*, i8** @global.1, align 4
  -->  %1 U: full-set S: full-set               Exits: <<Unknown>>             
LoopDispositions: { %loop: Variant }
  %2 = getelementptr inbounds i8, i8* %1, i32 1
  -->  (1 + %1)<nsw> U: full-set S: full-set            Exits: <<Unknown>>     
        LoopDispositions: { %loop: Variant }
Determining loop execution counts for: @hoge
Loop %loop: backedge-taken count is ((16 + (-1 * %x)) /u 8)
Loop %loop: max backedge-taken count is 3
Loop %loop: Predicated backedge-taken count is ((16 + (-1 * %x)) /u 8)
 Predicates:

Loop %loop: Trip multiple is 1

The loop runs a max of 3 iters, but SCEV computes max BE-taken count as 3.
The same issue is also found in
test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll, where max BE-taken count
is 333 instead of 334.

The problem is in computeMaxBECountForLT(), when Start is a (C + %x), where C
is a constant and %x is an unknown.
getUnsignedRangeMin(Start) returns full-set because of %x. But loop entry is
guarded by:
  %0 = icmp ult i32 %x, 17
so x is known in [0, 17), thus MinStart shall be C rather than 0.

-- 
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/20190607/589c2d8b/attachment-0001.html>