I don't have much experience with SCEV either, but I think your draft change for instcombine made sense:
https://bugs.llvm.org/show_bug.cgi?id=47136#c8

We definitely stretch instcombine beyond the basics to try to reduce icmps, so if we can do that more efficiently here, that seems like a win.
Do you know if http://bugs.llvm.org/PR47091 could (eventually) be handled here?
Is there any initial compile-time data?

In D85787#2214038, @lebedev.ri wrote:

@ reviewers - i'm not so much interested in deep code/algo review,
but more like in the general direction disscussion, like, is this okay for instcombine? :)

In D85709#2216241, @venkataramanan.kumar.llvm wrote:

For x = 0, x/sqrt(0) result in "nan". However when we specify -ffast-math we are setting "nnan" flag. The nnan flag says "Allow optimizations to assume the arguments and result are not NaN" so we can transform x/sqrt(x) to sqrt(x) under -ffast-math. is that the right understanding here?

Thanks! LGTM - see inline for a minor mod.

In D85709#2215786, @venkataramanan.kumar.llvm wrote:

In D85709#2215718, @spatel wrote:

In D85709#2214967, @venkataramanan.kumar.llvm wrote:

In D85709#2211204, @spatel wrote:

After looking at the codegen, I'm not sure if we can do this transform in IR with the expected performance in codegen because the transform loses information:
https://godbolt.org/z/7b84rG

The codegen for the case of "sqrt(x)" has to account for a 0.0 input. Ie, we filter out a 0.0 (or potentially denorm) input to avoid the NAN answer that we would get from "0.0 / 0.0". But the codegen for the case of "x/sqrt(x)" does not have to do that - NAN is the correct answer for a 0.0 input, so the code has implicitly signaled to us that 0.0 is not a valid input when compiled with -ffast-math (we can ignore possible NANs).

It might help to see the motivating code that produces the x/sqrt(x) pattern to see if there's something else we should be doing there.

Current AMD "x86_64" targets don't have the reciprocal sqrt instruction for the double precision types.
so x/sqrt(x) ends up with "vsqrtsd" followed by "vdivsd". This transform is basically to improve the efficiency.

Ah, I see. I think we should handle that in generic DAGCombiner then. There, we can make the target- and CPU-specific trade-offs necessary to get the (presumably) ideal asm code. I don't know how we would recover the missing div-by-0 info that I mentioned here.
Let me know if you want to try that patch. If not, I can take a shot at it.

Sure I will work on the DAGCombiner patch .

In D85709#2214967, @venkataramanan.kumar.llvm wrote:

In D85709#2211204, @spatel wrote:

After looking at the codegen, I'm not sure if we can do this transform in IR with the expected performance in codegen because the transform loses information:
https://godbolt.org/z/7b84rG

The codegen for the case of "sqrt(x)" has to account for a 0.0 input. Ie, we filter out a 0.0 (or potentially denorm) input to avoid the NAN answer that we would get from "0.0 / 0.0". But the codegen for the case of "x/sqrt(x)" does not have to do that - NAN is the correct answer for a 0.0 input, so the code has implicitly signaled to us that 0.0 is not a valid input when compiled with -ffast-math (we can ignore possible NANs).

It might help to see the motivating code that produces the x/sqrt(x) pattern to see if there's something else we should be doing there.

Current AMD "x86_64" targets don't have the reciprocal sqrt instruction for the double precision types.
so x/sqrt(x) ends up with "vsqrtsd" followed by "vdivsd". This transform is basically to improve the efficiency.

In D85825#2215592, @dmgreen wrote:

The part I am a little unsure about is that it is converting add(vmlav) into a new vmlava, but we are starting at the vmlav to do it. So need to set the insertion point and use replaceAllUsesWith/eraseInstFromFunction. I couldn't find anything else that worked like that in instcombine, but maybe just missed it. It seems to work just fine like this, but it might be cause potential problems with the way instcombine iterates? It hasn't caused any problems we have seen though.

In D72396#2213671, @xbolva00 wrote:

What is status of this patch?

In D81766#2211991, @spatel wrote:

In D81766#2211952, @srj wrote:

Can we just add another condition (!VectorSize) to this bailout?
if (!ScalarSize || VectorSize % ScalarSize != 0)

Changing it to if (!ScalarSize || !VectorSize || VectorSize % ScalarSize != 0) does indeed seem to make our failure go away, so that would be fine as a quick fix.

(I'm still surprised that getMinVectorRegisterBitWidth() should ever return 0, but I can take that up with Qualcomm folks separately; it is entirely possible I don't understand the full semantics of that method.)

rGb0b95dab1ce2
l'll see if I can find a better API and/or test case for that tomorrow.

In D81766#2211952, @srj wrote:

Can we just add another condition (!VectorSize) to this bailout?
if (!ScalarSize || VectorSize % ScalarSize != 0)

Changing it to if (!ScalarSize || !VectorSize || VectorSize % ScalarSize != 0) does indeed seem to make our failure go away, so that would be fine as a quick fix.

(I'm still surprised that getMinVectorRegisterBitWidth() should ever return 0, but I can take that up with Qualcomm folks separately; it is entirely possible I don't understand the full semantics of that method.)

In D81766#2211936, @srj wrote:

Update: it appears that VectorSize (from TTI.getMinVectorRegisterBitWidth()) is zero in this case, which causes the assertion failure.

