Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/BitTracker.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- BitTracker.cpp -----------------------------------------------------===//
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
// SSA-based bit propagation.
10
//
11
// The purpose of this code is, for a given virtual register, to provide
12
// information about the value of each bit in the register. The values
13
// of bits are represented by the class BitValue, and take one of four
14
// cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
15
// "ref" value means that the bit is a copy of another bit (which itself
16
// cannot be a copy of yet another bit---such chains are not allowed).
17
// A "ref" value is associated with a BitRef structure, which indicates
18
// which virtual register, and which bit in that register is the origin
19
// of the value. For example, given an instruction
20
//   %2 = ASL %1, 1
21
// assuming that nothing is known about bits of %1, bit 1 of %2
22
// will be a "ref" to (%1, 0). If there is a subsequent instruction
23
//   %3 = ASL %2, 2
24
// then bit 3 of %3 will be a "ref" to (%1, 0) as well.
25
// The "bottom" case means that the bit's value cannot be determined,
26
// and that this virtual register actually defines it. The "bottom" case
27
// is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
28
// to self", so for the %1 above, the bit 0 of it will be a "ref" to
29
// (%1, 0), bit 1 will be a "ref" to (%1, 1), etc.
30
//
31
// The tracker implements the Wegman-Zadeck algorithm, originally developed
32
// for SSA-based constant propagation. Each register is represented as
33
// a sequence of bits, with the convention that bit 0 is the least signi-
34
// ficant bit. Each bit is propagated individually. The class RegisterCell
35
// implements the register's representation, and is also the subject of
36
// the lattice operations in the tracker.
37
//
38
// The intended usage of the bit tracker is to create a target-specific
39
// machine instruction evaluator, pass the evaluator to the BitTracker
40
// object, and run the tracker. The tracker will then collect the bit
41
// value information for a given machine function. After that, it can be
42
// queried for the cells for each virtual register.
43
// Sample code:
44
//   const TargetSpecificEvaluator TSE(TRI, MRI);
45
//   BitTracker BT(TSE, MF);
46
//   BT.run();
47
//   ...
48
//   unsigned Reg = interestingRegister();
49
//   RegisterCell RC = BT.get(Reg);
50
//   if (RC[3].is(1))
51
//      Reg0bit3 = 1;
52
//
53
// The code below is intended to be fully target-independent.
54
55
#include "BitTracker.h"
56
#include "llvm/ADT/APInt.h"
57
#include "llvm/ADT/BitVector.h"
58
#include "llvm/CodeGen/MachineBasicBlock.h"
59
#include "llvm/CodeGen/MachineFunction.h"
60
#include "llvm/CodeGen/MachineInstr.h"
61
#include "llvm/CodeGen/MachineOperand.h"
62
#include "llvm/CodeGen/MachineRegisterInfo.h"
63
#include "llvm/CodeGen/TargetRegisterInfo.h"
64
#include "llvm/IR/Constants.h"
65
#include "llvm/Support/Debug.h"
66
#include "llvm/Support/raw_ostream.h"
67
#include <cassert>
68
#include <cstdint>
69
#include <iterator>
70
71
using namespace llvm;
72
73
using BT = BitTracker;
74
75
namespace {
76
77
  // Local trickery to pretty print a register (without the whole "%number"
78
  // business).
79
  struct printv {
80
0
    printv(unsigned r) : R(r) {}
81
82
    unsigned R;
83
  };
84
85
0
  raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
86
0
    if (PV.R)
87
0
      OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R);
88
0
    else
89
0
      OS << 's';
90
0
    return OS;
91
0
  }
92
93
} // end anonymous namespace
94
95
namespace llvm {
96
97
0
  raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) {
98
0
    switch (BV.Type) {
99
0
      case BT::BitValue::Top:
100
0
        OS << 'T';
101
0
        break;
102
0
      case BT::BitValue::Zero:
103
0
        OS << '0';
104
0
        break;
105
0
      case BT::BitValue::One:
106
0
        OS << '1';
107
0
        break;
108
0
      case BT::BitValue::Ref:
109
0
        OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
110
0
        break;
111
0
    }
112
0
    return OS;
113
0
  }
114
115
0
  raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
116
0
    unsigned n = RC.Bits.size();
117
0
    OS << "{ w:" << n;
118
0
    // Instead of printing each bit value individually, try to group them
119
0
    // into logical segments, such as sequences of 0 or 1 bits or references
120
0
    // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
121
0
    // "Start" will be the index of the beginning of the most recent segment.
122
0
    unsigned Start = 0;
123
0
    bool SeqRef = false;    // A sequence of refs to consecutive bits.
124
0
    bool ConstRef = false;  // A sequence of refs to the same bit.
125
0
126
0
    for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
127
0
      const BT::BitValue &V = RC[i];
128
0
      const BT::BitValue &SV = RC[Start];
129
0
      bool IsRef = (V.Type == BT::BitValue::Ref);
130
0
      // If the current value is the same as Start, skip to the next one.
131
0
      if (!IsRef && V == SV)
132
0
        continue;
133
0
      if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
134
0
        if (Start+1 == i) {
135
0
          SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
136
0
          ConstRef = (V.RefI.Pos == SV.RefI.Pos);
137
0
        }
138
0
        if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
139
0
          continue;
140
0
        if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
141
0
          continue;
142
0
      }
143
0
144
0
      // The current value is different. Print the previous one and reset
145
0
      // the Start.
146
0
      OS << " [" << Start;
147
0
      unsigned Count = i - Start;
148
0
      if (Count == 1) {
149
0
        OS << "]:" << SV;
150
0
      } else {
151
0
        OS << '-' << i-1 << "]:";
152
0
        if (SV.Type == BT::BitValue::Ref && SeqRef)
153
0
          OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
154
0
             << SV.RefI.Pos+(Count-1) << ']';
155
0
        else
156
0
          OS << SV;
157
0
      }
158
0
      Start = i;
159
0
      SeqRef = ConstRef = false;
160
0
    }
161
0
162
0
    OS << " [" << Start;
163
0
    unsigned Count = n - Start;
164
0
    if (n-Start == 1) {
165
0
      OS << "]:" << RC[Start];
166
0
    } else {
167
0
      OS << '-' << n-1 << "]:";
168
0
      const BT::BitValue &SV = RC[Start];
169
0
      if (SV.Type == BT::BitValue::Ref && SeqRef)
170
0
        OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
171
0
           << SV.RefI.Pos+(Count-1) << ']';
172
0
      else
173
0
        OS << SV;
174
0
    }
