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