[LLVMdev] ScalarEvolution::createNodeForPHI

Michele Scandale michele.scandale at gmail.com
Tue Oct 1 06:45:40 PDT 2013


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



More information about the llvm-dev mailing list