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.

I've renamed the constant pool labels as suggested.

Actually I was inspired by getPICLabel in ARMAsmPrinter.cpp but I can change it to 'CP' if it makes more sense.

Hi Christof,

It's unfortunate that we cannot share the globals across basic blocks. However, lowering a constant pool as a global variable guarantees that execute-only plays well with all the position-independent addressing modes out of the box. In order to support those with execute-only we would need to add new instruction patterns and logic to handle them in various places, which might introduce new bugs. I've switched back to the previous approach and added a few more checks to verify the CodeGen with position-independent addressing modes. I've also removed few more unreachable checks that can now be reached with PIC. Christof are you happy with it?

If find my original approach in diff1 less ad-hock than the latest one diff5. Lowering a Constant Pool as a Global Variable at the DAG level seems to me more legitimate than printing movw/movt for a LEApcrel machine instruction and then using the generic asm printer for the constant pool itself.

Fixed the way we materialise the address of a constant pool when generating execute-only code. Use movw/movt instead of pc-relative access.

Oops, I forgot to remove the llvm_unreachable() check from ARMISelLowering.

When generating execute-only code invoke the generic AsmPrinter in order to place the literals in the data section, otherwise handle Constant Pools in EmitInstruction.

Instead of suppressing this particular reproducer, teach the compiler to lower constant pools as global values (literals in the data section) when generating execute-only code.

Abandoning this on the base that Add Driver support for emitting the missing Tag_ABI_enum_size build attribute values has been abandoned. Apologies and thank you for reviewing this.

Hi Renato, apologies for the long silence. Unfortunately this work is more complicated than I initially thought. We'll have to rethink about it thoroughly. I am going to abandon the patch for now. Thank you for reviewing this.

Added the fallback logic for backwards compatibility.

Your suggestion that if all four options are mutually exclusive, then they should be a single integer option, totally makes sense to me. We could use a single integer option and make the old boolean flags deprecated (i.e. map '-fshort-enums' and 'fno-short enums' to the new integer option). My concern is that we have to be GCC compatible. I will communicate this to the GNU community.