Page MenuHomePhabricator

[IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative
ClosedPublic

Authored by lihuang on Apr 7 2016, 1:58 PM.

Details

Summary

[IndVarSimplify] Eliminate zext of a signed IV when widening if the IV is known to be non-negative.

This was part of a previous diff (D18777), now separated into a new diff. This change eliminates zexts of IV when IV is treated as signed and is known to be non-negative.

The change in D18777 will fail a front-end test (Frontend/optimization-remark-options.c) and this change should fix this test.

Diff Detail

Repository
rL LLVM

Event Timeline

lihuang updated this revision to Diff 52951.Apr 7 2016, 1:58 PM
lihuang retitled this revision from to [IndVarSimplify] Eliminate zext of a signed IV when the IV is known to be non-negative .
lihuang updated this object.
lihuang added reviewers: sanjoy, reames, mbodart.
lihuang added a subscriber: llvm-commits.
reames requested changes to this revision.Apr 13 2016, 4:58 PM
reames edited edge metadata.

Test case? Mandatory.

Drive by comments. I'll defer actual review to Sanjoy or someone more comfortable with this code. If you haven't gotten a review within a reasonable time frame (1 week), feel free to ping me directly and I'll take another look and rebuild my mental model of this code to be able to review..

lib/Transforms/Scalar/IndVarSimplify.cpp
1402 ↗(On Diff #52951)

Remove explicit value of default param.

This revision now requires changes to proceed.Apr 13 2016, 4:58 PM
lihuang updated this revision to Diff 53796.Apr 14 2016, 3:27 PM
lihuang edited edge metadata.

Add a test to this change.

lihuang marked an inline comment as done.Apr 14 2016, 3:28 PM
lihuang updated this object.Apr 15 2016, 9:46 AM
lihuang edited edge metadata.
mbodart added inline comments.Apr 15 2016, 2:08 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
1309 ↗(On Diff #53796)

The new check for isa<ZExtInst> seems unnecessary.
If DU.NeverNegative is true, it means DU.WideDef will have zeroes
in its upper bits regardless of whether it was created with a Zext or Sext.

This is the first time I've looked at this code, so I don't know if you can
simply delete this part of the check, or if you must at least verify
that DU.NarrowUse is some flavor of Extend (as opposed to an
arbitrary instruction).

1402 ↗(On Diff #53796)

While the change seems correct, it raises the question of why isKnownPredicate is not
catching this case. Have you looked into that?

sanjoy requested changes to this revision.Apr 17 2016, 10:12 PM
sanjoy edited edge metadata.

+1 to both comments by @mbodart

Specifically with regards to the isKnownNonNegative comment: if isKnownPredicate is failing here, you might consider teaching it to use getSignedRange internally, since the range SCEV computes for %i.0 is [0,-2147483648) (all positive integers) so we should be able to use that information.

This revision now requires changes to proceed.Apr 17 2016, 10:12 PM
lihuang updated this revision to Diff 54591.Apr 21 2016, 4:04 PM
lihuang edited edge metadata.

Sorry for the late reply, took sick days.

I spent some time looking at the ScalarEvolution code. isKnownPredicate doesn't catch this case because when creating SCEV from an instruction, the "nsw" flag of the instruction is not propagated to the SCEV. For example, the case in the added test:

        %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
        ... 
        %add = add nsw i32 %i.0, 2
        ...
        %inc = add nsw i32 %i.0, 1

When creating SCEV for %add from "%add = add nsw i32 %i.0, 2", the "nsw" flag is lost so it's not recognized as non-negative. The code that rules out this flag is in getNoWrapFlagsFromUB(), which is introduced in http://reviews.llvm.org/D11212 . I'm not very familiar with the SCEV code, so I'm not sure if the flag propagation in SCEV is supposed to propagate "nsw" in this case. If the flag propagation is correct, then we might need to use isKnownNonNegative from ValueTracking.

What do you suggest?

lihuang added inline comments.Apr 21 2016, 4:05 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
1308 ↗(On Diff #54591)

You are right, the DU.WideDef's upper bits will be zeros whether it was from a Zext or Sext. Here we need to verify that DU.NarrowUse is a Zext or Sext. I changed the checks here to include the 4 possible cases:

  1. DU.NarrowUse is a Sext, WideIV is signed,
  2. DU.NarrowUse is a Sext, WideIV is unsigned, but DU.NeverNegative is true
  3. DU.NarrowUse is a Zext, WideIV is unsigned,
  4. DU.NarrowUse is a Zext, WideIV is signed, but DU.NeverNegative is true

added one more test for case 2.

mbodart added inline comments.Apr 22 2016, 9:00 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
1308 ↗(On Diff #54591)

This looks great.
I'll defer to the other reviewers on the isKnownPredicate issue.

Ping :)

Hi Sanjoy and Philip,

For the NeverNegative issue, are you okay with using isKnownNonNegative? Or you think we should modify SCEV code to make isKnownPredicate work for this case.

Thanks!

I looked at the threads on llvm-dev discussing the no-wrap flag propagation issues. It seems like this has been a problem for a while and there is not a clear agreement on when and how to propagate no-wrap flags from instructions to corresponding SCEVs.

The problem in this case could be easily solved by propagating "nsw" flag of "%add = add nsw i32 %i.0, 2" to it's SCEV. It's not possible to infer the "nsw" flag for this SCEV. As %i.0 has range [0,-2147483648), "%i.0 + 2" could cause signed-overflow.

Sanjoy, I see you are actively contributing to SCEV. Do you know the community's plan on strengthening the no-wrap flag propagation? The tests I added here might not serve as a very good motivation for the effort but I think this will generally benefit SCEV and some optimizations depending on SCEV.

Thanks!

Hi!

Firstly, apologies for letting this set for so long.

I looked at the threads on llvm-dev discussing the no-wrap flag
propagation issues. It seems like this has been a problem for a while
and there is not a clear agreement on when and how to propagate
no-wrap flags from instructions to corresponding SCEVs.

The problem in this case could be easily solved by propagating "nsw"
flag of "%add = add nsw i32 %i.0, 2" to it's SCEV. It's not possible
to infer the "nsw" flag for this SCEV. As %i.0 has range
[0,-2147483648), "%i.0 + 2" could cause signed-overflow.

Sanjoy, I see you are actively contributing to SCEV. Do you know the
community's plan on strengthening the no-wrap flag propagation? The
tests I added here might not serve as a very good motivation for the
effort but I think this will generally benefit SCEV and some
optimizations depending on SCEV.

You're on the right track -- in many cases SCEV cannot propagate
no-wrap flags from the instruction to the SCEV expression. However,
the test cases as written don't work with isKnownPredicate because
the loops are not in canonical form, and not because of some
fundamental reason. If I run -loop-rotate on them (possibly
followed by -loop-simplifycfg) then your patch minus the
isKnownNonNegative bit does the right thing.

So I'd suggest checking if (in your pass pipeline) you're
canonicalizing the loops before passing them to -indvars. If you
are and are still facing issues, then it is fine to use
isKnownNonNegative here (since there _is_ a shortcoming in
ScalarEvolution::isKnownPredicate) with test cases that
fundamentally require isKnownNonNegative (and don't work with
ScalarEvolution::isKnownPredicate even on rotated loops).

Using -loop-rotate works for these cases, as the "%add = add nsw i32 %i.0, 2" is brought to loop header and "nsw" is propagated. Thank you Sanjoy!

lihuang updated this revision to Diff 62016.Jun 27 2016, 2:28 PM
lihuang edited edge metadata.

Removed the isKnownNonNegative part, created a new file for the 2 tests. As Sanjoy pointed out, isKnownPredicate didn't work with these cases because the loops are not in canonical form. Using loop-rotate before indvars solves the issue.

Actually, adding -loop-rotate just happens to work for this case, it doesn't solve the fundamental problem. For example, adding -loop-rotate or other loop pass sequences doesn't help with the case in D21773

+1 to both comments by @mbodart

Specifically with regards to the isKnownNonNegative comment: if isKnownPredicate is failing here, you might consider teaching it to use getSignedRange internally, since the range SCEV computes for %i.0 is [0,-2147483648) (all positive integers) so we should be able to use that information.

Hi Sanjoy,

This thread is old but I hope you could remember, sorry about this.

For this old issue, I tried different solutions but think I really need to use isKnownNonNegative here, because isKnownPredicate doesn't work because of the discrepancy of "nsw" flag between instruction and SCEV. The "nsw" flag propagation in SCEV based on poison value analysis is very conservative and only considers full poison propagation, so it doesn't work for this case. Loosing the flag propagation condition might be controversial and potentially a lot of work. The issues here could be easily solved by using isKnownNonNegative, which also solves the issue in D21773 which blocks D18777 and r274098.

Is there a strong reason against using ValueTracking's isKnownNonNegative here?

Thanks,
Li Huang

Hi @lihuang,

Using isKnownNonNegative is fine, but please add a comment stating
why you're doing that (to work around conservatism in
ScalarEvolution around no-wrap flags).

lihuang updated this revision to Diff 65841.Jul 27 2016, 5:07 PM

Hi Sanjoy,

Are you okay with the new change? I have added the comment as you asked. I also rebased the ValueTracking change in D18777 on the latest source.

sanjoy accepted this revision.Aug 3 2016, 4:32 PM
sanjoy edited edge metadata.

lgtm

This revision was automatically updated to reflect the committed changes.
lihuang edited edge metadata.Aug 24 2016, 1:05 PM
lihuang added a subscriber: Farhana.