[MSSA] Doc: Clobbers, more info on Defs / Def chain

[baziotis]

Summary

• Added more info about what we refer as a clobber in MSSA.
• Added more info about MemoryDefs and how there is a single Def chain.
• The doc portrayed MSSA as modeling the heap while it is modeling the whole memory, so I changed the wording to not be heap-specific.

[baziotis]

llvm/docs/MemorySSA.rst

25

A lot of times, the combo "heap memory" is used instead of just "memory". It doesn't seem to me that MSSA is heap-specific,
do I miss something?

[asbirlea]

Thank you for the documentation improvements, much appreciated!
Looks good with a few nits inline.

llvm/docs/MemorySSA.rst

25

It is not heap-specific.

101

s/access/may access

109

s/the use can't be hoisted outside/the use can't be hoisted outside alone.

(It's possible they can be hoisted together; promotion to scalars does this.)

[baziotis]

Thanks for the comments!

• Addressed comments
• I also changed the wording from "heap" to "memory" in all places.

[baziotis]

Ping :) Should I commit?

[george.burgess.iv]

thanks for this!

if someone stamps with nits and you're confident that you've addressed the nits, feel free to commit :)

[baziotis]

In D80000#2055195, @george.burgess.iv wrote:

thanks for this!

if someone stamps with nits and you're confident that you've addressed the nits, feel free to commit :)

Got it, thanks :) I'm committing.

llvm/docs/MemorySSA.rst

 =========
 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 should get
-better results, too.
+better results, too. One common use of ``MemorySSA`` is to quickly find out
+that something definitely cannot happen (for example, reason that a hoist
+out of a loop can't happen).
 
 At a high level, one of the goals of ``MemorySSA`` is to provide an SSA based
 form for memory, complete with def-use and use-def chains, which
 enables users to quickly find may-def and may-uses of memory operations.
 It can also be thought of as a way to cheaply give versions to the complete
-state of heap memory, and associate memory operations with those versions.
+state of memory, and associate memory operations with those versions.
 
 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 <http://www.airs.com/dnovillo/Papers/mem-ssa.pdf>`_. Though, it's
-relatively out-of-date; the paper references multiple heap partitions, but GCC
+relatively out-of-date; the paper references multiple memory partitions, but GCC
 eventually swapped to just using one, like we now have in LLVM.  Like
 GCC's, LLVM's MemorySSA is intraprocedural.
 
 
 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:
 
+- ``MemoryDef``
 - ``MemoryPhi``
 - ``MemoryUse``
-- ``MemoryDef``
+
+``MemoryDef``\ s are operations which may either modify memory, or which
+introduce some kind of ordering constraints. Examples of ``MemoryDef``\ s
+include ``store``\ s, function calls, ``load``\ s with ``acquire`` (or higher)
+ordering, volatile operations, memory fences, etc. A ``MemoryDef``
+always introduces a new version of the entire memory and is linked with a single
+``MemoryDef/MemoryPhi`` which is the version of memory that the new
+version is based on. This implies that there is a *single*
+``Def`` chain that connects all the ``Def``\ s, either directly
+or indireclty. For example in:
+
+.. code-block:: llvm
+  b = MemoryDef(a)
+  c = MemoryDef(b)
+  d = MemoryDef(c)
+
+``d`` is connected directly with ``c`` and indirectly with ``b``.
+This means that ``d`` potentially clobbers (see below) ``c`` *or*
+``b`` *or* both. This in turn implies that without the use of `The walker_`,
+initially every ``MemoryDef`` clobbers every other ``MemoryDef``.
 
 ``MemoryPhi``\ s are ``PhiNode``\ s, but for memory operations. 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, ``BasicBlock``\ s are mapped to ``MemoryPhi``\ s
 inside ``MemorySSA``, whereas ``Instruction``\ s are mapped to ``MemoryUse``\ s
 and ``MemoryDef``\ s.
 
 Note also that in SSA, Phi nodes merge must-reach definitions (that is,
 definitions that *must* be new versions of variables). In MemorySSA, PHI nodes
 merge may-reach definitions (that is, until disambiguated, the versions that
 reach a phi node may or may not clobber a given variable).
 
 ``MemoryUse``\ s are operations which use but don't modify memory. An example of
 a ``MemoryUse`` is a ``load``, or a ``readonly`` function call.
 
-``MemoryDef``\ s are operations which may either modify memory, or which
-introduce some kind of ordering constraints. 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. Use of
 ``liveOnEntry`` implies that the memory being used is either undefined or
 defined before the function begins.
 
 An example of all of this overlaid on LLVM IR (obtained by running ``opt
 -passes='print<memoryssa>' -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. Another useful way of looking at it is in
-terms of heap versions.  In that view, operands of a given
-``MemoryAccess`` are the version of the heap before the operation, and
-if the access produces a value, the value is the new version of the heap
-after the operation.
+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.
+
+If a ``MemoryAccess`` is a *clobber* of another, it means that these two
+``MemoryAccess``\ es may access the same memory. For example, ``x = MemoryDef(y)``
+means that ``x`` potentially modifies memory that ``y`` modifies/constrains
+(or has modified / constrained).
+In the same manner, ``a = MemoryPhi({BB1,b},{BB2,c})`` means that
+anyone that uses ``a`` is accessing memory potentially modified / constrained
+by either ``b`` or ``c`` (or both).  And finally, ``MemoryUse(x)`` means
+that this use accesses memory that ``x`` has modified / constrained
+(as an example, think that if ``x = MemoryDef(...)``
+and ``MemoryUse(x)`` are in the same loop, the use can't
+be hoisted outside alone).
+
+Another useful way of looking at it is in terms of memory versions.
+In that view, operands of a given ``MemoryAccess`` are the version
+of the entire memory before the operation, and if the access produces
+a value (i.e. ``MemoryDef/MemoryPhi``),
+the value is the new version of the memory after the operation.
 
 .. 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})
