Abandoned, problem was dealt with in https://reviews.llvm.org/D110292

This seem to cause some weird results.

This can be seen as an alternative to https://reviews.llvm.org/D110292

I'm also showing the alternative approach, making EarlyCSE less depending on what other passes is doing when updating the DomTree, here: https://reviews.llvm.org/D114620

Updated code comments.

LGTM

In D110527#3121935, @reames wrote:

In D110527#3121915, @bjope wrote:

The IR part can often be eliminated from a MIR based test case. But sure, one could argue that when running llvm-reduce it could be mandatory to add an IR section in the .mir file first (but then I think one needs to also add the function prototype).

I can maybe see this as an argument for allowing override of the triple, but not as an argument for not defaulting to the triple if present. Frankly, I find even the override case unconvincing.

In D110527#3121905, @reames wrote:

In D110527#3121844, @aeubanks wrote:

In D110527#3121812, @reames wrote:

I'm looking at using this functionality, and ran into a question on the design. I'm not clear why you exposed an mtriple command line argument on llvm-reduce. It appears you're using this to derive a default data layout, and as an input to parsing the machine function. However, LLVM IR allows specifying both data layout and triple in IR. As a result, we should be able to have the parsing derive the appropriate target directly from the test case. Is there something I'm missing here?

I believe it's only used in the MIR case, not the IR case. This could definitely be made clearer in the cl::opt help.

I don't think it's necessary even for the MIR case. MIR includes the full IR module, and is as a result, is also fully self describing. (If the optional datalayout and triple fields are present.)

LGTM

