AArch64A57FPLoadBalancing.cpp Source File (original) (raw)

44using namespace llvm;

46#define DEBUG_TYPE "aarch64-a57-fp-load-balancing"

51 TransformAll("aarch64-a57-fp-load-balancing-force-all",

52 cl::desc("Always modify dest registers regardless of color"),

59 cl::desc("Ignore balance information, always return "

60 "(1: Even, 2: Odd)."),

68 switch (MI->getOpcode()) {

69 case AArch64::FMULSrr:

70 case AArch64::FNMULSrr:

71 case AArch64::FMULDrr:

72 case AArch64::FNMULDrr:

73 return true;

74 default:

75 return false;

76 }

77}

81 switch (MI->getOpcode()) {

82 case AArch64::FMSUBSrrr:

83 case AArch64::FMADDSrrr:

84 case AArch64::FNMSUBSrrr:

85 case AArch64::FNMADDSrrr:

86 case AArch64::FMSUBDrrr:

87 case AArch64::FMADDDrrr:

88 case AArch64::FNMSUBDrrr:

89 case AArch64::FNMADDDrrr:

90 return true;

91 default:

92 return false;

93 }

94}

98namespace {

100

101enum class Color { Even, Odd };

102#ifndef NDEBUG

103static const char *ColorNames[2] = { "Even", "Odd" };

104#endif

105

106class Chain;

107

109 MachineRegisterInfo *MRI;

110 const TargetRegisterInfo *TRI;

111 RegisterClassInfo RCI;

112

113public:

114 static char ID;

115 explicit AArch64A57FPLoadBalancing() : MachineFunctionPass(ID) {}

116

117 bool runOnMachineFunction(MachineFunction &F) override;

118

119 MachineFunctionProperties getRequiredProperties() const override {

120 return MachineFunctionProperties().setNoVRegs();

121 }

122

123 StringRef getPassName() const override {

124 return "A57 FP Anti-dependency breaker";

125 }

126

127 void getAnalysisUsage(AnalysisUsage &AU) const override {

130 }

131

132private:

134 bool colorChainSet(std::vector<Chain*> GV, MachineBasicBlock &MBB,

135 int &Balance);

136 bool colorChain(Chain *G, Color C, MachineBasicBlock &MBB);

137 int scavengeRegister(Chain *G, Color C, MachineBasicBlock &MBB);

138 void scanInstruction(MachineInstr *MI, unsigned Idx,

139 std::map<unsigned, Chain*> &Active,

140 std::vector<std::unique_ptr> &AllChains);

141 void maybeKillChain(MachineOperand &MO, unsigned Idx,

142 std::map<unsigned, Chain*> &RegChains);

143 Color getColor(unsigned Register);

144 Chain *getAndEraseNext(Color PreferredColor, std::vector<Chain*> &L);

145};

146}

147

148char AArch64A57FPLoadBalancing::ID = 0;

149

151 "AArch64 A57 FP Load-Balancing", false, false)

154

155namespace {

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

182public:

183

185

186

188

189 std::set<MachineInstr*> Insts;

190

191

192

194

195

196

198

205

206

207

213 "Chain: broken invariant. A Chain can only be killed after its last "

214 "def");

215

217 }

218

219

221

222

224 return Insts.size();

225 }

226

227

228

234 "Chain: broken invariant. A Chain can only be killed after its last "

235 "def");

236 }

237

238

240

242

244

245

250

251

253

254

260

261

264 unsigned OtherEnd = Other.KillInst ?

265 Other.KillInstIdx : Other.LastInstIdx;

266

268 }

269

270

274

275

279

280

281 std::string str() const {

282 std::string S;

284

285 OS << "{";

286 StartInst->print(OS, true);

287 OS << " -> ";

288 LastInst->print(OS, true);

290 OS << " (kill @ ";

291 KillInst->print(OS, true);

292 OS << ")";

293 }

294 OS << "}";

295

296 return OS.str();

297 }

298

299};

300

301}

302

303

304

