[llvm-dev] SCEV related question

[vivek pandya via llvm-dev]

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

On Mon, Sep 2, 2019 at 10:00 PM Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> 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
>
> On Sun, Aug 25, 2019 at 9:02 PM vivek pandya <vivekvpandya at gmail.com>
> wrote:
> >
> > 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
> >
> > On Mon, Aug 26, 2019 at 2:09 AM Sanjoy Das <
> sanjoy at playingwithpointers.com> wrote:
> >>
> >> On Sun, Aug 25, 2019 at 4:49 AM vivek pandya via llvm-dev
> >> <llvm-dev at lists.llvm.org> wrote:
> >> >
> >> > 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
> >>
> >> > and thus we have a value for backedge taken count.
> >> >
> >> > Any help will be appriciated.
> >> >
> >> > Thanks,
> >> > Vivek
> >> > _______________________________________________
> >> > LLVM Developers mailing list
> >> > llvm-dev at lists.llvm.org
> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190903/a26a08e4/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: scev.patch
Type: application/octet-stream
Size: 7283 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190903/a26a08e4/attachment-0001.obj>