SCEV related question

Project Infrastructure LLVM Dev List Archives
#1

Hello,

I am first time paying with SCEV codebase.
I am trying to find out why ScalarEvolution is not able to give correct back edge taken count for an expression.

So in my case flow reaches to howFarToZero() and in that function, I have following expressions as SCEV

Start = (15 + (-1 * %i) (which is set to Distance SCEV)
Step = 1

now, first of all, should I expect Start as ConstantSCEV (15) instead of the whole expression
the problem here is getUnsignedRangeMax(Distance) returns very large number because of -1 in the SCEV.

How we can make this work? Here we can clearly say that after 15 steps this expression will be 0
and thus we have a value for backedge taken count.

Any help will be appriciated.

Thanks,
Vivek

#2

Hello,

I am first time paying with SCEV codebase.
I am trying to find out why ScalarEvolution is not able to give correct back edge taken count for an expression.

So in my case flow reaches to howFarToZero() and in that function, I have following expressions as SCEV

Start = (15 + (-1 * %i) (which is set to Distance SCEV)
Step = 1

now, first of all, should I expect Start as ConstantSCEV (15) instead of the whole expression
the problem here is getUnsignedRangeMax(Distance) returns very large number because of -1 in the SCEV.

Given you have have above, in howFarToZero SCEV is reasoning about the
loop as if it were:

unsigned i = ...;
unsigned Start = 15 - i;
while (Start != 0) {
  unsigned Step = 1;
  Start = Start + Step;
}

How we can make this work? Here we can clearly say that after 15 steps this expression will be 0

and so I don't think this assertion ("after 15 steps this expression
will be 0") is correct.

If you post a minimal example we can try to figure out if SCEV can be
smarter here.

-- Sanjoy

#3

Here is original C code:
void topup(int a[], unsigned long i) {
for (; i < 16; i++) {
a[i] = 1;
}
}

Here is the IR before the pass where I expect SCEV to return trip-count value

; Function Attrs: nofree norecurse nounwind uwtable writeonly
define dso_local void @topup(i32* nocapture %a, i64 %i) local_unnamed_addr #0 {
entry:
%cmp3 = icmp ult i64 %i, 16
br i1 %cmp3, label %for.body.preheader, label %for.end

for.body.preheader: ; preds = %entry
br label %for.body

for.body: ; preds = %for.body.preheader, %for.body
%i.addr.04 = phi i64 [ %inc, %for.body ], [ %i, %for.body.preheader ]
%arrayidx = getelementptr inbounds i32, i32* %a, i64 %i.addr.04
store i32 1, i32* %arrayidx, align 4, !tbaa !2
%inc = add nuw nsw i64 %i.addr.04, 1
%exitcond = icmp eq i64 %inc, 16
br i1 %exitcond, label %for.end.loopexit, label %for.body

for.end.loopexit: ; preds = %for.body
br label %for.end

for.end: ; preds = %for.end.loopexit, %entry
ret void
}

I have also checked that at a pass before above pass SCEV works and returns 16.

Here is the IR before a pass where SCEV works as per the expectations:
; Preheader:
for.body.preheader: ; preds = %entry
br label %for.body

; Loop:
for.body: ; preds = %for.body.preheader, %for.body
%i.addr.04 = phi i64 [ %inc, %for.body ], [ %i, %for.body.preheader ]
%arrayidx = getelementptr inbounds i32, i32* %a, i64 %i.addr.04
store i32 1, i32* %arrayidx, align 4, !tbaa !2
%inc = add nuw nsw i64 %i.addr.04, 1
%cmp = icmp ult i64 %inc, 16
br i1 %cmp, label %for.body, label %for.end.loopexit

; Exit blocks
for.end.loopexit: ; preds = %for.body
br label %for.end

  • Vivek
#4

With the first example I see:

Determining loop execution counts for: @topup
Loop %for.body: backedge-taken count is (15 + (-1 * %i))
Loop %for.body: max backedge-taken count is -1
Loop %for.body: Predicated backedge-taken count is (15 + (-1 * %i))

So is the real problem here isn't that SCEV isn't computing the
correct BE count, but that the max BE count it computes is not
precise?

If yes, I think you'll have to change
https://github.com/llvm-project/llvm/blob/16bef0f9a051afa7b57f5fd01624086c35ec1e60/lib/Analysis/ScalarEvolution.cpp#L8746
to produce a more precise max trip count.

-- Sanjoy

#5

yes, I reached a similar conclusion.
I have attached a patch if it looks on the correct direction I can send it for review.

-Vivek

scev.patch (7.11 KB)