175
0
    OS << " }";
176
0
177
0
    return OS;
178
0
  }
179
180
} // end namespace llvm
181
182
0
void BitTracker::print_cells(raw_ostream &OS) const {
183
0
  for (const std::pair<unsigned, RegisterCell> P : Map)
184
0
    dbgs() << printReg(P.first, &ME.TRI) << " -> " << P.second << "\n";
185
0
}
186
187
BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
188
10.0k
    : ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType), Trace(false) {
189
10.0k
}
190
191
10.0k
BitTracker::~BitTracker() {
192
10.0k
  delete &Map;
193
10.0k
}
194
195
// If we were allowed to update a cell for a part of a register, the meet
196
// operation would need to be parametrized by the register number and the
197
// exact part of the register, so that the computer BitRefs correspond to
198
// the actual bits of the "self" register.
199
// While this cannot happen in the current implementation, I'm not sure
200
// if this should be ruled out in the future.
201
26.8k
bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
202
26.8k
  // An example when "meet" can be invoked with SelfR == 0 is a phi node
203
26.8k
  // with a physical register as an operand.
204
26.8k
  assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR));
205
26.8k
  bool Changed = false;
206
1.77M
  for (uint16_t i = 0, n = Bits.size(); i < n; 
++i1.75M
) {
207
1.75M
    const BitValue &RCV = RC[i];
208
1.75M
    Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
209
1.75M
  }
210
26.8k
  return Changed;
211
26.8k
}
212
213
// Insert the entire cell RC into the current cell at position given by M.
214
BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
215
84.7k
      const BitMask &M) {
216
84.7k
  uint16_t B = M.first(), E = M.last(), W = width();
217
84.7k
  // Sanity: M must be a valid mask for *this.
218
84.7k
  assert(B < W && E < W);
219
84.7k
  // Sanity: the masked part of *this must have the same number of bits
220
84.7k
  // as the source.
221
84.7k
  assert(B > E || E-B+1 == RC.width());      // B <= E  =>  E-B+1 = |RC|.
222
84.7k
  assert(B <= E || E+(W-B)+1 == RC.width()); // E < B   =>  E+(W-B)+1 = |RC|.
223
84.7k
  if (B <= E) {
224
44.0M
    for (uint16_t i = 0; i <= E-B; 
++i43.9M
)
225
43.9M
      Bits[i+B] = RC[i];
226
84.7k
  } else {
227
0
    for (uint16_t i = 0; i < W-B; ++i)
228
0
      Bits[i+B] = RC[i];
229
0
    for (uint16_t i = 0; i <= E; ++i)
230
0
      Bits[i] = RC[i+(W-B)];
231
0
  }
232
84.7k
  return *this;
233
84.7k
}
234
235
21.4k
BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
236
21.4k
  uint16_t B = M.first(), E = M.last(), W = width();
237
21.4k
  assert(B < W && E < W);
238
21.4k
  if (B <= E) {
239
21.4k
    RegisterCell RC(E-B+1);
240
11.0M
    for (uint16_t i = B; i <= E; 
++i11.0M
)
241
11.0M
      RC.Bits[i-B] = Bits[i];
242
21.4k
    return RC;
243
21.4k
  }
244
0
245
0
  RegisterCell RC(E+(W-B)+1);
246
0
  for (uint16_t i = 0; i < W-B; ++i)
247
0
    RC.Bits[i] = Bits[i+B];
248
0
  for (uint16_t i = 0; i <= E; ++i)
249
0
    RC.Bits[i+(W-B)] = Bits[i];
250
0
  return RC;
251
0
}
252
253
5.34k
BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
254
5.34k
  // Rotate left (i.e. towards increasing bit indices).
255
5.34k
  // Swap the two parts:  [0..W-Sh-1] [W-Sh..W-1]
256
5.34k
  uint16_t W = width();
257
5.34k
  Sh = Sh % W;
258
5.34k
  if (Sh == 0)
259
12
    return *this;
260
5.33k
261
5.33k
  RegisterCell Tmp(W-Sh);
262
5.33k
  // Tmp = [0..W-Sh-1].
263
130k
  for (uint16_t i = 0; i < W-Sh; 
++i124k
)
264
124k
    Tmp[i] = Bits[i];
265
5.33k
  // Shift [W-Sh..W-1] to [0..Sh-1].
266
69.2k
  for (uint16_t i = 0; i < Sh; 
++i63.8k
)
267
63.8k
    Bits[i] = Bits[W-Sh+i];
268
5.33k
  // Copy Tmp to [Sh..W-1].
269
130k
  for (uint16_t i = 0; i < W-Sh; 
++i124k
)
270
124k
    Bits[i+Sh] = Tmp.Bits[i];
271
5.33k
  return *this;
272
5.33k
}
273
274
BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
275
94.0k
      const BitValue &V) {
276
94.0k
  assert(B <= E);
277
647k
  while (B < E)
278
553k
    Bits[B++] = V;
279
94.0k
  return *this;
280
94.0k
}
281
282
1.28k
BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
283
1.28k
  // Append the cell given as the argument to the "this" cell.
284
1.28k
  // Bit 0 of RC becomes bit W of the result, where W is this->width().
285
1.28k
  uint16_t W = width(), WRC = RC.width();
286
1.28k
  Bits.resize(W+WRC);
287
225k
  for (uint16_t i = 0; i < WRC; 
++i224k
)
288
224k
    Bits[i+W] = RC.Bits[i];
289
1.28k
  return *this;
290
1.28k
}
291
292
5.21k
uint16_t BT::RegisterCell::ct(bool B) const {
293
5.21k
  uint16_t W = width();
294
5.21k
  uint16_t C = 0;
295
5.21k
  BitValue V = B;
296
15.7k
  while (C < W && 
Bits[C] == V15.5k
)
297
10.5k
    C++;
298
5.21k
  return C;
299
5.21k
}
300
301
108
uint16_t BT::RegisterCell::cl(bool B) const {
302
108
  uint16_t W = width();
303
108
  uint16_t C = 0;
304
108
  BitValue V = B;
305
236
  while (C < W && Bits[W-(C+1)] == V)
306
128
    C++;
307
108
  return C;
308
108
}
309
310
77.1k
bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
311
77.1k
  uint16_t W = Bits.size();
312
77.1k
  if (RC.Bits.size() != W)
313
0
    return false;
