I couldn't manage to craft a test based on an .ll file, so I kept the unit test, but I'm now parsing the IR from a string.

Thanks for guiding me on this patch. I can't commit the patch myself as I don't have commit access.

In D97676#2609966, @nikic wrote:

Could you please also update the patch summary, as this is no longer using SCEV?

Updated patch to reflect the requested changes. Updated the revision description too.

Added a unit test to verify that the modification to IsGuaranteeLoopInvariant leads to retaining the location information associated to a MemoryAccess (in this case a MemoryPhi) when handling a pointer defined in the entry block.

The new diff just adds some additional tests, one showing that the DSE vector test proposed by @dfukalov is properly handled and two showing that non-fully overlapping stores are kept untouched. The unneeded short-circuit condition is also removed.

It seems these two fixes may be independent, but you can check my GVN approach in the diff: https://reviews.llvm.org/D93529?id=313082.

I'm reading the GVN source code to learn about it and understand your approach. I'll try to support the dead store example you shared. I'm probably missing something, but it seems the GVN approach is based on information deriving from the Memory Dependence Analysis (and related API), while here I'd like to find a solution suitable for both MD and MSSA in the isOverwrite function, hence I'll try to generalise the check to support the vector types.

Using a single AA.alias query.

@nikic I based it on the WIP patch you suggested and it works fine, so I updated the differential to reflect that it'll be doable without ScalarEvolution once the patch will be committed.

In D97155#2579921, @fhahn wrote:

I didn't provide a test yet, because it's not clear to me how to create one that is showing the improvement in the MemorySSA case.

Could you add a variant of the test added in a0017c2bc258690146f18491317144e487ddb101 ?

In D96979#2579928, @fhahn wrote:

Please let me know if you need someone to land this change on your behalf & the name + email that should be used for attribution.

@fhahn I verified the similar logic in MemorySSA.cpp, but I think the unification should be part of a different patch, right? Should we try to come up with a single function that we can call both from MemorySSA.cpp and DeadStoreElimination.cpp or should we keep them separated but semantically equivalent (therefore porting this addition to the MemorySSA.cpp version of the function)?

Added an explanation to the test file.

I tried to update the patch to execute the entry block check on the incoming pointer (if it's an instruction) as first thing in the IsGuaranteedLoopInvariant function.

Also, calling TempTrue->deleteValue(); and TempFalse->deleteValue(); if the values are not being used because the optimisation is not doable (conditions are not met) should be the right thing to do to avoid leaking, right?

@nikic I tried to oblige to your comment and come up with a check in SimplifySelectsFeedingBinaryOp to verify if we are in the condition where either the instruction has one use or True and False fold into constants.

OK I think I figured it out.

@lebedev.ri I just realised that obviously narrowing the problem from i64 to i8 will break it. I'll gladly relax the existing optimisation if possible and submit a new patch, but to me it's clear that there's something wrong going on with the i64 optimisation. I'm now trying to compile Alive2 with the trunk version of LLVM, but I would wait for your confirmation on the i64 case (with Alive2 or input values if possible) before updating the current patch.

Please just post IR inline, it's super inconvient to extract it from attachmensts

Took note of this, sorry!

I reduced the bit-width to i8 and the same issue is happening when I only disable the if (!I->hasOneUse()) return false; line from canEvaluateShifted. Is there a chance that disabling the check is not sufficient but that would actually require more changes?

Adding more context to the missed optimisation.

I thought the same when I first saw those calls to hasOneUse, but if the code to handle the multiple users case that I added to InstructionCombining.cpp is kept and the calls to SimplifySelectsFeedingBinaryOp are removed from InstCombineShifts.cpp, the simplification won't work anymore.

Applied formatting missing from one file.