xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/BitTracker.cpp (revision e17f5b1d307b7b8910d67883e57a9604305906d5)
1 //===- BitTracker.cpp -----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // SSA-based bit propagation.
10 //
11 // The purpose of this code is, for a given virtual register, to provide
12 // information about the value of each bit in the register. The values
13 // of bits are represented by the class BitValue, and take one of four
14 // cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
15 // "ref" value means that the bit is a copy of another bit (which itself
16 // cannot be a copy of yet another bit---such chains are not allowed).
17 // A "ref" value is associated with a BitRef structure, which indicates
18 // which virtual register, and which bit in that register is the origin
19 // of the value. For example, given an instruction
20 //   %2 = ASL %1, 1
21 // assuming that nothing is known about bits of %1, bit 1 of %2
22 // will be a "ref" to (%1, 0). If there is a subsequent instruction
23 //   %3 = ASL %2, 2
24 // then bit 3 of %3 will be a "ref" to (%1, 0) as well.
25 // The "bottom" case means that the bit's value cannot be determined,
26 // and that this virtual register actually defines it. The "bottom" case
27 // is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
28 // to self", so for the %1 above, the bit 0 of it will be a "ref" to
29 // (%1, 0), bit 1 will be a "ref" to (%1, 1), etc.
30 //
31 // The tracker implements the Wegman-Zadeck algorithm, originally developed
32 // for SSA-based constant propagation. Each register is represented as
33 // a sequence of bits, with the convention that bit 0 is the least signi-
34 // ficant bit. Each bit is propagated individually. The class RegisterCell
35 // implements the register's representation, and is also the subject of
36 // the lattice operations in the tracker.
37 //
38 // The intended usage of the bit tracker is to create a target-specific
39 // machine instruction evaluator, pass the evaluator to the BitTracker
40 // object, and run the tracker. The tracker will then collect the bit
41 // value information for a given machine function. After that, it can be
42 // queried for the cells for each virtual register.
43 // Sample code:
44 //   const TargetSpecificEvaluator TSE(TRI, MRI);
45 //   BitTracker BT(TSE, MF);
46 //   BT.run();
47 //   ...
48 //   unsigned Reg = interestingRegister();
49 //   RegisterCell RC = BT.get(Reg);
50 //   if (RC[3].is(1))
51 //      Reg0bit3 = 1;
52 //
53 // The code below is intended to be fully target-independent.
54 
55 #include "BitTracker.h"
56 #include "llvm/ADT/APInt.h"
57 #include "llvm/ADT/BitVector.h"
58 #include "llvm/CodeGen/MachineBasicBlock.h"
59 #include "llvm/CodeGen/MachineFunction.h"
60 #include "llvm/CodeGen/MachineInstr.h"
61 #include "llvm/CodeGen/MachineOperand.h"
62 #include "llvm/CodeGen/MachineRegisterInfo.h"
63 #include "llvm/CodeGen/TargetRegisterInfo.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/Support/Debug.h"
66 #include "llvm/Support/raw_ostream.h"
67 #include <cassert>
68 #include <cstdint>
69 #include <iterator>
70 
71 using namespace llvm;
72 
73 using BT = BitTracker;
74 
75 namespace {
76 
77   // Local trickery to pretty print a register (without the whole "%number"
78   // business).
79   struct printv {
80     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 
97   raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) {
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 
115   raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
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 
182 void BitTracker::print_cells(raw_ostream &OS) const {
183   for (const std::pair<unsigned, RegisterCell> P : Map)
184     dbgs() << printReg(P.first, &ME.TRI) << " -> " << P.second << "\n";
185 }
186 
187 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
188     : ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType), Trace(false) {
189 }
190 
191 BitTracker::~BitTracker() {
192   delete &Map;
193 }
194 
195 // If we were allowed to update a cell for a part of a register, the meet
196 // operation would need to be parametrized by the register number and the
197 // exact part of the register, so that the computer BitRefs correspond to
198 // the actual bits of the "self" register.
199 // While this cannot happen in the current implementation, I'm not sure
200 // if this should be ruled out in the future.
201 bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
202   // An example when "meet" can be invoked with SelfR == 0 is a phi node
203   // with a physical register as an operand.
204   assert(SelfR == 0 || Register::isVirtualRegister(SelfR));
205   bool Changed = false;
206   for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
207     const BitValue &RCV = RC[i];
208     Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
209   }
210   return Changed;
211 }
212 
213 // Insert the entire cell RC into the current cell at position given by M.
214 BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
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 
235 BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
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 
253 BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
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 
274 BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
275       const BitValue &V) {
276   assert(B <= E);
277   while (B < E)
278     Bits[B++] = V;
279   return *this;
280 }
281 
282 BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
283   // Append the cell given as the argument to the "this" cell.
284   // Bit 0 of RC becomes bit W of the result, where W is this->width().
285   uint16_t W = width(), WRC = RC.width();
286   Bits.resize(W+WRC);
287   for (uint16_t i = 0; i < WRC; ++i)
288     Bits[i+W] = RC.Bits[i];
289   return *this;
290 }
291 
292 uint16_t BT::RegisterCell::ct(bool B) const {
293   uint16_t W = width();
294   uint16_t C = 0;
295   BitValue V = B;
296   while (C < W && Bits[C] == V)
297     C++;
298   return C;
299 }
300 
301 uint16_t BT::RegisterCell::cl(bool B) const {
302   uint16_t W = width();
303   uint16_t C = 0;
304   BitValue V = B;
305   while (C < W && Bits[W-(C+1)] == V)
306     C++;
307   return C;
308 }
309 
310 bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
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 
320 BT::RegisterCell &BT::RegisterCell::regify(unsigned R) {
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 
329 uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
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 (Register::isVirtualRegister(RR.Reg)) {
339     const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub);
340     return TRI.getRegSizeInBits(VC);
341   }
342   assert(Register::isPhysicalRegister(RR.Reg));
343   Register PhysR =
344       (RR.Sub == 0) ? Register(RR.Reg) : TRI.getSubReg(RR.Reg, RR.Sub);
345   return getPhysRegBitWidth(PhysR);
346 }
347 
348 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
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 (Register::isPhysicalRegister(RR.Reg))
355     return RegisterCell::self(0, BW);
356 
357   assert(Register::isVirtualRegister(RR.Reg));
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 
375 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
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 (!Register::isVirtualRegister(RR.Reg))
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.
388 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
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 
422 BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
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 
432 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
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 
465 BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
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 
498 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
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 
508 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
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 
518 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
519       uint16_t Sh) const {
520   assert(Sh <= A1.width());
521   RegisterCell Res = RegisterCell::ref(A1);
522   Res.rol(Sh);
523   Res.fill(0, Sh, BitValue::Zero);
524   return Res;
525 }
526 
527 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
528       uint16_t Sh) const {
529   uint16_t W = A1.width();
530   assert(Sh <= W);
531   RegisterCell Res = RegisterCell::ref(A1);
532   Res.rol(W-Sh);
533   Res.fill(W-Sh, W, BitValue::Zero);
534   return Res;
535 }
536 
537 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
538       uint16_t Sh) const {
539   uint16_t W = A1.width();
540   assert(Sh <= W);
541   RegisterCell Res = RegisterCell::ref(A1);
542   BitValue Sign = Res[W-1];
543   Res.rol(W-Sh);
544   Res.fill(W-Sh, W, Sign);
545   return Res;
546 }
547 
548 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
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 
570 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
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 
592 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
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 
612 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
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 
627 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
628       uint16_t BitN) const {
629   assert(BitN < A1.width());
630   RegisterCell Res = RegisterCell::ref(A1);
631   Res[BitN] = BitValue::One;
632   return Res;
633 }
634 
635 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
636       uint16_t BitN) const {
637   assert(BitN < A1.width());
638   RegisterCell Res = RegisterCell::ref(A1);
639   Res[BitN] = BitValue::Zero;
640   return Res;
641 }
642 
643 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
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 
653 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
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 
663 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
664       uint16_t FromN) const {
665   uint16_t W = A1.width();
666   assert(FromN <= W);
667   RegisterCell Res = RegisterCell::ref(A1);
668   BitValue Sign = Res[FromN-1];
669   // Sign-extend "inreg".
670   Res.fill(FromN, W, Sign);
671   return Res;
672 }
673 
674 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
675       uint16_t FromN) const {
676   uint16_t W = A1.width();
677   assert(FromN <= W);
678   RegisterCell Res = RegisterCell::ref(A1);
679   Res.fill(FromN, W, BitValue::Zero);
680   return Res;
681 }
682 
683 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
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;
690   RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
691   // Return shorter cell.
692   return Res;
693 }
694 
695 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
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.
701   RegisterCell Res = RegisterCell::ref(A1);
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 
714 uint16_t BT::MachineEvaluator::getPhysRegBitWidth(unsigned Reg) const {
715   assert(Register::isPhysicalRegister(Reg));
716   const TargetRegisterClass &PC = *TRI.getMinimalPhysRegClass(Reg);
717   return TRI.getRegSizeInBits(PC);
718 }
719 
720 bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
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<const 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");
878     if (!Register::isVirtualRegister(RD.Reg))
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) {
966       MachineFunction::const_iterator BIt = B.getIterator();
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 
989 BT::RegisterCell BT::get(RegisterRef RR) const {
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) {
1087       MachineFunction::const_iterator BIt = B.getIterator();
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 }
1149