Unfortunately, the change that this test was designated to test never matured into a patch, so it was left as an orphan.
For the time being, you can even delete it altogether.

In D41574#972358, @opaparo wrote:

In D41574#964524, @opaparo wrote:

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

The new pass is a kind of preparation pass for InstCombine. It complements changes introduced at D39421, as well as other InstCombine transformations. Checkout my lit tests, they illustrate several scenarios.
I believe that this pass will open a gate to other reassociations required by InstCombine transformations, reassociations that can't be expressed in means of the existing Reassociate pass.

@davide, does that answer your questions? Do you have any additional concerns?

Rebased and added lit tests

Ping.

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

In D41574#1110465, @mzolotukhin wrote:

What are benchmarks results with this pass (compile-time/performance)? Do we really need it at all optlevels, or can we only include it at -O3?

Several changes in this revision:

In D47163#1108032, @spatel wrote:

@opaparo can you review this patch? I'm wondering if this will help any of the motivating cases for D46380.

Following this discussion, rebasing the patch to trunk.

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

In D46380#1103696, @spatel wrote:

In D46380#1098045, @opaparo wrote:

In D46380#1096108, @spatel wrote:

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.

In D46380#1096108, @spatel wrote:

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.

In D46380#1096108, @spatel wrote:

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)

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.

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

In D46380#1094593, @spatel wrote:

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.

Ping.

The required changes were made in D45731

In D45731#1070485, @spatel wrote:

Thanks for coming back to this. I think this patch is fine as one more match of a potential IR variant, but...
Since the time we started the discussion in D41353, there was a proposal to improve matching for ctpop and ctlz in D45173. I'm curious what others think about the fact that we match bswap/bitreverse in regular instcombine. Would it be better to match all of those intrinsics in the same place? Do we distinguish these based on how often we expect them to occur?

What are your plans for deeper associate-operand trees, such as in the tests I've suggested at D41574? Will you support such cases?

Restoring the ownership of this revision.

Ping

Ping

Ping

In D41574#964524, @opaparo wrote:

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

The new pass is a kind of preparation pass for InstCombine. It complements changes introduced at D39421, as well as other InstCombine transformations. Checkout my lit tests, they illustrate several scenarios.
I believe that this pass will open a gate to other reassociations required by InstCombine transformations, reassociations that can't be expressed in means of the existing Reassociate pass.

Ping

Ping

Ping

In D41574#964124, @davide wrote:

In D41574#964111, @opaparo wrote:

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Although both of the passes perform reassociation, they are essentially very different.
The Reassociate pass aggressively modifies the topography of the expression tree, basically rewriting it, while the WeakReassociate pass uses the existing topography.
The Reassociate pass creates new instructions while the WeakReassociate pass does not.
Moreover, their method of reassociation is completely different. To modify the existing Reassociate pass to supports reassociation of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3) will take a great amount of changes, changes that will almost certainly collide with existing behavior and test cases. For example, how will it decide whether (a_0 + a_1) + (a_2 + a_3) will be transformed into a_0 + (a_1 + (a_2 + a_3)) like its current behavior or to (a_0 + a_2) + (a_1 + a_3) like the new behavior?
The existing Reassociate pass lacks, by design, several kinds of reassociations, kinds that I believe can find a home in the new pass.
IMO, maintaining one big pass that has two distinguished purposes can prove to be a greater burden than maintaining two smaller passes, each dedicated to its own purpose.

(Only trying to understand) From what I see the main consumers of reassociation are Global Value Numbering to discover more equivalences and instruction combining.
The former can probably embed reassociation while performing equivalence finding (in fact, there are algorithms where this happens), the latter already performs a fair amount of "canonicalization" (sometimes, too much). I wonder where your pass fits/what's the use case? Do you plan to enable it as part of the default pipeline?

Thanks,

Davide

In D41574#964073, @davide wrote:

It's not entirely clear to me why you need another reassociate pass.
We should really try to share as much code as possible with the existing one instead of adding maintenance burden.

Now using the constant's value rather than its pointer value for enforcing total order on LeafClasses. This is needed in order to ensure deterministic output of the compiler (I actually got different results when running with different OSs before this change).

1. Generalized InstructionSimplify's IsSafeOverflowingBinaryOperator to handle 'add', 'sub' and 'mul' in addition to 'shl'. This was done by refactoring existing behavior out of InstCombine's internals into ValueTracking, so now both InstCombine and InstructionSimplify use it.
2. Added tests to cover possible cases. For each OverflowingBinaryOperator ('shl', 'add', 'sub' and 'mul') I've created tests according to the Cartesian product of four factors: the op has the nuw flag, the op has the nsw flag, there actually is an unsigned overflow, there actually is a signed overflow. The key idea is to check that optimizations occur if and only if the overflow flag is absent or no overflow is guaranteed. also note that the file name had changed from select-bitext-bitwise-ops.ll to select-obo-peo-ops.ll to better reflect the nature of the tests it contains.

Added a comment explaining the change of pattern in the bswap idiom detection.

Rebasing on top of the new parent review D41354

1. Relaxing the canonization condition: the masked shl will be canonized to the new form only if the 'shl''s 0th operand is not a shift instruction. This is due to other, better optimization that will be able to kick in.
2. Reverted the InstructionSimplify and bswap changes. Those will be added in two different reviews.

In D39421#945064, @spatel wrote:

Both this and D38037 are trying to start a pattern match with an 'or', but I'm curious if there's a 'trunc' in the larger source that creates these patterns? Either way, we're missing something bigger than patterns that start with 'or'.

