Committed as https://reviews.llvm.org/rL349338

In D55108#1330014, @dmgreen wrote:

IIRC, there is a test for the pass pipeline I would expect needs updating.

I've tested the patch with native builds of the llvm-test-suite on an AArch64 Cortex-A72 and couldn't spot anything interesting in terms of compilation time.

Ping

Looks fine. Thanks!

In D55009#1311601, @john.brawn wrote:

It may be worthwhile allowing scalar PRE on GEPs that we know won't be combined into the addressing mode of a load/store, i.e. those where TargetTransformInfo::isLegalAddressingMode returns false.

In D54170#1289220, @efriedma wrote:

This looks like a bunch of separate changes which should be split into multiple patches. Especially the changes to DAGCombine and InstCombiner::visitZExt .

In D53236#1289222, @spatel wrote:

LGTM

(For reference: I was wondering why x86 doesn't show any diffs for this change; it looks like there's custom code in X86ISelLowering that already does the same thing.)

Rebased and clang-formatted.

I've autogenerated the filecheck lines to show the diff compared to the trunk codegen. For making sure we never fall-through to the next block, having changed the CC but not swapped (N2, N3), I've moved all the preconditions to the beginning of the block (instead of moving the block into a helper function).

In D53236#1265594, @spatel wrote:

Is the motivating case integer or FP?
I'm asking because we have a canonicalization for integer cmp+sel for the IR in these tests, but we're missing the corresponding FP transform.
If we add the FP canonicalization in IR, would there still be a need for this backend patch? Ie, is something generating this select code in the DAG itself?

Not ready for review. Using this as reference to and RFC in llvm-dev.

