Yeah, this one is a bug in updating of the coefficients.

Check both ends of the range in getNumIterationsInRange, change comment for SolveQuadraticEquation.

I can change the comment to something like "returns the smallest positive x such that q(x-1) and q(x) belong to different intervals in the form of [k*2^BW, (k+1)*2^BW)".

In D48283#1167248, @efriedma wrote:

The current getNumIterationsInRange implementation is consistent with "equals 0 or wraps around 2^BW in the unsigned modulo 2^BW arithmetic" (but that's not what SolveQuadraticEquation actually computes at the moment).

We may need to guard this code with some extra checks (to verify that we have merged a non-undef value with an undef one), to avoid doing this unnecessarily, but I don't think there is a much simpler way to handle it.

Well, for one 2/2 seems to be -1...

Addressed the comments.

Why do you need this? Do you have MCInsts with operands that are not encoded?

The setcc type can be addressed later. This looks good to me.

At the moment D49242 expands these intrinsics into individual DAG operations. If the intrinsics were transformed into ROTL, and if instcombine could reassociate "or" operations to expose more fshl opportunities, then I guess it would be sufficient.

Rebased on top of trunk.

Ping.

Ping.

Sorry for the delay in reviewing. Yes, I think it's ok for now. At some point I will probably revisit this to try to generate better diagnostics, but this change is fine now.

Here's how the problem happens:

Ping.

1. Added solving for arbitrary overflow, i.e. q(x) = 2^n for n \in Z-{0}, (or mod 2^n).
2. Expanded comments.
3. Added more testcases (incl. from PR38024).

We do. Fixed in r336134.

In D26359#1147318, @scott.linder wrote:

I did not understand the undef register flag. Is there somewhere I can read more about MIR, or is the code the best place? https://llvm.org/docs/MIRLangRef.html is currently a little short on specifics.

I'm assuming that the line 10000B was misplaced in the snippet above, and should be in bb.2.

Ping.

I'm not sure if this patch needs any more work, it worked fine when I posted it (at least in my tests). Since it's been a while ago, it would be worthwhile to make sure that it still does. It's unfortunate that I didn't have a testcase to illustrate the problem I mentioned in the description, I'm wondering if it would still fail.

Please take over, I commandeered to restore the patch.

Restored the original patch.

Committed in rL335641.

This needs to be restored to the original form. A mistake in a commit message closed this review by accident.

Committed in https://reviews.llvm.org/rL335607.

I forgot to add the revision URL to the commit message: https://reviews.llvm.org/D48555.

The code itself is of a very reasonable size, I just meant removing the unnecessary fields from the machine function description, i.e. register classes (because they are specified inline), frame info, etc. Basically anything that is set to its default values. Testcases can be hard to generate for issues like this, so thank you for making effort to get them.

The testcase compiles fine with ToT at r335473.

I haven't looked at this in detail yet, but it's looking great. Thanks for tackling this!

Ping.

Added CHECK lines to the testcase (which was copied from D48546).

Please consider D48555 as a fix.

I don't want to be spending time reviewing more alternatives at this point. I'm familiar with what I've started and I fixed all known problems. I still need to analyze the problems in detail either way and reviewing additional patches is just more work for me.

This includes all testcases from related reviews.

Fixed handling of newly created implicit defs, relaxed handling of undef values in followCopyChain.

Rewrite SolveQuadraticEquation. This fixes https://bugs.llvm.org//show_bug.cgi?id=37211.

We shouldn't really be calling joinCopy with something that is not a COPY, but I guess it's a minor issue. Please replace the getOpcode() == ... with isImplicitDef(), and it should be fine.

The testcase was looking for two conditional assignments, both based on the same predicate register, but with one condition "if-true" and the other "if-false". The original bug was that the "kill" flag on the condition register wasn't cleared on the first assignment and so it was killed before the second conditional assignment (causing a verifier error). I just replaced this testcase with a .mir version, so it's no longer there.

This shouldn't be necessary. Try returning "true" from eliminateUndefCopy after generating an IMPLICIT_DEF.

For the purposes of matching the main pattern is really the same as the ones specified by Pats. I am opposed to making this feature specific to the "Pattern" field, (1) because this is a very useful feature to have in general, and (2) because if the implementation is main-pattern-specific, it would need to be replaced to make it work with Pats in the future. The main strength of this feature comes from multiple "source patterns" in a PatFrag.

My fix for the redef/undef issue was trying to avoid cases where we treat "undef" values from different registers as identical. I guess this could be relaxed (i.e. we can treat all undef values as identical), but we'd have to make sure that this equality is only used to allow removing an undef value (i.e. to allow pruning it without following it with extendToIndices).

Fix the "cannot join subranges" issue caused by redefining an undef value (more details in comments), roughly something like this:

I don't think that the new keyword is necessary. Why not have a new class Patternsthat takes a list of input dag patterns (otherwise identical to the current Pattern), and matches when any of these inputs matches? Then you can have a PatFrags as an analogy to PatFrag.

Fixed a typo and added a check for subrange liveness at OtherDef.

I committed a different fix for this: https://reviews.llvm.org/rL334963.

Updated x86 testcase.

Remove unnecessary stuff from the other testcase.

Updated the extension, added second testcase.

I can reproduce the problem using your testcase (which now works), let me try to reduce it and add to the patch.

Use extendToIndices.

You're right, extendToIndices should be ok. I wanted to be explicit about what gets extended (since it could catch other errors), while extendToIndices would just extend whatever is the reaching value.

Responded to comments, added x86-64 testcase.

This patch and the one you mentioned coincidentally both apply to rotates, but there wasn't any coordination between them.

Ping.

That simply undoes the pruning. It has to extend the specific value (OtherVNI).

My username at codeaurora.org.

Is it an .ll file? You can email it to me, I'll try to see if I can reduce it.