[GVN] MemorySSA for GVN: eliminate redundant loads via MemorySSA #152859

antoniofrighetto · 2025-08-09T14:39:41Z

Introduce the main algorithm performing redundant load elimination via MemorySSA in GVN. The entry point is findReachingValuesForLoad, which, given as input a possibly redundant load L, it attempts to provide as output a set of reaching memory values (ReachingMemVal), i.e., which values (defs or equivalent reads) can reach L along at least one path where that memory location is not modified meanwhile (if non-local, PRE will establish whether the load may be eliminated).

Specifically, a reaching value may be of the following descriptor kind (DepKind):

Def: found a new instruction that produces exactly the bits the load would read. For example, a must-alias store (which defines the load memory location), or a must-alias read (exactly reads the same memory location, found, e.g., after a phi-translation fixup);
Clobber: found a write that clobbers a superset of the bits the load would read. For example, a memset call over a memory region, whose value read overlaps such a region (and may be forwarded to the load), or a generic call clobbering the load that cannot be reused;
Other: a precise instruction could not be found, but know the block where the dependency exists (e.g., a memory location already live at function entry).

We start off by looking for the users of the defining memory access of the given load within the same block, searching for local dependencies. We may need to iteratively follow the use-def chain of the defining memory access to find the actual clobbering access, while staying within the scope of the load. If an actual local def/clobber (or liveOnEntry) is found, we are done and return that one. Otherwise, we move visiting the predecessors of the load's block, considering the incoming value from the MemoryPhi as a potential clobbering access. Hence, we search for dependencies within the predecessor block itself. If the new potential clobbering access is a MemoryPhi, we continue visiting the transitive closure of the predecessor, recording its new potential clobbering access. In this phase, as we are exploring non-local definitions, the load itself may be considered a must-alias def as well when being examined from a backedge path.

A detailed description of the algorithm from the original patch follows.

The algorithm consists of three parts:

Quick check for a local dependency;
Discover the set of basic blocks (and MemoryDefs, a.k.a clobbers) which could affect the load location, as well as all the blocks that lie on a path from a clobbering block to the load instruction, but do not modify the memory location (transparent blocks);
Examine the uses of the clobbers which belong to one of the basic blocks found in the previous step and find ones which alias the memory location.

First, we do a quick check for a local dependency, i.e., a memory read or write within the same basic block as the initial load instruction. Doing this first allows us to avoid having to disambiguate between the parts of the initial basic block
before and after the original load instruction (when entered from a backedge).

We find the clobbering set of blocks by doing a walk of the reverse CFG (iterative DFS with a worklist), stopping (i.e., not visiting the predecessors further) at blocks/instructions which definitely modify the memory location. With each basic block, we maintain the following associated information:

A memory address;
A initial clobbering memory access;
A final clobbering memory access.

The worklist is seeded with the predecessors of the starting basic block (the one that contains the initial load instruction). For each of these blocks, the memory address is the pointer operand of the load, possibly phi-translated and
the initial clobbering memory access is the defining access of the load, again, possibly phi-translated. The final clobbering memory access is at first the same as the initial one. These blocks are added to the set.

On each iteration we fetch and examine the next basic block. There are a few cases to consider:

If the memory address is unknown, it means phi-translation failed; do nothing at this point, later the block will be thought of as modifying the memory location in unknown way;
We have a (final) clobbering memory access that is an actual instruction (not a MemoryPhi) in the current block and indeed clobbers the memory address; we record the dependency information for later use, stop further traversal from this block and continue with the next iteration;
We have a (final) clobbering memory access that is an actual instruction (not a MemoryPhi) in the current block and does not actually clobber the memory address; we record its defining memory access as the new final clobbering memory access, re-queue the block, and continue to the next iteration;
If none of the above clauses hold, we know that block is transparent, i.e. the memory location is not modified when execution passes through this block. We add the predecessors of the block to the set. If needed, phi-translate the address and the final clobbering memory access. Then add the predecessors to the worklist and proceed to the next iteration.

There are a few subtle moments when transitioning to predecessors:

If the address needs to be phi-translated, but cannot to, we consider the memory location as modified in an unknown way just before entering the block; since we know the block is transparent, for uniformity and without loss of information we can treat this situation as if the memory location was modified immediately after exiting the block;
If a predecessor is a block already visited with a different address we mark the current block as modifying the memory location in an unknown way. The dependency information that RLE in GVN expects is per block and it cannot represent dependencies coming from the same block;
If a predecessor is an already visited (with the same address) block, just skip it at this point;

At this phase of the algorithm, the set we're building serves as the visited set so as to prevent infinite loops.

Once this first phase of the algorithm completes, we have obtained the needed set of the basic block as well as the memory writing instructions that could modify our location. For each block, the initial clobbering memory access is the
one we enter the block with, and there is a use-def chain to the final clobbering memory access where every access is non-aliasing, except for the final one.

We still have to determine if there are memory reads that act as definitions (see above). Once again we do an iterative DFS on the reverse CFG.

On each iteration we look for memory uses in the current block. For this we first construct a list of the memory clobbers that could be a defining memory access for our memory location. This list begins with the initial clobbering memory access for the current block, following the clobbers along the use-def chain up to the final clobbering memory access. If the final clobbering memory access belongs to the same block and is not a MemoryPhi that finishes building
the list – we cannot have an aliasing use in the block, that is not a use of the final clobbering memory access. Otherwise, we look to extend the list in a couple of ways:

If the final clobbering memory access is in another block, we transition to this other block and repeat the procedure;
If the final clobbering memory access is in the same block and it's a MemoryPhi, we transition to the immediate dominator of the current block and repeat the procedure.

