Go to the documentation of this file.
49 #include <unordered_map>
64 for (
const auto &
I :
P.Obj) {
65 OS <<
' ' <<
printReg(
I.first, &
P.G.getTRI()) <<
'{';
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) {
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)))
185 Blocks[Block(
IA)].push_back(
IA.Id);
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) {
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;
241 auto &Bucket = Blocks[
MBB];
242 TmpInst.insert(TmpInst.end(), Bucket.rbegin(), Bucket.rend());
285 if (FullChain || IsPhi || !RRs.
hasCoverOf(QR))
295 RRs.
insert(
DA.Addr->getRegRef(DFG));
307 std::pair<NodeSet,bool>
310 return getAllReachingDefsRecImpl(RefRR, RefA, Visited, Defs, 0,
MaxRecNest);
313 std::pair<NodeSet,bool>
315 NodeSet &Visited,
const NodeSet &Defs,
unsigned Nest,
unsigned MaxNest) {
324 DefRRs.insert(
DA.Addr->getRegRef(DFG));
329 return { Defs,
true };
343 if (!Visited.insert(PA.
Id).second)
347 const auto &
T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
350 return {
T.first,
false };
351 Result.insert(
T.first.begin(),
T.first.end());
368 return T.Id == FindId;
382 if (!PRI.
alias(R.Addr->getRegRef(DFG), RefRR))
403 if ((
N =
N->getIDom()))
437 U = UA.Addr->getSibling();
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));
496 PhiDefs.insert(R.Id);
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) {
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)
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});
844 SeenUses.insert(
T.Id);
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);
860 LiveMap[&MF.front()].insert(DFG.
getLiveIns());
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())
920 LV.set(
S.getSubReg());
922 }
while (
S.isValid());
927 CopyLiveIns(
B, LiveIn);
928 for (
auto *
SI :
B->successors())
929 CopyLiveIns(
SI, Live);
932 if (
MI.isDebugInstr())
936 for (
auto &
Op :
MI.operands()) {
941 if (!
Op.isReg() || !
Op.isDef() ||
Op.isImplicit())
949 for (
auto &
Op :
MI.operands()) {
950 if (!
Op.isReg() || !
Op.isUse() ||
Op.isUndef())
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) {
1067 LRef.Mask =
OR.second;
1075 if (RRs.insert(
DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
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)
1166 void 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);
MachineFunction & getMF() const
rr_iterator rr_end() const
NodeId getPredecessor() const
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
NodeList getRelatedRefs(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
static bool IsPreservingDef(const NodeAddr< DefNode * > DA)
NodeList members_if(Predicate P, const DataFlowGraph &G) const
RegisterAggr & insert(RegisterRef RR)
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
NodeId getReachedUse() const
std::unordered_map< RegisterId, NodeRefSet > RefMap
size_type size() const
Determine the number of elements in the SetVector.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
iterator find(MachineBasicBlock *B)
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...
SmallPtrSet< MachineInstr *, 2 > Uses
uint16_t getFlags() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
NodeAddr< FuncNode * > getFunc() const
iterator begin()
Get an iterator to the beginning of the SetVector.
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
RegisterRef getRegRef(const DataFlowGraph &G) const
(vector float) vec_cmpeq(*A, *B) C
bool alias(RegisterRef RA, RegisterRef RB) const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Pair of physical register and lane mask.
This class implements an extremely fast bulk output stream that can only output to a stream.
static bool IsDef(const NodeAddr< NodeBase * > BA)
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
bool hasCoverOf(RegisterRef RR) const
void sort(IteratorTy Start, IteratorTy End)
static bool IsCode(const NodeAddr< NodeBase * > BA)
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
NodeAddr< T > addr(NodeId N) const
static bool IsRef(const NodeAddr< NodeBase * > BA)
Representation of each machine instruction.
bool hasAliasOf(RegisterRef RR) const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
NodeList members(const DataFlowGraph &G) const
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
initializer< Ty > init(const Ty &Val)
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
bool insert(const value_type &X)
Insert a new element into the SetVector.
rr_iterator rr_begin() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Print(const T &, const DataFlowGraph &) -> Print< T >
self_iterator getIterator()
static bool IsUse(const NodeAddr< NodeBase * > BA)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
const MachineBasicBlock * getParent() const
Base class for the actual dominator tree node.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
const RegisterAggr & getLiveIns() const
Wrapper class representing virtual and physical registers.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
RegisterRef intersectWith(RegisterRef RR) const
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
NodeId getReachedDef() const
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
MCSubRegIterator enumerates all sub-registers of Reg.
NodeId getReachingDef() const
iterator end()
Get an iterator to the end of the SetVector.
RegisterRef clearIn(RegisterRef RR) const
std::set< NodeId > NodeSet
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
MachineBasicBlock * getCode() const
static cl::opt< unsigned > MaxRecNest("rdf-liveness-max-rec", cl::init(25), cl::Hidden, cl::desc("Maximum recursion level"))
auto reverse(ContainerTy &&C)
const char LLVMTargetMachineRef TM
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
std::unordered_set< NodeRef > NodeRefSet
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
A vector that has set insertion semantics.
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.
NodeAddr< BlockNode * > findBlock(MachineBasicBlock *BB) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
MCRegAliasIterator enumerates all registers aliasing Reg.
A Use represents the edge between a Value definition and its users.
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)