/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/RDFLiveness.h
Line | Count | Source (jump to first uncovered line) |
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 | 10.4k | LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {} |
39 | | |
40 | 9.68k | RegisterAggr &operator[] (MachineBasicBlock *B) { |
41 | 9.68k | return Map.emplace(B, Empty).first->second; |
42 | 9.68k | } |
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 | 10.4k | 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 | 67.3k | NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) { |
62 | 67.3k | return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, |
63 | 67.3k | false, NoRegs); |
64 | 67.3k | } |
65 | | |
66 | 31.6k | NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) { |
67 | 31.6k | return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); |
68 | 31.6k | } |
69 | | |
70 | | NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA, |
71 | | const RegisterAggr &DefRRs); |
72 | | |
73 | 1.66k | NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) { |
74 | 1.66k | return getAllReachedUses(RefRR, DefA, NoRegs); |
75 | 1.66k | } |
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 | 0 | LiveMapType &getLiveMap() { return LiveMap; } |
84 | 0 | const LiveMapType &getLiveMap() const { return LiveMap; } |
85 | | |
86 | 998 | const RefMap &getRealUses(NodeId P) const { |
87 | 998 | auto F = RealUseMap.find(P); |
88 | 998 | return F == RealUseMap.end() ? Empty0 : F->second; |
89 | 998 | } |
90 | | |
91 | | void computePhiInfo(); |
92 | | void computeLiveIns(); |
93 | | void resetLiveIns(); |
94 | | void resetKills(); |
95 | | void resetKills(MachineBasicBlock *B); |
96 | | |
97 | 394 | 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 |