Checks memory dependences among accesses to the same underlying object.
Synopsis
Declared in <llvm/Analysis/LoopAccessAnalysis.h>
class MemoryDepChecker;Description
Determines whether vectorization is legal and at which vectorization factor.
Note: This class will compute a conservative dependence for access to different underlying pointers. Clients, such as the loop vectorizer, will sometimes deal these potential dependencies by emitting runtime checks.
We use the ScalarEvolution framework to symbolically evalutate access functions pairs. Since we currently don't restructure the loop we can rely on the program order of memory accesses to determine their safety. At the moment we will only deem accesses as safe for: * A negative constant distance assuming program order.
Safe: tmp = a[i + 1]; OR a[i + 1]= x; a[i]= tmp; y = a[i];
The latter case is safe because later checks guarantuee that there can't be a cycle through a phi node (that is, we check that "x" and "y" is not the same variable: a header phi can only be an induction or a reduction, a reduction can't have a memory sink, an induction can't have a memory source). This is important and must not be violated (or we have to resort to checking for cycles through memory).
* A positive constant distance assuming program order that is bigger than the biggest memory access.
tmp = a[i]OR b[i]= x a[i+2]= tmp y = b[i+2];
Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively.
* Zero distances and all accesses have the same size.
Types
Name |
Description |
Dependece between memory access instructions. |
Type Aliases
Name |
Description |
Set of potential dependent memory accesses. |
|
Memory access identified by pointer and whether it is a write. |
Enums
Name |
Description |
Type to keep track of the status of the dependence check. The order of the elements is important and has to be from most permissive to least permissive. |
Member Functions
Name |
Description |
|
Construct a dependence checker for loop |
Register the location (instructions are given increasing numbers) of a write access. |
|
Check whether the dependencies between the accesses are safe, and records the dependence information in Dependences if so. |
|
Clear the recorded dependence list. |
|
Generate a mapping between the memory instructions and their indices according to program order. |
|
Return the assumption cache used by this checker. |
|
Return the dominator tree used by this checker. |
|
Returns the memory dependences. If null is returned we exceeded the MaxDependences threshold and this information is not available. |
|
Return the innermost loop being checked. |
|
Find the set of instructions that read or write via |
|
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of the element in bits. |
|
The vector of memory access instructions. The indices are used as instruction identifiers in the Dependence class. |
|
Return the program order indices for the access location (Ptr, IsWrite). Returns an empty ArrayRef if there are no accesses for the location. |
|
Return the cache of expanded pointer start/end bounds. |
|
Return safe power‐of‐2 number of elements, which do not prevent store‐load forwarding, multiplied by the size of the elements in bits. |
|
Return true if there are no store‐load forwarding dependencies. |
|
Return true if the number of elements that are safe to operate on simultaneously is not bounded. |
|
No memory dependence was encountered that would inhibit vectorization. |
|
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array access check. |
Created with MrDocs