LLVM 20.0.0git
RDFLiveness.h
Go to the documentation of this file.
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> {
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:
59 using NodeRefSet = std::unordered_set<NodeRef>;
60 using RefMap = std::unordered_map<RegisterId, NodeRefSet>;
61
63 : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()),
64 MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {}
65
67 bool TopShadows, bool FullChain,
68 const RegisterAggr &DefRRs);
69
71 return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, false,
72 NoRegs);
73 }
74
76 return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
77 }
78
80 const RegisterAggr &DefRRs);
81
83 return getAllReachedUses(RefRR, DefA, NoRegs);
84 }
85
86 std::pair<NodeSet, bool> getAllReachingDefsRec(RegisterRef RefRR,
88 NodeSet &Visited,
89 const NodeSet &Defs);
90
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(P);
99 return F == RealUseMap.end() ? Empty : F->second;
100 }
101
102 void computePhiInfo();
103 void computeLiveIns();
104 void resetLiveIns();
105 void resetKills();
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.
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
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define T
#define P(N)
raw_pwrite_stream & OS
INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:36
uint32_t NodeId
Definition: RDFGraph.h:262
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:45
std::set< NodeId > NodeSet
Definition: RDFGraph.h:551
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
LiveMapType & getLiveMap()
Definition: RDFLiveness.h:94
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
std::unordered_set< NodeRef > NodeRefSet
Definition: RDFLiveness.h:59
const RefMap & getRealUses(NodeId P) const
Definition: RDFLiveness.h:97
NodeAddr< RefNode * > getNearestAliasedRef(RegisterRef RefRR, NodeAddr< InstrNode * > IA)
Find the nearest ref node aliased to RefRR, going upwards in the data flow, starting from the instruc...
RegisterAggrMap< MachineBasicBlock * > LiveMapType
Definition: RDFLiveness.h:57
NodeList getAllReachingDefs(NodeAddr< RefNode * > RefA)
Definition: RDFLiveness.h:70
Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g)
Definition: RDFLiveness.h:62
detail::NodeRef NodeRef
Definition: RDFLiveness.h:58
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA)
Definition: RDFLiveness.h:75
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA)
Definition: RDFLiveness.h:82
void trace(bool T)
Definition: RDFLiveness.h:108
std::unordered_map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:60
const LiveMapType & getLiveMap() const
Definition: RDFLiveness.h:95
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
std::size_t operator()(llvm::rdf::detail::NodeRef R) const
Definition: RDFLiveness.h:45