[LangRef] Update the TBAA section

[sanjoy]

Summary

Update the TBAA section to mention the struct path TBAA that LLVM
implements today. This is not a proposal or change in semantics -- it
is intended only to document what LLVM already does today.

This is related to https://reviews.llvm.org/D26438 where I've tried to
implement some of the constraints as verifier checks.

[dberris]

docs/LangRef.rst

4610–4611

nit: You probably want to hide this as a comment? Not sure how/whether "TODO:" gets rendered differently from normal text in the final HTML.

[anna]

docs/LangRef.rst

4438

I'm confused here. By definition, scalar type descriptors don't contain other types. So, how can it have another scalar type descriptor as a parent?

4452

Nit: Extra word 'use'.
use type descriptors to describe the *location*

4494–4496

Could you please explain why this is needed?

4537

Is Root an identifier in TBAA?

4585–4605

The mandatory (AccessTy, AccessTy, 0) for the result of GetAliasingLocations(tag3)refers to (CharScalarTy, IntScalarTy, 0) right?

Can we have more than 2 AccessTy?

4586

Nit: extra comma? 'This means that other than `tag3` itself,'

4594–4595

Do we need this here? The representation of access tags explains it in detail.

4614–4615

Could we show the MDString argument for the struct type descriptors in the type system descriptor graph in the above example:

InnerStructTy = {"InnerStructType", (IntScalarTy, 0), (FloatScalarTy, 4)}

4616

'After this name, the struct type...'

[sanjoy]

docs/LangRef.rst

4610–4611

I'll ditch this before checkin -- this was more of a reminder to myself than anything else.

[sanjoy]

• review

[sanjoy]

docs/LangRef.rst

4494–4496

I don't want to get into the details in the LangRef (the section is already quite large now), but this requirement stems from MDNode::getMostGenericTBAA. It takes two struct tags as arguments (StructA, ScalarA, OffsetA) and (StructB, ScalarB, OffsetB) and first "coarsens" them to (ScalarA, ScalarA, OffsetA) and (ScalarB, ScalarB, OffsetB). It then tries to find a common alias tag for (ScalarA, ScalarA, OffsetA) and (ScalarB, ScalarB, OffsetB). The first step is wrong if (ScalarA, ScalarA, OffsetA) does not alias (StructA, ScalarA, OffsetA) (same for the other one) since then that step won't be a "coarsening" any more, and we'd go from aliasing some set of locations to aliasing a different set of locations, and the final result will be wrong.

As an example, say we have:

struct A {
  float f;
  int i;
}

and I want to compute the most generic metadata for the two accesses a.f = .. and a.i = ...

In the correct case, a.f will be tagged with (A, float, 0) and a.i will be tagged with (A, int, 4). getMostGenericTBAA will coarsen these to (float, float, 0) (i.e. any float access) and (int, int 0) (i.e. any int access) and will eventually resolve them to a common (char, char, 0) tag, which in C means it basically aliases with everything since char can be used to access locations of any type. In particular, it aliases with both the tags for a.i and a.f.

Now say we make a mistake, and tag a.i with (A, float, 4) (and a.f is the same). getMostGenericTBAA will resolve these to a common (float, float, 0) tag. However, (float, float, 0) does not alias with the incorrect tag for a.i (by the rules stated in GetAliasingLocations), which is wrong -- we wanted a tag that aliases both a.f and a.i.

4585–4605

These are tuples, and I'm showing the output of GetAliasingLocations

[manmanren]

Thanks for working on this, Sanjoy!

Manman

docs/LangRef.rst

4440

I think we should not call scalar type descriptors as a subset of struct type descriptors. The 2nd field for scalar type descriptors means the parent node. Internally we have an offset field to make alias analysis easy.

4453

Do we actually calculate this set in the source code? It is probably easier to understand if you provide a high-level description instead of the pseudo code. There are descriptions in the comments of TypeBasedAliasAnalysis.cpp.

4561

After this the name --> After the name

4563

The 2N th operand

4565

constant field --> contained field

4577

I actually prefer the descriptions for scalar type descriptors before this patch.
The first field is an identity field. It is a metadata string, which uniquely identifies the type. The second field identifies the type's parent node in the tree. The third field is optional...

