LLVM  10.0.0svn
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_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  LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {}
39 
41  return Map.emplace(B, Empty).first->second;
42  }
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 
55  : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()),
56  MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {}
57 
59  bool TopShadows, bool FullChain, const RegisterAggr &DefRRs);
60 
62  return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false,
63  false, NoRegs);
64  }
65 
67  return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
68  }
69 
71  const RegisterAggr &DefRRs);
72 
74  return getAllReachedUses(RefRR, DefA, NoRegs);
75  }
76 
77  std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR,
78  NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs);
79 
82 
83  LiveMapType &getLiveMap() { return LiveMap; }
84  const LiveMapType &getLiveMap() const { return LiveMap; }
85 
86  const RefMap &getRealUses(NodeId P) const {
87  auto F = RealUseMap.find(P);
88  return F == RealUseMap.end() ? Empty : F->second;
89  }
90 
91  void computePhiInfo();
92  void computeLiveIns();
93  void resetLiveIns();
94  void resetKills();
96 
97  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.
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
const LiveMapType & getLiveMap() const
Definition: RDFLiveness.h:84
A common definition of LaneBitmask for use in TableGen and CodeGen.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode *> RefA)
Definition: RDFLiveness.h:66
std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode *> RefA, NodeSet &Visited, const NodeSet &Defs)
unsigned const TargetRegisterInfo * TRI
F(f)
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...
LiveMapType(const PhysicalRegisterInfo &pri)
Definition: RDFLiveness.h:38
RegisterAggr & operator[](MachineBasicBlock *B)
Definition: RDFLiveness.h:40
void trace(bool T)
Definition: RDFLiveness.h:97
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode *> DefA)
Definition: RDFLiveness.h:73
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode *> RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
const RefMap & getRealUses(NodeId P) const
Definition: RDFLiveness.h:86
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:49
LiveMapType & getLiveMap()
Definition: RDFLiveness.h:83
std::map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:52
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
std::set< NodeId > NodeSet
Definition: RDFGraph.h:513
NodeList getAllReachingDefs(NodeAddr< RefNode *> RefA)
Definition: RDFLiveness.h:61
std::set< NodeRef > NodeRefSet
Definition: RDFLiveness.h:50
NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode *> DefA, const RegisterAggr &DefRRs)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g)
Definition: RDFLiveness.h:54
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...