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);
}
//-------------------------------------------------------------------------//
Thanks in advance.
Best regards,
-Michele Scandale
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. 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
----- 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
On 10/03/2013 01:22 AM, Andrew Trick wrote:> > I’m not sure how to make sense of an NUW flag coming from a sub. > > 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. >If the behavior is different between 'add nsw' and 'sub nsw' then the SCEV canonicalization of 'sub' leads to incorrect results. In your example both result should be the same but the 'add' produces a poison value. Is this what we really want? The case of an expression with mixed operator ('add' with and without nsw) flag would require an explicit representation of the two operator making more complex reassociation, simplification and reordering of the expression operands. Your proposed workaround of checking that the BEValue is an operation between the PHINode Value and a loop invariant would be fine but it's still a workaround. -Michele