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