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