1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py 2; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s 3 4; Tests for checking the trip multiple in loops where we cmp induction variables 5; against Min/Max SCEVs 6 7define void @nomulitply(i32 noundef %a, i32 noundef %b) { 8; CHECK-LABEL: 'nomulitply' 9; CHECK-NEXT: Classifying expressions for: @nomulitply 10; CHECK-NEXT: %cond = select i1 %cmp, i32 %a, i32 %b 11; CHECK-NEXT: --> (%a umin %b) U: full-set S: full-set 12; CHECK-NEXT: %i.08 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 13; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + (%a umin %b)) LoopDispositions: { %for.body: Computable } 14; CHECK-NEXT: %inc = add nuw nsw i32 %i.08, 1 15; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: (%a umin %b) LoopDispositions: { %for.body: Computable } 16; CHECK-NEXT: Determining loop execution counts for: @nomulitply 17; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + (%a umin %b)) 18; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 2147483646 19; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (%a umin %b)) 20; CHECK-NEXT: Loop %for.body: Trip multiple is 1 21; 22; No information about a or b. Trip multiple is 1. 23; void nomulitple(unsigned a, unsigned b) { 24; int N = a < b ? a : b; 25; for (int i = 0; i < N; ++i) { 26; foo(); 27; } 28; } 29 30entry: 31 %cmp = icmp ult i32 %a, %b 32 %cond = select i1 %cmp, i32 %a, i32 %b 33 %cmp17 = icmp sgt i32 %cond, 0 34 br i1 %cmp17, label %for.body, label %for.cond.cleanup 35 36for.cond.cleanup: ; preds = %for.body, %entry 37 ret void 38 39for.body: ; preds = %entry, %for.body 40 %i.08 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 41 tail call void (...) @foo() #2 42 %inc = add nuw nsw i32 %i.08, 1 43 %exitcond.not = icmp eq i32 %inc, %cond 44 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 45} 46 47define void @umin(i32 noundef %a, i32 noundef %b) { 48; CHECK-LABEL: 'umin' 49; CHECK-NEXT: Classifying expressions for: @umin 50; CHECK-NEXT: %mul = shl i32 %a, 1 51; CHECK-NEXT: --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647) 52; CHECK-NEXT: %mul1 = shl i32 %b, 2 53; CHECK-NEXT: --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645) 54; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 55; CHECK-NEXT: --> ((2 * %a) umin (4 * %b)) U: [0,-3) S: [-2147483648,2147483647) 56; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 57; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a) umin (4 * %b))) LoopDispositions: { %for.body: Computable } 58; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 59; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a) umin (4 * %b)) LoopDispositions: { %for.body: Computable } 60; CHECK-NEXT: Determining loop execution counts for: @umin 61; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umin (4 * %b))) 62; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 2147483646 63; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umin (4 * %b))) 64; CHECK-NEXT: Loop %for.body: Trip multiple is 1 65; 66; void umin(unsigned a, unsigned b) { 67; a *= 2; 68; b *= 4; 69; int N = a < b ? a : b; 70; for (int i = 0; i < N; ++i) { 71; foo(); 72; } 73; } 74 75entry: 76 %mul = shl i32 %a, 1 77 %mul1 = shl i32 %b, 2 78 %cmp = icmp ult i32 %mul, %mul1 79 %cond = select i1 %cmp, i32 %mul, i32 %mul1 80 %cmp210 = icmp sgt i32 %cond, 0 81 br i1 %cmp210, label %for.body, label %for.cond.cleanup 82 83for.cond.cleanup: ; preds = %for.body, %entry 84 ret void 85 86for.body: ; preds = %entry, %for.body 87 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 88 tail call void (...) @foo() #2 89 %inc = add nuw nsw i32 %i.011, 1 90 %exitcond.not = icmp eq i32 %inc, %cond 91 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 92} 93 94 95define void @umax(i32 noundef %a, i32 noundef %b) { 96; CHECK-LABEL: 'umax' 97; CHECK-NEXT: Classifying expressions for: @umax 98; CHECK-NEXT: %mul = shl i32 %a, 1 99; CHECK-NEXT: --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647) 100; CHECK-NEXT: %mul1 = shl i32 %b, 2 101; CHECK-NEXT: --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645) 102; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 103; CHECK-NEXT: --> ((2 * %a) umax (4 * %b)) U: [0,-1) S: [-2147483648,2147483647) 104; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 105; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a) umax (4 * %b))) LoopDispositions: { %for.body: Computable } 106; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 107; CHECK-NEXT: --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a) umax (4 * %b)) LoopDispositions: { %for.body: Computable } 108; CHECK-NEXT: Determining loop execution counts for: @umax 109; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((2 * %a) umax (4 * %b))) 110; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -3 111; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a) umax (4 * %b))) 112; CHECK-NEXT: Loop %for.body: Trip multiple is 2 113; 114 115; void umax(unsigned a, unsigned b) { 116; a *= 2; 117; b *= 4; 118; int N = a > b ? a : b; 119; for (int i = 0; i < N; ++i) { 120; foo(); 121; } 122; } 123 124entry: 125 %mul = shl i32 %a, 1 126 %mul1 = shl i32 %b, 2 127 %cmp = icmp ugt i32 %mul, %mul1 128 %cond = select i1 %cmp, i32 %mul, i32 %mul1 129 %cmp210 = icmp sgt i32 %cond, 0 130 br i1 %cmp210, label %for.body, label %for.cond.cleanup 131 132for.cond.cleanup: ; preds = %for.body, %entry 133 ret void 134 135for.body: ; preds = %entry, %for.body 136 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 137 tail call void (...) @foo() #2 138 %inc = add nuw nsw i32 %i.011, 1 139 %exitcond.not = icmp eq i32 %inc, %cond 140 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 141} 142 143define void @smin(i32 noundef %a, i32 noundef %b) { 144; CHECK-LABEL: 'smin' 145; CHECK-NEXT: Classifying expressions for: @smin 146; CHECK-NEXT: %mul = shl nsw i32 %a, 1 147; CHECK-NEXT: --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647) 148; CHECK-NEXT: %mul1 = shl nsw i32 %b, 2 149; CHECK-NEXT: --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645) 150; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 151; CHECK-NEXT: --> ((2 * %a)<nsw> smin (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483645) 152; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 153; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable } 154; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 155; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((2 * %a)<nsw> smin (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable } 156; CHECK-NEXT: Determining loop execution counts for: @smin 157; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) 158; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 2147483646 159; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smin (4 * %b)<nsw>)) 160; CHECK-NEXT: Loop %for.body: Trip multiple is 1 161; 162; void smin(signed a, signed b) { 163; a *= 2; 164; b *= 4; 165; int N = a < b ? a : b; 166; for (int i = 0; i < N; ++i) { 167; foo(); 168; } 169; } 170 171entry: 172 %mul = shl nsw i32 %a, 1 173 %mul1 = shl nsw i32 %b, 2 174 %cmp = icmp slt i32 %mul, %mul1 175 %cond = select i1 %cmp, i32 %mul, i32 %mul1 176 %cmp210 = icmp sgt i32 %cond, 0 177 br i1 %cmp210, label %for.body, label %for.cond.cleanup 178 179for.cond.cleanup: ; preds = %for.body, %entry 180 ret void 181 182for.body: ; preds = %entry, %for.body 183 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 184 tail call void (...) @foo() #2 185 %inc = add nuw nsw i32 %i.011, 1 186 %exitcond.not = icmp eq i32 %inc, %cond 187 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 188} 189 190define void @smax(i32 noundef %a, i32 noundef %b) { 191; CHECK-LABEL: 'smax' 192; CHECK-NEXT: Classifying expressions for: @smax 193; CHECK-NEXT: %mul = shl nsw i32 %a, 1 194; CHECK-NEXT: --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647) 195; CHECK-NEXT: %mul1 = shl nsw i32 %b, 2 196; CHECK-NEXT: --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645) 197; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 198; CHECK-NEXT: --> ((2 * %a)<nsw> smax (4 * %b)<nsw>) U: [0,-1) S: [-2147483648,2147483647) 199; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 200; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>)) LoopDispositions: { %for.body: Computable } 201; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 202; CHECK-NEXT: --> {1,+,1}<nuw><%for.body> U: [1,-1) S: [1,-1) Exits: ((2 * %a)<nsw> smax (4 * %b)<nsw>) LoopDispositions: { %for.body: Computable } 203; CHECK-NEXT: Determining loop execution counts for: @smax 204; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>)) 205; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 -3 206; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((2 * %a)<nsw> smax (4 * %b)<nsw>)) 207; CHECK-NEXT: Loop %for.body: Trip multiple is 2 208; 209; void smax(signed a, signed b) { 210; a *= 2; 211; b *= 4; 212; int N = a > b ? a : b; 213; for (int i = 0; i < N; ++i) { 214; foo(); 215; } 216; } 217 218entry: 219 %mul = shl nsw i32 %a, 1 220 %mul1 = shl nsw i32 %b, 2 221 %cmp = icmp sgt i32 %mul, %mul1 222 %cond = select i1 %cmp, i32 %mul, i32 %mul1 223 %cmp210 = icmp sgt i32 %cond, 0 224 br i1 %cmp210, label %for.body, label %for.cond.cleanup 225 226for.cond.cleanup: ; preds = %for.body, %entry 227 ret void 228 229for.body: ; preds = %entry, %for.body 230 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 231 tail call void (...) @foo() #2 232 %inc = add nuw nsw i32 %i.011, 1 233 %exitcond.not = icmp eq i32 %inc, %cond 234 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 235} 236 237define void @umin_seq2(i32 %n, i32 %m) { 238; CHECK-LABEL: 'umin_seq2' 239; CHECK-NEXT: Classifying expressions for: @umin_seq2 240; CHECK-NEXT: %n.2 = shl nsw i32 %n, 1 241; CHECK-NEXT: --> (2 * %n) U: [0,-1) S: [-2147483648,2147483647) 242; CHECK-NEXT: %m.2 = shl nsw i32 %m, 4 243; CHECK-NEXT: --> (16 * %m) U: [0,-15) S: [-2147483648,2147483633) 244; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] 245; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))) LoopDispositions: { %loop: Computable } 246; CHECK-NEXT: %i.next = add nuw nsw i32 %i, 1 247; CHECK-NEXT: --> {1,+,1}<nuw><%loop> U: [1,-15) S: [1,-15) Exits: (1 + ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))))<nuw> LoopDispositions: { %loop: Computable } 248; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false 249; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant } 250; CHECK-NEXT: Determining loop execution counts for: @umin_seq2 251; CHECK-NEXT: Loop %loop: backedge-taken count is ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))) 252; CHECK-NEXT: Loop %loop: constant max backedge-taken count is i32 -17 253; CHECK-NEXT: Loop %loop: symbolic max backedge-taken count is ((-1 + (1 umax (2 * %n))) umin_seq (-1 + (1 umax (16 * %m)))) 254; CHECK-NEXT: Loop %loop: Trip multiple is 1 255; 256; Can't find that trip multiple is 2 for this case of umin_seq 257entry: 258 %n.2 = shl nsw i32 %n, 1 259 %m.2 = shl nsw i32 %m, 4 260 br label %loop 261loop: 262 %i = phi i32 [0, %entry], [%i.next, %loop] 263 tail call void (...) @foo() #2 264 %i.next = add nuw nsw i32 %i, 1 265 %cond_p0 = icmp ult i32 %i.next, %n.2 266 %cond_p1 = icmp ult i32 %i.next, %m.2 267 %cond = select i1 %cond_p0, i1 %cond_p1, i1 false 268 br i1 %cond, label %loop, label %exit 269exit: 270 ret void 271} 272 273define void @umin-3and6(i32 noundef %a, i32 noundef %b) { 274; CHECK-LABEL: 'umin-3and6' 275; CHECK-NEXT: Classifying expressions for: @umin-3and6 276; CHECK-NEXT: %mul = mul i32 %a, 3 277; CHECK-NEXT: --> (3 * %a) U: full-set S: full-set 278; CHECK-NEXT: %mul1 = mul i32 %b, 6 279; CHECK-NEXT: --> (6 * %b) U: [0,-1) S: [-2147483648,2147483647) 280; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1 281; CHECK-NEXT: --> ((3 * %a) umin (6 * %b)) U: [0,-1) S: full-set 282; CHECK-NEXT: %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 283; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%for.body> U: [0,2147483647) S: [0,2147483647) Exits: (-1 + ((3 * %a) umin (6 * %b))) LoopDispositions: { %for.body: Computable } 284; CHECK-NEXT: %inc = add nuw nsw i32 %i.011, 1 285; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: ((3 * %a) umin (6 * %b)) LoopDispositions: { %for.body: Computable } 286; CHECK-NEXT: Determining loop execution counts for: @umin-3and6 287; CHECK-NEXT: Loop %for.body: backedge-taken count is (-1 + ((3 * %a) umin (6 * %b))) 288; CHECK-NEXT: Loop %for.body: constant max backedge-taken count is i32 2147483646 289; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + ((3 * %a) umin (6 * %b))) 290; CHECK-NEXT: Loop %for.body: Trip multiple is 1 291; 292; Trip multiple is 1 because we use GetMinTrailingZeros() to compute trip multiples. 293; SCEV cannot compute that the trip multiple is 3. 294; void umin(unsigned a, unsigned b) { 295; a *= 3; 296; b *= 6; 297; int N = a < b ? a : b; 298; for (int i = 0; i < N; ++i) { 299; foo(); 300; } 301; } 302 303entry: 304 %mul = mul i32 %a, 3 305 %mul1 = mul i32 %b, 6 306 %cmp = icmp ult i32 %mul, %mul1 307 %cond = select i1 %cmp, i32 %mul, i32 %mul1 308 %cmp210 = icmp sgt i32 %cond, 0 309 br i1 %cmp210, label %for.body, label %for.cond.cleanup 310 311for.cond.cleanup: ; preds = %for.body, %entry 312 ret void 313 314for.body: ; preds = %entry, %for.body 315 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ] 316 tail call void (...) @foo() #2 317 %inc = add nuw nsw i32 %i.011, 1 318 %exitcond.not = icmp eq i32 %inc, %cond 319 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body 320} 321 322declare void @foo(...) local_unnamed_addr #1 323