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