Page MenuHomePhabricator

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

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



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.

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

  %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 = add nsw nuw i32 %i, 1
  %cmp = icmp slt i32, %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


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.
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.

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.
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.


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.