lib/Target/Hexagon/HexagonNewValueJump.cpp

   1 //===- HexagonNewValueJump.cpp - Hexagon Backend New Value Jump -----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This implements NewValueJump pass in Hexagon.
  10 // Ideally, we should merge this as a Peephole pass prior to register
  11 // allocation, but because we have a spill in between the feeder and new value
  12 // jump instructions, we are forced to write after register allocation.
  13 // Having said that, we should re-attempt to pull this earlier at some point
  14 // in future.
  15
  16 // The basic approach looks for sequence of predicated jump, compare instruciton
  17 // that genereates the predicate and, the feeder to the predicate. Once it finds
  18 // all, it collapses compare and jump instruction into a new value jump
  19 // intstructions.
  20 //
  21 //===----------------------------------------------------------------------===//
  22
  23 #include "Hexagon.h"
  24 #include "HexagonInstrInfo.h"
  25 #include "HexagonRegisterInfo.h"
  26 #include "HexagonSubtarget.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/CodeGen/MachineBasicBlock.h"
  29 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineFunctionPass.h"
  32 #include "llvm/CodeGen/MachineInstr.h"
  33 #include "llvm/CodeGen/MachineInstrBuilder.h"
  34 #include "llvm/CodeGen/MachineOperand.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/TargetOpcodes.h"
  37 #include "llvm/CodeGen/TargetRegisterInfo.h"
  38 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  39 #include "llvm/IR/DebugLoc.h"
  40 #include "llvm/MC/MCInstrDesc.h"
  41 #include "llvm/Pass.h"
  42 #include "llvm/Support/BranchProbability.h"
  43 #include "llvm/Support/CommandLine.h"
  44 #include "llvm/Support/Debug.h"
  45 #include "llvm/Support/ErrorHandling.h"
  46 #include "llvm/Support/MathExtras.h"
  47 #include "llvm/Support/raw_ostream.h"
  48 #include <cassert>
  49 #include <cstdint>
  50 #include <iterator>
  51
  52 using namespace llvm;
  53
  54 #define DEBUG_TYPE "hexagon-nvj"
  55
  56 STATISTIC(NumNVJGenerated, "Number of New Value Jump Instructions created");
  57
  58 static cl::opt<int> DbgNVJCount("nvj-count", cl::init(-1), cl::Hidden,
  59     cl::desc("Maximum number of predicated jumps to be converted to "
  60     "New Value Jump"));
  61
  62 static cl::opt<bool> DisableNewValueJumps("disable-nvjump", cl::Hidden,
  63     cl::ZeroOrMore, cl::init(false),
  64     cl::desc("Disable New Value Jumps"));
  65
  66 namespace llvm {
  67
  68 FunctionPass *createHexagonNewValueJump();
  69 void initializeHexagonNewValueJumpPass(PassRegistry&);
  70
  71 } // end namespace llvm
  72
  73 namespace {
  74
  75   struct HexagonNewValueJump : public MachineFunctionPass {
  76     static char ID;
  77
  78     HexagonNewValueJump() : MachineFunctionPass(ID) {}
  79
  80     void getAnalysisUsage(AnalysisUsage &AU) const override {
  81       AU.addRequired<MachineBranchProbabilityInfo>();
  82       MachineFunctionPass::getAnalysisUsage(AU);
  83     }
  84
  85     StringRef getPassName() const override { return "Hexagon NewValueJump"; }
  86
  87     bool runOnMachineFunction(MachineFunction &Fn) override;
  88
  89     MachineFunctionProperties getRequiredProperties() const override {
  90       return MachineFunctionProperties().set(
  91           MachineFunctionProperties::Property::NoVRegs);
  92     }
  93
  94   private:
  95     const HexagonInstrInfo *QII;
  96     const HexagonRegisterInfo *QRI;
  97
  98     /// A handle to the branch probability pass.
  99     const MachineBranchProbabilityInfo *MBPI;
 100
 101     bool isNewValueJumpCandidate(const MachineInstr &MI) const;
 102   };
 103
 104 } // end anonymous namespace
 105
 106 char HexagonNewValueJump::ID = 0;
 107
 108 INITIALIZE_PASS_BEGIN(HexagonNewValueJump, "hexagon-nvj",
 109                       "Hexagon NewValueJump", false, false)
 110 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 111 INITIALIZE_PASS_END(HexagonNewValueJump, "hexagon-nvj",
 112                     "Hexagon NewValueJump", false, false)
 113
 114 // We have identified this II could be feeder to NVJ,
 115 // verify that it can be.
 116 static bool canBeFeederToNewValueJump(const HexagonInstrInfo *QII,
 117                                       const TargetRegisterInfo *TRI,
 118                                       MachineBasicBlock::iterator II,
 119                                       MachineBasicBlock::iterator end,
 120                                       MachineBasicBlock::iterator skip,
 121                                       MachineFunction &MF) {
 122   // Predicated instruction can not be feeder to NVJ.
 123   if (QII->isPredicated(*II))
 124     return false;
 125
 126   // Bail out if feederReg is a paired register (double regs in
 127   // our case). One would think that we can check to see if a given
 128   // register cmpReg1 or cmpReg2 is a sub register of feederReg
 129   // using -- if (QRI->isSubRegister(feederReg, cmpReg1) logic
 130   // before the callsite of this function
 131   // But we can not as it comes in the following fashion.
 132   //    %d0 = Hexagon_S2_lsr_r_p killed %d0, killed %r2
 133   //    %r0 = KILL %r0, implicit killed %d0
 134   //    %p0 = CMPEQri killed %r0, 0
 135   // Hence, we need to check if it's a KILL instruction.
 136   if (II->getOpcode() == TargetOpcode::KILL)
 137     return false;
 138
 139   if (II->isImplicitDef())
 140     return false;
 141
 142   if (QII->isSolo(*II))
 143     return false;
 144
 145   if (QII->isFloat(*II))
 146     return false;
 147
 148   // Make sure that the (unique) def operand is a register from IntRegs.
 149   bool HadDef = false;
 150   for (const MachineOperand &Op : II->operands()) {
 151     if (!Op.isReg() || !Op.isDef())
 152       continue;
 153     if (HadDef)
 154       return false;
 155     HadDef = true;
 156     if (!Hexagon::IntRegsRegClass.contains(Op.getReg()))
 157       return false;
 158   }
 159   assert(HadDef);
 160
 161   // Make sure there is no 'def' or 'use' of any of the uses of
 162   // feeder insn between its definition, this MI and jump, jmpInst
 163   // skipping compare, cmpInst.
 164   // Here's the example.
 165   //    r21=memub(r22+r24<<#0)
 166   //    p0 = cmp.eq(r21, #0)
 167   //    r4=memub(r3+r21<<#0)
 168   //    if (p0.new) jump:t .LBB29_45
 169   // Without this check, it will be converted into
 170   //    r4=memub(r3+r21<<#0)
 171   //    r21=memub(r22+r24<<#0)
 172   //    p0 = cmp.eq(r21, #0)
 173   //    if (p0.new) jump:t .LBB29_45
 174   // and result WAR hazards if converted to New Value Jump.
 175   for (unsigned i = 0; i < II->getNumOperands(); ++i) {
 176     if (II->getOperand(i).isReg() &&
 177         (II->getOperand(i).isUse() || II->getOperand(i).isDef())) {
 178       MachineBasicBlock::iterator localII = II;
 179       ++localII;
 180       Register Reg = II->getOperand(i).getReg();
 181       for (MachineBasicBlock::iterator localBegin = localII; localBegin != end;
 182            ++localBegin) {
 183         if (localBegin == skip)
 184           continue;
 185         // Check for Subregisters too.
 186         if (localBegin->modifiesRegister(Reg, TRI) ||
 187             localBegin->readsRegister(Reg, TRI))
 188           return false;
 189       }
 190     }
 191   }
 192   return true;
 193 }
 194
 195 // These are the common checks that need to performed
 196 // to determine if
 197 // 1. compare instruction can be moved before jump.
 198 // 2. feeder to the compare instruction can be moved before jump.
 199 static bool commonChecksToProhibitNewValueJump(bool afterRA,
 200                           MachineBasicBlock::iterator MII) {
 201   // If store in path, bail out.
 202   if (MII->mayStore())
 203     return false;
 204
 205   // if call in path, bail out.
 206   if (MII->isCall())
 207     return false;
 208
 209   // if NVJ is running prior to RA, do the following checks.
 210   if (!afterRA) {
 211     // The following Target Opcode instructions are spurious
 212     // to new value jump. If they are in the path, bail out.
 213     // KILL sets kill flag on the opcode. It also sets up a
 214     // single register, out of pair.
 215     //    %d0 = S2_lsr_r_p killed %d0, killed %r2
 216     //    %r0 = KILL %r0, implicit killed %d0
 217     //    %p0 = C2_cmpeqi killed %r0, 0
 218     // PHI can be anything after RA.
 219     // COPY can remateriaze things in between feeder, compare and nvj.
 220     if (MII->getOpcode() == TargetOpcode::KILL ||
 221         MII->getOpcode() == TargetOpcode::PHI ||
 222         MII->getOpcode() == TargetOpcode::COPY)
 223       return false;
 224
 225     // The following pseudo Hexagon instructions sets "use" and "def"
 226     // of registers by individual passes in the backend. At this time,
 227     // we don't know the scope of usage and definitions of these
 228     // instructions.
 229     if (MII->getOpcode() == Hexagon::LDriw_pred ||
 230         MII->getOpcode() == Hexagon::STriw_pred)
 231       return false;
 232   }
 233
 234   return true;
 235 }
 236
 237 static bool canCompareBeNewValueJump(const HexagonInstrInfo *QII,
 238                                      const TargetRegisterInfo *TRI,
 239                                      MachineBasicBlock::iterator II,
 240                                      unsigned pReg,
 241                                      bool secondReg,
 242                                      bool optLocation,
 243                                      MachineBasicBlock::iterator end,
 244                                      MachineFunction &MF) {
 245   MachineInstr &MI = *II;
 246
 247   // If the second operand of the compare is an imm, make sure it's in the
 248   // range specified by the arch.
 249   if (!secondReg) {
 250     const MachineOperand &Op2 = MI.getOperand(2);
 251     if (!Op2.isImm())
 252       return false;
 253
 254     int64_t v = Op2.getImm();
 255     bool Valid = false;
 256
 257     switch (MI.getOpcode()) {
 258       case Hexagon::C2_cmpeqi:
 259       case Hexagon::C4_cmpneqi:
 260       case Hexagon::C2_cmpgti:
 261       case Hexagon::C4_cmpltei:
 262         Valid = (isUInt<5>(v) || v == -1);
 263         break;
 264       case Hexagon::C2_cmpgtui:
 265       case Hexagon::C4_cmplteui:
 266         Valid = isUInt<5>(v);
 267         break;
 268       case Hexagon::S2_tstbit_i:
 269       case Hexagon::S4_ntstbit_i:
 270         Valid = (v == 0);
 271         break;
 272     }
 273
 274     if (!Valid)
 275       return false;
 276   }
 277
 278   unsigned cmpReg1, cmpOp2 = 0; // cmpOp2 assignment silences compiler warning.
 279   cmpReg1 = MI.getOperand(1).getReg();
 280
 281   if (secondReg) {
 282     cmpOp2 = MI.getOperand(2).getReg();
 283
 284     // If the same register appears as both operands, we cannot generate a new
 285     // value compare. Only one operand may use the .new suffix.
 286     if (cmpReg1 == cmpOp2)
 287       return false;
 288
 289     // Make sure that the second register is not from COPY
 290     // at machine code level, we don't need this, but if we decide
 291     // to move new value jump prior to RA, we would be needing this.
 292     MachineRegisterInfo &MRI = MF.getRegInfo();
 293     if (secondReg && !Register::isPhysicalRegister(cmpOp2)) {
 294       MachineInstr *def = MRI.getVRegDef(cmpOp2);
 295       if (def->getOpcode() == TargetOpcode::COPY)
 296         return false;
 297     }
 298   }
 299
 300   // Walk the instructions after the compare (predicate def) to the jump,
 301   // and satisfy the following conditions.
 302   ++II;
 303   for (MachineBasicBlock::iterator localII = II; localII != end; ++localII) {
 304     if (localII->isDebugInstr())
 305       continue;
 306
 307     // Check 1.
 308     // If "common" checks fail, bail out.
 309     if (!commonChecksToProhibitNewValueJump(optLocation, localII))
 310       return false;
 311
 312     // Check 2.
 313     // If there is a def or use of predicate (result of compare), bail out.
 314     if (localII->modifiesRegister(pReg, TRI) ||
 315         localII->readsRegister(pReg, TRI))
 316       return false;
 317
 318     // Check 3.
 319     // If there is a def of any of the use of the compare (operands of compare),
 320     // bail out.
 321     // Eg.
 322     //    p0 = cmp.eq(r2, r0)
 323     //    r2 = r4
 324     //    if (p0.new) jump:t .LBB28_3
 325     if (localII->modifiesRegister(cmpReg1, TRI) ||
 326         (secondReg && localII->modifiesRegister(cmpOp2, TRI)))
 327       return false;
 328   }
 329   return true;
 330 }
 331
 332 // Given a compare operator, return a matching New Value Jump compare operator.
 333 // Make sure that MI here is included in isNewValueJumpCandidate.
 334 static unsigned getNewValueJumpOpcode(MachineInstr *MI, int reg,
 335                                       bool secondRegNewified,
 336                                       MachineBasicBlock *jmpTarget,
 337                                       const MachineBranchProbabilityInfo
 338                                       *MBPI) {
 339   bool taken = false;
 340   MachineBasicBlock *Src = MI->getParent();
 341   const BranchProbability Prediction =
 342     MBPI->getEdgeProbability(Src, jmpTarget);
 343
 344   if (Prediction >= BranchProbability(1,2))
 345     taken = true;
 346
 347   switch (MI->getOpcode()) {
 348     case Hexagon::C2_cmpeq:
 349       return taken ? Hexagon::J4_cmpeq_t_jumpnv_t
 350                    : Hexagon::J4_cmpeq_t_jumpnv_nt;
 351
 352     case Hexagon::C2_cmpeqi:
 353       if (reg >= 0)
 354         return taken ? Hexagon::J4_cmpeqi_t_jumpnv_t
 355                      : Hexagon::J4_cmpeqi_t_jumpnv_nt;
 356       return taken ? Hexagon::J4_cmpeqn1_t_jumpnv_t
 357                    : Hexagon::J4_cmpeqn1_t_jumpnv_nt;
 358
 359     case Hexagon::C4_cmpneqi:
 360       if (reg >= 0)
 361         return taken ? Hexagon::J4_cmpeqi_f_jumpnv_t
 362                      : Hexagon::J4_cmpeqi_f_jumpnv_nt;
 363       return taken ? Hexagon::J4_cmpeqn1_f_jumpnv_t :
 364                      Hexagon::J4_cmpeqn1_f_jumpnv_nt;
 365
 366     case Hexagon::C2_cmpgt:
 367       if (secondRegNewified)
 368         return taken ? Hexagon::J4_cmplt_t_jumpnv_t
 369                      : Hexagon::J4_cmplt_t_jumpnv_nt;
 370       return taken ? Hexagon::J4_cmpgt_t_jumpnv_t
 371                    : Hexagon::J4_cmpgt_t_jumpnv_nt;
 372
 373     case Hexagon::C2_cmpgti:
 374       if (reg >= 0)
 375         return taken ? Hexagon::J4_cmpgti_t_jumpnv_t
 376                      : Hexagon::J4_cmpgti_t_jumpnv_nt;
 377       return taken ? Hexagon::J4_cmpgtn1_t_jumpnv_t
 378                    : Hexagon::J4_cmpgtn1_t_jumpnv_nt;
 379
 380     case Hexagon::C2_cmpgtu:
 381       if (secondRegNewified)
 382         return taken ? Hexagon::J4_cmpltu_t_jumpnv_t
 383                      : Hexagon::J4_cmpltu_t_jumpnv_nt;
 384       return taken ? Hexagon::J4_cmpgtu_t_jumpnv_t
 385                    : Hexagon::J4_cmpgtu_t_jumpnv_nt;
 386
 387     case Hexagon::C2_cmpgtui:
 388       return taken ? Hexagon::J4_cmpgtui_t_jumpnv_t
 389                    : Hexagon::J4_cmpgtui_t_jumpnv_nt;
 390
 391     case Hexagon::C4_cmpneq:
 392       return taken ? Hexagon::J4_cmpeq_f_jumpnv_t
 393                    : Hexagon::J4_cmpeq_f_jumpnv_nt;
 394
 395     case Hexagon::C4_cmplte:
 396       if (secondRegNewified)
 397         return taken ? Hexagon::J4_cmplt_f_jumpnv_t
 398                      : Hexagon::J4_cmplt_f_jumpnv_nt;
 399       return taken ? Hexagon::J4_cmpgt_f_jumpnv_t
 400                    : Hexagon::J4_cmpgt_f_jumpnv_nt;
 401
 402     case Hexagon::C4_cmplteu:
 403       if (secondRegNewified)
 404         return taken ? Hexagon::J4_cmpltu_f_jumpnv_t
 405                      : Hexagon::J4_cmpltu_f_jumpnv_nt;
 406       return taken ? Hexagon::J4_cmpgtu_f_jumpnv_t
 407                    : Hexagon::J4_cmpgtu_f_jumpnv_nt;
 408
 409     case Hexagon::C4_cmpltei:
 410       if (reg >= 0)
 411         return taken ? Hexagon::J4_cmpgti_f_jumpnv_t
 412                      : Hexagon::J4_cmpgti_f_jumpnv_nt;
 413       return taken ? Hexagon::J4_cmpgtn1_f_jumpnv_t
 414                    : Hexagon::J4_cmpgtn1_f_jumpnv_nt;
 415
 416     case Hexagon::C4_cmplteui:
 417       return taken ? Hexagon::J4_cmpgtui_f_jumpnv_t
 418                    : Hexagon::J4_cmpgtui_f_jumpnv_nt;
 419
 420     default:
 421        llvm_unreachable("Could not find matching New Value Jump instruction.");
 422   }
 423   // return *some value* to avoid compiler warning
 424   return 0;
 425 }
 426
 427 bool HexagonNewValueJump::isNewValueJumpCandidate(
 428     const MachineInstr &MI) const {
 429   switch (MI.getOpcode()) {
 430   case Hexagon::C2_cmpeq:
 431   case Hexagon::C2_cmpeqi:
 432   case Hexagon::C2_cmpgt:
 433   case Hexagon::C2_cmpgti:
 434   case Hexagon::C2_cmpgtu:
 435   case Hexagon::C2_cmpgtui:
 436   case Hexagon::C4_cmpneq:
 437   case Hexagon::C4_cmpneqi:
 438   case Hexagon::C4_cmplte:
 439   case Hexagon::C4_cmplteu:
 440   case Hexagon::C4_cmpltei:
 441   case Hexagon::C4_cmplteui:
 442     return true;
 443
 444   default:
 445     return false;
 446   }
 447 }
 448
 449 bool HexagonNewValueJump::runOnMachineFunction(MachineFunction &MF) {
 450   LLVM_DEBUG(dbgs() << "********** Hexagon New Value Jump **********\n"
 451                     << "********** Function: " << MF.getName() << "\n");
 452
 453   if (skipFunction(MF.getFunction()))
 454     return false;
 455
 456   // If we move NewValueJump before register allocation we'll need live variable
 457   // analysis here too.
 458
 459   QII = static_cast<const HexagonInstrInfo *>(MF.getSubtarget().getInstrInfo());
 460   QRI = static_cast<const HexagonRegisterInfo *>(
 461       MF.getSubtarget().getRegisterInfo());
 462   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
 463
 464   if (DisableNewValueJumps ||
 465       !MF.getSubtarget<HexagonSubtarget>().useNewValueJumps())
 466     return false;
 467
 468   int nvjCount = DbgNVJCount;
 469   int nvjGenerated = 0;
 470
 471   // Loop through all the bb's of the function
 472   for (MachineFunction::iterator MBBb = MF.begin(), MBBe = MF.end();
 473        MBBb != MBBe; ++MBBb) {
 474     MachineBasicBlock *MBB = &*MBBb;
 475
 476     LLVM_DEBUG(dbgs() << "** dumping bb ** " << MBB->getNumber() << "\n");
 477     LLVM_DEBUG(MBB->dump());
 478     LLVM_DEBUG(dbgs() << "\n"
 479                       << "********** dumping instr bottom up **********\n");
 480     bool foundJump    = false;
 481     bool foundCompare = false;
 482     bool invertPredicate = false;
 483     unsigned predReg = 0; // predicate reg of the jump.
 484     unsigned cmpReg1 = 0;
 485     int cmpOp2 = 0;
 486     MachineBasicBlock::iterator jmpPos;
 487     MachineBasicBlock::iterator cmpPos;
 488     MachineInstr *cmpInstr = nullptr, *jmpInstr = nullptr;
 489     MachineBasicBlock *jmpTarget = nullptr;
 490     bool afterRA = false;
 491     bool isSecondOpReg = false;
 492     bool isSecondOpNewified = false;
 493     // Traverse the basic block - bottom up
 494     for (MachineBasicBlock::iterator MII = MBB->end(), E = MBB->begin();
 495          MII != E;) {
 496       MachineInstr &MI = *--MII;
 497       if (MI.isDebugInstr()) {
 498         continue;
 499       }
 500
 501       if ((nvjCount == 0) || (nvjCount > -1 && nvjCount <= nvjGenerated))
 502         break;
 503
 504       LLVM_DEBUG(dbgs() << "Instr: "; MI.dump(); dbgs() << "\n");
 505
 506       if (!foundJump && (MI.getOpcode() == Hexagon::J2_jumpt ||
 507                          MI.getOpcode() == Hexagon::J2_jumptpt ||
 508                          MI.getOpcode() == Hexagon::J2_jumpf ||
 509                          MI.getOpcode() == Hexagon::J2_jumpfpt ||
 510                          MI.getOpcode() == Hexagon::J2_jumptnewpt ||
 511                          MI.getOpcode() == Hexagon::J2_jumptnew ||
 512                          MI.getOpcode() == Hexagon::J2_jumpfnewpt ||
 513                          MI.getOpcode() == Hexagon::J2_jumpfnew)) {
 514         // This is where you would insert your compare and
 515         // instr that feeds compare
 516         jmpPos = MII;
 517         jmpInstr = &MI;
 518         predReg = MI.getOperand(0).getReg();
 519         afterRA = Register::isPhysicalRegister(predReg);
 520
 521         // If ifconverter had not messed up with the kill flags of the
 522         // operands, the following check on the kill flag would suffice.
 523         // if(!jmpInstr->getOperand(0).isKill()) break;
 524
 525         // This predicate register is live out of BB
 526         // this would only work if we can actually use Live
 527         // variable analysis on phy regs - but LLVM does not
 528         // provide LV analysis on phys regs.
 529         //if(LVs.isLiveOut(predReg, *MBB)) break;
 530
 531         // Get all the successors of this block - which will always
 532         // be 2. Check if the predicate register is live-in in those
 533         // successor. If yes, we can not delete the predicate -
 534         // I am doing this only because LLVM does not provide LiveOut
 535         // at the BB level.
 536         bool predLive = false;
 537         for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
 538                                                     SIE = MBB->succ_end();
 539              SI != SIE; ++SI) {
 540           MachineBasicBlock *succMBB = *SI;
 541           if (succMBB->isLiveIn(predReg))
 542             predLive = true;
 543         }
 544         if (predLive)
 545           break;
 546
 547         if (!MI.getOperand(1).isMBB())
 548           continue;
 549         jmpTarget = MI.getOperand(1).getMBB();
 550         foundJump = true;
 551         if (MI.getOpcode() == Hexagon::J2_jumpf ||
 552             MI.getOpcode() == Hexagon::J2_jumpfnewpt ||
 553             MI.getOpcode() == Hexagon::J2_jumpfnew) {
 554           invertPredicate = true;
 555         }
 556         continue;
 557       }
 558
 559       // No new value jump if there is a barrier. A barrier has to be in its
 560       // own packet. A barrier has zero operands. We conservatively bail out
 561       // here if we see any instruction with zero operands.
 562       if (foundJump && MI.getNumOperands() == 0)
 563         break;
 564
 565       if (foundJump && !foundCompare && MI.getOperand(0).isReg() &&
 566           MI.getOperand(0).getReg() == predReg) {
 567         // Not all compares can be new value compare. Arch Spec: 7.6.1.1
 568         if (isNewValueJumpCandidate(MI)) {
 569           assert(
 570               (MI.getDesc().isCompare()) &&
 571               "Only compare instruction can be collapsed into New Value Jump");
 572           isSecondOpReg = MI.getOperand(2).isReg();
 573
 574           if (!canCompareBeNewValueJump(QII, QRI, MII, predReg, isSecondOpReg,
 575                                         afterRA, jmpPos, MF))
 576             break;
 577
 578           cmpInstr = &MI;
 579           cmpPos = MII;
 580           foundCompare = true;
 581
 582           // We need cmpReg1 and cmpOp2(imm or reg) while building
 583           // new value jump instruction.
 584           cmpReg1 = MI.getOperand(1).getReg();
 585
 586           if (isSecondOpReg)
 587             cmpOp2 = MI.getOperand(2).getReg();
 588           else
 589             cmpOp2 = MI.getOperand(2).getImm();
 590           continue;
 591         }
 592       }
 593
 594       if (foundCompare && foundJump) {
 595         // If "common" checks fail, bail out on this BB.
 596         if (!commonChecksToProhibitNewValueJump(afterRA, MII))
 597           break;
 598
 599         bool foundFeeder = false;
 600         MachineBasicBlock::iterator feederPos = MII;
 601         if (MI.getOperand(0).isReg() && MI.getOperand(0).isDef() &&
 602             (MI.getOperand(0).getReg() == cmpReg1 ||
 603              (isSecondOpReg &&
 604               MI.getOperand(0).getReg() == (unsigned)cmpOp2))) {
 605
 606           Register feederReg = MI.getOperand(0).getReg();
 607
 608           // First try to see if we can get the feeder from the first operand
 609           // of the compare. If we can not, and if secondOpReg is true
 610           // (second operand of the compare is also register), try that one.
 611           // TODO: Try to come up with some heuristic to figure out which
 612           // feeder would benefit.
 613
 614           if (feederReg == cmpReg1) {
 615             if (!canBeFeederToNewValueJump(QII, QRI, MII, jmpPos, cmpPos, MF)) {
 616               if (!isSecondOpReg)
 617                 break;
 618               else
 619                 continue;
 620             } else
 621               foundFeeder = true;
 622           }
 623
 624           if (!foundFeeder && isSecondOpReg && feederReg == (unsigned)cmpOp2)
 625             if (!canBeFeederToNewValueJump(QII, QRI, MII, jmpPos, cmpPos, MF))
 626               break;
 627
 628           if (isSecondOpReg) {
 629             // In case of CMPLT, or CMPLTU, or EQ with the second register
 630             // to newify, swap the operands.
 631             unsigned COp = cmpInstr->getOpcode();
 632             if ((COp == Hexagon::C2_cmpeq || COp == Hexagon::C4_cmpneq) &&
 633                 (feederReg == (unsigned)cmpOp2)) {
 634               unsigned tmp = cmpReg1;
 635               cmpReg1 = cmpOp2;
 636               cmpOp2 = tmp;
 637             }
 638
 639             // Now we have swapped the operands, all we need to check is,
 640             // if the second operand (after swap) is the feeder.
 641             // And if it is, make a note.
 642             if (feederReg == (unsigned)cmpOp2)
 643               isSecondOpNewified = true;
 644           }
 645
 646           // Now that we are moving feeder close the jump,
 647           // make sure we are respecting the kill values of
 648           // the operands of the feeder.
 649
 650           auto TransferKills = [jmpPos,cmpPos] (MachineInstr &MI) {
 651             for (MachineOperand &MO : MI.operands()) {
 652               if (!MO.isReg() || !MO.isUse())
 653                 continue;
 654               Register UseR = MO.getReg();
 655               for (auto I = std::next(MI.getIterator()); I != jmpPos; ++I) {
 656                 if (I == cmpPos)
 657                   continue;
 658                 for (MachineOperand &Op : I->operands()) {
 659                   if (!Op.isReg() || !Op.isUse() || !Op.isKill())
 660                     continue;
 661                   if (Op.getReg() != UseR)
 662                     continue;
 663                   // We found that there is kill of a use register
 664                   // Set up a kill flag on the register
 665                   Op.setIsKill(false);
 666                   MO.setIsKill(true);
 667                   return;
 668                 }
 669               }
 670             }
 671           };
 672
 673           TransferKills(*feederPos);
 674           TransferKills(*cmpPos);
 675           bool MO1IsKill = cmpPos->killsRegister(cmpReg1, QRI);
 676           bool MO2IsKill = isSecondOpReg && cmpPos->killsRegister(cmpOp2, QRI);
 677
 678           MBB->splice(jmpPos, MI.getParent(), MI);
 679           MBB->splice(jmpPos, MI.getParent(), cmpInstr);
 680           DebugLoc dl = MI.getDebugLoc();
 681           MachineInstr *NewMI;
 682
 683           assert((isNewValueJumpCandidate(*cmpInstr)) &&
 684                  "This compare is not a New Value Jump candidate.");
 685           unsigned opc = getNewValueJumpOpcode(cmpInstr, cmpOp2,
 686                                                isSecondOpNewified,
 687                                                jmpTarget, MBPI);
 688           if (invertPredicate)
 689             opc = QII->getInvertedPredicatedOpcode(opc);
 690
 691           if (isSecondOpReg)
 692             NewMI = BuildMI(*MBB, jmpPos, dl, QII->get(opc))
 693                         .addReg(cmpReg1, getKillRegState(MO1IsKill))
 694                         .addReg(cmpOp2, getKillRegState(MO2IsKill))
 695                         .addMBB(jmpTarget);
 696
 697           else
 698             NewMI = BuildMI(*MBB, jmpPos, dl, QII->get(opc))
 699                         .addReg(cmpReg1, getKillRegState(MO1IsKill))
 700                         .addImm(cmpOp2)
 701                         .addMBB(jmpTarget);
 702
 703           assert(NewMI && "New Value Jump Instruction Not created!");
 704           (void)NewMI;
 705           if (cmpInstr->getOperand(0).isReg() &&
 706               cmpInstr->getOperand(0).isKill())
 707             cmpInstr->getOperand(0).setIsKill(false);
 708           if (cmpInstr->getOperand(1).isReg() &&
 709               cmpInstr->getOperand(1).isKill())
 710             cmpInstr->getOperand(1).setIsKill(false);
 711           cmpInstr->eraseFromParent();
 712           jmpInstr->eraseFromParent();
 713           ++nvjGenerated;
 714           ++NumNVJGenerated;
 715           break;
 716         }
 717       }
 718     }
 719   }
 720
 721   return true;
 722 }
 723
 724 FunctionPass *llvm::createHexagonNewValueJump() {
 725   return new HexagonNewValueJump();
 726 }