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