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