llvm/test/Transforms/PhaseOrdering/scev-custom-dl.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 4
   2 ; RUN: opt -passes='default<O3>,print<scalar-evolution>' -disable-output -S < %s 2>&1 | FileCheck %s
   3
   4 target datalayout = "e-m:m-p:40:64:64:32-i32:32-i16:16-i8:8-n32"
   5
   6 ;
   7 ; This file contains phase ordering tests for scalar evolution.
   8 ; Test that the standard passes don't obfuscate the IR so scalar evolution can't
   9 ; recognize expressions.
  10
  11 ; The loop body contains two increments by %div.
  12 ; Make sure that 2*%div is recognizable, and not expressed as a bit mask of %d.
  13 define void @test1(i32 %d, ptr %p) nounwind uwtable ssp {
  14 ; CHECK-LABEL: 'test1'
  15 ; CHECK-NEXT:  Classifying expressions for: @test1
  16 ; CHECK-NEXT:    %div1 = lshr i32 %d, 2
  17 ; CHECK-NEXT:    --> (%d /u 4) U: [0,1073741824) S: [0,1073741824)
  18 ; CHECK-NEXT:    %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  19 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,64) S: [0,64) Exits: 63 LoopDispositions: { %for.body: Computable }
  20 ; CHECK-NEXT:    %p.addr.02 = phi ptr [ %p, %entry ], [ %add.ptr1, %for.body ]
  21 ; CHECK-NEXT:    --> {%p,+,(8 * (%d /u 4))}<%for.body> U: full-set S: full-set Exits: ((504 * (%d /u 4)) + %p) LoopDispositions: { %for.body: Computable }
  22 ; CHECK-NEXT:    %add.ptr = getelementptr inbounds i32, ptr %p.addr.02, i32 %div1
  23 ; CHECK-NEXT:    --> {((4 * (%d /u 4))<nuw><nsw> + %p),+,(8 * (%d /u 4))}<%for.body> U: full-set S: full-set Exits: ((508 * (%d /u 4)) + %p) LoopDispositions: { %for.body: Computable }
  24 ; CHECK-NEXT:    %add.ptr1 = getelementptr inbounds i32, ptr %add.ptr, i32 %div1
  25 ; CHECK-NEXT:    --> {((8 * (%d /u 4)) + %p),+,(8 * (%d /u 4))}<%for.body> U: full-set S: full-set Exits: ((512 * (%d /u 4)) + %p) LoopDispositions: { %for.body: Computable }
  26 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.03, 1
  27 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,65) S: [1,65) Exits: 64 LoopDispositions: { %for.body: Computable }
  28 ; CHECK-NEXT:  Determining loop execution counts for: @test1
  29 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i32 63
  30 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 63
  31 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i32 63
  32 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 64
  33 ;
  34 entry:
  35   %div = udiv i32 %d, 4
  36   br label %for.cond
  37
  38 for.cond:                                         ; preds = %for.inc, %entry
  39   %p.addr.0 = phi ptr [ %p, %entry ], [ %add.ptr1, %for.inc ]
  40   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  41   %cmp = icmp ne i32 %i.0, 64
  42   br i1 %cmp, label %for.body, label %for.end
  43
  44 for.body:                                         ; preds = %for.cond
  45   store i32 0, ptr %p.addr.0, align 4
  46   %add.ptr = getelementptr inbounds i32, ptr %p.addr.0, i32 %div
  47   store i32 1, ptr %add.ptr, align 4
  48   %add.ptr1 = getelementptr inbounds i32, ptr %add.ptr, i32 %div
  49   br label %for.inc
  50
  51 for.inc:                                          ; preds = %for.body
  52   %inc = add i32 %i.0, 1
  53   br label %for.cond
  54
  55 for.end:                                          ; preds = %for.cond
  56   ret void
  57 }
  58
  59 ; Same thing as test1, but it is even more tempting to fold 2 * (%d /u 2)
  60 define void @test1a(i32 %d, ptr %p) nounwind uwtable ssp {
  61 ; CHECK-LABEL: 'test1a'
  62 ; CHECK-NEXT:  Classifying expressions for: @test1a
  63 ; CHECK-NEXT:    %div1 = lshr i32 %d, 1
  64 ; CHECK-NEXT:    --> (%d /u 2) U: [0,-2147483648) S: [0,-2147483648)
  65 ; CHECK-NEXT:    %i.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  66 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%for.body> U: [0,64) S: [0,64) Exits: 63 LoopDispositions: { %for.body: Computable }
  67 ; CHECK-NEXT:    %p.addr.02 = phi ptr [ %p, %entry ], [ %add.ptr1, %for.body ]
  68 ; CHECK-NEXT:    --> {%p,+,(8 * (%d /u 2))}<%for.body> U: full-set S: full-set Exits: ((504 * (%d /u 2)) + %p) LoopDispositions: { %for.body: Computable }
  69 ; CHECK-NEXT:    %add.ptr = getelementptr inbounds i32, ptr %p.addr.02, i32 %div1
  70 ; CHECK-NEXT:    --> {((4 * (%d /u 2))<nuw><nsw> + %p),+,(8 * (%d /u 2))}<%for.body> U: full-set S: full-set Exits: ((508 * (%d /u 2)) + %p) LoopDispositions: { %for.body: Computable }
  71 ; CHECK-NEXT:    %add.ptr1 = getelementptr inbounds i32, ptr %add.ptr, i32 %div1
  72 ; CHECK-NEXT:    --> {((8 * (%d /u 2)) + %p),+,(8 * (%d /u 2))}<%for.body> U: full-set S: full-set Exits: ((512 * (%d /u 2)) + %p) LoopDispositions: { %for.body: Computable }
  73 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.03, 1
  74 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,65) S: [1,65) Exits: 64 LoopDispositions: { %for.body: Computable }
  75 ; CHECK-NEXT:  Determining loop execution counts for: @test1a
  76 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is i32 63
  77 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is i32 63
  78 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is i32 63
  79 ; CHECK-NEXT:  Loop %for.body: Trip multiple is 64
  80 ;
  81 entry:
  82   %div = udiv i32 %d, 2
  83   br label %for.cond
  84
  85 for.cond:                                         ; preds = %for.inc, %entry
  86   %p.addr.0 = phi ptr [ %p, %entry ], [ %add.ptr1, %for.inc ]
  87   %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  88   %cmp = icmp ne i32 %i.0, 64
  89   br i1 %cmp, label %for.body, label %for.end
  90
  91 for.body:                                         ; preds = %for.cond
  92   store i32 0, ptr %p.addr.0, align 4
  93   %add.ptr = getelementptr inbounds i32, ptr %p.addr.0, i32 %div
  94   store i32 1, ptr %add.ptr, align 4
  95   %add.ptr1 = getelementptr inbounds i32, ptr %add.ptr, i32 %div
  96   br label %for.inc
  97
  98 for.inc:                                          ; preds = %for.body
  99   %inc = add i32 %i.0, 1
 100   br label %for.cond
 101
 102 for.end:                                          ; preds = %for.cond
 103   ret void
 104 }
 105
 106 @array = weak global [101 x i32] zeroinitializer, align 32              ; <ptr> [#uses=1]
 107
 108
 109 define void @test_range_ref1a(i32 %x) {
 110 ; CHECK-LABEL: 'test_range_ref1a'
 111 ; CHECK-NEXT:  Classifying expressions for: @test_range_ref1a
 112 ; CHECK-NEXT:    %i.01.0 = phi i32 [ 100, %entry ], [ %tmp4, %bb ]
 113 ; CHECK-NEXT:    --> {100,+,-1}<nsw><%bb> U: [0,101) S: [0,101) Exits: 0 LoopDispositions: { %bb: Computable }
 114 ; CHECK-NEXT:    %tmp1 = getelementptr [101 x i32], ptr @array, i32 0, i32 %i.01.0
 115 ; CHECK-NEXT:    --> {(400 + @array),+,-4}<nw><%bb> U: [0,-3) S: [-2147483648,2147483645) Exits: @array LoopDispositions: { %bb: Computable }
 116 ; CHECK-NEXT:    %tmp4 = add nsw i32 %i.01.0, -1
 117 ; CHECK-NEXT:    --> {99,+,-1}<nsw><%bb> U: [-1,100) S: [-1,100) Exits: -1 LoopDispositions: { %bb: Computable }
 118 ; CHECK-NEXT:  Determining loop execution counts for: @test_range_ref1a
 119 ; CHECK-NEXT:  Loop %bb: backedge-taken count is i32 100
 120 ; CHECK-NEXT:  Loop %bb: constant max backedge-taken count is i32 100
 121 ; CHECK-NEXT:  Loop %bb: symbolic max backedge-taken count is i32 100
 122 ; CHECK-NEXT:  Loop %bb: Trip multiple is 101
 123 ;
 124 entry:
 125         br label %bb
 126
 127 bb:             ; preds = %bb, %entry
 128         %i.01.0 = phi i32 [ 100, %entry ], [ %tmp4, %bb ]               ; <i32> [#uses=2]
 129         %tmp1 = getelementptr [101 x i32], ptr @array, i32 0, i32 %i.01.0               ; <ptr> [#uses=1]
 130         store i32 %x, ptr %tmp1
 131         %tmp4 = add i32 %i.01.0, -1             ; <i32> [#uses=2]
 132         %tmp7 = icmp sgt i32 %tmp4, -1          ; <i1> [#uses=1]
 133         br i1 %tmp7, label %bb, label %return
 134
 135 return:         ; preds = %bb
 136         ret void
 137 }
 138
 139 define i32 @test_loop_idiom_recogize(i32 %x, i32 %y, ptr %lam, ptr %alp) nounwind {
 140 ; CHECK-LABEL: 'test_loop_idiom_recogize'
 141 ; CHECK-NEXT:  Classifying expressions for: @test_loop_idiom_recogize
 142 ; CHECK-NEXT:    %indvar = phi i32 [ 0, %bb1.thread ], [ %indvar.next, %bb1 ]
 143 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%bb1> U: [0,256) S: [0,256) Exits: 255 LoopDispositions: { %bb1: Computable }
 144 ; CHECK-NEXT:    %i.0.reg2mem.0 = sub nuw nsw i32 255, %indvar
 145 ; CHECK-NEXT:    --> {255,+,-1}<nsw><%bb1> U: [0,256) S: [0,256) Exits: 0 LoopDispositions: { %bb1: Computable }
 146 ; CHECK-NEXT:    %0 = getelementptr i32, ptr %alp, i32 %i.0.reg2mem.0
 147 ; CHECK-NEXT:    --> {(1020 + %alp),+,-4}<nw><%bb1> U: full-set S: full-set Exits: %alp LoopDispositions: { %bb1: Computable }
 148 ; CHECK-NEXT:    %1 = load i32, ptr %0, align 4
 149 ; CHECK-NEXT:    --> %1 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb1: Variant }
 150 ; CHECK-NEXT:    %2 = getelementptr i32, ptr %lam, i32 %i.0.reg2mem.0
 151 ; CHECK-NEXT:    --> {(1020 + %lam),+,-4}<nw><%bb1> U: full-set S: full-set Exits: %lam LoopDispositions: { %bb1: Computable }
 152 ; CHECK-NEXT:    %indvar.next = add nuw nsw i32 %indvar, 1
 153 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%bb1> U: [1,257) S: [1,257) Exits: 256 LoopDispositions: { %bb1: Computable }
 154 ; CHECK-NEXT:    %tmp10 = mul i32 %x, 255
 155 ; CHECK-NEXT:    --> (255 * %x) U: full-set S: full-set
 156 ; CHECK-NEXT:    %z.0.reg2mem.0 = add i32 %y, %x
 157 ; CHECK-NEXT:    --> (%x + %y) U: full-set S: full-set
 158 ; CHECK-NEXT:    %3 = add i32 %z.0.reg2mem.0, %tmp10
 159 ; CHECK-NEXT:    --> ((256 * %x) + %y) U: full-set S: full-set
 160 ; CHECK-NEXT:  Determining loop execution counts for: @test_loop_idiom_recogize
 161 ; CHECK-NEXT:  Loop %bb1: backedge-taken count is i32 255
 162 ; CHECK-NEXT:  Loop %bb1: constant max backedge-taken count is i32 255
 163 ; CHECK-NEXT:  Loop %bb1: symbolic max backedge-taken count is i32 255
 164 ; CHECK-NEXT:  Loop %bb1: Trip multiple is 256
 165 ;
 166 bb1.thread:
 167         br label %bb1
 168
 169 bb1:            ; preds = %bb1, %bb1.thread
 170         %indvar = phi i32 [ 0, %bb1.thread ], [ %indvar.next, %bb1 ]            ; <i32> [#uses=4]
 171         %i.0.reg2mem.0 = sub i32 255, %indvar           ; <i32> [#uses=2]
 172         %0 = getelementptr i32, ptr %alp, i32 %i.0.reg2mem.0            ; <ptr> [#uses=1]
 173         %1 = load i32, ptr %0, align 4          ; <i32> [#uses=1]
 174         %2 = getelementptr i32, ptr %lam, i32 %i.0.reg2mem.0            ; <ptr> [#uses=1]
 175         store i32 %1, ptr %2, align 4
 176         %3 = sub i32 254, %indvar               ; <i32> [#uses=1]
 177         %4 = icmp slt i32 %3, 0         ; <i1> [#uses=1]
 178         %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=1]
 179         br i1 %4, label %bb2, label %bb1
 180
 181 bb2:            ; preds = %bb1
 182         %tmp10 = mul i32 %indvar, %x            ; <i32> [#uses=1]
 183         %z.0.reg2mem.0 = add i32 %tmp10, %y             ; <i32> [#uses=1]
 184         %5 = add i32 %z.0.reg2mem.0, %x         ; <i32> [#uses=1]
 185         ret i32 %5
 186 }
 187
 188 declare void @use(i1)
 189
 190 declare void @llvm.experimental.guard(i1, ...)
 191
 192 ; This tests getRangeRef acts as intended with different idx size.
 193 define void @test_range_ref1(i8 %t) {
 194 ; CHECK-LABEL: 'test_range_ref1'
 195 ; CHECK-NEXT:  Classifying expressions for: @test_range_ref1
 196 ; CHECK-NEXT:    %0 = zext i8 %t to i40
 197 ; CHECK-NEXT:    --> (zext i8 %t to i40) U: [0,256) S: [0,256)
 198 ; CHECK-NEXT:    %t.ptr = inttoptr i40 %0 to ptr
 199 ; CHECK-NEXT:    --> %t.ptr U: [0,256) S: [0,256)
 200 ; CHECK-NEXT:    %idx = phi ptr [ %t.ptr, %entry ], [ %snext, %loop ]
 201 ; CHECK-NEXT:    --> {%t.ptr,+,1}<nuw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 202 ; CHECK-NEXT:    %snext = getelementptr inbounds i8, ptr %idx, i32 1
 203 ; CHECK-NEXT:    --> {(1 + %t.ptr)<nuw><nsw>,+,1}<nw><%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 204 ; CHECK-NEXT:  Determining loop execution counts for: @test_range_ref1
 205 ; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
 206 ; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
 207 ; CHECK-NEXT:  Loop %loop: Unpredictable symbolic max backedge-taken count.
 208 ;
 209  entry:
 210   %t.ptr = inttoptr i8 %t to ptr
 211   %p.42 = inttoptr i8 42 to ptr
 212   %cmp1 = icmp slt ptr %t.ptr, %p.42
 213   call void(i1, ...) @llvm.experimental.guard(i1 %cmp1) [ "deopt"() ]
 214   br label %loop
 215
 216  loop:
 217   %idx = phi ptr [ %t.ptr, %entry ], [ %snext, %loop ]
 218   %snext = getelementptr inbounds i8, ptr %idx, i64 1
 219   %c = icmp slt ptr %idx, %p.42
 220   call void @use(i1 %c)
 221   %be = icmp slt ptr %snext, %p.42
 222   br i1 %be, label %loop, label %exit
 223
 224  exit:
 225   ret void
 226 }
 227