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.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) {
623 for (
auto R :
I.second)
656 using SubMap = std::unordered_map<RegisterRef, RegisterRef>;
657 std::unordered_map<RegisterAggr, SubMap> Subs;
661 auto F = SM.find(RR);
670 for (
unsigned i = 0;
i < PhiUQ.size(); ++
i) {
676 std::map<NodeId,RegisterAggr> &PUM = PhiUp[UA.Id];
678 for (
const std::pair<const NodeId, RegisterAggr> &
P : PUM) {
679 bool Changed =
false;
687 SubMap &SM = Subs[MidDefs];
694 for (
const std::pair<const RegisterId, NodeRefSet> &
T : RUM) {
703 for (std::pair<NodeId,LaneBitmask> V :
T.second) {
709 Changed |= RS.insert({V.first,
SS.Mask}).second;
715 PhiUQ.push_back(
P.first);
721 dbgs() <<
"Real use map:\n";
722 for (
auto I : RealUseMap) {
745 NBMap.insert(std::make_pair(
RA.Id,
BB));
746 NBMap.insert(std::make_pair(IA.Id,
BB));
755 auto F1 = MDF.
find(&
B);
759 for (
unsigned i = 0;
i < IDFB.
size(); ++
i) {
760 auto F2 = MDF.
find(IDFB[
i]);
762 IDFB.
insert(F2->second.begin(), F2->second.end());
766 IDF[&
B].insert(IDFB.
begin(), IDFB.
end());
770 for (
auto S :
I.second)
771 IIDF[
S].insert(
I.first);
783 for (
const RefMap::value_type &
S : RealUseMap[
P.Id])
784 LON[
S.first].insert(
S.second.begin(),
S.second.end());
788 dbgs() <<
"Phi live-on-entry map:\n";
789 for (
auto &
I : PhiLON)
790 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
806 if (!SeenUses.insert(U.Id).second)
824 RefMap &LOX = PhiLOX[PrA.Addr->getCode()];
826 for (
const std::pair<const RegisterId, NodeRefSet> &RS : RUs) {
828 for (std::pair<NodeId,LaneBitmask>
P : RS.second) {
837 TA.insert(
D.Addr->getRegRef(DFG)).intersect(
S);
839 LOX[
S.Reg].insert({
D.Id,
TM});
845 SeenUses.insert(
T.Id);
851 dbgs() <<
"Phi live-on-exit map:\n";
852 for (
auto &
I : PhiLOX)
853 dbgs() <<
"block #" <<
I.first->getNumber() <<
" -> "
858 traverse(&MF.front(), LiveIn);
861 LiveMap[&MF.front()].insert(DFG.
getLiveIns());
866 std::vector<RegisterRef> LV;
868 LV.push_back(
RegisterRef(LI.PhysReg, LI.LaneMask));
881 dbgs() <<
"\tcomp = {";
891 for (
auto &
B : DFG.
getMF()) {
893 std::vector<unsigned>
T;
895 T.push_back(LI.PhysReg);
906 for (
auto &
B : DFG.
getMF())
912 for (
auto I :
B->liveins()) {
920 if ((
M &
I.LaneMask).any())
921 LV.set(
S.getSubReg());
923 }
while (
S.isValid());
928 CopyLiveIns(
B, LiveIn);
929 for (
auto SI :
B->successors())
930 CopyLiveIns(
SI, Live);
933 if (
MI.isDebugInstr())
937 for (
auto &
Op :
MI.operands()) {
942 if (!
Op.isReg() || !
Op.isDef() ||
Op.isImplicit())
950 for (
auto &
Op :
MI.operands()) {
951 if (!
Op.isReg() || !
Op.isUse() ||
Op.isUndef())
974 auto F = NBMap.find(
RN);
975 if (
F != NBMap.end())
1012 LiveIn[
S.first].insert(
S.second.begin(),
S.second.end());
1017 <<
" after recursion into: {";
1019 dbgs() <<
' ' <<
I->getBlock()->getNumber();
1028 LiveIn[
S.first].insert(
S.second.begin(),
S.second.end());
1031 dbgs() <<
"after LOX\n";
1043 RefMap LiveInCopy = LiveIn;
1046 for (
const std::pair<const RegisterId, NodeRefSet> &
LE : LiveInCopy) {
1068 LRef.Mask =
OR.second;
1076 if (RRs.insert(
DA.Addr->getRegRef(DFG)).hasCoverOf(LRef))
1097 NewDefs.insert({
TA.Id,
T.Mask});
1104 RRs.insert(
TA.Addr->getRegRef(DFG));
1106 if (RRs.hasCoverOf(LRef))
1115 dbgs() <<
"after defs in block\n";
1121 for (
auto I : DFG.
getFunc().Addr->findBlock(
B, DFG).Addr->members(DFG)) {
1130 if (getBlockWithRef(
D.Id) !=
B)
1131 LiveIn[RR.
Reg].insert({
D.Id,RR.
Mask});
1136 dbgs() <<
"after uses in block\n";
1145 for (
auto &R : LON) {
1147 for (
auto P :
R.second)
1153 dbgs() <<
"after phi uses in block\n";
1158 for (
auto C : IIDF[
B]) {
1160 for (
const std::pair<const RegisterId, NodeRefSet> &
S : LiveIn)
1161 for (
auto R :
S.second)
1167 void Liveness::emptify(RefMap &M) {
1168 for (
auto I =
M.begin(),
E =
M.end();
I !=
E; )
1169 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)