contrib/llvm/lib/Target/Hexagon/HexagonBitSimplify.cpp

   1 //===- HexagonBitSimplify.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 #include "BitTracker.h"
  11 #include "HexagonBitTracker.h"
  12 #include "HexagonInstrInfo.h"
  13 #include "HexagonRegisterInfo.h"
  14 #include "HexagonSubtarget.h"
  15 #include "llvm/ADT/BitVector.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/GraphTraits.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallVector.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineDominators.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFunctionPass.h"
  25 #include "llvm/CodeGen/MachineInstr.h"
  26 #include "llvm/CodeGen/MachineInstrBuilder.h"
  27 #include "llvm/CodeGen/MachineOperand.h"
  28 #include "llvm/CodeGen/MachineRegisterInfo.h"
  29 #include "llvm/CodeGen/TargetRegisterInfo.h"
  30 #include "llvm/IR/DebugLoc.h"
  31 #include "llvm/MC/MCInstrDesc.h"
  32 #include "llvm/Pass.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Compiler.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/ErrorHandling.h"
  37 #include "llvm/Support/MathExtras.h"
  38 #include "llvm/Support/raw_ostream.h"
  39 #include <algorithm>
  40 #include <cassert>
  41 #include <cstdint>
  42 #include <iterator>
  43 #include <limits>
  44 #include <utility>
  45 #include <vector>
  46
  47 #define DEBUG_TYPE "hexbit"
  48
  49 using namespace llvm;
  50
  51 static cl::opt<bool> PreserveTiedOps("hexbit-keep-tied", cl::Hidden,
  52   cl::init(true), cl::desc("Preserve subregisters in tied operands"));
  53 static cl::opt<bool> GenExtract("hexbit-extract", cl::Hidden,
  54   cl::init(true), cl::desc("Generate extract instructions"));
  55 static cl::opt<bool> GenBitSplit("hexbit-bitsplit", cl::Hidden,
  56   cl::init(true), cl::desc("Generate bitsplit instructions"));
  57
  58 static cl::opt<unsigned> MaxExtract("hexbit-max-extract", cl::Hidden,
  59   cl::init(std::numeric_limits<unsigned>::max()));
  60 static unsigned CountExtract = 0;
  61 static cl::opt<unsigned> MaxBitSplit("hexbit-max-bitsplit", cl::Hidden,
  62   cl::init(std::numeric_limits<unsigned>::max()));
  63 static unsigned CountBitSplit = 0;
  64
  65 namespace llvm {
  66
  67   void initializeHexagonBitSimplifyPass(PassRegistry& Registry);
  68   FunctionPass *createHexagonBitSimplify();
  69
  70 } // end namespace llvm
  71
  72 namespace {
  73
  74   // Set of virtual registers, based on BitVector.
  75   struct RegisterSet : private BitVector {
  76     RegisterSet() = default;
  77     explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
  78     RegisterSet(const RegisterSet &RS) = default;
  79
  80     using BitVector::clear;
  81     using BitVector::count;
  82
  83     unsigned find_first() const {
  84       int First = BitVector::find_first();
  85       if (First < 0)
  86         return 0;
  87       return x2v(First);
  88     }
  89
  90     unsigned find_next(unsigned Prev) const {
  91       int Next = BitVector::find_next(v2x(Prev));
  92       if (Next < 0)
  93         return 0;
  94       return x2v(Next);
  95     }
  96
  97     RegisterSet &insert(unsigned R) {
  98       unsigned Idx = v2x(R);
  99       ensure(Idx);
 100       return static_cast<RegisterSet&>(BitVector::set(Idx));
 101     }
 102     RegisterSet &remove(unsigned R) {
 103       unsigned Idx = v2x(R);
 104       if (Idx >= size())
 105         return *this;
 106       return static_cast<RegisterSet&>(BitVector::reset(Idx));
 107     }
 108
 109     RegisterSet &insert(const RegisterSet &Rs) {
 110       return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
 111     }
 112     RegisterSet &remove(const RegisterSet &Rs) {
 113       return static_cast<RegisterSet&>(BitVector::reset(Rs));
 114     }
 115
 116     reference operator[](unsigned R) {
 117       unsigned Idx = v2x(R);
 118       ensure(Idx);
 119       return BitVector::operator[](Idx);
 120     }
 121     bool operator[](unsigned R) const {
 122       unsigned Idx = v2x(R);
 123       assert(Idx < size());
 124       return BitVector::operator[](Idx);
 125     }
 126     bool has(unsigned R) const {
 127       unsigned Idx = v2x(R);
 128       if (Idx >= size())
 129         return false;
 130       return BitVector::test(Idx);
 131     }
 132
 133     bool empty() const {
 134       return !BitVector::any();
 135     }
 136     bool includes(const RegisterSet &Rs) const {
 137       // A.BitVector::test(B)  <=>  A-B != {}
 138       return !Rs.BitVector::test(*this);
 139     }
 140     bool intersects(const RegisterSet &Rs) const {
 141       return BitVector::anyCommon(Rs);
 142     }
 143
 144   private:
 145     void ensure(unsigned Idx) {
 146       if (size() <= Idx)
 147         resize(std::max(Idx+1, 32U));
 148     }
 149
 150     static inline unsigned v2x(unsigned v) {
 151       return TargetRegisterInfo::virtReg2Index(v);
 152     }
 153
 154     static inline unsigned x2v(unsigned x) {
 155       return TargetRegisterInfo::index2VirtReg(x);
 156     }
 157   };
 158
 159   struct PrintRegSet {
 160     PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
 161       : RS(S), TRI(RI) {}
 162
 163     friend raw_ostream &operator<< (raw_ostream &OS,
 164           const PrintRegSet &P);
 165
 166   private:
 167     const RegisterSet &RS;
 168     const TargetRegisterInfo *TRI;
 169   };
 170
 171   raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P)
 172     LLVM_ATTRIBUTE_UNUSED;
 173   raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
 174     OS << '{';
 175     for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
 176       OS << ' ' << printReg(R, P.TRI);
 177     OS << " }";
 178     return OS;
 179   }
 180
 181   class Transformation;
 182
 183   class HexagonBitSimplify : public MachineFunctionPass {
 184   public:
 185     static char ID;
 186
 187     HexagonBitSimplify() : MachineFunctionPass(ID) {}
 188
 189     StringRef getPassName() const override {
 190       return "Hexagon bit simplification";
 191     }
 192
 193     void getAnalysisUsage(AnalysisUsage &AU) const override {
 194       AU.addRequired<MachineDominatorTree>();
 195       AU.addPreserved<MachineDominatorTree>();
 196       MachineFunctionPass::getAnalysisUsage(AU);
 197     }
 198
 199     bool runOnMachineFunction(MachineFunction &MF) override;
 200
 201     static void getInstrDefs(const MachineInstr &MI, RegisterSet &Defs);
 202     static void getInstrUses(const MachineInstr &MI, RegisterSet &Uses);
 203     static bool isEqual(const BitTracker::RegisterCell &RC1, uint16_t B1,
 204         const BitTracker::RegisterCell &RC2, uint16_t B2, uint16_t W);
 205     static bool isZero(const BitTracker::RegisterCell &RC, uint16_t B,
 206         uint16_t W);
 207     static bool getConst(const BitTracker::RegisterCell &RC, uint16_t B,
 208         uint16_t W, uint64_t &U);
 209     static bool replaceReg(unsigned OldR, unsigned NewR,
 210         MachineRegisterInfo &MRI);
 211     static bool getSubregMask(const BitTracker::RegisterRef &RR,
 212         unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI);
 213     static bool replaceRegWithSub(unsigned OldR, unsigned NewR,
 214         unsigned NewSR, MachineRegisterInfo &MRI);
 215     static bool replaceSubWithSub(unsigned OldR, unsigned OldSR,
 216         unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI);
 217     static bool parseRegSequence(const MachineInstr &I,
 218         BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
 219         const MachineRegisterInfo &MRI);
 220
 221     static bool getUsedBitsInStore(unsigned Opc, BitVector &Bits,
 222         uint16_t Begin);
 223     static bool getUsedBits(unsigned Opc, unsigned OpN, BitVector &Bits,
 224         uint16_t Begin, const HexagonInstrInfo &HII);
 225
 226     static const TargetRegisterClass *getFinalVRegClass(
 227         const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI);
 228     static bool isTransparentCopy(const BitTracker::RegisterRef &RD,
 229         const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI);
 230
 231   private:
 232     MachineDominatorTree *MDT = nullptr;
 233
 234     bool visitBlock(MachineBasicBlock &B, Transformation &T, RegisterSet &AVs);
 235     static bool hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
 236         unsigned NewSub = Hexagon::NoSubRegister);
 237   };
 238
 239   using HBS = HexagonBitSimplify;
 240
 241   // The purpose of this class is to provide a common facility to traverse
 242   // the function top-down or bottom-up via the dominator tree, and keep
 243   // track of the available registers.
 244   class Transformation {
 245   public:
 246     bool TopDown;
 247
 248     Transformation(bool TD) : TopDown(TD) {}
 249     virtual ~Transformation() = default;
 250
 251     virtual bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) = 0;
 252   };
 253
 254 } // end anonymous namespace
 255
 256 char HexagonBitSimplify::ID = 0;
 257
 258 INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexagon-bit-simplify",
 259       "Hexagon bit simplification", false, false)
 260 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 261 INITIALIZE_PASS_END(HexagonBitSimplify, "hexagon-bit-simplify",
 262       "Hexagon bit simplification", false, false)
 263
 264 bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
 265       RegisterSet &AVs) {
 266   bool Changed = false;
 267
 268   if (T.TopDown)
 269     Changed = T.processBlock(B, AVs);
 270
 271   RegisterSet Defs;
 272   for (auto &I : B)
 273     getInstrDefs(I, Defs);
 274   RegisterSet NewAVs = AVs;
 275   NewAVs.insert(Defs);
 276
 277   for (auto *DTN : children<MachineDomTreeNode*>(MDT->getNode(&B)))
 278     Changed |= visitBlock(*(DTN->getBlock()), T, NewAVs);
 279
 280   if (!T.TopDown)
 281     Changed |= T.processBlock(B, AVs);
 282
 283   return Changed;
 284 }
 285
 286 //
 287 // Utility functions:
 288 //
 289 void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI,
 290       RegisterSet &Defs) {
 291   for (auto &Op : MI.operands()) {
 292     if (!Op.isReg() || !Op.isDef())
 293       continue;
 294     unsigned R = Op.getReg();
 295     if (!TargetRegisterInfo::isVirtualRegister(R))
 296       continue;
 297     Defs.insert(R);
 298   }
 299 }
 300
 301 void HexagonBitSimplify::getInstrUses(const MachineInstr &MI,
 302       RegisterSet &Uses) {
 303   for (auto &Op : MI.operands()) {
 304     if (!Op.isReg() || !Op.isUse())
 305       continue;
 306     unsigned R = Op.getReg();
 307     if (!TargetRegisterInfo::isVirtualRegister(R))
 308       continue;
 309     Uses.insert(R);
 310   }
 311 }
 312
 313 // Check if all the bits in range [B, E) in both cells are equal.
 314 bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1,
 315       uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2,
 316       uint16_t W) {
 317   for (uint16_t i = 0; i < W; ++i) {
 318     // If RC1[i] is "bottom", it cannot be proven equal to RC2[i].
 319     if (RC1[B1+i].Type == BitTracker::BitValue::Ref && RC1[B1+i].RefI.Reg == 0)
 320       return false;
 321     // Same for RC2[i].
 322     if (RC2[B2+i].Type == BitTracker::BitValue::Ref && RC2[B2+i].RefI.Reg == 0)
 323       return false;
 324     if (RC1[B1+i] != RC2[B2+i])
 325       return false;
 326   }
 327   return true;
 328 }
 329
 330 bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC,
 331       uint16_t B, uint16_t W) {
 332   assert(B < RC.width() && B+W <= RC.width());
 333   for (uint16_t i = B; i < B+W; ++i)
 334     if (!RC[i].is(0))
 335       return false;
 336   return true;
 337 }
 338
 339 bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC,
 340         uint16_t B, uint16_t W, uint64_t &U) {
 341   assert(B < RC.width() && B+W <= RC.width());
 342   int64_t T = 0;
 343   for (uint16_t i = B+W; i > B; --i) {
 344     const BitTracker::BitValue &BV = RC[i-1];
 345     T <<= 1;
 346     if (BV.is(1))
 347       T |= 1;
 348     else if (!BV.is(0))
 349       return false;
 350   }
 351   U = T;
 352   return true;
 353 }
 354
 355 bool HexagonBitSimplify::replaceReg(unsigned OldR, unsigned NewR,
 356       MachineRegisterInfo &MRI) {
 357   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
 358       !TargetRegisterInfo::isVirtualRegister(NewR))
 359     return false;
 360   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
 361   decltype(End) NextI;
 362   for (auto I = Begin; I != End; I = NextI) {
 363     NextI = std::next(I);
 364     I->setReg(NewR);
 365   }
 366   return Begin != End;
 367 }
 368
 369 bool HexagonBitSimplify::replaceRegWithSub(unsigned OldR, unsigned NewR,
 370       unsigned NewSR, MachineRegisterInfo &MRI) {
 371   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
 372       !TargetRegisterInfo::isVirtualRegister(NewR))
 373     return false;
 374   if (hasTiedUse(OldR, MRI, NewSR))
 375     return false;
 376   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
 377   decltype(End) NextI;
 378   for (auto I = Begin; I != End; I = NextI) {
 379     NextI = std::next(I);
 380     I->setReg(NewR);
 381     I->setSubReg(NewSR);
 382   }
 383   return Begin != End;
 384 }
 385
 386 bool HexagonBitSimplify::replaceSubWithSub(unsigned OldR, unsigned OldSR,
 387       unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI) {
 388   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
 389       !TargetRegisterInfo::isVirtualRegister(NewR))
 390     return false;
 391   if (OldSR != NewSR && hasTiedUse(OldR, MRI, NewSR))
 392     return false;
 393   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
 394   decltype(End) NextI;
 395   for (auto I = Begin; I != End; I = NextI) {
 396     NextI = std::next(I);
 397     if (I->getSubReg() != OldSR)
 398       continue;
 399     I->setReg(NewR);
 400     I->setSubReg(NewSR);
 401   }
 402   return Begin != End;
 403 }
 404
 405 // For a register ref (pair Reg:Sub), set Begin to the position of the LSB
 406 // of Sub in Reg, and set Width to the size of Sub in bits. Return true,
 407 // if this succeeded, otherwise return false.
 408 bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR,
 409       unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) {
 410   const TargetRegisterClass *RC = MRI.getRegClass(RR.Reg);
 411   if (RR.Sub == 0) {
 412     Begin = 0;
 413     Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(*RC);
 414     return true;
 415   }
 416
 417   Begin = 0;
 418
 419   switch (RC->getID()) {
 420     case Hexagon::DoubleRegsRegClassID:
 421     case Hexagon::HvxWRRegClassID:
 422       Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(*RC) / 2;
 423       if (RR.Sub == Hexagon::isub_hi || RR.Sub == Hexagon::vsub_hi)
 424         Begin = Width;
 425       break;
 426     default:
 427       return false;
 428   }
 429   return true;
 430 }
 431
 432
 433 // For a REG_SEQUENCE, set SL to the low subregister and SH to the high
 434 // subregister.
 435 bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I,
 436       BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
 437       const MachineRegisterInfo &MRI) {
 438   assert(I.getOpcode() == TargetOpcode::REG_SEQUENCE);
 439   unsigned Sub1 = I.getOperand(2).getImm(), Sub2 = I.getOperand(4).getImm();
 440   auto &DstRC = *MRI.getRegClass(I.getOperand(0).getReg());
 441   auto &HRI = static_cast<const HexagonRegisterInfo&>(
 442                   *MRI.getTargetRegisterInfo());
 443   unsigned SubLo = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_lo);
 444   unsigned SubHi = HRI.getHexagonSubRegIndex(DstRC, Hexagon::ps_sub_hi);
 445   assert((Sub1 == SubLo && Sub2 == SubHi) || (Sub1 == SubHi && Sub2 == SubLo));
 446   if (Sub1 == SubLo && Sub2 == SubHi) {
 447     SL = I.getOperand(1);
 448     SH = I.getOperand(3);
 449     return true;
 450   }
 451   if (Sub1 == SubHi && Sub2 == SubLo) {
 452     SH = I.getOperand(1);
 453     SL = I.getOperand(3);
 454     return true;
 455   }
 456   return false;
 457 }
 458
 459 // All stores (except 64-bit stores) take a 32-bit register as the source
 460 // of the value to be stored. If the instruction stores into a location
 461 // that is shorter than 32 bits, some bits of the source register are not
 462 // used. For each store instruction, calculate the set of used bits in
 463 // the source register, and set appropriate bits in Bits. Return true if
 464 // the bits are calculated, false otherwise.
 465 bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits,
 466       uint16_t Begin) {
 467   using namespace Hexagon;
 468
 469   switch (Opc) {
 470     // Store byte
 471     case S2_storerb_io:           // memb(Rs32+#s11:0)=Rt32
 472     case S2_storerbnew_io:        // memb(Rs32+#s11:0)=Nt8.new
 473     case S2_pstorerbt_io:         // if (Pv4) memb(Rs32+#u6:0)=Rt32
 474     case S2_pstorerbf_io:         // if (!Pv4) memb(Rs32+#u6:0)=Rt32
 475     case S4_pstorerbtnew_io:      // if (Pv4.new) memb(Rs32+#u6:0)=Rt32
 476     case S4_pstorerbfnew_io:      // if (!Pv4.new) memb(Rs32+#u6:0)=Rt32
 477     case S2_pstorerbnewt_io:      // if (Pv4) memb(Rs32+#u6:0)=Nt8.new
 478     case S2_pstorerbnewf_io:      // if (!Pv4) memb(Rs32+#u6:0)=Nt8.new
 479     case S4_pstorerbnewtnew_io:   // if (Pv4.new) memb(Rs32+#u6:0)=Nt8.new
 480     case S4_pstorerbnewfnew_io:   // if (!Pv4.new) memb(Rs32+#u6:0)=Nt8.new
 481     case S2_storerb_pi:           // memb(Rx32++#s4:0)=Rt32
 482     case S2_storerbnew_pi:        // memb(Rx32++#s4:0)=Nt8.new
 483     case S2_pstorerbt_pi:         // if (Pv4) memb(Rx32++#s4:0)=Rt32
 484     case S2_pstorerbf_pi:         // if (!Pv4) memb(Rx32++#s4:0)=Rt32
 485     case S2_pstorerbtnew_pi:      // if (Pv4.new) memb(Rx32++#s4:0)=Rt32
 486     case S2_pstorerbfnew_pi:      // if (!Pv4.new) memb(Rx32++#s4:0)=Rt32
 487     case S2_pstorerbnewt_pi:      // if (Pv4) memb(Rx32++#s4:0)=Nt8.new
 488     case S2_pstorerbnewf_pi:      // if (!Pv4) memb(Rx32++#s4:0)=Nt8.new
 489     case S2_pstorerbnewtnew_pi:   // if (Pv4.new) memb(Rx32++#s4:0)=Nt8.new
 490     case S2_pstorerbnewfnew_pi:   // if (!Pv4.new) memb(Rx32++#s4:0)=Nt8.new
 491     case S4_storerb_ap:           // memb(Re32=#U6)=Rt32
 492     case S4_storerbnew_ap:        // memb(Re32=#U6)=Nt8.new
 493     case S2_storerb_pr:           // memb(Rx32++Mu2)=Rt32
 494     case S2_storerbnew_pr:        // memb(Rx32++Mu2)=Nt8.new
 495     case S4_storerb_ur:           // memb(Ru32<<#u2+#U6)=Rt32
 496     case S4_storerbnew_ur:        // memb(Ru32<<#u2+#U6)=Nt8.new
 497     case S2_storerb_pbr:          // memb(Rx32++Mu2:brev)=Rt32
 498     case S2_storerbnew_pbr:       // memb(Rx32++Mu2:brev)=Nt8.new
 499     case S2_storerb_pci:          // memb(Rx32++#s4:0:circ(Mu2))=Rt32
 500     case S2_storerbnew_pci:       // memb(Rx32++#s4:0:circ(Mu2))=Nt8.new
 501     case S2_storerb_pcr:          // memb(Rx32++I:circ(Mu2))=Rt32
 502     case S2_storerbnew_pcr:       // memb(Rx32++I:circ(Mu2))=Nt8.new
 503     case S4_storerb_rr:           // memb(Rs32+Ru32<<#u2)=Rt32
 504     case S4_storerbnew_rr:        // memb(Rs32+Ru32<<#u2)=Nt8.new
 505     case S4_pstorerbt_rr:         // if (Pv4) memb(Rs32+Ru32<<#u2)=Rt32
 506     case S4_pstorerbf_rr:         // if (!Pv4) memb(Rs32+Ru32<<#u2)=Rt32
 507     case S4_pstorerbtnew_rr:      // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
 508     case S4_pstorerbfnew_rr:      // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
 509     case S4_pstorerbnewt_rr:      // if (Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
 510     case S4_pstorerbnewf_rr:      // if (!Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
 511     case S4_pstorerbnewtnew_rr:   // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
 512     case S4_pstorerbnewfnew_rr:   // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
 513     case S2_storerbgp:            // memb(gp+#u16:0)=Rt32
 514     case S2_storerbnewgp:         // memb(gp+#u16:0)=Nt8.new
 515     case S4_pstorerbt_abs:        // if (Pv4) memb(#u6)=Rt32
 516     case S4_pstorerbf_abs:        // if (!Pv4) memb(#u6)=Rt32
 517     case S4_pstorerbtnew_abs:     // if (Pv4.new) memb(#u6)=Rt32
 518     case S4_pstorerbfnew_abs:     // if (!Pv4.new) memb(#u6)=Rt32
 519     case S4_pstorerbnewt_abs:     // if (Pv4) memb(#u6)=Nt8.new
 520     case S4_pstorerbnewf_abs:     // if (!Pv4) memb(#u6)=Nt8.new
 521     case S4_pstorerbnewtnew_abs:  // if (Pv4.new) memb(#u6)=Nt8.new
 522     case S4_pstorerbnewfnew_abs:  // if (!Pv4.new) memb(#u6)=Nt8.new
 523       Bits.set(Begin, Begin+8);
 524       return true;
 525
 526     // Store low half
 527     case S2_storerh_io:           // memh(Rs32+#s11:1)=Rt32
 528     case S2_storerhnew_io:        // memh(Rs32+#s11:1)=Nt8.new
 529     case S2_pstorerht_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt32
 530     case S2_pstorerhf_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt32
 531     case S4_pstorerhtnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt32
 532     case S4_pstorerhfnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt32
 533     case S2_pstorerhnewt_io:      // if (Pv4) memh(Rs32+#u6:1)=Nt8.new
 534     case S2_pstorerhnewf_io:      // if (!Pv4) memh(Rs32+#u6:1)=Nt8.new
 535     case S4_pstorerhnewtnew_io:   // if (Pv4.new) memh(Rs32+#u6:1)=Nt8.new
 536     case S4_pstorerhnewfnew_io:   // if (!Pv4.new) memh(Rs32+#u6:1)=Nt8.new
 537     case S2_storerh_pi:           // memh(Rx32++#s4:1)=Rt32
 538     case S2_storerhnew_pi:        // memh(Rx32++#s4:1)=Nt8.new
 539     case S2_pstorerht_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt32
 540     case S2_pstorerhf_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt32
 541     case S2_pstorerhtnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt32
 542     case S2_pstorerhfnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt32
 543     case S2_pstorerhnewt_pi:      // if (Pv4) memh(Rx32++#s4:1)=Nt8.new
 544     case S2_pstorerhnewf_pi:      // if (!Pv4) memh(Rx32++#s4:1)=Nt8.new
 545     case S2_pstorerhnewtnew_pi:   // if (Pv4.new) memh(Rx32++#s4:1)=Nt8.new
 546     case S2_pstorerhnewfnew_pi:   // if (!Pv4.new) memh(Rx32++#s4:1)=Nt8.new
 547     case S4_storerh_ap:           // memh(Re32=#U6)=Rt32
 548     case S4_storerhnew_ap:        // memh(Re32=#U6)=Nt8.new
 549     case S2_storerh_pr:           // memh(Rx32++Mu2)=Rt32
 550     case S2_storerhnew_pr:        // memh(Rx32++Mu2)=Nt8.new
 551     case S4_storerh_ur:           // memh(Ru32<<#u2+#U6)=Rt32
 552     case S4_storerhnew_ur:        // memh(Ru32<<#u2+#U6)=Nt8.new
 553     case S2_storerh_pbr:          // memh(Rx32++Mu2:brev)=Rt32
 554     case S2_storerhnew_pbr:       // memh(Rx32++Mu2:brev)=Nt8.new
 555     case S2_storerh_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt32
 556     case S2_storerhnew_pci:       // memh(Rx32++#s4:1:circ(Mu2))=Nt8.new
 557     case S2_storerh_pcr:          // memh(Rx32++I:circ(Mu2))=Rt32
 558     case S2_storerhnew_pcr:       // memh(Rx32++I:circ(Mu2))=Nt8.new
 559     case S4_storerh_rr:           // memh(Rs32+Ru32<<#u2)=Rt32
 560     case S4_pstorerht_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt32
 561     case S4_pstorerhf_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt32
 562     case S4_pstorerhtnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
 563     case S4_pstorerhfnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
 564     case S4_storerhnew_rr:        // memh(Rs32+Ru32<<#u2)=Nt8.new
 565     case S4_pstorerhnewt_rr:      // if (Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
 566     case S4_pstorerhnewf_rr:      // if (!Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
 567     case S4_pstorerhnewtnew_rr:   // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
 568     case S4_pstorerhnewfnew_rr:   // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
 569     case S2_storerhgp:            // memh(gp+#u16:1)=Rt32
 570     case S2_storerhnewgp:         // memh(gp+#u16:1)=Nt8.new
 571     case S4_pstorerht_abs:        // if (Pv4) memh(#u6)=Rt32
 572     case S4_pstorerhf_abs:        // if (!Pv4) memh(#u6)=Rt32
 573     case S4_pstorerhtnew_abs:     // if (Pv4.new) memh(#u6)=Rt32
 574     case S4_pstorerhfnew_abs:     // if (!Pv4.new) memh(#u6)=Rt32
 575     case S4_pstorerhnewt_abs:     // if (Pv4) memh(#u6)=Nt8.new
 576     case S4_pstorerhnewf_abs:     // if (!Pv4) memh(#u6)=Nt8.new
 577     case S4_pstorerhnewtnew_abs:  // if (Pv4.new) memh(#u6)=Nt8.new
 578     case S4_pstorerhnewfnew_abs:  // if (!Pv4.new) memh(#u6)=Nt8.new
 579       Bits.set(Begin, Begin+16);
 580       return true;
 581
 582     // Store high half
 583     case S2_storerf_io:           // memh(Rs32+#s11:1)=Rt.H32
 584     case S2_pstorerft_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt.H32
 585     case S2_pstorerff_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt.H32
 586     case S4_pstorerftnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt.H32
 587     case S4_pstorerffnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt.H32
 588     case S2_storerf_pi:           // memh(Rx32++#s4:1)=Rt.H32
 589     case S2_pstorerft_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt.H32
 590     case S2_pstorerff_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt.H32
 591     case S2_pstorerftnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt.H32
 592     case S2_pstorerffnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt.H32
 593     case S4_storerf_ap:           // memh(Re32=#U6)=Rt.H32
 594     case S2_storerf_pr:           // memh(Rx32++Mu2)=Rt.H32
 595     case S4_storerf_ur:           // memh(Ru32<<#u2+#U6)=Rt.H32
 596     case S2_storerf_pbr:          // memh(Rx32++Mu2:brev)=Rt.H32
 597     case S2_storerf_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt.H32
 598     case S2_storerf_pcr:          // memh(Rx32++I:circ(Mu2))=Rt.H32
 599     case S4_storerf_rr:           // memh(Rs32+Ru32<<#u2)=Rt.H32
 600     case S4_pstorerft_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
 601     case S4_pstorerff_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
 602     case S4_pstorerftnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
 603     case S4_pstorerffnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
 604     case S2_storerfgp:            // memh(gp+#u16:1)=Rt.H32
 605     case S4_pstorerft_abs:        // if (Pv4) memh(#u6)=Rt.H32
 606     case S4_pstorerff_abs:        // if (!Pv4) memh(#u6)=Rt.H32
 607     case S4_pstorerftnew_abs:     // if (Pv4.new) memh(#u6)=Rt.H32
 608     case S4_pstorerffnew_abs:     // if (!Pv4.new) memh(#u6)=Rt.H32
 609       Bits.set(Begin+16, Begin+32);
 610       return true;
 611   }
 612
 613   return false;
 614 }
 615
 616 // For an instruction with opcode Opc, calculate the set of bits that it
 617 // uses in a register in operand OpN. This only calculates the set of used
 618 // bits for cases where it does not depend on any operands (as is the case
 619 // in shifts, for example). For concrete instructions from a program, the
 620 // operand may be a subregister of a larger register, while Bits would
 621 // correspond to the larger register in its entirety. Because of that,
 622 // the parameter Begin can be used to indicate which bit of Bits should be
 623 // considered the LSB of the operand.
 624 bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN,
 625       BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) {
 626   using namespace Hexagon;
 627
 628   const MCInstrDesc &D = HII.get(Opc);
 629   if (D.mayStore()) {
 630     if (OpN == D.getNumOperands()-1)
 631       return getUsedBitsInStore(Opc, Bits, Begin);
 632     return false;
 633   }
 634
 635   switch (Opc) {
 636     // One register source. Used bits: R1[0-7].
 637     case A2_sxtb:
 638     case A2_zxtb:
 639     case A4_cmpbeqi:
 640     case A4_cmpbgti:
 641     case A4_cmpbgtui:
 642       if (OpN == 1) {
 643         Bits.set(Begin, Begin+8);
 644         return true;
 645       }
 646       break;
 647
 648     // One register source. Used bits: R1[0-15].
 649     case A2_aslh:
 650     case A2_sxth:
 651     case A2_zxth:
 652     case A4_cmpheqi:
 653     case A4_cmphgti:
 654     case A4_cmphgtui:
 655       if (OpN == 1) {
 656         Bits.set(Begin, Begin+16);
 657         return true;
 658       }
 659       break;
 660
 661     // One register source. Used bits: R1[16-31].
 662     case A2_asrh:
 663       if (OpN == 1) {
 664         Bits.set(Begin+16, Begin+32);
 665         return true;
 666       }
 667       break;
 668
 669     // Two register sources. Used bits: R1[0-7], R2[0-7].
 670     case A4_cmpbeq:
 671     case A4_cmpbgt:
 672     case A4_cmpbgtu:
 673       if (OpN == 1) {
 674         Bits.set(Begin, Begin+8);
 675         return true;
 676       }
 677       break;
 678
 679     // Two register sources. Used bits: R1[0-15], R2[0-15].
 680     case A4_cmpheq:
 681     case A4_cmphgt:
 682     case A4_cmphgtu:
 683     case A2_addh_h16_ll:
 684     case A2_addh_h16_sat_ll:
 685     case A2_addh_l16_ll:
 686     case A2_addh_l16_sat_ll:
 687     case A2_combine_ll:
 688     case A2_subh_h16_ll:
 689     case A2_subh_h16_sat_ll:
 690     case A2_subh_l16_ll:
 691     case A2_subh_l16_sat_ll:
 692     case M2_mpy_acc_ll_s0:
 693     case M2_mpy_acc_ll_s1:
 694     case M2_mpy_acc_sat_ll_s0:
 695     case M2_mpy_acc_sat_ll_s1:
 696     case M2_mpy_ll_s0:
 697     case M2_mpy_ll_s1:
 698     case M2_mpy_nac_ll_s0:
 699     case M2_mpy_nac_ll_s1:
 700     case M2_mpy_nac_sat_ll_s0:
 701     case M2_mpy_nac_sat_ll_s1:
 702     case M2_mpy_rnd_ll_s0:
 703     case M2_mpy_rnd_ll_s1:
 704     case M2_mpy_sat_ll_s0:
 705     case M2_mpy_sat_ll_s1:
 706     case M2_mpy_sat_rnd_ll_s0:
 707     case M2_mpy_sat_rnd_ll_s1:
 708     case M2_mpyd_acc_ll_s0:
 709     case M2_mpyd_acc_ll_s1:
 710     case M2_mpyd_ll_s0:
 711     case M2_mpyd_ll_s1:
 712     case M2_mpyd_nac_ll_s0:
 713     case M2_mpyd_nac_ll_s1:
 714     case M2_mpyd_rnd_ll_s0:
 715     case M2_mpyd_rnd_ll_s1:
 716     case M2_mpyu_acc_ll_s0:
 717     case M2_mpyu_acc_ll_s1:
 718     case M2_mpyu_ll_s0:
 719     case M2_mpyu_ll_s1:
 720     case M2_mpyu_nac_ll_s0:
 721     case M2_mpyu_nac_ll_s1:
 722     case M2_mpyud_acc_ll_s0:
 723     case M2_mpyud_acc_ll_s1:
 724     case M2_mpyud_ll_s0:
 725     case M2_mpyud_ll_s1:
 726     case M2_mpyud_nac_ll_s0:
 727     case M2_mpyud_nac_ll_s1:
 728       if (OpN == 1 || OpN == 2) {
 729         Bits.set(Begin, Begin+16);
 730         return true;
 731       }
 732       break;
 733
 734     // Two register sources. Used bits: R1[0-15], R2[16-31].
 735     case A2_addh_h16_lh:
 736     case A2_addh_h16_sat_lh:
 737     case A2_combine_lh:
 738     case A2_subh_h16_lh:
 739     case A2_subh_h16_sat_lh:
 740     case M2_mpy_acc_lh_s0:
 741     case M2_mpy_acc_lh_s1:
 742     case M2_mpy_acc_sat_lh_s0:
 743     case M2_mpy_acc_sat_lh_s1:
 744     case M2_mpy_lh_s0:
 745     case M2_mpy_lh_s1:
 746     case M2_mpy_nac_lh_s0:
 747     case M2_mpy_nac_lh_s1:
 748     case M2_mpy_nac_sat_lh_s0:
 749     case M2_mpy_nac_sat_lh_s1:
 750     case M2_mpy_rnd_lh_s0:
 751     case M2_mpy_rnd_lh_s1:
 752     case M2_mpy_sat_lh_s0:
 753     case M2_mpy_sat_lh_s1:
 754     case M2_mpy_sat_rnd_lh_s0:
 755     case M2_mpy_sat_rnd_lh_s1:
 756     case M2_mpyd_acc_lh_s0:
 757     case M2_mpyd_acc_lh_s1:
 758     case M2_mpyd_lh_s0:
 759     case M2_mpyd_lh_s1:
 760     case M2_mpyd_nac_lh_s0:
 761     case M2_mpyd_nac_lh_s1:
 762     case M2_mpyd_rnd_lh_s0:
 763     case M2_mpyd_rnd_lh_s1:
 764     case M2_mpyu_acc_lh_s0:
 765     case M2_mpyu_acc_lh_s1:
 766     case M2_mpyu_lh_s0:
 767     case M2_mpyu_lh_s1:
 768     case M2_mpyu_nac_lh_s0:
 769     case M2_mpyu_nac_lh_s1:
 770     case M2_mpyud_acc_lh_s0:
 771     case M2_mpyud_acc_lh_s1:
 772     case M2_mpyud_lh_s0:
 773     case M2_mpyud_lh_s1:
 774     case M2_mpyud_nac_lh_s0:
 775     case M2_mpyud_nac_lh_s1:
 776     // These four are actually LH.
 777     case A2_addh_l16_hl:
 778     case A2_addh_l16_sat_hl:
 779     case A2_subh_l16_hl:
 780     case A2_subh_l16_sat_hl:
 781       if (OpN == 1) {
 782         Bits.set(Begin, Begin+16);
 783         return true;
 784       }
 785       if (OpN == 2) {
 786         Bits.set(Begin+16, Begin+32);
 787         return true;
 788       }
 789       break;
 790
 791     // Two register sources, used bits: R1[16-31], R2[0-15].
 792     case A2_addh_h16_hl:
 793     case A2_addh_h16_sat_hl:
 794     case A2_combine_hl:
 795     case A2_subh_h16_hl:
 796     case A2_subh_h16_sat_hl:
 797     case M2_mpy_acc_hl_s0:
 798     case M2_mpy_acc_hl_s1:
 799     case M2_mpy_acc_sat_hl_s0:
 800     case M2_mpy_acc_sat_hl_s1:
 801     case M2_mpy_hl_s0:
 802     case M2_mpy_hl_s1:
 803     case M2_mpy_nac_hl_s0:
 804     case M2_mpy_nac_hl_s1:
 805     case M2_mpy_nac_sat_hl_s0:
 806     case M2_mpy_nac_sat_hl_s1:
 807     case M2_mpy_rnd_hl_s0:
 808     case M2_mpy_rnd_hl_s1:
 809     case M2_mpy_sat_hl_s0:
 810     case M2_mpy_sat_hl_s1:
 811     case M2_mpy_sat_rnd_hl_s0:
 812     case M2_mpy_sat_rnd_hl_s1:
 813     case M2_mpyd_acc_hl_s0:
 814     case M2_mpyd_acc_hl_s1:
 815     case M2_mpyd_hl_s0:
 816     case M2_mpyd_hl_s1:
 817     case M2_mpyd_nac_hl_s0:
 818     case M2_mpyd_nac_hl_s1:
 819     case M2_mpyd_rnd_hl_s0:
 820     case M2_mpyd_rnd_hl_s1:
 821     case M2_mpyu_acc_hl_s0:
 822     case M2_mpyu_acc_hl_s1:
 823     case M2_mpyu_hl_s0:
 824     case M2_mpyu_hl_s1:
 825     case M2_mpyu_nac_hl_s0:
 826     case M2_mpyu_nac_hl_s1:
 827     case M2_mpyud_acc_hl_s0:
 828     case M2_mpyud_acc_hl_s1:
 829     case M2_mpyud_hl_s0:
 830     case M2_mpyud_hl_s1:
 831     case M2_mpyud_nac_hl_s0:
 832     case M2_mpyud_nac_hl_s1:
 833       if (OpN == 1) {
 834         Bits.set(Begin+16, Begin+32);
 835         return true;
 836       }
 837       if (OpN == 2) {
 838         Bits.set(Begin, Begin+16);
 839         return true;
 840       }
 841       break;
 842
 843     // Two register sources, used bits: R1[16-31], R2[16-31].
 844     case A2_addh_h16_hh:
 845     case A2_addh_h16_sat_hh:
 846     case A2_combine_hh:
 847     case A2_subh_h16_hh:
 848     case A2_subh_h16_sat_hh:
 849     case M2_mpy_acc_hh_s0:
 850     case M2_mpy_acc_hh_s1:
 851     case M2_mpy_acc_sat_hh_s0:
 852     case M2_mpy_acc_sat_hh_s1:
 853     case M2_mpy_hh_s0:
 854     case M2_mpy_hh_s1:
 855     case M2_mpy_nac_hh_s0:
 856     case M2_mpy_nac_hh_s1:
 857     case M2_mpy_nac_sat_hh_s0:
 858     case M2_mpy_nac_sat_hh_s1:
 859     case M2_mpy_rnd_hh_s0:
 860     case M2_mpy_rnd_hh_s1:
 861     case M2_mpy_sat_hh_s0:
 862     case M2_mpy_sat_hh_s1:
 863     case M2_mpy_sat_rnd_hh_s0:
 864     case M2_mpy_sat_rnd_hh_s1:
 865     case M2_mpyd_acc_hh_s0:
 866     case M2_mpyd_acc_hh_s1:
 867     case M2_mpyd_hh_s0:
 868     case M2_mpyd_hh_s1:
 869     case M2_mpyd_nac_hh_s0:
 870     case M2_mpyd_nac_hh_s1:
 871     case M2_mpyd_rnd_hh_s0:
 872     case M2_mpyd_rnd_hh_s1:
 873     case M2_mpyu_acc_hh_s0:
 874     case M2_mpyu_acc_hh_s1:
 875     case M2_mpyu_hh_s0:
 876     case M2_mpyu_hh_s1:
 877     case M2_mpyu_nac_hh_s0:
 878     case M2_mpyu_nac_hh_s1:
 879     case M2_mpyud_acc_hh_s0:
 880     case M2_mpyud_acc_hh_s1:
 881     case M2_mpyud_hh_s0:
 882     case M2_mpyud_hh_s1:
 883     case M2_mpyud_nac_hh_s0:
 884     case M2_mpyud_nac_hh_s1:
 885       if (OpN == 1 || OpN == 2) {
 886         Bits.set(Begin+16, Begin+32);
 887         return true;
 888       }
 889       break;
 890   }
 891
 892   return false;
 893 }
 894
 895 // Calculate the register class that matches Reg:Sub. For example, if
 896 // %1 is a double register, then %1:isub_hi would match the "int"
 897 // register class.
 898 const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass(
 899       const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) {
 900   if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
 901     return nullptr;
 902   auto *RC = MRI.getRegClass(RR.Reg);
 903   if (RR.Sub == 0)
 904     return RC;
 905   auto &HRI = static_cast<const HexagonRegisterInfo&>(
 906                   *MRI.getTargetRegisterInfo());
 907
 908   auto VerifySR = [&HRI] (const TargetRegisterClass *RC, unsigned Sub) -> void {
 909     (void)HRI;
 910     assert(Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_lo) ||
 911            Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_hi));
 912   };
 913
 914   switch (RC->getID()) {
 915     case Hexagon::DoubleRegsRegClassID:
 916       VerifySR(RC, RR.Sub);
 917       return &Hexagon::IntRegsRegClass;
 918     case Hexagon::HvxWRRegClassID:
 919       VerifySR(RC, RR.Sub);
 920       return &Hexagon::HvxVRRegClass;
 921   }
 922   return nullptr;
 923 }
 924
 925 // Check if RD could be replaced with RS at any possible use of RD.
 926 // For example a predicate register cannot be replaced with a integer
 927 // register, but a 64-bit register with a subregister can be replaced
 928 // with a 32-bit register.
 929 bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD,
 930       const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) {
 931   if (!TargetRegisterInfo::isVirtualRegister(RD.Reg) ||
 932       !TargetRegisterInfo::isVirtualRegister(RS.Reg))
 933     return false;
 934   // Return false if one (or both) classes are nullptr.
 935   auto *DRC = getFinalVRegClass(RD, MRI);
 936   if (!DRC)
 937     return false;
 938
 939   return DRC == getFinalVRegClass(RS, MRI);
 940 }
 941
 942 bool HexagonBitSimplify::hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
 943       unsigned NewSub) {
 944   if (!PreserveTiedOps)
 945     return false;
 946   return llvm::any_of(MRI.use_operands(Reg),
 947                       [NewSub] (const MachineOperand &Op) -> bool {
 948                         return Op.getSubReg() != NewSub && Op.isTied();
 949                       });
 950 }
 951
 952 namespace {
 953
 954   class DeadCodeElimination {
 955   public:
 956     DeadCodeElimination(MachineFunction &mf, MachineDominatorTree &mdt)
 957       : MF(mf), HII(*MF.getSubtarget<HexagonSubtarget>().getInstrInfo()),
 958         MDT(mdt), MRI(mf.getRegInfo()) {}
 959
 960     bool run() {
 961       return runOnNode(MDT.getRootNode());
 962     }
 963
 964   private:
 965     bool isDead(unsigned R) const;
 966     bool runOnNode(MachineDomTreeNode *N);
 967
 968     MachineFunction &MF;
 969     const HexagonInstrInfo &HII;
 970     MachineDominatorTree &MDT;
 971     MachineRegisterInfo &MRI;
 972   };
 973
 974 } // end anonymous namespace
 975
 976 bool DeadCodeElimination::isDead(unsigned R) const {
 977   for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) {
 978     MachineInstr *UseI = I->getParent();
 979     if (UseI->isDebugValue())
 980       continue;
 981     if (UseI->isPHI()) {
 982       assert(!UseI->getOperand(0).getSubReg());
 983       unsigned DR = UseI->getOperand(0).getReg();
 984       if (DR == R)
 985         continue;
 986     }
 987     return false;
 988   }
 989   return true;
 990 }
 991
 992 bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) {
 993   bool Changed = false;
 994
 995   for (auto *DTN : children<MachineDomTreeNode*>(N))
 996     Changed |= runOnNode(DTN);
 997
 998   MachineBasicBlock *B = N->getBlock();
 999   std::vector<MachineInstr*> Instrs;
1000   for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
1001     Instrs.push_back(&*I);
1002
1003   for (auto MI : Instrs) {
1004     unsigned Opc = MI->getOpcode();
1005     // Do not touch lifetime markers. This is why the target-independent DCE
1006     // cannot be used.
1007     if (Opc == TargetOpcode::LIFETIME_START ||
1008         Opc == TargetOpcode::LIFETIME_END)
1009       continue;
1010     bool Store = false;
1011     if (MI->isInlineAsm())
1012       continue;
1013     // Delete PHIs if possible.
1014     if (!MI->isPHI() && !MI->isSafeToMove(nullptr, Store))
1015       continue;
1016
1017     bool AllDead = true;
1018     SmallVector<unsigned,2> Regs;
1019     for (auto &Op : MI->operands()) {
1020       if (!Op.isReg() || !Op.isDef())
1021         continue;
1022       unsigned R = Op.getReg();
1023       if (!TargetRegisterInfo::isVirtualRegister(R) || !isDead(R)) {
1024         AllDead = false;
1025         break;
1026       }
1027       Regs.push_back(R);
1028     }
1029     if (!AllDead)
1030       continue;
1031
1032     B->erase(MI);
1033     for (unsigned i = 0, n = Regs.size(); i != n; ++i)
1034       MRI.markUsesInDebugValueAsUndef(Regs[i]);
1035     Changed = true;
1036   }
1037
1038   return Changed;
1039 }
1040
1041 namespace {
1042
1043 // Eliminate redundant instructions
1044 //
1045 // This transformation will identify instructions where the output register
1046 // is the same as one of its input registers. This only works on instructions
1047 // that define a single register (unlike post-increment loads, for example).
1048 // The equality check is actually more detailed: the code calculates which
1049 // bits of the output are used, and only compares these bits with the input
1050 // registers.
1051 // If the output matches an input, the instruction is replaced with COPY.
1052 // The copies will be removed by another transformation.
1053   class RedundantInstrElimination : public Transformation {
1054   public:
1055     RedundantInstrElimination(BitTracker &bt, const HexagonInstrInfo &hii,
1056           const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1057         : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1058
1059     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1060
1061   private:
1062     bool isLossyShiftLeft(const MachineInstr &MI, unsigned OpN,
1063           unsigned &LostB, unsigned &LostE);
1064     bool isLossyShiftRight(const MachineInstr &MI, unsigned OpN,
1065           unsigned &LostB, unsigned &LostE);
1066     bool computeUsedBits(unsigned Reg, BitVector &Bits);
1067     bool computeUsedBits(const MachineInstr &MI, unsigned OpN, BitVector &Bits,
1068           uint16_t Begin);
1069     bool usedBitsEqual(BitTracker::RegisterRef RD, BitTracker::RegisterRef RS);
1070
1071     const HexagonInstrInfo &HII;
1072     const HexagonRegisterInfo &HRI;
1073     MachineRegisterInfo &MRI;
1074     BitTracker &BT;
1075   };
1076
1077 } // end anonymous namespace
1078
1079 // Check if the instruction is a lossy shift left, where the input being
1080 // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1081 // of bit indices that are lost.
1082 bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI,
1083       unsigned OpN, unsigned &LostB, unsigned &LostE) {
1084   using namespace Hexagon;
1085
1086   unsigned Opc = MI.getOpcode();
1087   unsigned ImN, RegN, Width;
1088   switch (Opc) {
1089     case S2_asl_i_p:
1090       ImN = 2;
1091       RegN = 1;
1092       Width = 64;
1093       break;
1094     case S2_asl_i_p_acc:
1095     case S2_asl_i_p_and:
1096     case S2_asl_i_p_nac:
1097     case S2_asl_i_p_or:
1098     case S2_asl_i_p_xacc:
1099       ImN = 3;
1100       RegN = 2;
1101       Width = 64;
1102       break;
1103     case S2_asl_i_r:
1104       ImN = 2;
1105       RegN = 1;
1106       Width = 32;
1107       break;
1108     case S2_addasl_rrri:
1109     case S4_andi_asl_ri:
1110     case S4_ori_asl_ri:
1111     case S4_addi_asl_ri:
1112     case S4_subi_asl_ri:
1113     case S2_asl_i_r_acc:
1114     case S2_asl_i_r_and:
1115     case S2_asl_i_r_nac:
1116     case S2_asl_i_r_or:
1117     case S2_asl_i_r_sat:
1118     case S2_asl_i_r_xacc:
1119       ImN = 3;
1120       RegN = 2;
1121       Width = 32;
1122       break;
1123     default:
1124       return false;
1125   }
1126
1127   if (RegN != OpN)
1128     return false;
1129
1130   assert(MI.getOperand(ImN).isImm());
1131   unsigned S = MI.getOperand(ImN).getImm();
1132   if (S == 0)
1133     return false;
1134   LostB = Width-S;
1135   LostE = Width;
1136   return true;
1137 }
1138
1139 // Check if the instruction is a lossy shift right, where the input being
1140 // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1141 // of bit indices that are lost.
1142 bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI,
1143       unsigned OpN, unsigned &LostB, unsigned &LostE) {
1144   using namespace Hexagon;
1145
1146   unsigned Opc = MI.getOpcode();
1147   unsigned ImN, RegN;
1148   switch (Opc) {
1149     case S2_asr_i_p:
1150     case S2_lsr_i_p:
1151       ImN = 2;
1152       RegN = 1;
1153       break;
1154     case S2_asr_i_p_acc:
1155     case S2_asr_i_p_and:
1156     case S2_asr_i_p_nac:
1157     case S2_asr_i_p_or:
1158     case S2_lsr_i_p_acc:
1159     case S2_lsr_i_p_and:
1160     case S2_lsr_i_p_nac:
1161     case S2_lsr_i_p_or:
1162     case S2_lsr_i_p_xacc:
1163       ImN = 3;
1164       RegN = 2;
1165       break;
1166     case S2_asr_i_r:
1167     case S2_lsr_i_r:
1168       ImN = 2;
1169       RegN = 1;
1170       break;
1171     case S4_andi_lsr_ri:
1172     case S4_ori_lsr_ri:
1173     case S4_addi_lsr_ri:
1174     case S4_subi_lsr_ri:
1175     case S2_asr_i_r_acc:
1176     case S2_asr_i_r_and:
1177     case S2_asr_i_r_nac:
1178     case S2_asr_i_r_or:
1179     case S2_lsr_i_r_acc:
1180     case S2_lsr_i_r_and:
1181     case S2_lsr_i_r_nac:
1182     case S2_lsr_i_r_or:
1183     case S2_lsr_i_r_xacc:
1184       ImN = 3;
1185       RegN = 2;
1186       break;
1187
1188     default:
1189       return false;
1190   }
1191
1192   if (RegN != OpN)
1193     return false;
1194
1195   assert(MI.getOperand(ImN).isImm());
1196   unsigned S = MI.getOperand(ImN).getImm();
1197   LostB = 0;
1198   LostE = S;
1199   return true;
1200 }
1201
1202 // Calculate the bit vector that corresponds to the used bits of register Reg.
1203 // The vector Bits has the same size, as the size of Reg in bits. If the cal-
1204 // culation fails (i.e. the used bits are unknown), it returns false. Other-
1205 // wise, it returns true and sets the corresponding bits in Bits.
1206 bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) {
1207   BitVector Used(Bits.size());
1208   RegisterSet Visited;
1209   std::vector<unsigned> Pending;
1210   Pending.push_back(Reg);
1211
1212   for (unsigned i = 0; i < Pending.size(); ++i) {
1213     unsigned R = Pending[i];
1214     if (Visited.has(R))
1215       continue;
1216     Visited.insert(R);
1217     for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) {
1218       BitTracker::RegisterRef UR = *I;
1219       unsigned B, W;
1220       if (!HBS::getSubregMask(UR, B, W, MRI))
1221         return false;
1222       MachineInstr &UseI = *I->getParent();
1223       if (UseI.isPHI() || UseI.isCopy()) {
1224         unsigned DefR = UseI.getOperand(0).getReg();
1225         if (!TargetRegisterInfo::isVirtualRegister(DefR))
1226           return false;
1227         Pending.push_back(DefR);
1228       } else {
1229         if (!computeUsedBits(UseI, I.getOperandNo(), Used, B))
1230           return false;
1231       }
1232     }
1233   }
1234   Bits |= Used;
1235   return true;
1236 }
1237
1238 // Calculate the bits used by instruction MI in a register in operand OpN.
1239 // Return true/false if the calculation succeeds/fails. If is succeeds, set
1240 // used bits in Bits. This function does not reset any bits in Bits, so
1241 // subsequent calls over different instructions will result in the union
1242 // of the used bits in all these instructions.
1243 // The register in question may be used with a sub-register, whereas Bits
1244 // holds the bits for the entire register. To keep track of that, the
1245 // argument Begin indicates where in Bits is the lowest-significant bit
1246 // of the register used in operand OpN. For example, in instruction:
1247 //   %1 = S2_lsr_i_r %2:isub_hi, 10
1248 // the operand 1 is a 32-bit register, which happens to be a subregister
1249 // of the 64-bit register %2, and that subregister starts at position 32.
1250 // In this case Begin=32, since Bits[32] would be the lowest-significant bit
1251 // of %2:isub_hi.
1252 bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI,
1253       unsigned OpN, BitVector &Bits, uint16_t Begin) {
1254   unsigned Opc = MI.getOpcode();
1255   BitVector T(Bits.size());
1256   bool GotBits = HBS::getUsedBits(Opc, OpN, T, Begin, HII);
1257   // Even if we don't have bits yet, we could still provide some information
1258   // if the instruction is a lossy shift: the lost bits will be marked as
1259   // not used.
1260   unsigned LB, LE;
1261   if (isLossyShiftLeft(MI, OpN, LB, LE) || isLossyShiftRight(MI, OpN, LB, LE)) {
1262     assert(MI.getOperand(OpN).isReg());
1263     BitTracker::RegisterRef RR = MI.getOperand(OpN);
1264     const TargetRegisterClass *RC = HBS::getFinalVRegClass(RR, MRI);
1265     uint16_t Width = HRI.getRegSizeInBits(*RC);
1266
1267     if (!GotBits)
1268       T.set(Begin, Begin+Width);
1269     assert(LB <= LE && LB < Width && LE <= Width);
1270     T.reset(Begin+LB, Begin+LE);
1271     GotBits = true;
1272   }
1273   if (GotBits)
1274     Bits |= T;
1275   return GotBits;
1276 }
1277
1278 // Calculates the used bits in RD ("defined register"), and checks if these
1279 // bits in RS ("used register") and RD are identical.
1280 bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD,
1281       BitTracker::RegisterRef RS) {
1282   const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1283   const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1284
1285   unsigned DB, DW;
1286   if (!HBS::getSubregMask(RD, DB, DW, MRI))
1287     return false;
1288   unsigned SB, SW;
1289   if (!HBS::getSubregMask(RS, SB, SW, MRI))
1290     return false;
1291   if (SW != DW)
1292     return false;
1293
1294   BitVector Used(DC.width());
1295   if (!computeUsedBits(RD.Reg, Used))
1296     return false;
1297
1298   for (unsigned i = 0; i != DW; ++i)
1299     if (Used[i+DB] && DC[DB+i] != SC[SB+i])
1300       return false;
1301   return true;
1302 }
1303
1304 bool RedundantInstrElimination::processBlock(MachineBasicBlock &B,
1305       const RegisterSet&) {
1306   if (!BT.reached(&B))
1307     return false;
1308   bool Changed = false;
1309
1310   for (auto I = B.begin(), E = B.end(), NextI = I; I != E; ++I) {
1311     NextI = std::next(I);
1312     MachineInstr *MI = &*I;
1313
1314     if (MI->getOpcode() == TargetOpcode::COPY)
1315       continue;
1316     if (MI->isPHI() || MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
1317       continue;
1318     unsigned NumD = MI->getDesc().getNumDefs();
1319     if (NumD != 1)
1320       continue;
1321
1322     BitTracker::RegisterRef RD = MI->getOperand(0);
1323     if (!BT.has(RD.Reg))
1324       continue;
1325     const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1326     auto At = MachineBasicBlock::iterator(MI);
1327
1328     // Find a source operand that is equal to the result.
1329     for (auto &Op : MI->uses()) {
1330       if (!Op.isReg())
1331         continue;
1332       BitTracker::RegisterRef RS = Op;
1333       if (!BT.has(RS.Reg))
1334         continue;
1335       if (!HBS::isTransparentCopy(RD, RS, MRI))
1336         continue;
1337
1338       unsigned BN, BW;
1339       if (!HBS::getSubregMask(RS, BN, BW, MRI))
1340         continue;
1341
1342       const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1343       if (!usedBitsEqual(RD, RS) && !HBS::isEqual(DC, 0, SC, BN, BW))
1344         continue;
1345
1346       // If found, replace the instruction with a COPY.
1347       const DebugLoc &DL = MI->getDebugLoc();
1348       const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
1349       unsigned NewR = MRI.createVirtualRegister(FRC);
1350       MachineInstr *CopyI =
1351           BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1352             .addReg(RS.Reg, 0, RS.Sub);
1353       HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1354       // This pass can create copies between registers that don't have the
1355       // exact same values. Updating the tracker has to involve updating
1356       // all dependent cells. Example:
1357       //   %1  = inst %2     ; %1 != %2, but used bits are equal
1358       //
1359       //   %3  = copy %2     ; <- inserted
1360       //   ... = %3          ; <- replaced from %2
1361       // Indirectly, we can create a "copy" between %1 and %2 even
1362       // though their exact values do not match.
1363       BT.visit(*CopyI);
1364       Changed = true;
1365       break;
1366     }
1367   }
1368
1369   return Changed;
1370 }
1371
1372 namespace {
1373
1374 // Recognize instructions that produce constant values known at compile-time.
1375 // Replace them with register definitions that load these constants directly.
1376   class ConstGeneration : public Transformation {
1377   public:
1378     ConstGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1379         MachineRegisterInfo &mri)
1380       : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1381
1382     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1383     static bool isTfrConst(const MachineInstr &MI);
1384
1385   private:
1386     unsigned genTfrConst(const TargetRegisterClass *RC, int64_t C,
1387         MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL);
1388
1389     const HexagonInstrInfo &HII;
1390     MachineRegisterInfo &MRI;
1391     BitTracker &BT;
1392   };
1393
1394 } // end anonymous namespace
1395
1396 bool ConstGeneration::isTfrConst(const MachineInstr &MI) {
1397   unsigned Opc = MI.getOpcode();
1398   switch (Opc) {
1399     case Hexagon::A2_combineii:
1400     case Hexagon::A4_combineii:
1401     case Hexagon::A2_tfrsi:
1402     case Hexagon::A2_tfrpi:
1403     case Hexagon::PS_true:
1404     case Hexagon::PS_false:
1405     case Hexagon::CONST32:
1406     case Hexagon::CONST64:
1407       return true;
1408   }
1409   return false;
1410 }
1411
1412 // Generate a transfer-immediate instruction that is appropriate for the
1413 // register class and the actual value being transferred.
1414 unsigned ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C,
1415       MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL) {
1416   unsigned Reg = MRI.createVirtualRegister(RC);
1417   if (RC == &Hexagon::IntRegsRegClass) {
1418     BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), Reg)
1419         .addImm(int32_t(C));
1420     return Reg;
1421   }
1422
1423   if (RC == &Hexagon::DoubleRegsRegClass) {
1424     if (isInt<8>(C)) {
1425       BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrpi), Reg)
1426           .addImm(C);
1427       return Reg;
1428     }
1429
1430     unsigned Lo = Lo_32(C), Hi = Hi_32(C);
1431     if (isInt<8>(Lo) || isInt<8>(Hi)) {
1432       unsigned Opc = isInt<8>(Lo) ? Hexagon::A2_combineii
1433                                   : Hexagon::A4_combineii;
1434       BuildMI(B, At, DL, HII.get(Opc), Reg)
1435           .addImm(int32_t(Hi))
1436           .addImm(int32_t(Lo));
1437       return Reg;
1438     }
1439
1440     BuildMI(B, At, DL, HII.get(Hexagon::CONST64), Reg)
1441         .addImm(C);
1442     return Reg;
1443   }
1444
1445   if (RC == &Hexagon::PredRegsRegClass) {
1446     unsigned Opc;
1447     if (C == 0)
1448       Opc = Hexagon::PS_false;
1449     else if ((C & 0xFF) == 0xFF)
1450       Opc = Hexagon::PS_true;
1451     else
1452       return 0;
1453     BuildMI(B, At, DL, HII.get(Opc), Reg);
1454     return Reg;
1455   }
1456
1457   return 0;
1458 }
1459
1460 bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1461   if (!BT.reached(&B))
1462     return false;
1463   bool Changed = false;
1464   RegisterSet Defs;
1465
1466   for (auto I = B.begin(), E = B.end(); I != E; ++I) {
1467     if (isTfrConst(*I))
1468       continue;
1469     Defs.clear();
1470     HBS::getInstrDefs(*I, Defs);
1471     if (Defs.count() != 1)
1472       continue;
1473     unsigned DR = Defs.find_first();
1474     if (!TargetRegisterInfo::isVirtualRegister(DR))
1475       continue;
1476     uint64_t U;
1477     const BitTracker::RegisterCell &DRC = BT.lookup(DR);
1478     if (HBS::getConst(DRC, 0, DRC.width(), U)) {
1479       int64_t C = U;
1480       DebugLoc DL = I->getDebugLoc();
1481       auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1482       unsigned ImmReg = genTfrConst(MRI.getRegClass(DR), C, B, At, DL);
1483       if (ImmReg) {
1484         HBS::replaceReg(DR, ImmReg, MRI);
1485         BT.put(ImmReg, DRC);
1486         Changed = true;
1487       }
1488     }
1489   }
1490   return Changed;
1491 }
1492
1493 namespace {
1494
1495 // Identify pairs of available registers which hold identical values.
1496 // In such cases, only one of them needs to be calculated, the other one
1497 // will be defined as a copy of the first.
1498   class CopyGeneration : public Transformation {
1499   public:
1500     CopyGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1501         const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1502       : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1503
1504     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1505
1506   private:
1507     bool findMatch(const BitTracker::RegisterRef &Inp,
1508         BitTracker::RegisterRef &Out, const RegisterSet &AVs);
1509
1510     const HexagonInstrInfo &HII;
1511     const HexagonRegisterInfo &HRI;
1512     MachineRegisterInfo &MRI;
1513     BitTracker &BT;
1514     RegisterSet Forbidden;
1515   };
1516
1517 // Eliminate register copies RD = RS, by replacing the uses of RD with
1518 // with uses of RS.
1519   class CopyPropagation : public Transformation {
1520   public:
1521     CopyPropagation(const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1522         : Transformation(false), HRI(hri), MRI(mri) {}
1523
1524     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1525
1526     static bool isCopyReg(unsigned Opc, bool NoConv);
1527
1528   private:
1529     bool propagateRegCopy(MachineInstr &MI);
1530
1531     const HexagonRegisterInfo &HRI;
1532     MachineRegisterInfo &MRI;
1533   };
1534
1535 } // end anonymous namespace
1536
1537 /// Check if there is a register in AVs that is identical to Inp. If so,
1538 /// set Out to the found register. The output may be a pair Reg:Sub.
1539 bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp,
1540       BitTracker::RegisterRef &Out, const RegisterSet &AVs) {
1541   if (!BT.has(Inp.Reg))
1542     return false;
1543   const BitTracker::RegisterCell &InpRC = BT.lookup(Inp.Reg);
1544   auto *FRC = HBS::getFinalVRegClass(Inp, MRI);
1545   unsigned B, W;
1546   if (!HBS::getSubregMask(Inp, B, W, MRI))
1547     return false;
1548
1549   for (unsigned R = AVs.find_first(); R; R = AVs.find_next(R)) {
1550     if (!BT.has(R) || Forbidden[R])
1551       continue;
1552     const BitTracker::RegisterCell &RC = BT.lookup(R);
1553     unsigned RW = RC.width();
1554     if (W == RW) {
1555       if (FRC != MRI.getRegClass(R))
1556         continue;
1557       if (!HBS::isTransparentCopy(R, Inp, MRI))
1558         continue;
1559       if (!HBS::isEqual(InpRC, B, RC, 0, W))
1560         continue;
1561       Out.Reg = R;
1562       Out.Sub = 0;
1563       return true;
1564     }
1565     // Check if there is a super-register, whose part (with a subregister)
1566     // is equal to the input.
1567     // Only do double registers for now.
1568     if (W*2 != RW)
1569       continue;
1570     if (MRI.getRegClass(R) != &Hexagon::DoubleRegsRegClass)
1571       continue;
1572
1573     if (HBS::isEqual(InpRC, B, RC, 0, W))
1574       Out.Sub = Hexagon::isub_lo;
1575     else if (HBS::isEqual(InpRC, B, RC, W, W))
1576       Out.Sub = Hexagon::isub_hi;
1577     else
1578       continue;
1579     Out.Reg = R;
1580     if (HBS::isTransparentCopy(Out, Inp, MRI))
1581       return true;
1582   }
1583   return false;
1584 }
1585
1586 bool CopyGeneration::processBlock(MachineBasicBlock &B,
1587       const RegisterSet &AVs) {
1588   if (!BT.reached(&B))
1589     return false;
1590   RegisterSet AVB(AVs);
1591   bool Changed = false;
1592   RegisterSet Defs;
1593
1594   for (auto I = B.begin(), E = B.end(), NextI = I; I != E;
1595        ++I, AVB.insert(Defs)) {
1596     NextI = std::next(I);
1597     Defs.clear();
1598     HBS::getInstrDefs(*I, Defs);
1599
1600     unsigned Opc = I->getOpcode();
1601     if (CopyPropagation::isCopyReg(Opc, false) ||
1602         ConstGeneration::isTfrConst(*I))
1603       continue;
1604
1605     DebugLoc DL = I->getDebugLoc();
1606     auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1607
1608     for (unsigned R = Defs.find_first(); R; R = Defs.find_next(R)) {
1609       BitTracker::RegisterRef MR;
1610       auto *FRC = HBS::getFinalVRegClass(R, MRI);
1611
1612       if (findMatch(R, MR, AVB)) {
1613         unsigned NewR = MRI.createVirtualRegister(FRC);
1614         BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1615           .addReg(MR.Reg, 0, MR.Sub);
1616         BT.put(BitTracker::RegisterRef(NewR), BT.get(MR));
1617         HBS::replaceReg(R, NewR, MRI);
1618         Forbidden.insert(R);
1619         continue;
1620       }
1621
1622       if (FRC == &Hexagon::DoubleRegsRegClass ||
1623           FRC == &Hexagon::HvxWRRegClass) {
1624         // Try to generate REG_SEQUENCE.
1625         unsigned SubLo = HRI.getHexagonSubRegIndex(*FRC, Hexagon::ps_sub_lo);
1626         unsigned SubHi = HRI.getHexagonSubRegIndex(*FRC, Hexagon::ps_sub_hi);
1627         BitTracker::RegisterRef TL = { R, SubLo };
1628         BitTracker::RegisterRef TH = { R, SubHi };
1629         BitTracker::RegisterRef ML, MH;
1630         if (findMatch(TL, ML, AVB) && findMatch(TH, MH, AVB)) {
1631           auto *FRC = HBS::getFinalVRegClass(R, MRI);
1632           unsigned NewR = MRI.createVirtualRegister(FRC);
1633           BuildMI(B, At, DL, HII.get(TargetOpcode::REG_SEQUENCE), NewR)
1634             .addReg(ML.Reg, 0, ML.Sub)
1635             .addImm(SubLo)
1636             .addReg(MH.Reg, 0, MH.Sub)
1637             .addImm(SubHi);
1638           BT.put(BitTracker::RegisterRef(NewR), BT.get(R));
1639           HBS::replaceReg(R, NewR, MRI);
1640           Forbidden.insert(R);
1641         }
1642       }
1643     }
1644   }
1645
1646   return Changed;
1647 }
1648
1649 bool CopyPropagation::isCopyReg(unsigned Opc, bool NoConv) {
1650   switch (Opc) {
1651     case TargetOpcode::COPY:
1652     case TargetOpcode::REG_SEQUENCE:
1653     case Hexagon::A4_combineir:
1654     case Hexagon::A4_combineri:
1655       return true;
1656     case Hexagon::A2_tfr:
1657     case Hexagon::A2_tfrp:
1658     case Hexagon::A2_combinew:
1659     case Hexagon::V6_vcombine:
1660       return NoConv;
1661     default:
1662       break;
1663   }
1664   return false;
1665 }
1666
1667 bool CopyPropagation::propagateRegCopy(MachineInstr &MI) {
1668   bool Changed = false;
1669   unsigned Opc = MI.getOpcode();
1670   BitTracker::RegisterRef RD = MI.getOperand(0);
1671   assert(MI.getOperand(0).getSubReg() == 0);
1672
1673   switch (Opc) {
1674     case TargetOpcode::COPY:
1675     case Hexagon::A2_tfr:
1676     case Hexagon::A2_tfrp: {
1677       BitTracker::RegisterRef RS = MI.getOperand(1);
1678       if (!HBS::isTransparentCopy(RD, RS, MRI))
1679         break;
1680       if (RS.Sub != 0)
1681         Changed = HBS::replaceRegWithSub(RD.Reg, RS.Reg, RS.Sub, MRI);
1682       else
1683         Changed = HBS::replaceReg(RD.Reg, RS.Reg, MRI);
1684       break;
1685     }
1686     case TargetOpcode::REG_SEQUENCE: {
1687       BitTracker::RegisterRef SL, SH;
1688       if (HBS::parseRegSequence(MI, SL, SH, MRI)) {
1689         const TargetRegisterClass &RC = *MRI.getRegClass(RD.Reg);
1690         unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo);
1691         unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi);
1692         Changed  = HBS::replaceSubWithSub(RD.Reg, SubLo, SL.Reg, SL.Sub, MRI);
1693         Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, SH.Reg, SH.Sub, MRI);
1694       }
1695       break;
1696     }
1697     case Hexagon::A2_combinew:
1698     case Hexagon::V6_vcombine: {
1699       const TargetRegisterClass &RC = *MRI.getRegClass(RD.Reg);
1700       unsigned SubLo = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_lo);
1701       unsigned SubHi = HRI.getHexagonSubRegIndex(RC, Hexagon::ps_sub_hi);
1702       BitTracker::RegisterRef RH = MI.getOperand(1), RL = MI.getOperand(2);
1703       Changed  = HBS::replaceSubWithSub(RD.Reg, SubLo, RL.Reg, RL.Sub, MRI);
1704       Changed |= HBS::replaceSubWithSub(RD.Reg, SubHi, RH.Reg, RH.Sub, MRI);
1705       break;
1706     }
1707     case Hexagon::A4_combineir:
1708     case Hexagon::A4_combineri: {
1709       unsigned SrcX = (Opc == Hexagon::A4_combineir) ? 2 : 1;
1710       unsigned Sub = (Opc == Hexagon::A4_combineir) ? Hexagon::isub_lo
1711                                                     : Hexagon::isub_hi;
1712       BitTracker::RegisterRef RS = MI.getOperand(SrcX);
1713       Changed = HBS::replaceSubWithSub(RD.Reg, Sub, RS.Reg, RS.Sub, MRI);
1714       break;
1715     }
1716   }
1717   return Changed;
1718 }
1719
1720 bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1721   std::vector<MachineInstr*> Instrs;
1722   for (auto I = B.rbegin(), E = B.rend(); I != E; ++I)
1723     Instrs.push_back(&*I);
1724
1725   bool Changed = false;
1726   for (auto I : Instrs) {
1727     unsigned Opc = I->getOpcode();
1728     if (!CopyPropagation::isCopyReg(Opc, true))
1729       continue;
1730     Changed |= propagateRegCopy(*I);
1731   }
1732
1733   return Changed;
1734 }
1735
1736 namespace {
1737
1738 // Recognize patterns that can be simplified and replace them with the
1739 // simpler forms.
1740 // This is by no means complete
1741   class BitSimplification : public Transformation {
1742   public:
1743     BitSimplification(BitTracker &bt, const MachineDominatorTree &mdt,
1744         const HexagonInstrInfo &hii, const HexagonRegisterInfo &hri,
1745         MachineRegisterInfo &mri, MachineFunction &mf)
1746       : Transformation(true), MDT(mdt), HII(hii), HRI(hri), MRI(mri),
1747         MF(mf), BT(bt) {}
1748
1749     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1750
1751   private:
1752     struct RegHalf : public BitTracker::RegisterRef {
1753       bool Low;  // Low/High halfword.
1754     };
1755
1756     bool matchHalf(unsigned SelfR, const BitTracker::RegisterCell &RC,
1757           unsigned B, RegHalf &RH);
1758     bool validateReg(BitTracker::RegisterRef R, unsigned Opc, unsigned OpNum);
1759
1760     bool matchPackhl(unsigned SelfR, const BitTracker::RegisterCell &RC,
1761           BitTracker::RegisterRef &Rs, BitTracker::RegisterRef &Rt);
1762     unsigned getCombineOpcode(bool HLow, bool LLow);
1763
1764     bool genStoreUpperHalf(MachineInstr *MI);
1765     bool genStoreImmediate(MachineInstr *MI);
1766     bool genPackhl(MachineInstr *MI, BitTracker::RegisterRef RD,
1767           const BitTracker::RegisterCell &RC);
1768     bool genExtractHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1769           const BitTracker::RegisterCell &RC);
1770     bool genCombineHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1771           const BitTracker::RegisterCell &RC);
1772     bool genExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1773           const BitTracker::RegisterCell &RC);
1774     bool genBitSplit(MachineInstr *MI, BitTracker::RegisterRef RD,
1775           const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1776     bool simplifyTstbit(MachineInstr *MI, BitTracker::RegisterRef RD,
1777           const BitTracker::RegisterCell &RC);
1778     bool simplifyExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1779           const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1780     bool simplifyRCmp0(MachineInstr *MI, BitTracker::RegisterRef RD);
1781
1782     // Cache of created instructions to avoid creating duplicates.
1783     // XXX Currently only used by genBitSplit.
1784     std::vector<MachineInstr*> NewMIs;
1785
1786     const MachineDominatorTree &MDT;
1787     const HexagonInstrInfo &HII;
1788     const HexagonRegisterInfo &HRI;
1789     MachineRegisterInfo &MRI;
1790     MachineFunction &MF;
1791     BitTracker &BT;
1792   };
1793
1794 } // end anonymous namespace
1795
1796 // Check if the bits [B..B+16) in register cell RC form a valid halfword,
1797 // i.e. [0..16), [16..32), etc. of some register. If so, return true and
1798 // set the information about the found register in RH.
1799 bool BitSimplification::matchHalf(unsigned SelfR,
1800       const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) {
1801   // XXX This could be searching in the set of available registers, in case
1802   // the match is not exact.
1803
1804   // Match 16-bit chunks, where the RC[B..B+15] references exactly one
1805   // register and all the bits B..B+15 match between RC and the register.
1806   // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... },
1807   // and RC = { [0]:0 [1-15]:v1[1-15]... }.
1808   bool Low = false;
1809   unsigned I = B;
1810   while (I < B+16 && RC[I].num())
1811     I++;
1812   if (I == B+16)
1813     return false;
1814
1815   unsigned Reg = RC[I].RefI.Reg;
1816   unsigned P = RC[I].RefI.Pos;    // The RefI.Pos will be advanced by I-B.
1817   if (P < I-B)
1818     return false;
1819   unsigned Pos = P - (I-B);
1820
1821   if (Reg == 0 || Reg == SelfR)    // Don't match "self".
1822     return false;
1823   if (!TargetRegisterInfo::isVirtualRegister(Reg))
1824     return false;
1825   if (!BT.has(Reg))
1826     return false;
1827
1828   const BitTracker::RegisterCell &SC = BT.lookup(Reg);
1829   if (Pos+16 > SC.width())
1830     return false;
1831
1832   for (unsigned i = 0; i < 16; ++i) {
1833     const BitTracker::BitValue &RV = RC[i+B];
1834     if (RV.Type == BitTracker::BitValue::Ref) {
1835       if (RV.RefI.Reg != Reg)
1836         return false;
1837       if (RV.RefI.Pos != i+Pos)
1838         return false;
1839       continue;
1840     }
1841     if (RC[i+B] != SC[i+Pos])
1842       return false;
1843   }
1844
1845   unsigned Sub = 0;
1846   switch (Pos) {
1847     case 0:
1848       Sub = Hexagon::isub_lo;
1849       Low = true;
1850       break;
1851     case 16:
1852       Sub = Hexagon::isub_lo;
1853       Low = false;
1854       break;
1855     case 32:
1856       Sub = Hexagon::isub_hi;
1857       Low = true;
1858       break;
1859     case 48:
1860       Sub = Hexagon::isub_hi;
1861       Low = false;
1862       break;
1863     default:
1864       return false;
1865   }
1866
1867   RH.Reg = Reg;
1868   RH.Sub = Sub;
1869   RH.Low = Low;
1870   // If the subregister is not valid with the register, set it to 0.
1871   if (!HBS::getFinalVRegClass(RH, MRI))
1872     RH.Sub = 0;
1873
1874   return true;
1875 }
1876
1877 bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc,
1878       unsigned OpNum) {
1879   auto *OpRC = HII.getRegClass(HII.get(Opc), OpNum, &HRI, MF);
1880   auto *RRC = HBS::getFinalVRegClass(R, MRI);
1881   return OpRC->hasSubClassEq(RRC);
1882 }
1883
1884 // Check if RC matches the pattern of a S2_packhl. If so, return true and
1885 // set the inputs Rs and Rt.
1886 bool BitSimplification::matchPackhl(unsigned SelfR,
1887       const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs,
1888       BitTracker::RegisterRef &Rt) {
1889   RegHalf L1, H1, L2, H2;
1890
1891   if (!matchHalf(SelfR, RC, 0, L2)  || !matchHalf(SelfR, RC, 16, L1))
1892     return false;
1893   if (!matchHalf(SelfR, RC, 32, H2) || !matchHalf(SelfR, RC, 48, H1))
1894     return false;
1895
1896   // Rs = H1.L1, Rt = H2.L2
1897   if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || H1.Low || !L1.Low)
1898     return false;
1899   if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low)
1900     return false;
1901
1902   Rs = H1;
1903   Rt = H2;
1904   return true;
1905 }
1906
1907 unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) {
1908   return HLow ? LLow ? Hexagon::A2_combine_ll
1909                      : Hexagon::A2_combine_lh
1910               : LLow ? Hexagon::A2_combine_hl
1911                      : Hexagon::A2_combine_hh;
1912 }
1913
1914 // If MI stores the upper halfword of a register (potentially obtained via
1915 // shifts or extracts), replace it with a storerf instruction. This could
1916 // cause the "extraction" code to become dead.
1917 bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) {
1918   unsigned Opc = MI->getOpcode();
1919   if (Opc != Hexagon::S2_storerh_io)
1920     return false;
1921
1922   MachineOperand &ValOp = MI->getOperand(2);
1923   BitTracker::RegisterRef RS = ValOp;
1924   if (!BT.has(RS.Reg))
1925     return false;
1926   const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1927   RegHalf H;
1928   if (!matchHalf(0, RC, 0, H))
1929     return false;
1930   if (H.Low)
1931     return false;
1932   MI->setDesc(HII.get(Hexagon::S2_storerf_io));
1933   ValOp.setReg(H.Reg);
1934   ValOp.setSubReg(H.Sub);
1935   return true;
1936 }
1937
1938 // If MI stores a value known at compile-time, and the value is within a range
1939 // that avoids using constant-extenders, replace it with a store-immediate.
1940 bool BitSimplification::genStoreImmediate(MachineInstr *MI) {
1941   unsigned Opc = MI->getOpcode();
1942   unsigned Align = 0;
1943   switch (Opc) {
1944     case Hexagon::S2_storeri_io:
1945       Align++;
1946       LLVM_FALLTHROUGH;
1947     case Hexagon::S2_storerh_io:
1948       Align++;
1949       LLVM_FALLTHROUGH;
1950     case Hexagon::S2_storerb_io:
1951       break;
1952     default:
1953       return false;
1954   }
1955
1956   // Avoid stores to frame-indices (due to an unknown offset).
1957   if (!MI->getOperand(0).isReg())
1958     return false;
1959   MachineOperand &OffOp = MI->getOperand(1);
1960   if (!OffOp.isImm())
1961     return false;
1962
1963   int64_t Off = OffOp.getImm();
1964   // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x).
1965   if (!isUIntN(6+Align, Off) || (Off & ((1<<Align)-1)))
1966     return false;
1967   // Source register:
1968   BitTracker::RegisterRef RS = MI->getOperand(2);
1969   if (!BT.has(RS.Reg))
1970     return false;
1971   const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1972   uint64_t U;
1973   if (!HBS::getConst(RC, 0, RC.width(), U))
1974     return false;
1975
1976   // Only consider 8-bit values to avoid constant-extenders.
1977   int V;
1978   switch (Opc) {
1979     case Hexagon::S2_storerb_io:
1980       V = int8_t(U);
1981       break;
1982     case Hexagon::S2_storerh_io:
1983       V = int16_t(U);
1984       break;
1985     case Hexagon::S2_storeri_io:
1986       V = int32_t(U);
1987       break;
1988     default:
1989       // Opc is already checked above to be one of the three store instructions.
1990       // This silences a -Wuninitialized false positive on GCC 5.4.
1991       llvm_unreachable("Unexpected store opcode");
1992   }
1993   if (!isInt<8>(V))
1994     return false;
1995
1996   MI->RemoveOperand(2);
1997   switch (Opc) {
1998     case Hexagon::S2_storerb_io:
1999       MI->setDesc(HII.get(Hexagon::S4_storeirb_io));
2000       break;
2001     case Hexagon::S2_storerh_io:
2002       MI->setDesc(HII.get(Hexagon::S4_storeirh_io));
2003       break;
2004     case Hexagon::S2_storeri_io:
2005       MI->setDesc(HII.get(Hexagon::S4_storeiri_io));
2006       break;
2007   }
2008   MI->addOperand(MachineOperand::CreateImm(V));
2009   return true;
2010 }
2011
2012 // If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
2013 // last instruction in a sequence that results in something equivalent to
2014 // the pack-halfwords. The intent is to cause the entire sequence to become
2015 // dead.
2016 bool BitSimplification::genPackhl(MachineInstr *MI,
2017       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2018   unsigned Opc = MI->getOpcode();
2019   if (Opc == Hexagon::S2_packhl)
2020     return false;
2021   BitTracker::RegisterRef Rs, Rt;
2022   if (!matchPackhl(RD.Reg, RC, Rs, Rt))
2023     return false;
2024   if (!validateReg(Rs, Hexagon::S2_packhl, 1) ||
2025       !validateReg(Rt, Hexagon::S2_packhl, 2))
2026     return false;
2027
2028   MachineBasicBlock &B = *MI->getParent();
2029   unsigned NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2030   DebugLoc DL = MI->getDebugLoc();
2031   auto At = MI->isPHI() ? B.getFirstNonPHI()
2032                         : MachineBasicBlock::iterator(MI);
2033   BuildMI(B, At, DL, HII.get(Hexagon::S2_packhl), NewR)
2034       .addReg(Rs.Reg, 0, Rs.Sub)
2035       .addReg(Rt.Reg, 0, Rt.Sub);
2036   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2037   BT.put(BitTracker::RegisterRef(NewR), RC);
2038   return true;
2039 }
2040
2041 // If MI produces halfword of the input in the low half of the output,
2042 // replace it with zero-extend or extractu.
2043 bool BitSimplification::genExtractHalf(MachineInstr *MI,
2044       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2045   RegHalf L;
2046   // Check for halfword in low 16 bits, zeros elsewhere.
2047   if (!matchHalf(RD.Reg, RC, 0, L) || !HBS::isZero(RC, 16, 16))
2048     return false;
2049
2050   unsigned Opc = MI->getOpcode();
2051   MachineBasicBlock &B = *MI->getParent();
2052   DebugLoc DL = MI->getDebugLoc();
2053
2054   // Prefer zxth, since zxth can go in any slot, while extractu only in
2055   // slots 2 and 3.
2056   unsigned NewR = 0;
2057   auto At = MI->isPHI() ? B.getFirstNonPHI()
2058                         : MachineBasicBlock::iterator(MI);
2059   if (L.Low && Opc != Hexagon::A2_zxth) {
2060     if (validateReg(L, Hexagon::A2_zxth, 1)) {
2061       NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2062       BuildMI(B, At, DL, HII.get(Hexagon::A2_zxth), NewR)
2063           .addReg(L.Reg, 0, L.Sub);
2064     }
2065   } else if (!L.Low && Opc != Hexagon::S2_lsr_i_r) {
2066     if (validateReg(L, Hexagon::S2_lsr_i_r, 1)) {
2067       NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2068       BuildMI(B, MI, DL, HII.get(Hexagon::S2_lsr_i_r), NewR)
2069           .addReg(L.Reg, 0, L.Sub)
2070           .addImm(16);
2071     }
2072   }
2073   if (NewR == 0)
2074     return false;
2075   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2076   BT.put(BitTracker::RegisterRef(NewR), RC);
2077   return true;
2078 }
2079
2080 // If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
2081 // combine.
2082 bool BitSimplification::genCombineHalf(MachineInstr *MI,
2083       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2084   RegHalf L, H;
2085   // Check for combine h/l
2086   if (!matchHalf(RD.Reg, RC, 0, L) || !matchHalf(RD.Reg, RC, 16, H))
2087     return false;
2088   // Do nothing if this is just a reg copy.
2089   if (L.Reg == H.Reg && L.Sub == H.Sub && !H.Low && L.Low)
2090     return false;
2091
2092   unsigned Opc = MI->getOpcode();
2093   unsigned COpc = getCombineOpcode(H.Low, L.Low);
2094   if (COpc == Opc)
2095     return false;
2096   if (!validateReg(H, COpc, 1) || !validateReg(L, COpc, 2))
2097     return false;
2098
2099   MachineBasicBlock &B = *MI->getParent();
2100   DebugLoc DL = MI->getDebugLoc();
2101   unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2102   auto At = MI->isPHI() ? B.getFirstNonPHI()
2103                         : MachineBasicBlock::iterator(MI);
2104   BuildMI(B, At, DL, HII.get(COpc), NewR)
2105       .addReg(H.Reg, 0, H.Sub)
2106       .addReg(L.Reg, 0, L.Sub);
2107   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2108   BT.put(BitTracker::RegisterRef(NewR), RC);
2109   return true;
2110 }
2111
2112 // If MI resets high bits of a register and keeps the lower ones, replace it
2113 // with zero-extend byte/half, and-immediate, or extractu, as appropriate.
2114 bool BitSimplification::genExtractLow(MachineInstr *MI,
2115       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2116   unsigned Opc = MI->getOpcode();
2117   switch (Opc) {
2118     case Hexagon::A2_zxtb:
2119     case Hexagon::A2_zxth:
2120     case Hexagon::S2_extractu:
2121       return false;
2122   }
2123   if (Opc == Hexagon::A2_andir && MI->getOperand(2).isImm()) {
2124     int32_t Imm = MI->getOperand(2).getImm();
2125     if (isInt<10>(Imm))
2126       return false;
2127   }
2128
2129   if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
2130     return false;
2131   unsigned W = RC.width();
2132   while (W > 0 && RC[W-1].is(0))
2133     W--;
2134   if (W == 0 || W == RC.width())
2135     return false;
2136   unsigned NewOpc = (W == 8)  ? Hexagon::A2_zxtb
2137                   : (W == 16) ? Hexagon::A2_zxth
2138                   : (W < 10)  ? Hexagon::A2_andir
2139                   : Hexagon::S2_extractu;
2140   MachineBasicBlock &B = *MI->getParent();
2141   DebugLoc DL = MI->getDebugLoc();
2142
2143   for (auto &Op : MI->uses()) {
2144     if (!Op.isReg())
2145       continue;
2146     BitTracker::RegisterRef RS = Op;
2147     if (!BT.has(RS.Reg))
2148       continue;
2149     const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2150     unsigned BN, BW;
2151     if (!HBS::getSubregMask(RS, BN, BW, MRI))
2152       continue;
2153     if (BW < W || !HBS::isEqual(RC, 0, SC, BN, W))
2154       continue;
2155     if (!validateReg(RS, NewOpc, 1))
2156       continue;
2157
2158     unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2159     auto At = MI->isPHI() ? B.getFirstNonPHI()
2160                           : MachineBasicBlock::iterator(MI);
2161     auto MIB = BuildMI(B, At, DL, HII.get(NewOpc), NewR)
2162                   .addReg(RS.Reg, 0, RS.Sub);
2163     if (NewOpc == Hexagon::A2_andir)
2164       MIB.addImm((1 << W) - 1);
2165     else if (NewOpc == Hexagon::S2_extractu)
2166       MIB.addImm(W).addImm(0);
2167     HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2168     BT.put(BitTracker::RegisterRef(NewR), RC);
2169     return true;
2170   }
2171   return false;
2172 }
2173
2174 bool BitSimplification::genBitSplit(MachineInstr *MI,
2175       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2176       const RegisterSet &AVs) {
2177   if (!GenBitSplit)
2178     return false;
2179   if (MaxBitSplit.getNumOccurrences()) {
2180     if (CountBitSplit >= MaxBitSplit)
2181       return false;
2182   }
2183
2184   unsigned Opc = MI->getOpcode();
2185   switch (Opc) {
2186     case Hexagon::A4_bitsplit:
2187     case Hexagon::A4_bitspliti:
2188       return false;
2189   }
2190
2191   unsigned W = RC.width();
2192   if (W != 32)
2193     return false;
2194
2195   auto ctlz = [] (const BitTracker::RegisterCell &C) -> unsigned {
2196     unsigned Z = C.width();
2197     while (Z > 0 && C[Z-1].is(0))
2198       --Z;
2199     return C.width() - Z;
2200   };
2201
2202   // Count the number of leading zeros in the target RC.
2203   unsigned Z = ctlz(RC);
2204   if (Z == 0 || Z == W)
2205     return false;
2206
2207   // A simplistic analysis: assume the source register (the one being split)
2208   // is fully unknown, and that all its bits are self-references.
2209   const BitTracker::BitValue &B0 = RC[0];
2210   if (B0.Type != BitTracker::BitValue::Ref)
2211     return false;
2212
2213   unsigned SrcR = B0.RefI.Reg;
2214   unsigned SrcSR = 0;
2215   unsigned Pos = B0.RefI.Pos;
2216
2217   // All the non-zero bits should be consecutive bits from the same register.
2218   for (unsigned i = 1; i < W-Z; ++i) {
2219     const BitTracker::BitValue &V = RC[i];
2220     if (V.Type != BitTracker::BitValue::Ref)
2221       return false;
2222     if (V.RefI.Reg != SrcR || V.RefI.Pos != Pos+i)
2223       return false;
2224   }
2225
2226   // Now, find the other bitfield among AVs.
2227   for (unsigned S = AVs.find_first(); S; S = AVs.find_next(S)) {
2228     // The number of leading zeros here should be the number of trailing
2229     // non-zeros in RC.
2230     unsigned SRC = MRI.getRegClass(S)->getID();
2231     if (SRC != Hexagon::IntRegsRegClassID &&
2232         SRC != Hexagon::DoubleRegsRegClassID)
2233       continue;
2234     if (!BT.has(S))
2235       continue;
2236     const BitTracker::RegisterCell &SC = BT.lookup(S);
2237     if (SC.width() != W || ctlz(SC) != W-Z)
2238       continue;
2239     // The Z lower bits should now match SrcR.
2240     const BitTracker::BitValue &S0 = SC[0];
2241     if (S0.Type != BitTracker::BitValue::Ref || S0.RefI.Reg != SrcR)
2242       continue;
2243     unsigned P = S0.RefI.Pos;
2244
2245     if (Pos <= P && (Pos + W-Z) != P)
2246       continue;
2247     if (P < Pos && (P + Z) != Pos)
2248       continue;
2249     // The starting bitfield position must be at a subregister boundary.
2250     if (std::min(P, Pos) != 0 && std::min(P, Pos) != 32)
2251       continue;
2252
2253     unsigned I;
2254     for (I = 1; I < Z; ++I) {
2255       const BitTracker::BitValue &V = SC[I];
2256       if (V.Type != BitTracker::BitValue::Ref)
2257         break;
2258       if (V.RefI.Reg != SrcR || V.RefI.Pos != P+I)
2259         break;
2260     }
2261     if (I != Z)
2262       continue;
2263
2264     // Generate bitsplit where S is defined.
2265     if (MaxBitSplit.getNumOccurrences())
2266       CountBitSplit++;
2267     MachineInstr *DefS = MRI.getVRegDef(S);
2268     assert(DefS != nullptr);
2269     DebugLoc DL = DefS->getDebugLoc();
2270     MachineBasicBlock &B = *DefS->getParent();
2271     auto At = DefS->isPHI() ? B.getFirstNonPHI()
2272                             : MachineBasicBlock::iterator(DefS);
2273     if (MRI.getRegClass(SrcR)->getID() == Hexagon::DoubleRegsRegClassID)
2274       SrcSR = (std::min(Pos, P) == 32) ? Hexagon::isub_hi : Hexagon::isub_lo;
2275     if (!validateReg({SrcR,SrcSR}, Hexagon::A4_bitspliti, 1))
2276       continue;
2277     unsigned ImmOp = Pos <= P ? W-Z : Z;
2278
2279     // Find an existing bitsplit instruction if one already exists.
2280     unsigned NewR = 0;
2281     for (MachineInstr *In : NewMIs) {
2282       if (In->getOpcode() != Hexagon::A4_bitspliti)
2283         continue;
2284       MachineOperand &Op1 = In->getOperand(1);
2285       if (Op1.getReg() != SrcR || Op1.getSubReg() != SrcSR)
2286         continue;
2287       if (In->getOperand(2).getImm() != ImmOp)
2288         continue;
2289       // Check if the target register is available here.
2290       MachineOperand &Op0 = In->getOperand(0);
2291       MachineInstr *DefI = MRI.getVRegDef(Op0.getReg());
2292       assert(DefI != nullptr);
2293       if (!MDT.dominates(DefI, &*At))
2294         continue;
2295
2296       // Found one that can be reused.
2297       assert(Op0.getSubReg() == 0);
2298       NewR = Op0.getReg();
2299       break;
2300     }
2301     if (!NewR) {
2302       NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
2303       auto NewBS = BuildMI(B, At, DL, HII.get(Hexagon::A4_bitspliti), NewR)
2304                       .addReg(SrcR, 0, SrcSR)
2305                       .addImm(ImmOp);
2306       NewMIs.push_back(NewBS);
2307     }
2308     if (Pos <= P) {
2309       HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_lo, MRI);
2310       HBS::replaceRegWithSub(S,      NewR, Hexagon::isub_hi, MRI);
2311     } else {
2312       HBS::replaceRegWithSub(S,      NewR, Hexagon::isub_lo, MRI);
2313       HBS::replaceRegWithSub(RD.Reg, NewR, Hexagon::isub_hi, MRI);
2314     }
2315     return true;
2316   }
2317
2318   return false;
2319 }
2320
2321 // Check for tstbit simplification opportunity, where the bit being checked
2322 // can be tracked back to another register. For example:
2323 //   %2 = S2_lsr_i_r  %1, 5
2324 //   %3 = S2_tstbit_i %2, 0
2325 // =>
2326 //   %3 = S2_tstbit_i %1, 5
2327 bool BitSimplification::simplifyTstbit(MachineInstr *MI,
2328       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2329   unsigned Opc = MI->getOpcode();
2330   if (Opc != Hexagon::S2_tstbit_i)
2331     return false;
2332
2333   unsigned BN = MI->getOperand(2).getImm();
2334   BitTracker::RegisterRef RS = MI->getOperand(1);
2335   unsigned F, W;
2336   DebugLoc DL = MI->getDebugLoc();
2337   if (!BT.has(RS.Reg) || !HBS::getSubregMask(RS, F, W, MRI))
2338     return false;
2339   MachineBasicBlock &B = *MI->getParent();
2340   auto At = MI->isPHI() ? B.getFirstNonPHI()
2341                         : MachineBasicBlock::iterator(MI);
2342
2343   const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2344   const BitTracker::BitValue &V = SC[F+BN];
2345   if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) {
2346     const TargetRegisterClass *TC = MRI.getRegClass(V.RefI.Reg);
2347     // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is
2348     // a double register, need to use a subregister and adjust bit
2349     // number.
2350     unsigned P = std::numeric_limits<unsigned>::max();
2351     BitTracker::RegisterRef RR(V.RefI.Reg, 0);
2352     if (TC == &Hexagon::DoubleRegsRegClass) {
2353       P = V.RefI.Pos;
2354       RR.Sub = Hexagon::isub_lo;
2355       if (P >= 32) {
2356         P -= 32;
2357         RR.Sub = Hexagon::isub_hi;
2358       }
2359     } else if (TC == &Hexagon::IntRegsRegClass) {
2360       P = V.RefI.Pos;
2361     }
2362     if (P != std::numeric_limits<unsigned>::max()) {
2363       unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2364       BuildMI(B, At, DL, HII.get(Hexagon::S2_tstbit_i), NewR)
2365           .addReg(RR.Reg, 0, RR.Sub)
2366           .addImm(P);
2367       HBS::replaceReg(RD.Reg, NewR, MRI);
2368       BT.put(NewR, RC);
2369       return true;
2370     }
2371   } else if (V.is(0) || V.is(1)) {
2372     unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2373     unsigned NewOpc = V.is(0) ? Hexagon::PS_false : Hexagon::PS_true;
2374     BuildMI(B, At, DL, HII.get(NewOpc), NewR);
2375     HBS::replaceReg(RD.Reg, NewR, MRI);
2376     return true;
2377   }
2378
2379   return false;
2380 }
2381
2382 // Detect whether RD is a bitfield extract (sign- or zero-extended) of
2383 // some register from the AVs set. Create a new corresponding instruction
2384 // at the location of MI. The intent is to recognize situations where
2385 // a sequence of instructions performs an operation that is equivalent to
2386 // an extract operation, such as a shift left followed by a shift right.
2387 bool BitSimplification::simplifyExtractLow(MachineInstr *MI,
2388       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2389       const RegisterSet &AVs) {
2390   if (!GenExtract)
2391     return false;
2392   if (MaxExtract.getNumOccurrences()) {
2393     if (CountExtract >= MaxExtract)
2394       return false;
2395     CountExtract++;
2396   }
2397
2398   unsigned W = RC.width();
2399   unsigned RW = W;
2400   unsigned Len;
2401   bool Signed;
2402
2403   // The code is mostly class-independent, except for the part that generates
2404   // the extract instruction, and establishes the source register (in case it
2405   // needs to use a subregister).
2406   const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2407   if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2408     return false;
2409   assert(RD.Sub == 0);
2410
2411   // Observation:
2412   // If the cell has a form of 00..0xx..x with k zeros and n remaining
2413   // bits, this could be an extractu of the n bits, but it could also be
2414   // an extractu of a longer field which happens to have 0s in the top
2415   // bit positions.
2416   // The same logic applies to sign-extended fields.
2417   //
2418   // Do not check for the extended extracts, since it would expand the
2419   // search space quite a bit. The search may be expensive as it is.
2420
2421   const BitTracker::BitValue &TopV = RC[W-1];
2422
2423   // Eliminate candidates that have self-referential bits, since they
2424   // cannot be extracts from other registers. Also, skip registers that
2425   // have compile-time constant values.
2426   bool IsConst = true;
2427   for (unsigned I = 0; I != W; ++I) {
2428     const BitTracker::BitValue &V = RC[I];
2429     if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == RD.Reg)
2430       return false;
2431     IsConst = IsConst && (V.is(0) || V.is(1));
2432   }
2433   if (IsConst)
2434     return false;
2435
2436   if (TopV.is(0) || TopV.is(1)) {
2437     bool S = TopV.is(1);
2438     for (--W; W > 0 && RC[W-1].is(S); --W)
2439       ;
2440     Len = W;
2441     Signed = S;
2442     // The sign bit must be a part of the field being extended.
2443     if (Signed)
2444       ++Len;
2445   } else {
2446     // This could still be a sign-extended extract.
2447     assert(TopV.Type == BitTracker::BitValue::Ref);
2448     if (TopV.RefI.Reg == RD.Reg || TopV.RefI.Pos == W-1)
2449       return false;
2450     for (--W; W > 0 && RC[W-1] == TopV; --W)
2451       ;
2452     // The top bits of RC are copies of TopV. One occurrence of TopV will
2453     // be a part of the field.
2454     Len = W + 1;
2455     Signed = true;
2456   }
2457
2458   // This would be just a copy. It should be handled elsewhere.
2459   if (Len == RW)
2460     return false;
2461
2462   LLVM_DEBUG({
2463     dbgs() << __func__ << " on reg: " << printReg(RD.Reg, &HRI, RD.Sub)
2464            << ", MI: " << *MI;
2465     dbgs() << "Cell: " << RC << '\n';
2466     dbgs() << "Expected bitfield size: " << Len << " bits, "
2467            << (Signed ? "sign" : "zero") << "-extended\n";
2468   });
2469
2470   bool Changed = false;
2471
2472   for (unsigned R = AVs.find_first(); R != 0; R = AVs.find_next(R)) {
2473     if (!BT.has(R))
2474       continue;
2475     const BitTracker::RegisterCell &SC = BT.lookup(R);
2476     unsigned SW = SC.width();
2477
2478     // The source can be longer than the destination, as long as its size is
2479     // a multiple of the size of the destination. Also, we would need to be
2480     // able to refer to the subregister in the source that would be of the
2481     // same size as the destination, but only check the sizes here.
2482     if (SW < RW || (SW % RW) != 0)
2483       continue;
2484
2485     // The field can start at any offset in SC as long as it contains Len
2486     // bits and does not cross subregister boundary (if the source register
2487     // is longer than the destination).
2488     unsigned Off = 0;
2489     while (Off <= SW-Len) {
2490       unsigned OE = (Off+Len)/RW;
2491       if (OE != Off/RW) {
2492         // The assumption here is that if the source (R) is longer than the
2493         // destination, then the destination is a sequence of words of
2494         // size RW, and each such word in R can be accessed via a subregister.
2495         //
2496         // If the beginning and the end of the field cross the subregister
2497         // boundary, advance to the next subregister.
2498         Off = OE*RW;
2499         continue;
2500       }
2501       if (HBS::isEqual(RC, 0, SC, Off, Len))
2502         break;
2503       ++Off;
2504     }
2505
2506     if (Off > SW-Len)
2507       continue;
2508
2509     // Found match.
2510     unsigned ExtOpc = 0;
2511     if (Off == 0) {
2512       if (Len == 8)
2513         ExtOpc = Signed ? Hexagon::A2_sxtb : Hexagon::A2_zxtb;
2514       else if (Len == 16)
2515         ExtOpc = Signed ? Hexagon::A2_sxth : Hexagon::A2_zxth;
2516       else if (Len < 10 && !Signed)
2517         ExtOpc = Hexagon::A2_andir;
2518     }
2519     if (ExtOpc == 0) {
2520       ExtOpc =
2521           Signed ? (RW == 32 ? Hexagon::S4_extract  : Hexagon::S4_extractp)
2522                  : (RW == 32 ? Hexagon::S2_extractu : Hexagon::S2_extractup);
2523     }
2524     unsigned SR = 0;
2525     // This only recognizes isub_lo and isub_hi.
2526     if (RW != SW && RW*2 != SW)
2527       continue;
2528     if (RW != SW)
2529       SR = (Off/RW == 0) ? Hexagon::isub_lo : Hexagon::isub_hi;
2530     Off = Off % RW;
2531
2532     if (!validateReg({R,SR}, ExtOpc, 1))
2533       continue;
2534
2535     // Don't generate the same instruction as the one being optimized.
2536     if (MI->getOpcode() == ExtOpc) {
2537       // All possible ExtOpc's have the source in operand(1).
2538       const MachineOperand &SrcOp = MI->getOperand(1);
2539       if (SrcOp.getReg() == R)
2540         continue;
2541     }
2542
2543     DebugLoc DL = MI->getDebugLoc();
2544     MachineBasicBlock &B = *MI->getParent();
2545     unsigned NewR = MRI.createVirtualRegister(FRC);
2546     auto At = MI->isPHI() ? B.getFirstNonPHI()
2547                           : MachineBasicBlock::iterator(MI);
2548     auto MIB = BuildMI(B, At, DL, HII.get(ExtOpc), NewR)
2549                   .addReg(R, 0, SR);
2550     switch (ExtOpc) {
2551       case Hexagon::A2_sxtb:
2552       case Hexagon::A2_zxtb:
2553       case Hexagon::A2_sxth:
2554       case Hexagon::A2_zxth:
2555         break;
2556       case Hexagon::A2_andir:
2557         MIB.addImm((1u << Len) - 1);
2558         break;
2559       case Hexagon::S4_extract:
2560       case Hexagon::S2_extractu:
2561       case Hexagon::S4_extractp:
2562       case Hexagon::S2_extractup:
2563         MIB.addImm(Len)
2564            .addImm(Off);
2565         break;
2566       default:
2567         llvm_unreachable("Unexpected opcode");
2568     }
2569
2570     HBS::replaceReg(RD.Reg, NewR, MRI);
2571     BT.put(BitTracker::RegisterRef(NewR), RC);
2572     Changed = true;
2573     break;
2574   }
2575
2576   return Changed;
2577 }
2578
2579 bool BitSimplification::simplifyRCmp0(MachineInstr *MI,
2580       BitTracker::RegisterRef RD) {
2581   unsigned Opc = MI->getOpcode();
2582   if (Opc != Hexagon::A4_rcmpeqi && Opc != Hexagon::A4_rcmpneqi)
2583     return false;
2584   MachineOperand &CmpOp = MI->getOperand(2);
2585   if (!CmpOp.isImm() || CmpOp.getImm() != 0)
2586     return false;
2587
2588   const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2589   if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2590     return false;
2591   assert(RD.Sub == 0);
2592
2593   MachineBasicBlock &B = *MI->getParent();
2594   const DebugLoc &DL = MI->getDebugLoc();
2595   auto At = MI->isPHI() ? B.getFirstNonPHI()
2596                         : MachineBasicBlock::iterator(MI);
2597   bool KnownZ = true;
2598   bool KnownNZ = false;
2599
2600   BitTracker::RegisterRef SR = MI->getOperand(1);
2601   if (!BT.has(SR.Reg))
2602     return false;
2603   const BitTracker::RegisterCell &SC = BT.lookup(SR.Reg);
2604   unsigned F, W;
2605   if (!HBS::getSubregMask(SR, F, W, MRI))
2606     return false;
2607
2608   for (uint16_t I = F; I != F+W; ++I) {
2609     const BitTracker::BitValue &V = SC[I];
2610     if (!V.is(0))
2611       KnownZ = false;
2612     if (V.is(1))
2613       KnownNZ = true;
2614   }
2615
2616   auto ReplaceWithConst = [&] (int C) {
2617     unsigned NewR = MRI.createVirtualRegister(FRC);
2618     BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), NewR)
2619       .addImm(C);
2620     HBS::replaceReg(RD.Reg, NewR, MRI);
2621     BitTracker::RegisterCell NewRC(W);
2622     for (uint16_t I = 0; I != W; ++I) {
2623       NewRC[I] = BitTracker::BitValue(C & 1);
2624       C = unsigned(C) >> 1;
2625     }
2626     BT.put(BitTracker::RegisterRef(NewR), NewRC);
2627     return true;
2628   };
2629
2630   auto IsNonZero = [] (const MachineOperand &Op) {
2631     if (Op.isGlobal() || Op.isBlockAddress())
2632       return true;
2633     if (Op.isImm())
2634       return Op.getImm() != 0;
2635     if (Op.isCImm())
2636       return !Op.getCImm()->isZero();
2637     if (Op.isFPImm())
2638       return !Op.getFPImm()->isZero();
2639     return false;
2640   };
2641
2642   auto IsZero = [] (const MachineOperand &Op) {
2643     if (Op.isGlobal() || Op.isBlockAddress())
2644       return false;
2645     if (Op.isImm())
2646       return Op.getImm() == 0;
2647     if (Op.isCImm())
2648       return Op.getCImm()->isZero();
2649     if (Op.isFPImm())
2650       return Op.getFPImm()->isZero();
2651     return false;
2652   };
2653
2654   // If the source register is known to be 0 or non-0, the comparison can
2655   // be folded to a load of a constant.
2656   if (KnownZ || KnownNZ) {
2657     assert(KnownZ != KnownNZ && "Register cannot be both 0 and non-0");
2658     return ReplaceWithConst(KnownZ == (Opc == Hexagon::A4_rcmpeqi));
2659   }
2660
2661   // Special case: if the compare comes from a C2_muxii, then we know the
2662   // two possible constants that can be the source value.
2663   MachineInstr *InpDef = MRI.getVRegDef(SR.Reg);
2664   if (!InpDef)
2665     return false;
2666   if (SR.Sub == 0 && InpDef->getOpcode() == Hexagon::C2_muxii) {
2667     MachineOperand &Src1 = InpDef->getOperand(2);
2668     MachineOperand &Src2 = InpDef->getOperand(3);
2669     // Check if both are non-zero.
2670     bool KnownNZ1 = IsNonZero(Src1), KnownNZ2 = IsNonZero(Src2);
2671     if (KnownNZ1 && KnownNZ2)
2672       return ReplaceWithConst(Opc == Hexagon::A4_rcmpneqi);
2673     // Check if both are zero.
2674     bool KnownZ1 = IsZero(Src1), KnownZ2 = IsZero(Src2);
2675     if (KnownZ1 && KnownZ2)
2676       return ReplaceWithConst(Opc == Hexagon::A4_rcmpeqi);
2677
2678     // If for both operands we know that they are either 0 or non-0,
2679     // replace the comparison with a C2_muxii, using the same predicate
2680     // register, but with operands substituted with 0/1 accordingly.
2681     if ((KnownZ1 || KnownNZ1) && (KnownZ2 || KnownNZ2)) {
2682       unsigned NewR = MRI.createVirtualRegister(FRC);
2683       BuildMI(B, At, DL, HII.get(Hexagon::C2_muxii), NewR)
2684         .addReg(InpDef->getOperand(1).getReg())
2685         .addImm(KnownZ1 == (Opc == Hexagon::A4_rcmpeqi))
2686         .addImm(KnownZ2 == (Opc == Hexagon::A4_rcmpeqi));
2687       HBS::replaceReg(RD.Reg, NewR, MRI);
2688       // Create a new cell with only the least significant bit unknown.
2689       BitTracker::RegisterCell NewRC(W);
2690       NewRC[0] = BitTracker::BitValue::self();
2691       NewRC.fill(1, W, BitTracker::BitValue::Zero);
2692       BT.put(BitTracker::RegisterRef(NewR), NewRC);
2693       return true;
2694     }
2695   }
2696
2697   return false;
2698 }
2699
2700 bool BitSimplification::processBlock(MachineBasicBlock &B,
2701       const RegisterSet &AVs) {
2702   if (!BT.reached(&B))
2703     return false;
2704   bool Changed = false;
2705   RegisterSet AVB = AVs;
2706   RegisterSet Defs;
2707
2708   for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Defs)) {
2709     MachineInstr *MI = &*I;
2710     Defs.clear();
2711     HBS::getInstrDefs(*MI, Defs);
2712
2713     unsigned Opc = MI->getOpcode();
2714     if (Opc == TargetOpcode::COPY || Opc == TargetOpcode::REG_SEQUENCE)
2715       continue;
2716
2717     if (MI->mayStore()) {
2718       bool T = genStoreUpperHalf(MI);
2719       T = T || genStoreImmediate(MI);
2720       Changed |= T;
2721       continue;
2722     }
2723
2724     if (Defs.count() != 1)
2725       continue;
2726     const MachineOperand &Op0 = MI->getOperand(0);
2727     if (!Op0.isReg() || !Op0.isDef())
2728       continue;
2729     BitTracker::RegisterRef RD = Op0;
2730     if (!BT.has(RD.Reg))
2731       continue;
2732     const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2733     const BitTracker::RegisterCell &RC = BT.lookup(RD.Reg);
2734
2735     if (FRC->getID() == Hexagon::DoubleRegsRegClassID) {
2736       bool T = genPackhl(MI, RD, RC);
2737       T = T || simplifyExtractLow(MI, RD, RC, AVB);
2738       Changed |= T;
2739       continue;
2740     }
2741
2742     if (FRC->getID() == Hexagon::IntRegsRegClassID) {
2743       bool T = genBitSplit(MI, RD, RC, AVB);
2744       T = T || simplifyExtractLow(MI, RD, RC, AVB);
2745       T = T || genExtractHalf(MI, RD, RC);
2746       T = T || genCombineHalf(MI, RD, RC);
2747       T = T || genExtractLow(MI, RD, RC);
2748       T = T || simplifyRCmp0(MI, RD);
2749       Changed |= T;
2750       continue;
2751     }
2752
2753     if (FRC->getID() == Hexagon::PredRegsRegClassID) {
2754       bool T = simplifyTstbit(MI, RD, RC);
2755       Changed |= T;
2756       continue;
2757     }
2758   }
2759   return Changed;
2760 }
2761
2762 bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) {
2763   if (skipFunction(MF.getFunction()))
2764     return false;
2765
2766   auto &HST = MF.getSubtarget<HexagonSubtarget>();
2767   auto &HRI = *HST.getRegisterInfo();
2768   auto &HII = *HST.getInstrInfo();
2769
2770   MDT = &getAnalysis<MachineDominatorTree>();
2771   MachineRegisterInfo &MRI = MF.getRegInfo();
2772   bool Changed;
2773
2774   Changed = DeadCodeElimination(MF, *MDT).run();
2775
2776   const HexagonEvaluator HE(HRI, MRI, HII, MF);
2777   BitTracker BT(HE, MF);
2778   LLVM_DEBUG(BT.trace(true));
2779   BT.run();
2780
2781   MachineBasicBlock &Entry = MF.front();
2782
2783   RegisterSet AIG;  // Available registers for IG.
2784   ConstGeneration ImmG(BT, HII, MRI);
2785   Changed |= visitBlock(Entry, ImmG, AIG);
2786
2787   RegisterSet ARE;  // Available registers for RIE.
2788   RedundantInstrElimination RIE(BT, HII, HRI, MRI);
2789   bool Ried = visitBlock(Entry, RIE, ARE);
2790   if (Ried) {
2791     Changed = true;
2792     BT.run();
2793   }
2794
2795   RegisterSet ACG;  // Available registers for CG.
2796   CopyGeneration CopyG(BT, HII, HRI, MRI);
2797   Changed |= visitBlock(Entry, CopyG, ACG);
2798
2799   RegisterSet ACP;  // Available registers for CP.
2800   CopyPropagation CopyP(HRI, MRI);
2801   Changed |= visitBlock(Entry, CopyP, ACP);
2802
2803   Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2804
2805   BT.run();
2806   RegisterSet ABS;  // Available registers for BS.
2807   BitSimplification BitS(BT, *MDT, HII, HRI, MRI, MF);
2808   Changed |= visitBlock(Entry, BitS, ABS);
2809
2810   Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2811
2812   if (Changed) {
2813     for (auto &B : MF)
2814       for (auto &I : B)
2815         I.clearKillInfo();
2816     DeadCodeElimination(MF, *MDT).run();
2817   }
2818   return Changed;
2819 }
2820
2821 // Recognize loops where the code at the end of the loop matches the code
2822 // before the entry of the loop, and the matching code is such that is can
2823 // be simplified. This pass relies on the bit simplification above and only
2824 // prepares code in a way that can be handled by the bit simplifcation.
2825 //
2826 // This is the motivating testcase (and explanation):
2827 //
2828 // {
2829 //   loop0(.LBB0_2, r1)      // %for.body.preheader
2830 //   r5:4 = memd(r0++#8)
2831 // }
2832 // {
2833 //   r3 = lsr(r4, #16)
2834 //   r7:6 = combine(r5, r5)
2835 // }
2836 // {
2837 //   r3 = insert(r5, #16, #16)
2838 //   r7:6 = vlsrw(r7:6, #16)
2839 // }
2840 // .LBB0_2:
2841 // {
2842 //   memh(r2+#4) = r5
2843 //   memh(r2+#6) = r6            # R6 is really R5.H
2844 // }
2845 // {
2846 //   r2 = add(r2, #8)
2847 //   memh(r2+#0) = r4
2848 //   memh(r2+#2) = r3            # R3 is really R4.H
2849 // }
2850 // {
2851 //   r5:4 = memd(r0++#8)
2852 // }
2853 // {                             # "Shuffling" code that sets up R3 and R6
2854 //   r3 = lsr(r4, #16)           # so that their halves can be stored in the
2855 //   r7:6 = combine(r5, r5)      # next iteration. This could be folded into
2856 // }                             # the stores if the code was at the beginning
2857 // {                             # of the loop iteration. Since the same code
2858 //   r3 = insert(r5, #16, #16)   # precedes the loop, it can actually be moved
2859 //   r7:6 = vlsrw(r7:6, #16)     # there.
2860 // }:endloop0
2861 //
2862 //
2863 // The outcome:
2864 //
2865 // {
2866 //   loop0(.LBB0_2, r1)
2867 //   r5:4 = memd(r0++#8)
2868 // }
2869 // .LBB0_2:
2870 // {
2871 //   memh(r2+#4) = r5
2872 //   memh(r2+#6) = r5.h
2873 // }
2874 // {
2875 //   r2 = add(r2, #8)
2876 //   memh(r2+#0) = r4
2877 //   memh(r2+#2) = r4.h
2878 // }
2879 // {
2880 //   r5:4 = memd(r0++#8)
2881 // }:endloop0
2882
2883 namespace llvm {
2884
2885   FunctionPass *createHexagonLoopRescheduling();
2886   void initializeHexagonLoopReschedulingPass(PassRegistry&);
2887
2888 } // end namespace llvm
2889
2890 namespace {
2891
2892   class HexagonLoopRescheduling : public MachineFunctionPass {
2893   public:
2894     static char ID;
2895
2896     HexagonLoopRescheduling() : MachineFunctionPass(ID) {
2897       initializeHexagonLoopReschedulingPass(*PassRegistry::getPassRegistry());
2898     }
2899
2900     bool runOnMachineFunction(MachineFunction &MF) override;
2901
2902   private:
2903     const HexagonInstrInfo *HII = nullptr;
2904     const HexagonRegisterInfo *HRI = nullptr;
2905     MachineRegisterInfo *MRI = nullptr;
2906     BitTracker *BTP = nullptr;
2907
2908     struct LoopCand {
2909       LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb,
2910             MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {}
2911
2912       MachineBasicBlock *LB, *PB, *EB;
2913     };
2914     using InstrList = std::vector<MachineInstr *>;
2915     struct InstrGroup {
2916       BitTracker::RegisterRef Inp, Out;
2917       InstrList Ins;
2918     };
2919     struct PhiInfo {
2920       PhiInfo(MachineInstr &P, MachineBasicBlock &B);
2921
2922       unsigned DefR;
2923       BitTracker::RegisterRef LR, PR; // Loop Register, Preheader Register
2924       MachineBasicBlock *LB, *PB;     // Loop Block, Preheader Block
2925     };
2926
2927     static unsigned getDefReg(const MachineInstr *MI);
2928     bool isConst(unsigned Reg) const;
2929     bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const;
2930     bool isStoreInput(const MachineInstr *MI, unsigned DefR) const;
2931     bool isShuffleOf(unsigned OutR, unsigned InpR) const;
2932     bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2,
2933         unsigned &InpR2) const;
2934     void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB,
2935         MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR);
2936     bool processLoop(LoopCand &C);
2937   };
2938
2939 } // end anonymous namespace
2940
2941 char HexagonLoopRescheduling::ID = 0;
2942
2943 INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched",
2944   "Hexagon Loop Rescheduling", false, false)
2945
2946 HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
2947       MachineBasicBlock &B) {
2948   DefR = HexagonLoopRescheduling::getDefReg(&P);
2949   LB = &B;
2950   PB = nullptr;
2951   for (unsigned i = 1, n = P.getNumOperands(); i < n; i += 2) {
2952     const MachineOperand &OpB = P.getOperand(i+1);
2953     if (OpB.getMBB() == &B) {
2954       LR = P.getOperand(i);
2955       continue;
2956     }
2957     PB = OpB.getMBB();
2958     PR = P.getOperand(i);
2959   }
2960 }
2961
2962 unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) {
2963   RegisterSet Defs;
2964   HBS::getInstrDefs(*MI, Defs);
2965   if (Defs.count() != 1)
2966     return 0;
2967   return Defs.find_first();
2968 }
2969
2970 bool HexagonLoopRescheduling::isConst(unsigned Reg) const {
2971   if (!BTP->has(Reg))
2972     return false;
2973   const BitTracker::RegisterCell &RC = BTP->lookup(Reg);
2974   for (unsigned i = 0, w = RC.width(); i < w; ++i) {
2975     const BitTracker::BitValue &V = RC[i];
2976     if (!V.is(0) && !V.is(1))
2977       return false;
2978   }
2979   return true;
2980 }
2981
2982 bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
2983       unsigned DefR) const {
2984   unsigned Opc = MI->getOpcode();
2985   switch (Opc) {
2986     case TargetOpcode::COPY:
2987     case Hexagon::S2_lsr_i_r:
2988     case Hexagon::S2_asr_i_r:
2989     case Hexagon::S2_asl_i_r:
2990     case Hexagon::S2_lsr_i_p:
2991     case Hexagon::S2_asr_i_p:
2992     case Hexagon::S2_asl_i_p:
2993     case Hexagon::S2_insert:
2994     case Hexagon::A2_or:
2995     case Hexagon::A2_orp:
2996     case Hexagon::A2_and:
2997     case Hexagon::A2_andp:
2998     case Hexagon::A2_combinew:
2999     case Hexagon::A4_combineri:
3000     case Hexagon::A4_combineir:
3001     case Hexagon::A2_combineii:
3002     case Hexagon::A4_combineii:
3003     case Hexagon::A2_combine_ll:
3004     case Hexagon::A2_combine_lh:
3005     case Hexagon::A2_combine_hl:
3006     case Hexagon::A2_combine_hh:
3007       return true;
3008   }
3009   return false;
3010 }
3011
3012 bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
3013       unsigned InpR) const {
3014   for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
3015     const MachineOperand &Op = MI->getOperand(i);
3016     if (!Op.isReg())
3017       continue;
3018     if (Op.getReg() == InpR)
3019       return i == n-1;
3020   }
3021   return false;
3022 }
3023
3024 bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const {
3025   if (!BTP->has(OutR) || !BTP->has(InpR))
3026     return false;
3027   const BitTracker::RegisterCell &OutC = BTP->lookup(OutR);
3028   for (unsigned i = 0, w = OutC.width(); i < w; ++i) {
3029     const BitTracker::BitValue &V = OutC[i];
3030     if (V.Type != BitTracker::BitValue::Ref)
3031       continue;
3032     if (V.RefI.Reg != InpR)
3033       return false;
3034   }
3035   return true;
3036 }
3037
3038 bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
3039       unsigned OutR2, unsigned &InpR2) const {
3040   if (!BTP->has(OutR1) || !BTP->has(InpR1) || !BTP->has(OutR2))
3041     return false;
3042   const BitTracker::RegisterCell &OutC1 = BTP->lookup(OutR1);
3043   const BitTracker::RegisterCell &OutC2 = BTP->lookup(OutR2);
3044   unsigned W = OutC1.width();
3045   unsigned MatchR = 0;
3046   if (W != OutC2.width())
3047     return false;
3048   for (unsigned i = 0; i < W; ++i) {
3049     const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i];
3050     if (V1.Type != V2.Type || V1.Type == BitTracker::BitValue::One)
3051       return false;
3052     if (V1.Type != BitTracker::BitValue::Ref)
3053       continue;
3054     if (V1.RefI.Pos != V2.RefI.Pos)
3055       return false;
3056     if (V1.RefI.Reg != InpR1)
3057       return false;
3058     if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2)
3059       return false;
3060     if (!MatchR)
3061       MatchR = V2.RefI.Reg;
3062     else if (V2.RefI.Reg != MatchR)
3063       return false;
3064   }
3065   InpR2 = MatchR;
3066   return true;
3067 }
3068
3069 void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
3070       MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
3071       unsigned NewPredR) {
3072   DenseMap<unsigned,unsigned> RegMap;
3073
3074   const TargetRegisterClass *PhiRC = MRI->getRegClass(NewPredR);
3075   unsigned PhiR = MRI->createVirtualRegister(PhiRC);
3076   BuildMI(LB, At, At->getDebugLoc(), HII->get(TargetOpcode::PHI), PhiR)
3077     .addReg(NewPredR)
3078     .addMBB(&PB)
3079     .addReg(G.Inp.Reg)
3080     .addMBB(&LB);
3081   RegMap.insert(std::make_pair(G.Inp.Reg, PhiR));
3082
3083   for (unsigned i = G.Ins.size(); i > 0; --i) {
3084     const MachineInstr *SI = G.Ins[i-1];
3085     unsigned DR = getDefReg(SI);
3086     const TargetRegisterClass *RC = MRI->getRegClass(DR);
3087     unsigned NewDR = MRI->createVirtualRegister(RC);
3088     DebugLoc DL = SI->getDebugLoc();
3089
3090     auto MIB = BuildMI(LB, At, DL, HII->get(SI->getOpcode()), NewDR);
3091     for (unsigned j = 0, m = SI->getNumOperands(); j < m; ++j) {
3092       const MachineOperand &Op = SI->getOperand(j);
3093       if (!Op.isReg()) {
3094         MIB.add(Op);
3095         continue;
3096       }
3097       if (!Op.isUse())
3098         continue;
3099       unsigned UseR = RegMap[Op.getReg()];
3100       MIB.addReg(UseR, 0, Op.getSubReg());
3101     }
3102     RegMap.insert(std::make_pair(DR, NewDR));
3103   }
3104
3105   HBS::replaceReg(OldPhiR, RegMap[G.Out.Reg], *MRI);
3106 }
3107
3108 bool HexagonLoopRescheduling::processLoop(LoopCand &C) {
3109   LLVM_DEBUG(dbgs() << "Processing loop in " << printMBBReference(*C.LB)
3110                     << "\n");
3111   std::vector<PhiInfo> Phis;
3112   for (auto &I : *C.LB) {
3113     if (!I.isPHI())
3114       break;
3115     unsigned PR = getDefReg(&I);
3116     if (isConst(PR))
3117       continue;
3118     bool BadUse = false, GoodUse = false;
3119     for (auto UI = MRI->use_begin(PR), UE = MRI->use_end(); UI != UE; ++UI) {
3120       MachineInstr *UseI = UI->getParent();
3121       if (UseI->getParent() != C.LB) {
3122         BadUse = true;
3123         break;
3124       }
3125       if (isBitShuffle(UseI, PR) || isStoreInput(UseI, PR))
3126         GoodUse = true;
3127     }
3128     if (BadUse || !GoodUse)
3129       continue;
3130
3131     Phis.push_back(PhiInfo(I, *C.LB));
3132   }
3133
3134   LLVM_DEBUG({
3135     dbgs() << "Phis: {";
3136     for (auto &I : Phis) {
3137       dbgs() << ' ' << printReg(I.DefR, HRI) << "=phi("
3138              << printReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber()
3139              << ',' << printReg(I.LR.Reg, HRI, I.LR.Sub) << ":b"
3140              << I.LB->getNumber() << ')';
3141     }
3142     dbgs() << " }\n";
3143   });
3144
3145   if (Phis.empty())
3146     return false;
3147
3148   bool Changed = false;
3149   InstrList ShufIns;
3150
3151   // Go backwards in the block: for each bit shuffling instruction, check
3152   // if that instruction could potentially be moved to the front of the loop:
3153   // the output of the loop cannot be used in a non-shuffling instruction
3154   // in this loop.
3155   for (auto I = C.LB->rbegin(), E = C.LB->rend(); I != E; ++I) {
3156     if (I->isTerminator())
3157       continue;
3158     if (I->isPHI())
3159       break;
3160
3161     RegisterSet Defs;
3162     HBS::getInstrDefs(*I, Defs);
3163     if (Defs.count() != 1)
3164       continue;
3165     unsigned DefR = Defs.find_first();
3166     if (!TargetRegisterInfo::isVirtualRegister(DefR))
3167       continue;
3168     if (!isBitShuffle(&*I, DefR))
3169       continue;
3170
3171     bool BadUse = false;
3172     for (auto UI = MRI->use_begin(DefR), UE = MRI->use_end(); UI != UE; ++UI) {
3173       MachineInstr *UseI = UI->getParent();
3174       if (UseI->getParent() == C.LB) {
3175         if (UseI->isPHI()) {
3176           // If the use is in a phi node in this loop, then it should be
3177           // the value corresponding to the back edge.
3178           unsigned Idx = UI.getOperandNo();
3179           if (UseI->getOperand(Idx+1).getMBB() != C.LB)
3180             BadUse = true;
3181         } else {
3182           auto F = find(ShufIns, UseI);
3183           if (F == ShufIns.end())
3184             BadUse = true;
3185         }
3186       } else {
3187         // There is a use outside of the loop, but there is no epilog block
3188         // suitable for a copy-out.
3189         if (C.EB == nullptr)
3190           BadUse = true;
3191       }
3192       if (BadUse)
3193         break;
3194     }
3195
3196     if (BadUse)
3197       continue;
3198     ShufIns.push_back(&*I);
3199   }
3200
3201   // Partition the list of shuffling instructions into instruction groups,
3202   // where each group has to be moved as a whole (i.e. a group is a chain of
3203   // dependent instructions). A group produces a single live output register,
3204   // which is meant to be the input of the loop phi node (although this is
3205   // not checked here yet). It also uses a single register as its input,
3206   // which is some value produced in the loop body. After moving the group
3207   // to the beginning of the loop, that input register would need to be
3208   // the loop-carried register (through a phi node) instead of the (currently
3209   // loop-carried) output register.
3210   using InstrGroupList = std::vector<InstrGroup>;
3211   InstrGroupList Groups;
3212
3213   for (unsigned i = 0, n = ShufIns.size(); i < n; ++i) {
3214     MachineInstr *SI = ShufIns[i];
3215     if (SI == nullptr)
3216       continue;
3217
3218     InstrGroup G;
3219     G.Ins.push_back(SI);
3220     G.Out.Reg = getDefReg(SI);
3221     RegisterSet Inputs;
3222     HBS::getInstrUses(*SI, Inputs);
3223
3224     for (unsigned j = i+1; j < n; ++j) {
3225       MachineInstr *MI = ShufIns[j];
3226       if (MI == nullptr)
3227         continue;
3228       RegisterSet Defs;
3229       HBS::getInstrDefs(*MI, Defs);
3230       // If this instruction does not define any pending inputs, skip it.
3231       if (!Defs.intersects(Inputs))
3232         continue;
3233       // Otherwise, add it to the current group and remove the inputs that
3234       // are defined by MI.
3235       G.Ins.push_back(MI);
3236       Inputs.remove(Defs);
3237       // Then add all registers used by MI.
3238       HBS::getInstrUses(*MI, Inputs);
3239       ShufIns[j] = nullptr;
3240     }
3241
3242     // Only add a group if it requires at most one register.
3243     if (Inputs.count() > 1)
3244       continue;
3245     auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3246       return G.Out.Reg == P.LR.Reg;
3247     };
3248     if (llvm::find_if(Phis, LoopInpEq) == Phis.end())
3249       continue;
3250
3251     G.Inp.Reg = Inputs.find_first();
3252     Groups.push_back(G);
3253   }
3254
3255   LLVM_DEBUG({
3256     for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3257       InstrGroup &G = Groups[i];
3258       dbgs() << "Group[" << i << "] inp: "
3259              << printReg(G.Inp.Reg, HRI, G.Inp.Sub)
3260              << "  out: " << printReg(G.Out.Reg, HRI, G.Out.Sub) << "\n";
3261       for (unsigned j = 0, m = G.Ins.size(); j < m; ++j)
3262         dbgs() << "  " << *G.Ins[j];
3263     }
3264   });
3265
3266   for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3267     InstrGroup &G = Groups[i];
3268     if (!isShuffleOf(G.Out.Reg, G.Inp.Reg))
3269       continue;
3270     auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3271       return G.Out.Reg == P.LR.Reg;
3272     };
3273     auto F = llvm::find_if(Phis, LoopInpEq);
3274     if (F == Phis.end())
3275       continue;
3276     unsigned PrehR = 0;
3277     if (!isSameShuffle(G.Out.Reg, G.Inp.Reg, F->PR.Reg, PrehR)) {
3278       const MachineInstr *DefPrehR = MRI->getVRegDef(F->PR.Reg);
3279       unsigned Opc = DefPrehR->getOpcode();
3280       if (Opc != Hexagon::A2_tfrsi && Opc != Hexagon::A2_tfrpi)
3281         continue;
3282       if (!DefPrehR->getOperand(1).isImm())
3283         continue;
3284       if (DefPrehR->getOperand(1).getImm() != 0)
3285         continue;
3286       const TargetRegisterClass *RC = MRI->getRegClass(G.Inp.Reg);
3287       if (RC != MRI->getRegClass(F->PR.Reg)) {
3288         PrehR = MRI->createVirtualRegister(RC);
3289         unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi
3290                                                           : Hexagon::A2_tfrpi;
3291         auto T = C.PB->getFirstTerminator();
3292         DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc();
3293         BuildMI(*C.PB, T, DL, HII->get(TfrI), PrehR)
3294           .addImm(0);
3295       } else {
3296         PrehR = F->PR.Reg;
3297       }
3298     }
3299     // isSameShuffle could match with PrehR being of a wider class than
3300     // G.Inp.Reg, for example if G shuffles the low 32 bits of its input,
3301     // it would match for the input being a 32-bit register, and PrehR
3302     // being a 64-bit register (where the low 32 bits match). This could
3303     // be handled, but for now skip these cases.
3304     if (MRI->getRegClass(PrehR) != MRI->getRegClass(G.Inp.Reg))
3305       continue;
3306     moveGroup(G, *F->LB, *F->PB, F->LB->getFirstNonPHI(), F->DefR, PrehR);
3307     Changed = true;
3308   }
3309
3310   return Changed;
3311 }
3312
3313 bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) {
3314   if (skipFunction(MF.getFunction()))
3315     return false;
3316
3317   auto &HST = MF.getSubtarget<HexagonSubtarget>();
3318   HII = HST.getInstrInfo();
3319   HRI = HST.getRegisterInfo();
3320   MRI = &MF.getRegInfo();
3321   const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
3322   BitTracker BT(HE, MF);
3323   LLVM_DEBUG(BT.trace(true));
3324   BT.run();
3325   BTP = &BT;
3326
3327   std::vector<LoopCand> Cand;
3328
3329   for (auto &B : MF) {
3330     if (B.pred_size() != 2 || B.succ_size() != 2)
3331       continue;
3332     MachineBasicBlock *PB = nullptr;
3333     bool IsLoop = false;
3334     for (auto PI = B.pred_begin(), PE = B.pred_end(); PI != PE; ++PI) {
3335       if (*PI != &B)
3336         PB = *PI;
3337       else
3338         IsLoop = true;
3339     }
3340     if (!IsLoop)
3341       continue;
3342
3343     MachineBasicBlock *EB = nullptr;
3344     for (auto SI = B.succ_begin(), SE = B.succ_end(); SI != SE; ++SI) {
3345       if (*SI == &B)
3346         continue;
3347       // Set EP to the epilog block, if it has only 1 predecessor (i.e. the
3348       // edge from B to EP is non-critical.
3349       if ((*SI)->pred_size() == 1)
3350         EB = *SI;
3351       break;
3352     }
3353
3354     Cand.push_back(LoopCand(&B, PB, EB));
3355   }
3356
3357   bool Changed = false;
3358   for (auto &C : Cand)
3359     Changed |= processLoop(C);
3360
3361   return Changed;
3362 }
3363
3364 //===----------------------------------------------------------------------===//
3365 //                         Public Constructor Functions
3366 //===----------------------------------------------------------------------===//
3367
3368 FunctionPass *llvm::createHexagonLoopRescheduling() {
3369   return new HexagonLoopRescheduling();
3370 }
3371
3372 FunctionPass *llvm::createHexagonBitSimplify() {
3373   return new HexagonBitSimplify();
3374 }