[Assignment Tracking][1/*] Add initial docs for Assignment Tracking

[Orlando]

Summary

The Assignment Tracking debug-info feature is outlined in this RFC. This first series of patches adds documentation, the changes necessary to start emitting and using the new metadata, and updates clang with an option to enable the feature. Working with the new metadata in the middle and back end will come later. There are still a few rough edges but I'm putting these patches up now hoping to get feedback on the design and implementation from the upstream community.

---

Add a brief document outlining the intent and design.

[jmorse]

Not a major nit, but something occasionally encountered: IMO the word "debug" needs to occur somewhere in the opening paragraph, or even title. The compiler as a whole covers a pretty wide range of topics, and someone stumbling across the page at random might not immediately know that it's about debug-info.

Sounds good; not hitting "accept" just yet until we've waved these patches in the usual directions.

llvm/docs/AssignmentTracking.md

6–8

IMO this could be interpreted quite widely -- I think the point is to indicate that the technique isn't perfectly 100% sound, in which case perhaps we could say "in rare and complicated circumstances indirect assignments might be optimized away without being tracked, but otherwise we make our best effort to track all variable locations". The word "reasonable" does, alas, mean different things to different people.

13

"what we have now" will immediately go stale, how about "to using dbg.declare and dbg.value"

50–58

Probably best to ditch this IMO; or put the 2nd signature first and say "the formal signature in LLVM-IR is <metadata*5>...". That avoids the reader thinking they're reading redundant things.

76–78

I'd suggest fitting the word "node" in here somewhere just to be explicit that this is part of the existing DI metadata hierarchy, rather than some other meta-metadata.

112

asssign -> assign

128

Dunno how the elements below render, but presumably they want capitalization ("Cloning", "Moving" etc).

Also IMO, it's worth moving moving / deleting debug instructions to their own list, so that there's a collection of "things to do to Real instruction" and "things to do to debug instructions", which decomposes a little nicer IMHO, YMMV.

191

I think we've discussed existing limitations elsewhere -- does it make sense to put a few in here as a very high level "TODO" list, as it were? No point if it's a substantial amount of work, but if there's already a list, that could help future readers.

[jryans]

Overall, this looks great! Thanks for writing it up. 😄

Apologies for all of my style nits that follow... 😅

llvm/docs/AssignmentTracking.md

2

Please also link to this new page from some list of pages to make it easier to find, such as UserGuides.rst (most likely both in the page list and in the TOC tree). Search for InstrRefDebugInfo for a recent example of doing this for another Markdown-formatted doc.

5

Nit: When mentioning LLVM (the system, as opposed to a class or namespace) in text, most docs are fairly consistent in spelling it as "LLVM", so it would be good to follow that style here as well. (Apologies if this seems ultra-nitty...! 😅)

18

Does the guide for pass authors need any additions or tweaks to cover this new intrinsic? Since this is currently an experimental feature, perhaps it doesn't make sense merge all your pass-author guidance on Assignment Tracking into that existing doc, but at the very least, a few well-placed links to this doc seem like a good idea to me.

25

Nit: As with "LLVM", use the name "Clang" in text.

27

31

74

80

"use" is not IR syntax, so perhaps normal quotes are better to parallel "refers to" on the next line.

174

178

183

llvm/docs/SourceLevelDebugging.rst

265

AFAIK, the *.rst format needs two ticks for this... (Isn't writing in two document formats fun...?! 🤪)

266

Use ticks around "DIAssignID" here:

``DIAssignID``

270

You should be able to use the following to link the new page (even though it's in Markdown):

See :doc:`AssignmentTracking` for more info.

Also, you are currently pointing to the InstrRefDebugInfo page, but probably you meant your new AssignmentTracking instead...?

(Phabricator wouldn't let me suggest an edit here for some reason... 🤔)

[jryans]

llvm/docs/SourceLevelDebugging.rst

259

I think it would be nice to paste the C++ "signature in practice" over here as well... (The others in this list could use it too, but that's for another patch...)

I don't really think any one is going to make much sense out of just this list of 6 metadatas... (I've never quite followed why this section uses that style...)

[Orlando]

+ Address review comments.

Thank you both for the reviews!

llvm/docs/AssignmentTracking.md

2

Done - thanks for the example. You may notice that the InstrRefDebugInfo entry is conspicuously missing from the diff base, because it's a little old. I'll rebase everything as I start landing thing - I've put the AssignmentTracking references in UserGuides.rst next to where InstrRefDebugInfo comes in latest main.

5

Apologies if this seems ultra-nitty...!

I appreciate the detailed review :-)

18

Good point, I've added a link from HowToUpdateDebugInfo.rst.

76–78

like so?

[jryans]

Looks good overall, thanks! 😄

llvm/docs/AssignmentTracking.md

8

167

[Orlando]

+ Address comments
+ Add TODO list item regarding Poison / Undef values

[Orlando]

+ Minor formatting change. Sorry for the noise.

[Orlando]

I accidentally left off the review link in the patch - landed this in 33c7ae55e729069be754f56c4d4606cdeddd377b. Thanks again for the reviews.

[Orlando]

Follow-up to fix buildbot failure https://lab.llvm.org/buildbot/#/builders/30/builds/27812: fcbf807b55e6c39c09574f2d0be40f58f4140fdf

llvm/docs/AssignmentTracking.md

+# Debug Info Assignment Tracking
+
+Assignment Tracking is an alternative technique for tracking variable location
+debug info through optimisations in LLVM. It provides accurate variable
+locations for assignments where a local variable (or a field of one) is the
+LHS. In rare and complicated circumstances indirect assignments might be
+optimized away without being tracked, but otherwise we make our best effort to
+track all variable locations
+
+The core idea is to track more information about source assignments in order
+and preserve enough information to be able to defer decisions about whether to
+use non-memory locations (register, constant) or memory locations until after
+middle end optimisations have run. This is in opposition to using
+`llvm.dbg.declare` and `llvm.dbg.value`, which is to make the decision for most
+variables early on, which can result in suboptimal variable locations that may
+be either incorrect or incomplete.
+
+A secondary goal of assignment tracking is to cause minimal additional work for
+LLVM pass writers, and minimal disruption to LLVM in general.
+
+## Status and usage
+
+**Status**: Experimental work in progress. Enabling is strongly advised against
+except for development and testing.
+
+**Enable in Clang**: `-Xclang -fexperimental-assignment-tracking`
+
+**Enable in LLVM tools**: `-experimental-assignment-tracking`
+
+## Design and implementation
+
+### Assignment markers: `llvm.dbg.assign`
+
+`llvm.dbg.value`, a conventional debug intrinsic, marks out a position in the
+IR where a variable takes a particular value. Similarly, Assignment Tracking
+marks out the position of assignments with a new intrinsic called
+`llvm.dbg.assign`.
+
+In order to know where in IR it is appropriate to use a memory location for a
+variable, each assignment marker must in some way refer to the store, if any
+(or multiple!), that performs the assignment. That way, the position of the
+store and marker can be considered together when making that choice. Another
+important benefit of referring to the store is that we can then build a two-way
+mapping of stores<->markers that can be used to find markers that need to be
+updated when stores are modified.
+
+An `llvm.dbg.assign` marker that is not linked to any instruction signals that
+the store that performed the assignment has been optimised out, and therefore
+the memory location will not be valid for at least some part of the program.
+
+Here's the `llvm.dbg.assign` signature. Each parameter is wrapped in
+`MetadataAsValue`, and `Value *` type parameters are first wrapped in
+`ValueAsMetadata`:
+
+```
+void @llvm.dbg.assign(Value *Value,
+                      DIExpression *ValueExpression,
+                      DILocalVariable *Variable,
+                      DIAssignID *ID,
+                      Value *Address,
+                      DIExpression *AddressExpression)
+```
+
+The first three parameters look and behave like an `llvm.dbg.value`. `ID` is a
+reference to a store (see next section). `Address` is the destination address
+of the store and it is modified by `AddressExpression`. LLVM currently encodes
+variable fragment information in `DIExpression`s, so as an implementation quirk
+the `FragmentInfo` for `Variable` is contained within `ValueExpression` only.
+
+The formal LLVM-IR signature is:
+```
+void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata)
+```
+
+### Instruction link: `DIAssignID`
+
+`DIAssignID` metadata is the mechanism that is currently used to encode the
+store<->marker link. The metadata node has no operands and all instances are
+`distinct`; equality is checked for by comparing addresses.
+
+`llvm.dbg.assign` intrinsics use a `DIAssignID` metadata node instance as an
+operand. This way it refers to any store-like instruction that has the same
+`DIAssignID` attachment. E.g. For this test.cpp,
+
+```
+int fun(int a) {
+  return a;
+}
+```
+compiled without optimisations:
+```
+$ clang++ test.cpp -o test.ll -emit-llvm -S -g -O0 -Xclang -fexperimental-assignment-tracking
+```
+we get:
+```
+define dso_local noundef i32 @_Z3funi(i32 noundef %a) #0 !dbg !8 {
+entry:
+  %a.addr = alloca i32, align 4, !DIAssignID !13
+  call void @llvm.dbg.assign(metadata i1 undef, metadata !14, metadata !DIExpression(), metadata !13, metadata i32* %a.addr, metadata !DIExpression()), !dbg !15
+  store i32 %a, i32* %a.addr, align 4, !DIAssignID !16
+  call void @llvm.dbg.assign(metadata i32 %a, metadata !14, metadata !DIExpression(), metadata !16, metadata i32* %a.addr, metadata !DIExpression()), !dbg !15
+  %0 = load i32, i32* %a.addr, align 4, !dbg !17
+  ret i32 %0, !dbg !18
+}
+
+...
+!13 = distinct !DIAssignID()
+!14 = !DILocalVariable(name: "a", ...)
+...
+!16 = distinct !DIAssignID()
+```
+
+The first `llvm.dbg.assign` refers to the `alloca` through `!DIAssignID !13`,
+and the second refers to the `store` through `!DIAssignID !16`.
+
+### Store-like instructions
+
+In the absence of a linked `llvm.dbg.assign`, a store to an address that is
+known to be the backing storage for a variable is considered to represent an
+assignment to that variable.
+
+This gives us a safe fall-back in cases where `llvm.dbg.assign` intrinsics have
+been deleted, the `DIAssignID` attachment on the store has been dropped, or the
+optimiser has made a once-indirect store (not tracked with Assignment Tracking)
+direct.
+
+### Middle-end: Considerations for pass-writers
+
+#### Non-debug instruction updates
+
+**Cloning** an instruction: nothing new to do. Cloning automatically clones a
+`DIAssignID` attachment. Multiple instructions may have the same `DIAssignID`
+instruction. In this case, the assignment is considered to take place in
+multiple positions in the program.
+
+**Moving** a non-debug instruction: nothing new to do. Instructions linked to an
+`llvm.dbg.assign` have their initial IR position marked by the position of the
+`llvm.dbg.assign`.
+
+**Deleting** a non-debug instruction: nothing new to do. Simple DSE does not
+require any change; it’s safe to delete an instruction with a `DIAssignID`
+attachment. An `llvm.dbg.assign` that uses a `DIAssignID` that is not attached
+to any instruction indicates that the memory location isn’t valid.
+
+**Merging** stores: In many cases no change is required as `DIAssignID`
+attachments are automatically merged if `combineMetadata` is called. One way or
+another, the `DIAssignID` attachments must be merged such that new store
+becomes linked to all the `llvm.dbg.assign` intrinsics that the merged stores
+were linked to. This can be achieved simply by calling a helper function
+`Instruction::mergeDIAssignID`.
+
+**Inlining** stores: As stores are inlined we generate `llvm.dbg.assign`
+intrinsics and `DIAssignID` attachments as if the stores represent source
+assignments, just like the in frontend. This isn’t perfect, as stores may have
+been moved, modified or deleted before inlining, but it does at least keep the
+information about the variable correct within the non-inlined scope.
+
+**Splitting** stores: SROA and passes that split stores treat `llvm.dbg.assign`
+intrinsics similarly to `llvm.dbg.declare` intrinsics. Clone the
+`llvm.dbg.assign` intrinsics linked to the store, update the FragmentInfo in
+the `ValueExpression`, and give the split stores (and cloned intrinsics) new
+`DIAssignID` attachments each. In other words, treat the split stores as
+separate assignments. For partial DSE (e.g. shortening a memset), we do the
+same except that `llvm.dbg.assign` for the dead fragment gets an `Undef`
+`Address`.
+
+**promoting** allocas and store/loads: `llvm.dbg.assign` intrinsics implicitly
+describe joined values in memory locations at CFG joins, but this is not
+necessarily the case after promoting (or partially promoting) the
+variable. Passes that promote variables are responsible for inserting
+`llvm.dbg.assign` intrinsics after the resultant PHIs generated during
+promotion. `mem2reg` already has to do this (with `llvm.dbg.value`) for
+`llvm.dbg.declare`s. Where a store has no linked intrinsic, the store is
+assumed to represent an assignment for variables stored at the destination
+address.
+
+#### Debug intrinsic updates
+
+**Moving** a debug intrinsic: avoid moving `llvm.dbg.assign` intrinsics where
+possible, as they represent a source-level assignment, whose position in the
+program should not be affected by optimization passes.
+
+**Deleting** a debug intrinsic: Nothing new to do. Just like for conventional
+debug intrinsics, unless it is unreachable, it’s almost always incorrect to
+delete a `llvm.dbg.assign` intrinsic.
+
+### Lowering `llvm.dbg.assign` to MIR
+
+To begin with only SelectionDAG ISel will be supported. `llvm.dbg.assign`
+intrinsics are lowered to MIR `DBG_INSTR_REF` instructions. Before this happens
+we need to decide where it is appropriate to use memory locations and where we
+must use a non-memory location (or no location) for each variable. In order to
+make those decisions we run a standard fixed-point dataflow analysis that makes
+the choice at each instruction, iteratively joining the results for each block.
+
+### TODO list
+
+As this is an experimental work in progress so there are some items we still need
+to tackle:
+
+* The system expects locals to be backed by a local alloca. This isn't always
+  the case - sometimes a pointer to storage is passed into a function
+  (e.g. sret, byval). We need to be able to handle those cases. See
+  llvm/test/DebugInfo/Generic/assignment-tracking/track-assignments.ll and
+  clang/test/CodeGen/assignment-tracking/assignment-tracking.cpp for examples.
+
+* `trackAssignments` doesn't yet work for variables that have their
+  `llvm.dbg.declare` location modified by a `DIExpression`, e.g. when the
+  address of the variable is itself stored in an `alloca` with the
+  `llvm.dbg.declare` using `DIExpression(DW_OP_deref)`. See `indirectReturn` in
+  llvm/test/DebugInfo/Generic/assignment-tracking/track-assignments.ll and in
+  clang/test/CodeGen/assignment-tracking/assignment-tracking.cpp for an
+  example.
+
+* In order to solve the first bullet-point we need to be able to specify that a
+  memory location is available without using a `DIAssignID`. This is because
+  the storage address is not computed by an instruction (it's an argument
+  value) and therefore we have nowhere to put the metadata attachment. To solve
+  this we probably need another marker intrinsic to denote "the variable's
+  stack home is X address" - similar to `llvm.dbg.declare` and `llvm.dbg.addr`
+  except that it needs to compose with `llvm.dbg.assign` intrinsics such that
+  the stack home address is only selected as a location for the variable when
+  the `llvm.dbg.assign` intrinsics agree it should be.
+
+* Given the above (a special "the stack home is X" intrinsic), and the fact
+  that we can only track assignments with fixed offsets and sizes, I think we
+  can probably get rid of the address and address-expression part, since it
+  will always be computable with the info we have.

llvm/docs/HowToUpdateDebugInfo.rst

 a problem, because ``llvm::replaceAllDbgUsesWith`` takes care of inserting the
 necessary conversion operations into the DIExpressions of updated debug uses.
 
 Deleting a MIR-level MachineInstr
 ---------------------------------
 
 TODO
 
+Rules for updating ``DIAssignID`` Attachments
+=============================================
+
+``DIAssignID`` metadata attachments are used by Assignment Tracking, which is
+currently an experimental debug mode.
+
+See :doc:`AssignmentTracking` for how to update them and for more info on
+Assignment Tracking.
+
 How to automatically convert tests into debug info tests
 ========================================================
 
 .. _IRDebugify:
 
 Mutation testing for IR-level transformations
 ---------------------------------------------
 

llvm/docs/SourceLevelDebugging.rst

 description of the variable.  The third argument is a `complex expression
 <LangRef.html#diexpression>`_.
 
 An `llvm.dbg.value` intrinsic describes the *value* of a source variable
 directly, not its address.  Note that the value operand of this intrinsic may
 be indirect (i.e, a pointer to the source variable), provided that interpreting
 the complex expression derives the direct value.
 
+``llvm.dbg.assign``
+^^^^^^^^^^^^^^^^^^
+
+.. code-block:: llvm
+
+  void @llvm.dbg.assign(Value *Value,
+                        DIExpression *ValueExpression,
+                        DILocalVariable *Variable,
+                        DIAssignID *ID,
+                        Value *Address,
+                        DIExpression *AddressExpression)
+
+This intrinsic marks the position in IR where a source assignment occured. It
+encodes the value of the variable. It references the store, if any, that
+performs the assignment, and the destination address.
+
+The first three arguments are the same as for an ``llvm.dbg.value``. The fourth
+argument is a ``DIAssignID`` used to reference a store. The fifth is the
+destination of the store (wrapped as metadata), and the sixth is a `complex
+expression <LangRef.html#diexpression>`_ that modfies it.
+
+The formal LLVM-IR signature is:
+
+.. code-block:: llvm
+
+  void @llvm.dbg.assign(metadata, metadata, metadata, metadata, metadata, metadata)
+
+
+See :doc:`AssignmentTracking` for more info.
+
 Object lifetimes and scoping
 ============================
 
 In many languages, the local variables in functions can have their lifetimes or
 scopes limited to a subset of a function.  In the C family of languages, for
 example, variables are only live (readable and writable) within the source
 block that they are defined in.  In functional languages, values are only
 readable after they have been defined.  Though this is a very obvious concept,

llvm/docs/UserGuides.rst

.. toctree::
    ExtendingLLVM
    GoldPlugin
    HowToBuildOnARM
    HowToBuildWithPGO
    HowToBuildWindowsItaniumPrograms
    HowToCrossCompileBuiltinsOnArm
    HowToCrossCompileLLVM
    HowToUpdateDebugInfo
+   AssignmentTracking
    LinkTimeOptimization
    LoopTerminology
    MarkdownQuickstartTemplate
    MemorySSA
    MergeFunctions
    MCJITDesignAndImplementation
    ORCv2
    OpaquePointers

 
 :doc:`Remarks`
    A reference on the implementation of remarks in LLVM.
 
 :doc:`Source Level Debugging with LLVM <SourceLevelDebugging>`
    This document describes the design and philosophy behind the LLVM
    source-level debugger.
 
+:doc:`Assignment Tracking <AssignmentTracking>`
+   This document explains how LLVM uses assignment tracking to determine
+   variable locations for debug info through IR optimizations.
+
+
 Code Generation
 ---------------
 
 :doc:`WritingAnLLVMBackend`
    Information on how to write LLVM backends for machine targets.
 
 :doc:`CodeGenerator`
    The design and implementation of the LLVM code generator.  Useful if you are