After legalization and DAG combination, the SelectionDAG representation is in the optimized phase. However, the instructions represented are still target-independent and need to be mapped on target-specific instructions. The instruction selection phase takes the target-independent DAG nodes as the input, matches patterns in them, and gives the output DAG nodes, which are target-specific.
The TableGen DAG instruction selector generator reads the instruction patterns from the .td file, and automatically builds parts of the pattern matching code.
SelectionDAGISel is the common base class used for pattern-matching instruction selectors that are based on SelectionDAG. It inherits the MachineFunctionPass class. It has various functions used to determine the legality and profitability of operations such as folding. The basic skeleton of this class is as follows:
class SelectionDAGISel : public MachineFunctionPass {
public:
const TargetMachine &TM;
const TargetLowering &TLI;
const TargetLibraryInfo *LibInfo;
FunctionLoweringInfo *FuncInfo;
MachineFunction *MF;
MachineRegisterInfo *RegInfo;
SelectionDAG *CurDAG;
SelectionDAGBuilder *SDB;
AliasAnalysis *AA;
GCFunctionInfo *GFI;
CodeGenOpt::Level OptLevel;
static char ID;
explicit SelectionDAGISel(const TargetMachine &tm,
CodeGenOpt::Level OL = CodeGenOpt::Default);
virtual ~SelectionDAGISel();
const TargetLowering &getTargetLowering() { return TLI; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual void EmitFunctionEntryCode() {}
virtual void PreprocessISelDAG() {}
virtual void PostprocessISelDAG() {}
virtual SDNode *Select(SDNode *N) = 0;
virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
char ConstraintCode,
std::vector<SDValue> &OutOps) {
return true;
}
virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const;
static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
CodeGenOpt::Level OptLevel,
bool IgnoreChains = false);
enum BuiltinOpcodes {
OPC_Scope,
OPC_RecordNode,
OPC_CheckOpcode,
OPC_SwitchOpcode,
OPC_CheckFoldableChainNode,
OPC_EmitInteger,
OPC_EmitRegister,
OPC_EmitRegister2,
OPC_EmitConvertToTarget,
OPC_EmitMergeInputChains,
};
static inline int getNumFixedFromVariadicInfo(unsigned Flags) {
return ((Flags&OPFL_VariadicInfo) >> 4)-1;
}
protected:
// DAGSize - Size of DAG being instruction selected.
unsigned DAGSize;
void ReplaceUses(SDValue F, SDValue T) {
CurDAG->ReplaceAllUsesOfValueWith(F, T);
}
void ReplaceUses(const SDValue *F, const SDValue *T, unsigned Num) {
CurDAG->ReplaceAllUsesOfValuesWith(F, T, Num);
}
void ReplaceUses(SDNode *F, SDNode *T) {
CurDAG->ReplaceAllUsesWith(F, T);
}
void SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops);
public:
bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const;
bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
int64_t DesiredMaskS) const;
virtual bool CheckPatternPredicate(unsigned PredNo) const {
llvm_unreachable("Tblgen should generate the implementation of this!");
}
virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {
llvm_unreachable("Tblgen should generate the implementation of this!");
}
private:
SDNode *Select_INLINEASM(SDNode *N);
SDNode *Select_UNDEF(SDNode *N);
void CannotYetSelect(SDNode *N);
void DoInstructionSelection();
SDNode *MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTs,
const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo);
void PrepareEHLandingPad();
void SelectAllBasicBlocks(const Function &Fn);
bool TryToFoldFastISelLoad(const LoadInst *LI, const Instruction *FoldInst, FastISel *FastIS);
void FinishBasicBlock();
void SelectBasicBlock(BasicBlock::const_iterator Begin,
BasicBlock::const_iterator End,
bool &HadTailCall);
void CodeGenAndEmitDAG();
void LowerArguments(const BasicBlock *BB);
void ComputeLiveOutVRegInfo();
ScheduleDAGSDNodes *CreateScheduler();
};The instruction selection phase involves converting target-independent instructions to target-specific instructions. The TableGen class helps select target-specific instructions. This phase basically matches target-independent input nodes, which gives an output consisting of target-supported nodes.
The CodeGenAndEmitDAG() function calls the DoInstructionSelection() function, which visits each DAG node and calls the Select() function for each node, like this:
SDNode *ResNode = Select(Node);
The Select() function is an abstract method implemented by the targets. The x86 target implements it in the X86DAGToDAGISel::Select() function. The X86DAGToDAGISel::Select() function intercepts some nodes for manual matching, but delegates the bulk of the work to the X86DAGToDAGISel::SelectCode() function.
The X86DAGToDAGISel::SelectCode function is autogenerated by TableGen. It contains the matcher table, followed by a call to the generic SelectionDAGISel::SelectCodeCommon() function, passing it the table.
For example:
$ cat test.ll
define i32 @test(i32 %a, i32 %b, i32 %c) {
%add = add nsw i32 %a, %b
%div = sdiv i32 %add, %c
ret i32 %div
}To see the DAG before instruction selection, enter the following command line:
$ llc –view-isel-dags test.ll
The following figure shows the DAG before the instruction selection:
To see how DAG looks like after the instruction selection, enter the following command:
$ llc –view-sched-dags test.ll
The following figure shows the DAG after the instruction selection:
As seen, the Load operation is converted into the MOV32rm machine code by the instruction selection phase.