This appears to be the case because HexagonTTIImpl::getMinVectorRegisterBitWidth() returns 0 if useHVX() isn't true... and useHVX() returns false if the HexagonAutoHVX option isn't enabled.

By design, Halide doesn't enable the HexagonAutoHVX option; we like to do all the vectorization ourselves.

I'm not sure how to resolve this issue -- the flaw here seems to lie in HexagonTTIImpl's assumption that disabling HexagonAutoHVX should cause it to report zero-width vectors, which seems to be a dubious decision (and one that is at odds with every other implementation of getMinVectorRegisterBitWidth() that I see in trunk LLVM (none of them appear to ever return 0).

Would it make sense to consider backing out this change until this can be resolved, since it clearly appears to have bad consequences for Hexagon/HVX codegen?

Patch updated:
Given the transform above this one and the type checks included there and here, I think we can assert that sizes match. Let me know if that handles the possible problem patterns that we must avoid.

After looking at the codegen, I'm not sure if we can do this transform in IR with the expected performance in codegen because the transform loses information:
https://godbolt.org/z/7b84rG

In D85709#2210042, @cameron.mcinally wrote:

In D85709#2210034, @lebedev.ri wrote:

In D85709#2209979, @cameron.mcinally wrote:

I'm fairly sure this transform is a performance loss. For a target like Skylake Server, a SQRT(x) can take up to 20 cycles. But a RSQRT(x) is about 6 cycles and a MUL(y) is 4 cycles. We'd be better off with a X*RSQRT(X).

That is up to backends to decide. InstSimplify/InstCombine (and a few others) are canonicalization, target-independent passes.
A single sqrt(x) is more canonical IR than x/sqrt(x), because it's less instructions and x has less uses.

I agree with that. It should be canonicalized. It would also be good to make sure that the backends have lowering code in place before introducing a 2x performance hit.

In D85709#2209206, @grandinj wrote:

Just a drive-by comment : Possibly the more general form of this needs to be optimised too?

The more general form of this is

X^a * X^b -> X ^ (a+b)

X^a / X^b -> X ^ (a-b)

I agree that this looks wrong for the example with undef substituted in...but that also means that almost every instcombine that doesn't specify hasOneUse() is wrong!
But then how are we not miscompiling more often? We must be simplifying instructions with undefs before they can escape and cause trouble as @nikic hinted at?
@efriedma @regehr @nlopes - comments?

In D54749#2206518, @ebevhan wrote:

It seems like there are quite a few people who would like to use this intrinsic, though. The only lack of interest seems to be in reviewing.
I was planning on submitting something similar for the fixed-point support, but now that I know this patch exists, I feel like helping this move forward is the better option.

Please pre-commit the test file and upload diff with context.

In D64142#2204671, @RKSimon wrote:

@spatel Has this been superseded by D81766?

Patch updated:
Changed pointer check to an assert.

Is there a reason to do this in InstCombine rather than InstSimplify? We are not creating any new instructions.

Patch updated:
Use TTI.getScalarizationOverhead() to model insert cost of original code. I had not used this API before and the documentation comment isn't entirely clear to me, so please see if that looks as intended.

I'm ok with this as-is (mod "-1" code nit) followed by cleanup, so LGTM.
Wait a bit to see if anyone else wants to comment though.

In D84250#2202732, @aqjune wrote:

Should we go to D84792's direction?
If it is, I think we should mention that it is a workaround for the miscompilations including PR33165, and it can still be problematic in theory but chose to do it for performance.

The reassociate pass (like instcombine) is supposed to be a target-independent canonicalization pass:

  // This pass reassociates commutative expressions in an order that is designed
  // to promote better constant propagation, GCSE, LICM, PRE, etc.

So it's intentionally avoiding using TTI/TLI and trying not to do all forms of reassociation. As Roman mentioned, see D67383 as an example of a possible TTI-aware reassociation pass.

Patch updated:
Adjusted to match the most basic pattern that starts with an insertelement (so there's no extract created here). Hopefully, that removes any concern about interactions with other passes. Ie, the transform should almost always be profitable. (We could make an argument that this could be part of canonicalization, but we conservatively try not to create vector ops from scalar ops in passes like instcombine.)

In D85230#2194521, @RKSimon wrote:

Maybe make it clear at the start of InstCombinerImpl::foldSelectOpOp where we use the matchers that we can safely use the matchers for the select(icmp) pattern OR the intrinsics?

Patch updated:
No code changes, but added tests for non-zero gep offsets. This actually works more than I was expecting given that we're only using the base stripPointerCasts(). If there are enough dereferenceable bytes, isSafeToLoadUnconditionally() can still manage to use the offset load via the existing gep.

Will need update after:
rG04b99a4d18cf

Patch updated:
Pass in more info from the SimplifyQuery to ValueTracking.
Not sure what it takes to show the benefit, so no test diffs, but if there are suggestions, let me know.

LGTM

It's not clear to me how these all of the undef safety features will come together, but this looks correct and unlikely to cause regressions, so LGTM.

LGTM

Ping.

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

The SelectionDAG version does the following, so it would make sense to adapt these here:

// If the source's MSB is zero then we know the rest of the bits already.
if (Known2.isNonNegative()) {
  Known.Zero = Known2.Zero;
  Known.One = Known2.One;
  break;
}

LGTM