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