Scalar Evolution and Loop Trip Count.

Hi,

Scalar evolution seems to be wrapping around the trip count in the following loop.

void add (int *restrict a, int *restrict b, int *restrict c) {
   char i;
   for (i = 0; i < 255; i++)
     a[i] = b[i] + c[i];
}

When I run scalar evolution on the bit code, I get a backedge-taken count which is obviously wrong.
$> cat loop.ll
; Function Attrs: nounwind
define void @add(i32* noalias nocapture %a, i32* noalias nocapture %b, i32* noalias nocapture %c) #0 {
entry:
   br label %for.body

for.body: ; preds = %entry, %for.body
   %arrayidx.phi = phi i32* [ %b, %entry ], [ %arrayidx.inc, %for.body ]
   %arrayidx3.phi = phi i32* [ %c, %entry ], [ %arrayidx3.inc, %for.body ]
   %arrayidx5.phi = phi i32* [ %a, %entry ], [ %arrayidx5.inc, %for.body ]
   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   %0 = load i32* %arrayidx.phi, align 4, !tbaa !0
   %1 = load i32* %arrayidx3.phi, align 4, !tbaa !0
   %add = add nsw i32 %1, %0
   store i32 %add, i32* %arrayidx5.phi, align 4, !tbaa !0
   %indvars.iv.next = add i32 %indvars.iv, 1
   %lftr.wideiv = trunc i32 %indvars.iv.next to i8
   %exitcond = icmp eq i8 %lftr.wideiv, -1
   %arrayidx.inc = getelementptr i32* %arrayidx.phi, i32 1
   %arrayidx3.inc = getelementptr i32* %arrayidx3.phi, i32 1
   %arrayidx5.inc = getelementptr i32* %arrayidx5.phi, i32 1
   br i1 %exitcond, label %for.end, label %for.body

for.end: ; preds = %for.body
   ret void
}

$> opt -scalar-evolution -analyze loop.ll
Printing analysis 'Scalar Evolution Analysis' for function 'add':
Classifying expressions for: @add
   %arrayidx.phi = phi i32* [ %b, %entry ], [ %arrayidx.inc, %for.body ]
   --> {%b,+,4}<%for.body> Exits: (1016 + %b)
   %arrayidx3.phi = phi i32* [ %c, %entry ], [ %arrayidx3.inc, %for.body ]
   --> {%c,+,4}<%for.body> Exits: (1016 + %c)
   %arrayidx5.phi = phi i32* [ %a, %entry ], [ %arrayidx5.inc, %for.body ]
   --> {%a,+,4}<%for.body> Exits: (1016 + %a)
   %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
   --> {0,+,1}<%for.body> Exits: 254
   %0 = load i32* %arrayidx.phi, align 4, !tbaa !0
   --> %0 Exits: <<Unknown>>
   %1 = load i32* %arrayidx3.phi, align 4, !tbaa !0
   --> %1 Exits: <<Unknown>>
   %add = add nsw i32 %1, %0
   --> (%0 + %1) Exits: <<Unknown>>
   %indvars.iv.next = add i32 %indvars.iv, 1
   --> {1,+,1}<%for.body> Exits: 255
   %lftr.wideiv = trunc i32 %indvars.iv.next to i8
   --> {1,+,1}<%for.body> Exits: -1
   %arrayidx.inc = getelementptr i32* %arrayidx.phi, i32 1
   --> {(4 + %b),+,4}<%for.body> Exits: (1020 + %b)
   %arrayidx3.inc = getelementptr i32* %arrayidx3.phi, i32 1
   --> {(4 + %c),+,4}<%for.body> Exits: (1020 + %c)
   %arrayidx5.inc = getelementptr i32* %arrayidx5.phi, i32 1
   --> {(4 + %a),+,4}<%for.body> Exits: (1020 + %a)
Determining loop execution counts for: @add
Loop %for.body: backedge-taken count is -2
Loop %for.body: max backedge-taken count is -2

The problem seems to be in SCEVAddRecExpr:getNumIterationsInRange, specifically
   // If this is an affine expression then we have this situation:
       // Solve {0,+,A} in Range === Ax in Range

       // We know that zero is in the range. If A is positive then we know that
       // the upper value of the range must be the first possible exit value.
       // If A is negative then the lower of the range is the last possible loop
       // value. Also note that we already checked for a full range.
       APInt One(BitWidth,1);
       APInt A = cast<SCEVConstant>(getOperand(1))->getValue()->getValue();
       APInt End = A.sge(One) ? (Range.getUpper() - One) : Range.getLower();

       // The exit value should be (End+A)/A.
       APInt ExitVal = (End + A).udiv(A);
       ConstantInt *ExitValue = ConstantInt::get(SE.getContext(), ExitVal);

In gdb,
$6 = {BitWidth = 8, {VAL = 254, pVal = 0xfe}}
(gdb) p ExitVal.isNegative()
$7 = true
(gdb) p ExitValue->dump()
i8 -2
$8 = void

It looks like whenever the value of ExitVal is greater than 128, ExitValue is going to be negative. This makes getBackedgeTakenCount return a negative number, which does not make sense. Any thoughts ?

Pranav

getBackedgeTakenCount returns an unsigned number; we're just printing it wrong.

-Eli