Coverage Report

Created: 2017-10-03 07:32

/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 &Map;
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 &regify(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