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