1 //===--- RDFLiveness.h ----------------------------------------------------===// 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 RDF_LIVENESS_H 14 #define RDF_LIVENESS_H 15 16 #include "RDFGraph.h" 17 #include "llvm/ADT/DenseMap.h" 18 #include <map> 19 20 using namespace llvm; 21 22 namespace llvm { 23 class MachineBasicBlock; 24 class MachineFunction; 25 class MachineRegisterInfo; 26 class TargetRegisterInfo; 27 class MachineDominatorTree; 28 class MachineDominanceFrontier; 29 30 namespace rdf { 31 struct Liveness { 32 public: 33 typedef std::map<MachineBasicBlock*,RegisterSet> LiveMapType; 34 typedef std::map<RegisterRef,NodeSet> RefMap; 35 LivenessLiveness36 Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) 37 : DFG(g), TRI(g.getTRI()), MDT(g.getDT()), MDF(g.getDF()), 38 RAI(g.getRAI()), MRI(mri), Empty(), Trace(false) {} 39 40 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 41 bool FullChain = false, const RegisterSet &DefRRs = RegisterSet()); 42 NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA); 43 NodeSet getAllReachingDefsRec(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 44 NodeSet &Visited, const NodeSet &Defs); 45 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA, 46 const RegisterSet &DefRRs = RegisterSet()); 47 getLiveMapLiveness48 LiveMapType &getLiveMap() { return LiveMap; } getLiveMapLiveness49 const LiveMapType &getLiveMap() const { return LiveMap; } getRealUsesLiveness50 const RefMap &getRealUses(NodeId P) const { 51 auto F = RealUseMap.find(P); 52 return F == RealUseMap.end() ? Empty : F->second; 53 } 54 55 void computePhiInfo(); 56 void computeLiveIns(); 57 void resetLiveIns(); 58 void resetKills(); 59 void resetKills(MachineBasicBlock *B); 60 traceLiveness61 void trace(bool T) { Trace = T; } 62 63 private: 64 const DataFlowGraph &DFG; 65 const TargetRegisterInfo &TRI; 66 const MachineDominatorTree &MDT; 67 const MachineDominanceFrontier &MDF; 68 const RegisterAliasInfo &RAI; 69 MachineRegisterInfo &MRI; 70 LiveMapType LiveMap; 71 const RefMap Empty; 72 bool Trace; 73 74 // Cache of mapping from node ids (for RefNodes) to the containing 75 // basic blocks. Not computing it each time for each node reduces 76 // the liveness calculation time by a large fraction. 77 typedef DenseMap<NodeId,MachineBasicBlock*> NodeBlockMap; 78 NodeBlockMap NBMap; 79 80 // Phi information: 81 // 82 // map: NodeId -> (map: RegisterRef -> NodeSet) 83 // phi id -> (map: register -> set of reached non-phi uses) 84 std::map<NodeId, RefMap> RealUseMap; 85 86 // Inverse iterated dominance frontier. 87 std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF; 88 89 // Live on entry. 90 std::map<MachineBasicBlock*,RefMap> PhiLON; 91 92 // Phi uses are considered to be located at the end of the block that 93 // they are associated with. The reaching def of a phi use dominates the 94 // block that the use corresponds to, but not the block that contains 95 // the phi itself. To include these uses in the liveness propagation (up 96 // the dominator tree), create a map: block -> set of uses live on exit. 97 std::map<MachineBasicBlock*,RefMap> PhiLOX; 98 99 bool isRestricted(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, 100 RegisterRef RR) const; 101 RegisterRef getRestrictedRegRef(NodeAddr<RefNode*> RA) const; 102 unsigned getPhysReg(RegisterRef RR) const; 103 MachineBasicBlock *getBlockWithRef(NodeId RN) const; 104 void traverse(MachineBasicBlock *B, RefMap &LiveIn); 105 void emptify(RefMap &M); 106 }; 107 } // namespace rdf 108 } // namespace llvm 109 110 #endif // RDF_LIVENESS_H 111