Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/BitTracker.h
Line
Count
Source (jump to first uncovered line)
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"
15
#include "llvm/CodeGen/MachineInstr.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 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
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
3.35k
  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
10.0k
    UseQueueType() : Uses(Dist) {}
76
77
146k
    unsigned size() const {
78
146k
      return Uses.size();
79
146k
    }
80
146k
    bool empty() const {
81
146k
      return size() == 0;
82
146k
    }
83
218k
    MachineInstr *front() const {
84
218k
      return Uses.top();
85
218k
    }
86
159k
    void push(MachineInstr *MI) {
87
159k
      if (Set.insert(MI).second)
88
109k
        Uses.push(MI);
89
159k
    }
90
109k
    void pop() {
91
109k
      Set.erase(front());
92
109k
      Uses.pop();
93
109k
    }
94
13.4k
    void reset() {
95
13.4k
      Dist.clear();
96
13.4k
    }
97
  private:
98
    struct Cmp {
99
10.0k
      Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {}
100
      bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
101
      DenseMap<const MachineInstr*,unsigned> &Dist;
102
    };
103
    std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses;
104
    DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries.
105
    DenseMap<const MachineInstr*,unsigned> Dist;
106
  };
107
108
  void reset();
109
  void runEdgeQueue(BitVector &BlockScanned);
110
  void runUseQueue();
111
112
  const MachineEvaluator &ME;
113
  MachineFunction &MF;
