X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveRangeCalc.h;h=1b9099b5fc7e7a05b127ab39e8ae38ccc51d4a15;hb=6de0a12927845ca49cd5cb1da9206fe503b565ec;hp=55e67bb144511df45a3de373d6fc555baf54df46;hpb=b5a457c4cbc71db6ae313ef1bf8eadac65767ab0;p=oota-llvm.git diff --git a/lib/CodeGen/LiveRangeCalc.h b/lib/CodeGen/LiveRangeCalc.h index 55e67bb1445..1b9099b5fc7 100644 --- a/lib/CodeGen/LiveRangeCalc.h +++ b/lib/CodeGen/LiveRangeCalc.h @@ -19,8 +19,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CODEGEN_LIVERANGECALC_H -#define LLVM_CODEGEN_LIVERANGECALC_H +#ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H +#define LLVM_LIB_CODEGEN_LIVERANGECALC_H #include "llvm/ADT/BitVector.h" #include "llvm/ADT/IndexedMap.h" @@ -34,11 +34,11 @@ template class DomTreeNodeBase; typedef DomTreeNodeBase MachineDomTreeNode; class LiveRangeCalc { - /// Seen - Bit vector of active entries in LiveOut, also used as a visited - /// set by findReachingDefs. One entry per basic block, indexed by block - /// number. This is kept as a separate bit vector because it can be cleared - /// quickly when switching live ranges. - BitVector Seen; + const MachineFunction *MF; + const MachineRegisterInfo *MRI; + SlotIndexes *Indexes; + MachineDominatorTree *DomTree; + VNInfo::Allocator *Alloc; /// LiveOutPair - A value and the block that defined it. The domtree node is /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)]. @@ -47,8 +47,14 @@ class LiveRangeCalc { /// LiveOutMap - Map basic blocks to the value leaving the block. typedef IndexedMap LiveOutMap; - /// LiveOut - Map each basic block where a live range is live out to the - /// live-out value and its defining block. + /// Bit vector of active entries in LiveOut, also used as a visited set by + /// findReachingDefs. One entry per basic block, indexed by block number. + /// This is kept as a separate bit vector because it can be cleared quickly + /// when switching live ranges. + BitVector Seen; + + /// Map each basic block where a live range is live out to the live-out value + /// and its defining block. /// /// For every basic block, MBB, one of these conditions shall be true: /// @@ -64,14 +70,14 @@ class LiveRangeCalc { /// /// The map can be shared by multiple live ranges as long as no two are /// live-out of the same block. - LiveOutMap LiveOut; + LiveOutMap Map; /// LiveInBlock - Information about a basic block where a live range is known /// to be live-in, but the value has not yet been determined. struct LiveInBlock { - // LI - The live range that is live-in to this block. The algorithms can + // The live range set that is live-in to this block. The algorithms can // handle multiple non-overlapping live ranges simultaneously. - LiveInterval *LI; + LiveRange &LR; // DomNode - Dominator tree node for the block. // Cleared when the final value has been determined and LI has been updated. @@ -85,8 +91,8 @@ class LiveRangeCalc { // Live-in value filled in by updateSSA once it is known. VNInfo *Value; - LiveInBlock(LiveInterval *li, MachineDomTreeNode *node, SlotIndex kill) - : LI(li), DomNode(node), Kill(kill), Value(0) {} + LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill) + : LR(LR), DomNode(node), Kill(kill), Value(nullptr) {} }; /// LiveIn - Work list of blocks where the live-in value has yet to be @@ -95,31 +101,43 @@ class LiveRangeCalc { /// used to add entries directly. SmallVector LiveIn; - /// findReachingDefs - Assuming that LI is live-in to KillMBB and killed at - /// Kill, search for values that can reach KillMBB. All blocks that need LI - /// to be live-in are added to LiveIn. If a unique reaching def is found, - /// its value is returned, if Kill is jointly dominated by multiple values, - /// NULL is returned. - VNInfo *findReachingDefs(LiveInterval *LI, - MachineBasicBlock *KillMBB, - SlotIndex Kill, - SlotIndexes *Indexes, - MachineDominatorTree *DomTree); + /// Assuming that LI is live-in to KillMBB and killed at Kill, find the set + /// of defs that can reach it. + /// + /// If only one def can reach Kill, all paths from the def to kill are added + /// to LI, and the function returns true. + /// + /// If multiple values can reach Kill, the blocks that need LI to be live in + /// are added to the LiveIn array, and the function returns false. + /// + /// PhysReg, when set, is used to verify live-in lists on basic blocks. + bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB, + SlotIndex Kill, unsigned PhysReg); /// updateSSA - Compute the values that will be live in to all requested /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. /// /// Every live-in block must be jointly dominated by the added live-out /// blocks. No values are read from the live ranges. - void updateSSA(SlotIndexes *Indexes, - MachineDominatorTree *DomTree, - VNInfo::Allocator *Alloc); + void updateSSA(); - /// updateLiveIns - Add liveness as specified in the LiveIn vector, using VNI - /// as a wildcard value for LiveIn entries without a value. - void updateLiveIns(VNInfo *VNI, SlotIndexes*); + /// Transfer information from the LiveIn vector to the live ranges and update + /// the given @p LiveOuts. + void updateFromLiveIns(); + + /// Extend the live range of @p LR to reach all uses of Reg. + /// + /// All uses must be jointly dominated by existing liveness. PHI-defs are + /// inserted as needed to preserve SSA form. + void extendToUses(LiveRange &LR, unsigned Reg, unsigned LaneMask); + + /// Reset Map and Seen fields. + void resetLiveOutMap(); public: + LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr), + DomTree(nullptr), Alloc(nullptr) {} + //===--------------------------------------------------------------------===// // High-level interface. //===--------------------------------------------------------------------===// @@ -132,14 +150,10 @@ public: /// that may overlap a previously computed live range, and before the first /// live range in a function. If live ranges are not known to be /// non-overlapping, call reset before each. - void reset(const MachineFunction *MF); - - /// calculate - Calculate the live range of a virtual register from its defs - /// and uses. LI must be empty with no values. - void calculate(LiveInterval *LI, - MachineRegisterInfo *MRI, - SlotIndexes *Indexes, - VNInfo::Allocator *Alloc); + void reset(const MachineFunction *MF, + SlotIndexes*, + MachineDominatorTree*, + VNInfo::Allocator*); //===--------------------------------------------------------------------===// // Mid-level interface. @@ -154,21 +168,27 @@ public: /// Kill is not dominated by a single existing value, PHI-defs are inserted /// as required to preserve SSA form. If Kill is known to be dominated by a /// single existing value, Alloc may be null. - void extend(LiveInterval *LI, - SlotIndex Kill, - SlotIndexes *Indexes, - MachineDominatorTree *DomTree, - VNInfo::Allocator *Alloc); + /// + /// PhysReg, when set, is used to verify live-in lists on basic blocks. + void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0); + + /// createDeadDefs - Create a dead def in LI for every def operand of Reg. + /// Each instruction defining Reg gets a new VNInfo with a corresponding + /// minimal live range. + void createDeadDefs(LiveRange &LR, unsigned Reg); - /// extendToUses - Extend the live range of LI to reach all uses. + /// Extend the live range of @p LR to reach all uses of Reg. /// /// All uses must be jointly dominated by existing liveness. PHI-defs are /// inserted as needed to preserve SSA form. - void extendToUses(LiveInterval *LI, - MachineRegisterInfo *MRI, - SlotIndexes *Indexes, - MachineDominatorTree *DomTree, - VNInfo::Allocator *Alloc); + void extendToUses(LiveRange &LR, unsigned PhysReg) { + extendToUses(LR, PhysReg, ~0u); + } + + /// Calculates liveness for the register specified in live interval @p LI. + /// Creates subregister live ranges as needed if subreg liveness tracking is + /// enabled. + void calculate(LiveInterval &LI); //===--------------------------------------------------------------------===// // Low-level interface. @@ -191,22 +211,22 @@ public: /// addLiveInBlock(). void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) { Seen.set(MBB->getNumber()); - LiveOut[MBB] = LiveOutPair(VNI, 0); + Map[MBB] = LiveOutPair(VNI, nullptr); } /// addLiveInBlock - Add a block with an unknown live-in value. This /// function can only be called once per basic block. Once the live-in value /// has been determined, calculateValues() will add liveness to LI. /// - /// @param LI The live range that is live-in to the block. + /// @param LR The live range that is live-in to the block. /// @param DomNode The domtree node for the block. /// @param Kill Index in block where LI is killed. If the value is /// live-through, set Kill = SLotIndex() and also call /// setLiveOutValue(MBB, 0). - void addLiveInBlock(LiveInterval *LI, + void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill = SlotIndex()) { - LiveIn.push_back(LiveInBlock(LI, DomNode, Kill)); + LiveIn.push_back(LiveInBlock(LR, DomNode, Kill)); } /// calculateValues - Calculate the value that will be live-in to each block @@ -216,9 +236,7 @@ public: /// /// Every predecessor of a live-in block must have been given a value with /// setLiveOutValue, the value may be null for live-trough blocks. - void calculateValues(SlotIndexes *Indexes, - MachineDominatorTree *DomTree, - VNInfo::Allocator *Alloc); + void calculateValues(); }; } // end namespace llvm