Thanks for breaking this up - LGTM.
See inline for a couple of nits.

Note: memcmp expansion for x86 was reduced with https://reviews.llvm.org/rL308986 because it caused a perf regression in PR33914 ( https://bugs.llvm.org/show_bug.cgi?id=33914 ).
There's a proposal to revert the expansion for x86 entirely in PR34032 ( https://bugs.llvm.org/show_bug.cgi?id=34032 ) because of a related perf regression and compile-time explosion in CGP (PR33900 - https://bugs.llvm.org/show_bug.cgi?id=33900 ). IMO, we need to solve the CGP addressing-mode bug anyway, but just so everyone is aware - memcmp expansion for x86 is still shaky at this point.

In D36840#844861, @spatel wrote:

Patch updated:
Remove the general case fold which actually isn't a win if vselect is fast. We only convert the vselect when there's a clear optimization now.

Patch updated:
Remove the general case fold which actually isn't a win if vselect is fast. We only convert the vselect when there's a clear optimization now.

On Thu, Aug 17, 2017 at 3:52 PM, <escha@apple.com> wrote:

btw, to note, blendv *is* a “fast op” on most arches; what’s one extra uop is the fact that the V form takes 3 inputs. iirc, it’s the same reason that ADC, CMOV, etc can’t be 1 uop (2 inputs + flags). the forms that don’t take 3 inputs are usually 1 uop.

Adding some more x86 experts.

> For x86, blendv* is always a multi-uop / multi-cycle instruction according to Agner's docs

Are you sure?

Bulldozer, Piledriver, Ryzen, and Skylake seem to list PBLENDVB and BLENDVPS as 1 uop.

Thanks for the updates. I have no other suggestions.

I checked in the tests from cmov-promotion.ll at rL311052, so we'd see the baseline codegen. Can you rebase after that?

LGTM.

Just to make sure I'm understanding: the multiply patch (D36679) is independent of this?

Can we have the ashr fix as a separate patch before the mul patch? If yes, make tests for just that diff and split this up?

LGTM with change of the test diffs so this one goes in first.

Can you commit this one first with at least one test independent of those in D36498 to avoid the extra inst regressions seen there?

The comment about multi-uses of the compare in D36711 made me wonder what we're doing here. Should we check one-use before trying to transform?

In D36711#842468, @aivchenk wrote:

Thank you for your comments, I updated the patch to address them:

1. Done
2. MCU target does not have CMOV instruction so it is always converted into test+branch. I firstly cared about it - that's the reason why it is here

I think all of the non-multiply tests are simplified after rL310942. Can you double-check that? If so, you can remove those tests from this patch. Feel free to add them as an independent NFC commit if they cover some case that isn't covered already.

LGTM.

In D36711#842026, @spatel wrote:

It's worth noting that we could convert any select of constants to math ops. I was planning a follow-up to https://reviews.llvm.org/rL310717 that would do that, but there might be cases where we would prefer to select cmov? If not, that would make this patch obsolete.

It's worth noting that we could convert any select of constants to math ops. I was planning a follow-up to https://reviews.llvm.org/rL310717 that would do that, but there might be cases where we would prefer to select cmov? If not, that would make this patch obsolete.

In D36498#841022, @craig.topper wrote:

This patch is really just making InstCombine self consistent. We currently optimize this case differently depending on whether i8 is legal in datalayout.

