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