314
16.7M
  
for (uint16_t i = 0; 77.1k
i < W;
++i16.7M
)
315
16.7M
    if (Bits[i] != RC[i])
316
47.1k
      return false;
317
77.1k
  
return true30.0k
;
318
77.1k
}
319
320
239k
BT::RegisterCell &BT::RegisterCell::regify(unsigned R) {
321
72.4M
  for (unsigned i = 0, n = width(); i < n; 
++i72.2M
) {
322
72.2M
    const BitValue &V = Bits[i];
323
72.2M
    if (V.Type == BitValue::Ref && 
V.RefI.Reg == 070.2M
)
324
10.2M
      Bits[i].RefI = BitRef(R, i);
325
72.2M
  }
326
239k
  return *this;
327
239k
}
328
329
932k
uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
330
932k
  // The general problem is with finding a register class that corresponds
331
932k
  // to a given reference reg:sub. There can be several such classes, and
332
932k
  // since we only care about the register size, it does not matter which
333
932k
  // such class we would find.
334
932k
  // The easiest way to accomplish what we want is to
335
932k
  // 1. find a physical register PhysR from the same class as RR.Reg,
336
932k
  // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
337
932k
  // 3. find a register class that contains PhysS.
338
932k
  if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) {
339
835k
    const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub);
340
835k
    return TRI.getRegSizeInBits(VC);
341
835k
  }
342
96.4k
  assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg));
343
96.4k
  unsigned PhysR = (RR.Sub == 0) ? RR.Reg : 
TRI.getSubReg(RR.Reg, RR.Sub)0
;
344
96.4k
  return getPhysRegBitWidth(PhysR);
345
96.4k
}
346
347
BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
348
482k
      const CellMapType &M) const {
349
482k
  uint16_t BW = getRegBitWidth(RR);
350
482k
351
482k
  // Physical registers are assumed to be present in the map with an unknown
352
482k
  // value. Don't actually insert anything in the map, just return the cell.
353
482k
  if (TargetRegisterInfo::isPhysicalRegister(RR.Reg))
354
21.1k
    return RegisterCell::self(0, BW);
355
461k
356
461k
  assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
357
461k
  // For virtual registers that belong to a class that is not tracked,
358
461k
  // generate an "unknown" value as well.
359
461k
  const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
360
461k
  if (!track(C))
361
0
    return RegisterCell::self(0, BW);
362
461k
363
461k
  CellMapType::const_iterator F = M.find(RR.Reg);
364
461k
  if (F != M.end()) {
365
350k
    if (!RR.Sub)
366
333k
      return F->second;
367
17.5k
    BitMask M = mask(RR.Reg, RR.Sub);
368
17.5k
    return F->second.extract(M);
369
17.5k
  }
370
110k
  // If not found, create a "top" entry, but do not insert it in the map.
371
110k
  return RegisterCell::top(BW);
372
110k
}
373
374
void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
375
266k
      CellMapType &M) const {
376
266k
  // While updating the cell map can be done in a meaningful way for
377
266k
  // a part of a register, it makes little sense to implement it as the
378
266k
  // SSA representation would never contain such "partial definitions".
379
266k
  if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
380
27.4k
    return;
381
238k
  assert(RR.Sub == 0 && "Unexpected sub-register in definition");
382
238k
  // Eliminate all ref-to-reg-0 bit values: replace them with "self".
383
238k
  M[RR.Reg] = RC.regify(RR.Reg);
384
238k
}
385
386
// Check if the cell represents a compile-time integer value.
387
0
bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
388
0
  uint16_t W = A.width();
389
0
  for (uint16_t i = 0; i < W; ++i)
390
0
    if (!A[i].is(0) && !A[i].is(1))
391
0
      return false;
392
0
  return true;
393
0
}
394
395
// Convert a cell to the integer value. The result must fit in uint64_t.
396
0
uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
397
0
  assert(isInt(A));
398
0
  uint64_t Val = 0;
399
0
  uint16_t W = A.width();
400
0
  for (uint16_t i = 0; i < W; ++i) {
401
0
    Val <<= 1;
402
0
    Val |= A[i].is(1);
403
0
  }
404
0
  return Val;
405
0
}
406
407
// Evaluator helper functions. These implement some common operation on
408
// register cells that can be used to implement target-specific instructions
409
// in a target-specific evaluator.
410
411
22.6k
BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
412
22.6k
  RegisterCell Res(W);
413
22.6k
  // For bits beyond the 63rd, this will generate the sign bit of V.
414
766k
  for (uint16_t i = 0; i < W; 
++i743k
) {
415
743k
    Res[i] = BitValue(V & 1);
416
743k
    V >>= 1;
417
743k
  }
418
22.6k
  return Res;
419
22.6k
}
420
421
0
BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
422
0
  const APInt &A = CI->getValue();
423
0
  uint16_t BW = A.getBitWidth();
424
0
  assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow");
425
0
  RegisterCell Res(BW);
426
0
  for (uint16_t i = 0; i < BW; ++i)
427
0
    Res[i] = A[i];
428
0
  return Res;
