内容简介：LLVM学习笔记（11）
3.3.4. CodeGenRegBank
CodeGenTarget::getRegBank方法为CodeGenTarget实例返回一个CodeGenRegBank对象。213行的llvm::make_unique等同于C++11的std::unique_ptr。
211 CodeGenRegBank & CodeGenTarget::getRegBank () const {
212 if (!RegBank)
213 RegBank = llvm::make_unique<>(Records);
214 return *RegBank;
215 }
CodeGenRegBank的构造函数中会建立描述目标机器寄存器以及寄存器之间的关系的数据结构。CodeGenRegBank定义里有一个SetTheory类型的成员Sets。因此在执行CodeGenRegBank构造函数时，会隐含执行SetTheory的构造函数，同时它还注册了所需的Expandor。
923 CodeGenRegBank::CodeGenRegBank (RecordKeeper&Records) {
924 // Configureregister Sets to understand register classes and tuples.
925 Sets.addFieldExpander("RegisterClass","MemberList");
926 Sets.addFieldExpander("CalleeSavedRegs","SaveList");
927 Sets.addExpander("RegisterTuples",llvm::make_unique<TupleExpander>());
928
929 // Read in the user-defined(named) sub-register indices.
930 // More indiceswill be synthesized later.
931 std::vector<Record*> SRIs =Records.getAllDerivedDefinitions("SubRegIndex");
932 std::sort(SRIs.begin(), SRIs.end(),LessRecord());
933 for (unsignedi = 0, e = SRIs.size(); i != e; ++i)
934 (SRIs[i]);
935 // Buildcomposite maps from ComposedOf fields.
936 for ( auto &Idx : SubRegIndices)
937 Idx.(* this );
938
939 // Read in theregister definitions.
940 std::vector<Record*> Regs =Records.getAllDerivedDefinitions("Register");
941 std::sort(Regs.begin(), Regs.end(),LessRecordRegister());
942 // Assign theenumeration values.
943 for (unsignedi = 0, e = Regs.size(); i != e; ++i)
944 getReg(Regs[i]);
945
946 // Expand tuplesand number the new registers.
947 std::vector<Record*> Tups =
948 Records.getAllDerivedDefinitions("RegisterTuples");
949
950 for (Record*R : Tups) {
951 std::vector<Record *> TupRegs =*Sets.expand(R);
952 std::sort(TupRegs.begin(), TupRegs.end(),LessRecordRegister());
953 for (Record*RC : TupRegs)
954 getReg(RC);
955 }
956
957 // Now all theregisters are known. Build the object graph of explicit
958 //register-register references.
959 for ( auto &Reg : Registers)
960 Reg.(* this );
961
962 // Computeregister name map.
963 for ( auto &Reg : Registers)
964 // FIXME: Thiscould just be RegistersByName[name] = register, except that
965 // causes somefailures in MIPS - perhaps they have duplicate register name
966 // entries? (ormaybe there's a reason for it - I don't know much about this
967 // code, justdrive-by refactoring)
968 RegistersByName.insert(
969 std::make_pair(Reg.TheDef->getValueAsString("AsmName"),&Reg));
970
971 // Precompute allsub-register maps.
972 // This willcreate Composite entries for all inferred sub-register indices.
973 for ( auto &Reg : Registers)
974 Reg.(* this );
975
976 // Infer evenmore sub-registers by combining leading super-registers.
977 for ( auto &Reg : Registers)
978 if (Reg.CoveredBySubRegs)
979 Reg.computeSecondarySubRegs(* this );
980
981 // After thesub-register graph is complete, compute the topologically
982 // orderedSuperRegs list.
983 for ( auto &Reg : Registers)
984 Reg.(* this );
985
986 // Nativeregister units are associated with a leaf register. They've all been
987 // discoverednow.
988 NumNativeRegUnits = RegUnits.size();
989
990 // Read inregister class definitions.
991 std::vector<Record*> RCs =Records.getAllDerivedDefinitions("RegisterClass");
992 if (RCs.empty())
993 PrintFatalError("No 'RegisterClass'subclasses defined!");
994
995 // Allocateuser-defined register classes.
996 for ( auto *RC : RCs) {
997 RegClasses.emplace_back(* this , RC);
998 addToMaps(&RegClasses.back());
999 }
1000
1001 // Infer missingclasses to create a full algebra.
1002 computeInferredRegisterClasses();
1003
1004 // Order registerclasses topologically and assign enum values.
1005 RegClasses.sort(TopoOrderRC);
1006 unsigned i = 0;
1007 for ( auto &RC : RegClasses)
1008 RC.EnumValue = i++;
1009 CodeGenRegisterClass::(* this );
1010 }
上面CodeGenRegBank的getReg，getSubRegIdx方法将寄存器及寄存器索引的DAG对象保存在容器Registers（std::deque<CodeGenRegister>），SubRegIndices（std::deque<CodeGenSubRegIndex>）里。寄存器类别则直接使用容器RegClasses（std::list<CodeGenRegisterClass>）保存。
932行的LessRecord对SubRegIndex派生定义按它们名字字母序升序排序（如果名字中包含数字串，按代表的数值升序排序），因为这样最基本的索引最有可能出现在前面。
3.3.4.1. 复合索引
前面提到通常寄存器定义无需指定ComposedOf与CoveringSubRegIndices这两个域，TableGen可以自己推导。但在复杂情形下则需要明确给出索引的复合关系，比如前面ARM的例子一节中给出的例子，dsub_3由qsub_1与dsub_1复合得到，它用于表示一个寄存器偏移192，长度64字节的可援引部分（子寄存器）。
56 void CodeGenSubRegIndex::updateComponents (CodeGenRegBank&RegBank) {
57 if (!TheDef)
58 return ;
59
60 std::vector<Record*> Comps =TheDef->getValueAsListOfDefs("ComposedOf");
61 if (!Comps.empty()) {
62 if (Comps.size() != 2)
63 PrintFatalError(TheDef->getLoc(),
64 "ComposedOf musthave exactly two entries");
65 CodeGenSubRegIndex *A = RegBank.(Comps[0]);
66 CodeGenSubRegIndex *B =RegBank.getSubRegIdx(Comps[1]);
67 CodeGenSubRegIndex *X = A->(B, this );
68 if (X)
69 PrintFatalError(TheDef->getLoc(),"Ambiguous ComposedOf entries");
70 }
71
72 std::vector<Record*> Parts =
73 TheDef->getValueAsListOfDefs("CoveringSubRegIndices");
74 if (!Parts.empty()) {
75 if (Parts.size() < 2)
76 PrintFatalError(TheDef->getLoc(),
77 "CoveredBySubRegsmust have two or more entries");
78 SmallVector<CodeGenSubRegIndex*, 8>IdxParts;
79 for (unsigned i = 0, e = Parts.size(); i != e; ++i)
80 IdxParts.push_back(RegBank.getSubRegIdx(Parts[i]));
81 RegBank.addConcatSubRegIndex(IdxParts, this );
82 }
83 }
寄存器索引的DAG类是CodeGenSubRegIndex，为了快速从寄存器索引的Record对象找到对应的CodeGenSubRegIndex实例，CodeGenRegBank定义了容器Def2SubRegIdx（类型DenseMap<Record*,CodeGenRegister*>）。CodeGenSubRegIndex::updateComponents 65行的getSubRegIdx方法利用该容器查找子寄存器Record对象对应的CodeGenSubRegIndex实例（类似的，对Register有Def2Reg快速查找容器，及getReg方法；对RegisterClass有Def2RC快速查找容器，及getRegClass方法）：
1019 CodeGenSubRegIndex * CodeGenRegBank::getSubRegIdx (Record*Def) {
1020 CodeGenSubRegIndex *&Idx =Def2SubRegIdx[Def];
1021 if (Idx)
1022 return Idx;
1023 SubRegIndices.emplace_back(Def,SubRegIndices.size() + 1);
1024 Idx = &SubRegIndices.back();
1025 return Idx;
1026 }
CodeGenSubRegIndex使用std::map<CodeGenSubRegIndex*,CodeGenSubRegIndex*, deref<llvm:: less>>类型容器Composed来记录由自己牵头的复合索引。容器的第一个项是另一个组成索引，第二项是得到的复合索引。之所以这样，为了能够检查是否出现了具有歧义的复合定义，另外在后面CodeGenRegister::computeSubRegs的处理中，这样的结构是有利的。
因此在67行，第一个组成索引使用addComposite方法向Composed容器添加这个复合索引记录。
90 CodeGenSubRegIndex * addComposite (CodeGenSubRegIndex*A,
91 CodeGenSubRegIndex *B) {
92 assert (A&& B);
93 std::pair<CompMap::iterator, bool>Ins =
94 Composed.insert(std::make_pair(A, B));
95 // Syntheticsubreg indices that aren't contiguous (for instance ARM
96 // registertuples) don't have a bit range, so it's OK to let
97 //B->Offset == -1. For the other cases, accumulate the offset and set
98 // the sizehere. Only do so if there is no offset yet though.
99 if ((Offset != (uint16_t)-1 &&A->Offset != (uint16_t)-1) &&
100 (B->Offset == (uint16_t)-1)) {
101 B->Offset = Offset + A->Offset;
102 B->Size = A->Size;
103 }
104 return (Ins.second || Ins.first->second == B) ? nullptr
105 : Ins.first->second;
106 }
CoveringSubRegIndices可用于描述哪些索引包含了当前的索引。不过，通常TableGen能自动推导出这些SubRegIndex，不需要明确给出（后面会看到这个过程）。
CodeGenRegBank有一个std::map<SmallVector<CodeGenSubRegIndex*,8>, CodeGenSubRegIndex*>类型的容器ConcatIdx，用于记录这些索引对应子寄存器包含的子寄存器索引。
3.3.4.2. Register DAG
3.3.4.2.1. 寄存器的表示
回到CodeGenRegBank构造函数。接下来处理Register与RegisterTuples。类LessRecordRegister类似的，按名字的字母、数字序升序 排序 寄存器定义。对所有寄存器定义，通过getReg方法向容器Registers添加DAG对象（CodeGenRegister实例）。
至RegisterTuples定义，已经注册的TupleExpander是它的专属，因此调用SetTheory::expand方法来召唤它的expand方法：
541 struct TupleExpander: SetTheory::Expander {
542 void expand (SetTheory&ST, Record *Def, SetTheory::RecSet &Elts) override {
543 std::vector<Record*> Indices =Def->getValueAsListOfDefs("SubRegIndices");
544 unsigned Dim = Indices.size();
545 ListInit *SubRegs =Def->getValueAsListInit("SubRegs");
546 if (Dim != SubRegs->size())
547 PrintFatalError(Def->getLoc(),"SubRegIndices and SubRegs size mismatch");
548 if (Dim < 2)
549 PrintFatalError(Def->getLoc(),
550 "Tuples must have atleast 2 sub-registers");
551
552 // Evaluate thesub-register lists to be zipped.
553 unsigned Length = ~0u;
554 SmallVector<SetTheory::RecSet, 4>Lists(Dim);
555 for (unsigned i = 0; i != Dim; ++i) {
556 ST.evaluate(SubRegs->getElement(i),Lists[i], Def->getLoc());
557 Length = std::min(Length,unsigned(Lists[i].size()));
558 }
559
560 if (Length == 0)
561 return ;
562
563 // Precomputesome types.
564 Record *RegisterCl =Def->getRecords().getClass("Register");
565 RecTy *RegisterRecTy =RecordRecTy::get(RegisterCl);
566 StringInit *BlankName =StringInit::get("");
567
568 // Zip them up.
569 for (unsigned n = 0; n != Length; ++n) {
570 std::string Name;
571 Record *Proto = Lists[0][n];
572 std::vector<Init*> Tuple;
573 unsigned CostPerUse = 0;
574 for (unsigned i = 0; i != Dim; ++i) {
575 Record *Reg = Lists[i][n];
576 if (i) Name += '_';
577 Name += Reg->getName();
578 Tuple.push_back(DefInit::get(Reg));
579 CostPerUse = std::max(CostPerUse,
580 unsigned(Reg->getValueAsInt("CostPerUse")));
581 }
582
583 // Create anew Record representing the synthesized register. This record
584 // is onlyfor consumption by CodeGenRegister, it is not added to the
585 //RecordKeeper.
586 Record *NewReg = new Record(Name, Def->getLoc(), Def->getRecords());
587 Elts.insert(NewReg);
588
589 // Copy Protosuper-classes.
590 ArrayRef<Record *> Supers =Proto->getSuperClasses();
591 ArrayRef<SMRange> Ranges =Proto->getSuperClassRanges();
592 for (unsigned i = 0, e = Supers.size(); i != e; ++i)
593 NewReg->addSuperClass(Supers[i],Ranges[i]);
594
595 // Copy Proto fields.
596 for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) {
597 RecordVal RV =Proto->getValues()[i];
598
599 // Skipexisting fields, like NAME.
600 if(NewReg->getValue(RV.getNameInit()))
601 continue ;
602
603 StringRef Field = RV.getName();
604
605 // Replacethe sub-register list with Tuple.
606 if (Field == "SubRegs")
607 RV.setValue(ListInit::get(Tuple,RegisterRecTy));
608
609 // Providea blank AsmName. MC hacks are required anyway.
610 if (Field == "AsmName")
611 RV.setValue(BlankName);
612
613 //CostPerUse is aggregated from all Tuple members.
614 if (Field == "CostPerUse")
615 RV.setValue(IntInit::get(CostPerUse));
616
617 //Composite registers are always covered by sub-registers.
618 if (Field =="CoveredBySubRegs")
619 RV.setValue(BitInit::get(true));
620
621 // Copyfields from the RegisterTuples def.
622 if (Field == "SubRegIndices"||
623 Field =="CompositeIndices") {
624 NewReg->addValue(*Def->getValue(Field));
625 continue ;
626 }
627
628 // Somefields get their default uninitialized value.
629 if (Field == "DwarfNumbers"||
630 Field == "DwarfAlias" ||
631 Field == "Aliases") {
632 if ( const RecordVal *DefRV = RegisterCl->getValue(Field))
633 NewReg->addValue(*DefRV);
634 continue ;
635 }
636
637 //Everything else is copied from Proto.
638 NewReg->addValue(RV);
639 }
640 }
641 }
642 };
554行的SetTheory::RecSet是std::vector<Record*>的typedef。556行通过SetTheory::evaluate方法对RegisterTuples的SubRegs域中包含的表达式进行求值，获取对应的Register列表，然后在569行的循环里将这些列表中的对应的寄存器合成为一个超级寄存器（参考ARM的例子一节中的例子）。
在生成了所有的CodeGenRegister实例后，在CodeGenRegBank构造函数的959行逐个调用它们的buildObjectGraph方法，进一步完善生成的DAG：
117 void CodeGenRegister::buildObjectGraph (CodeGenRegBank&RegBank) {
118 std::vector<Record*> SRIs =TheDef->getValueAsListOfDefs("SubRegIndices");
119 std::vector<Record*> SRs =TheDef->getValueAsListOfDefs("SubRegs");
120
121 if (SRIs.size() != SRs.size())
122 PrintFatalError(TheDef->getLoc(),
123 "SubRegs andSubRegIndices must have the same size");
124
125 for (unsignedi = 0, e = SRIs.size(); i != e; ++i) {
126 ExplicitSubRegIndices.push_back(RegBank.(SRIs[i]));
127 ExplicitSubRegs.push_back(RegBank.getReg(SRs[i]));
128 }
129
130 // Also computeleading super-registers. Each register has a list of
131 //covered-by-subregs super-registers where it appears as the first explicit
132 // sub-register.
133 //
134 // This is usedby computeSecondarySubRegs() to find candidates.
135 if (CoveredBySubRegs &&!ExplicitSubRegs.empty())
136 ExplicitSubRegs.front()->LeadingSuperRegs.push_back( this );
137
138 // Add ad hocalias links. This is a symmetric relationship between two
139 // registers, sobuild a symmetric graph by adding links in both ends.
140 std::vector<Record*> Aliases =TheDef->getValueAsListOfDefs("Aliases");
141 for (unsignedi = 0, e = Aliases.size(); i != e; ++i) {
142 CodeGenRegister *Reg =RegBank.getReg(Aliases[i]);
143 ExplicitAliases.push_back(Reg);
144 Reg->ExplicitAliases.push_back( this );
145 }
146 }
CodeGenRegister使用容器：ExplicitSubRegIndices（SmallVector<CodeGenSubRegIndex*,8>），ExplicitSubRegs（SmallVector<CodeGenRegister*,8>）来记录对应的子寄存器索引与子寄存器。
135行的CoveredBySubRegs是Register定义中CoveredBySubRegs的值，它如果不为0，表示它的子寄存器能完全覆盖它所有的比特位。在这种情况下，第一个子寄存器的CodeGenRegister实例使用LeadingSuperRegs容器（std::vector<constCodeGenRegister*>）把当前的CodeGenRegister实例记录为以自己为起始的上级寄存器。
另外，同一个寄存器的不同Register定义视做互为“别名”（ARMRegisterInfo.td中有一个例子），这由Register定义中的Aliases域来描述。具体到CodeGenRegister则通过容器ExplicitAliases（类型SmallVector<CodeGenRegister*,8>）来记录。
3.3.4.2.2. 构建子寄存器关系
CodeGenRegBank的容器RegistersByName（StringMap<CodeGenRegister*>）用于将寄存器名关联到CodeGenRegister实例，963行循环完成这个关联。接着，在974行对所有的CodeGenRegister对象，调用方法computeSubRegs来推导它们的子寄存器组成。
CodeGenRegister使用容器SubRegs（std::map<CodeGenSubRegIndex*, CodeGenRegister *, deref< llvm::less>>）记录包含的子寄存器。另外，容器SubReg2Idx（DenseMap<constCodeGenRegister*, CodeGenSubRegIndex*>）关联子寄存器与子寄存器索引。
因此，computeSubRegs的第一步根据上面准备的ExplicitSubRegs与ExplicitSubRegIndices容器，关联起子寄存器与子寄存器索引。
214 const CodeGenRegister::SubRegMap &
215 CodeGenRegister::computeSubRegs (CodeGenRegBank&RegBank) {
216 // Only computethis map once.
217 if (SubRegsComplete)
218 return SubRegs;
219 SubRegsComplete = true;
220
221 HasDisjunctSubRegs = ExplicitSubRegs.size()> 1;
222
223 // First insertthe explicit subregs and make sure they are fully indexed.
224 for (unsignedi = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
225 CodeGenRegister *SR = ExplicitSubRegs[i];
226 CodeGenSubRegIndex *Idx =ExplicitSubRegIndices[i];
227 if (!SubRegs.insert(std::make_pair(Idx,SR)).second)
228 PrintFatalError(TheDef->getLoc(),"SubRegIndex " + Idx->getName() +
229 " appears twice inRegister " + getName());
230 // Map explicitsub-registers first, so the names take precedence.
231 // Theinherited sub-registers are mapped below.
232 SubReg2Idx.insert(std::make_pair(SR, Idx));
233 }
234
235 // Keep track ofinherited subregs and how they can be reached.
236 SmallPtrSet<CodeGenRegister*, 8>Orphans;
237
238 // Clone inheritedsubregs and place duplicate entries in Orphans.
239 // Here the orderis important - earlier subregs take precedence.
240 for (unsignedi = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
241 CodeGenRegister *SR = ExplicitSubRegs[i];
242 const SubRegMap&Map = SR->computeSubRegs(RegBank);
243 HasDisjunctSubRegs |=SR->HasDisjunctSubRegs;
244
245 for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE;
246 ++SI) {
247 if (!SubRegs.insert(*SI).second)
248 Orphans.insert(SI->second);
249 }
250 }
251
252 // Expand anycomposed subreg indices.
253 // If dsub_2 hasComposedOf = [qsub_1, dsub_0], and this register has a
254 // qsub_1 subreg,add a dsub_2 subreg. Keep growingIndices and process
255 // expandedsubreg indices recursively.
256 SmallVector<CodeGenSubRegIndex*, 8>Indices = ExplicitSubRegIndices;
257 for (unsignedi = 0; i != Indices.size(); ++i) {
258 CodeGenSubRegIndex *Idx = Indices[i];
259 const CodeGenSubRegIndex::CompMap &Comps = Idx->getComposites();
260 CodeGenRegister *SR = SubRegs[Idx];
261 const SubRegMap &Map = SR->computeSubRegs(RegBank);
262
263 // Look at thepossible compositions of Idx.
264 // They may notall be supported by SR.
265 for (CodeGenSubRegIndex::CompMap::const_iterator I = Comps.begin(),
266 E = Comps.end(); I != E; ++I) {
267 SubRegMap::const_iterator SRI =Map.find(I->first);
268 if (SRI == Map.end())
269 continue ; // Idx + I->first doesn't exist in SR.
270 // AddI->second as a name for the subreg SRI->second, assuming it is
271 // orphaned,and the name isn't already used for something else.
272 if (SubRegs.count(I->second) ||!Orphans.erase(SRI->second))
273 continue ;
274 // We found anew name for the orphaned sub-register.
275 SubRegs.insert(std::make_pair(I->second, SRI->second));
276 Indices.push_back(I->second);
277 }
278 }
279
280 // Now Orphanscontains the inherited subregisters without a direct index.
281 // Createinferred indexes for all missing entries.
282 // Work backwardsin the Indices vector in order to compose subregs bottom-up.
283 // Consider thissubreg sequence:
284 //
285 // qsub_1 -> dsub_0 -> ssub_0
286 //
287 // The qsub_1-> dsub_0 composition becomes dsub_2, so the ssub_0 register
288 // can be reachedin two different ways:
289 //
290 // qsub_1 -> ssub_0
291 // dsub_2 -> ssub_0
292 //
293 // We pick thelatter composition because another register may have [dsub_0,
294 // dsub_1,dsub_2] subregs without necessarily having a qsub_1 subreg. The
295 // dsub_2 ->ssub_0 composition can be shared.
296 while (!Indices.empty() && !Orphans.empty()) {
297 CodeGenSubRegIndex *Idx =Indices.pop_back_val();
298 CodeGenRegister *SR = SubRegs[Idx];
299 const SubRegMap &Map = SR->computeSubRegs(RegBank);
300 for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE;
301 ++SI)
302 if (Orphans.erase(SI->second))
303 SubRegs[RegBank.getCompositeSubRegIndex(Idx,SI->first)] = SI->second;
304 }
305
306 // Compute theinverse SubReg -> Idx map.
307 for (SubRegMap::const_iterator SI = SubRegs.begin(), SE = SubRegs.end();
308 SI != SE; ++SI) {
309 if (SI->second == this ) {
310 ArrayRef<SMLoc> Loc;
311 if (TheDef)
312 Loc = TheDef->getLoc();
313 PrintFatalError(Loc, "Register" + getName() +
314 " has itself as asub-register");
315 }
316
317 // ComputeAllSuperRegsCovered.
318 if (!CoveredBySubRegs)
319 SI->first->AllSuperRegsCovered =false;
320
321 // Ensure thatevery sub-register has a unique name.
322 DenseMap< const CodeGenRegister*, CodeGenSubRegIndex*>::iterator Ins =
323 SubReg2Idx.insert(std::make_pair(SI->second, SI->first)).first;
324 if (Ins->second == SI->first)
325 continue ;
326 // Trouble: Twodifferent names for SI->second.
327 ArrayRef<SMLoc> Loc;
328 if (TheDef)
329 Loc = TheDef->getLoc();
330 PrintFatalError(Loc, "Sub-registercan't have two names: " +
331 SI->second->getName() +" available as " +
332 SI->first->getName() +" and " + Ins->second->getName());
333 }
334
335 // Derivepossible names for sub-register concatenations from any explicit
336 // sub-registers.By doing this before computeSecondarySubRegs(), we ensure
337 // that getConcatSubRegIndex()won't invent any concatenated indices that the
338 // user alreadyspecified.
339 for (unsignedi = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
340 CodeGenRegister *SR = ExplicitSubRegs[i];
341 if (!SR->CoveredBySubRegs || SR->ExplicitSubRegs.size()<= 1)
342 continue ;
343
344 // SR iscomposed of multiple sub-regs. Find their names in this register.
345 SmallVector<CodeGenSubRegIndex*, 8>Parts;
346 for (unsigned j = 0, e = SR->ExplicitSubRegs.size(); j != e; ++j)
347 Parts.push_back(getSubRegIndex(SR->ExplicitSubRegs[j]));
348
349 // Offer thisas an existing spelling for the concatenation of Parts.
350 RegBank.addConcatSubRegIndex(Parts,ExplicitSubRegIndices[i]);
351 }
352
353 // InitializeRegUnitList. Because getSubRegs is called recursively, this
354 // processes theregister hierarchy in postorder.
355 //
356 // Inherit allsub-register units. It is good enough to look at the explicit
357 // sub-registers,the other registers won't contribute any more units.
358 for (unsignedi = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
359 CodeGenRegister *SR = ExplicitSubRegs[i];
360 RegUnits |= SR->RegUnits;
361 }
362
363 // Absent any adhoc aliasing, we create one register unit per leaf register.
364 // These unitscorrespond to the maximal cliques in the register overlap
365 // graph which isoptimal.
366 //
367 // When there isad hoc aliasing, we simply create one unit per edge in the
368 // undirected adhoc aliasing graph. Technically, we could do better by
369 // identifyingmaximal cliques in the ad hoc graph, but cliques larger than 2
370 // are extremelyrare anyway (I've never seen one), so we don't bother with
371 // the addedcomplexity.
372 for (unsignedi = 0, e = ExplicitAliases.size(); i != e; ++i) {
373 CodeGenRegister *AR = ExplicitAliases[i];
374 // Only visiteach edge once.
375 if (AR->SubRegsComplete)
376 continue ;
377 // Create aRegUnit representing this alias edge, and add it to both
378 // registers.
379 unsigned Unit = RegBank.( this ,AR);
380 RegUnits.set(Unit);
381 AR->RegUnits.set(Unit);
382 }
383
384 // Finally,create units for leaf registers without ad hoc aliases. Note that
385 // a leafregister with ad hoc aliases doesn't get its own unit - it isn't
386 // necessary.This means the aliasing leaf registers can share a single unit.
387 if (RegUnits.empty())
388 RegUnits.set(RegBank.( this ));
389
390 // We have nowcomputed the native register units. More may be adopted later
391 // for balancingpurposes.
392 NativeRegUnits = RegUnits;
393
394 return SubRegs;
395 }
前面提到TableGen能根据寄存器与索引的定义推导寄存器间的层次关系，并合成援引孙子寄存器的索引。比如X86的EAX寄存器，它的SubRegs定义为[AX]，而AX的SubRegs定义为[AL, AH]。对EAX的定义来说，它不知道[AL,AH]的存在。但在汇编代码里使用AL或AH，都是来自EAX的部分。因此我们需要一个索引来表示AL等在EAX中的位置与大小。
240行以下就是实现这个功能。240行的for循环首先让子寄存器递归调用computeSubRegs返回自己的子寄存器与索引，将当前寄存器所不知道的孙子寄存器及其索引记录到Orphans容器。
如果寄存器索引定义中明确使用了ComposedOf来说明组成的索引，我们需要确保组成索引所对应的寄存器及其子寄存器，如果是复合索引所对应寄存器的子寄存器，它们被正确记录。接着257行的for循环执行这个操作。
如果在296行Orphans还存有寄存器，这表示这些寄存器还没有关联索引，那么从已有的索引出发（保存在Indices容器里），遍历所有可能的子索引，找出与Orphans中寄存器对应的索引，并调用下面的方法合成所需的索引（也就是前面提到的推导）。
1071 CodeGenSubRegIndex*
1072 CodeGenRegBank::getCompositeSubRegIndex (CodeGenSubRegIndex*A,
1073 CodeGenSubRegIndex *B) {
1074 // Look for anexisting entry.
1075 CodeGenSubRegIndex *Comp = A->compose(B);
1076 if (Comp)
1077 return Comp;
1078
1079 // None exists,synthesize one.
1080 std::string Name = A->getName() +"_then_" + B->getName();
1081 Comp =(Name,A->getNamespace());
1082 A->(B, Comp);
1083 return Comp;
1084 }
1013 CodeGenSubRegIndex*
1014 CodeGenRegBank::createSubRegIndex (StringRefName, StringRef Namespace) {
1015 SubRegIndices.emplace_back(Name, Namespace,SubRegIndices.size() + 1);
1016 return &SubRegIndices.back();
1017 }
然后307行循环设置SubReg2Idx容器建立子寄存器到索引的映射。
如果寄存器有多级子寄存器可作为独立寄存器使用，且每级有多个子寄存器，那么可能存在寄存器定义中没有（难以）给出的可用子寄存器，339行循环为下面computeSecondarySubRegs中推导这些可用的子寄存器做准备。另外，346行循环将这些个子寄存器的子寄存器索引记录下来，在下面用于隐含孙子寄存器的推导。
最后的代码片段使用了两个RegUnits容器。其一来自CodeGenRegBank，类型是SmallVector<RegUnit, 8>。它用于寄存器压力与干扰模型。
每个最小可援引寄存器部分将分配一个独立的RegUnit实例，其他寄存器继承子寄存器RegUnit。
RegUnit有以下的定义，其中成员Weight用于估算寄存器压力：
435 struct RegUnit {
436 // Weightassigned to this RegUnit for estimating register pressure.
437 // This isuseful when equalizing weights in register classes with mixed
438 // registertopologies.
439 unsigned Weight;
440
441 // Each nativeRegUnit corresponds to one or two root registers. The full
442 // set ofregisters containing this unit can be computed as the union of
443 // these tworegisters and their super-registers.
444 const CodeGenRegister *Roots[2];
445
446 // Index intoRegClassUnitSets where we can find the list of UnitSets that
447 // contain thisunit.
448 unsigned RegClassUnitSetsIdx;
449
450 RegUnit() : Weight(0),RegClassUnitSetsIdx(0) {
451 Roots[0] = Roots[1] = nullptr;
452 }
453
454 ArrayRef< const CodeGenRegister*> getRoots() const {
455 assert (!(Roots[1]&& !Roots[0]) && "Invalid roots array");
456 return makeArrayRef(Roots, !!Roots[0] + !!Roots[1]);
457 }
458 };
方法newRegUnit创建一个RegUnit实例给叶子寄存器。
620 unsigned newRegUnit (CodeGenRegister *R0,CodeGenRegister *R1 = nullptr) {
621 RegUnits.resize(RegUnits.size() + 1);
622 RegUnits.back().Roots[0] = R0;
623 RegUnits.back().Roots[1] = R1;
624 return RegUnits.size() - 1;
625 }
另一个RegUnits容器则来自CodeGenRegister，类型是SparseBitVector<>，它实际上保存了对应RegUnit实例在前一个RegUnits容器中的索引。很明显，非叶子寄存器的RegUnit都继承自它的（孙）子寄存器。
3.3.4.2.3. 隐含的孙子寄存器
前面说过，如果寄存器存在比较复杂的多层可用子寄存器，会存在寄存器定义中没有办法给出的可用子寄存器，前面的computeSubRegs方法已经在CodeGenRegBank的ConcatIdx容器里做好了准备，现在开始调用computeSecondarySubRegs方法来推导这些隐含的子寄存器。比如从定义：QQ0= {Q0, Q1}, Q0 = {D0, D1}, Q1 = {D2, D3}, Q2={D1, D2}，推断出Q2也是QQ0的子寄存器。另外，还要构建从QQ0到Q2的寄存器索引，以及由此引出的所有子寄存器。
410 void CodeGenRegister::computeSecondarySubRegs (CodeGenRegBank&RegBank) {
411 // Collect newsub-registers first, add them later.
412 SmallVector<SubRegMap::value_type, 8>NewSubRegs;
413
414 // Look at theleading super-registers of each sub-register. Those are the
415 // candidates fornew sub-registers, assuming they are fully contained in
416 // this register.
417 for (SubRegMap::iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I){
418 const CodeGenRegister *SubReg = I->second;
419 const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs;
420 for (unsigned i = 0, e = Leads.size(); i != e; ++i) {
421 CodeGenRegister *Cand = const_cast <CodeGenRegister*>(Leads[i]);
422 // Alreadygot this sub-register?
423 if (Cand == this || getSubRegIndex (Cand))
424 continue ;
425 // Check ifeach component of Cand is already a sub-register.
426 // We knowthat the first component is I->second, and is present with the
427 // nameI->first.
428 SmallVector<CodeGenSubRegIndex*, 8>Parts(1, I->first);
429 assert (!Cand->ExplicitSubRegs.empty()&&
430 "Super-register has nosub-registers");
431 for (unsigned j = 1, e = Cand->ExplicitSubRegs.size(); j != e; ++j) {
432 if (CodeGenSubRegIndex *Idx =getSubRegIndex(Cand->ExplicitSubRegs[j]))
433 Parts.push_back(Idx);
434 else {
435 //Sub-register doesn't exist.
436 Parts.clear();
437 break ;
438 }
439 }
440 // If someCand sub-register is not part of this register, or if Cand only
441 // has onesub-register, there is nothing to do.
442 if (Parts.size() <= 1)
443 continue ;
444
445 // Each partof Cand is a sub-register of this. Make the full Cand also
446 // asub-register with a concatenated sub-register index.
447 CodeGenSubRegIndex *Concat= RegBank.(Parts);
448 NewSubRegs.push_back(std::make_pair(Concat,Cand));
449 }
450 }
451
452 // Now add allthe new sub-registers.
453 for (unsignedi = 0, e = NewSubRegs.size(); i != e; ++i) {
454 // Don't addCand if another sub-register is already using the index.
455 if (!SubRegs.insert(NewSubRegs[i]).second)
456 continue ;
457
458 CodeGenSubRegIndex *NewIdx =NewSubRegs[i].first;
459 CodeGenRegister *NewSubReg =NewSubRegs[i].second;
460 SubReg2Idx.insert(std::make_pair(NewSubReg,NewIdx));
461 }
462
463 // Create sub-registerindex composition maps for the synthesized indices.
464 for (unsignedi = 0, e = NewSubRegs.size(); i != e; ++i) {
465 CodeGenSubRegIndex *NewIdx =NewSubRegs[i].first;
466 CodeGenRegister *NewSubReg =NewSubRegs[i].second;
467 for (SubRegMap::const_iteratorSI = NewSubReg->SubRegs.begin(),
468 SE = NewSubReg->SubRegs.end(); SI!= SE; ++SI) {
469 CodeGenSubRegIndex *SubIdx =getSubRegIndex(SI->second);
470 if (!SubIdx)
471 PrintFatalError(TheDef->getLoc(),"No SubRegIndex for " +
472 SI->second->getName() + " in " + getName());
473 NewIdx->addComposite(SI->first,SubIdx);
474 }
475 }
476 }
419行的LeadingSuperRegs容器记录了该寄存器作为领头子寄存器的寄存器，其中SuperRegList是std::vector<constCodeGenRegister*>的typedef。以前面的例子来说，D0的LeadingSuperRegs容器包含了Q0，D1则包含Q2，D2包含Q1。对这个例子，一定是QQ0在执行417行的循环才有可能找出D1_D2这个子寄存器。而对于QQ0，目前它的子寄存器包括：Q0，Q1，D0，D1，D2及D3。在420行循环遍历这些子寄存器的上级寄存器。423行的判定如果成立，表示上级寄存器是当前寄存器，或者上级寄存器已知，否则在431行遍历、保存该上级寄存器除第一个的所有子寄存器索引。这里，ConcatIdx中有Q2的子寄存器索引集合，与从QQ0得到的D1与D2索引集合一致，因此如果这个复合索引还没创建，getConcatSubRegIndex方法将合成、返回它，同时记录在ConcatIdx容器里，使该子寄存器索引唯一。
1086 CodeGenSubRegIndex *CodeGenRegBank::
1087 getConcatSubRegIndex ( const SmallVector<CodeGenSubRegIndex *, 8>&Parts) {
1088 assert (Parts.size()> 1 && "Need two parts to concatenate");
1089
1090 // Look for anexisting entry.
1091 CodeGenSubRegIndex *&Idx =ConcatIdx[Parts];
1092 if (Idx)
1093 return Idx;
1094
1095 // None exists,synthesize one.
1096 std::string Name = Parts.front()->getName();
1097 // Determinewhether all parts are contiguous.
1098 bool isContinuous = true;
1099 unsigned Size = Parts.front()->Size;
1100 unsigned LastOffset =Parts.front()->Offset;
1101 unsigned LastSize = Parts.front()->Size;
1102 for (unsignedi = 1, e = Parts.size(); i != e; ++i) {
1103 Name += '_';
1104 Name += Parts[i]->getName();
1105 Size += Parts[i]->Size;
1106 if (Parts[i]->Offset != (LastOffset +LastSize))
1107 isContinuous = false;
1108 LastOffset = Parts[i]->Offset;
1109 LastSize = Parts[i]->Size;
1110 }
1111 Idx = createSubRegIndex(Name,Parts.front()->getNamespace());
1112 Idx->Size = Size;
1113 Idx->Offset = isContinuous ?Parts.front()->Offset : -1;
1114 return Idx;
1115 }
NewSubRegs只是一个临时容器。在453行的循环，它的内容被转移到了正式的SubReg2Idx容器。最后，以我们的例子来说，从QQ0访问Q2部分的索引已经建立，在464行循环进一步构建从QQ0访问Q2子寄存器的复合索引。
3.3.4.2.4. 构建上级寄存器关系
向下搞清楚了子寄存器与相关索引后，接下来就要向上搞清楚哪些寄存器是上级寄存器。
CodeGenRegister通过容器SuperRegs（std::vector<constCodeGenRegister*>）记录包含自己的上级寄存器。上级寄存器的枚举工作由下面的computeSuperRegs方法完成。
478 void CodeGenRegister::computeSuperRegs (CodeGenRegBank&RegBank) {
479 // Only visiteach register once.
480 if (SuperRegsComplete)
481 return ;
482 SuperRegsComplete = true;
483
484 // Make sure allsub-registers have been visited first, so the super-reg
485 // lists will betopologically ordered.
486 for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
487 I != E; ++I)
488 I->second->computeSuperRegs(RegBank);
489
490 // Now add thisas a super-register on all sub-registers.
491 // Also computethe TopoSigId in post-order.
492 TopoSigId Id;
493 for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
494 I != E; ++I) {
495 // Topologicalsignature computed from SubIdx, TopoId(SubReg).
496 // Loops andidempotent indices have TopoSig = ~0u.
497 Id.push_back(I->first->EnumValue);
498 Id.push_back(I->second->TopoSig);
499
500 // Don't addduplicate entries.
501 if (!I->second->SuperRegs.empty()&& I->second->SuperRegs.back() == this )
502 continue ;
503 I->second->SuperRegs.push_back( this );
504 }
505 TopoSig = RegBank.(Id);
506 }
在497行，CodeGenSubRegIndex的成员EnumValue实际上是该CodeGenSubRegIndex对象添加到CodeGenRegBank的SubRegIndices容器时的序号。而498行的TopoSig是在488行的computeSuperRegs递归调用里计算好的。对当前CodeGenRegister，由505行的getTopoSig方法计算TopoSig。
614 unsigned getTopoSig (const TopoSigId &Id) {
615 return TopoSigs.insert(std::make_pair(Id, TopoSigs.size())).first->second;
616 }
TopoSigs是std::map<TopoSigId, unsigned>类型的容器，TopoSigId是SmallVector<unsigned,16>的typedef。显然，getTopoSig方法返回的是参数Id在TopoSigs容器中的序号，这个序号接着返回给了当前CodeGenRegister对象的TopoSig。因为，Id的内容来自子寄存器，而且不同的叶子寄存器有不同的EnumValue（来自CodeGenSubRegIndex）与TopoSig（来自CodeGenRegister），因此，拥有相同TopoSig值的寄存器，一定具有相同的子寄存器结构。
以上所述就是小编给大家介绍的《LLVM学习笔记（11）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Mathematica Cookbook
Sal Mangano / O'Reilly Media / 2009 / GBP 51.99
As the leading software application for symbolic mathematics, Mathematica is standard in many environments that rely on math, such as science, engineering, financial analysis, software development, an......一起来看看 《Mathematica Cookbook》 这本书的介绍吧!
