contrib/llvm/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 "BitTracker.h"
  57 #include "llvm/ADT/APInt.h"
  58 #include "llvm/ADT/BitVector.h"
  59 #include "llvm/CodeGen/MachineBasicBlock.h"
  60 #include "llvm/CodeGen/MachineFunction.h"
  61 #include "llvm/CodeGen/MachineInstr.h"
  62 #include "llvm/CodeGen/MachineOperand.h"
  63 #include "llvm/CodeGen/MachineRegisterInfo.h"
  64 #include "llvm/IR/Constants.h"
  65 #include "llvm/Support/Debug.h"
  66 #include "llvm/Support/raw_ostream.h"
  67 #include "llvm/Target/TargetRegisterInfo.h"
  68 #include <iterator>
  69 #include <cassert>
  70 #include <cstdint>
  71
  72 using namespace llvm;
  73
  74 typedef BitTracker BT;
  75
  76 namespace {
  77
  78   // Local trickery to pretty print a register (without the whole "%vreg"
  79   // business).
  80   struct printv {
  81     printv(unsigned r) : R(r) {}
  82
  83     unsigned R;
  84   };
  85
  86   raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
  87     if (PV.R)
  88       OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R);
  89     else
  90       OS << 's';
  91     return OS;
  92   }
  93
  94 } // end anonymous namespace
  95
  96 namespace llvm {
  97
  98   raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) {
  99     switch (BV.Type) {
 100       case BT::BitValue::Top:
 101         OS << 'T';
 102         break;
 103       case BT::BitValue::Zero:
 104         OS << '0';
 105         break;
 106       case BT::BitValue::One:
 107         OS << '1';
 108         break;
 109       case BT::BitValue::Ref:
 110         OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
 111         break;
 112     }
 113     return OS;
 114   }
 115
 116   raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
 117     unsigned n = RC.Bits.size();
 118     OS << "{ w:" << n;
 119     // Instead of printing each bit value individually, try to group them
 120     // into logical segments, such as sequences of 0 or 1 bits or references
 121     // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
 122     // "Start" will be the index of the beginning of the most recent segment.
 123     unsigned Start = 0;
 124     bool SeqRef = false;    // A sequence of refs to consecutive bits.
 125     bool ConstRef = false;  // A sequence of refs to the same bit.
 126
 127     for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
 128       const BT::BitValue &V = RC[i];
 129       const BT::BitValue &SV = RC[Start];
 130       bool IsRef = (V.Type == BT::BitValue::Ref);
 131       // If the current value is the same as Start, skip to the next one.
 132       if (!IsRef && V == SV)
 133         continue;
 134       if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
 135         if (Start+1 == i) {
 136           SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
 137           ConstRef = (V.RefI.Pos == SV.RefI.Pos);
 138         }
 139         if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
 140           continue;
 141         if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
 142           continue;
 143       }
 144
 145       // The current value is different. Print the previous one and reset
 146       // the Start.
 147       OS << " [" << Start;
 148       unsigned Count = i - Start;
 149       if (Count == 1) {
 150         OS << "]:" << SV;
 151       } else {
 152         OS << '-' << i-1 << "]:";
 153         if (SV.Type == BT::BitValue::Ref && SeqRef)
 154           OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
 155              << SV.RefI.Pos+(Count-1) << ']';
 156         else
 157           OS << SV;
 158       }
 159       Start = i;
 160       SeqRef = ConstRef = false;
 161     }
 162
 163     OS << " [" << Start;
 164     unsigned Count = n - Start;
 165     if (n-Start == 1) {
 166       OS << "]:" << RC[Start];
 167     } else {
 168       OS << '-' << n-1 << "]:";
 169       const BT::BitValue &SV = RC[Start];
 170       if (SV.Type == BT::BitValue::Ref && SeqRef)
 171         OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
 172            << SV.RefI.Pos+(Count-1) << ']';
 173       else
 174         OS << SV;
 175     }
 176     OS << " }";
 177
 178     return OS;
 179   }
 180
 181 } // end namespace llvm
 182
 183 void BitTracker::print_cells(raw_ostream &OS) const {
 184   for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
 185     dbgs() << PrintReg(I->first, &ME.TRI) << " -> " << I->second << "\n";
 186 }
 187
 188 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
 189     : Trace(false), ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType) {}
 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 || TargetRegisterInfo::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 uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
 321   // The general problem is with finding a register class that corresponds
 322   // to a given reference reg:sub. There can be several such classes, and
 323   // since we only care about the register size, it does not matter which
 324   // such class we would find.
 325   // The easiest way to accomplish what we want is to
 326   // 1. find a physical register PhysR from the same class as RR.Reg,
 327   // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
 328   // 3. find a register class that contains PhysS.
 329   unsigned PhysR;
 330   if (TargetRegisterInfo::isVirtualRegister(RR.Reg)) {
 331     const TargetRegisterClass *VC = MRI.getRegClass(RR.Reg);
 332     assert(VC->begin() != VC->end() && "Empty register class");
 333     PhysR = *VC->begin();
 334   } else {
 335     assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg));
 336     PhysR = RR.Reg;
 337   }
 338
 339   unsigned PhysS = (RR.Sub == 0) ? PhysR : TRI.getSubReg(PhysR, RR.Sub);
 340   const TargetRegisterClass *RC = TRI.getMinimalPhysRegClass(PhysS);
 341   uint16_t BW = RC->getSize()*8;
 342   return BW;
 343 }
 344
 345 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
 346       const CellMapType &M) const {
 347   uint16_t BW = getRegBitWidth(RR);
 348
 349   // Physical registers are assumed to be present in the map with an unknown
 350   // value. Don't actually insert anything in the map, just return the cell.
 351   if (TargetRegisterInfo::isPhysicalRegister(RR.Reg))
 352     return RegisterCell::self(0, BW);
 353
 354   assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
 355   // For virtual registers that belong to a class that is not tracked,
 356   // generate an "unknown" value as well.
 357   const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
 358   if (!track(C))
 359     return RegisterCell::self(0, BW);
 360
 361   CellMapType::const_iterator F = M.find(RR.Reg);
 362   if (F != M.end()) {
 363     if (!RR.Sub)
 364       return F->second;
 365     BitMask M = mask(RR.Reg, RR.Sub);
 366     return F->second.extract(M);
 367   }
 368   // If not found, create a "top" entry, but do not insert it in the map.
 369   return RegisterCell::top(BW);
 370 }
 371
 372 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
 373       CellMapType &M) const {
 374   // While updating the cell map can be done in a meaningful way for
 375   // a part of a register, it makes little sense to implement it as the
 376   // SSA representation would never contain such "partial definitions".
 377   if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
 378     return;
 379   assert(RR.Sub == 0 && "Unexpected sub-register in definition");
 380   // Eliminate all ref-to-reg-0 bit values: replace them with "self".
 381   for (unsigned i = 0, n = RC.width(); i < n; ++i) {
 382     const BitValue &V = RC[i];
 383     if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
 384       RC[i].RefI = BitRef(RR.Reg, i);
 385   }
 386   M[RR.Reg] = RC;
 387 }
 388
 389 // Check if the cell represents a compile-time integer value.
 390 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
 391   uint16_t W = A.width();
 392   for (uint16_t i = 0; i < W; ++i)
 393     if (!A[i].is(0) && !A[i].is(1))
 394       return false;
 395   return true;
 396 }
 397
 398 // Convert a cell to the integer value. The result must fit in uint64_t.
 399 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
 400   assert(isInt(A));
 401   uint64_t Val = 0;
 402   uint16_t W = A.width();
 403   for (uint16_t i = 0; i < W; ++i) {
 404     Val <<= 1;
 405     Val |= A[i].is(1);
 406   }
 407   return Val;
 408 }
 409
 410 // Evaluator helper functions. These implement some common operation on
 411 // register cells that can be used to implement target-specific instructions
 412 // in a target-specific evaluator.
 413
 414 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
 415   RegisterCell Res(W);
 416   // For bits beyond the 63rd, this will generate the sign bit of V.
 417   for (uint16_t i = 0; i < W; ++i) {
 418     Res[i] = BitValue(V & 1);
 419     V >>= 1;
 420   }
 421   return Res;
 422 }
 423
 424 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 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
 435       const RegisterCell &A2) const {
 436   uint16_t W = A1.width();
 437   assert(W == A2.width());
 438   RegisterCell Res(W);
 439   bool Carry = false;
 440   uint16_t I;
 441   for (I = 0; I < W; ++I) {
 442     const BitValue &V1 = A1[I];
 443     const BitValue &V2 = A2[I];
 444     if (!V1.num() || !V2.num())
 445       break;
 446     unsigned S = bool(V1) + bool(V2) + Carry;
 447     Res[I] = BitValue(S & 1);
 448     Carry = (S > 1);
 449   }
 450   for (; I < W; ++I) {
 451     const BitValue &V1 = A1[I];
 452     const BitValue &V2 = A2[I];
 453     // If the next bit is same as Carry, the result will be 0 plus the
 454     // other bit. The Carry bit will remain unchanged.
 455     if (V1.is(Carry))
 456       Res[I] = BitValue::ref(V2);
 457     else if (V2.is(Carry))
 458       Res[I] = BitValue::ref(V1);
 459     else
 460       break;
 461   }
 462   for (; I < W; ++I)
 463     Res[I] = BitValue::self();
 464   return Res;
 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 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
 501       const RegisterCell &A2) const {
 502   uint16_t W = A1.width() + A2.width();
 503   uint16_t Z = A1.ct(false) + A2.ct(false);
 504   RegisterCell Res(W);
 505   Res.fill(0, Z, BitValue::Zero);
 506   Res.fill(Z, W, BitValue::self());
 507   return Res;
 508 }
 509
 510 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
 511       const RegisterCell &A2) const {
 512   uint16_t W = A1.width() + A2.width();
 513   uint16_t Z = A1.ct(false) + A2.ct(false);
 514   RegisterCell Res(W);
 515   Res.fill(0, Z, BitValue::Zero);
 516   Res.fill(Z, W, BitValue::self());
 517   return Res;
 518 }
 519
 520 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
 521       uint16_t Sh) const {
 522   assert(Sh <= A1.width());
 523   RegisterCell Res = RegisterCell::ref(A1);
 524   Res.rol(Sh);
 525   Res.fill(0, Sh, BitValue::Zero);
 526   return Res;
 527 }
 528
 529 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
 530       uint16_t Sh) const {
 531   uint16_t W = A1.width();
 532   assert(Sh <= W);
 533   RegisterCell Res = RegisterCell::ref(A1);
 534   Res.rol(W-Sh);
 535   Res.fill(W-Sh, W, BitValue::Zero);
 536   return Res;
 537 }
 538
 539 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
 540       uint16_t Sh) const {
 541   uint16_t W = A1.width();
 542   assert(Sh <= W);
 543   RegisterCell Res = RegisterCell::ref(A1);
 544   BitValue Sign = Res[W-1];
 545   Res.rol(W-Sh);
 546   Res.fill(W-Sh, W, Sign);
 547   return Res;
 548 }
 549
 550 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
 551       const RegisterCell &A2) const {
 552   uint16_t W = A1.width();
 553   assert(W == A2.width());
 554   RegisterCell Res(W);
 555   for (uint16_t i = 0; i < W; ++i) {
 556     const BitValue &V1 = A1[i];
 557     const BitValue &V2 = A2[i];
 558     if (V1.is(1))
 559       Res[i] = BitValue::ref(V2);
 560     else if (V2.is(1))
 561       Res[i] = BitValue::ref(V1);
 562     else if (V1.is(0) || V2.is(0))
 563       Res[i] = BitValue::Zero;
 564     else if (V1 == V2)
 565       Res[i] = V1;
 566     else
 567       Res[i] = BitValue::self();
 568   }
 569   return Res;
 570 }
 571
 572 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
 573       const RegisterCell &A2) const {
 574   uint16_t W = A1.width();
 575   assert(W == A2.width());
 576   RegisterCell Res(W);
 577   for (uint16_t i = 0; i < W; ++i) {
 578     const BitValue &V1 = A1[i];
 579     const BitValue &V2 = A2[i];
 580     if (V1.is(1) || V2.is(1))
 581       Res[i] = BitValue::One;
 582     else if (V1.is(0))
 583       Res[i] = BitValue::ref(V2);
 584     else if (V2.is(0))
 585       Res[i] = BitValue::ref(V1);
 586     else if (V1 == V2)
 587       Res[i] = V1;
 588     else
 589       Res[i] = BitValue::self();
 590   }
 591   return Res;
 592 }
 593
 594 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
 595       const RegisterCell &A2) const {
 596   uint16_t W = A1.width();
 597   assert(W == A2.width());
 598   RegisterCell Res(W);
 599   for (uint16_t i = 0; i < W; ++i) {
 600     const BitValue &V1 = A1[i];
 601     const BitValue &V2 = A2[i];
 602     if (V1.is(0))
 603       Res[i] = BitValue::ref(V2);
 604     else if (V2.is(0))
 605       Res[i] = BitValue::ref(V1);
 606     else if (V1 == V2)
 607       Res[i] = BitValue::Zero;
 608     else
 609       Res[i] = BitValue::self();
 610   }
 611   return Res;
 612 }
 613
 614 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
 615   uint16_t W = A1.width();
 616   RegisterCell Res(W);
 617   for (uint16_t i = 0; i < W; ++i) {
 618     const BitValue &V = A1[i];
 619     if (V.is(0))
 620       Res[i] = BitValue::One;
 621     else if (V.is(1))
 622       Res[i] = BitValue::Zero;
 623     else
 624       Res[i] = BitValue::self();
 625   }
 626   return Res;
 627 }
 628
 629 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
 630       uint16_t BitN) const {
 631   assert(BitN < A1.width());
 632   RegisterCell Res = RegisterCell::ref(A1);
 633   Res[BitN] = BitValue::One;
 634   return Res;
 635 }
 636
 637 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
 638       uint16_t BitN) const {
 639   assert(BitN < A1.width());
 640   RegisterCell Res = RegisterCell::ref(A1);
 641   Res[BitN] = BitValue::Zero;
 642   return Res;
 643 }
 644
 645 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
 646       uint16_t W) const {
 647   uint16_t C = A1.cl(B), AW = A1.width();
 648   // If the last leading non-B bit is not a constant, then we don't know
 649   // the real count.
 650   if ((C < AW && A1[AW-1-C].num()) || C == AW)
 651     return eIMM(C, W);
 652   return RegisterCell::self(0, W);
 653 }
 654
 655 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
 656       uint16_t W) const {
 657   uint16_t C = A1.ct(B), AW = A1.width();
 658   // If the last trailing non-B bit is not a constant, then we don't know
 659   // the real count.
 660   if ((C < AW && A1[C].num()) || C == AW)
 661     return eIMM(C, W);
 662   return RegisterCell::self(0, W);
 663 }
 664
 665 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
 666       uint16_t FromN) const {
 667   uint16_t W = A1.width();
 668   assert(FromN <= W);
 669   RegisterCell Res = RegisterCell::ref(A1);
 670   BitValue Sign = Res[FromN-1];
 671   // Sign-extend "inreg".
 672   Res.fill(FromN, W, Sign);
 673   return Res;
 674 }
 675
 676 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
 677       uint16_t FromN) const {
 678   uint16_t W = A1.width();
 679   assert(FromN <= W);
 680   RegisterCell Res = RegisterCell::ref(A1);
 681   Res.fill(FromN, W, BitValue::Zero);
 682   return Res;
 683 }
 684
 685 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
 686       uint16_t B, uint16_t E) const {
 687   uint16_t W = A1.width();
 688   assert(B < W && E <= W);
 689   if (B == E)
 690     return RegisterCell(0);
 691   uint16_t Last = (E > 0) ? E-1 : W-1;
 692   RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
 693   // Return shorter cell.
 694   return Res;
 695 }
 696
 697 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
 698       const RegisterCell &A2, uint16_t AtN) const {
 699   uint16_t W1 = A1.width(), W2 = A2.width();
 700   (void)W1;
 701   assert(AtN < W1 && AtN+W2 <= W1);
 702   // Copy bits from A1, insert A2 at position AtN.
 703   RegisterCell Res = RegisterCell::ref(A1);
 704   if (W2 > 0)
 705     Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
 706   return Res;
 707 }
 708
 709 BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const {
 710   assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
 711   uint16_t W = getRegBitWidth(Reg);
 712   assert(W > 0 && "Cannot generate mask for empty register");
 713   return BitMask(0, W-1);
 714 }
 715
 716 bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
 717                                     const CellMapType &Inputs,
 718                                     CellMapType &Outputs) const {
 719   unsigned Opc = MI.getOpcode();
 720   switch (Opc) {
 721     case TargetOpcode::REG_SEQUENCE: {
 722       RegisterRef RD = MI.getOperand(0);
 723       assert(RD.Sub == 0);
 724       RegisterRef RS = MI.getOperand(1);
 725       unsigned SS = MI.getOperand(2).getImm();
 726       RegisterRef RT = MI.getOperand(3);
 727       unsigned ST = MI.getOperand(4).getImm();
 728       assert(SS != ST);
 729
 730       uint16_t W = getRegBitWidth(RD);
 731       RegisterCell Res(W);
 732       Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
 733       Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
 734       putCell(RD, Res, Outputs);
 735       break;
 736     }
 737
 738     case TargetOpcode::COPY: {
 739       // COPY can transfer a smaller register into a wider one.
 740       // If that is the case, fill the remaining high bits with 0.
 741       RegisterRef RD = MI.getOperand(0);
 742       RegisterRef RS = MI.getOperand(1);
 743       assert(RD.Sub == 0);
 744       uint16_t WD = getRegBitWidth(RD);
 745       uint16_t WS = getRegBitWidth(RS);
 746       assert(WD >= WS);
 747       RegisterCell Src = getCell(RS, Inputs);
 748       RegisterCell Res(WD);
 749       Res.insert(Src, BitMask(0, WS-1));
 750       Res.fill(WS, WD, BitValue::Zero);
 751       putCell(RD, Res, Outputs);
 752       break;
 753     }
 754
 755     default:
 756       return false;
 757   }
 758
 759   return true;
 760 }
 761
 762 // Main W-Z implementation.
 763
 764 void BT::visitPHI(const MachineInstr &PI) {
 765   int ThisN = PI.getParent()->getNumber();
 766   if (Trace)
 767     dbgs() << "Visit FI(BB#" << ThisN << "): " << PI;
 768
 769   const MachineOperand &MD = PI.getOperand(0);
 770   assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
 771   RegisterRef DefRR(MD);
 772   uint16_t DefBW = ME.getRegBitWidth(DefRR);
 773
 774   RegisterCell DefC = ME.getCell(DefRR, Map);
 775   if (DefC == RegisterCell::self(DefRR.Reg, DefBW))    // XXX slow
 776     return;
 777
 778   bool Changed = false;
 779
 780   for (unsigned i = 1, n = PI.getNumOperands(); i < n; i += 2) {
 781     const MachineBasicBlock *PB = PI.getOperand(i + 1).getMBB();
 782     int PredN = PB->getNumber();
 783     if (Trace)
 784       dbgs() << "  edge BB#" << PredN << "->BB#" << ThisN;
 785     if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
 786       if (Trace)
 787         dbgs() << " not executable\n";
 788       continue;
 789     }
 790
 791     RegisterRef RU = PI.getOperand(i);
 792     RegisterCell ResC = ME.getCell(RU, Map);
 793     if (Trace)
 794       dbgs() << " input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
 795              << " cell: " << ResC << "\n";
 796     Changed |= DefC.meet(ResC, DefRR.Reg);
 797   }
 798
 799   if (Changed) {
 800     if (Trace)
 801       dbgs() << "Output: " << PrintReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
 802              << " cell: " << DefC << "\n";
 803     ME.putCell(DefRR, DefC, Map);
 804     visitUsesOf(DefRR.Reg);
 805   }
 806 }
 807
 808 void BT::visitNonBranch(const MachineInstr &MI) {
 809   if (Trace) {
 810     int ThisN = MI.getParent()->getNumber();
 811     dbgs() << "Visit MI(BB#" << ThisN << "): " << MI;
 812   }
 813   if (MI.isDebugValue())
 814     return;
 815   assert(!MI.isBranch() && "Unexpected branch instruction");
 816
 817   CellMapType ResMap;
 818   bool Eval = ME.evaluate(MI, Map, ResMap);
 819
 820   if (Trace && Eval) {
 821     for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
 822       const MachineOperand &MO = MI.getOperand(i);
 823       if (!MO.isReg() || !MO.isUse())
 824         continue;
 825       RegisterRef RU(MO);
 826       dbgs() << "  input reg: " << PrintReg(RU.Reg, &ME.TRI, RU.Sub)
 827              << " cell: " << ME.getCell(RU, Map) << "\n";
 828     }
 829     dbgs() << "Outputs:\n";
 830     for (CellMapType::iterator I = ResMap.begin(), E = ResMap.end();
 831          I != E; ++I) {
 832       RegisterRef RD(I->first);
 833       dbgs() << "  " << PrintReg(I->first, &ME.TRI) << " cell: "
 834              << ME.getCell(RD, ResMap) << "\n";
 835     }
 836   }
 837
 838   // Iterate over all definitions of the instruction, and update the
 839   // cells accordingly.
 840   for (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) {
 841     const MachineOperand &MO = MI.getOperand(i);
 842     // Visit register defs only.
 843     if (!MO.isReg() || !MO.isDef())
 844       continue;
 845     RegisterRef RD(MO);
 846     assert(RD.Sub == 0 && "Unexpected sub-register in definition");
 847     if (!TargetRegisterInfo::isVirtualRegister(RD.Reg))
 848       continue;
 849
 850     bool Changed = false;
 851     if (!Eval || ResMap.count(RD.Reg) == 0) {
 852       // Set to "ref" (aka "bottom").
 853       uint16_t DefBW = ME.getRegBitWidth(RD);
 854       RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
 855       if (RefC != ME.getCell(RD, Map)) {
 856         ME.putCell(RD, RefC, Map);
 857         Changed = true;
 858       }
 859     } else {
 860       RegisterCell DefC = ME.getCell(RD, Map);
 861       RegisterCell ResC = ME.getCell(RD, ResMap);
 862       // This is a non-phi instruction, so the values of the inputs come
 863       // from the same registers each time this instruction is evaluated.
 864       // During the propagation, the values of the inputs can become lowered
 865       // in the sense of the lattice operation, which may cause different
 866       // results to be calculated in subsequent evaluations. This should
 867       // not cause the bottoming of the result in the map, since the new
 868       // result is already reflecting the lowered inputs.
 869       for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
 870         BitValue &V = DefC[i];
 871         // Bits that are already "bottom" should not be updated.
 872         if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
 873           continue;
 874         // Same for those that are identical in DefC and ResC.
 875         if (V == ResC[i])
 876           continue;
 877         V = ResC[i];
 878         Changed = true;
 879       }
 880       if (Changed)
 881         ME.putCell(RD, DefC, Map);
 882     }
 883     if (Changed)
 884       visitUsesOf(RD.Reg);
 885   }
 886 }
 887
 888 void BT::visitBranchesFrom(const MachineInstr &BI) {
 889   const MachineBasicBlock &B = *BI.getParent();
 890   MachineBasicBlock::const_iterator It = BI, End = B.end();
 891   BranchTargetList Targets, BTs;
 892   bool FallsThrough = true, DefaultToAll = false;
 893   int ThisN = B.getNumber();
 894
 895   do {
 896     BTs.clear();
 897     const MachineInstr &MI = *It;
 898     if (Trace)
 899       dbgs() << "Visit BR(BB#" << ThisN << "): " << MI;
 900     assert(MI.isBranch() && "Expecting branch instruction");
 901     InstrExec.insert(&MI);
 902     bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
 903     if (!Eval) {
 904       // If the evaluation failed, we will add all targets. Keep going in
 905       // the loop to mark all executable branches as such.
 906       DefaultToAll = true;
 907       FallsThrough = true;
 908       if (Trace)
 909         dbgs() << "  failed to evaluate: will add all CFG successors\n";
 910     } else if (!DefaultToAll) {
 911       // If evaluated successfully add the targets to the cumulative list.
 912       if (Trace) {
 913         dbgs() << "  adding targets:";
 914         for (unsigned i = 0, n = BTs.size(); i < n; ++i)
 915           dbgs() << " BB#" << BTs[i]->getNumber();
 916         if (FallsThrough)
 917           dbgs() << "\n  falls through\n";
 918         else
 919           dbgs() << "\n  does not fall through\n";
 920       }
 921       Targets.insert(BTs.begin(), BTs.end());
 922     }
 923     ++It;
 924   } while (FallsThrough && It != End);
 925
 926   typedef MachineBasicBlock::const_succ_iterator succ_iterator;
 927   if (!DefaultToAll) {
 928     // Need to add all CFG successors that lead to EH landing pads.
 929     // There won't be explicit branches to these blocks, but they must
 930     // be processed.
 931     for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I) {
 932       const MachineBasicBlock *SB = *I;
 933       if (SB->isEHPad())
 934         Targets.insert(SB);
 935     }
 936     if (FallsThrough) {
 937       MachineFunction::const_iterator BIt = B.getIterator();
 938       MachineFunction::const_iterator Next = std::next(BIt);
 939       if (Next != MF.end())
 940         Targets.insert(&*Next);
 941     }
 942   } else {
 943     for (succ_iterator I = B.succ_begin(), E = B.succ_end(); I != E; ++I)
 944       Targets.insert(*I);
 945   }
 946
 947   for (unsigned i = 0, n = Targets.size(); i < n; ++i) {
 948     int TargetN = Targets[i]->getNumber();
 949     FlowQ.push(CFGEdge(ThisN, TargetN));
 950   }
 951 }
 952
 953 void BT::visitUsesOf(unsigned Reg) {
 954   if (Trace)
 955     dbgs() << "visiting uses of " << PrintReg(Reg, &ME.TRI) << "\n";
 956
 957   typedef MachineRegisterInfo::use_nodbg_iterator use_iterator;
 958   use_iterator End = MRI.use_nodbg_end();
 959   for (use_iterator I = MRI.use_nodbg_begin(Reg); I != End; ++I) {
 960     MachineInstr *UseI = I->getParent();
 961     if (!InstrExec.count(UseI))
 962       continue;
 963     if (UseI->isPHI())
 964       visitPHI(*UseI);
 965     else if (!UseI->isBranch())
 966       visitNonBranch(*UseI);
 967     else
 968       visitBranchesFrom(*UseI);
 969   }
 970 }
 971
 972 BT::RegisterCell BT::get(RegisterRef RR) const {
 973   return ME.getCell(RR, Map);
 974 }
 975
 976 void BT::put(RegisterRef RR, const RegisterCell &RC) {
 977   ME.putCell(RR, RC, Map);
 978 }
 979
 980 // Replace all references to bits from OldRR with the corresponding bits
 981 // in NewRR.
 982 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
 983   assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
 984   BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
 985   BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
 986   uint16_t OMB = OM.first(), OME = OM.last();
 987   uint16_t NMB = NM.first(), NME = NM.last();
 988   (void)NME;
 989   assert((OME-OMB == NME-NMB) &&
 990          "Substituting registers of different lengths");
 991   for (CellMapType::iterator I = Map.begin(), E = Map.end(); I != E; ++I) {
 992     RegisterCell &RC = I->second;
 993     for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
 994       BitValue &V = RC[i];
 995       if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
 996         continue;
 997       if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
 998         continue;
 999       V.RefI.Reg = NewRR.Reg;
1000       V.RefI.Pos += NMB-OMB;
1001     }
1002   }
1003 }
1004
1005 // Check if the block has been "executed" during propagation. (If not, the
1006 // block is dead, but it may still appear to be reachable.)
1007 bool BT::reached(const MachineBasicBlock *B) const {
1008   int BN = B->getNumber();
1009   assert(BN >= 0);
1010   for (EdgeSetType::iterator I = EdgeExec.begin(), E = EdgeExec.end();
1011        I != E; ++I) {
1012     if (I->second == BN)
1013       return true;
1014   }
1015   return false;
1016 }
1017
1018 // Visit an individual instruction. This could be a newly added instruction,
1019 // or one that has been modified by an optimization.
1020 void BT::visit(const MachineInstr &MI) {
1021   assert(!MI.isBranch() && "Only non-branches are allowed");
1022   InstrExec.insert(&MI);
1023   visitNonBranch(MI);
1024   // The call to visitNonBranch could propagate the changes until a branch
1025   // is actually visited. This could result in adding CFG edges to the flow
1026   // queue. Since the queue won't be processed, clear it.
1027   while (!FlowQ.empty())
1028     FlowQ.pop();
1029 }
1030
1031 void BT::reset() {
1032   EdgeExec.clear();
1033   InstrExec.clear();
1034   Map.clear();
1035 }
1036
1037 void BT::run() {
1038   reset();
1039   assert(FlowQ.empty());
1040
1041   typedef GraphTraits<const MachineFunction*> MachineFlowGraphTraits;
1042   const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1043
1044   unsigned MaxBN = 0;
1045   for (MachineFunction::const_iterator I = MF.begin(), E = MF.end();
1046        I != E; ++I) {
1047     assert(I->getNumber() >= 0 && "Disconnected block");
1048     unsigned BN = I->getNumber();
1049     if (BN > MaxBN)
1050       MaxBN = BN;
1051   }
1052
1053   // Keep track of visited blocks.
1054   BitVector BlockScanned(MaxBN+1);
1055
1056   int EntryN = Entry->getNumber();
1057   // Generate a fake edge to get something to start with.
1058   FlowQ.push(CFGEdge(-1, EntryN));
1059
1060   while (!FlowQ.empty()) {
1061     CFGEdge Edge = FlowQ.front();
1062     FlowQ.pop();
1063
1064     if (EdgeExec.count(Edge))
1065       continue;
1066     EdgeExec.insert(Edge);
1067
1068     const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1069     MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1070     // Visit PHI nodes first.
1071     while (It != End && It->isPHI()) {
1072       const MachineInstr &PI = *It++;
1073       InstrExec.insert(&PI);
1074       visitPHI(PI);
1075     }
1076
1077     // If this block has already been visited through a flow graph edge,
1078     // then the instructions have already been processed. Any updates to
1079     // the cells would now only happen through visitUsesOf...
1080     if (BlockScanned[Edge.second])
1081       continue;
1082     BlockScanned[Edge.second] = true;
1083
1084     // Visit non-branch instructions.
1085     while (It != End && !It->isBranch()) {
1086       const MachineInstr &MI = *It++;
1087       InstrExec.insert(&MI);
1088       visitNonBranch(MI);
1089     }
1090     // If block end has been reached, add the fall-through edge to the queue.
1091     if (It == End) {
1092       MachineFunction::const_iterator BIt = B.getIterator();
1093       MachineFunction::const_iterator Next = std::next(BIt);
1094       if (Next != MF.end() && B.isSuccessor(&*Next)) {
1095         int ThisN = B.getNumber();
1096         int NextN = Next->getNumber();
1097         FlowQ.push(CFGEdge(ThisN, NextN));
1098       }
1099     } else {
1100       // Handle the remaining sequence of branches. This function will update
1101       // the work queue.
1102       visitBranchesFrom(*It);
1103     }
1104   } // while (!FlowQ->empty())
1105
1106   if (Trace)
1107     print_cells(dbgs() << "Cells after propagation:\n");
1108 }