LLVM  9.0.0svn
BitTracker.cpp
Go to the documentation of this file.
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"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/Support/Debug.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  printv(unsigned r) : R(r) {}
81 
82  unsigned R;
83  };
84 
85  raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
86  if (PV.R)
87  OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R);
88  else
89  OS << 's';
90  return OS;
91  }
92 
93 } // end anonymous namespace
94 
95 namespace llvm {
96 
98  switch (BV.Type) {
99  case BT::BitValue::Top:
100  OS << 'T';
101  break;
102  case BT::BitValue::Zero:
103  OS << '0';
104  break;
105  case BT::BitValue::One:
106  OS << '1';
107  break;
108  case BT::BitValue::Ref:
109  OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
110  break;
111  }
112  return OS;
113  }
114 
116  unsigned n = RC.Bits.size();
117  OS << "{ w:" << n;
118  // Instead of printing each bit value individually, try to group them
119  // into logical segments, such as sequences of 0 or 1 bits or references
120  // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
121  // "Start" will be the index of the beginning of the most recent segment.
122  unsigned Start = 0;
123  bool SeqRef = false; // A sequence of refs to consecutive bits.
124  bool ConstRef = false; // A sequence of refs to the same bit.
125 
126  for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
127  const BT::BitValue &V = RC[i];
128  const BT::BitValue &SV = RC[Start];
129  bool IsRef = (V.Type == BT::BitValue::Ref);
130  // If the current value is the same as Start, skip to the next one.
131  if (!IsRef && V == SV)
132  continue;
133  if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
134  if (Start+1 == i) {
135  SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
136  ConstRef = (V.RefI.Pos == SV.RefI.Pos);
137  }
138  if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
139  continue;
140  if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
141  continue;
142  }
143 
144  // The current value is different. Print the previous one and reset
145  // the Start.
146  OS << " [" << Start;
147  unsigned Count = i - Start;
148  if (Count == 1) {
149  OS << "]:" << SV;
150  } else {
151  OS << '-' << i-1 << "]:";
152  if (SV.Type == BT::BitValue::Ref && SeqRef)
153  OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
154  << SV.RefI.Pos+(Count-1) << ']';
155  else
156  OS << SV;
157  }
158  Start = i;
159  SeqRef = ConstRef = false;
160  }
161 
162  OS << " [" << Start;
163  unsigned Count = n - Start;
164  if (n-Start == 1) {
165  OS << "]:" << RC[Start];
166  } else {
167  OS << '-' << n-1 << "]:";
168  const BT::BitValue &SV = RC[Start];
169  if (SV.Type == BT::BitValue::Ref && SeqRef)
170  OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
171  << SV.RefI.Pos+(Count-1) << ']';
172  else
173  OS << SV;
174  }
175  OS << " }";
176 
177  return OS;
178  }
179 
180 } // end namespace llvm
181 
183  for (const std::pair<unsigned, RegisterCell> P : Map)
184  dbgs() << printReg(P.first, &ME.TRI) << " -> " << P.second << "\n";
185 }
186 
188  : ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType), Trace(false) {
189 }
190 
192  delete &Map;
193 }
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 bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
202  // An example when "meet" can be invoked with SelfR == 0 is a phi node
203  // with a physical register as an operand.
204  assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR));
205  bool Changed = false;
206  for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
207  const BitValue &RCV = RC[i];
208  Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
209  }
210  return Changed;
211 }
212 
213 // Insert the entire cell RC into the current cell at position given by M.
215  const BitMask &M) {
216  uint16_t B = M.first(), E = M.last(), W = width();
217  // Sanity: M must be a valid mask for *this.
218  assert(B < W && E < W);
219  // Sanity: the masked part of *this must have the same number of bits
220  // as the source.
221  assert(B > E || E-B+1 == RC.width()); // B <= E => E-B+1 = |RC|.
222  assert(B <= E || E+(W-B)+1 == RC.width()); // E < B => E+(W-B)+1 = |RC|.
223  if (B <= E) {
224  for (uint16_t i = 0; i <= E-B; ++i)
225  Bits[i+B] = RC[i];
226  } else {
227  for (uint16_t i = 0; i < W-B; ++i)
228  Bits[i+B] = RC[i];
229  for (uint16_t i = 0; i <= E; ++i)
230  Bits[i] = RC[i+(W-B)];
231  }
232  return *this;
233 }
234 
236  uint16_t B = M.first(), E = M.last(), W = width();
237  assert(B < W && E < W);
238  if (B <= E) {
239  RegisterCell RC(E-B+1);
240  for (uint16_t i = B; i <= E; ++i)
241  RC.Bits[i-B] = Bits[i];
242  return RC;
243  }
244 
245  RegisterCell RC(E+(W-B)+1);
246  for (uint16_t i = 0; i < W-B; ++i)
247  RC.Bits[i] = Bits[i+B];
248  for (uint16_t i = 0; i <= E; ++i)
249  RC.Bits[i+(W-B)] = Bits[i];
250  return RC;
251 }
252 
254  // Rotate left (i.e. towards increasing bit indices).
255  // Swap the two parts: [0..W-Sh-1] [W-Sh..W-1]
256  uint16_t W = width();
257  Sh = Sh % W;
258  if (Sh == 0)
259  return *this;
260 
261  RegisterCell Tmp(W-Sh);
262  // Tmp = [0..W-Sh-1].
263  for (uint16_t i = 0; i < W-Sh; ++i)
264  Tmp[i] = Bits[i];
265  // Shift [W-Sh..W-1] to [0..Sh-1].
266  for (uint16_t i = 0; i < Sh; ++i)
267  Bits[i] = Bits[W-Sh+i];
268  // Copy Tmp to [Sh..W-1].
269  for (uint16_t i = 0; i < W-Sh; ++i)
270  Bits[i+Sh] = Tmp.Bits[i];
271  return *this;
272 }
273 
275  const BitValue &V) {
276  assert(B <= E);
277  while (B < E)
278  Bits[B++] = V;
279  return *this;
280 }
281 
283  // Append the cell given as the argument to the "this" cell.
284  // Bit 0 of RC becomes bit W of the result, where W is this->width().
285  uint16_t W = width(), WRC = RC.width();
286  Bits.resize(W+WRC);
287  for (uint16_t i = 0; i < WRC; ++i)
288  Bits[i+W] = RC.Bits[i];
289  return *this;
290 }
291 
292 uint16_t BT::RegisterCell::ct(bool B) const {
293  uint16_t W = width();
294  uint16_t C = 0;
295  BitValue V = B;
296  while (C < W && Bits[C] == V)
297  C++;
298  return C;
299 }
300 
301 uint16_t BT::RegisterCell::cl(bool B) const {
302  uint16_t W = width();
303  uint16_t C = 0;
304  BitValue V = B;
305  while (C < W && Bits[W-(C+1)] == V)
306  C++;
307  return C;
308 }
309 
311  uint16_t W = Bits.size();
312  if (RC.Bits.size() != W)
313  return false;
314  for (uint16_t i = 0; i < W; ++i)
315  if (Bits[i] != RC[i])
316  return false;
317  return true;
318 }
319 
321  for (unsigned i = 0, n = width(); i < n; ++i) {
322  const BitValue &V = Bits[i];
323  if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
324  Bits[i].RefI = BitRef(R, i);
325  }
326  return *this;
327 }
328 
330  // The general problem is with finding a register class that corresponds
331  // to a given reference reg:sub. There can be several such classes, and
332  // since we only care about the register size, it does not matter which
333  // such class we would find.
334  // The easiest way to accomplish what we want is to
335  // 1. find a physical register PhysR from the same class as RR.Reg,
336  // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
337  // 3. find a register class that contains PhysS.
339  const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub);
340  return TRI.getRegSizeInBits(VC);
341  }
343  unsigned PhysR = (RR.Sub == 0) ? RR.Reg : TRI.getSubReg(RR.Reg, RR.Sub);
344  return getPhysRegBitWidth(PhysR);
345 }
346 
348  const CellMapType &M) const {
349  uint16_t BW = getRegBitWidth(RR);
350 
351  // Physical registers are assumed to be present in the map with an unknown
352  // value. Don't actually insert anything in the map, just return the cell.
354  return RegisterCell::self(0, BW);
355 
357  // For virtual registers that belong to a class that is not tracked,
358  // generate an "unknown" value as well.
359  const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
360  if (!track(C))
361  return RegisterCell::self(0, BW);
362 
363  CellMapType::const_iterator F = M.find(RR.Reg);
364  if (F != M.end()) {
365  if (!RR.Sub)
366  return F->second;
367  BitMask M = mask(RR.Reg, RR.Sub);
368  return F->second.extract(M);
369  }
370  // If not found, create a "top" entry, but do not insert it in the map.
371  return RegisterCell::top(BW);
372 }
373 
375  CellMapType &M) const {
376  // While updating the cell map can be done in a meaningful way for
377  // a part of a register, it makes little sense to implement it as the
378  // SSA representation would never contain such "partial definitions".
380  return;
381  assert(RR.Sub == 0 && "Unexpected sub-register in definition");
382  // Eliminate all ref-to-reg-0 bit values: replace them with "self".
383  M[RR.Reg] = RC.regify(RR.Reg);
384 }
385 
386 // Check if the cell represents a compile-time integer value.
388  uint16_t W = A.width();
389  for (uint16_t i = 0; i < W; ++i)
390  if (!A[i].is(0) && !A[i].is(1))
391  return false;
392  return true;
393 }
394 
395 // Convert a cell to the integer value. The result must fit in uint64_t.
396 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
397  assert(isInt(A));
398  uint64_t Val = 0;
399  uint16_t W = A.width();
400  for (uint16_t i = 0; i < W; ++i) {
401  Val <<= 1;
402  Val |= A[i].is(1);
403  }
404  return Val;
405 }
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 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
412  RegisterCell Res(W);
413  // For bits beyond the 63rd, this will generate the sign bit of V.
414  for (uint16_t i = 0; i < W; ++i) {
415  Res[i] = BitValue(V & 1);
416  V >>= 1;
417  }
418  return Res;
419 }
420 
422  const APInt &A = CI->getValue();
423  uint16_t BW = A.getBitWidth();
424  assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow");
425  RegisterCell Res(BW);
426  for (uint16_t i = 0; i < BW; ++i)
427  Res[i] = A[i];
428  return Res;
429 }
430 
432  const RegisterCell &A2) const {
433  uint16_t W = A1.width();
434  assert(W == A2.width());
435  RegisterCell Res(W);
436  bool Carry = false;
437  uint16_t I;
438  for (I = 0; I < W; ++I) {
439  const BitValue &V1 = A1[I];
440  const BitValue &V2 = A2[I];
441  if (!V1.num() || !V2.num())
442  break;
443  unsigned S = bool(V1) + bool(V2) + Carry;
444  Res[I] = BitValue(S & 1);
445  Carry = (S > 1);
446  }
447  for (; I < W; ++I) {
448  const BitValue &V1 = A1[I];
449  const BitValue &V2 = A2[I];
450  // If the next bit is same as Carry, the result will be 0 plus the
451  // other bit. The Carry bit will remain unchanged.
452  if (V1.is(Carry))
453  Res[I] = BitValue::ref(V2);
454  else if (V2.is(Carry))
455  Res[I] = BitValue::ref(V1);
456  else
457  break;
458  }
459  for (; I < W; ++I)
460  Res[I] = BitValue::self();
461  return Res;
462 }
463 
465  const RegisterCell &A2) const {
466  uint16_t W = A1.width();
467  assert(W == A2.width());
468  RegisterCell Res(W);
469  bool Borrow = false;
470  uint16_t I;
471  for (I = 0; I < W; ++I) {
472  const BitValue &V1 = A1[I];
473  const BitValue &V2 = A2[I];
474  if (!V1.num() || !V2.num())
475  break;
476  unsigned S = bool(V1) - bool(V2) - Borrow;
477  Res[I] = BitValue(S & 1);
478  Borrow = (S > 1);
479  }
480  for (; I < W; ++I) {
481  const BitValue &V1 = A1[I];
482  const BitValue &V2 = A2[I];
483  if (V1.is(Borrow)) {
484  Res[I] = BitValue::ref(V2);
485  break;
486  }
487  if (V2.is(Borrow))
488  Res[I] = BitValue::ref(V1);
489  else
490  break;
491  }
492  for (; I < W; ++I)
493  Res[I] = BitValue::self();
494  return Res;
495 }
496 
498  const RegisterCell &A2) const {
499  uint16_t W = A1.width() + A2.width();
500  uint16_t Z = A1.ct(false) + A2.ct(false);
501  RegisterCell Res(W);
502  Res.fill(0, Z, BitValue::Zero);
503  Res.fill(Z, W, BitValue::self());
504  return Res;
505 }
506 
508  const RegisterCell &A2) const {
509  uint16_t W = A1.width() + A2.width();
510  uint16_t Z = A1.ct(false) + A2.ct(false);
511  RegisterCell Res(W);
512  Res.fill(0, Z, BitValue::Zero);
513  Res.fill(Z, W, BitValue::self());
514  return Res;
515 }
516 
518  uint16_t Sh) const {
519  assert(Sh <= A1.width());
521  Res.rol(Sh);
522  Res.fill(0, Sh, BitValue::Zero);
523  return Res;
524 }
525 
527  uint16_t Sh) const {
528  uint16_t W = A1.width();
529  assert(Sh <= W);
531  Res.rol(W-Sh);
532  Res.fill(W-Sh, W, BitValue::Zero);
533  return Res;
534 }
535 
537  uint16_t Sh) const {
538  uint16_t W = A1.width();
539  assert(Sh <= W);
541  BitValue Sign = Res[W-1];
542  Res.rol(W-Sh);
543  Res.fill(W-Sh, W, Sign);
544  return Res;
545 }
546 
548  const RegisterCell &A2) const {
549  uint16_t W = A1.width();
550  assert(W == A2.width());
551  RegisterCell Res(W);
552  for (uint16_t i = 0; i < W; ++i) {
553  const BitValue &V1 = A1[i];
554  const BitValue &V2 = A2[i];
555  if (V1.is(1))
556  Res[i] = BitValue::ref(V2);
557  else if (V2.is(1))
558  Res[i] = BitValue::ref(V1);
559  else if (V1.is(0) || V2.is(0))
560  Res[i] = BitValue::Zero;
561  else if (V1 == V2)
562  Res[i] = V1;
563  else
564  Res[i] = BitValue::self();
565  }
566  return Res;
567 }
568 
570  const RegisterCell &A2) const {
571  uint16_t W = A1.width();
572  assert(W == A2.width());
573  RegisterCell Res(W);
574  for (uint16_t i = 0; i < W; ++i) {
575  const BitValue &V1 = A1[i];
576  const BitValue &V2 = A2[i];
577  if (V1.is(1) || V2.is(1))
578  Res[i] = BitValue::One;
579  else if (V1.is(0))
580  Res[i] = BitValue::ref(V2);
581  else if (V2.is(0))
582  Res[i] = BitValue::ref(V1);
583  else if (V1 == V2)
584  Res[i] = V1;
585  else
586  Res[i] = BitValue::self();
587  }
588  return Res;
589 }
590 
592  const RegisterCell &A2) const {
593  uint16_t W = A1.width();
594  assert(W == A2.width());
595  RegisterCell Res(W);
596  for (uint16_t i = 0; i < W; ++i) {
597  const BitValue &V1 = A1[i];
598  const BitValue &V2 = A2[i];
599  if (V1.is(0))
600  Res[i] = BitValue::ref(V2);
601  else if (V2.is(0))
602  Res[i] = BitValue::ref(V1);
603  else if (V1 == V2)
604  Res[i] = BitValue::Zero;
605  else
606  Res[i] = BitValue::self();
607  }
608  return Res;
609 }
610 
612  uint16_t W = A1.width();
613  RegisterCell Res(W);
614  for (uint16_t i = 0; i < W; ++i) {
615  const BitValue &V = A1[i];
616  if (V.is(0))
617  Res[i] = BitValue::One;
618  else if (V.is(1))
619  Res[i] = BitValue::Zero;
620  else
621  Res[i] = BitValue::self();
622  }
623  return Res;
624 }
625 
627  uint16_t BitN) const {
628  assert(BitN < A1.width());
630  Res[BitN] = BitValue::One;
631  return Res;
632 }
633 
635  uint16_t BitN) const {
636  assert(BitN < A1.width());
638  Res[BitN] = BitValue::Zero;
639  return Res;
640 }
641 
643  uint16_t W) const {
644  uint16_t C = A1.cl(B), AW = A1.width();
645  // If the last leading non-B bit is not a constant, then we don't know
646  // the real count.
647  if ((C < AW && A1[AW-1-C].num()) || C == AW)
648  return eIMM(C, W);
649  return RegisterCell::self(0, W);
650 }
651 
653  uint16_t W) const {
654  uint16_t C = A1.ct(B), AW = A1.width();
655  // If the last trailing non-B bit is not a constant, then we don't know
656  // the real count.
657  if ((C < AW && A1[C].num()) || C == AW)
658  return eIMM(C, W);
659  return RegisterCell::self(0, W);
660 }
661 
663  uint16_t FromN) const {
664  uint16_t W = A1.width();
665  assert(FromN <= W);
667  BitValue Sign = Res[FromN-1];
668  // Sign-extend "inreg".
669  Res.fill(FromN, W, Sign);
670  return Res;
671 }
672 
674  uint16_t FromN) const {
675  uint16_t W = A1.width();
676  assert(FromN <= W);
678  Res.fill(FromN, W, BitValue::Zero);
679  return Res;
680 }
681 
683  uint16_t B, uint16_t E) const {
684  uint16_t W = A1.width();
685  assert(B < W && E <= W);
686  if (B == E)
687  return RegisterCell(0);
688  uint16_t Last = (E > 0) ? E-1 : W-1;
690  // Return shorter cell.
691  return Res;
692 }
693 
695  const RegisterCell &A2, uint16_t AtN) const {
696  uint16_t W1 = A1.width(), W2 = A2.width();
697  (void)W1;
698  assert(AtN < W1 && AtN+W2 <= W1);
699  // Copy bits from A1, insert A2 at position AtN.
701  if (W2 > 0)
702  Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
703  return Res;
704 }
705 
706 BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
707  assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
708  uint16_t W = getRegBitWidth(Reg);
709  assert(W > 0 && "Cannot generate mask for empty register");
710  return BitMask(0, W-1);
711 }
712 
716  return TRI.getRegSizeInBits(PC);
717 }
718 
720  const CellMapType &Inputs,
721  CellMapType &Outputs) const {
722  unsigned Opc = MI.getOpcode();
723  switch (Opc) {
724  case TargetOpcode::REG_SEQUENCE: {
725  RegisterRef RD = MI.getOperand(0);
726  assert(RD.Sub == 0);
727  RegisterRef RS = MI.getOperand(1);
728  unsigned SS = MI.getOperand(2).getImm();
729  RegisterRef RT = MI.getOperand(3);
730  unsigned ST = MI.getOperand(4).getImm();
731  assert(SS != ST);
732 
733  uint16_t W = getRegBitWidth(RD);
734  RegisterCell Res(W);
735  Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
736  Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
737  putCell(RD, Res, Outputs);
738  break;
739  }
740 
741  case TargetOpcode::COPY: {
742  // COPY can transfer a smaller register into a wider one.
743  // If that is the case, fill the remaining high bits with 0.
744  RegisterRef RD = MI.getOperand(0);
745  RegisterRef RS = MI.getOperand(1);
746  assert(RD.Sub == 0);
747  uint16_t WD = getRegBitWidth(RD);
748  uint16_t WS = getRegBitWidth(RS);
749  assert(WD >= WS);
750  RegisterCell Src = getCell(RS, Inputs);
751  RegisterCell Res(WD);
752  Res.insert(Src, BitMask(0, WS-1));
753  Res.fill(WS, WD, BitValue::Zero);
754  putCell(RD, Res, Outputs);
755  break;
756  }
757 
758  default:
759  return false;
760  }
761 
762  return true;
763 }
764 
765 bool BT::UseQueueType::Cmp::operator()(const MachineInstr *InstA,
766  const MachineInstr *InstB) const {
767  // This is a comparison function for a priority queue: give higher priority
768  // to earlier instructions.
769  // This operator is used as "less", so returning "true" gives InstB higher
770  // priority (because then InstA < InstB).
771  if (InstA == InstB)
772  return false;
773  const MachineBasicBlock *BA = InstA->getParent();
774  const MachineBasicBlock *BB = InstB->getParent();
775  if (BA != BB) {
776  // If the blocks are different, ideally the dominating block would
777  // have a higher priority, but it may be too expensive to check.
778  return BA->getNumber() > BB->getNumber();
779  }
780 
781  auto getDist = [this] (const MachineInstr *MI) {
782  auto F = Dist.find(MI);
783  if (F != Dist.end())
784  return F->second;
785  MachineBasicBlock::const_iterator I = MI->getParent()->begin();
786  MachineBasicBlock::const_iterator E = MI->getIterator();
787  unsigned D = std::distance(I, E);
788  Dist.insert(std::make_pair(MI, D));
789  return D;
790  };
791 
792  return getDist(InstA) > getDist(InstB);
793 }
794 
795 // Main W-Z implementation.
796 
797 void BT::visitPHI(const MachineInstr &PI) {
798  int ThisN = PI.getParent()->getNumber();
799  if (Trace)
800  dbgs() << "Visit FI(" << printMBBReference(*PI.getParent()) << "): " << PI;
801 
802  const MachineOperand &MD = PI.getOperand(0);
803  assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
804  RegisterRef DefRR(MD);
805  uint16_t DefBW = ME.getRegBitWidth(DefRR);
806 
807  RegisterCell DefC = ME.getCell(DefRR, Map);
808  if (DefC == RegisterCell::self(DefRR.Reg, DefBW)) // XXX slow
809  return;
810 
811  bool Changed = false;
812 
813  for (unsigned i = 1, n = PI.getNumOperands(); i < n; i += 2) {
814  const MachineBasicBlock *PB = PI.getOperand(i + 1).getMBB();
815  int PredN = PB->getNumber();
816  if (Trace)
817  dbgs() << " edge " << printMBBReference(*PB) << "->"
818  << printMBBReference(*PI.getParent());
819  if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
820  if (Trace)
821  dbgs() << " not executable\n";
822  continue;
823  }
824 
825  RegisterRef RU = PI.getOperand(i);
826  RegisterCell ResC = ME.getCell(RU, Map);
827  if (Trace)
828  dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
829  << " cell: " << ResC << "\n";
830  Changed |= DefC.meet(ResC, DefRR.Reg);
831  }
832 
833  if (Changed) {
834  if (Trace)
835  dbgs() << "Output: " << printReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
836  << " cell: " << DefC << "\n";
837  ME.putCell(DefRR, DefC, Map);
838  visitUsesOf(DefRR.Reg);
839  }
840 }
841 
842 void BT::visitNonBranch(const MachineInstr &MI) {
843  if (Trace)
844  dbgs() << "Visit MI(" << printMBBReference(*MI.getParent()) << "): " << MI;
845  if (MI.isDebugInstr())
846  return;
847  assert(!MI.isBranch() && "Unexpected branch instruction");
848 
849  CellMapType ResMap;
850  bool Eval = ME.evaluate(MI, Map, ResMap);
851 
852  if (Trace && Eval) {
853  for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
854  const MachineOperand &MO = MI.getOperand(i);
855  if (!MO.isReg() || !MO.isUse())
856  continue;
857  RegisterRef RU(MO);
858  dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
859  << " cell: " << ME.getCell(RU, Map) << "\n";
860  }
861  dbgs() << "Outputs:\n";
862  for (const std::pair<unsigned, RegisterCell> &P : ResMap) {
863  RegisterRef RD(P.first);
864  dbgs() << " " << printReg(P.first, &ME.TRI) << " cell: "
865  << ME.getCell(RD, ResMap) << "\n";
866  }
867  }
868 
869  // Iterate over all definitions of the instruction, and update the
870  // cells accordingly.
871  for (const MachineOperand &MO : MI.operands()) {
872  // Visit register defs only.
873  if (!MO.isReg() || !MO.isDef())
874  continue;
875  RegisterRef RD(MO);
876  assert(RD.Sub == 0 && "Unexpected sub-register in definition");
878  continue;
879 
880  bool Changed = false;
881  if (!Eval || ResMap.count(RD.Reg) == 0) {
882  // Set to "ref" (aka "bottom").
883  uint16_t DefBW = ME.getRegBitWidth(RD);
884  RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
885  if (RefC != ME.getCell(RD, Map)) {
886  ME.putCell(RD, RefC, Map);
887  Changed = true;
888  }
889  } else {
890  RegisterCell DefC = ME.getCell(RD, Map);
891  RegisterCell ResC = ME.getCell(RD, ResMap);
892  // This is a non-phi instruction, so the values of the inputs come
893  // from the same registers each time this instruction is evaluated.
894  // During the propagation, the values of the inputs can become lowered
895  // in the sense of the lattice operation, which may cause different
896  // results to be calculated in subsequent evaluations. This should
897  // not cause the bottoming of the result in the map, since the new
898  // result is already reflecting the lowered inputs.
899  for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
900  BitValue &V = DefC[i];
901  // Bits that are already "bottom" should not be updated.
902  if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
903  continue;
904  // Same for those that are identical in DefC and ResC.
905  if (V == ResC[i])
906  continue;
907  V = ResC[i];
908  Changed = true;
909  }
910  if (Changed)
911  ME.putCell(RD, DefC, Map);
912  }
913  if (Changed)
914  visitUsesOf(RD.Reg);
915  }
916 }
917 
918 void BT::visitBranchesFrom(const MachineInstr &BI) {
919  const MachineBasicBlock &B = *BI.getParent();
920  MachineBasicBlock::const_iterator It = BI, End = B.end();
921  BranchTargetList Targets, BTs;
922  bool FallsThrough = true, DefaultToAll = false;
923  int ThisN = B.getNumber();
924 
925  do {
926  BTs.clear();
927  const MachineInstr &MI = *It;
928  if (Trace)
929  dbgs() << "Visit BR(" << printMBBReference(B) << "): " << MI;
930  assert(MI.isBranch() && "Expecting branch instruction");
931  InstrExec.insert(&MI);
932  bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
933  if (!Eval) {
934  // If the evaluation failed, we will add all targets. Keep going in
935  // the loop to mark all executable branches as such.
936  DefaultToAll = true;
937  FallsThrough = true;
938  if (Trace)
939  dbgs() << " failed to evaluate: will add all CFG successors\n";
940  } else if (!DefaultToAll) {
941  // If evaluated successfully add the targets to the cumulative list.
942  if (Trace) {
943  dbgs() << " adding targets:";
944  for (unsigned i = 0, n = BTs.size(); i < n; ++i)
945  dbgs() << " " << printMBBReference(*BTs[i]);
946  if (FallsThrough)
947  dbgs() << "\n falls through\n";
948  else
949  dbgs() << "\n does not fall through\n";
950  }
951  Targets.insert(BTs.begin(), BTs.end());
952  }
953  ++It;
954  } while (FallsThrough && It != End);
955 
956  if (!DefaultToAll) {
957  // Need to add all CFG successors that lead to EH landing pads.
958  // There won't be explicit branches to these blocks, but they must
959  // be processed.
960  for (const MachineBasicBlock *SB : B.successors()) {
961  if (SB->isEHPad())
962  Targets.insert(SB);
963  }
964  if (FallsThrough) {
966  MachineFunction::const_iterator Next = std::next(BIt);
967  if (Next != MF.end())
968  Targets.insert(&*Next);
969  }
970  } else {
971  for (const MachineBasicBlock *SB : B.successors())
972  Targets.insert(SB);
973  }
974 
975  for (const MachineBasicBlock *TB : Targets)
976  FlowQ.push(CFGEdge(ThisN, TB->getNumber()));
977 }
978 
979 void BT::visitUsesOf(unsigned Reg) {
980  if (Trace)
981  dbgs() << "queuing uses of modified reg " << printReg(Reg, &ME.TRI)
982  << " cell: " << ME.getCell(Reg, Map) << '\n';
983 
984  for (MachineInstr &UseI : MRI.use_nodbg_instructions(Reg))
985  UseQ.push(&UseI);
986 }
987 
989  return ME.getCell(RR, Map);
990 }
991 
992 void BT::put(RegisterRef RR, const RegisterCell &RC) {
993  ME.putCell(RR, RC, Map);
994 }
995 
996 // Replace all references to bits from OldRR with the corresponding bits
997 // in NewRR.
998 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
999  assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
1000  BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
1001  BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
1002  uint16_t OMB = OM.first(), OME = OM.last();
1003  uint16_t NMB = NM.first(), NME = NM.last();
1004  (void)NME;
1005  assert((OME-OMB == NME-NMB) &&
1006  "Substituting registers of different lengths");
1007  for (std::pair<const unsigned, RegisterCell> &P : Map) {
1008  RegisterCell &RC = P.second;
1009  for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
1010  BitValue &V = RC[i];
1011  if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
1012  continue;
1013  if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
1014  continue;
1015  V.RefI.Reg = NewRR.Reg;
1016  V.RefI.Pos += NMB-OMB;
1017  }
1018  }
1019 }
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 bool BT::reached(const MachineBasicBlock *B) const {
1024  int BN = B->getNumber();
1025  assert(BN >= 0);
1026  return ReachedBB.count(BN);
1027 }
1028 
1029 // Visit an individual instruction. This could be a newly added instruction,
1030 // or one that has been modified by an optimization.
1031 void BT::visit(const MachineInstr &MI) {
1032  assert(!MI.isBranch() && "Only non-branches are allowed");
1033  InstrExec.insert(&MI);
1034  visitNonBranch(MI);
1035  // Make sure to flush all the pending use updates.
1036  runUseQueue();
1037  // The call to visitNonBranch could propagate the changes until a branch
1038  // is actually visited. This could result in adding CFG edges to the flow
1039  // queue. Since the queue won't be processed, clear it.
1040  while (!FlowQ.empty())
1041  FlowQ.pop();
1042 }
1043 
1044 void BT::reset() {
1045  EdgeExec.clear();
1046  InstrExec.clear();
1047  Map.clear();
1048  ReachedBB.clear();
1049  ReachedBB.reserve(MF.size());
1050 }
1051 
1052 void BT::runEdgeQueue(BitVector &BlockScanned) {
1053  while (!FlowQ.empty()) {
1054  CFGEdge Edge = FlowQ.front();
1055  FlowQ.pop();
1056 
1057  if (EdgeExec.count(Edge))
1058  return;
1059  EdgeExec.insert(Edge);
1060  ReachedBB.insert(Edge.second);
1061 
1062  const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1063  MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1064  // Visit PHI nodes first.
1065  while (It != End && It->isPHI()) {
1066  const MachineInstr &PI = *It++;
1067  InstrExec.insert(&PI);
1068  visitPHI(PI);
1069  }
1070 
1071  // If this block has already been visited through a flow graph edge,
1072  // then the instructions have already been processed. Any updates to
1073  // the cells would now only happen through visitUsesOf...
1074  if (BlockScanned[Edge.second])
1075  return;
1076  BlockScanned[Edge.second] = true;
1077 
1078  // Visit non-branch instructions.
1079  while (It != End && !It->isBranch()) {
1080  const MachineInstr &MI = *It++;
1081  InstrExec.insert(&MI);
1082  visitNonBranch(MI);
1083  }
1084  // If block end has been reached, add the fall-through edge to the queue.
1085  if (It == End) {
1087  MachineFunction::const_iterator Next = std::next(BIt);
1088  if (Next != MF.end() && B.isSuccessor(&*Next)) {
1089  int ThisN = B.getNumber();
1090  int NextN = Next->getNumber();
1091  FlowQ.push(CFGEdge(ThisN, NextN));
1092  }
1093  } else {
1094  // Handle the remaining sequence of branches. This function will update
1095  // the work queue.
1096  visitBranchesFrom(*It);
1097  }
1098  } // while (!FlowQ->empty())
1099 }
1100 
1101 void BT::runUseQueue() {
1102  while (!UseQ.empty()) {
1103  MachineInstr &UseI = *UseQ.front();
1104  UseQ.pop();
1105 
1106  if (!InstrExec.count(&UseI))
1107  continue;
1108  if (UseI.isPHI())
1109  visitPHI(UseI);
1110  else if (!UseI.isBranch())
1111  visitNonBranch(UseI);
1112  else
1113  visitBranchesFrom(UseI);
1114  }
1115 }
1116 
1117 void BT::run() {
1118  reset();
1119  assert(FlowQ.empty());
1120 
1121  using MachineFlowGraphTraits = GraphTraits<const MachineFunction*>;
1122  const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1123 
1124  unsigned MaxBN = 0;
1125  for (const MachineBasicBlock &B : MF) {
1126  assert(B.getNumber() >= 0 && "Disconnected block");
1127  unsigned BN = B.getNumber();
1128  if (BN > MaxBN)
1129  MaxBN = BN;
1130  }
1131 
1132  // Keep track of visited blocks.
1133  BitVector BlockScanned(MaxBN+1);
1134 
1135  int EntryN = Entry->getNumber();
1136  // Generate a fake edge to get something to start with.
1137  FlowQ.push(CFGEdge(-1, EntryN));
1138 
1139  while (!FlowQ.empty() || !UseQ.empty()) {
1140  runEdgeQueue(BlockScanned);
1141  runUseQueue();
1142  }
1143  UseQ.reset();
1144 
1145  if (Trace)
1146  print_cells(dbgs() << "Cells after propagation:\n");
1147 }
virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs, CellMapType &Outputs) const
Definition: BitTracker.cpp:719
uint64_t CallInst * C
RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:517
const TargetRegisterInfo & TRI
Definition: BitTracker.h:489
MachineBasicBlock * getMBB() const
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
RegisterCell & fill(uint16_t B, uint16_t E, const BitValue &V)
Definition: BitTracker.cpp:274
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:536
static RegisterCell top(uint16_t Width)
Definition: BitTracker.h:371
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const
Definition: BitTracker.cpp:374
unsigned Reg
void visit(const MachineInstr &MI)
static RegisterCell self(unsigned Reg, uint16_t Width)
Definition: BitTracker.h:363
RegisterCell & rol(uint16_t Sh)
Definition: BitTracker.cpp:253
F(f)
bool isInt(const RegisterCell &A) const
Definition: BitTracker.cpp:387
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:458
bool isPHI() const
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:569
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
iterator_range< succ_iterator > successors()
void print_cells(raw_ostream &OS) const
Definition: BitTracker.cpp:182
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
RegisterCell extract(const BitMask &M) const
Definition: BitTracker.cpp:235
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:526
zlib-gnu style compression
This file implements a class to represent arbitrary precision integral constant values and operations...
uint16_t cl(bool B) const
Definition: BitTracker.cpp:301
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:431
bool reached(const MachineBasicBlock *B) const
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:656
RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const
Definition: BitTracker.cpp:642
#define P(N)
RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:464
RegisterCell eIMM(int64_t V, uint16_t W) const
Definition: BitTracker.cpp:411
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
bool operator==(const RegisterCell &RC) const
Definition: BitTracker.cpp:310
RegisterCell eNOT(const RegisterCell &A1) const
Definition: BitTracker.cpp:611
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
virtual const TargetRegisterClass & composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const
Definition: BitTracker.h:481
unsigned getSubReg(unsigned Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo...
RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:547
void subst(RegisterRef OldRR, RegisterRef NewRR)
Definition: BitTracker.cpp:998
virtual uint16_t getPhysRegBitWidth(unsigned Reg) const
Definition: BitTracker.cpp:713
self_iterator getIterator()
Definition: ilist_node.h:81
virtual bool track(const TargetRegisterClass *RC) const
Definition: BitTracker.h:466
virtual BitMask mask(unsigned Reg, unsigned Sub) const
Definition: BitTracker.cpp:706
size_t size() const
Definition: SmallVector.h:52
RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2, uint16_t AtN) const
Definition: BitTracker.cpp:694
bool isDebugInstr() const
Definition: MachineInstr.h:998
std::map< unsigned, RegisterCell > CellMapType
Definition: BitTracker.h:44
RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:497
uint16_t getRegBitWidth(const RegisterRef &RR) const
Definition: BitTracker.cpp:329
Iterator for intrusive lists based on ilist_node.
uint16_t first() const
Definition: BitTracker.h:290
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
uint16_t last() const
Definition: BitTracker.h:291
static BitValue self(const BitRef &Self=BitRef())
Definition: BitTracker.h:279
RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const
Definition: BitTracker.cpp:626
uint64_t toInt(const RegisterCell &A) const
Definition: BitTracker.cpp:396
MachineOperand class - Representation of each machine instruction operand.
RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:591
RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const
Definition: BitTracker.cpp:652
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const
Definition: BitTracker.cpp:634
bool is(unsigned T) const
Definition: BitTracker.h:208
MachineRegisterInfo & MRI
Definition: BitTracker.h:490
int64_t getImm() const
uint16_t ct(bool B) const
Definition: BitTracker.cpp:292
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void clear()
Completely clear the SetVector.
Definition: SetVector.h:215
Class for arbitrary precision integers.
Definition: APInt.h:69
RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const
Definition: BitTracker.cpp:347
RegisterCell & insert(const RegisterCell &RC, const BitMask &M)
Definition: BitTracker.cpp:214
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:253
Representation of each machine instruction.
Definition: MachineInstr.h:63
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
RegisterCell & cat(const RegisterCell &RC)
Definition: BitTracker.cpp:282
BitTracker(const MachineEvaluator &E, MachineFunction &F)
Definition: BitTracker.cpp:187
#define I(x, y, z)
Definition: MD5.cpp:58
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2038
const TargetRegisterClass * getMinimalPhysRegClass(unsigned Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
RegisterCell get(RegisterRef RR) const
Definition: BitTracker.cpp:988
bool isReg() const
isReg - Tests if this is a MO_Register operand.
RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const
Definition: BitTracker.cpp:682
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const
Definition: BitTracker.cpp:662
RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:507
A vector that has set insertion semantics.
Definition: SetVector.h:40
void put(RegisterRef RR, const RegisterCell &RC)
Definition: BitTracker.cpp:992
RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const
Definition: BitTracker.cpp:673
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool meet(const RegisterCell &RC, unsigned SelfR)
Definition: BitTracker.cpp:201
IRTranslator LLVM IR MI
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
RegisterCell & regify(unsigned R)
Definition: BitTracker.cpp:320
static RegisterCell ref(const RegisterCell &C)
Definition: BitTracker.h:379
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(unsigned Reg) const
static BitValue ref(const BitValue &V)
Definition: BitTracker.h:270
void resize(size_type N)
Definition: SmallVector.h:343