365 lines · plain
1; RUN: opt -disable-output "-passes=print<scalar-evolution>" -S -debug-only=scalar-evolution,apint < %s 2>&1 2>&1 | FileCheck %s2; REQUIRES: asserts3 4; Use the following template to get a chrec {L,+,M,+,N}.5;6; define signext i32 @func() {7; entry:8; br label %loop9;10; loop:11; %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]12; %inc = phi i32 [ X, %entry ], [ %inc1, %loop ]13; %acc = phi i32 [ Y, %entry ], [ %acc1, %loop ]14; %ivr1 = add i32 %ivr, %inc15; %inc1 = add i32 %inc, Z ; M = inc1 = inc + N = X + N16; %acc1 = add i32 %acc, %inc ; L = acc1 = X + Y17; %and = and i32 %acc1, 2^W-1 ; iW18; %cond = icmp eq i32 %and, 019; br i1 %cond, label %exit, label %loop20;21; exit:22; %rv = phi i32 [ %acc1, %loop ]23; ret i32 %rv24; }25;26; From27; X + Y = L28; X + Z = M29; Z = N30; get31; X = M - N32; Y = N - M + L33; Z = N34 35; The connection between the chrec coefficients {L,+,M,+,N} and the quadratic36; coefficients is that the quadratic equation is N x^2 + (2M-N) x + 2L = 0,37; where the equation was multiplied by 2 to make the coefficient at x^2 an38; integer (the actual equation is N/2 x^2 + (M-N/2) x + L = 0).39 40; Quadratic equation: 2x^2 + 2x + 4 in i4, solution (wrap): 441; {14,+,14,+,14} -> X=0, Y=14, Z=1442;43; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test01'44; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {-2,+,-2,+,-2}<%loop>45; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 446; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation -2x^2 + -2x + -4, coeff bw: 5, multiplied by 247; CHECK: {{.*}}SolveQuadraticAddRecExact{{.*}}: solving for unsigned overflow48; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving -2x^2 + -2x + -4, rw:549; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 2x^2 + 2x + -28, rw:550; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 451; CHECK: Loop %loop: Unpredictable backedge-taken count52define signext i32 @test01() {53entry:54 br label %loop55 56loop:57 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]58 %inc = phi i32 [ 0, %entry ], [ %inc1, %loop ]59 %acc = phi i32 [ 14, %entry ], [ %acc1, %loop ]60 %ivr1 = add i32 %ivr, %inc61 %inc1 = add i32 %inc, 1462 %acc1 = add i32 %acc, %inc63 %and = and i32 %acc1, 1564 %cond = icmp eq i32 %and, 065 br i1 %cond, label %exit, label %loop66 67exit:68 %rv = phi i32 [ %acc1, %loop ]69 ret i32 %rv70}71 72; Quadratic equation: 1x^2 + -73x + -146 in i32, solution (wrap): 7573; {-72,+,-36,+,1} -> X=-37, Y=-35, Z=174;75; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test02':76; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {0,+,-36,+,1}<%loop>77; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 3278; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 1x^2 + -73x + 0, coeff bw: 33, multiplied by 279; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow80; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -73x + 4294967154, rw:3281; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -73x + -142, rw:3282; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 7583; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow84; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -73x + 4294967154, rw:3385; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -73x + -4294967438, rw:3386; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 6557387; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow88; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -73x + -146, rw:3289; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -73x + -146, rw:3290; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 7591; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow92; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -73x + -146, rw:3393; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -73x + -146, rw:3394; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 7595; CHECK: Loop %loop: backedge-taken count is i32 7596define signext i32 @test02() {97entry:98 br label %loop99 100loop:101 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]102 %inc = phi i32 [ -37, %entry ], [ %inc1, %loop ]103 %acc = phi i32 [ -35, %entry ], [ %acc1, %loop ]104 %ivr1 = add i32 %ivr, %inc105 %inc1 = add i32 %inc, 1106 %acc1 = add i32 %acc, %inc107 %and = and i32 %acc1, -1108 %cond = icmp sgt i32 %and, 0109 br i1 %cond, label %exit, label %loop110 111exit:112 %rv = phi i32 [ %acc1, %loop ]113 ret i32 %rv114}115 116; Quadratic equation: 2x^2 - 4x + 34 in i4, solution (exact): 1.117; {17,+,-1,+,2} -> X=-3, Y=20, Z=2118;119; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test03':120; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {1,+,-1,+,2}<%loop>121; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 4122; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 2x^2 + -4x + 2, coeff bw: 5, multiplied by 2123; CHECK: {{.*}}SolveQuadraticAddRecExact{{.*}}: solving for unsigned overflow124; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 2x^2 + -4x + 2, rw:5125; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 2x^2 + -4x + 2, rw:5126; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (root): 1127; CHECK: Loop %loop: backedge-taken count is i4 1128define signext i32 @test03() {129entry:130 br label %loop131 132loop:133 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]134 %inc = phi i32 [ -3, %entry ], [ %inc1, %loop ]135 %acc = phi i32 [ 20, %entry ], [ %acc1, %loop ]136 %ivr1 = add i32 %ivr, %inc137 %inc1 = add i32 %inc, 2138 %acc1 = add i32 %acc, %inc139 %and = and i32 %acc1, 15140 %cond = icmp eq i32 %and, 0141 br i1 %cond, label %exit, label %loop142 143exit:144 %rv = phi i32 [ %acc1, %loop ]145 ret i32 %rv146}147 148; Quadratic equation 4x^2 + 2x + 2 in i16, solution (wrap): 181149; {1,+,3,+,4} -> X=-1, Y=2, Z=4 (i16)150;151; This is an example where the returned solution is the first time an152; unsigned wrap occurs, whereas the actual exit condition occurs much153; later. The number of iterations returned by SolveQuadraticEquation154; is 181, but the loop will iterate 37174 times.155;156; Here is a C code that corresponds to this case that calculates the number157; of iterations:158;159; int test04() {160; int c = 0;161; int ivr = 0;162; int inc = -1;163; int acc = 2;164;165; while (acc & 0xffff) {166; c++;167; ivr += inc;168; inc += 4;169; acc += inc;170; }171;172; return c;173; }174;175 176; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test04':177; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {0,+,3,+,4}<%loop>178; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 16179; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 4x^2 + 2x + 0, coeff bw: 17, multiplied by 2180; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow181; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 4x^2 + 2x + 2, rw:16182; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 4x^2 + 2x + -65534, rw:16183; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 128184; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow185; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 4x^2 + 2x + 2, rw:17186; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 4x^2 + 2x + -131070, rw:17187; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 181188; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow189; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 4x^2 + 2x + 2, rw:16190; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 4x^2 + 2x + -65534, rw:16191; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 128192; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow193; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 4x^2 + 2x + 2, rw:17194; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 4x^2 + 2x + -131070, rw:17195; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 181196; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {1,+,3,+,4}<%loop>197; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 16198; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 4x^2 + 2x + 2, coeff bw: 17, multiplied by 2199; CHECK: {{.*}}SolveQuadraticAddRecExact{{.*}}: solving for unsigned overflow200; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 4x^2 + 2x + 2, rw:17201; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 4x^2 + 2x + -131070, rw:17202; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 181203; CHECK: Loop %loop: Unpredictable backedge-taken count.204define signext i32 @test04() {205entry:206 br label %loop207 208loop:209 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]210 %inc = phi i32 [ -1, %entry ], [ %inc1, %loop ]211 %acc = phi i32 [ 2, %entry ], [ %acc1, %loop ]212 %ivr1 = add i32 %ivr, %inc213 %inc1 = add i32 %inc, 4214 %acc1 = add i32 %acc, %inc215 %and = trunc i32 %acc1 to i16216 %cond = icmp eq i16 %and, 0217 br i1 %cond, label %exit, label %loop218 219exit:220 %rv = phi i32 [ %acc1, %loop ]221 ret i32 %rv222}223 224; A case with signed arithmetic, but unsigned comparison.225 226; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test05':227; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {0,+,-1,+,-1}<%loop>228; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 32229; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation -1x^2 + -1x + 0, coeff bw: 33, multiplied by 2230; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow231; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving -1x^2 + -1x + 4, rw:32232; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + 1x + -4, rw:32233; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 2234; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow235; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving -1x^2 + -1x + 4, rw:33236; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + 1x + -4, rw:33237; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 2238; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow239; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving -1x^2 + -1x + -2, rw:32240; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + 1x + -4294967294, rw:32241; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 65536242; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow243; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving -1x^2 + -1x + -2, rw:33244; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + 1x + -8589934590, rw:33245; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 92682246; CHECK: Loop %loop: backedge-taken count is i32 2247 248define signext i32 @test05() {249entry:250 br label %loop251 252loop:253 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]254 %inc = phi i32 [ 0, %entry ], [ %inc1, %loop ]255 %acc = phi i32 [ -1, %entry ], [ %acc1, %loop ]256 %ivr1 = add i32 %ivr, %inc257 %inc1 = add i32 %inc, -1258 %acc1 = add i32 %acc, %inc259 %and = and i32 %acc1, -1260 %cond = icmp ule i32 %and, -3261 br i1 %cond, label %exit, label %loop262 263exit:264 %rv = phi i32 [ %acc1, %loop ]265 ret i32 %rv266}267 268; A test that used to crash with one of the earlier versions of the code.269 270; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test06':271; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {0,+,-99999,+,1}<%loop>272; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 32273; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 1x^2 + -199999x + 0, coeff bw: 33, multiplied by 2274; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow275; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -199999x + -4294967294, rw:32276; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -199999x + 2, rw:32277; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 1278; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow279; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -199999x + -4294967294, rw:33280; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -199999x + 4294967298, rw:33281; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 24469282; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow283; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -199999x + -12, rw:32284; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -199999x + 4294967284, rw:32285; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 24469286; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow287; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 1x^2 + -199999x + -12, rw:33288; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 1x^2 + -199999x + 8589934580, rw:33289; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solution (wrap): 62450290; CHECK: Loop %loop: backedge-taken count is i32 24469291define signext i32 @test06() {292entry:293 br label %loop294 295loop:296 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]297 %inc = phi i32 [ -100000, %entry ], [ %inc1, %loop ]298 %acc = phi i32 [ 100000, %entry ], [ %acc1, %loop ]299 %ivr1 = add i32 %ivr, %inc300 %inc1 = add i32 %inc, 1301 %acc1 = add i32 %acc, %inc302 %and = and i32 %acc1, -1303 %cond = icmp sgt i32 %and, 5304 br i1 %cond, label %exit, label %loop305 306exit:307 %rv = phi i32 [ %acc1, %loop ]308 ret i32 %rv309}310 311; The equation312; 532052752x^2 + -450429774x + 71188414 = 0313; has two exact solutions (up to two decimal digits): 0.21 and 0.64.314; Since there is no integer between them, there is no integer n that either315; solves the equation exactly, or changes the sign of it between n and n+1.316 317; CHECK-LABEL: Printing analysis 'Scalar Evolution Analysis' for function 'test07':318; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {0,+,40811489,+,532052752}<%loop>319; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 32320; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 532052752x^2 + -450429774x + 0, coeff bw: 33, multiplied by 2321; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow322; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 532052752x^2 + -450429774x + 71188414, rw:32323; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 532052752x^2 + -450429774x + 71188414, rw:32324; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: no valid solution325; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow326; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 532052752x^2 + -450429774x + 71188414, rw:33327; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 532052752x^2 + -450429774x + 71188414, rw:33328; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: no valid solution329; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for signed overflow330; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 532052752x^2 + -450429774x + 71188414, rw:32331; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 532052752x^2 + -450429774x + 71188414, rw:32332; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: no valid solution333; CHECK: {{.*}}SolveQuadraticAddRecRange{{.*}}: solving for unsigned overflow334; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 532052752x^2 + -450429774x + 71188414, rw:33335; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 532052752x^2 + -450429774x + 71188414, rw:33336; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: no valid solution337; CHECK: {{.*}}GetQuadraticEquation{{.*}}: analyzing quadratic addrec: {35594207,+,40811489,+,532052752}<%loop>338; CHECK: {{.*}}GetQuadraticEquation{{.*}}: addrec coeff bw: 32339; CHECK: {{.*}}GetQuadraticEquation{{.*}}: equation 532052752x^2 + -450429774x + 71188414, coeff bw: 33, multiplied by 2340; CHECK: {{.*}}SolveQuadraticAddRecExact{{.*}}: solving for unsigned overflow341; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: solving 532052752x^2 + -450429774x + 71188414, rw:33342; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: updated coefficients 532052752x^2 + -450429774x + 71188414, rw:33343; CHECK: {{.*}}SolveQuadraticEquationWrap{{.*}}: no valid solution344; CHECK: Loop %loop: Unpredictable backedge-taken count.345define signext i32 @test07() {346entry:347 br label %loop348 349loop:350 %ivr = phi i32 [ 0, %entry ], [ %ivr1, %loop ]351 %inc = phi i32 [ -491241263, %entry ], [ %inc1, %loop ]352 %acc = phi i32 [ 526835470, %entry ], [ %acc1, %loop ]353 %ivr1 = add i32 %ivr, %inc354 %inc1 = add i32 %inc, 532052752355 %acc1 = add i32 %acc, %inc356 %and = and i32 %acc1, -1357 %cond = icmp eq i32 %and, 0358 br i1 %cond, label %exit, label %loop359 360exit:361 %rv = phi i32 [ %acc1, %loop ]362 ret i32 %rv363}364 365