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
25namespace llvm {
26
27class MachineBasicBlock;
28class MachineDominanceFrontier;
29class MachineDominatorTree;
30class MachineRegisterInfo;
31class TargetRegisterInfo;
32
33namespace rdf {
34namespace detail {
35
36using NodeRef = std::pair<NodeId, LaneBitmask>;
37
38} // namespace detail
39} // namespace rdf
40} // namespace llvm
41
42namespace std {
43
44template <> 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
53namespace llvm::rdf {
54
55struct Liveness {
56public:
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(RefRR: RefA.Addr->getRegRef(G: DFG), RefA, TopShadows: false, FullChain: false,
72 DefRRs: NoRegs);
73 }
74
75 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode *> RefA) {
76 return getAllReachingDefs(RefRR, RefA, TopShadows: false, FullChain: false, DefRRs: 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, DefRRs: 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(Val: 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
110private:
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
156raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P);
157
158} // end namespace llvm::rdf
159
160#endif // LLVM_CODEGEN_RDFLIVENESS_H
161