LLVM学习笔记(11)

栏目: 服务器 · 编程工具 · 发布时间: 7年前

内容简介: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)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构与算法

数据结构与算法

许卓群、杨冬青、唐世渭、张铭 / 高等教育出版社 / 2004-1 / 29.50元

《数据结构与算法》把数据结构的原理和算法分析技术有机地结合在一起,系统地介绍了各种类型的数据结构和排序、检索的各种算法,还引入了一些比较高级的数据结构及相关的算法分析技术。.《数据结构与算法》分为基本数据结构、排序和检索、高级数据结构三部分。借助抽象数据类型,从逻辑结构的角度系统地介绍了线性表、字符串、二叉树、树和图等各种基本数据结构;从算法的角度讨论排序、检索和索引算法;从应用的角度介绍了一些复......一起来看看 《数据结构与算法》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试