1362593Sdim//===- RDFLiveness.h --------------------------------------------*- C++ -*-===// 2362593Sdim// 3362593Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4362593Sdim// See https://llvm.org/LICENSE.txt for license information. 5362593Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6362593Sdim// 7362593Sdim//===----------------------------------------------------------------------===// 8362593Sdim// 9362593Sdim// Recalculate the liveness information given a data flow graph. 10362593Sdim// This includes block live-ins and kill flags. 11362593Sdim 12362593Sdim#ifndef LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 13362593Sdim#define LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 14362593Sdim 15362593Sdim#include "RDFGraph.h" 16362593Sdim#include "RDFRegisters.h" 17362593Sdim#include "llvm/ADT/DenseMap.h" 18362593Sdim#include "llvm/MC/LaneBitmask.h" 19362593Sdim#include <map> 20362593Sdim#include <set> 21362593Sdim#include <utility> 22362593Sdim 23362593Sdimnamespace llvm { 24362593Sdim 25362593Sdimclass MachineBasicBlock; 26362593Sdimclass MachineDominanceFrontier; 27362593Sdimclass MachineDominatorTree; 28362593Sdimclass MachineRegisterInfo; 29362593Sdimclass TargetRegisterInfo; 30362593Sdim 31362593Sdimnamespace rdf { 32362593Sdim 33362593Sdim struct Liveness { 34362593Sdim public: 35362593Sdim // This is really a std::map, except that it provides a non-trivial 36362593Sdim // default constructor to the element accessed via []. 37362593Sdim struct LiveMapType { 38362593Sdim LiveMapType(const PhysicalRegisterInfo &pri) : Empty(pri) {} 39362593Sdim 40362593Sdim RegisterAggr &operator[] (MachineBasicBlock *B) { 41362593Sdim return Map.emplace(B, Empty).first->second; 42362593Sdim } 43362593Sdim 44362593Sdim private: 45362593Sdim RegisterAggr Empty; 46362593Sdim std::map<MachineBasicBlock*,RegisterAggr> Map; 47362593Sdim }; 48362593Sdim 49362593Sdim using NodeRef = std::pair<NodeId, LaneBitmask>; 50362593Sdim using NodeRefSet = std::set<NodeRef>; 51362593Sdim // RegisterId in RefMap must be normalized. 52362593Sdim using RefMap = std::map<RegisterId, NodeRefSet>; 53362593Sdim 54362593Sdim Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) 55362593Sdim : DFG(g), TRI(g.getTRI()), PRI(g.getPRI()), MDT(g.getDT()), 56362593Sdim MDF(g.getDF()), LiveMap(g.getPRI()), Empty(), NoRegs(g.getPRI()) {} 57362593Sdim 58362593Sdim NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 59362593Sdim bool TopShadows, bool FullChain, const RegisterAggr &DefRRs); 60362593Sdim 61362593Sdim NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA) { 62362593Sdim return getAllReachingDefs(RefA.Addr->getRegRef(DFG), RefA, false, 63362593Sdim false, NoRegs); 64362593Sdim } 65362593Sdim 66362593Sdim NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA) { 67362593Sdim return getAllReachingDefs(RefRR, RefA, false, false, NoRegs); 68362593Sdim } 69362593Sdim 70362593Sdim NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA, 71362593Sdim const RegisterAggr &DefRRs); 72362593Sdim 73362593Sdim NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr<DefNode*> DefA) { 74362593Sdim return getAllReachedUses(RefRR, DefA, NoRegs); 75362593Sdim } 76362593Sdim 77362593Sdim std::pair<NodeSet,bool> getAllReachingDefsRec(RegisterRef RefRR, 78362593Sdim NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs); 79362593Sdim 80362593Sdim NodeAddr<RefNode*> getNearestAliasedRef(RegisterRef RefRR, 81362593Sdim NodeAddr<InstrNode*> IA); 82362593Sdim 83362593Sdim LiveMapType &getLiveMap() { return LiveMap; } 84362593Sdim const LiveMapType &getLiveMap() const { return LiveMap; } 85362593Sdim 86362593Sdim const RefMap &getRealUses(NodeId P) const { 87362593Sdim auto F = RealUseMap.find(P); 88362593Sdim return F == RealUseMap.end() ? Empty : F->second; 89362593Sdim } 90362593Sdim 91362593Sdim void computePhiInfo(); 92362593Sdim void computeLiveIns(); 93362593Sdim void resetLiveIns(); 94362593Sdim void resetKills(); 95362593Sdim void resetKills(MachineBasicBlock *B); 96362593Sdim 97362593Sdim void trace(bool T) { Trace = T; } 98362593Sdim 99362593Sdim private: 100362593Sdim const DataFlowGraph &DFG; 101362593Sdim const TargetRegisterInfo &TRI; 102362593Sdim const PhysicalRegisterInfo &PRI; 103362593Sdim const MachineDominatorTree &MDT; 104362593Sdim const MachineDominanceFrontier &MDF; 105362593Sdim LiveMapType LiveMap; 106362593Sdim const RefMap Empty; 107362593Sdim const RegisterAggr NoRegs; 108362593Sdim bool Trace = false; 109362593Sdim 110362593Sdim // Cache of mapping from node ids (for RefNodes) to the containing 111362593Sdim // basic blocks. Not computing it each time for each node reduces 112362593Sdim // the liveness calculation time by a large fraction. 113362593Sdim using NodeBlockMap = DenseMap<NodeId, MachineBasicBlock *>; 114362593Sdim NodeBlockMap NBMap; 115362593Sdim 116362593Sdim // Phi information: 117362593Sdim // 118362593Sdim // RealUseMap 119362593Sdim // map: NodeId -> (map: RegisterId -> NodeRefSet) 120362593Sdim // phi id -> (map: register -> set of reached non-phi uses) 121362593Sdim std::map<NodeId, RefMap> RealUseMap; 122362593Sdim 123362593Sdim // Inverse iterated dominance frontier. 124362593Sdim std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF; 125362593Sdim 126362593Sdim // Live on entry. 127362593Sdim std::map<MachineBasicBlock*,RefMap> PhiLON; 128362593Sdim 129362593Sdim // Phi uses are considered to be located at the end of the block that 130362593Sdim // they are associated with. The reaching def of a phi use dominates the 131362593Sdim // block that the use corresponds to, but not the block that contains 132362593Sdim // the phi itself. To include these uses in the liveness propagation (up 133362593Sdim // the dominator tree), create a map: block -> set of uses live on exit. 134362593Sdim std::map<MachineBasicBlock*,RefMap> PhiLOX; 135362593Sdim 136362593Sdim MachineBasicBlock *getBlockWithRef(NodeId RN) const; 137362593Sdim void traverse(MachineBasicBlock *B, RefMap &LiveIn); 138362593Sdim void emptify(RefMap &M); 139362593Sdim 140362593Sdim std::pair<NodeSet,bool> getAllReachingDefsRecImpl(RegisterRef RefRR, 141362593Sdim NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs, 142362593Sdim unsigned Nest, unsigned MaxNest); 143362593Sdim }; 144362593Sdim 145362593Sdim raw_ostream &operator<<(raw_ostream &OS, const Print<Liveness::RefMap> &P); 146362593Sdim 147362593Sdim} // end namespace rdf 148362593Sdim 149362593Sdim} // end namespace llvm 150362593Sdim 151362593Sdim#endif // LLVM_LIB_TARGET_HEXAGON_RDFLIVENESS_H 152