Page MenuHomePhabricator

[IndVarSimplify] Use control-dependent range information to prove non-negativity
ClosedPublic

Authored by apilipenko on Oct 18 2016, 11:07 AM.

Details

Summary

This change is motivated by the case when IndVarSimplify doesn't widen a comparison of IV increment because it can't prove IV increment being non-negative. We end up with a redundant trunc of the widened increment on this example.

for.body:
  %i = phi i32 [ %start, %for.body.lr.ph ], [ %i.inc, %for.inc ]
  %within_limits = icmp ult i32 %i, 64
  br i1 %within_limits, label %continue, label %for.end

continue:
  %i.i64 = zext i32 %i to i64
  %arrayidx = getelementptr inbounds i32, i32* %base, i64 %i.i64
  %val = load i32, i32* %arrayidx, align 4
  br label %for.inc

for.inc:
  %i.inc = add nsw nuw i32 %i, 1
  %cmp = icmp slt i32 %i.inc, %limit
  br i1 %cmp, label %for.body, label %for.end

There is a range check inside of the loop which guarantees the IV to be non-negative. NSW on the increment guarantees that the increment is also non-negative. ScalarEvolution can't prove that the increments non-negative because it doesn't reason about control dependencies inside of the loop. Teach IndVarSimplify to use the range check to prove non-negativity of loop increments.

It's difficult to gather control-dependent information on demand, because when it's needed some of the dominating conditions might be already widened. That's why collect control-dependent ranges before any transformation occurs for all increments of the IV and all uses of these increments.

Diff Detail

Repository
rL LLVM

Event Timeline

apilipenko retitled this revision from to [IndVarSimplify] Use control-dependent range information to prove non-negativity.
apilipenko updated this object.
apilipenko added reviewers: sanjoy, reames, lihuang.
apilipenko updated this object.
apilipenko added a subscriber: llvm-commits.
sanjoy requested changes to this revision.Oct 18 2016, 12:40 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
927 ↗(On Diff #75031)

Current seems unused?

930 ↗(On Diff #75031)

You can use PostIncRangeInfos.insert({Key, R}); here.

I'd also drop the braces.

1474 ↗(On Diff #75031)

End comment with period.

1521 ↗(On Diff #75031)

s/in the form of/of the form/

1594 ↗(On Diff #75031)

I'd s/ConstantRange/auto here.

1607 ↗(On Diff #75031)

auto * here.

I'd actually just remove TI altogether -- and instead do:

auto *BI = dyn_cast<BranchInst>(DTB->getBlock()->getTerminator());
1618 ↗(On Diff #75031)

Add a TODO here about also exploiting false edges in the future (feel free to implement it right now too -- it won't be that much more code).

1623 ↗(On Diff #75031)

I'd perhaps use a SmallPtrSet<16> here.

test/Transforms/IndVarSimplify/post-inc-range.ll
8 ↗(On Diff #75031)

Can you please add a test case that checks that we do the right thing for a comparison with, say, (%i * 3) + 1 where %i is the IV and there is a range check on %i * 3? That is, check that we're actually using the worklist algorithm above.

This revision now requires changes to proceed.Oct 18 2016, 12:40 PM
apilipenko marked 8 inline comments as done.Oct 19 2016, 5:19 AM
apilipenko added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
1607 ↗(On Diff #75031)

I'll need TI for guards here (see D25739).

apilipenko updated this revision to Diff 75136.Oct 19 2016, 6:23 AM
apilipenko edited edge metadata.

Address Sanjoy's comments, put under a flag.

sanjoy accepted this revision.Oct 19 2016, 11:06 AM
sanjoy edited edge metadata.

lgtm

This revision is now accepted and ready to land.Oct 19 2016, 11:06 AM
This revision was automatically updated to reflect the committed changes.