1de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar//===--- RDFLiveness.cpp --------------------------------------------------===// 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// Computation of the liveness information from the data-flow graph. 11de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 12de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The main functionality of this code is to compute block live-in 13de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// information. With the live-in information in place, the placement 14de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// of kill flags can also be recalculated. 15de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 16de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The block live-in calculation is based on the ideas from the following 17de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// publication: 18de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 19de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Dibyendu Das, Ramakrishna Upadrasta, Benoit Dupont de Dinechin. 20de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// "Efficient Liveness Computation Using Merge Sets and DJ-Graphs." 21de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// ACM Transactions on Architecture and Code Optimization, Association for 22de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Computing Machinery, 2012, ACM TACO Special Issue on "High-Performance 23de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// and Embedded Architectures and Compilers", 8 (4), 24de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// <10.1145/2086696.2086706>. <hal-00647369> 25de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 26de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "RDFGraph.h" 27de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "RDFLiveness.h" 28de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/ADT/SetVector.h" 29de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineBasicBlock.h" 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineDominanceFrontier.h" 31de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineDominators.h" 32de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineFunction.h" 33de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/CodeGen/MachineRegisterInfo.h" 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Target/TargetRegisterInfo.h" 35de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 36de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarusing namespace llvm; 37de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarusing namespace rdf; 38de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 39de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarnamespace llvm { 40de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarnamespace rdf { 41de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar template<> 42de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar raw_ostream &operator<< (raw_ostream &OS, const Print<Liveness::RefMap> &P) { 43de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << '{'; 44de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : P.Obj) { 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << ' ' << Print<RegisterRef>(I.first, P.G) << '{'; 46de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto J = I.second.begin(), E = I.second.end(); J != E; ) { 47de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << Print<NodeId>(*J, P.G); 48de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (++J != E) 49de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << ','; 50de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 51de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << '}'; 52de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 53de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar OS << " }"; 54de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return OS; 55de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 56de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} // namespace rdf 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} // namespace llvm 58de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 59de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The order in the returned sequence is the order of reaching defs in the 60de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// upward traversal: the first def is the closest to the given reference RefA, 61de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// the next one is further up, and so on. 62de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// The list ends at a reaching phi def, or when the reference from RefA is 63de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// covered by the defs in the list (see FullChain). 64de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// This function provides two modes of operation: 65de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// (1) Returning the sequence of reaching defs for a particular reference 66de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// node. This sequence will terminate at the first phi node [1]. 67de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// (2) Returning a partial sequence of reaching defs, where the final goal 68de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// is to traverse past phi nodes to the actual defs arising from the code 69de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// itself. 70de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// In mode (2), the register reference for which the search was started 71de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// may be different from the reference node RefA, for which this call was 72de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// made, hence the argument RefRR, which holds the original register. 73de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Also, some definitions may have already been encountered in a previous 74de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// call that will influence register covering. The register references 75de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// already defined are passed in through DefRRs. 76de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// In mode (1), the "continuation" considerations do not apply, and the 77de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// RefRR is the same as the register in RefA, and the set DefRRs is empty. 78de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// 79de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// [1] It is possible for multiple phi nodes to be included in the returned 80de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// sequence: 81de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// SubA = phi ... 82de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// SubB = phi ... 83de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// ... = SuperAB(rdef:SubA), SuperAB"(rdef:SubB) 84de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// However, these phi nodes are independent from one another in terms of 85de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// the data-flow. 86de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 87de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarNodeList Liveness::getAllReachingDefs(RegisterRef RefRR, 88de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<RefNode*> RefA, bool FullChain, const RegisterSet &DefRRs) { 89de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SetVector<NodeId> DefQ; 90de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SetVector<NodeId> Owners; 91de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 92de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The initial queue should not have reaching defs for shadows. The 93de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // whole point of a shadow is that it will have a reaching def that 94de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // is not aliased to the reaching defs of the related shadows. 95de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId Start = RefA.Id; 96de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto SNA = DFG.addr<RefNode*>(Start); 97de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (NodeId RD = SNA.Addr->getReachingDef()) 98de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefQ.insert(RD); 99de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 100de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Collect all the reaching defs, going up until a phi node is encountered, 101de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // or there are no more reaching defs. From this set, the actual set of 102de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // reaching defs will be selected. 103de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The traversal upwards must go on until a covering def is encountered. 104de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // It is possible that a collection of non-covering (individually) defs 105de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // will be sufficient, but keep going until a covering one is found. 106de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0; i < DefQ.size(); ++i) { 107de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto TA = DFG.addr<DefNode*>(DefQ[i]); 108de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (TA.Addr->getFlags() & NodeAttrs::PhiRef) 109de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 110de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Stop at the covering/overwriting def of the initial register reference. 111de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef RR = TA.Addr->getRegRef(); 112de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.covers(RR, RefRR)) { 113de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar uint16_t Flags = TA.Addr->getFlags(); 114de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(Flags & NodeAttrs::Preserving)) 115de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 116de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 117de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Get the next level of reaching defs. This will include multiple 118de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // reaching defs for shadows. 119de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : DFG.getRelatedRefs(TA.Addr->getOwner(DFG), TA)) 120de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (auto RD = NodeAddr<RefNode*>(S).Addr->getReachingDef()) 121de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefQ.insert(RD); 122de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 123de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 124de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Remove all non-phi defs that are not aliased to RefRR, and collect 125de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the owners of the remaining defs. 126de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SetVector<NodeId> Defs; 127de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto N : DefQ) { 128de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto TA = DFG.addr<DefNode*>(N); 129de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool IsPhi = TA.Addr->getFlags() & NodeAttrs::PhiRef; 130de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!IsPhi && !RAI.alias(RefRR, TA.Addr->getRegRef())) 131de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 132de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Defs.insert(TA.Id); 133de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Owners.insert(TA.Addr->getOwner(DFG).Id); 134de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 135de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 136de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Return the MachineBasicBlock containing a given instruction. 137de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Block = [this] (NodeAddr<InstrNode*> IA) -> MachineBasicBlock* { 138de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (IA.Addr->getKind() == NodeAttrs::Stmt) 139de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return NodeAddr<StmtNode*>(IA).Addr->getCode()->getParent(); 140de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(IA.Addr->getKind() == NodeAttrs::Phi); 141de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<PhiNode*> PA = IA; 142de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<BlockNode*> BA = PA.Addr->getOwner(DFG); 143de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return BA.Addr->getCode(); 144de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 145de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Less(A,B) iff instruction A is further down in the dominator tree than B. 146de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Less = [&Block,this] (NodeId A, NodeId B) -> bool { 147de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (A == B) 148de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 149de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto OA = DFG.addr<InstrNode*>(A), OB = DFG.addr<InstrNode*>(B); 150de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *BA = Block(OA), *BB = Block(OB); 151de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (BA != BB) 152de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return MDT.dominates(BB, BA); 153de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // They are in the same block. 154de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool StmtA = OA.Addr->getKind() == NodeAttrs::Stmt; 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool StmtB = OB.Addr->getKind() == NodeAttrs::Stmt; 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StmtA) { 157de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!StmtB) // OB is a phi and phis dominate statements. 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 159de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto CA = NodeAddr<StmtNode*>(OA).Addr->getCode(); 160de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto CB = NodeAddr<StmtNode*>(OB).Addr->getCode(); 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The order must be linear, so tie-break such equalities. 162de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (CA == CB) 163de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return A < B; 164de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return MDT.dominates(CB, CA); 165de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 166de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // OA is a phi. 167de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (StmtB) 168de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 169de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Both are phis. There is no ordering between phis (in terms of 170de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the data-flow), so tie-break this via node id comparison. 171de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return A < B; 172de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 173de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 174de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 175de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::vector<NodeId> Tmp(Owners.begin(), Owners.end()); 176de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::sort(Tmp.begin(), Tmp.end(), Less); 177de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 178de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The vector is a list of instructions, so that defs coming from 179de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the same instruction don't need to be artificially ordered. 180de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Then, when computing the initial segment, and iterating over an 181de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // instruction, pick the defs that contribute to the covering (i.e. is 182de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // not covered by previously added defs). Check the defs individually, 183de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // i.e. first check each def if is covered or not (without adding them 184de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // to the tracking set), and then add all the selected ones. 185de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 186de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The reason for this is this example: 187de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // *d1<A>, *d2<B>, ... Assume A and B are aliased (can happen in phi nodes). 188de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // *d3<C> If A \incl BuC, and B \incl AuC, then *d2 would be 189de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // covered if we added A first, and A would be covered 190de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // if we added B first. 191de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 192de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeList RDefs; 193de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet RRs = DefRRs; 194de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 195de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DefInSet = [&Defs] (NodeAddr<RefNode*> TA) -> bool { 196de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return TA.Addr->getKind() == NodeAttrs::Def && 197de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Defs.count(TA.Id); 198de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 199de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto T : Tmp) { 200de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!FullChain && RAI.covers(RRs, RefRR)) 201de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 202de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto TA = DFG.addr<InstrNode*>(T); 203de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool IsPhi = DFG.IsCode<NodeAttrs::Phi>(TA); 204de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeList Ds; 205de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<DefNode*> DA : TA.Addr->members_if(DefInSet, DFG)) { 206de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto QR = DA.Addr->getRegRef(); 207de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add phi defs even if they are covered by subsequent defs. This is 208de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for cases where the reached use is not covered by any of the defs 209de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // encountered so far: the phi def is needed to expose the liveness 210de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // of that use to the entry of the block. 211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Example: 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phi d1<R3>(,d2,), ... Phi def d1 is covered by d2. 213de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // d2<R3>(d1,,u3), ... 214de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // ..., u3<D1>(d2) This use needs to be live on entry. 215de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (FullChain || IsPhi || !RAI.covers(RRs, QR)) 216de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Ds.push_back(DA); 217de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 218de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RDefs.insert(RDefs.end(), Ds.begin(), Ds.end()); 219de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<DefNode*> DA : Ds) { 220de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // When collecting a full chain of definitions, do not consider phi 221de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // defs to actually define a register. 222de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar uint16_t Flags = DA.Addr->getFlags(); 223de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!FullChain || !(Flags & NodeAttrs::PhiRef)) 224de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(Flags & NodeAttrs::Preserving)) 225de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RRs.insert(DA.Addr->getRegRef()); 226de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 227de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 228de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 229de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return RDefs; 230de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 231de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 232de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 233de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic const RegisterSet NoRegs; 234de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 235de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarNodeList Liveness::getAllReachingDefs(NodeAddr<RefNode*> RefA) { 236de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return getAllReachingDefs(RefA.Addr->getRegRef(), RefA, false, NoRegs); 237de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 238de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 239de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 240de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarNodeSet Liveness::getAllReachingDefsRec(RegisterRef RefRR, 241de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<RefNode*> RefA, NodeSet &Visited, const NodeSet &Defs) { 242de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Collect all defined registers. Do not consider phis to be defining 243de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // anything, only collect "real" definitions. 244de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet DefRRs; 245de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (const auto D : Defs) { 246de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const auto DA = DFG.addr<const DefNode*>(D); 247de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 248de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefRRs.insert(DA.Addr->getRegRef()); 249de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 250de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 251de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto RDs = getAllReachingDefs(RefRR, RefA, true, DefRRs); 252de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RDs.empty()) 253de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Defs; 254de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 255de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Make a copy of the preexisting definitions and add the newly found ones. 256de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet TmpDefs = Defs; 257de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : RDs) 258de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TmpDefs.insert(R.Id); 259de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 260de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet Result = Defs; 261de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 262de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<DefNode*> DA : RDs) { 263de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Result.insert(DA.Id); 264de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(DA.Addr->getFlags() & NodeAttrs::PhiRef)) 265de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 266de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<PhiNode*> PA = DA.Addr->getOwner(DFG); 267de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Visited.count(PA.Id)) 268de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 269de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Visited.insert(PA.Id); 270de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Go over all phi uses and get the reaching defs for each use. 271de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 272de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar const auto &T = getAllReachingDefsRec(RefRR, U, Visited, TmpDefs); 273de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Result.insert(T.begin(), T.end()); 274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 275de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 276de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 277de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Result; 278de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 279de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 280de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarNodeSet Liveness::getAllReachedUses(RegisterRef RefRR, 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<DefNode*> DefA, const RegisterSet &DefRRs) { 283de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet Uses; 284de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 285de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If the original register is already covered by all the intervening 286de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // defs, no more uses can be reached. 287de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.covers(DefRRs, RefRR)) 288de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Uses; 289de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 290de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add all directly reached uses. 291de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId U = DefA.Addr->getReachedUse(); 292de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (U != 0) { 293de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto UA = DFG.addr<UseNode*>(U); 294de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto UR = UA.Addr->getRegRef(); 295de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.alias(RefRR, UR) && !RAI.covers(DefRRs, UR)) 296de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Uses.insert(U); 297de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar U = UA.Addr->getSibling(); 298de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 299de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 300de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Traverse all reached defs. 301de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeId D = DefA.Addr->getReachedDef(), NextD; D != 0; D = NextD) { 302de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DA = DFG.addr<DefNode*>(D); 303de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NextD = DA.Addr->getSibling(); 304de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DR = DA.Addr->getRegRef(); 305de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If this def is already covered, it cannot reach anything new. 306de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Similarly, skip it if it is not aliased to the interesting register. 307de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.covers(DefRRs, DR) || !RAI.alias(RefRR, DR)) 308de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 309de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet T; 310de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (DA.Addr->getFlags() & NodeAttrs::Preserving) { 311de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If it is a preserving def, do not update the set of intervening defs. 312de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar T = getAllReachedUses(RefRR, DA, DefRRs); 313de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 314de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet NewDefRRs = DefRRs; 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NewDefRRs.insert(DR); 316de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar T = getAllReachedUses(RefRR, DA, NewDefRRs); 317de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 318de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Uses.insert(T.begin(), T.end()); 319de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 320de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Uses; 321de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 322de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 323de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 324de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::computePhiInfo() { 325de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RealUseMap.clear(); 326de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 327de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeList Phis; 328de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<FuncNode*> FA = DFG.getFunc(); 329de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Blocks = FA.Addr->members(DFG); 330de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<BlockNode*> BA : Blocks) { 331de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Ps = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 332de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Phis.insert(Phis.end(), Ps.begin(), Ps.end()); 333de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 334de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 335de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phi use -> (map: reaching phi -> set of registers defined in between) 336de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::map<NodeId,std::map<NodeId,RegisterSet>> PhiUp; 337de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::vector<NodeId> PhiUQ; // Work list of phis for upward propagation. 338de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 339de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Go over all phis. 340de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<PhiNode*> PhiA : Phis) { 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Go over all defs and collect the reached uses that are non-phi uses 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // (i.e. the "real uses"). 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &RealUses = RealUseMap[PhiA.Id]; 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto PhiRefs = PhiA.Addr->members(DFG); 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Have a work queue of defs whose reached uses need to be found. 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // For each def, add to the queue all reached (non-phi) defs. 348de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SetVector<NodeId> DefQ; 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet PhiDefs; 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : PhiRefs) { 351de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!DFG.IsRef<NodeAttrs::Def>(R)) 352de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 353de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefQ.insert(R.Id); 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PhiDefs.insert(R.Id); 355de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 356de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0; i < DefQ.size(); ++i) { 357de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<DefNode*> DA = DFG.addr<DefNode*>(DefQ[i]); 358de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId UN = DA.Addr->getReachedUse(); 359de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (UN != 0) { 360de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<UseNode*> A = DFG.addr<UseNode*>(UN); 361de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(A.Addr->getFlags() & NodeAttrs::PhiRef)) 362de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RealUses[getRestrictedRegRef(A)].insert(A.Id); 363de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UN = A.Addr->getSibling(); 364de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 365de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId DN = DA.Addr->getReachedDef(); 366de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (DN != 0) { 367de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<DefNode*> A = DFG.addr<DefNode*>(DN); 368de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto T : DFG.getRelatedRefs(A.Addr->getOwner(DFG), A)) { 369de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar uint16_t Flags = NodeAddr<DefNode*>(T).Addr->getFlags(); 370de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Must traverse the reached-def chain. Consider: 371de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // def(D0) -> def(R0) -> def(R0) -> use(D0) 372de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The reachable use of D0 passes through a def of R0. 373de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(Flags & NodeAttrs::PhiRef)) 374de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefQ.insert(T.Id); 375de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 376de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DN = A.Addr->getSibling(); 377de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 378de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 379de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Filter out these uses that appear to be reachable, but really 380de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // are not. For example: 381de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 382de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // R1:0 = d1 383de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // = R1:0 u2 Reached by d1. 384de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // R0 = d3 385de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // = R1:0 u4 Still reached by d1: indirectly through 386de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the def d3. 387de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // R1 = d5 388de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // = R1:0 u6 Not reached by d1 (covered collectively 389de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // by d3 and d5), but following reached 390de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // defs and uses from d1 will lead here. 391de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto HasDef = [&PhiDefs] (NodeAddr<DefNode*> DA) -> bool { 392de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PhiDefs.count(DA.Id); 393de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 394de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto UI = RealUses.begin(), UE = RealUses.end(); UI != UE; ) { 395de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // For each reached register UI->first, there is a set UI->second, of 396de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // uses of it. For each such use, check if it is reached by this phi, 397de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // i.e. check if the set of its reaching uses intersects the set of 398de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // this phi's defs. 399de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &Uses = UI->second; 400de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = Uses.begin(), E = Uses.end(); I != E; ) { 401de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto UA = DFG.addr<UseNode*>(*I); 402de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeList RDs = getAllReachingDefs(UI->first, UA); 403de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (std::any_of(RDs.begin(), RDs.end(), HasDef)) 404de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++I; 405de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 406de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar I = Uses.erase(I); 407de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 408de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Uses.empty()) 409de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UI = RealUses.erase(UI); 410de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 411de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ++UI; 412de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 413de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 414de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // If this phi reaches some "real" uses, add it to the queue for upward 415de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // propagation. 416de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!RealUses.empty()) 417de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PhiUQ.push_back(PhiA.Id); 418de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 419de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Go over all phi uses and check if the reaching def is another phi. 420de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Collect the phis that are among the reaching defs of these uses. 421de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // While traversing the list of reaching defs for each phi use, collect 422de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the set of registers defined between this phi (Phi) and the owner phi 423de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // of the reaching def. 424de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : PhiRefs) { 425de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!DFG.IsRef<NodeAttrs::Use>(I)) 426de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 427de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<UseNode*> UA = I; 428de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &UpMap = PhiUp[UA.Id]; 429de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet DefRRs; 430de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<DefNode*> DA : getAllReachingDefs(UA)) { 431de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (DA.Addr->getFlags() & NodeAttrs::PhiRef) 432de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UpMap[DA.Addr->getOwner(DFG).Id] = DefRRs; 433de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else 434de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DefRRs.insert(DA.Addr->getRegRef()); 435de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 436de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 437de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 438de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 439de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 440de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "Phi-up-to-phi map:\n"; 441de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : PhiUp) { 442de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "phi " << Print<NodeId>(I.first, DFG) << " -> {"; 443de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : I.second) 444de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << ' ' << Print<NodeId>(R.first, DFG) 445de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << Print<RegisterSet>(R.second, DFG); 446de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " }\n"; 447de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 448de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 449de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 450de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Propagate the reached registers up in the phi chain. 451de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 452de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The following type of situation needs careful handling: 453de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 454de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phi d1<R1:0> (1) 455de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // | 456de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // ... d2<R1> 457de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // | 458de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phi u3<R1:0> (2) 459de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // | 460de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // ... u4<R1> 461de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 462de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The phi node (2) defines a register pair R1:0, and reaches a "real" 463de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // use u4 of just R1. The same phi node is also known to reach (upwards) 464de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the phi node (1). However, the use u4 is not reached by phi (1), 465de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // because of the intervening definition d2 of R1. The data flow between 466de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phis (1) and (2) is restricted to R1:0 minus R1, i.e. R0. 467de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 468de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // When propagating uses up the phi chains, get the all reaching defs 469de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for a given phi use, and traverse the list until the propagated ref 470de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // is covered, or until or until reaching the final phi. Only assume 471de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // that the reference reaches the phi in the latter case. 472de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 473de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0; i < PhiUQ.size(); ++i) { 474de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto PA = DFG.addr<PhiNode*>(PhiUQ[i]); 475de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &RealUses = RealUseMap[PA.Id]; 476de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 477de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<UseNode*> UA = U; 478de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &UpPhis = PhiUp[UA.Id]; 479de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto UP : UpPhis) { 480de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 481de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &MidDefs = UP.second; 482de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Collect the set UpReached of uses that are reached by the current 483de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // phi PA, and are not covered by any intervening def between PA and 484de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the upward phi UP. 485de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet UpReached; 486de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto T : RealUses) { 487de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!isRestricted(PA, UA, T.first)) 488de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 489de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!RAI.covers(MidDefs, T.first)) 490de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar UpReached.insert(T.first); 491de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 492de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (UpReached.empty()) 493de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 494de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Update the set PRUs of real uses reached by the upward phi UP with 495de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // the actual set of uses (UpReached) that the UP phi reaches. 496de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &PRUs = RealUseMap[UP.first]; 497de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : UpReached) { 498de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned Z = PRUs[R].size(); 499de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PRUs[R].insert(RealUses[R].begin(), RealUses[R].end()); 500de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= (PRUs[R].size() != Z); 501de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 502de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Changed) 503de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PhiUQ.push_back(UP.first); 504de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 505de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 506de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 507de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 508de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 509de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "Real use map:\n"; 510de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : RealUseMap) { 511de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "phi " << Print<NodeId>(I.first, DFG); 512de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<PhiNode*> PA = DFG.addr<PhiNode*>(I.first); 513de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeList Ds = PA.Addr->members_if(DFG.IsRef<NodeAttrs::Def>, DFG); 514de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Ds.empty()) { 515de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef RR = NodeAddr<DefNode*>(Ds[0]).Addr->getRegRef(); 516de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << '<' << Print<RegisterRef>(RR, DFG) << '>'; 517de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } else { 518de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "<noreg>"; 519de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 520de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " -> " << Print<RefMap>(I.second, DFG) << '\n'; 521de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 522de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 523de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 524de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 525de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 526de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::computeLiveIns() { 527de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Populate the node-to-block map. This speeds up the calculations 528de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // significantly. 529de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NBMap.clear(); 530de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 531de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *BB = BA.Addr->getCode(); 532de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 533de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 534de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NBMap.insert(std::make_pair(RA.Id, BB)); 535de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NBMap.insert(std::make_pair(IA.Id, BB)); 536de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 537de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 538de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 539de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineFunction &MF = DFG.getMF(); 540de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 541de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Compute IDF first, then the inverse. 542de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar decltype(IIDF) IDF; 543de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &B : MF) { 544de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto F1 = MDF.find(&B); 545de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (F1 == MDF.end()) 546de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 547de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar SetVector<MachineBasicBlock*> IDFB(F1->second.begin(), F1->second.end()); 548de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (unsigned i = 0; i < IDFB.size(); ++i) { 549de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto F2 = MDF.find(IDFB[i]); 550de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (F2 != MDF.end()) 551de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IDFB.insert(F2->second.begin(), F2->second.end()); 552de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 553de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add B to the IDF(B). This will put B in the IIDF(B). 554de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IDFB.insert(&B); 555de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IDF[&B].insert(IDFB.begin(), IDFB.end()); 556de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 557de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 558de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : IDF) 559de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : I.second) 560de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IIDF[S].insert(I.first); 561de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 562de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar computePhiInfo(); 563de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 564de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<FuncNode*> FA = DFG.getFunc(); 565de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Blocks = FA.Addr->members(DFG); 566de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 567de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Build the phi live-on-entry map. 568de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<BlockNode*> BA : Blocks) { 569de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *MB = BA.Addr->getCode(); 570de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LON = PhiLON[MB]; 571de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto P : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG)) 572de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : RealUseMap[P.Id]) 573de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LON[S.first].insert(S.second.begin(), S.second.end()); 574de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 575de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 576de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 577de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "Phi live-on-entry map:\n"; 578de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : PhiLON) 579de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "block #" << I.first->getNumber() << " -> " 580de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << Print<RefMap>(I.second, DFG) << '\n'; 581de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 582de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 583de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Build the phi live-on-exit map. Each phi node has some set of reached 584de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // "real" uses. Propagate this set backwards into the block predecessors 585de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // through the reaching defs of the corresponding phi uses. 586de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<BlockNode*> BA : Blocks) { 587de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Phis = BA.Addr->members_if(DFG.IsCode<NodeAttrs::Phi>, DFG); 588de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<PhiNode*> PA : Phis) { 589de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &RUs = RealUseMap[PA.Id]; 590de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RUs.empty()) 591de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 592de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 593de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto U : PA.Addr->members_if(DFG.IsRef<NodeAttrs::Use>, DFG)) { 594de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<PhiUseNode*> UA = U; 595de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (UA.Addr->getReachingDef() == 0) 596de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 597de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 598de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Mark all reached "real" uses of P as live on exit in the 599de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // predecessor. 600de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Remap all the RUs so that they have a correct reaching def. 601de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto PrA = DFG.addr<BlockNode*>(UA.Addr->getPredecessor()); 602de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LOX = PhiLOX[PrA.Addr->getCode()]; 603de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : RUs) { 604de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef RR = R.first; 605de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!isRestricted(PA, UA, RR)) 606de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RR = getRestrictedRegRef(UA); 607de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The restricted ref may be different from the ref that was 608de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // accessed in the "real use". This means that this phi use 609de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // is not the one that carries this reference, so skip it. 610de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!RAI.alias(R.first, RR)) 611de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 612de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto D : getAllReachingDefs(RR, UA)) 613de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LOX[RR].insert(D.Id); 614de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 615de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } // for U : phi uses 616de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } // for P : Phis 617de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } // for B : Blocks 618de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 619de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 620de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "Phi live-on-exit map:\n"; 621de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : PhiLOX) 622de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "block #" << I.first->getNumber() << " -> " 623de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << Print<RefMap>(I.second, DFG) << '\n'; 624de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 625de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 626de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RefMap LiveIn; 627de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar traverse(&MF.front(), LiveIn); 628de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 629de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add function live-ins to the live-in set of the function entry block. 630de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &EntryIn = LiveMap[&MF.front()]; 631de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = MRI.livein_begin(), E = MRI.livein_end(); I != E; ++I) 632de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar EntryIn.insert({I->first,0}); 633de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 634de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 635de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Dump the liveness map 636de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &B : MF) { 637de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BitVector LV(TRI.getNumRegs()); 638de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 639de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LV.set(I->PhysReg); 640de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "BB#" << B.getNumber() << "\t rec = {"; 641de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (int x = LV.find_first(); x >= 0; x = LV.find_next(x)) 642de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << ' ' << Print<RegisterRef>({unsigned(x),0}, DFG); 643de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " }\n"; 644de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "\tcomp = " << Print<RegisterSet>(LiveMap[&B], DFG) << '\n'; 645de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 646de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 647de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 648de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 649de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 650de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::resetLiveIns() { 651de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &B : DFG.getMF()) { 652de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Remove all live-ins. 653de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar std::vector<unsigned> T; 654de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = B.livein_begin(), E = B.livein_end(); I != E; ++I) 655de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar T.push_back(I->PhysReg); 656de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : T) 657de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar B.removeLiveIn(I); 658de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add the newly computed live-ins. 659de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LiveIns = LiveMap[&B]; 660de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : LiveIns) { 661de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(I.Sub == 0); 662de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar B.addLiveIn(I.Reg); 663de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 664de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 665de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 666de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 667de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 668de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::resetKills() { 669de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &B : DFG.getMF()) 670de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar resetKills(&B); 671de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 672de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 673de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 674de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::resetKills(MachineBasicBlock *B) { 675de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto CopyLiveIns = [] (MachineBasicBlock *B, BitVector &LV) -> void { 676de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = B->livein_begin(), E = B->livein_end(); I != E; ++I) 677de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LV.set(I->PhysReg); 678de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }; 679de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 680de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar BitVector LiveIn(TRI.getNumRegs()), Live(TRI.getNumRegs()); 681de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CopyLiveIns(B, LiveIn); 682de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto SI : B->successors()) 683de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar CopyLiveIns(SI, Live); 684de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 685de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = B->rbegin(), E = B->rend(); I != E; ++I) { 686de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineInstr *MI = &*I; 687de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (MI->isDebugValue()) 688de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 689de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 690de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MI->clearKillInfo(); 691de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &Op : MI->operands()) { 692de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // An implicit def of a super-register may not necessarily start a 693de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // live range of it, since an implicit use could be used to keep parts 694de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // of it live. Instead of analyzing the implicit operands, ignore 695de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // implicit defs. 696de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Op.isReg() || !Op.isDef() || Op.isImplicit()) 697de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 698de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned R = Op.getReg(); 699de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!TargetRegisterInfo::isPhysicalRegister(R)) 700de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 701de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 702de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Live.reset(*SR); 703de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 704de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &Op : MI->operands()) { 705de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Op.isReg() || !Op.isUse()) 706de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 707de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar unsigned R = Op.getReg(); 708de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!TargetRegisterInfo::isPhysicalRegister(R)) 709de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 710de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool IsLive = false; 711de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (MCRegAliasIterator AR(R, &TRI, true); AR.isValid(); ++AR) { 712de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Live[*AR]) 713de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 714de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar IsLive = true; 715de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 716de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 717de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (IsLive) 718de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 719de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Op.setIsKill(true); 720de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (MCSubRegIterator SR(R, &TRI, true); SR.isValid(); ++SR) 721de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Live.set(*SR); 722de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 723de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 724de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 725de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 726de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 727de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// For shadows, determine if RR is aliased to a reaching def of any other 728de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// shadow associated with RA. If it is not, then RR is "restricted" to RA, 729de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// and so it can be considered a value specific to RA. This is important 730de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// for accurately determining values associated with phi uses. 731de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// For non-shadows, this function returns "true". 732de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool Liveness::isRestricted(NodeAddr<InstrNode*> IA, NodeAddr<RefNode*> RA, 733de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef RR) const { 734de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId Start = RA.Id; 735de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<RefNode*> TA = DFG.getNextShadow(IA, RA); 736de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar TA.Id != 0 && TA.Id != Start; TA = DFG.getNextShadow(IA, TA)) { 737de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId RD = TA.Addr->getReachingDef(); 738de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RD == 0) 739de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 740de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.alias(RR, DFG.addr<DefNode*>(RD).Addr->getRegRef())) 741de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return false; 742de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 743de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return true; 744de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 745de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 746de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 747de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarRegisterRef Liveness::getRestrictedRegRef(NodeAddr<RefNode*> RA) const { 748de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(DFG.IsRef<NodeAttrs::Use>(RA)); 749de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RA.Addr->getFlags() & NodeAttrs::Shadow) { 750de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId RD = RA.Addr->getReachingDef(); 751de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar assert(RD); 752de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RA = DFG.addr<DefNode*>(RD); 753de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 754de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return RA.Addr->getRegRef(); 755de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 756de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 757de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 758de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarunsigned Liveness::getPhysReg(RegisterRef RR) const { 759de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!TargetRegisterInfo::isPhysicalRegister(RR.Reg)) 760de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return 0; 761de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return RR.Sub ? TRI.getSubReg(RR.Reg, RR.Sub) : RR.Reg; 762de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 763de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 764de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 765de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// Helper function to obtain the basic block containing the reaching def 766de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar// of the given use. 767de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarMachineBasicBlock *Liveness::getBlockWithRef(NodeId RN) const { 768de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto F = NBMap.find(RN); 769de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (F != NBMap.end()) 770de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return F->second; 771de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar llvm_unreachable("Node id not in map"); 772de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 773de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 774de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 775de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::traverse(MachineBasicBlock *B, RefMap &LiveIn) { 776de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The LiveIn map, for each (physical) register, contains the set of live 777de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // reaching defs of that register that are live on entry to the associated 778de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // block. 779de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 780de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // The summary of the traversal algorithm: 781de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 782de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // R is live-in in B, if there exists a U(R), such that rdef(R) dom B 783de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // and (U \in IDF(B) or B dom U). 784de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 785de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for (C : children) { 786de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // LU = {} 787de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // traverse(C, LU) 788de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // LiveUses += LU 789de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // } 790de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 791de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // LiveUses -= Defs(B); 792de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // LiveUses += UpwardExposedUses(B); 793de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for (C : IIDF[B]) 794de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // for (U : LiveUses) 795de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // if (Rdef(U) dom C) 796de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // C.addLiveIn(U) 797de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // 798de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 799de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Go up the dominator tree (depth-first). 800de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineDomTreeNode *N = MDT.getNode(B); 801de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : *N) { 802de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RefMap L; 803de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar MachineBasicBlock *SB = I->getBlock(); 804de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar traverse(SB, L); 805de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 806de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : L) 807de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveIn[S.first].insert(S.second.begin(), S.second.end()); 808de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 809de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 810de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 811de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << LLVM_FUNCTION_NAME << " in BB#" << B->getNumber() 812de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar << " after recursion into"; 813de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : *N) 814de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << ' ' << I->getBlock()->getNumber(); 815de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "\n LiveIn: " << Print<RefMap>(LiveIn, DFG); 816de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "\n Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 817de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 818de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 819de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Add phi uses that are live on exit from this block. 820de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RefMap &PUs = PhiLOX[B]; 821de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : PUs) 822de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveIn[S.first].insert(S.second.begin(), S.second.end()); 823de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 824de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 825de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "after LOX\n"; 826de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 827de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 828de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 829de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 830de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Stop tracking all uses defined in this block: erase those records 831de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // where the reaching def is located in B and which cover all reached 832de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // uses. 833de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto Copy = LiveIn; 834de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveIn.clear(); 835de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 836de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : Copy) { 837de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &Defs = LiveIn[I.first]; 838de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeSet Rest; 839de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : I.second) { 840de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DA = DFG.addr<DefNode*>(R); 841de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef DDR = DA.Addr->getRegRef(); 842de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); 843de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 844de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Defs from a different block need to be preserved. Defs from this 845de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // block will need to be processed further, except for phi defs, the 846de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // liveness of which is handled through the PhiLON/PhiLOX maps. 847de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (B != BA.Addr->getCode()) 848de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Defs.insert(R); 849de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar else { 850de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool IsPreserving = DA.Addr->getFlags() & NodeAttrs::Preserving; 851de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (IA.Addr->getKind() != NodeAttrs::Phi && !IsPreserving) { 852de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Covering = RAI.covers(DDR, I.first); 853de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeId U = DA.Addr->getReachedUse(); 854de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar while (U && Covering) { 855de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DUA = DFG.addr<UseNode*>(U); 856de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef Q = DUA.Addr->getRegRef(); 857de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Covering = RAI.covers(DA.Addr->getRegRef(), Q); 858de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar U = DUA.Addr->getSibling(); 859de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 860de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!Covering) 861de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Rest.insert(R); 862de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 863de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 864de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 865de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 866de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Non-covering defs from B. 867de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : Rest) { 868de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto DA = DFG.addr<DefNode*>(R); 869de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef DRR = DA.Addr->getRegRef(); 870de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterSet RRs; 871de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<DefNode*> TA : getAllReachingDefs(DA)) { 872de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<InstrNode*> IA = TA.Addr->getOwner(DFG); 873de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 874de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Preserving defs do not count towards covering. 875de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!(TA.Addr->getFlags() & NodeAttrs::Preserving)) 876de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RRs.insert(TA.Addr->getRegRef()); 877de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (BA.Addr->getCode() == B) 878de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 879de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (RAI.covers(RRs, DRR)) 880de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar break; 881de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Defs.insert(TA.Id); 882de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 883de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 884de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 885de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 886de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar emptify(LiveIn); 887de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 888de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 889de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "after defs in block\n"; 890de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 891de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 892de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 893de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 894de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Scan the block for upward-exposed uses and add them to the tracking set. 895de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I : DFG.getFunc().Addr->findBlock(B, DFG).Addr->members(DFG)) { 896de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar NodeAddr<InstrNode*> IA = I; 897de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (IA.Addr->getKind() != NodeAttrs::Stmt) 898de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar continue; 899de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { 900de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar RegisterRef RR = UA.Addr->getRegRef(); 901de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto D : getAllReachingDefs(UA)) 902de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (getBlockWithRef(D.Id) != B) 903de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveIn[RR].insert(D.Id); 904de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 905de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 906de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 907de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 908de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "after uses in block\n"; 909de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 910de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " Local: " << Print<RegisterSet>(LiveMap[B], DFG) << '\n'; 911de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 912de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 913de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // Phi uses should not be propagated up the dominator tree, since they 914de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // are not dominated by their corresponding reaching defs. 915de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &Local = LiveMap[B]; 916de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LON = PhiLON[B]; 917de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : LON) 918de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Local.insert(R.first); 919de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 920de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Trace) { 921de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << "after phi uses in block\n"; 922de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " LiveIn: " << Print<RefMap>(LiveIn, DFG) << '\n'; 923de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar dbgs() << " Local: " << Print<RegisterSet>(Local, DFG) << '\n'; 924de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 925de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 926de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto C : IIDF[B]) { 927de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LiveC = LiveMap[C]; 928de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto S : LiveIn) 929de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto R : S.second) 930de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (MDT.properlyDominates(getBlockWithRef(R), C)) 931de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LiveC.insert(S.first); 932de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 933de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 934de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 935de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 936de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid Liveness::emptify(RefMap &M) { 937de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto I = M.begin(), E = M.end(); I != E; ) 938de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar I = I->second.empty() ? M.erase(I) : std::next(I); 939de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 940de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 941