1 //===- RDFLiveness.h --------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Recalculate the liveness information given a data flow graph.
11 // This includes block live-ins and kill flags.
13 #ifndef LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H
14 #define LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H
17 #include "RDFRegisters.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/MC/LaneBitmask.h"
26 class MachineBasicBlock;
27 class MachineDominanceFrontier;
28 class MachineDominatorTree;
29 class MachineRegisterInfo;
30 class TargetRegisterInfo;
36 // This is really a std::map, except that it provides a non-trivial
37 // default constructor to the element accessed via [].
39 LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {}
41 RegisterAggr &operator[] (MachineBasicBlock *B) {
42 return Map.emplace(B, Empty).first->second;
47 std::map<MachineBasicBlock*,RegisterAggr> Map;
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>;
55 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()), NoRegs(g.getPRI()) {}
59 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA,
60 bool TopShadows, bool FullChain, const RegisterAggr &DefRRs);
62 NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) {
63 return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false,
67 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) {
68 return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
71 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA,
72 const RegisterAggr &DefRRs);
74 NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) {
75 return getAllReachedUses(RefRR, DefA, NoRegs);
78 std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR,
79 NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs);
81 NodeAddr<RefNode*> getNearestAliasedRef(RegisterRef RefRR,
82 NodeAddr<InstrNode*> IA);
84 LiveMapType &getLiveMap() { return LiveMap; }
85 const LiveMapType &getLiveMap() const { return LiveMap; }
87 const RefMap &getRealUses(NodeId P) const {
88 auto F = RealUseMap.find(P);
89 return F == RealUseMap.end() ? Empty : F->second;
92 void computePhiInfo();
93 void computeLiveIns();
96 void resetKills(MachineBasicBlock *B);
98 void trace(bool T) { Trace = T; }
101 const DataFlowGraph &DFG;
102 const TargetRegisterInfo &TRI;
103 const PhysicalRegisterInfo &PRI;
104 const MachineDominatorTree &MDT;
105 const MachineDominanceFrontier &MDF;
108 const RegisterAggr NoRegs;
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 *>;
120 // map: NodeId -> (map: RegisterId -> NodeRefSet)
121 // phi id -> (map: register -> set of reached non-phi uses)
122 std::map<NodeId, RefMap> RealUseMap;
124 // Inverse iterated dominance frontier.
125 std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF;
128 std::map<MachineBasicBlock*,RefMap> PhiLON;
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;
137 MachineBasicBlock *getBlockWithRef(NodeId RN) const;
138 void traverse(MachineBasicBlock *B, RefMap &LiveIn);
139 void emptify(RefMap &M);
141 std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR,
142 NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs,
143 unsigned Nest, unsigned MaxNest);
146 } // end namespace rdf
148 } // end namespace llvm
150 #endif // LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H