[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

4556–4557

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

4507

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?

4521

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

4522–4551

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

Can we have more than 2 AccessTy?

4523

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

4531–4532

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

4551–4552

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)}

4553

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

4563–4565

Could you please explain why this is needed?

4606

Is Root an identifier in TBAA?

[sanjoy]

docs/LangRef.rst

4556–4557

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

[sanjoy]

• review

[sanjoy]

docs/LangRef.rst

4522–4551

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

4563–4565

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.

[manmanren]

Thanks for working on this, Sanjoy!

Manman

docs/LangRef.rst

4504

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.

4517

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.

4625

After this the name --> After the name

4627

The 2N th operand

4629

constant field --> contained field

4641

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

4553

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

.. code-block:: text
 
    !2 = !DIMacroFile(macinfo: DW_MACINFO_start_file, line: 7, file: !2,
                      nodes: !3)
 
 '``tbaa``' Metadata
 ^^^^^^^^^^^^^^^^^^^
 
 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.:
+suitable for doing type based alias analysis (TBAA). Instead, metadata is
+added to the IR to describe a type system of a higher level language. This
+can be used to implement C/C++ strict type aliasing rules, but it can also
+be used to implement custom alias analysis behavior for other languages.
+
+This description of LLVM's TBAA system is broken into two parts:
+:ref:`Semantics<tbaa_node_semantics>` talks about high level issues, and
+:ref:`Representation<tbaa_node_representation>` talks about the metadata
+encoding of various entities.
+
+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.  **Scalar type descriptors** describe types that do not
+contain other types.  Each scalar type has a parent type, which must also
+be a scalar type or the TBAA root.  Via this parent relation, scalar types
+within a TBAA root form a tree.  **Struct type descriptors** denote types
+that contain a sequence of other type descriptors, at known offsets.  These
+contained type descriptors can either be struct type descriptors themselves
+or scalar type descriptors.
+
+**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)`` can describe one of two
+things:
+
+ * If ``BaseTy`` is a struct type, the tag describes a memory access (load
+   or store) of a value of type ``AccessTy`` contained in the struct type
+   ``BaseTy`` at offset ``Offset``.
+
+ * If ``BaseTy`` is a scalar type, ``Offset`` must be 0 and ``BaseTy`` and
+   ``AccessTy`` must be the same; and the access tag describes a scalar
+   access with scalar type ``AccessTy``.
+
+We first define an ``ImmediateParent`` relation on ``(BaseTy, Offset)``
+tuples this way:
+
+ * If ``BaseTy`` is a scalar type then ``ImmediateParent(BaseTy, 0)`` is
+   ``(ParentTy, 0)`` where ``ParentTy`` is the parent of the scalar type as
+   described in the TBAA metadata.  ``ImmediateParent(BaseTy, Offset)`` is
+   undefined if ``Offset`` is non-zero.
+
+ * If ``BaseTy`` is a struct type then ``ImmediateParent(BaseTy, Offset)``
+   is ``(NewTy, NewOffset)`` where ``NewTy`` is the type contained in
+   ``BaseTy`` at offset ``Offset`` and ``NewOffset`` is ``Offset`` adjusted
+   to be relative within that inner type.
+
+A memory access with an access tag ``(BaseTy1, AccessTy1, Offset1)``
+aliases a memory access with an access tag ``(BaseTy2, AccessTy2,
+Offset2)`` if either ``(BaseTy1, Offset1)`` is reachable from ``(Base2,
+Offset2)`` via the ``Parent`` relation or vice versa.
 
