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