429
0
}
430
431
BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
432
14.8k
      const RegisterCell &A2) const {
433
14.8k
  uint16_t W = A1.width();
434
14.8k
  assert(W == A2.width());
435
14.8k
  RegisterCell Res(W);
436
14.8k
  bool Carry = false;
437
14.8k
  uint16_t I;
438
58.5k
  for (I = 0; I < W; 
++I43.6k
) {
439
57.3k
    const BitValue &V1 = A1[I];
440
57.3k
    const BitValue &V2 = A2[I];
441
57.3k
    if (!V1.num() || 
!V2.num()44.1k
)
442
13.6k
      break;
443
43.6k
    unsigned S = bool(V1) + bool(V2) + Carry;
444
43.6k
    Res[I] = BitValue(S & 1);
445
43.6k
    Carry = (S > 1);
446
43.6k
  }
447
57.9k
  for (; I < W; 
++I43.0k
) {
448
55.7k
    const BitValue &V1 = A1[I];
449
55.7k
    const BitValue &V2 = A2[I];
450
55.7k
    // If the next bit is same as Carry, the result will be 0 plus the
451
55.7k
    // other bit. The Carry bit will remain unchanged.
452
55.7k
    if (V1.is(Carry))
453
7.49k
      Res[I] = BitValue::ref(V2);
454
48.2k
    else if (V2.is(Carry))
455
35.5k
      Res[I] = BitValue::ref(V1);
456
12.7k
    else
457
12.7k
      break;
458
55.7k
  }
459
426k
  for (; I < W; 
++I411k
)
460
411k
    Res[I] = BitValue::self();
461
14.8k
  return Res;
462
14.8k
}
463
464
BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
465
1.56k
      const RegisterCell &A2) const {
466
1.56k
  uint16_t W = A1.width();
467
1.56k
  assert(W == A2.width());
468
1.56k
  RegisterCell Res(W);
469
1.56k
  bool Borrow = false;
470
1.56k
  uint16_t I;
471
2.24k
  for (I = 0; I < W; 
++I676
) {
472
2.23k
    const BitValue &V1 = A1[I];
473
2.23k
    const BitValue &V2 = A2[I];
474
2.23k
    if (!V1.num() || 
!V2.num()1.30k
)
475
1.55k
      break;
476
676
    unsigned S = bool(V1) - bool(V2) - Borrow;
477
676
    Res[I] = BitValue(S & 1);
478
676
    Borrow = (S > 1);
479
676
  }
480
1.96k
  for (; I < W; 
++I392
) {
481
1.93k
    const BitValue &V1 = A1[I];
482
1.93k
    const BitValue &V2 = A2[I];
483
1.93k
    if (V1.is(Borrow)) {
484
439
      Res[I] = BitValue::ref(V2);
485
439
      break;
486
439
    }
487
1.49k
    if (V2.is(Borrow))
488
392
      Res[I] = BitValue::ref(V1);
489
1.10k
    else
490
1.10k
      break;
491
1.49k
  }
492
54.5k
  for (; I < W; 
++I52.9k
)
493
52.9k
    Res[I] = BitValue::self();
494
1.56k
  return Res;
495
1.56k
}
496
497
BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
498
2.29k
      const RegisterCell &A2) const {
499
2.29k
  uint16_t W = A1.width() + A2.width();
500
2.29k
  uint16_t Z = A1.ct(false) + A2.ct(false);
501
2.29k
  RegisterCell Res(W);
502
2.29k
  Res.fill(0, Z, BitValue::Zero);
503
2.29k
  Res.fill(Z, W, BitValue::self());
504
2.29k
  return Res;
505
2.29k
}
506
507
BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
508
272
      const RegisterCell &A2) const {
509
272
  uint16_t W = A1.width() + A2.width();
510
272
  uint16_t Z = A1.ct(false) + A2.ct(false);
511
272
  RegisterCell Res(W);
512
272
  Res.fill(0, Z, BitValue::Zero);
513
272
  Res.fill(Z, W, BitValue::self());
514
272
  return Res;
515
272
}
516
517
BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
518
3.45k
      uint16_t Sh) const {
519
3.45k
  assert(Sh <= A1.width());
520
3.45k
  RegisterCell Res = RegisterCell::ref(A1);
521
3.45k
  Res.rol(Sh);
522
3.45k
  Res.fill(0, Sh, BitValue::Zero);
523
3.45k
  return Res;
524
3.45k
}
525
526
BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
527
1.23k
      uint16_t Sh) const {
528
1.23k
  uint16_t W = A1.width();
529
1.23k
  assert(Sh <= W);
530
1.23k
  RegisterCell Res = RegisterCell::ref(A1);
531
1.23k
  Res.rol(W-Sh);
532
1.23k
  Res.fill(W-Sh, W, BitValue::Zero);
533
1.23k
  return Res;
534
1.23k
}
535
536
BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
537
652
      uint16_t Sh) const {
538
652
  uint16_t W = A1.width();
539
652
  assert(Sh <= W);
540
652
  RegisterCell Res = RegisterCell::ref(A1);
541
652
  BitValue Sign = Res[W-1];
542
652
  Res.rol(W-Sh);
543
652
  Res.fill(W-Sh, W, Sign);
544
652
  return Res;
545
652
}
546
547
BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
548
1.57k
      const RegisterCell &A2) const {
549
1.57k
  uint16_t W = A1.width();
550
1.57k
  assert(W == A2.width());
551
1.57k
  RegisterCell Res(W);
552
59.6k
  for (uint16_t i = 0; i < W; 
++i58.0k
) {
553
58.0k
    const BitValue &V1 = A1[i];
554
58.0k
    const BitValue &V2 = A2[i];
555
58.0k
    if (V1.is(1))
556
1.34k
      Res[i] = BitValue::ref(V2);
557
56.7k
    else if (V2.is(1))
558
15.2k
      Res[i] = BitValue::ref(V1);
559
41.4k
    else if (V1.is(0) || 
V2.is(0)32.1k
)
560
28.8k
      Res[i] = BitValue::Zero;
561
12.6k
    else if (V1 == V2)
562
8
      Res[i] = V1;
563
12.6k
    else
564
12.6k
      Res[i] = BitValue::self();
565
58.0k
  }
566
1.57k
  return Res;
567
1.57k
}
568
569
BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
570
3.16k
      const RegisterCell &A2) const {
571
3.16k
  uint16_t W = A1.width();
572
3.16k
  assert(W == A2.width());
573
3.16k
  RegisterCell Res(W);
574
112k
  for (uint16_t i = 0; i < W; 
++i108k
) {
575
108k
    const BitValue &V1 = A1[i];
576
108k
    const BitValue &V2 = A2[i];
577
108k
    if (V1.is(1) || 
V2.is(1)106k
)
578
4.08k
      Res[i] = BitValue::One;
579
104k
    else if (V1.is(0))
580
61.4k
      Res[i] = BitValue::ref(V2);
581
43.2k
    else if (V2.is(0))
582
22.7k
      Res[i] = BitValue::ref(V1);
583
20.5k
    else if (V1 == V2)
584
0
      Res[i] = V1;
585
20.5k
    else
586
20.5k
      Res[i] = BitValue::self();
587
108k
  }
588
3.16k
  return Res;
589
3.16k
}
590
591
BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
592
400
      const RegisterCell &A2) const {
593
400
  uint16_t W = A1.width();
594
400
  assert(W == A2.width());
595
400
  RegisterCell Res(W);
596
17.4k
  for (uint16_t i = 0; i < W; 
++i17.0k
) {
597
17.0k
    const BitValue &V1 = A1[i];
598
17.0k
    const BitValue &V2 = A2[i];
599
17.0k
    if (V1.is(0))
600
2.20k
      Res[i] = BitValue::ref(V2);
601
14.8k
    else if (V2.is(0))
602
2.60k
      Res[i] = BitValue::ref(V1);
603
12.2k
    else if (V1 == V2)
604
0
      Res[i] = BitValue::Zero;
605
12.2k
    else
606
12.2k
      Res[i] = BitValue::self();
607
17.0k
  }
608
400
  return Res;
609
400
}
610
611
3.86k
BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
612
3.86k
  uint16_t W = A1.width();
