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