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