114
  MachineRegisterInfo &MRI;
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.
126
struct BitTracker::BitRef {
127
156M
  BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {}
128
129
31.3M
  bool operator== (const BitRef &BR) const {
130
31.3M
    // If Reg is 0, disregard Pos.
131
31.3M
    return Reg == BR.Reg && 
(28.2M
Reg == 028.2M
||
Pos == BR.Pos28.2M
);
132
31.3M
  }
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.
140
struct BitTracker::RegisterRef {
141
  RegisterRef(unsigned R = 0, unsigned S = 0)
142
1.37M
    : Reg(R), Sub(S) {}
143
  RegisterRef(const MachineOperand &MO)
144
1.13M
      : 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.
154
struct BitTracker::BitValue {
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
  };
190
  ValueType Type;
191
  BitRef RefI;
192
193
40.7M
  BitValue(ValueType T = Top) : Type(T) {}
194
793k
  BitValue(bool B) : Type(B ? One : Zero) {}
195
57.3M
  BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {}
196
197
53.9M
  bool operator== (const BitValue &V) const {
198
53.9M
    if (Type != V.Type)
199
22.5M
      return false;
200
31.3M
    if (Type == Ref && 
!(RefI == V.RefI)30.3M
)
201
2.19M
      return false;
202
29.1M
    return true;
203
29.1M
  }
204
19.0M
  bool operator!= (const BitValue &V) const {
205
19.0M
    return !operator==(V);
206
19.0M
  }
207
208
2.45M
  bool is(unsigned T) const {
209
2.45M
    assert(T == 0 || T == 1);
210
2.45M
    return T == 0 ? 
Type == Zero1.58M
211
2.45M
                  : 
(T == 1 869k
?
Type == One869k
:
false0
);
212
2.45M
  }
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
1.75M
  bool meet(const BitValue &V, const BitRef &Self) {
229
1.75M
    // First, check the cases where there is nothing to be done.
230
1.75M
    if (Type == Ref && 
RefI == Self1.00M
) // Bottom.meet(V) = Bottom (i.e. This)
231
69.8k
      return false;
232
1.68M
    if (V.Type == Top)                  // This.meet(Top) = This
233
0
      return false;
234
1.68M
    if (*this == V)                     // This.meet(This) = This
235
865k
      return false;
236
815k
237
815k
    // At this point, we know that the value of "this" will change.
238
815k
    // If it is Top, it will become the same as V, otherwise it will
239
815k
    // become "bottom" (i.e. Self).
240
815k
    if (Type == Top) {
241
395k
      Type = V.Type;
242
395k
      RefI = V.RefI;  // This may be irrelevant, but copy anyway.
243
395k
      return true;
244
395k
    }
245
420k
    // Become "bottom".
246
420k
    Type = Ref;
247
420k
    RefI = Self;
248
420k
    return true;
249
420k
  }
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
167k
  bool num() const {
257
167k
    return Type == Zero || 
Type == One56.4k
;
258
167k
  }
259
260
88.6k
  operator bool() const {
261
88.6k
    assert(Type == Zero || Type == One);
262
88.6k
    return Type == One;
263
88.6k
  }
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).
269
inline BitTracker::BitValue
270
12.3M
BitTracker::BitValue::ref(const BitValue &V) {
271
12.3M
  if (V.Type != Ref)
272
811k
    return BitValue(V.Type);
273
11.5M
  if (V.RefI.Reg != 0)
274
11.4M
    return BitValue(V.RefI.Reg, V.RefI.Pos);
275
125k
  return self();
276
125k
}
277
278
inline BitTracker::BitValue
279
45.9M
BitTracker::BitValue::self(const BitRef &Self) {
280
45.9M
  return BitValue(Self.Reg, Self.Pos);
281
45.9M
}
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.
286
struct BitTracker::BitMask {
287
  BitMask() = default;
288
106k
  BitMask(uint16_t b, uint16_t e) : B(b), E(e) {}
289
290
106k
  uint16_t first() const { return B; }
291
106k
  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.
299
struct BitTracker::RegisterCell {
300
699k
  RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {}
301
302
2.66M
  uint16_t width() const {
303
2.66M
    return Bits.size();
304
2.66M
  }
305
306
88.5M
  const BitValue &operator[](uint16_t BitN) const {
307
88.5M
    assert(BitN < Bits.size());
308
88.5M
    return Bits[BitN];
309
88.5M
  }
310
100M
  BitValue &operator[](uint16_t BitN) {
311
100M
    assert(BitN < Bits.size());
312
100M
    return Bits[BitN];
313
100M
  }
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
60.2k
  bool operator!= (const RegisterCell &RC) const {
326
60.2k
    return !operator==(RC);
327
60.2k
  }
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;
345
  using BitValueList = SmallVector<BitValue, DefaultBitN>;
346
  BitValueList Bits;
347
348
  friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC);
349
};
350
351
1.32M
inline bool BitTracker::has(unsigned Reg) const {
352
1.32M
  return Map.find(Reg) != Map.end();
353
1.32M
}
354
355
inline const BitTracker::RegisterCell&
356
1.37M
BitTracker::lookup(unsigned Reg) const {
357
1.37M
  CellMapType::const_iterator F = Map.find(Reg);
358
1.37M
  assert(F != Map.end());
359
1.37M
  return F->second;
360
1.37M
}
361
362
inline BitTracker::RegisterCell
363
108k
BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) {
364
108k
  RegisterCell RC(Width);
365
44.9M
  for (uint16_t i = 0; i < Width; 
++i44.8M
)
366
44.8M
    RC.Bits[i] = BitValue::self(BitRef(Reg, i));
367
108k
  return RC;
368
108k
}
369
370
inline BitTracker::RegisterCell
371
110k
BitTracker::RegisterCell::top(uint16_t Width) {
372
110k
  RegisterCell RC(Width);
373
38.8M
  for (uint16_t i = 0; i < Width; 
++i38.7M
)
374
38.7M
    RC.Bits[i] = BitValue(BitValue::Top);
375
110k
  return RC;
376
110k
}
377
378
inline BitTracker::RegisterCell
379
84.6k
BitTracker::RegisterCell::ref(const RegisterCell &C) {
380
84.6k
  uint16_t W = C.width();
381
84.6k
  RegisterCell RC(W);
382
12.3M
  for (unsigned i = 0; i < W; 
++i12.2M
)
383
12.2M
    RC[i] = BitValue::ref(C[i]);
384
84.6k
  return RC;
385
84.6k
}
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.
391
struct BitTracker::MachineEvaluator {
392
  MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M)
393
10.0k
      : TRI(T), MRI(M) {}
394
10.0k
  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
0
  RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const {
405
0
    RegisterCell RC = getCell(RR, M);
406
0
    return RegisterCell::ref(RC);
407
0
  }
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
461k
  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
0
  composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const {
482
0
    if (Idx == 0)
483
0
      return RC;
484
0
    llvm_unreachable("Unimplemented composeWithSubRegIndex");
485
0
  }
486
  // Return the size in bits of the physical register Reg.
487
  virtual uint16_t getPhysRegBitWidth(unsigned Reg) const;
488
489
  const TargetRegisterInfo &TRI;
490
  MachineRegisterInfo &MRI;
491
};
492
493
} // end namespace llvm
494
495
#endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H