[CodeGen] [SelectionDAG] More efficient code for X % C == 0 (UREM case)

[xbolva00]

Summary

This implements an optimization described in Hacker's Delight 10-17: when C is constant, the result of X % C == 0 can be computed more cheaply without actually calculating the remainder. The motivation is discussed here: https://bugs.llvm.org/show_bug.cgi?id=35479.

Original patch author (Dmytro Shynkevych) Notes:

• In principle, it's possible to also handle the X % C1 == C2 case, as discussed on bugzilla. This seems to require an extra branch on overflow, so I refrained from implementing this for now.
• An explicit check for when the REM can be reduced to just its LHS is included: the X % C == 0 optimization breaks test1 in test/CodeGen/X86/jump_sign.ll otherwise. I hadn't managed to find a better way to not generate worse output in this case.
• I haven't contributed to LLVM before, so I tried to select reviewers based on who I saw in other reviews. In particular, @kparzysz: a Hexagon test is modified and I have no familiarity with the architecture; hopefully my changes are valid.

[hermord]

test/CodeGen/Hexagon/swp-const-tc2.ll

9

To the best of my understanding, it is valid to not perform the multiplication at all, since its can never be used because of the infinite loop at b3. This is the output I get:

// %bb.0:                               // %b0
	{
		r0 = ##-1431655765
	}
	{
		r0 = #0
	}
	{
		r0 = memw(r0+#0)
	}
	.p2align	4
.LBB0_1:                                // %b3
                                        // =>This Inner Loop Header: Depth=1
	{
		jump .LBB0_1
	}

[hermord]

test/CodeGen/Hexagon/swp-const-tc2.ll

9

*its result can never be used

[RKSimon]

include/llvm/CodeGen/TargetLowering.h

3502

Please can you not include the Divisor - we are aiming for full vector support for divisions, not just splats - see D50185

[kparzysz]

test/CodeGen/Hexagon/swp-const-tc2.ll

9

Can you make these changes instead?

-define void @f0() {
+define i32 @f0(i32* %a0) {
 b0:
   br label %b1
 
 b1:                                               ; preds = %b1, %b0
   %v0 = phi i32 [ 0, %b0 ], [ %v9, %b1 ]
   %v1 = phi i32 [ 0, %b0 ], [ %v8, %b1 ]
-  %v2 = load i32, i32* undef, align 4
+  %v2 = load i32, i32* %a0, align 4
   %v3 = add nsw i32 %v1, 1
   %v4 = srem i32 %v2, 3
   %v5 = icmp ne i32 %v4, 0
   %v6 = sub nsw i32 0, %v2
   %v7 = select i1 %v5, i32 %v6, i32 %v2
   %v8 = mul nsw i32 %v3, %v7
   %v9 = add nsw i32 %v0, 1
   %v10 = icmp eq i32 %v9, 1
   br i1 %v10, label %b2, label %b1
 
 b2:                                               ; preds = %b1
   %v11 = phi i32 [ %v8, %b1 ]
   br label %b3
 
 b3:                                               ; preds = %b3, %b2
-  br label %b3
+  ret i32 %v11
 }

[hermord]

Made changes as requested.

[majnemer]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3635

Is this supposed to be ashr even if we are doing UREM? Seems a little unusual but if this is correct, it probably earns a comment.

[hermord]

@majnemer Thanks; this was, in fact, incorrect. Now, to simplify the logic, the absolute value of D is taken and lshr is used.

[lebedev.ri]

In D50222#1188879, @hermord wrote:

@majnemer Thanks; this was, in fact, incorrect. Now, to simplify the logic, the absolute value of D is taken and lshr is used.

There were non-NFC changes to the code, but there was no test changes at all.
I suspect the test coverage is seriously lacking.

[majnemer]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3632–3639

The sign bit may be set for APInts fed into URem operations: all isNegative does is check that the MSB is set. I don't think it is OK to branch on the sign bit here without considering if we are in dealing with URem or SRem. I think what you want is:

if (IsSigned) {
  D0 = D.ashr(K);
} else {
  D0 = D.lshr(K);
}

[hermord]

As pointed out by @lebedev.ri, tests were inadequate. Added new tests and stepped through existing ones, adding descriptions. This uncovered two more bugs, which were also fixed here (an extraneous Q.lshrInPlace() and division by D instead of D0). As far as I can see, the coverage now seems reasonable; please point out any cases I missed.

Regarding @majnemer's suggestion, my bad: I should have mentioned in the last update that this algorithm actually assumes that D is positive ("because d is odd and, as we are assuming, positive and not equal to 1..." [Hacker's Delight, p.227]). It probably can be adapted to the D < 0 case with some tweaks, but it seems easier to just take the absolute value of D since this does not change the answer.

[lebedev.ri]

A few passing-by thoughts.

include/llvm/CodeGen/TargetLowering.h

3502

This should be SmallVectorImpl<SDNode *> &Created like in all the other cases.

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3372–3392

I think this is independent from the rest?
Can you split it into a separate review?

3394–3397

This feels slightly backwards.
Can you do this in DAGCombiner::visitSETCC(), and thus avoid all this use-dance?

18133–18135

Would be good to have a test (in a new file) for that.

18135

Please format your changes with clang-format (you can automate that via git pre-commit hook)

18142

SmallVector<SDNode *, 8> Built;

like in all the other functions.

18143–18145

Early return please.

SDValue NewCond = TLI.BuildREMEqFold(REMNode, CondNode, DAG, Built);

if (!NewCond)
  return SDValue();

18146–18151

Hm. Why is this different from what DAGCombiner::BuildUDIV() does?
I expected to see just the:

for (SDNode *N : Built)
  AddToWorklist(N);
return NewCond;

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

This should be SmallVectorImpl<SDNode *> &Created like in all the other cases.

3631

Separate with newline.

3633–3634

Add self-explanatory assertion?

3645

This is begging to be wrong. Can you create two variables on different lines?

test/CodeGen/Hexagon/swp-const-tc2.ll

36

I think the change to this test can land right away separately from the rest of the changes.

test/CodeGen/X86/rem.ll

81

Why not instead put all this into a new test/CodeGen/X86/rem-seteq.ll file?
I'm not sure whether it is worth it splitting the urem and srem tests into different files though.

[lebedev.ri]

Also, really minor, when adressing/fixing an inline comment, could you please actually mark that inline comment as fixed (via that checkbox), else it really isn't clear in which state which comment is..

[hermord]

Thank you for the review, @lebedev.ri. Sorry for the delay; resolved most of the issues. Quick summary of the changes:

1. BuildREMEqFold is now invoked from SimplifySetCC, as it logically should be. The signature is changed to mirror the other SimplifySetCC helpers.
2. Tests are moved to a separate file. The format is slightly changed to get rid of irrelevant selects. Size optimization tests are added. The Hexagon test fix is split into a separate patch: D50944.
3. The | LHS | < | RHS | optimization (call it (*)) is removed from this patch.

Note: since changes were split into two patches, this now fails tests until D50944 gets merged. Even when that happens, this will still fail test1 in CodeGen/X86/jump_sign because of (*). This failure should probably be fixed by implementing the (*) in a separate patch, but I'm unsure as to the best way to go about it: since BuilREMEqFold moved out of visitREM, it will get invoked before any optimizations in visitREM have had a chance to run, as the SETCC node is processed first. As I see it, there are the following options:

1. Move BuildREMEqFold back into visitREM. This is ugly for other reasons, as @lebedev.ri pointed out, but it does solve this particular hurdle. (*) can then be added right before it.
2. Make (*) a separate function and invoke it in both visitREM and SimplifySetCC (before calling BuildREMEqFold). This may result in it running twice, which is probably bad. Computing KnownBits looks like it's expensive.
3. Check if (*) is possible in SimplifySetCC and, if so, don't touch the node. visitREM then implements the actual optimization.
4. Ignore (*) and implement an equivalent optimization for multiplication on the output of BuildREMEqFold.
5. Accept the probably rare regression (dividend must be known to be smaller than the divisor AND the result has to be fed into a comparison with zero) and edit the test.

I lack experience to make the right call here and would much appreciate any suggestions.

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3633–3634

Sorry, I couldn't figure out what the assertion should be. The negative case can still be handled just fine; do you mean that I should assert (D0 =/= 1) and then make the caller check for that?

[lebedev.ri]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

3372–3392

You could put this fold into the middle-end, into instsimplify, if we don't do it already.
But since it needs computeKnownBits(), some measurements would be needed
(how many times does it fire on some codebase? possibly, measure compile-time impact)

[lebedev.ri]

Some more high-level nits/thoughs:

• Other than -Os, do we always want to do this, for every target, with no customization hook?
• Right now the tests look good (other than the run-line question), please commit them now.
• Similarly, if we want to do it for other arches, also commit a copy of that same rem-seteq.ll test for aarch64 at least.
• I think this should be further split into two reviews, unsigned case first :/

include/llvm/CodeGen/TargetLowering.h

3696

Separate with newline?

lib/CodeGen/SelectionDAG/TargetLowering.cpp

2767–2769

if (SDValue Folded = BuildREMEqFold(VT, N0, N1, Cond, DCI, dl))
  return Folded;

3608–3610

The produced patterns are rather different between unsigned and signed cases.
I think this should be at least done in two steps (two reviews, unsigned first),
and likely these should be done by two separate functions.

test/CodeGen/X86/rem-seteq.ll

2 ↗