Suggesting some edits (there shouldn't be a need to have a DIFile directory path (at least not in some of those test cases). So I think it is better to clean it up a bit more if touching those test cases.

LGTM!

I noticed that we have two downstream fixes (that for some reason haven't been upstreamed yet, I figure we did not have any reproducers identifying this as an upstream problem) that is a bit related to your patch.
Our patch looks like this:

I actually see lots of these as well:

clang: ../lib/Support/APInt.cpp:284: int llvm::APInt::compareSigned(const llvm::APInt &) const: Assertion `BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"' failed.

I get failures after having merged this patch:

Abandoned. Obsoleted by D111896.

Now using isKnownViaNonRecursiveReasoning instead of isKnownPredicate.

I plan to update this patch into using isKnownViaNonRecursiveReasoning as suggested by @nikic

I figure there might be some program out there for which this still will converge slowly etc, and I'm not sure exactly how to prove that this is better in general terms.

An alternative solution is presented in D112080 (using a different order for the checks involved).

Thank! LGTM!

In D110813#3045467, @bjope wrote:

In D110813#3041983, @fhahn wrote:

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

Yep. I've downloaded D110385, and used verify<scalar-evolution> after loop-rotate instead of print<scalar-evolution>. Then I see this:

Cached block disposition of SCEV (trunc i32 %wide to i16) for basic block: 
loop.inner:                                       ; preds = %loop.inner, %loop.inner.ph
  %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
  %iv.promoted = zext i16 %iv to i32
  %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted
  store i32 7, i32* %gep, align 1
  %iv.plus = add i16 %iv, 1
  %cmp = icmp ult i16 %iv.plus, 700
  br i1 %cmp, label %loop.inner, label %loop.outer.latch
 has changed!
Cached: 2
Actual: 0

In D110813#3041983, @fhahn wrote:

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

Rebased after modifications in D110812.

Cleaned up the test case a bit as suggested in the review.

In D110170#3042818, @spatel wrote:

In D110170#3041159, @bjope wrote:

I noticed a regression in a downstream benchmark, that at least partly seem to be caused by it. Here is a reduced example: https://godbolt.org/z/M9MKjcYPG

From what I can see there is a quite early run of InstCombine in the O3 pipeline, which basically happens directly after GlobalOpt without any CSE in between. So in such an early run of InstCombine we do trigger transforms based on "one use", which wouldn't have happened if running CSE before InstCombine. I figure that might be a more general problem and not only specific to the rewrites introduced in this patch.

We'll analyse the regression a bit more (maybe there are other things that happens that contributes to the regression). But wanted to mention the above. And it makes me a bit curious if it is a general problem with that early instcombine run that "one use" checks might be fooled by not having done CSE after GlobalOpt.

Thanks for posting the example. That does seem like a general problem, and it's worth experimenting with the pass manager to see if reordering the passes makes things better or worse.
I'm not sure if we have an IR pass that is responsible for seeing that we have redundant shift ops like in the example. Is that a possible trick for GVN?
Also, I tried running the example through codegen for x86 and AArch64, and they both manage to eliminate the redundant extra shift after legalization. Is it possible that your target is missing a semi-generic SDAG transform?

In D111066#3041655, @mkazantsev wrote:

This patch is one year old. It is extremely surprising that you are trying to disable it rather than find the root cause.

I don't believe this is infinite recursion. Before all, infinite recursion should end up with stack overflow and not timeout. I can believe there is some exponential explosion happening, but in this case you need to find how exactly it happens and fix the acutal reason. The fact that this patch triggers something very slow doesn't convince me that this patch is guilty, and this test doesn't allow to figure it out easily.

Could you please check (at least, but not limited to):

• Do we end up creating some HUGE SCEVs in your test?
• Do we end up making the same implication query millions of times?
• Do we end up walking huge dom trees for execution of some queries?

Before we decide to switch something off, I want to know why exactly.

Reduced the test case. Maybe too much, because now it terminates after around 10 minutes. The previous (>5000 lines) version of the test case is still running after 2 hours (and I do not even know if it will terminate).

I noticed a regression in a downstream benchmark, that at least partly seem to be caused by it. Here is a reduced example: https://godbolt.org/z/M9MKjcYPG

In D110848#3040584, @MatzeB wrote:

Yes I considered it, but I think there are advantages to both approaches. The problem with a MIR test case is that if the target changes its instruction definitions in any way, updating the MIR input is definitely a manual process.

That said, I'm happy to do a MIR test instead if you still prefer it.

The other side of the medal is that the test now depends on the all the passes before to behave the same, so changes to instruction selection, calling convention modeling etc. throw off the tests.

While I may be biased here as to what is more common, I think having a unit test as targetted as possible (1 pass only) is a good principle to aim for.

In D111066#3040370, @bjope wrote:

In D111066#3040144, @nikic wrote:

Can the test case be reduced? I don't think we want to add a 5000 line test case for this.

I made some attempts using bugpoint earlier (and this is actually a bit reduced compared to the original test case). A bit tricky to set it up as the fail scenario is that there should be a timeout, and then it will take lots of time to get bugpoint to actually reduce anything.
I also made some attempts adding some kind of debug printouts to detect failure by identifying some repeated patterns when calling ScalarEvolution::isImpliedCond, but never managed to get that working properly.
If I knew what the problem is it might be easier to reduce it ;-)

If anyone got some ideas on how to tackle the problem with reducing it I wouldn't mind testing those ideas.

(Maybe I should give "bugpoint + timeout" another try. But I think I need quite a long timeout setting, so it takes some time if it only attempts to remove 1 instruction every 5 minutes or so.)

In D111066#3040144, @nikic wrote:

Can the test case be reduced? I don't think we want to add a 5000 line test case for this.

In D89548#3026933, @bjope wrote:

In D89548#3009262, @uabelho wrote:

Hi @mkazantsev ,

The following hang started occuring with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51869

I've also seen hangs in loop-idiom-recognizer with the patch so I suppose many passes using SCEV might run into the same kind of problems.

I haven't tried to revert this patch, but maybe that should be explored (as it seems broken in the sense that it might cause infinite looping / severe compile time regressions)?

Rebased.

ping

In D110585#3029588, @arichardson wrote:

@bjope What do your pointers look like? For RISCV-64 CHERI and Arm's Morello we have 128 bits + 1 bit of hidden state, but only 64 of them are used for the address part, so uintptr_t is 128 bits and size_t/ptrdiff_t are 64 bits. Our datalayout string is e-m:e-pf200:128:128:128:64-p:64:64-i64:64-i128:128-n64-S128-A200-P200-G200 (the f in pf200 marks address space 200 as using "fat pointers", since our backend predates non-integral pointers and non-integral pointers also limit optimizations a bit too much since ptrtoint is fine for us). We also have a version CHERI for 32-bit architectures where we 64-bit pointers+32-bit size_t, and therefore use "e-m:e-pf200:64:64:64:32-p:32:32-i64:64-n32-S128-A200-P200-G200"

Notice that I feel a bit "on deep water" here. Is the patch (and the description in the commit msg) making sense?

In D110585#3028146, @nikic wrote:

As I mentioned on the other review, I think that DL.getIndexSizeInBits() should be used for the size_t size. If we do that, do we really need a TLI hook?

Ran clang-format on unittest updates.

In D110064#3015456, @niravd wrote:

Can you add a codegen test for PR51878? The example listed in your message should do.

Once I think with the follow up, this should be good to go.

In D89548#3009262, @uabelho wrote:

Hi @mkazantsev ,

The following hang started occuring with this patch:
https://bugs.llvm.org/show_bug.cgi?id=51869

I've also seen hangs in loop-idiom-recognizer with the patch so I suppose many passes using SCEV might run into the same kind of problems.

Rebased on top of D110584.

Update after review feedback:
Now assuming that we always have a Module (and DataLayout) when using getLibFunc/isValidProtoForLibFunc.