1 //===----- CriticalAntiDepBreaker.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 CriticalAntiDepBreaker class, which 11 // implements register anti-dependence breaking along a blocks 12 // critical path during post-RA scheduler. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #define DEBUG_TYPE "post-RA-sched" 17 #include "CriticalAntiDepBreaker.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/MachineFrameInfo.h" 20 #include "llvm/Target/TargetMachine.h" 21 #include "llvm/Target/TargetInstrInfo.h" 22 #include "llvm/Target/TargetRegisterInfo.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 27 using namespace llvm; 28 29 CriticalAntiDepBreaker:: 30 CriticalAntiDepBreaker(MachineFunction& MFi, const RegisterClassInfo &RCI) : 31 AntiDepBreaker(), MF(MFi), 32 MRI(MF.getRegInfo()), 33 TII(MF.getTarget().getInstrInfo()), 34 TRI(MF.getTarget().getRegisterInfo()), 35 RegClassInfo(RCI), 36 Classes(TRI->getNumRegs(), static_cast<const TargetRegisterClass *>(0)), 37 KillIndices(TRI->getNumRegs(), 0), 38 DefIndices(TRI->getNumRegs(), 0), 39 KeepRegs(TRI->getNumRegs(), false) {} 40 41 CriticalAntiDepBreaker::~CriticalAntiDepBreaker() { 42 } 43 44 void CriticalAntiDepBreaker::StartBlock(MachineBasicBlock *BB) { 45 const unsigned BBSize = BB->size(); 46 for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) { 47 // Clear out the register class data. 48 Classes[i] = static_cast<const TargetRegisterClass *>(0); 49 50 // Initialize the indices to indicate that no registers are live. 51 KillIndices[i] = ~0u; 52 DefIndices[i] = BBSize; 53 } 54 55 // Clear "do not change" set. 56 KeepRegs.reset(); 57 58 bool IsReturnBlock = (BBSize != 0 && BB->back().isReturn()); 59 60 // Determine the live-out physregs for this block. 61 if (IsReturnBlock) { 62 // In a return block, examine the function live-out regs. 63 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 64 E = MRI.liveout_end(); I != E; ++I) { 65 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { 66 unsigned Reg = *AI; 67 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 68 KillIndices[Reg] = BBSize; 69 DefIndices[Reg] = ~0u; 70 } 71 } 72 } 73 74 // In a non-return block, examine the live-in regs of all successors. 75 // Note a return block can have successors if the return instruction is 76 // predicated. 77 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 78 SE = BB->succ_end(); SI != SE; ++SI) 79 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 80 E = (*SI)->livein_end(); I != E; ++I) { 81 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { 82 unsigned Reg = *AI; 83 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 84 KillIndices[Reg] = BBSize; 85 DefIndices[Reg] = ~0u; 86 } 87 } 88 89 // Mark live-out callee-saved registers. In a return block this is 90 // all callee-saved registers. In non-return this is any 91 // callee-saved register that is not saved in the prolog. 92 const MachineFrameInfo *MFI = MF.getFrameInfo(); 93 BitVector Pristine = MFI->getPristineRegs(BB); 94 for (const uint16_t *I = TRI->getCalleeSavedRegs(&MF); *I; ++I) { 95 if (!IsReturnBlock && !Pristine.test(*I)) continue; 96 for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI) { 97 unsigned Reg = *AI; 98 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 99 KillIndices[Reg] = BBSize; 100 DefIndices[Reg] = ~0u; 101 } 102 } 103 } 104 105 void CriticalAntiDepBreaker::FinishBlock() { 106 RegRefs.clear(); 107 KeepRegs.reset(); 108 } 109 110 void CriticalAntiDepBreaker::Observe(MachineInstr *MI, unsigned Count, 111 unsigned InsertPosIndex) { 112 if (MI->isDebugValue()) 113 return; 114 assert(Count < InsertPosIndex && "Instruction index out of expected range!"); 115 116 for (unsigned Reg = 0; Reg != TRI->getNumRegs(); ++Reg) { 117 if (KillIndices[Reg] != ~0u) { 118 // If Reg is currently live, then mark that it can't be renamed as 119 // we don't know the extent of its live-range anymore (now that it 120 // has been scheduled). 121 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 122 KillIndices[Reg] = Count; 123 } else if (DefIndices[Reg] < InsertPosIndex && DefIndices[Reg] >= Count) { 124 // Any register which was defined within the previous scheduling region 125 // may have been rescheduled and its lifetime may overlap with registers 126 // in ways not reflected in our current liveness state. For each such 127 // register, adjust the liveness state to be conservatively correct. 128 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 129 130 // Move the def index to the end of the previous region, to reflect 131 // that the def could theoretically have been scheduled at the end. 132 DefIndices[Reg] = InsertPosIndex; 133 } 134 } 135 136 PrescanInstruction(MI); 137 ScanInstruction(MI, Count); 138 } 139 140 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up 141 /// critical path. 142 static const SDep *CriticalPathStep(const SUnit *SU) { 143 const SDep *Next = 0; 144 unsigned NextDepth = 0; 145 // Find the predecessor edge with the greatest depth. 146 for (SUnit::const_pred_iterator P = SU->Preds.begin(), PE = SU->Preds.end(); 147 P != PE; ++P) { 148 const SUnit *PredSU = P->getSUnit(); 149 unsigned PredLatency = P->getLatency(); 150 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; 151 // In the case of a latency tie, prefer an anti-dependency edge over 152 // other types of edges. 153 if (NextDepth < PredTotalLatency || 154 (NextDepth == PredTotalLatency && P->getKind() == SDep::Anti)) { 155 NextDepth = PredTotalLatency; 156 Next = &*P; 157 } 158 } 159 return Next; 160 } 161 162 void CriticalAntiDepBreaker::PrescanInstruction(MachineInstr *MI) { 163 // It's not safe to change register allocation for source operands of 164 // that have special allocation requirements. Also assume all registers 165 // used in a call must not be changed (ABI). 166 // FIXME: The issue with predicated instruction is more complex. We are being 167 // conservative here because the kill markers cannot be trusted after 168 // if-conversion: 169 // %R6<def> = LDR %SP, %reg0, 92, pred:14, pred:%reg0; mem:LD4[FixedStack14] 170 // ... 171 // STR %R0, %R6<kill>, %reg0, 0, pred:0, pred:%CPSR; mem:ST4[%395] 172 // %R6<def> = LDR %SP, %reg0, 100, pred:0, pred:%CPSR; mem:LD4[FixedStack12] 173 // STR %R0, %R6<kill>, %reg0, 0, pred:14, pred:%reg0; mem:ST4[%396](align=8) 174 // 175 // The first R6 kill is not really a kill since it's killed by a predicated 176 // instruction which may not be executed. The second R6 def may or may not 177 // re-define R6 so it's not safe to change it since the last R6 use cannot be 178 // changed. 179 bool Special = MI->isCall() || 180 MI->hasExtraSrcRegAllocReq() || 181 TII->isPredicated(MI); 182 183 // Scan the register operands for this instruction and update 184 // Classes and RegRefs. 185 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 186 MachineOperand &MO = MI->getOperand(i); 187 if (!MO.isReg()) continue; 188 unsigned Reg = MO.getReg(); 189 if (Reg == 0) continue; 190 const TargetRegisterClass *NewRC = 0; 191 192 if (i < MI->getDesc().getNumOperands()) 193 NewRC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 194 195 // For now, only allow the register to be changed if its register 196 // class is consistent across all uses. 197 if (!Classes[Reg] && NewRC) 198 Classes[Reg] = NewRC; 199 else if (!NewRC || Classes[Reg] != NewRC) 200 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 201 202 // Now check for aliases. 203 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { 204 // If an alias of the reg is used during the live range, give up. 205 // Note that this allows us to skip checking if AntiDepReg 206 // overlaps with any of the aliases, among other things. 207 unsigned AliasReg = *AI; 208 if (Classes[AliasReg]) { 209 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); 210 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 211 } 212 } 213 214 // If we're still willing to consider this register, note the reference. 215 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) 216 RegRefs.insert(std::make_pair(Reg, &MO)); 217 218 if (MO.isUse() && Special) { 219 if (!KeepRegs.test(Reg)) { 220 KeepRegs.set(Reg); 221 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 222 KeepRegs.set(*SubRegs); 223 } 224 } 225 } 226 } 227 228 void CriticalAntiDepBreaker::ScanInstruction(MachineInstr *MI, 229 unsigned Count) { 230 // Update liveness. 231 // Proceeding upwards, registers that are defed but not used in this 232 // instruction are now dead. 233 234 if (!TII->isPredicated(MI)) { 235 // Predicated defs are modeled as read + write, i.e. similar to two 236 // address updates. 237 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 238 MachineOperand &MO = MI->getOperand(i); 239 240 if (MO.isRegMask()) 241 for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) 242 if (MO.clobbersPhysReg(i)) { 243 DefIndices[i] = Count; 244 KillIndices[i] = ~0u; 245 KeepRegs.reset(i); 246 Classes[i] = 0; 247 RegRefs.erase(i); 248 } 249 250 if (!MO.isReg()) continue; 251 unsigned Reg = MO.getReg(); 252 if (Reg == 0) continue; 253 if (!MO.isDef()) continue; 254 // Ignore two-addr defs. 255 if (MI->isRegTiedToUseOperand(i)) continue; 256 257 DefIndices[Reg] = Count; 258 KillIndices[Reg] = ~0u; 259 assert(((KillIndices[Reg] == ~0u) != 260 (DefIndices[Reg] == ~0u)) && 261 "Kill and Def maps aren't consistent for Reg!"); 262 KeepRegs.reset(Reg); 263 Classes[Reg] = 0; 264 RegRefs.erase(Reg); 265 // Repeat, for all subregs. 266 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 267 unsigned SubregReg = *SubRegs; 268 DefIndices[SubregReg] = Count; 269 KillIndices[SubregReg] = ~0u; 270 KeepRegs.reset(SubregReg); 271 Classes[SubregReg] = 0; 272 RegRefs.erase(SubregReg); 273 } 274 // Conservatively mark super-registers as unusable. 275 for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) 276 Classes[*SR] = reinterpret_cast<TargetRegisterClass *>(-1); 277 } 278 } 279 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 280 MachineOperand &MO = MI->getOperand(i); 281 if (!MO.isReg()) continue; 282 unsigned Reg = MO.getReg(); 283 if (Reg == 0) continue; 284 if (!MO.isUse()) continue; 285 286 const TargetRegisterClass *NewRC = 0; 287 if (i < MI->getDesc().getNumOperands()) 288 NewRC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 289 290 // For now, only allow the register to be changed if its register 291 // class is consistent across all uses. 292 if (!Classes[Reg] && NewRC) 293 Classes[Reg] = NewRC; 294 else if (!NewRC || Classes[Reg] != NewRC) 295 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 296 297 RegRefs.insert(std::make_pair(Reg, &MO)); 298 299 // It wasn't previously live but now it is, this is a kill. 300 if (KillIndices[Reg] == ~0u) { 301 KillIndices[Reg] = Count; 302 DefIndices[Reg] = ~0u; 303 assert(((KillIndices[Reg] == ~0u) != 304 (DefIndices[Reg] == ~0u)) && 305 "Kill and Def maps aren't consistent for Reg!"); 306 } 307 // Repeat, for all aliases. 308 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { 309 unsigned AliasReg = *AI; 310 if (KillIndices[AliasReg] == ~0u) { 311 KillIndices[AliasReg] = Count; 312 DefIndices[AliasReg] = ~0u; 313 } 314 } 315 } 316 } 317 318 // Check all machine operands that reference the antidependent register and must 319 // be replaced by NewReg. Return true if any of their parent instructions may 320 // clobber the new register. 321 // 322 // Note: AntiDepReg may be referenced by a two-address instruction such that 323 // it's use operand is tied to a def operand. We guard against the case in which 324 // the two-address instruction also defines NewReg, as may happen with 325 // pre/postincrement loads. In this case, both the use and def operands are in 326 // RegRefs because the def is inserted by PrescanInstruction and not erased 327 // during ScanInstruction. So checking for an instructions with definitions of 328 // both NewReg and AntiDepReg covers it. 329 bool 330 CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin, 331 RegRefIter RegRefEnd, 332 unsigned NewReg) 333 { 334 for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) { 335 MachineOperand *RefOper = I->second; 336 337 // Don't allow the instruction defining AntiDepReg to earlyclobber its 338 // operands, in case they may be assigned to NewReg. In this case antidep 339 // breaking must fail, but it's too rare to bother optimizing. 340 if (RefOper->isDef() && RefOper->isEarlyClobber()) 341 return true; 342 343 // Handle cases in which this instructions defines NewReg. 344 MachineInstr *MI = RefOper->getParent(); 345 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 346 const MachineOperand &CheckOper = MI->getOperand(i); 347 348 if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg)) 349 return true; 350 351 if (!CheckOper.isReg() || !CheckOper.isDef() || 352 CheckOper.getReg() != NewReg) 353 continue; 354 355 // Don't allow the instruction to define NewReg and AntiDepReg. 356 // When AntiDepReg is renamed it will be an illegal op. 357 if (RefOper->isDef()) 358 return true; 359 360 // Don't allow an instruction using AntiDepReg to be earlyclobbered by 361 // NewReg 362 if (CheckOper.isEarlyClobber()) 363 return true; 364 365 // Don't allow inline asm to define NewReg at all. Who know what it's 366 // doing with it. 367 if (MI->isInlineAsm()) 368 return true; 369 } 370 } 371 return false; 372 } 373 374 unsigned 375 CriticalAntiDepBreaker::findSuitableFreeRegister(RegRefIter RegRefBegin, 376 RegRefIter RegRefEnd, 377 unsigned AntiDepReg, 378 unsigned LastNewReg, 379 const TargetRegisterClass *RC) 380 { 381 ArrayRef<unsigned> Order = RegClassInfo.getOrder(RC); 382 for (unsigned i = 0; i != Order.size(); ++i) { 383 unsigned NewReg = Order[i]; 384 // Don't replace a register with itself. 385 if (NewReg == AntiDepReg) continue; 386 // Don't replace a register with one that was recently used to repair 387 // an anti-dependence with this AntiDepReg, because that would 388 // re-introduce that anti-dependence. 389 if (NewReg == LastNewReg) continue; 390 // If any instructions that define AntiDepReg also define the NewReg, it's 391 // not suitable. For example, Instruction with multiple definitions can 392 // result in this condition. 393 if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue; 394 // If NewReg is dead and NewReg's most recent def is not before 395 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 396 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) 397 && "Kill and Def maps aren't consistent for AntiDepReg!"); 398 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) 399 && "Kill and Def maps aren't consistent for NewReg!"); 400 if (KillIndices[NewReg] != ~0u || 401 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || 402 KillIndices[AntiDepReg] > DefIndices[NewReg]) 403 continue; 404 return NewReg; 405 } 406 407 // No registers are free and available! 408 return 0; 409 } 410 411 unsigned CriticalAntiDepBreaker:: 412 BreakAntiDependencies(const std::vector<SUnit>& SUnits, 413 MachineBasicBlock::iterator Begin, 414 MachineBasicBlock::iterator End, 415 unsigned InsertPosIndex, 416 DbgValueVector &DbgValues) { 417 // The code below assumes that there is at least one instruction, 418 // so just duck out immediately if the block is empty. 419 if (SUnits.empty()) return 0; 420 421 // Keep a map of the MachineInstr*'s back to the SUnit representing them. 422 // This is used for updating debug information. 423 // 424 // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap 425 DenseMap<MachineInstr*,const SUnit*> MISUnitMap; 426 427 // Find the node at the bottom of the critical path. 428 const SUnit *Max = 0; 429 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 430 const SUnit *SU = &SUnits[i]; 431 MISUnitMap[SU->getInstr()] = SU; 432 if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) 433 Max = SU; 434 } 435 436 #ifndef NDEBUG 437 { 438 DEBUG(dbgs() << "Critical path has total latency " 439 << (Max->getDepth() + Max->Latency) << "\n"); 440 DEBUG(dbgs() << "Available regs:"); 441 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 442 if (KillIndices[Reg] == ~0u) 443 DEBUG(dbgs() << " " << TRI->getName(Reg)); 444 } 445 DEBUG(dbgs() << '\n'); 446 } 447 #endif 448 449 // Track progress along the critical path through the SUnit graph as we walk 450 // the instructions. 451 const SUnit *CriticalPathSU = Max; 452 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); 453 454 // Consider this pattern: 455 // A = ... 456 // ... = A 457 // A = ... 458 // ... = A 459 // A = ... 460 // ... = A 461 // A = ... 462 // ... = A 463 // There are three anti-dependencies here, and without special care, 464 // we'd break all of them using the same register: 465 // A = ... 466 // ... = A 467 // B = ... 468 // ... = B 469 // B = ... 470 // ... = B 471 // B = ... 472 // ... = B 473 // because at each anti-dependence, B is the first register that 474 // isn't A which is free. This re-introduces anti-dependencies 475 // at all but one of the original anti-dependencies that we were 476 // trying to break. To avoid this, keep track of the most recent 477 // register that each register was replaced with, avoid 478 // using it to repair an anti-dependence on the same register. 479 // This lets us produce this: 480 // A = ... 481 // ... = A 482 // B = ... 483 // ... = B 484 // C = ... 485 // ... = C 486 // B = ... 487 // ... = B 488 // This still has an anti-dependence on B, but at least it isn't on the 489 // original critical path. 490 // 491 // TODO: If we tracked more than one register here, we could potentially 492 // fix that remaining critical edge too. This is a little more involved, 493 // because unlike the most recent register, less recent registers should 494 // still be considered, though only if no other registers are available. 495 std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); 496 497 // Attempt to break anti-dependence edges on the critical path. Walk the 498 // instructions from the bottom up, tracking information about liveness 499 // as we go to help determine which registers are available. 500 unsigned Broken = 0; 501 unsigned Count = InsertPosIndex - 1; 502 for (MachineBasicBlock::iterator I = End, E = Begin; 503 I != E; --Count) { 504 MachineInstr *MI = --I; 505 if (MI->isDebugValue()) 506 continue; 507 508 // Check if this instruction has a dependence on the critical path that 509 // is an anti-dependence that we may be able to break. If it is, set 510 // AntiDepReg to the non-zero register associated with the anti-dependence. 511 // 512 // We limit our attention to the critical path as a heuristic to avoid 513 // breaking anti-dependence edges that aren't going to significantly 514 // impact the overall schedule. There are a limited number of registers 515 // and we want to save them for the important edges. 516 // 517 // TODO: Instructions with multiple defs could have multiple 518 // anti-dependencies. The current code here only knows how to break one 519 // edge per instruction. Note that we'd have to be able to break all of 520 // the anti-dependencies in an instruction in order to be effective. 521 unsigned AntiDepReg = 0; 522 if (MI == CriticalPathMI) { 523 if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) { 524 const SUnit *NextSU = Edge->getSUnit(); 525 526 // Only consider anti-dependence edges. 527 if (Edge->getKind() == SDep::Anti) { 528 AntiDepReg = Edge->getReg(); 529 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 530 if (!RegClassInfo.isAllocatable(AntiDepReg)) 531 // Don't break anti-dependencies on non-allocatable registers. 532 AntiDepReg = 0; 533 else if (KeepRegs.test(AntiDepReg)) 534 // Don't break anti-dependencies if an use down below requires 535 // this exact register. 536 AntiDepReg = 0; 537 else { 538 // If the SUnit has other dependencies on the SUnit that it 539 // anti-depends on, don't bother breaking the anti-dependency 540 // since those edges would prevent such units from being 541 // scheduled past each other regardless. 542 // 543 // Also, if there are dependencies on other SUnits with the 544 // same register as the anti-dependency, don't attempt to 545 // break it. 546 for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(), 547 PE = CriticalPathSU->Preds.end(); P != PE; ++P) 548 if (P->getSUnit() == NextSU ? 549 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 550 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 551 AntiDepReg = 0; 552 break; 553 } 554 } 555 } 556 CriticalPathSU = NextSU; 557 CriticalPathMI = CriticalPathSU->getInstr(); 558 } else { 559 // We've reached the end of the critical path. 560 CriticalPathSU = 0; 561 CriticalPathMI = 0; 562 } 563 } 564 565 PrescanInstruction(MI); 566 567 // If MI's defs have a special allocation requirement, don't allow 568 // any def registers to be changed. Also assume all registers 569 // defined in a call must not be changed (ABI). 570 if (MI->isCall() || MI->hasExtraDefRegAllocReq() || 571 TII->isPredicated(MI)) 572 // If this instruction's defs have special allocation requirement, don't 573 // break this anti-dependency. 574 AntiDepReg = 0; 575 else if (AntiDepReg) { 576 // If this instruction has a use of AntiDepReg, breaking it 577 // is invalid. 578 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 579 MachineOperand &MO = MI->getOperand(i); 580 if (!MO.isReg()) continue; 581 unsigned Reg = MO.getReg(); 582 if (Reg == 0) continue; 583 if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { 584 AntiDepReg = 0; 585 break; 586 } 587 } 588 } 589 590 // Determine AntiDepReg's register class, if it is live and is 591 // consistently used within a single class. 592 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 593 assert((AntiDepReg == 0 || RC != NULL) && 594 "Register should be live if it's causing an anti-dependence!"); 595 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 596 AntiDepReg = 0; 597 598 // Look for a suitable register to use to break the anti-depenence. 599 // 600 // TODO: Instead of picking the first free register, consider which might 601 // be the best. 602 if (AntiDepReg != 0) { 603 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 604 std::multimap<unsigned, MachineOperand *>::iterator> 605 Range = RegRefs.equal_range(AntiDepReg); 606 if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second, 607 AntiDepReg, 608 LastNewReg[AntiDepReg], 609 RC)) { 610 DEBUG(dbgs() << "Breaking anti-dependence edge on " 611 << TRI->getName(AntiDepReg) 612 << " with " << RegRefs.count(AntiDepReg) << " references" 613 << " using " << TRI->getName(NewReg) << "!\n"); 614 615 // Update the references to the old register to refer to the new 616 // register. 617 for (std::multimap<unsigned, MachineOperand *>::iterator 618 Q = Range.first, QE = Range.second; Q != QE; ++Q) { 619 Q->second->setReg(NewReg); 620 // If the SU for the instruction being updated has debug information 621 // related to the anti-dependency register, make sure to update that 622 // as well. 623 const SUnit *SU = MISUnitMap[Q->second->getParent()]; 624 if (!SU) continue; 625 for (DbgValueVector::iterator DVI = DbgValues.begin(), 626 DVE = DbgValues.end(); DVI != DVE; ++DVI) 627 if (DVI->second == Q->second->getParent()) 628 UpdateDbgValue(DVI->first, AntiDepReg, NewReg); 629 } 630 631 // We just went back in time and modified history; the 632 // liveness information for the anti-dependence reg is now 633 // inconsistent. Set the state as if it were dead. 634 Classes[NewReg] = Classes[AntiDepReg]; 635 DefIndices[NewReg] = DefIndices[AntiDepReg]; 636 KillIndices[NewReg] = KillIndices[AntiDepReg]; 637 assert(((KillIndices[NewReg] == ~0u) != 638 (DefIndices[NewReg] == ~0u)) && 639 "Kill and Def maps aren't consistent for NewReg!"); 640 641 Classes[AntiDepReg] = 0; 642 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 643 KillIndices[AntiDepReg] = ~0u; 644 assert(((KillIndices[AntiDepReg] == ~0u) != 645 (DefIndices[AntiDepReg] == ~0u)) && 646 "Kill and Def maps aren't consistent for AntiDepReg!"); 647 648 RegRefs.erase(AntiDepReg); 649 LastNewReg[AntiDepReg] = NewReg; 650 ++Broken; 651 } 652 } 653 654 ScanInstruction(MI, Count); 655 } 656 657 return Broken; 658 } 659