-.. code-block:: llvm
+As a concrete example, the type descriptor graph for the following program
+
+.. 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->inner_a.i = 0;    // tag1: (OuterStructTy, IntScalarTy, 12)
+      outer->inner_a.f = 0.0;  // tag2: (OuterStructTy, IntScalarTy, 16)
+      *f = 0.0;                // tag3: (FloatScalarTy, FloatScalarTy, 0)
+    }
+
+is (note that in C and C++, ``char`` can be used to access any arbitrary
+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)}
+
+
+with (e.g.) ``ImmediateParent(OuterStructTy, 12)`` = ``(InnerStructTy,
+0)``, ``ImmediateParent(InnerStructTy, 0)`` = ``(IntScalarTy, 0)``, and
+``ImmediateParent(IntScalarTy, 0)`` = ``(CharScalarTy, 0)``.
+
+.. _tbaa_node_representation:
+
+Representation
+""""""""""""""
 
-    !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.
+The root node of a TBAA type hierarchy is an ``MDNode`` with 0 operands or
+with exactly one ``MDString`` operand.
 
-If the third field is present, it's an integer which if equal to 1
-indicates that the type is "constant" (meaning
+Scalar type descriptors are represented as an ``MDNode`` s with two
+operands.  The first operand is an ``MDString`` denoting the name of the
+struct type.  LLVM does not assign meaning to the value of this operand, it
+only cares about it being an ``MDString``.  The second operand is an
+``MDNode`` which points to the parent for said scalar type descriptor,
+which is either another scalar type descriptor or the TBAA root.  Scalar
+type descriptors can have an optional third argument, but that must be the
+constant integer zero.
+
+Struct type descriptors are represented as ``MDNode`` s with an odd number
+of operands greater than 1.  The first operand is an ``MDString`` denoting
+the name of the struct type.  Like in scalar type descriptors the actual
+value of this name operand is irrelevant to LLVM.  After the name operand,
+the struct type descriptors have a sequence of alternating ``MDNode`` and
+``ConstantInt`` operands.  With N starting from 1, the 2N - 1 th operand,
+an ``MDNode``, denotes a contained field, and the 2N th operand, a
+``ConstantInt``, is the offset of the said contained field.  The offsets
+must be in non-decreasing order.
+
+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.
 For each group of three, the first operand gives the byte offset of a
 field in bytes, the second gives its size in bytes, and the third gives
 its tbaa tag. e.g.:

 When evaluating an aliasing query, if for some domain, the set
 of scopes with that domain in one instruction's ``alias.scope`` list is a
 subset of (or equal to) the set of scopes for that domain in another
 instruction's ``noalias`` list, then the two memory accesses are assumed not to
 alias.
 
 Because scopes in one domain don't affect scopes in other domains, separate
 domains can be used to compose multiple independent noalias sets.  This is
 used for example during inlining.  As the noalias function parameters are
 turned into noalias scope metadata, a new domain is used every time the
 function is inlined.
 
 The metadata identifying each domain is itself a list containing one or two
 entries. The first entry is the name of the domain. Note that if the name is a
 string then it can be combined across functions and translation units. A
 self-reference can be used to create globally unique domain names. A
 descriptive string may optionally be provided as a second list entry.
 
 The metadata identifying each scope is also itself a list containing two or
 three entries. The first entry is the name of the scope. Note that if the name
 is a string then it can be combined across functions and translation units. A
 self-reference can be used to create globally unique scope names. A metadata
 reference to the scope's domain is the second entry. A descriptive string may
 optionally be provided as a third list entry.
 
 For example,
 
 .. code-block:: llvm
 
     ; Two scope domains:
     !0 = !{!0}
     !1 = !{!1}
 
     ; Some scopes in these domains:
     !2 = !{!2, !0}
     !3 = !{!3, !0}
     !4 = !{!4, !1}
 
     ; Some scope lists:
     !5 = !{!4} ; A list containing only scope !4
     !6 = !{!4, !3, !2}
     !7 = !{!3}
 
     ; These two instructions don't alias:
     %0 = load float, float* %c, align 4, !alias.scope !5
     store float %0, float* %arrayidx.i, align 4, !noalias !5
 
     ; These two instructions also don't alias (for domain !1, the set of scopes
     ; in the !alias.scope equals that in the !noalias list):
     %2 = load float, float* %c, align 4, !alias.scope !5
     store float %2, float* %arrayidx.i2, align 4, !noalias !6