Can we talk about scalar type descriptors first, so when talking about struct type descriptors, we can refer to scalar type descriptors?
Such as here ------
The first operand is an `MDString` which, like for scalar type descriptors

[sanjoy]

• address review
• reduce the level of detail to make things less cluttered

[sanjoy]

ping!

[• dberlin]

Hey Sanjoy, I want to accept this, but i can't tell if you've addressed all the comments because they aren't marked done.
In particular, it looks like manman was not happy with some of the wording.
It seems like you reverted that part, but not positive.

[sanjoy]

Marking some inline comments as done.

docs/LangRef.rst

4616

This bit of text is no longer there.

[manmanren]

LGTM. Sorry for the delay,

I wonder where the previous versions of the patch are. The history only lists a single revision.

Manman

[sanjoy]

In D26831#675503, @manmanren wrote:

LGTM. Sorry for the delay,

I wonder where the previous versions of the patch are. The history only lists a single revision.

I am able to see the previous versions:

docs/LangRef.rst

 ^^^^^^^^^^^^^^^^^^^
 
 In LLVM IR, memory does not have types, so LLVM's own type system is not
 suitable for doing TBAA. Instead, metadata is added to the IR to
 describe a type system of a higher level language. This can be used to
 implement typical C/C++ TBAA, but it can also be used to implement
 custom alias analysis behavior for other languages.
 
-The current metadata format is very simple. TBAA metadata nodes have up
-to three fields, e.g.:
+The description of LLVM's TBAA system is broken into two parts.  The first
+part, :ref:`Semantics<tbaa_node_semantics>` talks about the high level
+algorithm, and the second part,
+:ref:`Representation<tbaa_node_representation>` talks about how the various
+entities are literally encoded in the IR as metadata nodes and about some
+syntactic aspects of the scheme.
 