(On Diff #161419)

Any reason this is targeting i386 specifically?
I think we should test:

; RUN: llc -mtriple=i686-unknown-linux-gnu                < %s | FileCheck %s --check-prefixes=CHECK,X86
; RUN: llc -mtriple=x86_64-unknown-linux-gnu              < %s | FileCheck %s --check-prefixes=CHECK,X64,NOBMI2
; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+bmi2 < %s | FileCheck %s --check-prefixes=CHECK,X64,BMI2

[hermord]

Thank you for the review, @lebedev.ri, addressed:

• • Added isIntDivCheap as an additional condition preventing this optimization. If this isn't customizable enough, we could probably do something like if (isIntDivCheap || (minsize && isIntDivShort)) where isIntDivShort can be overriden per-target.
• I'm not an LLVM developer; as far as I understand, I can't commit anything
• Added tests for AArch64
• Removed the signed bits

CodeGen/X86/jump_sign.ll still isn't passing; I've been trying different things, but none seem to make for a satisying fix (if I introduce the optimizaion in InstCombine, I'll still have to change the test to pipe through opt, which I'm not sure is better than just chaning the test to match current output). On a related note, after looking at it, should this entire thing be in InstCombine, actually?

[lebedev.ri]

Baseline tests committed, rebase please.

test/CodeGen/X86/urem-seteq.ll

4 ↗

(On Diff #163245)

Actually, looking at the check-lines, i'm not sure we want to check the bmi2 version.
I'm not seeing anything there that would benefit from anything above baseline, i think.

[lebedev.ri]

test/CodeGen/X86/jump_sign.ll

239–244

What do you mean by breaks? Is this a miscompilation?

test/CodeGen/X86/urem-seteq.ll

4 ↗

(On Diff #163245)

I've meant to drop this check-line, but apparently forgot.
I'm not 100% sure if we want/don't want it.

[lebedev.ri]

Starting to look much better. Some more nits.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3608

assert((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
       "Only applicable for [in]equality comparisons.");

3608

// fold (seteq/ne (urem N, D), 0) -> (setule/ugt (rotr (mul N, P), K), Q)

(it would be great to use more descriptive names to differentiate between Constants and not constants, too)

3630

// Decompose D into D0 * 2^K

3631

bool DivisorIsEven = K != 0;

3634–3636

So what we are really checking here, is that D is not power of two.
How about simplifying this into:

APInt D = Divisor->getAPIntValue();
unsigned W = D.getBitWidth();

// If D is power of two, D0 would be 1, and we cannot build this fold.
if(D.isPowerOf2())
  return SDValue();

// Decompose D into D0 * 2^K
...

BUT. I do not understand from where does this requirement comes from?
Can you quote specific part of [[ https://doc.lagout.org/security/Hackers%20Delight.pdf | 10–17 Test for Zero Remainder after Division by a Constant ]] that warrants this?

3638–3642

Would [[ http://llvm.org/doxygen/classllvm_1_1APInt.html#a28ee15b0286415cce5599d4fb9f9ce02 | APInt::multiplicativeInverse() ]] work here?

3645–3646

I would think just writing this as one line would be as clean

APInt Q = APInt::getAllOnesValue(W).udiv(D0);

3652

I do not know if this is needed?
At least rL338079 removed such a call.

3657

if(DivisorIsEven) {

[lebedev.ri]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3608

(it would be great to use more descriptive names to differentiate between Constants and not constants, too)

But thinking about it a bit more, probably don't rename the variables. Consistency [with the orig doc] may be best.

[lebedev.ri]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3627–3636

Well, i see it now - https://rise4fun.com/Alive/aXUu.
Then this should be:

APInt D = Divisor->getAPIntValue();

if(D.isPowerOf2()) {
  // rem by power-of-two is better represented by and-mask.
  return SDValue();
}

// Decompose D into D0 * 2^K
...

3645

Also, move the W here, to the use.

[hermord]

Comments addressed. The minsize condition needs some tweaking, it seems: the code with it works out to actually be longer on X86. Perhaps there should really be something like isIntDivShort.

Re: test1, by it being broken I only mean that it doesn't pass: it's not a miscompilation, just a less optimal output than desired.

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3634–3636

The algorithm also fails in general in this case because the inverse of 1 is 1 itself, and we get, for example:

Given: N: 1, D: 4, C: 0

Then:
K = 2
D0 = 1
P = 1
Q = (2^32 - 1)/1 = 2^32 - 1

And so: (P >>rot 2) == 2^30 < 2^32 - 1 == Q, so the condition holds,
but N % D != 0

The book mentions this in passing: "This can be simplified a little by observing that because d is odd and, as we are assuming, positive and not equal to 1 [...]" (p. 227).

test/CodeGen/X86/jump_sign.ll

239–244

Oh my bad, to clarify: I was referring to test1 in this file and not the one that's changed here. This one is fine, but the code produced for test1 after this patch would be less optimal than before. The output of BuildUREMEqFold just doesn't seem to fall into patterns that we're already optimizing well in this particular case (N is extended from i1, then AND'ed and then passed into an UREM), and we'd probably have to do a new KnownBits-based optimization elsewhere to avoid this. Via InstCombine this can actually be fixed without close to no extra overhead because we are already computing the necessary bits anyway.

[hermord]

Updated AArch64 tests.

[lebedev.ri]

This looks about right as far as i can tell.
But would be best if others could review, too.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3608

The comment change wasn't applied, i'm not aware of gte predicate, but i do know [u/s]ge.
Also, reading the actual code, ugt was meant it seems.

3613

You can move this closer to where it's actually used.

3630

You don't actually modify D as far as i can tell?
I think it should be const APInt &D

3640

Ok, thank you for the explanation regarding D0 != 1.
I think here now we can just add an assert, to document it.

APInt D0 = D.lshr(K);

assert(!D0.isOneValue() && "The fold is invalid for D0 of 1. Unreachable since we leave powers-of-two to be improved elsewhere.");

3655

Drop the comment about signed cases?
I strongly believe that should be done in a new function.

3665

Drop the comment about signed cases?
I strongly believe that should be done in a new function.

[RKSimon]

Please add uniform and non-uniform vector test cases as well.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3623

It should be trivial for you to add non-uniform vector support in this patch, following the patterns I did for the other divsion-by-constant builders.

[xbolva00]

And according to GCC mailing list (https://gcc.gnu.org/ml/gcc-patches/2018-09/msg00193.html) and their stats, unsigned case of X % C1 == C2 is still worth to handle as well.

[xbolva00]

And according to GCC mailing list (https://gcc.gnu.org/ml/gcc-patches/2018-09/msg00193.html) and their stats, unsigned case of X % C1 == C2 is still worth to handle as well.

[lebedev.ri]

In D50222#1221943, @RKSimon wrote:

Please add uniform and non-uniform vector test cases as well.

In D50222#1223180, @xbolva00 wrote:

And according to GCC mailing list (https://gcc.gnu.org/ml/gcc-patches/2018-09/msg00193.html) and their stats, unsigned case of X % C1 == C2 is still worth to handle as well.

@hermord to reiterate, as far i'm concerned, this only needs vector tests.
Everything else should go into new reviews (srem, urem nonsplat, srem nonsplat; non-zero constants (another 4 reviews ideally?)
As for the vector tests, just add them here, i will precommit.
I think, you want to operate on <4 x i32>, with the run line

; RUN: llc -mtriple=x86_64-unknown-linux-gnu -mattr=+sse2 < %s | FileCheck %s --check-prefixes=CHECK,CHECK-SSE2

and

; RUN: llc -mtriple=aarch64-unknown-linux-gnu < %s | FileCheck %s

Just completely duplicate the existing test files with -vector suffix. I.e. if you have

define i32 @test_urem_odd(i32 %X) nounwind readnone {
  %urem = urem i32 %X, 5
  %cmp = icmp eq i32 %urem, 0
  %ret = zext i1 %cmp to i32
  ret i32 %ret
}

It will be

define <4 x i32> @test_urem_odd_vec(<4 x i32> %X) nounwind readnone {
  %urem = urem <4 x i32> %X, <i32 5, i32 5, i32 5, i32 5>
  %cmp = icmp eq <4 x i32> %urem, <i32 0, i32 0, i32 0, i32 0>
  %ret = zext <4 x i1> %cmp to <4 x i32>
  ret <4 x i32> %ret
}

I'm not quite sure about nonsplat tests. things to keep in mind there:

• You have two constants, so add three positive tests with one constant element being undef (i.e. first test with undef in the first constant, second test with undef in the second constant, and a test with undef in both)
• The codepath is different depending on whether the divisor is even. So you want to add a test where half of the divisor is even, and half is odd
• ???

[hermord]

Apologies again for the delay.

• Made cosmetic changes as directed by @lebedev.ri and added vector tests.
• Disabled the fold for vector divisors with even values (see inline comment and test_urem_even_vec_i16).

Nonsplat divisors, nonzero C2 and possibly target customization (something like bool shouldBuildUREMEqFold(SDValue Divisor, SDValue CompTarget, bool isSREM, const DAGCombinerInfo &DCI)?) will be in separate patches.

The splat tests are only partly the same as the scalar ones because bit30/bit31 is not handled any differently in vectors and so is redundant; on the other hand, testing the <4 x i16> case turned out to be valuable (identified the ROTR-induced crash descibed in inline comment).

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3623

I've got conflicting directions for this patch (add nonsplat here or submit it separately), so I didn't touch that part in this update.

3640

This turns out to actually be reachable: the logic that handles REM by powers of two is in visitREM, which is invoked after visitSetCC from where we would've come here. I kept this as an early return if that's OK.

test/CodeGen/X86/jump_sign.ll

410

This is the test1 regression I mentioned in previous updates. I've made it explicit now, for the lack of a clean fix that I can see (without computeKnownBits).

test/CodeGen/X86/urem-seteq.ll

4 ↗

(On Diff #163245)

Should I drop it? On a related note, I could add AVX2 to the vector tests on X86 if that's likely to be useful.

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3633

APInt::lshr returns a value not a reference.

3652

APInt::zext returns a value not a reference.

3657

Again, value not a reference

3664

You must ensure that MUL + ROTR are legal when necessary - pass a IsAfterLegalization flag into the function and check with isOperationLegalOrCustom/isOperationLegal - see TargetLowering::BuildSDIV

test/CodeGen/X86/urem-seteq-vec-nonsplat.ll

2 ↗

(On Diff #164794)

Run with avx2 as well for better test coverage.

6 ↗

(On Diff #164794)

You don't need nonsplat in the test name - its in the filename.

test/CodeGen/X86/urem-seteq-vec-splat.ll

2 ↗

(On Diff #164794)

Run with avx2 as well for better test coverage.

27 ↗

(On Diff #164794)

Use legal types - 8 x i16 etc.

[lebedev.ri]

Updated the tests in rL341953.
As far i'm concerned this is good to go.
Vector and vector non-splat support sounds like a great task for the first follow-up :)
But, still let's wait for others to comment for a bit..

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3640

Sounds good.

test/CodeGen/X86/urem-seteq.ll

4 ↗

(On Diff #163245)

Right, good idea.
I checked all the various sse/avx versions, and kept the unique ones that make a difference here.

[hermord]

Thank you for the review, @RKSimon. Made changes as directed.

[lebedev.ri]

In D50222#1231315, @hermord wrote:

Thank you for the review, @RKSimon. Made changes as directed.

Can you please rebase your differential, so the diff is as compared to the svn?
(i have previously committed the vector tests, but they will need to be recommitted now).

[hermord]

Rebased.

[xbolva00]

Seems fine for trunk now..

[RKSimon]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

Isn't this still missing?

test/CodeGen/X86/urem-seteq-vec-nonsplat.ll

6 ↗

(On Diff #165115)

Please add these test cases back.

test/CodeGen/X86/urem-seteq-vec-splat.ll

6 ↗

(On Diff #165115)

Please add these test cases back.

[hermord]

Re-added previously commited tests.

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

The approach is different now: BuildUREMEqFold is now called from TargetLowering::SimplifySetCC and not from DAGCombiners::visitREM, and l tried to match the style of the other helpers called from there (like simplifySetCCWithAnd).

[hermord]

@RKSimon should I make any other changes to this?

[lebedev.ri]

Hm, i stalled the review here it seems, sorry.
See inline comment.

I think you only updated the splat vector tests to use legal vectors (<8 x i16> instead of <4 x i16>),
but did not update the non-splat test files?
Can you update them too please? I'll then re-commit the tests once more, hopefully the last time :)

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

Looking at the code on which this was originally based, i think i was slightly wrong.
This should still have a pointer to smallvector, and it should push back the newly created SDValues.
And this function should be called from a new helper function that would make proper use of that.

See TargetLowering::BuildSDIVPow2() (which is the implementation), vs DAGCombiner::BuildSDIVPow2() (which is the wrapper).

[lebedev.ri]

Hm, i stalled the review here it seems, sorry.
See inline comment.

I think you only updated the splat vector tests to use legal vectors (<8 x i16> instead of <4 x i16>),
but did not update the non-splat test files?
Can you update them too please? I'll then re-commit the tests once more, hopefully the last time :)

[hermord]

@lebedev.ri Sorry, couldn't find any instances of 4 x i16 in the nonsplat tests; I think I only had those in the splat ones. The patch no longer applied cleanly, so I rebased it again.

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

Ah sorry, just to clarify, there used to be a DAGCombiner::BuildREMEqFold in an earlier version of this patch, but my rationale for removing it was that:

1. We wanted to generate this fold when visiting the SETCC and not the UREM.
2. DAGCombiner::visitSetCC delegates to DAGCombiner::SimplifySetCC, which is just a stub calling TargetLowering::SimplifySetCC.
3. TargetLowering::SimplifySetCC adds nodes to the worklist directly and doesn't return an SDValue vector.

If it's better to mimic BuildSDIVPow2 and have a wrapper, I could:

1. Have TargetLowering::SimplifySetCC call the wrapper from DAGCombiner, at the risk of this being slightly confusing (I don't believe anything else in that function does that?)
2. Remove the call to TargetLowering::BuildUREMEqFold from TargetLowering::SimplifySetCC and add a call to the wrapper instead to DAGCombiner::SimplifySetCC or DAGCombiner::visitSETCC. Currently neither actually contains any case-specific simplification logic, so I'm not sure if I should change that.

[lebedev.ri]

In D50222#1244716, @hermord wrote:

@lebedev.ri Sorry, couldn't find any instances of 4 x i16 in the nonsplat tests; I think I only had those in the splat ones.

Hm, could be. I don't see them either now.

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

This current BuildUREMEqFold() does not adds nodes to the worklist directly as far as i can see?

Well, i had the third variant in mind.

1. Rename this function to something like BuildUREMEqFold_REAL() (bad name, just an example)
2. Add a new wrapper BuildUREMEqFold() here in this file, right after BuildUREMEqFold_REAL().

So nothing changes for the callers.
And the wrapper will do all that stuff about receiving the vector of newly created SDNodes,
and adding them to the worklist.

[hermord]

Made a wrapper as dicussed.

[hermord]

lib/CodeGen/SelectionDAG/TargetLowering.cpp

3606

It doesn't right now, this is true. I removed it following this comment:

Comment at: lib/CodeGen/SelectionDAG/TargetLowering.cpp:3771
+  SDValue Op1 = DAG.getNode(ISD::MUL, DL, REMVT, REMNode->getOperand(0), PVal);
+  DCI.AddToWorklist(Op1.getNode());
+  // Will change in the signed case
----------------
I do not know if this is needed?
At least rL338079 removed such a call.

Looking back at rL338079, it doesn't say that AddToWorklist is never necessary in this context, and similar code (BuildUDIV) does do it, so I removing it might have been premature.

I took a stab at the third variant in the latest diff.

[xbolva00]

Any futher blockers here?

[RKSimon]

test/CodeGen/AArch64/urem-seteq-vec-nonsplat.ll

6 ↗

(On Diff #167025)

You can commit the nonsplat test name changes as an NFC now to reduce this patch.

test/CodeGen/X86/jump_sign.ll

410

Have you made any progress working out what the problems is with test1?

test/CodeGen/X86/urem-seteq-vec-nonsplat.ll

10 ↗

(On Diff #167025)

You can commit the nonsplat test name changes as an NFC now to reduce this patch.

test/CodeGen/X86/urem-seteq-vec-splat.ll

66 ↗

(On Diff #167025)

These <4 x i16> -> <8 x i16> test changes need to be done as an NFC commit, showing the current codegen and then this patch rebased. Its up to you if you keep the aarch64 using <4 x i16> or not but the x86 versions need to be changed to a legal type.

[RKSimon]

@hermord Are you still looking at this?

[xbolva00]

Btw, why we do not this transformation on IR-level at first?

[RKSimon]

@hermord Do you mind if I commandeer this to get it finished please?

[hermord]

@RKSimon I am sorry for the long radio silence. It is entirely my fault.

Regarding test1, the problem seems to be that once this fold is applied, producing something of the form (setule (mul t, -85), 85), it is difficult to deduce that this is the same as (seteq t, 0) in this case. In what was produced before, (seteq (sub t, (mul ...)), 0), a series of optimizations could figure out that the mul node is always zero.

This can be worked around in InstCombine without any additional KnownBits computations beyond what already happens. I'd looked into implementing a fix there before (mentioned in dicussion with @lebedev.ri) and could replicate it, but this will require running opt on jump_sign.ll to restore previous behavior.

I do not have commit rights, so I cannot enact the suggestion to commit the tests as NFC, but I can implement the above (or any other) approach for test1 now, if required, to finalize the patch. I feel like this is very close to completion, but if this is not acceptable, please feel free to commandeer the patch.

[xbolva00]

Ok, so create new revision with tests? Somebody will commit it for you.

[hermord]

Rebased on top of D56372.

[RKSimon]

@hermord reverse ping

[gnudles]

Hi guys, I found the magical formula for unsigned integers that works also with even numbers without the need to check for overflows with any remainder:
from divisor d and reminder r, I calculate 4 constants.
any d!=0 should fit.

void calculate_constants64(uint64_t d, uint64_t r, uint64_t &k,uint64_t &mmi, uint64_t &s,uint64_t& u)
{
	k=__builtin_ctzll(d);/* the power of 2 */
	uint64_t d_odd=d>>k;
	mmi=find_mod_mul_inverse(d_odd,64);
	/* 64 is word size*/
	s=(r*mmi);
	u=(ULLONG_MAX-r)/d;/* note that I divide by d, not d_odd */
}

A little bit background: the constant (u +1) is the count of the possible values in the range of 64 bit number that will yield the correct modulo.
The constant s should zero the first k bits if the given value have modulo of r. it will also zero the modulo of d_odd.

then the compiler should generate the following code with the given constants:

int checkrem64(uint64_t k,uint64_t mmi, uint64_t s,uint64_t u,uint64_t x)
{
    uint64_t o=((x*mmi)-s);
    o= (o>>k)|(o<<(64-k));/*ROTR64(o,k)*/
    return o<=u;
}

this replace the following:

/* d is the divisor, r is the remainder */
int checkrem64(uint64_t x)
{
  return x%d==r;
}

this is the code to find modular inverse..

uint64_t find_mod_mul_inverse(uint64_t x, uint64_t bits)
{
      if (bits > 64 || ((x&1)==0))
              return 0;// invalid parameters
      uint64_t mask;
      if (bits == 64)
              mask = -1;
      else
      {                
              mask = 1;
              mask<<=bits;
              mask--;
      }
      x&=mask;
      uint64_t result=1, state=x, ctz=0;
      while(state!=1ULL)
      {
              ctz=__builtin_ctzll(state^1);
              result|=1ULL<<ctz;
              state+=x<<ctz;
              state&=mask;
      }
      return result;
}

good luck!
I tested this on all the cases of 10bit word size, and it passed.

*Edit:* I looked for something that will work for signed integers. I came up with something that would work with negative numbers if the following assumption was correct:

(-21)%10==9

but this assumption is not correct because (-21)%10 equals to -1.
anyway, the idea is like that, you shift the range and change s and accordingly:

void calculate_constants64(uint64_t d, uint64_t r, uint64_t &k,uint64_t &mmi, uint64_t &s,uint64_t& u)
{
	k=__builtin_ctzll(d);/* the power of 2 */
	uint64_t d_odd=d>>k;
	mmi=find_mod_mul_inverse(d_odd,64);
	/* 64 is word size*/
     //this is the added line to make it work with signed integers
      r+=0x8000 0000 0000 0000% d;
	s=(r*mmi);
	u=(ULLONG_MAX-r)/d;
}

int checkrem64(uint64_t k,uint64_t mmi, uint64_t s,uint64_t u,uint64_t x)
{
     //this is the added line to make it work with signed integers
//x came as signed number but was casted to unsigned
    x^=0x8000 0000 0000 0000;// this is addition simplified to xor, spaces for clarity.
    uint64_t o=((x*mmi)-s);
    o= (o>>k)|(o<<(64-k));/*ROTR64(o,k)*/
    return o<=u;
}

but there must be a way to tweak u and s to make it work on negative only numbers or positive only numbers.... it should be easy...
Can someone please contact me to do the math?
I need a background and explanation how the folding of unsigned numbers should act and then I will try to find for you the formula... [e-mail]
@jdoerfert, please read this carefully, cause you did not calculated correctly the Q constant when D is even. that is why it did not worked for you when D was 4, and it will also not work for you when D is 6 or 10 etc.

[xbolva00]

Rebased. Moved to DAGCombiner and fixed regression in jump_sign.ll.

[xbolva00]

Oh, no. Still there :((

[lebedev.ri]

Hmm, i don't see the button to take the review,
so i had to post a new one: D63391
The test/CodeGen/X86/jump_sign.ll regression is rather trivial, and is being fixed by a followup patch D63390.

include/llvm/CodeGen/TargetLowering.h

public:
   //
   SDValue BuildSDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
                     bool IsAfterLegalization,
                     SmallVectorImpl<SDNode *> &Created) const;
   SDValue BuildUDIV(SDNode *N, const APInt &Divisor, SelectionDAG &DAG,
                     bool IsAfterLegalization,
                     SmallVectorImpl<SDNode *> &Created) const;
 
+  //===--------------------------------------------------------------------===//
+  // REM equality fold
+  //
+  SDValue BuildREMEqFold(SDNode *N, SDNode *CondNode,
+                         const APInt &Divisor, SelectionDAG &DAG,
+                         std::vector<SDNode *> &Created) const;
+
   /// Targets may override this function to provide custom SDIV lowering for
   /// power-of-2 denominators.  If the target returns an empty SDValue, LLVM
   /// assumes SDIV is expensive and replaces it with a series of other integer
   /// operations.
   virtual SDValue BuildSDIVPow2(SDNode *N, const APInt &Divisor,
                                 SelectionDAG &DAG,
                                 SmallVectorImpl<SDNode *> &Created) const;
 
private:
   SDValue simplifySetCCWithAnd(EVT VT, SDValue N0, SDValue N1,
                                ISD::CondCode Cond, DAGCombinerInfo &DCI,
                                const SDLoc &DL) const;
 
   SDValue optimizeSetCCOfSignedTruncationCheck(EVT SCCVT, SDValue N0,
                                                SDValue N1, ISD::CondCode Cond,
                                                DAGCombinerInfo &DCI,
                                                const SDLoc &DL) const;
 };
 
 /// Given an LLVM IR type and return type attributes, compute the return value
 /// EVTs and flags, and optionally also the offsets, if the return value is
 /// being lowered to memory.
 void GetReturnInfo(CallingConv::ID CC, Type *ReturnType, AttributeList attr,
                    SmallVectorImpl<ISD::OutputArg> &Outs,
                    const TargetLowering &TLI, const DataLayout &DL);
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_TARGETLOWERING_H

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue CombineExtLoad(SDNode *N);
     SDValue CombineZExtLogicopShiftLoad(SDNode *N);
     SDValue combineRepeatedFPDivisors(SDNode *N);
     SDValue combineInsertEltToShuffle(SDNode *N, unsigned InsIndex);
     SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
     SDValue BuildSDIV(SDNode *N);
     SDValue BuildSDIVPow2(SDNode *N);
     SDValue BuildUDIV(SDNode *N);
+    SDValue BuildREMEqFold(SDNode *REMNode, SDNode *CondNode);
     SDValue BuildLogBase2(SDValue V, const SDLoc &DL);
     SDValue BuildReciprocalEstimate(SDValue Op, SDNodeFlags Flags);
     SDValue buildRsqrtEstimate(SDValue Op, SDNodeFlags Flags);
     SDValue buildSqrtEstimate(SDValue Op, SDNodeFlags Flags);
     SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
     SDValue buildSqrtNROneConst(SDValue Arg, SDValue Est, unsigned Iterations,
                                 SDNodeFlags Flags, bool Reciprocal);
     SDValue buildSqrtNRTwoConst(SDValue Arg, SDValue Est, unsigned Iterations,
if (N1.getOpcode() == ISD::SHL &&
         DAG.isKnownToBeAPowerOfTwo(N1.getOperand(0))) {
       // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
       SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N1, NegOne);
       AddToWorklist(Add.getNode());
       return DAG.getNode(ISD::AND, DL, VT, N0, Add);
     }
   }
 
+  // fold (rem lhs, rhs) -> lhs when |lhs| < |rhs|
+  // FIXME: this optimization is otherwise missed if BuildREMEqFold succeeds.
+  // Ref: test1 in test/CodeGen/X86/jump_sign.ll
+  if (N1C) {
+    KnownBits LHSBits;
+    DAG.computeKnownBits(N0, LHSBits);
+    LHSBits.makeNonNegative();
+    unsigned TypeWidth = N0.getValueSizeInBits();
+    unsigned LeadingZeros = LHSBits.countMinLeadingZeros();
+    APInt N1Value = N1C->getAPIntValue();
+    // If the possibly nonzero part of LHS is wider than RHS,
+    // we cannot conclude |LHS| < |RHS|
+    if (TypeWidth - LeadingZeros < N1Value.getBitWidth()) {
+      APInt LHSMaxValue(N1Value.getBitWidth(), 0);
+      LHSMaxValue.setLowBits(TypeWidth - LeadingZeros);
+      N1Value.clearSignBit();
+      // If |LHS| < |RHS|, the remainder is just LHS.
+      if (LHSMaxValue.ult(N1Value))
+        return N0;
+    }
+  }
+
+  if (N->hasOneUse() && N->use_begin()->getOpcode() == ISD::SETCC) {
+    if (SDValue Folded = BuildREMEqFold(N, *N->use_begin()))
+      return Folded;
+  }
+
   AttributeList Attr = DAG.getMachineFunction().getFunction().getAttributes();
 
   // If X/C can be simplified by the division-by-constant logic, lower
   // X%C to the equivalent of X-X/C*C.
   // Reuse the SDIVLike/UDIVLike combines - to avoid mangling nodes, the
   // speculative DIV must not cause a DIVREM conversion.  We guard against this
   // by skipping the simplification if isIntDivCheap().  When div is not cheap,
   // combine will not return a DIVREM.  Regardless, checking cheapness here
SDValue DAGCombiner::BuildSDIVPow2(SDNode *N) {
   SmallVector<SDNode *, 8> Built;
   SDValue S = TLI.BuildSDIVPow2(N, C->getAPIntValue(), DAG, Built);
 
   for (SDNode *N : Built)
     AddToWorklist(N);
   return S;
 }
 
+/// Given an ISD::UREM or ISD::SREM used only by an ISD::SETEQ or ISD::SETNE
+/// where the divisor is constant and the comparison target is zero,
+/// return a DAG expression that will generate the same comparison result
+/// using only multiplications, additions and shifts/rotations.
+/// Ref: "Hacker's Delight" 10-17.
+SDValue DAGCombiner::BuildREMEqFold(SDNode *REMNode, SDNode *CondNode) {
+  // UREM/SREM will be shorter than any other path we take here
+  if (DAG.getMachineFunction().getFunction().optForMinSize())
+      return SDValue();
+
+  ConstantSDNode *N1C = isConstOrConstSplat(REMNode->getOperand(1));
+  ConstantSDNode *C = isConstOrConstSplat(CondNode->getOperand(1));
+  // Divisor and comparison target must be constant
+  if (!N1C || !C)
+    return SDValue();
+
+  // Divisor must be non-zero, comparison target must be zero
+  if (N1C->isNullValue() || !C->isNullValue())
+    return SDValue();
+
+  SDValue CondCodeNode = CondNode->getOperand(2);
+  ISD::CondCode CondCode = cast<CondCodeSDNode>(CondCodeNode)->get();
+  if (CondCode != ISD::SETEQ && CondCode != ISD::SETNE)
+    return SDValue();
+
+  std::vector<SDNode *> Built;
+  SDValue NewCond = TLI.BuildREMEqFold(REMNode, CondNode,
+                                       N1C->getAPIntValue(), DAG, Built);
+
+  if (NewCond) {
+    SDNode *Last = Built.back();
+    for (SDNode *N : Built)
+      AddToWorklist(N);
+    AddToWorklist(NewCond.getNode());
+    DAG.ReplaceAllUsesWith(SDValue(CondNode, 0), NewCond);
+    return SDValue(Last, 0);
+  }
+
+  return SDValue();
+}
+
 /// Given an ISD::UDIV node expressing a divide by constant, return a DAG
 /// expression that will generate the same value by multiplying by a magic
 /// number.
 /// Ref: "Hacker's Delight" or "The PowerPC Compiler Writer's Guide".
 SDValue DAGCombiner::BuildUDIV(SDNode *N) {
   // when optimising for minimum size, we don't want to expand a div to a mul
   // and a shift.
   if (DAG.getMachineFunction().getFunction().optForMinSize())

lib/CodeGen/SelectionDAG/TargetLowering.cpp

if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 
     if (SDValue V = simplifySetCCWithAnd(VT, N0, N1, Cond, DCI, dl))
       return V;
   }
 
   // Fold away ALL boolean setcc's.
   SDValue Temp;
   if (N0.getValueType().getScalarType() == MVT::i1 && foldBooleans) {
     EVT OpVT = N0.getValueType();
     switch (Cond) {
     default: llvm_unreachable("Unknown integer setcc!");
     case ISD::SETEQ:  // X == Y  -> ~(X^Y)
       Temp = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
       N0 = DAG.getNOT(dl, Temp, OpVT);
       if (!DCI.isCalledByLegalizer())
         DCI.AddToWorklist(Temp.getNode());
       break;
     case ISD::SETNE:  // X != Y   -->  (X^Y)
       N0 = DAG.getNode(ISD::XOR, dl, OpVT, N0, N1);
if (magics.a == 0) {
     Created.push_back(NPQ.getNode());
     return DAG.getNode(
         ISD::SRL, dl, VT, NPQ,
         DAG.getConstant(magics.s - 1, dl,
                         getShiftAmountTy(NPQ.getValueType(), DL)));
   }
 }
 
+/// Given an ISD::UREM or ISD::SREM used only by an ISD::SETEQ or ISD::SETNE
+/// where the divisor is constant and the comparison target is zero,
+/// return a DAG expression that will generate the same comparison result
+/// using only multiplications, additions and shifts/rotations.
+/// Ref: "Hacker's Delight" 10-17.
+SDValue TargetLowering::BuildREMEqFold(SDNode *REMNode, SDNode *CondNode,
+                                       const APInt &D, SelectionDAG &DAG,
+                                       std::vector<SDNode *> &Created) const {
+  // fold (seteq/ne (urem N, D), 0) -> (setule/gte (rotr (mul N, P), K), Q)
+  // fold (seteq/ne (srem N, D), 0)
+  //          -> (setule/gte (rotr (add (mul N, P), Q''), K), (srl Q', K-1))
+  // - D must be constant with D = D0 * 2^K where D0 is odd
+  // - P is the multiplicative inverse of D0 modulo 2^W
+  // - Q = floor((2^W - 1) / D0)
+  // - Q' = floor((2^(W - 1) - 1) / D0)
+  // - Q'' = Q' & -2^K
+  // where W is the width of the common type of N and D
+  EVT REMVT = REMNode->getValueType(0);
+  EVT CondVT = CondNode->getValueType(0);
+  SDLoc DL(REMNode);
+  bool IsEq =
+      cast<CondCodeSDNode>(CondNode->getOperand(2))->get() == ISD::SETEQ;
+  bool IsSigned = (REMNode->getOpcode() == ISD::SREM);
+
+  if (!isTypeLegal(REMVT))
+    return SDValue();
+
+  // Rewrite D = D0 * 2^K
+  unsigned K = D.countTrailingZeros();
+  APInt D0 = D.ashr(K);
+
+  // Calculate the multiplicative inverse of D0 using Newton's method.
+  APInt tmp, P = D0;
+  while ((tmp = D0*P) != 1)
+    P *= APInt(D0.getBitWidth(), 2) - tmp;
+
+  // Q = floor((2^W - 1) / D)
+  APInt Q = APInt::getAllOnesValue(D.getBitWidth());
+  if (IsSigned)
+    Q.clearBit(D.getBitWidth());
+  Q = Q.udiv(D);
+  if (IsSigned) {
+    Q.ashrInPlace(1);
+    // Q'' = Q' & -2^K
+    APInt Neg2K = APInt(D.getBitWidth(), 0);
+    Neg2K.setHighBits(D.getBitWidth() - K);
+    Q &= Neg2K;
+  }
+
+  SDValue PVal = DAG.getConstant(P, DL, REMVT);
+  SDValue QVal = DAG.getConstant(Q, DL, REMVT);
+  // (mul N, P)
+  SDValue Op1 = DAG.getNode(ISD::MUL, DL, REMVT, REMNode->getOperand(0), PVal);
+  Created.push_back(Op1.getNode());
+  // Will change in the signed case
+  SDValue Op2 = QVal;
+
+  if (IsSigned) {
+    // (add (mul N, P), Q')
+    Op1 = DAG.getNode(ISD::ADD, DL, REMVT, Op1, QVal);
+    Created.push_back(Op1.getNode());
+  }
+
+  // Rotate right only if D was even and thus shifted (K > 0)
+  if (K) {
+    SDValue ShAmt =
+        DAG.getConstant(K, DL, getShiftAmountTy(REMVT, DAG.getDataLayout()));
+    SDNodeFlags Flags;
+    Flags.setExact(true);
+    // UREM: (rotr (mul N, P), K)
+    // SREM: (rotr (add (mul N, P), Q'), K)
+    Op1 = DAG.getNode(ISD::ROTR, DL, REMVT, Op1, ShAmt, Flags);
+    Created.push_back(Op1.getNode());
+  }
+
+  // Don't insert a useless node if K - 1 == 0
+  if (IsSigned && K != 1) {
+    if (K != 0)
+      Op2 = DAG.getConstant(Q.ashr(K - 1), DL, REMVT);
+    else
+      Op2 = DAG.getConstant(Q.shl(1), DL, REMVT);
+  }
+
+  // UREM: (setule/setugt (rotr (mul N, P), K), Q)
+  // SREM: (setule/setugt (rotr (add (mul N, P), Q''), K), (srl Q', K-1))
+  Op1 = DAG.getSetCC(DL, CondVT, Op1, Op2, (IsEq ? ISD::SETULE : ISD::SETUGT));
+  return Op1;
+}
+
 bool TargetLowering::
 verifyReturnAddressArgumentIsConstant(SDValue Op, SelectionDAG &DAG) const {
   if (!isa<ConstantSDNode>(Op.getOperand(0))) {
     DAG.getContext()->emitError("argument to '__builtin_return_address' must "
                                 "be a constant integer");
     return true;
   }
 

test/CodeGen/Hexagon/swp-const-tc2.ll

 ; RUN: llc -march=hexagon -rdf-opt=0 < %s | FileCheck %s
 
 ; Test that we fixup a pipelined loop correctly when the number of
 ; stages is greater than the compile-time loop trip count. In this
 ; test, there are two prolog stages, but the loop executes only once.
 ; In the bug, the final CFG contains two iterations of the loop.
 
 ; CHECK-NOT: loop0
-; CHECK: = mpy
-; CHECK-NOT: = mpy
+; CHECK: = memw
+; CHECK-NOT: = memw
 
 define void @f0() {
 b0:
   br label %b1
 
 b1:                                               ; preds = %b1, %b0
   %v0 = phi i32 [ 0, %b0 ], [ %v9, %b1 ]
   %v1 = phi i32 [ 0, %b0 ], [ %v8, %b1 ]
b1:                                               ; preds = %b1, %b0
   br i1 %v10, label %b2, label %b1
 
 b2:                                               ; preds = %b1
   %v11 = phi i32 [ %v8, %b1 ]
   br label %b3
 
 b3:                                               ; preds = %b3, %b2
   br label %b3
 }

test/CodeGen/X86/jump_sign.ll

 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB12_5
 ; CHECK-NEXT:  # %bb.3: # %sw.bb
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB12_8
 ; CHECK-NEXT:  # %bb.4: # %if.end29
 ; CHECK-NEXT:    movzwl (%eax), %eax
-; CHECK-NEXT:    movzwl %ax, %eax
-; CHECK-NEXT:    imull $52429, %eax, %ecx # imm = 0xCCCD
-; CHECK-NEXT:    shrl $19, %ecx
-; CHECK-NEXT:    addl %ecx, %ecx
-; CHECK-NEXT:    leal (%ecx,%ecx,4), %ecx
-; CHECK-NEXT:    cmpw %cx, %ax
-; CHECK-NEXT:    jne .LBB12_5
+; CHECK-NEXT:    imull $-13107, %eax, %eax # imm = 0xCCCD
+; CHECK-NEXT:    rorw $1, %ax
+; CHECK-NEXT:    movzwl %ax, %eax
+; CHECK-NEXT:    cmpl $6554, %eax
+; CHECK-NEXT:    jae  .LBB12_5
 ; CHECK-NEXT:  .LBB12_8: # %if.then44
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB12_9
 ; CHECK-NEXT:  # %bb.10: # %if.else.i104
 ; CHECK-NEXT:    retl
 ; CHECK-NEXT:  .LBB12_5: # %sw.default
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al

 ; CHECK-NEXT:    movl a, %eax
 ; CHECK-NEXT:    testb %al, %cl
 ; CHECK-NEXT:    je .LBB18_2
 ; CHECK-NEXT:  # %bb.1: # %if.then
 ; CHECK-NEXT:    decl %eax
 ; CHECK-NEXT:    movl %eax, a
 ; CHECK-NEXT:  .LBB18_2: # %if.end
 ; CHECK-NEXT:    retl
 entry:
   %t0 = load i32, i32* @b, align 4
   %cmp = icmp ult i32 %t0, %p1
   %conv = zext i1 %cmp to i32
   %t1 = load i32, i32* @a, align 4
   %and = and i32 %conv, %t1
   %conv1 = trunc i32 %and to i8
   %t2 = urem i8 %conv1, 3
   %tobool = icmp eq i8 %t2, 0

test/CodeGen/X86/rem.ll

 ; CHECK-NEXT:    idivl {{[0-9]+}}(%esp)
 ; CHECK-NEXT:    movl %edx, %eax
 ; CHECK-NEXT:    retl
 entry:
   %0 = srem i32 41, %X
   ret i32 %0
 }
 
+define i32 @test6(i32 %X) nounwind readnone {
+; CHECK-LABEL: test6:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    imull $-858993459, {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    cmpl $858993460, %eax
+; CHECK-NEXT:    movl $42, %eax
+; CHECK-NEXT:    jb [[LOC:\.LBB[0-9]+_[0-9]+]]
+; CHECK-NEXT:  # %bb.1: # %entry
+; CHECK-NEXT:    movl $-10, %eax
+; CHECK-NEXT:  [[LOC]]: # %entry
+; CHECK-NEXT:    retl
+
+entry:
+  %0 = urem i32 %X, 5
+  %cmp = icmp eq i32 %0, 0
+  %ret = select i1 %cmp, i32 42, i32 -10
+  ret i32 %ret
+}
+
+define i16 @test7(i16 %X) nounwind readnone {
+; CHECK-LABEL: test7:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    imull $28087, {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    rorw $1, %ax
+; CHECK-NEXT:    movzwl %ax, %eax
+; CHECK-NEXT:    cmpl $4681, %eax
+; CHECK-NEXT:    movl $42, %eax
+; CHECK-NEXT:    ja [[LOC:\.LBB[0-9]+_[0-9]+]]
+; CHECK-NEXT:  # %bb.1: # %entry
+; CHECK-NEXT:    movl $65526, %eax
+; CHECK-NEXT:  [[LOC]]: # %entry
+; CHECK-NEXT:  # kill: {{.*}}
+; CHECK-NEXT:    retl
+
+entry:
+  %0 = urem i16 %X, 14
+  %cmp = icmp ne i16 %0, 0
+  %ret = select i1 %cmp, i16 42, i16 -10
+  ret i16 %ret
+}
+
+define i32 @test8(i32 %X) nounwind readnone {
+; CHECK-LABEL: test8:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    imull $-1108378657, {{[0-9]+}}(%esp), %eax
+; CHECK-NEXT:    addl $69273666, %eax
+; CHECK-NEXT:    cmpl $138547333, %eax
+; CHECK-NEXT:    movl $42, %eax
+; CHECK-NEXT:    jb [[LOC:\.LBB[0-9]+_[0-9]+]]
+; CHECK-NEXT:  # %bb.1: # %entry
+; CHECK-NEXT:    movl $-10, %eax
+; CHECK-NEXT:  [[LOC]]: # %entry
+; CHECK-NEXT:    retl
+
+entry:
+  %0 = srem i32 %X, 31
+  %cmp = icmp eq i32 %0, 0
+  %ret = select i1 %cmp, i32 42, i32 -10
+  ret i32 %ret
+}
+
+define i8 @test9(i8 %X) nounwind readnone {
+; CHECK-LABEL: test9:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    movb {{[0-9]+}}(%esp), %al
+; CHECK-NEXT:    movb $-85, %cl
+; CHECK-NEXT:    mulb %cl
+; CHECK-NEXT:    addb $8, %al
+; CHECK-NEXT:    rorb $2, %al
+; CHECK-NEXT:    cmpb $4, %al
+; CHECK-NEXT:    movb $42, %al
+; CHECK-NEXT:    ja [[LOC:\.LBB[0-9]+_[0-9]+]]
+; CHECK-NEXT:  # %bb.1: # %entry
+; CHECK-NEXT:    movb $-10, %al
+; CHECK-NEXT:  [[LOC]]: # %entry
+; CHECK-NEXT:    retl
+
+entry:
+  %0 = srem i8 %X, 12
+  %cmp = icmp ne i8 %0, 0
+  %ret = select i1 %cmp, i8 42, i8 -10
+  ret i8 %ret
+}
+

test/CodeGen/X86/vselect-avx.ll

 ;
 ; Make sure that the and is fed by the original mask.
 ;
 ; <rdar://problem/18819506>
 
 define void @test3(<4 x i32> %induction30, <4 x i16>* %tmp16, <4 x i16>* %tmp17,  <4 x i16> %tmp3, <4 x i16> %tmp12) {
 ; AVX1-LABEL: test3:
 ; AVX1:       ## %bb.0:
-; AVX1-NEXT:    vpshufd {{.*#+}} xmm3 = xmm0[1,1,3,3]
-; AVX1-NEXT:    vmovdqa {{.*#+}} xmm4 = [1431655766,1431655766,1431655766,1431655766]
-; AVX1-NEXT:    vpmuldq %xmm4, %xmm3, %xmm3
-; AVX1-NEXT:    vpmuldq %xmm4, %xmm0, %xmm4
-; AVX1-NEXT:    vpshufd {{.*#+}} xmm4 = xmm4[1,1,3,3]
-; AVX1-NEXT:    vpblendw {{.*#+}} xmm3 = xmm4[0,1],xmm3[2,3],xmm4[4,5],xmm3[6,7]
-; AVX1-NEXT:    vpsrld $31, %xmm3, %xmm4
-; AVX1-NEXT:    vpaddd %xmm4, %xmm3, %xmm3
-; AVX1-NEXT:    vpmulld {{.*}}(%rip), %xmm3, %xmm3
-; AVX1-NEXT:    vpsubd %xmm3, %xmm0, %xmm0
-; AVX1-NEXT:    vpxor %xmm3, %xmm3, %xmm3
+; AVX1-NEXT:    vpmulld LCPI{{.*}}(%rip), %xmm0, %xmm0
+; AVX1-NEXT:    vpaddd LCPI{{.*}}(%rip), %xmm0, %xmm0
+; AVX1-NEXT:    vpminud LCPI{{.*}}(%rip), %xmm0, %xmm3
 ; AVX1-NEXT:    vpcmpeqd %xmm3, %xmm0, %xmm0
 ; AVX1-NEXT:    vblendvps %xmm0, %xmm1, %xmm2, %xmm1
 ; AVX1-NEXT:    vpackssdw %xmm0, %xmm0, %xmm0
 ; AVX1-NEXT:    vmovq %xmm0, (%rdi)
 ; AVX1-NEXT:    vpshufb {{.*#+}} xmm0 = xmm1[0,1,4,5,8,9,12,13,8,9,12,13,12,13,14,15]
 ; AVX1-NEXT:    vmovq %xmm0, (%rsi)
 ; AVX1-NEXT:    retq
 ;
 ; AVX2-LABEL: test3:
 ; AVX2:       ## %bb.0:
-; AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm3 = [1431655766,1431655766,1431655766,1431655766]
-; AVX2-NEXT:    vpshufd {{.*#+}} xmm4 = xmm3[1,1,3,3]
-; AVX2-NEXT:    vpshufd {{.*#+}} xmm5 = xmm0[1,1,3,3]
-; AVX2-NEXT:    vpmuldq %xmm4, %xmm5, %xmm4
-; AVX2-NEXT:    vpmuldq %xmm3, %xmm0, %xmm3
-; AVX2-NEXT:    vpshufd {{.*#+}} xmm3 = xmm3[1,1,3,3]
-; AVX2-NEXT:    vpblendd {{.*#+}} xmm3 = xmm3[0],xmm4[1],xmm3[2],xmm4[3]
-; AVX2-NEXT:    vpsrld $31, %xmm3, %xmm4
-; AVX2-NEXT:    vpaddd %xmm4, %xmm3, %xmm3
-; AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm4 = [3,3,3,3]
-; AVX2-NEXT:    vpmulld %xmm4, %xmm3, %xmm3
-; AVX2-NEXT:    vpsubd %xmm3, %xmm0, %xmm0
-; AVX2-NEXT:    vpxor %xmm3, %xmm3, %xmm3
+; AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm3 = [2863311531,2863311531,2863311531,2863311531]
+; AVX2-NEXT:    vpmulld %xmm3, %xmm0, %xmm0
+; AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm3 = [715827882,715827882,715827882,715827882]
+; AVX2-NEXT:    vpaddd %xmm3, %xmm0, %xmm0
+; AVX2-NEXT:    vpbroadcastd {{.*#+}} xmm3 = [1431655764,1431655764,1431655764,1431655764]
+; AVX2-NEXT:    vpminud %xmm3, %xmm0, %xmm3
 ; AVX2-NEXT:    vpcmpeqd %xmm3, %xmm0, %xmm0
 ; AVX2-NEXT:    vblendvps %xmm0, %xmm1, %xmm2, %xmm1
 ; AVX2-NEXT:    vpackssdw %xmm0, %xmm0, %xmm0
 ; AVX2-NEXT:    vmovq %xmm0, (%rdi)
 ; AVX2-NEXT:    vpshufb {{.*#+}} xmm0 = xmm1[0,1,4,5,8,9,12,13,8,9,12,13,12,13,14,15]
 ; AVX2-NEXT:    vmovq %xmm0, (%rsi)
 ; AVX2-NEXT:    retq
   %tmp6 = srem <4 x i32> %induction30, <i32 3, i32 3, i32 3, i32 3>