305bool AArch64A57FPLoadBalancing::runOnMachineFunction(MachineFunction &F) {

306 if (skipFunction(F.getFunction()))

307 return false;

308

309 if (.getSubtarget().balanceFPOps())

310 return false;

311

313 LLVM_DEBUG(dbgs() << "***** AArch64A57FPLoadBalancing *****\n");

314

315 MRI = &F.getRegInfo();

316 TRI = F.getRegInfo().getTargetRegisterInfo();

318

319 for (auto &MBB : F) {

321 }

322

324}

325

326bool AArch64A57FPLoadBalancing::runOnBasicBlock(MachineBasicBlock &MBB) {

329 << " - scanning instructions...\n");

330

331

332

333

334

335

336 std::map<unsigned, Chain*> ActiveChains;

337 std::vector<std::unique_ptr> AllChains;

338 unsigned Idx = 0;

339 for (auto &MI : MBB)

340 scanInstruction(&MI, Idx++, ActiveChains, AllChains);

341

342 LLVM_DEBUG(dbgs() << "Scan complete, " << AllChains.size()

343 << " chains created.\n");

344

345

346

347

348

349

350

351

352 EquivalenceClasses<Chain*> EC;

353 for (auto &I : AllChains)

354 EC.insert(I.get());

355

356 for (auto &I : AllChains)

357 for (auto &J : AllChains)

358 if (I != J && I->rangeOverlapsWith(*J))

359 EC.unionSets(I.get(), J.get());

360 LLVM_DEBUG(dbgs() << "Created " << EC.getNumClasses() << " disjoint sets.\n");

361

362

363

364

365

366 std::vector<std::vector<Chain*> > V;

367 for (const auto &E : EC) {

368 if (->isLeader())

369 continue;

370 std::vector<Chain *> Cs(EC.member_begin(*E), EC.member_end());

371 if (Cs.empty()) continue;

372 V.push_back(std::move(Cs));

373 }

374

375

376

378 [](const std::vector<Chain *> &A, const std::vector<Chain *> &B) {

379 return A.front()->startsBefore(B.front());

380 });

381

382

383

384

385

386

387

388

389

390

391

392

393 int Parity = 0;

394

395 for (auto &I : V)

396 Changed |= colorChainSet(std::move(I), MBB, Parity);

397

399}

400

401Chain *AArch64A57FPLoadBalancing::getAndEraseNext(Color PreferredColor,

402 std::vector<Chain*> &L) {

403 if (L.empty())

404 return nullptr;

405

406

407

408

409

410

411

412

413

414 const unsigned SizeFuzz = 1;

415 unsigned MinSize = L.front()->size() - SizeFuzz;

416 for (auto I = L.begin(), E = L.end(); I != E; ++I) {

417 if ((*I)->size() <= MinSize) {

418

419 Chain *Ch = *--I;

420 L.erase(I);

421 return Ch;

422 }

423

424 if ((*I)->getPreferredColor() == PreferredColor) {

425 Chain *Ch = *I;

426 L.erase(I);

427 return Ch;

428 }

429 }

430

431

432 Chain *Ch = L.front();

433 L.erase(L.begin());

434 return Ch;

435}

436

437bool AArch64A57FPLoadBalancing::colorChainSet(std::vector<Chain*> GV,

438 MachineBasicBlock &MBB,

439 int &Parity) {

441 LLVM_DEBUG(dbgs() << "colorChainSet(): #sets=" << GV.size() << "\n");

442

443

444

445

446

447

448

449

450

451

452 llvm::sort(GV, [](const Chain *G1, const Chain *G2) {

453 if (G1->size() != G2->size())

454 return G1->size() > G2->size();

455 if (G1->requiresFixup() != G2->requiresFixup())

456 return G1->requiresFixup() > G2->requiresFixup();

457

458 assert((G1 == G2 || (G1->startsBefore(G2) ^ G2->startsBefore(G1))) &&

459 "Starts before not total order!");

460 return G1->startsBefore(G2);

461 });

462

463 Color PreferredColor = Parity < 0 ? Color::Even : Color::Odd;

464 while (Chain *G = getAndEraseNext(PreferredColor, GV)) {

465

466 Color C = PreferredColor;

467 if (Parity == 0)

468

469 C = G->getPreferredColor();

470

472 << ", Color=" << ColorNames[(int)C] << "\n");

473

474

475

476

477 if (G->requiresFixup() && C != G->getPreferredColor()) {

478 C = G->getPreferredColor();

480 << " - not worthwhile changing; "

481 "color remains "

482 << ColorNames[(int)C] << "\n");

483 }

