llvm::Rematerializer

Declared in <llvm/CodeGen/Rematerializer.h>

At the moment this supports rematerializing registers that meet all of the following constraints. 1. The register is virtual. 2. The register is defined within a single region‐‐‐potentially over multiple MIs‐‐‐and isn't used by a MI that is not defining part of the register before its last defining MI. This restriction essentially means that, if the rematerializer only ever rematerializes all the defs of a register together, it can treat all virtual registers as having a "single value" (the one after the last def). Relaxing this restriction would require it to track VNInfos individually rather that virtual registers. 3. All defining instructions are deemed rematerializable by the TII and don't have any physical register use that is both non‐constant and non‐ignorable. 4. The register has at least one non‐debug use that is inside or at a region boundary (see below for what we consider to be a region).

Rematerializable registers (represented by Rematerializer::Reg) form a DAG of their own, with every register having incoming edges from all rematerializable registers which are read by the instruction defining it. It is possible to rematerialize registers with unrematerializable dependencies; however the latter are not considered part of this DAG since their position/identity never change and therefore do not require the same level of tracking.

Each register has a "dependency DAG" which is defined as the subset of nodes in the overall DAG that have at least one path to the register, which is called the "root" register in this context. Semantically, these nodes are the registers which are involved into the computation of the root register i.e., all of its transitive dependencies. We use the term "root" because all paths within the dependency DAG of a register terminate at it; however, there may be multiple paths between a non‐root node and the root node, so a dependency DAG is not always a tree.

The API uses dense unsigned integers starting at 0 to reference rematerializable registers. These indices are immutable i.e., even when registers are deleted their respective integer handle remain valid. Method which perform actual rematerializations should however be assumed to invalidate addresses to Rematerializer::Reg objects.

The rematerializer tracks def/use points of registers based on regions. These are alike the regions the machine scheduler works on. A region is simply a pair on MBB iterators encoding a range of machine instructions. The first iterator (beginning of the region) is inclusive whereas the second iterator (end of the region) is exclusive and can either point to a MBB's end sentinel or an actual MI (not necessarily a terminator). Regions must be non‐empty, cannot overlap, and cannot contain terminators. However, they do not have to cover the whole function.

The API uses dense unsigned integers starting at 0 to reference regions. These map directly to the indices of the corresponding regions in the region vector passed during construction.

The rematerializer supports rematerializing arbitrary complex DAGs of registers to regions where these registers are used, with the option of re‐using non‐root registers or their previous rematerializations instead of rematerializing them again.

Throughout its lifetime, the rematerializer tracks new registers it creates (which are rematerializable by construction) and their relations to other registers. It performs DAG and live interval updates immediately on rematerialization and/or user transfer. Importantly, missing dead flags on partial definitions of unrematerializable registers can yield dead definitions when rematerializing their users. They are deleted to preserve live interval validity. These deletions can cascade to other (un)rematerializable registers that also become dead as a result.

In its nomenclature, the rematerializer differentiates between "original registers" (registers that were present when it analyzed the function) and rematerializations of these original registers. Rematerializations have an "origin" which is the index of the original register they were rematerialized from (transitivity applies; a rematerialization and all of its own rematerializations have the same origin). Semantically, only original registers have rematerializations.

Dealing with sub‐registers is complicated, we have to handle dead‐defs, undef flags, and connected components

Created with MrDocs