50#define DEBUG_TYPE "regalloc"
54STATISTIC(NumCoalesced,
"Number of copies coalesced");
70 bool ClearVirtRegs_ =
true) :
72 ShouldAllocateClass(
F),
73 StackSlotForVirtReg(-1),
74 ClearVirtRegs(ClearVirtRegs_) {
99 bool Reloaded =
false;
102 explicit LiveReg(
Register VirtReg) : VirtReg(VirtReg) {}
104 unsigned getSparseSetIndex()
const {
112 LiveRegMap LiveVirtRegs;
146 std::vector<unsigned> RegUnitStates;
153 RegUnitSet UsedInInstr;
154 RegUnitSet PhysRegUses;
159 void setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState);
160 bool isPhysRegFree(
MCPhysReg PhysReg)
const;
163 void markRegUsedInInstr(
MCPhysReg PhysReg) {
165 UsedInInstr.insert(Unit);
169 bool isClobberedByRegMasks(
MCPhysReg PhysReg)
const {
176 bool isRegUsedInInstr(
MCPhysReg PhysReg,
bool LookAtPhysRegUses)
const {
177 if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
180 if (UsedInInstr.count(Unit))
182 if (LookAtPhysRegUses && PhysRegUses.count(Unit))
190 void markPhysRegUsedInInstr(
MCPhysReg PhysReg) {
192 PhysRegUses.insert(Unit);
196 void unmarkRegUsedInInstr(
MCPhysReg PhysReg) {
198 UsedInInstr.erase(Unit);
205 spillImpossible = ~0
u
218 MachineFunctionProperties::Property::NoPHIs);
224 MachineFunctionProperties::Property::NoVRegs);
232 MachineFunctionProperties::Property::IsSSA);
240 void addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
254 unsigned calcSpillCost(
MCPhysReg PhysReg)
const;
266 bool LookAtPhysRegUses =
false);
273 bool LookAtPhysRegUses =
false);
286 bool shouldAllocateRegister(
const Register Reg)
const;
287 int getStackSpaceFor(
Register VirtReg);
289 MCPhysReg AssignedReg,
bool Kill,
bool LiveOut);
296 void dumpState()
const;
301char RegAllocFast::ID = 0;
309 return ShouldAllocateClass(*
TRI, RC);
312void RegAllocFast::setPhysRegState(
MCPhysReg PhysReg,
unsigned NewState) {
314 RegUnitStates[Unit] = NewState;
317bool RegAllocFast::isPhysRegFree(
MCPhysReg PhysReg)
const {
319 if (RegUnitStates[Unit] != regFree)
327int RegAllocFast::getStackSpaceFor(
Register VirtReg) {
329 int SS = StackSlotForVirtReg[VirtReg];
336 unsigned Size =
TRI->getSpillSize(RC);
337 Align Alignment =
TRI->getSpillAlign(RC);
341 StackSlotForVirtReg[VirtReg] = FrameIdx;
353 for (; &*
I !=
A && &*
I !=
B; ++
I)
360bool RegAllocFast::mayLiveOut(
Register VirtReg) {
373 if (DefInst.getParent() !=
MBB) {
378 SelfLoopDef = &DefInst;
389 static const unsigned Limit = 8;
391 for (
const MachineInstr &UseInst :
MRI->use_nodbg_instructions(VirtReg)) {
392 if (UseInst.getParent() !=
MBB || ++
C >= Limit) {
401 if (SelfLoopDef == &UseInst ||
413bool RegAllocFast::mayLiveIn(
Register VirtReg) {
418 static const unsigned Limit = 8;
421 if (DefInst.getParent() !=
MBB || ++
C >= Limit) {
433 MCPhysReg AssignedReg,
bool Kill,
bool LiveOut) {
436 int FI = getStackSpaceFor(VirtReg);
453 SpilledOperandsMap[MO->getParent()].push_back(MO);
454 for (
auto MISpilledOperands : SpilledOperandsMap) {
460 *
MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
463 LLVM_DEBUG(
dbgs() <<
"Inserting debug info due to spill:\n" << *NewDV);
472 LLVM_DEBUG(
dbgs() <<
"Cloning debug info due to live out spill\n");
488 LRIDbgOperands.clear();
496 int FI = getStackSpaceFor(VirtReg);
507RegAllocFast::getMBBBeginInsertionPoint(
517 if (!
TII->isBasicBlockPrologue(*
I))
535 if (LiveVirtRegs.empty())
542 setPhysRegState(Reg, regLiveIn);
551 = getMBBBeginInsertionPoint(
MBB, PrologLiveIns);
552 for (
const LiveReg &LR : LiveVirtRegs) {
558 if (RegUnitStates[FirstUnit] == regLiveIn)
562 "no reload in start block. Missing vreg def?");
564 if (PrologLiveIns.
count(PhysReg)) {
568 reload(
MBB.
begin(), LR.VirtReg, PhysReg);
570 reload(InsertBefore, LR.VirtReg, PhysReg);
572 LiveVirtRegs.clear();
580 bool displacedAny = displacePhysReg(
MI, Reg);
581 setPhysRegState(Reg, regPreAssigned);
582 markRegUsedInInstr(Reg);
587 bool displacedAny = displacePhysReg(
MI, Reg);
588 setPhysRegState(Reg, regPreAssigned);
596 bool displacedAny =
false;
599 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
601 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
602 assert(LRI != LiveVirtRegs.end() &&
"datastructures in sync");
605 reload(ReloadBefore, VirtReg, LRI->PhysReg);
607 setPhysRegState(LRI->PhysReg, regFree);
609 LRI->Reloaded =
true;
614 RegUnitStates[Unit] = regFree;
624void RegAllocFast::freePhysReg(
MCPhysReg PhysReg) {
628 switch (
unsigned VirtReg = RegUnitStates[FirstUnit]) {
634 setPhysRegState(PhysReg, regFree);
637 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
638 assert(LRI != LiveVirtRegs.end());
640 setPhysRegState(LRI->PhysReg, regFree);
651unsigned RegAllocFast::calcSpillCost(
MCPhysReg PhysReg)
const {
653 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
659 return spillImpossible;
661 bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
662 findLiveVirtReg(VirtReg)->LiveOut;
663 return SureSpill ? spillClean : spillDirty;
670void RegAllocFast::assignDanglingDebugValues(
MachineInstr &Definition,
672 auto UDBGValIter = DanglingDbgValues.
find(VirtReg);
673 if (UDBGValIter == DanglingDbgValues.
end())
679 if (!
DbgValue->hasDebugOperandForReg(VirtReg))
687 if (
I->modifiesRegister(Reg,
TRI) || --Limit == 0) {
706void RegAllocFast::assignVirtToPhysReg(
MachineInstr &AtMI, LiveReg &LR,
711 assert(LR.PhysReg == 0 &&
"Already assigned a physreg");
712 assert(PhysReg != 0 &&
"Trying to assign no register");
713 LR.PhysReg = PhysReg;
714 setPhysRegState(PhysReg, VirtReg);
716 assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
720 return MI.isFullCopy();
724 static const unsigned ChainLengthLimit = 3;
727 if (
Reg.isPhysical())
735 }
while (++
C <= ChainLengthLimit);
743 static const unsigned DefLimit = 3;
748 Reg = traceCopyChain(Reg);
761 Register Hint0,
bool LookAtPhysRegUses) {
762 const Register VirtReg = LR.VirtReg;
767 <<
" in class " <<
TRI->getRegClassName(&RC)
772 !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
774 if (isPhysRegFree(Hint0)) {
777 assignVirtToPhysReg(
MI, LR, Hint0);
789 Register Hint1 = traceCopies(VirtReg);
791 !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
793 if (isPhysRegFree(Hint1)) {
796 assignVirtToPhysReg(
MI, LR, Hint1);
807 unsigned BestCost = spillImpossible;
811 if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
816 unsigned Cost = calcSpillCost(PhysReg);
820 assignVirtToPhysReg(
MI, LR, PhysReg);
824 if (PhysReg == Hint0 || PhysReg == Hint1)
825 Cost -= spillPrefBonus;
827 if (
Cost < BestCost) {
836 if (
MI.isInlineAsm())
837 MI.emitError(
"inline assembly requires more registers than available");
839 MI.emitError(
"ran out of registers during register allocation");
846 displacePhysReg(
MI, BestReg);
847 assignVirtToPhysReg(
MI, LR, BestReg);
854 if (!shouldAllocateRegister(VirtReg))
857 LiveRegMap::const_iterator LRI = findLiveVirtReg(VirtReg);
859 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
860 PhysReg = LRI->PhysReg;
869 if (SubRegIdx != 0) {
870 PhysReg =
TRI->getSubReg(PhysReg, SubRegIdx);
880bool RegAllocFast::defineLiveThroughVirtReg(
MachineInstr &
MI,
unsigned OpNum,
882 if (!shouldAllocateRegister(VirtReg))
884 LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
885 if (LRI != LiveVirtRegs.end()) {
887 if (PrevReg != 0 && isRegUsedInInstr(PrevReg,
true)) {
889 <<
" (tied/earlyclobber resolution)\n");
890 freePhysReg(PrevReg);
892 allocVirtReg(
MI, *LRI, 0,
true);
898 TII->get(TargetOpcode::COPY), PrevReg)
906 return defineVirtReg(
MI, OpNum, VirtReg,
true);
917 Register VirtReg,
bool LookAtPhysRegUses) {
919 if (!shouldAllocateRegister(VirtReg))
922 LiveRegMap::iterator LRI;
924 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
927 if (mayLiveOut(VirtReg)) {
935 if (LRI->PhysReg == 0) {
936 allocVirtReg(
MI, *LRI, 0, LookAtPhysRegUses);
947 assert(!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) &&
948 "TODO: preassign mismatch");
950 <<
" use existing assignment to "
955 if (LRI->Reloaded || LRI->LiveOut) {
956 if (!
MI.isImplicitDef()) {
959 LLVM_DEBUG(
dbgs() <<
"Spill Reason: LO: " << LRI->LiveOut <<
" RL: "
960 << LRI->Reloaded <<
'\n');
961 bool Kill = LRI->LastUse ==
nullptr;
962 spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);
966 if (
MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
967 int FI = StackSlotForVirtReg[VirtReg];
973 FI, &RC,
TRI, VirtReg);
980 LRI->LastUse =
nullptr;
982 LRI->LiveOut =
false;
983 LRI->Reloaded =
false;
985 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
986 BundleVirtRegsMap[VirtReg] = PhysReg;
988 markRegUsedInInstr(PhysReg);
989 return setPhysReg(
MI, MO, PhysReg);
997 if (!shouldAllocateRegister(VirtReg))
1000 LiveRegMap::iterator LRI;
1002 std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
1006 if (mayLiveOut(VirtReg)) {
1007 LRI->LiveOut =
true;
1014 assert((!MO.
isKill() || LRI->LastUse == &
MI) &&
"Invalid kill flag");
1018 if (LRI->PhysReg == 0) {
1021 if (
MI.isCopy() &&
MI.getOperand(1).getSubReg() == 0) {
1022 Hint =
MI.getOperand(0).getReg();
1024 assert(!shouldAllocateRegister(Hint));
1028 "Copy destination should already be assigned");
1031 allocVirtReg(
MI, *LRI, Hint,
false);
1043 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
1044 BundleVirtRegsMap[VirtReg] = LRI->PhysReg;
1046 markRegUsedInInstr(LRI->PhysReg);
1047 return setPhysReg(
MI, MO, LRI->PhysReg);
1072 MI.addRegisterKilled(PhysReg,
TRI,
true);
1081 MI.addRegisterDead(PhysReg,
TRI,
true);
1083 MI.addRegisterDefined(PhysReg,
TRI);
1092void RegAllocFast::dumpState()
const {
1093 for (
unsigned Unit = 1, UnitE =
TRI->getNumRegUnits(); Unit != UnitE;
1095 switch (
unsigned VirtReg = RegUnitStates[Unit]) {
1098 case regPreAssigned:
1105 LiveRegMap::const_iterator
I = findLiveVirtReg(VirtReg);
1106 assert(
I != LiveVirtRegs.end() &&
"have LiveVirtRegs entry");
1107 if (
I->LiveOut ||
I->Reloaded) {
1109 if (
I->LiveOut)
dbgs() <<
'O';
1110 if (
I->Reloaded)
dbgs() <<
'R';
1113 assert(
TRI->hasRegUnit(
I->PhysReg, Unit) &&
"inverse mapping present");
1120 for (
const LiveReg &LR : LiveVirtRegs) {
1126 "mapped to physreg");
1128 assert(RegUnitStates[Unit] == VirtReg &&
"inverse map valid");
1136void RegAllocFast::addRegClassDefCounts(std::vector<unsigned> &RegClassDefCounts,
1138 assert(RegClassDefCounts.size() ==
TRI->getNumRegClasses());
1140 if (
Reg.isVirtual()) {
1141 if (!shouldAllocateRegister(Reg))
1144 for (
unsigned RCIdx = 0, RCIdxEnd =
TRI->getNumRegClasses();
1145 RCIdx != RCIdxEnd; ++RCIdx) {
1149 ++RegClassDefCounts[RCIdx];
1155 for (
unsigned RCIdx = 0, RCIdxEnd =
TRI->getNumRegClasses();
1156 RCIdx != RCIdxEnd; ++RCIdx) {
1160 ++RegClassDefCounts[RCIdx];
1170void RegAllocFast::findAndSortDefOperandIndexes(
const MachineInstr &
MI) {
1171 DefOperandIndexes.
clear();
1174 std::vector<unsigned> RegClassDefCounts(
TRI->getNumRegClasses(), 0);
1175 assert(RegClassDefCounts[0] == 0);
1178 for (
unsigned I = 0,
E =
MI.getNumOperands();
I <
E; ++
I) {
1184 if (
Reg.isPhysical()) {
1186 markPhysRegUsedInInstr(Reg);
1191 if (
Reg.isVirtual() && shouldAllocateRegister(Reg))
1194 addRegClassDefCounts(RegClassDefCounts, Reg);
1208 unsigned ClassSize0 = RegClassInfo.
getOrder(&RC0).
size();
1209 unsigned ClassSize1 = RegClassInfo.
getOrder(&RC1).
size();
1211 bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.
getID()];
1212 bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.
getID()];
1213 if (SmallClass0 > SmallClass1)
1215 if (SmallClass0 < SmallClass1)
1223 if (Livethrough0 > Livethrough1)
1225 if (Livethrough0 < Livethrough1)
1246 UsedInInstr.clear();
1248 BundleVirtRegsMap.
clear();
1252 unsigned TiedIdx =
MI.findTiedOperandIdx(
Idx);
1257 bool HasPhysRegUse =
false;
1258 bool HasRegMask =
false;
1259 bool HasVRegDef =
false;
1260 bool HasDef =
false;
1261 bool HasEarlyClobber =
false;
1262 bool NeedToAssignLiveThroughs =
false;
1263 for (
unsigned I = 0;
I <
MI.getNumOperands(); ++
I) {
1267 if (
Reg.isVirtual()) {
1268 if (!shouldAllocateRegister(Reg))
1274 HasEarlyClobber =
true;
1275 NeedToAssignLiveThroughs =
true;
1277 if ((MO.
isTied() && !TiedOpIsUndef(MO,
I)) ||
1279 NeedToAssignLiveThroughs =
true;
1281 }
else if (
Reg.isPhysical()) {
1282 if (!
MRI->isReserved(Reg)) {
1285 bool displacedAny = definePhysReg(
MI, Reg);
1287 HasEarlyClobber =
true;
1292 HasPhysRegUse =
true;
1306 bool ReArrangedImplicitOps =
true;
1314 if (NeedToAssignLiveThroughs) {
1315 PhysRegUses.clear();
1317 while (ReArrangedImplicitOps) {
1318 ReArrangedImplicitOps =
false;
1319 findAndSortDefOperandIndexes(
MI);
1320 for (
uint16_t OpIdx : DefOperandIndexes) {
1325 (MO.
isTied() && !TiedOpIsUndef(MO, OpIdx)) ||
1327 ReArrangedImplicitOps = defineLiveThroughVirtReg(
MI, OpIdx, Reg);
1329 ReArrangedImplicitOps = defineVirtReg(
MI, OpIdx, Reg);
1331 if (ReArrangedImplicitOps) {
1340 while (ReArrangedImplicitOps) {
1341 ReArrangedImplicitOps =
false;
1342 for (
unsigned I = 0,
E =
MI.getNumOperands();
I <
E; ++
I) {
1347 if (
Reg.isVirtual()) {
1348 ReArrangedImplicitOps = defineVirtReg(
MI,
I, Reg);
1349 if (ReArrangedImplicitOps) {
1361 for (
signed I =
MI.getNumOperands() - 1;
I >= 0; --
I) {
1376 "tied def assigned to clobbered register");
1383 if (
Reg.isVirtual()) {
1384 assert(!shouldAllocateRegister(Reg));
1388 if (
MRI->isReserved(Reg))
1391 unmarkRegUsedInInstr(Reg);
1399 for (
const auto *RM : RegMasks)
1400 MRI->addPhysRegsUsedFromRegMask(RM);
1403 for (
const LiveReg &LR : LiveVirtRegs) {
1405 if (PhysReg != 0 && isClobberedByRegMasks(PhysReg))
1406 displacePhysReg(
MI, PhysReg);
1411 if (HasPhysRegUse) {
1416 if (!
Reg.isPhysical())
1418 if (
MRI->isReserved(Reg))
1420 bool displacedAny = usePhysReg(
MI, Reg);
1429 bool HasUndefUse =
false;
1430 bool ReArrangedImplicitMOs =
true;
1431 while (ReArrangedImplicitMOs) {
1432 ReArrangedImplicitMOs =
false;
1433 for (
unsigned I = 0;
I <
MI.getNumOperands(); ++
I) {
1438 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1452 ReArrangedImplicitMOs = useVirtReg(
MI,
I, Reg);
1453 if (ReArrangedImplicitMOs)
1464 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1467 assert(MO.
isUndef() &&
"Should only have undef virtreg uses left");
1468 allocVirtRegUndef(MO);
1473 if (HasEarlyClobber) {
1477 assert(!MO.
getSubReg() &&
"should be already handled in def processing");
1482 if (
Reg.isVirtual()) {
1483 assert(!shouldAllocateRegister(Reg));
1486 assert(
Reg.isPhysical() &&
"should have register assigned");
1494 if (
MI.readsRegister(Reg,
TRI))
1502 if (
MI.isCopy() &&
MI.getOperand(0).getReg() ==
MI.getOperand(1).getReg() &&
1503 MI.getNumOperands() == 2) {
1512 assert(
MI.isDebugValue() &&
"not a DBG_VALUE*");
1513 for (
const auto &MO :
MI.debug_operands()) {
1517 if (!
Reg.isVirtual())
1519 if (!shouldAllocateRegister(Reg))
1523 int SS = StackSlotForVirtReg[
Reg];
1533 LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
1538 if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
1540 for (
auto &RegMO : DbgOps)
1541 setPhysReg(
MI, *RegMO, LRI->PhysReg);
1543 DanglingDbgValues[
Reg].push_back(&
MI);
1548 LiveDbgValueMap[
Reg].append(DbgOps.
begin(), DbgOps.
end());
1555 while (BundledMI->isBundledWithPred()) {
1561 if (!
Reg.isVirtual() || !shouldAllocateRegister(Reg))
1565 DI = BundleVirtRegsMap.
find(Reg);
1566 assert(DI != BundleVirtRegsMap.
end() &&
"Unassigned virtual register");
1568 setPhysReg(
MI, MO, DI->second);
1579 RegUnitStates.assign(
TRI->getNumRegUnits(), regFree);
1580 assert(LiveVirtRegs.empty() &&
"Mapping not cleared from last block?");
1583 setPhysRegState(LiveReg.PhysReg, regPreAssigned);
1590 dbgs() <<
"\n>> " <<
MI <<
"Regs:";
1596 if (
MI.isDebugValue()) {
1597 handleDebugValue(
MI);
1601 allocateInstruction(
MI);
1605 if (
MI.getOpcode() == TargetOpcode::BUNDLE) {
1611 dbgs() <<
"Begin Regs:";
1616 LLVM_DEBUG(
dbgs() <<
"Loading live registers at begin of block.\n");
1623 NumCoalesced += Coalesced.size();
1625 for (
auto &UDBGPair : DanglingDbgValues) {
1629 if (!
DbgValue->hasDebugOperandForReg(UDBGPair.first))
1636 DanglingDbgValues.clear();
1642 LLVM_DEBUG(
dbgs() <<
"********** FAST REGISTER ALLOCATION **********\n"
1643 <<
"********** Function: " << MF.
getName() <<
'\n');
1649 MRI->freezeReservedRegs(MF);
1651 unsigned NumRegUnits =
TRI->getNumRegUnits();
1652 UsedInInstr.clear();
1653 UsedInInstr.setUniverse(NumRegUnits);
1654 PhysRegUses.clear();
1655 PhysRegUses.setUniverse(NumRegUnits);
1659 unsigned NumVirtRegs =
MRI->getNumVirtRegs();
1660 StackSlotForVirtReg.
resize(NumVirtRegs);
1661 LiveVirtRegs.setUniverse(NumVirtRegs);
1662 MayLiveAcrossBlocks.
clear();
1663 MayLiveAcrossBlocks.
resize(NumVirtRegs);
1667 allocateBasicBlock(
MBB);
1669 if (ClearVirtRegs) {
1672 MRI->clearVirtRegs();
1675 StackSlotForVirtReg.
clear();
1676 LiveDbgValueMap.
clear();
1681 return new RegAllocFast();
1685 bool ClearVirtRegs) {
1686 return new RegAllocFast(Ftor, ClearVirtRegs);
unsigned const MachineRegisterInfo * MRI
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
const HexagonInstrInfo * TII
This file implements an indexed map.
unsigned const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
static bool isCoalescable(const MachineInstr &MI)
static cl::opt< bool > IgnoreMissingDefs("rafast-ignore-missing-defs", cl::Hidden)
static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class recording the (high level) value of a variable.
Represent the analysis usage information of a pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool test(unsigned Idx) const
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void clear()
clear - Removes all bits from the bitvector.
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
Lightweight error class with error context and mandatory checking.
FunctionPass class - This class is used to implement most global optimizations.
void storeRegToStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register SrcReg, bool isKill, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const override
Store the specified register of the given register class to the specified stack frame index.
void loadRegFromStackSlot(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, Register DestReg, int FrameIndex, const TargetRegisterClass *RC, const TargetRegisterInfo *TRI, Register VReg) const override
Load the specified register of the given register class from the specified stack frame index.
void resize(typename StorageT::size_type s)
MCRegAliasIterator enumerates all registers aliasing Reg.
Wrapper class representing physical registers. Should be passed by value.
static constexpr unsigned NoRegister
iterator_range< liveout_iterator > liveouts() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
iterator_range< livein_iterator > liveins() const
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
int CreateSpillStackObject(uint64_t Size, Align Alignment)
Create a new statically sized stack object that represents a spill slot, returning a nonnegative iden...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual MachineFunctionProperties getClearedProperties() const
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual MachineFunctionProperties getSetProperties() const
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual MachineFunctionProperties getRequiredProperties() const
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
const MachineBasicBlock & front() const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
bool isDebugValueList() const
const MachineBasicBlock * getParent() const
bool isNonListDebugValue() const
MachineOperand & getDebugOperand(unsigned Index)
const MachineOperand & getOperand(unsigned i) const
MachineOperand class - Representation of each machine instruction operand.
void setSubReg(unsigned subReg)
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
void setIsRenamable(bool Val=true)
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
MachineBasicBlock * getMBB() const
void setIsDead(bool Val=true)
void setReg(Register Reg)
Change the register this operand corresponds to.
void setIsKill(bool Val=true)
bool isEarlyClobber() const
Register getReg() const
getReg - Returns the register number.
bool isInternalRead() const
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
bool isMBB() const
isMBB - Tests if this is a MO_MachineBasicBlock operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
ArrayRef< MCPhysReg > getOrder(const TargetRegisterClass *RC) const
getOrder - Returns the preferred allocation order for RC.
Wrapper class representing virtual and physical registers.
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
constexpr bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
typename DenseT::iterator iterator
typename DenseT::const_iterator const_iterator
StringRef - Represent a constant reference to a string, i.e.
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getID() const
Return the register class ID number.
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
bool hasSubClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a sub-class of or equal to this class.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
Iterator for intrusive lists based on ilist_node.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
@ Kill
The last use of a register.
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
FunctionPass * createFastRegisterAllocator()
FastRegisterAllocation Pass - This pass register allocates as fast as possible.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
void updateDbgValueForSpill(MachineInstr &Orig, int FrameIndex, Register Reg)
Update a DBG_VALUE whose value has been spilled to FrameIndex.
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
static bool allocateAllRegClasses(const TargetRegisterInfo &, const TargetRegisterClass &)
Default register class filter function for register allocation.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineInstr * buildDbgValueForSpill(MachineBasicBlock &BB, MachineBasicBlock::iterator I, const MachineInstr &Orig, int FrameIndex, Register SpillReg)
Clone a DBG_VALUE whose value has been spilled to FrameIndex.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
std::function< bool(const TargetRegisterInfo &TRI, const TargetRegisterClass &RC)> RegClassFilterFunc
This struct is a compact representation of a valid (non-zero power of two) alignment.
Pair of physical register and lane mask.
A MapVector that performs no allocations if smaller than a certain size.