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