lib/Target/Hexagon/BitTracker.cpp

   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 {
  75     printv(unsigned r) : R(r) {}
  76     unsigned R;
  77   };
  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 raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::BitValue &BV) {
  88   switch (BV.Type) {
  89     case BT::BitValue::Top:
  90       OS << 'T';
  91       break;
  92     case BT::BitValue::Zero:
  93       OS << '0';
  94       break;
  95     case BT::BitValue::One:
  96       OS << '1';
  97       break;
  98     case BT::BitValue::Ref:
  99       OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
 100       break;
 101   }
 102   return OS;
 103 }
 104
 105 raw_ostream &llvm::operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
 106   unsigned n = RC.Bits.size();
 107   OS << "{ w:" << n;
 108   // Instead of printing each bit value individually, try to group them
 109   // into logical segments, such as sequences of 0 or 1 bits or references
 110   // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
 111   // "Start" will be the index of the beginning of the most recent segment.
 112   unsigned Start = 0;
 113   bool SeqRef = false;    // A sequence of refs to consecutive bits.
 114   bool ConstRef = false;  // A sequence of refs to the same bit.
 115
 116   for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
 117     const BT::BitValue &V = RC[i];
 118     const BT::BitValue &SV = RC[Start];
 119     bool IsRef = (V.Type == BT::BitValue::Ref);
 120     // If the current value is the same as Start, skip to the next one.
 121     if (!IsRef && V == SV)
 122       continue;
 123     if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
 124       if (Start+1 == i) {
 125         SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
 126         ConstRef = (V.RefI.Pos == SV.RefI.Pos);
 127       }
 128       if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
 129         continue;
 130       if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
 131         continue;
 132     }
 133
 134     // The current value is different. Print the previous one and reset
 135     // the Start.
 136     OS << " [" << Start;
 137     unsigned Count = i - Start;
 138     if (Count == 1) {
 139       OS << "]:" << SV;
 140     } else {
 141       OS << '-' << i-1 << "]:";
 142       if (SV.Type == BT::BitValue::Ref && SeqRef)
 143         OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
 144            << SV.RefI.Pos+(Count-1) << ']';
 145       else
 146         OS << SV;
 147     }
 148     Start = i;
 149     SeqRef = ConstRef = false;
 150   }
 151
 152   OS << " [" << Start;
 153   unsigned Count = n - Start;
 154   if (n-Start == 1) {
 155     OS << "]:" << RC[Start];
 156   } else {
 157     OS << '-' << n-1 << "]:";
 158     const BT::BitValue &SV = RC[Start];
 159     if (SV.Type == BT::BitValue::Ref && SeqRef)
 160       OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
 161          << SV.RefI.Pos+(Count-1) << ']';
 162     else
 163       OS << SV;
 164   }
 165   OS << " }";
 166
 167   return OS;
 168 }
 169
 170 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
 171     : Trace(false), ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType) {}
 172
 173 BitTracker::~BitTracker() {
 174   delete &Map;
 175 }
 176
 177
 178 // If we were allowed to update a cell for a part of a register, the meet
 179 // operation would need to be parametrized by the register number and the
 180 // exact part of the register, so that the computer BitRefs correspond to
 181 // the actual bits of the "self" register.
 182 // While this cannot happen in the current implementation, I'm not sure
 183 // if this should be ruled out in the future.
 184 bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned SelfR) {
 185   // An example when "meet" can be invoked with SelfR == 0 is a phi node
 186   // with a physical register as an operand.
 187   assert(SelfR == 0 || TargetRegisterInfo::isVirtualRegister(SelfR));
 188   bool Changed = false;
 189   for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
 190     const BitValue &RCV = RC[i];
 191     Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
 192   }
 193   return Changed;
 194 }
 195
 196
 197 // Insert the entire cell RC into the current cell at position given by M.
 198 BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
 199       const BitMask &M) {
 200   uint16_t B = M.first(), E = M.last(), W = width();
 201   // Sanity: M must be a valid mask for *this.
 202   assert(B < W && E < W);
 203   // Sanity: the masked part of *this must have the same number of bits
 204   // as the source.
 205   assert(B > E || E-B+1 == RC.width());      // B <= E  =>  E-B+1 = |RC|.
 206   assert(B <= E || E+(W-B)+1 == RC.width()); // E < B   =>  E+(W-B)+1 = |RC|.
 207   if (B <= E) {
 208     for (uint16_t i = 0; i <= E-B; ++i)
 209       Bits[i+B] = RC[i];
 210   } else {
 211     for (uint16_t i = 0; i < W-B; ++i)
 212       Bits[i+B] = RC[i];
 213     for (uint16_t i = 0; i <= E; ++i)
 214       Bits[i] = RC[i+(W-B)];
 215   }
 216   return *this;
 217 }
 218
 219
 220 BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
 221   uint16_t B = M.first(), E = M.last(), W = width();
 222   assert(B < W && E < W);
 223   if (B <= E) {
 224     RegisterCell RC(E-B+1);
 225     for (uint16_t i = B; i <= E; ++i)
 226       RC.Bits[i-B] = Bits[i];
 227     return RC;
 228   }
 229
 230   RegisterCell RC(E+(W-B)+1);
 231   for (uint16_t i = 0; i < W-B; ++i)
 232     RC.Bits[i] = Bits[i+B];
 233   for (uint16_t i = 0; i <= E; ++i)
 234     RC.Bits[i+(W-B)] = Bits[i];
 235   return RC;
 236 }
 237
 238
 239 BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
 240   // Rotate left (i.e. towards increasing bit indices).
 241   // Swap the two parts:  [0..W-Sh-1] [W-Sh..W-1]
 242   uint16_t W = width();
 243   Sh = Sh % W;
 244   if (Sh == 0)
 245     return *this;
 246
 247   RegisterCell Tmp(W-Sh);
 248   // Tmp = [0..W-Sh-1].
 249   for (uint16_t i = 0; i < W-Sh; ++i)
 250     Tmp[i] = Bits[i];
 251   // Shift [W-Sh..W-1] to [0..Sh-1].
 252   for (uint16_t i = 0; i < Sh; ++i)
 253     Bits[i] = Bits[W-Sh+i];
 254   // Copy Tmp to [Sh..W-1].
 255   for (uint16_t i = 0; i < W-Sh; ++i)
 256     Bits[i+Sh] = Tmp.Bits[i];
 257   return *this;
 258 }
 259
 260
 261 BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
 262       const BitValue &V) {
 263   assert(B <= E);
 264   while (B < E)
 265     Bits[B++] = V;
 266   return *this;
 267 }
 268
 269
 270 BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
 271   // Append the cell given as the argument to the "this" cell.
 272   // Bit 0 of RC becomes bit W of the result, where W is this->width().
 273   uint16_t W = width(), WRC = RC.width();
 274   Bits.resize(W+WRC);
 275   for (uint16_t i = 0; i < WRC; ++i)
 276     Bits[i+W] = RC.Bits[i];
 277   return *this;
 278 }
 279
 280
 281 uint16_t BT::RegisterCell::ct(bool B) const {
 282   uint16_t W = width();
 283   uint16_t C = 0;
 284   BitValue V = B;
 285   while (C < W && Bits[C] == V)
 286     C++;
 287   return C;
 288 }
 289
 290
 291 uint16_t BT::RegisterCell::cl(bool B) const {
 292   uint16_t W = width();
 293   uint16_t C = 0;
 294   BitValue V = B;
 295   while (C < W && Bits[W-(C+1)] == V)
 296     C++;
 297   return C;
 298 }
 299
 300
 301 bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
 302   uint16_t W = Bits.size();
 303   if (RC.Bits.size() != W)
 304     return false;
 305   for (uint16_t i = 0; i < W; ++i)
 306     if (Bits[i] != RC[i])
 307       return false;
 308   return true;
 309 }
 310
 311
 312 uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
 313   // The general problem is with finding a register class that corresponds
 314   // to a given reference reg:sub. There can be several such classes, and
 315   // since we only care about the register size, it does not matter which
 316   // such class we would find.
 317   // The easiest way to accomplish what we want is to
 318   // 1. find a physical register PhysR from the same class as RR.Reg,
 319   // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
 320   // 3. find a register class that contains PhysS.
 321   unsigned PhysR;
 322   if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) {
 323     const TargetRegisterClass *VC = MRI.getRegClass(RR.Reg);
 324     assert(VC->begin() != VC->end() && "Empty register class");
 325     PhysR = *VC->begin();
 326   } else {
 327     assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg));
 328     PhysR = RR.Reg;
 329   }
 330
 331   unsigned PhysS = (RR.Sub == 0) ? PhysR : TRI.getSubReg(PhysR, RR.Sub);
 332   const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(PhysS);
 333   uint16_t BW = RC->getSize()*8;
 334   return BW;
 335 }
 336
 337
 338 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
 339       const CellMapType &M) const {
 340   uint16_t BW = getRegBitWidth(RR);
 341
 342   // Physical registers are assumed to be present in the map with an unknown
 343   // value. Don't actually insert anything in the map, just return the cell.
 344   if (TargetRegisterInfo::isPhysicalRegister(RR.Reg))
 345     return RegisterCell::self(0, BW);
 346
 347   assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
 348   // For virtual registers that belong to a class that is not tracked,
 349   // generate an "unknown" value as well.
 350   const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
 351   if (!track(C))
 352     return RegisterCell::self(0, BW);
 353
 354   CellMapType::const_iterator F = M.find(RR.Reg);
 355   if (F != M.end()) {
 356     if (!RR.Sub)
 357       return F->second;
 358     BitMask M = mask(RR.Reg, RR.Sub);
 359     return F->second.extract(M);
 360   }
 361   // If not found, create a "top" entry, but do not insert it in the map.
 362   return RegisterCell::top(BW);
 363 }
 364
 365
 366 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
 367       CellMapType &M) const {
 368   // While updating the cell map can be done in a meaningful way for
 369   // a part of a register, it makes little sense to implement it as the
 370   // SSA representation would never contain such "partial definitions".
 371   if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
 372     return;
 373   assert(RR.Sub == 0 && "Unexpected sub-register in definition");
 374   // Eliminate all ref-to-reg-0 bit values: replace them with "self".
 375   for (unsigned i = 0, n = RC.width(); i < n; ++i) {
 376     const BitValue &V = RC[i];
 377     if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
 378       RC[i].RefI = BitRef(RR.Reg, i);
 379   }
 380   M[RR.Reg] = RC;
 381 }
 382
 383
 384 // Check if the cell represents a compile-time integer value.
 385 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
 386   uint16_t W = A.width();
 387   for (uint16_t i = 0; i < W; ++i)
 388     if (!A[i].is(0) && !A[i].is(1))
 389       return false;
 390   return true;
 391 }
 392
 393
 394 // Convert a cell to the integer value. The result must fit in uint64_t.
 395 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
 396   assert(isInt(A));
 397   uint64_t Val = 0;
 398   uint16_t W = A.width();
 399   for (uint16_t i = 0; i < W; ++i) {
 400     Val <<= 1;
 401     Val |= A[i].is(1);
 402   }
 403   return Val;
 404 }
 405
 406
 407 // Evaluator helper functions. These implement some common operation on
 408 // register cells that can be used to implement target-specific instructions
 409 // in a target-specific evaluator.
 410
 411 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
 412   RegisterCell Res(W);
 413   // For bits beyond the 63rd, this will generate the sign bit of V.
 414   for (uint16_t i = 0; i < W; ++i) {
 415     Res[i] = BitValue(V & 1);
 416     V >>= 1;
 417   }
 418   return Res;
 419 }
 420
 421
 422 BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
 423   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
 433 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
 434       const RegisterCell &A2) const {
 435   uint16_t W = A1.width();
 436   assert(W == A2.width());
 437   RegisterCell Res(W);
 438   bool Carry = false;
 439   uint16_t I;
 440   for (I = 0; I < W; ++I) {
 441     const BitValue &V1 = A1[I];
 442     const BitValue &V2 = A2[I];
 443     if (!V1.num() || !V2.num())
 444       break;
 445     unsigned S = bool(V1) + bool(V2) + Carry;
 446     Res[I] = BitValue(S & 1);
 447     Carry = (S > 1);
 448   }
 449   for (; I < W; ++I) {
 450     const BitValue &V1 = A1[I];
 451     const BitValue &V2 = A2[I];
 452     // If the next bit is same as Carry, the result will be 0 plus the
 453     // other bit. The Carry bit will remain unchanged.
 454     if (V1.is(Carry))
 455       Res[I] = BitValue::ref(V2);
 456     else if (V2.is(Carry))
 457       Res[I] = BitValue::ref(V1);
 458     else
 459       break;
 460   }
 461   for (; I < W; ++I)
 462     Res[I] = BitValue::self();
 463   return Res;
 464 }
 465
 466
 467 BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
 468       const RegisterCell &A2) const {
 469   uint16_t W = A1.width();
 470   assert(W == A2.width());
 471   RegisterCell Res(W);
 472   bool Borrow = false;
 473   uint16_t I;
 474   for (I = 0; I < W; ++I) {
 475     const BitValue &V1 = A1[I];
 476     const BitValue &V2 = A2[I];
 477     if (!V1.num() || !V2.num())
 478       break;
 479     unsigned S = bool(V1) - bool(V2) - Borrow;
 480     Res[I] = BitValue(S & 1);
 481     Borrow = (S > 1);
 482   }
 483   for (; I < W; ++I) {
 484     const BitValue &V1 = A1[I];
 485     const BitValue &V2 = A2[I];
 486     if (V1.is(Borrow)) {
 487       Res[I] = BitValue::ref(V2);
 488       break;
 489     }
 490     if (V2.is(Borrow))
 491       Res[I] = BitValue::ref(V1);
 492     else
 493       break;
 494   }
 495   for (; I < W; ++I)
 496     Res[I] = BitValue::self();
 497   return Res;
 498 }
 499
 500
 501 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
 502       const RegisterCell &A2) const {
 503   uint16_t W = A1.width() + A2.width();
 504   uint16_t Z = A1.ct(0) + A2.ct(0);
 505   RegisterCell Res(W);
 506   Res.fill(0, Z, BitValue::Zero);
 507   Res.fill(Z, W, BitValue::self());
 508   return Res;
 509 }
 510
 511
 512 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
 513       const RegisterCell &A2) const {
 514   uint16_t W = A1.width() + A2.width();
 515   uint16_t Z = A1.ct(0) + A2.ct(0);
 516   RegisterCell Res(W);
 517   Res.fill(0, Z, BitValue::Zero);
 518   Res.fill(Z, W, BitValue::self());
 519   return Res;
 520 }
 521
 522
 523 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
 524       uint16_t Sh) const {
 525   assert(Sh <= A1.width());
 526   RegisterCell Res = RegisterCell::ref(A1);
 527   Res.rol(Sh);
 528   Res.fill(0, Sh, BitValue::Zero);
 529   return Res;
 530 }
 531
 532
 533 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
 534       uint16_t Sh) const {
 535   uint16_t W = A1.width();
 536   assert(Sh <= W);
 537   RegisterCell Res = RegisterCell::ref(A1);
 538   Res.rol(W-Sh);
 539   Res.fill(W-Sh, W, BitValue::Zero);
 540   return Res;
 541 }
 542
 543
 544 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
 545       uint16_t Sh) const {
 546   uint16_t W = A1.width();
 547   assert(Sh <= W);
 548   RegisterCell Res = RegisterCell::ref(A1);
 549   BitValue Sign = Res[W-1];
 550   Res.rol(W-Sh);
 551   Res.fill(W-Sh, W, Sign);
 552   return Res;
 553 }
 554
 555
 556 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
 557       const RegisterCell &A2) const {
 558   uint16_t W = A1.width();
 559   assert(W == A2.width());
 560   RegisterCell Res(W);
 561   for (uint16_t i = 0; i < W; ++i) {
 562     const BitValue &V1 = A1[i];
 563     const BitValue &V2 = A2[i];
 564     if (V1.is(1))
 565       Res[i] = BitValue::ref(V2);
 566     else if (V2.is(1))
 567       Res[i] = BitValue::ref(V1);
 568     else if (V1.is(0) || V2.is(0))
 569       Res[i] = BitValue::Zero;
 570     else if (V1 == V2)
 571       Res[i] = V1;
 572     else
 573       Res[i] = BitValue::self();
 574   }
 575   return Res;
 576 }
 577
 578
 579 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
 580       const RegisterCell &A2) const {
 581   uint16_t W = A1.width();
 582   assert(W == A2.width());
 583   RegisterCell Res(W);
 584   for (uint16_t i = 0; i < W; ++i) {
 585     const BitValue &V1 = A1[i];
 586     const BitValue &V2 = A2[i];
 587     if (V1.is(1) || V2.is(1))
 588       Res[i] = BitValue::One;
 589     else if (V1.is(0))
 590       Res[i] = BitValue::ref(V2);
 591     else if (V2.is(0))
 592       Res[i] = BitValue::ref(V1);
 593     else if (V1 == V2)
 594       Res[i] = V1;
 595     else
 596       Res[i] = BitValue::self();
 597   }
 598   return Res;
 599 }
 600
 601
 602 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
 603       const RegisterCell &A2) const {
 604   uint16_t W = A1.width();
 605   assert(W == A2.width());
 606   RegisterCell Res(W);
 607   for (uint16_t i = 0; i < W; ++i) {
 608     const BitValue &V1 = A1[i];
 609     const BitValue &V2 = A2[i];
 610     if (V1.is(0))
 611       Res[i] = BitValue::ref(V2);
 612     else if (V2.is(0))
 613       Res[i] = BitValue::ref(V1);
 614     else if (V1 == V2)
 615       Res[i] = BitValue::Zero;
 616     else
 617       Res[i] = BitValue::self();
 618   }
 619   return Res;
 620 }
 621
 622
 623 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
 624   uint16_t W = A1.width();
 625   RegisterCell Res(W);
 626   for (uint16_t i = 0; i < W; ++i) {
 627     const BitValue &V = A1[i];
 628     if (V.is(0))
 629       Res[i] = BitValue::One;
 630     else if (V.is(1))
 631       Res[i] = BitValue::Zero;
 632     else
 633       Res[i] = BitValue::self();
 634   }
 635   return Res;
 636 }
 637
 638
 639 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
 640       uint16_t BitN) const {
 641   assert(BitN < A1.width());
 642   RegisterCell Res = RegisterCell::ref(A1);
 643   Res[BitN] = BitValue::One;
 644   return Res;
 645 }
 646
 647
 648 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
 649       uint16_t BitN) const {
 650   assert(BitN < A1.width());
 651   RegisterCell Res = RegisterCell::ref(A1);
 652   Res[BitN] = BitValue::Zero;
 653   return Res;
 654 }
 655
 656
 657 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
 658       uint16_t W) const {
 659   uint16_t C = A1.cl(B), AW = A1.width();
 660   // If the last leading non-B bit is not a constant, then we don't know
 661   // the real count.
 662   if ((C < AW && A1[AW-1-C].num()) || C == AW)
 663     return eIMM(C, W);
 664   return RegisterCell::self(0, W);
 665 }
 666
 667
 668 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
 669       uint16_t W) const {
 670   uint16_t C = A1.ct(B), AW = A1.width();
 671   // If the last trailing non-B bit is not a constant, then we don't know
 672   // the real count.
 673   if ((C < AW && A1[C].num()) || C == AW)
 674     return eIMM(C, W);
 675   return RegisterCell::self(0, W);
 676 }
 677
 678
 679 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
 680       uint16_t FromN) const {
 681   uint16_t W = A1.width();
 682   assert(FromN <= W);
 683   RegisterCell Res = RegisterCell::ref(A1);
 684   BitValue Sign = Res[FromN-1];
 685   // Sign-extend "inreg".
 686   Res.fill(FromN, W, Sign);
 687   return Res;
 688 }
 689
 690
 691 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
 692       uint16_t FromN) const {
 693   uint16_t W = A1.width();
 694   assert(FromN <= W);
 695   RegisterCell Res = RegisterCell::ref(A1);
 696   Res.fill(FromN, W, BitValue::Zero);
 697   return Res;
 698 }
 699
 700
 701 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
 702       uint16_t B, uint16_t E) const {
 703   uint16_t W = A1.width();
 704   assert(B < W && E <= W);
 705   if (B == E)
 706     return RegisterCell(0);
 707   uint16_t Last = (E > 0) ? E-1 : W-1;
 708   RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
 709   // Return shorter cell.
 710   return Res;
 711 }
 712
 713
 714 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
 715       const RegisterCell &A2, uint16_t AtN) const {
 716   uint16_t W1 = A1.width(), W2 = A2.width();
 717   (void)W1;
 718   assert(AtN < W1 && AtN+W2 <= W1);
 719   // Copy bits from A1, insert A2 at position AtN.
 720   RegisterCell Res = RegisterCell::ref(A1);
 721   if (W2 > 0)
 722     Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
 723   return Res;
 724 }
 725
 726
 727 BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
 728   assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
 729   uint16_t W = getRegBitWidth(Reg);
 730   assert(W > 0 && "Cannot generate mask for empty register");
 731   return BitMask(0, W-1);
 732 }
 733
 734
 735 bool BT::MachineEvaluator::evaluate(const MachineInstr *MI,
 736       const CellMapType &Inputs, CellMapType &Outputs) const {
 737   unsigned Opc = MI->getOpcode();
 738   switch (Opc) {
 739     case TargetOpcode::REG_SEQUENCE: {
 740       RegisterRef RD = MI->getOperand(0);
 741       assert(RD.Sub == 0);
 742       RegisterRef RS = MI->getOperand(1);
 743       unsigned SS = MI->getOperand(2).getImm();
 744       RegisterRef RT = MI->getOperand(3);
 745       unsigned ST = MI->getOperand(4).getImm();
 746       assert(SS != ST);
 747
 748       uint16_t W = getRegBitWidth(RD);
 749       RegisterCell Res(W);
 750       Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
 751       Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
 752       putCell(RD, Res, Outputs);
 753       break;
 754     }
 755
 756     case TargetOpcode::COPY: {
 757       // COPY can transfer a smaller register into a wider one.
 758       // If that is the case, fill the remaining high bits with 0.
 759       RegisterRef RD = MI->getOperand(0);
 760       RegisterRef RS = MI->getOperand(1);
 761       assert(RD.Sub == 0);
 762       uint16_t WD = getRegBitWidth(RD);
 763       uint16_t WS = getRegBitWidth(RS);
 764       assert(WD >= WS);
 765       RegisterCell Src = getCell(RS, Inputs);
 766       RegisterCell Res(WD);
 767       Res.insert(Src, BitMask(0, WS-1));
 768       Res.fill(WS, WD, BitValue::Zero);
 769       putCell(RD, Res, Outputs);
 770       break;
 771     }
 772
 773     default:
 774       return false;
 775   }
 776
 777   return true;
 778 }
 779
 780
 781 // Main W-Z implementation.
 782
 783 void BT::visitPHI(const MachineInstr *PI) {
 784   int ThisN = PI->getParent()->getNumber();
 785   if (Trace)
 786     dbgs() << "Visit FI(BB#" << ThisN << "): " << *PI;
 787
 788   const MachineOperand &MD = PI->getOperand(0);
 789   assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
 790   RegisterRef DefRR(MD);
 791   uint16_t DefBW = ME.getRegBitWidth(DefRR);
 792
 793   RegisterCell DefC = ME.getCell(DefRR, Map);
 794   if (DefC == RegisterCell::self(DefRR.Reg, DefBW))    // XXX slow
 795     return;
 796
 797   bool Changed = false;
 798
 799   for (unsigned i = 1, n = PI->getNumOperands(); i < n; i += 2) {
 800     const MachineBasicBlock *PB = PI->getOperand(i+1).getMBB();
 801     int PredN = PB->getNumber();
 802     if (Trace)
 803       dbgs() << "  edge BB#" << PredN << "->BB#" << ThisN;
 804     if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
 805       if (Trace)
 806         dbgs() << " not executable\n";
 807       continue;
 808     }
 809
 810     RegisterRef RU = PI->getOperand(i);
 811     RegisterCell ResC = ME.getCell(RU, Map);
 812     if (Trace)
 813       dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
 814              << " cell: " << ResC << "\n";
 815     Changed |= DefC.meet(ResC, DefRR.Reg);
 816   }
 817
 818   if (Changed) {
 819     if (Trace)
 820       dbgs() << "Output: " << PrintReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
 821              << " cell: " << DefC << "\n";
 822     ME.putCell(DefRR, DefC, Map);
 823     visitUsesOf(DefRR.Reg);
 824   }
 825 }
 826
 827
 828 void BT::visitNonBranch(const MachineInstr *MI) {
 829   if (Trace) {
 830     int ThisN = MI->getParent()->getNumber();
 831     dbgs() << "Visit MI(BB#" << ThisN << "): " << *MI;
 832   }
 833   if (MI->isDebugValue())
 834     return;
 835   assert(!MI->isBranch() && "Unexpected branch instruction");
 836
 837   CellMapType ResMap;
 838   bool Eval = ME.evaluate(MI, Map, ResMap);
 839
 840   if (Trace && Eval) {
 841     for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
 842       const MachineOperand &MO = MI->getOperand(i);
 843       if (!MO.isReg() || !MO.isUse())
 844         continue;
 845       RegisterRef RU(MO);
 846       dbgs() << "  input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
 847              << " cell: " << ME.getCell(RU, Map) << "\n";
 848     }
 849     dbgs() << "Outputs:\n";
 850     for (CellMapType::iterator I = ResMap.begin(), E = ResMap.end();
 851          I != E; ++I) {
 852       RegisterRef RD(I->first);
 853       dbgs() << "  " << PrintReg(I->first, &ME.TRI) << " cell: "
 854              << ME.getCell(RD, ResMap) << "\n";
 855     }
 856   }
 857
 858   // Iterate over all definitions of the instruction, and update the
 859   // cells accordingly.
 860   for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
 861     const MachineOperand &MO = MI->getOperand(i);
 862     // Visit register defs only.
 863     if (!MO.isReg() || !MO.isDef())
 864       continue;
 865     RegisterRef RD(MO);
 866     assert(RD.Sub == 0 && "Unexpected sub-register in definition");
 867     if (!TargetRegisterInfo::isVirtualRegister(RD.Reg))
 868       continue;
 869
 870     bool Changed = false;
 871     if (!Eval || ResMap.count(RD.Reg) == 0) {
 872       // Set to "ref" (aka "bottom").
 873       uint16_t DefBW = ME.getRegBitWidth(RD);
 874       RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
 875       if (RefC != ME.getCell(RD, Map)) {
 876         ME.putCell(RD, RefC, Map);
 877         Changed = true;
 878       }
 879     } else {
 880       RegisterCell DefC = ME.getCell(RD, Map);
 881       RegisterCell ResC = ME.getCell(RD, ResMap);
 882       // This is a non-phi instruction, so the values of the inputs come
 883       // from the same registers each time this instruction is evaluated.
 884       // During the propagation, the values of the inputs can become lowered
 885       // in the sense of the lattice operation, which may cause different
 886       // results to be calculated in subsequent evaluations. This should
 887       // not cause the bottoming of the result in the map, since the new
 888       // result is already reflecting the lowered inputs.
 889       for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
 890         BitValue &V = DefC[i];
 891         // Bits that are already "bottom" should not be updated.
 892         if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
 893           continue;
 894         // Same for those that are identical in DefC and ResC.
 895         if (V == ResC[i])
 896           continue;
 897         V = ResC[i];
 898         Changed = true;
 899       }
 900       if (Changed)
 901         ME.putCell(RD, DefC, Map);
 902     }
 903     if (Changed)
 904       visitUsesOf(RD.Reg);
 905   }
 906 }
 907
 908
 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->isLandingPad())
 955         Targets.insert(SB);
 956     }
 957     if (FallsThrough) {
 958       MachineFunction::const_iterator BIt = &B;
 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
 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
 995 BT::RegisterCell BT::get(RegisterRef RR) const {
 996   return ME.getCell(RR, Map);
 997 }
 998
 999
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.
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.)
1033 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
1045 void BT::reset() {
1046   EdgeExec.clear();
1047   InstrExec.clear();
1048   Map.clear();
1049 }
1050
1051
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;
1108       MachineFunction::const_iterator Next = std::next(BIt);
1109       if (Next != MF.end()) {
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