/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/utils/TableGen/CodeGenRegisters.cpp

Bug Summary

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

Annotated Source Code

//===- CodeGenRegisters.cpp - Register and RegisterClass Info -------------===//

// The LLVM Compiler Infrastructure

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//===----------------------------------------------------------------------===//

// This file defines structures to encapsulate information gleaned from the

// target register and register class definitions.

//===----------------------------------------------------------------------===//

#include "CodeGenRegisters.h"

#include "CodeGenTarget.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/BitVector.h"

#include "llvm/ADT/DenseMap.h"

#include "llvm/ADT/IntEqClasses.h"

#include "llvm/ADT/SetVector.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/SparseBitVector.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/Twine.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/MathExtras.h"

#include "llvm/Support/raw_ostream.h"

#include "llvm/TableGen/Error.h"

#include "llvm/TableGen/Record.h"

#include <algorithm>

#include <cassert>

#include <cstdint>

#include <iterator>

#include <map>

#include <set>

#include <string>

#include <tuple>

#include <utility>

#include <vector>

using namespace llvm;

#define DEBUG_TYPE"regalloc-emitter" "regalloc-emitter"

//===----------------------------------------------------------------------===//

// CodeGenSubRegIndex

//===----------------------------------------------------------------------===//

CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum)

: TheDef(R), EnumValue(Enum), AllSuperRegsCovered(true) {

Name = R->getName();

if (R->getValue("Namespace"))

Namespace = R->getValueAsString("Namespace");

Size = R->getValueAsInt("Size");

Offset = R->getValueAsInt("Offset");

}

CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace,

unsigned Enum)

: TheDef(nullptr), Name(N), Namespace(Nspace), Size(-1), Offset(-1),

EnumValue(Enum), AllSuperRegsCovered(true) {

}

std::string CodeGenSubRegIndex::getQualifiedName() const {

std::string N = getNamespace();

if (!N.empty())

N += "::";

N += getName();

return N;

}

void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) {

if (!TheDef)

return;

std::vector<Record*> Comps = TheDef->getValueAsListOfDefs("ComposedOf");

if (!Comps.empty()) {

if (Comps.size() != 2)

PrintFatalError(TheDef->getLoc(),

"ComposedOf must have exactly two entries");

CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]);

CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]);

CodeGenSubRegIndex *X = A->addComposite(B, this);

if (X)

PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries");

}

std::vector<Record*> Parts =

TheDef->getValueAsListOfDefs("CoveringSubRegIndices");

if (!Parts.empty()) {

if (Parts.size() < 2)

PrintFatalError(TheDef->getLoc(),

"CoveredBySubRegs must have two or more entries");

SmallVector<CodeGenSubRegIndex*, 8> IdxParts;

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

105

LaneBitmask 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~svn303373/utils/TableGen/CodeGenRegisters.cpp"
, 117, __PRETTY_FUNCTION__));

118

LaneMask = M;

119

return LaneMask;

120

}

121

122

//===----------------------------------------------------------------------===//

123

// CodeGenRegister

124

//===----------------------------------------------------------------------===//

125

126

CodeGenRegister::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

137

void 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

168

const 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~svn303373/utils/TableGen/CodeGenRegisters.cpp"
, 169, __PRETTY_FUNCTION__));

170

return TheDef->getName();

171

}

172

173

namespace {

174

175

// Iterate over all register units in a set of registers.

176

class RegUnitIterator {

177

CodeGenRegister::Vec::const_iterator RegI, RegE;

178

CodeGenRegister::RegUnitList::iterator UnitI, UnitE;

179

180

public:

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~svn303373/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~svn303373/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~svn303373/utils/TableGen/CodeGenRegisters.cpp"
, 199, __PRETTY_FUNCTION__));

200

++UnitI;

201

advance();

202

}

203

204

protected:

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.

218

static 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.

224

bool 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

236

const CodeGenRegister::SubRegMap &

237

CodeGenRegister::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

432

void 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~svn303373/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~svn303373/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

500

void 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

530

void

531

CodeGenRegister::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~svn303373/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.

546

unsigned 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.

562

