Lines Matching +full:tri +full:- +full:state
1 //===- AggressiveAntiDepBreaker.cpp - Anti-dep breaker --------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 // implements register anti-dependence breaking during post-RA
11 // scheduling. It attempts to break all anti-dependencies within a
14 //===----------------------------------------------------------------------===//
41 #define DEBUG_TYPE "post-RA-sched"
45 DebugDiv("agg-antidep-debugdiv",
46 cl::desc("Debug control for aggressive anti-dep breaker"),
50 DebugMod("agg-antidep-debugmod",
51 cl::desc("Debug control for aggressive anti-dep breaker"),
59 const unsigned BBSize = BB->size(); in AggressiveAntiDepState()
62 // assign the register to the same-indexed GroupNode. in AggressiveAntiDepState()
84 if ((GetGroup(Reg) == Group) && (RegRefs->count(Reg) > 0)) in GetGroupRegs()
124 TRI(MF.getSubtarget().getRegisterInfo()), RegClassInfo(RCI) { in AggressiveAntiDepBreaker()
128 BitVector CPSet = TRI->getAllocatableSet(MF, RC); in AggressiveAntiDepBreaker()
135 LLVM_DEBUG(dbgs() << "AntiDep Critical-Path Registers:"); in AggressiveAntiDepBreaker()
138 << " " << printReg(r, TRI)); in AggressiveAntiDepBreaker()
143 delete State; in ~AggressiveAntiDepBreaker()
147 assert(!State); in StartBlock()
148 State = new AggressiveAntiDepState(TRI->getNumRegs(), BB); in StartBlock()
150 bool IsReturnBlock = BB->isReturnBlock(); in StartBlock()
151 std::vector<unsigned> &KillIndices = State->GetKillIndices(); in StartBlock()
152 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in StartBlock()
154 // Examine the live-in regs of all successors. in StartBlock()
155 for (MachineBasicBlock *Succ : BB->successors()) in StartBlock()
156 for (const auto &LI : Succ->liveins()) { in StartBlock()
157 for (MCRegAliasIterator AI(LI.PhysReg, TRI, true); AI.isValid(); ++AI) { in StartBlock()
159 State->UnionGroups(Reg, 0); in StartBlock()
160 KillIndices[Reg] = BB->size(); in StartBlock()
165 // Mark live-out callee-saved registers. In a return block this is in StartBlock()
166 // all callee-saved registers. In non-return this is any in StartBlock()
167 // callee-saved register that is not saved in the prolog. in StartBlock()
175 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { in StartBlock()
177 State->UnionGroups(AliasReg, 0); in StartBlock()
178 KillIndices[AliasReg] = BB->size(); in StartBlock()
185 delete State; in FinishBlock()
186 State = nullptr; in FinishBlock()
202 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in Observe()
203 for (unsigned Reg = 1; Reg != TRI->getNumRegs(); ++Reg) { in Observe()
205 // we don't know the extent of its live-range anymore (now that it in Observe()
210 if (State->IsLive(Reg)) { in Observe()
211 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() in Observe()
212 << " " << printReg(Reg, TRI) << "=g" << State->GetGroup(Reg) in Observe()
213 << "->g0(region live-out)"); in Observe()
214 State->UnionGroups(Reg, 0); in Observe()
234 Op = MI.findRegisterUseOperand(Reg, /*TRI=*/nullptr, true); in IsImplicitDefUse()
236 Op = MI.findRegisterDefOperand(Reg, /*TRI=*/nullptr); in IsImplicitDefUse()
238 return(Op && Op->isImplicit()); in IsImplicitDefUse()
249 for (MCPhysReg SubReg : TRI->subregs_inclusive(Reg)) in GetPassthruRegs()
255 /// AntiDepEdges - Return in Edges the anti- and output- dependencies
259 for (const SDep &Pred : SU->Preds) { in AntiDepEdges()
267 /// CriticalPathStep - Return the next SUnit after SU on the bottom-up
274 for (const SDep &Pred : SU->Preds) { in CriticalPathStep()
277 unsigned PredTotalLatency = PredSU->getDepth() + PredLatency; in CriticalPathStep()
278 // In the case of a latency tie, prefer an anti-dependency edge over in CriticalPathStep()
288 return (Next) ? Next->getSUnit() : nullptr; in CriticalPathStep()
295 std::vector<unsigned> &KillIndices = State->GetKillIndices(); in HandleLastUse()
296 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in HandleLastUse()
298 RegRefs = State->GetRegRefs(); in HandleLastUse()
304 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) in HandleLastUse()
305 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) { in HandleLastUse()
310 if (!State->IsLive(Reg)) { in HandleLastUse()
314 State->LeaveGroup(Reg); in HandleLastUse()
316 dbgs() << header << printReg(Reg, TRI); in HandleLastUse()
319 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << tag); in HandleLastUse()
324 for (MCPhysReg SubregReg : TRI->subregs(Reg)) { in HandleLastUse()
325 if (!State->IsLive(SubregReg)) { in HandleLastUse()
329 State->LeaveGroup(SubregReg); in HandleLastUse()
331 dbgs() << header << printReg(Reg, TRI); in HandleLastUse()
334 LLVM_DEBUG(dbgs() << " " << printReg(SubregReg, TRI) << "->g" in HandleLastUse()
335 << State->GetGroup(SubregReg) << tag); in HandleLastUse()
345 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in PrescanInstruction()
347 RegRefs = State->GetRegRefs(); in PrescanInstruction()
349 // Handle dead defs by simulating a last-use of the register just in PrescanInstruction()
368 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" in PrescanInstruction()
369 << State->GetGroup(Reg)); in PrescanInstruction()
375 // can tell user specified registers from compiler-specified. in PrescanInstruction()
376 if (MI.isCall() || MI.hasExtraDefRegAllocReq() || TII->isPredicated(MI) || in PrescanInstruction()
378 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); in PrescanInstruction()
379 State->UnionGroups(Reg, 0); in PrescanInstruction()
384 for (MCRegAliasIterator AI(Reg, TRI, false); AI.isValid(); ++AI) { in PrescanInstruction()
386 if (State->IsLive(AliasReg)) { in PrescanInstruction()
387 State->UnionGroups(Reg, AliasReg); in PrescanInstruction()
388 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(Reg) << "(via " in PrescanInstruction()
389 << printReg(AliasReg, TRI) << ")"); in PrescanInstruction()
396 RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); in PrescanInstruction()
404 // live-ranges. in PrescanInstruction()
414 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { in PrescanInstruction()
415 // We need to be careful here not to define already-live super registers. in PrescanInstruction()
419 // because we're iterating bottom-up) need to be linked to the same group in PrescanInstruction()
421 if (TRI->isSuperRegister(Reg, *AI) && State->IsLive(*AI)) in PrescanInstruction()
433 RegRefs = State->GetRegRefs(); in ScanInstruction()
441 // if-conversion: in ScanInstruction()
450 // re-define R6 so it's not safe to change it since the last R6 use cannot be in ScanInstruction()
453 TII->isPredicated(MI) || MI.isInlineAsm(); in ScanInstruction()
456 // live-ranges, groups and RegRefs. in ScanInstruction()
463 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI) << "=g" in ScanInstruction()
464 << State->GetGroup(Reg)); in ScanInstruction()
467 // the previous live-range information and start a new live-range in ScanInstruction()
469 HandleLastUse(Reg, Count, "(last-use)"); in ScanInstruction()
472 LLVM_DEBUG(if (State->GetGroup(Reg) != 0) dbgs() << "->g0(alloc-req)"); in ScanInstruction()
473 State->UnionGroups(Reg, 0); in ScanInstruction()
479 RC = TII->getRegClass(MI.getDesc(), i, TRI, MF); in ScanInstruction()
498 LLVM_DEBUG(dbgs() << "=" << printReg(Reg, TRI)); in ScanInstruction()
499 State->UnionGroups(FirstReg, Reg); in ScanInstruction()
501 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); in ScanInstruction()
506 LLVM_DEBUG(dbgs() << "->g" << State->GetGroup(FirstReg) << '\n'); in ScanInstruction()
511 BitVector BV(TRI->getNumRegs(), false); in GetRenameRegisters()
517 for (const auto &Q : make_range(State->GetRegRefs().equal_range(Reg))) { in GetRenameRegisters()
521 BitVector RCBV = TRI->getAllocatableSet(MF, RC); in GetRenameRegisters()
529 LLVM_DEBUG(dbgs() << " " << TRI->getRegClassName(RC)); in GetRenameRegisters()
538 std::vector<unsigned> &KillIndices = State->GetKillIndices(); in FindSuitableFreeRegisters()
539 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in FindSuitableFreeRegisters()
541 RegRefs = State->GetRegRefs(); in FindSuitableFreeRegisters()
545 // break the anti-dependence. in FindSuitableFreeRegisters()
547 State->GetGroupRegs(AntiDepGroupIndex, Regs, &RegRefs); in FindSuitableFreeRegisters()
560 LLVM_DEBUG(dbgs() << "\t\t" << printReg(Reg, TRI) << ":"); in FindSuitableFreeRegisters()
569 dbgs() << " " << printReg(r, TRI); in FindSuitableFreeRegisters()
578 bool IsSub = TRI->isSubRegister(SuperReg, Reg); in FindSuitableFreeRegisters()
593 dbgs() << "*** Performing rename " << printReg(SuperReg, TRI) in FindSuitableFreeRegisters()
598 // Check each possible rename register for SuperReg in round-robin in FindSuitableFreeRegisters()
607 TRI->getMinimalPhysRegClass(SuperReg, MVT::Other); in FindSuitableFreeRegisters()
624 --R; in FindSuitableFreeRegisters()
626 // Don't consider non-allocatable registers in FindSuitableFreeRegisters()
631 LLVM_DEBUG(dbgs() << " [" << printReg(NewSuperReg, TRI) << ':'); in FindSuitableFreeRegisters()
642 unsigned NewSubRegIdx = TRI->getSubRegIndex(SuperReg, Reg); in FindSuitableFreeRegisters()
644 NewReg = TRI->getSubReg(NewSuperReg, NewSubRegIdx); in FindSuitableFreeRegisters()
647 LLVM_DEBUG(dbgs() << " " << printReg(NewReg, TRI)); in FindSuitableFreeRegisters()
659 if (State->IsLive(NewReg) || (KillIndices[Reg] > DefIndices[NewReg])) { in FindSuitableFreeRegisters()
664 for (MCRegAliasIterator AI(NewReg, TRI, false); AI.isValid(); ++AI) { in FindSuitableFreeRegisters()
666 if (State->IsLive(AliasReg) || in FindSuitableFreeRegisters()
669 << "(alias " << printReg(AliasReg, TRI) << " live)"); in FindSuitableFreeRegisters()
679 // defines 'NewReg' via an early-clobber operand. in FindSuitableFreeRegisters()
681 MachineInstr *UseMI = Q.second.Operand->getParent(); in FindSuitableFreeRegisters()
682 int Idx = UseMI->findRegisterDefOperandIdx(NewReg, TRI, false, true); in FindSuitableFreeRegisters()
683 if (Idx == -1) in FindSuitableFreeRegisters()
686 if (UseMI->getOperand(Idx).isEarlyClobber()) { in FindSuitableFreeRegisters()
693 // 'Reg' is an early-clobber define and that instruction also uses in FindSuitableFreeRegisters()
696 if (!Q.second.Operand->isDef() || !Q.second.Operand->isEarlyClobber()) in FindSuitableFreeRegisters()
699 MachineInstr *DefMI = Q.second.Operand->getParent(); in FindSuitableFreeRegisters()
700 if (DefMI->readsRegister(NewReg, TRI)) { in FindSuitableFreeRegisters()
710 // If we fall-out here, then every register in the group can be in FindSuitableFreeRegisters()
727 /// BreakAntiDependencies - Identifiy anti-dependencies within the
735 std::vector<unsigned> &KillIndices = State->GetKillIndices(); in BreakAntiDependencies()
736 std::vector<unsigned> &DefIndices = State->GetDefIndices(); in BreakAntiDependencies()
738 RegRefs = State->GetRegRefs(); in BreakAntiDependencies()
754 // break critical-path anti-dependencies. in BreakAntiDependencies()
761 (CriticalPathSU->getDepth() + CriticalPathSU->Latency))) { in BreakAntiDependencies()
766 CriticalPathMI = CriticalPathSU->getInstr(); in BreakAntiDependencies()
770 LLVM_DEBUG(dbgs() << "\n===== Aggressive anti-dependency breaking\n"); in BreakAntiDependencies()
772 for (unsigned Reg = 1; Reg < TRI->getNumRegs(); ++Reg) { in BreakAntiDependencies()
773 if (!State->IsLive(Reg)) in BreakAntiDependencies()
774 LLVM_DEBUG(dbgs() << " " << printReg(Reg, TRI)); in BreakAntiDependencies()
779 BitVector RegAliases(TRI->getNumRegs()); in BreakAntiDependencies()
781 // Attempt to break anti-dependence edges. Walk the instructions in BreakAntiDependencies()
785 unsigned Count = InsertPosIndex - 1; in BreakAntiDependencies()
787 I != E; --Count) { in BreakAntiDependencies()
788 MachineInstr &MI = *--I; in BreakAntiDependencies()
802 // The dependence edges that represent anti- and output- in BreakAntiDependencies()
813 CriticalPathMI = (CriticalPathSU) ? CriticalPathSU->getInstr() : nullptr; in BreakAntiDependencies()
819 // but don't cause any anti-dependence breaking themselves) in BreakAntiDependencies()
821 // Attempt to break each anti-dependency... in BreakAntiDependencies()
823 SUnit *NextSU = Edge->getSUnit(); in BreakAntiDependencies()
825 if ((Edge->getKind() != SDep::Anti) && in BreakAntiDependencies()
826 (Edge->getKind() != SDep::Output)) continue; in BreakAntiDependencies()
828 unsigned AntiDepReg = Edge->getReg(); in BreakAntiDependencies()
829 LLVM_DEBUG(dbgs() << "\tAntidep reg: " << printReg(AntiDepReg, TRI)); in BreakAntiDependencies()
830 assert(AntiDepReg != 0 && "Anti-dependence on reg0?"); in BreakAntiDependencies()
833 // Don't break anti-dependencies on non-allocatable registers. in BreakAntiDependencies()
834 LLVM_DEBUG(dbgs() << " (non-allocatable)\n"); in BreakAntiDependencies()
836 } else if (ExcludeRegs && ExcludeRegs->test(AntiDepReg)) { in BreakAntiDependencies()
837 // Don't break anti-dependencies for critical path registers in BreakAntiDependencies()
839 LLVM_DEBUG(dbgs() << " (not critical-path)\n"); in BreakAntiDependencies()
842 // If the anti-dep register liveness "passes-thru", then in BreakAntiDependencies()
848 // No anti-dep breaking for implicit deps in BreakAntiDependencies()
850 MI.findRegisterDefOperand(AntiDepReg, /*TRI=*/nullptr); in BreakAntiDependencies()
852 if (!AntiDepOp || AntiDepOp->isImplicit()) { in BreakAntiDependencies()
858 // it anti-depends on, don't bother breaking the in BreakAntiDependencies()
859 // anti-dependency since those edges would prevent such in BreakAntiDependencies()
864 // same register as the anti-dependency, don't attempt to in BreakAntiDependencies()
866 for (const SDep &Pred : PathSU->Preds) { in BreakAntiDependencies()
875 for (const SDep &Pred : PathSU->Preds) { in BreakAntiDependencies()
897 const unsigned GroupIndex = State->GetGroup(AntiDepReg); in BreakAntiDependencies()
905 // Look for a suitable register to use to break the anti-dependence. in BreakAntiDependencies()
909 LLVM_DEBUG(dbgs() << "\tBreaking anti-dependence edge on " in BreakAntiDependencies()
910 << printReg(AntiDepReg, TRI) << ":"); in BreakAntiDependencies()
917 LLVM_DEBUG(dbgs() << " " << printReg(CurrReg, TRI) << "->" in BreakAntiDependencies()
918 << printReg(NewReg, TRI) << "(" in BreakAntiDependencies()
924 Q.second.Operand->setReg(NewReg); in BreakAntiDependencies()
926 // information related to the anti-dependency register, make in BreakAntiDependencies()
928 const SUnit *SU = MISUnitMap[Q.second.Operand->getParent()]; in BreakAntiDependencies()
930 UpdateDbgValues(DbgValues, Q.second.Operand->getParent(), in BreakAntiDependencies()
936 // the state as if it were dead. in BreakAntiDependencies()
937 State->UnionGroups(NewReg, 0); in BreakAntiDependencies()
942 State->UnionGroups(CurrReg, 0); in BreakAntiDependencies()