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 rdf { 34 namespace detail { 35 36 using NodeRef = std::pair<NodeId, LaneBitmask>; 37 38 } // namespace detail 39 } // namespace rdf 40 } // namespace llvm 41 42 namespace std { 43 44 template <> struct hash<llvm::rdf::detail::NodeRef> { 45 std::size_t operator()(llvm::rdf::detail::NodeRef R) const { 46 return std::hash<llvm::rdf::NodeId>{}(R.first) ^ 47 std::hash<llvm::LaneBitmask::Type>{}(R.second.getAsInteger()); 48 } 49 }; 50 51 } // namespace std 52 53 namespace llvm::rdf { 54 55 struct Liveness { 56 public: 57 using LiveMapType = RegisterAggrMap<MachineBasicBlock *>; 58 using NodeRef = detail::NodeRef; 59 using NodeRefSet = std::unordered_set<NodeRef>; 60 using RefMap = std::unordered_map<RegisterId, NodeRefSet>; 61 62 Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) 63 : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), 64 MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {} 65 66 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode *> RefA, 67 bool TopShadows, bool FullChain, 68 const RegisterAggr &DefRRs); 69 70 NodeList getAllReachingDefs(NodeAddr<RefNode *> RefA) { 71 return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, false, 72 NoRegs); 73 } 74 75 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode *> RefA) { 76 return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); 77 } 78 79 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA, 80 const RegisterAggr &DefRRs); 81 82 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA) { 83 return getAllReachedUses(RefRR, DefA, NoRegs); 84 } 85 86 std::pair<NodeSet, bool> getAllReachingDefsRec(RegisterRef RefRR, 87 NodeAddr<RefNode *> RefA, 88 NodeSet &Visited, 89 const NodeSet &Defs); 90 91 NodeAddr<RefNode *> getNearestAliasedRef(RegisterRef RefRR, 92 NodeAddr<InstrNode *> IA); 93 94 LiveMapType &getLiveMap() { return LiveMap; } 95 const LiveMapType &getLiveMap() const { return LiveMap; } 96 97 const RefMap &getRealUses(NodeId P) const { 98 auto F = RealUseMap.find(P); 99 return F == RealUseMap.end() ? Empty : F->second; 100 } 101 102 void computePhiInfo(); 103 void computeLiveIns(); 104 void resetLiveIns(); 105 void resetKills(); 106 void resetKills(MachineBasicBlock *B); 107 108 void trace(bool T) { Trace = T; } 109 110 private: 111 const DataFlowGraph &DFG; 112 const TargetRegisterInfo &TRI; 113 const PhysicalRegisterInfo &PRI; 114 const MachineDominatorTree &MDT; 115 const MachineDominanceFrontier &MDF; 116 LiveMapType LiveMap; 117 const RefMap Empty; 118 const RegisterAggr NoRegs; 119 bool Trace = false; 120 121 // Cache of mapping from node ids (for RefNodes) to the containing 122 // basic blocks. Not computing it each time for each node reduces 123 // the liveness calculation time by a large fraction. 124 DenseMap<NodeId, MachineBasicBlock *> NBMap; 125 126 // Phi information: 127 // 128 // RealUseMap 129 // map: NodeId -> (map: RegisterId -> NodeRefSet) 130 // phi id -> (map: register -> set of reached non-phi uses) 131 DenseMap<NodeId, RefMap> RealUseMap; 132 133 // Inverse iterated dominance frontier. 134 std::map<MachineBasicBlock *, std::set<MachineBasicBlock *>> IIDF; 135 136 // Live on entry. 137 std::map<MachineBasicBlock *, RefMap> PhiLON; 138 139 // Phi uses are considered to be located at the end of the block that 140 // they are associated with. The reaching def of a phi use dominates the 141 // block that the use corresponds to, but not the block that contains 142 // the phi itself. To include these uses in the liveness propagation (up 143 // the dominator tree), create a map: block -> set of uses live on exit. 144 std::map<MachineBasicBlock *, RefMap> PhiLOX; 145 146 MachineBasicBlock *getBlockWithRef(NodeId RN) const; 147 void traverse(MachineBasicBlock *B, RefMap &LiveIn); 148 void emptify(RefMap &M); 149 150 std::pair<NodeSet, bool> 151 getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode *> RefA, 152 NodeSet &Visited, const NodeSet &Defs, 153 unsigned Nest, unsigned MaxNest); 154 }; 155 156 raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P); 157 158 } // end namespace llvm::rdf 159 160 #endif // LLVM_CODEGEN_RDFLIVENESS_H 161