In both cases, transition occurs if and only if the new block is already among the collected set of clobbering blocks.

Once we have the list of clobbers, we look in turn at uses of each clobber in the list, that are in the current block, looking for memory reads which could provide (a superset of) the bits of the memory location. For those reads, we choose the one closest to the end of the block. A following (dominating) clobber in the list is processed only if no usable memory read was found so far.

If an interesting memory use was not found, we look for a clobber in the current block. This was already determined in the phase which collected the set of clobbering block. If there is a clobber, we include it in the list of the results, otherwise the block is transparent, and we can add it to the worklist.

Original patch: https://reviews.llvm.org/D116825, incrementally moved towards https://reviews.llvm.org/D130489 (primary change involves moving from a linear scan of the whole memory accesses of each basic block via getBlockAccesses() to building a list of potential clobbers and following their use-def chain.)

Minor additions wrt the latest original version encompass style, improved naming, further comments, code hoisting / rearrangement opportunities, APIs update, discontinued API removal, partial tests update (complete tests update prior to turning on MSSA).

Introduce the main algorithm performing redundant load elimination via MemorySSA in GVN. The entry point is `findReachingValuesForLoad`, which, given as input a possibly redundant load `L`, it attempts to provide as output a set of reaching memory values (`ReachingMemVal`), i.e., which values (defs or equivalent reads) can reach `L` along at least one path where that memory location is not modified meanwhile (if non-local, PRE will establish whether the load may be eliminated). Specifically, a reaching value may be of the following descriptor kind: * Def: found a new instruction that produces exactly the bits the load would read. For example, a must-alias store (which defines the load memory location), or a must-alias read (exactly reads the same memory location, found, e.g., after a phi-translation fixup); * Clobber: found a write that clobbers a superset of the bits the load would read. For example, a memset call over a memory region, whose value read overlaps such a region (and may be forwarded to the load), or a generic call clobbering the load that cannot be reused; * Other: a precise instruction could not be found, but know the block where the dependency exists (e.g., a memory location already live at function entry). We start off by looking for the users of the defining memory access of the given load within the same block, searching for local dependencies. We may need to iteratively follow the use-def chain of the defining memory access to find the actual clobbering access, while staying within the scope of the load. If an actual local def/clobber (or liveOnEntry) is found, we are done and return that one. Otherwise, we move visiting the predecessors of the load's block, considering the incoming value from the MemoryPhi as a potential clobbering access. Hence, we search for dependencies within the predecessor block itself. If the new potential clobbering access is a MemoryPhi, we continue visiting the transitive closure of the predecessor, recording its new potential clobbering access. In this phase, as we are exploring non-local definitions, the load itself may be considered a must-alias def as well when being examined from a backedge path.

github-actions · 2025-10-20T19:29:49Z

⚠️ undef deprecator found issues in your code. ⚠️

You can test this locally with the following command:

git diff -U0 --pickaxe-regex -S '([^a-zA-Z0-9#_-]undef([^a-zA-Z0-9_-]|$)|UndefValue::get)' 'HEAD~1' HEAD llvm/include/llvm/Transforms/Scalar/GVN.h llvm/lib/Transforms/Scalar/GVN.cpp llvm/test/Analysis/TypeBasedAliasAnalysis/gvn-nonlocal-type-mismatch.ll llvm/test/Transforms/GVN/PRE/load-metadata.ll llvm/test/Transforms/GVN/PRE/lpre-call-wrap.ll llvm/test/Transforms/GVN/PRE/phi-translate-2.ll llvm/test/Transforms/GVN/PRE/phi-translate-add.ll llvm/test/Transforms/GVN/PRE/phi-translate.ll llvm/test/Transforms/GVN/PRE/pre-after-rle.ll llvm/test/Transforms/GVN/PRE/pre-aliasning-path.ll llvm/test/Transforms/GVN/PRE/pre-load-dbg.ll llvm/test/Transforms/GVN/PRE/pre-load-guards.ll llvm/test/Transforms/GVN/PRE/pre-load-implicit-cf-updates.ll llvm/test/Transforms/GVN/PRE/pre-load.ll llvm/test/Transforms/GVN/PRE/pre-single-pred.ll llvm/test/Transforms/GVN/PRE/preserve-tbaa.ll llvm/test/Transforms/GVN/PRE/rle-addrspace-cast.ll llvm/test/Transforms/GVN/PRE/rle-semidominated.ll llvm/test/Transforms/GVN/PRE/rle.ll llvm/test/Transforms/GVN/nonescaping.ll llvm/test/Transforms/GVN/pr14166.ll llvm/test/Transforms/GVN/readattrs.ll llvm/test/Transforms/GVN/setjmp.ll llvm/test/Transforms/GVN/tbaa.ll llvm/test/Transforms/GVN/vscale.ll

The following files introduce new uses of undef:

llvm/test/Transforms/GVN/PRE/pre-load-dbg.ll
llvm/test/Transforms/GVN/vscale.ll

Undef is now deprecated and should only be used in the rare cases where no replacement is possible. For example, a load of uninitialized memory yields undef. You should use poison values for placeholders instead.

In tests, avoid using undef and having tests that trigger undefined behavior. If you need an operand with some unimportant value, you can add a new argument to the function and use that instead.

For example, this is considered a bad practice:

define void @fn() {
  ...
  br i1 undef, ...
}

Please use the following instead:

define void @fn(i1 %cond) {
  ...
  br i1 %cond, ...
}

Please refer to the Undefined Behavior Manual for more information.

antoniofrighetto · 2025-10-20T19:30:54Z