<li><a href="#machinebasicblock">The <tt>MachineBasicBlock</tt>
class</a></li>
<li><a href="#machinefunction">The <tt>MachineFunction</tt> class</a></li>
+ <li><a href="#machineinstrbundle"><tt>MachineInstr Bundles</tt></a></li>
</ul>
</li>
<li><a href="#mc">The "MC" Layer</a>
<li><a href="#regAlloc_builtIn">Built in register allocators</a></li>
</ul></li>
<li><a href="#codeemit">Code Emission</a></li>
+ <li><a href="#vliw_packetizer">VLIW Packetizer</a>
+ <ul>
+ <li><a href="#vliw_mapping">Mapping from instructions to functional
+ units</a></li>
+ <li><a href="#vliw_repr">How the packetization tables are
+ generated and used</a></li>
+ </ul>
+ </li>
</ul>
</li>
<li><a href="#nativeassembler">Implementing a Native Assembler</a></li>
<li><a href="#ppc_prolog">Prolog/Epilog</a></li>
<li><a href="#ppc_dynamic">Dynamic Allocation</a></li>
</ul></li>
+ <li><a href="#ptx">The PTX backend</a></li>
</ul></li>
</ol>
</div>
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="callclobber">Call-clobbered registers</a>
+</h4>
+
+<div>
+
+<p>Some machine instructions, like calls, clobber a large number of physical
+ registers. Rather than adding <code><def,dead></code> operands for
+ all of them, it is possible to use an <code>MO_RegisterMask</code> operand
+ instead. The register mask operand holds a bit mask of preserved registers,
+ and everything else is considered to be clobbered by the instruction. </p>
+
+</div>
+
<!-- _______________________________________________________________________ -->
<h4>
<a name="ssa">Machine code in SSA form</a>
</div>
+<!-- ======================================================================= -->
+<h3>
+ <a name="machineinstrbundle"><tt>MachineInstr Bundles</tt></a>
+</h3>
+
+<div>
+
+<p>LLVM code generator can model sequences of instructions as MachineInstr
+ bundles. A MI bundle can model a VLIW group / pack which contains an
+ arbitrary number of parallel instructions. It can also be used to model
+ a sequential list of instructions (potentially with data dependencies) that
+ cannot be legally separated (e.g. ARM Thumb2 IT blocks).</p>
+
+<p>Conceptually a MI bundle is a MI with a number of other MIs nested within:
+</p>
+
+<div class="doc_code">
+<pre>
+--------------
+| Bundle | ---------
+-------------- \
+ | ----------------
+ | | MI |
+ | ----------------
+ | |
+ | ----------------
+ | | MI |
+ | ----------------
+ | |
+ | ----------------
+ | | MI |
+ | ----------------
+ |
+--------------
+| Bundle | --------
+-------------- \
+ | ----------------
+ | | MI |
+ | ----------------
+ | |
+ | ----------------
+ | | MI |
+ | ----------------
+ | |
+ | ...
+ |
+--------------
+| Bundle | --------
+-------------- \
+ |
+ ...
+</pre>
+</div>
+
+<p> MI bundle support does not change the physical representations of
+ MachineBasicBlock and MachineInstr. All the MIs (including top level and
+ nested ones) are stored as sequential list of MIs. The "bundled" MIs are
+ marked with the 'InsideBundle' flag. A top level MI with the special BUNDLE
+ opcode is used to represent the start of a bundle. It's legal to mix BUNDLE
+ MIs with indiviual MIs that are not inside bundles nor represent bundles.
+</p>
+
+<p> MachineInstr passes should operate on a MI bundle as a single unit. Member
+ methods have been taught to correctly handle bundles and MIs inside bundles.
+ The MachineBasicBlock iterator has been modified to skip over bundled MIs to
+ enforce the bundle-as-a-single-unit concept. An alternative iterator
+ instr_iterator has been added to MachineBasicBlock to allow passes to
+ iterate over all of the MIs in a MachineBasicBlock, including those which
+ are nested inside bundles. The top level BUNDLE instruction must have the
+ correct set of register MachineOperand's that represent the cumulative
+ inputs and outputs of the bundled MIs.</p>
+
+<p> Packing / bundling of MachineInstr's should be done as part of the register
+ allocation super-pass. More specifically, the pass which determines what
+ MIs should be bundled together must be done after code generator exits SSA
+ form (i.e. after two-address pass, PHI elimination, and copy coalescing).
+ Bundles should only be finalized (i.e. adding BUNDLE MIs and input and
+ output register MachineOperands) after virtual registers have been
+ rewritten into physical registers. This requirement eliminates the need to
+ add virtual register operands to BUNDLE instructions which would effectively
+ double the virtual register def and use lists.</p>
+
+</div>
+
</div>
<!-- *********************************************************************** -->
range from 1 to 1023. To see how this numbering is defined for a particular
architecture, you can read the <tt>GenRegisterNames.inc</tt> file for that
architecture. For instance, by
- inspecting <tt>lib/Target/X86/X86GenRegisterNames.inc</tt> we see that the
- 32-bit register <tt>EAX</tt> is denoted by 15, and the MMX register
- <tt>MM0</tt> is mapped to 48.</p>
+ inspecting <tt>lib/Target/X86/X86GenRegisterInfo.inc</tt> we see that the
+ 32-bit register <tt>EAX</tt> is denoted by 43, and the MMX register
+ <tt>MM0</tt> is mapped to 65.</p>
<p>Some architectures contain registers that share the same physical location. A
notable example is the X86 platform. For instance, in the X86 architecture,
bits. These physical registers are marked as <i>aliased</i> in LLVM. Given a
particular architecture, you can check which registers are aliased by
inspecting its <tt>RegisterInfo.td</tt> file. Moreover, the method
- <tt>TargetRegisterInfo::getAliasSet(p_reg)</tt> returns an array containing
+ <tt>MCRegisterInfo::getAliasSet(p_reg)</tt> returns an array containing
all the physical registers aliased to the register <tt>p_reg</tt>.</p>
<p>Physical registers, in LLVM, are grouped in <i>Register Classes</i>.
different register allocators:</p>
<ul>
- <li><i>Linear Scan</i> — <i>The default allocator</i>. This is the
- well-know linear scan register allocator. Whereas the
- <i>Simple</i> and <i>Local</i> algorithms use a direct mapping
- implementation technique, the <i>Linear Scan</i> implementation
- uses a spiller in order to place load and stores.</li>
-
<li><i>Fast</i> — This register allocator is the default for debug
builds. It allocates registers on a basic block level, attempting to keep
values in registers and reusing registers as appropriate.</li>
+ <li><i>Basic</i> — This is an incremental approach to register
+ allocation. Live ranges are assigned to registers one at a time in
+ an order that is driven by heuristics. Since code can be rewritten
+ on-the-fly during allocation, this framework allows interesting
+ allocators to be developed as extensions. It is not itself a
+ production register allocator but is a potentially useful
+ stand-alone mode for triaging bugs and as a performance baseline.
+
+ <li><i>Greedy</i> — <i>The default allocator</i>. This is a
+ highly tuned implementation of the <i>Basic</i> allocator that
+ incorporates global live range splitting. This allocator works hard
+ to minimize the cost of spill code.
+
<li><i>PBQP</i> — A Partitioned Boolean Quadratic Programming (PBQP)
based register allocator. This allocator works by constructing a PBQP
problem representing the register allocation problem under consideration,
solving this using a PBQP solver, and mapping the solution back to a
register assignment.</li>
-
</ul>
<p>The type of register allocator used in <tt>llc</tt> can be chosen with the
<a name="proepicode">Prolog/Epilog Code Insertion</a>
</h3>
+<div>
+
<!-- _______________________________________________________________________ -->
<h4>
<a name="compact_unwind">Compact Unwind</a>
<p>The compact unwind encoding is a 32-bit value, which is encoded in an
architecture-specific way. It specifies which registers to restore and from
- where, and how to unwind out of the funciton. When the linker creates a final
+ where, and how to unwind out of the function. When the linker creates a final
linked image, it will create a <code>__TEXT,__unwind_info</code>
section. This section is a small and fast way for the runtime to access
unwind info for any given function. If we emit compact unwind info for the
</div>
+</div>
+
<!-- ======================================================================= -->
<h3>
<a name="latemco">Late Machine Code Optimizations</a>
</div>
+<!-- ======================================================================= -->
+<h3>
+ <a name="vliw_packetizer">VLIW Packetizer</a>
+</h3>
+
+<div>
+
+<p>In a Very Long Instruction Word (VLIW) architecture, the compiler is
+ responsible for mapping instructions to functional-units available on
+ the architecture. To that end, the compiler creates groups of instructions
+ called <i>packets</i> or <i>bundles</i>. The VLIW packetizer in LLVM is
+ a target-independent mechanism to enable the packetization of machine
+ instructions.</p>
+
+<!-- _______________________________________________________________________ -->
+
+<h4>
+ <a name="vliw_mapping">Mapping from instructions to functional units</a>
+</h4>
+
+<div>
+
+<p>Instructions in a VLIW target can typically be mapped to multiple functional
+units. During the process of packetizing, the compiler must be able to reason
+about whether an instruction can be added to a packet. This decision can be
+complex since the compiler has to examine all possible mappings of instructions
+to functional units. Therefore to alleviate compilation-time complexity, the
+VLIW packetizer parses the instruction classes of a target and generates tables
+at compiler build time. These tables can then be queried by the provided
+machine-independent API to determine if an instruction can be accommodated in a
+packet.</p>
+</div>
+
+<!-- ======================================================================= -->
+<h4>
+ <a name="vliw_repr">
+ How the packetization tables are generated and used
+ </a>
+</h4>
+
+<div>
+
+<p>The packetizer reads instruction classes from a target's itineraries and
+creates a deterministic finite automaton (DFA) to represent the state of a
+packet. A DFA consists of three major elements: inputs, states, and
+transitions. The set of inputs for the generated DFA represents the instruction
+being added to a packet. The states represent the possible consumption
+of functional units by instructions in a packet. In the DFA, transitions from
+one state to another occur on the addition of an instruction to an existing
+packet. If there is a legal mapping of functional units to instructions, then
+the DFA contains a corresponding transition. The absence of a transition
+indicates that a legal mapping does not exist and that the instruction cannot
+be added to the packet.</p>
+
+<p>To generate tables for a VLIW target, add <i>Target</i>GenDFAPacketizer.inc
+as a target to the Makefile in the target directory. The exported API provides
+three functions: <tt>DFAPacketizer::clearResources()</tt>,
+<tt>DFAPacketizer::reserveResources(MachineInstr *MI)</tt>, and
+<tt>DFAPacketizer::canReserveResources(MachineInstr *MI)</tt>. These functions
+allow a target packetizer to add an instruction to an existing packet and to
+check whether an instruction can be added to a packet. See
+<tt>llvm/CodeGen/DFAPacketizer.h</tt> for more information.</p>
+
+</div>
+
+</div>
+
</div>
<!-- *********************************************************************** -->
<tr>
<th>Feature</th>
<th>ARM</th>
- <th>Alpha</th>
- <th>Blackfin</th>
<th>CellSPU</th>
+ <th>Hexagon</th>
<th>MBlaze</th>
<th>MSP430</th>
<th>Mips</th>
<th>PTX</th>
<th>PowerPC</th>
<th>Sparc</th>
- <th>SystemZ</th>
<th>X86</th>
<th>XCore</th>
</tr>
<tr>
<td><a href="#feat_reliable">is generally reliable</a></td>
<td class="yes"></td> <!-- ARM -->
- <td class="unknown"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="yes"></td> <!-- Hexagon -->
<td class="no"></td> <!-- MBlaze -->
<td class="unknown"></td> <!-- MSP430 -->
- <td class="no"></td> <!-- Mips -->
+ <td class="yes"></td> <!-- Mips -->
<td class="no"></td> <!-- PTX -->
<td class="yes"></td> <!-- PowerPC -->
<td class="yes"></td> <!-- Sparc -->
- <td class="unknown"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="unknown"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_asmparser">assembly parser</a></td>
<td class="no"></td> <!-- ARM -->
- <td class="no"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="no"></td> <!-- Hexagon -->
<td class="yes"></td> <!-- MBlaze -->
<td class="no"></td> <!-- MSP430 -->
<td class="no"></td> <!-- Mips -->
<td class="no"></td> <!-- PTX -->
<td class="no"></td> <!-- PowerPC -->
<td class="no"></td> <!-- Sparc -->
- <td class="no"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="no"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_disassembler">disassembler</a></td>
<td class="yes"></td> <!-- ARM -->
- <td class="no"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="no"></td> <!-- Hexagon -->
<td class="yes"></td> <!-- MBlaze -->
<td class="no"></td> <!-- MSP430 -->
<td class="no"></td> <!-- Mips -->
<td class="no"></td> <!-- PTX -->
<td class="no"></td> <!-- PowerPC -->
<td class="no"></td> <!-- Sparc -->
- <td class="no"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="no"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_inlineasm">inline asm</a></td>
<td class="yes"></td> <!-- ARM -->
- <td class="unknown"></td> <!-- Alpha -->
- <td class="yes"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="yes"></td> <!-- Hexagon -->
<td class="yes"></td> <!-- MBlaze -->
<td class="unknown"></td> <!-- MSP430 -->
<td class="no"></td> <!-- Mips -->
<td class="unknown"></td> <!-- PTX -->
<td class="yes"></td> <!-- PowerPC -->
<td class="unknown"></td> <!-- Sparc -->
- <td class="unknown"></td> <!-- SystemZ -->
- <td class="yes"><a href="#feat_inlineasm_x86">*</a></td> <!-- X86 -->
+ <td class="yes"></td> <!-- X86 -->
<td class="unknown"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_jit">jit</a></td>
<td class="partial"><a href="#feat_jit_arm">*</a></td> <!-- ARM -->
- <td class="no"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="no"></td> <!-- Hexagon -->
<td class="no"></td> <!-- MBlaze -->
<td class="unknown"></td> <!-- MSP430 -->
- <td class="no"></td> <!-- Mips -->
+ <td class="yes"></td> <!-- Mips -->
<td class="unknown"></td> <!-- PTX -->
<td class="yes"></td> <!-- PowerPC -->
<td class="unknown"></td> <!-- Sparc -->
- <td class="unknown"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="unknown"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_objectwrite">.o file writing</a></td>
<td class="no"></td> <!-- ARM -->
- <td class="no"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="no"></td> <!-- Hexagon -->
<td class="yes"></td> <!-- MBlaze -->
<td class="no"></td> <!-- MSP430 -->
<td class="no"></td> <!-- Mips -->
<td class="no"></td> <!-- PTX -->
<td class="no"></td> <!-- PowerPC -->
<td class="no"></td> <!-- Sparc -->
- <td class="no"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="no"></td> <!-- XCore -->
</tr>
<tr>
<td><a href="#feat_tailcall">tail calls</a></td>
<td class="yes"></td> <!-- ARM -->
- <td class="unknown"></td> <!-- Alpha -->
- <td class="no"></td> <!-- Blackfin -->
<td class="no"></td> <!-- CellSPU -->
+ <td class="yes"></td> <!-- Hexagon -->
<td class="no"></td> <!-- MBlaze -->
<td class="unknown"></td> <!-- MSP430 -->
<td class="no"></td> <!-- Mips -->
<td class="unknown"></td> <!-- PTX -->
<td class="yes"></td> <!-- PowerPC -->
<td class="unknown"></td> <!-- Sparc -->
- <td class="unknown"></td> <!-- SystemZ -->
<td class="yes"></td> <!-- X86 -->
<td class="unknown"></td> <!-- XCore -->
</tr>
+<tr>
+ <td><a href="#feat_segstacks">segmented stacks</a></td>
+ <td class="no"></td> <!-- ARM -->
+ <td class="no"></td> <!-- CellSPU -->
+ <td class="no"></td> <!-- Hexagon -->
+ <td class="no"></td> <!-- MBlaze -->
+ <td class="no"></td> <!-- MSP430 -->
+ <td class="no"></td> <!-- Mips -->
+ <td class="no"></td> <!-- PTX -->
+ <td class="no"></td> <!-- PowerPC -->
+ <td class="no"></td> <!-- Sparc -->
+ <td class="partial"><a href="#feat_segstacks_x86">*</a></td> <!-- X86 -->
+ <td class="no"></td> <!-- XCore -->
+</tr>
+
</table>
<p>This box indicates whether the target supports most popular inline assembly
constraints and modifiers.</p>
-<p id="feat_inlineasm_x86">X86 lacks reliable support for inline assembly
-constraints relating to the X86 floating point stack.</p>
-
</div>
<!-- _______________________________________________________________________ -->
</div>
+<!-- _______________________________________________________________________ -->
+<h4 id="feat_segstacks">Segmented Stacks</h4>
+
+<div>
+
+<p>This box indicates whether the target supports segmented stacks. This
+replaces the traditional large C stack with many linked segments. It
+is compatible with the <a href="http://gcc.gnu.org/wiki/SplitStacks">gcc
+implementation</a> used by the Go front end.</p>
+
+<p id="feat_segstacks_x86">Basic support exists on the X86 backend. Currently
+vararg doesn't work and the object files are not marked the way the gold
+linker expects, but simple Go programs can be built by dragonegg.</p>
+
+</div>
+
</div>
<!-- ======================================================================= -->
</div>
+</div>
+
+<!-- ======================================================================= -->
+<h3>
+ <a name="ptx">The PTX backend</a>
+</h3>
+
+<div>
+
+<p>The PTX code generator lives in the lib/Target/PTX directory. It is
+ currently a work-in-progress, but already supports most of the code
+ generation functionality needed to generate correct PTX kernels for
+ CUDA devices.</p>
+
+<p>The code generator can target PTX 2.0+, and shader model 1.0+. The
+ PTX ISA Reference Manual is used as the primary source of ISA
+ information, though an effort is made to make the output of the code
+ generator match the output of the NVidia nvcc compiler, whenever
+ possible.</p>
+
+<p>Code Generator Options:</p>
+<table border="1" cellspacing="0">
+ <tr>
+ <th>Option</th>
+ <th>Description</th>
+ </tr>
+ <tr>
+ <td><code>double</code></td>
+ <td align="left">If enabled, the map_f64_to_f32 directive is
+ disabled in the PTX output, allowing native double-precision
+ arithmetic</td>
+ </tr>
+ <tr>
+ <td><code>no-fma</code></td>
+ <td align="left">Disable generation of Fused-Multiply Add
+ instructions, which may be beneficial for some devices</td>
+ </tr>
+ <tr>
+ <td><code>smxy / computexy</code></td>
+ <td align="left">Set shader model/compute capability to x.y,
+ e.g. sm20 or compute13</td>
+ </tr>
+</table>
+
+<p>Working:</p>
+<ul>
+ <li>Arithmetic instruction selection (including combo FMA)</li>
+ <li>Bitwise instruction selection</li>
+ <li>Control-flow instruction selection</li>
+ <li>Function calls (only on SM 2.0+ and no return arguments)</li>
+ <li>Addresses spaces (0 = global, 1 = constant, 2 = local, 4 =
+ shared)</li>
+ <li>Thread synchronization (bar.sync)</li>
+ <li>Special register reads ([N]TID, [N]CTAID, PMx, CLOCK, etc.)</li>
+</ul>
+
+<p>In Progress:</p>
+<ul>
+ <li>Robust call instruction selection</li>
+ <li>Stack frame allocation</li>
+ <li>Device-specific instruction scheduling optimizations</li>
+</ul>
+
+
</div>
</div>
projects / oota-llvm.git / blobdiff