Part 7.  Target Independent Code Generation.

Part 7.1 Official document on target independent code generator

First let’s take a look at the high-level overview of the target independent code generation in the LLVM document. This helps to establish a global picture of the relationships among various components (e.g., DAG, target independent algorithms for register allocation/instruction selection/scheduling, MC layer, target independent machine code representation, target description, etc.) of the LLVM code generator:

http://llvm.org/docs/CodeGenerator.html

The related source files are primarily located in llvm-3.1.src\lib\CodeGen,  llvm-3.1.src\lib\MC and llvm-3.1.src\lib\Target.  Note that under llvm-3.1.src\lib\Target there are sub-directories for various targets.  Those are target specific and will be discussed in Part 8.  

a tentative chapter list:

Part 7.2 Target  description

The interfaces of target independent descriptions are located in the include/llvm/Target directory and the implementations of these abstract target descriptions live in lib/Target/ directory (not the sub-directories). Important classes for abstracting various targets include TargetMachine,  DataLayout, TargetLowering, TargetFrameLowering, TargetRegisterInfo, TargetInstrInfo, TargetFrameInfo, TargetSubtarget and TargetJITInfo classes.   All of the target description classes (except the DataLayout class) are designed to be subclassed by the concrete target implementation, and have virtual methods implemented. The TargetMachine class provides virtual methods that are used to access the target-specific implementations of the various target description classes via the get**Info methods (getInstrInfo, getRegisterInfo, getFrameInfo, etc.). This class is designed to be specialized by a concrete target implementation (e.g., X86TargetMachine) which implements the various virtual methods. In the following subsections we are going to introduce the TargetMachine as well as other important classes for abstract target description.

Part 7.2.1 TargetMachine Class

As stated above, a concrete  target machine implementation should subclass the TargetMachine class and provide methods to enable accesses to the target-specific information such as the register files, instructions, frames, etc.  There are some ready-for-use target machines (although some of them may not run stably) implemented for common architectures and these target machines have the following relationships with their base class TargetMachine:

   

Let’s first look into the TargetMachine class and see what’s in it:

00051 /// TargetMachine - Primary interface to the complete machine description for
00052
/// the target machine.  All target-specific information should be accessible
00053
/// through this interface.
00054
///
00055 class TargetMachine {
00056  
 TargetMachine(const TargetMachine &) LLVM_DELETED_FUNCTION;
00057  
void operator=(const TargetMachine &) LLVM_DELETED_FUNCTION;
00058
protected: // Can only create subclasses.
00059  
 TargetMachine(const Target &T, StringRef TargetTriple,
00060                
 StringRef CPU, StringRef FS, const TargetOptions &Options);
00061
00062
 /// getSubtargetImpl - virtual method implemented by subclasses that returns
00063
 /// a reference to that target's TargetSubtargetInfo-derived member variable.
00064  virtual const TargetSubtargetInfo *getSubtargetImpl() const { return 0; }
00065
00066
 /// TheTarget - The Target that this machine was created for.
00067  const Target &TheTarget;
00068
00069
 /// TargetTriple, TargetCPU, TargetFS - Triple string, CPU name, and target
00070
 /// feature strings the TargetMachine instance is created with.
00071  std::string TargetTriple;
00072   std::string TargetCPU;
00073   std::string TargetFS;

…...............................................

00100   // Interfaces to the major aspects of target machine information:
00101  
// -- Instruction opcode and operand information
00102  
// -- Pipelines and scheduling information
00103  
// -- Stack frame information
00104  
// -- Selection DAG lowering information
00105  
//
00106   virtual const TargetInstrInfo         *getInstrInfo() const { return 0; }
00107   virtual const TargetFrameLowering *getFrameLowering() const { return 0; }
00108   virtual const TargetLowering    *getTargetLowering() const { return 0; }
00109   virtual const TargetSelectionDAGInfo *getSelectionDAGInfo() const{ return 0; }
00110   virtual const DataLayout             *getDataLayout() const { return 0; }
00111  
virtual const ScalarTargetTransformInfo*
00112   getScalarTargetTransformInfo() const { return 0; }
00113  
virtual const VectorTargetTransformInfo*
00114   getVectorTargetTransformInfo() const { return 0; }

…......................................

00127  /// getRegisterInfo - If register information is available, return it.  If
00128
 /// not, return null.  This is kept separate from RegInfo until RegInfo has
00129
 /// details of graph coloring register allocation removed from it.
00130
 ///
00131  virtual const TargetRegisterInfo *getRegisterInfo() const { return 0; }
…....................................

00150  /// hasMCRelaxAll - Check whether all machine code instructions should be
00151
 /// relaxed.
00152  bool hasMCRelaxAll() const { return MCRelaxAll; }
00153
00154
 /// setMCRelaxAll - Set whether all machine code instructions should be
00155
 /// relaxed.
00156  void setMCRelaxAll(bool Value) { MCRelaxAll = Value; }
00157
00158
 /// hasMCSaveTempLabels - Check whether temporary labels will be preserved
00159
 /// (i.e., not treated as temporary).
00160  bool hasMCSaveTempLabels() const { return MCSaveTempLabels; }
00161
00162
 /// setMCSaveTempLabels - Set whether temporary labels will be preserved
00163
 /// (i.e., not treated as temporary).
00164  void setMCSaveTempLabels(bool Value) { MCSaveTempLabels = Value; }
00165
00166
 /// hasMCNoExecStack - Check whether an executable stack is not needed.
00167  bool hasMCNoExecStack() const { return MCNoExecStack; }
00168
00169
 /// setMCNoExecStack - Set whether an executabel stack is not needed.
00170  void setMCNoExecStack(bool Value) { MCNoExecStack = Value; }
00171
00172
 /// hasMCUseLoc - Check whether we should use dwarf's .loc directive.
00173  bool hasMCUseLoc() const { return MCUseLoc; }

….....................................

00244  /// addPassesToEmitFile - Add passes to the specified pass manager to get the
00245
 /// specified file emitted.  Typically this will involve several steps of code
00246
 /// generation.  This method should return true if emission of this file type
00247
 /// is not supported, or false on success.
00248  virtual bool addPassesToEmitFile(PassManagerBase &,
00249                                  
 formatted_raw_ostream &,
00250                                  
 CodeGenFileType,
00251                                    
bool /*DisableVerify*/ = true,
00252                                  
 AnalysisID StartAfter = 0,
00253                                  
 AnalysisID StopAfter = 0) {
00254    
return true;
00255   }
00256
00257
 /// addPassesToEmitMachineCode - Add passes to the specified pass manager to
00258
 /// get machine code emitted.  This uses a JITCodeEmitter object to handle
00259
 /// actually outputting the machine code and resolving things like the address
00260
 /// of functions.  This method returns true if machine code emission is
00261
 /// not supported.
00262
 ///
00263  virtual bool addPassesToEmitMachineCode(PassManagerBase &,
00264                                          
 JITCodeEmitter &,
00265                                          
bool /*DisableVerify*/ = true) {
00266    
return true;
00267   }

…...............................

From the above definition we can see the TargetMachine class has the previously mentioned  get**Info virtual methods, some MC status set/get methods and a bunch of addPassesToEmit** methods.  In terms of its non-function members, we note that it has a &TheTarget member of the Target class (the line 00067). Further trace into the Target class and you can find it is defined in the llvm-3.1.src\include\llvm\Support\TargetRegistry.h file.  A code snap from it:

00060  /// Target - Wrapper for Target specific information.
00061
 ///
00062
 /// For registration purposes, this is a POD type so that targets can be
00063
 /// registered without the use of static constructors.
00064
 ///
00065
 /// Targets should implement a single global instance of this class (which
00066
 /// will be zero initialized), and pass that instance to the TargetRegistry as
00067
 /// part of their initialization.
00068  class Target {
00069  
public:

….....................................................

00080     typedef MCInstrInfo *(*MCInstrInfoCtorFnTy)(void);
00081     typedef MCInstrAnalysis *(*MCInstrAnalysisCtorFnTy)(const MCInstrInfo*Info);
00082     typedef MCRegisterInfo *(*MCRegInfoCtorFnTy)(StringRef TT);
00083     typedef MCSubtargetInfo *(*MCSubtargetInfoCtorFnTy)(StringRef TT,
00084                                                        
 StringRef CPU,
00085                                                        
 StringRef Features);
00086     typedef TargetMachine *(*TargetMachineCtorTy)(const Target &T,
00087                                                  
 StringRef TT,
00088                                                  
 StringRef CPU,
00089                                                  
 StringRef Features,
00090                                                  
const TargetOptions &Options,
00091                                                  
 Reloc::Model RM,
00092                                                  
 CodeModel::Model CM,
00093                                                  
 CodeGenOpt::Level OL);
00094     typedef AsmPrinter *(*AsmPrinterCtorTy)(TargetMachine &TM,
00095                                            
 MCStreamer &Streamer);
00096     typedef MCAsmBackend *(*MCAsmBackendCtorTy)(const Target &T,
00097                                                
 StringRef TT,
00098                                                
 StringRef CPU);
00099     typedef MCTargetAsmLexer *(*MCAsmLexerCtorTy)(const Target &T,
00100                                                  
const MCRegisterInfo &MRI,
00101                                                  
const MCAsmInfo &MAI);

…....................................

00124     typedef MCStreamer *(*AsmStreamerCtorTy)(MCContext &Ctx,
00125                                            
 formatted_raw_ostream &OS,
00126                                              
bool isVerboseAsm,
00127                                              
bool useLoc,
00128                                              
bool useCFI,
00129                                              
bool useDwarfDirectory,
00130                                            
 MCInstPrinter *InstPrint,
00131                                            
 MCCodeEmitter *CE,
00132                                            
 MCAsmBackend *TAB,
00133                                              
bool ShowInst);

…...................................

00138    Target *Next;
00139
00140
   /// TripleMatchQualityFn - The target function for rating the match quality
00141
   /// of a triple.
00142  
 TripleMatchQualityFnTy TripleMatchQualityFn;
00143
00144
   /// Name - The target name.
00145    
const char *Name;

….......................................

00179    TargetMachineCtorTy TargetMachineCtorFn;
00180
00181
   /// MCAsmBackendCtorFn - Construction function for this target's
00182
   /// MCAsmBackend, if registered.
00183  
 MCAsmBackendCtorTy MCAsmBackendCtorFn;
00184
00185
   /// MCAsmLexerCtorFn - Construction function for this target's
00186
   /// MCTargetAsmLexer, if registered.
00187  
 MCAsmLexerCtorTy MCAsmLexerCtorFn;

….....................................

00343    TargetMachine *createTargetMachine(StringRef Triple, StringRef CPU,
00344                            
 StringRef Features, const TargetOptions &Options,
00345                            
 Reloc::Model RM = Reloc::Default,
00346                            
 CodeModel::Model CM = CodeModel::Default,
00347                            
 CodeGenOpt::Level OL = CodeGenOpt::Default) const {
00348      
if (!TargetMachineCtorFn)
00349        
return 0;
00350      
return TargetMachineCtorFn(*this, Triple, CPU, Features, Options,
00351                                  RM, CM, OL);
00352     }

….............................................

00658    static void RegisterTargetMachine(Target &T,
00659                                      
 Target::TargetMachineCtorTy Fn) {
00660      
// Ignore duplicate registration.
00661      
if (!T.TargetMachineCtorFn)
00662         T.TargetMachineCtorFn = Fn;
00663     }

shows that it is a wrapper of an actual target machine class with lots of Fn pointers (function pointers)  pointing to methods for target creation,  ASM printing, MC asm backend,  MC streaming, etc. Specifically, there are two important functions: RegisterTargetMachine() and createTargetMachine() , used to register and create a target-specific machine, respectively.  

The RegisterTargetMachine() function just passes a function pointer (Target::TargetMachineCtorTy) argument to its TargetMachineCtorFn member, which stores the constructor function for a target-specific TargetMachine class (e.g., X86_32TargetMachine). In the implementation file (llvm-3.1.src\lib\Target\X86\X86TargetMachine.cpp) of the X86_32TargetMachine class there are a few lines at the very beginning:

00025 extern "C" void LLVMInitializeX86Target() {
00026  
// Register the target.
00027  
 RegisterTargetMachine<X86_32TargetMachine> X(TheX86_32Target);
….//Register another target (X86_64), not relevant to this example
00029 }

to register the X86_32TargetMachine.

Now, whenever the function createTargetMachine() is called on an object of the Target wrapper class, the function pointed by TargetMachineCtorFn, in our example the constructor of the X86_32TargetMachine class, will be invoked.

After discussing the TargetMachine abstract class and its Target wrapper member, now let’s look at

Part 7.2.2 DataLayout Class

The DataLayout class is the only target description class that is not extensible (you cannot derive a new class from it). DataLayout specifies information about how the target lays out memory for structures, the alignment requirements for various data types, the size of pointers in the target, and whether the target is little-endian or big-endian. In the beginning of Part 7.2 we know the TargetMachine class defines various virtual methods named get**Info to access target-specific objects for relevant information. Similar to these methods,  the TargetMachine class also has some get** function members for retrieving other target-dependent information. One of these functions is the DataLayout             *getDataLayout() function. It is obvious that it returns a DataLayout object. So what’s in DataLayout and how to use it?

The members in the DataLayout class are largely related to the size (e.g., size querying functions such as uint64_t getTypeStoreSize(Type *Ty), uint64_t getTypeSizeInBits(Type* Ty) getPointerSize()), alignment setting/getting functions (e.g., setPointerAlignment(), getPointerAlignment(), getPointerPrefAlignment() ),  Endianness checking/setting, etc. Note that this class is designed to be non-inheritable since it uses a non-virtual destructor:

00180   ~DataLayout();  // Not virtual, do not subclass this class

…..// maybe here I should add something about the struct layout..

One of its constructors (there are also copy and default constructors) accepts a string and call a function init() to initialize all the size, alignment, Endianess as well as other members:

00155 void DataLayout::init(StringRef Desc) {
00156  
 initializeDataLayoutPass(*PassRegistry::getPassRegistry());
00157
00158   LayoutMap = 0;
00159   LittleEndian =
false;
00160   StackNaturalAlign = 0;
00161
00162  
// Default alignments
00163   setAlignment(
INTEGER_ALIGN,   1,  1, 1);   // i1
00164   setAlignment(
INTEGER_ALIGN,   1,  1, 8);   // i8
00165   setAlignment(
INTEGER_ALIGN,   2,  2, 16);  // i16
00166   setAlignment(
INTEGER_ALIGN,   4,  4, 32);  // i32
00167   setAlignment(
INTEGER_ALIGN,   4,  8, 64);  // i64
00168   setAlignment(
FLOAT_ALIGN,     2,  2, 16);  // half
00169   setAlignment(
FLOAT_ALIGN,     4,  4, 32);  // float
00170   setAlignment(
FLOAT_ALIGN,     8,  8, 64);  // double
00171   setAlignment(
FLOAT_ALIGN,    16, 16, 128); // ppcf128, quad, ...
00172   setAlignment(
VECTOR_ALIGN,    8,  8, 64);  // v2i32, v1i64, ...
00173   setAlignment(
VECTOR_ALIGN,   16, 16, 128); // v16i8, v8i16, v4i32, ...
00174   setAlignment(
AGGREGATE_ALIGN, 0,  8,  0);  // struct
00175   setPointerAlignment(0, 8, 8, 8);
00176
00177   parseSpecifier(Desc);
00178 }

 

Here are some notes from http://llvm.org/docs/WritingAnLLVMBackend.html related to how to use and initialize a DataLayout object in your specific target implementation:

In addition, the XXXTargetMachine constructor should specify a TargetDescription string that determines the data layout for the target machine, including characteristics such as pointer size, alignment, and endianness. For example, the constructor forSparcTargetMachine contains the following:

SparcTargetMachine::SparcTargetMachine(const Module &M, const std::string &FS)
 
: DataLayout("E-p:32:32-f128:128:128"),
   Subtarget(M, FS), InstrInfo(Subtarget),
   FrameInfo(TargetFrameInfo
::StackGrowsDown, 8, 0) {
}

Hyphens separate portions of the TargetDescription string.

  1. An upper-case “E” in the string indicates a big-endian target data model. A lower-case “e” indicates little-endian.
  2. p:” is followed by pointer information: size, ABI alignment, and preferred alignment. If only two figures follow “p:”, then the first value is pointer size, and the second value is both ABI and preferred alignment.
  3. Then a letter for numeric type alignment: “i”, “f”, “v”, or “a” (corresponding to integer, floating point, vector, or aggregate). “i”, “v”, or “a” are followed by ABI alignment and preferred alignment. “f” is followed by three values: the first indicates the size of a long double, then ABI alignment, and then ABI preferred alignment.

Note that the in the DataLayout("E-p:32:32-f128:128:128") in the SparcTargetMachine initialization list is just one of many examples.  Another example of data layout initialization is demonstrated in the X86_64TargetMachine target:

00057 X86_64TargetMachine::X86_64TargetMachine(const Target &T, StringRef TT,
00058                                        
 StringRef CPU, StringRef FS,
00059                                          
const TargetOptions &Options,
00060                                        
 Reloc::Model RM, CodeModel::Model CM,
00061                                        
 CodeGenOpt::Level OL)
00062   :
 X86TargetMachine(T, TT, CPU, FS, Options, RM, CM, OL, true),
00063     DL(
"e-p:64:64-s:64-f64:64:64-i64:64:64-f80:128:128-f128:128:128-"
00064                
"n8:16:32:64-S128"),
00065     InstrInfo(*this),
00066     TSInfo(*this),
00067     TLInfo(*this),
00068     JITInfo(*this),
00069     STTI(&TLInfo), VTTI(&TLInfo){
00070 }

where DL is a member in X86_64TargetMachine with the type of DataLayout.  Here it should emphasized that only the final specific target machine requires a DataLayout member. In the above example, X86_64TargetMachine inherits the X86TargetMachine class, which does not have a DataLayout  member.

In terms of the inheritance hierarchy of the DataLayout class, please refer to the following figure:

From the above illustration we can conclude that LLVM has a very general definition of the concept “Pass”. Basically every operation that aims to extract/track certain information at a particular granularity (e.g., modules, functions, basic blocks, loops, etc.) is a “Pass”.  In the case of DataLayout the pass refers to the globally (i.e., at the module level) managed data layout information for a concrete target machine.

Part 7.2.3 TargetLowering Class

To understand what TargetLowering class does we first need to know the SelectionDAG. The following notes are selected from the LLVM documentation for a description for the SelectionDAG. Following the description of SelectionDAG is an LLVM official explanation of SelectionDAG legalization, which I think is highly related to the TargetLowering class. Thus I put them together here before jumping into the code of the TargetLowering class.

The SelectionDAG provides an abstraction for code representation in a way that is amenable to instruction selection using automatic techniques (e.g. dynamic-programming based optimal pattern matching selectors). It is also well-suited to other phases of code generation; in particular, instruction scheduling (SelectionDAG’s are very close to scheduling DAGs post-selection). Additionally, the SelectionDAG provides a host representation where a large variety of very-low-level (but target-independent) optimizations may be performed; ones which require extensive information about the instructions efficiently supported by the target.

The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the SDNode class. The primary payload of the SDNode is its operation code (Opcode) that indicates what operation the node performs and the operands to the operation. The various operation node types are described at the top of the include/llvm/CodeGen/SelectionDAGNodes.h file.

…..................

SelectionDAG-based instruction selection consists of the following steps:

  1. Build initial DAG — This stage performs a simple translation from the input LLVM code to an illegal SelectionDAG.
  2. Optimize SelectionDAG — This stage performs simple optimizations on the SelectionDAG to simplify it, and recognize meta instructions (like rotates and div/rem pairs) for targets that support these meta operations. This makes the resultant code more efficient and the select instructions from DAG phase (below) simpler.
  3. Legalize SelectionDAG Types — This stage transforms SelectionDAG nodes to eliminate any types that are unsupported on the target.
  4. Optimize SelectionDAG — The SelectionDAG optimizer is run to clean up redundancies exposed by type legalization.
  5. Legalize SelectionDAG Ops — This stage transforms SelectionDAG nodes to eliminate any operations that are unsupported on the target.
  6. Optimize SelectionDAG — The SelectionDAG optimizer is run to eliminate inefficiencies introduced by operation legalization.
  7. Select instructions from DAG — Finally, the target instruction selector matches the DAG operations to target instructions. This process translates the target-independent input DAG into another DAG of target instructions.
  8. SelectionDAG Scheduling and Formation — The last phase assigns a linear order to the instructions in the target-instruction DAG and emits them into the MachineFunction being compiled. This step uses traditional prepass scheduling techniques.

The initial SelectionDAG is naïvely peephole expanded from the LLVM input by the SelectionDAGBuilder class, which has the following members:

SmallVector< SDValue, 8 >

PendingLoads

const TargetMachine &

TM

const TargetLowering &

TLI

SelectionDAG &

DAG

const DataLayout *

TD

AliasAnalysis *

AA

const TargetLibraryInfo *

LibInfo

std::vector< CaseBlock >

SwitchCases

std::vector< JumpTableBlock >

JTCases

std::vector< BitTestBlock >

BitTestCases

DenseMap< const Constant 

*, unsigned >

ConstantsOut

FunctionLoweringInfo &

FuncInfo

CodeGenOpt::Level 

OptLevel

GCFunctionInfo *

GFI

 

GFI - Garbage collection metadata for the function.

DenseMap<MachineBasicBlock 

*, SmallVector< unsigned, 4 > >

LPadToCallSiteMap

 

LPadToCallSiteMap - Map a landing pad to the call site indexes.

bool 

HasTailCall

LLVMContext *

Context

Among these members, the TargetLowering member TLI provides target-specific hooks to lower calls, returns, varargs and target-specific information, etc. A target implementation tells the legalizer which types are supported (and which register class to use for them) by calling the addRegisterClass method in its TargetLowering constructor. A target implementation tells the legalizer which operations are not supported (and which of the above three actions to take) by calling the setOperationAction method in its TargetLowering constructor.

Among other things, this class indicates:

  1. an initial register class to use for various ValueTypes,
  2. which operations are natively supported by the target machine,
  3. the return type of setcc operations,
  4. the type to use for shift amounts, and
  5. various high-level characteristics, like whether it is profitable to turn division by a constant into a multiplication sequence.

The SelectionDAG Legalize

In the constructor for the XXXTargetLowering class, first use the addRegisterClass method to specify which types are supported and which register classes are associated with them. The code for the register classes are generated by TableGen fromXXXRegisterInfo.td and placed in XXXGenRegisterInfo.h.inc. For example, the implementation of the constructor for the SparcTargetLowering class (in SparcISelLowering.cpp) starts with the following code:

addRegisterClass(MVT::i32, SP::IntRegsRegisterClass);
addRegisterClass(MVT
::f32, SP::FPRegsRegisterClass);
addRegisterClass(MVT
::f64, SP::DFPRegsRegisterClass);

You should examine the node types in the ISD namespace (include/llvm/CodeGen/SelectionDAGNodes.h) and determine which operations the target natively supports. For operations that do not have native support, add a callback to the constructor for theXXXTargetLowering class, so the instruction selection process knows what to do. The TargetLowering class callback methods (declared in llvm/Target/TargetLowering.h) are:

  1. setOperationAction — General operation.
  2. setLoadExtAction — Load with extension.
  3. setTruncStoreAction — Truncating store.
  4. setIndexedLoadAction — Indexed load.
  5. setIndexedStoreAction — Indexed store.
  6. setConvertAction — Type conversion.
  7. setCondCodeAction — Support for a given condition code.
  8. many others....

These callbacks are used to determine that an operation does or does not work with a specified type (or types). And in all cases, the third parameter is a LegalAction type enum value: Promote, Expand, Custom, or Legal. SparcISelLowering.cpp contains examples of all four LegalAction values. For example, the setLoadExtAction() callback is defined as follows:

01157  /// setLoadExtAction - Indicate that the specified load with extension does
01158
 /// not work with the specified type and indicate what to do about it.
01159  void setLoadExtAction(unsigned ExtType, MVT VT,
01160                        
 LegalizeAction Action) {
01161     assert(ExtType <
 ISD::LAST_LOADEXT_TYPE && VT < MVT::LAST_VALUETYPE &&
01162            
"Table isn't big enough!");
01163     LoadExtActions[VT.
SimpleTy][ExtType] = (uint8_t)Action;
01164   }

Another example is setCondCodeAction() callback function:

01201  /// setCondCodeAction - Indicate that the specified condition code is or isn't
01202
 /// supported on the target and indicate what to do about it.
01203  void setCondCodeAction(ISD::CondCode CC, MVT VT,
01204                        
 LegalizeAction Action) {
01205     assert(VT <
 MVT::LAST_VALUETYPE &&
01206            (
unsigned)CC < array_lengthof(CondCodeActions) &&
01207            
"Table isn't big enough!");
01208
   /// The lower 5 bits of the SimpleTy index into Nth 2bit set from the 64bit
01209
   /// value and the upper 27 bits index into the second dimension of the
01210
   /// array to select what 64bit value to use.
01211    CondCodeActions[(
unsigned)CC][VT.SimpleTy >> 5]
01212       &= ~(uint64_t(3UL)  << (VT.
SimpleTy & 0x1F)*2);
01213     CondCodeActions[(
unsigned)CC][VT.SimpleTy >> 5]
01214       |= (uint64_t)Action << (VT.
SimpleTy & 0x1F)*2;
01215   }

Promote

For an operation without native support for a given type, the specified type may be promoted to a larger type that is supported. For example, SPARC does not support a sign-extending load for Boolean values (i1 type), so in SparcISelLowering.cpp the third parameter below, Promote, changes i1 type values to a large type before loading.

setLoadExtAction(ISD::SEXTLOAD, MVT::i1, Promote);

Another example in X86ISelLowering.cpp:

00247   // Promote all UINT_TO_FP to larger SINT_TO_FP's, as X86 doesn't have this
00248  
// operation.
00249  
 setOperationAction(ISD::UINT_TO_FP       , MVT::i1   , Promote);
00250  
 setOperationAction(ISD::UINT_TO_FP       , MVT::i8   , Promote);
00251  
 setOperationAction(ISD::UINT_TO_FP       , MVT::i16  , Promote);
00252
00253  
if (Subtarget->is64Bit()) {
00254    
 setOperationAction(ISD::UINT_TO_FP     , MVT::i32  , Promote);
….................

Expand

For a type without native support, a value may need to be broken down further, rather than promoted. For an operation without native support, a combination of other operations may be used to similar effect. In SPARC, the floating-point sine and cosine trig operations are supported by expansion to other operations, as indicated by the third parameter, Expand, to setOperationAction:

setOperationAction(ISD::FSIN, MVT::f32, Expand);
setOperationAction(ISD
::FCOS, MVT::f32, Expand);

In X86ISelLowering.cpp, there are things like:

00798     setLoadExtAction(ISD::SEXTLOAD, VT, Expand);
00799    
 setLoadExtAction(ISD::ZEXTLOAD, VT, Expand);
00800    
 setLoadExtAction(ISD::EXTLOAD, VT, Expand);

….............

Custom

For some operations, simple type promotion or operation expansion may be insufficient. In some cases, a special intrinsic function must be implemented.

For example, a constant value may require special treatment, or an operation may require spilling and restoring registers in the stack and working with register allocators.

As seen in SparcISelLowering.cpp code below, to perform a type conversion from a floating point value to a signed integer, first thesetOperationAction should be called with Custom as the third parameter:

setOperationAction(ISD::FP_TO_SINT, MVT::i32, Custom);

In the LowerOperation method, for each Custom operation, a case statement should be added to indicate what function to call. In the following code, an FP_TO_SINT opcode will call the LowerFP_TO_SINT method:

SDValue SparcTargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) {
 
switch (Op.getOpcode()) {
 
case ISD::FP_TO_SINT: return LowerFP_TO_SINT(Op, DAG);
 ...
 }
}

Finally, the LowerFP_TO_SINT method is implemented, using an FP register to convert the floating-point value to an integer.

static SDValue LowerFP_TO_SINT(SDValue Op, SelectionDAG &DAG) {
 assert(Op.getValueType()
== MVT::i32);
 Op
= DAG.getNode(SPISD::FTOI, MVT::f32, Op.getOperand(0));
 
return DAG.getNode(ISD::BITCAST, MVT::i32, Op);
}

In X86ISelLowering.cpp, there are things like:

00255     setOperationAction(ISD::UINT_TO_FP     , MVT::i64  , Custom);
00256   }
else if (!TM.Options.UseSoftFloat) {
00257    
// We have an algorithm for SSE2->double, and we turn this into a
00258    
// 64-bit FILD followed by conditional FADD for other targets.
00259    
 setOperationAction(ISD::UINT_TO_FP     , MVT::i64  , Custom);
00260    
// We have an algorithm for SSE2, and we turn this into a 64-bit
00261    
// FILD for other targets.
00262    
 setOperationAction(ISD::UINT_TO_FP     , MVT::i32  , Custom);
00263   }

Legal

The Legal LegalizeAction enum value simply indicates that an operation is natively supported. Legal represents the default condition, so it is rarely used. In SparcISelLowering.cpp, the action for CTPOP (an operation to count the bits set in an integer) is natively supported only for SPARC v9. The following code enables the Expand conversion technique for non-v9 SPARC implementations.

setOperationAction(ISD::CTPOP, MVT::i32, Expand);
...
if (TM.getSubtarget<SparcSubtarget>().isV9())
 setOperationAction(ISD
::CTPOP, MVT::i32, Legal);

Note that these set**Action functions are not virtual and typically do not re-implemented in a target-specific lowering class. These functions are just designed to be used in the constructors of a target-specific lowering class to convey information such as type conversion, constraints between a certain type and an operation, etc, of the target machine.  The source code includes some comments that I think summarize the above methods best:

//===--------------------------------------------------------------------===//
01036  
// TargetLowering Configuration Methods - These methods should be invoked by
01037  
// the derived class constructor to configure this object for the target.
01038  
//

Other than the set**Action functions, there are lots of other bool functions such as:

00156  /// isSelectExpensive - Return true if the select operation is expensive for
00157
 /// this target.
00158  bool isSelectExpensive() const { return SelectIsExpensive; }
00159
00160   virtual bool isSelectSupported(SelectSupportKind kind) const { return true; }

…..................

00181  /// isPow2DivCheap() - Return true if pow2 div is cheaper than a chain of
00182
 /// srl/add/sra.
00183  bool isPow2DivCheap() const { return Pow2DivIsCheap; }
00184
00185
 /// isJumpExpensive() - Return true if Flow Control is an expensive operation
00186
 /// that should be avoided.
00187  bool isJumpExpensive() const { return JumpIsExpensive; }

….................

00443  /// isLoadExtLegal - Return true if the specified load with extension is legal
00444
 /// on this target.
00445  bool isLoadExtLegal(unsigned ExtType, EVT VT) const {
00446    
return VT.isSimple() && getLoadExtAction(ExtType, VT) == Legal;
00447   }

to provide target-specific characteristics including latency of a certain operation, supportness of a certain operation, etc.

Also,corresponding to the set**Action functions, there are get**Action functions to retrieve a LegalizeAction object, which has been specified by the get**Action functions, to handle target-specific scenarios. For example:

00510  /// getCondCodeAction - Return how the condition code should be treated:
00511
 /// either it is legal, needs to be expanded to some other code sequence,
00512
 /// or the target has a custom expander for it.
00513
 LegalizeAction
00514   getCondCodeAction(ISD::CondCode CC, EVT VT) const {
00515     assert((
unsigned)CC < array_lengthof(CondCodeActions) &&
00516            (
unsigned)VT.getSimpleVT().SimpleTy < sizeof(CondCodeActions[0])*4 &&
00517            
"Table isn't big enough!");
00518
   /// The lower 5 bits of the SimpleTy index into Nth 2bit set from the 64bit
00519
   /// value and the upper 27 bits index into the second dimension of the
00520
   /// array to select what 64bit value to use.
00521  
 LegalizeAction Action = (LegalizeAction)
00522       ((CondCodeActions[CC][VT.
getSimpleVT().SimpleTy >> 5]
00523         >> (2*(VT.
getSimpleVT().SimpleTy & 0x1F))) & 3);
00524     assert(Action !=
 Promote && "Can't promote condition code!");
00525    
return Action;
00526   }

…........................

00432  /// getLoadExtAction - Return how this load with extension should be treated:
00433
 /// either it is legal, needs to be promoted to a larger size, needs to be
00434
 /// expanded to some other code sequence, or the target has a custom expander
00435
 /// for it.
00436  LegalizeAction getLoadExtAction(unsigned ExtType, EVT VT) const {
00437     assert(ExtType <
 ISD::LAST_LOADEXT_TYPE &&
00438            VT.
getSimpleVT() < MVT::LAST_VALUETYPE &&
00439            
"Table isn't big enough!");
00440    
return (LegalizeAction)LoadExtActions[VT.getSimpleVT().SimpleTy][ExtType];
00441   }

In additional to all the methods introduced above, The TargetLowering class defines tons of other interfaces for a variety of different purposes such as TargetLowering Optimization (e.g.,bool ShrinkDemandedConstant(SDValue Op, const APInt &Demanded); ,  bool SimplifyDemandedBits(),  SDValue SimplifySetCC(), etc.), Special Lowering methods (e.g., virtual SDValue LowerFormalArguments(), virtual SDValue LowerCall(), virtual void HandleByVal(), virtual bool CanLowerReturn(), virtual SDValue LowerReturn(),virtual bool mayBeEmittedAsTailCall(), etc. - These methods must be implemented by targets so that the SelectionDAGBuilder code knows how to lower these.), Inline Asm Support hooks, Instruction Emitting Hooks (e.g.,virtual MachineBasicBlock *EmitInstrWithCustomInserter

virtual void AdjustInstrPostInstrSelection() ), Addressing mode description hooks (e.g., virtual bool isLegalAddImmediate(), virtual bool isLegalAddressingMode(), etc.) and Runtime Library hooks.

Now we should be familar with what’s inside the TargetLowering class and how they should be defined and used based on a specific target implementation. Now let’s look at a bigger picture: the inheritance hierarchy of the TargetLowering class. The inheritance of the TargetLowering class is relatively simple. It is a base class for other target-specific lowering classes to inherit:

Part 7.2.4 TargetFrameLowering

TargetFrameLowering class defines interfaces to convey stack/frame related information (unsigned getStackAlignment(), virtual const SpillSlot *getCalleeSavedSpillSlots(), StackDirection getStackGrowthDirection() etc. ) and handle stack/frame relevant code generation (e.g., virtual void emitPrologue(), virtual void emitEpilogue(), etc.) for various targets.  Note that to retrieve a list of caller save or callee save registers you need to consult the TargetRegisterInfo class, not this class. 

The souce code of the TargetFrameLowering class is self-explained since it has enough comments to clarify what each interface does.  The source code for this class is not long, thus I just list the entire class definition source code here:

00026 /// Information about stack frame layout on the target.  It holds the direction
00027
/// of stack growth, the known stack alignment on entry to each function, and
00028
/// the offset to the locals area.
00029
///
00030
/// The offset to the local area is the offset from the stack pointer on
00031
/// function entry to the first location where function data (local variables,
00032
/// spill locations) can be stored.
00033 class TargetFrameLowering {
00034
public:
00035   enum StackDirection {
00036     StackGrowsUp,        // Adding to the stack increases the stack address
00037     StackGrowsDown       // Adding to the stack decreases the stack address
00038   };
00039
00040  
// Maps a callee saved register to a stack slot with a fixed offset.
00041   struct SpillSlot {
00042     unsigned Reg;
00043     int Offset; // Offset relative to stack pointer on function entry.
00044   };
00045
private:
00046  
 StackDirection StackDir;
00047  
unsigned StackAlignment;
00048  
unsigned TransientStackAlignment;
00049  
int LocalAreaOffset;
00050  
bool StackRealignable;
00051
public:
00052   TargetFrameLowering(StackDirection D, unsigned StackAl, int LAO,
00053                      
unsigned TransAl = 1, bool StackReal = true)
00054     : StackDir(D), StackAlignment(StackAl), TransientStackAlignment(TransAl),
00055       LocalAreaOffset(LAO), StackRealignable(StackReal) {}
00056
00057  
virtual ~TargetFrameLowering();
00058
00059  
// These methods return information that describes the abstract stack layout
00060  
// of the target machine.
00061
00062
 /// getStackGrowthDirection - Return the direction the stack grows
00063
 ///
00064  StackDirection getStackGrowthDirection() const { return StackDir; }
00065
00066
 /// getStackAlignment - This method returns the number of bytes to which the
00067
 /// stack pointer must be aligned on entry to a function.  Typically, this
00068
 /// is the largest alignment for any data object in the target.
00069
 ///
00070  unsigned getStackAlignment() const { return StackAlignment; }
00071
00072
 /// getTransientStackAlignment - This method returns the number of bytes to
00073
 /// which the stack pointer must be aligned at all times, even between
00074
 /// calls.
00075
 ///
00076  unsigned getTransientStackAlignment() const {
00077    
return TransientStackAlignment;
00078   }
00079
00080
 /// isStackRealignable - This method returns whether the stack can be
00081
 /// realigned.
00082  bool isStackRealignable() const {
00083    
return StackRealignable;
00084   }
00085
00086
 /// getOffsetOfLocalArea - This method returns the offset of the local area
00087
 /// from the stack pointer on entrance to a function.
00088
 ///
00089  int getOffsetOfLocalArea() const { return LocalAreaOffset; }
00090
00091
 /// getCalleeSavedSpillSlots - This method returns a pointer to an array of
00092
 /// pairs, that contains an entry for each callee saved register that must be
00093
 /// spilled to a particular stack location if it is spilled.
00094
 ///
00095
 /// Each entry in this array contains a <register,offset> pair, indicating the
00096
 /// fixed offset from the incoming stack pointer that each register should be
00097
 /// spilled at. If a register is not listed here, the code generator is
00098
 /// allowed to spill it anywhere it chooses.
00099
 ///
00100  
virtual const SpillSlot *
00101   getCalleeSavedSpillSlots(unsigned &NumEntries) const {
00102     NumEntries = 0;
00103    
return 0;
00104   }
00105
00106
 /// targetHandlesStackFrameRounding - Returns true if the target is
00107
 /// responsible for rounding up the stack frame (probably at emitPrologue
00108
 /// time).
00109  virtual bool targetHandlesStackFrameRounding() const {
00110    
return false;
00111   }
00112
00113
 /// emitProlog/emitEpilog - These methods insert prolog and epilog code into
00114
 /// the function.
00115  
virtual void emitPrologue(MachineFunction &MF) const = 0;
00116  
virtual void emitEpilogue(MachineFunction &MF,
00117                            
 MachineBasicBlock &MBB) const = 0;
00118
00119
 /// Adjust the prologue to have the function use segmented stacks. This works
00120
 /// by adding a check even before the "normal" function prologue.
00121  virtual void adjustForSegmentedStacks(MachineFunction &MF) const { }
00122
00123
 /// spillCalleeSavedRegisters - Issues instruction(s) to spill all callee
00124
 /// saved registers and returns true if it isn't possible / profitable to do
00125
 /// so by issuing a series of store instructions via
00126
 /// storeRegToStackSlot(). Returns false otherwise.
00127  virtual bool spillCalleeSavedRegisters(MachineBasicBlock &MBB,
00128                                        
 MachineBasicBlock::iterator MI,
00129                                        
const std::vector<CalleeSavedInfo> &CSI,
00130                                          
const TargetRegisterInfo *TRI) const {
00131    
return false;
00132   }
00133
00134
 /// restoreCalleeSavedRegisters - Issues instruction(s) to restore all callee
00135
 /// saved registers and returns true if it isn't possible / profitable to do
00136
 /// so by issuing a series of load instructions via loadRegToStackSlot().
00137
 /// Returns false otherwise.
00138  virtual bool restoreCalleeSavedRegisters(MachineBasicBlock &MBB,
00139                                          
 MachineBasicBlock::iterator MI,
00140                                        
const std::vector<CalleeSavedInfo> &CSI,
00141                                        
const TargetRegisterInfo *TRI) const {
00142    
return false;
00143   }
00144
00145
 /// hasFP - Return true if the specified function should have a dedicated
00146
 /// frame pointer register. For most targets this is true only if the function
00147
 /// has variable sized allocas or if frame pointer elimination is disabled.
00148  
virtual bool hasFP(const MachineFunction &MF) const = 0;
00149
00150
 /// hasReservedCallFrame - Under normal circumstances, when a frame pointer is
00151
 /// not required, we reserve argument space for call sites in the function
00152
 /// immediately on entry to the current function. This eliminates the need for
00153
 /// add/sub sp brackets around call sites. Returns true if the call frame is
00154
 /// included as part of the stack frame.
00155  virtual bool hasReservedCallFrame(const MachineFunction &MF) const {
00156    
return !hasFP(MF);
00157   }
00158
00159
 /// canSimplifyCallFramePseudos - When possible, it's best to simplify the
00160
 /// call frame pseudo ops before doing frame index elimination. This is
00161
 /// possible only when frame index references between the pseudos won't
00162
 /// need adjusting for the call frame adjustments. Normally, that's true
00163
 /// if the function has a reserved call frame or a frame pointer. Some
00164
 /// targets (Thumb2, for example) may have more complicated criteria,
00165
 /// however, and can override this behavior.
00166  virtual bool canSimplifyCallFramePseudos(const MachineFunction &MF) const {
00167    
return hasReservedCallFrame(MF) || hasFP(MF);
00168   }
00169
00170
 /// getFrameIndexOffset - Returns the displacement from the frame register to
00171
 /// the stack frame of the specified index.
00172  
virtual int getFrameIndexOffset(const MachineFunction &MF, int FI) const;
00173
00174
 /// getFrameIndexReference - This method should return the base register
00175
 /// and offset used to reference a frame index location. The offset is
00176
 /// returned directly, and the base register is returned via FrameReg.
00177  
virtual int getFrameIndexReference(const MachineFunction &MF, int FI,
00178                                      
unsigned &FrameReg) const;
00179
00180
 /// processFunctionBeforeCalleeSavedScan - This method is called immediately
00181
 /// before PrologEpilogInserter scans the physical registers used to determine
00182
 /// what callee saved registers should be spilled. This method is optional.
00183  virtual void processFunctionBeforeCalleeSavedScan(MachineFunction &MF,
00184                                                
 RegScavenger *RS = NULL) const {
00185
00186   }
00187
00188
 /// processFunctionBeforeFrameFinalized - This method is called immediately
00189
 /// before the specified function's frame layout (MF.getFrameInfo()) is
00190
 /// finalized.  Once the frame is finalized, MO_FrameIndex operands are
00191
 /// replaced with direct constants.  This method is optional.
00192
 ///
00193  virtual void processFunctionBeforeFrameFinalized(MachineFunction &MF) const {
00194   }
00195 };

From the above code we can see most of methods in the TargetFrameLowering  class are defined as virtual and thus should be subclassed by a concrete frame lowering class. The following figure illustrates the inheritance between the TargetFrameLowering  class and various concrete target-specific frame lowering subclasses implemented in the LLVM library.   For more details regarding how a target frame lowering subclass re-implements the virtual functions defined in the TargetFrameLowering  class, please refer to the corresponding source file of that target frame lowering subclass.

Part 7.2.5 TargetRegisterInfo Class

The LLVM document offers a brief introduction to the TargetRegisterInfo class:

The TargetRegisterInfo class is used to describe the register file of the target and any interactions between the registers.

Registers are represented in the code generator by unsigned integers. Physical registers (those that actually exist in the target description) are unique small numbers, and virtual registers are generally large. Note that register #0 is reserved as a flag value.

Each register in the processor description has an associated TargetRegisterDesc entry, which provides a textual name for the register (used for assembly output and debugging dumps) and a set of aliases (used to indicate whether one register overlaps with another).

In addition to the per-register description, the TargetRegisterInfo class exposes a set of processor specific register classes (instances of the TargetRegisterClass class). Each register class contains sets of registers that have the same properties (for example, they are all 32-bit integer registers). Each SSA virtual register created by the instruction selector has an associated register class. When the register allocator runs, it replaces virtual registers with a physical register in the set.

The target-specific implementations of these classes is auto-generated from a TableGen description of the register file.

Mapping virtual registers to physical registers

There are two ways to map virtual registers to physical registers (or to memory slots). The first way, that we will call direct mapping, is based on the use of methods of the classes TargetRegisterInfo, and MachineOperand. The second way, that we will call indirect mapping, relies on the VirtRegMap class in order to insert loads and stores sending and getting values to and from memory.

The direct mapping provides more flexibility to the developer of the register allocator; however, it is more error prone, and demands more implementation work. Basically, the programmer will have to specify where load and store instructions should be inserted in the target function being compiled in order to get and store values in memory. To assign a physical register to a virtual register present in a given operand, use MachineOperand::setReg(p_reg). To insert a store instruction, useTargetInstrInfo::storeRegToStackSlot(...), and to insert a load instruction, use TargetInstrInfo::loadRegFromStackSlot.

The indirect mapping shields the application developer from the complexities of inserting load and store instructions. In order to map a virtual register to a physical one, use VirtRegMap::assignVirt2Phys(vreg, preg). In order to map a certain virtual register to memory, use VirtRegMap::assignVirt2StackSlot(vreg). This method will return the stack slot where vreg‘s value will be located. If it is necessary to map another virtual register to the same stack slot, use VirtRegMap::assignVirt2StackSlot(vreg, stack_location). One important point to consider when using the indirect mapping, is that even if a virtual register is mapped to memory, it still needs to be mapped to a physical register. This physical register is the location where the virtual register is supposed to be found before being stored or after being reloaded.

If the indirect strategy is used, after all the virtual registers have been mapped to physical registers or stack slots, it is necessary to use a spiller object to place load and store instructions in the code. Every virtual that has been mapped to a stack slot will be stored to memory after been defined and will be loaded before being used. The implementation of the spiller tries to recycle load/store instructions, avoiding unnecessary instructions. For an example of how to invoke the spiller, seeRegAllocLinearScan::runOnMachineFunction in lib/CodeGen/RegAllocLinearScan.cpp.

Here are some code fragments for the TargetRegisterInfo class definition:

00213 /// TargetRegisterInfo base class - We assume that the target defines a static
00214
/// array of TargetRegisterDesc objects that represent all of the machine
00215
/// registers that the target has.  As such, we simply have to track a pointer
00216
/// to this array so that we can turn register number into a register
00217
/// descriptor.
00218
///
00219 class TargetRegisterInfo : public MCRegisterInfo {
00220
public:
00221   typedef const TargetRegisterClass * const * regclass_iterator;
00222
private:
00223  
const TargetRegisterInfoDesc *InfoDesc;     // Extra desc array for codegen
00224  
const char *const *SubRegIndexNames;        // Names of subreg indexes.
00225  
// Pointer to array of lane masks, one per sub-reg index.
00226  
const unsigned *SubRegIndexLaneMasks;
00227
00228  
 regclass_iterator RegClassBegin, RegClassEnd;   // List of regclasses
00229
00230
protected:
00231  
 TargetRegisterInfo(const TargetRegisterInfoDesc *ID,
00232                    
 regclass_iterator RegClassBegin,
00233                    
 regclass_iterator RegClassEnd,
00234                      
const char *const *SRINames,
00235                      
const unsigned *SRILaneMasks);
00236  
virtual ~TargetRegisterInfo();
00237
public:
00238
00239  
// Register numbers can represent physical registers, virtual registers, and
00240  
// sometimes stack slots. The unsigned values are divided into these ranges:
00241  
//
00242  
//   0           Not a register, can be used as a sentinel.
00243  
//   [1;2^30)    Physical registers assigned by TableGen.
00244  
//   [2^30;2^31) Stack slots. (Rarely used.)
00245  
//   [2^31;2^32) Virtual registers assigned by MachineRegisterInfo.
00246  
//
00247  
// Further sentinels can be allocated from the small negative integers.
00248  
// DenseMapInfo<unsigned> uses -1u and -2u.
00249
00250
 /// isStackSlot - Sometimes it is useful the be able to store a non-negative
00251
 /// frame index in a variable that normally holds a register. isStackSlot()
00252
 /// returns true if Reg is in the range used for stack slots.
00253
 ///
00254
 /// Note that isVirtualRegister() and isPhysicalRegister() cannot handle stack
00255
 /// slots, so if a variable may contains a stack slot, always check
00256
 /// isStackSlot() first.
00257
 ///
00258  static bool isStackSlot(unsigned Reg) {
00259    
return int(Reg) >= (1 << 30);
00260   }
00261
00262
 /// stackSlot2Index - Compute the frame index from a register value
00263
 /// representing a stack slot.
00264  static int stackSlot2Index(unsigned Reg) {
00265     assert(
isStackSlot(Reg) && "Not a stack slot");
00266    
return int(Reg - (1u << 30));
00267   }
00268
00269
 /// index2StackSlot - Convert a non-negative frame index to a stack slot
00270
 /// register value.
00271  static unsigned index2StackSlot(int FI) {
00272     assert(FI >= 0 &&
"Cannot hold a negative frame index.");
00273    
return FI + (1u << 30);
00274   }
00275
00276
 /// isPhysicalRegister - Return true if the specified register number is in
00277
 /// the physical register namespace.
00278  static bool isPhysicalRegister(unsigned Reg) {
00279     assert(!
isStackSlot(Reg) && "Not a register! Check isStackSlot() first.");
00280    
return int(Reg) > 0;
00281   }

…...........................

00365  /// regsOverlap - Returns true if the two registers are equal or alias each
00366
 /// other. The registers may be virtual register.
00367  bool regsOverlap(unsigned regA, unsigned regB) const {
00368    
if (regA == regB) return true;
00369    
if (isVirtualRegister(regA) || isVirtualRegister(regB))
00370      
return false;
00371
00372    
// Regunits are numerically ordered. Find a common unit.
00373    
 MCRegUnitIterator RUA(regA, this);
00374    
 MCRegUnitIterator RUB(regB, this);
00375    
do {
00376      
if (*RUA == *RUB) return true;
00377      
if (*RUA < *RUB) ++RUA;
00378      
else             ++RUB;
00379     }
while (RUA.isValid() && RUB.isValid());
00380    
return false;
00381   }
00382
00383
 /// hasRegUnit - Returns true if Reg contains RegUnit.
00384  bool hasRegUnit(unsigned Reg, unsigned RegUnit) const {
00385    
for (MCRegUnitIterator Units(Reg, this); Units.isValid(); ++Units)
00386      
if (*Units == RegUnit)
00387        
return true;
00388    
return false;
00389   }
00390
00391
 /// isSubRegister - Returns true if regB is a sub-register of regA.
00392
 ///
00393  bool isSubRegister(unsigned regA, unsigned regB) const {
00394    
return isSuperRegister(regB, regA);
00395   }
00396
00397
 /// isSuperRegister - Returns true if regB is a super-register of regA.
00398
 ///
00399  bool isSuperRegister(unsigned RegA, unsigned RegB) const {
00400    
for (MCSuperRegIterator I(RegA, this); I.isValid(); ++I)
00401      
if (*I == RegB)
00402        
return true;
00403    
return false;
00404   }

…............................

00411  virtual const MCPhysReg* getCalleeSavedRegs(const MachineFunction *MF = 0)
00412                                                                      
const = 0;

…............................

00470  /// TableGen will synthesize missing RC sub-classes.
00471  
virtual const TargetRegisterClass *
00472   getSubClassWithSubReg(const TargetRegisterClass *RC, unsigned Idx) const {
00473     assert(Idx == 0 &&
"Target has no sub-registers");
00474    
return RC;
00475   }

…...........................

00527  const TargetRegisterClass*
00528  
 getCommonSuperRegClass(const TargetRegisterClass *RCA, unsigned SubA,
00529                          
const TargetRegisterClass *RCB, unsigned SubB,
00530                          
unsigned &PreA, unsigned &PreB) const;
00531

…...........................

00598  /// Get the weight in units of pressure for this register class.
00599  
virtual const RegClassWeight &getRegClassWeight(
00600    
const TargetRegisterClass *RC) const = 0;
00601
00602
 /// Get the weight in units of pressure for this register unit.
00603  
virtual unsigned getRegUnitWeight(unsigned RegUnit) const = 0;
00604
00605
 /// Get the number of dimensions of register pressure.
00606  
virtual unsigned getNumRegPressureSets() const = 0;
00607
00608
 /// Get the name of this register unit pressure set.
00609  
virtual const char *getRegPressureSetName(unsigned Idx) const = 0;

…..........................

00644  /// avoidWriteAfterWrite - Return true if the register allocator should avoid
00645
 /// writing a register from RC in two consecutive instructions.
00646
 /// This can avoid pipeline stalls on certain architectures.
00647
 /// It does cause increased register pressure, though.
00648  virtual bool avoidWriteAfterWrite(const TargetRegisterClass *RC) const {
00649    
return false;
00650   }
00651
00652
 /// UpdateRegAllocHint - A callback to allow target a chance to update
00653
 /// register allocation hints when a register is "changed" (e.g. coalesced)
00654
 /// to another register. e.g. On ARM, some virtual registers should target
00655
 /// register pairs, if one of pair is coalesced to another register, the
00656
 /// allocation hint of the other half of the pair should be changed to point
00657
 /// to the new register.
00658  virtual void UpdateRegAllocHint(unsigned Reg, unsigned NewReg,
00659                                  
 MachineFunction &MF) const {
00660    
// Do nothing.
00661   }

…......................

00780  virtual unsigned getFrameRegister(const MachineFunction &MF) const = 0;

…......................

The functionalities/purposes of the methods defined in the above code snapshots of the TargetRegisterInfo class can be summarized as follows:

  1. unique or common register properties/attributes (e.g., registers with certain common properties can be grouped into one register class and can be specified using tablegen tool),
  2. interactions among registers (e.g., isSubRegister()),

How does tablegen generate a set of target-specific registers and register classes?  In addition to what’s generated by the tablegen, what other hand code is needed?  Working on it...

The TargetRegisterInfo  class is typically inherited by a target-specific register information class, which may be generated automatically by TableGen.  Take the X86 backend for example.  The files X86GenRegisterInfo.h.inc and X86GenRegisterInfo.inc are automatically generated by the TableGen from X86RegisterInfo.td file (not sure this is the only file that X86GenRegisterInfo.h.inc and X86GenRegisterInfo.inc depend on).  An example of X86GenRegisterInfo.h.inc file can be found at http://legup.eecg.utoronto.ca/doxygen/X86GenRegisterInfo_8h_8inc-source.html and it contains the following code fragment:

00014 struct X86GenRegisterInfo : public TargetRegisterInfo {
00015  
explicit X86GenRegisterInfo(int CallFrameSetupOpcode = -1, int CallFrameDestroyOpcode = -1);
00016  
virtual int getDwarfRegNumFull(unsigned RegNum, unsigned Flavour) const;
00017  
virtual int getDwarfRegNum(unsigned RegNum, bool isEH) const = 0;
00018  
virtual bool needsStackRealignment(const MachineFunction &) const
00019
    { return false; }
00020  
unsigned getSubReg(unsigned RegNo, unsigned Index) const;
00021  
unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const;
00022 };

The file X86GenRegisterInfo.inc looks something like this (example available at http://legup.eecg.utoronto.ca/doxygen/X86GenRegisterInfo_8inc-source.html ):

00012   // CCR Register Class...
00013  
static const unsigned CCR[] = {
00014     X86::EFLAGS,
00015   };
00016
00017  
// CONTROL_REG_32 Register Class...
00018  
static const unsigned CONTROL_REG_32[] = {
00019     X86::ECR0, X86::ECR1, X86::ECR2, X86::ECR3, X86::ECR4, X86::ECR5, X86::ECR6, X86::ECR7,
00020   };
00021
00022  
// CONTROL_REG_64 Register Class...
00023  
static const unsigned CONTROL_REG_64[] = {
00024     X86::RCR0, X86::RCR1, X86::RCR2, X86::RCR3, X86::RCR4, X86::RCR5, X86::RCR6, X86::RCR7, X86::RCR8,
00025   };

…...............................

CCRClass  CCRRegClass;
00326   CONTROL_REG_32Class CONTROL_REG_32RegClass;
00327   CONTROL_REG_64Class CONTROL_REG_64RegClass;
00328   DEBUG_REGClass  DEBUG_REGRegClass;
00329   FR32Class FR32RegClass;
00330   FR64Class FR64RegClass;
00331   GR16Class GR16RegClass;

…..................................

00357   // CCR Sub-register Classes...
00358  
static const TargetRegisterClass* const CCRSubRegClasses[] = {
00359     NULL
00360   };
00361
00362  
// CONTROL_REG_32 Sub-register Classes...
00363  
static const TargetRegisterClass* const CONTROL_REG_32SubRegClasses[] = {
00364     NULL
00365   };

…................................

01345 namespace {
01346  
const TargetRegisterClass* const RegisterClasses[] = {
01347     &X86::CCRRegClass,
01348     &X86::CONTROL_REG_32RegClass,
01349     &X86::CONTROL_REG_64RegClass,
01350     &X86::DEBUG_REGRegClass,
01351     &X86::FR32RegClass,
01352     &X86::FR64RegClass,
01353     &X86::GR16RegClass,
01354     &X86::GR16_ABCDRegClass,

…..........................

04089 unsigned X86GenRegisterInfo::getSubReg(unsigned RegNo, unsigned Index) const {
04090  
switch (RegNo) {
04091  
default:
04092    
return 0;
04093  
case X86::R11D:
04094    
switch (Index) {
04095    
default: return 0;
04096    
case 1: return X86::R11B;
04097    
case 3: return X86::R11W;
04098     };
04099    
break;
04100  
case X86::AX:
04101    
switch (Index) {
04102    
default: return 0;
04103    
case 1: return X86::AL;
04104    
case 2: return X86::AH;
04105     };
04106    
break;

The full X86GenRegisterInfo.inc file is very long and contains a large majority of relevant X86 register information.

We should note that the automatically generated files and classes do not provide all register-relevant functionalities and information for a target-specific backend (there are some virtual functions defined in the TargetRegisterInfo class not implemented in the automatically generated class).  Thus we need to manually implement the rest of the functions to retrieve certain register information, for example getCalleeSavedRegs() and getFrameRegister(), etc.

For X86,  the X86RegisterInfo.cpp and X86RegisterInfo.h defines a class named X86RegisterInfo, which inherits the X86GenRegisterInfo class:

00027 class X86RegisterInfo : public X86GenRegisterInfo {
00028
public:
00029   X86TargetMachine &TM;
00030   const TargetInstrInfo &TII;
00032
private:
00033
 /// Is64Bit - Is the target 64-bits.
00034
 ///
00035  
bool Is64Bit;
00036
00037
 /// IsWin64 - Is the target on of win64 flavours
00038
 ///
00039  
bool IsWin64;
00041
 /// SlotSize - Stack slot size in bytes.
00043  
unsigned SlotSize;
00045
 /// StackPtr - X86 physical register used as stack ptr.
00047  
unsigned StackPtr;
00049
 /// FramePtr - X86 physical register used as frame ptr.
00051  
unsigned FramePtr;
00053
 /// BasePtr - X86 physical register used as a base ptr in complex stack
00054
 /// frames. I.e., when we need a 3rd base, not just SP and FP, due to
00055
 /// variable size stack objects.
00056  
unsigned BasePtr;
00058
public:
00059  
 X86RegisterInfo(X86TargetMachine &tm, const TargetInstrInfo &tii);
00061  
// FIXME: This should be tablegen'd like getDwarfRegNum is
00062  
int getSEHRegNum(unsigned i) const;
00064
 /// getCompactUnwindRegNum - This function maps the register to the number for
00065
 /// compact unwind encoding. Return -1 if the register isn't valid.
00066  
int getCompactUnwindRegNum(unsigned RegNum, bool isEH) const;
00068
 /// Code Generation virtual methods...
00070  
virtual bool trackLivenessAfterRegAlloc(const MachineFunction &MF) const;
00072
 /// getMatchingSuperRegClass - Return a subclass of the specified register
00073
 /// class A so that each register in it has a sub-register of the
00074
 /// specified sub-register index which is in the specified register class B.
00075  
virtual const TargetRegisterClass *
00076  
 getMatchingSuperRegClass(const TargetRegisterClass *A,
00077                            
const TargetRegisterClass *B, unsigned Idx) const;
00079  
virtual const TargetRegisterClass *
00080  
 getSubClassWithSubReg(const TargetRegisterClass *RC, unsigned Idx) const;
00082  
const TargetRegisterClass*
00083  
 getLargestLegalSuperClass(const TargetRegisterClass *RC) const;
00085
 /// getPointerRegClass - Returns a TargetRegisterClass used for pointer
00086
 /// values.
00087  
const TargetRegisterClass *
00088  
 getPointerRegClass(const MachineFunction &MF, unsigned Kind = 0) const;
00090
 /// getCrossCopyRegClass - Returns a legal register class to copy a register
00091
 /// in the specified class to or from. Returns NULL if it is possible to copy
00092
 /// between a two registers of the specified class.
00093  
const TargetRegisterClass *
00094  
 getCrossCopyRegClass(const TargetRegisterClass *RC) const;
00096  
unsigned getRegPressureLimit(const TargetRegisterClass *RC,
00097                              
 MachineFunction &MF) const;
00099
 /// getCalleeSavedRegs - Return a null-terminated list of all of the
00100
 /// callee-save registers on this target.
00101  
const uint16_t *getCalleeSavedRegs(const MachineFunction* MF = 0) const;
00102  
const uint32_t *getCallPreservedMask(CallingConv::ID) const;
00103  
const uint32_t *getNoPreservedMask() const;
00109
 BitVector getReservedRegs(const MachineFunction &MF) const;
00111  
bool hasBasePointer(const MachineFunction &MF) const;
00113  
bool canRealignStack(const MachineFunction &MF) const;
00115  
bool needsStackRealignment(const MachineFunction &MF) const;
00117  
bool hasReservedSpillSlot(const MachineFunction &MF, unsigned Reg,
00118                            
int &FrameIdx) const;
00120  
void eliminateCallFramePseudoInstr(MachineFunction &MF,
00121                                    
 MachineBasicBlock &MBB,
00122                                    
 MachineBasicBlock::iterator MI) const;
00123
00124  
void eliminateFrameIndex(MachineBasicBlock::iterator MI,
00125                            
int SPAdj, RegScavenger *RS = NULL) const;
00127  
// Debug information queries.
00128  
unsigned getFrameRegister(const MachineFunction &MF) const;
00129   unsigned getStackRegister() const { return StackPtr; }
00130   unsigned getBaseRegister() const { return BasePtr; }
00131  
// FIXME: Move to FrameInfok
00132   unsigned getSlotSize() const { return SlotSize; }
00134  
// Exception handling queries.
00135  
unsigned getEHExceptionRegister() const;
00136  
unsigned getEHHandlerRegister() const;
00137 };

From the above discussion we can see that the inheritance graph for the register relevant classes has the following structure (due to the fact that **GenRegisterInfo class is automatically generated by TableGen, the inheritance graph in the LLVM document does not include target-specific register information classes.   ** represents a target name):

Part 7.2.6 TargetInstrInfo Class

This subsection starts by high-level descriptions from the LLVM document regarding an overall summary of the TargetInstrInfo class,  basic steps involved for providing target-specific instruction information and how to implement/use a concrete subclass of TargetInstrInfo. All these topics are highly related to the TargetInstrInfo class:

The TargetInstrInfo class

The TargetInstrInfo class is used to describe the machine instructions supported by the target. It is essentially an array of TargetInstrDescriptor objects, each of which describes one instruction the target supports. Descriptors define things like the mnemonic for the opcode, the number of operands, the list of implicit register uses and defs, whether the instruction has certain target-independent properties (accesses memory, is commutable, etc), and holds any target-specific flags.

Providing Target-specific Instruction Information

  1. Describe the instruction set of the target. Use TableGen to generate code for target-specific instructions from target-specific versions of TargetInstrFormats.td and TargetInstrInfo.td. You should write additional code for a subclass of the TargetInstrInfo class to represent machine instructions supported by the target machine.
  2. Describe the selection and conversion of the LLVM IR from a Directed Acyclic Graph (DAG) representation of instructions to native target-specific instructions. Use TableGen to generate code that matches patterns and selects instructions based on additional information in a target-specific version of TargetInstrInfo.td. Write code for XXXISelDAGToDAG.cpp, where XXXidentifies the specific target, to perform pattern matching and DAG-to-DAG instruction selection.

Implement a subclass of TargetInstrInfo

The final step is to hand code portions of XXXInstrInfo, which implements the interface described in TargetInstrInfo.h (see The TargetInstrInfo class). These functions return 0 or a Boolean or they assert, unless overridden. Here’s a list of functions that are overridden for the SPARC implementation in SparcInstrInfo.cpp:

  1. isLoadFromStackSlot — If the specified machine instruction is a direct load from a stack slot, return the register number of the destination and the FrameIndex of the stack slot.
  2. isStoreToStackSlot — If the specified machine instruction is a direct store to a stack slot, return the register number of the destination and the FrameIndex of the stack slot.
  3. copyPhysReg — Copy values between a pair of physical registers.
  4. storeRegToStackSlot — Store a register value to a stack slot.
  5. loadRegFromStackSlot — Load a register value from a stack slot.
  6. storeRegToAddr — Store a register value to memory.
  7. loadRegFromAddr — Load a register value from memory.
  8. foldMemoryOperand — Attempt to combine instructions of any load or store instruction for the specified operand(s).

Example Uses

TargetInstrInfo::get(opcode)::ImplicitDefs, where opcode is the opcode of the target instruction, can be used to check which registers are implicitly defined by an instruction.

To insert a store instruction, use TargetInstrInfo::storeRegToStackSlot(...), and to insert a load instruction, use TargetInstrInfo::loadRegFromStackSlot.

After going through the above official documents we should have gained a high-level understanding of the TargetInstrInfo class. Now let’s move on to its inheritance and source code study.

The inheritance graph of the TargetInstrInfo class is shown as follows (note that the following the figure does not show the entire inheritance due to the same reason mentioned in the end of part 7.2.5.  For example, a target-specific instruction class X86InstrInfo inherits X86GenInstrInfo, which is an automatically generated class that is a subclass of the TargetInstrInfo class. The full inheritance structure should have 4 hierarchies and look like the one in the end of part 7.2.5)

The MCInstrInfo class is simple and just defines the interface for describing machine instruction set. The source code of it (this class only has a header file, no cpp file) is short:

00026 class MCInstrInfo {
00027  
const MCInstrDesc *Desc;          // Raw array to allow static init'n
00028  
const unsigned *InstrNameIndices; // Array for name indices in InstrNameData
00029  
const char *InstrNameData;        // Instruction name string pool
00030  
unsigned NumOpcodes;              // Number of entries in the desc array
00031
00032
public:
00033
 /// InitMCInstrInfo - Initialize MCInstrInfo, called by TableGen
00034
 /// auto-generated routines. *DO NOT USE*.
00035  void InitMCInstrInfo(const MCInstrDesc *D, const unsigned *NI, const char *ND,
00036                        
unsigned NO) {
00037     Desc = D;
00038     InstrNameIndices = NI;
00039     InstrNameData = ND;
00040     NumOpcodes = NO;
00041   }
00042
00043   unsigned getNumOpcodes() const { return NumOpcodes; }
00044
00045
 /// get - Return the machine instruction descriptor that corresponds to the
00046
 /// specified instruction opcode.
00047
 ///
00048  const MCInstrDesc &get(unsigned Opcode) const {
00049     assert(Opcode < NumOpcodes &&
"Invalid opcode!");
00050    
return Desc[Opcode];
00051   }
00052
00053
 /// getName - Returns the name for the instructions with the given opcode.
00054  const char *getName(unsigned Opcode) const {
00055     assert(Opcode < NumOpcodes &&
"Invalid opcode!");
00056    
return &InstrNameData[InstrNameIndices[Opcode]];
00057   }
00058 };

…..................................

00368  bool isCommutable() const {
00369    
return Flags & (1 << MCID::Commutable);
00370   }

….............................

00386  bool isConvertibleTo3Addr() const {
00387    
return Flags & (1 << MCID::ConvertibleTo3Addr);
00388   }

…..........................

The most important member defined in the MCInstrInfo class is const MCInstrDesc *Desc;.  MCInstrDesc class captures information about a particular instruction (or instruction class?) such as instruction characteristics, side effects, register uses, etc. Here is part of the code in the definition of MCInstrDesc:

00134 class MCInstrDesc {
00135
public:
00136   unsigned short  Opcode;        // The opcode number
00137   unsigned short  NumOperands;   // Num of args (may be more if variable_ops)
00138   unsigned short  NumDefs;       // Num of args that are definitions
00139   unsigned short  SchedClass;    // enum identifying instr sched class
00140   unsigned short  Size;          // Number of bytes in encoding.
00141   unsigned        Flags;         // Flags identifying machine instr class
00142   uint64_t        TSFlags;       // Target Specific Flag values
00143   const uint16_t *ImplicitUses;  // Registers implicitly read by this instr
00144   const uint16_t *ImplicitDefs;  // Registers implicitly defined by this instr
00145   const MCOperandInfo *OpInfo;   // 'NumOperands' entries about operands

…........................

00147  /// getOperandConstraint - Returns the value of the specific constraint if
00148
 /// it is set. Returns -1 if it is not set.
00149  int getOperandConstraint(unsigned OpNum,
00150                          
 MCOI::OperandConstraint Constraint) const {
00151    
if (OpNum < NumOperands &&
00152         (
OpInfo[OpNum].Constraints & (1 << Constraint))) {
00153      
unsigned Pos = 16 + Constraint * 4;
00154      
return (int)(OpInfo[OpNum].Constraints >> Pos) & 0xf;
00155     }
00156    
return -1;
00157   }

…..............................

00164  /// getNumOperands - Return the number of declared MachineOperands for this
00165
 /// MachineInstruction.  Note that variadic (isVariadic() returns true)
00166
 /// instructions may have additional operands at the end of the list, and note
00167
 /// that the machine instruction may include implicit register def/uses as
00168
 /// well.
00169  unsigned getNumOperands() const {
00170    
return NumOperands;
00171   }

…..................

00189  bool isVariadic() const {
00190    
return Flags & (1 << MCID::Variadic);
00191   }

….................

00206   bool isReturn() const {
00207    
return Flags & (1 << MCID::Return);
00208   }

…..................

00210   bool isCall() const {
00211    
return Flags & (1 << MCID::Call);
00212   }

…..................

00235  bool isBranch() const {
00236    
return Flags & (1 << MCID::Branch);
00237   }

…..................

00265  bool isPredicable() const {
00266    
return Flags & (1 << MCID::Predicable);
00267   }
00268
00269
 /// isCompare - Return true if this instruction is a comparison.
00270  bool isCompare() const {
00271    
return Flags & (1 << MCID::Compare);
00272   }
00273
00274
 /// isMoveImmediate - Return true if this instruction is a move immediate
00275
 /// (including conditional moves) instruction.
00276  bool isMoveImmediate() const {
00277    
return Flags & (1 << MCID::MoveImm);
00278   }

…...............

00317   //===--------------------------------------------------------------------===//
00318  
// Side Effect Analysis
00319  
//===--------------------------------------------------------------------===//
00320
00321
 /// mayLoad - Return true if this instruction could possibly read memory.
00322
 /// Instructions with this flag set are not necessarily simple load
00323
 /// instructions, they may load a value and modify it, for example.
00324  bool mayLoad() const {
00325    
return Flags & (1 << MCID::MayLoad);
00326   }
00327
00328
00329
 /// mayStore - Return true if this instruction could possibly modify memory.
00330
 /// Instructions with this flag set are not necessarily simple store
00331
 /// instructions, they may store a modified value based on their operands, or
00332
 /// may not actually modify anything, for example.
00333  bool mayStore() const {
00334    
return Flags & (1 << MCID::MayStore);
00335   }

…......................

00480  /// This method returns null if the instruction has no implicit defs.
00481  const uint16_t *getImplicitDefs() const {
00482    
return ImplicitDefs;
00483   }

From the above code we can see the MCInstrInfo base class and its MCInstrDesc member just provide methods to retrieve some basic information about the instruction set of a particular target. In addition to the inherited MCInstrInfo base class members, TargetInstrInfo class defines methods (mostly virtual) to get some advanced instruction-related features and expose some optimization opportunities:

00047 class TargetInstrInfo : public MCInstrInfo {
00048  
 TargetInstrInfo(const TargetInstrInfo &) LLVM_DELETED_FUNCTION;
00049  
void operator=(const TargetInstrInfo &) LLVM_DELETED_FUNCTION;
00050
public:
00051   TargetInstrInfo(int CFSetupOpcode = -1, int CFDestroyOpcode = -1)
00052     : CallFrameSetupOpcode(CFSetupOpcode),
00053       CallFrameDestroyOpcode(CFDestroyOpcode) {
00054   }

…....................

00083  virtual bool isReallyTriviallyReMaterializable(const MachineInstr *MI,
00084                                                
 AliasAnalysis *AA) const {
00085    
return false;
00086   }

…...................

00104  int getCallFrameSetupOpcode() const { return CallFrameSetupOpcode; }
00105   int getCallFrameDestroyOpcode() const { return CallFrameDestroyOpcode; }

…...................

00119  /// isLoadFromStackSlot - If the specified machine instruction is a direct
00120
 /// load from a stack slot, return the virtual or physical register number of
00121
 /// the destination along with the FrameIndex of the loaded stack slot.  If
00122
 /// not, return 0.  This predicate must return 0 if the instruction has
00123
 /// any side effects other than loading from the stack slot.
00124  virtual unsigned isLoadFromStackSlot(const MachineInstr *MI,
00125                                        
int &FrameIndex) const {
00126    
return 0;
00127   }

…......................

00228  /// produceSameValue - Return true if two machine instructions would produce
00229
 /// identical values. By default, this is only true when the two instructions
00230
 /// are deemed identical except for defs. If this function is called when the
00231
 /// IR is still in SSA form, the caller can pass the MachineRegisterInfo for
00232
 /// aggressive checks.
00233  
virtual bool produceSameValue(const MachineInstr *MI0,
00234                                
const MachineInstr *MI1,
00235                                
const MachineRegisterInfo *MRI = 0) const;

….......................

00262  virtual bool AnalyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
00263                            
 MachineBasicBlock *&FBB,
00264                            
 SmallVectorImpl<MachineOperand> &Cond,
00265                              
bool AllowModify = false) const {
00266    
return true;
00267   }
00268
00269
 /// RemoveBranch - Remove the branching code at the end of the specific MBB.
00270
 /// This is only invoked in cases where AnalyzeBranch returns success. It
00271
 /// returns the number of instructions that were removed.
00272  virtual unsigned RemoveBranch(MachineBasicBlock &MBB) const {
00273    
 llvm_unreachable("Target didn't implement TargetInstrInfo::RemoveBranch!");
00274   }

…...........................

00531  MachineInstr* foldMemoryOperand(MachineBasicBlock::iterator MI,
00532                                  
const SmallVectorImpl<unsigned> &Ops,
00533                                  
int FrameIndex) const;

…..........................

00601  virtual bool areLoadsFromSameBasePtr(SDNode *Load1, SDNode *Load2,
00602                                     int64_t &Offset1, int64_t &Offset2)
 const {
00603    
return false;
00604   }

…..........................

00827  virtual unsigned getInstrLatency(const InstrItineraryData *ItinData,
00828                                    
const MachineInstr *MI,
00829                                    
unsigned *PredCost = 0) const;

…..........................

Working on it for a description of the relationship between what’s generated by the tablegen tool and the TargetInstrInfo class. (This can be added after I work on implementing the GPU divergance idea using LLVM)  For now just put official document here:

TableGen generates code for instruction selection using the following target description input files:

  1. XXXInstrInfo.td — Contains definitions of instructions in a target-specific instruction set, generates XXXGenDAGISel.inc, which is included in XXXISelDAGToDAG.cpp.
  2. XXXCallingConv.td — Contains the calling and return value conventions for the target architecture, and it generatesXXXGenCallingConv.inc, which is included in XXXISelLowering.cpp.

TableGen uses the following target description (.td) input files to generate much of the code for instruction definition:

  1. Target.td — Where the Instruction, Operand, InstrInfo, and other fundamental classes are defined.
  2. TargetSelectionDAG.td — Used by SelectionDAG instruction selection generators, contains SDTC* classes (selection DAG type constraint), definitions of SelectionDAG nodes (such as imm, cond, bb, add, fadd, sub), and pattern support (Pattern, Pat, PatFrag,PatLeaf, ComplexPattern.
  3. XXXInstrFormats.td — Patterns for definitions of target-specific instructions.
  4. XXXInstrInfo.td — Target-specific definitions of instruction templates, condition codes, and instructions of an instruction set. For architecture modifications, a different file name may be used. For example, for Pentium with SSE instruction, this file is X86InstrSSE.td, and for Pentium with MMX, this file is X86InstrMMX.td.

There is also a target-specific XXX.td file, where XXX is the name of the target. The XXX.td file includes the other .td input files, but its contents are only directly important for subtargets.

You should describe a concrete target-specific class XXXInstrInfo that represents machine instructions supported by a target machine. XXXInstrInfo contains an array of XXXInstrDescriptor objects, each of which describes one instruction. An instruction descriptor defines:

  1. Opcode mnemonic
  2. Number of operands
  3. List of implicit register definitions and uses
  4. Target-independent properties (such as memory access, is commutable)
  5. Target-specific flags

Part 7.2.7 TargetFrameInfo Class

Part 7.3  Machine code representation

Target independent machine code representation includes the BuildMI function located in the include/llvm/CodeGen/MachineInstrBuilder.h file, MachineFunction , MachineBasicBlock , and MachineInstr classes (defined in include/llvm/CodeGen). This representation is completely target agnostic, representing instructions in their most abstract form: an opcode and a series of operands. This representation is designed to support both an SSA representation for machine code, as well as a register allocated, non-SSA form.

Part 7.3.1 MachineFunction Class

A high level description in the LLVM documentation says that the MachineFunction class contains a list of machine basic blocks ( MachineBasicBlock instances). It corresponds one-to-one with the LLVM function input to the instruction selector. In addition to a list of basic blocks, the MachineFunction contains a a MachineConstantPool, a MachineFrameInfo, a MachineFunctionInfo, and aMachineRegisterInfo. MachineFunction  class has the following interface (see include/llvm/CodeGen/MachineFunction.h):

00074 class MachineFunction {
00075  
const Function *Fn;
00076  
const TargetMachine &Target;
00077  
 MCContext &Ctx;
00078  
 MachineModuleInfo &MMI;
00079  
 GCModuleInfo *GMI;
00080  
00081  
// RegInfo - Information about each register in use in the function.
00082  
 MachineRegisterInfo *RegInfo;
00083
00084  
// Used to keep track of target-specific per-machine function information for
00085  
// the target implementation.
00086  
 MachineFunctionInfo *MFInfo;
00087
00088  
// Keep track of objects allocated on the stack.
00089  
 MachineFrameInfo *FrameInfo;
00090
00091  
// Keep track of constants which are spilled to memory
00092  
 MachineConstantPool *ConstantPool;
00093  
00094  
// Keep track of jump tables for switch instructions
00095  
 MachineJumpTableInfo *JumpTableInfo;

….....................................

00111   // List of machine basic blocks in function
00112  
typedef ilist<MachineBasicBlock> BasicBlockListType;
00113  
 BasicBlockListType BasicBlocks;

….....................................

00142  /// getFunction - Return the LLVM function that this machine code represents
00143
 ///
00144  const Function *getFunction() const { return Fn; }

//Lots of other get** functions to retrieve various members of the MachineFunction class.

…....................................

00267  void viewCFG() const;

00294   //===--------------------------------------------------------------------===//
00295  
// BasicBlock accessor functions:

00307   unsigned                  size() const { return (unsigned)BasicBlocks.size();}
00308   bool                     empty() const { return BasicBlocks.empty(); }
00309   const MachineBasicBlock &front() const { return BasicBlocks.front(); }
00310         MachineBasicBlock &front()       { return BasicBlocks.front(); }
00311   const MachineBasicBlock & back() const { return BasicBlocks.back(); }
00312         MachineBasicBlock & back()       { return BasicBlocks.back(); }
00313
00314   void push_back (MachineBasicBlock *MBB) { BasicBlocks.push_back (MBB); }
00315   void push_front(MachineBasicBlock *MBB) { BasicBlocks.push_front(MBB); }
00316   void insert(iterator MBBI, MachineBasicBlock *MBB) {
00317     BasicBlocks.
insert(MBBI, MBB);
00318   }

….....................................

00333   //===--------------------------------------------------------------------===//
00334  
// Internal functions used to automatically number MachineBasicBlocks
00335  
//
00336
00337
 /// getNextMBBNumber - Returns the next unique number to be assigned
00338
 /// to a MachineBasicBlock in this MachineFunction.
00339
 ///
00340  unsigned addToMBBNumbering(MachineBasicBlock *MBB) {
00341     MBBNumbering.push_back(MBB);
00342    
return (unsigned)MBBNumbering.size()-1;
00343   }
00344
00345
 /// removeFromMBBNumbering - Remove the specific machine basic block from our
00346
 /// tracker, this is only really to be used by the MachineBasicBlock
00347
 /// implementation.
00348  void removeFromMBBNumbering(unsigned N) {
00349     assert(N < MBBNumbering.size() &&
"Illegal basic block #");
00350     MBBNumbering[N] = 0;
00351   }
00352
00353
 /// CreateMachineInstr - Allocate a new MachineInstr. Use this instead
00354
 /// of `new MachineInstr'.
00355
 ///
00356
 MachineInstr *CreateMachineInstr(const MCInstrDesc &MCID,
00357                                  
 DebugLoc DL,
00358                                    
bool NoImp = false);

From the above code we can see that MachineFunction primarily contains a list of MachineBasicBlock objects (00112   typedef ilist<MachineBasicBlock> BasicBlockListType;
00113  
 BasicBlockListType BasicBlocks;) and defines various methods for retrieving the information of the machine function and manipulating the objects in the BasicBlocks member. . A very important point to note is that the MachineFunction class maintains the control flow graph (CFG) of all basic blocks in a function. Control flow information in CFG is crucial for many optimizations and analyses (e.g., live variable analysis discussed in part 7.5.6). So it is important to know how the MachineFunction objects and the corresponding CFGs are constructed. For selection DAG and machine function construction details please refer to <Notes on LLVM 5 (SelectionDAG)>. For CFG construction please refer to the clang front end source code (Working on a section in Notes on LLVM 1 to explain how CFG and IR are generated?).

Part 7.3.2 MachineBasicBlock Class

The MachineBasicBlock class contains a list of machine instructions ( MachineInstr instances). It roughly corresponds to the LLVM code input to the instruction selector, but there can be a one-to-many mapping (i.e. one LLVM basic block can map to multiple machine basic blocks). The MachineBasicBlock class has a “getBasicBlock” method, which returns the LLVM basic block that it comes from. MachineBasicBlock has the following interface:

00062 class MachineBasicBlock : public ilist_node<MachineBasicBlock> {
00063  
typedef ilist<MachineInstr> Instructions;
00064  
 Instructions Insts;
00065  
const BasicBlock *BB;  // LLVM Basic Block
00066  
int Number;
00067  
 MachineFunction *xParent;
00068
00069
 /// Predecessors/Successors - Keep track of the predecessor / successor
00070
 /// basicblocks.
00071  std::vector<MachineBasicBlock *> Predecessors;
00072   std::vector<MachineBasicBlock *> Successors;

…...........................

00082  /// LiveIns - Keep track of the physical registers that are livein of
00083
 /// the basicblock.
00084  std::vector<unsigned> LiveIns;

…..................................

00114  const BasicBlock *getBasicBlock() const { return BB; }

…...................................

00124  /// hasAddressTaken - Test whether this block is potentially the target
00125
 /// of an indirect branch.
00126  bool hasAddressTaken() const { return AddressTaken; }
00127
00128
 /// setHasAddressTaken - Set this block to reflect that it potentially
00129
 /// is the target of an indirect branch.
00130  void setHasAddressTaken() { AddressTaken = true; }
00131
00132
 /// getParent - Return the MachineFunction containing this basic block.
00133
 ///
00134  const MachineFunction *getParent() const { return xParent; }

…...............................

00335  /// moveBefore/moveAfter - move 'this' block before or after the specified
00336
 /// block.  This only moves the block, it does not modify the CFG or adjust
00337
 /// potential fall-throughs at the end of the block.
00338  
void moveBefore(MachineBasicBlock *NewAfter);
00339  
void moveAfter(MachineBasicBlock *NewBefore);

….............................

00356  void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0);
00357
00358
 /// removeSuccessor - Remove successor from the successors list of this
00359
 /// MachineBasicBlock. The Predecessors list of succ is automatically updated.
00360
 ///
00361  
void removeSuccessor(MachineBasicBlock *succ);

…..............................

00410  iterator getFirstNonPHI();

…..................................

00432  /// SplitCriticalEdge - Split the critical edge from this block to the
00433
 /// given successor block, and return the newly created block, or null
00434
 /// if splitting is not possible.
00435
 ///
00436
 /// This function updates LiveVariables, MachineDominatorTree, and
00437
 /// MachineLoopInfo, as applicable.
00438
 MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass *P);
00439
00440   void pop_front() { Insts.pop_front(); }
00441   void pop_back() { Insts.pop_back(); }
00442   void push_back(MachineInstr *MI) { Insts.push_back(MI); }

….........................................

00464
00465
 /// Insert MI into the instruction list after I.
00466  iterator insertAfter(iterator I, MachineInstr *MI) {
00467     assert(!MI->
isBundledWithPred() && !MI->isBundledWithSucc() &&
00468            
"Cannot insert instruction with bundle flags");
00469    
return Insts.insertAfter(I.getInstrIterator(), MI);
00470   }

00511  MachineInstr *remove(MachineInstr *I) {
00512     assert(
!I->isBundled() && "Cannot remove bundled instructions");
00513    
return Insts.remove(I);
00514   }

As what we did when studying code for many other classes, we listed above several representative functions of different categories from the interface definition of the MachineBasicBlock class. As can be obviously seen, MachineBasicBlock keeps a list of machine instructions (00063   typedef ilist<MachineInstr> Instructions; 00064   Instructions Insts;) and the original LLVM BB (basic block). It also provides methods of various sorts including BB information querying (e.g.,getBasicBlock(),setHasAddressTaken()), BB-level manipulation (e.g.,moveBefore(),moveAfter(),addSuccessor()), instruction-level manipulation (e.g.,push_back(), insertAfter()) , etc.

Part 7.3.3 MachineInstr Class

Regarding the MachineInstr class, the LLVM documentation has the following description:

“Target machine instructions are represented as instances of the MachineInstr class. This class is an extremely abstract way of representing machine instructions. In particular, it only keeps track of an opcode number and a set of operands.

The opcode number is a simple unsigned integer that only has meaning to a specific backend. All of the instructions for a target should be defined in the *InstrInfo.tdfile for the target. The opcode enum values are auto-generated from this description. The MachineInstr class does not have any information about how to interpret the instruction (i.e., what the semantics of the instruction are); for that you must refer to the TargetInstrInfo class.

The operands of a machine instruction can be of several different types: a register reference, a constant integer, a basic block reference, etc. In addition, a machine operand should be marked as a def or a use of the value (though only registers are allowed to be defs).

By convention, the LLVM code generator orders instruction operands so that all register definitions come before the register uses, even on architectures that are normally printed in other orders. For example, the SPARC add instruction: “add %i1, %i2, %i3” adds the “%i1”, and “%i2” registers and stores the result into the “%i3” register. In the LLVM code generator, the operands should be stored as “%i3, %i1, %i2”: with the destination first.

Keeping destination (definition) operands at the beginning of the operand list has several advantages. In particular, the debugging printer will print the instruction like this:

%r3 = add %i1, %i2

Also if the first operand is a def, it is easier to create instructions whose only def is the first operand.

LLVM code generator can model sequences of instructions as MachineInstr bundles. A MI bundle can model a VLIW group / pack which contains an arbitrary number of parallel instructions. It can also be used to model a sequential list of instructions (potentially with data dependencies) that cannot be legally separated (e.g. ARM Thumb2 IT blocks).

Conceptually a MI bundle is a MI with a number of other MIs nested within”

Now let’s summarize what’s defined in MachineInstr‘s interface by first looking at a snapshot of its header file:

00045 class MachineInstr : public ilist_node<MachineInstr> {

00047   typedef MachineMemOperand **mmo_iterator;

….....................................

00064 private:

00065   const MCInstrDesc *MCID;              // Instruction descriptor.

00067   uint8_t Flags;                        // Various bits of additional

…..................................

00078   uint16_t NumMemRefs;                  // information on memory references

00079   mmo_iterator MemRefs;

00081   std::vector<MachineOperand> Operands; // the operands

00082   MachineBasicBlock *Parent;            // Pointer to the owning basic block.

….....................................

00110   MachineBasicBlock* getParent() { return Parent; }

…....................................

00149  void setFlag(MIFlag Flag) {

00150     Flags |= (uint8_t)Flag;

00151   }

…..............................-.......

00247  const MCInstrDesc &getDesc() const { return *MCID; }

00251  int getOpcode() const { return MCID->Opcode; }

00255  unsigned getNumOperands() const { return (unsigned)Operands.size(); }

00261   MachineOperand& getOperand(unsigned i) {

00262     assert(i < getNumOperands() && "getOperand() out of range!");

00263     return Operands[i];

00264   }

….....................................

00198  /// The first instruction has the special opcode "BUNDLE". It's not "inside"

00199  /// a bundle, but the next three MIs are.

00200  bool isInsideBundle() const {

00201     return getFlag(BundledPred);

00202   }

00229  /// Break bundle below this instruction.

00230  void unbundleFromSucc();

…....................................

00318  bool isVariadic(QueryType Type = IgnoreBundle) const {

00319     return hasProperty(MCID::Variadic, Type);

00320   }

00335   bool isReturn(QueryType Type = AnyInBundle) const {

00336     return hasProperty(MCID::Return, Type);

00337   }

00339   bool isCall(QueryType Type = AnyInBundle) const {

00340     return hasProperty(MCID::Call, Type);

00341   }

00364  bool isBranch(QueryType Type = AnyInBundle) const {

00365     return hasProperty(MCID::Branch, Type);

00366   }

00492  bool isCommutable(QueryType Type = IgnoreBundle) const {

00493     return hasProperty(MCID::Commutable, Type);

00494   }

…...................................

00448   //===--------------------------------------------------------------------===//

00449   // Side Effect Analysis

00450   //===--------------------------------------------------------------------===//

00452  /// mayLoad - Return true if this instruction could possibly read memory.

00453  /// Instructions with this flag set are not necessarily simple load

00454  /// instructions, they may load a value and modify it, for example.

00455  bool mayLoad(QueryType Type = AnyInBundle) const {

00456     if (isInlineAsm()) {

00457       unsigned ExtraInfo = getOperand(InlineAsm::MIOp_ExtraInfo).getImm();

00458       if (ExtraInfo & InlineAsm::Extra_MayLoad)

00459         return true;

00460     }

00461     return hasProperty(MCID::MayLoad, Type);

00462   }

…...................................

00608  void eraseFromParent();

00609

00610  /// Unlink 'this' form its basic block and delete it.

00611  ///

00612  /// If the instruction is part of a bundle, the other instructions in the

00613  /// bundle remain bundled.

00614  void eraseFromBundle();

…................................

00851  /// substituteRegister - Replace all occurrences of FromReg with ToReg:SubIdx,

00852  /// properly composing subreg indices where necessary.

00853  void substituteRegister(unsigned FromReg, unsigned ToReg, unsigned SubIdx,

00854                           const TargetRegisterInfo &RegInfo);

00855

00856  /// addRegisterKilled - We have determined MI kills a register. Look for the

00857  /// operand that uses it and mark it as IsKill.

00860  bool addRegisterKilled(unsigned IncomingReg,

00861                          const TargetRegisterInfo *RegInfo,

00862                          bool AddIfNotFound = false);

00940   //===--------------------------------------------------------------------===//

00941   // Accessors used to build up machine instructions.

00951  /// MachineInstrBuilder provides a more convenient interface for creating

00952  /// instructions and adding operands.

00953  void addOperand(MachineFunction &MF, const MachineOperand &Op);

00965  void setDesc(const MCInstrDesc &tid) { MCID = &tid; }

….............................

Based on the above code we can summarize the interface for the MachineInstr class. It has a MCID member with MCInstrDesc type to describe the instruction, a uint8_t Flags member, a memory reference member  mmo_iterator MemRefs and a vector member of operands std::vector<MachineOperand> Operands.   In terms of methods the MachineInstr class provides a basic set of get** and set** for information query (e.g., getOpcode(), getNumOperands(), etc.), bundle related operations (e.g.,isInsideBundle(), etc.),  boolean based methods to check if the instruction has certain property (e.g.,isVariadic(),isReturn(),isCall(),etc.), machine instruction manipulation (e.g.,eraseFromParent(),etc.), register related operations (e.g,ubstituteRegister(), addRegisterKilled(), etc.) and machine instruction creating methods (e.g.,addOperand(), setDesc(), etc.).  The above source code analyze confirms what’s described in the beginning of part 7.3.1: “...this class is an extremely abstract way of representing machine instructions. In particular, it only keeps track of an opcode number and a set of operands...”  Note that although the MachineInstr  class provides machine instruction creating methods, a dedicated function BuildMI() (defined in llvm-3.1.src\include\llvm\CodeGen\MachineInstrBuilder.h), based on

MachineInstrBuilder class, is more convenient. MachineInstrBuilder class will be discussed in the next subsection.

Part 7.3.4 MachineInstrBuilder 

The file MachineInstrBuilder.h defines a machine instruction builder. This file exposes a function called BuildMI(), which works internally with a class named MachineInstrBuilder. There are many different versions of BuildMI() functions. The source code is listed as below:

00008 //===----------------------------------------------------------------------===//
00009
//
00010
// This file exposes a function named BuildMI, which is useful for dramatically
00011
// simplifying how MachineInstr's are created.  It allows use of code like this:
00012
//
00013
//   M = BuildMI(X86::ADDrr8, 2).addReg(argVal1).addReg(argVal2);
00014
//
00015
//===----------------------------------------------------------------------===//

00044 class MachineInstrBuilder {
00045  
 MachineFunction *MF;
00046  
 MachineInstr *MI;
00047
public:
00048   MachineInstrBuilder() : MF(0), MI(0) {}
00049
00050
 /// Create a MachineInstrBuilder for manipulating an existing instruction.
00051
 /// F must be the machine function  that was used to allocate I.
00052  MachineInstrBuilder(MachineFunction &F, MachineInstr *I) : MF(&F), MI(I) {}
00053
00054
 /// Allow automatic conversion to the machine instruction we are working on.
00055
 ///
00056  operator MachineInstr*() const { return MI; }
00057   MachineInstr *operator->() const { return MI; }
00058   operator MachineBasicBlock::iterator() const { return MI; }
00059
00060
 /// addReg - Add a new virtual register operand...
00061
 ///
00062  
const
00063   MachineInstrBuilder &addReg(unsigned RegNo, unsigned flags = 0,
00064                              
unsigned SubReg = 0) const {
00065     assert((flags & 0x1) == 0 &&
00066            
"Passing in 'true' to addReg is forbidden! Use enums instead.");
00067     MI->
addOperand(*MF, MachineOperand::CreateReg(RegNo,
00068                                                flags &
 RegState::Define,
00069                                                flags &
 RegState::Implicit,
00070                                                flags &
 RegState::Kill,
00071                                                flags &
 RegState::Dead,
00072                                                flags &
 RegState::Undef,
00073                                                flags &
 RegState::EarlyClobber,
00074                                                SubReg,
00075                                                flags &
 RegState::Debug,
00076                                                flags &
 RegState::InternalRead));
00077    
return *this;
00078   }
00079
00080
 /// addImm - Add a new immediate operand.
00081
 ///
00082  const MachineInstrBuilder &addImm(int64_t Val) const {
00083     MI->
addOperand(*MF, MachineOperand::CreateImm(Val));
00084    
return *this;
00085   }

….......................

00219 /// BuildMI - Builder interface.  Specify how to create the initial instruction
00220
/// itself.
00221
///
00222 inline MachineInstrBuilder BuildMI(MachineFunction &MF,
00223                                  
 DebugLoc DL,
00224                                    
const MCInstrDesc &MCID) {
00225  
return MachineInstrBuilder(MF, MF.CreateMachineInstr(MCID, DL));
00226 }
00227
00228
/// BuildMI - This version of the builder sets up the first operand as a
00229
/// destination virtual register.
00230
///
00231 inline MachineInstrBuilder BuildMI(MachineFunction &MF,
00232                                  
 DebugLoc DL,
00233                                    
const MCInstrDesc &MCID,
00234                                    
unsigned DestReg) {
00235  
return MachineInstrBuilder(MF, MF.CreateMachineInstr(MCID, DL))
00236            .addReg(DestReg,
 RegState::Define);
00237 }
00238
00239
/// BuildMI - This version of the builder inserts the newly-built
00240
/// instruction before the given position in the given MachineBasicBlock, and
00241
/// sets up the first operand as a destination virtual register.
00242
///
00243 inline MachineInstrBuilder BuildMI(MachineBasicBlock &BB,
00244                                  
 MachineBasicBlock::iterator I,
00245                                  
 DebugLoc DL,
00246                                    
const MCInstrDesc &MCID,
00247                                    
unsigned DestReg) {
00248  
 MachineFunction &MF = *BB.getParent();
00249  
 MachineInstr *MI = MF.CreateMachineInstr(MCID, DL);
00250   BB.
insert(I, MI);
00251  
return MachineInstrBuilder(MF, MI).addReg(DestReg, RegState::Define);
00252 }

….............///// several other BuildMI() functions with different prototypes. ////................

…..........................

Regarding how to use BuildMI() to build instructions, it is enough to refer to the LLVM document (listed here for convenience):

Using the MachineInstrBuilder.h functions

Machine instructions are created by using the BuildMI functions, located in the include/llvm/CodeGen/MachineInstrBuilder.h file. The BuildMI functions make it easy to build arbitrary machine instructions. Usage of the BuildMI functions look like this:

// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
// instruction.  The '1' specifies how many operands will be added.
MachineInstr
*MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);

// Create the same instr, but insert it at the end of a basic block.
MachineBasicBlock
&MBB = ...
BuildMI(MBB, X86
::MOV32ri, 1, DestReg).addImm(42);

// Create the same instr, but insert it before a specified iterator point.
MachineBasicBlock
::iterator MBBI = ...
BuildMI(MBB, MBBI, X86
::MOV32ri, 1, DestReg).addImm(42);

// Create a 'cmp Reg, 0' instruction, no destination reg.
MI
= BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);

// Create an 'sahf' instruction which takes no operands and stores nothing.
MI
= BuildMI(X86::SAHF, 0);

// Create a self looping branch instruction.
BuildMI(MBB, X86
::JNE, 1).addMBB(&MBB);

The key thing to remember with the BuildMI functions is that you have to specify the number of operands that the machine instruction will take. This allows for efficient memory allocation. You also need to specify if operands default to be uses of values, not definitions. If you need to add a definition operand (other than the optional destination register), you must explicitly mark it as such:   MI.addReg(Reg, RegState::Define);

Part 7.4  MC layer

Ok, now for studying MC layer (machine code layer) let’s first put something offical here for a high-level description:

The “MC” Layer

The MC Layer is used to represent and process code at the raw machine code level, devoid of “high level” information like “constant pools”, “jump tables”, “global variables” or anything like that. At this level, LLVM handles things like label names, machine instructions, and sections in the object file. The code in this layer is used for a number of important purposes: the tail end of the code generator uses it to write a .s or .o file, and it is also used by the llvm-mc tool to implement standalone machine code assemblers and disassemblers.

This section describes some of the important classes. There are also a number of important subsystems that interact at this layer, they are described later in this manual.”

MC layer contains several important components such as MCStreamer, MCContext, MCSymbol, MCSection and MCInst. We will discuss these topics in the following subsections and the methodology we use to study them is starting each subsection/component by one paragraph from the LLVM document followed by a more detailed code study and explanation.

Part 7.4.1  MCStreamer

The MCStreamer API

MCStreamer is best thought of as an assembler API. It is an abstract API which is implemented in different ways (e.g. to output a .s file, output an ELF .o file, etc) but whose API correspond directly to what you see in a .s file. MCStreamer has one method per directive, such as EmitLabel, EmitSymbolAttribute, SwitchSection, EmitValue (for .byte, .word), etc, which directly correspond to assembly level directives. It also has an EmitInstruction method, which is used to output an MCInst to the streamer.

This API is most important for two clients: the llvm-mc stand-alone assembler is effectively a parser that parses a line, then invokes a method on MCStreamer. In the code generator, the Code Emission phase of the code generator lowers higher level LLVM IR and Machine* constructs down to the MC layer, emitting directives through MCStreamer.

On the implementation side of MCStreamer, there are two major implementations: one for writing out a .s file (MCAsmStreamer), and one for writing out a .o file (MCObjectStreamer). MCAsmStreamer is a straight-forward implementation that prints out a directive for each method (e.g. EmitValue -> .byte), but MCObjectStreamer implements a full assembler.”

A simplified class hierarchy is shown as follows (since some of the classes such as MCAsmStreamer does not have a corresponding header file thus the automatically generated llvm document does not have a complete class hierarchy):

First, let’s study MCStreamer.

MCStreamer - Streaming machine code generation interface. This interface is intended to provide a programatic interface that is very similar to the level that an assembler .s file provides. It has callbacks to emit bytes, handle directives, etc. The implementation of this interface retains state to know what the current section is etc. There are multiple implementations of this interface: one for writing out a .s file, and implementations that write out .o files of various formats.

Some representative function interfaces from the MCStreamer class are listed as below:

00047  class MCStreamer {
00048    
 MCContext &Context;
…...............................
00056     std::vector<MCDwarfFrameInfo> FrameInfos;
00057    
 MCDwarfFrameInfo *getCurrentFrameInfo();
00058    
 MCSymbol *EmitCFICommon();
00059    
void EnsureValidFrame();
00061     std::vector<MCWin64EHUnwindInfo *> W64UnwindInfos;
00062    
 MCWin64EHUnwindInfo *CurrentW64UnwindInfo;
00063    
void setCurrentW64UnwindInfo(MCWin64EHUnwindInfo *Frame);
00064    
void EnsureValidW64UnwindInfo();
00066    
 MCSymbol* LastSymbol;
00068
   /// SectionStack - This is stack of current and previous section
00069
   /// values saved by PushSection.
00070  
 SmallVector<std::pair<const MCSection *,
00071                
const MCSection *>, 4> SectionStack;

…...............................

00099     MCContext &getContext() const { return Context; }
00101     unsigned getNumFrameInfos() {
00102      
return FrameInfos.size(); }
00105     const MCDwarfFrameInfo &getFrameInfo(unsigned i) {
00106      
return FrameInfos[i];
00107     }

…......................

00162    /// getPreviousSection - Return the previous section that the streamer is
00163
   /// emitting code to.
00164    const MCSection *getPreviousSection() const {
00165      
if (!SectionStack.empty())
00166        
return SectionStack.back().second;
00167      
return NULL;
00168     }
00170
   /// ChangeSection - Update streamer for a new active section.
00172
   /// This is called by PopSection and SwitchSection, if the current
00173
   /// section changes.
00174    
virtual void ChangeSection(const MCSection *) = 0;
00176
   /// pushSection - Save the current and previous section on the
00177
   /// section stack.
00178    void PushSection() {
00179       SectionStack.
push_back(std::make_pair(getCurrentSection(),
00180                                            
 getPreviousSection()));
00181     }

…...............................

00245    virtual void EmitLabel(MCSymbol *Symbol);
00247    
virtual void EmitDebugLabel(MCSymbol *Symbol);
00249    
virtual void EmitEHSymAttributes(const MCSymbol *Symbol,
00250                                    
 MCSymbol *EHSymbol);
00252
   /// EmitAssemblerFlag - Note in the output the specified @p Flag.
00253    
virtual void EmitAssemblerFlag(MCAssemblerFlag Flag) = 0;
00255
   /// EmitDataRegion - Note in the output the specified region @p Kind.
00256    virtual void EmitDataRegion(MCDataRegionType Kind) {}
00258
   /// EmitThumbFunc - Note in the output that the specified @p Func is
00259
   /// a Thumb mode function (ARM target only).
00260    
virtual void EmitThumbFunc(MCSymbol *Func) = 0;

00273    virtual void EmitAssignment(MCSymbol *Symbol, const MCExpr *Value) = 0;

00282    virtual void EmitWeakReference(MCSymbol *Alias, const MCSymbol *Symbol) = 0;

00322    virtual void EmitELFSize(MCSymbol *Symbol, const MCExpr *Value) = 0;

00369    virtual void EmitBytes(StringRef Data, unsigned AddrSpace) = 0;

00489    /// EmitFileDirective - Switch to a new logical file.  This is used to
00490
   /// implement the '.file "foo.c"' assembler directive.
00491    
virtual void EmitFileDirective(StringRef Filename) = 0;
00492
00493
   /// EmitDwarfFileDirective - Associate a filename with a specified logical
00494
   /// file number.  This implements the DWARF2 '.file 4 "foo.c"' assembler
00495
   /// directive.
00496    
virtual bool EmitDwarfFileDirective(unsigned FileNo, StringRef Directory,
00497                                        
 StringRef Filename);

00521     void EmitCFIStartProc();
00522    
void EmitCFIEndProc();
00523    
virtual void EmitCFIDefCfa(int64_t Register, int64_t Offset);
00524    
virtual void EmitCFIDefCfaOffset(int64_t Offset);
00525    
virtual void EmitCFIDefCfaRegister(int64_t Register);
00526    
virtual void EmitCFIOffset(int64_t Register, int64_t Offset);
00527    
virtual void EmitCFIPersonality(const MCSymbol *Sym, unsigned Encoding);
00528    
virtual void EmitCFILsda(const MCSymbol *Sym, unsigned Encoding);
00529    
virtual void EmitCFIRememberState();
00530    
virtual void EmitCFIRestoreState();

…..................................

00631  /// createMachOStreamer - Create a machine code streamer which will generate
00632
 /// Mach-O format object files.
00634
 /// Takes ownership of \p TAB and \p CE.
00635  MCStreamer *
createMachOStreamer(MCContext &Ctx, MCAsmBackend &TAB,
00636                                   raw_ostream &OS, MCCodeEmitter *CE,
00637                                  
bool RelaxAll = false);
00639
 /// createWinCOFFStreamer - Create a machine code streamer which will
00640
 /// generate Microsoft COFF format object files.
00642
 /// Takes ownership of \p TAB and \p CE.
00643  MCStreamer *
createWinCOFFStreamer(MCContext &Ctx,
00644                                     MCAsmBackend &TAB,
00645                                     MCCodeEmitter &CE, raw_ostream &OS,
00646                                    
bool RelaxAll = false);
00648
 /// createELFStreamer - Create a machine code streamer which will generate
00649
 /// ELF format object files.
00650  MCStreamer *
createELFStreamer(MCContext &Ctx, MCAsmBackend &TAB,
00651                                 raw_ostream &OS, MCCodeEmitter *CE,
00652                                
bool RelaxAll, bool NoExecStack);
00654
 /// createPureStreamer - Create a machine code streamer which will generate
00655
 /// "pure" MC object files, for use with MC-JIT and testing tools.
00657
 /// Takes ownership of \p TAB and \p CE.
00658  MCStreamer *
createPureStreamer(MCContext &Ctx, MCAsmBackend &TAB,
00659                                  raw_ostream &OS, MCCodeEmitter *CE);

The above code snippet indicates MCStreamer class maintains a vector of frame info (std::vector<MCDwarfFrameInfo> FrameInfos), a vector of unwind information (std::vector<MCWin64EHUnwindInfo *> W64UnwindInfos), a section stack (SmallVector<std::pair<const MCSection *, const MCSection *>, 4> SectionStack) and defines several important categories of functions. These functions include information getting methods (e.g., getContext(),getNumFrameInfos(), etc.), section manipulation operations (e.g.,getPreviousSection(),PushSection(),etc.), emitting methods (e.g.,EmitLabel(), EmitDebugLabel(), EmitThumbFunc(), EmitAssignment() EmitELFSize(), EmitBytes(), etc.) and a series of streamer creation methods (e.g.,createELFStreamer(), createMachOStreamer()). Among those functions, the emitting methods and some of the other functions (e.g.,ChangeSection()) are defined as virtual or pure-virtual and thus are supposed to be re-implemented by a concrete streamer implementation.

From the inheritance hierarchy of the streamer class presented at the beginning of part 7.4.1 we can see MCObjectStreamer and MCAsmStreamer are two important classes that subclass the MCStreamer class. First let’s discuss the MCObjectStreamer class:

00025 /// \brief Streaming object file generation interface.
00027
/// This class provides an implementation of the MCStreamer interface which is
00028
/// suitable for use with the assembler backend. Specific object file formats
00029
/// are expected to subclass this interface to implement directives specific
00030
/// to that file format or custom semantics expected by the object writer
00031
/// implementation.
00032 class MCObjectStreamer : public MCStreamer {
00033  
 MCAssembler *Assembler;

….......................

MCObjectStreamer class is a little bit more concrete than the MCStreamer class but still not “very concrete”, i.e., it is supposed to be further sub-classed by a more concrete streamer (e.g., MCELFStreamer) class aimed to write out .o (object) files.

MCObjectStreamer class implements or re-implements the pure-virtual or virtual functions defined in the abstract MCStreamer class. Specifically, it implements or re-implements the following pure-virtual or virtual functions:

00071   virtual void EmitLabel(MCSymbol *Symbol);
00072  
virtual void EmitDebugLabel(MCSymbol *Symbol);
00073  
virtual void EmitAssignment(MCSymbol *Symbol, const MCExpr *Value);
00074  
virtual void EmitValueImpl(const MCExpr *Value, unsigned Size,
00075                              
unsigned AddrSpace);
00076  
virtual void EmitULEB128Value(const MCExpr *Value);
00077  
virtual void EmitSLEB128Value(const MCExpr *Value);
00078  
virtual void EmitWeakReference(MCSymbol *Alias, const MCSymbol *Symbol);
00079  
virtual void ChangeSection(const MCSection *Section);
00080  
virtual void EmitInstruction(const MCInst &Inst);
00084  
virtual void EmitInstToFragment(const MCInst &Inst);
00086  
virtual void EmitBundleAlignMode(unsigned AlignPow2);
00087  
virtual void EmitBundleLock();
00088  
virtual void EmitBundleUnlock();
00089  
virtual void EmitBytes(StringRef Data, unsigned AddrSpace);
00090  
virtual void EmitValueToAlignment(unsigned ByteAlignment,
00091                                     int64_t
 Value = 0,
00092                                    
unsigned ValueSize = 1,
00093                                    
unsigned MaxBytesToEmit = 0);
00094  
virtual void EmitCodeAlignment(unsigned ByteAlignment,
00095                                  
unsigned MaxBytesToEmit = 0);
00096  
virtual bool EmitValueToOffset(const MCExpr *Offset, unsigned char Value);
00097  
virtual void EmitDwarfAdvanceLineAddr(int64_t LineDelta,
00098                                        
const MCSymbol *LastLabel,
00099                                        
const MCSymbol *Label,
00100                                        
unsigned PointerSize);
00101  
virtual void EmitDwarfAdvanceFrameAddr(const MCSymbol *LastLabel,
00102                                          
const MCSymbol *Label);
00103  
virtual void EmitGPRel32Value(const MCExpr *Value);
00104  
virtual void EmitGPRel64Value(const MCExpr *Value);
00105  
virtual void EmitFill(uint64_t NumBytes, uint8_t FillValue,
00106                        
unsigned AddrSpace);
00107  
virtual void FinishImpl();

Functions such as EmitLabel() and EmitGPRel64Value() are re-implemented in the MCObjectStreamer class:

00122 void MCObjectStreamer::EmitLabel(MCSymbol *Symbol) {
00123  
 MCStreamer::EmitLabel(Symbol);
00125  
 MCSymbolData &SD = getAssembler().getOrCreateSymbolData(*Symbol);
00127  
// FIXME: This is wasteful, we don't necessarily need to create a data
00128  
// fragment. Instead, we should mark the symbol as pointing into the data
00129  
// fragment if it exists, otherwise we should just queue the label and set its
00130  
// fragment pointer when we emit the next fragment.
00131  
 MCDataFragment *F = getOrCreateDataFragment();
00132   assert(!SD.
getFragment() && "Unexpected fragment on symbol data!");
00133   SD.
setFragment(F);
00134   SD.
setOffset(F->getContents().size());
00135 }

….........................

00330 void MCObjectStreamer::EmitGPRel64Value(const MCExpr *Value) {
00331  
 MCDataFragment *DF = getOrCreateDataFragment();
00332
00333   DF->
getFixups().push_back(MCFixup::Create(DF->getContents().size(),
00334                                             Value,
 FK_GPRel_4));
00335   DF->
getContents().resize(DF->getContents().size() + 8, 0);
00336 }

while the original definitions of these two functions in the MCStreamer class are:

00143 void MCStreamer::EmitGPRel64Value(const MCExpr *Value) {
00144  
 report_fatal_error("unsupported directive in streamer");
00145 }

…........................

00191 void MCStreamer::EmitLabel(MCSymbol *Symbol) {
00192   assert(!Symbol->
isVariable() && "Cannot emit a variable symbol!");
00193   assert(
getCurrentSection() && "Cannot emit before setting section!");
00194   Symbol->
setSection(*getCurrentSection());
00195   LastSymbol =
 Symbol;
00196 }

Other functions are pure-virtual in the MCStreamer class but implemented in the MCObjectStreamer class. For example, the EmitInstruction() function is defined as a pure-virtual function in the MCStreamer class while has the following definition in the MCObjectStreamer class:

00177 void MCObjectStreamer::EmitInstruction(const MCInst &Inst) {
00178  
// Scan for values.
00179  
for (unsigned i = Inst.getNumOperands(); i--; )
00180    
if (Inst.getOperand(i).isExpr())
00181      
 AddValueSymbols(Inst.getOperand(i).getExpr());
00183  
 MCSectionData *SD = getCurrentSectionData();
00184   SD->
setHasInstructions(true);
00186  
// Now that a machine instruction has been assembled into this section, make
00187  
// a line entry for any .loc directive that has been seen.
00188  
 MCLineEntry::Make(this, getCurrentSection());
00190  
// If this instruction doesn't need relaxation, just emit it as data.
00191  
 MCAssembler &Assembler = getAssembler();
00192  
if (!Assembler.getBackend().mayNeedRelaxation(Inst)) {
00193     EmitInstToData(Inst);
00194    
return;
00195   }

Similarly, the EmitAssignment() function is defined as a pure-virtual function in the MCStreamer class while has the following definition in the MCObjectStreamer class:

00172 void MCObjectStreamer::EmitAssignment(MCSymbol *Symbol, const MCExpr *Value) {
00173  
 getAssembler().getOrCreateSymbolData(*Symbol);
00174   Symbol->
setVariableValue(AddValueSymbols(Value));
00175 }

The above code snippet reveals that MCObjectStreamer class is closely related to the  MCAssembler class. An MCObjectStreamer object gets its MCAssembler *Assembler member by calling getAssembler() and then invoke various methods (e.g.,Assembler.getBackend().mayNeedRelaxation(Inst), getAssembler().getOrCreateSymbolData(*Symbol)) upon it (Assembler).

For now we shall discuss other derived classes based on the MCStreamer class. We will discuss what’s the role of MCAssembler and its relationship with MCObjectStreamer as well as other object streamer derived classes in the next subsection (part 7.4.2). Following the above discussion of the MCObjectStreamer class, it is nice to extend the topic to its subclass MCELFStreamer.  

MCELFStreamer further re-implements some functions defined in MCObjectStreamer. For example the EmitLabel() function:

00077 void MCELFStreamer::EmitLabel(MCSymbol *Symbol) {
00078   assert(Symbol->
isUndefined() && "Cannot define a symbol twice!");
00080  
 MCObjectStreamer::EmitLabel(Symbol);
00082  
const MCSectionELF &Section =
00083    
static_cast<const MCSectionELF&>(Symbol->getSection());
00084  
 MCSymbolData &SD = getAssembler().getSymbolData(*Symbol);
00085  
if (Section.getFlags() & ELF::SHF_TLS)
00086    
 MCELF::SetType(SD, ELF::STT_TLS);
00087 }

It also implements some functions that are pure-virtual in the MCAssembler class and not implemented in the MCObjectStreamer class. For example the EmitFileDirective() function:

00287 void MCELFStreamer::EmitFileDirective(StringRef Filename) {
00288  
 MCSymbol *Symbol = getAssembler().getContext().GetOrCreateSymbol(Filename);
00289   Symbol->
setSection(*getCurrentSection());
00290   Symbol->
setAbsolute();
00292  
 MCSymbolData &SD = getAssembler().getOrCreateSymbolData(*Symbol);
00294   SD.
setFlags(ELF_STT_File | ELF_STB_Local | ELF_STV_Default);
00295 }

Another such example is EmitELFSize():

00251 void MCELFStreamer::EmitELFSize(MCSymbol *Symbol, const MCExpr *Value) {
00252  
 MCSymbolData &SD = getAssembler().getOrCreateSymbolData(*Symbol);
00253   SD.
setSize(Value);
00254 }

Other than the MCObjectStreamer  class and its subclass (e.g.,MCELFStreamer), there is another class that inherits the base class MCStreamer named MCAsmStreamer. Its code is listed here (note that this class does not have header file, all interface and definitions are in a cpp file):

00038 class MCAsmStreamer : public MCStreamer {
00039
protected:
00040  
 formatted_raw_ostream &OS;
00041  
const MCAsmInfo &MAI;
00042
private:
00043  
 OwningPtr<MCInstPrinter> InstPrinter;
00044  
 OwningPtr<MCCodeEmitter> Emitter;
00045  
 OwningPtr<MCAsmBackend> AsmBackend;
00047  
 SmallString<128> CommentToEmit;
00048  
 raw_svector_ostream CommentStream;

…........................

00346 void MCAsmStreamer::EmitLabel(MCSymbol *Symbol) {
00347   assert(Symbol->
isUndefined() && "Cannot define a symbol twice!");
00348  
 MCStreamer::EmitLabel(Symbol);
00350   OS << *Symbol << MAI.getLabelSuffix();
00351   EmitEOL();
00352 }

…......................

00362 void MCAsmStreamer::EmitAssemblerFlag(MCAssemblerFlag Flag) {
00363  
switch (Flag) {
00364  
case MCAF_SyntaxUnified:         OS << "\t.syntax unified"; break;
00365  
case MCAF_SubsectionsViaSymbols: OS << ".subsections_via_symbols"; break;
00366  
case MCAF_Code16:                OS << '\t'<< MAI.getCode16Directive(); break;
00367  
case MCAF_Code32:                OS << '\t'<< MAI.getCode32Directive(); break;
00368  
case MCAF_Code64:                OS << '\t'<< MAI.getCode64Directive(); break;
00369   }
00370   EmitEOL();
00371 }

….................................................................

00514 void MCAsmStreamer::EmitELFSize(MCSymbol *Symbol, const MCExpr *Value) {
00515   assert(MAI.
hasDotTypeDotSizeDirective());
00516   OS <<
"\t.size\t" << *Symbol << ", " << *Value << '\n';
00517 }

…...................................................................

00803 void MCAsmStreamer::EmitFileDirective(StringRef Filename) {
00804   assert(MAI.
hasSingleParameterDotFile());
00805   OS <<
"\t.file\t";
00806  
 PrintQuotedString(Filename, OS);
00807   EmitEOL();
00808 }

As can be seen from the above code snippet, MCAsmStreamer class implements or re-implements vast majority of relevant virtual functions in the MCStreamer class for streaming .s (assembly) files.  The MCAsmStreamer class relies on several important data members to provide target and platform specific information. These members are MCAsmInfo &MAI , OwningPtr<MCInstPrinter> InstPrinter, OwningPtr<MCCodeEmitter> Emitter and OwningPtr<MCAsmBackend> AsmBackend.  We shall discuss them in the next subsection (part 7.4.2)

Part 7.4.2 MCAssembler, MCAsmInfo, MCInstPrinter, MCCodeEmitter and MCAsmBackend

First let’s get start on

00711 class MCAssembler {
00712   friend class MCAsmLayout;
00732
private:
00736  
 MCContext &Context;
00738  
 MCAsmBackend &Backend;
00740  
 MCCodeEmitter &Emitter;
00742  
 MCObjectWriter &Writer;
00744  
 raw_ostream &OS;
00746  
 iplist<MCSectionData> Sections;
00748  
 iplist<MCSymbolData> Symbols;
00750
 /// The map of sections to their associated assembler backend data.
00753  
 DenseMap<const MCSection*, MCSectionData*> SectionMap;
00758  
 DenseMap<const MCSymbol*, MCSymbolData*> SymbolMap;
00760   std::
vector<IndirectSymbolData> IndirectSymbols;
00762   std::
vector<DataRegionData> DataRegions;
00781 private:
00782
 /// Evaluate a fixup to a relocatable expression and the value which should be
00783
 /// placed into the fixup.
00795  
bool evaluateFixup(const MCAsmLayout &Layout,
00796                      const
 MCFixup &Fixup, const MCFragment *DF,
00797                    
 MCValue &Target, uint64_t &Value) const;
00799
 /// Check whether a fixup can be satisfied, or whether it needs to be relaxed
00800
 /// (increased in size, in order to hold its value correctly).
00801  
bool fixupNeedsRelaxation(const MCFixup &Fixup, const MCInstFragment *DF,
00802                             const
 MCAsmLayout &Layout) const;
00804
 /// Check whether the given fragment needs relaxation.
00805  
bool fragmentNeedsRelaxation(const MCInstFragment *IF,
00806                                const
 MCAsmLayout &Layout) const;
00808
 /// \brief Perform one layout iteration and return true if any offsets
00809
 /// were adjusted.
00810  
bool layoutOnce(MCAsmLayout &Layout);
00816  
bool relaxInstruction(MCAsmLayout &Layout, MCInstFragment &IF);
00818  
bool relaxLEB(MCAsmLayout &Layout, MCLEBFragment &IF);
00820  
bool relaxDwarfLineAddr(MCAsmLayout &Layout, MCDwarfLineAddrFragment &DF);
00821  
bool relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
00822                                  
 MCDwarfCallFrameFragment &DF);
00824
 /// finishLayout - Finalize a layout, including fragment lowering.
00825  
void finishLayout(MCAsmLayout &Layout);
00827   uint64_t handleFixup(const
 MCAsmLayout &Layout,
00828                      
 MCFragment &F, const MCFixup &Fixup);

…..................

00830 public:
00831
 /// Compute the effective fragment size assuming it is laid out at the given
00832
 /// \p SectionAddress and \p FragmentOffset.
00833  uint64_t
 computeFragmentSize(const MCAsmLayout &Layout,
00834                                const
 MCFragment &F) const;
00838  const
 MCSymbolData *getAtom(const MCSymbolData *Symbol) const;
00844  
bool isSymbolLinkerVisible(const MCSymbol &SD) const;
00846
 /// Emit the section contents using the given object writer.
00847  
void writeSectionData(const MCSectionData *Section,
00848                         const
 MCAsmLayout &Layout) const;
00850
 /// Check whether a given symbol has been flagged with .thumb_func.
00851  bool isThumbFunc(const MCSymbol *Func) const {
00852    
return ThumbFuncs.count(Func);
00853   }
00855
 /// Flag a function symbol as the target of a .thumb_func directive.
00856  void setIsThumbFunc(const MCSymbol *Func) { ThumbFuncs.insert(Func); }

As can be seen from the above code, the MCAssembler class organizes together all the important data structures that an MC assembler should have: coder emitter, object writer, asm backend, sections, symbols, etc. In addition, MCAssembler provides various private functions such as code fixup [1],  relax**[2] methods, layout methods to his friend class MCAsmLayout. MCAssembler also provides some public methods for querying relevant information such as the fragment size, symbol linker visibility, section data information, etc.

This class is not supposed to be sub-classed. Object writer classes (e.g., ELFObjectWriter) heavily utilize the MCAssembler class. Also, an object streamer (e.g.,MCObjectStreamer and its subclasses) creates an MCAssembler object member upon construction:  

00023 MCObjectStreamer::MCObjectStreamer(MCContext &Context, MCAsmBackend &TAB,
00024                                  
 raw_ostream &OS, MCCodeEmitter *Emitter_)
00025   :
 MCStreamer(Context),
00026     Assembler(new
 MCAssembler(Context, TAB,
00027                               *Emitter_, *TAB.createObjectWriter(OS),
00028                               OS)),
00029     CurSectionData(0)
00030 {
00031 }

Note that MCAssembler has an MCObjectWriter member and thus MCObjectStreamer objects could use MCObjectWriter class indirectly through direct uses of the MCAssembler member.

Regarding the MCAsmInfo class the LLVM class document says that this class is intended to be used as a base class for asm properties and features specific to the target. Here is the inheritance graph:

The MCAsmInfo class interface file (.h) just defines various data members representing target-dependent characteristics and corresponding get** methods to retrieve these characteristics. In the implementation file, there is almost nothing but a default constructor that set these data members to their default values:    

00025 MCAsmInfo::MCAsmInfo() {
00026  
 PointerSize = 4;
00027  
 IsLittleEndian = true;
00028  
 StackGrowsUp = false;
00029  
 HasSubsectionsViaSymbols = false;
00030  
 HasMachoZeroFillDirective = false;
00031  
 HasMachoTBSSDirective = false;
00032  
 HasStaticCtorDtorReferenceInStaticMode = false;
00033  
 LinkerRequiresNonEmptyDwarfLines = false;
00034  
 MaxInstLength = 4;
00035  
 PCSymbol = "$";
00036  
 SeparatorString = ";";
00037  
 CommentColumn = 40;
00038  
 CommentString = "#";
00039  
 LabelSuffix = ":";
00040  
 DebugLabelSuffix = ":";
00041  
 GlobalPrefix = "";
00042  
 PrivateGlobalPrefix = ".";
00043  
 LinkerPrivateGlobalPrefix = "";
00044  
 InlineAsmStart = "APP";
00045  
 InlineAsmEnd = "NO_APP";
00046  
 Code16Directive = ".code16";
00047  
 Code32Directive = ".code32";
00048  
 Code64Directive = ".code64";
00049  
 AssemblerDialect = 0;
00050  
 AllowQuotesInName = false;
00051  
 AllowNameToStartWithDigit = false;
00052  
 AllowPeriodsInName = true;
00053  
 AllowUTF8 = true;
00054  
 UseDataRegionDirectives = false;
00055  
 ZeroDirective = "\t.zero\t";
00056  
 AsciiDirective = "\t.ascii\t";
00057  
 AscizDirective = "\t.asciz\t";
00058  
 Data8bitsDirective = "\t.byte\t";
00059  
 Data16bitsDirective = "\t.short\t";
00060  
 Data32bitsDirective = "\t.long\t";
00061  
 Data64bitsDirective = "\t.quad\t";
00062  
 SunStyleELFSectionSwitchSyntax = false;
00063  
 UsesELFSectionDirectiveForBSS = false;
00064  
 AlignDirective = "\t.align\t";
00065  
 AlignmentIsInBytes = true;
00066  
 TextAlignFillValue = 0;
00067  
 GPRel64Directive = 0;
00068  
 GPRel32Directive = 0;
00069  
 GlobalDirective = "\t.globl\t";
00070  
 HasSetDirective = true;
00071  
 HasAggressiveSymbolFolding = true;
00072  
 COMMDirectiveAlignmentIsInBytes = true;
00073  
 LCOMMDirectiveAlignmentType = LCOMM::NoAlignment;
00074  
 HasDotTypeDotSizeDirective = true;
00075  
 HasSingleParameterDotFile = true;
00076  
 HasNoDeadStrip = false;
00077  
 HasSymbolResolver = false;
00078  
 WeakRefDirective = 0;
00079  
 WeakDefDirective = 0;
00080  
 LinkOnceDirective = 0;
00081  
 HiddenVisibilityAttr = MCSA_Hidden;
00082  
 HiddenDeclarationVisibilityAttr = MCSA_Hidden;
00083  
 ProtectedVisibilityAttr = MCSA_Protected;
00084  
 HasLEB128 = false;
00085  
 SupportsDebugInformation = false;
00086  
 ExceptionsType = ExceptionHandling::None;
00087  
 DwarfUsesInlineInfoSection = false;
00088  
 DwarfSectionOffsetDirective = 0;
00089  
 DwarfUsesRelocationsAcrossSections = true;
00090  
 DwarfRegNumForCFI = false;
00091  
 HasMicrosoftFastStdCallMangling = false;
00092 }

In a target-specific subclass of MCAsmInfo, these data members can be set to appropriate values to reflect the characteristics of the represented target.

Now let’s move on to the interface of MCInstPrinter  class (both of its interface and definition is quite simple and the implementation details are supposed to be filled in a target-specific subclass):

00026 class MCInstPrinter {
00027
protected:
00031  raw_ostream *CommentStream;
00032   const MCAsmInfo &MAI;
00033   const MCInstrInfo &MII;
00034   const MCRegisterInfo &MRI;
00036
 /// The current set of available features.
00037  unsigned AvailableFeatures;
00039
 /// True if we are printing marked up assembly.
00040  bool UseMarkup;
00042
 /// True if we are printing immediates as hex.
00043  bool PrintImmHex;
00045
 /// Utility function for printing annotations.
00046  
void printAnnotation(raw_ostream &OS, StringRef Annot);
00047
public:
00048   MCInstPrinter(const MCAsmInfo &mai, const MCInstrInfo &mii,
00049                
const MCRegisterInfo &mri)
00050     :
 CommentStream(0), MAI(mai), MII(mii), MRI(mri), AvailableFeatures(0),
00051      
 UseMarkup(0), PrintImmHex(0) {}
00053  
virtual ~MCInstPrinter();
00055
 /// setCommentStream - Specify a stream to emit comments to.
00056  void setCommentStream(raw_ostream &OS) { CommentStream = &OS; }
00058
 /// printInst - Print the specified MCInst to the specified raw_ostream.
00060  
virtual void printInst(const MCInst *MI, raw_ostream &OS,
00061                        
 StringRef Annot) = 0;
00063
 /// getOpcodeName - Return the name of the specified opcode enum (e.g.
00064
 /// "MOV32ri") or empty if we can't resolve it.
00065
 StringRef getOpcodeName(unsigned Opcode) const;
00067
 /// printRegName - Print the assembler register name.
00068  
virtual void printRegName(raw_ostream &OS, unsigned RegNo) const;
00070   unsigned getAvailableFeatures() const { return AvailableFeatures; }
00071   void setAvailableFeatures(unsigned Value) { AvailableFeatures = Value; }
00073   bool getUseMarkup() const { return UseMarkup; }
00074   void setUseMarkup(bool Value) { UseMarkup = Value; }
00076
 /// Utility functions to make adding mark ups simpler.
00077
 StringRef markup(StringRef s) const;
00078  
 StringRef markup(StringRef a, StringRef b) const;
00080   bool getPrintImmHex() const { return PrintImmHex; }
00081   void setPrintImmHex(bool Value) { PrintImmHex = Value; }
00083
 /// Utility function to print immediates in decimal or hex.
00084
 format_object1<int64_t> formatImm(const int64_t Value) const;
00085 };

The primary goal of this class is to define interface to convert an MCInst to valid target assembly syntax. In the LLVM library there are various implemented subclass derived from MCInstPrinter :

                         

Now look at the class MCCodeEmitter. It provides a generic instruction encoding interface:

00021 /// MCCodeEmitter - Generic instruction encoding interface.
00022 class MCCodeEmitter {
00023
private:
00024  
 MCCodeEmitter(const MCCodeEmitter &) LLVM_DELETED_FUNCTION;
00025  
void operator=(const MCCodeEmitter &) LLVM_DELETED_FUNCTION;
00026
protected: // Can only create subclasses.
00027  
 MCCodeEmitter();
00029
public:
00030  
virtual ~MCCodeEmitter();
00032
 /// Lifetime management
00033  virtual void reset() { }
00035
 /// EncodeInstruction - Encode the given \p Inst to bytes on the output
00036
 /// stream \p OS.
00037  
virtual void EncodeInstruction(const MCInst &Inst, raw_ostream &OS,
00038                                
 SmallVectorImpl<MCFixup> &Fixups) const = 0;
00039 };

Quite simple, isn’t it? The corresponding cpp file is even simpler:

00010 #include "llvm/MC/MCCodeEmitter.h"
00014 MCCodeEmitter::MCCodeEmitter() {
00015 }
00017 MCCodeEmitter::~MCCodeEmitter() {
00018 }

Now the inheritance hierarchy:

Finally, let’s clear MCAsmBackend, which aims to provide a generic interface to target specific assembler backends. It has the following interface:

00032 class MCAsmBackend {
00033  
 MCAsmBackend(const MCAsmBackend &) LLVM_DELETED_FUNCTION;
00034  
void operator=(const MCAsmBackend &) LLVM_DELETED_FUNCTION;
00035
protected: // Can only create subclasses.
00036  
 MCAsmBackend();
00038   unsigned HasReliableSymbolDifference : 1;
00039   unsigned HasDataInCodeSupport : 1;
00041
public:
00042  
virtual ~MCAsmBackend();
00044
 /// lifetime management
00045  virtual void reset() { }
00047
 /// createObjectWriter - Create a new MCObjectWriter instance for use by the
00048
 /// assembler backend to emit the final object file.
00049  
virtual MCObjectWriter *createObjectWriter(raw_ostream &OS) const = 0;
00051
 /// createELFObjectTargetWriter - Create a new ELFObjectTargetWriter to enable
00052
 /// non-standard ELFObjectWriters.
00053  virtual  MCELFObjectTargetWriter *createELFObjectTargetWriter() const {
00054    
 llvm_unreachable("createELFObjectTargetWriter is not supported by asm "
00055                      
"backend");
00056   }
00058
 /// hasReliableSymbolDifference - Check whether this target implements
00059
 /// accurate relocations for differences between symbols. If not, differences
00060
 /// between symbols will always be relocatable expressions and any references
00061
 /// to temporary symbols will be assumed to be in the same atom, unless they
00062
 /// reside in a different section.
00068  bool hasReliableSymbolDifference() const {
00069    
return HasReliableSymbolDifference;
00070   }
00071
00072
 /// hasDataInCodeSupport - Check whether this target implements data-in-code
00073
 /// markers. If not, data region directives will be ignored.
00074  bool hasDataInCodeSupport() const {
00075    
return HasDataInCodeSupport;
00076   }
00077
00078
 /// doesSectionRequireSymbols - Check whether the given section requires that
00079
 /// all symbols (even temporaries) have symbol table entries.
00080  virtual bool doesSectionRequireSymbols(const MCSection &Section) const {
00081    
return false;
00082   }
00088  virtual bool isSectionAtomizable(const MCSection &Section) const {
00089    
return true;
00090   }
00092
 /// @name Target Fixup Interfaces
00095
 /// getNumFixupKinds - Get the number of target specific fixup kinds.
00096  
virtual unsigned getNumFixupKinds() const = 0;
00097
00098
 /// getFixupKindInfo - Get information on a fixup kind.
00099  
virtual const MCFixupKindInfo &getFixupKindInfo(MCFixupKind Kind) const;
…................// some other fixup methods
00115  
virtual void applyFixup(const MCFixup &Fixup, char *Data, unsigned DataSize,
00116                           uint64_t
 Value) const = 0;
00129
 /// fixupNeedsRelaxation - Target specific predicate for whether a given
00130
 /// fixup requires the associated instruction to be relaxed.
00131  
virtual bool fixupNeedsRelaxation(const MCFixup &Fixup,
00132                                     uint64_t
 Value,
00133                                    
const MCInstFragment *DF,
00134                                    
const MCAsmLayout &Layout) const = 0;
00136
 /// RelaxInstruction - Relax the instruction in the given fragment to the next
00137
 /// wider instruction.
00142  
virtual void relaxInstruction(const MCInst &Inst, MCInst &Res) const = 0;
00151  virtual unsigned getMinimumNopSize() const { return 1; }
00153
 /// writeNopData - Write an (optimal) nop sequence of Count bytes to the given
00154
 /// output. If the target cannot generate such a sequence, it should return error.
00158  
virtual bool writeNopData(uint64_t Count, MCObjectWriter *OW) const = 0;
00160
 /// handleAssemblerFlag - Handle any target-specific assembler flags.
00161
 /// By default, do nothing.
00162  virtual void handleAssemblerFlag(MCAssemblerFlag Flag) {}
00163 };

The implementation of the MCAsmBackend class is left empty to be filled by a subclass. This class is inherited by various target-specific subclasses including MipsAsmBackend, ARMAsmBackend, X86AsmBackend,PPCAsmBackend,MBlazeAsmBackend. For each target,i.e., architecture, there are further derived classes. For example, for ARMAsmBackend,  there are ELFARMAsmBackend and DarwinARMAsmBackend subclass.

All of these subclasses do not have header files thus the LLVM document does not generate a class inheritance hierarchy diagram. The following code related to ARMAsmBackend is selected from the ARMAsmBackend.cpp file:

00041 class ARMAsmBackend : public MCAsmBackend {
00042  
const MCSubtargetInfo* STI;
00043  
bool isThumbMode;  // Currently emitting Thumb code.
00044
public:
00045   ARMAsmBackend(
const Target &T, const StringRef TT)
00046     :
 MCAsmBackend(), STI(ARM_MC::createARMMCSubtargetInfo(TT, "", "")),
00047       isThumbMode(TT.startswith(
"thumb")) {}
00048
00049   ~ARMAsmBackend() {
00050    
delete STI;
00051   }

00160 bool ARMAsmBackend::mayNeedRelaxation(const MCInst &Inst) const {
00161  
if (getRelaxedOpcode(Inst.getOpcode()) != Inst.getOpcode())
00162    
return true;
00163  
return false;
00164 }

00166 bool ARMAsmBackend::fixupNeedsRelaxation(const MCFixup &Fixup,
00167                                          uint64_t
 Value,
00168                                          
const MCInstFragment *DF,
00169                                          
const MCAsmLayout &Layout) const {
00170  
switch ((unsigned)Fixup.getKind()) {
00171  
case ARM::fixup_arm_thumb_br: {
00172    
// Relaxing tB to t2B. tB has a signed 12-bit displacement with the
00173    
// low bit being an implied zero. There's an implied +4 offset for the
00174    
// branch, so we adjust the other way here to determine what's
00175    
// encodable.
00176    
//
00177    
// Relax if the value is too big for a (signed) i8.
00178     int64_t Offset = int64_t(Value) - 4;
00179    
return Offset > 2046 || Offset < -2048;
00180   }
00181  
case ARM::fixup_arm_thumb_bcc: {
00182    
// Relaxing tBcc to t2Bcc. tBcc has a signed 9-bit displacement with the
00183    
// low bit being an implied zero. There's an implied +4 offset for the
00184    
// branch, so we adjust the other way here to determine what's
00185    
// encodable.
00186    
//
00187    
// Relax if the value is too big for a (signed) i8.
00188     int64_t Offset = int64_t(Value) - 4;
00189    
return Offset > 254 || Offset < -256;
00190   }
00191  
case ARM::fixup_thumb_adr_pcrel_10:
00192  
case ARM::fixup_arm_thumb_cp: {
00193    
// If the immediate is negative, greater than 1020, or not a multiple
00194    
// of four, the wide version of the instruction must be used.
00195     int64_t Offset = int64_t(Value) - 4;
00196    
return Offset > 1020 || Offset < 0 || Offset & 3;
00197   }
00198   }
00199  
 llvm_unreachable("Unexpected fixup kind in fixupNeedsRelaxation()!");
00200 }
00201
00202
void ARMAsmBackend::relaxInstruction(const MCInst &Inst, MCInst &Res) const {
00203  
unsigned RelaxedOp = getRelaxedOpcode(Inst.getOpcode());
00204
00205  
// Sanity check w/ diagnostic if we get here w/ a bogus instruction.
00206  
if (RelaxedOp == Inst.getOpcode()) {
00207    
 SmallString<256> Tmp;
00208    
 raw_svector_ostream OS(Tmp);
00209     Inst.
dump_pretty(OS);
00210     OS <<
"\n";
00211    
 report_fatal_error("unexpected instruction to relax: " + OS.str());
00212   }
00213
00214  
// The instructions we're relaxing have (so far) the same operands.
00215  
// We just need to update to the proper opcode.
00216   Res = Inst;
00217   Res.
setOpcode(RelaxedOp);
00218 }
00219
00220
bool ARMAsmBackend::writeNopData(uint64_t Count, MCObjectWriter *OW) const {
00221  
const uint16_t Thumb1_16bitNopEncoding = 0x46c0; // using MOV r8,r8
00222  
const uint16_t Thumb2_16bitNopEncoding = 0xbf00; // NOP
00223  
const uint32_t ARMv4_NopEncoding = 0xe1a00000; // using MOV r0,r0
00224  
const uint32_t ARMv6T2_NopEncoding = 0xe320f000; // NOP
00225  
if (isThumb()) {
00226    
const uint16_t nopEncoding = hasNOP() ? Thumb2_16bitNopEncoding
00227                                           : Thumb1_16bitNopEncoding;
00228     uint64_t NumNops = Count / 2;
00229    
for (uint64_t i = 0; i != NumNops; ++i)
00230       OW->
Write16(nopEncoding);
00231    
if (Count & 1)
00232       OW->
Write8(0);
00233    
return true;
00234   }
00235  
// ARM mode
00236  
const uint32_t nopEncoding = hasNOP() ? ARMv6T2_NopEncoding
00237                                         : ARMv4_NopEncoding;
00238   uint64_t NumNops = Count / 4;
00239  
for (uint64_t i = 0; i != NumNops; ++i)
00240     OW->
Write32(nopEncoding);
00241  
// FIXME: should this function return false when unable to write exactly
00242  
// 'Count' bytes with NOP encodings?
00243  
switch (Count % 4) {
00244  
default: break; // No leftover bytes to write
00245  
case 1: OW->Write8(0); break;
00246  
case 2: OW->Write16(0); break;
00247  
case 3: OW->Write16(0); OW->Write8(0xa0); break;
00248   }
00249
00250  
return true;
00251 }

00522 void ARMAsmBackend::processFixupValue(const MCAssembler &Asm,
00523                                      
const MCAsmLayout &Layout,
00524                                      
const MCFixup &Fixup,
00525                                      
const MCFragment *DF,
00526                                      
 MCValue &Target, uint64_t &Value,
00527                                      
bool &IsResolved) {
00528  
const MCSymbolRefExpr *A = Target.getSymA();
00529  
// Some fixups to thumb function symbols need the low bit (thumb bit)
00530  
// twiddled.
00531  
if ((unsigned)Fixup.getKind() != ARM::fixup_arm_ldst_pcrel_12 &&
00532       (
unsigned)Fixup.getKind() != ARM::fixup_t2_ldst_pcrel_12 &&
00533       (
unsigned)Fixup.getKind() != ARM::fixup_arm_adr_pcrel_12 &&
00534       (
unsigned)Fixup.getKind() != ARM::fixup_thumb_adr_pcrel_10 &&
00535       (
unsigned)Fixup.getKind() != ARM::fixup_t2_adr_pcrel_12 &&
00536       (
unsigned)Fixup.getKind() != ARM::fixup_arm_thumb_cp) {
00537    
if (A) {
00538      
const MCSymbol &Sym = A->getSymbol().AliasedSymbol();
00539      
if (Asm.isThumbFunc(&Sym))
00540         Value |= 1;
00541     }
00542   }
00543  
// We must always generate a relocation for BL/BLX instructions if we have
00544  
// a symbol to reference, as the linker relies on knowing the destination
00545  
// symbol's thumb-ness to get interworking right.
00546  
if (A && ((unsigned)Fixup.getKind() == ARM::fixup_arm_thumb_blx ||
00547             (
unsigned)Fixup.getKind() == ARM::fixup_arm_thumb_bl ||
00548             (
unsigned)Fixup.getKind() == ARM::fixup_arm_blx ||
00549             (
unsigned)Fixup.getKind() == ARM::fixup_arm_uncondbl ||
00550             (
unsigned)Fixup.getKind() == ARM::fixup_arm_condbl))
00551     IsResolved =
false;
00552
00553  
// Try to get the encoded value for the fixup as-if we're mapping it into
00554  
// the instruction. This allows adjustFixupValue() to issue a diagnostic
00555  
// if the value aren't invalid.
00556   (void)
adjustFixupValue(Fixup, Value, &Asm.getContext());
00557 }

00607 void ARMAsmBackend::applyFixup(const MCFixup &Fixup, char *Data,
00608                                
unsigned DataSize, uint64_t Value) const {
00609  
unsigned NumBytes = getFixupKindNumBytes(Fixup.getKind());
00610   Value =
 adjustFixupValue(Fixup, Value);
00611  
if (!Value) return;           // Doesn't change encoding.
00613  
unsigned Offset = Fixup.getOffset();
00614   assert(Offset + NumBytes <= DataSize &&
"Invalid fixup offset!");
00616  
// For each byte of the fragment that the fixup touches, mask in the bits from
00617  
// the fixup value. The Value has been "split up" into the appropriate
00618  
// bitfields above.
00619  
for (unsigned i = 0; i != NumBytes; ++i)
00620     Data[Offset + i] |= uint8_t((Value >> (i * 8)) & 0xff);
00621 }

We’ll dive deeper and try to put things together using one target-specific example (X86 or ARM) in Part 8.  

Part 7.4.3  MCContext

The MCContext class

The MCContext class is the owner of a variety of uniqued data structures at the MC layer, including symbols, sections, etc. As such, this is the class that you interact with to create symbols and sections. This class can not be subclassed.”

Context object for machine code objects. This class owns all of the sections that it creates.

Put the interface here:

00042  class MCContext {
00043    
 MCContext(const MCContext&) LLVM_DELETED_FUNCTION;
00044    
 MCContext &operator=(const MCContext&) LLVM_DELETED_FUNCTION;
00045  
public:
00046     typedef StringMap<MCSymbol*, BumpPtrAllocator&> SymbolTable;
00047  
private:
00048
   /// The SourceMgr for this object, if any.
00049    
const SourceMgr *SrcMgr;
00051
   /// The MCAsmInfo for this target.
00052    
const MCAsmInfo &MAI;
00054
   /// The MCRegisterInfo for this target.
00055    
const MCRegisterInfo &MRI;
00057
   /// The MCObjectFileInfo for this target.
00058    
const MCObjectFileInfo *MOFI;
00066
   /// Symbols - Bindings of names to symbols.
00067  
 SymbolTable Symbols;
00069
   /// UsedNames - Keeps tracks of names that were used both for used declared
00070
   /// and artificial symbols.
00071  
 StringMap<bool, BumpPtrAllocator&> UsedNames;
00073
   /// NextUniqueID - The next ID to dole out to an unnamed assembler temporary
00074
   /// symbol.
00075    
unsigned NextUniqueID;
00077
   /// Instances of directional local labels.
00078  
 DenseMap<unsigned, MCLabel *> Instances;
00079
   /// NextInstance() creates the next instance of the directional local label
00080
   /// for the LocalLabelVal and adds it to the map if needed.
00081    
unsigned NextInstance(int64_t LocalLabelVal);
00082
   /// GetInstance() gets the current instance of the directional local label
00083
   /// for the LocalLabelVal and adds it to the map if needed.
00084    
unsigned GetInstance(int64_t LocalLabelVal); 
00086
   /// The file name of the log file from the environment variable
00087
   /// AS_SECURE_LOG_FILE.  Which must be set before the .secure_log_unique
00088
   /// directive is used or it is an error.
00089    
char *SecureLogFile;
00090
   /// The stream that gets written to for the .secure_log_unique directive.
00091  
 raw_ostream *SecureLog;
00095    
bool SecureLogUsed;
00097
   /// The compilation directory to use for DW_AT_comp_dir.
00098    std::string CompilationDir;
00100
   /// The main file name if passed in explicitly.
00101    std::string MainFileName;
00103
   /// The dwarf file and directory tables from the dwarf .file directive.
00104    std::vector<MCDwarfFile *> MCDwarfFiles;
00105     std::vector<StringRef> MCDwarfDirs;
00107
   /// The current dwarf line information from the last dwarf .loc directive.
00108  
 MCDwarfLoc CurrentDwarfLoc;
00109    
bool DwarfLocSeen;
00111
   /// Generate dwarf debugging info for assembly source files.
00112    
bool GenDwarfForAssembly;
00114
   /// The current dwarf file number when generate dwarf debugging info for
00115
   /// assembly source files.
00116    
unsigned GenDwarfFileNumber;
00118
   /// The default initial text section that we generate dwarf debugging line
00119
   /// info for when generating dwarf assembly source files.
00120    
const MCSection *GenDwarfSection;
00121
   /// Symbols created for the start and end of this section.
00122  
 MCSymbol *GenDwarfSectionStartSym, *GenDwarfSectionEndSym;
00124
   /// The information gathered from labels that will have dwarf label
00125
   /// entries when generating dwarf assembly source files.
00126    std::vector<const MCGenDwarfLabelEntry *> MCGenDwarfLabelEntries;
00130  
 StringRef DwarfDebugFlags;
00135    
bool AllowTemporaryLabels;
00149    
 MCSymbol *CreateSymbol(StringRef Name);

Part 7.4.4  MCSymbol

The MCSymbol class

The MCSymbol class represents a symbol (aka label) in the assembly file. There are two interesting kinds of symbols: assembler temporary symbols, and normal symbols. Assembler temporary symbols are used and processed by the assembler but are discarded when the object file is produced. The distinction is usually represented by adding a prefix to the label, for example “L” labels are assembler temporary labels in MachO.

MCSymbols are created by MCContext and uniqued there. This means that MCSymbols can be compared for pointer equivalence to find out if they are the same symbol. Note that pointer inequality does not guarantee the labels will end up at different addresses though. It’s perfectly legal to output something like this to the .s file:

foo:
bar:
 .byte 4

In this case, both the foo and bar symbols will have the same address.”

MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created and unique'd by the MCContext class.  MCSymbols should only be constructed with valid names for the object file. If the symbol is defined/emitted into the current translation unit, the Section member is set to indicate what section it lives in.  Otherwise, if it is a reference to an external entity, it has a null section.

The interface of MCSymbol is as follows:

00033  class MCSymbol {
00037    
static const MCSection *AbsolutePseudoSection;
00039    /// Name - The name of the symbol.  The referred-to string data is actually
00040    /// held by the StringMap that lives in MCContext.
00041  
 StringRef Name;
00043    /// Section - The section the symbol is defined in. This is null for
00044    /// undefined symbols, and the special AbsolutePseudoSection value for
00045    /// absolute symbols.
00046    
const MCSection *Section;
00048    /// Value - If non-null, the value for a variable symbol.
00049    
const MCExpr *Value;
00051    /// IsTemporary - True if this is an assembler temporary label, which
00052    /// typically does not survive in the .o file's symbol table.  Usually
00053    /// "Lfoo" or ".foo".
00054    
unsigned IsTemporary : 1;
00056    /// IsUsed - True if this symbol has been used.
00057    
mutable unsigned IsUsed : 1;
00059  
private:  // MCContext creates and uniques these.
00060     friend class MCExpr;
00061     friend class MCContext;
00062    
 MCSymbol(StringRef name, bool isTemporary)
00063       :
 Name(name), Section(0), Value(0),
00064         IsTemporary(isTemporary), IsUsed(
false) {}
00066    
 MCSymbol(const MCSymbol&) LLVM_DELETED_FUNCTION;
00067    
void operator=(const MCSymbol&) LLVM_DELETED_FUNCTION;
00068   public:
00069    /// getName - Get the symbol name.
00070    StringRef getName() const { return Name; }
00075    /// isTemporary - Check if this is an assembler temporary symbol.
00076    bool isTemporary() const { return IsTemporary; }
00078    /// isUsed - Check if this is used.
00079    bool isUsed() const { return IsUsed; }
00080     void setUsed(bool Value) const { IsUsed = Value; }
00086    /// isDefined - Check if this symbol is defined (i.e., it has an address).
00088    /// Defined symbols are either absolute or in some section.
00089    bool isDefined() const {
00090      
return Section != 0;
00091     }
00093    /// isInSection - Check if this symbol is defined in some section (i.e., it
00094    /// is defined but not absolute).
00095    bool isInSection() const {
00096      
return isDefined() && !isAbsolute();
00097     }
00099    /// isUndefined - Check if this symbol undefined (i.e., implicitly defined).
00100    bool isUndefined() const {
00101      
return !isDefined();
00102     }
00104    /// isAbsolute - Check if this is an absolute symbol.
00105    bool isAbsolute() const {
00106      
return Section == AbsolutePseudoSection;
00107     }
00109    /// getSection - Get the section associated with a defined, non-absolute symbol.
00111    const MCSection &getSection() const {
00112       assert(
isInSection() && "Invalid accessor!");
00113      
return *Section;
00114     }
00116    /// setSection - Mark the symbol as defined in the section \p S.
00117    void setSection(const MCSection &S) { Section = &S; }
00119    /// setUndefined - Mark the symbol as undefined.
00120    void setUndefined() {
00121      
 Section = 0;
00122     }
00124    /// setAbsolute - Mark the symbol as absolute.
00125    void setAbsolute() { Section = AbsolutePseudoSection; }
00131    /// isVariable - Check if this is a variable symbol.
00132    bool isVariable() const {
00133      
return Value != 0;
00134     }
00136    /// getVariableValue() - Get the value for variable symbols.
00137    const MCExpr *getVariableValue() const {
00138       assert(
isVariable() && "Invalid accessor!");
00139       IsUsed =
true;
00140      
return Value;
00141     }
00143     // AliasedSymbol() - If this is an alias (a = b), return the symbol
00144     // we ultimately point to.
00146    
const MCSymbol &AliasedSymbol() const;
00148    
void setVariableValue(const MCExpr *Value);
00152    /// print - Print the value to the stream \p OS.
00153    
void print(raw_ostream &OS) const;
00155    /// dump - Print the value to stderr.
00156    
void dump() const;
00157   };

Part 7.4.5  MCSection

The MCSection class

The MCSection class represents an object-file specific section. It is subclassed by object file specific implementations (e.g. MCSectionMachO, MCSectionCOFF, MCSectionELF) and these are created and uniqued by MCContext. The MCStreamer has a notion of the current section, which can be changed with the SwitchToSection method (which corresponds to a ”.section” directive in a .s file).”

Instances of this class represent a uniqued identifier for a section in the current translation unit.  The MCContext class uniques and creates these. Just put the code since it is somewhat self-explained with decent comments for every function:

00028  class MCSection {
00029  
public:
00030     enum SectionVariant {
00031       SV_COFF = 0,
00032       SV_ELF,
00033       SV_MachO
00034     };
00036  
private:
00037    
 MCSection(const MCSection&) LLVM_DELETED_FUNCTION;
00038    
void operator=(const MCSection&) LLVM_DELETED_FUNCTION;
00039   protected:
00040     MCSection(SectionVariant V, SectionKind K) : Variant(V), Kind(K) {}
00041     SectionVariant Variant;
00042     SectionKind Kind;
00043  
public:
00044    
virtual ~MCSection();
00046     SectionKind getKind() const { return Kind; }
00048     SectionVariant getVariant() const { return Variant; }
00050    
virtual void PrintSwitchToSection(const MCAsmInfo &MAI,
00051                                      
 raw_ostream &OS) const = 0;
00053     // Convenience routines to get label names for the beginning/end of a
00054     // section.
00055    
virtual std::string getLabelBeginName() const = 0;
00056    
virtual std::string getLabelEndName() const = 0;
00058    /// isBaseAddressKnownZero - Return true if we know that this section will
00059    /// get a base address of zero.  In cases where we know that this is true we
00060    /// can emit section offsets as direct references to avoid a subtraction
00061    /// from the base of the section, saving a relocation.
00062    virtual bool isBaseAddressKnownZero() const {
00063      
return false;
00064     }
00066     // UseCodeAlign - Return true if a .align directive should use
00067     // "optimized nops" to fill instead of 0s.
00068    
virtual bool UseCodeAlign() const = 0;
00070    /// isVirtualSection - Check whether this section is "virtual", that is
00071    /// has no actual object file contents.
00072    
virtual bool isVirtualSection() const = 0;
00073   };

Part 7.4.6  MCInst

The MCInst class

The MCInst class is a target-independent representation of an instruction. It is a simple class (much more so than MachineInstr) that holds a target-specific opcode and a vector of MCOperands. MCOperand, in turn, is a simple discriminated union of three cases: 1) a simple immediate, 2) a target register ID, 3) a symbolic expression (e.g. “Lfoo-Lbar+42”) as an MCExpr.  MCInst is the common currency used to represent machine instructions at the MC layer. It is the type used by the instruction encoder, the instruction printer, and the type generated by the assembly parser and disassembler.”  Let’s make the above explanation concrete by putting the entire interface of the MCOperand and MCInst class here:

00033 class MCOperand {
00034  
enum MachineOperandType {
00035     kInvalid,                
///< Uninitialized.
00036    kRegister,                
///< Register operand.
00037    kImmediate,              
///< Immediate operand.
00038    kFPImmediate,            
///< Floating-point immediate operand.
00039    kExpr,                    
///< Relocatable immediate operand.
00040    kInst                    
///< Sub-instruction operand.
00041  };
00042  
unsigned char Kind;
00044  
union {
00045     unsigned RegVal;
00046     int64_t ImmVal;
00047     double FPImmVal;
00048     const MCExpr *ExprVal;
00049     const MCInst *InstVal; };
00051
public:
00053   MCOperand() : Kind(kInvalid), FPImmVal(0.0) {}
00055   bool isValid() const { return Kind != kInvalid; }
00056   bool isReg() const { return Kind == kRegister; }
00057   bool isImm() const { return Kind == kImmediate; }
00058   bool isFPImm() const { return Kind == kFPImmediate; }
00059   bool isExpr() const { return Kind == kExpr; }
00060   bool isInst() const { return Kind == kInst; }
00062
 /// getReg - Returns the register number.
00063  unsigned getReg() const {
00064     assert(
isReg() && "This is not a register operand!");
00065    
return RegVal; }
00068
 /// setReg - Set the register number.
00069  void setReg(unsigned Reg) {
00070     assert(
isReg() && "This is not a register operand!");
00071    
 RegVal = Reg; }
00074   int64_t getImm() const {
00075     assert(
isImm() && "This is not an immediate");
00076    
return ImmVal; }
00078   void setImm(int64_t Val) {
00079     assert(
isImm() && "This is not an immediate");
00080    
 ImmVal = Val; }
00083   double getFPImm() const {
00084     assert(
isFPImm() && "This is not an FP immediate");
00085    
return FPImmVal; }
00088   void setFPImm(double Val) {
00089     assert(
isFPImm() && "This is not an FP immediate");
00090    
 FPImmVal = Val; }
00093   const MCExpr *getExpr() const {
00094     assert(
isExpr() && "This is not an expression");
00095    
return ExprVal; }
00097   void setExpr(const MCExpr *Val) {
00098     assert(
isExpr() && "This is not an expression");
00099    
 ExprVal = Val; }
00102   const MCInst *getInst() const {
00103     assert(
isInst() && "This is not a sub-instruction");
00104    
return InstVal; }
00106   void setInst(const MCInst *Val) {
00107     assert(
isInst() && "This is not a sub-instruction");
00108    
 InstVal = Val; }
00111   static MCOperand CreateReg(unsigned Reg) {
00112    
 MCOperand Op;
00113     Op.Kind = kRegister;
00114     Op.
RegVal = Reg;
00115    
return Op; }
00117   static MCOperand CreateImm(int64_t Val) {
00118    
 MCOperand Op;
00119     Op.Kind = kImmediate;
00120     Op.
ImmVal = Val;
00121    
return Op;  }
00123   static MCOperand CreateFPImm(double Val) {
00124    
 MCOperand Op;
00125     Op.Kind = kFPImmediate;
00126     Op.
FPImmVal = Val;
00127    
return Op; }
00129   static MCOperand CreateExpr(const MCExpr *Val) {
00130    
 MCOperand Op;
00131     Op.Kind = kExpr;
00132     Op.
ExprVal = Val;
00133    
return Op; }
00135   static MCOperand CreateInst(const MCInst *Val) {
00136    
 MCOperand Op;
00137     Op.Kind = kInst;
00138     Op.
InstVal = Val;
00139    
return Op; }
00142  
void print(raw_ostream &OS, const MCAsmInfo *MAI) const;
00143  
void dump() const;  };
00146 template <> struct isPodLike<MCOperand> { static const bool value = true; };
00148
/// MCInst - Instances of this class represent a single low-level machine
00149
/// instruction.
00150 class MCInst {
00151  
unsigned Opcode;
00152  
 SMLoc Loc;
00153  
 SmallVector<MCOperand, 8> Operands;
00154
public:
00155   MCInst() : Opcode(0) {}
00157   void setOpcode(unsigned Op) { Opcode = Op; }
00158   unsigned getOpcode() const { return Opcode; }
00160   void setLoc(SMLoc loc) { Loc = loc; }
00161   SMLoc getLoc() const { return Loc; }
00163   const MCOperand &getOperand(unsigned i) const { return Operands[i]; }
00164   MCOperand &getOperand(unsigned i) { return Operands[i]; }
00165   unsigned getNumOperands() const { return Operands.size(); }
00167   void addOperand(const MCOperand &Op) {
00168     Operands.
push_back(Op); }
00171   void clear() { Operands.clear(); }
00172   size_t size() { return Operands.size(); }
00174   typedef SmallVector<MCOperand, 8>::iterator iterator;
00175   iterator begin() { return Operands.begin(); }
00176   iterator end()   { return Operands.end();   }
00177   iterator insert(iterator I, const MCOperand &Op) {
00178    
return Operands.insert(I, Op); }
00181  
void print(raw_ostream &OS, const MCAsmInfo *MAI) const;
00182  
void dump() const;
00184
 /// \brief Dump the MCInst as prettily as possible using the additional MC
00185
 /// structures, if given. Operators are separated by the \p Separator string.
00187  
void dump_pretty(raw_ostream &OS, const MCAsmInfo *MAI = 0,
00188                    
const MCInstPrinter *Printer = 0,
00189                  
 StringRef Separator = " ") const;};

The implementation file for this class just defines the dump() and print() methods in the interface.

Part 7.4.7  MCAsmParser

MCAsmParser class provides a generic assembler parser interface, for use by target specific assembly parsers:

00046 class MCAsmParser {
00047
public:
00048   typedef bool (*DirectiveHandler)(MCAsmParserExtension*, StringRef, SMLoc);
00050
private:
00051  
 MCAsmParser(const MCAsmParser &) LLVM_DELETED_FUNCTION;
00052  
void operator=(const MCAsmParser &) LLVM_DELETED_FUNCTION;
00054  
 MCTargetAsmParser *TargetParser;
00056  
unsigned ShowParsedOperands : 1;
00058 protected:
// Can only create subclasses.
00059  
 MCAsmParser();
00061 public:
00062   virtual ~MCAsmParser();
00064   virtual
void AddDirectiveHandler(MCAsmParserExtension *Object,
00065                                  
 StringRef Directive,
00066                                  
 DirectiveHandler Handler) = 0;
00068   virtual
 SourceMgr &getSourceManager() = 0;
00070   virtual
 MCAsmLexer &getLexer() = 0;
00072   virtual
 MCContext &getContext() = 0;
00074
 /// getStreamer - Return the output streamer for the assembler.
00075  virtual
 MCStreamer &getStreamer() = 0;
00077   MCTargetAsmParser &getTargetParser() const { return *TargetParser; }
00078  
void setTargetParser(MCTargetAsmParser &P);
00080   virtual unsigned getAssemblerDialect() { return 0;}
00081   virtual void setAssemblerDialect(unsigned i) { }
00083   bool getShowParsedOperands() const { return ShowParsedOperands; }
00084   void setShowParsedOperands(bool Value) { ShowParsedOperands = Value; }
00086
 /// Run - Run the parser on the input source buffer.
00087  
virtual bool Run(bool NoInitialTextSection, bool NoFinalize = false) = 0;
00089  
virtual void setParsingInlineAsm(bool V) = 0;
00090  
virtual bool isParsingInlineAsm() = 0;
00092
 /// ParseMSInlineAsm - Parse ms-style inline assembly.
00093  
virtual bool ParseMSInlineAsm(................

…..............
00105  
virtual bool Warning(SMLoc L, const Twine &Msg,
00106                      
 ArrayRef<SMRange> Ranges = ArrayRef<SMRange>()) = 0;
00112  
virtual bool Error(SMLoc L, const Twine &Msg,
00113                    
 ArrayRef<SMRange> Ranges = ArrayRef<SMRange>()) = 0;
00115
 /// Lex - Get the next AsmToken in the stream
00117  
virtual const AsmToken &Lex() = 0;
00119
 /// getTok - Get the current AsmToken from the stream.
00120  
const AsmToken &getTok();
00122
 /// \brief Report an error at the current lexer location.
00123  
bool TokError(const Twine &Msg,
00124                
 ArrayRef<SMRange> Ranges = ArrayRef<SMRange>());
00126
 /// ParseIdentifier - Parse an identifier or string (as a quoted identifier)
00127
 /// and set \p Res to the identifier contents.
00128  
virtual bool ParseIdentifier(StringRef &Res) = 0;
00133  
virtual StringRef ParseStringToEndOfStatement() = 0;
00137  
virtual void EatToEndOfStatement() = 0;
00144  
virtual bool ParseExpression(const MCExpr *&Res, SMLoc &EndLoc) = 0;
00145  
bool ParseExpression(const MCExpr *&Res);
00153  
virtual bool ParseParenExpression(const MCExpr *&Res, SMLoc &EndLoc) = 0;
00161  
virtual bool ParseAbsoluteExpression(int64_t &Res) = 0;
00162 };

Note that class MCAsmParser has a  MCTargetAsmParser *TargetParser member which can be set using the setTargetParser() method:

00026 void MCAsmParser::setTargetParser(MCTargetAsmParser &P) {
00027   assert(!TargetParser &&
"Target parser is already initialized!");
00028   TargetParser = &P;
00029   TargetParser->
Initialize(*this);
00030 }
00031
00032 const AsmToken &MCAsmParser::getTok() {
00033  
return getLexer().getTok();
00034 }

The MCTargetAsmParser object member TargetParser is very important since the MCTargetAsmParser class is inherited by two target specific asm parsers, i.e., ARMAsmParser (defined in llvm-3.1.src\lib\Target\ARM\AsmParser\ARMAsmParser.cpp) and X86AsmParser. These two subclasses provide target specific asm parsing (e.g., register and instruction parsing, etc.) for ARM and X86 and can be use by MCAsmParser and its subclass such as AsmParser.  AsmParser is more complicated and defines a much more detailed asm file parsing interface, yet it is still target-independent. Since it is a subclass of the MCAsmParser class, it can leverage the target specific parsing methods from MCTargetAsmParser and its sub-classes (i.e.,ARMAsmParser and X86AsmParser) to handle target-dependent register operand parsing, instruction parsing, etc. A code snippet from the definition of the AsmParser class (line 1405 and 3099 use target specific parser):

00118 class AsmParser : public MCAsmParser {
00119  
friend class GenericAsmParser;
00120
00121   AsmParser(
const AsmParser &) LLVM_DELETED_FUNCTION;
00122  
void operator=(const AsmParser &) LLVM_DELETED_FUNCTION;
00123 private:
00124  
 AsmLexer Lexer;
00125  
 MCContext &Ctx;
00126  
 MCStreamer &Out;
00127   const
 MCAsmInfo &MAI;
00128  
 SourceMgr &SrcMgr;
00129  
 SourceMgr::DiagHandlerTy SavedDiagHandler;
00130  
void *SavedDiagContext;
00131  
 MCAsmParserExtension *GenericParser;
00132  
 MCAsmParserExtension *PlatformParser;

….............................

00585 const AsmToken &AsmParser::Lex() {
00586  
const AsmToken *tok = &Lexer.Lex();
00587
00588  
if (tok->is(AsmToken::Eof)) {
00589    
// If this is the end of an included file, pop the parent file off the
00590    
// include stack.
00591    
 SMLoc ParentIncludeLoc = SrcMgr.getParentIncludeLoc(CurBuffer);
00592    
if (ParentIncludeLoc != SMLoc()) {
00593       JumpToLoc(ParentIncludeLoc);
00594       tok = &Lexer.Lex();
00595     }
00596   }
00597
00598  
if (tok->is(AsmToken::Error))
00599    
 Error(Lexer.getErrLoc(), Lexer.getErr());
00600
00601  
return *tok;
00602 }

….......................

01113 bool AsmParser::ParseStatement(ParseStatementInfo &Info) {
01114  
if (Lexer.is(AsmToken::EndOfStatement)) {
01115     Out.AddBlankLine();
01116     Lex();
01117    
return false;
01118   }

01121   AsmToken ID = getTok();
01122  
 SMLoc IDLoc = ID.getLoc();
01123  
 StringRef IDVal;

…........................

01355     if (IDVal == ".weak_def_can_be_hidden")
01356      
return ParseDirectiveSymbolAttribute(MCSA_WeakDefAutoPrivate);
01357
01358    
if (IDVal == ".comm" || IDVal == ".common")
01359      
return ParseDirectiveComm(/*IsLocal=*/false);
01360    
if (IDVal == ".lcomm")
01361      
return ParseDirectiveComm(/*IsLocal=*/true);
01362
01363    
if (IDVal == ".abort")
01364      
return ParseDirectiveAbort();
01365    
if (IDVal == ".include")
01366      
return ParseDirectiveInclude();
01367    
if (IDVal == ".incbin")
01368      
return ParseDirectiveIncbin();

…..............................

…..............................

01404   ParseInstructionInfo IInfo(Info.AsmRewrites);
01405  
bool HadError = getTargetParser().ParseInstruction(IInfo, OpcodeStr.str(),
01406                                                      IDLoc,Info.ParsedOperands);

…................................

}

…......................................

02628 bool AsmParser::ParseDirectiveInclude() {
02629  
if (getLexer().isNot(AsmToken::String))
02630    
return TokError("expected string in '.include' directive");
02631
02632   std::string Filename = getTok().getString();
02633  
 SMLoc IncludeLoc = getLexer().getLoc();
02634   Lex();
02635
02636  
if (getLexer().isNot(AsmToken::EndOfStatement))
02637    
return TokError("unexpected token in '.include' directive");
02638
02639  
// Strip the quotes.
02640   Filename = Filename.substr(1, Filename.size()-2);
02641
02642  
// Attempt to switch the lexer to the included file before consuming the end
02643  
// of statement to avoid losing it when we switch.
02644  
if (EnterIncludeFile(Filename)) {
02645    
 Error(IncludeLoc, "Could not find include file '" + Filename + "'");
02646    
return true;
02647   }
02648
02649  
return false;
02650 }

…............

03094 bool GenericAsmParser::ParseRegisterOrRegisterNumber(int64_t &Register,
03095                                                    
 SMLoc DirectiveLoc) {
03096  
unsigned RegNo;
03097
03098  
if (getLexer().isNot(AsmToken::Integer)) {
03099    
if (getParser().getTargetParser().ParseRegister(RegNo, DirectiveLoc,
03100       DirectiveLoc))
03101      
return true;
03102     Register = getContext().getRegisterInfo().getDwarfRegNum(RegNo,
true);
03103   }
else
03104    
return getParser().ParseAbsoluteExpression(Register);
03105
03106  
return false;
03107 }

At a high-level, AsmParser has a Lex() function that invokes its AsmLexer Lexer member to perform the lexing. Based on the lexed token AsmParser parses different components of the asm input by invoking various parsing methods. When necessary, call the target specific parsing methods through getTargetParser().

Part 7.4.8  Implementing An LLVM Integrated Assembler

To put things together, please refer to this simple application notes for implementing an LLVM assembler.

http://www.embecosm.com/appnotes/ean10/ean10-howto-llvmas-1.0.html

Part 7.5  Code generation

This part covers largely the source code lives in llvm-3.1.src\lib\CodeGen and put together  various components introduced in previous chapters.  Get start from the SelectionDAGBuilder class?

Part 7.5.1 SelectionDAG

Part 7.5.1.1 SelectionDAG node

SDNode represents one node in the SelectionDAG. It is defined in llvm-3.x.src/src/include/llvm/CodeGen/SelectionDAGNodes.h (which also defines SDValue and SDUse classes):

00083 //===----------------------------------------------------------------------===//
00084
/// SDValue - Unlike LLVM values, Selection DAG nodes may return multiple
00085
/// values as the result of a computation.  Many nodes return multiple values,
00086
/// from loads (which define a token and a return value) to ADDC (which returns
00087
/// a result and a carry value), to calls (which may return an arbitrary number
00088
/// of values).
00089
///
00090
/// As such, each use of a SelectionDAG computation must indicate the node that
00091
/// computes it as well as which return value to use from that node.  This pair
00092
/// of information is represented with the SDValue value type.
00093
///

00094 class SDValue {
00095  
 SDNode *Node;       // The node defining the value we are using.
00096  
unsigned ResNo;     // Which return value of the node we are using.
00097
public:
00098   SDValue() : Node(0), ResNo(0) {}
00099   SDValue(SDNode *node, unsigned resno) : Node(node), ResNo(resno) {}
00100
00101
 /// get the index which selects a specific result in the SDNode
00102  unsigned getResNo() const { return ResNo; }

….................................................

00210 /// SDUse - Represents a use of a SDNode. This class holds an SDValue,
00211
/// which records the SDNode being used and the result number, a
00212
/// pointer to the SDNode using the value, and Next and Prev pointers,
00213
/// which link together all the uses of an SDNode.
00214
///
00215 class SDUse {
00216
 /// Val - The value being used.
00217
 SDValue Val;
00218
 /// User - The user of this value.
00219
 SDNode *User;
00220
 /// Prev, Next - Pointers to the uses list of the SDNode referred by
00221
 /// this operand.
00222
 SDUse **Prev, *Next;
00223
00224  
 SDUse(const SDUse &U) LLVM_DELETED_FUNCTION;
00225  
void operator=(const SDUse &U) LLVM_DELETED_FUNCTION;
00226
00227
public:
00228   SDUse() : Val(), User(NULL), Prev(NULL), Next(NULL) {}
00229
00230
 /// Normally SDUse will just implicitly convert to an SDValue that it holds.
00231  operator const SDValue&() const { return Val; }

 ….........................................

00312 class SDNode : public FoldingSetNode, public ilist_node<SDNode> {
00313
private:
00314
 /// NodeType - The operation that this node performs.
00316  int16_t NodeType;
00318
 /// OperandsNeedDelete - This is true if OperandList was new[]'d.  If true,
00319
 /// then they will be delete[]'d when the node is destroyed.
00320  uint16_t OperandsNeedDelete : 1;
00322
 /// HasDebugValue - This tracks whether this node has one or more dbg_value
00323
 /// nodes corresponding to it.
00324  uint16_t HasDebugValue : 1;
00326
protected:
00327
 /// SubclassData - This member is defined by this class, but is not used for
00328
 /// anything.  Subclasses can use it to hold whatever state they find useful.
00329
 /// This field is initialized to zero by the ctor.
00330  uint16_t SubclassData : 14;
00332
private:
00333
 /// NodeId - Unique id per SDNode in the DAG.
00334  
int NodeId;
00336
 /// OperandList - The values that are used by this operation.
00338
 SDUse *OperandList;
00340
 /// ValueList - The types of the values this node defines.  SDNode's may
00341
 /// define multiple values simultaneously.
00342  
const EVT *ValueList;
00344
 /// UseList - List of uses for this SDNode.
00345
 SDUse *UseList;
00347
 /// NumOperands/NumValues - The number of entries in the Operand/Value list.
00348  
unsigned short NumOperands, NumValues;
00350
 /// debugLoc - source line information.
00351
 DebugLoc debugLoc;
00353
 /// getValueTypeList - Return a pointer to the specified value type.
00354  
static const EVT *getValueTypeList(EVT VT);
00356   friend class SelectionDAG;
00357   friend struct ilist_traits<SDNode>;
00359
public:
00360  
//===--------------------------------------------------------------------===//
00361  
//  Accessors
00364
 /// getOpcode - Return the SelectionDAG opcode value for this node.
00368  unsigned getOpcode()  const { return (unsigned short)NodeType; }
00370
 /// isTargetOpcode - Test if this node has a target-specific opcode (in the
00371
 /// <target>ISD namespace).
00372  bool isTargetOpcode() const { return NodeType >= ISD::BUILTIN_OP_END; }
00374
 /// isTargetMemoryOpcode - Test if this node has a target-specific
00375
 /// memory-referencing opcode (in the <target>ISD namespace and
00376
 /// greater than FIRST_TARGET_MEMORY_OPCODE).
00377  bool isTargetMemoryOpcode() const {
00378    
return NodeType >= ISD::FIRST_TARGET_MEMORY_OPCODE; }
00381
 /// isMachineOpcode - Test if this node has a post-isel opcode, directly
00382
 /// corresponding to a MachineInstr opcode.
00383  bool isMachineOpcode() const { return NodeType < 0; }
00385
 /// getMachineOpcode - This may only be called if isMachineOpcode returns
00386
 /// true. It returns the MachineInstr opcode value that the node's opcode
00387
 /// corresponds to.
00388  unsigned getMachineOpcode() const {
00389     assert(
isMachineOpcode() && "Not a MachineInstr opcode!");
00390    
return ~NodeType; }
00399
 /// use_empty - Return true if there are no uses of this node.
00401  bool use_empty() const { return UseList == NULL; }
00409
 /// use_size - Return the number of uses of this node. This method takes
00410
 /// time proportional to the number of uses.
00412  size_t use_size() const { return std::distance(use_begin(), use_end()); }
00414
 /// getNodeId - Return the unique node id.
00416  int getNodeId() const { return NodeId; }
00418
 /// setNodeId - Set unique node id.
00419  void setNodeId(int Id) { NodeId = Id; }
00428
 /// use_iterator - This class provides iterator support for SDUse
00429
 /// operands that use a specific SDNode.
00430  class use_iterator
00431     :
public std::iterator<std::forward_iterator_tag, SDUse, ptrdiff_t> {
00432    
 SDUse *Op;
00433    
explicit use_iterator(SDUse *op) : Op(op) {
00434     }
00435     friend class SDNode;
00436  
public:
00437    
typedef std::iterator<std::forward_iterator_tag,
00438                           SDUse, ptrdiff_t>::reference reference;
00439    
typedef std::iterator<std::forward_iterator_tag,
00440                           SDUse, ptrdiff_t>::pointer pointer;
00442     use_iterator(const use_iterator &I) : Op(I.Op) {}
00443     use_iterator() : Op(0) {}
00445     bool operator==(const use_iterator &x) const {
00446      
return Op == x.Op;}
00452
   /// atEnd - return true if this iterator is at the end of uses list.
00453    bool atEnd() const { return Op == 0; }
…............................
00476
   /// getOperandNo - Retrieve the operand # of this use in its user.
00478    unsigned getOperandNo() const {
00479       assert(Op &&
"Cannot dereference end iterator!");
00480      
return (unsigned)(Op - Op->getUser()->OperandList);
00481     }
00482   };
…............................
00494
 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
00495
 /// indicated value.  This method ignores uses of other values defined by this
00496
 /// operation.
00497  
bool hasNUsesOfValue(unsigned NUses, unsigned Value) const;
00499
 /// hasAnyUseOfValue - Return true if there are any use of the indicated
00500
 /// value. This method ignores uses of other values defined by this operation.
00501  
bool hasAnyUseOfValue(unsigned Value) const;
00503
 /// isOnlyUserOf - Return true if this node is the only use of N.
00505  
bool isOnlyUserOf(SDNode *N) const;
00507
 /// isOperandOf - Return true if this node is an operand of N.
00509  
bool isOperandOf(SDNode *N) const;
00511
 /// isPredecessorOf - Return true if this node is a predecessor of N.
00512
 /// NOTE: Implemented on top of hasPredecessor and every bit as
00513
 /// expensive. Use carefully.
00514  bool isPredecessorOf(const SDNode *N) const { return N->hasPredecessor(this); }
00516
 /// hasPredecessor - Return true if N is a predecessor of this node.
00520  
bool hasPredecessor(const SDNode *N) const;
00535
 /// getNumOperands - Return the number of values used by this operation.
00537  unsigned getNumOperands() const { return NumOperands; }
00539
 /// getConstantOperandVal - Helper method returns the integer value of a
00540
 /// ConstantSDNode operand.
00541  uint64_t
 getConstantOperandVal(unsigned Num) const;

In addition to the SDValue, SDUse and SDNode classes, SelectionDAGNodes.h also defines many other classes that inherit the SDNode class.  The entire class inheritance graph for SDNode class is depicted as follows:

Part 7.5.1.2 SelectionDAG class

SelectionDAG class - This is used to represent a portion of an LLVM function in a low-level Data

Dependence DAG representation suitable for instruction selection. This DAG is constructed as the

first step of instruction selection in order to allow implementation of machine specific optimizations

and code simplifications. The representation used by the SelectionDAG is a target-independent

representation, which has some similarities to the GCC RTL representation, but is significantly more

simple, powerful, and is a graph form instead of a linear form.

First, let’s put the most important part of its interface defined in SelectionDAG.h

00130 class SelectionDAG {
00131  
const TargetMachine &TM;
00132  
const TargetLowering &TLI;
00133  
const TargetSelectionDAGInfo &TSI;
00134  
 MachineFunction *MF;
00135  
 LLVMContext *Context;
00136  
 CodeGenOpt::Level OptLevel;
00138
 /// EntryNode - The starting token.
00139
 SDNode EntryNode;
00141
 /// Root - The root of the entire DAG.
00142
 SDValue Root;
00144
 /// AllNodes - A linked list of nodes in the current DAG.
00145
 ilist<SDNode> AllNodes;
00147
 /// NodeAllocatorType - The AllocatorType for allocating SDNodes. We use
00148
 /// pool allocation with recycling.
00149  
typedef RecyclingAllocator<BumpPtrAllocator, SDNode, sizeof(LargestSDNode),
00150                            
 AlignOf<MostAlignedSDNode>::Alignment>
00151    
 NodeAllocatorType;
00153
 /// NodeAllocator - Pool allocation for nodes.
00154
 NodeAllocatorType NodeAllocator;
00156
 /// CSEMap - This structure is used to memoize nodes, automatically performing
00157
 /// CSE with existing nodes when a duplicate is requested.
00158
 FoldingSet<SDNode> CSEMap;
00160
 /// OperandAllocator - Pool allocation for machine-opcode SDNode operands.
00161
 BumpPtrAllocator OperandAllocator;

00163  /// Allocator - Pool allocation for misc. objects that are created once per
00164
 /// SelectionDAG.
00165
 BumpPtrAllocator Allocator;
00167
 /// SDNodeOrdering - The ordering of the SDNodes. It roughly corresponds to
00168
 /// the ordering of the original LLVM instructions.
00169
 SDNodeOrdering *Ordering;
00174
public:
00175
 /// DAGUpdateListener - Clients of various APIs that cause global effects on
00176
 /// the DAG can optionally implement this interface.  This allows the clients
00177
 /// to handle the various sorts of updates that happen.
00179
 /// A DAGUpdateListener automatically registers itself with DAG when it is
00180
 /// constructed, and removes itself when destroyed in RAII fashion.
00181  struct DAGUpdateListener {
00182     DAGUpdateListener *const Next;
00183     SelectionDAG &DAG;
00185     explicit DAGUpdateListener(SelectionDAG &D)
00186       :
 Next(D.UpdateListeners), DAG(D) {
00187      
 DAG.UpdateListeners = this;
00188     }

….............................

/// NodeDeleted - The node N that was deleted and, if E is not null, an
00197
   /// equivalent node E that replaced it.
00198    
virtual void NodeDeleted(SDNode *N, SDNode *E);
00199
00200
   /// NodeUpdated - The node N that was updated.
00201    
virtual void