484

486

487 Parity += (C == Color::Even) ? G->size() : -G->size();

488 PreferredColor = Parity < 0 ? Color::Even : Color::Odd;

489 }

490

492}

493

494int AArch64A57FPLoadBalancing::scavengeRegister(Chain *G, Color C,

495 MachineBasicBlock &MBB) {

496

497

498 LiveRegUnits Units(*TRI);

499 Units.addLiveOuts(MBB);

502 while (I != ChainEnd) {

503 --I;

504 Units.stepBackward(*I);

505 }

506

507

509 assert(ChainBegin != ChainEnd && "Chain should contain instructions");

510 do {

511 --I;

512 Units.accumulate(*I);

513 } while (I != ChainBegin);

514

515

516 unsigned RegClassID = ChainBegin->getDesc().operands()[0].RegClass;

517 auto Ord = RCI.getOrder(TRI->getRegClass(RegClassID));

518 for (auto Reg : Ord) {

519 if (!Units.available(Reg))

520 continue;

521 if (C == getColor(Reg))

522 return Reg;

523 }

524

525 return -1;

526}

527

528bool AArch64A57FPLoadBalancing::colorChain(Chain *G, Color C,

529 MachineBasicBlock &MBB) {

531 LLVM_DEBUG(dbgs() << " - colorChain(" << G->str() << ", "

532 << ColorNames[(int)C] << ")\n");

533

534

535

536 int Reg = scavengeRegister(G, C, MBB);

537 if (Reg == -1) {

538 LLVM_DEBUG(dbgs() << "Scavenging (thus coloring) failed!\n");

539 return false;

540 }

542

543 std::map<unsigned, unsigned> Substs;

544 for (MachineInstr &I : *G) {

545 if (->contains(I) && (&I != G->getKill() || G->isKillImmutable()))

546 continue;

547

548

549

550 std::vector ToErase;

551 for (auto &U : I.operands()) {

552 if (U.isReg() && U.isUse() && Substs.find(U.getReg()) != Substs.end()) {

554 U.setReg(Substs[OrigReg]);

555 if (U.isKill())

556

557

558 ToErase.push_back(OrigReg);

559 } else if (U.isRegMask()) {

560 for (auto J : Substs) {

561 if (U.clobbersPhysReg(J.first))

562 ToErase.push_back(J.first);

563 }

564 }

565 }

566

567 for (auto J : ToErase)

568 Substs.erase(J);

569

570

571 if (&I != G->getKill()) {

572 MachineOperand &MO = I.getOperand(0);

573

575 if (G->requiresFixup() && &I == G->getLast())

576 Change = false;

577

578 if (Change) {

581

583 }

584 }

585 }

586 assert(Substs.size() == 0 && "No substitutions should be left active!");

587

588 if (G->getKill()) {

590 } else {

591

592

593 LLVM_DEBUG(dbgs() << " - Destination register not changed.\n");

594 }

596}

597

