llvm/CodeGen/RDFLiveness.h

0001 //===- RDFLiveness.h --------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Recalculate the liveness information given a data flow graph.
0010 // This includes block live-ins and kill flags.
0011
0012 #ifndef LLVM_CODEGEN_RDFLIVENESS_H
0013 #define LLVM_CODEGEN_RDFLIVENESS_H
0014
0015 #include "RDFGraph.h"
0016 #include "RDFRegisters.h"
0017 #include "llvm/ADT/DenseMap.h"
0018 #include "llvm/MC/LaneBitmask.h"
0019 #include <map>
0020 #include <set>
0021 #include <unordered_map>
0022 #include <unordered_set>
0023 #include <utility>
0024
0025 namespace llvm {
0026
0027 class MachineBasicBlock;
0028 class MachineDominanceFrontier;
0029 class MachineDominatorTree;
0030 class MachineRegisterInfo;
0031 class TargetRegisterInfo;
0032
0033 namespace rdf {
0034 namespace detail {
0035
0036 using NodeRef = std::pair<NodeId, LaneBitmask>;
0037
0038 } // namespace detail
0039 } // namespace rdf
0040 } // namespace llvm
0041
0042 namespace std {
0043
0044 template <> struct hash<llvm::rdf::detail::NodeRef> {
0045   std::size_t operator()(llvm::rdf::detail::NodeRef R) const {
0046     return std::hash<llvm::rdf::NodeId>{}(R.first) ^
0047            std::hash<llvm::LaneBitmask::Type>{}(R.second.getAsInteger());
0048   }
0049 };
0050
0051 } // namespace std
0052
0053 namespace llvm::rdf {
0054
0055 struct Liveness {
0056 public:
0057   using LiveMapType = RegisterAggrMap<MachineBasicBlock *>;
0058   using NodeRef = detail::NodeRef;
0059   using NodeRefSet = std::unordered_set<NodeRef>;
0060   using RefMap = std::unordered_map<RegisterId, NodeRefSet>;
0061
0062   Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g)
0063       : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()),
0064         MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {}
0065
0066   NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
0067                               bool TopShadows, bool FullChain,
0068                               const RegisterAggr &DefRRs);
0069
0070   NodeList getAllReachingDefs(NodeAddr<RefNode *> RefA) {
0071     return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, false,
0072                               NoRegs);
0073   }
0074
0075   NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode *> RefA) {
0076     return getAllReachingDefs(RefRR, RefA, false, false, NoRegs);
0077   }
0078
0079   NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA,
0080                             const RegisterAggr &DefRRs);
0081
0082   NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode *> DefA) {
0083     return getAllReachedUses(RefRR, DefA, NoRegs);
0084   }
0085
0086   std::pair<NodeSet, bool> getAllReachingDefsRec(RegisterRef RefRR,
0087                                                  NodeAddr<RefNode *> RefA,
0088                                                  NodeSet &Visited,
0089                                                  const NodeSet &Defs);
0090
0091   NodeAddr<RefNode *> getNearestAliasedRef(RegisterRef RefRR,
0092                                            NodeAddr<InstrNode *> IA);
0093
0094   LiveMapType &getLiveMap() { return LiveMap; }
0095   const LiveMapType &getLiveMap() const { return LiveMap; }
0096
0097   const RefMap &getRealUses(NodeId P) const {
0098     auto F = RealUseMap.find(P);
0099     return F == RealUseMap.end() ? Empty : F->second;
0100   }
0101
0102   void computePhiInfo();
0103   void computeLiveIns();
0104   void resetLiveIns();
0105   void resetKills();
0106   void resetKills(MachineBasicBlock *B);
0107
0108   void trace(bool T) { Trace = T; }
0109
0110 private:
0111   const DataFlowGraph &DFG;
0112   const TargetRegisterInfo &TRI;
0113   const PhysicalRegisterInfo &PRI;
0114   const MachineDominatorTree &MDT;
0115   const MachineDominanceFrontier &MDF;
0116   LiveMapType LiveMap;
0117   const RefMap Empty;
0118   const RegisterAggr NoRegs;
0119   bool Trace = false;
0120
0121   // Cache of mapping from node ids (for RefNodes) to the containing
0122   // basic blocks. Not computing it each time for each node reduces
0123   // the liveness calculation time by a large fraction.
0124   DenseMap<NodeId, MachineBasicBlock *> NBMap;
0125
0126   // Phi information:
0127   //
0128   // RealUseMap
0129   // map: NodeId -> (map: RegisterId -> NodeRefSet)
0130   //      phi id -> (map: register -> set of reached non-phi uses)
0131   DenseMap<NodeId, RefMap> RealUseMap;
0132
0133   // Inverse iterated dominance frontier.
0134   std::map<MachineBasicBlock *, std::set<MachineBasicBlock *>> IIDF;
0135
0136   // Live on entry.
0137   std::map<MachineBasicBlock *, RefMap> PhiLON;
0138
0139   // Phi uses are considered to be located at the end of the block that
0140   // they are associated with. The reaching def of a phi use dominates the
0141   // block that the use corresponds to, but not the block that contains
0142   // the phi itself. To include these uses in the liveness propagation (up
0143   // the dominator tree), create a map: block -> set of uses live on exit.
0144   std::map<MachineBasicBlock *, RefMap> PhiLOX;
0145
0146   MachineBasicBlock *getBlockWithRef(NodeId RN) const;
0147   void traverse(MachineBasicBlock *B, RefMap &LiveIn);
0148   void emptify(RefMap &M);
0149
0150   std::pair<NodeSet, bool>
0151   getAllReachingDefsRecImpl(RegisterRef RefRR, NodeAddr<RefNode *> RefA,
0152                             NodeSet &Visited, const NodeSet &Defs,
0153                             unsigned Nest, unsigned MaxNest);
0154 };
0155
0156 raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P);
0157
0158 } // end namespace llvm::rdf
0159
0160 #endif // LLVM_CODEGEN_RDFLIVENESS_H