================ @@ -33,315 +30,296 @@ This document contains information necessary to successfully implement this interface, use it, and to test both sides. It also explains some of the finer points about what exactly results mean. -``AliasAnalysis`` Class Overview -================================ +## `AliasAnalysis` Class Overview -The `AliasAnalysis <https://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`__ +The [AliasAnalysis](https://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html) class defines the interface that the various alias analysis implementations -should support. This class exports two important enums: ``AliasResult`` and -``ModRefResult`` which represent the result of an alias query or a mod/ref +should support. This class exports two important enums: `AliasResult` and +`ModRefResult` which represent the result of an alias query or a mod/ref query, respectively. -The ``AliasAnalysis`` interface exposes information about memory, represented in +The `AliasAnalysis` interface exposes information about memory, represented in several different ways. In particular, memory objects are represented as a starting address and size, and function calls are represented as the actual -``call`` or ``invoke`` instructions that perform the call. The -``AliasAnalysis`` interface also exposes some helper methods which allow you to +`call` or `invoke` instructions that perform the call. The +`AliasAnalysis` interface also exposes some helper methods which allow you to get mod/ref information for arbitrary instructions. -All ``AliasAnalysis`` interfaces require that in queries involving multiple -values, values which are not :ref:`constants <constants>` are all +All `AliasAnalysis` interfaces require that in queries involving multiple +values, values which are not {ref}`constants <constants>` are all defined within the same function. -Representation of Pointers --------------------------- +### Representation of Pointers -Most importantly, the ``AliasAnalysis`` class provides several methods which are +Most importantly, the `AliasAnalysis` class provides several methods which are used to query whether or not two memory objects alias, whether function calls can modify or read a memory object, etc. For all of these queries, memory objects are represented as a pair of their starting address (a symbolic LLVM -``Value*``) and a static size. +`Value*`) and a static size. Representing memory objects as a starting address and a size is critically important for correct Alias Analyses. For example, consider this (silly, but possible) C code: -.. code-block:: c++ - - int i; - char C[2]; - char A[10]; - /* ... */ - for (i = 0; i != 10; ++i) { - C[0] = A[i]; /* One byte store */ - C[1] = A[9-i]; /* One byte store */ - } - -In this case, the ``basic-aa`` pass will disambiguate the stores to ``C[0]`` and -``C[1]`` because they are accesses to two distinct locations one byte apart, and +```c++ +int i; +char C[2]; +char A[10]; +/* ... */ +for (i = 0; i != 10; ++i) { + C[0] = A[i]; /* One byte store */ + C[1] = A[9-i]; /* One byte store */ +} +``` + +In this case, the `basic-aa` pass will disambiguate the stores to `C[0]` and +`C[1]` because they are accesses to two distinct locations one byte apart, and the accesses are each one byte. In this case, the Loop Invariant Code Motion (LICM) pass can use store motion to remove the stores from the loop. In contrast, the following code: -.. code-block:: c++ - - int i; - char C[2]; - char A[10]; - /* ... */ - for (i = 0; i != 10; ++i) { - ((short*)C)[0] = A[i]; /* Two byte store! */ - C[1] = A[9-i]; /* One byte store */ - } +```c++ +int i; +char C[2]; +char A[10]; +/* ... */ +for (i = 0; i != 10; ++i) { + ((short*)C)[0] = A[i]; /* Two byte store! */ + C[1] = A[9-i]; /* One byte store */ +} +``` In this case, the two stores to C do alias each other, because the access to the -``&C[0]`` element is a two byte access. If size information wasn't available in +`&C[0]` element is a two byte access. If size information wasn't available in the query, even the first case would have to conservatively assume that the accesses alias. -.. _alias: +(alias)= -The ``alias`` method --------------------- +### The `alias` method -The ``alias`` method is the primary interface used to determine whether or not +The `alias` method is the primary interface used to determine whether or not two memory objects alias each other. It takes two memory objects as input and returns MustAlias, PartialAlias, MayAlias, or NoAlias as appropriate. -Like all ``AliasAnalysis`` interfaces, the ``alias`` method requires that either +Like all `AliasAnalysis` interfaces, the `alias` method requires that either the two pointer values be defined within the same function, or at least one of -the values is a :ref:`constant <constants>`. +the values is a {ref}`constant <constants>`. -.. _Must, May, or No: +(Must, May, or No)= -Must, May, and No Alias Responses -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +#### Must, May, and No Alias Responses -The ``NoAlias`` response may be used when there is never an immediate dependence +The `NoAlias` response may be used when there is never an immediate dependence between any memory reference *based* on one pointer and any memory reference *based on* the other. The most obvious example is when the two pointers point to non-overlapping memory ranges. Another is when the two pointers are only ever used for reading memory. Another is when the memory is freed and reallocated between accesses through one pointer and accesses through the other --- in this case, there is a dependence, but it's mediated by the free and reallocation. -An exception to this is with the :ref:`noalias <noalias>` keyword; +An exception to this is with the {ref}`noalias <noalias>` keyword; the "irrelevant" dependencies are ignored. -The ``MayAlias`` response is used whenever the two pointers might refer to the +The `MayAlias` response is used whenever the two pointers might refer to the same object. -The ``PartialAlias`` response is used when the two memory objects are known to +The `PartialAlias` response is used when the two memory objects are known to be overlapping in some way, regardless of whether they start at the same address or not. -The ``MustAlias`` response may only be returned if the two memory objects are -guaranteed to always start at exactly the same location. A ``MustAlias`` +The `MustAlias` response may only be returned if the two memory objects are +guaranteed to always start at exactly the same location. A `MustAlias` response does not imply that the pointers compare equal. -The ``getModRefInfo`` methods ------------------------------ +### The `getModRefInfo` methods -The ``getModRefInfo`` methods return information about whether the execution of +The `getModRefInfo` methods return information about whether the execution of an instruction can read or modify a memory location. Mod/Ref information is always conservative: if an instruction **might** read or write a location, -``ModRef`` is returned. - -The ``AliasAnalysis`` class also provides a ``getModRefInfo`` method for testing -dependencies between function calls. This method takes two call sites (``CS1`` -& ``CS2``), returns ``NoModRef`` if neither call writes to memory read or -written by the other, ``Ref`` if ``CS1`` reads memory written by ``CS2``, -``Mod`` if ``CS1`` writes to memory read or written by ``CS2``, or ``ModRef`` if -``CS1`` might read or write memory written to by ``CS2``. Note that this +`ModRef` is returned. + +The `AliasAnalysis` class also provides a `getModRefInfo` method for testing +dependencies between function calls. This method takes two call sites (`CS1` +& `CS2`), returns `NoModRef` if neither call writes to memory read or +written by the other, `Ref` if `CS1` reads memory written by `CS2`, +`Mod` if `CS1` writes to memory read or written by `CS2`, or `ModRef` if +`CS1` might read or write memory written to by `CS2`. Note that this relation is not commutative. -Other useful ``AliasAnalysis`` methods --------------------------------------- +### Other useful `AliasAnalysis` methods Several other tidbits of information are often collected by various alias analysis implementations and can be put to good use by various clients. -The ``getModRefInfoMask`` method -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +#### The `getModRefInfoMask` method -The ``getModRefInfoMask`` method returns a bound on Mod/Ref information for +The `getModRefInfoMask` method returns a bound on Mod/Ref information for the supplied pointer, based on knowledge about whether the pointer points to -globally-constant memory (for which it returns ``NoModRef``) or -locally-invariant memory (for which it returns ``Ref``). Globally-constant +globally-constant memory (for which it returns `NoModRef`) or +locally-invariant memory (for which it returns `Ref`). Globally-constant memory includes functions, constant global variables, and the null pointer. Locally-invariant memory is memory that we know is invariant for the lifetime of its SSA value, but not necessarily for the life of the program: for example, -the memory pointed to by ``readonly`` ``noalias`` parameters is known-invariant +the memory pointed to by `readonly` `noalias` parameters is known-invariant for the duration of the corresponding function call. Given Mod/Ref information -``MRI`` for a memory location ``Loc``, ``MRI`` can be refined with a statement -like ``MRI &= AA.getModRefInfoMask(Loc);``. Another useful idiom is -``isModSet(AA.getModRefInfoMask(Loc))``; this checks to see if the given +`MRI` for a memory location `Loc`, `MRI` can be refined with a statement +like `MRI &= AA.getModRefInfoMask(Loc);`. Another useful idiom is +`isModSet(AA.getModRefInfoMask(Loc))`; this checks to see if the given location can be modified at all. For convenience, there is also a method -``pointsToConstantMemory(Loc)``; this is synonymous with -``isNoModRef(AA.getModRefInfoMask(Loc))``. +`pointsToConstantMemory(Loc)`; this is synonymous with +`isNoModRef(AA.getModRefInfoMask(Loc))`. -.. _never access memory or only read memory: +(never access memory or only read memory)= -The ``doesNotAccessMemory`` and ``onlyReadsMemory`` methods -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ +#### The `doesNotAccessMemory` and `onlyReadsMemory` methods These methods are used to provide very simple mod/ref information for function -calls. The ``doesNotAccessMemory`` method returns true for a function if the +calls. The `doesNotAccessMemory` method returns true for a function if the analysis can prove that the function never reads or writes to memory, or if the function only reads from constant memory. Functions with this property are side-effect free and only depend on their input arguments, allowing them to be eliminated if they form common subexpressions or be hoisted out of loops. Many -common functions behave this way (e.g., ``sin`` and ``cos``) but many others do -not (e.g., ``acos``, which modifies the ``errno`` variable). +common functions behave this way (e.g., `sin` and `cos`) but many others do +not (e.g., `acos`, which modifies the `errno` variable). -The ``onlyReadsMemory`` method returns true for a function if analysis can prove +The `onlyReadsMemory` method returns true for a function if analysis can prove that (at most) the function only reads from non-volatile memory. Functions with this property are side-effect free, only depending on their input arguments and the state of memory when they are called. This property allows calls to these functions to be eliminated and moved around, as long as there is no store instruction that changes the contents of memory. Note that all functions that -satisfy the ``doesNotAccessMemory`` method also satisfy ``onlyReadsMemory``. +satisfy the `doesNotAccessMemory` method also satisfy `onlyReadsMemory`. -Writing a new ``AliasAnalysis`` Implementation -============================================== +## Writing a new `AliasAnalysis` Implementation Writing a new alias analysis implementation for LLVM is quite straightforward. There are already several implementations that you can use for examples, and the following information should help fill in any details. For example, take a -look at the `various alias analysis implementations`_ included with LLVM. +look at the {ref}`various alias analysis implementations` included with LLVM. -Different Pass styles ---------------------- +### Different Pass styles -The first step is to determine what type of :doc:`LLVM pass <WritingAnLLVMPass>` +The first step is to determine what type of {doc}`LLVM pass <WritingAnLLVMPass>` you need to use for your Alias Analysis. As is the case with most other analyses and transformations, the answer should be fairly obvious from what type of problem you are trying to solve: -#. If you require interprocedural analysis, it should be a ``Pass``. -#. If you are a function-local analysis, subclass ``FunctionPass``. -#. If you don't need to look at the program at all, subclass ``ImmutablePass``. +1. If you require interprocedural analysis, it should be a `Pass`. +1. If you are a function-local analysis, subclass `FunctionPass`. ---------------- boomanaiden154 wrote:
Numbered lists all start with 1? This doesn’t seem right. https://myst-parser.readthedocs.io/en/latest/syntax/typography.html https://github.com/llvm/llvm-project/pull/201465 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