define i32 @test71(i32 %x) {
; CHECK-LABEL: @test71(
; CHECK-NEXT: [[TMP1:%.*]] = lshr i32 [[X:%.*]], 6
; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 2
; CHECK-NEXT: [[TMP3:%.*]] = or i32 [[TMP2]], 40
; CHECK-NEXT: ret i32 [[TMP3]]
;

%1 = and i32 %x, 128
%2 = icmp eq i32 %1, 0
%3 = select i1 %2, i32 40, i32 42
ret i32 %3

}

If we want to remove foldSelectICmpAnd that's a different question.

LGTM.

Make sure I'm seeing this correctly: this patch should contain additional tests for ule/uge; ult/ugt should be added to the step before this (D36593)?

Wait - this does have a testable change, right? You can check the ult/ugt cases from InstSimplify with this:
http://rise4fun.com/Alive/XAV

LGTM.

I've been operating under the assumption that we want to transform in the opposite direction in IR. Ie, preserve and probably create more select-of-constants (see https://reviews.llvm.org/D24480 which I am planning to abandon). We should be able to reduce selects to logic/math in the DAG where it makes sense (eg, https://reviews.llvm.org/rL310717 ). Some reasons to prefer select were noted in:
http://lists.llvm.org/pipermail/llvm-dev/2016-September/105335.html

LGTM - thanks!

In D35035#839852, @joerg wrote:

@spatel: I don't see a reason why we can't (or shouldn't) try to do common-prefix elimination for the memcmp intrinsic. It certainly seems to be better to me to preserve the intrinsics in your case as they should be easier to reason about. That's kind of my question for here too -- why does the expansion allow better code?

Patch updated:
Replace the assume deletion with a comment about why it can't happen. :)

Patch updated - sorry, the last diff was not the one I intended to upload. This is NFC from the last rev, but:

1. Includes Hal's comment about range metadata.
2. Has CHECK lines for the poison_on_call_user_is_ok() test.

In D35035#839833, @joerg wrote:

What is the advantage of expanding the memcpy intrinsic in InstCombine vs doing it later in the target-specific code?

Patch updated - mostly just cutting and pasting the code Hal posted:

1. Make isExternallyVisible() check the calculated demanded bits rather than a list of opcodes.
2. Add a check for and delete llvm.assume.

Patch updated:

1. Use a loop (worklist) rather than recursion to avoid blowing up the stack.
2. Add an exclusion list based on opcodes to stop the search.
3. Add a test to show that the exclusion list works for a call inst.
4. Add a TODO comment with Nuno's suggestion from the bug report to make this better.

This patch as uploaded makes even less sense to me than before:

1. There are no tests to show the diff.
2. You've changed the code rather than an assertion in an unrelated test to show a functional difference?

LGTM.

Patch updated:
As shown in PR34097 ( https://bugs.llvm.org/show_bug.cgi?id=34097 ), I failed to account for the subtract overflow case, so add a check for that.

Patch updated - no functional changes intended from the previous rev, but cleaner:

1. Use isa<VectorType> in the assert and the callers' type check to make it clearer that vectors are allowed.
2. Use m_SpecificInt in pattern matches to reduce code.

In D36395#836103, @craig.topper wrote:

/// \brief Match a specific integer value or vector with all elements equal to
/// the value.
inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); }

Patch updated:

1. Add an assert for the shouldChangeType() guard that's in the caller function.
2. Replace the explicit match for zext of the shift value with a call to MaskedValueIsZero().
3. Remove the MaskedValueIsZero() check for the shift amount and generate our own masks to make the transform safe:

http://rise4fun.com/Alive/Qzm

4. Add test to exercise #2 and #3.

In D36395#834263, @efriedma wrote:

I spent a bit of time playing with the generated for for various implementations of rotate for 16-bit values. It looks like this transform actually makes things worse; e.g. on ARM the transformed version compiles to one more instruction. Granted, that's probably not important; I think the optimal lowering for a 16-bit rotate on ARM actually involves lowering it to a 32-bit rotate and fixing up the result, and that's probably a transform which doesn't make sense until legalization.

In D36395#834263, @efriedma wrote:

Also, on x86, it looks like we're missing an important pattern here: we generate the sequence andb $15, %cl; rolw %cl, %ax.

LGTM.

Reopening - the patch was reverted at rL310264 because it caused/exposed failures in test-suite jpeg tests:
https://bugs.llvm.org/show_bug.cgi?id=34097
https://bugs.llvm.org/show_bug.cgi?id=34105

LGTM.

LGTM.

Please add the sext test to this patch. I assume a zext variant already exists - if not, we could use one of those too.
That way we'll be sure that the intended folds are still happening via other mechanisms.

LGTM. I think it makes sense for the same reason as the zext case.

Double-check to make sure, but I think the sext variant isn't handled if we remove this block (sadly, there's no regression test for it):

I pushed 'test7' through llc for x86 and PPC64LE, and no problems. But then I tried AArch64 and ARM, and they went nuts whether it was an 'xor' or an 'and':

In D35182#828396, @craig.topper wrote:

The C code with the global variables never creates a 'not' operation and never combines the 4 compares with 0. For your modified version, it looks like something combined the two compares with A into a single compare and the xor and with this patch instcombine undoes that. Isn't that moving in the opposite direction of PR27431?