| blob | 4dc7c8124cb0f361a2517e49dc5bc7e9df63ca62 |
3 <html>
4 <head>
8 </head>
9 <body>
12 The LLVM Target-Independent Code Generator
13 </div>
15 <ol>
17 <ul>
20 generator</a></li>
22 </ul>
23 </li>
25 <ul>
34 </ul>
35 </li>
37 <ul>
40 class</a></li>
42 </ul>
43 </li>
45 <ul>
47 <ul>
50 Process</a></li>
52 Construction</a></li>
55 Phase: the DAG Combiner</a></li>
58 Phase</a></li>
60 SelectionDAG</a></li>
61 </ul></li>
63 <ul>
66 </ul></li>
68 <ul>
70 LLVM</a></li>
72 registers</a></li>
77 </ul></li>
79 <ul>
82 </ul></li>
83 </ul>
84 </li>
86 <ul>
89 <ul>
94 </ul></li>
95 </ul></li>
97 </ol>
103 Pereira</a> and
105 </div>
109 </div>
111 <!-- *********************************************************************** -->
114 </div>
115 <!-- *********************************************************************** -->
119 <p>The LLVM target-independent code generator is a framework that provides a
120 suite of reusable components for translating the LLVM internal representation to
121 the machine code for a specified target—either in assembly form (suitable
122 for a static compiler) or in binary machine code format (usable for a JIT
123 compiler). The LLVM target-independent code generator consists of five main
124 components:</p>
126 <ol>
128 capture important properties about various aspects of the machine, independently
129 of how they will be used. These interfaces are defined in
133 generated for a target. These classes are intended to be abstract enough to
138 various phases of native code generation (register allocation, scheduling, stack
142 interfaces</a> for particular targets. These machine descriptions make use of
143 the components provided by LLVM, and can optionally provide custom
144 target-specific passes, to build complete code generators for a specific target.
149 interface for target-specific issues. The code for the target-independent
152 </ol>
154 <p>
155 Depending on which part of the code generator you are interested in working on,
156 different pieces of this will be useful to you. In any case, you should be
163 should only depend on the target-description and machine code representation
164 classes, ensuring that it is portable.
165 </p>
167 </div>
169 <!-- ======================================================================= -->
172 </div>
176 <p>The two pieces of the LLVM code generator are the high-level interface to the
177 code generator and the set of reusable components that can be used to build
178 target-specific backends. The two most important interfaces (<a
181 required to be defined for a backend to fit into the LLVM system, but the others
182 must be defined if the reusable code generator components are going to be
183 used.</p>
185 <p>This design has two important implications. The first is that LLVM can
186 support completely non-traditional code generation targets. For example, the C
187 backend does not require register allocation, instruction selection, or any of
188 the other standard components provided by the system. As such, it only
189 implements these two interfaces, and does its own thing. Another example of a
190 code generator like this is a (purely hypothetical) backend that converts LLVM
191 to the GCC RTL form and uses GCC to emit machine code for a target.</p>
193 <p>This design also implies that it is possible to design and
194 implement radically different code generators in the LLVM system that do not
195 make use of any of the built-in components. Doing so is not recommended at all,
196 but could be required for radically different targets that do not fit into the
197 LLVM machine description model: FPGAs for example.</p>
199 </div>
201 <!-- ======================================================================= -->
204 </div>
208 <p>The LLVM target-independent code generator is designed to support efficient and
209 quality code generation for standard register-based microprocessors. Code
210 generation in this model is divided into the following stages:</p>
212 <ol>
214 determines an efficient way to express the input LLVM code in the target
215 instruction set.
216 This stage produces the initial code for the program in the target instruction
217 set, then makes use of virtual registers in SSA form and physical registers that
218 represent any required register assignments due to target constraints or calling
219 conventions. This step turns the LLVM code into a DAG of target
220 instructions.</li>
223 phase takes the DAG of target instructions produced by the instruction selection
224 phase, determines an ordering of the instructions, then emits the instructions
229 </li>
232 optional stage consists of a series of machine-code optimizations that
233 operate on the SSA-form produced by the instruction selector. Optimizations
234 like modulo-scheduling or peephole optimization work here.
235 </li>
238 target code is transformed from an infinite virtual register file in SSA form
239 to the concrete register file used by the target. This phase introduces spill
240 code and eliminates all virtual register references from the program.</li>
243 machine code has been generated for the function and the amount of stack space
244 required is known (used for LLVM alloca's and spill slots), the prolog and
245 epilog code for the function can be inserted and "abstract stack location
246 references" can be eliminated. This stage is responsible for implementing
247 optimizations like frame-pointer elimination and stack packing.</li>
250 that operate on "final" machine code can go here, such as spill code scheduling
251 and peephole optimizations.</li>
254 puts out the code for the current function, either in the target assembler
255 format or in machine code.</li>
257 </ol>
259 <p>The code generator is based on the assumption that the instruction selector
260 will use an optimal pattern matching selector to create high-quality sequences of
261 native instructions. Alternative code generator designs based on pattern
262 expansion and aggressive iterative peephole optimization are much slower. This
263 design permits efficient compilation (important for JIT environments) and
264 aggressive optimization (used when generating code offline) by allowing
265 components of varying levels of sophistication to be used for any step of
266 compilation.</p>
268 <p>In addition to these stages, target implementations can insert arbitrary
269 target-specific passes into the flow. For example, the X86 target uses a
270 special pass to handle the 80x87 floating point stack architecture. Other
271 targets with unusual requirements can be supported with custom passes as
272 needed.</p>
274 </div>
277 <!-- ======================================================================= -->
280 </div>
284 <p>The target description classes require a detailed description of the target
285 architecture. These target descriptions often have a large amount of common
288 In order to allow the maximum amount of commonality to be factored out, the LLVM
290 describe big chunks of the target machine, which allows the use of
291 domain-specific and target-specific abstractions to reduce the amount of
292 repetition.</p>
294 <p>As LLVM continues to be developed and refined, we plan to move more and more
296 number of advantages. The most important is that it makes it easier to port
297 LLVM because it reduces the amount of C++ code that has to be written, and the
298 surface area of the code generator that needs to be understood before someone
299 can get something working. Second, it makes it easier to change things. In
302 to a new interface.</p>
304 </div>
306 <!-- *********************************************************************** -->
309 </div>
310 <!-- *********************************************************************** -->
314 <p>The LLVM target description classes (located in the
316 target machine independent of any particular client. These classes are
318 instructions and registers it has), and do not incorporate any particular pieces
319 of code generation algorithms.</p>
323 the concrete target implementation, and have virtual methods implemented. To
324 get to these implementations, the <tt><a
326 should be implemented by the target.</p>
328 </div>
330 <!-- ======================================================================= -->
333 </div>
338 access the target-specific implementations of the various target description
341 designed to be specialized by
343 implements the various virtual methods. The only required target description
345 code generator components are to be used, the other interfaces should be
346 implemented as well.</p>
348 </div>
351 <!-- ======================================================================= -->
354 </div>
359 and it is the only class that is not extensible (you cannot derived a new
361 lays out memory for structures, the alignment requirements for various data
362 types, the size of pointers in the target, and whether the target is
363 little-endian or big-endian.</p>
365 </div>
367 <!-- ======================================================================= -->
370 </div>
375 selectors primarily to describe how LLVM code should be lowered to SelectionDAG
376 operations. Among other things, this class indicates:</p>
378 <ul>
383 <li>various high-level characteristics, like whether it is profitable to turn
384 division by a constant into a multiplication sequence</li>
385 </ul>
387 </div>
389 <!-- ======================================================================= -->
392 </div>
398 target and any interactions between the registers.</p>
400 <p>Registers in the code generator are represented in the code generator by
401 unsigned integers. Physical registers (those that actually exist in the target
402 description) are unique small numbers, and virtual registers are generally
405 <p>Each register in the processor description has an associated
407 register (used for assembly output and debugging dumps) and a set of aliases
408 (used to indicate whether one register overlaps with another).
409 </p>
412 exposes a set of processor specific register classes (instances of the
414 registers that have the same properties (for example, they are all 32-bit
415 integer registers). Each SSA virtual register created by the instruction
416 selector has an associated register class. When the register allocator runs, it
417 replaces virtual registers with a physical register in the set.</p>
419 <p>
420 The target-specific implementations of these classes is auto-generated from a <a
422 </p>
424 </div>
426 <!-- ======================================================================= -->
429 </div>
433 instructions supported by the target. It is essentially an array of
435 instruction the target supports. Descriptors define things like the mnemonic
436 for the opcode, the number of operands, the list of implicit register uses
437 and defs, whether the instruction has certain target-independent properties
438 (accesses memory, is commutable, etc), and holds any target-specific
439 flags.</p>
440 </div>
442 <!-- ======================================================================= -->
445 </div>
449 stack frame layout of the target. It holds the direction of stack growth,
450 the known stack alignment on entry to each function, and the offset to the
451 local area. The offset to the local area is the offset from the stack
452 pointer on function entry to the first location where function data (local
453 variables, spill locations) can be stored.</p>
454 </div>
456 <!-- ======================================================================= -->
459 </div>
463 specific chip set being targeted. A sub-target informs code generation of
464 which instructions are supported, instruction latencies and instruction
465 execution itinerary; i.e., which processing units are used, in what order, and
466 for how long.</p>
467 </div>
470 <!-- ======================================================================= -->
473 </div>
477 Just-In-Time code generator to perform target-specific activities, such as
480 method.</p>
481 </div>
483 <!-- *********************************************************************** -->
486 </div>
487 <!-- *********************************************************************** -->
491 <p>At the high-level, LLVM code is translated to a machine specific
492 representation formed out of
497 target agnostic, representing instructions in their most abstract form: an
498 opcode and a series of operands. This representation is designed to support
499 both an SSA representation for machine code, as well as a register allocated,
500 non-SSA form.</p>
502 </div>
504 <!-- ======================================================================= -->
507 </div>
511 <p>Target machine instructions are represented as instances of the
513 representing machine instructions. In particular, it only keeps track of
514 an opcode number and a set of operands.</p>
516 <p>The opcode number is a simple unsigned integer that only has meaning to a
517 specific backend. All of the instructions for a target should be defined in
520 not have any information about how to interpret the instruction (i.e., what the
521 semantics of the instruction are); for that you must refer to the
524 <p>The operands of a machine instruction can be of several different types:
525 a register reference, a constant integer, a basic block reference, etc. In
526 addition, a machine operand should be marked as a def or a use of the value
527 (though only registers are allowed to be defs).</p>
529 <p>By convention, the LLVM code generator orders instruction operands so that
530 all register definitions come before the register uses, even on architectures
531 that are normally printed in other orders. For example, the SPARC add
533 and stores the result into the "%i3" register. In the LLVM code generator,
534 the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
535 first.</p>
537 <p>Keeping destination (definition) operands at the beginning of the operand
538 list has several advantages. In particular, the debugging printer will print
539 the instruction like this:</p>
542 <pre>
543 %r3 = add %i1, %i2
544 </pre>
545 </div>
549 operand.</p>
551 </div>
553 <!-- _______________________________________________________________________ -->
556 </div>
566 <pre>
568 // instruction. The '1' specifies how many operands will be added.
571 // Create the same instr, but insert it at the end of a basic block.
572 MachineBasicBlock &MBB = ...
575 // Create the same instr, but insert it before a specified iterator point.
576 MachineBasicBlock::iterator MBBI = ...
579 // Create a 'cmp Reg, 0' instruction, no destination reg.
581 // Create an 'sahf' instruction which takes no operands and stores nothing.
582 MI = BuildMI(X86::SAHF, 0);
584 // Create a self looping branch instruction.
586 </pre>
587 </div>
590 have to specify the number of operands that the machine instruction will take.
591 This allows for efficient memory allocation. You also need to specify if
592 operands default to be uses of values, not definitions. If you need to add a
593 definition operand (other than the optional destination register), you must
594 explicitly mark it as such:</p>
597 <pre>
598 MI.addReg(Reg, MachineOperand::Def);
599 </pre>
600 </div>
602 </div>
604 <!-- _______________________________________________________________________ -->
607 </div>
611 <p>One important issue that the code generator needs to be aware of is the
612 presence of fixed registers. In particular, there are often places in the
614 particular value to be in a particular register. This can occur due to
615 limitations of the instruction set (e.g., the X86 can only do a 32-bit divide
617 conventions. In any case, the instruction selector should emit code that
618 copies a virtual register into or out of a physical register when needed.</p>
623 <pre>
624 int %test(int %X, int %Y) {
625 %Z = div int %X, %Y
626 ret int %Z
627 }
628 </pre>
629 </div>
636 <pre>
637 ;; Start of div
638 %EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
639 %reg1027 = sar %reg1024, 31
640 %EDX = mov %reg1027 ;; Sign extend X into EDX
641 idiv %reg1025 ;; Divide by Y (in reg1025)
642 %reg1026 = mov %EAX ;; Read the result (Z) out of EAX
644 ;; Start of ret
645 %EAX = mov %reg1026 ;; 32-bit return value goes in EAX
646 ret
647 </pre>
648 </div>
650 <p>By the end of code generation, the register allocator has coalesced
651 the registers and deleted the resultant identity moves producing the
652 following code:</p>
655 <pre>
656 ;; X is in EAX, Y is in ECX
657 mov %EAX, %EDX
658 sar %EDX, 31
659 idiv %ECX
660 ret
661 </pre>
662 </div>
664 <p>This approach is extremely general (if it can handle the X86 architecture,
665 it can handle anything!) and allows all of the target specific
666 knowledge about the instruction stream to be isolated in the instruction
667 selector. Note that physical registers should have a short lifetime for good
668 code generation, and all physical registers are assumed dead on entry to and
669 exit from basic blocks (before register allocation). Thus, if you need a value
671 register.</p>
673 </div>
675 <!-- _______________________________________________________________________ -->
678 </div>
683 are maintained in SSA-form until register allocation happens. For the most
684 part, this is trivially simple since LLVM is already in SSA form; LLVM PHI nodes
685 become machine code PHI nodes, and virtual registers are only allowed to have a
686 single definition.</p>
688 <p>After register allocation, machine code is no longer in SSA-form because there
689 are no virtual registers left in the code.</p>
691 </div>
693 <!-- ======================================================================= -->
696 </div>
702 corresponds to the LLVM code input to the instruction selector, but there can be
703 a one-to-many mapping (i.e. one LLVM basic block can map to multiple machine
705 "<tt>getBasicBlock</tt>" method, which returns the LLVM basic block that it
706 comes from.</p>
708 </div>
710 <!-- ======================================================================= -->
713 </div>
719 corresponds one-to-one with the LLVM function input to the instruction selector.
723 live out registers for the function. See
726 </div>
728 <!-- *********************************************************************** -->
731 </div>
732 <!-- *********************************************************************** -->
738 explains how they work and some of the rationale behind their design.</p>
740 </div>
742 <!-- ======================================================================= -->
745 </div>
748 <p>
749 Instruction Selection is the process of translating LLVM code presented to the
750 code generator into target-specific machine instructions. There are several
751 well-known ways to do this in the literature. In LLVM there are two main forms:
752 the SelectionDAG based instruction selector framework and an old-style 'simple'
753 instruction selector, which effectively peephole selects each LLVM instruction
754 into a series of machine instructions. We recommend that all targets use the
755 SelectionDAG infrastructure.
756 </p>
758 <p>Portions of the DAG instruction selector are generated from the target
761 </div>
763 <!-- _______________________________________________________________________ -->
766 </div>
770 <p>The SelectionDAG provides an abstraction for code representation in a way
771 that is amenable to instruction selection using automatic techniques
772 (e.g. dynamic-programming based optimal pattern matching selectors). It is also
773 well-suited to other phases of code generation; in particular,
774 instruction scheduling (SelectionDAG's are very close to scheduling DAGs
775 post-selection). Additionally, the SelectionDAG provides a host representation
776 where a large variety of very-low-level (but target-independent)
778 performed; ones which require extensive information about the instructions
779 efficiently supported by the target.</p>
781 <p>The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
783 operation code (Opcode) that indicates what operation the node performs and
784 the operands to the operation.
785 The various operation node types are described at the top of the
788 <p>Although most operations define a single value, each node in the graph may
789 define multiple values. For example, a combined div/rem operation will define
790 both the dividend and the remainder. Many other situations require multiple
791 values as well. Each node also has some number of operands, which are edges
792 to the node defining the used value. Because nodes may define multiple values,
798 <p>SelectionDAGs contain two different kinds of values: those that represent
799 data flow and those that represent control flow dependencies. Data values are
800 simple edges with an integer or floating point value type. Control edges are
802 provide an ordering between nodes that have side effects (such as
803 loads, stores, calls, returns, etc). All nodes that have side effects should
804 take a token chain as input and produce a new one as output. By convention,
805 token chain inputs are always operand #0, and chain results are always the last
806 value produced by an operation.</p>
810 is the final side-effecting node in the token chain. For example, in a single
811 basic block function it would be the return node.</p>
814 "illegal" DAG. A legal DAG for a target is one that only uses supported
815 operations and supported types. On a 32-bit PowerPC, for example, a DAG with
816 a value of type i1, i8, i16, or i64 would be illegal, as would a DAG that uses a
817 SREM or UREM operation. The
819 an illegal DAG into a legal DAG.</p>
821 </div>
823 <!-- _______________________________________________________________________ -->
826 </div>
832 <ol>
834 performs a simple translation from the input LLVM code to an illegal
835 SelectionDAG.</li>
837 performs simple optimizations on the SelectionDAG to simplify it, and
839 pairs) for targets that support these meta operations. This makes the
843 converts the illegal SelectionDAG to a legal SelectionDAG by eliminating
844 unsupported operations and data types.</li>
846 second run of the SelectionDAG optimizes the newly legalized DAG to
847 eliminate inefficiencies introduced by legalization.</li>
849 the target instruction selector matches the DAG operations to target
850 instructions. This process translates the target-independent input DAG into
851 another DAG of target instructions.</li>
853 - The last phase assigns a linear order to the instructions in the
854 target-instruction DAG and emits them into the MachineFunction being
855 compiled. This step uses traditional prepass scheduling techniques.</li>
856 </ol>
858 <p>After all of these steps are complete, the SelectionDAG is destroyed and the
859 rest of the code generation passes are run.</p>
861 <p>One great way to visualize what is going on here is to take advantage of a
863 option pops up a window with the SelectionDAG input to the Select phase for all
864 of the code compiled (if you only get errors printed to the console while using
867 views the SelectionDAG output from the Select phase and input to the Scheduler
868 phase.</p>
870 </div>
872 <!-- _______________________________________________________________________ -->
875 </div>
882 pass is to expose as much low-level, target-specific details to the SelectionDAG
885 obvious arithmetic). This pass requires target-specific hooks to lower calls,
886 returns, varargs, etc. For these features, the
889 </div>
891 <!-- _______________________________________________________________________ -->
894 </div>
898 <p>The Legalize phase is in charge of converting a DAG to only use the types and
899 operations that are natively supported by the target. This involves two major
900 tasks:</p>
902 <ol>
904 <p>There are two main ways of doing this: converting small types to
905 larger types ("promoting"), and breaking up large integer types
906 into smaller ones ("expanding"). For example, a target might require
907 that all f32 values are promoted to f64 and that all i1/i8/i16 values
908 are promoted to i32. The same target might require that all i64 values
909 be expanded into i32 values. These changes can insert sign and zero
910 extensions as needed to make sure that the final code has the same
911 behavior as the input.</p>
912 <p>A target implementation tells the legalizer which types are supported
913 (and which register class to use for them) by calling the
915 </li>
918 <p>Targets often have weird constraints, such as not supporting every
919 operation on every supported datatype (e.g. X86 does not support byte
920 conditional moves and PowerPC does not support sign-extending loads from
921 a 16-bit memory location). Legalize takes care of this by open-coding
922 another sequence of operations to emulate the operation ("expansion"), by
923 promoting one type to a larger type that supports the operation
924 ("promotion"), or by using a target-specific hook to implement the
926 <p>A target implementation tells the legalizer which operations are not
927 supported (and which of the above three actions to take) by calling the
929 constructor.</p>
930 </li>
931 </ol>
933 <p>Prior to the existance of the Legalize pass, we required that every target
935 operator and type even if they are not natively supported. The introduction of
936 the Legalize phase allows all of the cannonicalization patterns to be shared
937 across targets, and makes it very easy to optimize the cannonicalized code
938 because it is still in the form of a DAG.</p>
940 </div>
942 <!-- _______________________________________________________________________ -->
945 Combiner</a>
946 </div>
950 <p>The SelectionDAG optimization phase is run twice for code generation: once
951 immediately after the DAG is built and once after legalization. The first run
952 of the pass allows the initial code to be cleaned up (e.g. performing
953 optimizations that depend on knowing that the operators have restricted type
954 inputs). The second run of the pass cleans up the messy code generated by the
955 Legalize pass, which allows Legalize to be very simple (it can focus on making
958 <p>One important class of optimizations performed is optimizing inserted sign
959 and zero extension instructions. We currently use ad-hoc techniques, but could
960 move to more rigorous techniques in the future. Here are some good papers on
961 the subject:</p>
963 <p>
966 Kevin Redwine and Norman Ramsey<br>
967 International Conference on Compiler Construction (CC) 2004
968 </p>
971 <p>
974 Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani<br>
975 Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
976 and Implementation.
977 </p>
979 </div>
981 <!-- _______________________________________________________________________ -->
984 </div>
988 <p>The Select phase is the bulk of the target-specific code for instruction
989 selection. This phase takes a legal SelectionDAG as input, pattern matches the
990 instructions supported by the target to this DAG, and produces a new DAG of
991 target code. For example, consider the following LLVM fragment:</p>
994 <pre>
995 %t1 = add float %W, %X
996 %t2 = mul float %t1, %Y
997 %t3 = add float %t2, %Z
998 </pre>
999 </div>
1001 <p>This LLVM code corresponds to a SelectionDAG that looks basically like
1002 this:</p>
1005 <pre>
1006 (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
1007 </pre>
1008 </div>
1010 <p>If a target supports floating point multiply-and-add (FMA) operations, one
1011 of the adds can be merged with the multiply. On the PowerPC, for example, the
1012 output of the instruction selector might look like this DAG:</p>
1015 <pre>
1016 (FMADDS (FADDS W, X), Y, Z)
1017 </pre>
1018 </div>
1021 first two operands and adds the third (as single-precision floating-point
1023 add instruction. To perform this pattern match, the PowerPC backend includes
1024 the following instruction definitions:</p>
1027 <pre>
1029 (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
1030 "fmadds $FRT, $FRA, $FRC, $FRB",
1031 [<b>(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),
1034 (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),
1035 "fadds $FRT, $FRA, $FRB",
1037 </pre>
1038 </div>
1040 <p>The portion of the instruction definition in bold indicates the pattern used
1045 <p>The TableGen DAG instruction selector generator reads the instruction
1047 matching code for your target. It has the following strengths:</p>
1049 <ul>
1050 <li>At compiler-compiler time, it analyzes your instruction patterns and tells
1051 you if your patterns make sense or not.</li>
1052 <li>It can handle arbitrary constraints on operands for the pattern match. In
1053 particular, it is straight-forward to say things like "match any immediate
1054 that is a 13-bit sign-extended value". For examples, see the
1056 backend.</li>
1057 <li>It knows several important identities for the patterns defined. For
1058 example, it knows that addition is commutative, so it allows the
1060 well as "<tt>(fadd (fmul X, Y), Z)</tt>", without the target author having
1061 to specially handle this case.</li>
1062 <li>It has a full-featured type-inferencing system. In particular, you should
1063 rarely have to explicitly tell the system what type parts of your patterns
1066 was able to infer and propagate this knowledge from the fact that
1069 Pattern fragments are chunks of reusable patterns that get inlined into your
1070 patterns during compiler-compiler time. For example, the integer
1071 "<tt>(not x)</tt>" operation is actually defined as a pattern fragment that
1072 expands as "<tt>(xor x, -1)</tt>", since the SelectionDAG does not have a
1076 <li>In addition to instructions, targets can specify arbitrary patterns that
1077 map to one or more instructions using the 'Pat' class. For example,
1078 the PowerPC has no way to load an arbitrary integer immediate into a
1079 register in one instruction. To tell tblgen how to do this, it defines:
1080 <br>
1081 <br>
1083 <pre>
1084 // Arbitrary immediate support. Implement in terms of LIS/ORI.
1085 def : Pat<(i32 imm:$imm),
1086 (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
1087 </pre>
1088 </div>
1089 <br>
1090 If none of the single-instruction patterns for loading an immediate into a
1091 register match, this will be used. This rule says "match an arbitrary i32
1092 immediate, turning it into an <tt>ORI</tt> ('or a 16-bit immediate') and an
1093 <tt>LIS</tt> ('load 16-bit immediate, where the immediate is shifted to the
1094 left 16 bits') instruction". To make this work, the
1096 input immediate (in this case, take the high or low 16-bits of the
1097 immediate).</li>
1098 <li>While the system does automate a lot, it still allows you to write custom
1099 C++ code to match special cases if there is something that is hard to
1100 express.</li>
1101 </ul>
1103 <p>While it has many strengths, the system currently has some limitations,
1104 primarily because it is a work in progress and is not yet finished:</p>
1106 <ul>
1107 <li>Overall, there is no way to define or match SelectionDAG nodes that define
1110 write custom C++ code for your instruction selector.</li>
1111 <li>There is no great way to support matching complex addressing modes yet. In
1112 the future, we will extend pattern fragments to allow them to define
1114 addressing mode</a>). In addition, we'll extend fragments so that a
1115 fragment can match multiple different patterns.</li>
1117 <li>We don't automatically generate the set of supported registers and
1120 </ul>
1122 <p>Despite these limitations, the instruction selector generator is still quite
1123 useful for most of the binary and logical operations in typical instruction
1124 sets. If you run into any problems or can't figure out how to do something,
1125 please let Chris know!</p>
1127 </div>
1129 <!-- _______________________________________________________________________ -->
1132 </div>
1136 <p>The scheduling phase takes the DAG of target instructions from the selection
1137 phase and assigns an order. The scheduler can pick an order depending on
1138 various constraints of the machines (i.e. order for minimal register pressure or
1139 try to cover instruction latencies). Once an order is established, the DAG is
1141 the SelectionDAG is destroyed.</p>
1143 <p>Note that this phase is logically separate from the instruction selection
1144 phase, but is tied to it closely in the code because it operates on
1145 SelectionDAGs.</p>
1147 </div>
1149 <!-- _______________________________________________________________________ -->
1152 </div>
1156 <ol>
1159 </ol>
1161 </div>
1163 <!-- ======================================================================= -->
1166 </div>
1169 <!-- ======================================================================= -->
1172 </div>
1178 determine if two or more virtual registers which require the same physical
1179 register are live at the same point in the program (i.e., they conflict). When
1182 </div>
1184 <!-- _______________________________________________________________________ -->
1187 </div>
1191 <p>The first step in determining the live intervals of variables is to
1192 calculate the set of registers that are immediately dead after the
1193 instruction (i.e., the instruction calculates the value, but it is
1194 never used) and the set of registers that are used by the instruction,
1195 but are never used after the instruction (i.e., they are killed). Live
1198 is done in a very efficient manner because it uses SSA to sparsely
1199 compute lifetime information for virtual registers (which are in SSA
1200 form) and only has to track physical registers within a block. Before
1201 register allocation, LLVM can assume that physical registers are only
1202 live within a single basic block. This allows it to do a single,
1203 local analysis to resolve physical register lifetimes within each
1204 basic block. If a physical register is not register allocatable (e.g.,
1205 a stack pointer or condition codes), it is not tracked.</p>
1207 <p>Physical registers may be live in to or out of a function. Live in values
1208 are typically arguments in registers. Live out values are typically return
1209 values in registers. Live in values are marked as such, and are given a dummy
1210 "defining" instruction during live intervals analysis. If the last basic block
1212 values in the function.</p>
1215 of the live variable information from a depth first traversal of the CFG of
1218 the definition is handled, because the uses will be handled in other basic
1219 blocks.</p>
1222 assignment at the end of the current basic block and traverse the successor
1226 and all of its predecessor basic blocks, until the basic block with the
1227 defining instruction is encountered.</p>
1229 </div>
1231 <!-- _______________________________________________________________________ -->
1234 </div>
1238 <p>We now have the information available to perform the live intervals analysis
1239 and build the live intervals themselves. We start off by numbering the basic
1240 blocks and machine instructions. We then handle the "live-in" values. These
1241 are in physical registers, so the physical register is assumed to be killed by
1242 the end of the basic block. Live intervals for virtual registers are computed
1245 variable is live.</p>
1249 </div>
1251 <!-- ======================================================================= -->
1254 </div>
1261 (possibly small) number of physical registers. Each target architecture has
1262 a different number of physical registers. If the number of physical
1263 registers is not enough to accommodate all the virtual registers, some of
1264 them will have to be mapped into memory. These virtuals are called
1267 </div>
1269 <!-- _______________________________________________________________________ -->
1273 </div>
1277 <p>In LLVM, physical registers are denoted by integer numbers that
1279 for a particular architecture, you can read the
1281 instance, by inspecting
1286 <p>Some architectures contain registers that share the same physical
1287 location. A notable example is the X86 platform. For instance, in the
1291 can check which registers are aliased by inspecting its
1297 Elements in the same register class are functionally equivalent, and can
1298 be interchangeably used. Each virtual register can only be mapped to
1299 physical registers of a particular class. For instance, in the X86
1300 architecture, some virtuals can only be allocated to 8 bit registers.
1302 To discover if a virtual register is compatible with a given physical,
1303 this code can be used:
1304 </p>
1307 <pre>
1308 bool RegMapping_Fer::compatible_class(MachineFunction &mf,
1309 unsigned v_reg,
1310 unsigned p_reg) {
1311 assert(MRegisterInfo::isPhysicalRegister(p_reg) &&
1312 "Target register must be physical");
1313 const TargetRegisterClass *trc = mf.getSSARegMap()->getRegClass(v_reg);
1314 return trc->contains(p_reg);
1315 }
1316 </pre>
1317 </div>
1319 <p>Sometimes, mostly for debugging purposes, it is useful to change
1320 the number of physical registers available in the target
1321 architecture. This must be done statically, inside the
1324 registers. Just commenting some out is one simple way to avoid them
1325 being used. A more polite way is to explicitly exclude some registers
1331 <p>Virtual registers are also denoted by integer numbers. Contrary to
1332 physical registers, different virtual registers never share the same
1333 number. The smallest virtual register is normally assigned the number
1334 1024. This may change, so, in order to know which is the first virtual
1335 register, you should access
1337 number is greater than or equal to
1339 register. Whereas physical registers are statically defined in a
1341 application developer, that is not the case with virtual registers.
1342 In order to create new virtual registers, use the method
1344 virtual register with the highest code.
1345 </p>
1347 <p>Before register allocation, the operands of an instruction are
1348 mostly virtual registers, although physical registers may also be
1349 used. In order to check if a given machine operand is a register, use
1351 the integer code of a register, use
1356 if that register is being used by the instruction. The method
1358 defined.</p>
1360 <p>We will call physical registers present in the LLVM bytecode before
1362 registers are used in many different situations, for instance, to pass
1363 parameters of functions calls, and to store results of particular
1364 instructions. There are two types of pre-colored registers: the ones
1366 defined. Explicitly defined registers are normal operands, and can be
1368 order to check which registers are implicitly defined by an
1369 instruction, use the
1372 difference between explicit and implicit physical registers is that
1373 the latter are defined statically for each instruction, whereas the
1374 former may vary depending on the program being compiled. For example,
1375 an instruction that represents a function call will always implicitly
1376 define or use the same set of physical registers. To read the
1377 registers implicitly used by an instruction, use
1379 registers impose constraints on any register allocation algorithm. The
1380 register allocator must make sure that none of them is been
1381 overwritten by the values of virtual registers while still alive.</p>
1383 </div>
1385 <!-- _______________________________________________________________________ -->
1389 </div>
1393 <p>There are two ways to map virtual registers to physical registers (or to
1398 order to insert loads and stores sending and getting values to and from
1399 memory.</p>
1401 <p>The direct mapping provides more flexibility to the developer of
1402 the register allocator; however, it is more error prone, and demands
1403 more implementation work. Basically, the programmer will have to
1404 specify where load and store instructions should be inserted in the
1405 target function being compiled in order to get and store values in
1406 memory. To assign a physical register to a virtual register present in
1408 a store instruction, use
1412 <p>The indirect mapping shields the application developer from the
1413 complexities of inserting load and store instructions. In order to map
1414 a virtual register to a physical one, use
1416 certain virtual register to memory, use
1419 it is necessary to map another virtual register to the same stack
1420 slot, use <tt>VirtRegMap::assignVirt2StackSlot(vreg,
1421 stack_location)</tt>. One important point to consider when using the
1422 indirect mapping, is that even if a virtual register is mapped to
1423 memory, it still needs to be mapped to a physical register. This
1424 physical register is the location where the virtual register is
1425 supposed to be found before being stored or after being reloaded.</p>
1427 <p>If the indirect strategy is used, after all the virtual registers
1428 have been mapped to physical registers or stack slots, it is necessary
1429 to use a spiller object to place load and store instructions in the
1430 code. Every virtual that has been mapped to a stack slot will be
1431 stored to memory after been defined and will be loaded before being
1432 used. The implementation of the spiller tries to recycle load/store
1433 instructions, avoiding unnecessary instructions. For an example of how
1434 to invoke the spiller, see
1438 </div>
1440 <!-- _______________________________________________________________________ -->
1443 </div>
1447 <p>With very rare exceptions (e.g., function calls), the LLVM machine
1448 code instructions are three address instructions. That is, each
1449 instruction is expected to define at most one register, and to use at
1450 most two registers. However, some architectures use two address
1451 instructions. In this case, the defined register is also one of the
1452 used register. For instance, an instruction such as <tt>ADD %EAX,
1456 <p>In order to produce correct code, LLVM must convert three address
1457 instructions that represent two address instructions into true two
1458 address instructions. LLVM provides the pass
1460 be run before register allocation takes place. After its execution,
1461 the resulting code may no longer be in SSA form. This happens, for
1462 instance, in situations where an instruction such as <tt>%a = ADD %b
1466 <pre>
1467 %a = MOVE %b
1468 %a = ADD %a %b
1469 </pre>
1470 </div>
1472 <p>Notice that, internally, the second instruction is represented as
1474 both used and defined by the instruction.</p>
1476 </div>
1478 <!-- _______________________________________________________________________ -->
1481 </div>
1485 <p>An important transformation that happens during register allocation is called
1487 analyses that are performed on the control flow graph of
1488 programs. However, traditional instruction sets do not implement
1489 PHI instructions. Thus, in order to generate executable code, compilers
1490 must replace PHI instructions with other instructions that preserve their
1491 semantics.</p>
1493 <p>There are many ways in which PHI instructions can safely be removed
1494 from the target code. The most traditional PHI deconstruction
1495 algorithm replaces PHI instructions with copy instructions. That is
1496 the strategy adopted by LLVM. The SSA deconstruction algorithm is
1499 marked as required in the code of the register allocator.</p>
1501 </div>
1503 <!-- _______________________________________________________________________ -->
1506 </div>
1511 register allocation that removes unnecessary copy instructions. For
1512 instance, a sequence of instructions such as:</p>
1515 <pre>
1516 %EBX = LOAD %mem_address
1517 %EAX = COPY %EBX
1518 </pre>
1519 </div>
1521 <p>can be safely substituted by the single instruction:
1524 <pre>
1525 %EAX = LOAD %mem_address
1526 </pre>
1527 </div>
1529 <p>Instructions can be folded with the
1531 taken when folding instructions; a folded instruction can be quite
1532 different from the original instruction. See
1536 </div>
1538 <!-- _______________________________________________________________________ -->
1542 </div>
1546 <p>The LLVM infrastructure provides the application developer with
1547 three different register allocators:</p>
1549 <ul>
1551 not keep values in registers across instructions. This register
1552 allocator immediately spills every value right after it is
1553 computed, and reloads all used operands from memory to temporary
1554 registers before each instruction.</li>
1557 block level, attempting to keep values in registers and reusing
1558 registers as appropriate.</li>
1560 well-know linear scan register allocator. Whereas the
1563 uses a spiller in order to place load and stores.</li>
1564 </ul>
1570 <pre>
1571 $ llc -f -regalloc=simple file.bc -o sp.s;
1572 $ llc -f -regalloc=local file.bc -o lc.s;
1573 $ llc -f -regalloc=linearscan file.bc -o ln.s;
1574 </pre>
1575 </div>
1577 </div>
1579 <!-- ======================================================================= -->
1582 </div>
1584 <!-- ======================================================================= -->
1587 </div>
1589 <!-- ======================================================================= -->
1592 </div>
1594 <!-- _______________________________________________________________________ -->
1597 </div>
1599 <!-- _______________________________________________________________________ -->
1602 </div>
1606 </div>
1609 <!-- *********************************************************************** -->
1612 </div>
1613 <!-- *********************************************************************** -->
1617 <p>This section of the document explains features or design decisions that
1618 are specific to the code generator for a particular target.</p>
1620 </div>
1623 <!-- ======================================================================= -->
1626 </div>
1631 code generator currently targets a generic P6-like processor. As such, it
1632 produces a few P6-and-above instructions (like conditional moves), but it does
1633 not make use of newer features like MMX or SSE. In the future, the X86 backend
1634 will have sub-target support added for specific processor families and
1635 implementations.</p>
1637 </div>
1639 <!-- _______________________________________________________________________ -->
1642 </div>
1646 <p>The following are the known target triples that are supported by the X86
1647 backend. This is not an exhaustive list, and it would be useful to add those
1648 that people test.</p>
1650 <ul>
1657 </ul>
1659 </div>
1661 <!-- _______________________________________________________________________ -->
1664 </div>
1671 <ul>
1676 </ul>
1678 </div>
1680 <!-- _______________________________________________________________________ -->
1683 </div>
1687 <p>The x86 has a very flexible way of accessing memory. It is capable of
1688 forming memory addresses of the following expression directly in integer
1689 instructions (which use ModR/M addressing):</p>
1692 <pre>
1694 </pre>
1695 </div>
1701 <pre>
1703 Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement
1704 OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm
1705 </pre>
1707 <p>Stores, and all other instructions, treat the four memory operands in the
1708 same way and in the same order.</p>
1710 </div>
1712 <!-- _______________________________________________________________________ -->
1715 </div>
1719 <p>An instruction name consists of the base name, a default operand size, and a
1720 a character per operand with an optional special size. For example:</p>
1722 <p>
1727 </p>
1729 </div>
1731 <!-- ======================================================================= -->
1734 </div>
1737 <p>The PowerPC code generator lives in the lib/Target/PowerPC directory. The
1739 the PowerPC ISA; including ppc32, ppc64 and altivec.
1740 </p>
1741 </div>
1743 <!-- _______________________________________________________________________ -->
1746 </div>
1749 <p>LLVM follows the AIX PowerPC ABI, with two deviations. LLVM uses a PC
1750 relative (PIC) or static addressing for accessing global values, so no TOC (r2)
1751 is used. Second, r31 is used as a frame pointer to allow dynamic growth of a
1752 stack frame. LLVM takes advantage of having no TOC to provide space to save
1753 the frame pointer in the PowerPC linkage area of the caller frame. Other
1754 details of PowerPC ABI can be found at <a href=
1755 "http://developer.apple.com/documentation/DeveloperTools/Conceptual/LowLevelABI/Articles/32bitPowerPC.html"
1758 reserved for system use.</p>
1759 </div>
1761 <!-- _______________________________________________________________________ -->
1764 </div>
1767 <p>The size of a PowerPC frame is usually fixed for the duration of a
1768 function’s invocation. Since the frame is fixed size, all references into
1769 the frame can be accessed via fixed offsets from the stack pointer. The
1770 exception to this is when dynamic alloca or variable sized arrays are present,
1771 then a base pointer (r31) is used as a proxy for the stack pointer and stack
1772 pointer is free to grow or shrink. A base pointer is also used if llvm-gcc is
1773 not passed the -fomit-frame-pointer flag. The stack pointer is always aligned to
1774 16 bytes, so that space allocated for altivec vectors will be properly
1775 aligned.</p>
1777 </div>
1781 <tr>
1783 </tr>
1784 <tr>
1786 </tr>
1787 <tr>
1789 </tr>
1790 <tr>
1792 </tr>
1793 <tr>
1795 </tr>
1797 <td><br></td>
1798 </tr>
1799 <tr>
1801 </tr>
1802 </table>
1803 </div>
1807 to allocating its own frame. Only three entries are relevant to LLVM. The
1808 first entry is the previous stack pointer (sp), aka link. This allows probing
1809 tools like gdb or exception handlers to quickly scan the frames in the stack. A
1810 function epilog can also use the link to pop the frame from the stack. The
1811 third entry in the linkage area is used to save the return address from the lr
1812 register. Finally, as mentioned above, the last entry is used to save the
1813 previous frame pointer (r31.) The entries in the linkage area are the size of a
1815 bit mode.</p>
1816 </div>
1821 <tr>
1824 </tr>
1825 <tr>
1828 </tr>
1829 <tr>
1832 </tr>
1833 <tr>
1836 </tr>
1837 <tr>
1840 </tr>
1841 <tr>
1844 </tr>
1845 </table>
1846 </div>
1851 <tr>
1854 </tr>
1855 <tr>
1858 </tr>
1859 <tr>
1862 </tr>
1863 <tr>
1866 </tr>
1867 <tr>
1870 </tr>
1871 <tr>
1874 </tr>
1875 </table>
1876 </div>
1880 function. Following the PowerPC ABI, the first few arguments are actually
1881 passed in registers, with the space in the parameter area unused. However, if
1882 there are not enough registers or the callee is a thunk or vararg function,
1883 these register arguments can be spilled into the parameter area. Thus, the
1884 parameter area must be large enough to store all the parameters for the largest
1885 call sequence made by the caller. The size must also be mimimally large enough
1886 to spill registers r3-r10. This allows callees blind to the call signature,
1887 such as thunks and vararg functions, enough space to cache the argument
1889 bit mode.) Also note that since the parameter area is a fixed offset from the
1890 top of the frame, that a callee can access its spilt arguments using fixed
1891 offsets from the stack pointer (or base pointer.)</p>
1892 </div>
1895 <p>Combining the information about the linkage, parameter areas and alignment. A
1897 mode.</p>
1898 </div>
1902 alloca then space is added to the stack, the linkage and parameter areas are
1903 shifted to top of stack, and the new space is available immediately below the
1904 linkage and parameter areas. The cost of shifting the linkage and parameter
1905 areas is minor since only the link value needs to be copied. The link value can
1906 be easily fetched by adding the original frame size to the base pointer. Note
1908 </div>
1912 variables.</p>
1913 </div>
1917 registers on entry to the callee.</p>
1918 </div>
1920 <!-- _______________________________________________________________________ -->
1923 </div>
1926 <p>The llvm prolog and epilog are the same as described in the PowerPC ABI, with
1927 the following exceptions. Callee saved registers are spilled after the frame is
1928 created. This allows the llvm epilog/prolog support to be common with other
1929 targets. The base pointer callee saved register r31 is saved in the TOC slot of
1930 linkage area. This simplifies allocation of space for the base pointer and
1931 makes it convenient to locate programatically and during debugging.</p>
1932 </div>
1934 <!-- _______________________________________________________________________ -->
1937 </div>
1940 <p></p>
1941 </div>
1945 </div>
1948 <!-- *********************************************************************** -->
1949 <hr>
1950 <address>
1958 Last modified: $Date$
1959 </address>
1961 </body>
1962 </html>