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