|
150
|
1 ==========================================
|
|
|
2 The LLVM Target-Independent Code Generator
|
|
|
3 ==========================================
|
|
|
4
|
|
|
5 .. role:: raw-html(raw)
|
|
|
6 :format: html
|
|
|
7
|
|
|
8 .. raw:: html
|
|
|
9
|
|
|
10 <style>
|
|
|
11 .unknown { background-color: #C0C0C0; text-align: center; }
|
|
|
12 .unknown:before { content: "?" }
|
|
|
13 .no { background-color: #C11B17 }
|
|
|
14 .no:before { content: "N" }
|
|
|
15 .partial { background-color: #F88017 }
|
|
|
16 .yes { background-color: #0F0; }
|
|
|
17 .yes:before { content: "Y" }
|
|
|
18 .na { background-color: #6666FF; }
|
|
|
19 .na:before { content: "N/A" }
|
|
|
20 </style>
|
|
|
21
|
|
|
22 .. contents::
|
|
|
23 :local:
|
|
|
24
|
|
|
25 .. warning::
|
|
|
26 This is a work in progress.
|
|
|
27
|
|
|
28 Introduction
|
|
|
29 ============
|
|
|
30
|
|
|
31 The LLVM target-independent code generator is a framework that provides a suite
|
|
|
32 of reusable components for translating the LLVM internal representation to the
|
|
|
33 machine code for a specified target---either in assembly form (suitable for a
|
|
|
34 static compiler) or in binary machine code format (usable for a JIT
|
|
|
35 compiler). The LLVM target-independent code generator consists of six main
|
|
|
36 components:
|
|
|
37
|
|
|
38 1. `Abstract target description`_ interfaces which capture important properties
|
|
|
39 about various aspects of the machine, independently of how they will be used.
|
|
|
40 These interfaces are defined in ``include/llvm/Target/``.
|
|
|
41
|
|
|
42 2. Classes used to represent the `code being generated`_ for a target. These
|
|
|
43 classes are intended to be abstract enough to represent the machine code for
|
|
|
44 *any* target machine. These classes are defined in
|
|
|
45 ``include/llvm/CodeGen/``. At this level, concepts like "constant pool
|
|
|
46 entries" and "jump tables" are explicitly exposed.
|
|
|
47
|
|
|
48 3. Classes and algorithms used to represent code at the object file level, the
|
|
|
49 `MC Layer`_. These classes represent assembly level constructs like labels,
|
|
|
50 sections, and instructions. At this level, concepts like "constant pool
|
|
|
51 entries" and "jump tables" don't exist.
|
|
|
52
|
|
|
53 4. `Target-independent algorithms`_ used to implement various phases of native
|
|
|
54 code generation (register allocation, scheduling, stack frame representation,
|
|
|
55 etc). This code lives in ``lib/CodeGen/``.
|
|
|
56
|
|
|
57 5. `Implementations of the abstract target description interfaces`_ for
|
|
|
58 particular targets. These machine descriptions make use of the components
|
|
|
59 provided by LLVM, and can optionally provide custom target-specific passes,
|
|
|
60 to build complete code generators for a specific target. Target descriptions
|
|
|
61 live in ``lib/Target/``.
|
|
|
62
|
|
|
63 6. The target-independent JIT components. The LLVM JIT is completely target
|
|
|
64 independent (it uses the ``TargetJITInfo`` structure to interface for
|
|
|
65 target-specific issues. The code for the target-independent JIT lives in
|
|
|
66 ``lib/ExecutionEngine/JIT``.
|
|
|
67
|
|
|
68 Depending on which part of the code generator you are interested in working on,
|
|
|
69 different pieces of this will be useful to you. In any case, you should be
|
|
|
70 familiar with the `target description`_ and `machine code representation`_
|
|
|
71 classes. If you want to add a backend for a new target, you will need to
|
|
|
72 `implement the target description`_ classes for your new target and understand
|
|
|
73 the :doc:`LLVM code representation <LangRef>`. If you are interested in
|
|
|
74 implementing a new `code generation algorithm`_, it should only depend on the
|
|
|
75 target-description and machine code representation classes, ensuring that it is
|
|
|
76 portable.
|
|
|
77
|
|
|
78 Required components in the code generator
|
|
|
79 -----------------------------------------
|
|
|
80
|
|
|
81 The two pieces of the LLVM code generator are the high-level interface to the
|
|
|
82 code generator and the set of reusable components that can be used to build
|
|
|
83 target-specific backends. The two most important interfaces (:raw-html:`<tt>`
|
|
|
84 `TargetMachine`_ :raw-html:`</tt>` and :raw-html:`<tt>` `DataLayout`_
|
|
|
85 :raw-html:`</tt>`) are the only ones that are required to be defined for a
|
|
|
86 backend to fit into the LLVM system, but the others must be defined if the
|
|
|
87 reusable code generator components are going to be used.
|
|
|
88
|
|
|
89 This design has two important implications. The first is that LLVM can support
|
|
|
90 completely non-traditional code generation targets. For example, the C backend
|
|
|
91 does not require register allocation, instruction selection, or any of the other
|
|
|
92 standard components provided by the system. As such, it only implements these
|
|
|
93 two interfaces, and does its own thing. Note that C backend was removed from the
|
|
|
94 trunk since LLVM 3.1 release. Another example of a code generator like this is a
|
|
|
95 (purely hypothetical) backend that converts LLVM to the GCC RTL form and uses
|
|
|
96 GCC to emit machine code for a target.
|
|
|
97
|
|
|
98 This design also implies that it is possible to design and implement radically
|
|
|
99 different code generators in the LLVM system that do not make use of any of the
|
|
|
100 built-in components. Doing so is not recommended at all, but could be required
|
|
|
101 for radically different targets that do not fit into the LLVM machine
|
|
|
102 description model: FPGAs for example.
|
|
|
103
|
|
|
104 .. _high-level design of the code generator:
|
|
|
105
|
|
|
106 The high-level design of the code generator
|
|
|
107 -------------------------------------------
|
|
|
108
|
|
|
109 The LLVM target-independent code generator is designed to support efficient and
|
|
|
110 quality code generation for standard register-based microprocessors. Code
|
|
|
111 generation in this model is divided into the following stages:
|
|
|
112
|
|
|
113 1. `Instruction Selection`_ --- This phase determines an efficient way to
|
|
|
114 express the input LLVM code in the target instruction set. This stage
|
|
|
115 produces the initial code for the program in the target instruction set, then
|
|
|
116 makes use of virtual registers in SSA form and physical registers that
|
|
|
117 represent any required register assignments due to target constraints or
|
|
|
118 calling conventions. This step turns the LLVM code into a DAG of target
|
|
|
119 instructions.
|
|
|
120
|
|
|
121 2. `Scheduling and Formation`_ --- This phase takes the DAG of target
|
|
|
122 instructions produced by the instruction selection phase, determines an
|
|
|
123 ordering of the instructions, then emits the instructions as :raw-html:`<tt>`
|
|
|
124 `MachineInstr`_\s :raw-html:`</tt>` with that ordering. Note that we
|
|
|
125 describe this in the `instruction selection section`_ because it operates on
|
|
|
126 a `SelectionDAG`_.
|
|
|
127
|
|
|
128 3. `SSA-based Machine Code Optimizations`_ --- This optional stage consists of a
|
|
|
129 series of machine-code optimizations that operate on the SSA-form produced by
|
|
|
130 the instruction selector. Optimizations like modulo-scheduling or peephole
|
|
|
131 optimization work here.
|
|
|
132
|
|
|
133 4. `Register Allocation`_ --- The target code is transformed from an infinite
|
|
|
134 virtual register file in SSA form to the concrete register file used by the
|
|
|
135 target. This phase introduces spill code and eliminates all virtual register
|
|
|
136 references from the program.
|
|
|
137
|
|
|
138 5. `Prolog/Epilog Code Insertion`_ --- Once the machine code has been generated
|
|
|
139 for the function and the amount of stack space required is known (used for
|
|
|
140 LLVM alloca's and spill slots), the prolog and epilog code for the function
|
|
|
141 can be inserted and "abstract stack location references" can be eliminated.
|
|
|
142 This stage is responsible for implementing optimizations like frame-pointer
|
|
|
143 elimination and stack packing.
|
|
|
144
|
|
|
145 6. `Late Machine Code Optimizations`_ --- Optimizations that operate on "final"
|
|
|
146 machine code can go here, such as spill code scheduling and peephole
|
|
|
147 optimizations.
|
|
|
148
|
|
|
149 7. `Code Emission`_ --- The final stage actually puts out the code for the
|
|
|
150 current function, either in the target assembler format or in machine
|
|
|
151 code.
|
|
|
152
|
|
|
153 The code generator is based on the assumption that the instruction selector will
|
|
|
154 use an optimal pattern matching selector to create high-quality sequences of
|
|
|
155 native instructions. Alternative code generator designs based on pattern
|
|
|
156 expansion and aggressive iterative peephole optimization are much slower. This
|
|
|
157 design permits efficient compilation (important for JIT environments) and
|
|
|
158 aggressive optimization (used when generating code offline) by allowing
|
|
|
159 components of varying levels of sophistication to be used for any step of
|
|
|
160 compilation.
|
|
|
161
|
|
|
162 In addition to these stages, target implementations can insert arbitrary
|
|
|
163 target-specific passes into the flow. For example, the X86 target uses a
|
|
|
164 special pass to handle the 80x87 floating point stack architecture. Other
|
|
|
165 targets with unusual requirements can be supported with custom passes as needed.
|
|
|
166
|
|
|
167 Using TableGen for target description
|
|
|
168 -------------------------------------
|
|
|
169
|
|
|
170 The target description classes require a detailed description of the target
|
|
|
171 architecture. These target descriptions often have a large amount of common
|
|
|
172 information (e.g., an ``add`` instruction is almost identical to a ``sub``
|
|
|
173 instruction). In order to allow the maximum amount of commonality to be
|
|
|
174 factored out, the LLVM code generator uses the
|
|
|
175 :doc:`TableGen/index` tool to describe big chunks of the
|
|
|
176 target machine, which allows the use of domain-specific and target-specific
|
|
|
177 abstractions to reduce the amount of repetition.
|
|
|
178
|
|
|
179 As LLVM continues to be developed and refined, we plan to move more and more of
|
|
|
180 the target description to the ``.td`` form. Doing so gives us a number of
|
|
|
181 advantages. The most important is that it makes it easier to port LLVM because
|
|
|
182 it reduces the amount of C++ code that has to be written, and the surface area
|
|
|
183 of the code generator that needs to be understood before someone can get
|
|
|
184 something working. Second, it makes it easier to change things. In particular,
|
|
|
185 if tables and other things are all emitted by ``tblgen``, we only need a change
|
|
|
186 in one place (``tblgen``) to update all of the targets to a new interface.
|
|
|
187
|
|
|
188 .. _Abstract target description:
|
|
|
189 .. _target description:
|
|
|
190
|
|
|
191 Target description classes
|
|
|
192 ==========================
|
|
|
193
|
|
|
194 The LLVM target description classes (located in the ``include/llvm/Target``
|
|
|
195 directory) provide an abstract description of the target machine independent of
|
|
|
196 any particular client. These classes are designed to capture the *abstract*
|
|
|
197 properties of the target (such as the instructions and registers it has), and do
|
|
|
198 not incorporate any particular pieces of code generation algorithms.
|
|
|
199
|
|
|
200 All of the target description classes (except the :raw-html:`<tt>` `DataLayout`_
|
|
|
201 :raw-html:`</tt>` class) are designed to be subclassed by the concrete target
|
|
|
202 implementation, and have virtual methods implemented. To get to these
|
|
|
203 implementations, the :raw-html:`<tt>` `TargetMachine`_ :raw-html:`</tt>` class
|
|
|
204 provides accessors that should be implemented by the target.
|
|
|
205
|
|
|
206 .. _TargetMachine:
|
|
|
207
|
|
|
208 The ``TargetMachine`` class
|
|
|
209 ---------------------------
|
|
|
210
|
|
|
211 The ``TargetMachine`` class provides virtual methods that are used to access the
|
|
|
212 target-specific implementations of the various target description classes via
|
|
|
213 the ``get*Info`` methods (``getInstrInfo``, ``getRegisterInfo``,
|
|
|
214 ``getFrameInfo``, etc.). This class is designed to be specialized by a concrete
|
|
|
215 target implementation (e.g., ``X86TargetMachine``) which implements the various
|
|
|
216 virtual methods. The only required target description class is the
|
|
|
217 :raw-html:`<tt>` `DataLayout`_ :raw-html:`</tt>` class, but if the code
|
|
|
218 generator components are to be used, the other interfaces should be implemented
|
|
|
219 as well.
|
|
|
220
|
|
|
221 .. _DataLayout:
|
|
|
222
|
|
|
223 The ``DataLayout`` class
|
|
|
224 ------------------------
|
|
|
225
|
|
|
226 The ``DataLayout`` class is the only required target description class, and it
|
|
|
227 is the only class that is not extensible (you cannot derive a new class from
|
|
|
228 it). ``DataLayout`` specifies information about how the target lays out memory
|
|
|
229 for structures, the alignment requirements for various data types, the size of
|
|
|
230 pointers in the target, and whether the target is little-endian or
|
|
|
231 big-endian.
|
|
|
232
|
|
|
233 .. _TargetLowering:
|
|
|
234
|
|
|
235 The ``TargetLowering`` class
|
|
|
236 ----------------------------
|
|
|
237
|
|
|
238 The ``TargetLowering`` class is used by SelectionDAG based instruction selectors
|
|
|
239 primarily to describe how LLVM code should be lowered to SelectionDAG
|
|
|
240 operations. Among other things, this class indicates:
|
|
|
241
|
|
|
242 * an initial register class to use for various ``ValueType``\s,
|
|
|
243
|
|
|
244 * which operations are natively supported by the target machine,
|
|
|
245
|
|
|
246 * the return type of ``setcc`` operations,
|
|
|
247
|
|
|
248 * the type to use for shift amounts, and
|
|
|
249
|
|
|
250 * various high-level characteristics, like whether it is profitable to turn
|
|
|
251 division by a constant into a multiplication sequence.
|
|
|
252
|
|
|
253 .. _TargetRegisterInfo:
|
|
|
254
|
|
|
255 The ``TargetRegisterInfo`` class
|
|
|
256 --------------------------------
|
|
|
257
|
|
|
258 The ``TargetRegisterInfo`` class is used to describe the register file of the
|
|
|
259 target and any interactions between the registers.
|
|
|
260
|
|
|
261 Registers are represented in the code generator by unsigned integers. Physical
|
|
|
262 registers (those that actually exist in the target description) are unique
|
|
|
263 small numbers, and virtual registers are generally large. Note that
|
|
|
264 register ``#0`` is reserved as a flag value.
|
|
|
265
|
|
|
266 Each register in the processor description has an associated
|
|
|
267 ``TargetRegisterDesc`` entry, which provides a textual name for the register
|
|
|
268 (used for assembly output and debugging dumps) and a set of aliases (used to
|
|
|
269 indicate whether one register overlaps with another).
|
|
|
270
|
|
|
271 In addition to the per-register description, the ``TargetRegisterInfo`` class
|
|
|
272 exposes a set of processor specific register classes (instances of the
|
|
|
273 ``TargetRegisterClass`` class). Each register class contains sets of registers
|
|
|
274 that have the same properties (for example, they are all 32-bit integer
|
|
|
275 registers). Each SSA virtual register created by the instruction selector has
|
|
|
276 an associated register class. When the register allocator runs, it replaces
|
|
|
277 virtual registers with a physical register in the set.
|
|
|
278
|
|
|
279 The target-specific implementations of these classes is auto-generated from a
|
|
|
280 :doc:`TableGen/index` description of the register file.
|
|
|
281
|
|
|
282 .. _TargetInstrInfo:
|
|
|
283
|
|
|
284 The ``TargetInstrInfo`` class
|
|
|
285 -----------------------------
|
|
|
286
|
|
|
287 The ``TargetInstrInfo`` class is used to describe the machine instructions
|
|
|
288 supported by the target. Descriptions define things like the mnemonic for
|
|
|
289 the opcode, the number of operands, the list of implicit register uses and defs,
|
|
|
290 whether the instruction has certain target-independent properties (accesses
|
|
|
291 memory, is commutable, etc), and holds any target-specific flags.
|
|
|
292
|
|
|
293 The ``TargetFrameLowering`` class
|
|
|
294 ---------------------------------
|
|
|
295
|
|
|
296 The ``TargetFrameLowering`` class is used to provide information about the stack
|
|
|
297 frame layout of the target. It holds the direction of stack growth, the known
|
|
|
298 stack alignment on entry to each function, and the offset to the local area.
|
|
|
299 The offset to the local area is the offset from the stack pointer on function
|
|
|
300 entry to the first location where function data (local variables, spill
|
|
|
301 locations) can be stored.
|
|
|
302
|
|
|
303 The ``TargetSubtarget`` class
|
|
|
304 -----------------------------
|
|
|
305
|
|
|
306 The ``TargetSubtarget`` class is used to provide information about the specific
|
|
|
307 chip set being targeted. A sub-target informs code generation of which
|
|
|
308 instructions are supported, instruction latencies and instruction execution
|
|
|
309 itinerary; i.e., which processing units are used, in what order, and for how
|
|
|
310 long.
|
|
|
311
|
|
|
312 The ``TargetJITInfo`` class
|
|
|
313 ---------------------------
|
|
|
314
|
|
|
315 The ``TargetJITInfo`` class exposes an abstract interface used by the
|
|
|
316 Just-In-Time code generator to perform target-specific activities, such as
|
|
|
317 emitting stubs. If a ``TargetMachine`` supports JIT code generation, it should
|
|
|
318 provide one of these objects through the ``getJITInfo`` method.
|
|
|
319
|
|
|
320 .. _code being generated:
|
|
|
321 .. _machine code representation:
|
|
|
322
|
|
|
323 Machine code description classes
|
|
|
324 ================================
|
|
|
325
|
|
|
326 At the high-level, LLVM code is translated to a machine specific representation
|
|
|
327 formed out of :raw-html:`<tt>` `MachineFunction`_ :raw-html:`</tt>`,
|
|
|
328 :raw-html:`<tt>` `MachineBasicBlock`_ :raw-html:`</tt>`, and :raw-html:`<tt>`
|
|
|
329 `MachineInstr`_ :raw-html:`</tt>` instances (defined in
|
|
|
330 ``include/llvm/CodeGen``). This representation is completely target agnostic,
|
|
|
331 representing instructions in their most abstract form: an opcode and a series of
|
|
|
332 operands. This representation is designed to support both an SSA representation
|
|
|
333 for machine code, as well as a register allocated, non-SSA form.
|
|
|
334
|
|
|
335 .. _MachineInstr:
|
|
|
336
|
|
|
337 The ``MachineInstr`` class
|
|
|
338 --------------------------
|
|
|
339
|
|
|
340 Target machine instructions are represented as instances of the ``MachineInstr``
|
|
|
341 class. This class is an extremely abstract way of representing machine
|
|
|
342 instructions. In particular, it only keeps track of an opcode number and a set
|
|
|
343 of operands.
|
|
|
344
|
|
|
345 The opcode number is a simple unsigned integer that only has meaning to a
|
|
|
346 specific backend. All of the instructions for a target should be defined in the
|
|
|
347 ``*InstrInfo.td`` file for the target. The opcode enum values are auto-generated
|
|
|
348 from this description. The ``MachineInstr`` class does not have any information
|
|
|
349 about how to interpret the instruction (i.e., what the semantics of the
|
|
|
350 instruction are); for that you must refer to the :raw-html:`<tt>`
|
|
|
351 `TargetInstrInfo`_ :raw-html:`</tt>` class.
|
|
|
352
|
|
|
353 The operands of a machine instruction can be of several different types: a
|
|
|
354 register reference, a constant integer, a basic block reference, etc. In
|
|
|
355 addition, a machine operand should be marked as a def or a use of the value
|
|
|
356 (though only registers are allowed to be defs).
|
|
|
357
|
|
|
358 By convention, the LLVM code generator orders instruction operands so that all
|
|
|
359 register definitions come before the register uses, even on architectures that
|
|
|
360 are normally printed in other orders. For example, the SPARC add instruction:
|
|
|
361 "``add %i1, %i2, %i3``" adds the "%i1", and "%i2" registers and stores the
|
|
|
362 result into the "%i3" register. In the LLVM code generator, the operands should
|
|
|
363 be stored as "``%i3, %i1, %i2``": with the destination first.
|
|
|
364
|
|
|
365 Keeping destination (definition) operands at the beginning of the operand list
|
|
|
366 has several advantages. In particular, the debugging printer will print the
|
|
|
367 instruction like this:
|
|
|
368
|
|
|
369 .. code-block:: llvm
|
|
|
370
|
|
|
371 %r3 = add %i1, %i2
|
|
|
372
|
|
|
373 Also if the first operand is a def, it is easier to `create instructions`_ whose
|
|
|
374 only def is the first operand.
|
|
|
375
|
|
|
376 .. _create instructions:
|
|
|
377
|
|
|
378 Using the ``MachineInstrBuilder.h`` functions
|
|
|
379 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
380
|
|
|
381 Machine instructions are created by using the ``BuildMI`` functions, located in
|
|
|
382 the ``include/llvm/CodeGen/MachineInstrBuilder.h`` file. The ``BuildMI``
|
|
|
383 functions make it easy to build arbitrary machine instructions. Usage of the
|
|
|
384 ``BuildMI`` functions look like this:
|
|
|
385
|
|
|
386 .. code-block:: c++
|
|
|
387
|
|
|
388 // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
|
|
|
389 // instruction and insert it at the end of the given MachineBasicBlock.
|
|
|
390 const TargetInstrInfo &TII = ...
|
|
|
391 MachineBasicBlock &MBB = ...
|
|
|
392 DebugLoc DL;
|
|
|
393 MachineInstr *MI = BuildMI(MBB, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);
|
|
|
394
|
|
|
395 // Create the same instr, but insert it before a specified iterator point.
|
|
|
396 MachineBasicBlock::iterator MBBI = ...
|
|
|
397 BuildMI(MBB, MBBI, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);
|
|
|
398
|
|
|
399 // Create a 'cmp Reg, 0' instruction, no destination reg.
|
|
|
400 MI = BuildMI(MBB, DL, TII.get(X86::CMP32ri8)).addReg(Reg).addImm(42);
|
|
|
401
|
|
|
402 // Create an 'sahf' instruction which takes no operands and stores nothing.
|
|
|
403 MI = BuildMI(MBB, DL, TII.get(X86::SAHF));
|
|
|
404
|
|
|
405 // Create a self looping branch instruction.
|
|
|
406 BuildMI(MBB, DL, TII.get(X86::JNE)).addMBB(&MBB);
|
|
|
407
|
|
|
408 If you need to add a definition operand (other than the optional destination
|
|
|
409 register), you must explicitly mark it as such:
|
|
|
410
|
|
|
411 .. code-block:: c++
|
|
|
412
|
|
|
413 MI.addReg(Reg, RegState::Define);
|
|
|
414
|
|
|
415 Fixed (preassigned) registers
|
|
|
416 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
417
|
|
|
418 One important issue that the code generator needs to be aware of is the presence
|
|
|
419 of fixed registers. In particular, there are often places in the instruction
|
|
|
420 stream where the register allocator *must* arrange for a particular value to be
|
|
|
421 in a particular register. This can occur due to limitations of the instruction
|
|
|
422 set (e.g., the X86 can only do a 32-bit divide with the ``EAX``/``EDX``
|
|
|
423 registers), or external factors like calling conventions. In any case, the
|
|
|
424 instruction selector should emit code that copies a virtual register into or out
|
|
|
425 of a physical register when needed.
|
|
|
426
|
|
|
427 For example, consider this simple LLVM example:
|
|
|
428
|
|
|
429 .. code-block:: llvm
|
|
|
430
|
|
|
431 define i32 @test(i32 %X, i32 %Y) {
|
|
|
432 %Z = sdiv i32 %X, %Y
|
|
|
433 ret i32 %Z
|
|
|
434 }
|
|
|
435
|
|
|
436 The X86 instruction selector might produce this machine code for the ``div`` and
|
|
|
437 ``ret``:
|
|
|
438
|
|
|
439 .. code-block:: text
|
|
|
440
|
|
|
441 ;; Start of div
|
|
|
442 %EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
|
|
|
443 %reg1027 = sar %reg1024, 31
|
|
|
444 %EDX = mov %reg1027 ;; Sign extend X into EDX
|
|
|
445 idiv %reg1025 ;; Divide by Y (in reg1025)
|
|
|
446 %reg1026 = mov %EAX ;; Read the result (Z) out of EAX
|
|
|
447
|
|
|
448 ;; Start of ret
|
|
|
449 %EAX = mov %reg1026 ;; 32-bit return value goes in EAX
|
|
|
450 ret
|
|
|
451
|
|
|
452 By the end of code generation, the register allocator would coalesce the
|
|
|
453 registers and delete the resultant identity moves producing the following
|
|
|
454 code:
|
|
|
455
|
|
|
456 .. code-block:: text
|
|
|
457
|
|
|
458 ;; X is in EAX, Y is in ECX
|
|
|
459 mov %EAX, %EDX
|
|
|
460 sar %EDX, 31
|
|
|
461 idiv %ECX
|
|
|
462 ret
|
|
|
463
|
|
|
464 This approach is extremely general (if it can handle the X86 architecture, it
|
|
|
465 can handle anything!) and allows all of the target specific knowledge about the
|
|
|
466 instruction stream to be isolated in the instruction selector. Note that
|
|
|
467 physical registers should have a short lifetime for good code generation, and
|
|
|
468 all physical registers are assumed dead on entry to and exit from basic blocks
|
|
|
469 (before register allocation). Thus, if you need a value to be live across basic
|
|
|
470 block boundaries, it *must* live in a virtual register.
|
|
|
471
|
|
|
472 Call-clobbered registers
|
|
|
473 ^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
474
|
|
|
475 Some machine instructions, like calls, clobber a large number of physical
|
|
|
476 registers. Rather than adding ``<def,dead>`` operands for all of them, it is
|
|
|
477 possible to use an ``MO_RegisterMask`` operand instead. The register mask
|
|
|
478 operand holds a bit mask of preserved registers, and everything else is
|
|
|
479 considered to be clobbered by the instruction.
|
|
|
480
|
|
|
481 Machine code in SSA form
|
|
|
482 ^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
483
|
|
|
484 ``MachineInstr``'s are initially selected in SSA-form, and are maintained in
|
|
|
485 SSA-form until register allocation happens. For the most part, this is
|
|
|
486 trivially simple since LLVM is already in SSA form; LLVM PHI nodes become
|
|
|
487 machine code PHI nodes, and virtual registers are only allowed to have a single
|
|
|
488 definition.
|
|
|
489
|
|
|
490 After register allocation, machine code is no longer in SSA-form because there
|
|
|
491 are no virtual registers left in the code.
|
|
|
492
|
|
|
493 .. _MachineBasicBlock:
|
|
|
494
|
|
|
495 The ``MachineBasicBlock`` class
|
|
|
496 -------------------------------
|
|
|
497
|
|
|
498 The ``MachineBasicBlock`` class contains a list of machine instructions
|
|
|
499 (:raw-html:`<tt>` `MachineInstr`_ :raw-html:`</tt>` instances). It roughly
|
|
|
500 corresponds to the LLVM code input to the instruction selector, but there can be
|
|
|
501 a one-to-many mapping (i.e. one LLVM basic block can map to multiple machine
|
|
|
502 basic blocks). The ``MachineBasicBlock`` class has a "``getBasicBlock``" method,
|
|
|
503 which returns the LLVM basic block that it comes from.
|
|
|
504
|
|
|
505 .. _MachineFunction:
|
|
|
506
|
|
|
507 The ``MachineFunction`` class
|
|
|
508 -----------------------------
|
|
|
509
|
|
|
510 The ``MachineFunction`` class contains a list of machine basic blocks
|
|
|
511 (:raw-html:`<tt>` `MachineBasicBlock`_ :raw-html:`</tt>` instances). It
|
|
|
512 corresponds one-to-one with the LLVM function input to the instruction selector.
|
|
|
513 In addition to a list of basic blocks, the ``MachineFunction`` contains a a
|
|
|
514 ``MachineConstantPool``, a ``MachineFrameInfo``, a ``MachineFunctionInfo``, and
|
|
|
515 a ``MachineRegisterInfo``. See ``include/llvm/CodeGen/MachineFunction.h`` for
|
|
|
516 more information.
|
|
|
517
|
|
|
518 ``MachineInstr Bundles``
|
|
|
519 ------------------------
|
|
|
520
|
|
|
521 LLVM code generator can model sequences of instructions as MachineInstr
|
|
|
522 bundles. A MI bundle can model a VLIW group / pack which contains an arbitrary
|
|
|
523 number of parallel instructions. It can also be used to model a sequential list
|
|
|
524 of instructions (potentially with data dependencies) that cannot be legally
|
|
|
525 separated (e.g. ARM Thumb2 IT blocks).
|
|
|
526
|
|
|
527 Conceptually a MI bundle is a MI with a number of other MIs nested within:
|
|
|
528
|
|
|
529 ::
|
|
|
530
|
|
|
531 --------------
|
|
|
532 | Bundle | ---------
|
|
|
533 -------------- \
|
|
|
534 | ----------------
|
|
|
535 | | MI |
|
|
|
536 | ----------------
|
|
|
537 | |
|
|
|
538 | ----------------
|
|
|
539 | | MI |
|
|
|
540 | ----------------
|
|
|
541 | |
|
|
|
542 | ----------------
|
|
|
543 | | MI |
|
|
|
544 | ----------------
|
|
|
545 |
|
|
|
546 --------------
|
|
|
547 | Bundle | --------
|
|
|
548 -------------- \
|
|
|
549 | ----------------
|
|
|
550 | | MI |
|
|
|
551 | ----------------
|
|
|
552 | |
|
|
|
553 | ----------------
|
|
|
554 | | MI |
|
|
|
555 | ----------------
|
|
|
556 | |
|
|
|
557 | ...
|
|
|
558 |
|
|
|
559 --------------
|
|
|
560 | Bundle | --------
|
|
|
561 -------------- \
|
|
|
562 |
|
|
|
563 ...
|
|
|
564
|
|
|
565 MI bundle support does not change the physical representations of
|
|
|
566 MachineBasicBlock and MachineInstr. All the MIs (including top level and nested
|
|
|
567 ones) are stored as sequential list of MIs. The "bundled" MIs are marked with
|
|
|
568 the 'InsideBundle' flag. A top level MI with the special BUNDLE opcode is used
|
|
|
569 to represent the start of a bundle. It's legal to mix BUNDLE MIs with individual
|
|
|
570 MIs that are not inside bundles nor represent bundles.
|
|
|
571
|
|
|
572 MachineInstr passes should operate on a MI bundle as a single unit. Member
|
|
|
573 methods have been taught to correctly handle bundles and MIs inside bundles.
|
|
|
574 The MachineBasicBlock iterator has been modified to skip over bundled MIs to
|
|
|
575 enforce the bundle-as-a-single-unit concept. An alternative iterator
|
|
|
576 instr_iterator has been added to MachineBasicBlock to allow passes to iterate
|
|
|
577 over all of the MIs in a MachineBasicBlock, including those which are nested
|
|
|
578 inside bundles. The top level BUNDLE instruction must have the correct set of
|
|
|
579 register MachineOperand's that represent the cumulative inputs and outputs of
|
|
|
580 the bundled MIs.
|
|
|
581
|
|
|
582 Packing / bundling of MachineInstrs for VLIW architectures should
|
|
|
583 generally be done as part of the register allocation super-pass. More
|
|
|
584 specifically, the pass which determines what MIs should be bundled
|
|
|
585 together should be done after code generator exits SSA form
|
|
|
586 (i.e. after two-address pass, PHI elimination, and copy coalescing).
|
|
|
587 Such bundles should be finalized (i.e. adding BUNDLE MIs and input and
|
|
|
588 output register MachineOperands) after virtual registers have been
|
|
|
589 rewritten into physical registers. This eliminates the need to add
|
|
|
590 virtual register operands to BUNDLE instructions which would
|
|
|
591 effectively double the virtual register def and use lists. Bundles may
|
|
|
592 use virtual registers and be formed in SSA form, but may not be
|
|
|
593 appropriate for all use cases.
|
|
|
594
|
|
|
595 .. _MC Layer:
|
|
|
596
|
|
|
597 The "MC" Layer
|
|
|
598 ==============
|
|
|
599
|
|
|
600 The MC Layer is used to represent and process code at the raw machine code
|
|
|
601 level, devoid of "high level" information like "constant pools", "jump tables",
|
|
|
602 "global variables" or anything like that. At this level, LLVM handles things
|
|
|
603 like label names, machine instructions, and sections in the object file. The
|
|
|
604 code in this layer is used for a number of important purposes: the tail end of
|
|
|
605 the code generator uses it to write a .s or .o file, and it is also used by the
|
|
|
606 llvm-mc tool to implement standalone machine code assemblers and disassemblers.
|
|
|
607
|
|
|
608 This section describes some of the important classes. There are also a number
|
|
|
609 of important subsystems that interact at this layer, they are described later in
|
|
|
610 this manual.
|
|
|
611
|
|
|
612 .. _MCStreamer:
|
|
|
613
|
|
|
614 The ``MCStreamer`` API
|
|
|
615 ----------------------
|
|
|
616
|
|
|
617 MCStreamer is best thought of as an assembler API. It is an abstract API which
|
|
|
618 is *implemented* in different ways (e.g. to output a .s file, output an ELF .o
|
|
|
619 file, etc) but whose API correspond directly to what you see in a .s file.
|
|
|
620 MCStreamer has one method per directive, such as EmitLabel, EmitSymbolAttribute,
|
|
|
621 SwitchSection, EmitValue (for .byte, .word), etc, which directly correspond to
|
|
|
622 assembly level directives. It also has an EmitInstruction method, which is used
|
|
|
623 to output an MCInst to the streamer.
|
|
|
624
|
|
|
625 This API is most important for two clients: the llvm-mc stand-alone assembler is
|
|
|
626 effectively a parser that parses a line, then invokes a method on MCStreamer. In
|
|
|
627 the code generator, the `Code Emission`_ phase of the code generator lowers
|
|
|
628 higher level LLVM IR and Machine* constructs down to the MC layer, emitting
|
|
|
629 directives through MCStreamer.
|
|
|
630
|
|
|
631 On the implementation side of MCStreamer, there are two major implementations:
|
|
|
632 one for writing out a .s file (MCAsmStreamer), and one for writing out a .o
|
|
|
633 file (MCObjectStreamer). MCAsmStreamer is a straightforward implementation
|
|
|
634 that prints out a directive for each method (e.g. ``EmitValue -> .byte``), but
|
|
|
635 MCObjectStreamer implements a full assembler.
|
|
|
636
|
|
|
637 For target specific directives, the MCStreamer has a MCTargetStreamer instance.
|
|
|
638 Each target that needs it defines a class that inherits from it and is a lot
|
|
|
639 like MCStreamer itself: It has one method per directive and two classes that
|
|
|
640 inherit from it, a target object streamer and a target asm streamer. The target
|
|
|
641 asm streamer just prints it (``emitFnStart -> .fnstart``), and the object
|
|
|
642 streamer implement the assembler logic for it.
|
|
|
643
|
|
|
644 To make llvm use these classes, the target initialization must call
|
|
|
645 TargetRegistry::RegisterAsmStreamer and TargetRegistry::RegisterMCObjectStreamer
|
|
|
646 passing callbacks that allocate the corresponding target streamer and pass it
|
|
|
647 to createAsmStreamer or to the appropriate object streamer constructor.
|
|
|
648
|
|
|
649 The ``MCContext`` class
|
|
|
650 -----------------------
|
|
|
651
|
|
|
652 The MCContext class is the owner of a variety of uniqued data structures at the
|
|
|
653 MC layer, including symbols, sections, etc. As such, this is the class that you
|
|
|
654 interact with to create symbols and sections. This class can not be subclassed.
|
|
|
655
|
|
|
656 The ``MCSymbol`` class
|
|
|
657 ----------------------
|
|
|
658
|
|
|
659 The MCSymbol class represents a symbol (aka label) in the assembly file. There
|
|
|
660 are two interesting kinds of symbols: assembler temporary symbols, and normal
|
|
|
661 symbols. Assembler temporary symbols are used and processed by the assembler
|
|
|
662 but are discarded when the object file is produced. The distinction is usually
|
|
|
663 represented by adding a prefix to the label, for example "L" labels are
|
|
|
664 assembler temporary labels in MachO.
|
|
|
665
|
|
|
666 MCSymbols are created by MCContext and uniqued there. This means that MCSymbols
|
|
|
667 can be compared for pointer equivalence to find out if they are the same symbol.
|
|
|
668 Note that pointer inequality does not guarantee the labels will end up at
|
|
|
669 different addresses though. It's perfectly legal to output something like this
|
|
|
670 to the .s file:
|
|
|
671
|
|
|
672 ::
|
|
|
673
|
|
|
674 foo:
|
|
|
675 bar:
|
|
|
676 .byte 4
|
|
|
677
|
|
|
678 In this case, both the foo and bar symbols will have the same address.
|
|
|
679
|
|
|
680 The ``MCSection`` class
|
|
|
681 -----------------------
|
|
|
682
|
|
|
683 The ``MCSection`` class represents an object-file specific section. It is
|
|
|
684 subclassed by object file specific implementations (e.g. ``MCSectionMachO``,
|
|
|
685 ``MCSectionCOFF``, ``MCSectionELF``) and these are created and uniqued by
|
|
|
686 MCContext. The MCStreamer has a notion of the current section, which can be
|
|
|
687 changed with the SwitchToSection method (which corresponds to a ".section"
|
|
|
688 directive in a .s file).
|
|
|
689
|
|
|
690 .. _MCInst:
|
|
|
691
|
|
|
692 The ``MCInst`` class
|
|
|
693 --------------------
|
|
|
694
|
|
|
695 The ``MCInst`` class is a target-independent representation of an instruction.
|
|
|
696 It is a simple class (much more so than `MachineInstr`_) that holds a
|
|
|
697 target-specific opcode and a vector of MCOperands. MCOperand, in turn, is a
|
|
|
698 simple discriminated union of three cases: 1) a simple immediate, 2) a target
|
|
|
699 register ID, 3) a symbolic expression (e.g. "``Lfoo-Lbar+42``") as an MCExpr.
|
|
|
700
|
|
|
701 MCInst is the common currency used to represent machine instructions at the MC
|
|
|
702 layer. It is the type used by the instruction encoder, the instruction printer,
|
|
|
703 and the type generated by the assembly parser and disassembler.
|
|
|
704
|
|
|
705 .. _Target-independent algorithms:
|
|
|
706 .. _code generation algorithm:
|
|
|
707
|
|
|
708 Target-independent code generation algorithms
|
|
|
709 =============================================
|
|
|
710
|
|
|
711 This section documents the phases described in the `high-level design of the
|
|
|
712 code generator`_. It explains how they work and some of the rationale behind
|
|
|
713 their design.
|
|
|
714
|
|
|
715 .. _Instruction Selection:
|
|
|
716 .. _instruction selection section:
|
|
|
717
|
|
|
718 Instruction Selection
|
|
|
719 ---------------------
|
|
|
720
|
|
|
721 Instruction Selection is the process of translating LLVM code presented to the
|
|
|
722 code generator into target-specific machine instructions. There are several
|
|
|
723 well-known ways to do this in the literature. LLVM uses a SelectionDAG based
|
|
|
724 instruction selector.
|
|
|
725
|
|
|
726 Portions of the DAG instruction selector are generated from the target
|
|
|
727 description (``*.td``) files. Our goal is for the entire instruction selector
|
|
|
728 to be generated from these ``.td`` files, though currently there are still
|
|
|
729 things that require custom C++ code.
|
|
|
730
|
|
223
|
731 `GlobalISel <https://llvm.org/docs/GlobalISel/index.html>`_ is another
|
|
|
732 instruction selection framework.
|
|
|
733
|
|
150
|
734 .. _SelectionDAG:
|
|
|
735
|
|
|
736 Introduction to SelectionDAGs
|
|
|
737 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
738
|
|
|
739 The SelectionDAG provides an abstraction for code representation in a way that
|
|
|
740 is amenable to instruction selection using automatic techniques
|
|
|
741 (e.g. dynamic-programming based optimal pattern matching selectors). It is also
|
|
|
742 well-suited to other phases of code generation; in particular, instruction
|
|
|
743 scheduling (SelectionDAG's are very close to scheduling DAGs post-selection).
|
|
|
744 Additionally, the SelectionDAG provides a host representation where a large
|
|
|
745 variety of very-low-level (but target-independent) `optimizations`_ may be
|
|
|
746 performed; ones which require extensive information about the instructions
|
|
|
747 efficiently supported by the target.
|
|
|
748
|
|
|
749 The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
|
|
|
750 ``SDNode`` class. The primary payload of the ``SDNode`` is its operation code
|
|
|
751 (Opcode) that indicates what operation the node performs and the operands to the
|
|
|
752 operation. The various operation node types are described at the top of the
|
|
|
753 ``include/llvm/CodeGen/ISDOpcodes.h`` file.
|
|
|
754
|
|
|
755 Although most operations define a single value, each node in the graph may
|
|
|
756 define multiple values. For example, a combined div/rem operation will define
|
|
|
757 both the dividend and the remainder. Many other situations require multiple
|
|
|
758 values as well. Each node also has some number of operands, which are edges to
|
|
|
759 the node defining the used value. Because nodes may define multiple values,
|
|
|
760 edges are represented by instances of the ``SDValue`` class, which is a
|
|
|
761 ``<SDNode, unsigned>`` pair, indicating the node and result value being used,
|
|
|
762 respectively. Each value produced by an ``SDNode`` has an associated ``MVT``
|
|
|
763 (Machine Value Type) indicating what the type of the value is.
|
|
|
764
|
|
|
765 SelectionDAGs contain two different kinds of values: those that represent data
|
|
|
766 flow and those that represent control flow dependencies. Data values are simple
|
|
|
767 edges with an integer or floating point value type. Control edges are
|
|
|
768 represented as "chain" edges which are of type ``MVT::Other``. These edges
|
|
|
769 provide an ordering between nodes that have side effects (such as loads, stores,
|
|
|
770 calls, returns, etc). All nodes that have side effects should take a token
|
|
|
771 chain as input and produce a new one as output. By convention, token chain
|
|
|
772 inputs are always operand #0, and chain results are always the last value
|
|
|
773 produced by an operation. However, after instruction selection, the
|
|
|
774 machine nodes have their chain after the instruction's operands, and
|
|
|
775 may be followed by glue nodes.
|
|
|
776
|
|
|
777 A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
|
|
|
778 always a marker node with an Opcode of ``ISD::EntryToken``. The Root node is
|
|
|
779 the final side-effecting node in the token chain. For example, in a single basic
|
|
|
780 block function it would be the return node.
|
|
|
781
|
|
|
782 One important concept for SelectionDAGs is the notion of a "legal" vs.
|
|
|
783 "illegal" DAG. A legal DAG for a target is one that only uses supported
|
|
|
784 operations and supported types. On a 32-bit PowerPC, for example, a DAG with a
|
|
|
785 value of type i1, i8, i16, or i64 would be illegal, as would a DAG that uses a
|
|
|
786 SREM or UREM operation. The `legalize types`_ and `legalize operations`_ phases
|
|
|
787 are responsible for turning an illegal DAG into a legal DAG.
|
|
|
788
|
|
|
789 .. _SelectionDAG-Process:
|
|
|
790
|
|
|
791 SelectionDAG Instruction Selection Process
|
|
|
792 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
793
|
|
|
794 SelectionDAG-based instruction selection consists of the following steps:
|
|
|
795
|
|
|
796 #. `Build initial DAG`_ --- This stage performs a simple translation from the
|
|
|
797 input LLVM code to an illegal SelectionDAG.
|
|
|
798
|
|
|
799 #. `Optimize SelectionDAG`_ --- This stage performs simple optimizations on the
|
|
|
800 SelectionDAG to simplify it, and recognize meta instructions (like rotates
|
|
|
801 and ``div``/``rem`` pairs) for targets that support these meta operations.
|
|
|
802 This makes the resultant code more efficient and the `select instructions
|
|
|
803 from DAG`_ phase (below) simpler.
|
|
|
804
|
|
|
805 #. `Legalize SelectionDAG Types`_ --- This stage transforms SelectionDAG nodes
|
|
|
806 to eliminate any types that are unsupported on the target.
|
|
|
807
|
|
|
808 #. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to clean up
|
|
|
809 redundancies exposed by type legalization.
|
|
|
810
|
|
|
811 #. `Legalize SelectionDAG Ops`_ --- This stage transforms SelectionDAG nodes to
|
|
|
812 eliminate any operations that are unsupported on the target.
|
|
|
813
|
|
|
814 #. `Optimize SelectionDAG`_ --- The SelectionDAG optimizer is run to eliminate
|
|
|
815 inefficiencies introduced by operation legalization.
|
|
|
816
|
|
|
817 #. `Select instructions from DAG`_ --- Finally, the target instruction selector
|
|
|
818 matches the DAG operations to target instructions. This process translates
|
|
|
819 the target-independent input DAG into another DAG of target instructions.
|
|
|
820
|
|
|
821 #. `SelectionDAG Scheduling and Formation`_ --- The last phase assigns a linear
|
|
|
822 order to the instructions in the target-instruction DAG and emits them into
|
|
|
823 the MachineFunction being compiled. This step uses traditional prepass
|
|
|
824 scheduling techniques.
|
|
|
825
|
|
|
826 After all of these steps are complete, the SelectionDAG is destroyed and the
|
|
|
827 rest of the code generation passes are run.
|
|
|
828
|
|
|
829 One great way to visualize what is going on here is to take advantage of a few
|
|
|
830 LLC command line options. The following options pop up a window displaying the
|
|
|
831 SelectionDAG at specific times (if you only get errors printed to the console
|
|
|
832 while using this, you probably `need to configure your
|
|
|
833 system <ProgrammersManual.html#viewing-graphs-while-debugging-code>`_ to add support for it).
|
|
|
834
|
|
|
835 * ``-view-dag-combine1-dags`` displays the DAG after being built, before the
|
|
|
836 first optimization pass.
|
|
|
837
|
|
|
838 * ``-view-legalize-dags`` displays the DAG before Legalization.
|
|
|
839
|
|
|
840 * ``-view-dag-combine2-dags`` displays the DAG before the second optimization
|
|
|
841 pass.
|
|
|
842
|
|
|
843 * ``-view-isel-dags`` displays the DAG before the Select phase.
|
|
|
844
|
|
|
845 * ``-view-sched-dags`` displays the DAG before Scheduling.
|
|
|
846
|
|
|
847 The ``-view-sunit-dags`` displays the Scheduler's dependency graph. This graph
|
|
|
848 is based on the final SelectionDAG, with nodes that must be scheduled together
|
|
|
849 bundled into a single scheduling-unit node, and with immediate operands and
|
|
|
850 other nodes that aren't relevant for scheduling omitted.
|
|
|
851
|
|
|
852 The option ``-filter-view-dags`` allows to select the name of the basic block
|
|
|
853 that you are interested to visualize and filters all the previous
|
|
|
854 ``view-*-dags`` options.
|
|
|
855
|
|
|
856 .. _Build initial DAG:
|
|
|
857
|
|
|
858 Initial SelectionDAG Construction
|
|
|
859 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
860
|
|
|
861 The initial SelectionDAG is na\ :raw-html:`ï`\ vely peephole expanded from
|
|
|
862 the LLVM input by the ``SelectionDAGBuilder`` class. The intent of this pass
|
|
|
863 is to expose as much low-level, target-specific details to the SelectionDAG as
|
|
|
864 possible. This pass is mostly hard-coded (e.g. an LLVM ``add`` turns into an
|
|
|
865 ``SDNode add`` while a ``getelementptr`` is expanded into the obvious
|
|
|
866 arithmetic). This pass requires target-specific hooks to lower calls, returns,
|
|
|
867 varargs, etc. For these features, the :raw-html:`<tt>` `TargetLowering`_
|
|
|
868 :raw-html:`</tt>` interface is used.
|
|
|
869
|
|
|
870 .. _legalize types:
|
|
|
871 .. _Legalize SelectionDAG Types:
|
|
|
872 .. _Legalize SelectionDAG Ops:
|
|
|
873
|
|
|
874 SelectionDAG LegalizeTypes Phase
|
|
|
875 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
876
|
|
|
877 The Legalize phase is in charge of converting a DAG to only use the types that
|
|
|
878 are natively supported by the target.
|
|
|
879
|
|
|
880 There are two main ways of converting values of unsupported scalar types to
|
|
|
881 values of supported types: converting small types to larger types ("promoting"),
|
|
|
882 and breaking up large integer types into smaller ones ("expanding"). For
|
|
|
883 example, a target might require that all f32 values are promoted to f64 and that
|
|
|
884 all i1/i8/i16 values are promoted to i32. The same target might require that
|
|
|
885 all i64 values be expanded into pairs of i32 values. These changes can insert
|
|
|
886 sign and zero extensions as needed to make sure that the final code has the same
|
|
|
887 behavior as the input.
|
|
|
888
|
|
|
889 There are two main ways of converting values of unsupported vector types to
|
|
|
890 value of supported types: splitting vector types, multiple times if necessary,
|
|
|
891 until a legal type is found, and extending vector types by adding elements to
|
|
|
892 the end to round them out to legal types ("widening"). If a vector gets split
|
|
|
893 all the way down to single-element parts with no supported vector type being
|
|
|
894 found, the elements are converted to scalars ("scalarizing").
|
|
|
895
|
|
|
896 A target implementation tells the legalizer which types are supported (and which
|
|
|
897 register class to use for them) by calling the ``addRegisterClass`` method in
|
|
|
898 its ``TargetLowering`` constructor.
|
|
|
899
|
|
|
900 .. _legalize operations:
|
|
|
901 .. _Legalizer:
|
|
|
902
|
|
|
903 SelectionDAG Legalize Phase
|
|
|
904 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
905
|
|
|
906 The Legalize phase is in charge of converting a DAG to only use the operations
|
|
|
907 that are natively supported by the target.
|
|
|
908
|
|
|
909 Targets often have weird constraints, such as not supporting every operation on
|
|
|
910 every supported datatype (e.g. X86 does not support byte conditional moves and
|
|
|
911 PowerPC does not support sign-extending loads from a 16-bit memory location).
|
|
|
912 Legalize takes care of this by open-coding another sequence of operations to
|
|
|
913 emulate the operation ("expansion"), by promoting one type to a larger type that
|
|
|
914 supports the operation ("promotion"), or by using a target-specific hook to
|
|
|
915 implement the legalization ("custom").
|
|
|
916
|
|
|
917 A target implementation tells the legalizer which operations are not supported
|
|
|
918 (and which of the above three actions to take) by calling the
|
|
|
919 ``setOperationAction`` method in its ``TargetLowering`` constructor.
|
|
|
920
|
|
|
921 If a target has legal vector types, it is expected to produce efficient machine
|
|
|
922 code for common forms of the shufflevector IR instruction using those types.
|
|
|
923 This may require custom legalization for SelectionDAG vector operations that
|
|
|
924 are created from the shufflevector IR. The shufflevector forms that should be
|
|
|
925 handled include:
|
|
|
926
|
|
|
927 * Vector select --- Each element of the vector is chosen from either of the
|
|
|
928 corresponding elements of the 2 input vectors. This operation may also be
|
|
|
929 known as a "blend" or "bitwise select" in target assembly. This type of shuffle
|
|
|
930 maps directly to the ``shuffle_vector`` SelectionDAG node.
|
|
|
931
|
|
|
932 * Insert subvector --- A vector is placed into a longer vector type starting
|
|
|
933 at index 0. This type of shuffle maps directly to the ``insert_subvector``
|
|
|
934 SelectionDAG node with the ``index`` operand set to 0.
|
|
|
935
|
|
|
936 * Extract subvector --- A vector is pulled from a longer vector type starting
|
|
|
937 at index 0. This type of shuffle maps directly to the ``extract_subvector``
|
|
|
938 SelectionDAG node with the ``index`` operand set to 0.
|
|
|
939
|
|
|
940 * Splat --- All elements of the vector have identical scalar elements. This
|
|
|
941 operation may also be known as a "broadcast" or "duplicate" in target assembly.
|
|
|
942 The shufflevector IR instruction may change the vector length, so this operation
|
|
|
943 may map to multiple SelectionDAG nodes including ``shuffle_vector``,
|
|
|
944 ``concat_vectors``, ``insert_subvector``, and ``extract_subvector``.
|
|
|
945
|
|
|
946 Prior to the existence of the Legalize passes, we required that every target
|
|
|
947 `selector`_ supported and handled every operator and type even if they are not
|
|
|
948 natively supported. The introduction of the Legalize phases allows all of the
|
|
|
949 canonicalization patterns to be shared across targets, and makes it very easy to
|
|
|
950 optimize the canonicalized code because it is still in the form of a DAG.
|
|
|
951
|
|
|
952 .. _optimizations:
|
|
|
953 .. _Optimize SelectionDAG:
|
|
|
954 .. _selector:
|
|
|
955
|
|
|
956 SelectionDAG Optimization Phase: the DAG Combiner
|
|
|
957 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
958
|
|
|
959 The SelectionDAG optimization phase is run multiple times for code generation,
|
|
|
960 immediately after the DAG is built and once after each legalization. The first
|
|
|
961 run of the pass allows the initial code to be cleaned up (e.g. performing
|
|
|
962 optimizations that depend on knowing that the operators have restricted type
|
|
|
963 inputs). Subsequent runs of the pass clean up the messy code generated by the
|
|
|
964 Legalize passes, which allows Legalize to be very simple (it can focus on making
|
|
|
965 code legal instead of focusing on generating *good* and legal code).
|
|
|
966
|
|
|
967 One important class of optimizations performed is optimizing inserted sign and
|
|
|
968 zero extension instructions. We currently use ad-hoc techniques, but could move
|
|
|
969 to more rigorous techniques in the future. Here are some good papers on the
|
|
|
970 subject:
|
|
|
971
|
|
|
972 "`Widening integer arithmetic <http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html>`_" :raw-html:`<br>`
|
|
|
973 Kevin Redwine and Norman Ramsey :raw-html:`<br>`
|
|
|
974 International Conference on Compiler Construction (CC) 2004
|
|
|
975
|
|
|
976 "`Effective sign extension elimination <http://portal.acm.org/citation.cfm?doid=512529.512552>`_" :raw-html:`<br>`
|
|
|
977 Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani :raw-html:`<br>`
|
|
|
978 Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
|
|
|
979 and Implementation.
|
|
|
980
|
|
|
981 .. _Select instructions from DAG:
|
|
|
982
|
|
|
983 SelectionDAG Select Phase
|
|
|
984 ^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
985
|
|
|
986 The Select phase is the bulk of the target-specific code for instruction
|
|
|
987 selection. This phase takes a legal SelectionDAG as input, pattern matches the
|
|
|
988 instructions supported by the target to this DAG, and produces a new DAG of
|
|
|
989 target code. For example, consider the following LLVM fragment:
|
|
|
990
|
|
|
991 .. code-block:: llvm
|
|
|
992
|
|
|
993 %t1 = fadd float %W, %X
|
|
|
994 %t2 = fmul float %t1, %Y
|
|
|
995 %t3 = fadd float %t2, %Z
|
|
|
996
|
|
|
997 This LLVM code corresponds to a SelectionDAG that looks basically like this:
|
|
|
998
|
|
|
999 .. code-block:: text
|
|
|
1000
|
|
|
1001 (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
|
|
|
1002
|
|
|
1003 If a target supports floating point multiply-and-add (FMA) operations, one of
|
|
|
1004 the adds can be merged with the multiply. On the PowerPC, for example, the
|
|
|
1005 output of the instruction selector might look like this DAG:
|
|
|
1006
|
|
|
1007 ::
|
|
|
1008
|
|
|
1009 (FMADDS (FADDS W, X), Y, Z)
|
|
|
1010
|
|
|
1011 The ``FMADDS`` instruction is a ternary instruction that multiplies its first
|
|
|
1012 two operands and adds the third (as single-precision floating-point numbers).
|
|
|
1013 The ``FADDS`` instruction is a simple binary single-precision add instruction.
|
|
|
1014 To perform this pattern match, the PowerPC backend includes the following
|
|
|
1015 instruction definitions:
|
|
|
1016
|
|
|
1017 .. code-block:: text
|
|
|
1018 :emphasize-lines: 4-5,9
|
|
|
1019
|
|
|
1020 def FMADDS : AForm_1<59, 29,
|
|
|
1021 (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
|
|
|
1022 "fmadds $FRT, $FRA, $FRC, $FRB",
|
|
|
1023 [(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
|
|
|
1024 F4RC:$FRB))]>;
|
|
|
1025 def FADDS : AForm_2<59, 21,
|
|
|
1026 (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
|
|
|
1027 "fadds $FRT, $FRA, $FRB",
|
|
|
1028 [(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;
|
|
|
1029
|
|
|
1030 The highlighted portion of the instruction definitions indicates the pattern
|
|
|
1031 used to match the instructions. The DAG operators (like ``fmul``/``fadd``)
|
|
|
1032 are defined in the ``include/llvm/Target/TargetSelectionDAG.td`` file.
|
|
|
1033 "``F4RC``" is the register class of the input and result values.
|
|
|
1034
|
|
|
1035 The TableGen DAG instruction selector generator reads the instruction patterns
|
|
|
1036 in the ``.td`` file and automatically builds parts of the pattern matching code
|
|
|
1037 for your target. It has the following strengths:
|
|
|
1038
|
|
|
1039 * At compiler-compile time, it analyzes your instruction patterns and tells you
|
|
|
1040 if your patterns make sense or not.
|
|
|
1041
|
|
|
1042 * It can handle arbitrary constraints on operands for the pattern match. In
|
|
|
1043 particular, it is straight-forward to say things like "match any immediate
|
|
|
1044 that is a 13-bit sign-extended value". For examples, see the ``immSExt16``
|
|
|
1045 and related ``tblgen`` classes in the PowerPC backend.
|
|
|
1046
|
|
|
1047 * It knows several important identities for the patterns defined. For example,
|
|
|
1048 it knows that addition is commutative, so it allows the ``FMADDS`` pattern
|
|
|
1049 above to match "``(fadd X, (fmul Y, Z))``" as well as "``(fadd (fmul X, Y),
|
|
|
1050 Z)``", without the target author having to specially handle this case.
|
|
|
1051
|
|
|
1052 * It has a full-featured type-inferencing system. In particular, you should
|
|
|
1053 rarely have to explicitly tell the system what type parts of your patterns
|
|
|
1054 are. In the ``FMADDS`` case above, we didn't have to tell ``tblgen`` that all
|
|
|
1055 of the nodes in the pattern are of type 'f32'. It was able to infer and
|
|
|
1056 propagate this knowledge from the fact that ``F4RC`` has type 'f32'.
|
|
|
1057
|
|
|
1058 * Targets can define their own (and rely on built-in) "pattern fragments".
|
|
|
1059 Pattern fragments are chunks of reusable patterns that get inlined into your
|
|
|
1060 patterns during compiler-compile time. For example, the integer "``(not
|
|
|
1061 x)``" operation is actually defined as a pattern fragment that expands as
|
|
|
1062 "``(xor x, -1)``", since the SelectionDAG does not have a native '``not``'
|
|
|
1063 operation. Targets can define their own short-hand fragments as they see fit.
|
|
|
1064 See the definition of '``not``' and '``ineg``' for examples.
|
|
|
1065
|
|
|
1066 * In addition to instructions, targets can specify arbitrary patterns that map
|
|
|
1067 to one or more instructions using the 'Pat' class. For example, the PowerPC
|
|
|
1068 has no way to load an arbitrary integer immediate into a register in one
|
|
|
1069 instruction. To tell tblgen how to do this, it defines:
|
|
|
1070
|
|
|
1071 ::
|
|
|
1072
|
|
|
1073 // Arbitrary immediate support. Implement in terms of LIS/ORI.
|
|
|
1074 def : Pat<(i32 imm:$imm),
|
|
|
1075 (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
|
|
|
1076
|
|
|
1077 If none of the single-instruction patterns for loading an immediate into a
|
|
|
1078 register match, this will be used. This rule says "match an arbitrary i32
|
|
|
1079 immediate, turning it into an ``ORI`` ('or a 16-bit immediate') and an ``LIS``
|
|
|
1080 ('load 16-bit immediate, where the immediate is shifted to the left 16 bits')
|
|
|
1081 instruction". To make this work, the ``LO16``/``HI16`` node transformations
|
|
|
1082 are used to manipulate the input immediate (in this case, take the high or low
|
|
|
1083 16-bits of the immediate).
|
|
|
1084
|
|
|
1085 * When using the 'Pat' class to map a pattern to an instruction that has one
|
|
|
1086 or more complex operands (like e.g. `X86 addressing mode`_), the pattern may
|
|
|
1087 either specify the operand as a whole using a ``ComplexPattern``, or else it
|
|
|
1088 may specify the components of the complex operand separately. The latter is
|
|
|
1089 done e.g. for pre-increment instructions by the PowerPC back end:
|
|
|
1090
|
|
|
1091 ::
|
|
|
1092
|
|
|
1093 def STWU : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),
|
|
|
1094 "stwu $rS, $dst", LdStStoreUpd, []>,
|
|
|
1095 RegConstraint<"$dst.reg = $ea_res">, NoEncode<"$ea_res">;
|
|
|
1096
|
|
|
1097 def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),
|
|
|
1098 (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;
|
|
|
1099
|
|
|
1100 Here, the pair of ``ptroff`` and ``ptrreg`` operands is matched onto the
|
|
|
1101 complex operand ``dst`` of class ``memri`` in the ``STWU`` instruction.
|
|
|
1102
|
|
|
1103 * While the system does automate a lot, it still allows you to write custom C++
|
|
|
1104 code to match special cases if there is something that is hard to
|
|
|
1105 express.
|
|
|
1106
|
|
|
1107 While it has many strengths, the system currently has some limitations,
|
|
|
1108 primarily because it is a work in progress and is not yet finished:
|
|
|
1109
|
|
|
1110 * Overall, there is no way to define or match SelectionDAG nodes that define
|
|
|
1111 multiple values (e.g. ``SMUL_LOHI``, ``LOAD``, ``CALL``, etc). This is the
|
|
|
1112 biggest reason that you currently still *have to* write custom C++ code
|
|
|
1113 for your instruction selector.
|
|
|
1114
|
|
|
1115 * There is no great way to support matching complex addressing modes yet. In
|
|
|
1116 the future, we will extend pattern fragments to allow them to define multiple
|
|
|
1117 values (e.g. the four operands of the `X86 addressing mode`_, which are
|
|
|
1118 currently matched with custom C++ code). In addition, we'll extend fragments
|
|
|
1119 so that a fragment can match multiple different patterns.
|
|
|
1120
|
|
|
1121 * We don't automatically infer flags like ``isStore``/``isLoad`` yet.
|
|
|
1122
|
|
|
1123 * We don't automatically generate the set of supported registers and operations
|
|
|
1124 for the `Legalizer`_ yet.
|
|
|
1125
|
|
|
1126 * We don't have a way of tying in custom legalized nodes yet.
|
|
|
1127
|
|
|
1128 Despite these limitations, the instruction selector generator is still quite
|
|
|
1129 useful for most of the binary and logical operations in typical instruction
|
|
|
1130 sets. If you run into any problems or can't figure out how to do something,
|
|
|
1131 please let Chris know!
|
|
|
1132
|
|
|
1133 .. _Scheduling and Formation:
|
|
|
1134 .. _SelectionDAG Scheduling and Formation:
|
|
|
1135
|
|
|
1136 SelectionDAG Scheduling and Formation Phase
|
|
|
1137 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1138
|
|
|
1139 The scheduling phase takes the DAG of target instructions from the selection
|
|
|
1140 phase and assigns an order. The scheduler can pick an order depending on
|
|
|
1141 various constraints of the machines (i.e. order for minimal register pressure or
|
|
|
1142 try to cover instruction latencies). Once an order is established, the DAG is
|
|
|
1143 converted to a list of :raw-html:`<tt>` `MachineInstr`_\s :raw-html:`</tt>` and
|
|
|
1144 the SelectionDAG is destroyed.
|
|
|
1145
|
|
|
1146 Note that this phase is logically separate from the instruction selection phase,
|
|
|
1147 but is tied to it closely in the code because it operates on SelectionDAGs.
|
|
|
1148
|
|
|
1149 Future directions for the SelectionDAG
|
|
|
1150 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1151
|
|
|
1152 #. Optional function-at-a-time selection.
|
|
|
1153
|
|
|
1154 #. Auto-generate entire selector from ``.td`` file.
|
|
|
1155
|
|
|
1156 .. _SSA-based Machine Code Optimizations:
|
|
|
1157
|
|
|
1158 SSA-based Machine Code Optimizations
|
|
|
1159 ------------------------------------
|
|
|
1160
|
|
|
1161 To Be Written
|
|
|
1162
|
|
|
1163 Live Intervals
|
|
|
1164 --------------
|
|
|
1165
|
|
|
1166 Live Intervals are the ranges (intervals) where a variable is *live*. They are
|
|
|
1167 used by some `register allocator`_ passes to determine if two or more virtual
|
|
|
1168 registers which require the same physical register are live at the same point in
|
|
|
1169 the program (i.e., they conflict). When this situation occurs, one virtual
|
|
|
1170 register must be *spilled*.
|
|
|
1171
|
|
|
1172 Live Variable Analysis
|
|
|
1173 ^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1174
|
|
|
1175 The first step in determining the live intervals of variables is to calculate
|
|
|
1176 the set of registers that are immediately dead after the instruction (i.e., the
|
|
|
1177 instruction calculates the value, but it is never used) and the set of registers
|
|
|
1178 that are used by the instruction, but are never used after the instruction
|
|
|
1179 (i.e., they are killed). Live variable information is computed for
|
|
|
1180 each *virtual* register and *register allocatable* physical register
|
|
|
1181 in the function. This is done in a very efficient manner because it uses SSA to
|
|
|
1182 sparsely compute lifetime information for virtual registers (which are in SSA
|
|
|
1183 form) and only has to track physical registers within a block. Before register
|
|
|
1184 allocation, LLVM can assume that physical registers are only live within a
|
|
|
1185 single basic block. This allows it to do a single, local analysis to resolve
|
|
|
1186 physical register lifetimes within each basic block. If a physical register is
|
|
|
1187 not register allocatable (e.g., a stack pointer or condition codes), it is not
|
|
|
1188 tracked.
|
|
|
1189
|
|
|
1190 Physical registers may be live in to or out of a function. Live in values are
|
|
|
1191 typically arguments in registers. Live out values are typically return values in
|
|
|
1192 registers. Live in values are marked as such, and are given a dummy "defining"
|
|
|
1193 instruction during live intervals analysis. If the last basic block of a
|
|
|
1194 function is a ``return``, then it's marked as using all live out values in the
|
|
|
1195 function.
|
|
|
1196
|
|
|
1197 ``PHI`` nodes need to be handled specially, because the calculation of the live
|
|
|
1198 variable information from a depth first traversal of the CFG of the function
|
|
|
1199 won't guarantee that a virtual register used by the ``PHI`` node is defined
|
|
|
1200 before it's used. When a ``PHI`` node is encountered, only the definition is
|
|
|
1201 handled, because the uses will be handled in other basic blocks.
|
|
|
1202
|
|
|
1203 For each ``PHI`` node of the current basic block, we simulate an assignment at
|
|
|
1204 the end of the current basic block and traverse the successor basic blocks. If a
|
|
|
1205 successor basic block has a ``PHI`` node and one of the ``PHI`` node's operands
|
|
|
1206 is coming from the current basic block, then the variable is marked as *alive*
|
|
|
1207 within the current basic block and all of its predecessor basic blocks, until
|
|
|
1208 the basic block with the defining instruction is encountered.
|
|
|
1209
|
|
|
1210 Live Intervals Analysis
|
|
|
1211 ^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1212
|
|
|
1213 We now have the information available to perform the live intervals analysis and
|
|
|
1214 build the live intervals themselves. We start off by numbering the basic blocks
|
|
|
1215 and machine instructions. We then handle the "live-in" values. These are in
|
|
|
1216 physical registers, so the physical register is assumed to be killed by the end
|
|
|
1217 of the basic block. Live intervals for virtual registers are computed for some
|
|
|
1218 ordering of the machine instructions ``[1, N]``. A live interval is an interval
|
|
|
1219 ``[i, j)``, where ``1 >= i >= j > N``, for which a variable is live.
|
|
|
1220
|
|
|
1221 .. note::
|
|
|
1222 More to come...
|
|
|
1223
|
|
|
1224 .. _Register Allocation:
|
|
|
1225 .. _register allocator:
|
|
|
1226
|
|
|
1227 Register Allocation
|
|
|
1228 -------------------
|
|
|
1229
|
|
|
1230 The *Register Allocation problem* consists in mapping a program
|
|
|
1231 :raw-html:`<b><tt>` P\ :sub:`v`\ :raw-html:`</tt></b>`, that can use an unbounded
|
|
|
1232 number of virtual registers, to a program :raw-html:`<b><tt>` P\ :sub:`p`\
|
|
|
1233 :raw-html:`</tt></b>` that contains a finite (possibly small) number of physical
|
|
|
1234 registers. Each target architecture has a different number of physical
|
|
|
1235 registers. If the number of physical registers is not enough to accommodate all
|
|
|
1236 the virtual registers, some of them will have to be mapped into memory. These
|
|
|
1237 virtuals are called *spilled virtuals*.
|
|
|
1238
|
|
|
1239 How registers are represented in LLVM
|
|
|
1240 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1241
|
|
|
1242 In LLVM, physical registers are denoted by integer numbers that normally range
|
|
|
1243 from 1 to 1023. To see how this numbering is defined for a particular
|
|
|
1244 architecture, you can read the ``GenRegisterNames.inc`` file for that
|
|
|
1245 architecture. For instance, by inspecting
|
|
|
1246 ``lib/Target/X86/X86GenRegisterInfo.inc`` we see that the 32-bit register
|
|
|
1247 ``EAX`` is denoted by 43, and the MMX register ``MM0`` is mapped to 65.
|
|
|
1248
|
|
|
1249 Some architectures contain registers that share the same physical location. A
|
|
|
1250 notable example is the X86 platform. For instance, in the X86 architecture, the
|
|
|
1251 registers ``EAX``, ``AX`` and ``AL`` share the first eight bits. These physical
|
|
|
1252 registers are marked as *aliased* in LLVM. Given a particular architecture, you
|
|
|
1253 can check which registers are aliased by inspecting its ``RegisterInfo.td``
|
|
|
1254 file. Moreover, the class ``MCRegAliasIterator`` enumerates all the physical
|
|
|
1255 registers aliased to a register.
|
|
|
1256
|
|
|
1257 Physical registers, in LLVM, are grouped in *Register Classes*. Elements in the
|
|
|
1258 same register class are functionally equivalent, and can be interchangeably
|
|
|
1259 used. Each virtual register can only be mapped to physical registers of a
|
|
|
1260 particular class. For instance, in the X86 architecture, some virtuals can only
|
|
|
1261 be allocated to 8 bit registers. A register class is described by
|
|
|
1262 ``TargetRegisterClass`` objects. To discover if a virtual register is
|
|
|
1263 compatible with a given physical, this code can be used:
|
|
|
1264
|
|
|
1265 .. code-block:: c++
|
|
|
1266
|
|
|
1267 bool RegMapping_Fer::compatible_class(MachineFunction &mf,
|
|
|
1268 unsigned v_reg,
|
|
|
1269 unsigned p_reg) {
|
|
|
1270 assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
|
|
|
1271 "Target register must be physical");
|
|
|
1272 const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
|
|
|
1273 return trc->contains(p_reg);
|
|
|
1274 }
|
|
|
1275
|
|
|
1276 Sometimes, mostly for debugging purposes, it is useful to change the number of
|
|
|
1277 physical registers available in the target architecture. This must be done
|
|
|
1278 statically, inside the ``TargetRegisterInfo.td`` file. Just ``grep`` for
|
|
|
1279 ``RegisterClass``, the last parameter of which is a list of registers. Just
|
|
|
1280 commenting some out is one simple way to avoid them being used. A more polite
|
|
|
1281 way is to explicitly exclude some registers from the *allocation order*. See the
|
|
|
1282 definition of the ``GR8`` register class in
|
|
|
1283 ``lib/Target/X86/X86RegisterInfo.td`` for an example of this.
|
|
|
1284
|
|
|
1285 Virtual registers are also denoted by integer numbers. Contrary to physical
|
|
|
1286 registers, different virtual registers never share the same number. Whereas
|
|
|
1287 physical registers are statically defined in a ``TargetRegisterInfo.td`` file
|
|
|
1288 and cannot be created by the application developer, that is not the case with
|
|
|
1289 virtual registers. In order to create new virtual registers, use the method
|
|
|
1290 ``MachineRegisterInfo::createVirtualRegister()``. This method will return a new
|
|
|
1291 virtual register. Use an ``IndexedMap<Foo, VirtReg2IndexFunctor>`` to hold
|
|
|
1292 information per virtual register. If you need to enumerate all virtual
|
|
|
1293 registers, use the function ``TargetRegisterInfo::index2VirtReg()`` to find the
|
|
|
1294 virtual register numbers:
|
|
|
1295
|
|
|
1296 .. code-block:: c++
|
|
|
1297
|
|
|
1298 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
|
|
|
1299 unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);
|
|
|
1300 stuff(VirtReg);
|
|
|
1301 }
|
|
|
1302
|
|
|
1303 Before register allocation, the operands of an instruction are mostly virtual
|
|
|
1304 registers, although physical registers may also be used. In order to check if a
|
|
|
1305 given machine operand is a register, use the boolean function
|
|
|
1306 ``MachineOperand::isRegister()``. To obtain the integer code of a register, use
|
|
|
1307 ``MachineOperand::getReg()``. An instruction may define or use a register. For
|
|
|
1308 instance, ``ADD reg:1026 := reg:1025 reg:1024`` defines the registers 1024, and
|
|
|
1309 uses registers 1025 and 1026. Given a register operand, the method
|
|
|
1310 ``MachineOperand::isUse()`` informs if that register is being used by the
|
|
|
1311 instruction. The method ``MachineOperand::isDef()`` informs if that registers is
|
|
|
1312 being defined.
|
|
|
1313
|
|
|
1314 We will call physical registers present in the LLVM bitcode before register
|
|
|
1315 allocation *pre-colored registers*. Pre-colored registers are used in many
|
|
|
1316 different situations, for instance, to pass parameters of functions calls, and
|
|
|
1317 to store results of particular instructions. There are two types of pre-colored
|
|
|
1318 registers: the ones *implicitly* defined, and those *explicitly*
|
|
|
1319 defined. Explicitly defined registers are normal operands, and can be accessed
|
|
|
1320 with ``MachineInstr::getOperand(int)::getReg()``. In order to check which
|
|
|
1321 registers are implicitly defined by an instruction, use the
|
|
|
1322 ``TargetInstrInfo::get(opcode)::ImplicitDefs``, where ``opcode`` is the opcode
|
|
|
1323 of the target instruction. One important difference between explicit and
|
|
|
1324 implicit physical registers is that the latter are defined statically for each
|
|
|
1325 instruction, whereas the former may vary depending on the program being
|
|
|
1326 compiled. For example, an instruction that represents a function call will
|
|
|
1327 always implicitly define or use the same set of physical registers. To read the
|
|
|
1328 registers implicitly used by an instruction, use
|
|
|
1329 ``TargetInstrInfo::get(opcode)::ImplicitUses``. Pre-colored registers impose
|
|
|
1330 constraints on any register allocation algorithm. The register allocator must
|
|
|
1331 make sure that none of them are overwritten by the values of virtual registers
|
|
|
1332 while still alive.
|
|
|
1333
|
|
|
1334 Mapping virtual registers to physical registers
|
|
|
1335 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1336
|
|
|
1337 There are two ways to map virtual registers to physical registers (or to memory
|
|
|
1338 slots). The first way, that we will call *direct mapping*, is based on the use
|
|
|
1339 of methods of the classes ``TargetRegisterInfo``, and ``MachineOperand``. The
|
|
|
1340 second way, that we will call *indirect mapping*, relies on the ``VirtRegMap``
|
|
|
1341 class in order to insert loads and stores sending and getting values to and from
|
|
|
1342 memory.
|
|
|
1343
|
|
|
1344 The direct mapping provides more flexibility to the developer of the register
|
|
|
1345 allocator; however, it is more error prone, and demands more implementation
|
|
|
1346 work. Basically, the programmer will have to specify where load and store
|
|
|
1347 instructions should be inserted in the target function being compiled in order
|
|
|
1348 to get and store values in memory. To assign a physical register to a virtual
|
|
|
1349 register present in a given operand, use ``MachineOperand::setReg(p_reg)``. To
|
|
|
1350 insert a store instruction, use ``TargetInstrInfo::storeRegToStackSlot(...)``,
|
|
|
1351 and to insert a load instruction, use ``TargetInstrInfo::loadRegFromStackSlot``.
|
|
|
1352
|
|
|
1353 The indirect mapping shields the application developer from the complexities of
|
|
|
1354 inserting load and store instructions. In order to map a virtual register to a
|
|
|
1355 physical one, use ``VirtRegMap::assignVirt2Phys(vreg, preg)``. In order to map
|
|
|
1356 a certain virtual register to memory, use
|
|
|
1357 ``VirtRegMap::assignVirt2StackSlot(vreg)``. This method will return the stack
|
|
|
1358 slot where ``vreg``'s value will be located. If it is necessary to map another
|
|
|
1359 virtual register to the same stack slot, use
|
|
|
1360 ``VirtRegMap::assignVirt2StackSlot(vreg, stack_location)``. One important point
|
|
|
1361 to consider when using the indirect mapping, is that even if a virtual register
|
|
|
1362 is mapped to memory, it still needs to be mapped to a physical register. This
|
|
|
1363 physical register is the location where the virtual register is supposed to be
|
|
|
1364 found before being stored or after being reloaded.
|
|
|
1365
|
|
|
1366 If the indirect strategy is used, after all the virtual registers have been
|
|
|
1367 mapped to physical registers or stack slots, it is necessary to use a spiller
|
|
|
1368 object to place load and store instructions in the code. Every virtual that has
|
|
|
1369 been mapped to a stack slot will be stored to memory after being defined and will
|
|
|
1370 be loaded before being used. The implementation of the spiller tries to recycle
|
|
|
1371 load/store instructions, avoiding unnecessary instructions. For an example of
|
|
|
1372 how to invoke the spiller, see ``RegAllocLinearScan::runOnMachineFunction`` in
|
|
|
1373 ``lib/CodeGen/RegAllocLinearScan.cpp``.
|
|
|
1374
|
|
|
1375 Handling two address instructions
|
|
|
1376 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1377
|
|
|
1378 With very rare exceptions (e.g., function calls), the LLVM machine code
|
|
|
1379 instructions are three address instructions. That is, each instruction is
|
|
|
1380 expected to define at most one register, and to use at most two registers.
|
|
|
1381 However, some architectures use two address instructions. In this case, the
|
|
|
1382 defined register is also one of the used registers. For instance, an instruction
|
|
|
1383 such as ``ADD %EAX, %EBX``, in X86 is actually equivalent to ``%EAX = %EAX +
|
|
|
1384 %EBX``.
|
|
|
1385
|
|
|
1386 In order to produce correct code, LLVM must convert three address instructions
|
|
|
1387 that represent two address instructions into true two address instructions. LLVM
|
|
|
1388 provides the pass ``TwoAddressInstructionPass`` for this specific purpose. It
|
|
|
1389 must be run before register allocation takes place. After its execution, the
|
|
|
1390 resulting code may no longer be in SSA form. This happens, for instance, in
|
|
|
1391 situations where an instruction such as ``%a = ADD %b %c`` is converted to two
|
|
|
1392 instructions such as:
|
|
|
1393
|
|
|
1394 ::
|
|
|
1395
|
|
|
1396 %a = MOVE %b
|
|
|
1397 %a = ADD %a %c
|
|
|
1398
|
|
|
1399 Notice that, internally, the second instruction is represented as ``ADD
|
|
|
1400 %a[def/use] %c``. I.e., the register operand ``%a`` is both used and defined by
|
|
|
1401 the instruction.
|
|
|
1402
|
|
|
1403 The SSA deconstruction phase
|
|
|
1404 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1405
|
|
|
1406 An important transformation that happens during register allocation is called
|
|
|
1407 the *SSA Deconstruction Phase*. The SSA form simplifies many analyses that are
|
|
|
1408 performed on the control flow graph of programs. However, traditional
|
|
|
1409 instruction sets do not implement PHI instructions. Thus, in order to generate
|
|
|
1410 executable code, compilers must replace PHI instructions with other instructions
|
|
|
1411 that preserve their semantics.
|
|
|
1412
|
|
|
1413 There are many ways in which PHI instructions can safely be removed from the
|
|
|
1414 target code. The most traditional PHI deconstruction algorithm replaces PHI
|
|
|
1415 instructions with copy instructions. That is the strategy adopted by LLVM. The
|
|
|
1416 SSA deconstruction algorithm is implemented in
|
|
|
1417 ``lib/CodeGen/PHIElimination.cpp``. In order to invoke this pass, the identifier
|
|
|
1418 ``PHIEliminationID`` must be marked as required in the code of the register
|
|
|
1419 allocator.
|
|
|
1420
|
|
|
1421 Instruction folding
|
|
|
1422 ^^^^^^^^^^^^^^^^^^^
|
|
|
1423
|
|
|
1424 *Instruction folding* is an optimization performed during register allocation
|
|
|
1425 that removes unnecessary copy instructions. For instance, a sequence of
|
|
|
1426 instructions such as:
|
|
|
1427
|
|
|
1428 ::
|
|
|
1429
|
|
|
1430 %EBX = LOAD %mem_address
|
|
|
1431 %EAX = COPY %EBX
|
|
|
1432
|
|
|
1433 can be safely substituted by the single instruction:
|
|
|
1434
|
|
|
1435 ::
|
|
|
1436
|
|
|
1437 %EAX = LOAD %mem_address
|
|
|
1438
|
|
|
1439 Instructions can be folded with the
|
|
|
1440 ``TargetRegisterInfo::foldMemoryOperand(...)`` method. Care must be taken when
|
|
|
1441 folding instructions; a folded instruction can be quite different from the
|
|
|
1442 original instruction. See ``LiveIntervals::addIntervalsForSpills`` in
|
|
|
1443 ``lib/CodeGen/LiveIntervalAnalysis.cpp`` for an example of its use.
|
|
|
1444
|
|
|
1445 Built in register allocators
|
|
|
1446 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1447
|
|
|
1448 The LLVM infrastructure provides the application developer with three different
|
|
|
1449 register allocators:
|
|
|
1450
|
|
|
1451 * *Fast* --- This register allocator is the default for debug builds. It
|
|
|
1452 allocates registers on a basic block level, attempting to keep values in
|
|
|
1453 registers and reusing registers as appropriate.
|
|
|
1454
|
|
|
1455 * *Basic* --- This is an incremental approach to register allocation. Live
|
|
|
1456 ranges are assigned to registers one at a time in an order that is driven by
|
|
|
1457 heuristics. Since code can be rewritten on-the-fly during allocation, this
|
|
|
1458 framework allows interesting allocators to be developed as extensions. It is
|
|
|
1459 not itself a production register allocator but is a potentially useful
|
|
|
1460 stand-alone mode for triaging bugs and as a performance baseline.
|
|
|
1461
|
|
|
1462 * *Greedy* --- *The default allocator*. This is a highly tuned implementation of
|
|
|
1463 the *Basic* allocator that incorporates global live range splitting. This
|
|
|
1464 allocator works hard to minimize the cost of spill code.
|
|
|
1465
|
|
|
1466 * *PBQP* --- A Partitioned Boolean Quadratic Programming (PBQP) based register
|
|
|
1467 allocator. This allocator works by constructing a PBQP problem representing
|
|
|
1468 the register allocation problem under consideration, solving this using a PBQP
|
|
|
1469 solver, and mapping the solution back to a register assignment.
|
|
|
1470
|
|
|
1471 The type of register allocator used in ``llc`` can be chosen with the command
|
|
|
1472 line option ``-regalloc=...``:
|
|
|
1473
|
|
|
1474 .. code-block:: bash
|
|
|
1475
|
|
|
1476 $ llc -regalloc=linearscan file.bc -o ln.s
|
|
|
1477 $ llc -regalloc=fast file.bc -o fa.s
|
|
|
1478 $ llc -regalloc=pbqp file.bc -o pbqp.s
|
|
|
1479
|
|
|
1480 .. _Prolog/Epilog Code Insertion:
|
|
|
1481
|
|
|
1482 Prolog/Epilog Code Insertion
|
|
|
1483 ----------------------------
|
|
|
1484
|
|
|
1485 Compact Unwind
|
|
|
1486
|
|
|
1487 Throwing an exception requires *unwinding* out of a function. The information on
|
|
|
1488 how to unwind a given function is traditionally expressed in DWARF unwind
|
|
|
1489 (a.k.a. frame) info. But that format was originally developed for debuggers to
|
|
|
1490 backtrace, and each Frame Description Entry (FDE) requires ~20-30 bytes per
|
|
|
1491 function. There is also the cost of mapping from an address in a function to the
|
|
|
1492 corresponding FDE at runtime. An alternative unwind encoding is called *compact
|
|
|
1493 unwind* and requires just 4-bytes per function.
|
|
|
1494
|
|
|
1495 The compact unwind encoding is a 32-bit value, which is encoded in an
|
|
|
1496 architecture-specific way. It specifies which registers to restore and from
|
|
|
1497 where, and how to unwind out of the function. When the linker creates a final
|
|
|
1498 linked image, it will create a ``__TEXT,__unwind_info`` section. This section is
|
|
|
1499 a small and fast way for the runtime to access unwind info for any given
|
|
|
1500 function. If we emit compact unwind info for the function, that compact unwind
|
|
|
1501 info will be encoded in the ``__TEXT,__unwind_info`` section. If we emit DWARF
|
|
|
1502 unwind info, the ``__TEXT,__unwind_info`` section will contain the offset of the
|
|
|
1503 FDE in the ``__TEXT,__eh_frame`` section in the final linked image.
|
|
|
1504
|
|
|
1505 For X86, there are three modes for the compact unwind encoding:
|
|
|
1506
|
|
|
1507 *Function with a Frame Pointer (``EBP`` or ``RBP``)*
|
|
|
1508 ``EBP/RBP``-based frame, where ``EBP/RBP`` is pushed onto the stack
|
|
|
1509 immediately after the return address, then ``ESP/RSP`` is moved to
|
|
|
1510 ``EBP/RBP``. Thus to unwind, ``ESP/RSP`` is restored with the current
|
|
|
1511 ``EBP/RBP`` value, then ``EBP/RBP`` is restored by popping the stack, and the
|
|
|
1512 return is done by popping the stack once more into the PC. All non-volatile
|
|
|
1513 registers that need to be restored must have been saved in a small range on
|
|
|
1514 the stack that starts ``EBP-4`` to ``EBP-1020`` (``RBP-8`` to
|
|
|
1515 ``RBP-1020``). The offset (divided by 4 in 32-bit mode and 8 in 64-bit mode)
|
|
|
1516 is encoded in bits 16-23 (mask: ``0x00FF0000``). The registers saved are
|
|
|
1517 encoded in bits 0-14 (mask: ``0x00007FFF``) as five 3-bit entries from the
|
|
|
1518 following table:
|
|
|
1519
|
|
|
1520 ============== ============= ===============
|
|
|
1521 Compact Number i386 Register x86-64 Register
|
|
|
1522 ============== ============= ===============
|
|
|
1523 1 ``EBX`` ``RBX``
|
|
|
1524 2 ``ECX`` ``R12``
|
|
|
1525 3 ``EDX`` ``R13``
|
|
|
1526 4 ``EDI`` ``R14``
|
|
|
1527 5 ``ESI`` ``R15``
|
|
|
1528 6 ``EBP`` ``RBP``
|
|
|
1529 ============== ============= ===============
|
|
|
1530
|
|
|
1531 *Frameless with a Small Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*
|
|
|
1532 To return, a constant (encoded in the compact unwind encoding) is added to the
|
|
|
1533 ``ESP/RSP``. Then the return is done by popping the stack into the PC. All
|
|
|
1534 non-volatile registers that need to be restored must have been saved on the
|
|
|
1535 stack immediately after the return address. The stack size (divided by 4 in
|
|
|
1536 32-bit mode and 8 in 64-bit mode) is encoded in bits 16-23 (mask:
|
|
|
1537 ``0x00FF0000``). There is a maximum stack size of 1024 bytes in 32-bit mode
|
|
|
1538 and 2048 in 64-bit mode. The number of registers saved is encoded in bits 9-12
|
|
|
1539 (mask: ``0x00001C00``). Bits 0-9 (mask: ``0x000003FF``) contain which
|
|
|
1540 registers were saved and their order. (See the
|
|
|
1541 ``encodeCompactUnwindRegistersWithoutFrame()`` function in
|
|
|
1542 ``lib/Target/X86FrameLowering.cpp`` for the encoding algorithm.)
|
|
|
1543
|
|
|
1544 *Frameless with a Large Constant Stack Size (``EBP`` or ``RBP`` is not used as a frame pointer)*
|
|
|
1545 This case is like the "Frameless with a Small Constant Stack Size" case, but
|
|
|
1546 the stack size is too large to encode in the compact unwind encoding. Instead
|
|
|
1547 it requires that the function contains "``subl $nnnnnn, %esp``" in its
|
|
|
1548 prolog. The compact encoding contains the offset to the ``$nnnnnn`` value in
|
|
|
1549 the function in bits 9-12 (mask: ``0x00001C00``).
|
|
|
1550
|
|
|
1551 .. _Late Machine Code Optimizations:
|
|
|
1552
|
|
|
1553 Late Machine Code Optimizations
|
|
|
1554 -------------------------------
|
|
|
1555
|
|
|
1556 .. note::
|
|
|
1557
|
|
|
1558 To Be Written
|
|
|
1559
|
|
|
1560 .. _Code Emission:
|
|
|
1561
|
|
|
1562 Code Emission
|
|
|
1563 -------------
|
|
|
1564
|
|
|
1565 The code emission step of code generation is responsible for lowering from the
|
|
|
1566 code generator abstractions (like `MachineFunction`_, `MachineInstr`_, etc) down
|
|
|
1567 to the abstractions used by the MC layer (`MCInst`_, `MCStreamer`_, etc). This
|
|
|
1568 is done with a combination of several different classes: the (misnamed)
|
|
|
1569 target-independent AsmPrinter class, target-specific subclasses of AsmPrinter
|
|
|
1570 (such as SparcAsmPrinter), and the TargetLoweringObjectFile class.
|
|
|
1571
|
|
|
1572 Since the MC layer works at the level of abstraction of object files, it doesn't
|
|
|
1573 have a notion of functions, global variables etc. Instead, it thinks about
|
|
|
1574 labels, directives, and instructions. A key class used at this time is the
|
|
|
1575 MCStreamer class. This is an abstract API that is implemented in different ways
|
|
|
1576 (e.g. to output a .s file, output an ELF .o file, etc) that is effectively an
|
|
|
1577 "assembler API". MCStreamer has one method per directive, such as EmitLabel,
|
|
|
1578 EmitSymbolAttribute, SwitchSection, etc, which directly correspond to assembly
|
|
|
1579 level directives.
|
|
|
1580
|
|
|
1581 If you are interested in implementing a code generator for a target, there are
|
|
|
1582 three important things that you have to implement for your target:
|
|
|
1583
|
|
|
1584 #. First, you need a subclass of AsmPrinter for your target. This class
|
|
|
1585 implements the general lowering process converting MachineFunction's into MC
|
|
|
1586 label constructs. The AsmPrinter base class provides a number of useful
|
|
|
1587 methods and routines, and also allows you to override the lowering process in
|
|
|
1588 some important ways. You should get much of the lowering for free if you are
|
|
|
1589 implementing an ELF, COFF, or MachO target, because the
|
|
|
1590 TargetLoweringObjectFile class implements much of the common logic.
|
|
|
1591
|
|
|
1592 #. Second, you need to implement an instruction printer for your target. The
|
|
|
1593 instruction printer takes an `MCInst`_ and renders it to a raw_ostream as
|
|
|
1594 text. Most of this is automatically generated from the .td file (when you
|
|
|
1595 specify something like "``add $dst, $src1, $src2``" in the instructions), but
|
|
|
1596 you need to implement routines to print operands.
|
|
|
1597
|
|
|
1598 #. Third, you need to implement code that lowers a `MachineInstr`_ to an MCInst,
|
|
|
1599 usually implemented in "<target>MCInstLower.cpp". This lowering process is
|
|
|
1600 often target specific, and is responsible for turning jump table entries,
|
|
|
1601 constant pool indices, global variable addresses, etc into MCLabels as
|
|
|
1602 appropriate. This translation layer is also responsible for expanding pseudo
|
|
|
1603 ops used by the code generator into the actual machine instructions they
|
|
|
1604 correspond to. The MCInsts that are generated by this are fed into the
|
|
|
1605 instruction printer or the encoder.
|
|
|
1606
|
|
|
1607 Finally, at your choosing, you can also implement a subclass of MCCodeEmitter
|
|
|
1608 which lowers MCInst's into machine code bytes and relocations. This is
|
|
|
1609 important if you want to support direct .o file emission, or would like to
|
|
|
1610 implement an assembler for your target.
|
|
|
1611
|
|
|
1612 Emitting function stack size information
|
|
|
1613 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1614
|
|
|
1615 A section containing metadata on function stack sizes will be emitted when
|
|
|
1616 ``TargetLoweringObjectFile::StackSizesSection`` is not null, and
|
|
|
1617 ``TargetOptions::EmitStackSizeSection`` is set (-stack-size-section). The
|
|
|
1618 section will contain an array of pairs of function symbol values (pointer size)
|
|
|
1619 and stack sizes (unsigned LEB128). The stack size values only include the space
|
|
|
1620 allocated in the function prologue. Functions with dynamic stack allocations are
|
|
|
1621 not included.
|
|
|
1622
|
|
|
1623 VLIW Packetizer
|
|
|
1624 ---------------
|
|
|
1625
|
|
|
1626 In a Very Long Instruction Word (VLIW) architecture, the compiler is responsible
|
|
|
1627 for mapping instructions to functional-units available on the architecture. To
|
|
|
1628 that end, the compiler creates groups of instructions called *packets* or
|
|
|
1629 *bundles*. The VLIW packetizer in LLVM is a target-independent mechanism to
|
|
|
1630 enable the packetization of machine instructions.
|
|
|
1631
|
|
|
1632 Mapping from instructions to functional units
|
|
|
1633 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1634
|
|
|
1635 Instructions in a VLIW target can typically be mapped to multiple functional
|
|
|
1636 units. During the process of packetizing, the compiler must be able to reason
|
|
|
1637 about whether an instruction can be added to a packet. This decision can be
|
|
|
1638 complex since the compiler has to examine all possible mappings of instructions
|
|
|
1639 to functional units. Therefore to alleviate compilation-time complexity, the
|
|
|
1640 VLIW packetizer parses the instruction classes of a target and generates tables
|
|
|
1641 at compiler build time. These tables can then be queried by the provided
|
|
|
1642 machine-independent API to determine if an instruction can be accommodated in a
|
|
|
1643 packet.
|
|
|
1644
|
|
|
1645 How the packetization tables are generated and used
|
|
|
1646 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
1647
|
|
|
1648 The packetizer reads instruction classes from a target's itineraries and creates
|
|
|
1649 a deterministic finite automaton (DFA) to represent the state of a packet. A DFA
|
|
|
1650 consists of three major elements: inputs, states, and transitions. The set of
|
|
|
1651 inputs for the generated DFA represents the instruction being added to a
|
|
|
1652 packet. The states represent the possible consumption of functional units by
|
|
|
1653 instructions in a packet. In the DFA, transitions from one state to another
|
|
|
1654 occur on the addition of an instruction to an existing packet. If there is a
|
|
|
1655 legal mapping of functional units to instructions, then the DFA contains a
|
|
|
1656 corresponding transition. The absence of a transition indicates that a legal
|
|
|
1657 mapping does not exist and that the instruction cannot be added to the packet.
|
|
|
1658
|
|
|
1659 To generate tables for a VLIW target, add *Target*\ GenDFAPacketizer.inc as a
|
|
|
1660 target to the Makefile in the target directory. The exported API provides three
|
|
|
1661 functions: ``DFAPacketizer::clearResources()``,
|
|
|
1662 ``DFAPacketizer::reserveResources(MachineInstr *MI)``, and
|
|
|
1663 ``DFAPacketizer::canReserveResources(MachineInstr *MI)``. These functions allow
|
|
|
1664 a target packetizer to add an instruction to an existing packet and to check
|
|
|
1665 whether an instruction can be added to a packet. See
|
|
|
1666 ``llvm/CodeGen/DFAPacketizer.h`` for more information.
|
|
|
1667
|
|
|
1668 Implementing a Native Assembler
|
|
|
1669 ===============================
|
|
|
1670
|
|
|
1671 Though you're probably reading this because you want to write or maintain a
|
|
|
1672 compiler backend, LLVM also fully supports building a native assembler.
|
|
|
1673 We've tried hard to automate the generation of the assembler from the .td files
|
|
|
1674 (in particular the instruction syntax and encodings), which means that a large
|
|
|
1675 part of the manual and repetitive data entry can be factored and shared with the
|
|
|
1676 compiler.
|
|
|
1677
|
|
|
1678 Instruction Parsing
|
|
|
1679 -------------------
|
|
|
1680
|
|
|
1681 .. note::
|
|
|
1682
|
|
|
1683 To Be Written
|
|
|
1684
|
|
|
1685
|
|
|
1686 Instruction Alias Processing
|
|
|
1687 ----------------------------
|
|
|
1688
|
|
|
1689 Once the instruction is parsed, it enters the MatchInstructionImpl function.
|
|
|
1690 The MatchInstructionImpl function performs alias processing and then does actual
|
|
|
1691 matching.
|
|
|
1692
|
|
|
1693 Alias processing is the phase that canonicalizes different lexical forms of the
|
|
|
1694 same instructions down to one representation. There are several different kinds
|
|
|
1695 of alias that are possible to implement and they are listed below in the order
|
|
|
1696 that they are processed (which is in order from simplest/weakest to most
|
|
|
1697 complex/powerful). Generally you want to use the first alias mechanism that
|
|
|
1698 meets the needs of your instruction, because it will allow a more concise
|
|
|
1699 description.
|
|
|
1700
|
|
|
1701 Mnemonic Aliases
|
|
|
1702 ^^^^^^^^^^^^^^^^
|
|
|
1703
|
|
|
1704 The first phase of alias processing is simple instruction mnemonic remapping for
|
|
|
1705 classes of instructions which are allowed with two different mnemonics. This
|
|
|
1706 phase is a simple and unconditionally remapping from one input mnemonic to one
|
|
|
1707 output mnemonic. It isn't possible for this form of alias to look at the
|
|
|
1708 operands at all, so the remapping must apply for all forms of a given mnemonic.
|
|
|
1709 Mnemonic aliases are defined simply, for example X86 has:
|
|
|
1710
|
|
|
1711 ::
|
|
|
1712
|
|
|
1713 def : MnemonicAlias<"cbw", "cbtw">;
|
|
|
1714 def : MnemonicAlias<"smovq", "movsq">;
|
|
|
1715 def : MnemonicAlias<"fldcww", "fldcw">;
|
|
|
1716 def : MnemonicAlias<"fucompi", "fucomip">;
|
|
|
1717 def : MnemonicAlias<"ud2a", "ud2">;
|
|
|
1718
|
|
|
1719 ... and many others. With a MnemonicAlias definition, the mnemonic is remapped
|
|
|
1720 simply and directly. Though MnemonicAlias's can't look at any aspect of the
|
|
|
1721 instruction (such as the operands) they can depend on global modes (the same
|
|
|
1722 ones supported by the matcher), through a Requires clause:
|
|
|
1723
|
|
|
1724 ::
|
|
|
1725
|
|
|
1726 def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;
|
|
|
1727 def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;
|
|
|
1728
|
|
|
1729 In this example, the mnemonic gets mapped into a different one depending on
|
|
|
1730 the current instruction set.
|
|
|
1731
|
|
|
1732 Instruction Aliases
|
|
|
1733 ^^^^^^^^^^^^^^^^^^^
|
|
|
1734
|
|
|
1735 The most general phase of alias processing occurs while matching is happening:
|
|
|
1736 it provides new forms for the matcher to match along with a specific instruction
|
|
|
1737 to generate. An instruction alias has two parts: the string to match and the
|
|
|
1738 instruction to generate. For example:
|
|
|
1739
|
|
|
1740 ::
|
|
|
1741
|
|
|
1742 def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8 :$src)>;
|
|
|
1743 def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;
|
|
|
1744 def : InstAlias<"movsx $src, $dst", (MOVSX32rr8 GR32:$dst, GR8 :$src)>;
|
|
|
1745 def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;
|
|
|
1746 def : InstAlias<"movsx $src, $dst", (MOVSX64rr8 GR64:$dst, GR8 :$src)>;
|
|
|
1747 def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;
|
|
|
1748 def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;
|
|
|
1749
|
|
|
1750 This shows a powerful example of the instruction aliases, matching the same
|
|
|
1751 mnemonic in multiple different ways depending on what operands are present in
|
|
|
1752 the assembly. The result of instruction aliases can include operands in a
|
|
|
1753 different order than the destination instruction, and can use an input multiple
|
|
|
1754 times, for example:
|
|
|
1755
|
|
|
1756 ::
|
|
|
1757
|
|
|
1758 def : InstAlias<"clrb $reg", (XOR8rr GR8 :$reg, GR8 :$reg)>;
|
|
|
1759 def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;
|
|
|
1760 def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;
|
|
|
1761 def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;
|
|
|
1762
|
|
|
1763 This example also shows that tied operands are only listed once. In the X86
|
|
|
1764 backend, XOR8rr has two input GR8's and one output GR8 (where an input is tied
|
|
|
1765 to the output). InstAliases take a flattened operand list without duplicates
|
|
|
1766 for tied operands. The result of an instruction alias can also use immediates
|
|
|
1767 and fixed physical registers which are added as simple immediate operands in the
|
|
|
1768 result, for example:
|
|
|
1769
|
|
|
1770 ::
|
|
|
1771
|
|
|
1772 // Fixed Immediate operand.
|
|
|
1773 def : InstAlias<"aad", (AAD8i8 10)>;
|
|
|
1774
|
|
|
1775 // Fixed register operand.
|
|
|
1776 def : InstAlias<"fcomi", (COM_FIr ST1)>;
|
|
|
1777
|
|
|
1778 // Simple alias.
|
|
|
1779 def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;
|
|
|
1780
|
|
|
1781 Instruction aliases can also have a Requires clause to make them subtarget
|
|
|
1782 specific.
|
|
|
1783
|
|
|
1784 If the back-end supports it, the instruction printer can automatically emit the
|
|
|
1785 alias rather than what's being aliased. It typically leads to better, more
|
|
|
1786 readable code. If it's better to print out what's being aliased, then pass a '0'
|
|
|
1787 as the third parameter to the InstAlias definition.
|
|
|
1788
|
|
|
1789 Instruction Matching
|
|
|
1790 --------------------
|
|
|
1791
|
|
|
1792 .. note::
|
|
|
1793
|
|
|
1794 To Be Written
|
|
|
1795
|
|
|
1796 .. _Implementations of the abstract target description interfaces:
|
|
|
1797 .. _implement the target description:
|
|
|
1798
|
|
|
1799 Target-specific Implementation Notes
|
|
|
1800 ====================================
|
|
|
1801
|
|
|
1802 This section of the document explains features or design decisions that are
|
|
|
1803 specific to the code generator for a particular target. First we start with a
|
|
|
1804 table that summarizes what features are supported by each target.
|
|
|
1805
|
|
|
1806 .. _target-feature-matrix:
|
|
|
1807
|
|
|
1808 Target Feature Matrix
|
|
|
1809 ---------------------
|
|
|
1810
|
|
|
1811 Note that this table does not list features that are not supported fully by any
|
|
|
1812 target yet. It considers a feature to be supported if at least one subtarget
|
|
|
1813 supports it. A feature being supported means that it is useful and works for
|
|
|
1814 most cases, it does not indicate that there are zero known bugs in the
|
|
|
1815 implementation. Here is the key:
|
|
|
1816
|
|
|
1817 :raw-html:`<table border="1" cellspacing="0">`
|
|
|
1818 :raw-html:`<tr>`
|
|
|
1819 :raw-html:`<th>Unknown</th>`
|
|
|
1820 :raw-html:`<th>Not Applicable</th>`
|
|
|
1821 :raw-html:`<th>No support</th>`
|
|
|
1822 :raw-html:`<th>Partial Support</th>`
|
|
|
1823 :raw-html:`<th>Complete Support</th>`
|
|
|
1824 :raw-html:`</tr>`
|
|
|
1825 :raw-html:`<tr>`
|
|
|
1826 :raw-html:`<td class="unknown"></td>`
|
|
|
1827 :raw-html:`<td class="na"></td>`
|
|
|
1828 :raw-html:`<td class="no"></td>`
|
|
|
1829 :raw-html:`<td class="partial"></td>`
|
|
|
1830 :raw-html:`<td class="yes"></td>`
|
|
|
1831 :raw-html:`</tr>`
|
|
|
1832 :raw-html:`</table>`
|
|
|
1833
|
|
|
1834 Here is the table:
|
|
|
1835
|
|
|
1836 :raw-html:`<table width="689" border="1" cellspacing="0">`
|
|
|
1837 :raw-html:`<tr><td></td>`
|
|
|
1838 :raw-html:`<td colspan="13" align="center" style="background-color:#ffc">Target</td>`
|
|
|
1839 :raw-html:`</tr>`
|
|
|
1840 :raw-html:`<tr>`
|
|
|
1841 :raw-html:`<th>Feature</th>`
|
|
|
1842 :raw-html:`<th>ARM</th>`
|
|
|
1843 :raw-html:`<th>Hexagon</th>`
|
|
|
1844 :raw-html:`<th>MSP430</th>`
|
|
|
1845 :raw-html:`<th>Mips</th>`
|
|
|
1846 :raw-html:`<th>NVPTX</th>`
|
|
|
1847 :raw-html:`<th>PowerPC</th>`
|
|
|
1848 :raw-html:`<th>Sparc</th>`
|
|
|
1849 :raw-html:`<th>SystemZ</th>`
|
|
|
1850 :raw-html:`<th>X86</th>`
|
|
|
1851 :raw-html:`<th>XCore</th>`
|
|
|
1852 :raw-html:`<th>eBPF</th>`
|
|
|
1853 :raw-html:`</tr>`
|
|
|
1854
|
|
|
1855 :raw-html:`<tr>`
|
|
|
1856 :raw-html:`<td><a href="#feat_reliable">is generally reliable</a></td>`
|
|
|
1857 :raw-html:`<td class="yes"></td> <!-- ARM -->`
|
|
|
1858 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
|
|
|
1859 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
|
|
|
1860 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1861 :raw-html:`<td class="yes"></td> <!-- NVPTX -->`
|
|
|
1862 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1863 :raw-html:`<td class="yes"></td> <!-- Sparc -->`
|
|
|
1864 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1865 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1866 :raw-html:`<td class="yes"></td> <!-- XCore -->`
|
|
|
1867 :raw-html:`<td class="yes"></td> <!-- eBPF -->`
|
|
|
1868 :raw-html:`</tr>`
|
|
|
1869
|
|
|
1870 :raw-html:`<tr>`
|
|
|
1871 :raw-html:`<td><a href="#feat_asmparser">assembly parser</a></td>`
|
|
|
1872 :raw-html:`<td class="no"></td> <!-- ARM -->`
|
|
|
1873 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
|
|
|
1874 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
|
|
|
1875 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1876 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
|
|
|
1877 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1878 :raw-html:`<td class="no"></td> <!-- Sparc -->`
|
|
|
1879 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1880 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1881 :raw-html:`<td class="no"></td> <!-- XCore -->`
|
|
|
1882 :raw-html:`<td class="no"></td> <!-- eBPF -->`
|
|
|
1883 :raw-html:`</tr>`
|
|
|
1884
|
|
|
1885 :raw-html:`<tr>`
|
|
|
1886 :raw-html:`<td><a href="#feat_disassembler">disassembler</a></td>`
|
|
|
1887 :raw-html:`<td class="yes"></td> <!-- ARM -->`
|
|
|
1888 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
|
|
|
1889 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
|
|
|
1890 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1891 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
|
|
|
1892 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1893 :raw-html:`<td class="yes"></td> <!-- Sparc -->`
|
|
|
1894 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1895 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1896 :raw-html:`<td class="yes"></td> <!-- XCore -->`
|
|
|
1897 :raw-html:`<td class="yes"></td> <!-- eBPF -->`
|
|
|
1898 :raw-html:`</tr>`
|
|
|
1899
|
|
|
1900 :raw-html:`<tr>`
|
|
|
1901 :raw-html:`<td><a href="#feat_inlineasm">inline asm</a></td>`
|
|
|
1902 :raw-html:`<td class="yes"></td> <!-- ARM -->`
|
|
|
1903 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
|
|
|
1904 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
|
|
|
1905 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1906 :raw-html:`<td class="yes"></td> <!-- NVPTX -->`
|
|
|
1907 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1908 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
|
|
|
1909 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1910 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1911 :raw-html:`<td class="yes"></td> <!-- XCore -->`
|
|
|
1912 :raw-html:`<td class="no"></td> <!-- eBPF -->`
|
|
|
1913 :raw-html:`</tr>`
|
|
|
1914
|
|
|
1915 :raw-html:`<tr>`
|
|
|
1916 :raw-html:`<td><a href="#feat_jit">jit</a></td>`
|
|
|
1917 :raw-html:`<td class="partial"><a href="#feat_jit_arm">*</a></td> <!-- ARM -->`
|
|
|
1918 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
|
|
|
1919 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
|
|
|
1920 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1921 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
|
|
|
1922 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1923 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
|
|
|
1924 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1925 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1926 :raw-html:`<td class="no"></td> <!-- XCore -->`
|
|
|
1927 :raw-html:`<td class="yes"></td> <!-- eBPF -->`
|
|
|
1928 :raw-html:`</tr>`
|
|
|
1929
|
|
|
1930 :raw-html:`<tr>`
|
|
|
1931 :raw-html:`<td><a href="#feat_objectwrite">.o file writing</a></td>`
|
|
|
1932 :raw-html:`<td class="no"></td> <!-- ARM -->`
|
|
|
1933 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
|
|
|
1934 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
|
|
|
1935 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1936 :raw-html:`<td class="na"></td> <!-- NVPTX -->`
|
|
|
1937 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1938 :raw-html:`<td class="no"></td> <!-- Sparc -->`
|
|
|
1939 :raw-html:`<td class="yes"></td> <!-- SystemZ -->`
|
|
|
1940 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1941 :raw-html:`<td class="no"></td> <!-- XCore -->`
|
|
|
1942 :raw-html:`<td class="yes"></td> <!-- eBPF -->`
|
|
|
1943 :raw-html:`</tr>`
|
|
|
1944
|
|
|
1945 :raw-html:`<tr>`
|
|
|
1946 :raw-html:`<td><a hr:raw-html:`ef="#feat_tailcall">tail calls</a></td>`
|
|
|
1947 :raw-html:`<td class="yes"></td> <!-- ARM -->`
|
|
|
1948 :raw-html:`<td class="yes"></td> <!-- Hexagon -->`
|
|
|
1949 :raw-html:`<td class="unknown"></td> <!-- MSP430 -->`
|
|
|
1950 :raw-html:`<td class="yes"></td> <!-- Mips -->`
|
|
|
1951 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
|
|
|
1952 :raw-html:`<td class="yes"></td> <!-- PowerPC -->`
|
|
|
1953 :raw-html:`<td class="unknown"></td> <!-- Sparc -->`
|
|
|
1954 :raw-html:`<td class="no"></td> <!-- SystemZ -->`
|
|
|
1955 :raw-html:`<td class="yes"></td> <!-- X86 -->`
|
|
|
1956 :raw-html:`<td class="no"></td> <!-- XCore -->`
|
|
|
1957 :raw-html:`<td class="no"></td> <!-- eBPF -->`
|
|
|
1958 :raw-html:`</tr>`
|
|
|
1959
|
|
|
1960 :raw-html:`<tr>`
|
|
|
1961 :raw-html:`<td><a href="#feat_segstacks">segmented stacks</a></td>`
|
|
|
1962 :raw-html:`<td class="no"></td> <!-- ARM -->`
|
|
|
1963 :raw-html:`<td class="no"></td> <!-- Hexagon -->`
|
|
|
1964 :raw-html:`<td class="no"></td> <!-- MSP430 -->`
|
|
|
1965 :raw-html:`<td class="no"></td> <!-- Mips -->`
|
|
|
1966 :raw-html:`<td class="no"></td> <!-- NVPTX -->`
|
|
|
1967 :raw-html:`<td class="no"></td> <!-- PowerPC -->`
|
|
|
1968 :raw-html:`<td class="no"></td> <!-- Sparc -->`
|
|
|
1969 :raw-html:`<td class="no"></td> <!-- SystemZ -->`
|
|
|
1970 :raw-html:`<td class="partial"><a href="#feat_segstacks_x86">*</a></td> <!-- X86 -->`
|
|
|
1971 :raw-html:`<td class="no"></td> <!-- XCore -->`
|
|
|
1972 :raw-html:`<td class="no"></td> <!-- eBPF -->`
|
|
|
1973 :raw-html:`</tr>`
|
|
|
1974
|
|
|
1975 :raw-html:`</table>`
|
|
|
1976
|
|
|
1977 .. _feat_reliable:
|
|
|
1978
|
|
|
1979 Is Generally Reliable
|
|
|
1980 ^^^^^^^^^^^^^^^^^^^^^
|
|
|
1981
|
|
|
1982 This box indicates whether the target is considered to be production quality.
|
|
|
1983 This indicates that the target has been used as a static compiler to compile
|
|
|
1984 large amounts of code by a variety of different people and is in continuous use.
|
|
|
1985
|
|
|
1986 .. _feat_asmparser:
|
|
|
1987
|
|
|
1988 Assembly Parser
|
|
|
1989 ^^^^^^^^^^^^^^^
|
|
|
1990
|
|
|
1991 This box indicates whether the target supports parsing target specific .s files
|
|
|
1992 by implementing the MCAsmParser interface. This is required for llvm-mc to be
|
|
|
1993 able to act as a native assembler and is required for inline assembly support in
|
|
|
1994 the native .o file writer.
|
|
|
1995
|
|
|
1996 .. _feat_disassembler:
|
|
|
1997
|
|
|
1998 Disassembler
|
|
|
1999 ^^^^^^^^^^^^
|
|
|
2000
|
|
|
2001 This box indicates whether the target supports the MCDisassembler API for
|
|
|
2002 disassembling machine opcode bytes into MCInst's.
|
|
|
2003
|
|
|
2004 .. _feat_inlineasm:
|
|
|
2005
|
|
|
2006 Inline Asm
|
|
|
2007 ^^^^^^^^^^
|
|
|
2008
|
|
|
2009 This box indicates whether the target supports most popular inline assembly
|
|
|
2010 constraints and modifiers.
|
|
|
2011
|
|
|
2012 .. _feat_jit:
|
|
|
2013
|
|
|
2014 JIT Support
|
|
|
2015 ^^^^^^^^^^^
|
|
|
2016
|
|
|
2017 This box indicates whether the target supports the JIT compiler through the
|
|
|
2018 ExecutionEngine interface.
|
|
|
2019
|
|
|
2020 .. _feat_jit_arm:
|
|
|
2021
|
|
|
2022 The ARM backend has basic support for integer code in ARM codegen mode, but
|
|
|
2023 lacks NEON and full Thumb support.
|
|
|
2024
|
|
|
2025 .. _feat_objectwrite:
|
|
|
2026
|
|
|
2027 .o File Writing
|
|
|
2028 ^^^^^^^^^^^^^^^
|
|
|
2029
|
|
|
2030 This box indicates whether the target supports writing .o files (e.g. MachO,
|
|
|
2031 ELF, and/or COFF) files directly from the target. Note that the target also
|
|
|
2032 must include an assembly parser and general inline assembly support for full
|
|
|
2033 inline assembly support in the .o writer.
|
|
|
2034
|
|
|
2035 Targets that don't support this feature can obviously still write out .o files,
|
|
|
2036 they just rely on having an external assembler to translate from a .s file to a
|
|
|
2037 .o file (as is the case for many C compilers).
|
|
|
2038
|
|
|
2039 .. _feat_tailcall:
|
|
|
2040
|
|
|
2041 Tail Calls
|
|
|
2042 ^^^^^^^^^^
|
|
|
2043
|
|
|
2044 This box indicates whether the target supports guaranteed tail calls. These are
|
|
|
2045 calls marked "`tail <LangRef.html#i_call>`_" and use the fastcc calling
|
|
|
2046 convention. Please see the `tail call section`_ for more details.
|
|
|
2047
|
|
|
2048 .. _feat_segstacks:
|
|
|
2049
|
|
|
2050 Segmented Stacks
|
|
|
2051 ^^^^^^^^^^^^^^^^
|
|
|
2052
|
|
|
2053 This box indicates whether the target supports segmented stacks. This replaces
|
|
|
2054 the traditional large C stack with many linked segments. It is compatible with
|
|
|
2055 the `gcc implementation <http://gcc.gnu.org/wiki/SplitStacks>`_ used by the Go
|
|
|
2056 front end.
|
|
|
2057
|
|
|
2058 .. _feat_segstacks_x86:
|
|
|
2059
|
|
|
2060 Basic support exists on the X86 backend. Currently vararg doesn't work and the
|
|
|
2061 object files are not marked the way the gold linker expects, but simple Go
|
|
|
2062 programs can be built by dragonegg.
|
|
|
2063
|
|
|
2064 .. _tail call section:
|
|
|
2065
|
|
|
2066 Tail call optimization
|
|
|
2067 ----------------------
|
|
|
2068
|
|
|
2069 Tail call optimization, callee reusing the stack of the caller, is currently
|
|
221
|
2070 supported on x86/x86-64, PowerPC, AArch64, and WebAssembly. It is performed on
|
|
|
2071 x86/x86-64, PowerPC, and AArch64 if:
|
|
150
|
2072
|
|
|
2073 * Caller and callee have the calling convention ``fastcc``, ``cc 10`` (GHC
|
|
221
|
2074 calling convention), ``cc 11`` (HiPE calling convention), ``tailcc``, or
|
|
|
2075 ``swifttailcc``.
|
|
150
|
2076
|
|
|
2077 * The call is a tail call - in tail position (ret immediately follows call and
|
|
|
2078 ret uses value of call or is void).
|
|
|
2079
|
|
|
2080 * Option ``-tailcallopt`` is enabled or the calling convention is ``tailcc``.
|
|
|
2081
|
|
|
2082 * Platform-specific constraints are met.
|
|
|
2083
|
|
|
2084 x86/x86-64 constraints:
|
|
|
2085
|
|
|
2086 * No variable argument lists are used.
|
|
|
2087
|
|
|
2088 * On x86-64 when generating GOT/PIC code only module-local calls (visibility =
|
|
|
2089 hidden or protected) are supported.
|
|
|
2090
|
|
|
2091 PowerPC constraints:
|
|
|
2092
|
|
|
2093 * No variable argument lists are used.
|
|
|
2094
|
|
|
2095 * No byval parameters are used.
|
|
|
2096
|
|
|
2097 * On ppc32/64 GOT/PIC only module-local calls (visibility = hidden or protected)
|
|
|
2098 are supported.
|
|
|
2099
|
|
|
2100 WebAssembly constraints:
|
|
|
2101
|
|
|
2102 * No variable argument lists are used
|
|
|
2103
|
|
|
2104 * The 'tail-call' target attribute is enabled.
|
|
|
2105
|
|
|
2106 * The caller and callee's return types must match. The caller cannot
|
|
|
2107 be void unless the callee is, too.
|
|
|
2108
|
|
221
|
2109 AArch64 constraints:
|
|
|
2110
|
|
|
2111 * No variable argument lists are used.
|
|
|
2112
|
|
150
|
2113 Example:
|
|
|
2114
|
|
|
2115 Call as ``llc -tailcallopt test.ll``.
|
|
|
2116
|
|
|
2117 .. code-block:: llvm
|
|
|
2118
|
|
|
2119 declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)
|
|
|
2120
|
|
|
2121 define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
|
|
|
2122 %l1 = add i32 %in1, %in2
|
|
221
|
2123 %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)
|
|
150
|
2124 ret i32 %tmp
|
|
|
2125 }
|
|
|
2126
|
|
|
2127 Implications of ``-tailcallopt``:
|
|
|
2128
|
|
|
2129 To support tail call optimization in situations where the callee has more
|
|
|
2130 arguments than the caller a 'callee pops arguments' convention is used. This
|
|
|
2131 currently causes each ``fastcc`` call that is not tail call optimized (because
|
|
|
2132 one or more of above constraints are not met) to be followed by a readjustment
|
|
|
2133 of the stack. So performance might be worse in such cases.
|
|
|
2134
|
|
|
2135 Sibling call optimization
|
|
|
2136 -------------------------
|
|
|
2137
|
|
|
2138 Sibling call optimization is a restricted form of tail call optimization.
|
|
|
2139 Unlike tail call optimization described in the previous section, it can be
|
|
|
2140 performed automatically on any tail calls when ``-tailcallopt`` option is not
|
|
|
2141 specified.
|
|
|
2142
|
|
|
2143 Sibling call optimization is currently performed on x86/x86-64 when the
|
|
|
2144 following constraints are met:
|
|
|
2145
|
|
|
2146 * Caller and callee have the same calling convention. It can be either ``c`` or
|
|
|
2147 ``fastcc``.
|
|
|
2148
|
|
|
2149 * The call is a tail call - in tail position (ret immediately follows call and
|
|
|
2150 ret uses value of call or is void).
|
|
|
2151
|
|
|
2152 * Caller and callee have matching return type or the callee result is not used.
|
|
|
2153
|
|
|
2154 * If any of the callee arguments are being passed in stack, they must be
|
|
|
2155 available in caller's own incoming argument stack and the frame offsets must
|
|
|
2156 be the same.
|
|
|
2157
|
|
|
2158 Example:
|
|
|
2159
|
|
|
2160 .. code-block:: llvm
|
|
|
2161
|
|
|
2162 declare i32 @bar(i32, i32)
|
|
|
2163
|
|
|
2164 define i32 @foo(i32 %a, i32 %b, i32 %c) {
|
|
|
2165 entry:
|
|
|
2166 %0 = tail call i32 @bar(i32 %a, i32 %b)
|
|
|
2167 ret i32 %0
|
|
|
2168 }
|
|
|
2169
|
|
|
2170 The X86 backend
|
|
|
2171 ---------------
|
|
|
2172
|
|
|
2173 The X86 code generator lives in the ``lib/Target/X86`` directory. This code
|
|
|
2174 generator is capable of targeting a variety of x86-32 and x86-64 processors, and
|
|
|
2175 includes support for ISA extensions such as MMX and SSE.
|
|
|
2176
|
|
|
2177 X86 Target Triples supported
|
|
|
2178 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2179
|
|
|
2180 The following are the known target triples that are supported by the X86
|
|
|
2181 backend. This is not an exhaustive list, and it would be useful to add those
|
|
|
2182 that people test.
|
|
|
2183
|
|
|
2184 * **i686-pc-linux-gnu** --- Linux
|
|
|
2185
|
|
|
2186 * **i386-unknown-freebsd5.3** --- FreeBSD 5.3
|
|
|
2187
|
|
|
2188 * **i686-pc-cygwin** --- Cygwin on Win32
|
|
|
2189
|
|
|
2190 * **i686-pc-mingw32** --- MingW on Win32
|
|
|
2191
|
|
|
2192 * **i386-pc-mingw32msvc** --- MingW crosscompiler on Linux
|
|
|
2193
|
|
|
2194 * **i686-apple-darwin*** --- Apple Darwin on X86
|
|
|
2195
|
|
|
2196 * **x86_64-unknown-linux-gnu** --- Linux
|
|
|
2197
|
|
|
2198 X86 Calling Conventions supported
|
|
|
2199 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2200
|
|
|
2201 The following target-specific calling conventions are known to backend:
|
|
|
2202
|
|
|
2203 * **x86_StdCall** --- stdcall calling convention seen on Microsoft Windows
|
|
|
2204 platform (CC ID = 64).
|
|
|
2205
|
|
|
2206 * **x86_FastCall** --- fastcall calling convention seen on Microsoft Windows
|
|
|
2207 platform (CC ID = 65).
|
|
|
2208
|
|
|
2209 * **x86_ThisCall** --- Similar to X86_StdCall. Passes first argument in ECX,
|
|
|
2210 others via stack. Callee is responsible for stack cleaning. This convention is
|
|
|
2211 used by MSVC by default for methods in its ABI (CC ID = 70).
|
|
|
2212
|
|
|
2213 .. _X86 addressing mode:
|
|
|
2214
|
|
|
2215 Representing X86 addressing modes in MachineInstrs
|
|
|
2216 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2217
|
|
|
2218 The x86 has a very flexible way of accessing memory. It is capable of forming
|
|
|
2219 memory addresses of the following expression directly in integer instructions
|
|
|
2220 (which use ModR/M addressing):
|
|
|
2221
|
|
|
2222 ::
|
|
|
2223
|
|
|
2224 SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32
|
|
|
2225
|
|
|
2226 In order to represent this, LLVM tracks no less than 5 operands for each memory
|
|
|
2227 operand of this form. This means that the "load" form of '``mov``' has the
|
|
|
2228 following ``MachineOperand``\s in this order:
|
|
|
2229
|
|
|
2230 ::
|
|
|
2231
|
|
|
2232 Index: 0 | 1 2 3 4 5
|
|
|
2233 Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement Segment
|
|
|
2234 OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm PhysReg
|
|
|
2235
|
|
|
2236 Stores, and all other instructions, treat the four memory operands in the same
|
|
|
2237 way and in the same order. If the segment register is unspecified (regno = 0),
|
|
|
2238 then no segment override is generated. "Lea" operations do not have a segment
|
|
|
2239 register specified, so they only have 4 operands for their memory reference.
|
|
|
2240
|
|
|
2241 X86 address spaces supported
|
|
|
2242 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2243
|
|
|
2244 x86 has a feature which provides the ability to perform loads and stores to
|
|
|
2245 different address spaces via the x86 segment registers. A segment override
|
|
|
2246 prefix byte on an instruction causes the instruction's memory access to go to
|
|
|
2247 the specified segment. LLVM address space 0 is the default address space, which
|
|
|
2248 includes the stack, and any unqualified memory accesses in a program. Address
|
|
|
2249 spaces 1-255 are currently reserved for user-defined code. The GS-segment is
|
|
|
2250 represented by address space 256, the FS-segment is represented by address space
|
|
|
2251 257, and the SS-segment is represented by address space 258. Other x86 segments
|
|
|
2252 have yet to be allocated address space numbers.
|
|
|
2253
|
|
|
2254 While these address spaces may seem similar to TLS via the ``thread_local``
|
|
|
2255 keyword, and often use the same underlying hardware, there are some fundamental
|
|
|
2256 differences.
|
|
|
2257
|
|
|
2258 The ``thread_local`` keyword applies to global variables and specifies that they
|
|
|
2259 are to be allocated in thread-local memory. There are no type qualifiers
|
|
|
2260 involved, and these variables can be pointed to with normal pointers and
|
|
|
2261 accessed with normal loads and stores. The ``thread_local`` keyword is
|
|
|
2262 target-independent at the LLVM IR level (though LLVM doesn't yet have
|
|
|
2263 implementations of it for some configurations)
|
|
|
2264
|
|
|
2265 Special address spaces, in contrast, apply to static types. Every load and store
|
|
|
2266 has a particular address space in its address operand type, and this is what
|
|
|
2267 determines which address space is accessed. LLVM ignores these special address
|
|
|
2268 space qualifiers on global variables, and does not provide a way to directly
|
|
|
2269 allocate storage in them. At the LLVM IR level, the behavior of these special
|
|
|
2270 address spaces depends in part on the underlying OS or runtime environment, and
|
|
|
2271 they are specific to x86 (and LLVM doesn't yet handle them correctly in some
|
|
|
2272 cases).
|
|
|
2273
|
|
|
2274 Some operating systems and runtime environments use (or may in the future use)
|
|
|
2275 the FS/GS-segment registers for various low-level purposes, so care should be
|
|
|
2276 taken when considering them.
|
|
|
2277
|
|
|
2278 Instruction naming
|
|
|
2279 ^^^^^^^^^^^^^^^^^^
|
|
|
2280
|
|
|
2281 An instruction name consists of the base name, a default operand size, and a a
|
|
|
2282 character per operand with an optional special size. For example:
|
|
|
2283
|
|
|
2284 ::
|
|
|
2285
|
|
|
2286 ADD8rr -> add, 8-bit register, 8-bit register
|
|
|
2287 IMUL16rmi -> imul, 16-bit register, 16-bit memory, 16-bit immediate
|
|
|
2288 IMUL16rmi8 -> imul, 16-bit register, 16-bit memory, 8-bit immediate
|
|
|
2289 MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory
|
|
|
2290
|
|
|
2291 The PowerPC backend
|
|
|
2292 -------------------
|
|
|
2293
|
|
|
2294 The PowerPC code generator lives in the lib/Target/PowerPC directory. The code
|
|
|
2295 generation is retargetable to several variations or *subtargets* of the PowerPC
|
|
|
2296 ISA; including ppc32, ppc64 and altivec.
|
|
|
2297
|
|
|
2298 LLVM PowerPC ABI
|
|
|
2299 ^^^^^^^^^^^^^^^^
|
|
|
2300
|
|
|
2301 LLVM follows the AIX PowerPC ABI, with two deviations. LLVM uses a PC relative
|
|
|
2302 (PIC) or static addressing for accessing global values, so no TOC (r2) is
|
|
|
2303 used. Second, r31 is used as a frame pointer to allow dynamic growth of a stack
|
|
|
2304 frame. LLVM takes advantage of having no TOC to provide space to save the frame
|
|
|
2305 pointer in the PowerPC linkage area of the caller frame. Other details of
|
|
|
2306 PowerPC ABI can be found at `PowerPC ABI
|
|
|
2307 <http://developer.apple.com/documentation/DeveloperTools/Conceptual/LowLevelABI/Articles/32bitPowerPC.html>`_\
|
|
|
2308 . Note: This link describes the 32 bit ABI. The 64 bit ABI is similar except
|
|
|
2309 space for GPRs are 8 bytes wide (not 4) and r13 is reserved for system use.
|
|
|
2310
|
|
|
2311 Frame Layout
|
|
|
2312 ^^^^^^^^^^^^
|
|
|
2313
|
|
|
2314 The size of a PowerPC frame is usually fixed for the duration of a function's
|
|
|
2315 invocation. Since the frame is fixed size, all references into the frame can be
|
|
|
2316 accessed via fixed offsets from the stack pointer. The exception to this is
|
|
|
2317 when dynamic alloca or variable sized arrays are present, then a base pointer
|
|
|
2318 (r31) is used as a proxy for the stack pointer and stack pointer is free to grow
|
|
|
2319 or shrink. A base pointer is also used if llvm-gcc is not passed the
|
|
|
2320 -fomit-frame-pointer flag. The stack pointer is always aligned to 16 bytes, so
|
|
|
2321 that space allocated for altivec vectors will be properly aligned.
|
|
|
2322
|
|
|
2323 An invocation frame is laid out as follows (low memory at top):
|
|
|
2324
|
|
|
2325 :raw-html:`<table border="1" cellspacing="0">`
|
|
|
2326 :raw-html:`<tr>`
|
|
|
2327 :raw-html:`<td>Linkage<br><br></td>`
|
|
|
2328 :raw-html:`</tr>`
|
|
|
2329 :raw-html:`<tr>`
|
|
|
2330 :raw-html:`<td>Parameter area<br><br></td>`
|
|
|
2331 :raw-html:`</tr>`
|
|
|
2332 :raw-html:`<tr>`
|
|
|
2333 :raw-html:`<td>Dynamic area<br><br></td>`
|
|
|
2334 :raw-html:`</tr>`
|
|
|
2335 :raw-html:`<tr>`
|
|
|
2336 :raw-html:`<td>Locals area<br><br></td>`
|
|
|
2337 :raw-html:`</tr>`
|
|
|
2338 :raw-html:`<tr>`
|
|
|
2339 :raw-html:`<td>Saved registers area<br><br></td>`
|
|
|
2340 :raw-html:`</tr>`
|
|
|
2341 :raw-html:`<tr style="border-style: none hidden none hidden;">`
|
|
|
2342 :raw-html:`<td><br></td>`
|
|
|
2343 :raw-html:`</tr>`
|
|
|
2344 :raw-html:`<tr>`
|
|
|
2345 :raw-html:`<td>Previous Frame<br><br></td>`
|
|
|
2346 :raw-html:`</tr>`
|
|
|
2347 :raw-html:`</table>`
|
|
|
2348
|
|
|
2349 The *linkage* area is used by a callee to save special registers prior to
|
|
|
2350 allocating its own frame. Only three entries are relevant to LLVM. The first
|
|
|
2351 entry is the previous stack pointer (sp), aka link. This allows probing tools
|
|
|
2352 like gdb or exception handlers to quickly scan the frames in the stack. A
|
|
|
2353 function epilog can also use the link to pop the frame from the stack. The
|
|
|
2354 third entry in the linkage area is used to save the return address from the lr
|
|
|
2355 register. Finally, as mentioned above, the last entry is used to save the
|
|
|
2356 previous frame pointer (r31.) The entries in the linkage area are the size of a
|
|
|
2357 GPR, thus the linkage area is 24 bytes long in 32 bit mode and 48 bytes in 64
|
|
|
2358 bit mode.
|
|
|
2359
|
|
|
2360 32 bit linkage area:
|
|
|
2361
|
|
|
2362 :raw-html:`<table border="1" cellspacing="0">`
|
|
|
2363 :raw-html:`<tr>`
|
|
|
2364 :raw-html:`<td>0</td>`
|
|
|
2365 :raw-html:`<td>Saved SP (r1)</td>`
|
|
|
2366 :raw-html:`</tr>`
|
|
|
2367 :raw-html:`<tr>`
|
|
|
2368 :raw-html:`<td>4</td>`
|
|
|
2369 :raw-html:`<td>Saved CR</td>`
|
|
|
2370 :raw-html:`</tr>`
|
|
|
2371 :raw-html:`<tr>`
|
|
|
2372 :raw-html:`<td>8</td>`
|
|
|
2373 :raw-html:`<td>Saved LR</td>`
|
|
|
2374 :raw-html:`</tr>`
|
|
|
2375 :raw-html:`<tr>`
|
|
|
2376 :raw-html:`<td>12</td>`
|
|
|
2377 :raw-html:`<td>Reserved</td>`
|
|
|
2378 :raw-html:`</tr>`
|
|
|
2379 :raw-html:`<tr>`
|
|
|
2380 :raw-html:`<td>16</td>`
|
|
|
2381 :raw-html:`<td>Reserved</td>`
|
|
|
2382 :raw-html:`</tr>`
|
|
|
2383 :raw-html:`<tr>`
|
|
|
2384 :raw-html:`<td>20</td>`
|
|
|
2385 :raw-html:`<td>Saved FP (r31)</td>`
|
|
|
2386 :raw-html:`</tr>`
|
|
|
2387 :raw-html:`</table>`
|
|
|
2388
|
|
|
2389 64 bit linkage area:
|
|
|
2390
|
|
|
2391 :raw-html:`<table border="1" cellspacing="0">`
|
|
|
2392 :raw-html:`<tr>`
|
|
|
2393 :raw-html:`<td>0</td>`
|
|
|
2394 :raw-html:`<td>Saved SP (r1)</td>`
|
|
|
2395 :raw-html:`</tr>`
|
|
|
2396 :raw-html:`<tr>`
|
|
|
2397 :raw-html:`<td>8</td>`
|
|
|
2398 :raw-html:`<td>Saved CR</td>`
|
|
|
2399 :raw-html:`</tr>`
|
|
|
2400 :raw-html:`<tr>`
|
|
|
2401 :raw-html:`<td>16</td>`
|
|
|
2402 :raw-html:`<td>Saved LR</td>`
|
|
|
2403 :raw-html:`</tr>`
|
|
|
2404 :raw-html:`<tr>`
|
|
|
2405 :raw-html:`<td>24</td>`
|
|
|
2406 :raw-html:`<td>Reserved</td>`
|
|
|
2407 :raw-html:`</tr>`
|
|
|
2408 :raw-html:`<tr>`
|
|
|
2409 :raw-html:`<td>32</td>`
|
|
|
2410 :raw-html:`<td>Reserved</td>`
|
|
|
2411 :raw-html:`</tr>`
|
|
|
2412 :raw-html:`<tr>`
|
|
|
2413 :raw-html:`<td>40</td>`
|
|
|
2414 :raw-html:`<td>Saved FP (r31)</td>`
|
|
|
2415 :raw-html:`</tr>`
|
|
|
2416 :raw-html:`</table>`
|
|
|
2417
|
|
|
2418 The *parameter area* is used to store arguments being passed to a callee
|
|
|
2419 function. Following the PowerPC ABI, the first few arguments are actually
|
|
|
2420 passed in registers, with the space in the parameter area unused. However, if
|
|
|
2421 there are not enough registers or the callee is a thunk or vararg function,
|
|
|
2422 these register arguments can be spilled into the parameter area. Thus, the
|
|
|
2423 parameter area must be large enough to store all the parameters for the largest
|
|
|
2424 call sequence made by the caller. The size must also be minimally large enough
|
|
|
2425 to spill registers r3-r10. This allows callees blind to the call signature,
|
|
|
2426 such as thunks and vararg functions, enough space to cache the argument
|
|
|
2427 registers. Therefore, the parameter area is minimally 32 bytes (64 bytes in 64
|
|
|
2428 bit mode.) Also note that since the parameter area is a fixed offset from the
|
|
|
2429 top of the frame, that a callee can access its split arguments using fixed
|
|
|
2430 offsets from the stack pointer (or base pointer.)
|
|
|
2431
|
|
|
2432 Combining the information about the linkage, parameter areas and alignment. A
|
|
|
2433 stack frame is minimally 64 bytes in 32 bit mode and 128 bytes in 64 bit mode.
|
|
|
2434
|
|
|
2435 The *dynamic area* starts out as size zero. If a function uses dynamic alloca
|
|
|
2436 then space is added to the stack, the linkage and parameter areas are shifted to
|
|
|
2437 top of stack, and the new space is available immediately below the linkage and
|
|
|
2438 parameter areas. The cost of shifting the linkage and parameter areas is minor
|
|
|
2439 since only the link value needs to be copied. The link value can be easily
|
|
|
2440 fetched by adding the original frame size to the base pointer. Note that
|
|
|
2441 allocations in the dynamic space need to observe 16 byte alignment.
|
|
|
2442
|
|
|
2443 The *locals area* is where the llvm compiler reserves space for local variables.
|
|
|
2444
|
|
|
2445 The *saved registers area* is where the llvm compiler spills callee saved
|
|
|
2446 registers on entry to the callee.
|
|
|
2447
|
|
|
2448 Prolog/Epilog
|
|
|
2449 ^^^^^^^^^^^^^
|
|
|
2450
|
|
|
2451 The llvm prolog and epilog are the same as described in the PowerPC ABI, with
|
|
|
2452 the following exceptions. Callee saved registers are spilled after the frame is
|
|
|
2453 created. This allows the llvm epilog/prolog support to be common with other
|
|
|
2454 targets. The base pointer callee saved register r31 is saved in the TOC slot of
|
|
|
2455 linkage area. This simplifies allocation of space for the base pointer and
|
|
|
2456 makes it convenient to locate programmatically and during debugging.
|
|
|
2457
|
|
|
2458 Dynamic Allocation
|
|
|
2459 ^^^^^^^^^^^^^^^^^^
|
|
|
2460
|
|
|
2461 .. note::
|
|
|
2462
|
|
|
2463 TODO - More to come.
|
|
|
2464
|
|
|
2465 The NVPTX backend
|
|
|
2466 -----------------
|
|
|
2467
|
|
|
2468 The NVPTX code generator under lib/Target/NVPTX is an open-source version of
|
|
|
2469 the NVIDIA NVPTX code generator for LLVM. It is contributed by NVIDIA and is
|
|
|
2470 a port of the code generator used in the CUDA compiler (nvcc). It targets the
|
|
|
2471 PTX 3.0/3.1 ISA and can target any compute capability greater than or equal to
|
|
|
2472 2.0 (Fermi).
|
|
|
2473
|
|
|
2474 This target is of production quality and should be completely compatible with
|
|
|
2475 the official NVIDIA toolchain.
|
|
|
2476
|
|
|
2477 Code Generator Options:
|
|
|
2478
|
|
|
2479 :raw-html:`<table border="1" cellspacing="0">`
|
|
|
2480 :raw-html:`<tr>`
|
|
|
2481 :raw-html:`<th>Option</th>`
|
|
|
2482 :raw-html:`<th>Description</th>`
|
|
|
2483 :raw-html:`</tr>`
|
|
|
2484 :raw-html:`<tr>`
|
|
|
2485 :raw-html:`<td>sm_20</td>`
|
|
|
2486 :raw-html:`<td align="left">Set shader model/compute capability to 2.0</td>`
|
|
|
2487 :raw-html:`</tr>`
|
|
|
2488 :raw-html:`<tr>`
|
|
|
2489 :raw-html:`<td>sm_21</td>`
|
|
|
2490 :raw-html:`<td align="left">Set shader model/compute capability to 2.1</td>`
|
|
|
2491 :raw-html:`</tr>`
|
|
|
2492 :raw-html:`<tr>`
|
|
|
2493 :raw-html:`<td>sm_30</td>`
|
|
|
2494 :raw-html:`<td align="left">Set shader model/compute capability to 3.0</td>`
|
|
|
2495 :raw-html:`</tr>`
|
|
|
2496 :raw-html:`<tr>`
|
|
|
2497 :raw-html:`<td>sm_35</td>`
|
|
|
2498 :raw-html:`<td align="left">Set shader model/compute capability to 3.5</td>`
|
|
|
2499 :raw-html:`</tr>`
|
|
|
2500 :raw-html:`<tr>`
|
|
|
2501 :raw-html:`<td>ptx30</td>`
|
|
|
2502 :raw-html:`<td align="left">Target PTX 3.0</td>`
|
|
|
2503 :raw-html:`</tr>`
|
|
|
2504 :raw-html:`<tr>`
|
|
|
2505 :raw-html:`<td>ptx31</td>`
|
|
|
2506 :raw-html:`<td align="left">Target PTX 3.1</td>`
|
|
|
2507 :raw-html:`</tr>`
|
|
|
2508 :raw-html:`</table>`
|
|
|
2509
|
|
|
2510 The extended Berkeley Packet Filter (eBPF) backend
|
|
|
2511 --------------------------------------------------
|
|
|
2512
|
|
|
2513 Extended BPF (or eBPF) is similar to the original ("classic") BPF (cBPF) used
|
|
|
2514 to filter network packets. The
|
|
|
2515 `bpf() system call <http://man7.org/linux/man-pages/man2/bpf.2.html>`_
|
|
|
2516 performs a range of operations related to eBPF. For both cBPF and eBPF
|
|
|
2517 programs, the Linux kernel statically analyzes the programs before loading
|
|
|
2518 them, in order to ensure that they cannot harm the running system. eBPF is
|
|
|
2519 a 64-bit RISC instruction set designed for one to one mapping to 64-bit CPUs.
|
|
|
2520 Opcodes are 8-bit encoded, and 87 instructions are defined. There are 10
|
|
|
2521 registers, grouped by function as outlined below.
|
|
|
2522
|
|
|
2523 ::
|
|
|
2524
|
|
|
2525 R0 return value from in-kernel functions; exit value for eBPF program
|
|
|
2526 R1 - R5 function call arguments to in-kernel functions
|
|
|
2527 R6 - R9 callee-saved registers preserved by in-kernel functions
|
|
|
2528 R10 stack frame pointer (read only)
|
|
|
2529
|
|
|
2530 Instruction encoding (arithmetic and jump)
|
|
|
2531 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2532 eBPF is reusing most of the opcode encoding from classic to simplify conversion
|
|
|
2533 of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
|
|
|
2534 field is divided into three parts:
|
|
|
2535
|
|
|
2536 ::
|
|
|
2537
|
|
|
2538 +----------------+--------+--------------------+
|
|
|
2539 | 4 bits | 1 bit | 3 bits |
|
|
|
2540 | operation code | source | instruction class |
|
|
|
2541 +----------------+--------+--------------------+
|
|
|
2542 (MSB) (LSB)
|
|
|
2543
|
|
|
2544 Three LSB bits store instruction class which is one of:
|
|
|
2545
|
|
|
2546 ::
|
|
|
2547
|
|
|
2548 BPF_LD 0x0
|
|
|
2549 BPF_LDX 0x1
|
|
|
2550 BPF_ST 0x2
|
|
|
2551 BPF_STX 0x3
|
|
|
2552 BPF_ALU 0x4
|
|
|
2553 BPF_JMP 0x5
|
|
|
2554 (unused) 0x6
|
|
|
2555 BPF_ALU64 0x7
|
|
|
2556
|
|
|
2557 When BPF_CLASS(code) == BPF_ALU or BPF_ALU64 or BPF_JMP,
|
|
|
2558 4th bit encodes source operand
|
|
|
2559
|
|
|
2560 ::
|
|
|
2561
|
|
|
2562 BPF_X 0x1 use src_reg register as source operand
|
|
|
2563 BPF_K 0x0 use 32 bit immediate as source operand
|
|
|
2564
|
|
|
2565 and four MSB bits store operation code
|
|
|
2566
|
|
|
2567 ::
|
|
|
2568
|
|
|
2569 BPF_ADD 0x0 add
|
|
|
2570 BPF_SUB 0x1 subtract
|
|
|
2571 BPF_MUL 0x2 multiply
|
|
|
2572 BPF_DIV 0x3 divide
|
|
|
2573 BPF_OR 0x4 bitwise logical OR
|
|
|
2574 BPF_AND 0x5 bitwise logical AND
|
|
|
2575 BPF_LSH 0x6 left shift
|
|
|
2576 BPF_RSH 0x7 right shift (zero extended)
|
|
|
2577 BPF_NEG 0x8 arithmetic negation
|
|
|
2578 BPF_MOD 0x9 modulo
|
|
|
2579 BPF_XOR 0xa bitwise logical XOR
|
|
|
2580 BPF_MOV 0xb move register to register
|
|
|
2581 BPF_ARSH 0xc right shift (sign extended)
|
|
|
2582 BPF_END 0xd endianness conversion
|
|
|
2583
|
|
|
2584 If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of
|
|
|
2585
|
|
|
2586 ::
|
|
|
2587
|
|
|
2588 BPF_JA 0x0 unconditional jump
|
|
|
2589 BPF_JEQ 0x1 jump ==
|
|
|
2590 BPF_JGT 0x2 jump >
|
|
|
2591 BPF_JGE 0x3 jump >=
|
|
|
2592 BPF_JSET 0x4 jump if (DST & SRC)
|
|
|
2593 BPF_JNE 0x5 jump !=
|
|
|
2594 BPF_JSGT 0x6 jump signed >
|
|
|
2595 BPF_JSGE 0x7 jump signed >=
|
|
|
2596 BPF_CALL 0x8 function call
|
|
|
2597 BPF_EXIT 0x9 function return
|
|
|
2598
|
|
|
2599 Instruction encoding (load, store)
|
|
|
2600 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2601 For load and store instructions the 8-bit 'code' field is divided as:
|
|
|
2602
|
|
|
2603 ::
|
|
|
2604
|
|
|
2605 +--------+--------+-------------------+
|
|
|
2606 | 3 bits | 2 bits | 3 bits |
|
|
|
2607 | mode | size | instruction class |
|
|
|
2608 +--------+--------+-------------------+
|
|
|
2609 (MSB) (LSB)
|
|
|
2610
|
|
|
2611 Size modifier is one of
|
|
|
2612
|
|
|
2613 ::
|
|
|
2614
|
|
|
2615 BPF_W 0x0 word
|
|
|
2616 BPF_H 0x1 half word
|
|
|
2617 BPF_B 0x2 byte
|
|
|
2618 BPF_DW 0x3 double word
|
|
|
2619
|
|
|
2620 Mode modifier is one of
|
|
|
2621
|
|
|
2622 ::
|
|
|
2623
|
|
|
2624 BPF_IMM 0x0 immediate
|
|
|
2625 BPF_ABS 0x1 used to access packet data
|
|
|
2626 BPF_IND 0x2 used to access packet data
|
|
|
2627 BPF_MEM 0x3 memory
|
|
|
2628 (reserved) 0x4
|
|
|
2629 (reserved) 0x5
|
|
|
2630 BPF_XADD 0x6 exclusive add
|
|
|
2631
|
|
|
2632
|
|
|
2633 Packet data access (BPF_ABS, BPF_IND)
|
|
|
2634 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|
|
|
2635
|
|
|
2636 Two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
|
|
|
2637 (BPF_IND | <size> | BPF_LD) which are used to access packet data.
|
|
|
2638 Register R6 is an implicit input that must contain pointer to sk_buff.
|
|
|
2639 Register R0 is an implicit output which contains the data fetched
|
|
|
2640 from the packet. Registers R1-R5 are scratch registers and must not
|
|
|
2641 be used to store the data across BPF_ABS | BPF_LD or BPF_IND | BPF_LD
|
|
|
2642 instructions. These instructions have implicit program exit condition
|
|
|
2643 as well. When eBPF program is trying to access the data beyond
|
|
|
2644 the packet boundary, the interpreter will abort the execution of the program.
|
|
|
2645
|
|
|
2646 BPF_IND | BPF_W | BPF_LD is equivalent to:
|
|
|
2647 R0 = ntohl(\*(u32 \*) (((struct sk_buff \*) R6)->data + src_reg + imm32))
|
|
|
2648
|
|
|
2649 eBPF maps
|
|
|
2650 ^^^^^^^^^
|
|
|
2651
|
|
|
2652 eBPF maps are provided for sharing data between kernel and user-space.
|
|
|
2653 Currently implemented types are hash and array, with potential extension to
|
|
|
2654 support bloom filters, radix trees, etc. A map is defined by its type,
|
|
|
2655 maximum number of elements, key size and value size in bytes. eBPF syscall
|
|
|
2656 supports create, update, find and delete functions on maps.
|
|
|
2657
|
|
|
2658 Function calls
|
|
|
2659 ^^^^^^^^^^^^^^
|
|
|
2660
|
|
|
2661 Function call arguments are passed using up to five registers (R1 - R5).
|
|
|
2662 The return value is passed in a dedicated register (R0). Four additional
|
|
|
2663 registers (R6 - R9) are callee-saved, and the values in these registers
|
|
|
2664 are preserved within kernel functions. R0 - R5 are scratch registers within
|
|
|
2665 kernel functions, and eBPF programs must therefor store/restore values in
|
|
|
2666 these registers if needed across function calls. The stack can be accessed
|
|
|
2667 using the read-only frame pointer R10. eBPF registers map 1:1 to hardware
|
|
|
2668 registers on x86_64 and other 64-bit architectures. For example, x86_64
|
|
|
2669 in-kernel JIT maps them as
|
|
|
2670
|
|
|
2671 ::
|
|
|
2672
|
|
|
2673 R0 - rax
|
|
|
2674 R1 - rdi
|
|
|
2675 R2 - rsi
|
|
|
2676 R3 - rdx
|
|
|
2677 R4 - rcx
|
|
|
2678 R5 - r8
|
|
|
2679 R6 - rbx
|
|
|
2680 R7 - r13
|
|
|
2681 R8 - r14
|
|
|
2682 R9 - r15
|
|
|
2683 R10 - rbp
|
|
|
2684
|
|
|
2685 since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
|
|
|
2686 and rbx, r12 - r15 are callee saved.
|
|
|
2687
|
|
|
2688 Program start
|
|
|
2689 ^^^^^^^^^^^^^
|
|
|
2690
|
|
|
2691 An eBPF program receives a single argument and contains
|
|
|
2692 a single eBPF main routine; the program does not contain eBPF functions.
|
|
|
2693 Function calls are limited to a predefined set of kernel functions. The size
|
|
|
2694 of a program is limited to 4K instructions: this ensures fast termination and
|
|
|
2695 a limited number of kernel function calls. Prior to running an eBPF program,
|
|
|
2696 a verifier performs static analysis to prevent loops in the code and
|
|
|
2697 to ensure valid register usage and operand types.
|
|
|
2698
|
|
|
2699 The AMDGPU backend
|
|
|
2700 ------------------
|
|
|
2701
|
|
|
2702 The AMDGPU code generator lives in the ``lib/Target/AMDGPU``
|
|
|
2703 directory. This code generator is capable of targeting a variety of
|
|
|
2704 AMD GPU processors. Refer to :doc:`AMDGPUUsage` for more information.
|
