Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/LiveRangeCalc.h @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents afa8332a0e37
children 803732b1fca8
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
20 //===----------------------------------------------------------------------===// 20 //===----------------------------------------------------------------------===//
21 21
22 #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H 22 #ifndef LLVM_LIB_CODEGEN_LIVERANGECALC_H
23 #define LLVM_LIB_CODEGEN_LIVERANGECALC_H 23 #define LLVM_LIB_CODEGEN_LIVERANGECALC_H
24 24
25 #include "llvm/ADT/ArrayRef.h"
25 #include "llvm/ADT/BitVector.h" 26 #include "llvm/ADT/BitVector.h"
26 #include "llvm/ADT/IndexedMap.h" 27 #include "llvm/ADT/IndexedMap.h"
27 #include "llvm/CodeGen/LiveInterval.h" 28 #include "llvm/CodeGen/LiveInterval.h"
28 29
29 namespace llvm { 30 namespace llvm {
50 /// Bit vector of active entries in LiveOut, also used as a visited set by 51 /// Bit vector of active entries in LiveOut, also used as a visited set by
51 /// findReachingDefs. One entry per basic block, indexed by block number. 52 /// findReachingDefs. One entry per basic block, indexed by block number.
52 /// This is kept as a separate bit vector because it can be cleared quickly 53 /// This is kept as a separate bit vector because it can be cleared quickly
53 /// when switching live ranges. 54 /// when switching live ranges.
54 BitVector Seen; 55 BitVector Seen;
56
57 /// Map LiveRange to sets of blocks (represented by bit vectors) that
58 /// in the live range are defined on entry and undefined on entry.
59 /// A block is defined on entry if there is a path from at least one of
60 /// the defs in the live range to the entry of the block, and conversely,
61 /// a block is undefined on entry, if there is no such path (i.e. no
62 /// definition reaches the entry of the block). A single LiveRangeCalc
63 /// object is used to track live-out information for multiple registers
64 /// in live range splitting (which is ok, since the live ranges of these
65 /// registers do not overlap), but the defined/undefined information must
66 /// be kept separate for each individual range.
67 /// By convention, EntryInfoMap[&LR] = { Defined, Undefined }.
68 std::map<LiveRange*,std::pair<BitVector,BitVector>> EntryInfoMap;
55 69
56 /// Map each basic block where a live range is live out to the live-out value 70 /// Map each basic block where a live range is live out to the live-out value
57 /// and its defining block. 71 /// and its defining block.
58 /// 72 ///
59 /// For every basic block, MBB, one of these conditions shall be true: 73 /// For every basic block, MBB, one of these conditions shall be true:
99 /// determined. This list is typically computed by findReachingDefs() and 113 /// determined. This list is typically computed by findReachingDefs() and
100 /// used as a work list by updateSSA(). The low-level interface may also be 114 /// used as a work list by updateSSA(). The low-level interface may also be
101 /// used to add entries directly. 115 /// used to add entries directly.
102 SmallVector<LiveInBlock, 16> LiveIn; 116 SmallVector<LiveInBlock, 16> LiveIn;
103 117
104 /// Assuming that @p LR is live-in to @p UseMBB, find the set of defs that can 118 /// Check if the entry to block @p MBB can be reached by any of the defs
105 /// reach it. 119 /// in @p LR. Return true if none of the defs reach the entry to @p MBB.
106 /// 120 bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
107 /// If only one def can reach @p UseMBB, all paths from the def to @p UseMBB 121 MachineBasicBlock &MBB, BitVector &DefOnEntry,
108 /// are added to @p LR, and the function returns true. 122 BitVector &UndefOnEntry);
123
124 /// Find the set of defs that can reach @p Kill. @p Kill must belong to
125 /// @p UseMBB.
126 ///
127 /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill,
128 /// all paths from the def to @p UseMBB are added to @p LR, and the function
129 /// returns true.
109 /// 130 ///
110 /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be 131 /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be
111 /// live in are added to the LiveIn array, and the function returns false. 132 /// live in are added to the LiveIn array, and the function returns false.
112 /// 133 ///
134 /// The array @p Undef provides the locations where the range @p LR becomes
135 /// undefined by <def,read-undef> operands on other subranges. If @p Undef
136 /// is non-empty and @p Kill is jointly dominated only by the entries of
137 /// @p Undef, the function returns false.
138 ///
113 /// PhysReg, when set, is used to verify live-in lists on basic blocks. 139 /// PhysReg, when set, is used to verify live-in lists on basic blocks.
114 bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, 140 bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
115 SlotIndex Kill, unsigned PhysReg); 141 SlotIndex Kill, unsigned PhysReg,
142 ArrayRef<SlotIndex> Undefs);
116 143
117 /// updateSSA - Compute the values that will be live in to all requested 144 /// updateSSA - Compute the values that will be live in to all requested
118 /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form. 145 /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form.
119 /// 146 ///
120 /// Every live-in block must be jointly dominated by the added live-out 147 /// Every live-in block must be jointly dominated by the added live-out
125 /// the given @p LiveOuts. 152 /// the given @p LiveOuts.
126 void updateFromLiveIns(); 153 void updateFromLiveIns();
127 154
128 /// Extend the live range of @p LR to reach all uses of Reg. 155 /// Extend the live range of @p LR to reach all uses of Reg.
129 /// 156 ///
130 /// All uses must be jointly dominated by existing liveness. PHI-defs are 157 /// If @p LR is a main range, or if @p LI is null, then all uses must be
131 /// inserted as needed to preserve SSA form. 158 /// jointly dominated by the definitions from @p LR. If @p LR is a subrange
132 void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask); 159 /// of the live interval @p LI, corresponding to lane mask @p LaneMask,
160 /// all uses must be jointly dominated by the definitions from @p LR
161 /// together with definitions of other lanes where @p LR becomes undefined
162 /// (via <def,read-undef> operands).
163 /// If @p LR is a main range, the @p LaneMask should be set to ~0.
164 void extendToUses(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask,
165 LiveInterval *LI = nullptr);
133 166
134 /// Reset Map and Seen fields. 167 /// Reset Map and Seen fields.
135 void resetLiveOutMap(); 168 void resetLiveOutMap();
136 169
137 public: 170 public:
167 /// The existing values in @p LR must be live so they jointly dominate @p Use. 200 /// The existing values in @p LR must be live so they jointly dominate @p Use.
168 /// If @p Use is not dominated by a single existing value, PHI-defs are 201 /// If @p Use is not dominated by a single existing value, PHI-defs are
169 /// inserted as required to preserve SSA form. 202 /// inserted as required to preserve SSA form.
170 /// 203 ///
171 /// PhysReg, when set, is used to verify live-in lists on basic blocks. 204 /// PhysReg, when set, is used to verify live-in lists on basic blocks.
172 void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg = 0); 205 void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
206 ArrayRef<SlotIndex> Undefs);
173 207
174 /// createDeadDefs - Create a dead def in LI for every def operand of Reg. 208 /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
175 /// Each instruction defining Reg gets a new VNInfo with a corresponding 209 /// Each instruction defining Reg gets a new VNInfo with a corresponding
176 /// minimal live range. 210 /// minimal live range.
177 void createDeadDefs(LiveRange &LR, unsigned Reg); 211 void createDeadDefs(LiveRange &LR, unsigned Reg);
186 220
187 /// Calculates liveness for the register specified in live interval @p LI. 221 /// Calculates liveness for the register specified in live interval @p LI.
188 /// Creates subregister live ranges as needed if subreg liveness tracking is 222 /// Creates subregister live ranges as needed if subreg liveness tracking is
189 /// enabled. 223 /// enabled.
190 void calculate(LiveInterval &LI, bool TrackSubRegs); 224 void calculate(LiveInterval &LI, bool TrackSubRegs);
225
226 /// For live interval \p LI with correct SubRanges construct matching
227 /// information for the main live range. Expects the main live range to not
228 /// have any segments or value numbers.
229 void constructMainRangeFromSubranges(LiveInterval &LI);
191 230
192 //===--------------------------------------------------------------------===// 231 //===--------------------------------------------------------------------===//
193 // Low-level interface. 232 // Low-level interface.
194 //===--------------------------------------------------------------------===// 233 //===--------------------------------------------------------------------===//
195 // 234 //