llvm/test/Analysis/ScalarEvolution/decrementing_addrecs.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 2
   2 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s --check-prefix=DEFAULT
   3 ; RUN: opt -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-use-expensive-range-sharpening < %s 2>&1 | FileCheck %s  --check-prefix=EXPENSIVE_SHARPENING
   4
   5 ; This test exercises the following scenario:
   6 ; given: n > 0
   7 ; for (i = 0, j = n - 1; i < n; i++, j--) {
   8 ;   a = n - i;
   9 ;   b = (n - 1) - i;
  10 ;   c = 2147483647 - 1;
  11 ; }
  12 ;
  13 ; Note that value ranges of 'i' and 'j' are the same, just inverted. It means that
  14 ; they have same ranges and same no-wrap properties. 'b' is just an alternative
  15 ; way to compute the same value as 'j'. 'a' is effectively 'j + 1' and 'c' is a
  16 ; a positive value. All involved addrecs for 'i', 'j', 'a', 'b', 'c' should have
  17 ; no-sign-wrap flag.
  18 ;
  19 ;        i's AddRec is expected to be proven no-sign-wrap
  20 ;        j's AddRec is expected to be proven no-sign-wrap
  21 ; FIXME: a's AddRec is expected to be no-sign-wrap
  22 ;        b's AddRec is expected to be no-sign-wrap
  23 ; FIXME: c's AddRec is expected to be no-sign-wrap
  24 ;        i is expected to be non-negative
  25 ;        j is expected to be non-negative
  26 ;        a is expected to be positive
  27 ;        b is expected to be non-negative
  28 ;        c is expected to be positive
  29 define i32 @test_step_1_flags(i32 %n) {
  30 ; DEFAULT-LABEL: 'test_step_1_flags'
  31 ; DEFAULT-NEXT:  Classifying expressions for: @test_step_1_flags
  32 ; DEFAULT-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
  33 ; DEFAULT-NEXT:    --> (-1 + %n) U: full-set S: full-set
  34 ; DEFAULT-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  35 ; DEFAULT-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }
  36 ; DEFAULT-NEXT:    %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ]
  37 ; DEFAULT-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
  38 ; DEFAULT-NEXT:    %a = sub i32 %n, %i
  39 ; DEFAULT-NEXT:    --> {%n,+,-1}<nw><%loop> U: full-set S: full-set Exits: 1 LoopDispositions: { %loop: Computable }
  40 ; DEFAULT-NEXT:    %b = sub i32 %n.minus.1, %i
  41 ; DEFAULT-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: full-set S: full-set Exits: 0 LoopDispositions: { %loop: Computable }
  42 ; DEFAULT-NEXT:    %c = sub i32 2147483647, %i
  43 ; DEFAULT-NEXT:    --> {2147483647,+,-1}<nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
  44 ; DEFAULT-NEXT:    %i.next = add nuw nsw i32 %i, 1
  45 ; DEFAULT-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
  46 ; DEFAULT-NEXT:    %j.next = add nsw i32 %j, -1
  47 ; DEFAULT-NEXT:    --> {(-2 + %n),+,-1}<nw><%loop> U: full-set S: full-set Exits: -1 LoopDispositions: { %loop: Computable }
  48 ; DEFAULT-NEXT:  Determining loop execution counts for: @test_step_1_flags
  49 ; DEFAULT-NEXT:  Loop %loop: backedge-taken count is (-1 + %n)
  50 ; DEFAULT-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
  51 ; DEFAULT-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %n)
  52 ; DEFAULT-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %n)
  53 ; DEFAULT-NEXT:   Predicates:
  54 ; DEFAULT-NEXT:  Loop %loop: Trip multiple is 1
  55 ;
  56 ; EXPENSIVE_SHARPENING-LABEL: 'test_step_1_flags'
  57 ; EXPENSIVE_SHARPENING-NEXT:  Classifying expressions for: @test_step_1_flags
  58 ; EXPENSIVE_SHARPENING-NEXT:    %n.minus.1 = sub nsw i32 %n, 1
  59 ; EXPENSIVE_SHARPENING-NEXT:    --> (-1 + %n) U: full-set S: full-set
  60 ; EXPENSIVE_SHARPENING-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  61 ; EXPENSIVE_SHARPENING-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + %n) LoopDispositions: { %loop: Computable }
  62 ; EXPENSIVE_SHARPENING-NEXT:    %j = phi i32 [ %n.minus.1, %entry ], [ %j.next, %loop ]
  63 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
  64 ; EXPENSIVE_SHARPENING-NEXT:    %a = sub i32 %n, %i
  65 ; EXPENSIVE_SHARPENING-NEXT:    --> {%n,+,-1}<nw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: 1 LoopDispositions: { %loop: Computable }
  66 ; EXPENSIVE_SHARPENING-NEXT:    %b = sub i32 %n.minus.1, %i
  67 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-1 + %n),+,-1}<nsw><%loop> U: [0,2147483647) S: [0,2147483647) Exits: 0 LoopDispositions: { %loop: Computable }
  68 ; EXPENSIVE_SHARPENING-NEXT:    %c = sub i32 2147483647, %i
  69 ; EXPENSIVE_SHARPENING-NEXT:    --> {2147483647,+,-1}<nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: (-2147483648 + (-1 * %n)) LoopDispositions: { %loop: Computable }
  70 ; EXPENSIVE_SHARPENING-NEXT:    %i.next = add nuw nsw i32 %i, 1
  71 ; EXPENSIVE_SHARPENING-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
  72 ; EXPENSIVE_SHARPENING-NEXT:    %j.next = add nsw i32 %j, -1
  73 ; EXPENSIVE_SHARPENING-NEXT:    --> {(-2 + %n),+,-1}<nsw><%loop> U: full-set S: [-1,2147483646) Exits: -1 LoopDispositions: { %loop: Computable }
  74 ; EXPENSIVE_SHARPENING-NEXT:  Determining loop execution counts for: @test_step_1_flags
  75 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: backedge-taken count is (-1 + %n)
  76 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: constant max backedge-taken count is 2147483646
  77 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %n)
  78 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %n)
  79 ; EXPENSIVE_SHARPENING-NEXT:   Predicates:
  80 ; EXPENSIVE_SHARPENING-NEXT:  Loop %loop: Trip multiple is 1
  81 ;
  82 entry:
  83   %n.minus.1 = sub nsw i32 %n, 1
  84   %precond = icmp sgt i32 %n, 0
  85   br i1 %precond, label %loop, label %fail
  86
  87 loop:
  88   %i = phi i32 [0, %entry], [%i.next, %loop]                      ; 0...n-1
  89   %j = phi i32 [%n.minus.1, %entry], [%j.next, %loop]             ; n-1...0
  90   %a = sub i32 %n, %i                                             ; n...1
  91   %b = sub i32 %n.minus.1, %i                                     ; n-1...0
  92   %c = sub i32 2147483647, %i                                     ; 2147483647...1
  93   %i.next = add nuw nsw i32 %i, 1
  94   %j.next = add nsw i32 %j, -1
  95   %cond = icmp slt i32 %i.next, %n
  96   br i1 %cond, label %loop, label %exit
  97
  98 fail:
  99   ret i32 -1
 100
 101 exit:
 102   ret i32 0
 103 }