LLVM  14.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 
25 namespace llvm {
26 
27 class MachineBasicBlock;
28 class MachineDominanceFrontier;
29 class MachineDominatorTree;
30 class MachineRegisterInfo;
31 class TargetRegisterInfo;
32 
33 } // namespace llvm
34 
35 namespace llvm {
36 namespace rdf {
37 namespace detail {
38 
39 using NodeRef = std::pair<NodeId, LaneBitmask>;
40 
41 } // namespace detail
42 } // namespace rdf
43 } // namespace llvm
44 
45 namespace std {
46 
47 template <> struct hash<llvm::rdf::detail::NodeRef> {
48  std::size_t operator()(llvm::rdf::detail::NodeRef R) const {
49  return std::hash<llvm::rdf::NodeId>{}(R.first) ^
50  std::hash<llvm::LaneBitmask::Type>{}(R.second.getAsInteger());
51  }
52 };
53 
54 } // namespace std
55 
56 namespace llvm {
57 namespace rdf {
58 
59  struct Liveness {
60  public:
61  // This is really a std::map, except that it provides a non-trivial
62  // default constructor to the element accessed via [].
63  struct LiveMapType {
64  LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {}
65 
67  return Map.emplace(B, Empty).first->second;
68  }
69 
70  private:
71  RegisterAggr Empty;
72  std::map<MachineBasicBlock*,RegisterAggr> Map;
73  };
74 
76  using NodeRefSet = std::unordered_set<NodeRef>;
77  using RefMap = std::unordered_map<RegisterId, NodeRefSet>;
78 
80  : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()),
81  MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {}
82 
84  bool TopShadows, bool FullChain, const RegisterAggr &DefRRs);
85 
87  return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false,
88  false, NoRegs);
89  }
90 
92  return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
93  }
94 
96  const RegisterAggr &DefRRs);
97 
99  return getAllReachedUses(RefRR, DefA, NoRegs);
100  }
101 
102  std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR,
103  NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs);
104 
107 
108  LiveMapType &getLiveMap() { return LiveMap; }
109  const LiveMapType &getLiveMap() const { return LiveMap; }
110 
111  const RefMap &getRealUses(NodeId P) const {
112  auto F = RealUseMap.find(P);
113  return F == RealUseMap.end() ? Empty : F->second;
114  }
115 
116  void computePhiInfo();
117  void computeLiveIns();
118  void resetLiveIns();
119  void resetKills();
121 
122  void trace(bool T) { Trace = T; }
123 
124  private:
125  const DataFlowGraph &DFG;
126  const TargetRegisterInfo &TRI;
127  const PhysicalRegisterInfo &PRI;
128  const MachineDominatorTree &MDT;
129  const MachineDominanceFrontier &MDF;
130  LiveMapType LiveMap;
131  const RefMap Empty;
132  const RegisterAggr NoRegs;
133  bool Trace = false;
134 
135  // Cache of mapping from node ids (for RefNodes) to the containing
136  // basic blocks. Not computing it each time for each node reduces
137  // the liveness calculation time by a large fraction.
139 
140  // Phi information:
141  //
142  // RealUseMap
143  // map: NodeId -> (map: RegisterId -> NodeRefSet)
144  // phi id -> (map: register -> set of reached non-phi uses)
145  DenseMap<NodeId, RefMap> RealUseMap;
146 
147  // Inverse iterated dominance frontier.
148  std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF;
149 
150  // Live on entry.
151  std::map<MachineBasicBlock*,RefMap> PhiLON;
152 
153  // Phi uses are considered to be located at the end of the block that
154  // they are associated with. The reaching def of a phi use dominates the
155  // block that the use corresponds to, but not the block that contains
156  // the phi itself. To include these uses in the liveness propagation (up
157  // the dominator tree), create a map: block -> set of uses live on exit.
158  std::map<MachineBasicBlock*,RefMap> PhiLOX;
159 
160  MachineBasicBlock *getBlockWithRef(NodeId RN) const;
161  void traverse(MachineBasicBlock *B, RefMap &LiveIn);
162  void emptify(RefMap &M);
163 
164  std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR,
165  NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs,
166  unsigned Nest, unsigned MaxNest);
167  };
168 
169  raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P);
170 
171 } // end namespace rdf
172 
173 } // end namespace llvm
174 
175 #endif // LLVM_CODEGEN_RDFLIVENESS_H
llvm::rdf::Liveness::LiveMapType::LiveMapType
LiveMapType(const PhysicalRegisterInfo &pri)
Definition: RDFLiveness.h:64
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::rdf::Liveness::RefMap
std::unordered_map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:77
llvm::rdf::Liveness::LiveMapType
Definition: RDFLiveness.h:63
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::rdf::Liveness::getAllReachedUses
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
Definition: RDFLiveness.cpp:419
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
llvm::rdf::Liveness::getAllReachingDefsRec
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
Definition: RDFLiveness.cpp:309
T
#define T
Definition: Mips16ISelLowering.cpp:341
g
should just be implemented with a CLZ instruction Since there are other e g
Definition: README.txt:709
llvm::rdf::Liveness::Liveness
Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g)
Definition: RDFLiveness.h:79
llvm::rdf::Liveness::getAllReachingDefs
NodeList getAllReachingDefs(NodeAddr< RefNode * > RefA)
Definition: RDFLiveness.h:86
llvm::rdf::Liveness::getNearestAliasedRef
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...
Definition: RDFLiveness.cpp:362
RDFRegisters.h
llvm::rdf::RegisterRef
Definition: RDFRegisters.h:71
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::rdf::Liveness::getRealUses
const RefMap & getRealUses(NodeId P) const
Definition: RDFLiveness.h:111
llvm::rdf::NodeAddr
Definition: RDFGraph.h:334
llvm::rdf::Liveness::getAllReachedUses
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA)
Definition: RDFLiveness.h:98
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::rdf::RegisterAggr
Definition: RDFRegisters.h:168
llvm::rdf::NodeId
uint32_t NodeId
Definition: RDFGraph.h:260
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::rdf::PhysicalRegisterInfo
Definition: RDFRegisters.h:102
llvm::rdf::NodeAddr::Addr
T Addr
Definition: RDFGraph.h:351
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::rdf::Liveness::LiveMapType::operator[]
RegisterAggr & operator[](MachineBasicBlock *B)
Definition: RDFLiveness.h:66
llvm::rdf::Liveness::getLiveMap
LiveMapType & getLiveMap()
Definition: RDFLiveness.h:108
llvm::MachineDominanceFrontier
Definition: MachineDominanceFrontier.h:20
llvm::DenseMap
Definition: DenseMap.h:714
llvm::rdf::DataFlowGraph
Definition: RDFGraph.h:644
llvm::rdf::Liveness::NodeRef
detail::NodeRef NodeRef
Definition: RDFLiveness.h:75
llvm::rdf::operator<<
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:57
llvm::rdf::Liveness::resetKills
void resetKills()
Definition: RDFLiveness.cpp:907
RDFGraph.h
uint32_t
llvm::Trace
Definition: Trace.h:30
std
Definition: BitVector.h:838
llvm::rdf::Liveness::computePhiInfo
void computePhiInfo()
Definition: RDFLiveness.cpp:465
std::hash< llvm::rdf::detail::NodeRef >::operator()
std::size_t operator()(llvm::rdf::detail::NodeRef R) const
Definition: RDFLiveness.h:48
llvm::rdf::Liveness::resetLiveIns
void resetLiveIns()
Definition: RDFLiveness.cpp:892
llvm::rdf::Liveness::trace
void trace(bool T)
Definition: RDFLiveness.h:122
llvm::rdf::Liveness
Definition: RDFLiveness.h:59
llvm::rdf::NodeSet
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
llvm::rdf::Liveness::getLiveMap
const LiveMapType & getLiveMap() const
Definition: RDFLiveness.h:109
LaneBitmask.h
llvm::rdf::Liveness::getAllReachingDefs
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA)
Definition: RDFLiveness.h:91
llvm::rdf::Liveness::NodeRefSet
std::unordered_set< NodeRef > NodeRefSet
Definition: RDFLiveness.h:76
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::rdf::Liveness::getAllReachingDefs
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
Definition: RDFLiveness.cpp:109
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::rdf::Liveness::computeLiveIns
void computeLiveIns()
Definition: RDFLiveness.cpp:739