LLVM  10.0.0svn
BitTracker.h
Go to the documentation of this file.
1 //===- BitTracker.h ---------------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
10 #define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
11 
12 #include "llvm/ADT/DenseSet.h"
13 #include "llvm/ADT/SetVector.h"
14 #include "llvm/ADT/SmallVector.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 BitVector;
27 class ConstantInt;
28 class MachineRegisterInfo;
29 class MachineBasicBlock;
30 class MachineFunction;
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 
44  using CellMapType = std::map<unsigned, RegisterCell>;
45 
47  ~BitTracker();
48 
49  void run();
50  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 
67  using CFGEdge = std::pair<int, int>;
68  using EdgeSetType = std::set<CFGEdge>;
69  using InstrSetType = std::set<const MachineInstr *>;
70  using EdgeQueueType = std::queue<CFGEdge>;
71 
72  // Priority queue of instructions using modified registers, ordered by
73  // their relative position in a basic block.
74  struct UseQueueType {
75  UseQueueType() : Uses(Dist) {}
76 
77  unsigned size() const {
78  return Uses.size();
79  }
80  bool empty() const {
81  return size() == 0;
82  }
83  MachineInstr *front() const {
84  return Uses.top();
85  }
86  void push(MachineInstr *MI) {
87  if (Set.insert(MI).second)
88  Uses.push(MI);
89  }
90  void pop() {
91  Set.erase(front());
92  Uses.pop();
93  }
94  void reset() {
95  Dist.clear();
96  }
97  private:
98  struct Cmp {
99  Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {}
100  bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
102  };
103  std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses;
104  DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries.
106  };
107 
108  void reset();
109  void runEdgeQueue(BitVector &BlockScanned);
110  void runUseQueue();
111 
112  const MachineEvaluator &ME;
113  MachineFunction &MF;
115  CellMapType &Map;
116 
117  EdgeSetType EdgeExec; // Executable flow graph edges.
118  InstrSetType InstrExec; // Executable instructions.
119  UseQueueType UseQ; // Work queue of register uses.
120  EdgeQueueType FlowQ; // Work queue of CFG edges.
121  DenseSet<unsigned> ReachedBB; // Cache of reached blocks.
122  bool Trace; // Enable tracing for debugging.
123 };
124 
125 // Abstraction of a reference to bit at position Pos from a register Reg.
127  BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {}
128 
129  bool operator== (const BitRef &BR) const {
130  // If Reg is 0, disregard Pos.
131  return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos);
132  }
133 
134  unsigned Reg;
135  uint16_t Pos;
136 };
137 
138 // Abstraction of a register reference in MachineOperand. It contains the
139 // register number and the subregister index.
141  RegisterRef(unsigned R = 0, unsigned S = 0)
142  : Reg(R), Sub(S) {}
144  : Reg(MO.getReg()), Sub(MO.getSubReg()) {}
145 
146  unsigned Reg, Sub;
147 };
148 
149 // Value that a single bit can take. This is outside of the context of
150 // any register, it is more of an abstraction of the two-element set of
151 // possible bit values. One extension here is the "Ref" type, which
152 // indicates that this bit takes the same value as the bit described by
153 // RefInfo.
155  enum ValueType {
156  Top, // Bit not yet defined.
157  Zero, // Bit = 0.
158  One, // Bit = 1.
159  Ref // Bit value same as the one described in RefI.
160  // Conceptually, there is no explicit "bottom" value: the lattice's
161  // bottom will be expressed as a "ref to itself", which, in the context
162  // of registers, could be read as "this value of this bit is defined by
163  // this bit".
164  // The ordering is:
165  // x <= Top,
166  // Self <= x, where "Self" is "ref to itself".
167  // This makes the value lattice different for each virtual register
168  // (even for each bit in the same virtual register), since the "bottom"
169  // for one register will be a simple "ref" for another register.
170  // Since we do not store the "Self" bit and register number, the meet
171  // operation will need to take it as a parameter.
172  //
173  // In practice there is a special case for values that are not associa-
174  // ted with any specific virtual register. An example would be a value
175  // corresponding to a bit of a physical register, or an intermediate
176  // value obtained in some computation (such as instruction evaluation).
177  // Such cases are identical to the usual Ref type, but the register
178  // number is 0. In such case the Pos field of the reference is ignored.
179  //
180  // What is worthy of notice is that in value V (that is a "ref"), as long
181  // as the RefI.Reg is not 0, it may actually be the same register as the
182  // one in which V will be contained. If the RefI.Pos refers to the posi-
183  // tion of V, then V is assumed to be "bottom" (as a "ref to itself"),
184  // otherwise V is taken to be identical to the referenced bit of the
185  // same register.
186  // If RefI.Reg is 0, however, such a reference to the same register is
187  // not possible. Any value V that is a "ref", and whose RefI.Reg is 0
188  // is treated as "bottom".
189  };
192 
193  BitValue(ValueType T = Top) : Type(T) {}
194  BitValue(bool B) : Type(B ? One : Zero) {}
195  BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {}
196 
197  bool operator== (const BitValue &V) const {
198  if (Type != V.Type)
199  return false;
200  if (Type == Ref && !(RefI == V.RefI))
201  return false;
202  return true;
203  }
204  bool operator!= (const BitValue &V) const {
205  return !operator==(V);
206  }
207 
208  bool is(unsigned T) const {
209  assert(T == 0 || T == 1);
210  return T == 0 ? Type == Zero
211  : (T == 1 ? Type == One : false);
212  }
213 
214  // The "meet" operation is the "." operation in a semilattice (L, ., T, B):
215  // (1) x.x = x
216  // (2) x.y = y.x
217  // (3) x.(y.z) = (x.y).z
218  // (4) x.T = x (i.e. T = "top")
219  // (5) x.B = B (i.e. B = "bottom")
220  //
221  // This "meet" function will update the value of the "*this" object with
222  // the newly calculated one, and return "true" if the value of *this has
223  // changed, and "false" otherwise.
224  // To prove that it satisfies the conditions (1)-(5), it is sufficient
225  // to show that a relation
226  // x <= y <=> x.y = x
227  // defines a partial order (i.e. that "meet" is same as "infimum").
228  bool meet(const BitValue &V, const BitRef &Self) {
229  // First, check the cases where there is nothing to be done.
230  if (Type == Ref && RefI == Self) // Bottom.meet(V) = Bottom (i.e. This)
231  return false;
232  if (V.Type == Top) // This.meet(Top) = This
233  return false;
234  if (*this == V) // This.meet(This) = This
235  return false;
236 
237  // At this point, we know that the value of "this" will change.
238  // If it is Top, it will become the same as V, otherwise it will
239  // become "bottom" (i.e. Self).
240  if (Type == Top) {
241  Type = V.Type;
242  RefI = V.RefI; // This may be irrelevant, but copy anyway.
243  return true;
244  }
245  // Become "bottom".
246  Type = Ref;
247  RefI = Self;
248  return true;
249  }
250 
251  // Create a reference to the bit value V.
252  static BitValue ref(const BitValue &V);
253  // Create a "self".
254  static BitValue self(const BitRef &Self = BitRef());
255 
256  bool num() const {
257  return Type == Zero || Type == One;
258  }
259 
260  operator bool() const {
261  assert(Type == Zero || Type == One);
262  return Type == One;
263  }
264 
265  friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV);
266 };
267 
268 // This operation must be idempotent, i.e. ref(ref(V)) == ref(V).
271  if (V.Type != Ref)
272  return BitValue(V.Type);
273  if (V.RefI.Reg != 0)
274  return BitValue(V.RefI.Reg, V.RefI.Pos);
275  return self();
276 }
277 
280  return BitValue(Self.Reg, Self.Pos);
281 }
282 
283 // A sequence of bits starting from index B up to and including index E.
284 // If E < B, the mask represents two sections: [0..E] and [B..W) where
285 // W is the width of the register.
287  BitMask() = default;
288  BitMask(uint16_t b, uint16_t e) : B(b), E(e) {}
289 
290  uint16_t first() const { return B; }
291  uint16_t last() const { return E; }
292 
293 private:
294  uint16_t B = 0;
295  uint16_t E = 0;
296 };
297 
298 // Representation of a register: a list of BitValues.
300  RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {}
301 
302  uint16_t width() const {
303  return Bits.size();
304  }
305 
306  const BitValue &operator[](uint16_t BitN) const {
307  assert(BitN < Bits.size());
308  return Bits[BitN];
309  }
310  BitValue &operator[](uint16_t BitN) {
311  assert(BitN < Bits.size());
312  return Bits[BitN];
313  }
314 
315  bool meet(const RegisterCell &RC, unsigned SelfR);
316  RegisterCell &insert(const RegisterCell &RC, const BitMask &M);
317  RegisterCell extract(const BitMask &M) const; // Returns a new cell.
318  RegisterCell &rol(uint16_t Sh); // Rotate left.
319  RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V);
320  RegisterCell &cat(const RegisterCell &RC); // Concatenate.
321  uint16_t cl(bool B) const;
322  uint16_t ct(bool B) const;
323 
324  bool operator== (const RegisterCell &RC) const;
325  bool operator!= (const RegisterCell &RC) const {
326  return !operator==(RC);
327  }
328 
329  // Replace the ref-to-reg-0 bit values with the given register.
330  RegisterCell &regify(unsigned R);
331 
332  // Generate a "ref" cell for the corresponding register. In the resulting
333  // cell each bit will be described as being the same as the corresponding
334  // bit in register Reg (i.e. the cell is "defined" by register Reg).
335  static RegisterCell self(unsigned Reg, uint16_t Width);
336  // Generate a "top" cell of given size.
337  static RegisterCell top(uint16_t Width);
338  // Generate a cell that is a "ref" to another cell.
339  static RegisterCell ref(const RegisterCell &C);
340 
341 private:
342  // The DefaultBitN is here only to avoid frequent reallocation of the
343  // memory in the vector.
344  static const unsigned DefaultBitN = 32;
347 
348  friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC);
349 };
350 
351 inline bool BitTracker::has(unsigned Reg) const {
352  return Map.find(Reg) != Map.end();
353 }
354 
355 inline const BitTracker::RegisterCell&
356 BitTracker::lookup(unsigned Reg) const {
357  CellMapType::const_iterator F = Map.find(Reg);
358  assert(F != Map.end());
359  return F->second;
360 }
361 
364  RegisterCell RC(Width);
365  for (uint16_t i = 0; i < Width; ++i)
366  RC.Bits[i] = BitValue::self(BitRef(Reg, i));
367  return RC;
368 }
369 
372  RegisterCell RC(Width);
373  for (uint16_t i = 0; i < Width; ++i)
374  RC.Bits[i] = BitValue(BitValue::Top);
375  return RC;
376 }
377 
380  uint16_t W = C.width();
381  RegisterCell RC(W);
382  for (unsigned i = 0; i < W; ++i)
383  RC[i] = BitValue::ref(C[i]);
384  return RC;
385 }
386 
387 // A class to evaluate target's instructions and update the cell maps.
388 // This is used internally by the bit tracker. A target that wants to
389 // utilize this should implement the evaluation functions (noted below)
390 // in a subclass of this class.
393  : TRI(T), MRI(M) {}
394  virtual ~MachineEvaluator() = default;
395 
396  uint16_t getRegBitWidth(const RegisterRef &RR) const;
397 
398  RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const;
399  void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const;
400 
401  // A result of any operation should use refs to the source cells, not
402  // the cells directly. This function is a convenience wrapper to quickly
403  // generate a ref for a cell corresponding to a register reference.
404  RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const {
405  RegisterCell RC = getCell(RR, M);
406  return RegisterCell::ref(RC);
407  }
408 
409  // Helper functions.
410  // Check if a cell is an immediate value (i.e. all bits are either 0 or 1).
411  bool isInt(const RegisterCell &A) const;
412  // Convert cell to an immediate value.
413  uint64_t toInt(const RegisterCell &A) const;
414 
415  // Generate cell from an immediate value.
416  RegisterCell eIMM(int64_t V, uint16_t W) const;
417  RegisterCell eIMM(const ConstantInt *CI) const;
418 
419  // Arithmetic.
420  RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const;
421  RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const;
422  RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const;
423  RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const;
424 
425  // Shifts.
426  RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const;
427  RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const;
428  RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const;
429 
430  // Logical.
431  RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const;
432  RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const;
433  RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const;
434  RegisterCell eNOT(const RegisterCell &A1) const;
435 
436  // Set bit, clear bit.
437  RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const;
438  RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const;
439 
440  // Count leading/trailing bits (zeros/ones).
441  RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const;
442  RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const;
443 
444  // Sign/zero extension.
445  RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const;
446  RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const;
447 
448  // Extract/insert
449  // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1.
450  // INS R,S,b: take R and replace bits starting from b with S.
451  RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const;
452  RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2,
453  uint16_t AtN) const;
454 
455  // User-provided functions for individual targets:
456 
457  // Return a sub-register mask that indicates which bits in Reg belong
458  // to the subregister Sub. These bits are assumed to be contiguous in
459  // the super-register, and have the same ordering in the sub-register
460  // as in the super-register. It is valid to call this function with
461  // Sub == 0, in this case, the function should return a mask that spans
462  // the entire register Reg (which is what the default implementation
463  // does).
464  virtual BitMask mask(unsigned Reg, unsigned Sub) const;
465  // Indicate whether a given register class should be tracked.
466  virtual bool track(const TargetRegisterClass *RC) const { return true; }
467  // Evaluate a non-branching machine instruction, given the cell map with
468  // the input values. Place the results in the Outputs map. Return "true"
469  // if evaluation succeeded, "false" otherwise.
470  virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs,
471  CellMapType &Outputs) const;
472  // Evaluate a branch, given the cell map with the input values. Fill out
473  // a list of all possible branch targets and indicate (through a flag)
474  // whether the branch could fall-through. Return "true" if this information
475  // has been successfully computed, "false" otherwise.
476  virtual bool evaluate(const MachineInstr &BI, const CellMapType &Inputs,
477  BranchTargetList &Targets, bool &FallsThru) const = 0;
478  // Given a register class RC, return a register class that should be assumed
479  // when a register from class RC is used with a subregister of index Idx.
480  virtual const TargetRegisterClass&
481  composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const {
482  if (Idx == 0)
483  return RC;
484  llvm_unreachable("Unimplemented composeWithSubRegIndex");
485  }
486  // Return the size in bits of the physical register Reg.
487  virtual uint16_t getPhysRegBitWidth(unsigned Reg) const;
488 
491 };
492 
493 } // end namespace llvm
494 
495 #endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
uint64_t CallInst * C
RegisterRef(unsigned R=0, unsigned S=0)
Definition: BitTracker.h:141
MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M)
Definition: BitTracker.h:392
const TargetRegisterInfo & TRI
Definition: BitTracker.h:489
BitValue(ValueType T=Top)
Definition: BitTracker.h:193
void trace(bool On=false)
Definition: BitTracker.h:50
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BitValue(unsigned Reg, uint16_t Pos)
Definition: BitTracker.h:195
static RegisterCell top(uint16_t Width)
Definition: BitTracker.h:371
Implements a dense probed hash-table based set.
Definition: DenseSet.h:249
unsigned Reg
void visit(const MachineInstr &MI)
unsigned getRegBitWidth(unsigned RCID)
Get the size in bits of a register from the register class RC.
static RegisterCell self(unsigned Reg, uint16_t Width)
Definition: BitTracker.h:363
unsigned const TargetRegisterInfo * TRI
F(f)
void print_cells(raw_ostream &OS) const
Definition: BitTracker.cpp:182
The access may reference the value stored in memory.
BitValue & operator[](uint16_t BitN)
Definition: BitTracker.h:310
BitRef(unsigned R=0, uint16_t P=0)
Definition: BitTracker.h:127
BitMask(uint16_t b, uint16_t e)
Definition: BitTracker.h:288
bool reached(const MachineBasicBlock *B) const
#define P(N)
Control flow instructions. These all have token chains.
Definition: ISDOpcodes.h:657
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
Definition: MathExtras.h:298
const RegisterCell & lookup(unsigned Reg) const
Definition: BitTracker.h:356
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
virtual const TargetRegisterClass & composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const
Definition: BitTracker.h:481
static uint32_t rol(uint32_t Number, int Bits)
Definition: SHA1.cpp:29
RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const
Definition: BitTracker.h:404
void subst(RegisterRef OldRR, RegisterRef NewRR)
Definition: BitTracker.cpp:999
virtual bool track(const TargetRegisterClass *RC) const
Definition: BitTracker.h:466
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::map< unsigned, RegisterCell > CellMapType
Definition: BitTracker.h:44
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
const BitValue & operator[](uint16_t BitN) const
Definition: BitTracker.h:306
uint16_t first() const
Definition: BitTracker.h:290
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1146
uint16_t last() const
Definition: BitTracker.h:291
static BitValue self(const BitRef &Self=BitRef())
Definition: BitTracker.h:279
MachineOperand class - Representation of each machine instruction operand.
bool is(unsigned T) const
Definition: BitTracker.h:208
MachineRegisterInfo & MRI
Definition: BitTracker.h:490
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
loop extract
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
bool operator!=(uint64_t V1, const APInt &V2)
Definition: APInt.h:1975
Representation of each machine instruction.
Definition: MachineInstr.h:64
BitTracker(const MachineEvaluator &E, MachineFunction &F)
Definition: BitTracker.cpp:187
bool has(unsigned Reg) const
Definition: BitTracker.h:351
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegisterRef(const MachineOperand &MO)
Definition: BitTracker.h:143
RegisterCell(uint16_t Width=DefaultBitN)
Definition: BitTracker.h:300
A vector that has set insertion semantics.
Definition: SetVector.h:40
void put(RegisterRef RR, const RegisterCell &RC)
Definition: BitTracker.cpp:993
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1973
static RegisterCell ref(const RegisterCell &C)
Definition: BitTracker.h:379
bool meet(const BitValue &V, const BitRef &Self)
Definition: BitTracker.h:228
static BitValue ref(const BitValue &V)
Definition: BitTracker.h:270