[LLVMdev] ScalarEvolution::createNodeForPHI

[Hal Finkel]

----- Original Message -----
> 
> On Oct 1, 2013, at 6:45 AM, Michele Scandale
> <michele.scandale at gmail.com> wrote:
> 
> > Hello to everybody,
> > 
> > I'm working on some improvements on trip count computation with
> > ScalarEvolution
> > analysis.
> > Considering the following test
> > 
> > ;----------------------------------------------------------------------------;
> > define void @foo(i32 %a, i32 %b, i32 %s) #0 {
> > entry:
> >  %cmp = icmp sgt i32 %s, 0
> >  %cmp15 = icmp sgt i32 %a, %b
> >  %or.cond = and i1 %cmp, %cmp15
> >  br i1 %or.cond, label %for.body, label %if.end
> > 
> > for.body:
> >  %i.06 = phi i32 [ %sub, %for.body ], [ %a, %entry ]
> >  tail call void @f(i32 %i.06) #2
> >  %sub = sub nsw i32 %i.06, %s
> >  %cmp1 = icmp sgt i32 %sub, %b
> >  br i1 %cmp1, label %for.body, label %if.end
> > 
> > if.end:
> >  ret void
> > }
> > ;----------------------------------------------------------------------------;
> > 
> > I've noticed that the SCEV for %i.06 and %sub are the following:
> > 
> > %i.06 = phi i32 [ %sub, %for.body ], [ %a, %entry ]
> > -->  {%a,+,(-1 * %s)}<%for.body>
> > 
> > %sub = sub nsw i32 %i.06, %s
> > -->  {((-1 * %s) + %a),+,(-1 * %s)}<%for.body>
> > 
> > but the NSW flag that is present in the SUB instruction is not
> > propagated in the
> > AddRec.
> > 
> > Looking in the source code I analyzed the construction of the SCEV
> > for a PHINode
> > and during the analysis of the loop-invariant part of the increment
> > the flags
> > NSW/NUW are set according to the Operator BEValueV
> > (ScalarEvoluton.cpp:3099-3113), but only Add and GEP operators are
> > checked.
> > 
> > //-------------------------------------------------------------------------//
> > if (const AddOperator *OBO = dyn_cast<AddOperator>(BEValueV)) {
> >  if (OBO->hasNoUnsignedWrap())
> >    Flags = setFlags(Flags, SCEV::FlagNUW);
> >  if (OBO->hasNoSignedWrap())
> >    Flags = setFlags(Flags, SCEV::FlagNSW);
> > } else if (const GEPOperator *GEP =
> >             dyn_cast<GEPOperator>(BEValueV)) {
> >  // If the increment is an inbounds GEP, then we know the address
> >  // space cannot be wrapped around. We cannot make any guarantee
> >  // about signed or unsigned overflow because pointers are
> >  // unsigned but we may have a negative index from the base
> >  // pointer.
> >  if (GEP->isInBounds())
> >    Flags = setFlags(Flags, SCEV::FlagNW);
> > }
> > //-------------------------------------------------------------------------//
> > 
> > Is there any reason to not check also Sub operator in a similar way
> > to the Add
> > operator?
> > 
> > //-------------------------------------------------------------------------//
> > if (const SubOperator *OBO = dyn_cast<SubOperator>(BEValueV)) {
> >  if (OBO->hasNoUnsignedWrap())
> >    Flags = setFlags(Flags, SCEV::FlagNUW);
> >  if (OBO->hasNoSignedWrap())
> >    Flags = setFlags(Flags, SCEV::FlagNSW);
> > }
> > //-------------------------------------------------------------------------//
> 
> 
> I’m not sure how to make sense of an NUW flag coming from a sub.

I thought that sub nuw a, b just meant that we were allowed to assume that a >= b. No?

 -Hal

> 
> NSW is just a misnomer for signed overflow. SCEV canonicalizes sub
> a,b to add a, (-b). Unfortunately, signed overflow is not the same
> thing for sub and add...
> 
> sub nsw %a, %b != add nsw %a, (-1 * %b)
> 
> sub nsw i32, -1, INT_MIN is true.
> 
> add nsw i32, -1, (-1 * INT_MIN) is false.
> 
> NSW flags just aren’t an effective way to tell SCEV about overflow.
> Ideally we could reason more generally about the loop’s undefined
> behavior. For example, I’d like to query the range of values that a
> variable can hold before the loop hits undefined behavior. I don’t
> know how to implement something like this yet. Ideas are welcome.
> 
> Reading this code again, even the addition case looks too aggressive
> to me.
> See:
> llvm.org/PR17452 - SCEV createNodeForPHI is too optimistic about NSW.
> 
> -Andy
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 

-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory