CodeGenRegisters.cpp 91 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450
  1. //===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This file defines structures to encapsulate information gleaned from the
  10. // target register and register class definitions.
  11. //
  12. //===----------------------------------------------------------------------===//
  13. #include "CodeGenRegisters.h"
  14. #include "CodeGenTarget.h"
  15. #include "llvm/ADT/ArrayRef.h"
  16. #include "llvm/ADT/BitVector.h"
  17. #include "llvm/ADT/DenseMap.h"
  18. #include "llvm/ADT/IntEqClasses.h"
  19. #include "llvm/ADT/SetVector.h"
  20. #include "llvm/ADT/SmallPtrSet.h"
  21. #include "llvm/ADT/SmallSet.h"
  22. #include "llvm/ADT/SmallVector.h"
  23. #include "llvm/ADT/STLExtras.h"
  24. #include "llvm/ADT/StringExtras.h"
  25. #include "llvm/ADT/StringRef.h"
  26. #include "llvm/ADT/Twine.h"
  27. #include "llvm/Support/Debug.h"
  28. #include "llvm/Support/MathExtras.h"
  29. #include "llvm/Support/raw_ostream.h"
  30. #include "llvm/TableGen/Error.h"
  31. #include "llvm/TableGen/Record.h"
  32. #include <algorithm>
  33. #include <cassert>
  34. #include <cstdint>
  35. #include <iterator>
  36. #include <map>
  37. #include <queue>
  38. #include <set>
  39. #include <string>
  40. #include <tuple>
  41. #include <utility>
  42. #include <vector>
  43. using namespace llvm;
  44. #define DEBUG_TYPE "regalloc-emitter"
  45. //===----------------------------------------------------------------------===//
  46. // CodeGenSubRegIndex
  47. //===----------------------------------------------------------------------===//
  48. CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum)
  49. : TheDef(R), EnumValue(Enum), AllSuperRegsCovered(true), Artificial(true) {
  50. Name = std::string(R->getName());
  51. if (R->getValue("Namespace"))
  52. Namespace = std::string(R->getValueAsString("Namespace"));
  53. Size = R->getValueAsInt("Size");
  54. Offset = R->getValueAsInt("Offset");
  55. }
  56. CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,
  57. unsigned Enum)
  58. : TheDef(nullptr), Name(std::string(N)), Namespace(std::string(Nspace)),
  59. Size(-1), Offset(-1), EnumValue(Enum), AllSuperRegsCovered(true),
  60. Artificial(true) {}
  61. std::string CodeGenSubRegIndex::getQualifiedName() const {
  62. std::string N = getNamespace();
  63. if (!N.empty())
  64. N += "::";
  65. N += getName();
  66. return N;
  67. }
  68. void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) {
  69. if (!TheDef)
  70. return;
  71. std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf");
  72. if (!Comps.empty()) {
  73. if (Comps.size() != 2)
  74. PrintFatalError(TheDef->getLoc(),
  75. "ComposedOf must have exactly two entries");
  76. CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);
  77. CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);
  78. CodeGenSubRegIndex *X = A->addComposite(B, this);
  79. if (X)
  80. PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries");
  81. }
  82. std::vector<Record*> Parts =
  83. TheDef->getValueAsListOfDefs("CoveringSubRegIndices");
  84. if (!Parts.empty()) {
  85. if (Parts.size() < 2)
  86. PrintFatalError(TheDef->getLoc(),
  87. "CoveredBySubRegs must have two or more entries");
  88. SmallVector<CodeGenSubRegIndex*, 8> IdxParts;
  89. for (Record *Part : Parts)
  90. IdxParts.push_back(RegBank.getSubRegIdx(Part));
  91. setConcatenationOf(IdxParts);
  92. }
  93. }
  94. LaneBitmask CodeGenSubRegIndex::computeLaneMask() const {
  95. // Already computed?
  96. if (LaneMask.any())
  97. return LaneMask;
  98. // Recursion guard, shouldn't be required.
  99. LaneMask = LaneBitmask::getAll();
  100. // The lane mask is simply the union of all sub-indices.
  101. LaneBitmask M;
  102. for (const auto &C : Composed)
  103. M |= C.second->computeLaneMask();
  104. assert(M.any() && "Missing lane mask, sub-register cycle?");
  105. LaneMask = M;
  106. return LaneMask;
  107. }
  108. void CodeGenSubRegIndex::setConcatenationOf(
  109. ArrayRef<CodeGenSubRegIndex*> Parts) {
  110. if (ConcatenationOf.empty())
  111. ConcatenationOf.assign(Parts.begin(), Parts.end());
  112. else
  113. assert(std::equal(Parts.begin(), Parts.end(),
  114. ConcatenationOf.begin()) && "parts consistent");
  115. }
  116. void CodeGenSubRegIndex::computeConcatTransitiveClosure() {
  117. for (SmallVectorImpl<CodeGenSubRegIndex*>::iterator
  118. I = ConcatenationOf.begin(); I != ConcatenationOf.end(); /*empty*/) {
  119. CodeGenSubRegIndex *SubIdx = *I;
  120. SubIdx->computeConcatTransitiveClosure();
  121. #ifndef NDEBUG
  122. for (CodeGenSubRegIndex *SRI : SubIdx->ConcatenationOf)
  123. assert(SRI->ConcatenationOf.empty() && "No transitive closure?");
  124. #endif
  125. if (SubIdx->ConcatenationOf.empty()) {
  126. ++I;
  127. } else {
  128. I = ConcatenationOf.erase(I);
  129. I = ConcatenationOf.insert(I, SubIdx->ConcatenationOf.begin(),
  130. SubIdx->ConcatenationOf.end());
  131. I += SubIdx->ConcatenationOf.size();
  132. }
  133. }
  134. }
  135. //===----------------------------------------------------------------------===//
  136. // CodeGenRegister
  137. //===----------------------------------------------------------------------===//
  138. CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
  139. : TheDef(R),
  140. EnumValue(Enum),
  141. CostPerUse(R->getValueAsInt("CostPerUse")),
  142. CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")),
  143. HasDisjunctSubRegs(false),
  144. SubRegsComplete(false),
  145. SuperRegsComplete(false),
  146. TopoSig(~0u) {
  147. Artificial = R->getValueAsBit("isArtificial");
  148. }
  149. void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
  150. std::vector<Record*> SRIs = TheDef->getValueAsListOfDefs("SubRegIndices");
  151. std::vector<Record*> SRs = TheDef->getValueAsListOfDefs("SubRegs");
  152. if (SRIs.size() != SRs.size())
  153. PrintFatalError(TheDef->getLoc(),
  154. "SubRegs and SubRegIndices must have the same size");
  155. for (unsigned i = 0, e = SRIs.size(); i != e; ++i) {
  156. ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i]));
  157. ExplicitSubRegs.push_back(RegBank.getReg(SRs[i]));
  158. }
  159. // Also compute leading super-registers. Each register has a list of
  160. // covered-by-subregs super-registers where it appears as the first explicit
  161. // sub-register.
  162. //
  163. // This is used by computeSecondarySubRegs() to find candidates.
  164. if (CoveredBySubRegs && !ExplicitSubRegs.empty())
  165. ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this);
  166. // Add ad hoc alias links. This is a symmetric relationship between two
  167. // registers, so build a symmetric graph by adding links in both ends.
  168. std::vector<Record*> Aliases = TheDef->getValueAsListOfDefs("Aliases");
  169. for (Record *Alias : Aliases) {
  170. CodeGenRegister *Reg = RegBank.getReg(Alias);
  171. ExplicitAliases.push_back(Reg);
  172. Reg->ExplicitAliases.push_back(this);
  173. }
  174. }
  175. StringRef CodeGenRegister::getName() const {
  176. assert(TheDef && "no def");
  177. return TheDef->getName();
  178. }
  179. namespace {
  180. // Iterate over all register units in a set of registers.
  181. class RegUnitIterator {
  182. CodeGenRegister::Vec::const_iterator RegI, RegE;
  183. CodeGenRegister::RegUnitList::iterator UnitI, UnitE;
  184. public:
  185. RegUnitIterator(const CodeGenRegister::Vec &Regs):
  186. RegI(Regs.begin()), RegE(Regs.end()) {
  187. if (RegI != RegE) {
  188. UnitI = (*RegI)->getRegUnits().begin();
  189. UnitE = (*RegI)->getRegUnits().end();
  190. advance();
  191. }
  192. }
  193. bool isValid() const { return UnitI != UnitE; }
  194. unsigned operator* () const { assert(isValid()); return *UnitI; }
  195. const CodeGenRegister *getReg() const { assert(isValid()); return *RegI; }
  196. /// Preincrement. Move to the next unit.
  197. void operator++() {
  198. assert(isValid() && "Cannot advance beyond the last operand");
  199. ++UnitI;
  200. advance();
  201. }
  202. protected:
  203. void advance() {
  204. while (UnitI == UnitE) {
  205. if (++RegI == RegE)
  206. break;
  207. UnitI = (*RegI)->getRegUnits().begin();
  208. UnitE = (*RegI)->getRegUnits().end();
  209. }
  210. }
  211. };
  212. } // end anonymous namespace
  213. // Return true of this unit appears in RegUnits.
  214. static bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) {
  215. return RegUnits.test(Unit);
  216. }
  217. // Inherit register units from subregisters.
  218. // Return true if the RegUnits changed.
  219. bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) {
  220. bool changed = false;
  221. for (const auto &SubReg : SubRegs) {
  222. CodeGenRegister *SR = SubReg.second;
  223. // Merge the subregister's units into this register's RegUnits.
  224. changed |= (RegUnits |= SR->RegUnits);
  225. }
  226. return changed;
  227. }
  228. const CodeGenRegister::SubRegMap &
  229. CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
  230. // Only compute this map once.
  231. if (SubRegsComplete)
  232. return SubRegs;
  233. SubRegsComplete = true;
  234. HasDisjunctSubRegs = ExplicitSubRegs.size() > 1;
  235. // First insert the explicit subregs and make sure they are fully indexed.
  236. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  237. CodeGenRegister *SR = ExplicitSubRegs[i];
  238. CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i];
  239. if (!SR->Artificial)
  240. Idx->Artificial = false;
  241. if (!SubRegs.insert(std::make_pair(Idx, SR)).second)
  242. PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() +
  243. " appears twice in Register " + getName());
  244. // Map explicit sub-registers first, so the names take precedence.
  245. // The inherited sub-registers are mapped below.
  246. SubReg2Idx.insert(std::make_pair(SR, Idx));
  247. }
  248. // Keep track of inherited subregs and how they can be reached.
  249. SmallPtrSet<CodeGenRegister*, 8> Orphans;
  250. // Clone inherited subregs and place duplicate entries in Orphans.
  251. // Here the order is important - earlier subregs take precedence.
  252. for (CodeGenRegister *ESR : ExplicitSubRegs) {
  253. const SubRegMap &Map = ESR->computeSubRegs(RegBank);
  254. HasDisjunctSubRegs |= ESR->HasDisjunctSubRegs;
  255. for (const auto &SR : Map) {
  256. if (!SubRegs.insert(SR).second)
  257. Orphans.insert(SR.second);
  258. }
  259. }
  260. // Expand any composed subreg indices.
  261. // If dsub_2 has ComposedOf = [qsub_1, dsub_0], and this register has a
  262. // qsub_1 subreg, add a dsub_2 subreg. Keep growing Indices and process
  263. // expanded subreg indices recursively.
  264. SmallVector<CodeGenSubRegIndex*, 8> Indices = ExplicitSubRegIndices;
  265. for (unsigned i = 0; i != Indices.size(); ++i) {
  266. CodeGenSubRegIndex *Idx = Indices[i];
  267. const CodeGenSubRegIndex::CompMap &Comps = Idx->getComposites();
  268. CodeGenRegister *SR = SubRegs[Idx];
  269. const SubRegMap &Map = SR->computeSubRegs(RegBank);
  270. // Look at the possible compositions of Idx.
  271. // They may not all be supported by SR.
  272. for (CodeGenSubRegIndex::CompMap::const_iterator I = Comps.begin(),
  273. E = Comps.end(); I != E; ++I) {
  274. SubRegMap::const_iterator SRI = Map.find(I->first);
  275. if (SRI == Map.end())
  276. continue; // Idx + I->first doesn't exist in SR.
  277. // Add I->second as a name for the subreg SRI->second, assuming it is
  278. // orphaned, and the name isn't already used for something else.
  279. if (SubRegs.count(I->second) || !Orphans.erase(SRI->second))
  280. continue;
  281. // We found a new name for the orphaned sub-register.
  282. SubRegs.insert(std::make_pair(I->second, SRI->second));
  283. Indices.push_back(I->second);
  284. }
  285. }
  286. // Now Orphans contains the inherited subregisters without a direct index.
  287. // Create inferred indexes for all missing entries.
  288. // Work backwards in the Indices vector in order to compose subregs bottom-up.
  289. // Consider this subreg sequence:
  290. //
  291. // qsub_1 -> dsub_0 -> ssub_0
  292. //
  293. // The qsub_1 -> dsub_0 composition becomes dsub_2, so the ssub_0 register
  294. // can be reached in two different ways:
  295. //
  296. // qsub_1 -> ssub_0
  297. // dsub_2 -> ssub_0
  298. //
  299. // We pick the latter composition because another register may have [dsub_0,
  300. // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The
  301. // dsub_2 -> ssub_0 composition can be shared.
  302. while (!Indices.empty() && !Orphans.empty()) {
  303. CodeGenSubRegIndex *Idx = Indices.pop_back_val();
  304. CodeGenRegister *SR = SubRegs[Idx];
  305. const SubRegMap &Map = SR->computeSubRegs(RegBank);
  306. for (const auto &SubReg : Map)
  307. if (Orphans.erase(SubReg.second))
  308. SubRegs[RegBank.getCompositeSubRegIndex(Idx, SubReg.first)] = SubReg.second;
  309. }
  310. // Compute the inverse SubReg -> Idx map.
  311. for (const auto &SubReg : SubRegs) {
  312. if (SubReg.second == this) {
  313. ArrayRef<SMLoc> Loc;
  314. if (TheDef)
  315. Loc = TheDef->getLoc();
  316. PrintFatalError(Loc, "Register " + getName() +
  317. " has itself as a sub-register");
  318. }
  319. // Compute AllSuperRegsCovered.
  320. if (!CoveredBySubRegs)
  321. SubReg.first->AllSuperRegsCovered = false;
  322. // Ensure that every sub-register has a unique name.
  323. DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*>::iterator Ins =
  324. SubReg2Idx.insert(std::make_pair(SubReg.second, SubReg.first)).first;
  325. if (Ins->second == SubReg.first)
  326. continue;
  327. // Trouble: Two different names for SubReg.second.
  328. ArrayRef<SMLoc> Loc;
  329. if (TheDef)
  330. Loc = TheDef->getLoc();
  331. PrintFatalError(Loc, "Sub-register can't have two names: " +
  332. SubReg.second->getName() + " available as " +
  333. SubReg.first->getName() + " and " + Ins->second->getName());
  334. }
  335. // Derive possible 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 already specified.
  339. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  340. CodeGenRegister *SR = ExplicitSubRegs[i];
  341. if (!SR->CoveredBySubRegs || SR->ExplicitSubRegs.size() <= 1 ||
  342. SR->Artificial)
  343. continue;
  344. // SR is composed 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. CodeGenSubRegIndex &I = *SR->ExplicitSubRegIndices[j];
  348. if (!I.Artificial)
  349. Parts.push_back(getSubRegIndex(SR->ExplicitSubRegs[j]));
  350. }
  351. // Offer this as an existing spelling for the concatenation of Parts.
  352. CodeGenSubRegIndex &Idx = *ExplicitSubRegIndices[i];
  353. Idx.setConcatenationOf(Parts);
  354. }
  355. // Initialize RegUnitList. Because getSubRegs is called recursively, this
  356. // processes the register hierarchy in postorder.
  357. //
  358. // Inherit all sub-register units. It is good enough to look at the explicit
  359. // sub-registers, the other registers won't contribute any more units.
  360. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  361. CodeGenRegister *SR = ExplicitSubRegs[i];
  362. RegUnits |= SR->RegUnits;
  363. }
  364. // Absent any ad hoc aliasing, we create one register unit per leaf register.
  365. // These units correspond to the maximal cliques in the register overlap
  366. // graph which is optimal.
  367. //
  368. // When there is ad hoc aliasing, we simply create one unit per edge in the
  369. // undirected ad hoc aliasing graph. Technically, we could do better by
  370. // identifying maximal cliques in the ad hoc graph, but cliques larger than 2
  371. // are extremely rare anyway (I've never seen one), so we don't bother with
  372. // the added complexity.
  373. for (unsigned i = 0, e = ExplicitAliases.size(); i != e; ++i) {
  374. CodeGenRegister *AR = ExplicitAliases[i];
  375. // Only visit each edge once.
  376. if (AR->SubRegsComplete)
  377. continue;
  378. // Create a RegUnit representing this alias edge, and add it to both
  379. // registers.
  380. unsigned Unit = RegBank.newRegUnit(this, AR);
  381. RegUnits.set(Unit);
  382. AR->RegUnits.set(Unit);
  383. }
  384. // Finally, create units for leaf registers without ad hoc aliases. Note that
  385. // a leaf register 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.newRegUnit(this));
  389. // We have now computed the native register units. More may be adopted later
  390. // for balancing purposes.
  391. NativeRegUnits = RegUnits;
  392. return SubRegs;
  393. }
  394. // In a register that is covered by its sub-registers, try to find redundant
  395. // sub-registers. For example:
  396. //
  397. // QQ0 = {Q0, Q1}
  398. // Q0 = {D0, D1}
  399. // Q1 = {D2, D3}
  400. //
  401. // We can infer that D1_D2 is also a sub-register, even if it wasn't named in
  402. // the register definition.
  403. //
  404. // The explicitly specified registers form a tree. This function discovers
  405. // sub-register relationships that would force a DAG.
  406. //
  407. void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
  408. SmallVector<SubRegMap::value_type, 8> NewSubRegs;
  409. std::queue<std::pair<CodeGenSubRegIndex*,CodeGenRegister*>> SubRegQueue;
  410. for (std::pair<CodeGenSubRegIndex*,CodeGenRegister*> P : SubRegs)
  411. SubRegQueue.push(P);
  412. // Look at the leading super-registers of each sub-register. Those are the
  413. // candidates for new sub-registers, assuming they are fully contained in
  414. // this register.
  415. while (!SubRegQueue.empty()) {
  416. CodeGenSubRegIndex *SubRegIdx;
  417. const CodeGenRegister *SubReg;
  418. std::tie(SubRegIdx, SubReg) = SubRegQueue.front();
  419. SubRegQueue.pop();
  420. const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs;
  421. for (unsigned i = 0, e = Leads.size(); i != e; ++i) {
  422. CodeGenRegister *Cand = const_cast<CodeGenRegister*>(Leads[i]);
  423. // Already got this sub-register?
  424. if (Cand == this || getSubRegIndex(Cand))
  425. continue;
  426. // Check if each component of Cand is already a sub-register.
  427. assert(!Cand->ExplicitSubRegs.empty() &&
  428. "Super-register has no sub-registers");
  429. if (Cand->ExplicitSubRegs.size() == 1)
  430. continue;
  431. SmallVector<CodeGenSubRegIndex*, 8> Parts;
  432. // We know that the first component is (SubRegIdx,SubReg). However we
  433. // may still need to split it into smaller subregister parts.
  434. assert(Cand->ExplicitSubRegs[0] == SubReg && "LeadingSuperRegs correct");
  435. assert(getSubRegIndex(SubReg) == SubRegIdx && "LeadingSuperRegs correct");
  436. for (CodeGenRegister *SubReg : Cand->ExplicitSubRegs) {
  437. if (CodeGenSubRegIndex *SubRegIdx = getSubRegIndex(SubReg)) {
  438. if (SubRegIdx->ConcatenationOf.empty())
  439. Parts.push_back(SubRegIdx);
  440. else
  441. append_range(Parts, SubRegIdx->ConcatenationOf);
  442. } else {
  443. // Sub-register doesn't exist.
  444. Parts.clear();
  445. break;
  446. }
  447. }
  448. // There is nothing to do if some Cand sub-register is not part of this
  449. // register.
  450. if (Parts.empty())
  451. continue;
  452. // Each part of Cand is a sub-register of this. Make the full Cand also
  453. // a sub-register with a concatenated sub-register index.
  454. CodeGenSubRegIndex *Concat = RegBank.getConcatSubRegIndex(Parts);
  455. std::pair<CodeGenSubRegIndex*,CodeGenRegister*> NewSubReg =
  456. std::make_pair(Concat, Cand);
  457. if (!SubRegs.insert(NewSubReg).second)
  458. continue;
  459. // We inserted a new subregister.
  460. NewSubRegs.push_back(NewSubReg);
  461. SubRegQueue.push(NewSubReg);
  462. SubReg2Idx.insert(std::make_pair(Cand, Concat));
  463. }
  464. }
  465. // Create sub-register index composition maps for the synthesized indices.
  466. for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) {
  467. CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
  468. CodeGenRegister *NewSubReg = NewSubRegs[i].second;
  469. for (SubRegMap::const_iterator SI = NewSubReg->SubRegs.begin(),
  470. SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) {
  471. CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second);
  472. if (!SubIdx)
  473. PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " +
  474. SI->second->getName() + " in " + getName());
  475. NewIdx->addComposite(SI->first, SubIdx);
  476. }
  477. }
  478. }
  479. void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) {
  480. // Only visit each register once.
  481. if (SuperRegsComplete)
  482. return;
  483. SuperRegsComplete = true;
  484. // Make sure all sub-registers have been visited first, so the super-reg
  485. // lists will be topologically ordered.
  486. for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
  487. I != E; ++I)
  488. I->second->computeSuperRegs(RegBank);
  489. // Now add this as a super-register on all sub-registers.
  490. // Also compute the TopoSigId in post-order.
  491. TopoSigId Id;
  492. for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
  493. I != E; ++I) {
  494. // Topological signature computed from SubIdx, TopoId(SubReg).
  495. // Loops and idempotent indices have TopoSig = ~0u.
  496. Id.push_back(I->first->EnumValue);
  497. Id.push_back(I->second->TopoSig);
  498. // Don't add duplicate entries.
  499. if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this)
  500. continue;
  501. I->second->SuperRegs.push_back(this);
  502. }
  503. TopoSig = RegBank.getTopoSig(Id);
  504. }
  505. void
  506. CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
  507. CodeGenRegBank &RegBank) const {
  508. assert(SubRegsComplete && "Must precompute sub-registers");
  509. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
  510. CodeGenRegister *SR = ExplicitSubRegs[i];
  511. if (OSet.insert(SR))
  512. SR->addSubRegsPreOrder(OSet, RegBank);
  513. }
  514. // Add any secondary sub-registers that weren't part of the explicit tree.
  515. for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
  516. I != E; ++I)
  517. OSet.insert(I->second);
  518. }
  519. // Get the sum of this register's unit weights.
  520. unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const {
  521. unsigned Weight = 0;
  522. for (RegUnitList::iterator I = RegUnits.begin(), E = RegUnits.end();
  523. I != E; ++I) {
  524. Weight += RegBank.getRegUnit(*I).Weight;
  525. }
  526. return Weight;
  527. }
  528. //===----------------------------------------------------------------------===//
  529. // RegisterTuples
  530. //===----------------------------------------------------------------------===//
  531. // A RegisterTuples def is used to generate pseudo-registers from lists of
  532. // sub-registers. We provide a SetTheory expander class that returns the new
  533. // registers.
  534. namespace {
  535. struct TupleExpander : SetTheory::Expander {
  536. // Reference to SynthDefs in the containing CodeGenRegBank, to keep track of
  537. // the synthesized definitions for their lifetime.
  538. std::vector<std::unique_ptr<Record>> &SynthDefs;
  539. TupleExpander(std::vector<std::unique_ptr<Record>> &SynthDefs)
  540. : SynthDefs(SynthDefs) {}
  541. void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) override {
  542. std::vector<Record*> Indices = Def->getValueAsListOfDefs("SubRegIndices");
  543. unsigned Dim = Indices.size();
  544. ListInit *SubRegs = Def->getValueAsListInit("SubRegs");
  545. if (Dim != SubRegs->size())
  546. PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch");
  547. if (Dim < 2)
  548. PrintFatalError(Def->getLoc(),
  549. "Tuples must have at least 2 sub-registers");
  550. // Evaluate the sub-register lists to be zipped.
  551. unsigned Length = ~0u;
  552. SmallVector<SetTheory::RecSet, 4> Lists(Dim);
  553. for (unsigned i = 0; i != Dim; ++i) {
  554. ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc());
  555. Length = std::min(Length, unsigned(Lists[i].size()));
  556. }
  557. if (Length == 0)
  558. return;
  559. // Precompute some types.
  560. Record *RegisterCl = Def->getRecords().getClass("Register");
  561. RecTy *RegisterRecTy = RecordRecTy::get(RegisterCl);
  562. std::vector<StringRef> RegNames =
  563. Def->getValueAsListOfStrings("RegAsmNames");
  564. // Zip them up.
  565. for (unsigned n = 0; n != Length; ++n) {
  566. std::string Name;
  567. Record *Proto = Lists[0][n];
  568. std::vector<Init*> Tuple;
  569. unsigned CostPerUse = 0;
  570. for (unsigned i = 0; i != Dim; ++i) {
  571. Record *Reg = Lists[i][n];
  572. if (i) Name += '_';
  573. Name += Reg->getName();
  574. Tuple.push_back(DefInit::get(Reg));
  575. CostPerUse = std::max(CostPerUse,
  576. unsigned(Reg->getValueAsInt("CostPerUse")));
  577. }
  578. StringInit *AsmName = StringInit::get("");
  579. if (!RegNames.empty()) {
  580. if (RegNames.size() <= n)
  581. PrintFatalError(Def->getLoc(),
  582. "Register tuple definition missing name for '" +
  583. Name + "'.");
  584. AsmName = StringInit::get(RegNames[n]);
  585. }
  586. // Create a new Record representing the synthesized register. This record
  587. // is only for consumption by CodeGenRegister, it is not added to the
  588. // RecordKeeper.
  589. SynthDefs.emplace_back(
  590. std::make_unique<Record>(Name, Def->getLoc(), Def->getRecords()));
  591. Record *NewReg = SynthDefs.back().get();
  592. Elts.insert(NewReg);
  593. // Copy Proto super-classes.
  594. ArrayRef<std::pair<Record *, SMRange>> Supers = Proto->getSuperClasses();
  595. for (const auto &SuperPair : Supers)
  596. NewReg->addSuperClass(SuperPair.first, SuperPair.second);
  597. // Copy Proto fields.
  598. for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) {
  599. RecordVal RV = Proto->getValues()[i];
  600. // Skip existing fields, like NAME.
  601. if (NewReg->getValue(RV.getNameInit()))
  602. continue;
  603. StringRef Field = RV.getName();
  604. // Replace the sub-register list with Tuple.
  605. if (Field == "SubRegs")
  606. RV.setValue(ListInit::get(Tuple, RegisterRecTy));
  607. if (Field == "AsmName")
  608. RV.setValue(AsmName);
  609. // CostPerUse is aggregated from all Tuple members.
  610. if (Field == "CostPerUse")
  611. RV.setValue(IntInit::get(CostPerUse));
  612. // Composite registers are always covered by sub-registers.
  613. if (Field == "CoveredBySubRegs")
  614. RV.setValue(BitInit::get(true));
  615. // Copy fields from the RegisterTuples def.
  616. if (Field == "SubRegIndices" ||
  617. Field == "CompositeIndices") {
  618. NewReg->addValue(*Def->getValue(Field));
  619. continue;
  620. }
  621. // Some fields get their default uninitialized value.
  622. if (Field == "DwarfNumbers" ||
  623. Field == "DwarfAlias" ||
  624. Field == "Aliases") {
  625. if (const RecordVal *DefRV = RegisterCl->getValue(Field))
  626. NewReg->addValue(*DefRV);
  627. continue;
  628. }
  629. // Everything else is copied from Proto.
  630. NewReg->addValue(RV);
  631. }
  632. }
  633. }
  634. };
  635. } // end anonymous namespace
  636. //===----------------------------------------------------------------------===//
  637. // CodeGenRegisterClass
  638. //===----------------------------------------------------------------------===//
  639. static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) {
  640. llvm::sort(M, deref<std::less<>>());
  641. M.erase(std::unique(M.begin(), M.end(), deref<std::equal_to<>>()), M.end());
  642. }
  643. CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
  644. : TheDef(R), Name(std::string(R->getName())),
  645. TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1) {
  646. GeneratePressureSet = R->getValueAsBit("GeneratePressureSet");
  647. std::vector<Record*> TypeList = R->getValueAsListOfDefs("RegTypes");
  648. if (TypeList.empty())
  649. PrintFatalError(R->getLoc(), "RegTypes list must not be empty!");
  650. for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
  651. Record *Type = TypeList[i];
  652. if (!Type->isSubClassOf("ValueType"))
  653. PrintFatalError(R->getLoc(),
  654. "RegTypes list member '" + Type->getName() +
  655. "' does not derive from the ValueType class!");
  656. VTs.push_back(getValueTypeByHwMode(Type, RegBank.getHwModes()));
  657. }
  658. // Allocation order 0 is the full set. AltOrders provides others.
  659. const SetTheory::RecVec *Elements = RegBank.getSets().expand(R);
  660. ListInit *AltOrders = R->getValueAsListInit("AltOrders");
  661. Orders.resize(1 + AltOrders->size());
  662. // Default allocation order always contains all registers.
  663. Artificial = true;
  664. for (unsigned i = 0, e = Elements->size(); i != e; ++i) {
  665. Orders[0].push_back((*Elements)[i]);
  666. const CodeGenRegister *Reg = RegBank.getReg((*Elements)[i]);
  667. Members.push_back(Reg);
  668. Artificial &= Reg->Artificial;
  669. TopoSigs.set(Reg->getTopoSig());
  670. }
  671. sortAndUniqueRegisters(Members);
  672. // Alternative allocation orders may be subsets.
  673. SetTheory::RecSet Order;
  674. for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) {
  675. RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc());
  676. Orders[1 + i].append(Order.begin(), Order.end());
  677. // Verify that all altorder members are regclass members.
  678. while (!Order.empty()) {
  679. CodeGenRegister *Reg = RegBank.getReg(Order.back());
  680. Order.pop_back();
  681. if (!contains(Reg))
  682. PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() +
  683. " is not a class member");
  684. }
  685. }
  686. Namespace = R->getValueAsString("Namespace");
  687. if (const RecordVal *RV = R->getValue("RegInfos"))
  688. if (DefInit *DI = dyn_cast_or_null<DefInit>(RV->getValue()))
  689. RSI = RegSizeInfoByHwMode(DI->getDef(), RegBank.getHwModes());
  690. unsigned Size = R->getValueAsInt("Size");
  691. assert((RSI.hasDefault() || Size != 0 || VTs[0].isSimple()) &&
  692. "Impossible to determine register size");
  693. if (!RSI.hasDefault()) {
  694. RegSizeInfo RI;
  695. RI.RegSize = RI.SpillSize = Size ? Size
  696. : VTs[0].getSimple().getSizeInBits();
  697. RI.SpillAlignment = R->getValueAsInt("Alignment");
  698. RSI.Map.insert({DefaultMode, RI});
  699. }
  700. CopyCost = R->getValueAsInt("CopyCost");
  701. Allocatable = R->getValueAsBit("isAllocatable");
  702. AltOrderSelect = R->getValueAsString("AltOrderSelect");
  703. int AllocationPriority = R->getValueAsInt("AllocationPriority");
  704. if (AllocationPriority < 0 || AllocationPriority > 63)
  705. PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,63]");
  706. this->AllocationPriority = AllocationPriority;
  707. }
  708. // Create an inferred register class that was missing from the .td files.
  709. // Most properties will be inherited from the closest super-class after the
  710. // class structure has been computed.
  711. CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank,
  712. StringRef Name, Key Props)
  713. : Members(*Props.Members), TheDef(nullptr), Name(std::string(Name)),
  714. TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), RSI(Props.RSI),
  715. CopyCost(0), Allocatable(true), AllocationPriority(0) {
  716. Artificial = true;
  717. GeneratePressureSet = false;
  718. for (const auto R : Members) {
  719. TopoSigs.set(R->getTopoSig());
  720. Artificial &= R->Artificial;
  721. }
  722. }
  723. // Compute inherited propertied for a synthesized register class.
  724. void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
  725. assert(!getDef() && "Only synthesized classes can inherit properties");
  726. assert(!SuperClasses.empty() && "Synthesized class without super class");
  727. // The last super-class is the smallest one.
  728. CodeGenRegisterClass &Super = *SuperClasses.back();
  729. // Most properties are copied directly.
  730. // Exceptions are members, size, and alignment
  731. Namespace = Super.Namespace;
  732. VTs = Super.VTs;
  733. CopyCost = Super.CopyCost;
  734. Allocatable = Super.Allocatable;
  735. AltOrderSelect = Super.AltOrderSelect;
  736. AllocationPriority = Super.AllocationPriority;
  737. GeneratePressureSet |= Super.GeneratePressureSet;
  738. // Copy all allocation orders, filter out foreign registers from the larger
  739. // super-class.
  740. Orders.resize(Super.Orders.size());
  741. for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i)
  742. for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j)
  743. if (contains(RegBank.getReg(Super.Orders[i][j])))
  744. Orders[i].push_back(Super.Orders[i][j]);
  745. }
  746. bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {
  747. return std::binary_search(Members.begin(), Members.end(), Reg,
  748. deref<std::less<>>());
  749. }
  750. unsigned CodeGenRegisterClass::getWeight(const CodeGenRegBank& RegBank) const {
  751. if (TheDef && !TheDef->isValueUnset("Weight"))
  752. return TheDef->getValueAsInt("Weight");
  753. if (Members.empty() || Artificial)
  754. return 0;
  755. return (*Members.begin())->getWeight(RegBank);
  756. }
  757. namespace llvm {
  758. raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) {
  759. OS << "{ " << K.RSI;
  760. for (const auto R : *K.Members)
  761. OS << ", " << R->getName();
  762. return OS << " }";
  763. }
  764. } // end namespace llvm
  765. // This is a simple lexicographical order that can be used to search for sets.
  766. // It is not the same as the topological order provided by TopoOrderRC.
  767. bool CodeGenRegisterClass::Key::
  768. operator<(const CodeGenRegisterClass::Key &B) const {
  769. assert(Members && B.Members);
  770. return std::tie(*Members, RSI) < std::tie(*B.Members, B.RSI);
  771. }
  772. // Returns true if RC is a strict subclass.
  773. // RC is a sub-class of this class if it is a valid replacement for any
  774. // instruction operand where a register of this classis required. It must
  775. // satisfy these conditions:
  776. //
  777. // 1. All RC registers are also in this.
  778. // 2. The RC spill size must not be smaller than our spill size.
  779. // 3. RC spill alignment must be compatible with ours.
  780. //
  781. static bool testSubClass(const CodeGenRegisterClass *A,
  782. const CodeGenRegisterClass *B) {
  783. return A->RSI.isSubClassOf(B->RSI) &&
  784. std::includes(A->getMembers().begin(), A->getMembers().end(),
  785. B->getMembers().begin(), B->getMembers().end(),
  786. deref<std::less<>>());
  787. }
  788. /// Sorting predicate for register classes. This provides a topological
  789. /// ordering that arranges all register classes before their sub-classes.
  790. ///
  791. /// Register classes with the same registers, spill size, and alignment form a
  792. /// clique. They will be ordered alphabetically.
  793. ///
  794. static bool TopoOrderRC(const CodeGenRegisterClass &PA,
  795. const CodeGenRegisterClass &PB) {
  796. auto *A = &PA;
  797. auto *B = &PB;
  798. if (A == B)
  799. return false;
  800. if (A->RSI < B->RSI)
  801. return true;
  802. if (A->RSI != B->RSI)
  803. return false;
  804. // Order by descending set size. Note that the classes' allocation order may
  805. // not have been computed yet. The Members set is always vaild.
  806. if (A->getMembers().size() > B->getMembers().size())
  807. return true;
  808. if (A->getMembers().size() < B->getMembers().size())
  809. return false;
  810. // Finally order by name as a tie breaker.
  811. return StringRef(A->getName()) < B->getName();
  812. }
  813. std::string CodeGenRegisterClass::getQualifiedName() const {
  814. if (Namespace.empty())
  815. return getName();
  816. else
  817. return (Namespace + "::" + getName()).str();
  818. }
  819. // Compute sub-classes of all register classes.
  820. // Assume the classes are ordered topologically.
  821. void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) {
  822. auto &RegClasses = RegBank.getRegClasses();
  823. // Visit backwards so sub-classes are seen first.
  824. for (auto I = RegClasses.rbegin(), E = RegClasses.rend(); I != E; ++I) {
  825. CodeGenRegisterClass &RC = *I;
  826. RC.SubClasses.resize(RegClasses.size());
  827. RC.SubClasses.set(RC.EnumValue);
  828. if (RC.Artificial)
  829. continue;
  830. // Normally, all subclasses have IDs >= rci, unless RC is part of a clique.
  831. for (auto I2 = I.base(), E2 = RegClasses.end(); I2 != E2; ++I2) {
  832. CodeGenRegisterClass &SubRC = *I2;
  833. if (RC.SubClasses.test(SubRC.EnumValue))
  834. continue;
  835. if (!testSubClass(&RC, &SubRC))
  836. continue;
  837. // SubRC is a sub-class. Grap all its sub-classes so we won't have to
  838. // check them again.
  839. RC.SubClasses |= SubRC.SubClasses;
  840. }
  841. // Sweep up missed clique members. They will be immediately preceding RC.
  842. for (auto I2 = std::next(I); I2 != E && testSubClass(&RC, &*I2); ++I2)
  843. RC.SubClasses.set(I2->EnumValue);
  844. }
  845. // Compute the SuperClasses lists from the SubClasses vectors.
  846. for (auto &RC : RegClasses) {
  847. const BitVector &SC = RC.getSubClasses();
  848. auto I = RegClasses.begin();
  849. for (int s = 0, next_s = SC.find_first(); next_s != -1;
  850. next_s = SC.find_next(s)) {
  851. std::advance(I, next_s - s);
  852. s = next_s;
  853. if (&*I == &RC)
  854. continue;
  855. I->SuperClasses.push_back(&RC);
  856. }
  857. }
  858. // With the class hierarchy in place, let synthesized register classes inherit
  859. // properties from their closest super-class. The iteration order here can
  860. // propagate properties down multiple levels.
  861. for (auto &RC : RegClasses)
  862. if (!RC.getDef())
  863. RC.inheritProperties(RegBank);
  864. }
  865. Optional<std::pair<CodeGenRegisterClass *, CodeGenRegisterClass *>>
  866. CodeGenRegisterClass::getMatchingSubClassWithSubRegs(
  867. CodeGenRegBank &RegBank, const CodeGenSubRegIndex *SubIdx) const {
  868. auto SizeOrder = [this](const CodeGenRegisterClass *A,
  869. const CodeGenRegisterClass *B) {
  870. // If there are multiple, identical register classes, prefer the original
  871. // register class.
  872. if (A == B)
  873. return false;
  874. if (A->getMembers().size() == B->getMembers().size())
  875. return A == this;
  876. return A->getMembers().size() > B->getMembers().size();
  877. };
  878. auto &RegClasses = RegBank.getRegClasses();
  879. // Find all the subclasses of this one that fully support the sub-register
  880. // index and order them by size. BiggestSuperRC should always be first.
  881. CodeGenRegisterClass *BiggestSuperRegRC = getSubClassWithSubReg(SubIdx);
  882. if (!BiggestSuperRegRC)
  883. return None;
  884. BitVector SuperRegRCsBV = BiggestSuperRegRC->getSubClasses();
  885. std::vector<CodeGenRegisterClass *> SuperRegRCs;
  886. for (auto &RC : RegClasses)
  887. if (SuperRegRCsBV[RC.EnumValue])
  888. SuperRegRCs.emplace_back(&RC);
  889. llvm::stable_sort(SuperRegRCs, SizeOrder);
  890. assert(SuperRegRCs.front() == BiggestSuperRegRC &&
  891. "Biggest class wasn't first");
  892. // Find all the subreg classes and order them by size too.
  893. std::vector<std::pair<CodeGenRegisterClass *, BitVector>> SuperRegClasses;
  894. for (auto &RC: RegClasses) {
  895. BitVector SuperRegClassesBV(RegClasses.size());
  896. RC.getSuperRegClasses(SubIdx, SuperRegClassesBV);
  897. if (SuperRegClassesBV.any())
  898. SuperRegClasses.push_back(std::make_pair(&RC, SuperRegClassesBV));
  899. }
  900. llvm::sort(SuperRegClasses,
  901. [&](const std::pair<CodeGenRegisterClass *, BitVector> &A,
  902. const std::pair<CodeGenRegisterClass *, BitVector> &B) {
  903. return SizeOrder(A.first, B.first);
  904. });
  905. // Find the biggest subclass and subreg class such that R:subidx is in the
  906. // subreg class for all R in subclass.
  907. //
  908. // For example:
  909. // All registers in X86's GR64 have a sub_32bit subregister but no class
  910. // exists that contains all the 32-bit subregisters because GR64 contains RIP
  911. // but GR32 does not contain EIP. Instead, we constrain SuperRegRC to
  912. // GR32_with_sub_8bit (which is identical to GR32_with_sub_32bit) and then,
  913. // having excluded RIP, we are able to find a SubRegRC (GR32).
  914. CodeGenRegisterClass *ChosenSuperRegClass = nullptr;
  915. CodeGenRegisterClass *SubRegRC = nullptr;
  916. for (auto *SuperRegRC : SuperRegRCs) {
  917. for (const auto &SuperRegClassPair : SuperRegClasses) {
  918. const BitVector &SuperRegClassBV = SuperRegClassPair.second;
  919. if (SuperRegClassBV[SuperRegRC->EnumValue]) {
  920. SubRegRC = SuperRegClassPair.first;
  921. ChosenSuperRegClass = SuperRegRC;
  922. // If SubRegRC is bigger than SuperRegRC then there are members of
  923. // SubRegRC that don't have super registers via SubIdx. Keep looking to
  924. // find a better fit and fall back on this one if there isn't one.
  925. //
  926. // This is intended to prevent X86 from making odd choices such as
  927. // picking LOW32_ADDR_ACCESS_RBP instead of GR32 in the example above.
  928. // LOW32_ADDR_ACCESS_RBP is a valid choice but contains registers that
  929. // aren't subregisters of SuperRegRC whereas GR32 has a direct 1:1
  930. // mapping.
  931. if (SuperRegRC->getMembers().size() >= SubRegRC->getMembers().size())
  932. return std::make_pair(ChosenSuperRegClass, SubRegRC);
  933. }
  934. }
  935. // If we found a fit but it wasn't quite ideal because SubRegRC had excess
  936. // registers, then we're done.
  937. if (ChosenSuperRegClass)
  938. return std::make_pair(ChosenSuperRegClass, SubRegRC);
  939. }
  940. return None;
  941. }
  942. void CodeGenRegisterClass::getSuperRegClasses(const CodeGenSubRegIndex *SubIdx,
  943. BitVector &Out) const {
  944. auto FindI = SuperRegClasses.find(SubIdx);
  945. if (FindI == SuperRegClasses.end())
  946. return;
  947. for (CodeGenRegisterClass *RC : FindI->second)
  948. Out.set(RC->EnumValue);
  949. }
  950. // Populate a unique sorted list of units from a register set.
  951. void CodeGenRegisterClass::buildRegUnitSet(const CodeGenRegBank &RegBank,
  952. std::vector<unsigned> &RegUnits) const {
  953. std::vector<unsigned> TmpUnits;
  954. for (RegUnitIterator UnitI(Members); UnitI.isValid(); ++UnitI) {
  955. const RegUnit &RU = RegBank.getRegUnit(*UnitI);
  956. if (!RU.Artificial)
  957. TmpUnits.push_back(*UnitI);
  958. }
  959. llvm::sort(TmpUnits);
  960. std::unique_copy(TmpUnits.begin(), TmpUnits.end(),
  961. std::back_inserter(RegUnits));
  962. }
  963. //===----------------------------------------------------------------------===//
  964. // CodeGenRegBank
  965. //===----------------------------------------------------------------------===//
  966. CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records,
  967. const CodeGenHwModes &Modes) : CGH(Modes) {
  968. // Configure register Sets to understand register classes and tuples.
  969. Sets.addFieldExpander("RegisterClass", "MemberList");
  970. Sets.addFieldExpander("CalleeSavedRegs", "SaveList");
  971. Sets.addExpander("RegisterTuples",
  972. std::make_unique<TupleExpander>(SynthDefs));
  973. // Read in the user-defined (named) sub-register indices.
  974. // More indices will be synthesized later.
  975. std::vector<Record*> SRIs = Records.getAllDerivedDefinitions("SubRegIndex");
  976. llvm::sort(SRIs, LessRecord());
  977. for (unsigned i = 0, e = SRIs.size(); i != e; ++i)
  978. getSubRegIdx(SRIs[i]);
  979. // Build composite maps from ComposedOf fields.
  980. for (auto &Idx : SubRegIndices)
  981. Idx.updateComponents(*this);
  982. // Read in the register definitions.
  983. std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
  984. llvm::sort(Regs, LessRecordRegister());
  985. // Assign the enumeration values.
  986. for (unsigned i = 0, e = Regs.size(); i != e; ++i)
  987. getReg(Regs[i]);
  988. // Expand tuples and number the new registers.
  989. std::vector<Record*> Tups =
  990. Records.getAllDerivedDefinitions("RegisterTuples");
  991. for (Record *R : Tups) {
  992. std::vector<Record *> TupRegs = *Sets.expand(R);
  993. llvm::sort(TupRegs, LessRecordRegister());
  994. for (Record *RC : TupRegs)
  995. getReg(RC);
  996. }
  997. // Now all the registers are known. Build the object graph of explicit
  998. // register-register references.
  999. for (auto &Reg : Registers)
  1000. Reg.buildObjectGraph(*this);
  1001. // Compute register name map.
  1002. for (auto &Reg : Registers)
  1003. // FIXME: This could just be RegistersByName[name] = register, except that
  1004. // causes some failures in MIPS - perhaps they have duplicate register name
  1005. // entries? (or maybe there's a reason for it - I don't know much about this
  1006. // code, just drive-by refactoring)
  1007. RegistersByName.insert(
  1008. std::make_pair(Reg.TheDef->getValueAsString("AsmName"), &Reg));
  1009. // Precompute all sub-register maps.
  1010. // This will create Composite entries for all inferred sub-register indices.
  1011. for (auto &Reg : Registers)
  1012. Reg.computeSubRegs(*this);
  1013. // Compute transitive closure of subregister index ConcatenationOf vectors
  1014. // and initialize ConcatIdx map.
  1015. for (CodeGenSubRegIndex &SRI : SubRegIndices) {
  1016. SRI.computeConcatTransitiveClosure();
  1017. if (!SRI.ConcatenationOf.empty())
  1018. ConcatIdx.insert(std::make_pair(
  1019. SmallVector<CodeGenSubRegIndex*,8>(SRI.ConcatenationOf.begin(),
  1020. SRI.ConcatenationOf.end()), &SRI));
  1021. }
  1022. // Infer even more sub-registers by combining leading super-registers.
  1023. for (auto &Reg : Registers)
  1024. if (Reg.CoveredBySubRegs)
  1025. Reg.computeSecondarySubRegs(*this);
  1026. // After the sub-register graph is complete, compute the topologically
  1027. // ordered SuperRegs list.
  1028. for (auto &Reg : Registers)
  1029. Reg.computeSuperRegs(*this);
  1030. // For each pair of Reg:SR, if both are non-artificial, mark the
  1031. // corresponding sub-register index as non-artificial.
  1032. for (auto &Reg : Registers) {
  1033. if (Reg.Artificial)
  1034. continue;
  1035. for (auto P : Reg.getSubRegs()) {
  1036. const CodeGenRegister *SR = P.second;
  1037. if (!SR->Artificial)
  1038. P.first->Artificial = false;
  1039. }
  1040. }
  1041. // Native register units are associated with a leaf register. They've all been
  1042. // discovered now.
  1043. NumNativeRegUnits = RegUnits.size();
  1044. // Read in register class definitions.
  1045. std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
  1046. if (RCs.empty())
  1047. PrintFatalError("No 'RegisterClass' subclasses defined!");
  1048. // Allocate user-defined register classes.
  1049. for (auto *R : RCs) {
  1050. RegClasses.emplace_back(*this, R);
  1051. CodeGenRegisterClass &RC = RegClasses.back();
  1052. if (!RC.Artificial)
  1053. addToMaps(&RC);
  1054. }
  1055. // Infer missing classes to create a full algebra.
  1056. computeInferredRegisterClasses();
  1057. // Order register classes topologically and assign enum values.
  1058. RegClasses.sort(TopoOrderRC);
  1059. unsigned i = 0;
  1060. for (auto &RC : RegClasses)
  1061. RC.EnumValue = i++;
  1062. CodeGenRegisterClass::computeSubClasses(*this);
  1063. }
  1064. // Create a synthetic CodeGenSubRegIndex without a corresponding Record.
  1065. CodeGenSubRegIndex*
  1066. CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) {
  1067. SubRegIndices.emplace_back(Name, Namespace, SubRegIndices.size() + 1);
  1068. return &SubRegIndices.back();
  1069. }
  1070. CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) {
  1071. CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def];
  1072. if (Idx)
  1073. return Idx;
  1074. SubRegIndices.emplace_back(Def, SubRegIndices.size() + 1);
  1075. Idx = &SubRegIndices.back();
  1076. return Idx;
  1077. }
  1078. const CodeGenSubRegIndex *
  1079. CodeGenRegBank::findSubRegIdx(const Record* Def) const {
  1080. return Def2SubRegIdx.lookup(Def);
  1081. }
  1082. CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
  1083. CodeGenRegister *&Reg = Def2Reg[Def];
  1084. if (Reg)
  1085. return Reg;
  1086. Registers.emplace_back(Def, Registers.size() + 1);
  1087. Reg = &Registers.back();
  1088. return Reg;
  1089. }
  1090. void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) {
  1091. if (Record *Def = RC->getDef())
  1092. Def2RC.insert(std::make_pair(Def, RC));
  1093. // Duplicate classes are rejected by insert().
  1094. // That's OK, we only care about the properties handled by CGRC::Key.
  1095. CodeGenRegisterClass::Key K(*RC);
  1096. Key2RC.insert(std::make_pair(K, RC));
  1097. }
  1098. // Create a synthetic sub-class if it is missing.
  1099. CodeGenRegisterClass*
  1100. CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC,
  1101. const CodeGenRegister::Vec *Members,
  1102. StringRef Name) {
  1103. // Synthetic sub-class has the same size and alignment as RC.
  1104. CodeGenRegisterClass::Key K(Members, RC->RSI);
  1105. RCKeyMap::const_iterator FoundI = Key2RC.find(K);
  1106. if (FoundI != Key2RC.end())
  1107. return FoundI->second;
  1108. // Sub-class doesn't exist, create a new one.
  1109. RegClasses.emplace_back(*this, Name, K);
  1110. addToMaps(&RegClasses.back());
  1111. return &RegClasses.back();
  1112. }
  1113. CodeGenRegisterClass *CodeGenRegBank::getRegClass(const Record *Def) const {
  1114. if (CodeGenRegisterClass *RC = Def2RC.lookup(Def))
  1115. return RC;
  1116. PrintFatalError(Def->getLoc(), "Not a known RegisterClass!");
  1117. }
  1118. CodeGenSubRegIndex*
  1119. CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A,
  1120. CodeGenSubRegIndex *B) {
  1121. // Look for an existing entry.
  1122. CodeGenSubRegIndex *Comp = A->compose(B);
  1123. if (Comp)
  1124. return Comp;
  1125. // None exists, synthesize one.
  1126. std::string Name = A->getName() + "_then_" + B->getName();
  1127. Comp = createSubRegIndex(Name, A->getNamespace());
  1128. A->addComposite(B, Comp);
  1129. return Comp;
  1130. }
  1131. CodeGenSubRegIndex *CodeGenRegBank::
  1132. getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts) {
  1133. assert(Parts.size() > 1 && "Need two parts to concatenate");
  1134. #ifndef NDEBUG
  1135. for (CodeGenSubRegIndex *Idx : Parts) {
  1136. assert(Idx->ConcatenationOf.empty() && "No transitive closure?");
  1137. }
  1138. #endif
  1139. // Look for an existing entry.
  1140. CodeGenSubRegIndex *&Idx = ConcatIdx[Parts];
  1141. if (Idx)
  1142. return Idx;
  1143. // None exists, synthesize one.
  1144. std::string Name = Parts.front()->getName();
  1145. // Determine whether all parts are contiguous.
  1146. bool isContinuous = true;
  1147. unsigned Size = Parts.front()->Size;
  1148. unsigned LastOffset = Parts.front()->Offset;
  1149. unsigned LastSize = Parts.front()->Size;
  1150. for (unsigned i = 1, e = Parts.size(); i != e; ++i) {
  1151. Name += '_';
  1152. Name += Parts[i]->getName();
  1153. Size += Parts[i]->Size;
  1154. if (Parts[i]->Offset != (LastOffset + LastSize))
  1155. isContinuous = false;
  1156. LastOffset = Parts[i]->Offset;
  1157. LastSize = Parts[i]->Size;
  1158. }
  1159. Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
  1160. Idx->Size = Size;
  1161. Idx->Offset = isContinuous ? Parts.front()->Offset : -1;
  1162. Idx->ConcatenationOf.assign(Parts.begin(), Parts.end());
  1163. return Idx;
  1164. }
  1165. void CodeGenRegBank::computeComposites() {
  1166. using RegMap = std::map<const CodeGenRegister*, const CodeGenRegister*>;
  1167. // Subreg -> { Reg->Reg }, where the right-hand side is the mapping from
  1168. // register to (sub)register associated with the action of the left-hand
  1169. // side subregister.
  1170. std::map<const CodeGenSubRegIndex*, RegMap> SubRegAction;
  1171. for (const CodeGenRegister &R : Registers) {
  1172. const CodeGenRegister::SubRegMap &SM = R.getSubRegs();
  1173. for (std::pair<const CodeGenSubRegIndex*, const CodeGenRegister*> P : SM)
  1174. SubRegAction[P.first].insert({&R, P.second});
  1175. }
  1176. // Calculate the composition of two subregisters as compositions of their
  1177. // associated actions.
  1178. auto compose = [&SubRegAction] (const CodeGenSubRegIndex *Sub1,
  1179. const CodeGenSubRegIndex *Sub2) {
  1180. RegMap C;
  1181. const RegMap &Img1 = SubRegAction.at(Sub1);
  1182. const RegMap &Img2 = SubRegAction.at(Sub2);
  1183. for (std::pair<const CodeGenRegister*, const CodeGenRegister*> P : Img1) {
  1184. auto F = Img2.find(P.second);
  1185. if (F != Img2.end())
  1186. C.insert({P.first, F->second});
  1187. }
  1188. return C;
  1189. };
  1190. // Check if the two maps agree on the intersection of their domains.
  1191. auto agree = [] (const RegMap &Map1, const RegMap &Map2) {
  1192. // Technically speaking, an empty map agrees with any other map, but
  1193. // this could flag false positives. We're interested in non-vacuous
  1194. // agreements.
  1195. if (Map1.empty() || Map2.empty())
  1196. return false;
  1197. for (std::pair<const CodeGenRegister*, const CodeGenRegister*> P : Map1) {
  1198. auto F = Map2.find(P.first);
  1199. if (F == Map2.end() || P.second != F->second)
  1200. return false;
  1201. }
  1202. return true;
  1203. };
  1204. using CompositePair = std::pair<const CodeGenSubRegIndex*,
  1205. const CodeGenSubRegIndex*>;
  1206. SmallSet<CompositePair,4> UserDefined;
  1207. for (const CodeGenSubRegIndex &Idx : SubRegIndices)
  1208. for (auto P : Idx.getComposites())
  1209. UserDefined.insert(std::make_pair(&Idx, P.first));
  1210. // Keep track of TopoSigs visited. We only need to visit each TopoSig once,
  1211. // and many registers will share TopoSigs on regular architectures.
  1212. BitVector TopoSigs(getNumTopoSigs());
  1213. for (const auto &Reg1 : Registers) {
  1214. // Skip identical subreg structures already processed.
  1215. if (TopoSigs.test(Reg1.getTopoSig()))
  1216. continue;
  1217. TopoSigs.set(Reg1.getTopoSig());
  1218. const CodeGenRegister::SubRegMap &SRM1 = Reg1.getSubRegs();
  1219. for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(),
  1220. e1 = SRM1.end(); i1 != e1; ++i1) {
  1221. CodeGenSubRegIndex *Idx1 = i1->first;
  1222. CodeGenRegister *Reg2 = i1->second;
  1223. // Ignore identity compositions.
  1224. if (&Reg1 == Reg2)
  1225. continue;
  1226. const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs();
  1227. // Try composing Idx1 with another SubRegIndex.
  1228. for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM2.begin(),
  1229. e2 = SRM2.end(); i2 != e2; ++i2) {
  1230. CodeGenSubRegIndex *Idx2 = i2->first;
  1231. CodeGenRegister *Reg3 = i2->second;
  1232. // Ignore identity compositions.
  1233. if (Reg2 == Reg3)
  1234. continue;
  1235. // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3.
  1236. CodeGenSubRegIndex *Idx3 = Reg1.getSubRegIndex(Reg3);
  1237. assert(Idx3 && "Sub-register doesn't have an index");
  1238. // Conflicting composition? Emit a warning but allow it.
  1239. if (CodeGenSubRegIndex *Prev = Idx1->addComposite(Idx2, Idx3)) {
  1240. // If the composition was not user-defined, always emit a warning.
  1241. if (!UserDefined.count({Idx1, Idx2}) ||
  1242. agree(compose(Idx1, Idx2), SubRegAction.at(Idx3)))
  1243. PrintWarning(Twine("SubRegIndex ") + Idx1->getQualifiedName() +
  1244. " and " + Idx2->getQualifiedName() +
  1245. " compose ambiguously as " + Prev->getQualifiedName() +
  1246. " or " + Idx3->getQualifiedName());
  1247. }
  1248. }
  1249. }
  1250. }
  1251. }
  1252. // Compute lane masks. This is similar to register units, but at the
  1253. // sub-register index level. Each bit in the lane mask is like a register unit
  1254. // class, and two lane masks will have a bit in common if two sub-register
  1255. // indices overlap in some register.
  1256. //
  1257. // Conservatively share a lane mask bit if two sub-register indices overlap in
  1258. // some registers, but not in others. That shouldn't happen a lot.
  1259. void CodeGenRegBank::computeSubRegLaneMasks() {
  1260. // First assign individual bits to all the leaf indices.
  1261. unsigned Bit = 0;
  1262. // Determine mask of lanes that cover their registers.
  1263. CoveringLanes = LaneBitmask::getAll();
  1264. for (auto &Idx : SubRegIndices) {
  1265. if (Idx.getComposites().empty()) {
  1266. if (Bit > LaneBitmask::BitWidth) {
  1267. PrintFatalError(
  1268. Twine("Ran out of lanemask bits to represent subregister ")
  1269. + Idx.getName());
  1270. }
  1271. Idx.LaneMask = LaneBitmask::getLane(Bit);
  1272. ++Bit;
  1273. } else {
  1274. Idx.LaneMask = LaneBitmask::getNone();
  1275. }
  1276. }
  1277. // Compute transformation sequences for composeSubRegIndexLaneMask. The idea
  1278. // here is that for each possible target subregister we look at the leafs
  1279. // in the subregister graph that compose for this target and create
  1280. // transformation sequences for the lanemasks. Each step in the sequence
  1281. // consists of a bitmask and a bitrotate operation. As the rotation amounts
  1282. // are usually the same for many subregisters we can easily combine the steps
  1283. // by combining the masks.
  1284. for (const auto &Idx : SubRegIndices) {
  1285. const auto &Composites = Idx.getComposites();
  1286. auto &LaneTransforms = Idx.CompositionLaneMaskTransform;
  1287. if (Composites.empty()) {
  1288. // Moving from a class with no subregisters we just had a single lane:
  1289. // The subregister must be a leaf subregister and only occupies 1 bit.
  1290. // Move the bit from the class without subregisters into that position.
  1291. unsigned DstBit = Idx.LaneMask.getHighestLane();
  1292. assert(Idx.LaneMask == LaneBitmask::getLane(DstBit) &&
  1293. "Must be a leaf subregister");
  1294. MaskRolPair MaskRol = { LaneBitmask::getLane(0), (uint8_t)DstBit };
  1295. LaneTransforms.push_back(MaskRol);
  1296. } else {
  1297. // Go through all leaf subregisters and find the ones that compose with
  1298. // Idx. These make out all possible valid bits in the lane mask we want to
  1299. // transform. Looking only at the leafs ensure that only a single bit in
  1300. // the mask is set.
  1301. unsigned NextBit = 0;
  1302. for (auto &Idx2 : SubRegIndices) {
  1303. // Skip non-leaf subregisters.
  1304. if (!Idx2.getComposites().empty())
  1305. continue;
  1306. // Replicate the behaviour from the lane mask generation loop above.
  1307. unsigned SrcBit = NextBit;
  1308. LaneBitmask SrcMask = LaneBitmask::getLane(SrcBit);
  1309. if (NextBit < LaneBitmask::BitWidth-1)
  1310. ++NextBit;
  1311. assert(Idx2.LaneMask == SrcMask);
  1312. // Get the composed subregister if there is any.
  1313. auto C = Composites.find(&Idx2);
  1314. if (C == Composites.end())
  1315. continue;
  1316. const CodeGenSubRegIndex *Composite = C->second;
  1317. // The Composed subreg should be a leaf subreg too
  1318. assert(Composite->getComposites().empty());
  1319. // Create Mask+Rotate operation and merge with existing ops if possible.
  1320. unsigned DstBit = Composite->LaneMask.getHighestLane();
  1321. int Shift = DstBit - SrcBit;
  1322. uint8_t RotateLeft = Shift >= 0 ? (uint8_t)Shift
  1323. : LaneBitmask::BitWidth + Shift;
  1324. for (auto &I : LaneTransforms) {
  1325. if (I.RotateLeft == RotateLeft) {
  1326. I.Mask |= SrcMask;
  1327. SrcMask = LaneBitmask::getNone();
  1328. }
  1329. }
  1330. if (SrcMask.any()) {
  1331. MaskRolPair MaskRol = { SrcMask, RotateLeft };
  1332. LaneTransforms.push_back(MaskRol);
  1333. }
  1334. }
  1335. }
  1336. // Optimize if the transformation consists of one step only: Set mask to
  1337. // 0xffffffff (including some irrelevant invalid bits) so that it should
  1338. // merge with more entries later while compressing the table.
  1339. if (LaneTransforms.size() == 1)
  1340. LaneTransforms[0].Mask = LaneBitmask::getAll();
  1341. // Further compression optimization: For invalid compositions resulting
  1342. // in a sequence with 0 entries we can just pick any other. Choose
  1343. // Mask 0xffffffff with Rotation 0.
  1344. if (LaneTransforms.size() == 0) {
  1345. MaskRolPair P = { LaneBitmask::getAll(), 0 };
  1346. LaneTransforms.push_back(P);
  1347. }
  1348. }
  1349. // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented
  1350. // by the sub-register graph? This doesn't occur in any known targets.
  1351. // Inherit lanes from composites.
  1352. for (const auto &Idx : SubRegIndices) {
  1353. LaneBitmask Mask = Idx.computeLaneMask();
  1354. // If some super-registers without CoveredBySubRegs use this index, we can
  1355. // no longer assume that the lanes are covering their registers.
  1356. if (!Idx.AllSuperRegsCovered)
  1357. CoveringLanes &= ~Mask;
  1358. }
  1359. // Compute lane mask combinations for register classes.
  1360. for (auto &RegClass : RegClasses) {
  1361. LaneBitmask LaneMask;
  1362. for (const auto &SubRegIndex : SubRegIndices) {
  1363. if (RegClass.getSubClassWithSubReg(&SubRegIndex) == nullptr)
  1364. continue;
  1365. LaneMask |= SubRegIndex.LaneMask;
  1366. }
  1367. // For classes without any subregisters set LaneMask to 1 instead of 0.
  1368. // This makes it easier for client code to handle classes uniformly.
  1369. if (LaneMask.none())
  1370. LaneMask = LaneBitmask::getLane(0);
  1371. RegClass.LaneMask = LaneMask;
  1372. }
  1373. }
  1374. namespace {
  1375. // UberRegSet is a helper class for computeRegUnitWeights. Each UberRegSet is
  1376. // the transitive closure of the union of overlapping register
  1377. // classes. Together, the UberRegSets form a partition of the registers. If we
  1378. // consider overlapping register classes to be connected, then each UberRegSet
  1379. // is a set of connected components.
  1380. //
  1381. // An UberRegSet will likely be a horizontal slice of register names of
  1382. // the same width. Nontrivial subregisters should then be in a separate
  1383. // UberRegSet. But this property isn't required for valid computation of
  1384. // register unit weights.
  1385. //
  1386. // A Weight field caches the max per-register unit weight in each UberRegSet.
  1387. //
  1388. // A set of SingularDeterminants flags single units of some register in this set
  1389. // for which the unit weight equals the set weight. These units should not have
  1390. // their weight increased.
  1391. struct UberRegSet {
  1392. CodeGenRegister::Vec Regs;
  1393. unsigned Weight = 0;
  1394. CodeGenRegister::RegUnitList SingularDeterminants;
  1395. UberRegSet() = default;
  1396. };
  1397. } // end anonymous namespace
  1398. // Partition registers into UberRegSets, where each set is the transitive
  1399. // closure of the union of overlapping register classes.
  1400. //
  1401. // UberRegSets[0] is a special non-allocatable set.
  1402. static void computeUberSets(std::vector<UberRegSet> &UberSets,
  1403. std::vector<UberRegSet*> &RegSets,
  1404. CodeGenRegBank &RegBank) {
  1405. const auto &Registers = RegBank.getRegisters();
  1406. // The Register EnumValue is one greater than its index into Registers.
  1407. assert(Registers.size() == Registers.back().EnumValue &&
  1408. "register enum value mismatch");
  1409. // For simplicitly make the SetID the same as EnumValue.
  1410. IntEqClasses UberSetIDs(Registers.size()+1);
  1411. std::set<unsigned> AllocatableRegs;
  1412. for (auto &RegClass : RegBank.getRegClasses()) {
  1413. if (!RegClass.Allocatable)
  1414. continue;
  1415. const CodeGenRegister::Vec &Regs = RegClass.getMembers();
  1416. if (Regs.empty())
  1417. continue;
  1418. unsigned USetID = UberSetIDs.findLeader((*Regs.begin())->EnumValue);
  1419. assert(USetID && "register number 0 is invalid");
  1420. AllocatableRegs.insert((*Regs.begin())->EnumValue);
  1421. for (auto I = std::next(Regs.begin()), E = Regs.end(); I != E; ++I) {
  1422. AllocatableRegs.insert((*I)->EnumValue);
  1423. UberSetIDs.join(USetID, (*I)->EnumValue);
  1424. }
  1425. }
  1426. // Combine non-allocatable regs.
  1427. for (const auto &Reg : Registers) {
  1428. unsigned RegNum = Reg.EnumValue;
  1429. if (AllocatableRegs.count(RegNum))
  1430. continue;
  1431. UberSetIDs.join(0, RegNum);
  1432. }
  1433. UberSetIDs.compress();
  1434. // Make the first UberSet a special unallocatable set.
  1435. unsigned ZeroID = UberSetIDs[0];
  1436. // Insert Registers into the UberSets formed by union-find.
  1437. // Do not resize after this.
  1438. UberSets.resize(UberSetIDs.getNumClasses());
  1439. unsigned i = 0;
  1440. for (const CodeGenRegister &Reg : Registers) {
  1441. unsigned USetID = UberSetIDs[Reg.EnumValue];
  1442. if (!USetID)
  1443. USetID = ZeroID;
  1444. else if (USetID == ZeroID)
  1445. USetID = 0;
  1446. UberRegSet *USet = &UberSets[USetID];
  1447. USet->Regs.push_back(&Reg);
  1448. sortAndUniqueRegisters(USet->Regs);
  1449. RegSets[i++] = USet;
  1450. }
  1451. }
  1452. // Recompute each UberSet weight after changing unit weights.
  1453. static void computeUberWeights(std::vector<UberRegSet> &UberSets,
  1454. CodeGenRegBank &RegBank) {
  1455. // Skip the first unallocatable set.
  1456. for (std::vector<UberRegSet>::iterator I = std::next(UberSets.begin()),
  1457. E = UberSets.end(); I != E; ++I) {
  1458. // Initialize all unit weights in this set, and remember the max units/reg.
  1459. const CodeGenRegister *Reg = nullptr;
  1460. unsigned MaxWeight = 0, Weight = 0;
  1461. for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) {
  1462. if (Reg != UnitI.getReg()) {
  1463. if (Weight > MaxWeight)
  1464. MaxWeight = Weight;
  1465. Reg = UnitI.getReg();
  1466. Weight = 0;
  1467. }
  1468. if (!RegBank.getRegUnit(*UnitI).Artificial) {
  1469. unsigned UWeight = RegBank.getRegUnit(*UnitI).Weight;
  1470. if (!UWeight) {
  1471. UWeight = 1;
  1472. RegBank.increaseRegUnitWeight(*UnitI, UWeight);
  1473. }
  1474. Weight += UWeight;
  1475. }
  1476. }
  1477. if (Weight > MaxWeight)
  1478. MaxWeight = Weight;
  1479. if (I->Weight != MaxWeight) {
  1480. LLVM_DEBUG(dbgs() << "UberSet " << I - UberSets.begin() << " Weight "
  1481. << MaxWeight;
  1482. for (auto &Unit
  1483. : I->Regs) dbgs()
  1484. << " " << Unit->getName();
  1485. dbgs() << "\n");
  1486. // Update the set weight.
  1487. I->Weight = MaxWeight;
  1488. }
  1489. // Find singular determinants.
  1490. for (const auto R : I->Regs) {
  1491. if (R->getRegUnits().count() == 1 && R->getWeight(RegBank) == I->Weight) {
  1492. I->SingularDeterminants |= R->getRegUnits();
  1493. }
  1494. }
  1495. }
  1496. }
  1497. // normalizeWeight is a computeRegUnitWeights helper that adjusts the weight of
  1498. // a register and its subregisters so that they have the same weight as their
  1499. // UberSet. Self-recursion processes the subregister tree in postorder so
  1500. // subregisters are normalized first.
  1501. //
  1502. // Side effects:
  1503. // - creates new adopted register units
  1504. // - causes superregisters to inherit adopted units
  1505. // - increases the weight of "singular" units
  1506. // - induces recomputation of UberWeights.
  1507. static bool normalizeWeight(CodeGenRegister *Reg,
  1508. std::vector<UberRegSet> &UberSets,
  1509. std::vector<UberRegSet*> &RegSets,
  1510. BitVector &NormalRegs,
  1511. CodeGenRegister::RegUnitList &NormalUnits,
  1512. CodeGenRegBank &RegBank) {
  1513. NormalRegs.resize(std::max(Reg->EnumValue + 1, NormalRegs.size()));
  1514. if (NormalRegs.test(Reg->EnumValue))
  1515. return false;
  1516. NormalRegs.set(Reg->EnumValue);
  1517. bool Changed = false;
  1518. const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
  1519. for (CodeGenRegister::SubRegMap::const_iterator SRI = SRM.begin(),
  1520. SRE = SRM.end(); SRI != SRE; ++SRI) {
  1521. if (SRI->second == Reg)
  1522. continue; // self-cycles happen
  1523. Changed |= normalizeWeight(SRI->second, UberSets, RegSets,
  1524. NormalRegs, NormalUnits, RegBank);
  1525. }
  1526. // Postorder register normalization.
  1527. // Inherit register units newly adopted by subregisters.
  1528. if (Reg->inheritRegUnits(RegBank))
  1529. computeUberWeights(UberSets, RegBank);
  1530. // Check if this register is too skinny for its UberRegSet.
  1531. UberRegSet *UberSet = RegSets[RegBank.getRegIndex(Reg)];
  1532. unsigned RegWeight = Reg->getWeight(RegBank);
  1533. if (UberSet->Weight > RegWeight) {
  1534. // A register unit's weight can be adjusted only if it is the singular unit
  1535. // for this register, has not been used to normalize a subregister's set,
  1536. // and has not already been used to singularly determine this UberRegSet.
  1537. unsigned AdjustUnit = *Reg->getRegUnits().begin();
  1538. if (Reg->getRegUnits().count() != 1
  1539. || hasRegUnit(NormalUnits, AdjustUnit)
  1540. || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) {
  1541. // We don't have an adjustable unit, so adopt a new one.
  1542. AdjustUnit = RegBank.newRegUnit(UberSet->Weight - RegWeight);
  1543. Reg->adoptRegUnit(AdjustUnit);
  1544. // Adopting a unit does not immediately require recomputing set weights.
  1545. }
  1546. else {
  1547. // Adjust the existing single unit.
  1548. if (!RegBank.getRegUnit(AdjustUnit).Artificial)
  1549. RegBank.increaseRegUnitWeight(AdjustUnit, UberSet->Weight - RegWeight);
  1550. // The unit may be shared among sets and registers within this set.
  1551. computeUberWeights(UberSets, RegBank);
  1552. }
  1553. Changed = true;
  1554. }
  1555. // Mark these units normalized so superregisters can't change their weights.
  1556. NormalUnits |= Reg->getRegUnits();
  1557. return Changed;
  1558. }
  1559. // Compute a weight for each register unit created during getSubRegs.
  1560. //
  1561. // The goal is that two registers in the same class will have the same weight,
  1562. // where each register's weight is defined as sum of its units' weights.
  1563. void CodeGenRegBank::computeRegUnitWeights() {
  1564. std::vector<UberRegSet> UberSets;
  1565. std::vector<UberRegSet*> RegSets(Registers.size());
  1566. computeUberSets(UberSets, RegSets, *this);
  1567. // UberSets and RegSets are now immutable.
  1568. computeUberWeights(UberSets, *this);
  1569. // Iterate over each Register, normalizing the unit weights until reaching
  1570. // a fix point.
  1571. unsigned NumIters = 0;
  1572. for (bool Changed = true; Changed; ++NumIters) {
  1573. assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights");
  1574. Changed = false;
  1575. for (auto &Reg : Registers) {
  1576. CodeGenRegister::RegUnitList NormalUnits;
  1577. BitVector NormalRegs;
  1578. Changed |= normalizeWeight(&Reg, UberSets, RegSets, NormalRegs,
  1579. NormalUnits, *this);
  1580. }
  1581. }
  1582. }
  1583. // Find a set in UniqueSets with the same elements as Set.
  1584. // Return an iterator into UniqueSets.
  1585. static std::vector<RegUnitSet>::const_iterator
  1586. findRegUnitSet(const std::vector<RegUnitSet> &UniqueSets,
  1587. const RegUnitSet &Set) {
  1588. std::vector<RegUnitSet>::const_iterator
  1589. I = UniqueSets.begin(), E = UniqueSets.end();
  1590. for(;I != E; ++I) {
  1591. if (I->Units == Set.Units)
  1592. break;
  1593. }
  1594. return I;
  1595. }
  1596. // Return true if the RUSubSet is a subset of RUSuperSet.
  1597. static bool isRegUnitSubSet(const std::vector<unsigned> &RUSubSet,
  1598. const std::vector<unsigned> &RUSuperSet) {
  1599. return std::includes(RUSuperSet.begin(), RUSuperSet.end(),
  1600. RUSubSet.begin(), RUSubSet.end());
  1601. }
  1602. /// Iteratively prune unit sets. Prune subsets that are close to the superset,
  1603. /// but with one or two registers removed. We occasionally have registers like
  1604. /// APSR and PC thrown in with the general registers. We also see many
  1605. /// special-purpose register subsets, such as tail-call and Thumb
  1606. /// encodings. Generating all possible overlapping sets is combinatorial and
  1607. /// overkill for modeling pressure. Ideally we could fix this statically in
  1608. /// tablegen by (1) having the target define register classes that only include
  1609. /// the allocatable registers and marking other classes as non-allocatable and
  1610. /// (2) having a way to mark special purpose classes as "don't-care" classes for
  1611. /// the purpose of pressure. However, we make an attempt to handle targets that
  1612. /// are not nicely defined by merging nearly identical register unit sets
  1613. /// statically. This generates smaller tables. Then, dynamically, we adjust the
  1614. /// set limit by filtering the reserved registers.
  1615. ///
  1616. /// Merge sets only if the units have the same weight. For example, on ARM,
  1617. /// Q-tuples with ssub index 0 include all S regs but also include D16+. We
  1618. /// should not expand the S set to include D regs.
  1619. void CodeGenRegBank::pruneUnitSets() {
  1620. assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets");
  1621. // Form an equivalence class of UnitSets with no significant difference.
  1622. std::vector<unsigned> SuperSetIDs;
  1623. for (unsigned SubIdx = 0, EndIdx = RegUnitSets.size();
  1624. SubIdx != EndIdx; ++SubIdx) {
  1625. const RegUnitSet &SubSet = RegUnitSets[SubIdx];
  1626. unsigned SuperIdx = 0;
  1627. for (; SuperIdx != EndIdx; ++SuperIdx) {
  1628. if (SuperIdx == SubIdx)
  1629. continue;
  1630. unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight;
  1631. const RegUnitSet &SuperSet = RegUnitSets[SuperIdx];
  1632. if (isRegUnitSubSet(SubSet.Units, SuperSet.Units)
  1633. && (SubSet.Units.size() + 3 > SuperSet.Units.size())
  1634. && UnitWeight == RegUnits[SuperSet.Units[0]].Weight
  1635. && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) {
  1636. LLVM_DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx
  1637. << "\n");
  1638. // We can pick any of the set names for the merged set. Go for the
  1639. // shortest one to avoid picking the name of one of the classes that are
  1640. // artificially created by tablegen. So "FPR128_lo" instead of
  1641. // "QQQQ_with_qsub3_in_FPR128_lo".
  1642. if (RegUnitSets[SubIdx].Name.size() < RegUnitSets[SuperIdx].Name.size())
  1643. RegUnitSets[SuperIdx].Name = RegUnitSets[SubIdx].Name;
  1644. break;
  1645. }
  1646. }
  1647. if (SuperIdx == EndIdx)
  1648. SuperSetIDs.push_back(SubIdx);
  1649. }
  1650. // Populate PrunedUnitSets with each equivalence class's superset.
  1651. std::vector<RegUnitSet> PrunedUnitSets(SuperSetIDs.size());
  1652. for (unsigned i = 0, e = SuperSetIDs.size(); i != e; ++i) {
  1653. unsigned SuperIdx = SuperSetIDs[i];
  1654. PrunedUnitSets[i].Name = RegUnitSets[SuperIdx].Name;
  1655. PrunedUnitSets[i].Units.swap(RegUnitSets[SuperIdx].Units);
  1656. }
  1657. RegUnitSets.swap(PrunedUnitSets);
  1658. }
  1659. // Create a RegUnitSet for each RegClass that contains all units in the class
  1660. // including adopted units that are necessary to model register pressure. Then
  1661. // iteratively compute RegUnitSets such that the union of any two overlapping
  1662. // RegUnitSets is repreresented.
  1663. //
  1664. // RegisterInfoEmitter will map each RegClass to its RegUnitClass and any
  1665. // RegUnitSet that is a superset of that RegUnitClass.
  1666. void CodeGenRegBank::computeRegUnitSets() {
  1667. assert(RegUnitSets.empty() && "dirty RegUnitSets");
  1668. // Compute a unique RegUnitSet for each RegClass.
  1669. auto &RegClasses = getRegClasses();
  1670. for (auto &RC : RegClasses) {
  1671. if (!RC.Allocatable || RC.Artificial || !RC.GeneratePressureSet)
  1672. continue;
  1673. // Speculatively grow the RegUnitSets to hold the new set.
  1674. RegUnitSets.resize(RegUnitSets.size() + 1);
  1675. RegUnitSets.back().Name = RC.getName();
  1676. // Compute a sorted list of units in this class.
  1677. RC.buildRegUnitSet(*this, RegUnitSets.back().Units);
  1678. // Find an existing RegUnitSet.
  1679. std::vector<RegUnitSet>::const_iterator SetI =
  1680. findRegUnitSet(RegUnitSets, RegUnitSets.back());
  1681. if (SetI != std::prev(RegUnitSets.end()))
  1682. RegUnitSets.pop_back();
  1683. }
  1684. LLVM_DEBUG(dbgs() << "\nBefore pruning:\n"; for (unsigned USIdx = 0,
  1685. USEnd = RegUnitSets.size();
  1686. USIdx < USEnd; ++USIdx) {
  1687. dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name << ":";
  1688. for (auto &U : RegUnitSets[USIdx].Units)
  1689. printRegUnitName(U);
  1690. dbgs() << "\n";
  1691. });
  1692. // Iteratively prune unit sets.
  1693. pruneUnitSets();
  1694. LLVM_DEBUG(dbgs() << "\nBefore union:\n"; for (unsigned USIdx = 0,
  1695. USEnd = RegUnitSets.size();
  1696. USIdx < USEnd; ++USIdx) {
  1697. dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name << ":";
  1698. for (auto &U : RegUnitSets[USIdx].Units)
  1699. printRegUnitName(U);
  1700. dbgs() << "\n";
  1701. } dbgs() << "\nUnion sets:\n");
  1702. // Iterate over all unit sets, including new ones added by this loop.
  1703. unsigned NumRegUnitSubSets = RegUnitSets.size();
  1704. for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
  1705. // In theory, this is combinatorial. In practice, it needs to be bounded
  1706. // by a small number of sets for regpressure to be efficient.
  1707. // If the assert is hit, we need to implement pruning.
  1708. assert(Idx < (2*NumRegUnitSubSets) && "runaway unit set inference");
  1709. // Compare new sets with all original classes.
  1710. for (unsigned SearchIdx = (Idx >= NumRegUnitSubSets) ? 0 : Idx+1;
  1711. SearchIdx != EndIdx; ++SearchIdx) {
  1712. std::set<unsigned> Intersection;
  1713. std::set_intersection(RegUnitSets[Idx].Units.begin(),
  1714. RegUnitSets[Idx].Units.end(),
  1715. RegUnitSets[SearchIdx].Units.begin(),
  1716. RegUnitSets[SearchIdx].Units.end(),
  1717. std::inserter(Intersection, Intersection.begin()));
  1718. if (Intersection.empty())
  1719. continue;
  1720. // Speculatively grow the RegUnitSets to hold the new set.
  1721. RegUnitSets.resize(RegUnitSets.size() + 1);
  1722. RegUnitSets.back().Name =
  1723. RegUnitSets[Idx].Name + "_with_" + RegUnitSets[SearchIdx].Name;
  1724. std::set_union(RegUnitSets[Idx].Units.begin(),
  1725. RegUnitSets[Idx].Units.end(),
  1726. RegUnitSets[SearchIdx].Units.begin(),
  1727. RegUnitSets[SearchIdx].Units.end(),
  1728. std::inserter(RegUnitSets.back().Units,
  1729. RegUnitSets.back().Units.begin()));
  1730. // Find an existing RegUnitSet, or add the union to the unique sets.
  1731. std::vector<RegUnitSet>::const_iterator SetI =
  1732. findRegUnitSet(RegUnitSets, RegUnitSets.back());
  1733. if (SetI != std::prev(RegUnitSets.end()))
  1734. RegUnitSets.pop_back();
  1735. else {
  1736. LLVM_DEBUG(dbgs() << "UnitSet " << RegUnitSets.size() - 1 << " "
  1737. << RegUnitSets.back().Name << ":";
  1738. for (auto &U
  1739. : RegUnitSets.back().Units) printRegUnitName(U);
  1740. dbgs() << "\n";);
  1741. }
  1742. }
  1743. }
  1744. // Iteratively prune unit sets after inferring supersets.
  1745. pruneUnitSets();
  1746. LLVM_DEBUG(
  1747. dbgs() << "\n"; for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
  1748. USIdx < USEnd; ++USIdx) {
  1749. dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name << ":";
  1750. for (auto &U : RegUnitSets[USIdx].Units)
  1751. printRegUnitName(U);
  1752. dbgs() << "\n";
  1753. });
  1754. // For each register class, list the UnitSets that are supersets.
  1755. RegClassUnitSets.resize(RegClasses.size());
  1756. int RCIdx = -1;
  1757. for (auto &RC : RegClasses) {
  1758. ++RCIdx;
  1759. if (!RC.Allocatable)
  1760. continue;
  1761. // Recompute the sorted list of units in this class.
  1762. std::vector<unsigned> RCRegUnits;
  1763. RC.buildRegUnitSet(*this, RCRegUnits);
  1764. // Don't increase pressure for unallocatable regclasses.
  1765. if (RCRegUnits.empty())
  1766. continue;
  1767. LLVM_DEBUG(dbgs() << "RC " << RC.getName() << " Units:\n";
  1768. for (auto U
  1769. : RCRegUnits) printRegUnitName(U);
  1770. dbgs() << "\n UnitSetIDs:");
  1771. // Find all supersets.
  1772. for (unsigned USIdx = 0, USEnd = RegUnitSets.size();
  1773. USIdx != USEnd; ++USIdx) {
  1774. if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) {
  1775. LLVM_DEBUG(dbgs() << " " << USIdx);
  1776. RegClassUnitSets[RCIdx].push_back(USIdx);
  1777. }
  1778. }
  1779. LLVM_DEBUG(dbgs() << "\n");
  1780. assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass");
  1781. }
  1782. // For each register unit, ensure that we have the list of UnitSets that
  1783. // contain the unit. Normally, this matches an existing list of UnitSets for a
  1784. // register class. If not, we create a new entry in RegClassUnitSets as a
  1785. // "fake" register class.
  1786. for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits;
  1787. UnitIdx < UnitEnd; ++UnitIdx) {
  1788. std::vector<unsigned> RUSets;
  1789. for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) {
  1790. RegUnitSet &RUSet = RegUnitSets[i];
  1791. if (!is_contained(RUSet.Units, UnitIdx))
  1792. continue;
  1793. RUSets.push_back(i);
  1794. }
  1795. unsigned RCUnitSetsIdx = 0;
  1796. for (unsigned e = RegClassUnitSets.size();
  1797. RCUnitSetsIdx != e; ++RCUnitSetsIdx) {
  1798. if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) {
  1799. break;
  1800. }
  1801. }
  1802. RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx;
  1803. if (RCUnitSetsIdx == RegClassUnitSets.size()) {
  1804. // Create a new list of UnitSets as a "fake" register class.
  1805. RegClassUnitSets.resize(RCUnitSetsIdx + 1);
  1806. RegClassUnitSets[RCUnitSetsIdx].swap(RUSets);
  1807. }
  1808. }
  1809. }
  1810. void CodeGenRegBank::computeRegUnitLaneMasks() {
  1811. for (auto &Register : Registers) {
  1812. // Create an initial lane mask for all register units.
  1813. const auto &RegUnits = Register.getRegUnits();
  1814. CodeGenRegister::RegUnitLaneMaskList
  1815. RegUnitLaneMasks(RegUnits.count(), LaneBitmask::getNone());
  1816. // Iterate through SubRegisters.
  1817. typedef CodeGenRegister::SubRegMap SubRegMap;
  1818. const SubRegMap &SubRegs = Register.getSubRegs();
  1819. for (SubRegMap::const_iterator S = SubRegs.begin(),
  1820. SE = SubRegs.end(); S != SE; ++S) {
  1821. CodeGenRegister *SubReg = S->second;
  1822. // Ignore non-leaf subregisters, their lane masks are fully covered by
  1823. // the leaf subregisters anyway.
  1824. if (!SubReg->getSubRegs().empty())
  1825. continue;
  1826. CodeGenSubRegIndex *SubRegIndex = S->first;
  1827. const CodeGenRegister *SubRegister = S->second;
  1828. LaneBitmask LaneMask = SubRegIndex->LaneMask;
  1829. // Distribute LaneMask to Register Units touched.
  1830. for (unsigned SUI : SubRegister->getRegUnits()) {
  1831. bool Found = false;
  1832. unsigned u = 0;
  1833. for (unsigned RU : RegUnits) {
  1834. if (SUI == RU) {
  1835. RegUnitLaneMasks[u] |= LaneMask;
  1836. assert(!Found);
  1837. Found = true;
  1838. }
  1839. ++u;
  1840. }
  1841. (void)Found;
  1842. assert(Found);
  1843. }
  1844. }
  1845. Register.setRegUnitLaneMasks(RegUnitLaneMasks);
  1846. }
  1847. }
  1848. void CodeGenRegBank::computeDerivedInfo() {
  1849. computeComposites();
  1850. computeSubRegLaneMasks();
  1851. // Compute a weight for each register unit created during getSubRegs.
  1852. // This may create adopted register units (with unit # >= NumNativeRegUnits).
  1853. computeRegUnitWeights();
  1854. // Compute a unique set of RegUnitSets. One for each RegClass and inferred
  1855. // supersets for the union of overlapping sets.
  1856. computeRegUnitSets();
  1857. computeRegUnitLaneMasks();
  1858. // Compute register class HasDisjunctSubRegs/CoveredBySubRegs flag.
  1859. for (CodeGenRegisterClass &RC : RegClasses) {
  1860. RC.HasDisjunctSubRegs = false;
  1861. RC.CoveredBySubRegs = true;
  1862. for (const CodeGenRegister *Reg : RC.getMembers()) {
  1863. RC.HasDisjunctSubRegs |= Reg->HasDisjunctSubRegs;
  1864. RC.CoveredBySubRegs &= Reg->CoveredBySubRegs;
  1865. }
  1866. }
  1867. // Get the weight of each set.
  1868. for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
  1869. RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units);
  1870. // Find the order of each set.
  1871. RegUnitSetOrder.reserve(RegUnitSets.size());
  1872. for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx)
  1873. RegUnitSetOrder.push_back(Idx);
  1874. llvm::stable_sort(RegUnitSetOrder, [this](unsigned ID1, unsigned ID2) {
  1875. return getRegPressureSet(ID1).Units.size() <
  1876. getRegPressureSet(ID2).Units.size();
  1877. });
  1878. for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) {
  1879. RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx;
  1880. }
  1881. }
  1882. //
  1883. // Synthesize missing register class intersections.
  1884. //
  1885. // Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X)
  1886. // returns a maximal register class for all X.
  1887. //
  1888. void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) {
  1889. assert(!RegClasses.empty());
  1890. // Stash the iterator to the last element so that this loop doesn't visit
  1891. // elements added by the getOrCreateSubClass call within it.
  1892. for (auto I = RegClasses.begin(), E = std::prev(RegClasses.end());
  1893. I != std::next(E); ++I) {
  1894. CodeGenRegisterClass *RC1 = RC;
  1895. CodeGenRegisterClass *RC2 = &*I;
  1896. if (RC1 == RC2)
  1897. continue;
  1898. // Compute the set intersection of RC1 and RC2.
  1899. const CodeGenRegister::Vec &Memb1 = RC1->getMembers();
  1900. const CodeGenRegister::Vec &Memb2 = RC2->getMembers();
  1901. CodeGenRegister::Vec Intersection;
  1902. std::set_intersection(Memb1.begin(), Memb1.end(), Memb2.begin(),
  1903. Memb2.end(),
  1904. std::inserter(Intersection, Intersection.begin()),
  1905. deref<std::less<>>());
  1906. // Skip disjoint class pairs.
  1907. if (Intersection.empty())
  1908. continue;
  1909. // If RC1 and RC2 have different spill sizes or alignments, use the
  1910. // stricter one for sub-classing. If they are equal, prefer RC1.
  1911. if (RC2->RSI.hasStricterSpillThan(RC1->RSI))
  1912. std::swap(RC1, RC2);
  1913. getOrCreateSubClass(RC1, &Intersection,
  1914. RC1->getName() + "_and_" + RC2->getName());
  1915. }
  1916. }
  1917. //
  1918. // Synthesize missing sub-classes for getSubClassWithSubReg().
  1919. //
  1920. // Make sure that the set of registers in RC with a given SubIdx sub-register
  1921. // form a register class. Update RC->SubClassWithSubReg.
  1922. //
  1923. void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
  1924. // Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
  1925. typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Vec,
  1926. deref<std::less<>>>
  1927. SubReg2SetMap;
  1928. // Compute the set of registers supporting each SubRegIndex.
  1929. SubReg2SetMap SRSets;
  1930. for (const auto R : RC->getMembers()) {
  1931. if (R->Artificial)
  1932. continue;
  1933. const CodeGenRegister::SubRegMap &SRM = R->getSubRegs();
  1934. for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(),
  1935. E = SRM.end(); I != E; ++I) {
  1936. if (!I->first->Artificial)
  1937. SRSets[I->first].push_back(R);
  1938. }
  1939. }
  1940. for (auto I : SRSets)
  1941. sortAndUniqueRegisters(I.second);
  1942. // Find matching classes for all SRSets entries. Iterate in SubRegIndex
  1943. // numerical order to visit synthetic indices last.
  1944. for (const auto &SubIdx : SubRegIndices) {
  1945. if (SubIdx.Artificial)
  1946. continue;
  1947. SubReg2SetMap::const_iterator I = SRSets.find(&SubIdx);
  1948. // Unsupported SubRegIndex. Skip it.
  1949. if (I == SRSets.end())
  1950. continue;
  1951. // In most cases, all RC registers support the SubRegIndex.
  1952. if (I->second.size() == RC->getMembers().size()) {
  1953. RC->setSubClassWithSubReg(&SubIdx, RC);
  1954. continue;
  1955. }
  1956. // This is a real subset. See if we have a matching class.
  1957. CodeGenRegisterClass *SubRC =
  1958. getOrCreateSubClass(RC, &I->second,
  1959. RC->getName() + "_with_" + I->first->getName());
  1960. RC->setSubClassWithSubReg(&SubIdx, SubRC);
  1961. }
  1962. }
  1963. //
  1964. // Synthesize missing sub-classes of RC for getMatchingSuperRegClass().
  1965. //
  1966. // Create sub-classes of RC such that getMatchingSuperRegClass(RC, SubIdx, X)
  1967. // has a maximal result for any SubIdx and any X >= FirstSubRegRC.
  1968. //
  1969. void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC,
  1970. std::list<CodeGenRegisterClass>::iterator FirstSubRegRC) {
  1971. SmallVector<std::pair<const CodeGenRegister*,
  1972. const CodeGenRegister*>, 16> SSPairs;
  1973. BitVector TopoSigs(getNumTopoSigs());
  1974. // Iterate in SubRegIndex numerical order to visit synthetic indices last.
  1975. for (auto &SubIdx : SubRegIndices) {
  1976. // Skip indexes that aren't fully supported by RC's registers. This was
  1977. // computed by inferSubClassWithSubReg() above which should have been
  1978. // called first.
  1979. if (RC->getSubClassWithSubReg(&SubIdx) != RC)
  1980. continue;
  1981. // Build list of (Super, Sub) pairs for this SubIdx.
  1982. SSPairs.clear();
  1983. TopoSigs.reset();
  1984. for (const auto Super : RC->getMembers()) {
  1985. const CodeGenRegister *Sub = Super->getSubRegs().find(&SubIdx)->second;
  1986. assert(Sub && "Missing sub-register");
  1987. SSPairs.push_back(std::make_pair(Super, Sub));
  1988. TopoSigs.set(Sub->getTopoSig());
  1989. }
  1990. // Iterate over sub-register class candidates. Ignore classes created by
  1991. // this loop. They will never be useful.
  1992. // Store an iterator to the last element (not end) so that this loop doesn't
  1993. // visit newly inserted elements.
  1994. assert(!RegClasses.empty());
  1995. for (auto I = FirstSubRegRC, E = std::prev(RegClasses.end());
  1996. I != std::next(E); ++I) {
  1997. CodeGenRegisterClass &SubRC = *I;
  1998. if (SubRC.Artificial)
  1999. continue;
  2000. // Topological shortcut: SubRC members have the wrong shape.
  2001. if (!TopoSigs.anyCommon(SubRC.getTopoSigs()))
  2002. continue;
  2003. // Compute the subset of RC that maps into SubRC.
  2004. CodeGenRegister::Vec SubSetVec;
  2005. for (unsigned i = 0, e = SSPairs.size(); i != e; ++i)
  2006. if (SubRC.contains(SSPairs[i].second))
  2007. SubSetVec.push_back(SSPairs[i].first);
  2008. if (SubSetVec.empty())
  2009. continue;
  2010. // RC injects completely into SubRC.
  2011. sortAndUniqueRegisters(SubSetVec);
  2012. if (SubSetVec.size() == SSPairs.size()) {
  2013. SubRC.addSuperRegClass(&SubIdx, RC);
  2014. continue;
  2015. }
  2016. // Only a subset of RC maps into SubRC. Make sure it is represented by a
  2017. // class.
  2018. getOrCreateSubClass(RC, &SubSetVec, RC->getName() + "_with_" +
  2019. SubIdx.getName() + "_in_" +
  2020. SubRC.getName());
  2021. }
  2022. }
  2023. }
  2024. //
  2025. // Infer missing register classes.
  2026. //
  2027. void CodeGenRegBank::computeInferredRegisterClasses() {
  2028. assert(!RegClasses.empty());
  2029. // When this function is called, the register classes have not been sorted
  2030. // and assigned EnumValues yet. That means getSubClasses(),
  2031. // getSuperClasses(), and hasSubClass() functions are defunct.
  2032. // Use one-before-the-end so it doesn't move forward when new elements are
  2033. // added.
  2034. auto FirstNewRC = std::prev(RegClasses.end());
  2035. // Visit all register classes, including the ones being added by the loop.
  2036. // Watch out for iterator invalidation here.
  2037. for (auto I = RegClasses.begin(), E = RegClasses.end(); I != E; ++I) {
  2038. CodeGenRegisterClass *RC = &*I;
  2039. if (RC->Artificial)
  2040. continue;
  2041. // Synthesize answers for getSubClassWithSubReg().
  2042. inferSubClassWithSubReg(RC);
  2043. // Synthesize answers for getCommonSubClass().
  2044. inferCommonSubClass(RC);
  2045. // Synthesize answers for getMatchingSuperRegClass().
  2046. inferMatchingSuperRegClass(RC);
  2047. // New register classes are created while this loop is running, and we need
  2048. // to visit all of them. I particular, inferMatchingSuperRegClass needs
  2049. // to match old super-register classes with sub-register classes created
  2050. // after inferMatchingSuperRegClass was called. At this point,
  2051. // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC =
  2052. // [0..FirstNewRC). We need to cover SubRC = [FirstNewRC..rci].
  2053. if (I == FirstNewRC) {
  2054. auto NextNewRC = std::prev(RegClasses.end());
  2055. for (auto I2 = RegClasses.begin(), E2 = std::next(FirstNewRC); I2 != E2;
  2056. ++I2)
  2057. inferMatchingSuperRegClass(&*I2, E2);
  2058. FirstNewRC = NextNewRC;
  2059. }
  2060. }
  2061. }
  2062. /// getRegisterClassForRegister - Find the register class that contains the
  2063. /// specified physical register. If the register is not in a register class,
  2064. /// return null. If the register is in multiple classes, and the classes have a
  2065. /// superset-subset relationship and the same set of types, return the
  2066. /// superclass. Otherwise return null.
  2067. const CodeGenRegisterClass*
  2068. CodeGenRegBank::getRegClassForRegister(Record *R) {
  2069. const CodeGenRegister *Reg = getReg(R);
  2070. const CodeGenRegisterClass *FoundRC = nullptr;
  2071. for (const auto &RC : getRegClasses()) {
  2072. if (!RC.contains(Reg))
  2073. continue;
  2074. // If this is the first class that contains the register,
  2075. // make a note of it and go on to the next class.
  2076. if (!FoundRC) {
  2077. FoundRC = &RC;
  2078. continue;
  2079. }
  2080. // If a register's classes have different types, return null.
  2081. if (RC.getValueTypes() != FoundRC->getValueTypes())
  2082. return nullptr;
  2083. // Check to see if the previously found class that contains
  2084. // the register is a subclass of the current class. If so,
  2085. // prefer the superclass.
  2086. if (RC.hasSubClass(FoundRC)) {
  2087. FoundRC = &RC;
  2088. continue;
  2089. }
  2090. // Check to see if the previously found class that contains
  2091. // the register is a superclass of the current class. If so,
  2092. // prefer the superclass.
  2093. if (FoundRC->hasSubClass(&RC))
  2094. continue;
  2095. // Multiple classes, and neither is a superclass of the other.
  2096. // Return null.
  2097. return nullptr;
  2098. }
  2099. return FoundRC;
  2100. }
  2101. const CodeGenRegisterClass *
  2102. CodeGenRegBank::getMinimalPhysRegClass(Record *RegRecord,
  2103. ValueTypeByHwMode *VT) {
  2104. const CodeGenRegister *Reg = getReg(RegRecord);
  2105. const CodeGenRegisterClass *BestRC = nullptr;
  2106. for (const auto &RC : getRegClasses()) {
  2107. if ((!VT || RC.hasType(*VT)) &&
  2108. RC.contains(Reg) && (!BestRC || BestRC->hasSubClass(&RC)))
  2109. BestRC = &RC;
  2110. }
  2111. assert(BestRC && "Couldn't find the register class");
  2112. return BestRC;
  2113. }
  2114. BitVector CodeGenRegBank::computeCoveredRegisters(ArrayRef<Record*> Regs) {
  2115. SetVector<const CodeGenRegister*> Set;
  2116. // First add Regs with all sub-registers.
  2117. for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
  2118. CodeGenRegister *Reg = getReg(Regs[i]);
  2119. if (Set.insert(Reg))
  2120. // Reg is new, add all sub-registers.
  2121. // The pre-ordering is not important here.
  2122. Reg->addSubRegsPreOrder(Set, *this);
  2123. }
  2124. // Second, find all super-registers that are completely covered by the set.
  2125. for (unsigned i = 0; i != Set.size(); ++i) {
  2126. const CodeGenRegister::SuperRegList &SR = Set[i]->getSuperRegs();
  2127. for (unsigned j = 0, e = SR.size(); j != e; ++j) {
  2128. const CodeGenRegister *Super = SR[j];
  2129. if (!Super->CoveredBySubRegs || Set.count(Super))
  2130. continue;
  2131. // This new super-register is covered by its sub-registers.
  2132. bool AllSubsInSet = true;
  2133. const CodeGenRegister::SubRegMap &SRM = Super->getSubRegs();
  2134. for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(),
  2135. E = SRM.end(); I != E; ++I)
  2136. if (!Set.count(I->second)) {
  2137. AllSubsInSet = false;
  2138. break;
  2139. }
  2140. // All sub-registers in Set, add Super as well.
  2141. // We will visit Super later to recheck its super-registers.
  2142. if (AllSubsInSet)
  2143. Set.insert(Super);
  2144. }
  2145. }
  2146. // Convert to BitVector.
  2147. BitVector BV(Registers.size() + 1);
  2148. for (unsigned i = 0, e = Set.size(); i != e; ++i)
  2149. BV.set(Set[i]->EnumValue);
  2150. return BV;
  2151. }
  2152. void CodeGenRegBank::printRegUnitName(unsigned Unit) const {
  2153. if (Unit < NumNativeRegUnits)
  2154. dbgs() << ' ' << RegUnits[Unit].Roots[0]->getName();
  2155. else
  2156. dbgs() << " #" << Unit;
  2157. }