1 //===- RDFLiveness.h --------------------------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Recalculate the liveness information given a data flow graph. 11 // This includes block live-ins and kill flags. 12 13 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 14 #define LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 15 16 #include "RDFGraph.h" 17 #include "RDFRegisters.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/MC/LaneBitmask.h" 20 #include <map> 21 #include <set> 22 #include <utility> 23 24 namespace llvm { 25 26 class MachineBasicBlock; 27 class MachineDominanceFrontier; 28 class MachineDominatorTree; 29 class MachineRegisterInfo; 30 class TargetRegisterInfo; 31 32 namespace rdf { 33 34 struct Liveness { 35 public: 36 // This is really a std::map, except that it provides a non-trivial 37 // default constructor to the element accessed via []. 38 struct LiveMapType { LiveMapTypeLiveness::LiveMapType39 LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {} 40 41 RegisterAggr &operator[] (MachineBasicBlock *B) { 42 return Map.emplace(B, Empty).first->second; 43 } 44 45 private: 46 RegisterAggr Empty; 47 std::map<MachineBasicBlock*,RegisterAggr> Map; 48 }; 49 50 using NodeRef = std::pair<NodeId, LaneBitmask>; 51 using NodeRefSet = std::set<NodeRef>; 52 // RegisterId in RefMap must be normalized. 53 using RefMap = std::map<RegisterId, NodeRefSet>; 54 LivenessLiveness55 Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) 56 : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), 57 MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {} 58 59 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 60 bool TopShadows, bool FullChain, const RegisterAggr &DefRRs); 61 getAllReachingDefsLiveness62 NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) { 63 return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, 64 false, NoRegs); 65 } 66 getAllReachingDefsLiveness67 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) { 68 return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); 69 } 70 71 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA, 72 const RegisterAggr &DefRRs); 73 getAllReachedUsesLiveness74 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) { 75 return getAllReachedUses(RefRR, DefA, NoRegs); 76 } 77 78 std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR, 79 NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs); 80 81 NodeAddr<RefNode*> getNearestAliasedRef(RegisterRef RefRR, 82 NodeAddr<InstrNode*> IA); 83 getLiveMapLiveness84 LiveMapType &getLiveMap() { return LiveMap; } getLiveMapLiveness85 const LiveMapType &getLiveMap() const { return LiveMap; } 86 getRealUsesLiveness87 const RefMap &getRealUses(NodeId P) const { 88 auto F = RealUseMap.find(P); 89 return F == RealUseMap.end() ? Empty : F->second; 90 } 91 92 void computePhiInfo(); 93 void computeLiveIns(); 94 void resetLiveIns(); 95 void resetKills(); 96 void resetKills(MachineBasicBlock *B); 97 traceLiveness98 void trace(bool T) { Trace = T; } 99 100 private: 101 const DataFlowGraph &DFG; 102 const TargetRegisterInfo &TRI; 103 const PhysicalRegisterInfo &PRI; 104 const MachineDominatorTree &MDT; 105 const MachineDominanceFrontier &MDF; 106 LiveMapType LiveMap; 107 const RefMap Empty; 108 const RegisterAggr NoRegs; 109 bool Trace = false; 110 111 // Cache of mapping from node ids (for RefNodes) to the containing 112 // basic blocks. Not computing it each time for each node reduces 113 // the liveness calculation time by a large fraction. 114 using NodeBlockMap = DenseMap<NodeId, MachineBasicBlock *>; 115 NodeBlockMap NBMap; 116 117 // Phi information: 118 // 119 // RealUseMap 120 // map: NodeId -> (map: RegisterId -> NodeRefSet) 121 // phi id -> (map: register -> set of reached non-phi uses) 122 std::map<NodeId, RefMap> RealUseMap; 123 124 // Inverse iterated dominance frontier. 125 std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF; 126 127 // Live on entry. 128 std::map<MachineBasicBlock*,RefMap> PhiLON; 129 130 // Phi uses are considered to be located at the end of the block that 131 // they are associated with. The reaching def of a phi use dominates the 132 // block that the use corresponds to, but not the block that contains 133 // the phi itself. To include these uses in the liveness propagation (up 134 // the dominator tree), create a map: block -> set of uses live on exit. 135 std::map<MachineBasicBlock*,RefMap> PhiLOX; 136 137 MachineBasicBlock *getBlockWithRef(NodeId RN) const; 138 void traverse(MachineBasicBlock *B, RefMap &LiveIn); 139 void emptify(RefMap &M); 140 141 std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR, 142 NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs, 143 unsigned Nest, unsigned MaxNest); 144 }; 145 146 } // end namespace rdf 147 148 } // end namespace llvm 149 150 #endif // LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 151