1 //===----- AggressiveAntiDepBreaker.cpp - Anti-dep breaker ----------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the AggressiveAntiDepBreaker class, which 11 // implements register anti-dependence breaking during post-RA 12 // scheduling. It attempts to break all anti-dependencies within a 13 // block. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "AggressiveAntiDepBreaker.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/MachineFrameInfo.h" 20 #include "llvm/CodeGen/MachineInstr.h" 21 #include "llvm/CodeGen/RegisterClassInfo.h" 22 #include "llvm/Support/CommandLine.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 #include "llvm/Target/TargetInstrInfo.h" 27 #include "llvm/Target/TargetRegisterInfo.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "post-RA-sched" 31 32 // If DebugDiv > 0 then only break antidep with (ID % DebugDiv) == DebugMod 33 static cl::opt<int> 34 DebugDiv("agg-antidep-debugdiv", 35 cl::desc("Debug control for aggressive anti-dep breaker"), 36 cl::init(0), cl::Hidden); 37 static cl::opt<int> 38 DebugMod("agg-antidep-debugmod", 39 cl::desc("Debug control for aggressive anti-dep breaker"), 40 cl::init(0), cl::Hidden); 41 42 AggressiveAntiDepState::AggressiveAntiDepState(const unsigned TargetRegs, 43 MachineBasicBlock *BB) : 44 NumTargetRegs(TargetRegs), GroupNodes(TargetRegs, 0), 45 GroupNodeIndices(TargetRegs, 0), 46 KillIndices(TargetRegs, 0), 47 DefIndices(TargetRegs, 0) 48 { 49 const unsigned BBSize = BB->size(); 50 for (unsigned i = 0; i < NumTargetRegs; ++i) { 51 // Initialize all registers to be in their own group. Initially we 52 // assign the register to the same-indexed GroupNode. 53 GroupNodeIndices[i] = i; 54 // Initialize the indices to indicate that no registers are live. 55 KillIndices[i] = ~0u; 56 DefIndices[i] = BBSize; 57 } 58 } 59 60 unsigned AggressiveAntiDepState::GetGroup(unsigned Reg) { 61 unsigned Node = GroupNodeIndices[Reg]; 62 while (GroupNodes[Node] != Node) 63 Node = GroupNodes[Node]; 64 65 return Node; 66 } 67 68 void AggressiveAntiDepState::GetGroupRegs( 69 unsigned Group, 70 std::vector<unsigned> &Regs, 71 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference> *RegRefs) 72 { 73 for (unsigned Reg = 0; Reg != NumTargetRegs; ++Reg) { 74 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) 75 Regs.push_back(Reg); 76 } 77 } 78 79 unsigned AggressiveAntiDepState::UnionGroups(unsigned Reg1, unsigned Reg2) 80 { 81 assert(GroupNodes[0] == 0 && "GroupNode 0 not parent!"); 82 assert(GroupNodeIndices[0] == 0 && "Reg 0 not in Group 0!"); 83 84 // find group for each register 85 unsigned Group1 = GetGroup(Reg1); 86 unsigned Group2 = GetGroup(Reg2); 87 88 // if either group is 0, then that must become the parent 89 unsigned Parent = (Group1 == 0) ? Group1 : Group2; 90 unsigned Other = (Parent == Group1) ? Group2 : Group1; 91 GroupNodes.at(Other) = Parent; 92 return Parent; 93 } 94 95 unsigned AggressiveAntiDepState::LeaveGroup(unsigned Reg) 96 { 97 // Create a new GroupNode for Reg. Reg's existing GroupNode must 98 // stay as is because there could be other GroupNodes referring to 99 // it. 100 unsigned idx = GroupNodes.size(); 101 GroupNodes.push_back(idx); 102 GroupNodeIndices[Reg] = idx; 103 return idx; 104 } 105 106 bool AggressiveAntiDepState::IsLive(unsigned Reg) 107 { 108 // KillIndex must be defined and DefIndex not defined for a register 109 // to be live. 110 return((KillIndices[Reg] != ~0u) && (DefIndices[Reg] == ~0u)); 111 } 112 113 AggressiveAntiDepBreaker::AggressiveAntiDepBreaker( 114 MachineFunction &MFi, const RegisterClassInfo &RCI, 115 TargetSubtargetInfo::RegClassVector &CriticalPathRCs) 116 : AntiDepBreaker(), MF(MFi), MRI(MF.getRegInfo()), 117 TII(MF.getSubtarget().getInstrInfo()), 118 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI), 119 State(nullptr) { 120 /* Collect a bitset of all registers that are only broken if they 121 are on the critical path. */ 122 for (unsigned i = 0, e = CriticalPathRCs.size(); i < e; ++i) { 123 BitVector CPSet = TRI->getAllocatableSet(MF, CriticalPathRCs[i]); 124 if (CriticalPathSet.none()) 125 CriticalPathSet = CPSet; 126 else 127 CriticalPathSet |= CPSet; 128 } 129 130 DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); 131 DEBUG(for (int r = CriticalPathSet.find_first(); r != -1; 132 r = CriticalPathSet.find_next(r)) 133 dbgs() << " " << TRI->getName(r)); 134 DEBUG(dbgs() << '\n'); 135 } 136 137 AggressiveAntiDepBreaker::~AggressiveAntiDepBreaker() { 138 delete State; 139 } 140 141 void AggressiveAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { 142 assert(!State); 143 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); 144 145 bool IsReturnBlock = BB->isReturnBlock(); 146 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 147 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 148 149 // Examine the live-in regs of all successors. 150 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 151 SE = BB->succ_end(); SI != SE; ++SI) 152 for (const auto &LI : (*SI)->liveins()) { 153 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { 154 unsigned Reg = *AI; 155 State->UnionGroups(Reg, 0); 156 KillIndices[Reg] = BB->size(); 157 DefIndices[Reg] = ~0u; 158 } 159 } 160 161 // Mark live-out callee-saved registers. In a return block this is 162 // all callee-saved registers. In non-return this is any 163 // callee-saved register that is not saved in the prolog. 164 const MachineFrameInfo *MFI = MF.getFrameInfo(); 165 BitVector Pristine = MFI->getPristineRegs(MF); 166 for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) { 167 unsigned Reg = *I; 168 if (!IsReturnBlock && !Pristine.test(Reg)) continue; 169 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 170 unsigned AliasReg = *AI; 171 State->UnionGroups(AliasReg, 0); 172 KillIndices[AliasReg] = BB->size(); 173 DefIndices[AliasReg] = ~0u; 174 } 175 } 176 } 177 178 void AggressiveAntiDepBreaker::FinishBlock() { 179 delete State; 180 State = nullptr; 181 } 182 183 void AggressiveAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, 184 unsigned InsertPosIndex) { 185 assert(Count < InsertPosIndex && "Instruction index out of expected range!"); 186 187 std::set<unsigned> PassthruRegs; 188 GetPassthruRegs(MI, PassthruRegs); 189 PrescanInstruction(MI, Count, PassthruRegs); 190 ScanInstruction(MI, Count); 191 192 DEBUG(dbgs() << "Observe: "); 193 DEBUG(MI->dump()); 194 DEBUG(dbgs() << "\tRegs:"); 195 196 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 197 for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { 198 // If Reg is current live, then mark that it can't be renamed as 199 // we don't know the extent of its live-range anymore (now that it 200 // has been scheduled). If it is not live but was defined in the 201 // previous schedule region, then set its def index to the most 202 // conservative location (i.e. the beginning of the previous 203 // schedule region). 204 if (State->IsLive(Reg)) { 205 DEBUG(if (State->GetGroup(Reg) != 0) 206 dbgs() << " " << TRI->getName(Reg) << "=g" << 207 State->GetGroup(Reg) << "->g0(region live-out)"); 208 State->UnionGroups(Reg, 0); 209 } else if ((DefIndices[Reg] < InsertPosIndex) 210 && (DefIndices[Reg] >= Count)) { 211 DefIndices[Reg] = Count; 212 } 213 } 214 DEBUG(dbgs() << '\n'); 215 } 216 217 bool AggressiveAntiDepBreaker::IsImplicitDefUse(MachineInstr *MI, 218 MachineOperand& MO) 219 { 220 if (!MO.isReg() || !MO.isImplicit()) 221 return false; 222 223 unsigned Reg = MO.getReg(); 224 if (Reg == 0) 225 return false; 226 227 MachineOperand *Op = nullptr; 228 if (MO.isDef()) 229 Op = MI->findRegisterUseOperand(Reg, true); 230 else 231 Op = MI->findRegisterDefOperand(Reg); 232 233 return(Op && Op->isImplicit()); 234 } 235 236 void AggressiveAntiDepBreaker::GetPassthruRegs(MachineInstr *MI, 237 std::set<unsigned>& PassthruRegs) { 238 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 239 MachineOperand &MO = MI->getOperand(i); 240 if (!MO.isReg()) continue; 241 if ((MO.isDef() && MI->isRegTiedToUseOperand(i)) || 242 IsImplicitDefUse(MI, MO)) { 243 const unsigned Reg = MO.getReg(); 244 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 245 SubRegs.isValid(); ++SubRegs) 246 PassthruRegs.insert(*SubRegs); 247 } 248 } 249 } 250 251 /// AntiDepEdges - Return in Edges the anti- and output- dependencies 252 /// in SU that we want to consider for breaking. 253 static void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) { 254 SmallSet<unsigned, 4> RegSet; 255 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 256 P != PE; ++P) { 257 if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) { 258 if (RegSet.insert(P->getReg()).second) 259 Edges.push_back(&*P); 260 } 261 } 262 } 263 264 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up 265 /// critical path. 266 static const SUnit *CriticalPathStep(const SUnit *SU) { 267 const SDep *Next = nullptr; 268 unsigned NextDepth = 0; 269 // Find the predecessor edge with the greatest depth. 270 if (SU) { 271 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 272 P != PE; ++P) { 273 const SUnit *PredSU = P->getSUnit(); 274 unsigned PredLatency = P->getLatency(); 275 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 276 // In the case of a latency tie, prefer an anti-dependency edge over 277 // other types of edges. 278 if (NextDepth < PredTotalLatency || 279 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 280 NextDepth = PredTotalLatency; 281 Next = &*P; 282 } 283 } 284 } 285 286 return (Next) ? Next->getSUnit() : nullptr; 287 } 288 289 void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, 290 const char *tag, 291 const char *header, 292 const char *footer) { 293 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 294 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 295 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 296 RegRefs = State->GetRegRefs(); 297 298 // FIXME: We must leave subregisters of live super registers as live, so that 299 // we don't clear out the register tracking information for subregisters of 300 // super registers we're still tracking (and with which we're unioning 301 // subregister definitions). 302 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 303 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) { 304 DEBUG(if (!header && footer) dbgs() << footer); 305 return; 306 } 307 308 if (!State->IsLive(Reg)) { 309 KillIndices[Reg] = KillIdx; 310 DefIndices[Reg] = ~0u; 311 RegRefs.erase(Reg); 312 State->LeaveGroup(Reg); 313 DEBUG(if (header) { 314 dbgs() << header << TRI->getName(Reg); header = nullptr; }); 315 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); 316 } 317 // Repeat for subregisters. 318 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 319 unsigned SubregReg = *SubRegs; 320 if (!State->IsLive(SubregReg)) { 321 KillIndices[SubregReg] = KillIdx; 322 DefIndices[SubregReg] = ~0u; 323 RegRefs.erase(SubregReg); 324 State->LeaveGroup(SubregReg); 325 DEBUG(if (header) { 326 dbgs() << header << TRI->getName(Reg); header = nullptr; }); 327 DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" << 328 State->GetGroup(SubregReg) << tag); 329 } 330 } 331 332 DEBUG(if (!header && footer) dbgs() << footer); 333 } 334 335 void AggressiveAntiDepBreaker::PrescanInstruction(MachineInstr *MI, 336 unsigned Count, 337 std::set<unsigned>& PassthruRegs) { 338 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 339 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 340 RegRefs = State->GetRegRefs(); 341 342 // Handle dead defs by simulating a last-use of the register just 343 // after the def. A dead def can occur because the def is truly 344 // dead, or because only a subregister is live at the def. If we 345 // don't do this the dead def will be incorrectly merged into the 346 // previous def. 347 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 348 MachineOperand &MO = MI->getOperand(i); 349 if (!MO.isReg() || !MO.isDef()) continue; 350 unsigned Reg = MO.getReg(); 351 if (Reg == 0) continue; 352 353 HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); 354 } 355 356 DEBUG(dbgs() << "\tDef Groups:"); 357 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 358 MachineOperand &MO = MI->getOperand(i); 359 if (!MO.isReg() || !MO.isDef()) continue; 360 unsigned Reg = MO.getReg(); 361 if (Reg == 0) continue; 362 363 DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg)); 364 365 // If MI's defs have a special allocation requirement, don't allow 366 // any def registers to be changed. Also assume all registers 367 // defined in a call must not be changed (ABI). Inline assembly may 368 // reference either system calls or the register directly. Skip it until we 369 // can tell user specified registers from compiler-specified. 370 if (MI->isCall() || MI->hasExtraDefRegAllocReq() || 371 TII->isPredicated(MI) || MI->isInlineAsm()) { 372 DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); 373 State->UnionGroups(Reg, 0); 374 } 375 376 // Any aliased that are live at this point are completely or 377 // partially defined here, so group those aliases with Reg. 378 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { 379 unsigned AliasReg = *AI; 380 if (State->IsLive(AliasReg)) { 381 State->UnionGroups(Reg, AliasReg); 382 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " << 383 TRI->getName(AliasReg) << ")"); 384 } 385 } 386 387 // Note register reference... 388 const TargetRegisterClass *RC = nullptr; 389 if (i < MI->getDesc().getNumOperands()) 390 RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 391 AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; 392 RegRefs.insert(std::make_pair(Reg, RR)); 393 } 394 395 DEBUG(dbgs() << '\n'); 396 397 // Scan the register defs for this instruction and update 398 // live-ranges. 399 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 400 MachineOperand &MO = MI->getOperand(i); 401 if (!MO.isReg() || !MO.isDef()) continue; 402 unsigned Reg = MO.getReg(); 403 if (Reg == 0) continue; 404 // Ignore KILLs and passthru registers for liveness... 405 if (MI->isKill() || (PassthruRegs.count(Reg) != 0)) 406 continue; 407 408 // Update def for Reg and aliases. 409 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 410 // We need to be careful here not to define already-live super registers. 411 // If the super register is already live, then this definition is not 412 // a definition of the whole super register (just a partial insertion 413 // into it). Earlier subregister definitions (which we've not yet visited 414 // because we're iterating bottom-up) need to be linked to the same group 415 // as this definition. 416 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) 417 continue; 418 419 DefIndices[*AI] = Count; 420 } 421 } 422 } 423 424 void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr *MI, 425 unsigned Count) { 426 DEBUG(dbgs() << "\tUse Groups:"); 427 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 428 RegRefs = State->GetRegRefs(); 429 430 // If MI's uses have special allocation requirement, don't allow 431 // any use registers to be changed. Also assume all registers 432 // used in a call must not be changed (ABI). 433 // Inline Assembly register uses also cannot be safely changed. 434 // FIXME: The issue with predicated instruction is more complex. We are being 435 // conservatively here because the kill markers cannot be trusted after 436 // if-conversion: 437 // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] 438 // ... 439 // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] 440 // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] 441 // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) 442 // 443 // The first R6 kill is not really a kill since it's killed by a predicated 444 // instruction which may not be executed. The second R6 def may or may not 445 // re-define R6 so it's not safe to change it since the last R6 use cannot be 446 // changed. 447 bool Special = MI->isCall() || 448 MI->hasExtraSrcRegAllocReq() || 449 TII->isPredicated(MI) || MI->isInlineAsm(); 450 451 // Scan the register uses for this instruction and update 452 // live-ranges, groups and RegRefs. 453 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 454 MachineOperand &MO = MI->getOperand(i); 455 if (!MO.isReg() || !MO.isUse()) continue; 456 unsigned Reg = MO.getReg(); 457 if (Reg == 0) continue; 458 459 DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << 460 State->GetGroup(Reg)); 461 462 // It wasn't previously live but now it is, this is a kill. Forget 463 // the previous live-range information and start a new live-range 464 // for the register. 465 HandleLastUse(Reg, Count, "(last-use)"); 466 467 if (Special) { 468 DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); 469 State->UnionGroups(Reg, 0); 470 } 471 472 // Note register reference... 473 const TargetRegisterClass *RC = nullptr; 474 if (i < MI->getDesc().getNumOperands()) 475 RC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 476 AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; 477 RegRefs.insert(std::make_pair(Reg, RR)); 478 } 479 480 DEBUG(dbgs() << '\n'); 481 482 // Form a group of all defs and uses of a KILL instruction to ensure 483 // that all registers are renamed as a group. 484 if (MI->isKill()) { 485 DEBUG(dbgs() << "\tKill Group:"); 486 487 unsigned FirstReg = 0; 488 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 489 MachineOperand &MO = MI->getOperand(i); 490 if (!MO.isReg()) continue; 491 unsigned Reg = MO.getReg(); 492 if (Reg == 0) continue; 493 494 if (FirstReg != 0) { 495 DEBUG(dbgs() << "=" << TRI->getName(Reg)); 496 State->UnionGroups(FirstReg, Reg); 497 } else { 498 DEBUG(dbgs() << " " << TRI->getName(Reg)); 499 FirstReg = Reg; 500 } 501 } 502 503 DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); 504 } 505 } 506 507 BitVector AggressiveAntiDepBreaker::GetRenameRegisters(unsigned Reg) { 508 BitVector BV(TRI->getNumRegs(), false); 509 bool first = true; 510 511 // Check all references that need rewriting for Reg. For each, use 512 // the corresponding register class to narrow the set of registers 513 // that are appropriate for renaming. 514 for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) { 515 const TargetRegisterClass *RC = Q.second.RC; 516 if (!RC) continue; 517 518 BitVector RCBV = TRI->getAllocatableSet(MF, RC); 519 if (first) { 520 BV |= RCBV; 521 first = false; 522 } else { 523 BV &= RCBV; 524 } 525 526 DEBUG(dbgs() << " " << TRI->getRegClassName(RC)); 527 } 528 529 return BV; 530 } 531 532 bool AggressiveAntiDepBreaker::FindSuitableFreeRegisters( 533 unsigned AntiDepGroupIndex, 534 RenameOrderType& RenameOrder, 535 std::map<unsigned, unsigned> &RenameMap) { 536 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 537 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 538 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 539 RegRefs = State->GetRegRefs(); 540 541 // Collect all referenced registers in the same group as 542 // AntiDepReg. These all need to be renamed together if we are to 543 // break the anti-dependence. 544 std::vector<unsigned> Regs; 545 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); 546 assert(Regs.size() > 0 && "Empty register group!"); 547 if (Regs.size() == 0) 548 return false; 549 550 // Find the "superest" register in the group. At the same time, 551 // collect the BitVector of registers that can be used to rename 552 // each register. 553 DEBUG(dbgs() << "\tRename Candidates for Group g" << AntiDepGroupIndex 554 << ":\n"); 555 std::map<unsigned, BitVector> RenameRegisterMap; 556 unsigned SuperReg = 0; 557 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 558 unsigned Reg = Regs[i]; 559 if ((SuperReg == 0) || TRI->isSuperRegister(SuperReg, Reg)) 560 SuperReg = Reg; 561 562 // If Reg has any references, then collect possible rename regs 563 if (RegRefs.count(Reg) > 0) { 564 DEBUG(dbgs() << "\t\t" << TRI->getName(Reg) << ":"); 565 566 BitVector BV = GetRenameRegisters(Reg); 567 RenameRegisterMap.insert(std::pair<unsigned, BitVector>(Reg, BV)); 568 569 DEBUG(dbgs() << " ::"); 570 DEBUG(for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) 571 dbgs() << " " << TRI->getName(r)); 572 DEBUG(dbgs() << "\n"); 573 } 574 } 575 576 // All group registers should be a subreg of SuperReg. 577 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 578 unsigned Reg = Regs[i]; 579 if (Reg == SuperReg) continue; 580 bool IsSub = TRI->isSubRegister(SuperReg, Reg); 581 // FIXME: remove this once PR18663 has been properly fixed. For now, 582 // return a conservative answer: 583 // assert(IsSub && "Expecting group subregister"); 584 if (!IsSub) 585 return false; 586 } 587 588 #ifndef NDEBUG 589 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod 590 if (DebugDiv > 0) { 591 static int renamecnt = 0; 592 if (renamecnt++ % DebugDiv != DebugMod) 593 return false; 594 595 dbgs() << "*** Performing rename " << TRI->getName(SuperReg) << 596 " for debug ***\n"; 597 } 598 #endif 599 600 // Check each possible rename register for SuperReg in round-robin 601 // order. If that register is available, and the corresponding 602 // registers are available for the other group subregisters, then we 603 // can use those registers to rename. 604 605 // FIXME: Using getMinimalPhysRegClass is very conservative. We should 606 // check every use of the register and find the largest register class 607 // that can be used in all of them. 608 const TargetRegisterClass *SuperRC = 609 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); 610 611 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); 612 if (Order.empty()) { 613 DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); 614 return false; 615 } 616 617 DEBUG(dbgs() << "\tFind Registers:"); 618 619 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); 620 621 unsigned OrigR = RenameOrder[SuperRC]; 622 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); 623 unsigned R = OrigR; 624 do { 625 if (R == 0) R = Order.size(); 626 --R; 627 const unsigned NewSuperReg = Order[R]; 628 // Don't consider non-allocatable registers 629 if (!MRI.isAllocatable(NewSuperReg)) continue; 630 // Don't replace a register with itself. 631 if (NewSuperReg == SuperReg) continue; 632 633 DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':'); 634 RenameMap.clear(); 635 636 // For each referenced group register (which must be a SuperReg or 637 // a subregister of SuperReg), find the corresponding subregister 638 // of NewSuperReg and make sure it is free to be renamed. 639 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 640 unsigned Reg = Regs[i]; 641 unsigned NewReg = 0; 642 if (Reg == SuperReg) { 643 NewReg = NewSuperReg; 644 } else { 645 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); 646 if (NewSubRegIdx != 0) 647 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); 648 } 649 650 DEBUG(dbgs() << " " << TRI->getName(NewReg)); 651 652 // Check if Reg can be renamed to NewReg. 653 BitVector BV = RenameRegisterMap[Reg]; 654 if (!BV.test(NewReg)) { 655 DEBUG(dbgs() << "(no rename)"); 656 goto next_super_reg; 657 } 658 659 // If NewReg is dead and NewReg's most recent def is not before 660 // Regs's kill, it's safe to replace Reg with NewReg. We 661 // must also check all aliases of NewReg, because we can't define a 662 // register when any sub or super is already live. 663 if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) { 664 DEBUG(dbgs() << "(live)"); 665 goto next_super_reg; 666 } else { 667 bool found = false; 668 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { 669 unsigned AliasReg = *AI; 670 if (State->IsLive(AliasReg) || 671 (KillIndices[Reg] > DefIndices[AliasReg])) { 672 DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)"); 673 found = true; 674 break; 675 } 676 } 677 if (found) 678 goto next_super_reg; 679 } 680 681 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also 682 // defines 'NewReg' via an early-clobber operand. 683 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { 684 MachineInstr *UseMI = Q.second.Operand->getParent(); 685 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI); 686 if (Idx == -1) 687 continue; 688 689 if (UseMI->getOperand(Idx).isEarlyClobber()) { 690 DEBUG(dbgs() << "(ec)"); 691 goto next_super_reg; 692 } 693 } 694 695 // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining 696 // 'Reg' is an early-clobber define and that instruction also uses 697 // 'NewReg'. 698 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { 699 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber()) 700 continue; 701 702 MachineInstr *DefMI = Q.second.Operand->getParent(); 703 if (DefMI->readsRegister(NewReg, TRI)) { 704 DEBUG(dbgs() << "(ec)"); 705 goto next_super_reg; 706 } 707 } 708 709 // Record that 'Reg' can be renamed to 'NewReg'. 710 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg)); 711 } 712 713 // If we fall-out here, then every register in the group can be 714 // renamed, as recorded in RenameMap. 715 RenameOrder.erase(SuperRC); 716 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R)); 717 DEBUG(dbgs() << "]\n"); 718 return true; 719 720 next_super_reg: 721 DEBUG(dbgs() << ']'); 722 } while (R != EndR); 723 724 DEBUG(dbgs() << '\n'); 725 726 // No registers are free and available! 727 return false; 728 } 729 730 /// BreakAntiDependencies - Identifiy anti-dependencies within the 731 /// ScheduleDAG and break them by renaming registers. 732 /// 733 unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( 734 const std::vector<SUnit>& SUnits, 735 MachineBasicBlock::iterator Begin, 736 MachineBasicBlock::iterator End, 737 unsigned InsertPosIndex, 738 DbgValueVector &DbgValues) { 739 740 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 741 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 742 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 743 RegRefs = State->GetRegRefs(); 744 745 // The code below assumes that there is at least one instruction, 746 // so just duck out immediately if the block is empty. 747 if (SUnits.empty()) return 0; 748 749 // For each regclass the next register to use for renaming. 750 RenameOrderType RenameOrder; 751 752 // ...need a map from MI to SUnit. 753 std::map<MachineInstr *, const SUnit *> MISUnitMap; 754 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 755 const SUnit *SU = &SUnits[i]; 756 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(), 757 SU)); 758 } 759 760 // Track progress along the critical path through the SUnit graph as 761 // we walk the instructions. This is needed for regclasses that only 762 // break critical-path anti-dependencies. 763 const SUnit *CriticalPathSU = nullptr; 764 MachineInstr *CriticalPathMI = nullptr; 765 if (CriticalPathSet.any()) { 766 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 767 const SUnit *SU = &SUnits[i]; 768 if (!CriticalPathSU || 769 ((SU->getDepth() + SU->Latency) > 770 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { 771 CriticalPathSU = SU; 772 } 773 } 774 775 CriticalPathMI = CriticalPathSU->getInstr(); 776 } 777 778 #ifndef NDEBUG 779 DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); 780 DEBUG(dbgs() << "Available regs:"); 781 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 782 if (!State->IsLive(Reg)) 783 DEBUG(dbgs() << " " << TRI->getName(Reg)); 784 } 785 DEBUG(dbgs() << '\n'); 786 #endif 787 788 // Attempt to break anti-dependence edges. Walk the instructions 789 // from the bottom up, tracking information about liveness as we go 790 // to help determine which registers are available. 791 unsigned Broken = 0; 792 unsigned Count = InsertPosIndex - 1; 793 for (MachineBasicBlock::iterator I = End, E = Begin; 794 I != E; --Count) { 795 MachineInstr *MI = --I; 796 797 if (MI->isDebugValue()) 798 continue; 799 800 DEBUG(dbgs() << "Anti: "); 801 DEBUG(MI->dump()); 802 803 std::set<unsigned> PassthruRegs; 804 GetPassthruRegs(MI, PassthruRegs); 805 806 // Process the defs in MI... 807 PrescanInstruction(MI, Count, PassthruRegs); 808 809 // The dependence edges that represent anti- and output- 810 // dependencies that are candidates for breaking. 811 std::vector<const SDep *> Edges; 812 const SUnit *PathSU = MISUnitMap[MI]; 813 AntiDepEdges(PathSU, Edges); 814 815 // If MI is not on the critical path, then we don't rename 816 // registers in the CriticalPathSet. 817 BitVector *ExcludeRegs = nullptr; 818 if (MI == CriticalPathMI) { 819 CriticalPathSU = CriticalPathStep(CriticalPathSU); 820 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; 821 } else if (CriticalPathSet.any()) { 822 ExcludeRegs = &CriticalPathSet; 823 } 824 825 // Ignore KILL instructions (they form a group in ScanInstruction 826 // but don't cause any anti-dependence breaking themselves) 827 if (!MI->isKill()) { 828 // Attempt to break each anti-dependency... 829 for (unsigned i = 0, e = Edges.size(); i != e; ++i) { 830 const SDep *Edge = Edges[i]; 831 SUnit *NextSU = Edge->getSUnit(); 832 833 if ((Edge->getKind() != SDep::Anti) && 834 (Edge->getKind() != SDep::Output)) continue; 835 836 unsigned AntiDepReg = Edge->getReg(); 837 DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); 838 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 839 840 if (!MRI.isAllocatable(AntiDepReg)) { 841 // Don't break anti-dependencies on non-allocatable registers. 842 DEBUG(dbgs() << " (non-allocatable)\n"); 843 continue; 844 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) { 845 // Don't break anti-dependencies for critical path registers 846 // if not on the critical path 847 DEBUG(dbgs() << " (not critical-path)\n"); 848 continue; 849 } else if (PassthruRegs.count(AntiDepReg) != 0) { 850 // If the anti-dep register liveness "passes-thru", then 851 // don't try to change it. It will be changed along with 852 // the use if required to break an earlier antidep. 853 DEBUG(dbgs() << " (passthru)\n"); 854 continue; 855 } else { 856 // No anti-dep breaking for implicit deps 857 MachineOperand *AntiDepOp = MI->findRegisterDefOperand(AntiDepReg); 858 assert(AntiDepOp && "Can't find index for defined register operand"); 859 if (!AntiDepOp || AntiDepOp->isImplicit()) { 860 DEBUG(dbgs() << " (implicit)\n"); 861 continue; 862 } 863 864 // If the SUnit has other dependencies on the SUnit that 865 // it anti-depends on, don't bother breaking the 866 // anti-dependency since those edges would prevent such 867 // units from being scheduled past each other 868 // regardless. 869 // 870 // Also, if there are dependencies on other SUnits with the 871 // same register as the anti-dependency, don't attempt to 872 // break it. 873 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 874 PE = PathSU->Preds.end(); P != PE; ++P) { 875 if (P->getSUnit() == NextSU ? 876 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 877 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 878 AntiDepReg = 0; 879 break; 880 } 881 } 882 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 883 PE = PathSU->Preds.end(); P != PE; ++P) { 884 if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) && 885 (P->getKind() != SDep::Output)) { 886 DEBUG(dbgs() << " (real dependency)\n"); 887 AntiDepReg = 0; 888 break; 889 } else if ((P->getSUnit() != NextSU) && 890 (P->getKind() == SDep::Data) && 891 (P->getReg() == AntiDepReg)) { 892 DEBUG(dbgs() << " (other dependency)\n"); 893 AntiDepReg = 0; 894 break; 895 } 896 } 897 898 if (AntiDepReg == 0) continue; 899 } 900 901 assert(AntiDepReg != 0); 902 if (AntiDepReg == 0) continue; 903 904 // Determine AntiDepReg's register group. 905 const unsigned GroupIndex = State->GetGroup(AntiDepReg); 906 if (GroupIndex == 0) { 907 DEBUG(dbgs() << " (zero group)\n"); 908 continue; 909 } 910 911 DEBUG(dbgs() << '\n'); 912 913 // Look for a suitable register to use to break the anti-dependence. 914 std::map<unsigned, unsigned> RenameMap; 915 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { 916 DEBUG(dbgs() << "\tBreaking anti-dependence edge on " 917 << TRI->getName(AntiDepReg) << ":"); 918 919 // Handle each group register... 920 for (std::map<unsigned, unsigned>::iterator 921 S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { 922 unsigned CurrReg = S->first; 923 unsigned NewReg = S->second; 924 925 DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" << 926 TRI->getName(NewReg) << "(" << 927 RegRefs.count(CurrReg) << " refs)"); 928 929 // Update the references to the old register CurrReg to 930 // refer to the new register NewReg. 931 for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) { 932 Q.second.Operand->setReg(NewReg); 933 // If the SU for the instruction being updated has debug 934 // information related to the anti-dependency register, make 935 // sure to update that as well. 936 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()]; 937 if (!SU) continue; 938 for (DbgValueVector::iterator DVI = DbgValues.begin(), 939 DVE = DbgValues.end(); DVI != DVE; ++DVI) 940 if (DVI->second == Q.second.Operand->getParent()) 941 UpdateDbgValue(DVI->first, AntiDepReg, NewReg); 942 } 943 944 // We just went back in time and modified history; the 945 // liveness information for CurrReg is now inconsistent. Set 946 // the state as if it were dead. 947 State->UnionGroups(NewReg, 0); 948 RegRefs.erase(NewReg); 949 DefIndices[NewReg] = DefIndices[CurrReg]; 950 KillIndices[NewReg] = KillIndices[CurrReg]; 951 952 State->UnionGroups(CurrReg, 0); 953 RegRefs.erase(CurrReg); 954 DefIndices[CurrReg] = KillIndices[CurrReg]; 955 KillIndices[CurrReg] = ~0u; 956 assert(((KillIndices[CurrReg] == ~0u) != 957 (DefIndices[CurrReg] == ~0u)) && 958 "Kill and Def maps aren't consistent for AntiDepReg!"); 959 } 960 961 ++Broken; 962 DEBUG(dbgs() << '\n'); 963 } 964 } 965 } 966 967 ScanInstruction(MI, Count); 968 } 969 970 return Broken; 971 } 972