3.4.3. 指令选择代码的自动生成
LLVM指令选择代码有相当部分是自动生成的（Tablegen目前尚要依靠手写代码来进行特定的处理。未来Tablegen的目标是后端代码完全自动生成——雄伟而野心勃勃的目标！J）。这里生成的文件是X86GenDAGISel.inc（以X86为例）。
122 void DAGISelEmitter::run(raw_ostream&OS) {
123 emitSourceFileHeader("DAG InstructionSelector for the " +
124 CGP.getTargetInfo().getName() + " target", OS);
125
126 OS << "// *** NOTE: This file is#included into the middle of the target\n"
127 << "// *** instruction selectorclass. These functions are really "
128 << "methods.\n\n";
129
130 DEBUG(errs() << "\n\nALL PATTERNSTO MATCH:\n\n";
131 for(CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
132 E = CGP.ptm_end(); I != E; ++I) {
133 errs() << "PATTERN:"; I->getSrcPattern()->dump();
134 errs() << "\nRESULT: "; I->getDstPattern()->dump();
135 errs() << "\n";
136 });
137
138 // Add all thepatterns to a temporary list so we can sort them.
139 std::vector<constPatternToMatch*> Patterns;
140 for(CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
141 I != E; ++I)
142 Patterns.push_back(&*I);
143
144 // We want toprocess the matches in order of minimal cost. Sort the patterns
145 // so the leastcost one is at the start.
146 std::sort(Patterns.begin(), Patterns.end(),PatternSortingPredicate(CGP));
123行的emitSourceFileHeader为生成的文件产生一个文件头，内容大致上是这样的：
/*===- TableGen'erated file-------------------------------------*- C++ -*-===*\
|* *|
|* DAG Instruction Selector for the X86 target *|
|* *|
|* Automatically generated file, do not edit! *|
|* *|
\*===----------------------------------------------------------------------===*/
// *** NOTE: This file is #included into the middleof the target
//*** instruction selector class. Thesefunctions are really methods.
接着在146行对所有的PatternToMatch实例进行排序。
3.4.3.1. PatternToMatch的排序
影响PatternToMatch排序的因素有几个。首先是返回值类型，标量类型好过浮点类型，浮点类型又胜过向量类型。
78 structPatternSortingPredicate {
79 PatternSortingPredicate(CodeGenDAGPatterns&cgp) : CGP(cgp) {}
80 CodeGenDAGPatterns &CGP;
81
82 bool operator()(const PatternToMatch *LHS, constPatternToMatch *RHS) {
83 constTreePatternNode *LHSSrc = LHS->getSrcPattern();
84 constTreePatternNode *RHSSrc = RHS->getSrcPattern();
85
86 MVT LHSVT = (LHSSrc->getNumTypes() != 0? LHSSrc->getType(0) : MVT::Other);
87 MVT RHSVT = (RHSSrc->getNumTypes() != 0? RHSSrc->getType(0) : MVT::Other);
88 if (LHSVT.isVector() != RHSVT.isVector())
89 returnRHSVT.isVector();
90
91 if(LHSVT.isFloatingPoint() != RHSVT.isFloatingPoint())
92 returnRHSVT.isFloatingPoint();
93
94 // Otherwise,if the patterns might both match, sort based on complexity,
95 // which meansthat we prefer to match patterns that cover more nodes in the
96 // input overnodes that cover fewer.
97 int LHSSize = LHS->getPatternComplexity(CGP);
98 int RHSSize =RHS->getPatternComplexity(CGP);
99 if (LHSSize > RHSSize)return true; // LHS -> bigger -> less cost
100 if (LHSSize < RHSSize)return false;
101
102 // If thepatterns have equal complexity, compare generated instruction cost
103 unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(),CGP);
104 unsigned RHSCost =getResultPatternCost(RHS->getDstPattern(), CGP);
105 if (LHSCost < RHSCost)return true;
106 if (LHSCost > RHSCost)return false;
107
108 unsigned LHSPatSize =getResultPatternSize(LHS->getDstPattern(),CGP);
109 unsigned RHSPatSize =getResultPatternSize(RHS->getDstPattern(), CGP);
110 if (LHSPatSize < RHSPatSize)return true;
111 if (LHSPatSize > RHSPatSize)return false;
112
113 // Sort basedon the UID of the pattern, giving us a deterministic ordering
114 // if all othersorting conditions fail.
115 assert(LHS== RHS || LHS->ID != RHS->ID);
116 returnLHS->ID < RHS->ID;
117 }
118 };
其次，匹配模式越复杂越占优。在指令定义的AddedComplexity域可用于描述指令的额外复杂度（默认为0）。下面836行的getAddedComplexity方法获取这个值。
834 int PatternToMatch::
835 getPatternComplexity(const CodeGenDAGPatterns &CGP)const {
836 return getPatternSize(getSrcPattern(), CGP) +getAddedComplexity();
837 }
方法getPatternSize则是获取所谓的模式“尺寸”。TablegGen希望在生成的代码里“大模式”优先于“小模式”匹配。在这里可以看出所谓的“大模式”能匹配更大的DAG，这通常意味着生成更好、更高效的代码。
787 static unsignedgetPatternSize(constTreePatternNode *P,
788 const CodeGenDAGPatterns &CGP) {
789 unsigned Size = 3; // The nodeitself.
790 // If the rootnode is a ConstantSDNode, increases its size.
791 // e.g. (setR32:$dst, 0).
792 if (P->isLeaf() &&isa<IntInit>(P->getLeafValue()))
793 Size += 2;
794
795 // FIXME: This isa hack to statically increase the priority of patterns
796 // which maps asub-dag to a complex pattern. e.g. favors LEA over ADD.
797 // Later we canallow complexity / cost for each pattern to be (optionally)
798 // specified. Toget best possible pattern match we'll need to dynamically
799 // calculate thecomplexity of all patterns a dag can potentially map to.
800 const ComplexPattern *AM =P->getComplexPatternInfo(CGP);
801 if (AM) {
802 Size += AM->getNumOperands() * 3;
803
804 // We don'twant to count any children twice, so return early.
805 returnSize;
806 }
807
808 // If this nodehas some predicate function that must match, it adds to the
809 // complexity ofthis node.
810 if (!P->getPredicateFns().empty())
811 ++Size;
812
813 // Count childrenin the count if they are also nodes.
814 for (unsignedi = 0, e = P->getNumChildren(); i != e; ++i) {
815 TreePatternNode *Child = P->getChild(i);
816 if (!Child->isLeaf() &&Child->getNumTypes() &&
817 Child->getType(0) != MVT::Other)
818 Size += getPatternSize(Child, CGP);
819 else if (Child->isLeaf()) {
820 if(isa<IntInit>(Child->getLeafValue()))
821 Size += 5; // Matches aConstantSDNode (+3) and a specific value (+2).
822 else if(Child->getComplexPatternInfo(CGP))
823 Size += getPatternSize(Child, CGP);
824 else if(!Child->getPredicateFns().empty())
825 ++Size;
826 }
827 }
828
829 return Size;
830 }
如果“大小”不相上下，接着比较目标模板的“代价”。50行的usesCustomInserter如果是1，表示插入该指令需要特殊的支持。显然，目标模板生成的指令越多，代价越大。
41 static unsignedgetResultPatternCost(TreePatternNode *P,
42 CodeGenDAGPatterns &CGP) {
43 if (P->isLeaf()) return0;
44
45 unsigned Cost = 0;
46 Record *Op = P->getOperator();
47 if(Op->isSubClassOf("Instruction")) {
48 Cost++;
49 CodeGenInstruction &II =CGP.getTargetInfo().getInstruction(Op);
50 if (II.usesCustomInserter)
51 Cost += 10;
52 }
53 for (unsignedi = 0, e = P->getNumChildren(); i != e; ++i)
54 Cost +=getResultPatternCost(P->getChild(i), CGP);
55 return Cost;
56 }
如果还是不相上下，接着比较目标模板的“大小”。这次起作用的是Instruction定义里的CodeSize域。
60 static unsignedgetResultPatternSize(TreePatternNode *P,
61 CodeGenDAGPatterns &CGP) {
62 if (P->isLeaf()) return0;
63
64 unsigned Cost = 0;
65 Record *Op = P->getOperator();
66 if(Op->isSubClassOf("Instruction")) {
67 Cost +=Op->getValueAsInt("CodeSize");
68 }
69 for (unsignedi = 0, e = P->getNumChildren(); i != e; ++i)
70 Cost +=getResultPatternSize(P->getChild(i), CGP);
71 return Cost;
72 }
如果这样还是没辙，就只能比较ID了：谁先定义，谁就是老大。