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 4target 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. 13define 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 nuw i32, ptr %p.addr.02, i32 %div1 23; CHECK-NEXT: --> {((4 * (%d /u 4))<nuw><nsw> + %p)<nuw>,+,(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 nuw 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; 34entry: 35 %div = udiv i32 %d, 4 36 br label %for.cond 37 38for.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 44for.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 51for.inc: ; preds = %for.body 52 %inc = add i32 %i.0, 1 53 br label %for.cond 54 55for.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) 60define 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 nuw i32, ptr %p.addr.02, i32 %div1 70; CHECK-NEXT: --> {((4 * (%d /u 2))<nuw><nsw> + %p)<nuw>,+,(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 nuw 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; 81entry: 82 %div = udiv i32 %d, 2 83 br label %for.cond 84 85for.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 91for.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 98for.inc: ; preds = %for.body 99 %inc = add i32 %i.0, 1 100 br label %for.cond 101 102for.end: ; preds = %for.cond 103 ret void 104} 105 106@array = weak global [101 x i32] zeroinitializer, align 32 ; <ptr> [#uses=1] 107 108 109define 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)<nuw>,+,-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; 124entry: 125 br label %bb 126 127bb: ; 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 135return: ; preds = %bb 136 ret void 137} 138 139define 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; 166bb1.thread: 167 br label %bb1 168 169bb1: ; 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 181bb2: ; 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 188declare void @use(i1) 189 190declare void @llvm.experimental.guard(i1, ...) 191 192; This tests getRangeRef acts as intended with different idx size. 193define 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 nuw 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 228