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