For example, I was looking at PR31667:
https://bugs.llvm.org/show_bug.cgi?id=31667

Name: sub_mask_shift

%and1 = lshr i32 %x, 3
%shr1 = and i32 %and1, 8191
%and2 = lshr i32 %x, 1
%shr2 = and i32 %and2, 32767
%r = sub i32 %shr1, %shr2

...which was filed as a backend bug, but we wouldn't handle that in IR either:
https://rise4fun.com/Alive/id4

So I think there's some more general sequence that we want to capture and optimize, but it may be difficult to justify as part of instcombine?

Note that there is a proposal for a new pass where all of these might find a home:
D38313

These changes will be handled by D41233, D39421 and perhaps a few more future changes.

Rebasing on parent revision and adding more test cases.

In D39421#937705, @spatel wrote:

I think inverting the canonicalization of shl+and would make your first test case optimize without this patch

Could you please explain why? I'm not sure I'm seeing it.

Currently, we end up inverting the canonicalization in the x86 backend (because a smaller constant mask can be created in less instruction bytes), so it would be better to "get it right" here in IR in the first place.
I understand the multi-use case better now with your explanation, so I agree that we want this patch to handle those cases too. But I don't think we should ignore the underlying canonicalization choices just because we know we want to catch the larger patterns.

I agree that this alternative canonization could prove to be beneficial and more correct. However, I feel that this discussion is orthogonal to this patch, and if it would indeed be decided to switch to the new form then some of the code of this patch, along with several other pieces of code, may need to change accordingly.

In D39421#923308, @spatel wrote:

Why do we canonicalize shift-left before 'and'?

Ie, shouldn't we prefer this:

define i8 @andshl(i8 %x) {
  %and = and i8 %x, 1
  %shl = shl i8 %and, 3
  ret i8 %shl
}

instead of this:

define i8 @andshl(i8 %x) {
  %and = shl i8 %x, 3
  %shl = and i8 %and, 8
  ret i8 %shl
}

...because doing the 'and' before the shift always uses a smaller constant?

Replacing std::make_unique with llvm::make_unique.
Adding "skylake-avx512" to the architectures which the optimization will be enabled for.

Now using MCInstrDesc via MCInstrInfo instead of checking for specific opcodes.
Checked in the test and rebased to make changes more clear.
Added a negative test.
Fixed some typos.

Adding a pattern match for a shift of and ((V&C1)<<C2).
Although and of shift is the canonical form, this new form is also required in some cases. The new test multiuse3 demonstrate such a case.

In D38037#882371, @spatel wrote:

I haven't looked much at the reassociation pass, but this seems like something that would be simpler to canonicalize there. Did you look at adding a rule there?

Eg, in the "or_or_shift" test, you have a tree of 'or' ops. If you reassociate those so that similar shifts are paired together, instcombine would manage to fold that using existing patterns (although maybe not optimally yet):

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %3, %5    <--- shl with shl
  %8 = or i32 %4, %6    <--- lshr with lshr
  %9 = or i32 %7, %8
  ret i32 %9
}

$ ./opt -instcombine reass.ll -S

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = shl i32 %x, 6
  %2 = and i32 %1, 384
  %3 = lshr i32 %x, 1
  %4 = and i32 %3, 3
  %5 = or i32 %2, %4
  ret i32 %5
}

1. Removed the lambda MatchShiftOfAnd as Shift of And is canonicalized to And of Shift, so the lambda MatchAndOfShift is sufficient.
2. The lambda MatchAndOfShift is now not static.
3. Removed unnecessary calls to replaceAllUsesWith.
4. Fixed test documentation.

1. MCAsmBackend c'tor now takes a unique_ptr of MCCodePadder instead of a raw pointer
2. MCCodePaddingContext has a new field: IsBasicBlockReachableViaBranch
3. Changed names of a function and several variables

In D34393#844569, @davidxl wrote:

Tried the two patches with our internal benchmark -- the alignment related performance issue is still there. The problem disappears with -mllvm -x86-experimental-pref-loop-alignment=5 is used.

In D34396#843773, @iteratee wrote:

Do you plan on doing something similar for the DSB decode cache issues that occasionally arise?
Specifically this: https://bugs.llvm.org/show_bug.cgi?id=5615

Ping

Ping

Removed unwanted dependencies introduces in my previous patch: MC layer no longer depends on CodeGen, Core or Target. This was achieved by introducing a new structure named MCCodePaddingContext that is being created by AsmPrinter and passed on to the MC layer (all the way to MCCodePadder). This replaces the direct use of TargetMachine, MachineBasicBlock, MachineFunction and MachineLoopInfo by the MCCodePadder.
Note: This time I used "svn diff -x -U999999" to create the patch, so comparison between this patch and the previous one may prove to be challenging (This had to be done for future work and review).

Removed unwanted dependencies introduces in my previous patch: MC layer no longer depends on CodeGen, Core or Target. This was achieved by introducing a new structure named MCCodePaddingContext that is being created by AsmPrinter and passed on to the MC layer (all the way to MCCodePadder). This replaces the direct use of TargetMachine, MachineBasicBlock, MachineFunction and MachineLoopInfo by the MCCodePadder.
Note: This time I used "svn diff -x -U999999" to create the patch, so comparison between this patch and the previous one may prove to be challenging (This had to be done for future work and review).

Should we expose this to the .s?

That would make it easy to test codegen because you would just need to
check for things like .pad_bb_begin.

It would make it easier to test the layout as you could use a simple .s
file for that.

Cheers,
Rafael

Added 32-bit test for the intrinsics