Rebase rL338240 since the excessive memory usage observed when using GVNHoist with UBSan has been fixed by rL340818 (https://reviews.llvm.org/D50323).

In D50323#1205193, @hiraditya wrote:

Do you need help with pushing the changes?

Apologies for delaying this, I was out of office. I'll rebase and push it asap.

So, is everyone happy with this change?

This got reverted because of an out-of-memory error on an ubsan buildbot. Details and fix here -> https://reviews.llvm.org/D50323. I'll update the tests upon rebase.

Did you test it with some benchmarks? Results?

I am running lnt, spec2000 and spec2006 on AArch64 at the moment. I'll post results soon.

Changes to prior revision.

• Removed the update loop for PhiOps and used TrackingVH<MemoryAccess> instead.
• Replaced the Bitcode reproducer with IR using -preserve-ll-uselistorder.

In D49425#1167032, @efriedma wrote:

If the bitcode is crashing but the textual IR isn't, you're probably getting bitten by use-list ordering. You can use the preserve-ll-uselistorder option for "opt" to preserve it in IR.

Does the original test-case crash reliably as IR for you? If so, please use that instead. (Phab won't let me download the attached bitcode, but with asan, I see use-after-free crashes 100% of the time in the original repro).

It does, but using opt -S -O3 ./tc_memphi_gvnhoist.ll -enable-gvn-hoist. Using bugpoint on that command you get the bitcode I uploaded.

A few remarks:

• SmallVector<WeakVH, 8> PhiOps fixes the bug on its own (without the rest changes) and I am wondering why..
• When we mark a block as visited why do we cache it? When the recursion ends we might trivially remove the Phi. In that case the second cache insertion for the same key block should fail, no?
• Do we ever reach the PHIExistsButNeedsUpdate case? Is it when a Phi existed beforehand, meaning we did not create it? I can't think of another way to reach that state.
• Interestingly enough the reproducer only made opt crash in bitcode form and not in IR form.

Ok, I've convinced myself that using WeakVH is the most straightforward fix for now. We shouldn't be spending more time on this.

Replacing MemoryPhi * with WeakVH won't work out of the box; it requires typecasts and null checks upon iteration. It also adds and additional overhead (similar to AssertingVH though). In general, the idea of keeping null references in the ADT instead of actually deleting them seems like a workaround to me. I don't see why we should be afraid of making non trivial changes in the code if there's a fundamental bug. On that note I still believe the line 303 of the original revision is wrong since we push_back() when adding new elements:

FixupList.append(InsertedPHIs.end() - StartingPHISize, InsertedPHIs.end());

Shouldn't it be like this?

FixupList.append(InsertedPHIs.begin() + StartingPHISize, InsertedPHIs.end());

Answering some inline comments:

Changes to the prior revision:

• I've used std::set for InsertedPHIs to avoid linear cost lookups upon deletion.
• I've refactored insertDef() so that it no longer relies on insertion order iteration over InsertedPHIs.

In D49030#1155072, @dexonsmith wrote:

Personally, I'd be in favour of changing MapVector to just do this, since it already has an index. I'd also be in favour of adding an index to SetVector to match. There'd be some work to do in auditing/updating users, but I doubt there are many calls to erase() and I'm skeptical that anyone relies on the current order for something other than determinism.

I think we should not change MapVector. Its underlying data structure is a vector with <key,value> pairs but we only need to store a single value. Moreover, both MapVector and SetVector provide insertion order iteration and their users might rely on that. I am not sure we should change that. SmallSet might be a good alternative for lower insertion/deletion complexity, but at the moment it does not provide iteration over the underlying data structures. It uses a SmallVector for small data sets and expands it to an std::set if it grows too much. Is there a way to abstract those underlying iterators? If not I think we should keep this new ADT and rename/document it properly.

In D49030#1155000, @chandlerc wrote:

We already have SetVector which is widely used for these patterns. If we need both, we need a clear explanation of the difference and why we need both (IE, why users of one can't use the other).

The remove operation on a SetVector can cost linear time and this might be an issue in some cases. Please have a look at the review comments of https://reviews.llvm.org/D48372

Added back the header file for SmallPtrSet that was accidentally removed.

Used the ADT from https://reviews.llvm.org/D49030

I've accidentally edited the revision instead of just adding a new diff. Anyway, I've reset it to the original content and created https://reviews.llvm.org/D49030 with my changes for review.

Another thing to consider maybe is the complexity of iteration over the vector. Imagine the case where we insert N elements and we erase M with M being almost the size of N. The iteration will be O(N) and not O(N-M).

My argument would be that this change is fairly small. To be honest I don't know what is the status of GVN-Hoist. If it is in a good shape, then enabling it is the best way to go. If there are a few bugs to fix I am happy to help, but if it is far from being in a good shape then a workaround like this should be acceptable.

Bail the optimization if the memory alignment is not power of two. Added a test to cover this case.

• Restrict the optimization to table lookups returning a <8 x i8> vector type. It's only beneficial for the mask {7,6,5,4,3,2,1,0} anyway.
• Bail out if the constant mask contains an index out of range. The second argument of the new shufflevector is always going to be <undef> so the range is [0 ~ NumElts-1], not [0 ~ 2*NumElts-1], like @efriedma noticed.
• Replaced getZExtValue() with getLimitedValue() for getting the value of a ConstantInt.
• Simplified the retrieval of mask indices by using ConstantDataVector::get instead of ConstantVector::get.
• Added testcases where the transform bails out.
• Autogenerated the Filecheck patterns using the script utils/update_test_checks.py

Using getLimitedValue() instead of getZExtValue() for the ConstantInt representing the memory alignment of the load instruction. Updated the tests: alignment in now expressed in bytes instead of bits.

Ping?

Ping?

Please update your diff file in order to contain all the file content. Thanks.

@efriedma, ping.

@efriedma, ping. Any perf results on this?

Sure! Thanks again for the review :)

I've actually used the utils/update_test_checks.py to auto-generate Filecheck assertions for the unit test. @spatel, this script is very practical but I am bit sceptical about it. We must be very careful when using it. The checks may not impose the desired compiler behaviour when auto-generated.

@spatel, how cool! Thanks for pointing that out. I wasn't aware of that script. I'll update my test shortly.

Changes to the test file:

• Made the RUN line redirect the input file to opt.
• Added a NOTE to enable autogenerated assertions.

The dynamic cast check for the alignment parameter of the intrinsic is necessary. I could bail the optimization if it's not constant and let the backend crash later on. There are plenty of intrinsics where some arguments need to be constant, but IR has no way to enforce that. Clang will guarantee for it. The rest of the suggestions sound sensible. I'll update my patch accordingly.

Good catch. The current patch hits the assertion when handling the llvm.aarch64.neon.tbl1.v16i8 inrinsic, because NumElts is 16. Does it make sense to perform the transformation in this case? I could get rid of the assert and bail the optimization if NumElts neither 8 nor 16 (or just 8).

I've moved the constant folding to a new revision: https://reviews.llvm.org/D46273. I've also added comments to the tests explaining the reason of this transformation.

@efriedma I am going to create a new revision for converting a vld1 into an llvm load. I'll then update this revision to keep only the tbl1~>shufflevector conversion. I'll also make the patch accept any constant mask pattern.

The constant folding of the vld1 intrinsic might worth moving in lib/Analysis/ConstantFolding.cpp as a separate patch, but I wasn't sure whether we always want to fold vld1, even when it's not used as a table lookup mask. I've asked about the matter in llvm-dev.

The Address Sanitizer caught a stack-use-after-scope of a Twine variable. This is now fixed by passing the Twine directly as a function parameter.

I've upset a buildbot which runs the address sanitizer:
ERROR: AddressSanitizer:
stack-use-after-scope lib/Target/ARM/ARMISelLowering.cpp:2690
That Twine variable is used illegally. I am reopening the revision.