RDFLiveness.h revision 296417
1//===--- RDFLiveness.h ----------------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// Recalculate the liveness information given a data flow graph. 11// This includes block live-ins and kill flags. 12 13#ifndef RDF_LIVENESS_H 14#define RDF_LIVENESS_H 15 16#include "RDFGraph.h" 17#include "llvm/ADT/DenseMap.h" 18#include <map> 19 20using namespace llvm; 21 22namespace llvm { 23 class MachineBasicBlock; 24 class MachineFunction; 25 class MachineRegisterInfo; 26 class TargetRegisterInfo; 27 class MachineDominatorTree; 28 class MachineDominanceFrontier; 29} 30 31namespace rdf { 32 struct Liveness { 33 public: 34 typedef std::map<MachineBasicBlock*,RegisterSet> LiveMapType; 35 typedef std::map<RegisterRef,NodeSet> RefMap; 36 37 Liveness(MachineRegisterInfo &mri, const DataFlowGraph &g) 38 : DFG(g), TRI(g.getTRI()), MDT(g.getDT()), MDF(g.getDF()), 39 RAI(g.getRAI()), MRI(mri), Empty(), Trace(false) {} 40 41 NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr<RefNode*> RefA, 42 bool FullChain = false, const RegisterSet &DefRRs = RegisterSet()); 43 NodeList getAllReachingDefs(NodeAddr<RefNode*> RefA); 44 45 LiveMapType &getLiveMap() { return LiveMap; } 46 const LiveMapType &getLiveMap() const { return LiveMap; } 47 const RefMap &getRealUses(NodeId P) const { 48 auto F = RealUseMap.find(P); 49 return F == RealUseMap.end() ? Empty : F->second; 50 } 51 52 void computePhiInfo(); 53 void computeLiveIns(); 54 void resetLiveIns(); 55 void resetKills(); 56 void resetKills(MachineBasicBlock *B); 57 58 void trace(bool T) { Trace = T; } 59 60 private: 61 const DataFlowGraph &DFG; 62 const TargetRegisterInfo &TRI; 63 const MachineDominatorTree &MDT; 64 const MachineDominanceFrontier &MDF; 65 const RegisterAliasInfo &RAI; 66 MachineRegisterInfo &MRI; 67 LiveMapType LiveMap; 68 const RefMap Empty; 69 bool Trace; 70 71 // Cache of mapping from node ids (for RefNodes) to the containing 72 // basic blocks. Not computing it each time for each node reduces 73 // the liveness calculation time by a large fraction. 74 typedef DenseMap<NodeId,MachineBasicBlock*> NodeBlockMap; 75 NodeBlockMap NBMap; 76 77 // Phi information: 78 // 79 // map: NodeId -> (map: RegisterRef -> NodeSet) 80 // phi id -> (map: register -> set of reached non-phi uses) 81 std::map<NodeId, RefMap> RealUseMap; 82 83 // Inverse iterated dominance frontier. 84 std::map<MachineBasicBlock*,std::set<MachineBasicBlock*>> IIDF; 85 86 // Live on entry. 87 std::map<MachineBasicBlock*,RefMap> PhiLON; 88 89 // Phi uses are considered to be located at the end of the block that 90 // they are associated with. The reaching def of a phi use dominates the 91 // block that the use corresponds to, but not the block that contains 92 // the phi itself. To include these uses in the liveness propagation (up 93 // the dominator tree), create a map: block -> set of uses live on exit. 94 std::map<MachineBasicBlock*,RefMap> PhiLOX; 95 96 bool isRestricted(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, 97 RegisterRef RR) const; 98 RegisterRef getRestrictedRegRef(NodeAddr<RefNode*> RA) const; 99 unsigned getPhysReg(RegisterRef RR) const; 100 MachineBasicBlock *getBlockWithRef(NodeId RN) const; 101 void traverse(MachineBasicBlock *B, RefMap &LiveIn); 102 void emptify(RefMap &M); 103 }; 104} 105 106#endif // RDF_LIVENESS_H 107