Page MenuHomePhabricator

[IndVars] Widen more comparisons for non-negative induction vars.
ClosedPublic

Authored by sanjoy on Sep 9 2015, 6:07 PM.

Details

Summary

If an induction variable is provably non-negative, its sign extension is
equal to its zero extension. This means narrow uses like

icmp slt iNarrow %indvar, %rhs

can be widened into

icmp slt iWide zext(%indvar), sext(%rhs)

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 34395.Sep 9 2015, 6:07 PM
sanjoy retitled this revision from to [IndVars] Widen more comparisons for non-negative induction vars..
sanjoy updated this object.
sanjoy added reviewers: mcrosier, atrick.
sanjoy added a subscriber: llvm-commits.
sanjoy updated this revision to Diff 34396.Sep 9 2015, 6:11 PM
  • rename AlwaysPositive to NeverNegative
reames added a subscriber: reames.Sep 10 2015, 10:17 AM

Minor comments. The direction of the change looks right to me. I'm not comfortable giving a LGTM on this given I don't know the area well enough.

lib/Transforms/Scalar/IndVarSimplify.cpp
849 ↗(On Diff #34396)

A brief bit about what we can use this fact for would be good in the comment.

1265 ↗(On Diff #34396)

Why not just SE->isKnownNonNegative(AddRec)?

test/Transforms/IndVarSimplify/widen-loop-comp.ll
200 ↗(On Diff #34396)

CHECK_LABEL

213 ↗(On Diff #34396)

It isn't obvious to me whether we chose a sext or a sext for the induction variable in this loop. We could do either base on order of visitation. Could you clarify this?

Also, can you add tests for the full 2 x 2 matrix of signed/unsigned widdening x signed/unsigned compare?

reames added inline comments.Sep 10 2015, 10:21 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
1267 ↗(On Diff #34396)

p.s. A follow on change which would be good would be to use NeverNegative to set IsSigned. (Either value is legal, I think treating it as unsigned would be more canonical.) This would remove the order of visit dependency in the common case and help create a single canonical form.

When you do this, you'll need to adjust some of the extension elimination logic to account for when a sext and zext are interchangable.

Once that's done, we can canonicalize all sext on non-negative indvars to zext. Arguably, that could be done instead of adjusting the cast removal logic mentioned previously.

sanjoy updated this revision to Diff 34478.Sep 10 2015, 12:38 PM
sanjoy marked 2 inline comments as done.
  • Address Philip's review.

replied inline.

lib/Transforms/Scalar/IndVarSimplify.cpp
849 ↗(On Diff #34396)

Added a comment, ptal.

1265 ↗(On Diff #34396)

isKnownNonNegative does not look at control flow and so is weaker than isKnownPredicate. I've added a test case (test8) that does not work with isKnownNonNegative.

test/Transforms/IndVarSimplify/widen-loop-comp.ll
213 ↗(On Diff #34396)

It isn't obvious to me whether we chose a sext or a sext for the
induction variable in this loop. We could do either base on order of
visitation. Could you clarify this?

Thanks for pointing this out!

In @test7 and @test6 it is impossible to tell what -indvars did
(sign extend or zero extend) based solely on how the structure of
%indvars.iv. This is because normally you'd look at the initial
value of induction variable to deduce if the induction variable was
sign or zero extended; but here we're out of luck since the initial
value is a positive constant (== 0) so its sign and zero extensions
are the same.

I've added two more tests @test8 and @test9 that have a
non-constant initial value of the induction variable being widened.
By looking at the initial value of the induction variable phi (whether
it is a sext or zext), we can deduce if the indvar was zero extended
or sign extended.

If we start canonicalizing sign extensions of positive induction
variables to zero extensions then then it would be impossible tell if
zero or signed widening happened on @test8 and @test9 also; but we
do not do that today.

Also, can you add tests for the full 2 x 2 matrix of signed/unsigned
widdening x signed/unsigned compare?

The rest of the file already has tests for the two (signed widening,
signed compare) and (unsigned widening, unsigned compare) cases.
@test8 checks the (signed extension, unsigned compare) case, while
@test9 checks the (unsigned extension, signed compare) case.

Also, given your comment, I think @test6 and @test7 do not add
much value to this change beyond just being generic correctness tests.
Do you think it makes sense to remove these?

reames added inline comments.Sep 10 2015, 2:46 PM
test/Transforms/IndVarSimplify/widen-loop-comp.ll
213 ↗(On Diff #34478)

I would prefer you left them. The zero based increasing loop is a simpler, easier to understand, and really important case. I think there's value even if they're covered by the additional cases.

mcrosier edited edge metadata.Sep 14 2015, 9:41 AM

My understanding of the CHECK-LABEL directive is that it matches a single unique strings within a file (e.g., function names). I assumed FileCheck would complain if you have multiple CHECK-LABEL directives with the same (i.e., for.cond:) check, but that doesn't appear to be the case here. What have I missed?

sanjoy updated this revision to Diff 34702.Sep 14 2015, 10:43 AM
sanjoy edited edge metadata.

The docs are pretty clear about CHECK-LABEL's matching unique lines
"they must simply uniquely match a single line in the file being
verified.", so I've removed the problematic CHECK-LABEL directives.

However, FileCheck does not complain either way.

hfinkel accepted this revision.Sep 18 2015, 12:13 PM
hfinkel added a reviewer: hfinkel.
hfinkel added a subscriber: hfinkel.

LGTM.

This revision is now accepted and ready to land.Sep 18 2015, 12:13 PM
This revision was automatically updated to reflect the committed changes.