+    ; 6 = MemoryPhi({entry,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:

 - ``5 = MemoryPhi({if.then,2},{if.else,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
   reaching definition is ``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``). In heap versioning parlance, it really only depends on
-  the heap version 1, and is unaffected by the new heap versions generated since
+  the store to ``%p3``). In memory versioning parlance, it really only depends on
+  the memory version 1, and is unaffected by the new memory versions generated since
   then.
 
 As an aside, ``MemoryAccess`` is a ``Value`` mostly for convenience; it's not
 meant to interact with LLVM IR.
 
 Design of MemorySSA
 ===================
 

 ``MemorySSA`` will optimize some ``MemoryAccess``\ es at build-time.
 Specifically, we optimize the operand of every ``MemoryUse`` 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.  This is done to make walking,
 value numbering, etc, faster and easier.
 
 It is not possible to optimize ``MemoryDef`` in the same way, as we
-restrict ``MemorySSA`` to one heap variable and, thus, one Phi node
+restrict ``MemorySSA`` to one memory variable and, thus, one Phi node
 per block.
 
 
 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

 Design tradeoffs
 ----------------
 
 Precision
 ^^^^^^^^^
 
 ``MemorySSA`` in LLVM deliberately trades off precision for speed.
 Let us think about memory variables as if they were disjoint partitions of the
-heap (that is, if you have one variable, as above, it represents the entire
-heap, and if you have multiple variables, each one represents some
-disjoint portion of the heap)
+memory (that is, if you have one variable, as above, it represents the entire
+memory, and if you have multiple variables, each one represents some
+disjoint portion of the memory)
 
 First, because alias analysis results conflict with each other, and
 each result may be what an analysis wants (IE
 TBAA may say no-alias, and something else may say must-alias), it is
-not possible to partition the heap the way every optimization wants.
+not possible to partition the memory the way every optimization wants.
 Second, some alias analysis results are not transitive (IE A noalias B,
 and B noalias C, does not mean A noalias C), so it is not possible to
 come up with a precise partitioning in all cases without variables to
 represent every pair of possible aliases.  Thus, partitioning
 precisely may require introducing at least N^2 new virtual variables,
 phi nodes, etc.
 
 Each of these variables may be clobbered at multiple def sites.