Inquiry regarding accurate calculation of maximum constant backedge count in SCEV

IR & Optimizations
1

Hi, I have a question regarding SCEV.

I’m trying to get the maximum constant backedge count for the loop below, but I’m unable to get an accurate value of 4294967294.

; int foo(int *a, int iv_start, int n) {
;   int sum = 0;
;   for (int i = iv_start; i < n; i++)
;     sum += a[i];
;   return sum;
; }
;
define dso_local signext i32 @foo(ptr nocapture noundef readonly %a, i32 noundef signext %iv_start, i32 noundef signext %n) local_unnamed_addr #0 {
entry:
  %cmp4 = icmp slt i32 %iv_start, %n
  br i1 %cmp4, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:                               ; preds = %entry
  %0 = sext i32 %iv_start to i64
  %wide.trip.count = sext i32 %n to i64
  br label %for.body

for.cond.cleanup.loopexit:                        ; preds = %for.body
  %add.lcssa = phi i32 [ %add, %for.body ]
  br label %for.cond.cleanup

for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
  %sum.0.lcssa = phi i32 [ 0, %entry ], [ %add.lcssa, %for.cond.cleanup.loopexit ]
  ret i32 %sum.0.lcssa

for.body:                                         ; preds = %for.body.preheader, %for.body
  %indvars.iv = phi i64 [ %0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
  %sum.05 = phi i32 [ 0, %for.body.preheader ], [ %add, %for.body ]
  %arrayidx = getelementptr inbounds i32, ptr %a, i64 %indvars.iv
  %1 = load i32, ptr %arrayidx, align 4, !tbaa !5
  %add = add nsw i32 %1, %sum.05
  %indvars.iv.next = add nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body, !llvm.loop !9
}

The reason seems to be that even after applying loop guard, it’s still unable to calculate the exact range of the symbolic backedge count.

// In the function ScalarEvolution::howFarToZero

(gdb) print Distance->dump()
(-1 + (sext i32 %n to i64) + (-1 * (sext i32 %iv_start to i64))<nsw>)
(gdb) print applyLoopGuards(Distance, L)->dump()
(-1 + (sext i32 %n to i64) + (-1 * ((sext i32 (-1 + %n) to i64) smin (sext i32 %iv_start to i64)))<nsw>)
(gdb) print getUnsignedRange(applyLoopGuards(Distance, L)).dump()
[-4294967296,4294967295) <---expect [0,4294967295) here
(gdb) print getUnsignedRangeMax(applyLoopGuards(Distance, L)).dump()
APInt(64b, 18446744073709551615u -1s)

Here’s a question: Is the following SCEV simplification correct? If yes, it is possible to get more precise max backedge count.

(-1 + (sext i32 %n to i64) + (-1 * ((sext i32 (-1 + %n) to i64) smin (sext i32 %iv_start to i64)))<nsw>)
--> (-1 + (sext i32 %n to i64) + ((sext i32 (1 - %n) to i64) smax (sext i32 (-1 * %iv_start) to i64))<nsw>)
--> (-1 + ((sext i32 1 to i64) smax (sext i32 (%n + (-1 * %iv_start)) to i64))<nsw>)

Or are there other ways to improve the accuracy of max const backedge count?

Regards,
Mel

2

@fhahn @preames I hope this message finds you, and I look forward to your suggestions.
In my opinion, reinforcing the distributive laws for smin and smax in getMulExpr and getAddExpr could achieve a more accurate max backedge count.

  • For getMulExpr
    -1 * smin(X, Y) → smax(-X, -Y)
  • For getAddExpr
    X + smax(Y, Z) → smax(X + Y, X + Z)

However, I’m uncertain if this transformation is correct, and if it’s the best way to address this issue. If you have any suggestions, please let me know. Thank you.