613
3.86k
  RegisterCell Res(W);
614
129k
  for (uint16_t i = 0; i < W; 
++i125k
) {
615
125k
    const BitValue &V = A1[i];
616
125k
    if (V.is(0))
617
75.5k
      Res[i] = BitValue::One;
618
50.1k
    else if (V.is(1))
619
0
      Res[i] = BitValue::Zero;
620
50.1k
    else
621
50.1k
      Res[i] = BitValue::self();
622
125k
  }
623
3.86k
  return Res;
624
3.86k
}
625
626
BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
627
0
      uint16_t BitN) const {
628
0
  assert(BitN < A1.width());
629
0
  RegisterCell Res = RegisterCell::ref(A1);
630
0
  Res[BitN] = BitValue::One;
631
0
  return Res;
632
0
}
633
634
BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
635
0
      uint16_t BitN) const {
636
0
  assert(BitN < A1.width());
637
0
  RegisterCell Res = RegisterCell::ref(A1);
638
0
  Res[BitN] = BitValue::Zero;
639
0
  return Res;
640
0
}
641
642
BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
643
108
      uint16_t W) const {
644
108
  uint16_t C = A1.cl(B), AW = A1.width();
645
108
  // If the last leading non-B bit is not a constant, then we don't know
646
108
  // the real count.
647
108
  if ((C < AW && A1[AW-1-C].num()) || C == AW)
648
0
    return eIMM(C, W);
649
108
  return RegisterCell::self(0, W);
650
108
}
651
652
BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
653
86
      uint16_t W) const {
654
86
  uint16_t C = A1.ct(B), AW = A1.width();
655
86
  // If the last trailing non-B bit is not a constant, then we don't know
656
86
  // the real count.
657
86
  if ((C < AW && A1[C].num()) || 
C == AW82
)
658
4
    return eIMM(C, W);
659
82
  return RegisterCell::self(0, W);
660
82
}
661
662
BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
663
1.43k
      uint16_t FromN) const {
664
1.43k
  uint16_t W = A1.width();
665
1.43k
  assert(FromN <= W);
666
1.43k
  RegisterCell Res = RegisterCell::ref(A1);
667
1.43k
  BitValue Sign = Res[FromN-1];
668
1.43k
  // Sign-extend "inreg".
669
1.43k
  Res.fill(FromN, W, Sign);
670
1.43k
  return Res;
671
1.43k
}
672
673
BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
674
1.77k
      uint16_t FromN) const {
675
1.77k
  uint16_t W = A1.width();
676
1.77k
  assert(FromN <= W);
677
1.77k
  RegisterCell Res = RegisterCell::ref(A1);
678
1.77k
  Res.fill(FromN, W, BitValue::Zero);
679
1.77k
  return Res;
680
1.77k
}
681
682
BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
683
3.91k
      uint16_t B, uint16_t E) const {
684
3.91k
  uint16_t W = A1.width();
685
3.91k
  assert(B < W && E <= W);
686
3.91k
  if (B == E)
687
0
    return RegisterCell(0);
688
3.91k
  uint16_t Last = (E > 0) ? E-1 : 
W-10
;
689
3.91k
  RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
690
3.91k
  // Return shorter cell.
691
3.91k
  return Res;
692
3.91k
}
693
694
BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
695
100
      const RegisterCell &A2, uint16_t AtN) const {
696
100
  uint16_t W1 = A1.width(), W2 = A2.width();
697
100
  (void)W1;
698
100
  assert(AtN < W1 && AtN+W2 <= W1);
699
100
  // Copy bits from A1, insert A2 at position AtN.
700
100
  RegisterCell Res = RegisterCell::ref(A1);
701
100
  if (W2 > 0)
702
100
    Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
703
100
  return Res;
704
100
}
705
706
0
BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
707
0
  assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
708
0
  uint16_t W = getRegBitWidth(Reg);
709
0
  assert(W > 0 && "Cannot generate mask for empty register");
710
0
  return BitMask(0, W-1);
711
0
}
712
713
0
uint16_t BT::MachineEvaluator::getPhysRegBitWidth(unsigned Reg) const {
714
0
  assert(TargetRegisterInfo::isPhysicalRegister(Reg));
715
0
  const TargetRegisterClass &PC = *TRI.getMinimalPhysRegClass(Reg);
716
0
  return TRI.getRegSizeInBits(PC);
717
0
}
718
719
bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
720
                                    const CellMapType &Inputs,
