This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] Adding safety checks for 'shl', 'ashr' and 'lshr'
Needs ReviewPublic

Authored by opaparo on May 2 2018, 11:44 PM.

Details

Summary

As of today, InstSimplify does not transform patterns that include an 'shl', a 'ashr' or a 'lshr', as such a transformation may result in a different behavior in the case that that operand loses bits. However, in many cases these operators can be proven to not violate their restrictions and not lose any bits, and so we are missing safe transformation opportunities.
This patch introduces safety checks for the OverflowingBinaryOperators 'shl', and for the PossiblyExactOperators 'ashr' and 'lshr', enabling new kinds of transformations.

Diff Detail

Repository
rL LLVM

Event Timeline

opaparo created this revision.May 2 2018, 11:44 PM
opaparo edited the summary of this revision. (Show Details)May 3 2018, 12:04 AM

Moving the functions from instcombine to valuetracking is NFC, right? If so, can you do that now, so this patch is minimized? The similar functions should be in one place already.

opaparo updated this revision to Diff 146150.May 10 2018, 10:15 AM

Moving the functions from instcombine to valuetracking is NFC, right? If so, can you do that now, so this patch is minimized? The similar functions should be in one place already.

Done. Separated the NFC to a different review and rebased on top of it.

I haven't looked at the details of everything that's going on in these folds, but a couple of higher-level points:

  1. This is an instsimplify patch - the review title should be changed; there should be minimal tests for each transform under tests/Transforms/InstSimplify.
  2. This is using ValueTracking which can be expensive in compile-time - do you have any stats for how often this fires, perf improvements, compile-time regressions? (adding Eli for thoughts about where we would draw that line because I really don't know)
opaparo retitled this revision from [InstCombine] Extending InstructionSimplify to check OverflowingBinaryOperators and PossiblyExactOperators safety to [InstSimplify] Adding safety checks for 'shl', 'ashr' and 'lshr'.May 14 2018, 8:32 AM
opaparo edited the summary of this revision. (Show Details)
opaparo updated this revision to Diff 146621.May 14 2018, 8:35 AM

Removing safety checks for 'add', 'sub' and 'mul', since they require ValueTracking which proved to be too expensive in compile time.

  1. This is an instsimplify patch - the review title should be changed; there should be minimal tests for each transform under tests/Transforms/InstSimplify.

The title was changed. However, those changes do not affect InstSimplify directly, as they are not used by this pass. The only functional change is in InstCombine, which uses these parts of InstSimplify as a library.

  1. This is using ValueTracking which can be expensive in compile-time - do you have any stats for how often this fires, perf improvements, compile-time regressions? (adding Eli for thoughts about where we would draw that line because I really don't know)

After a close look I discovered some compile-time regressions, as you predicted. I removed the safety checks for 'add', 'sub' and 'mul', which require ValueTracking (so now there are only safety checks for 'shl', 'ashr' and 'lshr'). That elimintated those regressions.

  1. This is an instsimplify patch - the review title should be changed; there should be minimal tests for each transform under tests/Transforms/InstSimplify.

The title was changed. However, those changes do not affect InstSimplify directly, as they are not used by this pass. The only functional change is in InstCombine, which uses these parts of InstSimplify as a library.

I don't understand this statement. The proposal affects SimplifyWithOpReplaced() which is only called from within instsimplify (simplifySelectWithICmpCond), so every test should be visible using only -instsimplify. The first test should be reduced to something like this:

define i64 @sel_false_val_is_a_masked_shl_of_true_val1(i32 %x) {
  %x15 = and i32 %x, 15
  %sh = shl nuw nsw i32 %x15, 2
  %z = zext i32 %sh to i64
  %cmp = icmp eq i32 %x15, 0
  %r = select i1 %cmp, i64 0, i64 %z
  ret i64 %r
}

But this example doesn't need nsw/nuw, so what is this test trying to demonstrate?
https://rise4fun.com/Alive/9zX

Also, this is still using ValueTracking, so I'm not comfortable continuing this review until we have more data about the cost and benefits.

craig.topper added inline comments.May 20 2018, 6:19 PM
lib/Analysis/InstructionSimplify.cpp
3486

dyn_cast_or_null allows OBO to be null, but it was dereferenced on the line above. If PEO can't be null, then this should just be dyn_cast.

3514

dyn_cast_or_null allows PEO to be null, but it was dereferenced on the line above. If PEO can't be null, then this should just be dyn_cast.

  1. This is an instsimplify patch - the review title should be changed; there should be minimal tests for each transform under tests/Transforms/InstSimplify.

The title was changed. However, those changes do not affect InstSimplify directly, as they are not used by this pass. The only functional change is in InstCombine, which uses these parts of InstSimplify as a library.

I don't understand this statement. The proposal affects SimplifyWithOpReplaced() which is only called from within instsimplify (simplifySelectWithICmpCond), so every test should be visible using only -instsimplify. The first test should be reduced to something like this:

define i64 @sel_false_val_is_a_masked_shl_of_true_val1(i32 %x) {
  %x15 = and i32 %x, 15
  %sh = shl nuw nsw i32 %x15, 2
  %z = zext i32 %sh to i64
  %cmp = icmp eq i32 %x15, 0
  %r = select i1 %cmp, i64 0, i64 %z
  ret i64 %r
}

You're right. I've originally missed the direct effect on InstSimplify, and I will change the tests location and structure if this change is accepted, but please also note that lib/Transforms/InstCombine/InstCombineSelect.cpp calls SimplifySelectInst which calls simplifySelectWithICmpCond which in turn calls SimplifyWithOpReplaced. Hence, InstCombine also benefits from this functional change.

But this example doesn't need nsw/nuw, so what is this test trying to demonstrate?
https://rise4fun.com/Alive/9zX

Exactly that. In the current status, InstCombine and InstSimplify will not perform this transformation despite it's correctness. Furthermore, if you remove the nsw/nuw flags from the 'shl' in this example, InstCombine will first identify that the 'shl' really has no signed and unsigned wraps and will add the flags before the 'select' had the chance to optimize, which will result in the same un-transformed code. This is exactly one of the missed transformation opportunities I'm trying to cease.

Also, this is still using ValueTracking, so I'm not comfortable continuing this review until we have more data about the cost and benefits.

You're right that ValueTracking is still used, but running this change on a large set of benchmark did not yield any noticeable compile-time regressions. In addition, the two functions from ValueTracking that I'm using (ComputeNumSignBits and MaskedValueIsZero) are already in use in InstructionSimplify.cpp.

opaparo updated this revision to Diff 148005.May 22 2018, 7:43 AM

Changing 'dyn_cast_or_null' to 'dyn_cast' in two places where the operator cannot be null.

opaparo marked 2 inline comments as done.May 22 2018, 7:44 AM
opaparo updated this revision to Diff 151645.Jun 17 2018, 8:14 AM

Rebasing the patch and adjusting it to the changes made in rL333689.
Removed special code for CastInst in InstructionSimplify::SimplifyWithOpReplaced as rL333689's changes handle that (in a different way).

I see the motivation better now, but I'm still worried about using ValueTracking.

Can you collect some stats as was done in D47891? I'm curious to know:

  1. How often do we call ValueTracking?
  2. How often does this transform occur?

Reasonable benchmarks are the same as in the other patch: test-suite or compiling clang/llvm.

lebedev.ri requested changes to this revision.Jul 14 2018, 7:13 AM

(Removing from my review queue for the time being.)

This revision now requires changes to proceed.Jul 14 2018, 7:13 AM
sanjoy resigned from this revision.Jan 29 2022, 5:42 PM
lebedev.ri resigned from this revision.Jan 12 2023, 4:57 PM

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

This revision now requires review to proceed.Jan 12 2023, 4:57 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 4:57 PM
Herald added a subscriber: StephenFan. · View Herald Transcript