LLVM  13.0.0git
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' << Register::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.
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 || SelfR.isVirtual());
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 
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 
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.
338  if (RR.Reg.isVirtual()) {
339  const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub);
340  return TRI.getRegSizeInBits(VC);
341  }
342  assert(RR.Reg.isPhysical());
343  MCRegister PhysR =
344  (RR.Sub == 0) ? RR.Reg.asMCReg() : 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.
354  if (RR.Reg.isPhysical())
355  return RegisterCell::self(0, BW);
356 
357  assert(RR.Reg.isVirtual());
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".
380  if (!RR.Reg.isVirtual())
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 
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 
708  assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
710  assert(W > 0 && "Cannot generate mask for empty register");
711  return BitMask(0, W-1);
712 }
713 
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<const 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");
877  if (!RD.Reg.isVirtual())
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 (B.mayHaveInlineAsmBr())
957  DefaultToAll = true;
958 
959  if (!DefaultToAll) {
960  // Need to add all CFG successors that lead to EH landing pads.
961  // There won't be explicit branches to these blocks, but they must
962  // be processed.
963  for (const MachineBasicBlock *SB : B.successors()) {
964  if (SB->isEHPad())
965  Targets.insert(SB);
966  }
967  if (FallsThrough) {
968  MachineFunction::const_iterator BIt = B.getIterator();
969  MachineFunction::const_iterator Next = std::next(BIt);
970  if (Next != MF.end())
971  Targets.insert(&*Next);
972  }
973  } else {
974  for (const MachineBasicBlock *SB : B.successors())
975  Targets.insert(SB);
976  }
977 
978  for (const MachineBasicBlock *TB : Targets)
979  FlowQ.push(CFGEdge(ThisN, TB->getNumber()));
980 }
981 
982 void BT::visitUsesOf(Register Reg) {
983  if (Trace)
984  dbgs() << "queuing uses of modified reg " << printReg(Reg, &ME.TRI)
985  << " cell: " << ME.getCell(Reg, Map) << '\n';
986 
987  for (MachineInstr &UseI : MRI.use_nodbg_instructions(Reg))
988  UseQ.push(&UseI);
989 }
990 
992  return ME.getCell(RR, Map);
993 }
994 
995 void BT::put(RegisterRef RR, const RegisterCell &RC) {
996  ME.putCell(RR, RC, Map);
997 }
998 
999 // Replace all references to bits from OldRR with the corresponding bits
1000 // in NewRR.
1001 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
1002  assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
1003  BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
1004  BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
1005  uint16_t OMB = OM.first(), OME = OM.last();
1006  uint16_t NMB = NM.first(), NME = NM.last();
1007  (void)NME;
1008  assert((OME-OMB == NME-NMB) &&
1009  "Substituting registers of different lengths");
1010  for (std::pair<const unsigned, RegisterCell> &P : Map) {
1011  RegisterCell &RC = P.second;
1012  for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
1013  BitValue &V = RC[i];
1014  if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
1015  continue;
1016  if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
1017  continue;
1018  V.RefI.Reg = NewRR.Reg;
1019  V.RefI.Pos += NMB-OMB;
1020  }
1021  }
1022 }
1023 
1024 // Check if the block has been "executed" during propagation. (If not, the
1025 // block is dead, but it may still appear to be reachable.)
1026 bool BT::reached(const MachineBasicBlock *B) const {
1027  int BN = B->getNumber();
1028  assert(BN >= 0);
1029  return ReachedBB.count(BN);
1030 }
1031 
1032 // Visit an individual instruction. This could be a newly added instruction,
1033 // or one that has been modified by an optimization.
1034 void BT::visit(const MachineInstr &MI) {
1035  assert(!MI.isBranch() && "Only non-branches are allowed");
1036  InstrExec.insert(&MI);
1037  visitNonBranch(MI);
1038  // Make sure to flush all the pending use updates.
1039  runUseQueue();
1040  // The call to visitNonBranch could propagate the changes until a branch
1041  // is actually visited. This could result in adding CFG edges to the flow
1042  // queue. Since the queue won't be processed, clear it.
1043  while (!FlowQ.empty())
1044  FlowQ.pop();
1045 }
1046 
1047 void BT::reset() {
1048  EdgeExec.clear();
1049  InstrExec.clear();
1050  Map.clear();
1051  ReachedBB.clear();
1052  ReachedBB.reserve(MF.size());
1053 }
1054 
1055 void BT::runEdgeQueue(BitVector &BlockScanned) {
1056  while (!FlowQ.empty()) {
1057  CFGEdge Edge = FlowQ.front();
1058  FlowQ.pop();
1059 
1060  if (EdgeExec.count(Edge))
1061  return;
1062  EdgeExec.insert(Edge);
1063  ReachedBB.insert(Edge.second);
1064 
1065  const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1066  MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1067  // Visit PHI nodes first.
1068  while (It != End && It->isPHI()) {
1069  const MachineInstr &PI = *It++;
1070  InstrExec.insert(&PI);
1071  visitPHI(PI);
1072  }
1073 
1074  // If this block has already been visited through a flow graph edge,
1075  // then the instructions have already been processed. Any updates to
1076  // the cells would now only happen through visitUsesOf...
1077  if (BlockScanned[Edge.second])
1078  return;
1079  BlockScanned[Edge.second] = true;
1080 
1081  // Visit non-branch instructions.
1082  while (It != End && !It->isBranch()) {
1083  const MachineInstr &MI = *It++;
1084  InstrExec.insert(&MI);
1085  visitNonBranch(MI);
1086  }
1087  // If block end has been reached, add the fall-through edge to the queue.
1088  if (It == End) {
1089  MachineFunction::const_iterator BIt = B.getIterator();
1090  MachineFunction::const_iterator Next = std::next(BIt);
1091  if (Next != MF.end() && B.isSuccessor(&*Next)) {
1092  int ThisN = B.getNumber();
1093  int NextN = Next->getNumber();
1094  FlowQ.push(CFGEdge(ThisN, NextN));
1095  }
1096  } else {
1097  // Handle the remaining sequence of branches. This function will update
1098  // the work queue.
1099  visitBranchesFrom(*It);
1100  }
1101  } // while (!FlowQ->empty())
1102 }
1103 
1104 void BT::runUseQueue() {
1105  while (!UseQ.empty()) {
1106  MachineInstr &UseI = *UseQ.front();
1107  UseQ.pop();
1108 
1109  if (!InstrExec.count(&UseI))
1110  continue;
1111  if (UseI.isPHI())
1112  visitPHI(UseI);
1113  else if (!UseI.isBranch())
1114  visitNonBranch(UseI);
1115  else
1116  visitBranchesFrom(UseI);
1117  }
1118 }
1119 
1120 void BT::run() {
1121  reset();
1122  assert(FlowQ.empty());
1123 
1124  using MachineFlowGraphTraits = GraphTraits<const MachineFunction*>;
1125  const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1126 
1127  unsigned MaxBN = 0;
1128  for (const MachineBasicBlock &B : MF) {
1129  assert(B.getNumber() >= 0 && "Disconnected block");
1130  unsigned BN = B.getNumber();
1131  if (BN > MaxBN)
1132  MaxBN = BN;
1133  }
1134 
1135  // Keep track of visited blocks.
1136  BitVector BlockScanned(MaxBN+1);
1137 
1138  int EntryN = Entry->getNumber();
1139  // Generate a fake edge to get something to start with.
1140  FlowQ.push(CFGEdge(-1, EntryN));
1141 
1142  while (!FlowQ.empty() || !UseQ.empty()) {
1143  runEdgeQueue(BlockScanned);
1144  runUseQueue();
1145  }
1146  UseQ.reset();
1147 
1148  if (Trace)
1149  print_cells(dbgs() << "Cells after propagation:\n");
1150 }
i
i
Definition: README.txt:29
llvm::MachineInstr::isBranch
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:844
llvm::BitTracker::subst
void subst(RegisterRef OldRR, RegisterRef NewRR)
Definition: BitTracker.cpp:1001
is
should just be implemented with a CLZ instruction Since there are other e that share this it would be best to implement this in a target independent as zero is the default value for the binary encoder e add r0 add r5 Register operands should be distinct That is
Definition: README.txt:725
llvm::BitTracker::BitTracker
BitTracker(const MachineEvaluator &E, MachineFunction &F)
Definition: BitTracker.cpp:187
llvm::BitTracker::MachineEvaluator::eORL
RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:570
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
MachineInstr.h
llvm
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::BitTracker::RegisterCell::top
static RegisterCell top(uint16_t Width)
Definition: BitTracker.h:372
llvm::detail::DenseSetImpl::reserve
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
Definition: DenseSet.h:90
llvm::BitTracker::MachineEvaluator::eSXT
RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const
Definition: BitTracker.cpp:663
llvm::BitTracker::RegisterCell::regify
RegisterCell & regify(unsigned R)
Definition: BitTracker.cpp:320
llvm::BitTracker::MachineEvaluator::eASR
RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:537
llvm::BitTracker::BitValue::RefI
BitRef RefI
Definition: BitTracker.h:192
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BitTracker::RegisterCell::meet
bool meet(const RegisterCell &RC, Register SelfR)
Definition: BitTracker.cpp:201
llvm::BitTracker::MachineEvaluator::getPhysRegBitWidth
virtual uint16_t getPhysRegBitWidth(MCRegister Reg) const
Definition: BitTracker.cpp:714
llvm::BitTracker::RegisterCell::ref
static RegisterCell ref(const RegisterCell &C)
Definition: BitTracker.h:380
llvm::BitTracker::RegisterRef::Sub
unsigned Sub
Definition: BitTracker.h:147
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:131
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:134
llvm::MachineFunction::end
iterator end()
Definition: MachineFunction.h:742
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
MachineBasicBlock.h
llvm::BitTracker::BitValue::Ref
@ Ref
Definition: BitTracker.h:160
llvm::BitTracker::MachineEvaluator::eZXT
RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const
Definition: BitTracker.cpp:674
llvm::MachineRegisterInfo::use_nodbg_instructions
iterator_range< use_instr_nodbg_iterator > use_nodbg_instructions(Register Reg) const
Definition: MachineRegisterInfo.h:543
APInt.h
llvm::BitTracker::~BitTracker
~BitTracker()
Definition: BitTracker.cpp:191
llvm::BitTracker::MachineEvaluator::evaluate
virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs, CellMapType &Outputs) const
Definition: BitTracker.cpp:719
llvm::BitTracker::BitMask
Definition: BitTracker.h:287
llvm::BitTracker::CellMapType
std::map< unsigned, RegisterCell > CellMapType
Definition: BitTracker.h:44
llvm::BitTracker::BitValue::Top
@ Top
Definition: BitTracker.h:157
llvm::BitTracker::MachineEvaluator::eASL
RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:518
llvm::BitTracker::MachineEvaluator::eXOR
RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:592
llvm::BitTracker::RegisterCell::self
static RegisterCell self(unsigned Reg, uint16_t Width)
Definition: BitTracker.h:364
llvm::BitTracker::RegisterCell::fill
RegisterCell & fill(uint16_t B, uint16_t E, const BitValue &V)
Definition: BitTracker.cpp:274
llvm::BitTracker::MachineEvaluator::eCLB
RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const
Definition: BitTracker.cpp:643
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::BitTracker::MachineEvaluator::composeWithSubRegIndex
virtual const TargetRegisterClass & composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const
Definition: BitTracker.h:482
llvm::detail::DenseSetImpl::count
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
llvm::BitTracker::RegisterCell::extract
RegisterCell extract(const BitMask &M) const
Definition: BitTracker.cpp:235
llvm::BitTracker::visit
void visit(const MachineInstr &MI)
Definition: BitTracker.cpp:1034
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
llvm::GraphTraits< const MachineFunction * >
Definition: MachineFunction.h:1164
F
#define F(x, y, z)
Definition: MD5.cpp:56
MachineRegisterInfo.h
llvm::BitTracker::RegisterRef::Reg
Register Reg
Definition: BitTracker.h:146
llvm::BitTracker::MachineEvaluator::eAND
RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:548
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
BitTracker.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::BitTracker::BitValue::is
bool is(unsigned T) const
Definition: BitTracker.h:209
llvm::BitTracker::MachineEvaluator::putCell
void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const
Definition: BitTracker.cpp:375
llvm::X86AS::SS
@ SS
Definition: X86.h:184
llvm::BitTracker::MachineEvaluator::track
virtual bool track(const TargetRegisterClass *RC) const
Definition: BitTracker.h:467
llvm::BitTracker::RegisterCell::rol
RegisterCell & rol(uint16_t Sh)
Definition: BitTracker.cpp:253
llvm::AArch64CC::VC
@ VC
Definition: AArch64BaseInfo.h:243
Constants.h
llvm::BitTracker::RegisterCell::width
uint16_t width() const
Definition: BitTracker.h:303
llvm::BitTracker::BitMask::first
uint16_t first() const
Definition: BitTracker.h:291
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::BitTracker::RegisterCell::operator==
bool operator==(const RegisterCell &RC) const
Definition: BitTracker.cpp:310
llvm::BitTracker::BitMask::last
uint16_t last() const
Definition: BitTracker.h:292
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:370
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:488
llvm::BitTracker::MachineEvaluator::eMLU
RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:508
llvm::BitTracker::MachineEvaluator::eMLS
RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:498
llvm::BitTracker::MachineEvaluator::isInt
bool isInt(const RegisterCell &A) const
Definition: BitTracker.cpp:388
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
llvm::BitTracker
Definition: BitTracker.h:35
false
Definition: StackSlotColoring.cpp:142
llvm::MachineFunction::size
unsigned size() const
Definition: MachineFunction.h:750
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::BitTracker::MachineEvaluator::toInt
uint64_t toInt(const RegisterCell &A) const
Definition: BitTracker.cpp:397
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:606
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
BitVector.h
llvm::BitTracker::BitValue::self
static BitValue self(const BitRef &Self=BitRef())
Definition: BitTracker.h:280
llvm::BitVector
Definition: BitVector.h:74
llvm::BitTracker::MachineEvaluator::eCTB
RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const
Definition: BitTracker.cpp:653
llvm::BitTracker::print_cells
void print_cells(raw_ostream &OS) const
Definition: BitTracker.cpp:182
llvm::BitTracker::run
void run()
Definition: BitTracker.cpp:1120
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::BitTracker::BranchTargetList
SetVector< const MachineBasicBlock * > BranchTargetList
Definition: BitTracker.h:43
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::BitTracker::MachineEvaluator::eIMM
RegisterCell eIMM(int64_t V, uint16_t W) const
Definition: BitTracker.cpp:412
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
llvm::BitTracker::RegisterCell::cl
uint16_t cl(bool B) const
Definition: BitTracker.cpp:301
llvm::BitTracker::BitValue::num
bool num() const
Definition: BitTracker.h:257
llvm::BitTracker::MachineEvaluator::eNOT
RegisterCell eNOT(const RegisterCell &A1) const
Definition: BitTracker.cpp:612
llvm::BitTracker::BitRef::Reg
Register Reg
Definition: BitTracker.h:134
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:321
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::BitTracker::put
void put(RegisterRef RR, const RegisterCell &RC)
Definition: BitTracker.cpp:995
llvm::BitTracker::MachineEvaluator::eCLR
RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const
Definition: BitTracker.cpp:635
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::BitTracker::MachineEvaluator::MRI
MachineRegisterInfo & MRI
Definition: BitTracker.h:491
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::BitTracker::RegisterCell::ct
uint16_t ct(bool B) const
Definition: BitTracker.cpp:292
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::BitTracker::MachineEvaluator::mask
virtual BitMask mask(Register Reg, unsigned Sub) const
Definition: BitTracker.cpp:707
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::BitTracker::reached
bool reached(const MachineBasicBlock *B) const
Definition: BitTracker.cpp:1026
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1243
llvm::BitTracker::MachineEvaluator::eSUB
RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:465
llvm::Register::asMCReg
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
llvm::BitTracker::RegisterCell::cat
RegisterCell & cat(const RegisterCell &RC)
Definition: BitTracker.cpp:282
llvm::BitTracker::MachineEvaluator::eADD
RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const
Definition: BitTracker.cpp:432
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::detail::DenseSetImpl::clear
void clear()
Definition: DenseSet.h:92
llvm::X86II::TB
@ TB
Definition: X86BaseInfo.h:800
llvm::BitTracker::get
RegisterCell get(RegisterRef RR) const
Definition: BitTracker.cpp:991
llvm::BitTracker::BitRef
Definition: BitTracker.h:126
llvm::MachineOperand::getMBB
MachineBasicBlock * getMBB() const
Definition: MachineOperand.h:552
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:969
llvm::BitTracker::MachineEvaluator::eSET
RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const
Definition: BitTracker.cpp:627
llvm::BitTracker::BitValue::Zero
@ Zero
Definition: BitTracker.h:158
llvm::BitTracker::RegisterRef
Definition: BitTracker.h:141
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:375
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:286
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::Trace
Definition: Trace.h:30
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineOperand::getSubReg
unsigned getSubReg() const
Definition: MachineOperand.h:365
llvm::BitTracker::RegisterCell
Definition: BitTracker.h:300
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:675
llvm::BitTracker::MachineEvaluator::getCell
RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const
Definition: BitTracker.cpp:348
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::TargetRegisterInfo::getRegSizeInBits
unsigned getRegSizeInBits(const TargetRegisterClass &RC) const
Return the size in bits of a register from class RC.
Definition: TargetRegisterInfo.h:274
uint16_t
llvm::BitTracker::MachineEvaluator::eINS
RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2, uint16_t AtN) const
Definition: BitTracker.cpp:695
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::BitTracker::MachineEvaluator::getRegBitWidth
uint16_t getRegBitWidth(const RegisterRef &RR) const
Definition: BitTracker.cpp:329
llvm::BitTracker::MachineEvaluator::TRI
const TargetRegisterInfo & TRI
Definition: BitTracker.h:490
llvm::BitTracker::RegisterCell::insert
RegisterCell & insert(const RegisterCell &RC, const BitMask &M)
Definition: BitTracker.cpp:214
llvm::BitTracker::BitRef::Pos
uint16_t Pos
Definition: BitTracker.h:135
llvm::BitTracker::BitValue::ref
static BitValue ref(const BitValue &V)
Definition: BitTracker.h:271
llvm::BitTracker::MachineEvaluator
Definition: BitTracker.h:392
llvm::BitTracker::BitValue::One
@ One
Definition: BitTracker.h:159
llvm::BitTracker::MachineEvaluator::eLSR
RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const
Definition: BitTracker.cpp:527
llvm::MachineInstr::getNumOperands
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:481
llvm::BitTracker::MachineEvaluator::eXTR
RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const
Definition: BitTracker.cpp:683
llvm::BitTracker::BitValue::Type
ValueType Type
Definition: BitTracker.h:191
MachineOperand.h
llvm::TargetRegisterInfo::getSubReg
MCRegister getSubReg(MCRegister Reg, unsigned Idx) const
Returns the physical register number of sub-register "Index" for physical register RegNo.
Definition: TargetRegisterInfo.h:1092
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::Register::virtReg2Index
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
llvm::TargetRegisterInfo::getMinimalPhysRegClass
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
Definition: TargetRegisterInfo.cpp:211
raw_ostream.h
llvm::BitTracker::BitValue
Definition: BitTracker.h:155
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:110
llvm::MachineInstrBundleIterator< const MachineInstr >
TargetRegisterInfo.h
Debug.h
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:22