721
122k
                                    CellMapType &Outputs) const {
722
122k
  unsigned Opc = MI.getOpcode();
723
122k
  switch (Opc) {
724
122k
    case TargetOpcode::REG_SEQUENCE: {
725
8.23k
      RegisterRef RD = MI.getOperand(0);
726
8.23k
      assert(RD.Sub == 0);
727
8.23k
      RegisterRef RS = MI.getOperand(1);
728
8.23k
      unsigned SS = MI.getOperand(2).getImm();
729
8.23k
      RegisterRef RT = MI.getOperand(3);
730
8.23k
      unsigned ST = MI.getOperand(4).getImm();
731
8.23k
      assert(SS != ST);
732
8.23k
733
8.23k
      uint16_t W = getRegBitWidth(RD);
734
8.23k
      RegisterCell Res(W);
735
8.23k
      Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
736
8.23k
      Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
737
8.23k
      putCell(RD, Res, Outputs);
738
8.23k
      break;
739
122k
    }
740
122k
741
122k
    case TargetOpcode::COPY: {
742
67.2k
      // COPY can transfer a smaller register into a wider one.
743
67.2k
      // If that is the case, fill the remaining high bits with 0.
744
67.2k
      RegisterRef RD = MI.getOperand(0);
745
67.2k
      RegisterRef RS = MI.getOperand(1);
746
67.2k
      assert(RD.Sub == 0);
747
67.2k
      uint16_t WD = getRegBitWidth(RD);
748
67.2k
      uint16_t WS = getRegBitWidth(RS);
749
67.2k
      assert(WD >= WS);
750
67.2k
      RegisterCell Src = getCell(RS, Inputs);
751
67.2k
      RegisterCell Res(WD);
752
67.2k
      Res.insert(Src, BitMask(0, WS-1));
753
67.2k
      Res.fill(WS, WD, BitValue::Zero);
754
67.2k
      putCell(RD, Res, Outputs);
755
67.2k
      break;
756
122k
    }
757
122k
758
122k
    default:
759
46.8k
      return false;
760
75.5k
  }
761
75.5k
762
75.5k
  return true;
763
75.5k
}
764
765
bool BT::UseQueueType::Cmp::operator()(const MachineInstr *InstA,
766
607k
                                       const MachineInstr *InstB) const {
767
607k
  // This is a comparison function for a priority queue: give higher priority
768
607k
  // to earlier instructions.
769
607k
  // This operator is used as "less", so returning "true" gives InstB higher
770
607k
  // priority (because then InstA < InstB).
771
607k
  if (InstA == InstB)
772
0
    return false;
773
607k
  const MachineBasicBlock *BA = InstA->getParent();
774
607k
  const MachineBasicBlock *BB = InstB->getParent();
775
607k
  if (BA != BB) {
776
145k
    // If the blocks are different, ideally the dominating block would
777
145k
    // have a higher priority, but it may be too expensive to check.
778
145k
    return BA->getNumber() > BB->getNumber();
779
145k
  }
780
461k
781
923k
  
auto getDist = [this] (const MachineInstr *MI) 461k
{
782
923k
    auto F = Dist.find(MI);
783
923k
    if (F != Dist.end())
784
829k
      return F->second;
785
93.8k
    MachineBasicBlock::const_iterator I = MI->getParent()->begin();
786
93.8k
    MachineBasicBlock::const_iterator E = MI->getIterator();
787
93.8k
    unsigned D = std::distance(I, E);
788
93.8k
    Dist.insert(std::make_pair(MI, D));
789
93.8k
    return D;
790
93.8k
  };
791
461k
792
461k
  return getDist(InstA) > getDist(InstB);
793
461k
}
794
795
// Main W-Z implementation.
796
797
16.8k
void BT::visitPHI(const MachineInstr &PI) {
798
16.8k
  int ThisN = PI.getParent()->getNumber();
799
16.8k
  if (Trace)
800
0
    dbgs() << "Visit FI(" << printMBBReference(*PI.getParent()) << "): " << PI;
801
16.8k
802
16.8k
  const MachineOperand &MD = PI.getOperand(0);
803
16.8k
  assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
804
16.8k
  RegisterRef DefRR(MD);
805
16.8k
  uint16_t DefBW = ME.getRegBitWidth(DefRR);
806
16.8k
807
16.8k
  RegisterCell DefC = ME.getCell(DefRR, Map);
808
16.8k
  if (DefC == RegisterCell::self(DefRR.Reg, DefBW))    // XXX slow
809
2.11k
    return;
810
14.7k
811
14.7k
  bool Changed = false;
812
14.7k
813
48.0k
  for (unsigned i = 1, n = PI.getNumOperands(); i < n; 
i += 233.2k
) {
814
33.2k
    const MachineBasicBlock *PB = PI.getOperand(i + 1).getMBB();
815
33.2k
    int PredN = PB->getNumber();
816
33.2k
    if (Trace)
817
0
      dbgs() << "  edge " << printMBBReference(*PB) << "->"
818
0
             << printMBBReference(*PI.getParent());
819
33.2k
    if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
820
9.73k
      if (Trace)
821
0
        dbgs() << " not executable\n";
822
9.73k
      continue;
823
9.73k
    }
824
23.5k
825
23.5k
    RegisterRef RU = PI.getOperand(i);
826
23.5k
    RegisterCell ResC = ME.getCell(RU, Map);
827
23.5k
    if (Trace)
828
0
      dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
829
0
             << " cell: " << ResC << "\n";
830
23.5k
    Changed |= DefC.meet(ResC, DefRR.Reg);
831
23.5k
  }
832
14.7k
833
14.7k
  if (Changed) {
834
10.5k
    if (Trace)
835
0
      dbgs() << "Output: " << printReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
836
0
             << " cell: " << DefC << "\n";
837
10.5k
    ME.putCell(DefRR, DefC, Map);
838
10.5k
    visitUsesOf(DefRR.Reg);
839
10.5k
  }
840
14.7k
}
841
842
232k
void BT::visitNonBranch(const MachineInstr &MI) {
843
232k
  if (Trace)
844
0
    dbgs() << "Visit MI(" << printMBBReference(*MI.getParent()) << "): " << MI;
845
232k
  if (MI.isDebugInstr())
846
84
    return;
847
232k
  assert(!MI.isBranch() && "Unexpected branch instruction");
848
232k
849
232k
  CellMapType ResMap;
850
232k
  bool Eval = ME.evaluate(MI, Map, ResMap);
851
232k
852
232k
  if (Trace && 
Eval0
) {
853
0
    for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
854
0
      const MachineOperand &MO = MI.getOperand(i);
855
0
      if (!MO.isReg() || !MO.isUse())
856
0
        continue;
857
0
      RegisterRef RU(MO);
858
0
      dbgs() << "  input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
859
0
             << " cell: " << ME.getCell(RU, Map) << "\n";
860
0
    }
861
0
    dbgs() << "Outputs:\n";
862
0
    for (const std::pair<unsigned, RegisterCell> &P : ResMap) {
863
0
      RegisterRef RD(P.first);
864
0
      dbgs() << "  " << printReg(P.first, &ME.TRI) << " cell: "
865
0
             << ME.getCell(RD, ResMap) << "\n";
866
0
    }
867
0
  }
868
232k
869
232k
  // Iterate over all definitions of the instruction, and update the
870
232k
  // cells accordingly.
