Index: docs/AliasAnalysis.rst =================================================================== --- docs/AliasAnalysis.rst +++ docs/AliasAnalysis.rst @@ -702,6 +702,12 @@ Memory Dependence Analysis ========================== +.. note:: + + We are currently in the process of migrating things from + ``MemoryDependenceAnalysis`` to :doc:`MemorySSA`. Please try to use + that instead. + If you're just looking to be a client of alias analysis information, consider using the Memory Dependence Analysis interface instead. MemDep is a lazy, caching layer on top of alias analysis that is able to answer the question of Index: docs/MemorySSA.rst =================================================================== --- /dev/null +++ docs/MemorySSA.rst @@ -0,0 +1,301 @@ +========= +MemorySSA +========= + +.. contents:: + :local: + +Introduction +============ + +``MemorySSA`` is an analysis that allows us to cheaply reason about the +interactions between various memory operations. Its goal is to replace +``MemoryDependenceAnalysis`` for most (if not all) use-cases. This is because, +unless you're very careful, use of ``MemoryDependenceAnalysis`` can easily +result in quadratic-time algorithms in LLVM. Additionally, ``MemorySSA`` doesn't +have as many arbitrary limits as ``MemoryDependenceAnalysis``, so you may get +better results, too. + +At a high level, one of the goals of ``MemorySSA`` is to provide an API that +allows the user to quickly find the clobber for a given memory operation. It +also allows the user to walk all memory operations in a ``Function``, without +having to walk every ``Instruction`` in said ``Function``. + +This document goes over how ``MemorySSA`` is structured, and some basic +intuition on how ``MemorySSA`` works. + +A paper on MemorySSA (with notes about how it's implemented in GCC) `can be +found here `_. + + +MemorySSA Structure +=================== + +MemorySSA is a virtual IR. After it's built, ``MemorySSA`` will contain a +structure that maps ``Instruction`` s to ``MemoryAccess`` es, which are +``MemorySSA``'s parallel to LLVM ``Instruction`` s. + +Each ``MemoryAccess`` can be one of three types: + +- ``MemoryPhi`` +- ``MemoryUse`` +- ``MemoryDef`` + +``MemoryPhi`` s are basically ``PhiNode`` s. If at any point we have two (or +more) ``MemoryDef`` s that could flow into a ``BasicBlock``, the block's top +``MemoryAccess`` will be a ``MemoryPhi``. As in LLVM IR, ``MemoryPhi`` s don't +correspond to any concrete operation. As such, you can't look up a ``MemoryPhi`` +with an ``Instruction`` (though we do allow you to do so with a ``BasicBlock``). + +``MemoryUse`` s are operations which don't modify memory, and, if executed +repeatedly, will always hand back the same result. An example of a ``MemoryUse`` +is a ``load``, or a ``readonly`` function call. + +``MemoryDef`` s are operations which may either modify memory, or which may not +hand us a deterministic result. Examples of ``MemoryDef`` s include ``store`` s, +function calls, ``load`` s with ``acquire`` (or higher) ordering, volatile +operations, memory fences, etc. + +Every function that exists has a special ``MemoryDef`` called ``liveOnEntry``. +It dominates every ``MemoryAccess`` in the function that ``MemorySSA`` is being +run on, and implies that we've hit the top of the function. It's the only +``MemoryDef`` that maps to no ``Instruction`` in LLVM IR. + +An example of all of this overlayed on LLVM IR (obtained by running ``opt +-passes='print' -disable-output`` on an ``.ll`` file) is below. When +viewing this example, it may be helpful to view it in terms of clobbers. The +operands of a given ``MemoryAccess`` are all (potential) clobbers of said +MemoryAccess, and the value produced by a ``MemoryAccess`` can act as a clobber +for other ``MemoryAccess`` es. + +.. code-block:: llvm + + define void @foo() { + entry: + %p1 = alloca i8 + %p2 = alloca i8 + %p3 = alloca i8 + ; 1 = MemoryDef(liveOnEntry) + store i8 0, i8* %p3 + br label %while.cond + + while.cond: + ; 6 = MemoryPhi({%0,1},{if.end,4}) + br i1 undef, label %if.then, label %if.else + + if.then: + ; 2 = MemoryDef(6) + store i8 0, i8* %p1 + br label %if.end + + if.else: + ; 3 = MemoryDef(6) + store i8 1, i8* %p2 + br label %if.end + + if.end: + ; 5 = MemoryPhi({if.then,2},{if.then,3}) + ; MemoryUse(5) + %1 = load i8, i8* %p1 + ; 4 = MemoryDef(5) + store i8 2, i8* %p2 + ; MemoryUse(1) + %2 = load i8, i8* %p3 + br label %while.cond + } + +The ``MemorySSA`` IR is located comments that precede the instructions they map +to (if such an instruction exists). For example, ``1 = MemoryDef(liveOnEntry)`` +is a ``MemoryAccess`` (specifically, a ``MemoryDef``), and it describes the LLVM +instruction ``store i8 0, i8* %p3``. Other places in ``MemorySSA`` refer to this +particular ``MemoryDef`` as ``1`` (much like how one can refer to ``load i8, i8* +%p1`` in LLVM with ``%1``). Again, ``MemoryPhi`` s don't correspond to any LLVM +Instruction, so the line directly below a ``MemoryPhi`` isn't special. + +Going from the top down: + +- ``6 = MemoryPhi({%0,1},{if.end,4})`` notes that, when entering ``while.cond``, + the most recent ``MemoryDef`` or ``MemoryPhi`` is either ``liveOnEntry`` or + ``4``. This ``MemoryPhi`` is referred to in the textual IR by the number + ``6``. +- ``2 = MemoryDef(6)`` notes that ``store i8 0, i8* %p1`` is a definition, + and the definition immediately before it is ``6``, or the ``MemoryPhi`` after + ``while.cond``. +- ``3 = MemoryDef(6)`` notes that ``store i8 0, i8* %p2`` is a definition; its + preceding definition is also ``6``. +- ``5 = MemoryPhi({if.then,2},{if.then,3})`` notes that the clobber before + this block could either be ``2`` or ``3``. +- ``MemoryUse(5)`` notes that ``load i8, i8* %p1`` is a use of memory, and that + it's clobbered by ``5``. +- ``4 = MemoryDef(5)`` notes that ``store i8 2, i8* %p2`` is a definition; it's + preceded by ``5``. +- ``MemoryUse(1)`` notes that ``load i8, i8* %p3`` is just a user of memory, + and the last thing that could clobber this use is above ``while.cond`` (e.g. + the store to ``%p3``). + +As an aside, ``MemoryAccess`` is a ``Value`` mostly for convenience; it's not +meant to interact with LLVM IR. + +Design of MemorySSA +=================== + +``MemorySSA`` is an analysis that can be built for any arbitrary function. When +it's built, it does a pass over the function's IR in order to build up its +mapping of ``MemoryAccess`` es. You can then query ``MemorySSA`` for things like +the dominance relation between ``MemoryAccess`` es, and get the ``MemoryAccess`` +for any given ``Instruction`` . + +When ``MemorySSA`` is done building, it also hands you a ``MemorySSAWalker`` +that you can use (see below). + + +The walker +---------- + +A structure that helps ``MemorySSA`` do its job is the ``MemorySSAWalker``, or +the walker, for short. The goal of the walker is to provide answers to clobber +queries beyond what's represented directly by ``MemoryAccess`` es. For example, +given: + +.. code-block:: llvm + + define void @foo() { + %a = alloca i8 + %b = alloca i8 + + ; 1 = MemoryDef(liveOnEntry) + store i8 0, i8* %a + ; 2 = MemoryDef(1) + store i8 0, i8* %b + } + +The store to ``%a`` is clearly not a clobber for the store to ``%b``. It would +be the walker's goal to figure this out, and return ``liveOnEntry`` when queried +for the clobber of ``MemoryAccess`` ``2``. + +By default, ``MemorySSA`` provides a walker that can optimize ``MemoryDef`` s +and ``MemoryUse`` s by consulting alias analysis. Walkers were built to be +flexible, though, so it's entirely reasonable (and expected) to create more +specialized walkers (e.g. one that queries ``GlobalsAA``). + + +Locating clobbers yourself +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +If you choose to make your own walker, you can find the clobber for a +``MemoryAccess`` by walking every ``MemoryDef`` that dominates said +``MemoryAccess``. The structure of ``MemoryDef`` s makes this relatively simple; +they ultimately form a linked list of every clobber that dominates the +``MemoryAccess`` that you're trying to optimize. In other words, the +``definingAccess`` of a ``MemoryDef`` is always the nearest dominating +``MemoryDef`` or ``MemoryPhi`` of said ``MemoryDef``. This is a reason that we +don't optimize ``MemoryDef`` s in the same way that we optimize ``MemoryUse`` s. + + +Use optimization +---------------- + +``MemorySSA`` will optimize some ``MemoryAccess`` es at build-time. +Specifically, we optimize the operand of every ``MemoryUse`` s to point to the +actual clobber of said ``MemoryUse``. This can be seen in the above example; the +second ``MemoryUse`` in ``if.end`` has an operand of ``1``, which is a +``MemoryDef`` from the entry block. + +We don't do a similar optimization for ``MemoryDef`` s for reasons described in +`Locating clobbers yourself`_. + + +Invalidation and updating +------------------------- + +Because ``MemorySSA`` keeps track of LLVM IR, it needs to be updated whenever +the IR is updated. "Update", in this case, includes the addition, deletion, and +motion of IR instructions. The update API is being made on an as-needed basis. + + +Phi placement +^^^^^^^^^^^^^ + +``MemorySSA`` only places ``MemoryPhi`` s where they're actually needed. For +example, consider: + +.. code-block:: llvm + + define void @foo() { + entry: + %p1 = alloca i8 + %p2 = alloca i8 + %p3 = alloca i8 + ; 1 = MemoryDef(liveOnEntry) + store i8 0, i8* %p3 + br label %while.cond + + while.cond: + ; 3 = MemoryPhi({%0,1},{if.end,2}) + br i1 undef, label %if.then, label %if.else + + if.then: + br label %if.end + + if.else: + br label %if.end + + if.end: + ; MemoryUse(1) + %1 = load i8, i8* %p1 + ; 2 = MemoryDef(3) + store i8 2, i8* %p2 + ; MemoryUse(1) + %2 = load i8, i8* %p3 + br label %while.cond + } + +Because we removed the stores from ``if.then`` and ``if.else``, a ``MemoryPhi`` +for ``if.end`` would be pointless, so we don't place one. So, if you need to +place a ``MemoryDef`` in ``if.then`` or ``if.else``, you'll need to also create +a ``MemoryPhi`` for ``if.end``. + +If it turns out that this is a large burden, we can just place ``MemoryPhi`` s +everywhere. Because we have Walkers that are capable of optimizing above said +phis, doing so shouldn't prohibit optimizations. + + +Non-Goals +--------- + +``MemorySSA`` is meant to reason about the relation between memory operations. +It isn't meant to be the single source of truth for all potential memory-related +optimizations. Specifically, care must be taken when trying to use ``MemorySSA`` +to reason about atomic or volatile operations, as in: + +.. code-block:: llvm + + define i8 @foo(i8* %a) { + entry: + br i1 undef, label %if.then, label %if.end + + if.then: + ; 1 = MemoryDef(liveOnEntry) + %0 = load volatile i8, i8* %a + br label %if.end + + if.end: + %av = phi i8 [0, %entry], [%0, %if.then] + ret i8 %av + } + +Going solely by ``MemorySSA``'s analysis, hoisting the ``load`` to ``entry`` may +seem legal. Because it's a volatile load, though, it's not. + + +One partition +------------- + +In literature, ``MemorySSA`` is often partitioned in some way (e.g. by symbolic +memory location). For LLVM, we've chosen to have all of memory be represented by +one massive partition, and use walkers to disambiguate between clobbers and +non-clobbers, because: + +- Partitioning is complicated +- There seems to exist no single incredibly accurate way of doing partitioning + that doesn't take until the heat-death of the universe Index: docs/index.rst =================================================================== --- docs/index.rst +++ docs/index.rst @@ -235,6 +235,7 @@ :hidden: AliasAnalysis + MemorySSA BitCodeFormat BlockFrequencyTerminology BranchWeightMetadata @@ -291,6 +292,9 @@ Information on how to write a new alias analysis implementation or how to use existing analyses. +:doc:`MemorySSA` + Information about the MemorySSA utility in LLVM, as well as how to use it. + :doc:`GarbageCollection` The interfaces source-language compilers should use for compiling GC'd programs.