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