<div dir="ltr"><div>yes, I reached a similar conclusion.</div><div>I have attached a patch if it looks on the correct direction I can send it for review.</div><div><br></div><div>-Vivek<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Sep 2, 2019 at 10:00 PM Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">With the first example I see:<br>
<br>
Determining loop execution counts for: @topup<br>
Loop %for.body: backedge-taken count is (15 + (-1 * %i))<br>
Loop %for.body: max backedge-taken count is -1<br>
Loop %for.body: Predicated backedge-taken count is (15 + (-1 * %i))<br>
<br>
So is the real problem here isn't that SCEV isn't computing the<br>
correct BE count, but that the max BE count it computes is not<br>
precise?<br>
<br>
If yes, I think you'll have to change<br>
<a href="https://github.com/llvm-project/llvm/blob/16bef0f9a051afa7b57f5fd01624086c35ec1e60/lib/Analysis/ScalarEvolution.cpp#L8746" rel="noreferrer" target="_blank">https://github.com/llvm-project/llvm/blob/16bef0f9a051afa7b57f5fd01624086c35ec1e60/lib/Analysis/ScalarEvolution.cpp#L8746</a><br>
to produce a more precise max trip count.<br>
<br>
-- Sanjoy<br>
<br>
On Sun, Aug 25, 2019 at 9:02 PM vivek pandya <<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>> wrote:<br>
><br>
> Here is original C code:<br>
>   void topup(int a[], unsigned long i) {<br>
>      for (; i < 16; i++) {<br>
>        a[i] = 1;<br>
>      }<br>
>    }<br>
><br>
> Here is the IR before the pass where I expect SCEV to return trip-count value<br>
><br>
>  ; Function Attrs: nofree norecurse nounwind uwtable writeonly<br>
>  define dso_local void @topup(i32* nocapture %a, i64 %i) local_unnamed_addr #0 {<br>
>  entry:<br>
>    %cmp3 = icmp ult i64 %i, 16<br>
>    br i1 %cmp3, label %for.body.preheader, label %for.end<br>
><br>
>  for.body.preheader:                               ; preds = %entry<br>
>    br label %for.body<br>
><br>
>  for.body:                                         ; preds = %for.body.preheader, %for.body<br>
>    %i.addr.04 = phi i64 [ %inc, %for.body ], [ %i, %for.body.preheader ]<br>
>    %arrayidx = getelementptr inbounds i32, i32* %a, i64 %i.addr.04<br>
>    store i32 1, i32* %arrayidx, align 4, !tbaa !2<br>
>    %inc = add nuw nsw i64 %i.addr.04, 1<br>
>    %exitcond = icmp eq i64 %inc, 16<br>
>    br i1 %exitcond, label %for.end.loopexit, label %for.body<br>
><br>
>  for.end.loopexit:                                 ; preds = %for.body<br>
>    br label %for.end<br>
><br>
>  for.end:                                          ; preds = %for.end.loopexit, %entry<br>
>    ret void<br>
> }<br>
><br>
> I have also checked that at a pass before above pass SCEV works and returns 16.<br>
><br>
> Here is the IR before a pass where SCEV works as per the expectations:<br>
>  ; Preheader:<br>
>  for.body.preheader:                               ; preds = %entry<br>
>    br label %for.body<br>
><br>
>  ; Loop:<br>
>  for.body:                                         ; preds = %for.body.preheader, %for.body<br>
>    %i.addr.04 = phi i64 [ %inc, %for.body ], [ %i, %for.body.preheader ]<br>
>    %arrayidx = getelementptr inbounds i32, i32* %a, i64 %i.addr.04<br>
>    store i32 1, i32* %arrayidx, align 4, !tbaa !2<br>
>    %inc = add nuw nsw i64 %i.addr.04, 1<br>
>    %cmp = icmp ult i64 %inc, 16<br>
>    br i1 %cmp, label %for.body, label %for.end.loopexit<br>
><br>
>  ; Exit blocks<br>
>  for.end.loopexit:                                 ; preds = %for.body<br>
>    br label %for.end<br>
><br>
> - Vivek<br>
><br>
> On Mon, Aug 26, 2019 at 2:09 AM Sanjoy Das <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>> wrote:<br>
>><br>
>> On Sun, Aug 25, 2019 at 4:49 AM vivek pandya via llvm-dev<br>
>> <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
>> ><br>
>> > Hello,<br>
>> ><br>
>> > I am first time paying with SCEV codebase.<br>
>> > I am trying to find out why ScalarEvolution is not able to give correct back edge taken count for an expression.<br>
>> ><br>
>> > So in my case flow reaches to howFarToZero() and in that function, I have following expressions as SCEV<br>
>> ><br>
>> > Start = (15 + (-1 * %i) (which is set to Distance SCEV)<br>
>> > Step = 1<br>
>> ><br>
>> > now, first of all, should I expect Start as ConstantSCEV (15) instead of the whole expression<br>
>> > the problem here is getUnsignedRangeMax(Distance) returns very large number because of -1 in the SCEV.<br>
>><br>
>> Given you have have above, in howFarToZero SCEV is reasoning about the<br>
>> loop as if it were:<br>
>><br>
>> unsigned i = ...;<br>
>> unsigned Start = 15 - i;<br>
>> while (Start != 0) {<br>
>>   unsigned Step = 1;<br>
>>   Start = Start + Step;<br>
>> }<br>
>><br>
>> > How we can make this work? Here we can clearly say that after 15 steps this expression will be 0<br>
>><br>
>> and so I don't think this assertion ("after 15 steps this expression<br>
>> will be 0") is correct.<br>
>><br>
>> If you post a minimal example we can try to figure out if SCEV can be<br>
>> smarter here.<br>
>><br>
>> -- Sanjoy<br>
>><br>
>> > and thus we have a value for backedge taken count.<br>
>> ><br>
>> > Any help will be appriciated.<br>
>> ><br>
>> > Thanks,<br>
>> > Vivek<br>
>> > _______________________________________________<br>
>> > LLVM Developers mailing list<br>
>> > <a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
>> > <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>