contrib/llvm-project/llvm/lib/Target/Hexagon/BitTracker.cpp

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