Ping.

No custom decoding is required

Fixed the tests as to check boundaries, and one value in the middle.
Changed tests ordering as they generated empty lines not treated by FileCheck.

To send patch....

Removed processor and specific triple target from test.

Updated test to use llvm-mc instead of clang.

Simplified tests. Using the standard function for emitting data symbols, if required.

In D51683#1226329, @joerg wrote:

Correct. The protected name is double underscore as both suffix and prefix.

Fix test march triple.

Fixed comment explaining the elaborated growth cost-function.

Using FileCheck in test file.

Added missing test-file

Moving this pattern matching to AggressiveInstCombine following a suggestion of @lebedev.ri . Now it searches for minimal required patterns as desired by @spatel.

In D49229#1185608, @spatel wrote:

So all expensive operations have been eliminated, I do not see why it wouldn't fit in InstCombne. We detect a pattern and we reduce it.

Because the pattern that we are matching is larger than it needs to be (as the comment in the test file clearly shows - there is no 'or' in the minimal pattern). This problem of trying to make everything fit in instcombine has been discussed several times on llvm-dev in the last ~year. Eg:
http://lists.llvm.org/pipermail/llvm-dev/2017-September/117151.html

I agree that it won't handle all cases. But one will need to come with a more generic thinking as to create a new pass that handles this. Something like an abstract known bits, that tells that two values hold the same bits coming from a given instruction, or some simplification by demanded bits from the same values. It is feasible, but it is not my intention to do it so now.

Did you look at (new)-GVN to see if it fits in there?

I must confess that I did not quite understand all the work-flow of newGVN, but from what I did see, it mostly wouldn't fit. It seems to behave like InstCombine, expecting to replace the current instruction being visited. And it would require to create one value as to detect if there is a leader of that value and then reuse it. It is not that complicated, but quite awkward IMO.

If this is in instcombine (in addition to missing the pattern when there is no 'or'), I think you have to limit the transform based on uses as Roman mentioned in an earlier comment.

Added test that the inner and must be replaced by the new shift operation.
Converted the function to bool, as it does not require to create the Or operation after the replaceAll.

As we are replacing all the uses of the DeadAnd, it is not required to create and replace the visiting Or operation. Replace all uses does the job already.

Replaces all uses of the innermost and with the new shift.

Relaxed conditions for which the transformation is applied.
Added more tests for ashr.

Removed unused arguments.
Early exit.

All required values are obtained during the pattern matching.

Moved to a separated function. Placed function call after knowing more about the operands.
Added ashr case, that was being wrongly treated as lshr.
Added comments, including one that argues that this function would be useless if and instructions are move before any type of shift operations.
Using m_c_Or, and passing operands as arguments.

Did most fixes. Just don't how to capture non-leaf nodes of the pattern being matched. Using other match operations would actually be more complicated than just passing the operands as arguments to the new function, now that I already know they are AND operations due the function call placement.

Detect desired pattern from the binary operation using the results.

In D49229#1163319, @lebedev.ri wrote:

1. Please always upload all patches with the full context (-U99999)

Sorry, I thought that it being an entire function it wouldn't matter. Lesson learned.

Added context.

Using hasNUses() instead of numUses() ==

Replaced num_uses by !hasNUsesOfValue as requested.

Moved test to correct folder

Only accepts instructions with 2 uses (AND / SHIFT operations). So that looping through the uses is not expensive, and we avoid it in most cases.
Removed recursive bit value computations(computeKnownBits).

Fixed execution costs. See below.

Constrain to allow the transformation to happen only when the masked value has only 2 users (an AND and a SHIFT).
Removed value tracking operations.

In D48278#1155793, @spatel wrote:

In D48278#1155779, @spatel wrote:

In D48278#1155560, @dnsampaio wrote:

It reduces the number of computation operations, from 3 to 2, and the number of constants kept int constants for performing the masking, from 2 to 1.
I don't see how it increases the latency. If you are going to perform the masking and the shift anyway.

Ah, I see that now. But I'm not convinced this is the right approach. Why are we waiting to optimize this in the backend? This is a universally good optimization, so it should be in IR:
https://rise4fun.com/Alive/O04

I'm not sure exactly where that optimization belongs. Ie, is it EarlyCSE, GVN, somewhere else, or is it its own pass? But I don't see any benefit in waiting to do this in the DAG.

This also raises a question that has come up in another review recently - D41233. If we reverse the canonicalization of shl+and, we would solve the most basic case that I showed above:

define i32 @shl_first(i32 %a {
  %t2 = shl i32 %a, 8
  %t3 = and i32 %t2, 44032
  ret i32 %t3
}

define i32 @mask_first(i32 %a) {
  %a2 = and i32 %a, 172
  %a3 = shl i32 %a2, 8
  ret i32 %a3
}

Ah, I see that now. But I'm not convinced this is the right approach. Why are we waiting to optimize this in the backend? This is a universally good optimization, so it should be in IR:

Agree, I also intend to implement this transformation in the IR. But there are cases that this is only seen after some instructions have been combined in the dag, so why not here also? And indeed, it is a requirement for a future patch that detects opportunities to reduce load and store widths.

Added checks for shift opcodes as to early exit if not found.
Validate mask widths (although it would be a error in the code if they are of different).

In D48278#1155230, @RKSimon wrote:

Like @spatel I'm not clear on what you're really trying to accomplish here - has the arm/arm64 codegen improved?

In D48278#1155201, @spatel wrote:

This patch was reverted with rL336453 because it caused:
https://bugs.llvm.org/show_bug.cgi?id=38084

Sorry about that.

Beyond that, I don't understand the motivation. The patch increases the latency of a computation. Why is that beneficial? The x86 diff doesn't look like a win to me.

It reduces the number of computation operations, from 3 to 2, and the number of constants kept for performing the masking, from 2 to 1.
I don't see how it increases the latency. If you are going to perform the masking and the shift anyway.

I don't know what the ARM/AArch output looked like before this patch. Always check in the baseline tests before making a code change, so we have that as a reference (and in case the patch is reverted, we won't lose the test coverage that motivated the code patch).

One bot is failing in the test CodeGen/AArch64/FoldRedundantShiftedMasking.ll
I'm trying to figure out why as it doesn't happen with my debug or release builds.

Give patch more context.

AArch64 tests go into the folder AArch64

Please see
https://bugs.llvm.org/show_bug.cgi?id=38061

Replaced tests as to be not dependent in the load width reduction.
Added 1 positive test per case, and 2 negative tests, one where one mask is not a constant and other the shifted amount is not constant.

All good.

Seems good to me.

Hi Ivan,
The patch fixes the crash, but I would like to know if the desired updates aren't already done, just needing to copy paste them?
Cheers
Diogo

Please add the new intrinsics to the target specific combine function of VLDUP NEON load/store intrinsics
ARMISelLowering.cpp, line 11477. The switch dies on llvm_unreachable.

Removed flag as requested.