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