/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/Hexagon/BitTracker.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- BitTracker.h ---------------------------------------------*- C++ -*-===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | |
10 | | #ifndef LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H |
11 | | #define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H |
12 | | |
13 | | #include "llvm/ADT/DenseSet.h" |
14 | | #include "llvm/ADT/SetVector.h" |
15 | | #include "llvm/ADT/SmallVector.h" |
16 | | #include "llvm/CodeGen/MachineOperand.h" |
17 | | #include <cassert> |
18 | | #include <cstdint> |
19 | | #include <map> |
20 | | #include <queue> |
21 | | #include <set> |
22 | | #include <utility> |
23 | | |
24 | | namespace llvm { |
25 | | |
26 | | class ConstantInt; |
27 | | class MachineRegisterInfo; |
28 | | class MachineBasicBlock; |
29 | | class MachineFunction; |
30 | | class MachineInstr; |
31 | | class raw_ostream; |
32 | | class TargetRegisterClass; |
33 | | class TargetRegisterInfo; |
34 | | |
35 | | struct BitTracker { |
36 | | struct BitRef; |
37 | | struct RegisterRef; |
38 | | struct BitValue; |
39 | | struct BitMask; |
40 | | struct RegisterCell; |
41 | | struct MachineEvaluator; |
42 | | |
43 | | using BranchTargetList = SetVector<const MachineBasicBlock *>; |
44 | | using CellMapType = std::map<unsigned, RegisterCell>; |
45 | | |
46 | | BitTracker(const MachineEvaluator &E, MachineFunction &F); |
47 | | ~BitTracker(); |
48 | | |
49 | | void run(); |
50 | 860 | void trace(bool On = false) { Trace = On; } |
51 | | bool has(unsigned Reg) const; |
52 | | const RegisterCell &lookup(unsigned Reg) const; |
53 | | RegisterCell get(RegisterRef RR) const; |
54 | | void put(RegisterRef RR, const RegisterCell &RC); |
55 | | void subst(RegisterRef OldRR, RegisterRef NewRR); |
56 | | bool reached(const MachineBasicBlock *B) const; |
57 | | void visit(const MachineInstr &MI); |
58 | | |
59 | | void print_cells(raw_ostream &OS) const; |
60 | | |
61 | | private: |
62 | | void visitPHI(const MachineInstr &PI); |
63 | | void visitNonBranch(const MachineInstr &MI); |
64 | | void visitBranchesFrom(const MachineInstr &BI); |
65 | | void visitUsesOf(unsigned Reg); |
66 | | void reset(); |
67 | | |
68 | | using CFGEdge = std::pair<int, int>; |
69 | | using EdgeSetType = std::set<CFGEdge>; |
70 | | using InstrSetType = std::set<const MachineInstr *>; |
71 | | using EdgeQueueType = std::queue<CFGEdge>; |
72 | | |
73 | | EdgeSetType EdgeExec; // Executable flow graph edges. |
74 | | InstrSetType InstrExec; // Executable instructions. |
75 | | EdgeQueueType FlowQ; // Work queue of CFG edges. |
76 | | DenseSet<unsigned> ReachedBB; // Cache of reached blocks. |
77 | | bool Trace; // Enable tracing for debugging. |
78 | | |
79 | | const MachineEvaluator &ME; |
80 | | MachineFunction &MF; |
81 | | MachineRegisterInfo &MRI; |
82 | | CellMapType ⤅ |
83 | | }; |
84 | | |
85 | | // Abstraction of a reference to bit at position Pos from a register Reg. |
86 | | struct BitTracker::BitRef { |
87 | 18.0M | BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {} |
88 | | |
89 | 1.69M | bool operator== (const BitRef &BR) const { |
90 | 1.69M | // If Reg is 0, disregard Pos. |
91 | 457k | return Reg == BR.Reg && (Reg == 0 || 457k Pos == BR.Pos457k ); |
92 | 1.69M | } |
93 | | |
94 | | unsigned Reg; |
95 | | uint16_t Pos; |
96 | | }; |
97 | | |
98 | | // Abstraction of a register reference in MachineOperand. It contains the |
99 | | // register number and the subregister index. |
100 | | struct BitTracker::RegisterRef { |
101 | | RegisterRef(unsigned R = 0, unsigned S = 0) |
102 | 667k | : Reg(R), Sub(S) {} |
103 | | RegisterRef(const MachineOperand &MO) |
104 | 222k | : Reg(MO.getReg()), Sub(MO.getSubReg()) {} |
105 | | |
106 | | unsigned Reg, Sub; |
107 | | }; |
108 | | |
109 | | // Value that a single bit can take. This is outside of the context of |
110 | | // any register, it is more of an abstraction of the two-element set of |
111 | | // possible bit values. One extension here is the "Ref" type, which |
112 | | // indicates that this bit takes the same value as the bit described by |
113 | | // RefInfo. |
114 | | struct BitTracker::BitValue { |
115 | | enum ValueType { |
116 | | Top, // Bit not yet defined. |
117 | | Zero, // Bit = 0. |
118 | | One, // Bit = 1. |
119 | | Ref // Bit value same as the one described in RefI. |
120 | | // Conceptually, there is no explicit "bottom" value: the lattice's |
121 | | // bottom will be expressed as a "ref to itself", which, in the context |
122 | | // of registers, could be read as "this value of this bit is defined by |
123 | | // this bit". |
124 | | // The ordering is: |
125 | | // x <= Top, |
126 | | // Self <= x, where "Self" is "ref to itself". |
127 | | // This makes the value lattice different for each virtual register |
128 | | // (even for each bit in the same virtual register), since the "bottom" |
129 | | // for one register will be a simple "ref" for another register. |
130 | | // Since we do not store the "Self" bit and register number, the meet |
131 | | // operation will need to take it as a parameter. |
132 | | // |
133 | | // In practice there is a special case for values that are not associa- |
134 | | // ted with any specific virtual register. An example would be a value |
135 | | // corresponding to a bit of a physical register, or an intermediate |
136 | | // value obtained in some computation (such as instruction evaluation). |
137 | | // Such cases are identical to the usual Ref type, but the register |
138 | | // number is 0. In such case the Pos field of the reference is ignored. |
139 | | // |
140 | | // What is worthy of notice is that in value V (that is a "ref"), as long |
141 | | // as the RefI.Reg is not 0, it may actually be the same register as the |
142 | | // one in which V will be contained. If the RefI.Pos refers to the posi- |
143 | | // tion of V, then V is assumed to be "bottom" (as a "ref to itself"), |
144 | | // otherwise V is taken to be identical to the referenced bit of the |
145 | | // same register. |
146 | | // If RefI.Reg is 0, however, such a reference to the same register is |
147 | | // not possible. Any value V that is a "ref", and whose RefI.Reg is 0 |
148 | | // is treated as "bottom". |
149 | | }; |
150 | | ValueType Type; |
151 | | BitRef RefI; |
152 | | |
153 | 5.78M | BitValue(ValueType T = Top) : Type(T) {} |
154 | 238k | BitValue(bool B) : Type(B ? One : Zero) {} |
155 | 5.88M | BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {} |
156 | | |
157 | 3.13M | bool operator== (const BitValue &V) const { |
158 | 3.13M | if (Type != V.Type) |
159 | 1.44M | return false; |
160 | 1.69M | if (1.69M Type == Ref && 1.69M !(RefI == V.RefI)1.47M ) |
161 | 1.04M | return false; |
162 | 647k | return true; |
163 | 3.13M | } |
164 | 1.15M | bool operator!= (const BitValue &V) const { |
165 | 1.15M | return !operator==(V); |
166 | 1.15M | } |
167 | | |
168 | 2.67M | bool is(unsigned T) const { |
169 | 2.67M | assert(T == 0 || T == 1); |
170 | 2.39M | return T == 0 ? Type == Zero |
171 | 273k | : (T == 1 ? 273k Type == One273k : false0 ); |
172 | 2.67M | } |
173 | | |
174 | | // The "meet" operation is the "." operation in a semilattice (L, ., T, B): |
175 | | // (1) x.x = x |
176 | | // (2) x.y = y.x |
177 | | // (3) x.(y.z) = (x.y).z |
178 | | // (4) x.T = x (i.e. T = "top") |
179 | | // (5) x.B = B (i.e. B = "bottom") |
180 | | // |
181 | | // This "meet" function will update the value of the "*this" object with |
182 | | // the newly calculated one, and return "true" if the value of *this has |
183 | | // changed, and "false" otherwise. |
184 | | // To prove that it satisfies the conditions (1)-(5), it is sufficient |
185 | | // to show that a relation |
186 | | // x <= y <=> x.y = x |
187 | | // defines a partial order (i.e. that "meet" is same as "infimum"). |
188 | 436k | bool meet(const BitValue &V, const BitRef &Self) { |
189 | 436k | // First, check the cases where there is nothing to be done. |
190 | 436k | if (Type == Ref && 436k RefI == Self224k ) // Bottom.meet(V) = Bottom (i.e. This) |
191 | 5.90k | return false; |
192 | 430k | if (430k V.Type == Top430k ) // This.meet(Top) = This |
193 | 0 | return false; |
194 | 430k | if (430k *this == V430k ) // This.meet(This) = This |
195 | 224k | return false; |
196 | 430k | |
197 | 430k | // At this point, we know that the value of "this" will change. |
198 | 430k | // If it is Top, it will become the same as V, otherwise it will |
199 | 430k | // become "bottom" (i.e. Self). |
200 | 206k | if (206k Type == Top206k ) { |
201 | 102k | Type = V.Type; |
202 | 102k | RefI = V.RefI; // This may be irrelevant, but copy anyway. |
203 | 102k | return true; |
204 | 102k | } |
205 | 206k | // Become "bottom". |
206 | 104k | Type = Ref; |
207 | 104k | RefI = Self; |
208 | 104k | return true; |
209 | 436k | } |
210 | | |
211 | | // Create a reference to the bit value V. |
212 | | static BitValue ref(const BitValue &V); |
213 | | // Create a "self". |
214 | | static BitValue self(const BitRef &Self = BitRef()); |
215 | | |
216 | 68.4k | bool num() const { |
217 | 17.7k | return Type == Zero || Type == One; |
218 | 68.4k | } |
219 | | |
220 | 35.1k | operator bool() const { |
221 | 35.1k | assert(Type == Zero || Type == One); |
222 | 35.1k | return Type == One; |
223 | 35.1k | } |
224 | | |
225 | | friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV); |
226 | | }; |
227 | | |
228 | | // This operation must be idempotent, i.e. ref(ref(V)) == ref(V). |
229 | | inline BitTracker::BitValue |
230 | 730k | BitTracker::BitValue::ref(const BitValue &V) { |
231 | 730k | if (V.Type != Ref) |
232 | 139k | return BitValue(V.Type); |
233 | 591k | if (591k V.RefI.Reg != 0591k ) |
234 | 572k | return BitValue(V.RefI.Reg, V.RefI.Pos); |
235 | 18.6k | return self(); |
236 | 730k | } |
237 | | |
238 | | inline BitTracker::BitValue |
239 | 5.31M | BitTracker::BitValue::self(const BitRef &Self) { |
240 | 5.31M | return BitValue(Self.Reg, Self.Pos); |
241 | 5.31M | } |
242 | | |
243 | | // A sequence of bits starting from index B up to and including index E. |
244 | | // If E < B, the mask represents two sections: [0..E] and [B..W) where |
245 | | // W is the width of the register. |
246 | | struct BitTracker::BitMask { |
247 | | BitMask() = default; |
248 | 14.0k | BitMask(uint16_t b, uint16_t e) : B(b), E(e) {} |
249 | | |
250 | 14.0k | uint16_t first() const { return B; } |
251 | 14.0k | uint16_t last() const { return E; } |
252 | | |
253 | | private: |
254 | | uint16_t B = 0; |
255 | | uint16_t E = 0; |
256 | | }; |
257 | | |
258 | | // Representation of a register: a list of BitValues. |
259 | | struct BitTracker::RegisterCell { |
260 | 175k | RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {} |
261 | | |
262 | 1.59M | uint16_t width() const { |
263 | 1.59M | return Bits.size(); |
264 | 1.59M | } |
265 | | |
266 | 9.83M | const BitValue &operator[](uint16_t BitN) const { |
267 | 9.83M | assert(BitN < Bits.size()); |
268 | 9.83M | return Bits[BitN]; |
269 | 9.83M | } |
270 | 4.60M | BitValue &operator[](uint16_t BitN) { |
271 | 4.60M | assert(BitN < Bits.size()); |
272 | 4.60M | return Bits[BitN]; |
273 | 4.60M | } |
274 | | |
275 | | bool meet(const RegisterCell &RC, unsigned SelfR); |
276 | | RegisterCell &insert(const RegisterCell &RC, const BitMask &M); |
277 | | RegisterCell extract(const BitMask &M) const; // Returns a new cell. |
278 | | RegisterCell &rol(uint16_t Sh); // Rotate left. |
279 | | RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V); |
280 | | RegisterCell &cat(const RegisterCell &RC); // Concatenate. |
281 | | uint16_t cl(bool B) const; |
282 | | uint16_t ct(bool B) const; |
283 | | |
284 | | bool operator== (const RegisterCell &RC) const; |
285 | 13.2k | bool operator!= (const RegisterCell &RC) const { |
286 | 13.2k | return !operator==(RC); |
287 | 13.2k | } |
288 | | |
289 | | // Replace the ref-to-reg-0 bit values with the given register. |
290 | | RegisterCell ®ify(unsigned R); |
291 | | |
292 | | // Generate a "ref" cell for the corresponding register. In the resulting |
293 | | // cell each bit will be described as being the same as the corresponding |
294 | | // bit in register Reg (i.e. the cell is "defined" by register Reg). |
295 | | static RegisterCell self(unsigned Reg, uint16_t Width); |
296 | | // Generate a "top" cell of given size. |
297 | | static RegisterCell top(uint16_t Width); |
298 | | // Generate a cell that is a "ref" to another cell. |
299 | | static RegisterCell ref(const RegisterCell &C); |
300 | | |
301 | | private: |
302 | | // The DefaultBitN is here only to avoid frequent reallocation of the |
303 | | // memory in the vector. |
304 | | static const unsigned DefaultBitN = 32; |
305 | | using BitValueList = SmallVector<BitValue, DefaultBitN>; |
306 | | BitValueList Bits; |
307 | | |
308 | | friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC); |
309 | | }; |
310 | | |
311 | 982k | inline bool BitTracker::has(unsigned Reg) const { |
312 | 982k | return Map.find(Reg) != Map.end(); |
313 | 982k | } |
314 | | |
315 | | inline const BitTracker::RegisterCell& |
316 | 1.00M | BitTracker::lookup(unsigned Reg) const { |
317 | 1.00M | CellMapType::const_iterator F = Map.find(Reg); |
318 | 1.00M | assert(F != Map.end()); |
319 | 1.00M | return F->second; |
320 | 1.00M | } |
321 | | |
322 | | inline BitTracker::RegisterCell |
323 | 25.6k | BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) { |
324 | 25.6k | RegisterCell RC(Width); |
325 | 5.03M | for (uint16_t i = 0; i < Width5.03M ; ++i5.00M ) |
326 | 5.00M | RC.Bits[i] = BitValue::self(BitRef(Reg, i)); |
327 | 25.6k | return RC; |
328 | 25.6k | } |
329 | | |
330 | | inline BitTracker::RegisterCell |
331 | 36.1k | BitTracker::RegisterCell::top(uint16_t Width) { |
332 | 36.1k | RegisterCell RC(Width); |
333 | 5.38M | for (uint16_t i = 0; i < Width5.38M ; ++i5.34M ) |
334 | 5.34M | RC.Bits[i] = BitValue(BitValue::Top); |
335 | 36.1k | return RC; |
336 | 36.1k | } |
337 | | |
338 | | inline BitTracker::RegisterCell |
339 | 18.0k | BitTracker::RegisterCell::ref(const RegisterCell &C) { |
340 | 18.0k | uint16_t W = C.width(); |
341 | 18.0k | RegisterCell RC(W); |
342 | 711k | for (unsigned i = 0; i < W711k ; ++i693k ) |
343 | 693k | RC[i] = BitValue::ref(C[i]); |
344 | 18.0k | return RC; |
345 | 18.0k | } |
346 | | |
347 | | // A class to evaluate target's instructions and update the cell maps. |
348 | | // This is used internally by the bit tracker. A target that wants to |
349 | | // utilize this should implement the evaluation functions (noted below) |
350 | | // in a subclass of this class. |
351 | | struct BitTracker::MachineEvaluator { |
352 | | MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M) |
353 | 2.56k | : TRI(T), MRI(M) {} |
354 | 2.56k | virtual ~MachineEvaluator() = default; |
355 | | |
356 | | uint16_t getRegBitWidth(const RegisterRef &RR) const; |
357 | | |
358 | | RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const; |
359 | | void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const; |
360 | | |
361 | | // A result of any operation should use refs to the source cells, not |
362 | | // the cells directly. This function is a convenience wrapper to quickly |
363 | | // generate a ref for a cell corresponding to a register reference. |
364 | 0 | RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const { |
365 | 0 | RegisterCell RC = getCell(RR, M); |
366 | 0 | return RegisterCell::ref(RC); |
367 | 0 | } |
368 | | |
369 | | // Helper functions. |
370 | | // Check if a cell is an immediate value (i.e. all bits are either 0 or 1). |
371 | | bool isInt(const RegisterCell &A) const; |
372 | | // Convert cell to an immediate value. |
373 | | uint64_t toInt(const RegisterCell &A) const; |
374 | | |
375 | | // Generate cell from an immediate value. |
376 | | RegisterCell eIMM(int64_t V, uint16_t W) const; |
377 | | RegisterCell eIMM(const ConstantInt *CI) const; |
378 | | |
379 | | // Arithmetic. |
380 | | RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const; |
381 | | RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const; |
382 | | RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const; |
383 | | RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const; |
384 | | |
385 | | // Shifts. |
386 | | RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const; |
387 | | RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const; |
388 | | RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const; |
389 | | |
390 | | // Logical. |
391 | | RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const; |
392 | | RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const; |
393 | | RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const; |
394 | | RegisterCell eNOT(const RegisterCell &A1) const; |
395 | | |
396 | | // Set bit, clear bit. |
397 | | RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const; |
398 | | RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const; |
399 | | |
400 | | // Count leading/trailing bits (zeros/ones). |
401 | | RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const; |
402 | | RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const; |
403 | | |
404 | | // Sign/zero extension. |
405 | | RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const; |
406 | | RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const; |
407 | | |
408 | | // Extract/insert |
409 | | // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1. |
410 | | // INS R,S,b: take R and replace bits starting from b with S. |
411 | | RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const; |
412 | | RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2, |
413 | | uint16_t AtN) const; |
414 | | |
415 | | // User-provided functions for individual targets: |
416 | | |
417 | | // Return a sub-register mask that indicates which bits in Reg belong |
418 | | // to the subregister Sub. These bits are assumed to be contiguous in |
419 | | // the super-register, and have the same ordering in the sub-register |
420 | | // as in the super-register. It is valid to call this function with |
421 | | // Sub == 0, in this case, the function should return a mask that spans |
422 | | // the entire register Reg (which is what the default implementation |
423 | | // does). |
424 | | virtual BitMask mask(unsigned Reg, unsigned Sub) const; |
425 | | // Indicate whether a given register class should be tracked. |
426 | 99.3k | virtual bool track(const TargetRegisterClass *RC) const { return true; } |
427 | | // Evaluate a non-branching machine instruction, given the cell map with |
428 | | // the input values. Place the results in the Outputs map. Return "true" |
429 | | // if evaluation succeeded, "false" otherwise. |
430 | | virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs, |
431 | | CellMapType &Outputs) const; |
432 | | // Evaluate a branch, given the cell map with the input values. Fill out |
433 | | // a list of all possible branch targets and indicate (through a flag) |
434 | | // whether the branch could fall-through. Return "true" if this information |
435 | | // has been successfully computed, "false" otherwise. |
436 | | virtual bool evaluate(const MachineInstr &BI, const CellMapType &Inputs, |
437 | | BranchTargetList &Targets, bool &FallsThru) const = 0; |
438 | | // Given a register class RC, return a register class that should be assumed |
439 | | // when a register from class RC is used with a subregister of index Idx. |
440 | | virtual const TargetRegisterClass& |
441 | 0 | composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const { |
442 | 0 | if (Idx == 0) |
443 | 0 | return RC; |
444 | 0 | llvm_unreachable0 ("Unimplemented composeWithSubRegIndex"); |
445 | | } |
446 | | // Return the size in bits of the physical register Reg. |
447 | | virtual uint16_t getPhysRegBitWidth(unsigned Reg) const; |
448 | | |
449 | | const TargetRegisterInfo &TRI; |
450 | | MachineRegisterInfo &MRI; |
451 | | }; |
452 | | |
453 | | } // end namespace llvm |
454 | | |
455 | | #endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H |