598void AArch64A57FPLoadBalancing::scanInstruction(

599 MachineInstr *MI, unsigned Idx, std::map<unsigned, Chain *> &ActiveChains,

600 std::vector<std::unique_ptr> &AllChains) {

601

602

604

605 for (auto &I : MI->uses())

606 maybeKillChain(I, Idx, ActiveChains);

607 for (auto &I : MI->defs())

608 maybeKillChain(I, Idx, ActiveChains);

609

610

611

612 Register DestReg = MI->getOperand(0).getReg();

613

614 LLVM_DEBUG(dbgs() << "New chain started for register "

616

617 auto G = std::make_unique(MI, Idx, getColor(DestReg));

618 ActiveChains[DestReg] = G.get();

619 AllChains.push_back(std::move(G));

620

622

623

624

625 Register DestReg = MI->getOperand(0).getReg();

626 Register AccumReg = MI->getOperand(3).getReg();

627

628 maybeKillChain(MI->getOperand(1), Idx, ActiveChains);

629 maybeKillChain(MI->getOperand(2), Idx, ActiveChains);

630 if (DestReg != AccumReg)

631 maybeKillChain(MI->getOperand(0), Idx, ActiveChains);

632

633 if (ActiveChains.find(AccumReg) != ActiveChains.end()) {

634 LLVM_DEBUG(dbgs() << "Chain found for accumulator register "

636

637

638

639

640

641

642 if (MI->getOperand(3).isKill()) {

643

644 LLVM_DEBUG(dbgs() << "Instruction was successfully added to chain.\n");

645 ActiveChains[AccumReg]->add(MI, Idx, getColor(DestReg));

646

647 if (DestReg != AccumReg) {

648 ActiveChains[DestReg] = ActiveChains[AccumReg];

649 ActiveChains.erase(AccumReg);

650 }

651 return;

652 }

653

655 dbgs() << "Cannot add to chain because accumulator operand wasn't "

656 << "marked !\n");

657 maybeKillChain(MI->getOperand(3), Idx, ActiveChains);

658 }

659

660 LLVM_DEBUG(dbgs() << "Creating new chain for dest register "

662 auto G = std::make_unique(MI, Idx, getColor(DestReg));

663 ActiveChains[DestReg] = G.get();

664 AllChains.push_back(std::move(G));

665

666 } else {

667

668

669

670 for (auto &I : MI->uses())

671 maybeKillChain(I, Idx, ActiveChains);

672 for (auto &I : MI->defs())

673 maybeKillChain(I, Idx, ActiveChains);

674

675 }

676}

677

678void AArch64A57FPLoadBalancing::

679maybeKillChain(MachineOperand &MO, unsigned Idx,

680 std::map<unsigned, Chain*> &ActiveChains) {

681

682

684

685 if (MO.isReg()) {

686

687

688 if (MO.isKill() && ActiveChains.find(MO.getReg()) != ActiveChains.end()) {

690 << "\n");

691 ActiveChains[MO.getReg()]->setKill(MI, Idx, MO.isTied());

692 }

693 ActiveChains.erase(MO.getReg());

694

696

697 for (auto I = ActiveChains.begin(), E = ActiveChains.end();

698 I != E;) {

700 LLVM_DEBUG(dbgs() << "Kill (regmask) seen for chain "

702 I->second->setKill(MI, Idx, true);

703 ActiveChains.erase(I++);

704 } else

705 ++I;

706 }

707

708 }

709}

710

711Color AArch64A57FPLoadBalancing::getColor(unsigned Reg) {

712 if ((TRI->getEncodingValue(Reg) % 2) == 0)

713 return Color::Even;

714 else

715 return Color::Odd;

716}

717

718

720 return new AArch64A57FPLoadBalancing();

721}

static bool isMul(MachineInstr *MI)

Definition AArch64A57FPLoadBalancing.cpp:67

static cl::opt< unsigned > OverrideBalance("aarch64-a57-fp-load-balancing-override", cl::desc("Ignore balance information, always return " "(1: Even, 2: Odd)."), cl::init(0), cl::Hidden)

static cl::opt< bool > TransformAll("aarch64-a57-fp-load-balancing-force-all", cl::desc("Always modify dest registers regardless of color"), cl::init(false), cl::Hidden)

static bool isMla(MachineInstr *MI)

Definition AArch64A57FPLoadBalancing.cpp:80

unsigned const MachineRegisterInfo * MRI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

static bool runOnBasicBlock(MachineBasicBlock *MBB, unsigned BasicBlockNum, VRegRenamer &Renamer)

Promote Memory to Register

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

This file declares the machine register scavenger class.

MachineInstr * StartInst

The important (marker) instructions.

Definition AArch64A57FPLoadBalancing.cpp:184

MachineBasicBlock::iterator begin() const

