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