323 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py2; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s3 4; Tests for checking the trip multiple in loops where we cmp induction variables5; against Min/Max SCEVs6 7define void @nomulitply(i32 noundef %a, i32 noundef %b) {8; CHECK-LABEL: 'nomulitply'9; CHECK-NEXT: Classifying expressions for: @nomulitply10; CHECK-NEXT: %cond = select i1 %cmp, i32 %a, i32 %b11; CHECK-NEXT: --> (%a umin %b) U: full-set S: full-set12; 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, 115; 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: @nomulitply17; 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 214748364619; CHECK-NEXT: Loop %for.body: symbolic max backedge-taken count is (-1 + (%a umin %b))20; CHECK-NEXT: Loop %for.body: Trip multiple is 121;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, %b32 %cond = select i1 %cmp, i32 %a, i32 %b33 %cmp17 = icmp sgt i32 %cond, 034 br i1 %cmp17, label %for.body, label %for.cond.cleanup35 36for.cond.cleanup: ; preds = %for.body, %entry37 ret void38 39for.body: ; preds = %entry, %for.body40 %i.08 = phi i32 [ %inc, %for.body ], [ 0, %entry ]41 tail call void (...) @foo() #242 %inc = add nuw nsw i32 %i.08, 143 %exitcond.not = icmp eq i32 %inc, %cond44 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body45}46 47define void @umin(i32 noundef %a, i32 noundef %b) {48; CHECK-LABEL: 'umin'49; CHECK-NEXT: Classifying expressions for: @umin50; CHECK-NEXT: %mul = shl i32 %a, 151; CHECK-NEXT: --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)52; CHECK-NEXT: %mul1 = shl i32 %b, 253; CHECK-NEXT: --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)54; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul155; 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, 159; 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: @umin61; 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 214748364663; 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 265;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, 177 %mul1 = shl i32 %b, 278 %cmp = icmp ult i32 %mul, %mul179 %cond = select i1 %cmp, i32 %mul, i32 %mul180 %cmp210 = icmp sgt i32 %cond, 081 br i1 %cmp210, label %for.body, label %for.cond.cleanup82 83for.cond.cleanup: ; preds = %for.body, %entry84 ret void85 86for.body: ; preds = %entry, %for.body87 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]88 tail call void (...) @foo() #289 %inc = add nuw nsw i32 %i.011, 190 %exitcond.not = icmp eq i32 %inc, %cond91 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body92}93 94 95define void @umax(i32 noundef %a, i32 noundef %b) {96; CHECK-LABEL: 'umax'97; CHECK-NEXT: Classifying expressions for: @umax98; CHECK-NEXT: %mul = shl i32 %a, 199; CHECK-NEXT: --> (2 * %a) U: [0,-1) S: [-2147483648,2147483647)100; CHECK-NEXT: %mul1 = shl i32 %b, 2101; CHECK-NEXT: --> (4 * %b) U: [0,-3) S: [-2147483648,2147483645)102; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1103; 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, 1107; 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: @umax109; 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 -3111; 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 2113;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, 1126 %mul1 = shl i32 %b, 2127 %cmp = icmp ugt i32 %mul, %mul1128 %cond = select i1 %cmp, i32 %mul, i32 %mul1129 %cmp210 = icmp sgt i32 %cond, 0130 br i1 %cmp210, label %for.body, label %for.cond.cleanup131 132for.cond.cleanup: ; preds = %for.body, %entry133 ret void134 135for.body: ; preds = %entry, %for.body136 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]137 tail call void (...) @foo() #2138 %inc = add nuw nsw i32 %i.011, 1139 %exitcond.not = icmp eq i32 %inc, %cond140 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body141}142 143define void @smin(i32 noundef %a, i32 noundef %b) {144; CHECK-LABEL: 'smin'145; CHECK-NEXT: Classifying expressions for: @smin146; CHECK-NEXT: %mul = shl nsw i32 %a, 1147; CHECK-NEXT: --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)148; CHECK-NEXT: %mul1 = shl nsw i32 %b, 2149; CHECK-NEXT: --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)150; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1151; 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, 1155; 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: @smin157; 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 2147483646159; 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 2161;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, 1173 %mul1 = shl nsw i32 %b, 2174 %cmp = icmp slt i32 %mul, %mul1175 %cond = select i1 %cmp, i32 %mul, i32 %mul1176 %cmp210 = icmp sgt i32 %cond, 0177 br i1 %cmp210, label %for.body, label %for.cond.cleanup178 179for.cond.cleanup: ; preds = %for.body, %entry180 ret void181 182for.body: ; preds = %entry, %for.body183 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]184 tail call void (...) @foo() #2185 %inc = add nuw nsw i32 %i.011, 1186 %exitcond.not = icmp eq i32 %inc, %cond187 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body188}189 190define void @smax(i32 noundef %a, i32 noundef %b) {191; CHECK-LABEL: 'smax'192; CHECK-NEXT: Classifying expressions for: @smax193; CHECK-NEXT: %mul = shl nsw i32 %a, 1194; CHECK-NEXT: --> (2 * %a)<nsw> U: [0,-1) S: [-2147483648,2147483647)195; CHECK-NEXT: %mul1 = shl nsw i32 %b, 2196; CHECK-NEXT: --> (4 * %b)<nsw> U: [0,-3) S: [-2147483648,2147483645)197; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1198; 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, 1202; 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: @smax204; 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 -3206; 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 2208;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, 1220 %mul1 = shl nsw i32 %b, 2221 %cmp = icmp sgt i32 %mul, %mul1222 %cond = select i1 %cmp, i32 %mul, i32 %mul1223 %cmp210 = icmp sgt i32 %cond, 0224 br i1 %cmp210, label %for.body, label %for.cond.cleanup225 226for.cond.cleanup: ; preds = %for.body, %entry227 ret void228 229for.body: ; preds = %entry, %for.body230 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]231 tail call void (...) @foo() #2232 %inc = add nuw nsw i32 %i.011, 1233 %exitcond.not = icmp eq i32 %inc, %cond234 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body235}236 237define void @umin_seq2(i32 %n, i32 %m) {238; CHECK-LABEL: 'umin_seq2'239; CHECK-NEXT: Classifying expressions for: @umin_seq2240; CHECK-NEXT: %n.2 = shl nsw i32 %n, 1241; CHECK-NEXT: --> (2 * %n) U: [0,-1) S: [-2147483648,2147483647)242; CHECK-NEXT: %m.2 = shl nsw i32 %m, 4243; 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, 1247; 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 false249; 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_seq2251; 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 -17253; 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 1255;256; Can't find that trip multiple is 2 for this case of umin_seq257entry:258 %n.2 = shl nsw i32 %n, 1259 %m.2 = shl nsw i32 %m, 4260 br label %loop261loop:262 %i = phi i32 [0, %entry], [%i.next, %loop]263 tail call void (...) @foo() #2264 %i.next = add nuw nsw i32 %i, 1265 %cond_p0 = icmp ult i32 %i.next, %n.2266 %cond_p1 = icmp ult i32 %i.next, %m.2267 %cond = select i1 %cond_p0, i1 %cond_p1, i1 false268 br i1 %cond, label %loop, label %exit269exit:270 ret void271}272 273define void @umin-3and6(i32 noundef %a, i32 noundef %b) {274; CHECK-LABEL: 'umin-3and6'275; CHECK-NEXT: Classifying expressions for: @umin-3and6276; CHECK-NEXT: %mul = mul i32 %a, 3277; CHECK-NEXT: --> (3 * %a) U: full-set S: full-set278; CHECK-NEXT: %mul1 = mul i32 %b, 6279; CHECK-NEXT: --> (6 * %b) U: [0,-1) S: [-2147483648,2147483647)280; CHECK-NEXT: %cond = select i1 %cmp, i32 %mul, i32 %mul1281; CHECK-NEXT: --> ((3 * %a) umin (6 * %b)) U: [0,-1) S: full-set282; 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, 1285; 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-3and6287; 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 2147483646289; 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 1291;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, 3305 %mul1 = mul i32 %b, 6306 %cmp = icmp ult i32 %mul, %mul1307 %cond = select i1 %cmp, i32 %mul, i32 %mul1308 %cmp210 = icmp sgt i32 %cond, 0309 br i1 %cmp210, label %for.body, label %for.cond.cleanup310 311for.cond.cleanup: ; preds = %for.body, %entry312 ret void313 314for.body: ; preds = %entry, %for.body315 %i.011 = phi i32 [ %inc, %for.body ], [ 0, %entry ]316 tail call void (...) @foo() #2317 %inc = add nuw nsw i32 %i.011, 1318 %exitcond.not = icmp eq i32 %inc, %cond319 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body320}321 322declare void @foo(...) local_unnamed_addr #1323