Definition AArch64A57FPLoadBalancing.cpp:249

bool isKillImmutable() const

Can the Kill instruction (assuming one exists) be modified?

Definition AArch64A57FPLoadBalancing.cpp:252

unsigned LastInstIdx

Definition AArch64A57FPLoadBalancing.cpp:187

void add(MachineInstr *MI, unsigned Idx, Color C)

Add a new instruction into the chain.

Definition AArch64A57FPLoadBalancing.cpp:208

bool contains(MachineInstr &MI)

Return true if MI is a member of the chain.

Definition AArch64A57FPLoadBalancing.cpp:220

Color LastColor

The "color" of LastInst.

Definition AArch64A57FPLoadBalancing.cpp:197

bool requiresFixup() const

Return true if the group will require a fixup MOV at the end.

Definition AArch64A57FPLoadBalancing.cpp:276

MachineInstr * getLast() const

Return the last instruction in the chain.

Definition AArch64A57FPLoadBalancing.cpp:241

MachineInstr * LastInst

Definition AArch64A57FPLoadBalancing.cpp:184

MachineInstr * KillInst

Definition AArch64A57FPLoadBalancing.cpp:184

bool KillIsImmutable

True if KillInst cannot be modified.

Definition AArch64A57FPLoadBalancing.cpp:193

bool rangeOverlapsWith(const Chain &Other) const

Return true if this chain (StartInst..KillInst) overlaps with Other.

Definition AArch64A57FPLoadBalancing.cpp:262

MachineInstr * getStart() const

Return the first instruction in the chain.

Definition AArch64A57FPLoadBalancing.cpp:239

unsigned size() const

Return the number of instructions in the chain.

Definition AArch64A57FPLoadBalancing.cpp:223

MachineBasicBlock::iterator end() const

Return an instruction that can be used as an iterator for the end of the chain.

Definition AArch64A57FPLoadBalancing.cpp:246

void setKill(MachineInstr *MI, unsigned Idx, bool Immutable)

Inform the chain that its last active register (the dest register of LastInst) is killed by MI with n...

Definition AArch64A57FPLoadBalancing.cpp:229

MachineInstr * getKill() const

Return the "kill" instruction (as set with setKill()) or NULL.

Definition AArch64A57FPLoadBalancing.cpp:243

unsigned StartInstIdx

The index, from the start of the basic block, that each marker appears.

Definition AArch64A57FPLoadBalancing.cpp:187

unsigned KillInstIdx

Definition AArch64A57FPLoadBalancing.cpp:187

Color getPreferredColor()

Return the preferred color of this chain.

Definition AArch64A57FPLoadBalancing.cpp:255

std::string str() const

Return a simple string representation of the chain.

Definition AArch64A57FPLoadBalancing.cpp:281

std::set< MachineInstr * > Insts

All instructions in the chain.

Definition AArch64A57FPLoadBalancing.cpp:189

Chain(MachineInstr *MI, unsigned Idx, Color C)

Definition AArch64A57FPLoadBalancing.cpp:199

bool startsBefore(const Chain *Other) const

Return true if this chain starts before Other.

Definition AArch64A57FPLoadBalancing.cpp:271

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

FunctionPass class - This class is used to implement most global optimizations.

MachineInstrBundleIterator< MachineInstr > iterator

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

Representation of each machine instruction.

bool isReg() const

isReg - Tests if this is a MO_Register operand.

bool isRegMask() const

isRegMask - Tests if this is a MO_RegisterMask operand.

LLVM_ABI void setReg(Register Reg)

Change the register this operand corresponds to.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

getReg - Returns the register number.

static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)

clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.

LLVM_ABI void runOnMachineFunction(const MachineFunction &MF, bool Rev=false)

runOnFunction - Prepare to answer questions about MF.

ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const

getOrder - Returns the preferred allocation order for RC.

A raw_ostream that writes to an std::string.

std::string & str()

Returns the string's reference.

@ C

The default llvm calling convention, compatible with C.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionPass * createAArch64A57FPLoadBalancing()

Definition AArch64A57FPLoadBalancing.cpp:719

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.