Go to the documentation of this file.
49 #include <unordered_map>
64 for (
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.count(PA.
Id))
345 Visited.insert(PA.
Id);
348 const auto &
T = getAllReachingDefsRecImpl(RefRR, U, Visited, TmpDefs,
351 return {
T.first,
false };
352 Result.insert(
T.first.begin(),
T.first.end());
369 return T.Id == FindId;
383 if (!PRI.
alias(R.Addr->getRegRef(DFG), RefRR))
404 if ((
N =
N->getIDom()))
438 U = UA.Addr->getSibling();
444 NextD =
DA.Addr->getSibling();
459 Uses.insert(
T.begin(),
T.end());
476 std::map<NodeId,std::map<NodeId,RegisterAggr>> PhiUp;
477 std::vector<NodeId> PhiUQ;
478 std::unordered_map<NodeId,RegisterAggr> PhiDRs;
484 RefMap &RealUses = RealUseMap[PhiA.Id];
485 NodeList PhiRefs = PhiA.Addr->members(DFG);
495 DRs.
insert(R.Addr->getRegRef(DFG));
497 PhiDefs.insert(R.Id);
499 PhiDRs.insert(std::make_pair(PhiA.Id, DRs));
506 for (
unsigned i = 0;
i < DefQ.
size(); ++
i) {
517 RealUses[R.Reg].insert({A.Id,R.Mask});
519 UN = A.Addr->getSibling();
524 NodeId DN =
DA.Addr->getReachedDef();
535 DN = A.Addr->getSibling();
550 for (
auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) {
557 for (std::pair<NodeId,LaneBitmask>
I :
Uses) {
565 if (PhiDefs.count(
DA.Id))
567 Covered.
insert(
DA.Addr->getRegRef(DFG));
573 UI->second.insert({
I.first,
S.Mask});
576 UI = UI->second.empty() ? RealUses.erase(UI) : std::next(UI);
581 if (!RealUses.empty())
582 PhiUQ.push_back(PhiA.Id);
591 for (
auto I : PhiRefs) {
605 std::map<NodeId,RegisterAggr> &
M = PhiUp[PUA.
Id];
608 M.insert(std::make_pair(
RP, DefRRs));
610 F->second.insert(DefRRs);
612 DefRRs.
insert(
D.Addr->getRegRef(DFG));
621 dbgs() <<
"Phi-up-to-phi map with intervening defs:\n";
622 for (
auto I : PhiUp) {
624 for (
auto R :
I.second)
657 using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
658 std::unordered_map<RegisterAggr, SubMap> Subs;
662 auto F = SM.find(RR);
671 for (
unsigned i = 0;
i < PhiUQ.size(); ++
i) {
677 std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
679 for (
const std::pair<const NodeId, RegisterAggr> &
P : PUM) {
680 bool Changed =
false;
688 SubMap &SM = Subs[MidDefs];
695 for (
const std::pair<const RegisterId, NodeRefSet> &
T : RUM) {
704 for (std::pair<NodeId,LaneBitmask> V :
T.second) {
710 Changed |= RS.insert({V.first,
SS.Mask}).second;
716 PhiUQ.push_back(
P.first);
722 dbgs() <<
"Real use map:\n";
723 for (
auto I : RealUseMap) {
746 NBMap.insert(std::make_pair(
RA.Id,
BB));
747 NBMap.insert(std::make_pair(IA.Id,
BB));
756 auto F1 = MDF.
find(&
B);
760 for (
unsigned i = 0;
i < IDFB.
size(); ++
i) {
761 auto F2 = MDF.
find(IDFB[
i]);
763 IDFB.
insert(F2->second.begin(), F2->second.end());
767 IDF[&
B].insert(IDFB.
begin(), IDFB.
end());
771 for (
auto S :
I.second)
772 IIDF[
S].insert(
I.first);
784 for (
const RefMap::value_type &
S : RealUseMap[
P.Id])
785 LON[
S.first].insert(
S.second.begin(),
S.second.end());
789 dbgs() <<
"Phi live-on-entry map:\n";
790 for (
auto &
I : PhiLON)
791 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
807 if (!SeenUses.insert(U.Id).second)
825 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
827 for (
const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
829 for (std::pair<NodeId,LaneBitmask>
P : RS.second) {
838 TA.insert(
D.Addr->getRegRef(DFG)).intersect(
S);
840 LOX[
S.Reg].insert({
D.Id,
TM});
846 SeenUses.insert(
T.Id);
852 dbgs() <<
"Phi live-on-exit map:\n";
853 for (
auto &
I : PhiLOX)
854 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
859 traverse(&MF.front(), LiveIn);
862 LiveMap[&MF.front()].insert(DFG.
getLiveIns());
867 std::vector<RegisterRef> LV;
869 LV.push_back(
RegisterRef(LI.PhysReg, LI.LaneMask));
882 dbgs() <<
"\tcomp = {";
892 for (
auto &
B : DFG.
getMF()) {
894 std::vector<unsigned>
T;
896 T.push_back(LI.PhysReg);
907 for (
auto &
B : DFG.
getMF())
913 for (
auto I :
B->liveins()) {
921 if ((
M &
I.LaneMask).any())
922 LV.set(
S.getSubReg());
924 }
while (
S.isValid());
929 CopyLiveIns(
B, LiveIn);
930 for (
auto SI :
B->successors())
931 CopyLiveIns(
SI, Live);
934 if (
MI.isDebugInstr())
938 for (
auto &
Op :
MI.operands()) {
943 if (!
Op.isReg() || !
Op.isDef() ||
Op.isImplicit())
951 for (
auto &
Op :
MI.operands()) {
952 if (!
Op.isReg() || !
Op.isUse() ||
Op.isUndef())
975 auto F = NBMap.find(
RN);
976 if (
F != NBMap.end())
1013 LiveIn[
S.first].insert(
S.second.begin(),
S.second.end());
1018 <<
" after recursion into: {";
1020 dbgs() <<
' ' <<
I->getBlock()->getNumber();
1029 LiveIn[
S.first].insert(
S.second.begin(),
S.second.end());
1032 dbgs() <<
"after LOX\n";
1044 RefMap LiveInCopy = LiveIn;
1047 for (
const std::pair<const RegisterId, NodeRefSet> &
LE : LiveInCopy) {
1069 LRef.Mask =
OR.second;
1077 if (RRs.insert(
DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1098 NewDefs.insert({
TA.Id,
T.Mask});
1105 RRs.insert(
TA.Addr->getRegRef(DFG));
1107 if (RRs.hasCoverOf(LRef))
1116 dbgs() <<
"after defs in block\n";
1122 for (
auto I : DFG.
getFunc().Addr->findBlock(
B, DFG).Addr->members(DFG)) {
1131 if (getBlockWithRef(
D.Id) !=
B)
1132 LiveIn[RR.
Reg].insert({
D.Id,RR.
Mask});
1137 dbgs() <<
"after uses in block\n";
1146 for (
auto &R : LON) {
1148 for (
auto P :
R.second)
1154 dbgs() <<
"after phi uses in block\n";
1159 for (
auto C : IIDF[
B]) {
1161 for (
const std::pair<const RegisterId, NodeRefSet> &
S : LiveIn)
1162 for (
auto R :
S.second)
1168 void Liveness::emptify(RefMap &M) {
1169 for (
auto I =
M.begin(),
E =
M.end();
I !=
E; )
1170 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)
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
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
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
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
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())
StandardInstrumentations SI(Debug, VerifyEach)
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.
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
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
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
void sort(IteratorTy Start, IteratorTy End)
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
NodeId getReachedDef() const
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"))
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)