49#include <unordered_map>
64 for (
const auto &
I :
P.Obj) {
66 for (
auto J =
I.second.begin(),
E =
I.second.end(); J !=
E; ) {
128 if (
NodeId RD = SNA.Addr->getReachingDef())
142 for (
unsigned i = 0; i < DefQ.
size(); ++i) {
168 return BA.
Addr->getCode();
175 std::map<NodeId, NodeAddr<InstrNode*>> Owners;
176 std::map<MachineBasicBlock*, SmallVector<NodeId,32>>
Blocks;
180 if (!IsPhi && !PRI.
alias(RefRR, TA.Addr->getRegRef(DFG)))
195 if (StmtA && StmtB) {
199 auto FA = OrdMap.
find(InA);
200 if (FA != OrdMap.
end())
201 return FA->second < OrdMap.
find(InB)->second;
203 for (
auto It = BB->
begin(),
E = BB->
end(); It !=
E; ++It) {
212 if (!StmtA && !StmtB) {
223 OrdMap.
insert({&In, ++Pos});
227 std::vector<MachineBasicBlock*> TmpBB;
228 for (
auto &Bucket :
Blocks) {
229 TmpBB.push_back(Bucket.first);
230 if (Bucket.second.size() > 2)
231 GetOrder(*Bucket.first);
239 std::vector<NodeId> TmpInst;
242 TmpInst.insert(TmpInst.end(), Bucket.rbegin(), Bucket.rend());
285 if (FullChain || IsPhi || !RRs.
hasCoverOf(QR))
295 RRs.
insert(DA.Addr->getRegRef(DFG));
307std::pair<NodeSet,bool>
310 return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0,
MaxRecNest);
313std::pair<NodeSet,bool>
315 NodeSet &Visited,
const NodeSet &Defs,
unsigned Nest,
unsigned MaxNest) {
324 DefRRs.insert(DA.Addr->getRegRef(DFG));
329 return { Defs,
true };
347 const auto &
T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
350 return {
T.first,
false };
351 Result.insert(
T.first.begin(),
T.first.end());
366 auto B = std::find_if(Ins.rbegin(),
E,
368 return T.Id == FindId;
382 if (!PRI.
alias(R.Addr->getRegRef(DFG), RefRR))
403 if ((
N =
N->getIDom()))
409 Ins = BA.
Addr->members(DFG);
437 U = UA.Addr->getSibling();
441 for (
NodeId D = DefA.
Addr->getReachedDef(), NextD;
D != 0;
D = NextD) {
443 NextD = DA.Addr->getSibling();
458 Uses.insert(
T.begin(),
T.end());
475 std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp;
476 std::vector<NodeId> PhiUQ;
477 std::unordered_map<NodeId,RegisterAggr> PhiDRs;
483 RefMap &RealUses = RealUseMap[PhiA.Id];
484 NodeList PhiRefs = PhiA.Addr->members(DFG);
494 DRs.
insert(R.Addr->getRegRef(DFG));
498 PhiDRs.insert(std::make_pair(PhiA.Id, DRs));
505 for (
unsigned i = 0; i < DefQ.
size(); ++i) {
516 RealUses[R.Reg].insert({
A.Id,R.Mask});
518 UN =
A.Addr->getSibling();
523 NodeId DN = DA.Addr->getReachedDef();
534 DN =
A.Addr->getSibling();
549 for (
auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) {
556 for (std::pair<NodeId,LaneBitmask>
I :
Uses) {
564 if (PhiDefs.
count(DA.Id))
566 Covered.
insert(DA.Addr->getRegRef(DFG));
572 UI->second.insert({
I.first, S.
Mask});
575 UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI);
580 if (!RealUses.empty())
581 PhiUQ.push_back(PhiA.Id);
590 for (
auto I : PhiRefs) {
594 if (PUA.
Addr->getReachingDef() == 0)
603 NodeId RP =
D.Addr->getOwner(DFG).Id;
604 std::map<NodeId,RegisterAggr> &M = PhiUp[PUA.
Id];
607 M.insert(std::make_pair(RP, DefRRs));
609 F->second.insert(DefRRs);
611 DefRRs.
insert(
D.Addr->getRegRef(DFG));
620 dbgs() <<
"Phi-up-to-phi map with intervening defs:\n";
621 for (
auto I : PhiUp) {
622 dbgs() <<
"phi " <<
Print(
I.first, DFG) <<
" -> {";
623 for (
auto R :
I.second)
655 using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
656 std::unordered_map<RegisterAggr, SubMap> Subs;
660 auto F = SM.find(RR);
669 for (
unsigned i = 0; i < PhiUQ.size(); ++i) {
675 std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
677 for (
const std::pair<const NodeId, RegisterAggr> &
P : PUM) {
678 bool Changed =
false;
686 SubMap &SM = Subs[MidDefs];
693 for (
const std::pair<const RegisterId, NodeRefSet> &
T : RUM) {
702 for (std::pair<NodeId,LaneBitmask> V :
T.second) {
708 Changed |= RS.insert({V.first,SS.Mask}).second;
714 PhiUQ.push_back(
P.first);
720 dbgs() <<
"Real use map:\n";
721 for (
auto I : RealUseMap) {
731 dbgs() <<
" -> " <<
Print(
I.second, DFG) <<
'\n';
744 NBMap.insert(std::make_pair(
RA.Id, BB));
745 NBMap.insert(std::make_pair(IA.Id, BB));
754 auto F1 = MDF.
find(&
B);
758 for (
unsigned i = 0; i < IDFB.
size(); ++i) {
759 auto F2 = MDF.
find(IDFB[i]);
761 IDFB.
insert(F2->second.begin(), F2->second.end());
765 IDF[&
B].insert(IDFB.
begin(), IDFB.
end());
769 for (
auto *S :
I.second)
770 IIDF[S].insert(
I.first);
782 for (
const RefMap::value_type &S : RealUseMap[
P.Id])
783 LON[S.first].insert(S.second.begin(), S.second.end());
787 dbgs() <<
"Phi live-on-entry map:\n";
788 for (
auto &
I : PhiLON)
789 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
790 <<
Print(
I.second, DFG) <<
'\n';
805 if (!SeenUses.
insert(U.Id).second)
808 if (PUA.
Addr->getReachingDef() == 0)
823 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
825 for (
const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
827 for (std::pair<NodeId,LaneBitmask>
P : RS.second) {
836 TA.insert(
D.Addr->getRegRef(DFG)).intersect(S);
838 LOX[S.
Reg].insert({
D.Id,
TM});
850 dbgs() <<
"Phi live-on-exit map:\n";
851 for (
auto &
I : PhiLOX)
852 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
853 <<
Print(
I.second, DFG) <<
'\n';
857 traverse(&MF.
front(), LiveIn);
865 std::vector<RegisterRef> LV;
867 LV.push_back(
RegisterRef(LI.PhysReg, LI.LaneMask));
880 dbgs() <<
"\tcomp = {";
890 for (
auto &
B : DFG.
getMF()) {
892 std::vector<unsigned>
T;
894 T.push_back(LI.PhysReg);
905 for (
auto &
B : DFG.
getMF())
911 for (
auto I :
B->liveins()) {
919 if ((M &
I.LaneMask).any())
927 CopyLiveIns(
B, LiveIn);
928 for (
auto *
SI :
B->successors())
932 if (
MI.isDebugInstr())
936 for (
auto &Op :
MI.all_defs()) {
949 for (
auto &Op :
MI.all_uses()) {
973 auto F = NBMap.find(RN);
974 if (
F != NBMap.end())
1005 for (
auto *
I : *
N) {
1011 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1016 <<
" after recursion into: {";
1018 dbgs() <<
' ' <<
I->getBlock()->getNumber();
1020 dbgs() <<
" LiveIn: " <<
Print(LiveIn, DFG) <<
'\n';
1021 dbgs() <<
" Local: " <<
Print(LiveMap[
B], DFG) <<
'\n';
1027 LiveIn[S.first].insert(S.second.begin(), S.second.end());
1030 dbgs() <<
"after LOX\n";
1031 dbgs() <<
" LiveIn: " <<
Print(LiveIn, DFG) <<
'\n';
1032 dbgs() <<
" Local: " <<
Print(LiveMap[
B], DFG) <<
'\n';
1042 RefMap LiveInCopy = LiveIn;
1045 for (
const std::pair<const RegisterId, NodeRefSet> &LE : LiveInCopy) {
1054 if (
B != BA.
Addr->getCode()) {
1067 LRef.Mask =
OR.second;
1075 if (RRs.insert(
DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1089 if (BTA.
Addr->getCode() !=
B) {
1096 NewDefs.insert({
TA.Id,
T.Mask});
1103 RRs.insert(
TA.Addr->getRegRef(DFG));
1105 if (RRs.hasCoverOf(LRef))
1114 dbgs() <<
"after defs in block\n";
1115 dbgs() <<
" LiveIn: " <<
Print(LiveIn, DFG) <<
'\n';
1116 dbgs() <<
" Local: " <<
Print(LiveMap[
B], DFG) <<
'\n';
1120 for (
auto I : DFG.
getFunc().Addr->findBlock(
B, DFG).Addr->members(DFG)) {
1129 if (getBlockWithRef(
D.Id) !=
B)
1130 LiveIn[RR.
Reg].insert({
D.Id,RR.
Mask});
1135 dbgs() <<
"after uses in block\n";
1136 dbgs() <<
" LiveIn: " <<
Print(LiveIn, DFG) <<
'\n';
1137 dbgs() <<
" Local: " <<
Print(LiveMap[
B], DFG) <<
'\n';
1144 for (
auto &R : LON) {
1146 for (
auto P :
R.second)
1152 dbgs() <<
"after phi uses in block\n";
1153 dbgs() <<
" LiveIn: " <<
Print(LiveIn, DFG) <<
'\n';
1154 dbgs() <<
" Local: " <<
Print(Local, DFG) <<
'\n';
1157 for (
auto *
C : IIDF[
B]) {
1159 for (
const std::pair<const RegisterId, NodeRefSet> &S : LiveIn)
1160 for (
auto R : S.second)
1166void Liveness::emptify(RefMap &M) {
1167 for (
auto I =
M.begin(),
E =
M.end();
I !=
E; )
1168 I =
I->second.empty() ?
M.erase(
I) : std::next(
I);
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Looks at all the uses of the given value Returns the Liveness deduced from the uses of this value Adds all uses that cause the result to be MaybeLive to MaybeLiveRetUses If the result is Live
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
Rewrite Partial Register Uses
A common definition of LaneBitmask for use in TableGen and CodeGen.
const char LLVMTargetMachineRef TM
static cl::opt< unsigned > MaxRecNest("rdf-liveness-max-rec", cl::init(25), cl::Hidden, cl::desc("Maximum recursion level"))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallSet class.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Base class for the actual dominator tree node.
MCRegAliasIterator enumerates all registers aliasing Reg.
iterator_range< mc_subreg_iterator > subregs_inclusive(MCRegister Reg) const
Return an iterator range over all sub-registers of Reg, including Reg.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
bool isValid() const
Returns true if this iterator is not yet at the end.
unsigned getSubRegIndex() const
Returns sub-register index of the current sub-register.
MCRegister getSubReg() const
Returns current sub-register.
iterator find(MachineBasicBlock *B)
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
const MachineBasicBlock & front() const
Representation of each machine instruction.
const MachineBasicBlock * getParent() const
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
unsigned count(SUnit *SU) const
Wrapper class representing virtual and physical registers.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
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 is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
A Use represents the edge between a Value definition and its users.
self_iterator getIterator()
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
std::set< NodeId > NodeSet
This is an optimization pass for GlobalISel generic memory operations.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
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.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
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.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Pair of physical register and lane mask.
const RegisterAggr & getLiveIns() const
NodeAddr< FuncNode * > getFunc() const
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
static bool IsPreservingDef(const NodeAddr< DefNode * > DA)
static bool IsRef(const NodeAddr< NodeBase * > BA)
MachineFunction & getMF() const
static bool IsUse(const NodeAddr< NodeBase * > BA)
static bool IsDef(const NodeAddr< NodeBase * > BA)
static bool IsCode(const NodeAddr< NodeBase * > BA)
NodeList getRelatedRefs(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
NodeAddr< T > addr(NodeId N) const
std::unordered_set< NodeRef > NodeRefSet
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
std::unordered_map< RegisterId, NodeRefSet > RefMap
NodeAddr< RefNode * > getNearestAliasedRef(RegisterRef RefRR, NodeAddr< InstrNode * > IA)
Find the nearest ref node aliased to RefRR, going upwards in the data flow, starting from the instruc...
bool alias(RegisterRef RA, RegisterRef RB) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
rr_iterator rr_end() const
RegisterAggr & insert(RegisterRef RR)
bool hasAliasOf(RegisterRef RR) const
bool hasCoverOf(RegisterRef RR) const
RegisterRef clearIn(RegisterRef RR) const
RegisterRef intersectWith(RegisterRef RR) const
rr_iterator rr_begin() const
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)