14#define DEBUG_TYPE "hexagon_live_vars"
32 "Hexagon Live Variable Analysis",
false,
false)
37class HexagonLiveVariablesImpl {
141 unsigned getNumRegs()
const {
return NumRegs; }
145 void clearDistanceMap() { DistanceMap.
clear(); }
160 HLV(
std::make_unique<HexagonLiveVariablesImpl>()) {
178 HLV->runOnMachineFunction(MF, MDT, MPDT);
182 return HLV->updateLocalLiveness(Fn);
187 HLV->constructUseDef(
MBB);
188 return HLV->updateLocalLiveness(
MBB, updateBundle);
194 assert(MIDelta->getParent() == To);
196 return HLV->incrementalUpdate(MIDelta, From, To);
205 HLV->addNewMI(
MI,
MBB);
209 HLV->constructUseDef(
MBB);
216 HLVComplete = !HLV->runOnMachineFunction(Fn, MDT, MPDT);
221 unsigned Reg)
const {
223 auto It = HLV->MBBLiveOuts.find(
MBB);
224 if (It == HLV->MBBLiveOuts.end())
226 if (Reg >= It->second.size())
228 return It->second[Reg];
234 auto It = HLV->MBBLiveOuts.find(
MBB);
235 if (It == HLV->MBBLiveOuts.end())
251 if (MIBegin == MIEnd)
256 if (MII->isBundle() || MII->isDebugInstr())
258 if (ExceptionsList && ExceptionsList->
contains(&*MII))
260 auto It = HLV->MIUseDefs.find(&*MII);
261 assert(It != HLV->MIUseDefs.end());
263 if (It->second.first[*AI]) {
267 }
while (MII != MIBegin);
280 if (MIBegin == MIEnd)
285 if (MII->isBundle() || MII->isDebugInstr())
287 auto It = HLV->MIUseDefs.find(&*MII);
288 assert(It != HLV->MIUseDefs.end());
290 if (It->second.second[*AI]) {
294 }
while (MII != MIBegin);
302 assert(
MI &&
"Invalid machine instruction");
303 assert(
MBB &&
"Invalid machine basic block");
304 auto It = HLV->MIUseDefs.find(
MI);
305 assert(It != HLV->MIUseDefs.end() &&
"Missing MI use/def information");
308 lit !=
MBB->livein_end(); ++lit) {
315 return MBBLiveIns.
anyCommon(It->second.second);
324 unsigned BufferPerMBB)
const {
325 assert(HLV->DistanceMap.find(From) != HLV->DistanceMap.end());
326 assert(HLV->DistanceMap.find(To) != HLV->DistanceMap.end());
327 unsigned FromSize = HLV->DistanceMap[From];
332 unsigned S = BufferPerMBB;
333 bool ToFirst =
false;
338 else if (
MBB == To) {
351 S += HLV->DistanceMap[
MBB] + BufferPerMBB;
355 S += FromSize + HLV->DistanceMap[To] + 2 * BufferPerMBB;
360 HLV->clearDistanceMap();
361 HLV->generateDistanceMap(Fn);
367bool HexagonLiveVariablesImpl::runOnMachineFunction(
375 TRI = ST.getRegisterInfo();
376 QII = ST.getInstrInfo();
378 NumRegs =
TRI->getNumRegs();
384 LLVM_DEBUG(
dbgs() <<
"\nNumber of registers in Hexagon is:" << NumRegs);
386 PhysRegDef.resize(NumRegs);
387 PhysRegUse.resize(NumRegs);
391 constructUseDef(&*
MBBI);
393 updateGlobalLiveness(Fn);
398 std::fill(PhysRegDef.begin(), PhysRegDef.end(), (
MachineInstr *)0);
399 std::fill(PhysRegUse.begin(), PhysRegUse.end(), (
MachineInstr *)0);
402 std::pair<BitVector, BitVector> &UseDef = MBBUseDefs[
MBB];
410 Defs.
resize(NumRegs,
false);
411 LiveOuts.
resize(NumRegs,
false);
418 unsigned MBBInsSize = 0;
423 MBBInsSize += QII->getSize(*
MI);
425 if (
MI->isBundle() ||
MI->isDebugInstr())
430 MIUseDef.first.resize(NumRegs);
431 MIUseDef.second.resize(NumRegs);
432 MIUseDef.first.reset();
433 MIUseDef.second.reset();
438 unsigned NumOperandsToProcess =
MI->getNumOperands();
439 for (
unsigned i = 0; i != NumOperandsToProcess; ++i) {
443 if (!QII->isPredicated(*
MI))
454 MIUseDef.first.set(
Reg);
457 if (!QII->isPredicated(*
MI) && !
MI->isKill()) {
463 MIUseDef.second.set(
Reg);
467 for (
unsigned i = 0, e = UseRegs.
size(); i != e; ++i)
468 handlePhysRegUse(UseRegs[i],
MI,
Uses);
470 for (
unsigned i = 0, e = DefRegs.
size(); i != e; ++i)
471 handlePhysRegDef(DefRegs[i],
MI, Defs);
473 DistanceMap[
MBB] = MBBInsSize;
476void HexagonLiveVariablesImpl::handlePhysRegUse(
MachineOperand *MO,
484 if (PhysRegDef[*SupI])
489 bool subRegDefined =
false;
492 if (PhysRegDef[*SubI])
493 subRegDefined =
true;
499 if (undefSubRegs.
empty()) {
500 if (!subRegDefined) {
504 PhysRegUse[*SubI] =
MI;
511 for (
unsigned i = 0; i < undefSubRegs.
size(); ++i) {
513 PhysRegUse[undefSubRegs[i]] =
MI;
514 Uses.set(undefSubRegs[i]);
519void HexagonLiveVariablesImpl::handlePhysRegDef(
MachineOperand *MO,
522 auto SetRegDef = [&](
unsigned Reg) ->
void {
523 PhysRegDef[
Reg] =
MI;
525 if (PhysRegUse[*AI]) {
537 for (
unsigned R = 1, NR =
TRI->getNumRegs(); R != NR; ++R)
560 while (!WorkStack.
empty()) {
562 BlockState &WState = State[W->getNumber()];
567 if (W->succ_empty() || WState.SuccQueued) {
570 WState.SuccQueued =
true;
574 WState.SuccQueued =
true;
586 dbgs() <<
"gatherBlocksDF: {";
589 B != BE; ++
B) { dbgs() <<
" BB#" << (*B)->getNumber(); }
dbgs()
593bool HexagonLiveVariablesImpl::updateGlobalLiveness(
MachineFunction &Fn) {
598 for (++
I;
I !=
E; ++
I) {
599 std::vector<MachineBasicBlock::RegisterMaskPair> OldLiveIn(
600 I->livein_begin(),
I->livein_end());
601 for (
unsigned i = 0; i < OldLiveIn.size(); ++i)
602 I->removeLiveIn(OldLiveIn[i].PhysReg);
613 B = BlocksDepthFirst.begin(),
614 BE = BlocksDepthFirst.end();
616 Repeat |= updateGlobalLiveness(*
B, Defs, LiveIns);
621 Changed |= updateLocalLiveness(Fn);
627 assert(
X &&
"Invalid start block");
628 assert(
Y &&
"Invalid end block");
635 BlocksDepthFirst.end();
637 for (
B = BlocksDepthFirst.begin(); (
B != BE); ++
B) {
648 Repeat |= updateGlobalLiveness(*
B, Defs, LiveIns);
650 B = BlocksDepthFirst.begin();
665 auto LiveOutIt = MBBLiveOuts.find(
MBB);
666 if (LiveOutIt == MBBLiveOuts.end())
667 LiveOutIt = MBBLiveOuts.insert({
MBB,
BitVector(NumRegs)}).first;
676 if (!LiveOuts[(*LI).PhysReg]) {
678 LiveOuts.
set((*LI).PhysReg);
685 Changed |= updateLiveIns(
MBB, LiveIns, LiveOuts);
696 const std::pair<BitVector, BitVector> &UseDefs = MBBUseDefs[
MBB];
700 LiveIns.
reset(UseDefs.second);
701 LiveIns |= UseDefs.first;
720 unsigned R = (*I).PhysReg;
730bool HexagonLiveVariablesImpl::updateLocalLiveness(
MachineFunction &Fn) {
733 updateLocalLiveness(&*
B,
false);
743 updateLiveOuts(
MBB, LiveOut);
750 MII != MIREnd; ++MII) {
753 if (
MI->isBundle()) {
758 if (
MI->isDebugInstr())
762 for (
unsigned i = 0; i <
MI->getNumOperands(); ++i) {
768 if (!QII->isPredicated(*
MI) && !
MI->isKill()) {
775 if (!QII->isPredicated(*
MI))
781 auto RemoveDef = [&](
unsigned Reg,
bool Implicit) ->
void {
787 for (
auto *UseOp : UseRegs)
788 if (UseOp->isImplicit() &&
TRI->regsOverlap(*
SI, UseOp->getReg()))
789 Used.set(UseOp->getReg());
793 for (
unsigned i = 0; i < DefRegs.
size(); ++i) {
798 for (
unsigned R = 1, NR =
TRI->getNumRegs(); R != NR; ++R)
804 for (
unsigned i = UseRegs.
size(); i > 0;) {
806 unsigned UseReg = UseRegs[i]->getReg();
813 if (Killed && !UseRegs[i]->
isDebug())
814 UseRegs[i]->setIsKill(
true);
819 MII != BundleHeads.
end(); ++MII) {
821 assert(
MI &&
"Invalid bundle head");
822 assert(
MI->isBundle() &&
"Expected a bundle head instruction");
823 assert(
MI->getParent() ==
MBB &&
"Bundle head not in expected block");
826 for (++BS; BS != BE; ++BS)
828 BS->unbundleFromPred();
830 BS =
MI->getIterator();
832 bool memShufDisabled = QII->getBundleNoShuf(*
MI);
833 MI->eraseFromParent();
837 QII->setBundleNoShuf(BundleMII);
843bool HexagonLiveVariablesImpl::incrementalUpdate(MICInstIterType MIDelta,
849 constructUseDef(From);
854 updateGlobalLiveness(From, To);
856 updateLocalLiveness(From,
true);
857 updateLocalLiveness(To,
true);
862 if (MIUseDef == MIUseDefs.end())
864 const BitVector &Defs = MIUseDef->second.second;
878 constructUseDef(
MBB);
880 updateGlobalLiveness(
MBB,
MBB);
887 constructUseDef(
MBB);
888 updateGlobalLiveness(
MBB,
MBB);
891void HexagonLiveVariablesImpl::generateDistanceMap(
const MachineFunction &Fn) {
892 assert(DistanceMap.empty() &&
"DistanceMap not empty, first clear!");
896 unsigned MBBInsSize = 0;
901 MBBInsSize += QII->getSize(*
MI);
903 DistanceMap[
MBB] = MBBInsSize;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator MBBI
Function Alias Analysis false
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static Register UseReg(const MachineOperand &MO)
static void UpdateBundle(MachineInstr *BundleHead)
static void gatherBlocksDF(MachineFunction &Fn, SmallVectorImpl< MachineBasicBlock * > *Blocks)
Register const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
MachineRegisterInfo & MRI
Remove Loads Into Fake Uses
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
LLVM_ABI void setPreservesCFG()
This function should be called by the pass, iff they do not:
BitVector & reset()
Reset all bits in the bitvector.
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
BitVector & set()
Set all bits in the bitvector.
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT, true > const_iterator
MachineBasicBlock::const_instr_iterator MICInstIterType
void recalculate(MachineFunction &MF)
recalculate - recalculates the liveness from scratch.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
void constructUseDef(MachineBasicBlock *MBB)
Constructs use-defs of MBB by analyzing each MachineOperand.
unsigned getDistanceBetween(const MachineBasicBlock *From, const MachineBasicBlock *To, unsigned BufferPerMBB=HEXAGON_INSTR_SIZE) const
Returns the linear distance (as per layout) of MI from the Function.
bool isUsedWithin(MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg, MICInstIterType &Use, SmallPtrSet< MachineInstr *, 2 > *ExceptionsList=nullptr) const
bool incrementalUpdate(MICInstIterType MIDelta, MachineBasicBlock *From, MachineBasicBlock *To)
incrementalUpdate - update the liveness when MIDelta is moved from From to To.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool updateLocalLiveness(MachineFunction &Fn)
updateLocalLiveness - update only kill flags of operands.
const BitVector & getLiveOuts(const MachineBasicBlock *MBB) const
bool isDefLiveIn(const MachineInstr *MI, const MachineBasicBlock *MBB) const
MIUseDef_t & getMIUseDefs()
void regenerateDistanceMap(const MachineFunction &Fn)
MBBUseDef_t & getMBBUseDefs()
void addNewMBB(MachineBasicBlock *MBB)
addNewMBB - inform the LiveVariable Analysis that new MBB has been added.
bool isLiveOut(const MachineBasicBlock *MBB, unsigned Reg) const
bool isDefinedWithin(MICInstIterType MIBegin, MICInstIterType MIEnd, unsigned Reg, MICInstIterType &Def) const
void addNewMI(MachineInstr *MI, MachineBasicBlock *MBB)
MCRegAliasIterator enumerates all registers aliasing Reg.
MCSubRegIterator enumerates all sub-registers of Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
MCSuperRegIterator enumerates all super-registers of Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
livein_iterator livein_end() const
instr_iterator instr_begin()
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
succ_iterator succ_begin()
bool livein_empty() const
LLVM_ABI void removeLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll())
Remove the specified register from the live in set.
LiveInVector::const_iterator livein_iterator
LLVM_ABI livein_iterator livein_begin() const
SmallVectorImpl< MachineBasicBlock * >::iterator succ_iterator
reverse_instr_iterator instr_rend()
Instructions::iterator instr_iterator
instr_iterator instr_end()
Instructions::const_iterator const_instr_iterator
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.
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Instructions::reverse_iterator reverse_instr_iterator
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass(char &ID)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
BasicBlockListType::iterator iterator
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
BasicBlockListType::const_iterator const_iterator
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsDead(bool Val=true)
void setIsKill(bool Val=true)
Register getReg() const
getReg - Returns the register number.
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
MachinePostDominatorTree - an analysis pass wrapper for DominatorTree used to compute the post-domina...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
bool isAllocatable(MCRegister PhysReg) const
isAllocatable - Returns true when PhysReg belongs to an allocatable register class and it hasn't been...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void reserve(size_type N)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A Use represents the edge between a Value definition and its users.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI void finalizeBundle(MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
finalizeBundle - Finalize a machine instruction bundle which includes a sequence of instructions star...
@ Implicit
Not emitted register (e.g. carry, or temporary result).
char & HexagonLiveVariablesID
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
MachineBasicBlock::instr_iterator getBundleEnd(MachineBasicBlock::instr_iterator I)
Returns an iterator pointing beyond the bundle containing I.
DenseMap< MachineBasicBlock *, UseDef_t > MBBUseDef_t
void initializeHexagonLiveVariablesPass(PassRegistry &)
std::pair< BitVector, BitVector > UseDef_t
LLVM_ABI 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.
DenseMap< const MachineInstr *, UseDef_t > MIUseDef_t
Implement std::hash so that hash_code can be used in STL containers.