-.. code-block:: llvm
+It is always possible to trace any TBAA node to a "root" TBAA node (details
+in the :ref:`Representation<tbaa_node_representation>` section).  TBAA
+nodes with different roots have an unknown aliasing relationship, and LLVM
+conservatively infers ``MayAlias`` between them.  The rules mentioned in
+this section only pertain to TBAA nodes living under the same root.
+
+.. _tbaa_node_semantics:
+
+Semantics
+"""""""""
+
+The TBAA metadata system, referred to as "struct path TBAA" (not to be
+confused with ``tbaa.struct``), consists of the following high level
+concepts: *Type Descriptors*, further subdivided into scalar type
+descriptors and struct type descriptors; and *Access Tags*.
+
+*Type descriptors* describe the type system of the higher level language
+being compiled.
+
+*Struct type descriptors* denote types that contain a sequence of other
+type descriptors, at known offsets.  These other type descriptors can
+either be struct type descriptors themselves or scalar type descriptors.
+
+*Scalar type descriptors* are a subset of struct type descriptors that
+contain only one type at offset 0, which is either itself a scalar type
+descriptor or the TBAA root.  The latter case denotes a scalar type
+descriptor that does not contain any other type.
+
+*Access tags* are metadata nodes attached to load and store instructions.
+Access tags use type descriptors to describe the *location* being accessed
+in terms of the type system of the higher level language.  Access tags are
+tuples consisting of a base type, an access type and an offset.  The base
+type is a scalar type descriptor or a struct type descriptor, the access
+type is a scalar type descriptor, and the offset is a constant integer.
+
+The access tag, ``(BaseTy, AccessTy, Offset)`` from a load or store
+instruction can be used to compute the set of aliasing access tags by this
+algorithm:
+
+.. code-block:: text
+
+    GetParent(ScalarTy):
+      (Name, Parent) = ScalarTy
+      return Parent
+
+    TraverseIntoField(StructTy, Offset);
+      Let Field be the last (by increasing offset) field in StructTy that
+      begins before or on Offset, and NextOffset be the offset of said
+      Field.
+
+      return (Field, Offset - NextOffset)
+      
+
+    GetAliasingLocations(AccessTag):
+      (BaseTy, AccessTy, Offset) = AccessTag
+      AliasingSet = EmptySet
+      do
+        AliasingSet = AliasingSet Union { (BaseTy, AccessTy, Offset) }
+        if (BaseTy is a Scalar Type)
+          Assert Offset == 0
+          BaseTy = GetParent(BaseTy)
+        else
+          (BaseTy, Offset) = TraverseIntoField(BaseTy, Offset)
+      while Next is not Root
+      return AliasingSet
+
+
+Note that we do not use the ``AccessTy`` component in the algorithm above.
+Today it is used to update TBAA metadata (when transforming the IR requires
+it), but not as part of the aliasing query.
+
+For the updating logic to work, the metadata has to be structured in a way
+that for every access tag ``(BaseTy, AccessTy, Offset)``,
+``GetAliasingLocations((BaseTy, AccessTy, Offset))`` contains ``(AccessTy,
+AccessTy, 0)``.
+
+
+Two memory operations with access tags ``TagA`` and ``TagB`` may alias only
+if either ``(TagB.BaseTy, _, TagB.Offset)`` belongs to
+``GetAliasingLocations(TagA)`` or ``(TagA.BaseTy, _, TagA.Offset)`` belongs
+to ``GetAliasingLocations(TagB)``, where ``_`` stands for any access type.
 
-    !0 = !{ !"an example type tree" }
-    !1 = !{ !"int", !0 }
-    !2 = !{ !"float", !0 }
-    !3 = !{ !"const float", !2, i64 1 }
-
-The first field is an identity field. It can be any value, usually a
-metadata string, which uniquely identifies the type. The most important
-name in the tree is the name of the root node. Two trees with different
-root node names are entirely disjoint, even if they have leaves with
-common names.
-
-The second field identifies the type's parent node in the tree, or is
-null or omitted for a root node. A type is considered to alias all of
-its descendants and all of its ancestors in the tree. Also, a type is
-considered to alias all types in other trees, so that bitcode produced
-from multiple front-ends is handled conservatively.
 
-If the third field is present, it's an integer which if equal to 1
-indicates that the type is "constant" (meaning
+As a concrete example, consider:
+
+.. code-block:: c
+
+    struct Inner {
+      int i;    // offset 0
+      float f;  // offset 4
+    };
+    
+    struct Outer {
+      float f;  // offset 0
+      double d; // offset 4
+      struct Inner inner_a;  // offset 12
+    };
+    
+    void f(struct Outer* outer, struct Inner* inner, float* f, int* i, char* c) {
+      outer->f = 0;            // tag0: (OuterStructTy, FloatScalarTy, 0)
+      outer->d = 0.0;          // tag1: (OuterStructTy, DoubleScalarTy, 4)
+      outer->inner_a.i = 0;    // tag2: (OuterStructTy, IntScalarTy, 12)
+      outer->inner_a.f = 0.0;  // tag3: (OuterStructTy, IntScalarTy, 16)
+      inner->i = 0;            // tag4: (InnerStructTy, IntScalarTy, 0)
+      inner->f = 0.0;          // tag5: (InnerStructTy, FloatScalarTy, 4)
+      *f = 0.0;                // tag6: (FloatScalarTy, FloatScalarTy, 0)
+      *i = 0;                  // tag7: (IntScalarTy, IntScalarTy, 0)
+      *c = 0;                  // tag8: (CharScalarTy, CharScalarTy, 0)
+    }
+
+With the type system descriptor graph as (note that in C and C++, a
+``char`` can be used to access into any type):
+
+.. code-block:: text
+
+    Root = "TBAA Root"
+    CharScalarTy = ("char", Root, 0)
+    FloatScalarTy = ("float", CharScalarTy, 0)
+    DoubleScalarTy = ("double", CharScalarTy, 0)
+    IntScalarTy = ("int", CharScalarTy, 0)
+    InnerStructTy = {"Inner" (IntScalarTy, 0), (FloatScalarTy, 4)}
+    OuterStructTy = {"Outer", (FloatScalarTy, 0), (DoubleScalarTy, 4),
+                     (InnerStructTy, 12)}
+
+
+``GetAliasingLocations(tag3)`` is ``{tag3, tag4, tag7, (CharScalarTy,
+IntScalarTy, 0)}``.  This means that other than ``tag3`` itself, ``tag3``
+aliases ``tag4``, ``tag7`` and ``tag8``, reflecting the fact that
+``inner``, ``i`` and ``c`` could have been set to point into the containing
+``outer`` structure.  Alternatively, ``tag6`` does not alias ``tag3`` since
+neither is ``(FloatScalarTy, _, 0)`` in ``GetAliasingLocations(tag3)``, nor
+is ``(OuterStructTy, _, 16)`` in ``GetAliasingLocations(tag6)`` ``=``
+``{tag6, (CharScalarTy, FloatScalarTy, 0)}``.
+
+.. _tbaa_node_representation:
+
+Representation
+""""""""""""""
+
+The root node of a TBAA type hierarchy is an ``MDNode`` with 0 operands or
+with exactly one ``MDString`` operand.
+
+Struct type descriptors are represented as ``MDNode`` s with an odd number
+of operands greater than 1.  The first operand is an ``MDString`` which,
+like for scalar type descriptors, is for ergonomics -- LLVM only cares that
+it finds an ``MDString`` there.  After this the name, the struct type
+descriptors have a sequence of alternating ``MDNode`` and ``ConstantInt``
+operands.  The 2N + 1 th operand, an ``MDNode`` denotes a contained field,
+and the 2N + 1 th operand, a ``ConstantInt`` is the offset of the said
+constant field.  The offsets must be in non-decreasing order.  We can
+determine the TBAA root a struct type descriptor belongs to by recursing
+into any of its operands till we see a scalar type descriptor, at which
+point the rule for finding the TBAA root for scalar type descriptor
+applies.  It should not matter which operand we recurse into, since they
+should all lead to the same root.
+
+Scalar type descriptors, being a proper subset of struct type descriptors
+have the same representation as struct type descriptors in general.
+However, there is one shorthand for making the representation of scalar
+type descriptors easier: an ``MDNode`` with two operands, the first operand
+being an ``MDString`` and the second operand being another ``MDNode`` is
+treated as having a constant integer 0 as an implicit third operand.  We
+can determine the TBAA root a scalar type descriptor belongs to by
+recursing into this second operand till we see a root node.
+
+The example above, reified into metadata nodes, will look like:
+
+.. code-block:: text
+
+    !0 = !{!"TBAA Root"} ;; Root
+    !1 = !{!"char", !0, i64 0} ;; CharScalarTy
+    ;; Possible shorthand: !1 = !{!"char", !0}
+    !2 = !{!"float", !0, i64 0} ;; FloatScalarTy
+    ;; Possible shorthand: !2 = !{!"float", !0}
+    !3 = !{!"double", !0, i64 0} ;; DoubleScalarTy
+    ;; Possible shorthand: !3 = !{!"double", !0}
+    !4 = !{!"int", !0, i64 0} ;; IntScalarTy
+    ;; Possible shorthand: !4 = !{!"int", !0}
+    !5 = !{!"Inner", !4, i64 0, !2, i64 4} ;; InnerStructTy
+    !6 = !{!"Outer", !2, i64 0, !3, i64 4, !5, 12}
+
+
+Access tags are represented as ``MDNode`` s with either 3 or 4 operands.
+The first operand is an ``MDNode`` pointing to the node representing the
+base type.  The second operand is an ``MDNode`` pointing to the node
+representing the access type.  The third operand is a ``ConstantInt`` that
+states the offset of the access.  If a fourth field is present, it must be
+a ``ConstantInt`` valued at 0 or 1.  If it is 1 then the access tag states
+that the location being accessed is "constant" (meaning
 ``pointsToConstantMemory`` should return true; see `other useful
-AliasAnalysis methods <AliasAnalysis.html#OtherItfs>`_).
+AliasAnalysis methods <AliasAnalysis.html#OtherItfs>`_).  The TBAA root of
+the access type and the base type of an access tag must be the same, and
+that is the TBAA root of the access tag.
 
 '``tbaa.struct``' Metadata
 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 The :ref:`llvm.memcpy <int_memcpy>` is often used to implement
 aggregate assignment operations in C and similar languages, however it
 is defined to copy a contiguous region of memory, which is more than
 strictly necessary for aggregate types which contain holes due to
 padding. Also, it doesn't contain any TBAA information about the fields
 of the aggregate.
 
 ``!tbaa.struct`` metadata can describe which memory subregions in a
 memcpy are padding and what the TBAA tags of the struct are.
 
 The current metadata format is very simple. ``!tbaa.struct`` metadata
 nodes are a list of operands which are in conceptual groups of three.