Lines Matching +full:keep +full:- +full:a +full:- +full:live
1 //===- CriticalAntiDepBreaker.cpp - Anti-dep breaker ----------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // implements register anti-dependence breaking along a blocks
11 // critical path during post-RA scheduler.
13 //===----------------------------------------------------------------------===//
39 #define DEBUG_TYPE "post-RA-sched"
45 Classes(TRI->getNumRegs(), nullptr), KillIndices(TRI->getNumRegs(), 0), in CriticalAntiDepBreaker()
46 DefIndices(TRI->getNumRegs(), 0), KeepRegs(TRI->getNumRegs(), false) {} in CriticalAntiDepBreaker()
51 const unsigned BBSize = BB->size(); in StartBlock()
52 for (unsigned i = 1, e = TRI->getNumRegs(); i != e; ++i) { in StartBlock()
56 // Initialize the indices to indicate that no registers are live. in StartBlock()
64 bool IsReturnBlock = BB->isReturnBlock(); in StartBlock()
66 // Examine the live-in regs of all successors. in StartBlock()
67 for (const MachineBasicBlock *Succ : BB->successors()) in StartBlock()
68 for (const auto &LI : Succ->liveins()) { in StartBlock()
71 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in StartBlock()
77 // Mark live-out callee-saved registers. In a return block this is in StartBlock()
78 // all callee-saved registers. In non-return this is any in StartBlock()
79 // callee-saved register that is not saved in the prolog. in StartBlock()
89 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in StartBlock()
104 // be a real definition earlier that needs to be paired with uses dominated by in Observe()
114 for (unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) { in Observe()
116 // If Reg is currently live, then mark that it can't be renamed as in Observe()
117 // we don't know the extent of its live-range anymore (now that it in Observe()
119 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in Observe()
126 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in Observe()
138 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
144 for (const SDep &P : SU->Preds) { in CriticalPathStep()
147 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; in CriticalPathStep()
148 // In the case of a latency tie, prefer an anti-dependency edge over in CriticalPathStep()
162 // registers used in a call must not be changed (ABI). in PrescanInstruction()
165 // if-conversion: in PrescanInstruction()
172 // The first R6 kill is not really a kill since it's killed by a predicated in PrescanInstruction()
174 // re-define R6 so it's not safe to change it since the last R6 use cannot be in PrescanInstruction()
177 MI.isCall() || MI.hasExtraSrcRegAllocReq() || TII->isPredicated(MI); in PrescanInstruction()
189 NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); in PrescanInstruction()
196 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in PrescanInstruction()
200 // If an alias of the reg is used during the live range, give up. in PrescanInstruction()
205 Classes[AliasReg] = reinterpret_cast<TargetRegisterClass *>(-1); in PrescanInstruction()
206 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in PrescanInstruction()
211 if (Classes[Reg] != reinterpret_cast<TargetRegisterClass *>(-1)) in PrescanInstruction()
216 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) in PrescanInstruction()
228 // If this reg is tied and live (Classes[Reg] is set to -1), we can't change in PrescanInstruction()
235 // of a register? In the above 'xor' example, the uses of %eax are undef, so in PrescanInstruction()
239 Classes[Reg] == reinterpret_cast<TargetRegisterClass *>(-1)) { in PrescanInstruction()
240 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) { in PrescanInstruction()
243 for (MCPhysReg SuperReg : TRI->superregs(Reg)) { in PrescanInstruction()
254 assert(!MI.isKill() && "Attempting to scan a kill instruction"); in ScanInstruction()
256 if (!TII->isPredicated(MI)) { in ScanInstruction()
264 return all_of(TRI->subregs_inclusive(PhysReg), in ScanInstruction()
268 for (unsigned i = 1, e = TRI->getNumRegs(); i != e; ++i) { in ScanInstruction()
284 // Ignore two-addr defs. in ScanInstruction()
290 bool Keep = KeepRegs.test(Reg); in ScanInstruction() local
294 for (MCPhysReg SubregReg : TRI->subregs_inclusive(Reg)) { in ScanInstruction()
299 if (!Keep) in ScanInstruction()
302 // Conservatively mark super-registers as unusable. in ScanInstruction()
303 for (MCPhysReg SR : TRI->superregs(Reg)) in ScanInstruction()
304 Classes[SR] = reinterpret_cast<TargetRegisterClass *>(-1); in ScanInstruction()
316 NewRC = TII->getRegClass(MI.getDesc(), i, TRI, MF); in ScanInstruction()
323 Classes[Reg] = reinterpret_cast<TargetRegisterClass *>(-1); in ScanInstruction()
327 // It wasn't previously live but now it is, this is a kill. in ScanInstruction()
343 // Note: AntiDepReg may be referenced by a two-address instruction such that
344 // it's use operand is tied to a def operand. We guard against the case in which
345 // the two-address instruction also defines NewReg, as may happen with
355 MachineOperand *RefOper = I->second; in isNewRegClobberedByRefs()
360 if (RefOper->isDef() && RefOper->isEarlyClobber()) in isNewRegClobberedByRefs()
364 MachineInstr *MI = RefOper->getParent(); in isNewRegClobberedByRefs()
365 for (const MachineOperand &CheckOper : MI->operands()) { in isNewRegClobberedByRefs()
375 if (RefOper->isDef()) in isNewRegClobberedByRefs()
385 if (MI->isInlineAsm()) in isNewRegClobberedByRefs()
401 // Don't replace a register with itself. in findSuitableFreeRegister()
403 // Don't replace a register with one that was recently used to repair in findSuitableFreeRegister()
404 // an anti-dependence with this AntiDepReg, because that would in findSuitableFreeRegister()
405 // re-introduce that anti-dependence. in findSuitableFreeRegister()
418 Classes[NewReg] == reinterpret_cast<TargetRegisterClass *>(-1) || in findSuitableFreeRegister()
424 if (TRI->regsOverlap(NewReg, R)) { in findSuitableFreeRegister()
446 // Keep a map of the MachineInstr*'s back to the SUnit representing them. in BreakAntiDependencies()
456 if (!Max || SU.getDepth() + SU.Latency > Max->getDepth() + Max->Latency) in BreakAntiDependencies()
464 << (Max->getDepth() + Max->Latency) << "\n"); in BreakAntiDependencies()
466 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) { in BreakAntiDependencies()
477 MachineInstr *CriticalPathMI = CriticalPathSU->getInstr(); in BreakAntiDependencies()
480 // A = ... in BreakAntiDependencies()
481 // ... = A in BreakAntiDependencies()
482 // A = ... in BreakAntiDependencies()
483 // ... = A in BreakAntiDependencies()
484 // A = ... in BreakAntiDependencies()
485 // ... = A in BreakAntiDependencies()
486 // A = ... in BreakAntiDependencies()
487 // ... = A in BreakAntiDependencies()
488 // There are three anti-dependencies here, and without special care, in BreakAntiDependencies()
490 // A = ... in BreakAntiDependencies()
491 // ... = A in BreakAntiDependencies()
498 // because at each anti-dependence, B is the first register that in BreakAntiDependencies()
499 // isn't A which is free. This re-introduces anti-dependencies in BreakAntiDependencies()
500 // at all but one of the original anti-dependencies that we were in BreakAntiDependencies()
501 // trying to break. To avoid this, keep track of the most recent in BreakAntiDependencies()
503 // using it to repair an anti-dependence on the same register. in BreakAntiDependencies()
505 // A = ... in BreakAntiDependencies()
506 // ... = A in BreakAntiDependencies()
513 // This still has an anti-dependence on B, but at least it isn't on the in BreakAntiDependencies()
517 // fix that remaining critical edge too. This is a little more involved, in BreakAntiDependencies()
520 std::vector<unsigned> LastNewReg(TRI->getNumRegs(), 0); in BreakAntiDependencies()
522 // Attempt to break anti-dependence edges on the critical path. Walk the in BreakAntiDependencies()
526 unsigned Count = InsertPosIndex - 1; in BreakAntiDependencies()
527 for (MachineBasicBlock::iterator I = End, E = Begin; I != E; --Count) { in BreakAntiDependencies()
528 MachineInstr &MI = *--I; in BreakAntiDependencies()
530 // might be a real definition earlier that needs to be paired with uses in BreakAntiDependencies()
539 // Check if this instruction has a dependence on the critical path that in BreakAntiDependencies()
540 // is an anti-dependence that we may be able to break. If it is, set in BreakAntiDependencies()
541 // AntiDepReg to the non-zero register associated with the anti-dependence. in BreakAntiDependencies()
543 // We limit our attention to the critical path as a heuristic to avoid in BreakAntiDependencies()
544 // breaking anti-dependence edges that aren't going to significantly in BreakAntiDependencies()
545 // impact the overall schedule. There are a limited number of registers in BreakAntiDependencies()
549 // anti-dependencies. The current code here only knows how to break one in BreakAntiDependencies()
551 // the anti-dependencies in an instruction in order to be effective. in BreakAntiDependencies()
555 const SUnit *NextSU = Edge->getSUnit(); in BreakAntiDependencies()
557 // Only consider anti-dependence edges. in BreakAntiDependencies()
558 if (Edge->getKind() == SDep::Anti) { in BreakAntiDependencies()
559 AntiDepReg = Edge->getReg(); in BreakAntiDependencies()
560 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); in BreakAntiDependencies()
562 // Don't break anti-dependencies on non-allocatable registers. in BreakAntiDependencies()
565 // Don't break anti-dependencies if a use down below requires in BreakAntiDependencies()
570 // anti-depends on, don't bother breaking the anti-dependency in BreakAntiDependencies()
575 // same register as the anti-dependency, don't attempt to in BreakAntiDependencies()
577 for (const SDep &P : CriticalPathSU->Preds) in BreakAntiDependencies()
588 CriticalPathMI = CriticalPathSU->getInstr(); in BreakAntiDependencies()
600 // If MI's defs have a special allocation requirement, don't allow in BreakAntiDependencies()
602 // defined in a call must not be changed (ABI). in BreakAntiDependencies()
603 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI)) in BreakAntiDependencies()
605 // break this anti-dependency. in BreakAntiDependencies()
608 // If this instruction has a use of AntiDepReg, breaking it in BreakAntiDependencies()
610 // save a list of them so that we don't pick a new register in BreakAntiDependencies()
616 if (MO.isUse() && TRI->regsOverlap(AntiDepReg, Reg)) { in BreakAntiDependencies()
625 // Determine AntiDepReg's register class, if it is live and is in BreakAntiDependencies()
626 // consistently used within a single class. in BreakAntiDependencies()
630 "Register should be live if it's causing an anti-dependence!"); in BreakAntiDependencies()
631 if (RC == reinterpret_cast<TargetRegisterClass *>(-1)) in BreakAntiDependencies()
634 // Look for a suitable register to use to break the anti-dependence. in BreakAntiDependencies()
646 LLVM_DEBUG(dbgs() << "Breaking anti-dependence edge on " in BreakAntiDependencies()
655 Q->second->setReg(NewReg); in BreakAntiDependencies()
657 // related to the anti-dependency register, make sure to update that in BreakAntiDependencies()
659 const SUnit *SU = MISUnitMap[Q->second->getParent()]; in BreakAntiDependencies()
661 UpdateDbgValues(DbgValues, Q->second->getParent(), in BreakAntiDependencies()
666 // liveness information for the anti-dependence reg is now in BreakAntiDependencies()