SCEV getMulExpr() not propagating Wrap flags

Project Infrastructure LLVM Dev List Archives
1

Hi folks,

I’m trying to analyse this piece of IR:

for.body: ; preds = %for.body, %entry
%indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
%0 = shl nsw i64 %indvars.iv, 1
%arrayidx = getelementptr inbounds i32* %b, i64 %0
%1 = load i32* %arrayidx, align 4, !tbaa !1
%add = add nsw i32 %1, %I
%arrayidx3 = getelementptr inbounds i32* %a, i64 %0
store i32 %add, i32* %arrayidx3, align 4, !tbaa !1
%2 = or i64 %0, 1
%arrayidx7 = getelementptr inbounds i32* %b, i64 %2
%3 = load i32* %arrayidx7, align 4, !tbaa !1
%add8 = add nsw i32 %3, %I
%arrayidx12 = getelementptr inbounds i32* %a, i64 %2
store i32 %add8, i32* %arrayidx12, align 4, !tbaa !1
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
%exitcond = icmp eq i64 %indvars.iv.next, 512
br i1 %exitcond, label %for.end, label %for.body

And, when going through the GEP:

%0 = shl nsw i64 %indvars.iv, 1
%arrayidx = getelementptr inbounds i32* %b, i64 %0

ScalarEvolution::createNodeForGEP() is losing the SCEV::FlagNSW, and I believe it’s because of this piece of code in getMulExpr():

// Build the new addrec. Propagate the NUW and NSW flags if both the
// outer mul and the inner addrec are guaranteed to have no overflow.
//
// No self-wrap cannot be guaranteed after changing the step size, but
// will be inferred if either NUW or NSW is true.
Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);

// If all of the other operands were loop invariant, we are done.
if (Ops.size() == 1) return NewRec;

I understand that you can’t assume it won’t wrap around with the new stride, but I couldn’t find anything else later that would re-assign NSW/NUW. Maybe I need to add this code myself? Possibly in the GEP code, if I can detect the range will be safe, even for large strides?

cheers,

–renato

2

Hi Renato,

Did you figure this out? The code you’re pointing to should preserve NSW and NUW. It is only clearing NW. Here’s what I think should happen, without actually trying it myself:

- createNodeForGEP notices that inbounds implies NSW

  SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap

- The array index should already be an AddRecExpr with NSW

       const SCEV *IndexS = getSCEV(Index);

- createNodeForGEP attempts to scale the index using the NSW flag we picked up earlier

      const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize, Wrap);

- getMulExpr constructs a new AddRec with NSW:

      Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
      const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);

The clearing of NW does not need to happen in your case (NSW/NUW should always imply NW). You could try this and see if it fixes the problem:

      Flags = AddRec->getNoWrapFlags();

If that fixes your case, then the right/safe fix will be trivial.

-Andy

3

- getMulExpr constructs a new AddRec with NSW:

      Flags = AddRec->getNoWrapFlags(clearFlags(Flags, SCEV::FlagNW));
      const SCEV *NewRec = getAddRecExpr(NewOps, AddRecLoop, Flags);

Hi Andrew,

Thanks for looking at this.

Clearing the flags here makes sense, but it's being too conservative. I'm
thinking I'll need something like propagateSafeFlags(...) with knowledge of
the loop induction ranges or something else instead of simply relying on
later processes to spot the problems.

The clearing of NW does not need to happen in your case (NSW/NUW should

always imply NW). You could try this and see if it fixes the problem:

      Flags = AddRec->getNoWrapFlags();

If that fixes your case, then the right/safe fix will be trivial.

It does, on that case. Shouldn't be too hard, but having the right info on
the right place could be tricky.

cheers,
--renato

4

That code is not intending to drop information in your case, but the implementation of the flags is sloppy here. If you can drop a test case in a PR I’ll fix it.

Andy

5

Thanks Andrew,

http://llvm.org/bugs/show_bug.cgi?id=17963

cheers,
--renato