Bug Summary

File:utils/TableGen/CodeGenRegisters.cpp
Warning:line 1228, column 7
The result of the '<<' expression is undefined

Annotated Source Code

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