namespace {

563

564

struct 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

672

static 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

677

CodeGenRegisterClass::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~svn303373/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.

745

CodeGenRegisterClass::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.

762

void 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~svn303373/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~svn303373/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

787

bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {

788

return std::binary_search(Members.begin(), Members.end(), Reg,

789

deref<llvm::less>());

790

}

791

792

namespace 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.

805

bool CodeGenRegisterClass::Key::

806

operator<(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~svn303373/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

821

static 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

///

836

static 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

866

std::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.

875

void 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

923

void 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.

933

void 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

947

CodeGenRegBank::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.

1037

CodeGenSubRegIndex*

1038

CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) {

1039

SubRegIndices.emplace_back(Name, Namespace, SubRegIndices.size() + 1);

1040

return &SubRegIndices.back();

1041

}

1042

1043

CodeGenSubRegIndex *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

1052

CodeGenRegister *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

1061

void 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.

1072

CodeGenRegisterClass*

1073

CodeGenRegBank::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

1088

CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) {

1089

if (CodeGenRegisterClass *RC = Def2RC[Def])

1090

return RC;

1091

1092

PrintFatalError(Def->getLoc(), "Not a known RegisterClass!");

1093

}

1094

1095

CodeGenSubRegIndex*

1096

CodeGenRegBank::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

1110

CodeGenSubRegIndex *CodeGenRegBank::

1111

getConcatSubRegIndex(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~svn303373/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

1141

void 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~svn303373/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.

1191

void 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()) {

Assuming the condition is false

Taking false branch

Assuming the condition is false

Taking false branch

Assuming the condition is false

→

←

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()) {

←

Assuming the condition is false

Taking false branch

Assuming the condition is true

→

←

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~svn303373/utils/TableGen/CodeGenRegisters.cpp"
, 1229, __PRETTY_FUNCTION__))

←

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~svn303373/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())

←

Assuming the condition is false

Taking false branch

Assuming the condition is false

→

←

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)

Taking true branch

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~svn303373/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())

←

Assuming the condition is false

Taking false branch

Assuming the condition is false

→

←

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~svn303373/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

←

'?' condition is true

→

←

'?' condition is true

→

1263

: LaneBitmask::BitWidth + Shift;

1264

for (auto &I : LaneTransforms) {

←

Assuming '__begin' is equal to '__end'

→

←

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()) {

Taking true branch

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)

←

Assuming the condition is false

→

←

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) {

←

Assuming the condition is false

→

←

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

1322

namespace {

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.

1340

struct 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.

1354

static 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~svn303373/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~svn303373/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~svn303373/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.

1415

static 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 " <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 " <Regs) dbgs() << " " << Unit
->getName(); dbgs() << "\n"; } } while (false)

1443

for (auto &Unit : I->Regs)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "UberSet " <Regs) dbgs() << " " << Unit
->getName(); dbgs() << "\n"; } } while (false)

1444

dbgs() << " " << Unit->getName();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "UberSet " <Regs) dbgs() << " " << Unit
->getName(); dbgs() << "\n"; } } while (false)

1445

dbgs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("regalloc-emitter")) { dbgs() << "UberSet " <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.

1469

static 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.

1531

void 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~svn303373/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.

1556

static std::vector<RegUnitSet>::const_iterator

1557

findRegUnitSet(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.

1569

static 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.

1592

void 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~svn303373/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.

1642

void 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~svn303373/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~svn303373/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~svn303373/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

1811

void 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~svn303373/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~svn303373/utils/TableGen/CodeGenRegisters.cpp"
, 1843, __PRETTY_FUNCTION__));

1844

}

1845

}

1846

1847

}

1848

}

1849

1850

void 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

1899

void 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~svn303373/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

1940

void 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

1984

void 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~svn303373/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

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

2047

void CodeGenRegBank::computeInferredRegisterClasses() {

2048

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.

2092

const CodeGenRegisterClass*

2093

CodeGenRegBank::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

2132

BitVector 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

2174

void CodeGenRegBank::printRegUnitName(unsigned Unit) const {

2175

if (Unit < NumNativeRegUnits)

2176

dbgs() << ' ' << RegUnits[Unit].Roots[0]->getName();

2177

else

2178

dbgs() << " #" << Unit;

2179

}