871
684k
  for (const MachineOperand &MO : MI.operands()) {
872
684k
    // Visit register defs only.
873
684k
    if (!MO.isReg() || 
!MO.isDef()551k
)
874
454k
      continue;
875
229k
    RegisterRef RD(MO);
876
229k
    assert(RD.Sub == 0 && "Unexpected sub-register in definition");
877
229k
    if (!TargetRegisterInfo::isVirtualRegister(RD.Reg))
878
52.7k
      continue;
879
176k
880
176k
    bool Changed = false;
881
176k
    if (!Eval || 
ResMap.count(RD.Reg) == 0118k
) {
882
60.2k
      // Set to "ref" (aka "bottom").
883
60.2k
      uint16_t DefBW = ME.getRegBitWidth(RD);
884
60.2k
      RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
885
60.2k
      if (RefC != ME.getCell(RD, Map)) {
886
32.3k
        ME.putCell(RD, RefC, Map);
887
32.3k
        Changed = true;
888
32.3k
      }
889
116k
    } else {
890
116k
      RegisterCell DefC = ME.getCell(RD, Map);
891
116k
      RegisterCell ResC = ME.getCell(RD, ResMap);
892
116k
      // This is a non-phi instruction, so the values of the inputs come
893
116k
      // from the same registers each time this instruction is evaluated.
894
116k
      // During the propagation, the values of the inputs can become lowered
895
116k
      // in the sense of the lattice operation, which may cause different
896
116k
      // results to be calculated in subsequent evaluations. This should
897
116k
      // not cause the bottoming of the result in the map, since the new
898
116k
      // result is already reflecting the lowered inputs.
899
32.7M
      for (uint16_t i = 0, w = DefC.width(); i < w; 
++i32.6M
) {
900
32.6M
        BitValue &V = DefC[i];
901
32.6M
        // Bits that are already "bottom" should not be updated.
902
32.6M
        if (V.Type == BitValue::Ref && 
V.RefI.Reg == RD.Reg10.9M
)
903
530k
          continue;
904
32.1M
        // Same for those that are identical in DefC and ResC.
905
32.1M
        if (V == ResC[i])
906
10.7M
          continue;
907
21.3M
        V = ResC[i];
908
21.3M
        Changed = true;
909
21.3M
      }
910
116k
      if (Changed)
911
77.9k
        ME.putCell(RD, DefC, Map);
912
116k
    }
913
176k
    if (Changed)
914
110k
      visitUsesOf(RD.Reg);
915
176k
  }
916
232k
}
917
918
21.5k
void BT::visitBranchesFrom(const MachineInstr &BI) {
919
21.5k
  const MachineBasicBlock &B = *BI.getParent();
920
21.5k
  MachineBasicBlock::const_iterator It = BI, End = B.end();
921
21.5k
  BranchTargetList Targets, BTs;
922
21.5k
  bool FallsThrough = true, DefaultToAll = false;
923
21.5k
  int ThisN = B.getNumber();
924
21.5k
925
29.1k
  do {
926
29.1k
    BTs.clear();
927
29.1k
    const MachineInstr &MI = *It;
928
29.1k
    if (Trace)
929
0
      dbgs() << "Visit BR(" << printMBBReference(B) << "): " << MI;
930
29.1k
    assert(MI.isBranch() && "Expecting branch instruction");
931
29.1k
    InstrExec.insert(&MI);
932
29.1k
    bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
933
29.1k
    if (!Eval) {
934
20.8k
      // If the evaluation failed, we will add all targets. Keep going in
935
20.8k
      // the loop to mark all executable branches as such.
936
20.8k
      DefaultToAll = true;
937
20.8k
      FallsThrough = true;
938
20.8k
      if (Trace)
939
0
        dbgs() << "  failed to evaluate: will add all CFG successors\n";
940
20.8k
    } else 
if (8.27k
!DefaultToAll8.27k
) {
941
723
      // If evaluated successfully add the targets to the cumulative list.
942
723
      if (Trace) {
943
0
        dbgs() << "  adding targets:";
944
0
        for (unsigned i = 0, n = BTs.size(); i < n; ++i)
945
0
          dbgs() << " " << printMBBReference(*BTs[i]);
946
0
        if (FallsThrough)
947
0
          dbgs() << "\n  falls through\n";
948
0
        else
949
0
          dbgs() << "\n  does not fall through\n";
950
0
      }
951
723
      Targets.insert(BTs.begin(), BTs.end());
952
723
    }
953
29.1k
    ++It;
954
29.1k
  } while (FallsThrough && 
It != End20.8k
);
955
21.5k
956
21.5k
  if (!DefaultToAll) {
957
723
    // Need to add all CFG successors that lead to EH landing pads.
958
723
    // There won't be explicit branches to these blocks, but they must
959
723
    // be processed.
960
767
    for (const MachineBasicBlock *SB : B.successors()) {
961
767
      if (SB->isEHPad())
962
44
        Targets.insert(SB);
963
767
    }
964
723
    if (FallsThrough) {
965
0
      MachineFunction::const_iterator BIt = B.getIterator();
966
0
      MachineFunction::const_iterator Next = std::next(BIt);
967
0
      if (Next != MF.end())
968
0
        Targets.insert(&*Next);
969
0
    }
970
20.8k
  } else {
971
20.8k
    for (const MachineBasicBlock *SB : B.successors())
972
15.6k
      Targets.insert(SB);
973
20.8k
  }
974
21.5k
975
21.5k
  for (const MachineBasicBlock *TB : Targets)
976
16.3k
    FlowQ.push(CFGEdge(ThisN, TB->getNumber()));
977
21.5k
}
978
979
120k
void BT::visitUsesOf(unsigned Reg) {
980
120k
  if (Trace)
981
0
    dbgs() << "queuing uses of modified reg " << printReg(Reg, &ME.TRI)
982
0
           << " cell: " << ME.getCell(Reg, Map) << '\n';
983
120k
984
120k
  for (MachineInstr &UseI : MRI.use_nodbg_instructions(Reg))
985
159k
    UseQ.push(&UseI);
986
120k
}
987
988
248
BT::RegisterCell BT::get(RegisterRef RR) const {
989
248
  return ME.getCell(RR, Map);
990
248
}
991
992
576
void BT::put(RegisterRef RR, const RegisterCell &RC) {
993
576
  ME.putCell(RR, RC, Map);
994
576
}
995
996
// Replace all references to bits from OldRR with the corresponding bits
997
// in NewRR.
998
0
void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
999
0
  assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
1000
0
  BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
1001
0
  BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
1002
0
  uint16_t OMB = OM.first(), OME = OM.last();
1003
0
  uint16_t NMB = NM.first(), NME = NM.last();
1004
0
  (void)NME;
1005
0
  assert((OME-OMB == NME-NMB) &&
1006
0
         "Substituting registers of different lengths");
1007
0
  for (std::pair<const unsigned, RegisterCell> &P : Map) {
1008
0
    RegisterCell &RC = P.second;
1009
0
    for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
1010
0
      BitValue &V = RC[i];
1011
0
      if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
1012
0
        continue;
1013
0
      if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
1014
0
        continue;
1015
0
      V.RefI.Reg = NewRR.Reg;
1016
0
      V.RefI.Pos += NMB-OMB;
1017
0
    }
