Isn't this still missing?

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

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

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.

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.

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.

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.

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?

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

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.