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 if (!MO.isReg() || !MO.isImplicit()) 220 return false; 221 222 unsigned Reg = MO.getReg(); 223 if (Reg == 0) 224 return false; 225 226 MachineOperand *Op = nullptr; 227 if (MO.isDef()) 228 Op = MI.findRegisterUseOperand(Reg, true); 229 else 230 Op = MI.findRegisterDefOperand(Reg); 231 232 return(Op && Op->isImplicit()); 233 } 234 235 void AggressiveAntiDepBreaker::GetPassthruRegs( 236 MachineInstr &MI, std::set<unsigned> &PassthruRegs) { 237 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 238 MachineOperand &MO = MI.getOperand(i); 239 if (!MO.isReg()) continue; 240 if ((MO.isDef() && MI.isRegTiedToUseOperand(i)) || 241 IsImplicitDefUse(MI, MO)) { 242 const unsigned Reg = MO.getReg(); 243 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 244 SubRegs.isValid(); ++SubRegs) 245 PassthruRegs.insert(*SubRegs); 246 } 247 } 248 } 249 250 /// AntiDepEdges - Return in Edges the anti- and output- dependencies 251 /// in SU that we want to consider for breaking. 252 static void AntiDepEdges(const SUnit *SU, std::vector<const SDep*>& Edges) { 253 SmallSet<unsigned, 4> RegSet; 254 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 255 P != PE; ++P) { 256 if ((P->getKind() == SDep::Anti) || (P->getKind() == SDep::Output)) { 257 if (RegSet.insert(P->getReg()).second) 258 Edges.push_back(&*P); 259 } 260 } 261 } 262 263 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up 264 /// critical path. 265 static const SUnit *CriticalPathStep(const SUnit *SU) { 266 const SDep *Next = nullptr; 267 unsigned NextDepth = 0; 268 // Find the predecessor edge with the greatest depth. 269 if (SU) { 270 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 271 P != PE; ++P) { 272 const SUnit *PredSU = P->getSUnit(); 273 unsigned PredLatency = P->getLatency(); 274 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 275 // In the case of a latency tie, prefer an anti-dependency edge over 276 // other types of edges. 277 if (NextDepth < PredTotalLatency || 278 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 279 NextDepth = PredTotalLatency; 280 Next = &*P; 281 } 282 } 283 } 284 285 return (Next) ? Next->getSUnit() : nullptr; 286 } 287 288 void AggressiveAntiDepBreaker::HandleLastUse(unsigned Reg, unsigned KillIdx, 289 const char *tag, 290 const char *header, 291 const char *footer) { 292 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 293 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 294 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 295 RegRefs = State->GetRegRefs(); 296 297 // FIXME: We must leave subregisters of live super registers as live, so that 298 // we don't clear out the register tracking information for subregisters of 299 // super registers we're still tracking (and with which we're unioning 300 // subregister definitions). 301 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 302 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) { 303 DEBUG(if (!header && footer) dbgs() << footer); 304 return; 305 } 306 307 if (!State->IsLive(Reg)) { 308 KillIndices[Reg] = KillIdx; 309 DefIndices[Reg] = ~0u; 310 RegRefs.erase(Reg); 311 State->LeaveGroup(Reg); 312 DEBUG(if (header) { 313 dbgs() << header << TRI->getName(Reg); header = nullptr; }); 314 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); 315 // Repeat for subregisters. Note that we only do this if the superregister 316 // was not live because otherwise, regardless whether we have an explicit 317 // use of the subregister, the subregister's contents are needed for the 318 // uses of the superregister. 319 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 320 unsigned SubregReg = *SubRegs; 321 if (!State->IsLive(SubregReg)) { 322 KillIndices[SubregReg] = KillIdx; 323 DefIndices[SubregReg] = ~0u; 324 RegRefs.erase(SubregReg); 325 State->LeaveGroup(SubregReg); 326 DEBUG(if (header) { 327 dbgs() << header << TRI->getName(Reg); header = nullptr; }); 328 DEBUG(dbgs() << " " << TRI->getName(SubregReg) << "->g" << 329 State->GetGroup(SubregReg) << tag); 330 } 331 } 332 } 333 334 DEBUG(if (!header && footer) dbgs() << footer); 335 } 336 337 void AggressiveAntiDepBreaker::PrescanInstruction( 338 MachineInstr &MI, unsigned Count, std::set<unsigned> &PassthruRegs) { 339 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 340 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 341 RegRefs = State->GetRegRefs(); 342 343 // Handle dead defs by simulating a last-use of the register just 344 // after the def. A dead def can occur because the def is truly 345 // dead, or because only a subregister is live at the def. If we 346 // don't do this the dead def will be incorrectly merged into the 347 // previous def. 348 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 349 MachineOperand &MO = MI.getOperand(i); 350 if (!MO.isReg() || !MO.isDef()) continue; 351 unsigned Reg = MO.getReg(); 352 if (Reg == 0) continue; 353 354 HandleLastUse(Reg, Count + 1, "", "\tDead Def: ", "\n"); 355 } 356 357 DEBUG(dbgs() << "\tDef Groups:"); 358 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 359 MachineOperand &MO = MI.getOperand(i); 360 if (!MO.isReg() || !MO.isDef()) continue; 361 unsigned Reg = MO.getReg(); 362 if (Reg == 0) continue; 363 364 DEBUG(dbgs() << " " << TRI->getName(Reg) << "=g" << State->GetGroup(Reg)); 365 366 // If MI's defs have a special allocation requirement, don't allow 367 // any def registers to be changed. Also assume all registers 368 // defined in a call must not be changed (ABI). Inline assembly may 369 // reference either system calls or the register directly. Skip it until we 370 // can tell user specified registers from compiler-specified. 371 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) || 372 MI.isInlineAsm()) { 373 DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); 374 State->UnionGroups(Reg, 0); 375 } 376 377 // Any aliased that are live at this point are completely or 378 // partially defined here, so group those aliases with Reg. 379 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { 380 unsigned AliasReg = *AI; 381 if (State->IsLive(AliasReg)) { 382 State->UnionGroups(Reg, AliasReg); 383 DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " << 384 TRI->getName(AliasReg) << ")"); 385 } 386 } 387 388 // Note register reference... 389 const TargetRegisterClass *RC = nullptr; 390 if (i < MI.getDesc().getNumOperands()) 391 RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); 392 AggressiveAntiDepState::RegisterReference RR = { &MO, RC }; 393 RegRefs.insert(std::make_pair(Reg, RR)); 394 } 395 396 DEBUG(dbgs() << '\n'); 397 398 // Scan the register defs for this instruction and update 399 // live-ranges. 400 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 401 MachineOperand &MO = MI.getOperand(i); 402 if (!MO.isReg() || !MO.isDef()) continue; 403 unsigned Reg = MO.getReg(); 404 if (Reg == 0) continue; 405 // Ignore KILLs and passthru registers for liveness... 406 if (MI.isKill() || (PassthruRegs.count(Reg) != 0)) 407 continue; 408 409 // Update def for Reg and aliases. 410 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 411 // We need to be careful here not to define already-live super registers. 412 // If the super register is already live, then this definition is not 413 // a definition of the whole super register (just a partial insertion 414 // into it). Earlier subregister definitions (which we've not yet visited 415 // because we're iterating bottom-up) need to be linked to the same group 416 // as this definition. 417 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) 418 continue; 419 420 DefIndices[*AI] = Count; 421 } 422 } 423 } 424 425 void AggressiveAntiDepBreaker::ScanInstruction(MachineInstr &MI, 426 unsigned Count) { 427 DEBUG(dbgs() << "\tUse Groups:"); 428 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 429 RegRefs = State->GetRegRefs(); 430 431 // If MI's uses have special allocation requirement, don't allow 432 // any use registers to be changed. Also assume all registers 433 // used in a call must not be changed (ABI). 434 // Inline Assembly register uses also cannot be safely changed. 435 // FIXME: The issue with predicated instruction is more complex. We are being 436 // conservatively here because the kill markers cannot be trusted after 437 // if-conversion: 438 // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] 439 // ... 440 // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] 441 // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] 442 // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) 443 // 444 // The first R6 kill is not really a kill since it's killed by a predicated 445 // instruction which may not be executed. The second R6 def may or may not 446 // re-define R6 so it's not safe to change it since the last R6 use cannot be 447 // changed. 448 bool Special = MI.isCall() || 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 = RenameRegisterMap[Reg]; 567 assert(BV.empty()); 568 BV = GetRenameRegisters(Reg); 569 570 DEBUG({ 571 dbgs() << " ::"; 572 for (int r = BV.find_first(); r != -1; r = BV.find_next(r)) 573 dbgs() << " " << TRI->getName(r); 574 dbgs() << "\n"; 575 }); 576 } 577 } 578 579 // All group registers should be a subreg of SuperReg. 580 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 581 unsigned Reg = Regs[i]; 582 if (Reg == SuperReg) continue; 583 bool IsSub = TRI->isSubRegister(SuperReg, Reg); 584 // FIXME: remove this once PR18663 has been properly fixed. For now, 585 // return a conservative answer: 586 // assert(IsSub && "Expecting group subregister"); 587 if (!IsSub) 588 return false; 589 } 590 591 #ifndef NDEBUG 592 // If DebugDiv > 0 then only rename (renamecnt % DebugDiv) == DebugMod 593 if (DebugDiv > 0) { 594 static int renamecnt = 0; 595 if (renamecnt++ % DebugDiv != DebugMod) 596 return false; 597 598 dbgs() << "*** Performing rename " << TRI->getName(SuperReg) << 599 " for debug ***\n"; 600 } 601 #endif 602 603 // Check each possible rename register for SuperReg in round-robin 604 // order. If that register is available, and the corresponding 605 // registers are available for the other group subregisters, then we 606 // can use those registers to rename. 607 608 // FIXME: Using getMinimalPhysRegClass is very conservative. We should 609 // check every use of the register and find the largest register class 610 // that can be used in all of them. 611 const TargetRegisterClass *SuperRC = 612 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); 613 614 ArrayRef<MCPhysReg> Order = RegClassInfo.getOrder(SuperRC); 615 if (Order.empty()) { 616 DEBUG(dbgs() << "\tEmpty Super Regclass!!\n"); 617 return false; 618 } 619 620 DEBUG(dbgs() << "\tFind Registers:"); 621 622 RenameOrder.insert(RenameOrderType::value_type(SuperRC, Order.size())); 623 624 unsigned OrigR = RenameOrder[SuperRC]; 625 unsigned EndR = ((OrigR == Order.size()) ? 0 : OrigR); 626 unsigned R = OrigR; 627 do { 628 if (R == 0) R = Order.size(); 629 --R; 630 const unsigned NewSuperReg = Order[R]; 631 // Don't consider non-allocatable registers 632 if (!MRI.isAllocatable(NewSuperReg)) continue; 633 // Don't replace a register with itself. 634 if (NewSuperReg == SuperReg) continue; 635 636 DEBUG(dbgs() << " [" << TRI->getName(NewSuperReg) << ':'); 637 RenameMap.clear(); 638 639 // For each referenced group register (which must be a SuperReg or 640 // a subregister of SuperReg), find the corresponding subregister 641 // of NewSuperReg and make sure it is free to be renamed. 642 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 643 unsigned Reg = Regs[i]; 644 unsigned NewReg = 0; 645 if (Reg == SuperReg) { 646 NewReg = NewSuperReg; 647 } else { 648 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); 649 if (NewSubRegIdx != 0) 650 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); 651 } 652 653 DEBUG(dbgs() << " " << TRI->getName(NewReg)); 654 655 // Check if Reg can be renamed to NewReg. 656 if (!RenameRegisterMap[Reg].test(NewReg)) { 657 DEBUG(dbgs() << "(no rename)"); 658 goto next_super_reg; 659 } 660 661 // If NewReg is dead and NewReg's most recent def is not before 662 // Regs's kill, it's safe to replace Reg with NewReg. We 663 // must also check all aliases of NewReg, because we can't define a 664 // register when any sub or super is already live. 665 if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) { 666 DEBUG(dbgs() << "(live)"); 667 goto next_super_reg; 668 } else { 669 bool found = false; 670 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { 671 unsigned AliasReg = *AI; 672 if (State->IsLive(AliasReg) || 673 (KillIndices[Reg] > DefIndices[AliasReg])) { 674 DEBUG(dbgs() << "(alias " << TRI->getName(AliasReg) << " live)"); 675 found = true; 676 break; 677 } 678 } 679 if (found) 680 goto next_super_reg; 681 } 682 683 // We cannot rename 'Reg' to 'NewReg' if one of the uses of 'Reg' also 684 // defines 'NewReg' via an early-clobber operand. 685 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { 686 MachineInstr *UseMI = Q.second.Operand->getParent(); 687 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, false, true, TRI); 688 if (Idx == -1) 689 continue; 690 691 if (UseMI->getOperand(Idx).isEarlyClobber()) { 692 DEBUG(dbgs() << "(ec)"); 693 goto next_super_reg; 694 } 695 } 696 697 // Also, we cannot rename 'Reg' to 'NewReg' if the instruction defining 698 // 'Reg' is an early-clobber define and that instruction also uses 699 // 'NewReg'. 700 for (const auto &Q : make_range(RegRefs.equal_range(Reg))) { 701 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber()) 702 continue; 703 704 MachineInstr *DefMI = Q.second.Operand->getParent(); 705 if (DefMI->readsRegister(NewReg, TRI)) { 706 DEBUG(dbgs() << "(ec)"); 707 goto next_super_reg; 708 } 709 } 710 711 // Record that 'Reg' can be renamed to 'NewReg'. 712 RenameMap.insert(std::pair<unsigned, unsigned>(Reg, NewReg)); 713 } 714 715 // If we fall-out here, then every register in the group can be 716 // renamed, as recorded in RenameMap. 717 RenameOrder.erase(SuperRC); 718 RenameOrder.insert(RenameOrderType::value_type(SuperRC, R)); 719 DEBUG(dbgs() << "]\n"); 720 return true; 721 722 next_super_reg: 723 DEBUG(dbgs() << ']'); 724 } while (R != EndR); 725 726 DEBUG(dbgs() << '\n'); 727 728 // No registers are free and available! 729 return false; 730 } 731 732 /// BreakAntiDependencies - Identifiy anti-dependencies within the 733 /// ScheduleDAG and break them by renaming registers. 734 /// 735 unsigned AggressiveAntiDepBreaker::BreakAntiDependencies( 736 const std::vector<SUnit>& SUnits, 737 MachineBasicBlock::iterator Begin, 738 MachineBasicBlock::iterator End, 739 unsigned InsertPosIndex, 740 DbgValueVector &DbgValues) { 741 742 std::vector<unsigned> &KillIndices = State->GetKillIndices(); 743 std::vector<unsigned> &DefIndices = State->GetDefIndices(); 744 std::multimap<unsigned, AggressiveAntiDepState::RegisterReference>& 745 RegRefs = State->GetRegRefs(); 746 747 // The code below assumes that there is at least one instruction, 748 // so just duck out immediately if the block is empty. 749 if (SUnits.empty()) return 0; 750 751 // For each regclass the next register to use for renaming. 752 RenameOrderType RenameOrder; 753 754 // ...need a map from MI to SUnit. 755 std::map<MachineInstr *, const SUnit *> MISUnitMap; 756 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 757 const SUnit *SU = &SUnits[i]; 758 MISUnitMap.insert(std::pair<MachineInstr *, const SUnit *>(SU->getInstr(), 759 SU)); 760 } 761 762 // Track progress along the critical path through the SUnit graph as 763 // we walk the instructions. This is needed for regclasses that only 764 // break critical-path anti-dependencies. 765 const SUnit *CriticalPathSU = nullptr; 766 MachineInstr *CriticalPathMI = nullptr; 767 if (CriticalPathSet.any()) { 768 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 769 const SUnit *SU = &SUnits[i]; 770 if (!CriticalPathSU || 771 ((SU->getDepth() + SU->Latency) > 772 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { 773 CriticalPathSU = SU; 774 } 775 } 776 777 CriticalPathMI = CriticalPathSU->getInstr(); 778 } 779 780 #ifndef NDEBUG 781 DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); 782 DEBUG(dbgs() << "Available regs:"); 783 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 784 if (!State->IsLive(Reg)) 785 DEBUG(dbgs() << " " << TRI->getName(Reg)); 786 } 787 DEBUG(dbgs() << '\n'); 788 #endif 789 790 BitVector RegAliases(TRI->getNumRegs()); 791 792 // Attempt to break anti-dependence edges. Walk the instructions 793 // from the bottom up, tracking information about liveness as we go 794 // to help determine which registers are available. 795 unsigned Broken = 0; 796 unsigned Count = InsertPosIndex - 1; 797 for (MachineBasicBlock::iterator I = End, E = Begin; 798 I != E; --Count) { 799 MachineInstr &MI = *--I; 800 801 if (MI.isDebugValue()) 802 continue; 803 804 DEBUG(dbgs() << "Anti: "); 805 DEBUG(MI.dump()); 806 807 std::set<unsigned> PassthruRegs; 808 GetPassthruRegs(MI, PassthruRegs); 809 810 // Process the defs in MI... 811 PrescanInstruction(MI, Count, PassthruRegs); 812 813 // The dependence edges that represent anti- and output- 814 // dependencies that are candidates for breaking. 815 std::vector<const SDep *> Edges; 816 const SUnit *PathSU = MISUnitMap[&MI]; 817 AntiDepEdges(PathSU, Edges); 818 819 // If MI is not on the critical path, then we don't rename 820 // registers in the CriticalPathSet. 821 BitVector *ExcludeRegs = nullptr; 822 if (&MI == CriticalPathMI) { 823 CriticalPathSU = CriticalPathStep(CriticalPathSU); 824 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; 825 } else if (CriticalPathSet.any()) { 826 ExcludeRegs = &CriticalPathSet; 827 } 828 829 // Ignore KILL instructions (they form a group in ScanInstruction 830 // but don't cause any anti-dependence breaking themselves) 831 if (!MI.isKill()) { 832 // Attempt to break each anti-dependency... 833 for (unsigned i = 0, e = Edges.size(); i != e; ++i) { 834 const SDep *Edge = Edges[i]; 835 SUnit *NextSU = Edge->getSUnit(); 836 837 if ((Edge->getKind() != SDep::Anti) && 838 (Edge->getKind() != SDep::Output)) continue; 839 840 unsigned AntiDepReg = Edge->getReg(); 841 DEBUG(dbgs() << "\tAntidep reg: " << TRI->getName(AntiDepReg)); 842 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 843 844 if (!MRI.isAllocatable(AntiDepReg)) { 845 // Don't break anti-dependencies on non-allocatable registers. 846 DEBUG(dbgs() << " (non-allocatable)\n"); 847 continue; 848 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) { 849 // Don't break anti-dependencies for critical path registers 850 // if not on the critical path 851 DEBUG(dbgs() << " (not critical-path)\n"); 852 continue; 853 } else if (PassthruRegs.count(AntiDepReg) != 0) { 854 // If the anti-dep register liveness "passes-thru", then 855 // don't try to change it. It will be changed along with 856 // the use if required to break an earlier antidep. 857 DEBUG(dbgs() << " (passthru)\n"); 858 continue; 859 } else { 860 // No anti-dep breaking for implicit deps 861 MachineOperand *AntiDepOp = MI.findRegisterDefOperand(AntiDepReg); 862 assert(AntiDepOp && "Can't find index for defined register operand"); 863 if (!AntiDepOp || AntiDepOp->isImplicit()) { 864 DEBUG(dbgs() << " (implicit)\n"); 865 continue; 866 } 867 868 // If the SUnit has other dependencies on the SUnit that 869 // it anti-depends on, don't bother breaking the 870 // anti-dependency since those edges would prevent such 871 // units from being scheduled past each other 872 // regardless. 873 // 874 // Also, if there are dependencies on other SUnits with the 875 // same register as the anti-dependency, don't attempt to 876 // break it. 877 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 878 PE = PathSU->Preds.end(); P != PE; ++P) { 879 if (P->getSUnit() == NextSU ? 880 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 881 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 882 AntiDepReg = 0; 883 break; 884 } 885 } 886 for (SUnit::const_pred_iterator P = PathSU->Preds.begin(), 887 PE = PathSU->Preds.end(); P != PE; ++P) { 888 if ((P->getSUnit() == NextSU) && (P->getKind() != SDep::Anti) && 889 (P->getKind() != SDep::Output)) { 890 DEBUG(dbgs() << " (real dependency)\n"); 891 AntiDepReg = 0; 892 break; 893 } else if ((P->getSUnit() != NextSU) && 894 (P->getKind() == SDep::Data) && 895 (P->getReg() == AntiDepReg)) { 896 DEBUG(dbgs() << " (other dependency)\n"); 897 AntiDepReg = 0; 898 break; 899 } 900 } 901 902 if (AntiDepReg == 0) continue; 903 904 // If the definition of the anti-dependency register does not start 905 // a new live range, bail out. This can happen if the anti-dep 906 // register is a sub-register of another register whose live range 907 // spans over PathSU. In such case, PathSU defines only a part of 908 // the larger register. 909 RegAliases.reset(); 910 for (MCRegAliasIterator AI(AntiDepReg, TRI, true); AI.isValid(); ++AI) 911 RegAliases.set(*AI); 912 for (SDep S : PathSU->Succs) { 913 SDep::Kind K = S.getKind(); 914 if (K != SDep::Data && K != SDep::Output && K != SDep::Anti) 915 continue; 916 unsigned R = S.getReg(); 917 if (!RegAliases[R]) 918 continue; 919 if (R == AntiDepReg || TRI->isSubRegister(AntiDepReg, R)) 920 continue; 921 AntiDepReg = 0; 922 break; 923 } 924 925 if (AntiDepReg == 0) continue; 926 } 927 928 assert(AntiDepReg != 0); 929 if (AntiDepReg == 0) continue; 930 931 // Determine AntiDepReg's register group. 932 const unsigned GroupIndex = State->GetGroup(AntiDepReg); 933 if (GroupIndex == 0) { 934 DEBUG(dbgs() << " (zero group)\n"); 935 continue; 936 } 937 938 DEBUG(dbgs() << '\n'); 939 940 // Look for a suitable register to use to break the anti-dependence. 941 std::map<unsigned, unsigned> RenameMap; 942 if (FindSuitableFreeRegisters(GroupIndex, RenameOrder, RenameMap)) { 943 DEBUG(dbgs() << "\tBreaking anti-dependence edge on " 944 << TRI->getName(AntiDepReg) << ":"); 945 946 // Handle each group register... 947 for (std::map<unsigned, unsigned>::iterator 948 S = RenameMap.begin(), E = RenameMap.end(); S != E; ++S) { 949 unsigned CurrReg = S->first; 950 unsigned NewReg = S->second; 951 952 DEBUG(dbgs() << " " << TRI->getName(CurrReg) << "->" << 953 TRI->getName(NewReg) << "(" << 954 RegRefs.count(CurrReg) << " refs)"); 955 956 // Update the references to the old register CurrReg to 957 // refer to the new register NewReg. 958 for (const auto &Q : make_range(RegRefs.equal_range(CurrReg))) { 959 Q.second.Operand->setReg(NewReg); 960 // If the SU for the instruction being updated has debug 961 // information related to the anti-dependency register, make 962 // sure to update that as well. 963 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()]; 964 if (!SU) continue; 965 for (DbgValueVector::iterator DVI = DbgValues.begin(), 966 DVE = DbgValues.end(); DVI != DVE; ++DVI) 967 if (DVI->second == Q.second.Operand->getParent()) 968 UpdateDbgValue(*DVI->first, AntiDepReg, NewReg); 969 } 970 971 // We just went back in time and modified history; the 972 // liveness information for CurrReg is now inconsistent. Set 973 // the state as if it were dead. 974 State->UnionGroups(NewReg, 0); 975 RegRefs.erase(NewReg); 976 DefIndices[NewReg] = DefIndices[CurrReg]; 977 KillIndices[NewReg] = KillIndices[CurrReg]; 978 979 State->UnionGroups(CurrReg, 0); 980 RegRefs.erase(CurrReg); 981 DefIndices[CurrReg] = KillIndices[CurrReg]; 982 KillIndices[CurrReg] = ~0u; 983 assert(((KillIndices[CurrReg] == ~0u) != 984 (DefIndices[CurrReg] == ~0u)) && 985 "Kill and Def maps aren't consistent for AntiDepReg!"); 986 } 987 988 ++Broken; 989 DEBUG(dbgs() << '\n'); 990 } 991 } 992 } 993 994 ScanInstruction(MI, Count); 995 } 996 997 return Broken; 998 } 999
