| blob | b430d4dd3f4bf706432ee85b141ff47faa55032e |
3 <html>
4 <head>
8 </head>
10 <body>
13 Writing an LLVM Compiler Backend
14 </div>
16 <ol>
18 <ul>
23 </ul>
26 <ul>
30 </ul></li>
32 <ul>
36 </ul></li>
38 <ul>
40 <ul>
45 </ul></li>
47 </ul></li>
51 <ul>
54 </ul></li>
55 </ol>
60 </div>
62 <!-- *********************************************************************** -->
65 </div>
66 <!-- *********************************************************************** -->
70 <p>
71 This document describes techniques for writing compiler backends that convert
72 the LLVM Intermediate Representation (IR) to code for a specified machine or
73 other languages. Code intended for a specific machine can take the form of
74 either assembly code or binary code (usable for a JIT compiler).
75 </p>
77 <p>
78 The backend of LLVM features a target-independent code generator that may create
79 output for several types of target CPUs — including X86, PowerPC, Alpha,
80 and SPARC. The backend may also be used to generate code targeted at SPUs of the
81 Cell processor or GPUs to support the execution of compute kernels.
82 </p>
84 <p>
85 The document focuses on existing examples found in subdirectories
87 document focuses on the example of creating a static compiler (one that emits
88 text assembly) for a SPARC target, because SPARC has fairly standard
89 characteristics, such as a RISC instruction set and straightforward calling
90 conventions.
91 </p>
93 </div>
97 </div>
101 <p>
102 The audience for this document is anyone who needs to write an LLVM backend to
103 generate code for a specific hardware or software target.
104 </p>
106 </div>
110 </div>
114 <p>
115 These essential documents must be read before reading this document:
116 </p>
118 <ul>
124 (classes and code generation algorithms) for translating the LLVM internal
125 representation into machine code for a specified target. Pay particular
126 attention to the descriptions of code generation stages: Instruction
127 Selection, Scheduling and Formation, SSA-based Optimization, Register
128 Allocation, Prolog/Epilog Code Insertion, Late Machine Code Optimizations,
129 and Code Emission.</li>
134 support LLVM code generation. TableGen processes input from a target
136 used for code generation.</li>
140 several SelectionDAG processing steps.</li>
141 </ul>
143 <p>
144 To follow the SPARC examples in this document, have a copy of
148 Reference Manual</a></i>. For more about the GNU Assembler format
152 machine dependent features.
153 </p>
155 </div>
159 </div>
163 <p>
164 To write a compiler backend for LLVM that converts the LLVM IR to code for a
165 specified target (machine or other language), follow these steps:
166 </p>
168 <ul>
169 <li>Create a subclass of the TargetMachine class that describes characteristics
170 of your target machine. Copy existing examples of specific TargetMachine
171 class and header files; for example, start with
173 change the file names for your target. Similarly, change code that
176 <li>Describe the register set of the target. Use TableGen to generate code for
177 register definition, register aliases, and register classes from a
179 additional code for a subclass of the TargetRegisterInfo class that
180 represents the class register file data used for register allocation and
181 also describes the interactions between registers.</li>
183 <li>Describe the instruction set of the target. Use TableGen to generate code
184 for target-specific instructions from target-specific versions of
186 write additional code for a subclass of the TargetInstrInfo class to
187 represent machine instructions supported by the target machine. </li>
189 <li>Describe the selection and conversion of the LLVM IR from a Directed Acyclic
190 Graph (DAG) representation of instructions to native target-specific
191 instructions. Use TableGen to generate code that matches patterns and
192 selects instructions based on additional information in a target-specific
195 to perform pattern matching and DAG-to-DAG instruction selection. Also write
197 data types that are not supported natively in a SelectionDAG. </li>
199 <li>Write code for an assembly printer that converts LLVM IR to a GAS format for
200 your target machine. You should add assembly strings to the instructions
202 should also write code for a subclass of AsmPrinter that performs the
203 LLVM-to-assembly conversion and a trivial subclass of TargetAsmInfo.</li>
205 <li>Optionally, add support for subtargets (i.e., variants with different
206 capabilities). You should also write code for a subclass of the
210 <li>Optionally, add JIT support and create a machine code emitter (subclass of
211 TargetJITInfo) that is used to emit binary code directly into memory. </li>
212 </ul>
214 <p>
216 then implement them later. Initially, you may not know which private members
217 that the class will need and which components will need to be subclassed.
218 </p>
220 </div>
224 </div>
228 <p>
229 To actually create your compiler backend, you need to create and modify a few
230 files. The absolute minimum is discussed here. But to actually use the LLVM
231 target-independent code generator, you must perform the steps described in
233 Target-Independent Code Generator</a> document.
234 </p>
236 <p>
238 the files related to your target. If your target is called "Dummy," create the
240 </p>
242 <p>
243 In this new
252 target).
253 </p>
255 <p>
259 </p>
261 <p>
262 To make your target actually do something, you need to implement a subclass of
266 target independent code generator, you should do what all current machine
269 </p>
271 <p>
272 To get LLVM to actually build and link your target, you need to add it to
276 target to the lists there (some creativity required), and then
279 </p>
281 </div>
283 <!-- *********************************************************************** -->
286 </div>
287 <!-- *********************************************************************** -->
291 <p>
294 class should be specialized by a concrete target class that implements the
298 processes numerous command-line options.
299 </p>
301 <p>
304 should name the files that you create to reflect your specific target. For
307 </p>
309 <p>
317 characteristics, such as data type size and alignment requirements.
318 </p>
320 <p>
321 For instance, for the SPARC target, the header file
324 </p>
327 <pre>
328 namespace llvm {
330 class Module;
332 class SparcTargetMachine : public LLVMTargetMachine {
333 const TargetData DataLayout; // Calculates type size & alignment
334 SparcSubtarget Subtarget;
335 SparcInstrInfo InstrInfo;
336 TargetFrameInfo FrameInfo;
338 protected:
339 virtual const TargetAsmInfo *createTargetAsmInfo() const;
341 public:
344 virtual const SparcInstrInfo *getInstrInfo() const {return &InstrInfo; }
345 virtual const TargetFrameInfo *getFrameInfo() const {return &FrameInfo; }
346 virtual const TargetSubtarget *getSubtargetImpl() const{return &Subtarget; }
347 virtual const TargetRegisterInfo *getRegisterInfo() const {
348 return &InstrInfo.getRegisterInfo();
349 }
350 virtual const TargetData *getTargetData() const { return &DataLayout; }
351 static unsigned getModuleMatchQuality(const Module &M);
353 // Pass Pipeline Configuration
354 virtual bool addInstSelector(PassManagerBase &PM, bool Fast);
355 virtual bool addPreEmitPass(PassManagerBase &PM, bool Fast);
356 virtual bool addAssemblyEmitter(PassManagerBase &PM, bool Fast,
357 std::ostream &Out);
358 };
360 } // end namespace llvm
361 </pre>
362 </div>
364 </div>
369 <ul>
375 </ul>
379 <ul>
382 </ul>
384 <p>
387 machine, including characteristics such as pointer size, alignment, and
388 endianness. For example, the constructor for SparcTargetMachine contains the
389 following:
390 </p>
393 <pre>
395 : DataLayout("E-p:32:32-f128:128:128"),
396 Subtarget(M, FS), InstrInfo(Subtarget),
398 }
399 </pre>
400 </div>
402 </div>
408 <ul>
413 preferred alignment. If only two figures follow "<tt>p:</tt>", then the
414 first value is pointer size, and the second value is both ABI and preferred
415 alignment.</li>
420 followed by ABI alignment and preferred alignment. "<tt>f</tt>" is followed
421 by three values: the first indicates the size of a long double, then ABI
422 alignment, and then ABI preferred alignment.</li>
423 </ul>
425 <p>
429 </p>
432 <pre>
433 namespace {
434 // Register the target.
436 }
437 </pre>
438 </div>
440 </div>
442 <!-- *********************************************************************** -->
445 </div>
446 <!-- *********************************************************************** -->
450 <p>
451 You should describe a concrete target-specific class that represents the
454 file data that is used for register allocation. It also describes the
455 interactions between registers.
456 </p>
458 <p>
459 You also need to define register classes to categorize related registers. A
460 register class should be added for groups of registers that are all treated the
461 same way for some instruction. Typical examples are register classes for
462 integer, floating-point, or vector registers. A register allocator allows an
463 instruction to use any register in a specified register class to perform the
464 instruction in a similar manner. Register classes allocate virtual registers to
465 instructions from these sets, and register classes let the target-independent
466 register allocator automatically choose the actual registers.
467 </p>
469 <p>
470 Much of the code for registers, including register definition, register aliases,
475 </p>
477 </div>
479 <!-- ======================================================================= -->
482 </div>
486 <p>
492 specify any aliases.
493 </p>
496 <pre>
498 string Namespace = "";
499 string AsmName = n;
500 string Name = n;
501 int SpillSize = 0;
502 int SpillAlignment = 0;
506 }
507 </pre>
508 </div>
510 <p>
512 definitions that utilize the Register class, such as:
513 </p>
516 <pre>
518 </pre>
519 </div>
521 <p>
527 different modes: the first element is for X86-64, the second for exception
529 that indicates the gcc number is undefined, and -2 indicates the register number
530 is invalid for this mode.
531 </p>
533 <p>
536 </p>
539 <pre>
540 static const unsigned GR8[] = { X86::AL, ... };
542 const unsigned AL_AliasSet[] = { X86::AX, X86::EAX, X86::RAX, 0 };
544 const TargetRegisterDesc RegisterDescriptors[] = {
545 ...
547 </pre>
548 </div>
550 <p>
554 </p>
557 <pre>
558 struct TargetRegisterDesc {
559 const char *AsmName; // Assembly language name for the register
560 const char *Name; // Printable name for the reg (for debugging)
561 const unsigned *AliasSet; // Register Alias Set
562 const unsigned *SubRegs; // Sub-register set
563 const unsigned *ImmSubRegs; // Immediate sub-register set
564 const unsigned *SuperRegs; // Super-register set
565 };</pre>
566 </div>
568 <p>
573 example, other definitions establish the registers "<tt>AX</tt>",
576 set.
577 </p>
579 <p>
584 </p>
587 <pre>
588 class RegisterWithSubRegs<string n,
590 let SubRegs = subregs;
591 }
592 </pre>
593 </div>
595 <p>
599 numbers, which is a feature common to these subclasses. Note the use of
602 </p>
605 <pre>
608 let Namespace = "SP";
609 }
610 // Ri - 32-bit integer registers
613 let Num = num;
614 }
615 // Rf - 32-bit floating-point registers
618 let Num = num;
619 }
620 // Rd - Slots in the FP register file for 64-bit
621 floating-point values.
624 let Num = num;
625 let SubRegs = subregs;
626 }
627 </pre>
628 </div>
630 <p>
633 </p>
636 <pre>
640 ...
645 ...
650 </pre>
651 </div>
653 <p>
655 double-precision floating-point registers that are aliases for pairs of
656 single-precision floating-point sub-registers. In addition to aliases, the
657 sub-register and super-register relationships of the defined register are in
658 fields of a register's TargetRegisterDesc.
659 </p>
661 </div>
663 <!-- ======================================================================= -->
666 </div>
670 <p>
672 define an object that represents a group of related registers and also defines
673 the default allocation order of the registers. A target description file
675 classes using the following class:
676 </p>
679 <pre>
680 class RegisterClass<string namespace,
683 string Namespace = namespace;
685 int Size = 0; // spill size, in bits; zero lets tblgen pick the size
686 int Alignment = alignment;
688 // CopyCost is the cost of copying a value between two registers
689 // default value 1 means a single instruction
690 // A negative value means copying is extremely expensive or impossible
691 int CopyCost = 1;
694 // for register classes that are subregisters of this class
697 code MethodProtos = [{}]; // to insert arbitrary code
698 code MethodBodies = [{}];
699 }
700 </pre>
701 </div>
705 <ul>
715 data in different configurations. For example a register that can process a
720 alignment required of the registers when they are stored or loaded to
721 memory.</li>
726 register allocator.</li>
727 </ul>
729 <p>
732 classes, the first argument defines the namespace with the string
735 a group of 16 double-precision registers
738 code into generated output.
739 </p>
742 <pre>
744 [F0, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12, F13, F14, F15,
745 F16, F17, F18, F19, F20, F21, F22, F23, F24, F25, F26, F27, F28, F29, F30, F31]>;
748 [D0, D1, D2, D3, D4, D5, D6, D7, D8, D9, D10, D11, D12, D13, D14, D15]>;
749
751 [L0, L1, L2, L3, L4, L5, L6, L7,
752 I0, I1, I2, I3, I4, I5,
753 O0, O1, O2, O3, O4, O5, O7,
754 G1,
755 // Non-allocatable regs:
756 G2, G3, G4,
757 O6, // stack ptr
758 I6, // frame ptr
759 I7, // return address
760 G0, // constant zero
761 G5, G6, G7 // reserved for kernel
762 ]> {
763 let MethodProtos = [{
764 iterator allocation_order_end(const MachineFunction &MF) const;
765 }];
766 let MethodBodies = [{
767 IntRegsClass::iterator
768 IntRegsClass::allocation_order_end(const MachineFunction &MF) const {
769 return end() - 10 // Don't allocate special registers
770 -1;
771 }
772 }];
773 }
774 </pre>
775 </div>
777 <p>
779 that are intended for inclusion in other source code that you write.
781 which should be included in the header file for the implementation of the SPARC
785 base. It also specifies types, based upon the defined register
787 </p>
789 <p>
792 register implementation. The code below shows only the generated integer
793 registers and associated register classes. The order of registers
795 the target description file. Take special note of the use
799 </p>
802 <pre> // IntRegs Register Class...
803 static const unsigned IntRegs[] = {
804 SP::L0, SP::L1, SP::L2, SP::L3, SP::L4, SP::L5,
805 SP::L6, SP::L7, SP::I0, SP::I1, SP::I2, SP::I3,
806 SP::I4, SP::I5, SP::O0, SP::O1, SP::O2, SP::O3,
807 SP::O4, SP::O5, SP::O7, SP::G1, SP::G2, SP::G3,
808 SP::G4, SP::O6, SP::I6, SP::I7, SP::G0, SP::G5,
809 SP::G6, SP::G7,
810 };
812 // IntRegsVTs Register Class Value Types...
813 static const MVT::ValueType IntRegsVTs[] = {
814 MVT::i32, MVT::Other
815 };
817 namespace SP { // Register class instances
818 DFPRegsClass DFPRegsRegClass;
819 FPRegsClass FPRegsRegClass;
820 IntRegsClass IntRegsRegClass;
821 ...
822 // IntRegs Sub-register Classess...
823 static const TargetRegisterClass* const IntRegsSubRegClasses [] = {
824 NULL
825 };
826 ...
827 // IntRegs Super-register Classess...
828 static const TargetRegisterClass* const IntRegsSuperRegClasses [] = {
829 NULL
830 };
831 ...
832 // IntRegs Register Class sub-classes...
833 static const TargetRegisterClass* const IntRegsSubclasses [] = {
834 NULL
835 };
836 ...
837 // IntRegs Register Class super-classes...
838 static const TargetRegisterClass* const IntRegsSuperclasses [] = {
839 NULL
840 };
841 ...
842 IntRegsClass::iterator
843 IntRegsClass::allocation_order_end(const MachineFunction &MF) const {
844 return end()-10 // Don't allocate special registers
845 -1;
846 }
848 IntRegsClass::IntRegsClass() : TargetRegisterClass(IntRegsRegClassID,
849 IntRegsVTs, IntRegsSubclasses, IntRegsSuperclasses, IntRegsSubRegClasses,
851 }
852 </pre>
853 </div>
855 </div>
857 <!-- ======================================================================= -->
861 </div>
865 <p>
869 overridden. Here is a list of functions that are overridden for the SPARC
871 </p>
873 <ul>
875 in the order of the desired callee-save stack frame offset.</li>
878 register classes with which to spill each callee saved register.</li>
881 register numbers, indicating if a particular register is unavailable.</li>
884 a dedicated frame pointer register.</li>
887 destroy pseudo instructions are used, this can be called to eliminate
888 them.</li>
891 instructions that may use them.</li>
896 </ul>
898 </div>
900 <!-- *********************************************************************** -->
903 </div>
905 <!-- *********************************************************************** -->
908 <p>
909 During the early stages of code generation, the LLVM IR code is converted to a
912 requirements, and operation properties. For example, is an operation
913 commutative, does an operation load from memory. The various operation node
916 </p>
918 <p>
920 generate much of the code for instruction definition:
921 </p>
923 <ul>
935 target-specific instructions.</li>
938 templates, condition codes, and instructions of an instruction set. For
939 architecture modifications, a different file name may be used. For example,
942 </ul>
944 <p>
947 input files, but its contents are only directly important for subtargets.
948 </p>
950 <p>
952 represents machine instructions supported by a target machine.
954 each of which describes one instruction. An instruction descriptor defines:</p>
956 <ul>
966 </ul>
968 <p>
970 for more complex instruction classes.
971 </p>
974 <pre>class Instruction {
975 string Namespace = "";
976 dag OutOperandList; // An dag containing the MI def operand list.
977 dag InOperandList; // An dag containing the MI use operand list.
978 string AsmString = ""; // The .s format to print the instruction with.
983 ... remainder not shown for space ...
984 }
985 </pre>
986 </div>
988 <p>
990 representing a target-specific instruction that is defined
992 instructions from the architecture manual of the target machine (such as the
993 SPARC Architecture Manual for the SPARC target).
994 </p>
996 <p>
997 A single instruction from the architecture manual is often modeled as multiple
998 target instructions, depending upon its operands. For example, a manual might
999 describe an add instruction that takes a register or an immediate operand. An
1002 </p>
1004 <p>
1005 You should define a class for each instruction category and define each opcode
1006 as a subclass of the category with appropriate parameters such as the fixed
1007 binary encoding of opcodes and extended opcodes. You should map the register
1008 bits to the bits of the instruction in which they are encoded (for the
1009 JIT). Also you should specify how the instruction should be printed when the
1010 automatic assembly printer is used.
1011 </p>
1013 <p>
1014 As is described in the SPARC Architecture Manual, Version 8, there are three
1017 high bits of a register) instructions. Format 3 is for other instructions.
1018 </p>
1020 <p>
1023 classes are specified for more precise formats: for example
1029 synthetic SPARC instructions.
1030 </p>
1032 <p>
1038 operation value for this category of operation. The second parameter
1043 </p>
1047 "ld [$addr], $dst",
1048 [(set IntRegs:$dst, (load ADDRrr:$addr))]>;
1049 </pre>
1050 </div>
1052 <p>
1053 The fourth parameter is the input source, which uses the address
1055 </p>
1059 let PrintMethod = "printMemOperand";
1060 let MIOperandInfo = (ops IntRegs, IntRegs);
1061 }
1062 </pre>
1063 </div>
1065 <p>
1066 The fifth parameter is a string that is used by the assembly printer and can be
1067 left as an empty string until the assembly printer interface is implemented. The
1068 sixth and final parameter is the pattern used to match the instruction during
1069 the SelectionDAG Select Phase described in
1071 Target-Independent Code Generator</a>). This parameter is detailed in the next
1073 </p>
1075 <p>
1076 Instruction class definitions are not overloaded for different operand types, so
1077 separate versions of instructions are needed for register, memory, or immediate
1078 value operands. For example, to perform a Load Integer instruction for a Word
1079 from an immediate operand to a register, the following instruction class is
1080 defined:
1081 </p>
1085 "ld [$addr], $dst",
1086 [(set IntRegs:$dst, (load ADDRri:$addr))]>;
1087 </pre>
1088 </div>
1090 <p>
1091 Writing these definitions for so many similar instructions can involve a lot of
1093 creation of templates to define several instruction classes at once (using
1097 </p>
1102 (outs IntRegs:$dst), (ins IntRegs:$b, IntRegs:$c),
1103 !strconcat(OpcStr, " $b, $c, $dst"),
1104 [(set IntRegs:$dst, (OpNode IntRegs:$b, IntRegs:$c))]>;
1106 (outs IntRegs:$dst), (ins IntRegs:$b, i32imm:$c),
1107 !strconcat(OpcStr, " $b, $c, $dst"),
1108 [(set IntRegs:$dst, (OpNode IntRegs:$b, simm13:$c))]>;
1109 }
1110 </pre>
1111 </div>
1113 <p>
1117 </p>
1120 <pre>
1123 </pre>
1124 </div>
1126 <p>
1128 are referenced by branch instructions. The following definitions
1132 than' condition for floats.
1133 </p>
1136 <pre>
1140 ...
1144 ...
1145 </pre>
1146 </div>
1148 <p>
1153 </p>
1155 </div>
1157 <!-- ======================================================================= -->
1160 </div>
1164 <p>
1165 The code generator backend maps instruction operands to fields in the
1166 instruction. Operands are assigned to unbound fields in the instruction in the
1167 order they are defined. Fields are bound when they are assigned a value. For
1170 </p>
1173 <pre>
1175 (outs IntRegs:$dst), (ins IntRegs:$b, IntRegs:$c),
1176 "xnor $b, $c, $dst",
1177 [(set IntRegs:$dst, (not (xor IntRegs:$b, IntRegs:$c)))]>;
1178 </pre>
1179 </div>
1181 <p>
1184 </p>
1187 <pre>
1190 let Namespace = "SP";
1193 dag OutOperandList = outs;
1194 dag InOperandList = ins;
1195 let AsmString = asmstr;
1196 let Pattern = pattern;
1197 }
1198 </pre>
1199 </div>
1204 <pre>
1214 }
1215 </pre>
1216 </div>
1218 <p>
1222 </p>
1225 <pre>
1230 let op = opVal;
1231 let op3 = op3val;
1235 }
1236 </pre>
1237 </div>
1239 <p>
1245 </p>
1247 </div>
1249 <!-- ======================================================================= -->
1253 </div>
1257 <p>
1261 overridden. Here's a list of functions that are overridden for the SPARC
1263 </p>
1265 <ul>
1267 register move; false, otherwise.</li>
1270 a direct load from a stack slot, return the register number of the
1274 a direct store to a stack slot, return the register number of the
1280 slot.</li>
1283 slot.</li>
1290 load or store instruction for the specified operand(s).</li>
1291 </ul>
1293 </div>
1295 <!-- ======================================================================= -->
1298 </div>
1301 <p>
1302 Performance can be improved by combining instructions or by eliminating
1306 a machine basic block (MBB) for opportunities for improvement, such as branch
1311 instructions.
1312 </p>
1314 <p>
1318 implementation is shown below.
1319 </p>
1323 <ul>
1325 examined.</li>
1329 the destination.</li>
1335 operands to evaluate a condition for a conditional branch.</li>
1336 </ul>
1338 <p>
1339 In the simplest case, if a block ends without a branch, then it falls through to
1343 function parameters and the code for the simplest case.
1344 </p>
1350 {
1351 MachineBasicBlock::iterator I = MBB.end();
1352 if (I == MBB.begin() || !isUnpredicatedTerminator(--I))
1353 return false;
1354 </pre>
1355 </div>
1357 <p>
1358 If a block ends with a single unconditional branch instruction, then
1361 </p>
1364 <pre>
1365 if (LastOpc == ARM::B || LastOpc == ARM::tB) {
1367 return false;
1368 }
1369 </pre>
1370 </div>
1372 <p>
1373 If a block ends with two unconditional branches, then the second branch is never
1374 reached. In that situation, as shown below, remove the last branch instruction
1376 </p>
1379 <pre>
1380 if ((SecondLastOpc == ARM::B || SecondLastOpc==ARM::tB) &&
1381 (LastOpc == ARM::B || LastOpc == ARM::tB)) {
1383 I = LastInst;
1384 I->eraseFromParent();
1385 return false;
1386 }
1387 </pre>
1388 </div>
1390 <p>
1391 A block may end with a single conditional branch instruction that falls through
1392 to successor block if the condition evaluates to false. In that case,
1396 </p>
1399 <pre>
1400 if (LastOpc == ARM::Bcc || LastOpc == ARM::tBcc) {
1401 // Block ends with fall-through condbranch.
1405 return false;
1406 }
1407 </pre>
1408 </div>
1410 <p>
1411 If a block ends with both a conditional branch and an ensuing unconditional
1413 branch destination (assuming it corresponds to a conditional evaluation of
1418 </p>
1421 <pre>
1422 unsigned SecondLastOpc = SecondLastInst->getOpcode();
1424 if ((SecondLastOpc == ARM::Bcc && LastOpc == ARM::B) ||
1425 (SecondLastOpc == ARM::tBcc && LastOpc == ARM::tB)) {
1430 return false;
1431 }
1432 </pre>
1433 </div>
1435 <p>
1436 For the last two cases (ending with a single conditional branch or ending with
1437 one conditional and one unconditional branch), the operands returned in
1439 create new branches or perform other operations. An implementation
1442 </p>
1444 <p>
1448 return true if it encounters a terminator it cannot handle, such as an indirect
1449 branch.
1450 </p>
1452 </div>
1454 <!-- *********************************************************************** -->
1457 </div>
1458 <!-- *********************************************************************** -->
1462 <p>
1465 instructions. During code generation, instruction selection passes are performed
1466 to convert non-native DAG instructions into native target-specific
1468 match patterns and perform DAG-to-DAG instruction selection. Optionally, a pass
1470 operations for branch instructions. Later, the code in
1473 </p>
1475 <p>
1476 TableGen generates code for instruction selection using the following target
1477 description input files:
1478 </p>
1480 <ul>
1486 conventions for the target architecture, and it generates
1489 </ul>
1491 <p>
1492 The implementation of an instruction selection pass must include a header that
1495 selection pass into the queue of passes to run.
1496 </p>
1498 <p>
1503 SelectionDAG Instruction Selection Process</a>.
1504 </p>
1506 <p>
1507 To describe instruction selector behavior, you should add patterns for lowering
1511 the last parameter describes a pattern with the store DAG operator.
1512 </p>
1515 <pre>
1518 </pre>
1519 </div>
1521 <p>
1524 </p>
1527 <pre>
1529 </pre>
1530 </div>
1532 <p>
1534 function defined in an implementation of the Instructor Selector (such
1536 </p>
1538 <p>
1540 defined below:
1541 </p>
1544 <pre>
1545 def store : PatFrag<(ops node:$val, node:$ptr),
1546 (st node:$val, node:$ptr), [{
1549 ST->getAddressingMode() == ISD::UNINDEXED;
1550 return false;
1551 }]>;
1552 </pre>
1553 </div>
1555 <p>
1560 </p>
1563 <pre>
1564 SDNode *SelectCode(SDValue N) {
1565 ...
1567 switch (N.getOpcode()) {
1568 case ISD::STORE: {
1569 switch (NVT) {
1570 default:
1571 return Select_ISD_STORE(N);
1572 break;
1573 }
1574 break;
1575 }
1576 ...
1577 </pre>
1578 </div>
1580 <p>
1585 instruction.
1586 </p>
1589 <pre>
1590 SDNode *Select_ISD_STORE(const SDValue &N) {
1591 SDValue Chain = N.getOperand(0);
1592 if (Predicate_store(N.getNode())) {
1593 SDValue N1 = N.getOperand(1);
1594 SDValue N2 = N.getOperand(2);
1595 SDValue CPTmp0;
1596 SDValue CPTmp1;
1598 // Pattern: (st:void IntRegs:i32:$src,
1600 // Emits: (STrr:void ADDRrr:i32:$addr, IntRegs:i32:$src)
1602 if (SelectADDRrr(N, N2, CPTmp0, CPTmp1) &&
1605 return Emit_22(N, SP::STrr, CPTmp0, CPTmp1);
1606 }
1607 ...
1608 </pre>
1609 </div>
1611 </div>
1613 <!-- ======================================================================= -->
1616 </div>
1620 <p>
1621 The Legalize phase converts a DAG to use types and operations that are natively
1622 supported by the target. For natively unsupported types and operations, you need
1623 to add code to the target-specific XXXTargetLowering implementation to convert
1624 unsupported types and operations to supported ones.
1625 </p>
1627 <p>
1630 register classes are associated with them. The code for the register classes are
1633 constructor for the SparcTargetLowering class (in
1635 </p>
1638 <pre>
1639 addRegisterClass(MVT::i32, SP::IntRegsRegisterClass);
1640 addRegisterClass(MVT::f32, SP::FPRegsRegisterClass);
1641 addRegisterClass(MVT::f64, SP::DFPRegsRegisterClass);
1642 </pre>
1643 </div>
1645 <p>
1649 native support, add a callback to the constructor for the XXXTargetLowering
1650 class, so the instruction selection process knows what to do. The TargetLowering
1652 </p>
1654 <ul>
1668 </ul>
1670 <p>
1674 to see what methods are specifically supported.
1675 </p>
1677 <p>
1678 These callbacks are used to determine that an operation does or does not work
1679 with a specified type (or types). And in all cases, the third parameter is
1683 </p>
1685 </div>
1687 <!-- _______________________________________________________________________ -->
1690 </div>
1694 <p>
1695 For an operation without native support for a given type, the specified type may
1696 be promoted to a larger type that is supported. For example, SPARC does not
1700 </p>
1703 <pre>
1704 setLoadExtAction(ISD::SEXTLOAD, MVT::i1, Promote);
1705 </pre>
1706 </div>
1708 </div>
1710 <!-- _______________________________________________________________________ -->
1713 </div>
1717 <p>
1718 For a type without native support, a value may need to be broken down further,
1719 rather than promoted. For an operation without native support, a combination of
1720 other operations may be used to similar effect. In SPARC, the floating-point
1721 sine and cosine trig operations are supported by expansion to other operations,
1724 </p>
1727 <pre>
1728 setOperationAction(ISD::FSIN, MVT::f32, Expand);
1729 setOperationAction(ISD::FCOS, MVT::f32, Expand);
1730 </pre>
1731 </div>
1733 </div>
1735 <!-- _______________________________________________________________________ -->
1738 </div>
1742 <p>
1743 For some operations, simple type promotion or operation expansion may be
1744 insufficient. In some cases, a special intrinsic function must be implemented.
1745 </p>
1747 <p>
1748 For example, a constant value may require special treatment, or an operation may
1749 require spilling and restoring registers in the stack and working with register
1750 allocators.
1751 </p>
1753 <p>
1755 conversion from a floating point value to a signed integer, first the
1757 parameter:
1758 </p>
1761 <pre>
1762 setOperationAction(ISD::FP_TO_SINT, MVT::i32, Custom);
1763 </pre>
1764 </div>
1766 <p>
1768 case statement should be added to indicate what function to call. In the
1771 </p>
1774 <pre>
1775 SDValue SparcTargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) {
1776 switch (Op.getOpcode()) {
1777 case ISD::FP_TO_SINT: return LowerFP_TO_SINT(Op, DAG);
1778 ...
1779 }
1780 }
1781 </pre>
1782 </div>
1784 <p>
1786 register to convert the floating-point value to an integer.
1787 </p>
1790 <pre>
1791 static SDValue LowerFP_TO_SINT(SDValue Op, SelectionDAG &DAG) {
1792 assert(Op.getValueType() == MVT::i32);
1793 Op = DAG.getNode(SPISD::FTOI, MVT::f32, Op.getOperand(0));
1794 return DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Op);
1795 }
1796 </pre>
1797 </div>
1799 </div>
1801 <!-- _______________________________________________________________________ -->
1804 </div>
1808 <p>
1813 natively supported only for SPARC v9. The following code enables
1815 </p>
1818 <pre>
1819 setOperationAction(ISD::CTPOP, MVT::i32, Expand);
1820 ...
1822 setOperationAction(ISD::CTPOP, MVT::i32, Legal);
1823 case ISD::SETULT: return SPCC::ICC_CS;
1824 case ISD::SETULE: return SPCC::ICC_LEU;
1825 case ISD::SETUGT: return SPCC::ICC_GU;
1826 case ISD::SETUGE: return SPCC::ICC_CC;
1827 }
1828 }
1829 </pre>
1830 </div>
1832 </div>
1834 <!-- ======================================================================= -->
1837 </div>
1841 <p>
1843 uses interfaces (such as CCIfType and CCAssignToReg) that are defined in
1849 </p>
1851 <ul>
1854 <li>Where parameters and return values are placed (that is, on the stack or in
1855 registers).</li>
1860 </ul>
1862 <p>
1869 </p>
1872 <pre>
1874 </pre>
1875 </div>
1877 <p>
1879 return-value calling convention (RetCC_Sparc32) and a basic 32-bit C calling
1881 (shown below) indicates which registers are used for specified scalar return
1885 </p>
1888 <pre>
1889 def RetCC_Sparc32 : CallingConv<[
1893 ]>;
1894 </pre>
1895 </div>
1897 <p>
1900 specified size and alignment. In the example below, the first parameter, 4,
1901 indicates the size of the slot, and the second parameter, also 4, indicates the
1902 stack alignment along 4-byte units. (Special cases: if size is zero, then the
1903 ABI size is used; if alignment is zero, then the ABI alignment is used.)
1904 </p>
1907 <pre>
1908 def CC_Sparc32 : CallingConv<[
1909 // All arguments get passed in integer registers if there is space.
1912 ]>;
1913 </pre>
1914 </div>
1916 <p>
1918 specified sub-calling convention, and, if a match is found, it is invoked. In
1923 </p>
1926 <pre>
1927 def RetCC_X86_32_C : CallingConv<[
1931 ]>;
1932 </pre>
1933 </div>
1935 <p>
1937 current calling convention. If the name identifies the current calling
1938 convention, then a specified action is invoked. In the following example (in
1942 </p>
1945 <pre>
1946 def RetCC_X86_32 : CallingConv<[
1950 ]>;
1951 </pre>
1952 </div>
1956 <ul>
1958 apply the action.</li>
1967 not take a variable number of arguments, apply the action.</li>
1973 slot with the minimum specified size and alignment.</li>
1976 the specified type.</li>
1979 convention that is supported.</li>
1980 </ul>
1982 </div>
1984 <!-- *********************************************************************** -->
1987 </div>
1988 <!-- *********************************************************************** -->
1992 <p>
1993 During the code emission stage, the code generator may utilize an LLVM pass to
1994 produce assembly output. To do this, you want to implement the code for a
1995 printer that converts LLVM IR to a GAS-format assembly language for your target
1996 machine, using the following steps:
1997 </p>
1999 <ul>
2000 <li>Define all the assembly strings for your target, adding them to the
2012 methods.</li>
2015 class that performs the LLVM-to-assembly conversion.</li>
2016 </ul>
2018 <p>
2024 </p>
2027 <pre>
2028 SparcTargetAsmInfo::SparcTargetAsmInfo(const SparcTargetMachine &TM) {
2029 Data16bitsDirective = "\t.half\t";
2030 Data32bitsDirective = "\t.word\t";
2031 Data64bitsDirective = 0; // .xword is only supported by V9.
2032 ZeroDirective = "\t.skip\t";
2033 CommentString = "!";
2035 }
2036 </pre>
2037 </div>
2039 <p>
2043 </p>
2045 <p>
2046 A target-specific implementation of AsmPrinter is written in
2048 converts the LLVM to printable assembly. The implementation must include the
2052 </p>
2055 <pre>
2056 #include "llvm/CodeGen/AsmPrinter.h"
2057 #include "llvm/CodeGen/MachineFunctionPass.h"
2058 </pre>
2059 </div>
2061 <p>
2065 variable names.
2066 </p>
2068 <p>
2074 generally do the following to process each machine function:
2075 </p>
2077 <ul>
2081 which have been spilled to memory.</li>
2084 function.</li>
2088 <li>Print out the code for the function, including basic block labels and the
2090 </ul>
2092 <p>
2097 </p>
2099 <ul>
2119 </ul>
2121 <p>
2124 generally adequate for printing assembly and do not need to be
2128 </p>
2130 <p>
2132 statement for the type of operand: register, immediate, basic block, external
2133 symbol, global address, constant pool index, or jump table index. For an
2135 should be implemented to generate the proper output. Similarly,
2137 </p>
2140 it should be called to shut down the assembly printer. During
2142 output.
2143 </p>
2145 </div>
2147 <!-- *********************************************************************** -->
2150 </div>
2151 <!-- *********************************************************************** -->
2155 <p>
2156 Subtarget support is used to inform the code generation process of instruction
2157 set variations for a given chip set. For example, the LLVM SPARC implementation
2158 provided covers three major versions of the SPARC microprocessor architecture:
2160 architecture), and the UltraSPARC architecture. V8 has 16 double-precision
2162 quad-precision registers. V8 is also purely big-endian. V9 has 32
2163 double-precision floating-point registers that are also usable as 16
2164 quad-precision registers, but cannot be used as single-precision registers. The
2165 UltraSPARC architecture combines V9 with UltraSPARC Visual Instruction Set
2166 extensions.
2167 </p>
2169 <p>
2170 If subtarget support is needed, you should implement a target-specific
2171 XXXSubtarget class for your architecture. This class should process the
2173 </p>
2175 <p>
2180 attribute set by the feature, the value of the attribute, and a description of
2181 the feature. (The fifth parameter is a list of features whose presence is
2182 implied, and its default value is an empty array.)
2183 </p>
2186 <pre>
2187 class SubtargetFeature<string n, string a, string v, string d,
2189 string Name = n;
2190 string Attribute = a;
2191 string Value = v;
2192 string Desc = d;
2194 }
2195 </pre>
2196 </div>
2198 <p>
2200 following features.
2201 </p>
2204 <pre>
2212 </pre>
2213 </div>
2215 <p>
2217 define particular SPARC processor subtypes that may have the previously
2218 described features.
2219 </p>
2222 <pre>
2225
2239 </pre>
2240 </div>
2242 <p>
2244 SparcGenSubtarget.inc specifies enum values to identify the features, arrays of
2245 constants to represent the CPU features and CPU subtypes, and the
2246 ParseSubtargetFeatures method that parses the features string that sets
2249 implementation of the XXXSubtarget method should follow this pseudocode:
2250 </p>
2253 <pre>
2255 // Set the default features
2256 // Determine default and user specified characteristics of the CPU
2257 // Call ParseSubtargetFeatures(FS, CPU) to parse the features string
2258 // Perform any additional operations
2259 }
2260 </pre>
2261 </div>
2263 </div>
2265 <!-- *********************************************************************** -->
2268 </div>
2269 <!-- *********************************************************************** -->
2273 <p>
2274 The implementation of a target machine optionally includes a Just-In-Time (JIT)
2275 code generator that emits machine code and auxiliary structures as binary output
2276 that can be written directly to memory. To do this, implement JIT code
2277 generation by performing the following steps:
2278 </p>
2280 <ul>
2282 pass that transforms target-machine instructions into relocatable machine
2283 code.</li>
2286 target-specific code-generation activities, such as emitting machine code
2287 and stubs.</li>
2291 </ul>
2293 <p>
2294 There are several different approaches to writing the JIT support code. For
2295 instance, TableGen and target descriptor files may be used for creating a JIT
2296 code generator, but are not mandatory. For the Alpha and PowerPC target
2298 contains the binary coding of machine instructions and the
2300 implementations do not.
2301 </p>
2303 <p>
2307 that write data (in bytes, words, strings, etc.) to the output stream.
2308 </p>
2310 </div>
2312 <!-- ======================================================================= -->
2315 </div>
2319 <p>
2321 is implemented as a function pass (subclass
2327 implemented with case statements on the instruction types defined in
2330 statements:
2331 </p>
2334 <pre>
2336 case X86II::Pseudo: // for not yet implemented instructions
2337 ... // or pseudo-instructions
2338 break;
2339 case X86II::RawFrm: // for instructions with a fixed opcode value
2340 ...
2341 break;
2342 case X86II::AddRegFrm: // for instructions that have one register operand
2343 ... // added to their opcode
2344 break;
2345 case X86II::MRMDestReg:// for instructions that use the Mod/RM byte
2346 ... // to specify a destination (register)
2347 break;
2348 case X86II::MRMDestMem:// for instructions that use the Mod/RM byte
2349 ... // to specify a destination (memory)
2350 break;
2351 case X86II::MRMSrcReg: // for instructions that use the Mod/RM byte
2352 ... // to specify a source (register)
2353 break;
2354 case X86II::MRMSrcMem: // for instructions that use the Mod/RM byte
2355 ... // to specify a source (memory)
2356 break;
2357 case X86II::MRM0r: case X86II::MRM1r: // for instructions that operate on
2358 case X86II::MRM2r: case X86II::MRM3r: // a REGISTER r/m operand and
2359 case X86II::MRM4r: case X86II::MRM5r: // use the Mod/RM byte and a field
2360 case X86II::MRM6r: case X86II::MRM7r: // to hold extended opcode data
2361 ...
2362 break;
2363 case X86II::MRM0m: case X86II::MRM1m: // for instructions that operate on
2364 case X86II::MRM2m: case X86II::MRM3m: // a MEMORY r/m operand and
2365 case X86II::MRM4m: case X86II::MRM5m: // use the Mod/RM byte and a field
2366 case X86II::MRM6m: case X86II::MRM7m: // to hold extended opcode data
2367 ...
2368 break;
2369 case X86II::MRMInitReg: // for instructions whose source and
2370 ... // destination are the same register
2371 break;
2372 }
2373 </pre>
2374 </div>
2376 <p>
2377 The implementations of these case statements often first emit the opcode and
2378 then get the operand(s). Then depending upon the operand, helper methods may be
2390 </p>
2393 <pre>
2394 case X86II::AddRegFrm:
2395 MCE.emitByte(BaseOpcode + getX86RegNum(MI.getOperand(CurOp++).getReg()));
2397 if (CurOp != NumOps) {
2398 const MachineOperand &MO1 = MI.getOperand(CurOp++);
2399 unsigned Size = X86InstrInfo::sizeOfImm(Desc);
2400 if (MO1.isImmediate())
2401 emitConstant(MO1.getImm(), Size);
2402 else {
2403 unsigned rt = Is64BitMode ? X86::reloc_pcrel_word
2404 : (IsPIC ? X86::reloc_picrel_word : X86::reloc_absolute_word);
2405 if (Opcode == X86::MOV64ri)
2406 rt = X86::reloc_absolute_dword; // FIXME: add X86II flag?
2407 if (MO1.isGlobalAddress()) {
2409 bool isLazy = gvNeedsLazyPtr(MO1.getGlobal());
2410 emitGlobalAddress(MO1.getGlobal(), rt, MO1.getOffset(), 0,
2411 NeedStub, isLazy);
2412 } else if (MO1.isExternalSymbol())
2413 emitExternalSymbolAddress(MO1.getSymbolName(), rt);
2414 else if (MO1.isConstantPoolIndex())
2415 emitConstPoolAddress(MO1.getIndex(), rt);
2416 else if (MO1.isJumpTableIndex())
2417 emitJumpTableAddress(MO1.getIndex(), rt);
2418 }
2419 }
2420 break;
2421 </pre>
2422 </div>
2424 <p>
2427 relocate addresses (for example, a global address with a PIC base offset). The
2431 addresses for referenced global symbols.
2432 </p>
2434 <p>
2436 for the X86 addresses. In all four cases, the relocated value is added to the
2439 </p>
2442 <pre>
2443 enum RelocationType {
2444 reloc_pcrel_word = 0, // add reloc value after adjusting for the PC loc
2445 reloc_picrel_word = 1, // add reloc value after adjusting for the PIC base
2446 reloc_absolute_word = 2, // absolute relocation; no additional adjustment
2447 reloc_absolute_dword = 3 // absolute relocation; no additional adjustment
2448 };
2449 </pre>
2450 </div>
2452 </div>
2454 <!-- ======================================================================= -->
2457 </div>
2461 <p>
2463 code-generation activities, such as emitting machine code and stubs. At minimum,
2465 </p>
2467 <ul>
2469 target a function that is used for compilation.</li>
2472 address for a callback function.</li>
2475 on relocation types.</li>
2477 <li>Callback function that are wrappers to a function stub that is used when the
2478 real target is not initially known.</li>
2479 </ul>
2481 <p>
2484 callback function that will be used a function wrapper. For the Alpha target
2486 implementation is simply:
2487 </p>
2490 <pre>
2491 TargetJITInfo::LazyResolverFn AlphaJITInfo::getLazyResolverFunction(
2492 JITCompilerFn F) {
2493 JITCompilerFunction = F;
2494 return AlphaCompilationCallback;
2495 }
2496 </pre>
2497 </div>
2499 <p>
2501 little more complication, because it returns a different callback function for
2502 processors with SSE instructions and XMM registers.
2503 </p>
2505 <p>
2506 The callback function initially saves and later restores the callee register
2507 values, incoming arguments, and frame and return address. The callback function
2508 needs low-level access to the registers or stack, so it is typically implemented
2509 with assembler.
2510 </p>
2512 </div>
2514 <!-- *********************************************************************** -->
2516 <hr>
2517 <address>
2523 <a href="http://www.woo.com">Mason Woo</a> and <a href="http://misha.brukman.net">Misha Brukman</a><br>
2525 <br>
2526 Last modified: $Date$
2527 </address>
2529 </body>
2530 </html>