1018
0
  }
1019
0
}
1020
1021
// Check if the block has been "executed" during propagation. (If not, the
1022
// block is dead, but it may still appear to be reachable.)
1023
29.8k
bool BT::reached(const MachineBasicBlock *B) const {
1024
29.8k
  int BN = B->getNumber();
1025
29.8k
  assert(BN >= 0);
1026
29.8k
  return ReachedBB.count(BN);
1027
29.8k
}
1028
1029
// Visit an individual instruction. This could be a newly added instruction,
1030
// or one that has been modified by an optimization.
1031
171
void BT::visit(const MachineInstr &MI) {
1032
171
  assert(!MI.isBranch() && "Only non-branches are allowed");
1033
171
  InstrExec.insert(&MI);
1034
171
  visitNonBranch(MI);
1035
171
  // Make sure to flush all the pending use updates.
1036
171
  runUseQueue();
1037
171
  // The call to visitNonBranch could propagate the changes until a branch
1038
171
  // is actually visited. This could result in adding CFG edges to the flow
1039
171
  // queue. Since the queue won't be processed, clear it.
1040
171
  while (!FlowQ.empty())
1041
0
    FlowQ.pop();
1042
171
}
1043
1044
13.4k
void BT::reset() {
1045
13.4k
  EdgeExec.clear();
1046
13.4k
  InstrExec.clear();
1047
13.4k
  Map.clear();
1048
13.4k
  ReachedBB.clear();
1049
13.4k
  ReachedBB.reserve(MF.size());
1050
13.4k
}
1051
1052
23.4k
void BT::runEdgeQueue(BitVector &BlockScanned) {
1053
43.6k
  while (!FlowQ.empty()) {
1054
31.7k
    CFGEdge Edge = FlowQ.front();
1055
31.7k
    FlowQ.pop();
1056
31.7k
1057
31.7k
    if (EdgeExec.count(Edge))
1058
7.80k
      return;
1059
23.9k
    EdgeExec.insert(Edge);
1060
23.9k
    ReachedBB.insert(Edge.second);
1061
23.9k
1062
23.9k
    const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1063
23.9k
    MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1064
23.9k
    // Visit PHI nodes first.
1065
33.6k
    while (It != End && 
It->isPHI()33.3k
) {
1066
9.69k
      const MachineInstr &PI = *It++;
1067
9.69k
      InstrExec.insert(&PI);
1068
9.69k
      visitPHI(PI);
1069
9.69k
    }
1070
23.9k
1071
23.9k
    // If this block has already been visited through a flow graph edge,
1072
23.9k
    // then the instructions have already been processed. Any updates to
1073
23.9k
    // the cells would now only happen through visitUsesOf...
1074
23.9k
    if (BlockScanned[Edge.second])
1075
3.77k
      return;
1076
20.2k
    BlockScanned[Edge.second] = true;
1077
20.2k
1078
20.2k
    // Visit non-branch instructions.
1079
158k
    while (It != End && 
!It->isBranch()156k
) {
1080
138k
      const MachineInstr &MI = *It++;
1081
138k
      InstrExec.insert(&MI);
1082
138k
      visitNonBranch(MI);
1083
138k
    }
1084
20.2k
    // If block end has been reached, add the fall-through edge to the queue.
1085
20.2k
    if (It == End) {
1086
2.46k
      MachineFunction::const_iterator BIt = B.getIterator();
1087
2.46k
      MachineFunction::const_iterator Next = std::next(BIt);
1088
2.46k
      if (Next != MF.end() && 
B.isSuccessor(&*Next)2.14k
) {
1089
1.92k
        int ThisN = B.getNumber();
1090
1.92k
        int NextN = Next->getNumber();
1091
1.92k
        FlowQ.push(CFGEdge(ThisN, NextN));
1092
1.92k
      }
1093
17.7k
    } else {
1094
17.7k
      // Handle the remaining sequence of branches. This function will update
1095
17.7k
      // the work queue.
1096
17.7k
      visitBranchesFrom(*It);
1097
17.7k
    }
1098
20.2k
  } // while (!FlowQ->empty())
1099
23.4k
}
1100
1101
23.5k
void BT::runUseQueue() {
1102
132k
  while (!UseQ.empty()) {
1103
109k
    MachineInstr &UseI = *UseQ.front();
1104
109k
    UseQ.pop();
1105
109k
1106
109k
    if (!InstrExec.count(&UseI))
1107
4.43k
      continue;
1108
104k
    if (UseI.isPHI())
1109
7.19k
      visitPHI(UseI);
1110
97.5k
    else if (!UseI.isBranch())
1111
93.7k
      visitNonBranch(UseI);
1112
3.83k
    else
1113
3.83k
      visitBranchesFrom(UseI);
1114
104k
  }
1115
23.5k
}
1116
1117
13.4k
void BT::run() {
1118
13.4k
  reset();
1119
13.4k
  assert(FlowQ.empty());
1120
13.4k
1121
13.4k
  using MachineFlowGraphTraits = GraphTraits<const MachineFunction*>;
1122
13.4k
  const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1123
13.4k
1124
13.4k
  unsigned MaxBN = 0;
1125
20.2k
  for (const MachineBasicBlock &B : MF) {
1126
20.2k
    assert(B.getNumber() >= 0 && "Disconnected block");
1127
20.2k
    unsigned BN = B.getNumber();
1128
20.2k
    if (BN > MaxBN)
1129
6.29k
      MaxBN = BN;
1130
20.2k
  }
1131
13.4k
1132
13.4k
  // Keep track of visited blocks.
1133
13.4k
  BitVector BlockScanned(MaxBN+1);
1134
13.4k
1135
13.4k
  int EntryN = Entry->getNumber();
1136
13.4k
  // Generate a fake edge to get something to start with.
1137
13.4k
  FlowQ.push(CFGEdge(-1, EntryN));
1138
13.4k
1139
36.8k
  while (!FlowQ.empty() || 
!UseQ.empty()13.4k
) {
1140
23.4k
    runEdgeQueue(BlockScanned);
1141
23.4k
    runUseQueue();
1142
23.4k
  }
1143
13.4k
  UseQ.reset();
1144
13.4k
1145
13.4k
  if (Trace)
1146
0
    print_cells(dbgs() << "Cells after propagation:\n");
1147
13.4k
}