CriticalAntiDepBreaker.cpp revision f152fe8d487c46873bbdd4abab43200f783e978b
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 27using namespace llvm; 28 29CriticalAntiDepBreaker:: 30CriticalAntiDepBreaker(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 41CriticalAntiDepBreaker::~CriticalAntiDepBreaker() { 42} 43 44void 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 105void CriticalAntiDepBreaker::FinishBlock() { 106 RegRefs.clear(); 107 KeepRegs.reset(); 108} 109 110void 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. 142static 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 162void 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 (const uint16_t *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 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 = *Alias; 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 (const uint16_t *Subreg = TRI->getSubRegisters(Reg); 222 *Subreg; ++Subreg) 223 KeepRegs.set(*Subreg); 224 } 225 } 226 } 227} 228 229void CriticalAntiDepBreaker::ScanInstruction(MachineInstr *MI, 230 unsigned Count) { 231 // Update liveness. 232 // Proceding upwards, registers that are defed but not used in this 233 // instruction are now dead. 234 235 if (!TII->isPredicated(MI)) { 236 // Predicated defs are modeled as read + write, i.e. similar to two 237 // address updates. 238 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 239 MachineOperand &MO = MI->getOperand(i); 240 241 if (MO.isRegMask()) 242 for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) 243 if (MO.clobbersPhysReg(i)) { 244 DefIndices[i] = Count; 245 KillIndices[i] = ~0u; 246 KeepRegs.reset(i); 247 Classes[i] = 0; 248 RegRefs.erase(i); 249 } 250 251 if (!MO.isReg()) continue; 252 unsigned Reg = MO.getReg(); 253 if (Reg == 0) continue; 254 if (!MO.isDef()) continue; 255 // Ignore two-addr defs. 256 if (MI->isRegTiedToUseOperand(i)) continue; 257 258 DefIndices[Reg] = Count; 259 KillIndices[Reg] = ~0u; 260 assert(((KillIndices[Reg] == ~0u) != 261 (DefIndices[Reg] == ~0u)) && 262 "Kill and Def maps aren't consistent for Reg!"); 263 KeepRegs.reset(Reg); 264 Classes[Reg] = 0; 265 RegRefs.erase(Reg); 266 // Repeat, for all subregs. 267 for (const uint16_t *Subreg = TRI->getSubRegisters(Reg); 268 *Subreg; ++Subreg) { 269 unsigned SubregReg = *Subreg; 270 DefIndices[SubregReg] = Count; 271 KillIndices[SubregReg] = ~0u; 272 KeepRegs.reset(SubregReg); 273 Classes[SubregReg] = 0; 274 RegRefs.erase(SubregReg); 275 } 276 // Conservatively mark super-registers as unusable. 277 for (const uint16_t *Super = TRI->getSuperRegisters(Reg); 278 *Super; ++Super) { 279 unsigned SuperReg = *Super; 280 Classes[SuperReg] = reinterpret_cast<TargetRegisterClass *>(-1); 281 } 282 } 283 } 284 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 285 MachineOperand &MO = MI->getOperand(i); 286 if (!MO.isReg()) continue; 287 unsigned Reg = MO.getReg(); 288 if (Reg == 0) continue; 289 if (!MO.isUse()) continue; 290 291 const TargetRegisterClass *NewRC = 0; 292 if (i < MI->getDesc().getNumOperands()) 293 NewRC = TII->getRegClass(MI->getDesc(), i, TRI, MF); 294 295 // For now, only allow the register to be changed if its register 296 // class is consistent across all uses. 297 if (!Classes[Reg] && NewRC) 298 Classes[Reg] = NewRC; 299 else if (!NewRC || Classes[Reg] != NewRC) 300 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); 301 302 RegRefs.insert(std::make_pair(Reg, &MO)); 303 304 // It wasn't previously live but now it is, this is a kill. 305 if (KillIndices[Reg] == ~0u) { 306 KillIndices[Reg] = Count; 307 DefIndices[Reg] = ~0u; 308 assert(((KillIndices[Reg] == ~0u) != 309 (DefIndices[Reg] == ~0u)) && 310 "Kill and Def maps aren't consistent for Reg!"); 311 } 312 // Repeat, for all aliases. 313 for (const uint16_t *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 314 unsigned AliasReg = *Alias; 315 if (KillIndices[AliasReg] == ~0u) { 316 KillIndices[AliasReg] = Count; 317 DefIndices[AliasReg] = ~0u; 318 } 319 } 320 } 321} 322 323// Check all machine operands that reference the antidependent register and must 324// be replaced by NewReg. Return true if any of their parent instructions may 325// clobber the new register. 326// 327// Note: AntiDepReg may be referenced by a two-address instruction such that 328// it's use operand is tied to a def operand. We guard against the case in which 329// the two-address instruction also defines NewReg, as may happen with 330// pre/postincrement loads. In this case, both the use and def operands are in 331// RegRefs because the def is inserted by PrescanInstruction and not erased 332// during ScanInstruction. So checking for an instructions with definitions of 333// both NewReg and AntiDepReg covers it. 334bool 335CriticalAntiDepBreaker::isNewRegClobberedByRefs(RegRefIter RegRefBegin, 336 RegRefIter RegRefEnd, 337 unsigned NewReg) 338{ 339 for (RegRefIter I = RegRefBegin; I != RegRefEnd; ++I ) { 340 MachineOperand *RefOper = I->second; 341 342 // Don't allow the instruction defining AntiDepReg to earlyclobber its 343 // operands, in case they may be assigned to NewReg. In this case antidep 344 // breaking must fail, but it's too rare to bother optimizing. 345 if (RefOper->isDef() && RefOper->isEarlyClobber()) 346 return true; 347 348 // Handle cases in which this instructions defines NewReg. 349 MachineInstr *MI = RefOper->getParent(); 350 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 351 const MachineOperand &CheckOper = MI->getOperand(i); 352 353 if (CheckOper.isRegMask() && CheckOper.clobbersPhysReg(NewReg)) 354 return true; 355 356 if (!CheckOper.isReg() || !CheckOper.isDef() || 357 CheckOper.getReg() != NewReg) 358 continue; 359 360 // Don't allow the instruction to define NewReg and AntiDepReg. 361 // When AntiDepReg is renamed it will be an illegal op. 362 if (RefOper->isDef()) 363 return true; 364 365 // Don't allow an instruction using AntiDepReg to be earlyclobbered by 366 // NewReg 367 if (CheckOper.isEarlyClobber()) 368 return true; 369 370 // Don't allow inline asm to define NewReg at all. Who know what it's 371 // doing with it. 372 if (MI->isInlineAsm()) 373 return true; 374 } 375 } 376 return false; 377} 378 379unsigned 380CriticalAntiDepBreaker::findSuitableFreeRegister(RegRefIter RegRefBegin, 381 RegRefIter RegRefEnd, 382 unsigned AntiDepReg, 383 unsigned LastNewReg, 384 const TargetRegisterClass *RC) 385{ 386 ArrayRef<unsigned> Order = RegClassInfo.getOrder(RC); 387 for (unsigned i = 0; i != Order.size(); ++i) { 388 unsigned NewReg = Order[i]; 389 // Don't replace a register with itself. 390 if (NewReg == AntiDepReg) continue; 391 // Don't replace a register with one that was recently used to repair 392 // an anti-dependence with this AntiDepReg, because that would 393 // re-introduce that anti-dependence. 394 if (NewReg == LastNewReg) continue; 395 // If any instructions that define AntiDepReg also define the NewReg, it's 396 // not suitable. For example, Instruction with multiple definitions can 397 // result in this condition. 398 if (isNewRegClobberedByRefs(RegRefBegin, RegRefEnd, NewReg)) continue; 399 // If NewReg is dead and NewReg's most recent def is not before 400 // AntiDepReg's kill, it's safe to replace AntiDepReg with NewReg. 401 assert(((KillIndices[AntiDepReg] == ~0u) != (DefIndices[AntiDepReg] == ~0u)) 402 && "Kill and Def maps aren't consistent for AntiDepReg!"); 403 assert(((KillIndices[NewReg] == ~0u) != (DefIndices[NewReg] == ~0u)) 404 && "Kill and Def maps aren't consistent for NewReg!"); 405 if (KillIndices[NewReg] != ~0u || 406 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || 407 KillIndices[AntiDepReg] > DefIndices[NewReg]) 408 continue; 409 return NewReg; 410 } 411 412 // No registers are free and available! 413 return 0; 414} 415 416unsigned CriticalAntiDepBreaker:: 417BreakAntiDependencies(const std::vector<SUnit>& SUnits, 418 MachineBasicBlock::iterator Begin, 419 MachineBasicBlock::iterator End, 420 unsigned InsertPosIndex, 421 DbgValueVector &DbgValues) { 422 // The code below assumes that there is at least one instruction, 423 // so just duck out immediately if the block is empty. 424 if (SUnits.empty()) return 0; 425 426 // Keep a map of the MachineInstr*'s back to the SUnit representing them. 427 // This is used for updating debug information. 428 // 429 // FIXME: Replace this with the existing map in ScheduleDAGInstrs::MISUnitMap 430 DenseMap<MachineInstr*,const SUnit*> MISUnitMap; 431 432 // Find the node at the bottom of the critical path. 433 const SUnit *Max = 0; 434 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 435 const SUnit *SU = &SUnits[i]; 436 MISUnitMap[SU->getInstr()] = SU; 437 if (!Max || SU->getDepth() + SU->Latency > Max->getDepth() + Max->Latency) 438 Max = SU; 439 } 440 441#ifndef NDEBUG 442 { 443 DEBUG(dbgs() << "Critical path has total latency " 444 << (Max->getDepth() + Max->Latency) << "\n"); 445 DEBUG(dbgs() << "Available regs:"); 446 for (unsigned Reg = 0; Reg < TRI->getNumRegs(); ++Reg) { 447 if (KillIndices[Reg] == ~0u) 448 DEBUG(dbgs() << " " << TRI->getName(Reg)); 449 } 450 DEBUG(dbgs() << '\n'); 451 } 452#endif 453 454 // Track progress along the critical path through the SUnit graph as we walk 455 // the instructions. 456 const SUnit *CriticalPathSU = Max; 457 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); 458 459 // Consider this pattern: 460 // A = ... 461 // ... = A 462 // A = ... 463 // ... = A 464 // A = ... 465 // ... = A 466 // A = ... 467 // ... = A 468 // There are three anti-dependencies here, and without special care, 469 // we'd break all of them using the same register: 470 // A = ... 471 // ... = A 472 // B = ... 473 // ... = B 474 // B = ... 475 // ... = B 476 // B = ... 477 // ... = B 478 // because at each anti-dependence, B is the first register that 479 // isn't A which is free. This re-introduces anti-dependencies 480 // at all but one of the original anti-dependencies that we were 481 // trying to break. To avoid this, keep track of the most recent 482 // register that each register was replaced with, avoid 483 // using it to repair an anti-dependence on the same register. 484 // This lets us produce this: 485 // A = ... 486 // ... = A 487 // B = ... 488 // ... = B 489 // C = ... 490 // ... = C 491 // B = ... 492 // ... = B 493 // This still has an anti-dependence on B, but at least it isn't on the 494 // original critical path. 495 // 496 // TODO: If we tracked more than one register here, we could potentially 497 // fix that remaining critical edge too. This is a little more involved, 498 // because unlike the most recent register, less recent registers should 499 // still be considered, though only if no other registers are available. 500 std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); 501 502 // Attempt to break anti-dependence edges on the critical path. Walk the 503 // instructions from the bottom up, tracking information about liveness 504 // as we go to help determine which registers are available. 505 unsigned Broken = 0; 506 unsigned Count = InsertPosIndex - 1; 507 for (MachineBasicBlock::iterator I = End, E = Begin; 508 I != E; --Count) { 509 MachineInstr *MI = --I; 510 if (MI->isDebugValue()) 511 continue; 512 513 // Check if this instruction has a dependence on the critical path that 514 // is an anti-dependence that we may be able to break. If it is, set 515 // AntiDepReg to the non-zero register associated with the anti-dependence. 516 // 517 // We limit our attention to the critical path as a heuristic to avoid 518 // breaking anti-dependence edges that aren't going to significantly 519 // impact the overall schedule. There are a limited number of registers 520 // and we want to save them for the important edges. 521 // 522 // TODO: Instructions with multiple defs could have multiple 523 // anti-dependencies. The current code here only knows how to break one 524 // edge per instruction. Note that we'd have to be able to break all of 525 // the anti-dependencies in an instruction in order to be effective. 526 unsigned AntiDepReg = 0; 527 if (MI == CriticalPathMI) { 528 if (const SDep *Edge = CriticalPathStep(CriticalPathSU)) { 529 const SUnit *NextSU = Edge->getSUnit(); 530 531 // Only consider anti-dependence edges. 532 if (Edge->getKind() == SDep::Anti) { 533 AntiDepReg = Edge->getReg(); 534 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); 535 if (!RegClassInfo.isAllocatable(AntiDepReg)) 536 // Don't break anti-dependencies on non-allocatable registers. 537 AntiDepReg = 0; 538 else if (KeepRegs.test(AntiDepReg)) 539 // Don't break anti-dependencies if an use down below requires 540 // this exact register. 541 AntiDepReg = 0; 542 else { 543 // If the SUnit has other dependencies on the SUnit that it 544 // anti-depends on, don't bother breaking the anti-dependency 545 // since those edges would prevent such units from being 546 // scheduled past each other regardless. 547 // 548 // Also, if there are dependencies on other SUnits with the 549 // same register as the anti-dependency, don't attempt to 550 // break it. 551 for (SUnit::const_pred_iterator P = CriticalPathSU->Preds.begin(), 552 PE = CriticalPathSU->Preds.end(); P != PE; ++P) 553 if (P->getSUnit() == NextSU ? 554 (P->getKind() != SDep::Anti || P->getReg() != AntiDepReg) : 555 (P->getKind() == SDep::Data && P->getReg() == AntiDepReg)) { 556 AntiDepReg = 0; 557 break; 558 } 559 } 560 } 561 CriticalPathSU = NextSU; 562 CriticalPathMI = CriticalPathSU->getInstr(); 563 } else { 564 // We've reached the end of the critical path. 565 CriticalPathSU = 0; 566 CriticalPathMI = 0; 567 } 568 } 569 570 PrescanInstruction(MI); 571 572 // If MI's defs have a special allocation requirement, don't allow 573 // any def registers to be changed. Also assume all registers 574 // defined in a call must not be changed (ABI). 575 if (MI->isCall() || MI->hasExtraDefRegAllocReq() || 576 TII->isPredicated(MI)) 577 // If this instruction's defs have special allocation requirement, don't 578 // break this anti-dependency. 579 AntiDepReg = 0; 580 else if (AntiDepReg) { 581 // If this instruction has a use of AntiDepReg, breaking it 582 // is invalid. 583 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 584 MachineOperand &MO = MI->getOperand(i); 585 if (!MO.isReg()) continue; 586 unsigned Reg = MO.getReg(); 587 if (Reg == 0) continue; 588 if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { 589 AntiDepReg = 0; 590 break; 591 } 592 } 593 } 594 595 // Determine AntiDepReg's register class, if it is live and is 596 // consistently used within a single class. 597 const TargetRegisterClass *RC = AntiDepReg != 0 ? Classes[AntiDepReg] : 0; 598 assert((AntiDepReg == 0 || RC != NULL) && 599 "Register should be live if it's causing an anti-dependence!"); 600 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) 601 AntiDepReg = 0; 602 603 // Look for a suitable register to use to break the anti-depenence. 604 // 605 // TODO: Instead of picking the first free register, consider which might 606 // be the best. 607 if (AntiDepReg != 0) { 608 std::pair<std::multimap<unsigned, MachineOperand *>::iterator, 609 std::multimap<unsigned, MachineOperand *>::iterator> 610 Range = RegRefs.equal_range(AntiDepReg); 611 if (unsigned NewReg = findSuitableFreeRegister(Range.first, Range.second, 612 AntiDepReg, 613 LastNewReg[AntiDepReg], 614 RC)) { 615 DEBUG(dbgs() << "Breaking anti-dependence edge on " 616 << TRI->getName(AntiDepReg) 617 << " with " << RegRefs.count(AntiDepReg) << " references" 618 << " using " << TRI->getName(NewReg) << "!\n"); 619 620 // Update the references to the old register to refer to the new 621 // register. 622 for (std::multimap<unsigned, MachineOperand *>::iterator 623 Q = Range.first, QE = Range.second; Q != QE; ++Q) { 624 Q->second->setReg(NewReg); 625 // If the SU for the instruction being updated has debug information 626 // related to the anti-dependency register, make sure to update that 627 // as well. 628 const SUnit *SU = MISUnitMap[Q->second->getParent()]; 629 if (!SU) continue; 630 for (DbgValueVector::iterator DVI = DbgValues.begin(), 631 DVE = DbgValues.end(); DVI != DVE; ++DVI) 632 if (DVI->second == Q->second->getParent()) 633 UpdateDbgValue(DVI->first, AntiDepReg, NewReg); 634 } 635 636 // We just went back in time and modified history; the 637 // liveness information for the anti-dependence reg is now 638 // inconsistent. Set the state as if it were dead. 639 Classes[NewReg] = Classes[AntiDepReg]; 640 DefIndices[NewReg] = DefIndices[AntiDepReg]; 641 KillIndices[NewReg] = KillIndices[AntiDepReg]; 642 assert(((KillIndices[NewReg] == ~0u) != 643 (DefIndices[NewReg] == ~0u)) && 644 "Kill and Def maps aren't consistent for NewReg!"); 645 646 Classes[AntiDepReg] = 0; 647 DefIndices[AntiDepReg] = KillIndices[AntiDepReg]; 648 KillIndices[AntiDepReg] = ~0u; 649 assert(((KillIndices[AntiDepReg] == ~0u) != 650 (DefIndices[AntiDepReg] == ~0u)) && 651 "Kill and Def maps aren't consistent for AntiDepReg!"); 652 653 RegRefs.erase(AntiDepReg); 654 LastNewReg[AntiDepReg] = NewReg; 655 ++Broken; 656 } 657 } 658 659 ScanInstruction(MI, Count); 660 } 661 662 return Broken; 663} 664