lib/Target/Hexagon/HexagonVLIWPacketizer.cpp

   1 //===----- HexagonPacketizer.cpp - vliw packetizer ---------------------===//
   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 // This implements a simple VLIW packetizer using DFA. The packetizer works on
  11 // machine basic blocks. For each instruction I in BB, the packetizer consults
  12 // the DFA to see if machine resources are available to execute I. If so, the
  13 // packetizer checks if I depends on any instruction J in the current packet.
  14 // If no dependency is found, I is added to current packet and machine resource
  15 // is marked as taken. If any dependency is found, a target API call is made to
  16 // prune the dependence.
  17 //
  18 //===----------------------------------------------------------------------===//
  19 #define DEBUG_TYPE "packets"
  20 #include "llvm/CodeGen/DFAPacketizer.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/MachineDominators.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/MachineLoopInfo.h"
  25 #include "llvm/CodeGen/ScheduleDAG.h"
  26 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  27 #include "llvm/CodeGen/LatencyPriorityQueue.h"
  28 #include "llvm/CodeGen/SchedulerRegistry.h"
  29 #include "llvm/CodeGen/MachineFrameInfo.h"
  30 #include "llvm/CodeGen/MachineInstrBuilder.h"
  31 #include "llvm/CodeGen/MachineRegisterInfo.h"
  32 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
  33 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
  34 #include "llvm/Target/TargetMachine.h"
  35 #include "llvm/Target/TargetInstrInfo.h"
  36 #include "llvm/Target/TargetRegisterInfo.h"
  37 #include "llvm/ADT/DenseMap.h"
  38 #include "llvm/ADT/Statistic.h"
  39 #include "llvm/Support/MathExtras.h"
  40 #include "llvm/MC/MCInstrItineraries.h"
  41 #include "llvm/Support/Compiler.h"
  42 #include "llvm/Support/CommandLine.h"
  43 #include "llvm/Support/Debug.h"
  44 #include "Hexagon.h"
  45 #include "HexagonTargetMachine.h"
  46 #include "HexagonRegisterInfo.h"
  47 #include "HexagonSubtarget.h"
  48 #include "HexagonMachineFunctionInfo.h"
  49
  50 #include <map>
  51 #include <vector>
  52
  53 using namespace llvm;
  54
  55 static cl::opt<bool> PacketizeVolatiles("hexagon-packetize-volatiles",
  56       cl::ZeroOrMore, cl::Hidden, cl::init(true),
  57       cl::desc("Allow non-solo packetization of volatile memory references"));
  58
  59 namespace llvm {
  60   void initializeHexagonPacketizerPass(PassRegistry&);
  61 }
  62
  63
  64 namespace {
  65   class HexagonPacketizer : public MachineFunctionPass {
  66
  67   public:
  68     static char ID;
  69     HexagonPacketizer() : MachineFunctionPass(ID) {
  70       initializeHexagonPacketizerPass(*PassRegistry::getPassRegistry());
  71     }
  72
  73     void getAnalysisUsage(AnalysisUsage &AU) const {
  74       AU.setPreservesCFG();
  75       AU.addRequired<MachineDominatorTree>();
  76       AU.addRequired<MachineBranchProbabilityInfo>();
  77       AU.addPreserved<MachineDominatorTree>();
  78       AU.addRequired<MachineLoopInfo>();
  79       AU.addPreserved<MachineLoopInfo>();
  80       MachineFunctionPass::getAnalysisUsage(AU);
  81     }
  82
  83     const char *getPassName() const {
  84       return "Hexagon Packetizer";
  85     }
  86
  87     bool runOnMachineFunction(MachineFunction &Fn);
  88   };
  89   char HexagonPacketizer::ID = 0;
  90
  91   class HexagonPacketizerList : public VLIWPacketizerList {
  92
  93   private:
  94
  95     // Has the instruction been promoted to a dot-new instruction.
  96     bool PromotedToDotNew;
  97
  98     // Has the instruction been glued to allocframe.
  99     bool GlueAllocframeStore;
 100
 101     // Has the feeder instruction been glued to new value jump.
 102     bool GlueToNewValueJump;
 103
 104     // Check if there is a dependence between some instruction already in this
 105     // packet and this instruction.
 106     bool Dependence;
 107
 108     // Only check for dependence if there are resources available to
 109     // schedule this instruction.
 110     bool FoundSequentialDependence;
 111
 112     /// \brief A handle to the branch probability pass.
 113    const MachineBranchProbabilityInfo *MBPI;
 114
 115    // Track MIs with ignored dependece.
 116    std::vector<MachineInstr*> IgnoreDepMIs;
 117
 118   public:
 119     // Ctor.
 120     HexagonPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
 121                           MachineDominatorTree &MDT,
 122                           const MachineBranchProbabilityInfo *MBPI);
 123
 124     // initPacketizerState - initialize some internal flags.
 125     void initPacketizerState();
 126
 127     // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
 128     bool ignorePseudoInstruction(MachineInstr *MI, MachineBasicBlock *MBB);
 129
 130     // isSoloInstruction - return true if instruction MI can not be packetized
 131     // with any other instruction, which means that MI itself is a packet.
 132     bool isSoloInstruction(MachineInstr *MI);
 133
 134     // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ
 135     // together.
 136     bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ);
 137
 138     // isLegalToPruneDependencies - Is it legal to prune dependece between SUI
 139     // and SUJ.
 140     bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ);
 141
 142     MachineBasicBlock::iterator addToPacket(MachineInstr *MI);
 143   private:
 144     bool IsCallDependent(MachineInstr* MI, SDep::Kind DepType, unsigned DepReg);
 145     bool PromoteToDotNew(MachineInstr* MI, SDep::Kind DepType,
 146                          MachineBasicBlock::iterator &MII,
 147                          const TargetRegisterClass* RC);
 148     bool CanPromoteToDotNew(MachineInstr* MI, SUnit* PacketSU,
 149                             unsigned DepReg,
 150                             std::map <MachineInstr*, SUnit*> MIToSUnit,
 151                             MachineBasicBlock::iterator &MII,
 152                             const TargetRegisterClass* RC);
 153     bool CanPromoteToNewValue(MachineInstr* MI, SUnit* PacketSU,
 154                               unsigned DepReg,
 155                               std::map <MachineInstr*, SUnit*> MIToSUnit,
 156                               MachineBasicBlock::iterator &MII);
 157     bool CanPromoteToNewValueStore(MachineInstr* MI, MachineInstr* PacketMI,
 158                                    unsigned DepReg,
 159                                    std::map <MachineInstr*, SUnit*> MIToSUnit);
 160     bool DemoteToDotOld(MachineInstr* MI);
 161     bool ArePredicatesComplements(MachineInstr* MI1, MachineInstr* MI2,
 162                     std::map <MachineInstr*, SUnit*> MIToSUnit);
 163     bool RestrictingDepExistInPacket(MachineInstr*,
 164                     unsigned, std::map <MachineInstr*, SUnit*>);
 165     bool isNewifiable(MachineInstr* MI);
 166     bool isCondInst(MachineInstr* MI);
 167     bool IsNewifyStore (MachineInstr* MI);
 168     bool tryAllocateResourcesForConstExt(MachineInstr* MI);
 169     bool canReserveResourcesForConstExt(MachineInstr *MI);
 170     void reserveResourcesForConstExt(MachineInstr* MI);
 171     bool isNewValueInst(MachineInstr* MI);
 172   };
 173 }
 174
 175 INITIALIZE_PASS_BEGIN(HexagonPacketizer, "packets", "Hexagon Packetizer",
 176                       false, false)
 177 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 178 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 179 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 180 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 181 INITIALIZE_PASS_END(HexagonPacketizer, "packets", "Hexagon Packetizer",
 182                     false, false)
 183
 184
 185 // HexagonPacketizerList Ctor.
 186 HexagonPacketizerList::HexagonPacketizerList(
 187   MachineFunction &MF, MachineLoopInfo &MLI,MachineDominatorTree &MDT,
 188   const MachineBranchProbabilityInfo *MBPI)
 189   : VLIWPacketizerList(MF, MLI, MDT, true){
 190   this->MBPI = MBPI;
 191 }
 192
 193 bool HexagonPacketizer::runOnMachineFunction(MachineFunction &Fn) {
 194   const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo();
 195   MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>();
 196   MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>();
 197   const MachineBranchProbabilityInfo *MBPI =
 198     &getAnalysis<MachineBranchProbabilityInfo>();
 199   // Instantiate the packetizer.
 200   HexagonPacketizerList Packetizer(Fn, MLI, MDT, MBPI);
 201
 202   // DFA state table should not be empty.
 203   assert(Packetizer.getResourceTracker() && "Empty DFA table!");
 204
 205   //
 206   // Loop over all basic blocks and remove KILL pseudo-instructions
 207   // These instructions confuse the dependence analysis. Consider:
 208   // D0 = ...   (Insn 0)
 209   // R0 = KILL R0, D0 (Insn 1)
 210   // R0 = ... (Insn 2)
 211   // Here, Insn 1 will result in the dependence graph not emitting an output
 212   // dependence between Insn 0 and Insn 2. This can lead to incorrect
 213   // packetization
 214   //
 215   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 216        MBB != MBBe; ++MBB) {
 217     MachineBasicBlock::iterator End = MBB->end();
 218     MachineBasicBlock::iterator MI = MBB->begin();
 219     while (MI != End) {
 220       if (MI->isKill()) {
 221         MachineBasicBlock::iterator DeleteMI = MI;
 222         ++MI;
 223         MBB->erase(DeleteMI);
 224         End = MBB->end();
 225         continue;
 226       }
 227       ++MI;
 228     }
 229   }
 230
 231   // Loop over all of the basic blocks.
 232   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 233        MBB != MBBe; ++MBB) {
 234     // Find scheduling regions and schedule / packetize each region.
 235     unsigned RemainingCount = MBB->size();
 236     for(MachineBasicBlock::iterator RegionEnd = MBB->end();
 237         RegionEnd != MBB->begin();) {
 238       // The next region starts above the previous region. Look backward in the
 239       // instruction stream until we find the nearest boundary.
 240       MachineBasicBlock::iterator I = RegionEnd;
 241       for(;I != MBB->begin(); --I, --RemainingCount) {
 242         if (TII->isSchedulingBoundary(llvm::prior(I), MBB, Fn))
 243           break;
 244       }
 245       I = MBB->begin();
 246
 247       // Skip empty scheduling regions.
 248       if (I == RegionEnd) {
 249         RegionEnd = llvm::prior(RegionEnd);
 250         --RemainingCount;
 251         continue;
 252       }
 253       // Skip regions with one instruction.
 254       if (I == llvm::prior(RegionEnd)) {
 255         RegionEnd = llvm::prior(RegionEnd);
 256         continue;
 257       }
 258
 259       Packetizer.PacketizeMIs(MBB, I, RegionEnd);
 260       RegionEnd = I;
 261     }
 262   }
 263
 264   return true;
 265 }
 266
 267
 268 static bool IsIndirectCall(MachineInstr* MI) {
 269   return ((MI->getOpcode() == Hexagon::CALLR) ||
 270           (MI->getOpcode() == Hexagon::CALLRv3));
 271 }
 272
 273 // Reserve resources for constant extender. Trigure an assertion if
 274 // reservation fail.
 275 void HexagonPacketizerList::reserveResourcesForConstExt(MachineInstr* MI) {
 276   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 277   MachineFunction *MF = MI->getParent()->getParent();
 278   MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::IMMEXT_i),
 279                                                   MI->getDebugLoc());
 280
 281   if (ResourceTracker->canReserveResources(PseudoMI)) {
 282     ResourceTracker->reserveResources(PseudoMI);
 283     MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI);
 284   } else {
 285     MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI);
 286     llvm_unreachable("can not reserve resources for constant extender.");
 287   }
 288   return;
 289 }
 290
 291 bool HexagonPacketizerList::canReserveResourcesForConstExt(MachineInstr *MI) {
 292   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 293   assert((QII->isExtended(MI) || QII->isConstExtended(MI)) &&
 294          "Should only be called for constant extended instructions");
 295   MachineFunction *MF = MI->getParent()->getParent();
 296   MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::IMMEXT_i),
 297                                                   MI->getDebugLoc());
 298   bool CanReserve = ResourceTracker->canReserveResources(PseudoMI);
 299   MF->DeleteMachineInstr(PseudoMI);
 300   return CanReserve;
 301 }
 302
 303 // Allocate resources (i.e. 4 bytes) for constant extender. If succeed, return
 304 // true, otherwise, return false.
 305 bool HexagonPacketizerList::tryAllocateResourcesForConstExt(MachineInstr* MI) {
 306   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 307   MachineFunction *MF = MI->getParent()->getParent();
 308   MachineInstr *PseudoMI = MF->CreateMachineInstr(QII->get(Hexagon::IMMEXT_i),
 309                                                   MI->getDebugLoc());
 310
 311   if (ResourceTracker->canReserveResources(PseudoMI)) {
 312     ResourceTracker->reserveResources(PseudoMI);
 313     MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI);
 314     return true;
 315   } else {
 316     MI->getParent()->getParent()->DeleteMachineInstr(PseudoMI);
 317     return false;
 318   }
 319 }
 320
 321
 322 bool HexagonPacketizerList::IsCallDependent(MachineInstr* MI,
 323                                           SDep::Kind DepType,
 324                                           unsigned DepReg) {
 325
 326   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 327   const HexagonRegisterInfo* QRI =
 328               (const HexagonRegisterInfo *) TM.getRegisterInfo();
 329
 330   // Check for lr dependence
 331   if (DepReg == QRI->getRARegister()) {
 332     return true;
 333   }
 334
 335   if (QII->isDeallocRet(MI)) {
 336     if (DepReg == QRI->getFrameRegister() ||
 337         DepReg == QRI->getStackRegister())
 338       return true;
 339   }
 340
 341   // Check if this is a predicate dependence
 342   const TargetRegisterClass* RC = QRI->getMinimalPhysRegClass(DepReg);
 343   if (RC == &Hexagon::PredRegsRegClass) {
 344     return true;
 345   }
 346
 347   //
 348   // Lastly check for an operand used in an indirect call
 349   // If we had an attribute for checking if an instruction is an indirect call,
 350   // then we could have avoided this relatively brittle implementation of
 351   // IsIndirectCall()
 352   //
 353   // Assumes that the first operand of the CALLr is the function address
 354   //
 355   if (IsIndirectCall(MI) && (DepType == SDep::Data)) {
 356     MachineOperand MO = MI->getOperand(0);
 357     if (MO.isReg() && MO.isUse() && (MO.getReg() == DepReg)) {
 358       return true;
 359     }
 360   }
 361
 362   return false;
 363 }
 364
 365 static bool IsRegDependence(const SDep::Kind DepType) {
 366   return (DepType == SDep::Data || DepType == SDep::Anti ||
 367           DepType == SDep::Output);
 368 }
 369
 370 static bool IsDirectJump(MachineInstr* MI) {
 371   return (MI->getOpcode() == Hexagon::JMP);
 372 }
 373
 374 static bool IsSchedBarrier(MachineInstr* MI) {
 375   switch (MI->getOpcode()) {
 376   case Hexagon::BARRIER:
 377     return true;
 378   }
 379   return false;
 380 }
 381
 382 static bool IsControlFlow(MachineInstr* MI) {
 383   return (MI->getDesc().isTerminator() || MI->getDesc().isCall());
 384 }
 385
 386 // Function returns true if an instruction can be promoted to the new-value
 387 // store. It will always return false for v2 and v3.
 388 // It lists all the conditional and unconditional stores that can be promoted
 389 // to the new-value stores.
 390
 391 bool HexagonPacketizerList::IsNewifyStore (MachineInstr* MI) {
 392   const HexagonRegisterInfo* QRI =
 393                           (const HexagonRegisterInfo *) TM.getRegisterInfo();
 394   switch (MI->getOpcode())
 395   {
 396     // store byte
 397     case Hexagon::STrib:
 398     case Hexagon::STrib_indexed:
 399     case Hexagon::STrib_indexed_shl_V4:
 400     case Hexagon::STrib_shl_V4:
 401     case Hexagon::STb_GP_V4:
 402     case Hexagon::POST_STbri:
 403     case Hexagon::STrib_cPt:
 404     case Hexagon::STrib_cdnPt_V4:
 405     case Hexagon::STrib_cNotPt:
 406     case Hexagon::STrib_cdnNotPt_V4:
 407     case Hexagon::STrib_indexed_cPt:
 408     case Hexagon::STrib_indexed_cdnPt_V4:
 409     case Hexagon::STrib_indexed_cNotPt:
 410     case Hexagon::STrib_indexed_cdnNotPt_V4:
 411     case Hexagon::STrib_indexed_shl_cPt_V4:
 412     case Hexagon::STrib_indexed_shl_cdnPt_V4:
 413     case Hexagon::STrib_indexed_shl_cNotPt_V4:
 414     case Hexagon::STrib_indexed_shl_cdnNotPt_V4:
 415     case Hexagon::POST_STbri_cPt:
 416     case Hexagon::POST_STbri_cdnPt_V4:
 417     case Hexagon::POST_STbri_cNotPt:
 418     case Hexagon::POST_STbri_cdnNotPt_V4:
 419     case Hexagon::STb_GP_cPt_V4:
 420     case Hexagon::STb_GP_cNotPt_V4:
 421     case Hexagon::STb_GP_cdnPt_V4:
 422     case Hexagon::STb_GP_cdnNotPt_V4:
 423
 424     // store halfword
 425     case Hexagon::STrih:
 426     case Hexagon::STrih_indexed:
 427     case Hexagon::STrih_indexed_shl_V4:
 428     case Hexagon::STrih_shl_V4:
 429     case Hexagon::STh_GP_V4:
 430     case Hexagon::POST_SThri:
 431     case Hexagon::STrih_cPt:
 432     case Hexagon::STrih_cdnPt_V4:
 433     case Hexagon::STrih_cNotPt:
 434     case Hexagon::STrih_cdnNotPt_V4:
 435     case Hexagon::STrih_indexed_cPt:
 436     case Hexagon::STrih_indexed_cdnPt_V4:
 437     case Hexagon::STrih_indexed_cNotPt:
 438     case Hexagon::STrih_indexed_cdnNotPt_V4:
 439     case Hexagon::STrih_indexed_shl_cPt_V4:
 440     case Hexagon::STrih_indexed_shl_cdnPt_V4:
 441     case Hexagon::STrih_indexed_shl_cNotPt_V4:
 442     case Hexagon::STrih_indexed_shl_cdnNotPt_V4:
 443     case Hexagon::POST_SThri_cPt:
 444     case Hexagon::POST_SThri_cdnPt_V4:
 445     case Hexagon::POST_SThri_cNotPt:
 446     case Hexagon::POST_SThri_cdnNotPt_V4:
 447     case Hexagon::STh_GP_cPt_V4:
 448     case Hexagon::STh_GP_cNotPt_V4:
 449     case Hexagon::STh_GP_cdnPt_V4:
 450     case Hexagon::STh_GP_cdnNotPt_V4:
 451
 452     // store word
 453     case Hexagon::STriw:
 454     case Hexagon::STriw_indexed:
 455     case Hexagon::STriw_indexed_shl_V4:
 456     case Hexagon::STriw_shl_V4:
 457     case Hexagon::STw_GP_V4:
 458     case Hexagon::POST_STwri:
 459     case Hexagon::STriw_cPt:
 460     case Hexagon::STriw_cdnPt_V4:
 461     case Hexagon::STriw_cNotPt:
 462     case Hexagon::STriw_cdnNotPt_V4:
 463     case Hexagon::STriw_indexed_cPt:
 464     case Hexagon::STriw_indexed_cdnPt_V4:
 465     case Hexagon::STriw_indexed_cNotPt:
 466     case Hexagon::STriw_indexed_cdnNotPt_V4:
 467     case Hexagon::STriw_indexed_shl_cPt_V4:
 468     case Hexagon::STriw_indexed_shl_cdnPt_V4:
 469     case Hexagon::STriw_indexed_shl_cNotPt_V4:
 470     case Hexagon::STriw_indexed_shl_cdnNotPt_V4:
 471     case Hexagon::POST_STwri_cPt:
 472     case Hexagon::POST_STwri_cdnPt_V4:
 473     case Hexagon::POST_STwri_cNotPt:
 474     case Hexagon::POST_STwri_cdnNotPt_V4:
 475     case Hexagon::STw_GP_cPt_V4:
 476     case Hexagon::STw_GP_cNotPt_V4:
 477     case Hexagon::STw_GP_cdnPt_V4:
 478     case Hexagon::STw_GP_cdnNotPt_V4:
 479         return QRI->Subtarget.hasV4TOps();
 480   }
 481   return false;
 482 }
 483
 484 static bool IsLoopN(MachineInstr *MI) {
 485   return (MI->getOpcode() == Hexagon::LOOP0_i ||
 486           MI->getOpcode() == Hexagon::LOOP0_r);
 487 }
 488
 489 /// DoesModifyCalleeSavedReg - Returns true if the instruction modifies a
 490 /// callee-saved register.
 491 static bool DoesModifyCalleeSavedReg(MachineInstr *MI,
 492                                      const TargetRegisterInfo *TRI) {
 493   for (const uint16_t *CSR = TRI->getCalleeSavedRegs(); *CSR; ++CSR) {
 494     unsigned CalleeSavedReg = *CSR;
 495     if (MI->modifiesRegister(CalleeSavedReg, TRI))
 496       return true;
 497   }
 498   return false;
 499 }
 500
 501 // Returns true if an instruction can be promoted to .new predicate
 502 // or new-value store.
 503 bool HexagonPacketizerList::isNewifiable(MachineInstr* MI) {
 504   if ( isCondInst(MI) || IsNewifyStore(MI))
 505     return true;
 506   else
 507     return false;
 508 }
 509
 510 bool HexagonPacketizerList::isCondInst (MachineInstr* MI) {
 511   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 512   const MCInstrDesc& TID = MI->getDesc();
 513                                     // bug 5670: until that is fixed,
 514                                     // this portion is disabled.
 515   if (   TID.isConditionalBranch()  // && !IsRegisterJump(MI)) ||
 516       || QII->isConditionalTransfer(MI)
 517       || QII->isConditionalALU32(MI)
 518       || QII->isConditionalLoad(MI)
 519       || QII->isConditionalStore(MI)) {
 520     return true;
 521   }
 522   return false;
 523 }
 524
 525
 526 // Promote an instructiont to its .new form.
 527 // At this time, we have already made a call to CanPromoteToDotNew
 528 // and made sure that it can *indeed* be promoted.
 529 bool HexagonPacketizerList::PromoteToDotNew(MachineInstr* MI,
 530                         SDep::Kind DepType, MachineBasicBlock::iterator &MII,
 531                         const TargetRegisterClass* RC) {
 532
 533   assert (DepType == SDep::Data);
 534   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
 535
 536   int NewOpcode;
 537   if (RC == &Hexagon::PredRegsRegClass)
 538     NewOpcode = QII->GetDotNewPredOp(MI, MBPI);
 539   else
 540     NewOpcode = QII->GetDotNewOp(MI);
 541   MI->setDesc(QII->get(NewOpcode));
 542
 543   return true;
 544 }
 545
 546 // Returns the most basic instruction for the .new predicated instructions and
 547 // new-value stores.
 548 // For example, all of the following instructions will be converted back to the
 549 // same instruction:
 550 // 1) if (p0.new) memw(R0+#0) = R1.new  --->
 551 // 2) if (p0) memw(R0+#0)= R1.new      -------> if (p0) memw(R0+#0) = R1
 552 // 3) if (p0.new) memw(R0+#0) = R1      --->
 553 //
 554 // To understand the translation of instruction 1 to its original form, consider
 555 // a packet with 3 instructions.
 556 // { p0 = cmp.eq(R0,R1)
 557 //   if (p0.new) R2 = add(R3, R4)
 558 //   R5 = add (R3, R1)
 559 //   }
 560 // if (p0) memw(R5+#0) = R2 <--- trying to include it in the previous packet
 561 //
 562 // This instruction can be part of the previous packet only if both p0 and R2
 563 // are promoted to .new values. This promotion happens in steps, first
 564 // predicate register is promoted to .new and in the next iteration R2 is
 565 // promoted. Therefore, in case of dependence check failure (due to R5) during
 566 // next iteration, it should be converted back to its most basic form.
 567
 568 static int GetDotOldOp(const int opc) {
 569   switch (opc) {
 570   default: llvm_unreachable("Unknown .old type");
 571   case Hexagon::TFR_cdnPt:
 572     return Hexagon::TFR_cPt;
 573
 574   case Hexagon::TFR_cdnNotPt:
 575     return Hexagon::TFR_cNotPt;
 576
 577   case Hexagon::TFRI_cdnPt:
 578     return Hexagon::TFRI_cPt;
 579
 580   case Hexagon::TFRI_cdnNotPt:
 581     return Hexagon::TFRI_cNotPt;
 582
 583   case Hexagon::JMP_tnew_t:
 584     return Hexagon::JMP_t;
 585
 586   case Hexagon::JMP_fnew_t:
 587     return Hexagon::JMP_f;
 588
 589   case Hexagon::JMPR_tnew_tV3:
 590     return Hexagon::JMPR_t;
 591
 592   case Hexagon::JMPR_fnew_tV3:
 593     return Hexagon::JMPR_f;
 594
 595   // Load double word
 596
 597   case Hexagon::LDrid_cdnPt :
 598     return Hexagon::LDrid_cPt;
 599
 600   case Hexagon::LDrid_cdnNotPt :
 601     return Hexagon::LDrid_cNotPt;
 602
 603   case Hexagon::LDrid_indexed_cdnPt :
 604     return Hexagon::LDrid_indexed_cPt;
 605
 606   case Hexagon::LDrid_indexed_cdnNotPt :
 607     return Hexagon::LDrid_indexed_cNotPt;
 608
 609   case Hexagon::POST_LDrid_cdnPt_V4 :
 610     return Hexagon::POST_LDrid_cPt;
 611
 612   case Hexagon::POST_LDrid_cdnNotPt_V4 :
 613     return Hexagon::POST_LDrid_cNotPt;
 614
 615   // Load word
 616
 617   case Hexagon::LDriw_cdnPt :
 618     return Hexagon::LDriw_cPt;
 619
 620   case Hexagon::LDriw_cdnNotPt :
 621     return Hexagon::LDriw_cNotPt;
 622
 623   case Hexagon::LDriw_indexed_cdnPt :
 624     return Hexagon::LDriw_indexed_cPt;
 625
 626   case Hexagon::LDriw_indexed_cdnNotPt :
 627     return Hexagon::LDriw_indexed_cNotPt;
 628
 629   case Hexagon::POST_LDriw_cdnPt_V4 :
 630     return Hexagon::POST_LDriw_cPt;
 631
 632   case Hexagon::POST_LDriw_cdnNotPt_V4 :
 633     return Hexagon::POST_LDriw_cNotPt;
 634
 635   // Load half
 636
 637   case Hexagon::LDrih_cdnPt :
 638     return Hexagon::LDrih_cPt;
 639
 640   case Hexagon::LDrih_cdnNotPt :
 641     return Hexagon::LDrih_cNotPt;
 642
 643   case Hexagon::LDrih_indexed_cdnPt :
 644     return Hexagon::LDrih_indexed_cPt;
 645
 646   case Hexagon::LDrih_indexed_cdnNotPt :
 647     return Hexagon::LDrih_indexed_cNotPt;
 648
 649   case Hexagon::POST_LDrih_cdnPt_V4 :
 650     return Hexagon::POST_LDrih_cPt;
 651
 652   case Hexagon::POST_LDrih_cdnNotPt_V4 :
 653     return Hexagon::POST_LDrih_cNotPt;
 654
 655   // Load byte
 656
 657   case Hexagon::LDrib_cdnPt :
 658     return Hexagon::LDrib_cPt;
 659
 660   case Hexagon::LDrib_cdnNotPt :
 661     return Hexagon::LDrib_cNotPt;
 662
 663   case Hexagon::LDrib_indexed_cdnPt :
 664     return Hexagon::LDrib_indexed_cPt;
 665
 666   case Hexagon::LDrib_indexed_cdnNotPt :
 667     return Hexagon::LDrib_indexed_cNotPt;
 668
 669   case Hexagon::POST_LDrib_cdnPt_V4 :
 670     return Hexagon::POST_LDrib_cPt;
 671
 672   case Hexagon::POST_LDrib_cdnNotPt_V4 :
 673     return Hexagon::POST_LDrib_cNotPt;
 674
 675   // Load unsigned half
 676
 677   case Hexagon::LDriuh_cdnPt :
 678     return Hexagon::LDriuh_cPt;
 679
 680   case Hexagon::LDriuh_cdnNotPt :
 681     return Hexagon::LDriuh_cNotPt;
 682
 683   case Hexagon::LDriuh_indexed_cdnPt :
 684     return Hexagon::LDriuh_indexed_cPt;
 685
 686   case Hexagon::LDriuh_indexed_cdnNotPt :
 687     return Hexagon::LDriuh_indexed_cNotPt;
 688
 689   case Hexagon::POST_LDriuh_cdnPt_V4 :
 690     return Hexagon::POST_LDriuh_cPt;
 691
 692   case Hexagon::POST_LDriuh_cdnNotPt_V4 :
 693     return Hexagon::POST_LDriuh_cNotPt;
 694
 695   // Load unsigned byte
 696   case Hexagon::LDriub_cdnPt :
 697     return Hexagon::LDriub_cPt;
 698
 699   case Hexagon::LDriub_cdnNotPt :
 700     return Hexagon::LDriub_cNotPt;
 701
 702   case Hexagon::LDriub_indexed_cdnPt :
 703     return Hexagon::LDriub_indexed_cPt;
 704
 705   case Hexagon::LDriub_indexed_cdnNotPt :
 706     return Hexagon::LDriub_indexed_cNotPt;
 707
 708   case Hexagon::POST_LDriub_cdnPt_V4 :
 709     return Hexagon::POST_LDriub_cPt;
 710
 711   case Hexagon::POST_LDriub_cdnNotPt_V4 :
 712     return Hexagon::POST_LDriub_cNotPt;
 713
 714   // V4 indexed+scaled Load
 715
 716   case Hexagon::LDrid_indexed_shl_cdnPt_V4 :
 717     return Hexagon::LDrid_indexed_shl_cPt_V4;
 718
 719   case Hexagon::LDrid_indexed_shl_cdnNotPt_V4 :
 720     return Hexagon::LDrid_indexed_shl_cNotPt_V4;
 721
 722   case Hexagon::LDrib_indexed_shl_cdnPt_V4 :
 723     return Hexagon::LDrib_indexed_shl_cPt_V4;
 724
 725   case Hexagon::LDrib_indexed_shl_cdnNotPt_V4 :
 726     return Hexagon::LDrib_indexed_shl_cNotPt_V4;
 727
 728   case Hexagon::LDriub_indexed_shl_cdnPt_V4 :
 729     return Hexagon::LDriub_indexed_shl_cPt_V4;
 730
 731   case Hexagon::LDriub_indexed_shl_cdnNotPt_V4 :
 732     return Hexagon::LDriub_indexed_shl_cNotPt_V4;
 733
 734   case Hexagon::LDrih_indexed_shl_cdnPt_V4 :
 735     return Hexagon::LDrih_indexed_shl_cPt_V4;
 736
 737   case Hexagon::LDrih_indexed_shl_cdnNotPt_V4 :
 738     return Hexagon::LDrih_indexed_shl_cNotPt_V4;
 739
 740   case Hexagon::LDriuh_indexed_shl_cdnPt_V4 :
 741     return Hexagon::LDriuh_indexed_shl_cPt_V4;
 742
 743   case Hexagon::LDriuh_indexed_shl_cdnNotPt_V4 :
 744     return Hexagon::LDriuh_indexed_shl_cNotPt_V4;
 745
 746   case Hexagon::LDriw_indexed_shl_cdnPt_V4 :
 747     return Hexagon::LDriw_indexed_shl_cPt_V4;
 748
 749   case Hexagon::LDriw_indexed_shl_cdnNotPt_V4 :
 750     return Hexagon::LDriw_indexed_shl_cNotPt_V4;
 751
 752   // V4 global address load
 753
 754   case Hexagon::LDd_GP_cdnPt_V4:
 755     return Hexagon::LDd_GP_cPt_V4;
 756
 757   case Hexagon::LDd_GP_cdnNotPt_V4:
 758     return Hexagon::LDd_GP_cNotPt_V4;
 759
 760   case Hexagon::LDb_GP_cdnPt_V4:
 761     return Hexagon::LDb_GP_cPt_V4;
 762
 763   case Hexagon::LDb_GP_cdnNotPt_V4:
 764     return Hexagon::LDb_GP_cNotPt_V4;
 765
 766   case Hexagon::LDub_GP_cdnPt_V4:
 767     return Hexagon::LDub_GP_cPt_V4;
 768
 769   case Hexagon::LDub_GP_cdnNotPt_V4:
 770     return Hexagon::LDub_GP_cNotPt_V4;
 771
 772   case Hexagon::LDh_GP_cdnPt_V4:
 773     return Hexagon::LDh_GP_cPt_V4;
 774
 775   case Hexagon::LDh_GP_cdnNotPt_V4:
 776     return Hexagon::LDh_GP_cNotPt_V4;
 777
 778   case Hexagon::LDuh_GP_cdnPt_V4:
 779     return Hexagon::LDuh_GP_cPt_V4;
 780
 781   case Hexagon::LDuh_GP_cdnNotPt_V4:
 782     return Hexagon::LDuh_GP_cNotPt_V4;
 783
 784   case Hexagon::LDw_GP_cdnPt_V4:
 785     return Hexagon::LDw_GP_cPt_V4;
 786
 787   case Hexagon::LDw_GP_cdnNotPt_V4:
 788     return Hexagon::LDw_GP_cNotPt_V4;
 789
 790   // Conditional add
 791
 792   case Hexagon::ADD_ri_cdnPt :
 793     return Hexagon::ADD_ri_cPt;
 794   case Hexagon::ADD_ri_cdnNotPt :
 795     return Hexagon::ADD_ri_cNotPt;
 796
 797   case Hexagon::ADD_rr_cdnPt :
 798     return Hexagon::ADD_rr_cPt;
 799   case Hexagon::ADD_rr_cdnNotPt:
 800     return Hexagon::ADD_rr_cNotPt;
 801
 802   // Conditional logical Operations
 803
 804   case Hexagon::XOR_rr_cdnPt :
 805     return Hexagon::XOR_rr_cPt;
 806   case Hexagon::XOR_rr_cdnNotPt :
 807     return Hexagon::XOR_rr_cNotPt;
 808
 809   case Hexagon::AND_rr_cdnPt :
 810     return Hexagon::AND_rr_cPt;
 811   case Hexagon::AND_rr_cdnNotPt :
 812     return Hexagon::AND_rr_cNotPt;
 813
 814   case Hexagon::OR_rr_cdnPt :
 815     return Hexagon::OR_rr_cPt;
 816   case Hexagon::OR_rr_cdnNotPt :
 817     return Hexagon::OR_rr_cNotPt;
 818
 819   // Conditional Subtract
 820
 821   case Hexagon::SUB_rr_cdnPt :
 822     return Hexagon::SUB_rr_cPt;
 823   case Hexagon::SUB_rr_cdnNotPt :
 824     return Hexagon::SUB_rr_cNotPt;
 825
 826   // Conditional combine
 827
 828   case Hexagon::COMBINE_rr_cdnPt :
 829     return Hexagon::COMBINE_rr_cPt;
 830   case Hexagon::COMBINE_rr_cdnNotPt :
 831     return Hexagon::COMBINE_rr_cNotPt;
 832
 833 // Conditional shift operations
 834
 835   case Hexagon::ASLH_cdnPt_V4 :
 836     return Hexagon::ASLH_cPt_V4;
 837   case Hexagon::ASLH_cdnNotPt_V4 :
 838     return Hexagon::ASLH_cNotPt_V4;
 839
 840   case Hexagon::ASRH_cdnPt_V4 :
 841     return Hexagon::ASRH_cPt_V4;
 842   case Hexagon::ASRH_cdnNotPt_V4 :
 843     return Hexagon::ASRH_cNotPt_V4;
 844
 845   case Hexagon::SXTB_cdnPt_V4 :
 846     return Hexagon::SXTB_cPt_V4;
 847   case Hexagon::SXTB_cdnNotPt_V4 :
 848     return Hexagon::SXTB_cNotPt_V4;
 849
 850   case Hexagon::SXTH_cdnPt_V4 :
 851     return Hexagon::SXTH_cPt_V4;
 852   case Hexagon::SXTH_cdnNotPt_V4 :
 853     return Hexagon::SXTH_cNotPt_V4;
 854
 855   case Hexagon::ZXTB_cdnPt_V4 :
 856     return Hexagon::ZXTB_cPt_V4;
 857   case Hexagon::ZXTB_cdnNotPt_V4 :
 858     return Hexagon::ZXTB_cNotPt_V4;
 859
 860   case Hexagon::ZXTH_cdnPt_V4 :
 861     return Hexagon::ZXTH_cPt_V4;
 862   case Hexagon::ZXTH_cdnNotPt_V4 :
 863     return Hexagon::ZXTH_cNotPt_V4;
 864
 865   // Store byte
 866
 867   case Hexagon::STrib_imm_cdnPt_V4 :
 868     return Hexagon::STrib_imm_cPt_V4;
 869
 870   case Hexagon::STrib_imm_cdnNotPt_V4 :
 871     return Hexagon::STrib_imm_cNotPt_V4;
 872
 873   case Hexagon::STrib_cdnPt_nv_V4 :
 874   case Hexagon::STrib_cPt_nv_V4 :
 875   case Hexagon::STrib_cdnPt_V4 :
 876     return Hexagon::STrib_cPt;
 877
 878   case Hexagon::STrib_cdnNotPt_nv_V4 :
 879   case Hexagon::STrib_cNotPt_nv_V4 :
 880   case Hexagon::STrib_cdnNotPt_V4 :
 881     return Hexagon::STrib_cNotPt;
 882
 883   case Hexagon::STrib_indexed_cdnPt_V4 :
 884   case Hexagon::STrib_indexed_cPt_nv_V4 :
 885   case Hexagon::STrib_indexed_cdnPt_nv_V4 :
 886     return Hexagon::STrib_indexed_cPt;
 887
 888   case Hexagon::STrib_indexed_cdnNotPt_V4 :
 889   case Hexagon::STrib_indexed_cNotPt_nv_V4 :
 890   case Hexagon::STrib_indexed_cdnNotPt_nv_V4 :
 891     return Hexagon::STrib_indexed_cNotPt;
 892
 893   case Hexagon::STrib_indexed_shl_cdnPt_nv_V4:
 894   case Hexagon::STrib_indexed_shl_cPt_nv_V4 :
 895   case Hexagon::STrib_indexed_shl_cdnPt_V4 :
 896     return Hexagon::STrib_indexed_shl_cPt_V4;
 897
 898   case Hexagon::STrib_indexed_shl_cdnNotPt_nv_V4:
 899   case Hexagon::STrib_indexed_shl_cNotPt_nv_V4 :
 900   case Hexagon::STrib_indexed_shl_cdnNotPt_V4 :
 901     return Hexagon::STrib_indexed_shl_cNotPt_V4;
 902
 903   case Hexagon::POST_STbri_cdnPt_nv_V4 :
 904   case Hexagon::POST_STbri_cPt_nv_V4 :
 905   case Hexagon::POST_STbri_cdnPt_V4 :
 906     return Hexagon::POST_STbri_cPt;
 907
 908   case Hexagon::POST_STbri_cdnNotPt_nv_V4 :
 909   case Hexagon::POST_STbri_cNotPt_nv_V4:
 910   case Hexagon::POST_STbri_cdnNotPt_V4 :
 911     return Hexagon::POST_STbri_cNotPt;
 912
 913   case Hexagon::STb_GP_cdnPt_nv_V4:
 914   case Hexagon::STb_GP_cdnPt_V4:
 915   case Hexagon::STb_GP_cPt_nv_V4:
 916     return Hexagon::STb_GP_cPt_V4;
 917
 918   case Hexagon::STb_GP_cdnNotPt_nv_V4:
 919   case Hexagon::STb_GP_cdnNotPt_V4:
 920   case Hexagon::STb_GP_cNotPt_nv_V4:
 921     return Hexagon::STb_GP_cNotPt_V4;
 922
 923   // Store new-value byte - unconditional
 924   case Hexagon::STrib_nv_V4:
 925     return Hexagon::STrib;
 926
 927   case Hexagon::STrib_indexed_nv_V4:
 928     return Hexagon::STrib_indexed;
 929
 930   case Hexagon::STrib_indexed_shl_nv_V4:
 931     return Hexagon::STrib_indexed_shl_V4;
 932
 933   case Hexagon::STrib_shl_nv_V4:
 934     return Hexagon::STrib_shl_V4;
 935
 936   case Hexagon::STb_GP_nv_V4:
 937     return Hexagon::STb_GP_V4;
 938
 939   case Hexagon::POST_STbri_nv_V4:
 940     return Hexagon::POST_STbri;
 941
 942   // Store halfword
 943   case Hexagon::STrih_imm_cdnPt_V4 :
 944     return Hexagon::STrih_imm_cPt_V4;
 945
 946   case Hexagon::STrih_imm_cdnNotPt_V4 :
 947     return Hexagon::STrih_imm_cNotPt_V4;
 948
 949   case Hexagon::STrih_cdnPt_nv_V4 :
 950   case Hexagon::STrih_cPt_nv_V4 :
 951   case Hexagon::STrih_cdnPt_V4 :
 952     return Hexagon::STrih_cPt;
 953
 954   case Hexagon::STrih_cdnNotPt_nv_V4 :
 955   case Hexagon::STrih_cNotPt_nv_V4 :
 956   case Hexagon::STrih_cdnNotPt_V4 :
 957     return Hexagon::STrih_cNotPt;
 958
 959   case Hexagon::STrih_indexed_cdnPt_nv_V4:
 960   case Hexagon::STrih_indexed_cPt_nv_V4 :
 961   case Hexagon::STrih_indexed_cdnPt_V4 :
 962     return Hexagon::STrih_indexed_cPt;
 963
 964   case Hexagon::STrih_indexed_cdnNotPt_nv_V4:
 965   case Hexagon::STrih_indexed_cNotPt_nv_V4 :
 966   case Hexagon::STrih_indexed_cdnNotPt_V4 :
 967     return Hexagon::STrih_indexed_cNotPt;
 968
 969   case Hexagon::STrih_indexed_shl_cdnPt_nv_V4 :
 970   case Hexagon::STrih_indexed_shl_cPt_nv_V4 :
 971   case Hexagon::STrih_indexed_shl_cdnPt_V4 :
 972     return Hexagon::STrih_indexed_shl_cPt_V4;
 973
 974   case Hexagon::STrih_indexed_shl_cdnNotPt_nv_V4 :
 975   case Hexagon::STrih_indexed_shl_cNotPt_nv_V4 :
 976   case Hexagon::STrih_indexed_shl_cdnNotPt_V4 :
 977     return Hexagon::STrih_indexed_shl_cNotPt_V4;
 978
 979   case Hexagon::POST_SThri_cdnPt_nv_V4 :
 980   case Hexagon::POST_SThri_cPt_nv_V4 :
 981   case Hexagon::POST_SThri_cdnPt_V4 :
 982     return Hexagon::POST_SThri_cPt;
 983
 984   case Hexagon::POST_SThri_cdnNotPt_nv_V4 :
 985   case Hexagon::POST_SThri_cNotPt_nv_V4 :
 986   case Hexagon::POST_SThri_cdnNotPt_V4 :
 987     return Hexagon::POST_SThri_cNotPt;
 988
 989   case Hexagon::STh_GP_cdnPt_nv_V4:
 990   case Hexagon::STh_GP_cdnPt_V4:
 991   case Hexagon::STh_GP_cPt_nv_V4:
 992     return Hexagon::STh_GP_cPt_V4;
 993
 994   case Hexagon::STh_GP_cdnNotPt_nv_V4:
 995   case Hexagon::STh_GP_cdnNotPt_V4:
 996   case Hexagon::STh_GP_cNotPt_nv_V4:
 997     return Hexagon::STh_GP_cNotPt_V4;
 998
 999   // Store new-value halfword - unconditional
1000
1001   case Hexagon::STrih_nv_V4:
1002     return Hexagon::STrih;
1003
1004   case Hexagon::STrih_indexed_nv_V4:
1005     return Hexagon::STrih_indexed;
1006
1007   case Hexagon::STrih_indexed_shl_nv_V4:
1008     return Hexagon::STrih_indexed_shl_V4;
1009
1010   case Hexagon::STrih_shl_nv_V4:
1011     return Hexagon::STrih_shl_V4;
1012
1013   case Hexagon::STh_GP_nv_V4:
1014     return Hexagon::STh_GP_V4;
1015
1016   case Hexagon::POST_SThri_nv_V4:
1017     return Hexagon::POST_SThri;
1018
1019    // Store word
1020
1021    case Hexagon::STriw_imm_cdnPt_V4 :
1022     return Hexagon::STriw_imm_cPt_V4;
1023
1024   case Hexagon::STriw_imm_cdnNotPt_V4 :
1025     return Hexagon::STriw_imm_cNotPt_V4;
1026
1027   case Hexagon::STriw_cdnPt_nv_V4 :
1028   case Hexagon::STriw_cPt_nv_V4 :
1029   case Hexagon::STriw_cdnPt_V4 :
1030     return Hexagon::STriw_cPt;
1031
1032   case Hexagon::STriw_cdnNotPt_nv_V4 :
1033   case Hexagon::STriw_cNotPt_nv_V4 :
1034   case Hexagon::STriw_cdnNotPt_V4 :
1035     return Hexagon::STriw_cNotPt;
1036
1037   case Hexagon::STriw_indexed_cdnPt_nv_V4 :
1038   case Hexagon::STriw_indexed_cPt_nv_V4 :
1039   case Hexagon::STriw_indexed_cdnPt_V4 :
1040     return Hexagon::STriw_indexed_cPt;
1041
1042   case Hexagon::STriw_indexed_cdnNotPt_nv_V4 :
1043   case Hexagon::STriw_indexed_cNotPt_nv_V4 :
1044   case Hexagon::STriw_indexed_cdnNotPt_V4 :
1045     return Hexagon::STriw_indexed_cNotPt;
1046
1047   case Hexagon::STriw_indexed_shl_cdnPt_nv_V4 :
1048   case Hexagon::STriw_indexed_shl_cPt_nv_V4 :
1049   case Hexagon::STriw_indexed_shl_cdnPt_V4 :
1050     return Hexagon::STriw_indexed_shl_cPt_V4;
1051
1052   case Hexagon::STriw_indexed_shl_cdnNotPt_nv_V4 :
1053   case Hexagon::STriw_indexed_shl_cNotPt_nv_V4 :
1054   case Hexagon::STriw_indexed_shl_cdnNotPt_V4 :
1055     return Hexagon::STriw_indexed_shl_cNotPt_V4;
1056
1057   case Hexagon::POST_STwri_cdnPt_nv_V4 :
1058   case Hexagon::POST_STwri_cPt_nv_V4 :
1059   case Hexagon::POST_STwri_cdnPt_V4 :
1060     return Hexagon::POST_STwri_cPt;
1061
1062   case Hexagon::POST_STwri_cdnNotPt_nv_V4 :
1063   case Hexagon::POST_STwri_cNotPt_nv_V4 :
1064   case Hexagon::POST_STwri_cdnNotPt_V4 :
1065     return Hexagon::POST_STwri_cNotPt;
1066
1067   case Hexagon::STw_GP_cdnPt_nv_V4:
1068   case Hexagon::STw_GP_cdnPt_V4:
1069   case Hexagon::STw_GP_cPt_nv_V4:
1070     return Hexagon::STw_GP_cPt_V4;
1071
1072   case Hexagon::STw_GP_cdnNotPt_nv_V4:
1073   case Hexagon::STw_GP_cdnNotPt_V4:
1074   case Hexagon::STw_GP_cNotPt_nv_V4:
1075     return Hexagon::STw_GP_cNotPt_V4;
1076
1077   // Store new-value word - unconditional
1078
1079   case Hexagon::STriw_nv_V4:
1080     return Hexagon::STriw;
1081
1082   case Hexagon::STriw_indexed_nv_V4:
1083     return Hexagon::STriw_indexed;
1084
1085   case Hexagon::STriw_indexed_shl_nv_V4:
1086     return Hexagon::STriw_indexed_shl_V4;
1087
1088   case Hexagon::STriw_shl_nv_V4:
1089     return Hexagon::STriw_shl_V4;
1090
1091   case Hexagon::STw_GP_nv_V4:
1092     return Hexagon::STw_GP_V4;
1093
1094   case Hexagon::POST_STwri_nv_V4:
1095     return Hexagon::POST_STwri;
1096
1097  // Store doubleword
1098
1099   case Hexagon::STrid_cdnPt_V4 :
1100     return Hexagon::STrid_cPt;
1101
1102   case Hexagon::STrid_cdnNotPt_V4 :
1103     return Hexagon::STrid_cNotPt;
1104
1105   case Hexagon::STrid_indexed_cdnPt_V4 :
1106     return Hexagon::STrid_indexed_cPt;
1107
1108   case Hexagon::STrid_indexed_cdnNotPt_V4 :
1109     return Hexagon::STrid_indexed_cNotPt;
1110
1111   case Hexagon::STrid_indexed_shl_cdnPt_V4 :
1112     return Hexagon::STrid_indexed_shl_cPt_V4;
1113
1114   case Hexagon::STrid_indexed_shl_cdnNotPt_V4 :
1115     return Hexagon::STrid_indexed_shl_cNotPt_V4;
1116
1117   case Hexagon::POST_STdri_cdnPt_V4 :
1118     return Hexagon::POST_STdri_cPt;
1119
1120   case Hexagon::POST_STdri_cdnNotPt_V4 :
1121     return Hexagon::POST_STdri_cNotPt;
1122
1123   case Hexagon::STd_GP_cdnPt_V4 :
1124     return Hexagon::STd_GP_cPt_V4;
1125
1126   case Hexagon::STd_GP_cdnNotPt_V4 :
1127     return Hexagon::STd_GP_cNotPt_V4;
1128
1129   }
1130 }
1131
1132 bool HexagonPacketizerList::DemoteToDotOld(MachineInstr* MI) {
1133   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1134   int NewOpcode = GetDotOldOp(MI->getOpcode());
1135   MI->setDesc(QII->get(NewOpcode));
1136   return true;
1137 }
1138
1139 enum PredicateKind {
1140   PK_False,
1141   PK_True,
1142   PK_Unknown
1143 };
1144
1145 /// Returns true if an instruction is predicated on p0 and false if it's
1146 /// predicated on !p0.
1147 static PredicateKind getPredicateSense(MachineInstr* MI,
1148                                        const HexagonInstrInfo *QII) {
1149   if (!QII->isPredicated(MI))
1150     return PK_Unknown;
1151
1152   if (QII->isPredicatedTrue(MI))
1153     return PK_True;
1154
1155   return PK_False;
1156 }
1157
1158 static MachineOperand& GetPostIncrementOperand(MachineInstr *MI,
1159                                                const HexagonInstrInfo *QII) {
1160   assert(QII->isPostIncrement(MI) && "Not a post increment operation.");
1161 #ifndef NDEBUG
1162   // Post Increment means duplicates. Use dense map to find duplicates in the
1163   // list. Caution: Densemap initializes with the minimum of 64 buckets,
1164   // whereas there are at most 5 operands in the post increment.
1165   DenseMap<unsigned,  unsigned> DefRegsSet;
1166   for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++)
1167     if (MI->getOperand(opNum).isReg() &&
1168         MI->getOperand(opNum).isDef()) {
1169       DefRegsSet[MI->getOperand(opNum).getReg()] = 1;
1170     }
1171
1172   for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++)
1173     if (MI->getOperand(opNum).isReg() &&
1174         MI->getOperand(opNum).isUse()) {
1175       if (DefRegsSet[MI->getOperand(opNum).getReg()]) {
1176         return MI->getOperand(opNum);
1177       }
1178     }
1179 #else
1180   if (MI->getDesc().mayLoad()) {
1181     // The 2nd operand is always the post increment operand in load.
1182     assert(MI->getOperand(1).isReg() &&
1183                 "Post increment operand has be to a register.");
1184     return (MI->getOperand(1));
1185   }
1186   if (MI->getDesc().mayStore()) {
1187     // The 1st operand is always the post increment operand in store.
1188     assert(MI->getOperand(0).isReg() &&
1189                 "Post increment operand has be to a register.");
1190     return (MI->getOperand(0));
1191   }
1192 #endif
1193   // we should never come here.
1194   llvm_unreachable("mayLoad or mayStore not set for Post Increment operation");
1195 }
1196
1197 // get the value being stored
1198 static MachineOperand& GetStoreValueOperand(MachineInstr *MI) {
1199   // value being stored is always the last operand.
1200   return (MI->getOperand(MI->getNumOperands()-1));
1201 }
1202
1203 // can be new value store?
1204 // Following restrictions are to be respected in convert a store into
1205 // a new value store.
1206 // 1. If an instruction uses auto-increment, its address register cannot
1207 //    be a new-value register. Arch Spec 5.4.2.1
1208 // 2. If an instruction uses absolute-set addressing mode,
1209 //    its address register cannot be a new-value register.
1210 //    Arch Spec 5.4.2.1.TODO: This is not enabled as
1211 //    as absolute-set address mode patters are not implemented.
1212 // 3. If an instruction produces a 64-bit result, its registers cannot be used
1213 //    as new-value registers. Arch Spec 5.4.2.2.
1214 // 4. If the instruction that sets a new-value register is conditional, then
1215 //    the instruction that uses the new-value register must also be conditional,
1216 //    and both must always have their predicates evaluate identically.
1217 //    Arch Spec 5.4.2.3.
1218 // 5. There is an implied restriction of a packet can not have another store,
1219 //    if there is a  new value store in the packet. Corollary, if there is
1220 //    already a store in a packet, there can not be a new value store.
1221 //    Arch Spec: 3.4.4.2
1222 bool HexagonPacketizerList::CanPromoteToNewValueStore( MachineInstr *MI,
1223                 MachineInstr *PacketMI, unsigned DepReg,
1224                 std::map <MachineInstr*, SUnit*> MIToSUnit)
1225 {
1226   // Make sure we are looking at the store
1227   if (!IsNewifyStore(MI))
1228     return false;
1229
1230   // Make sure there is dependency and can be new value'ed
1231   if (GetStoreValueOperand(MI).isReg() &&
1232       GetStoreValueOperand(MI).getReg() != DepReg)
1233     return false;
1234
1235   const HexagonRegisterInfo* QRI =
1236                             (const HexagonRegisterInfo *) TM.getRegisterInfo();
1237   const MCInstrDesc& MCID = PacketMI->getDesc();
1238   // first operand is always the result
1239
1240   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1241   const TargetRegisterClass* PacketRC = QII->getRegClass(MCID, 0, QRI, MF);
1242
1243   // if there is already an store in the packet, no can do new value store
1244   // Arch Spec 3.4.4.2.
1245   for (std::vector<MachineInstr*>::iterator VI = CurrentPacketMIs.begin(),
1246          VE = CurrentPacketMIs.end();
1247        (VI != VE); ++VI) {
1248     SUnit* PacketSU = MIToSUnit[*VI];
1249     if (PacketSU->getInstr()->getDesc().mayStore() ||
1250         // if we have mayStore = 1 set on ALLOCFRAME and DEALLOCFRAME,
1251         // then we don't need this
1252         PacketSU->getInstr()->getOpcode() == Hexagon::ALLOCFRAME ||
1253         PacketSU->getInstr()->getOpcode() == Hexagon::DEALLOCFRAME)
1254       return false;
1255   }
1256
1257   if (PacketRC == &Hexagon::DoubleRegsRegClass) {
1258     // new value store constraint: double regs can not feed into new value store
1259     // arch spec section: 5.4.2.2
1260     return false;
1261   }
1262
1263   // Make sure it's NOT the post increment register that we are going to
1264   // new value.
1265   if (QII->isPostIncrement(MI) &&
1266       MI->getDesc().mayStore() &&
1267       GetPostIncrementOperand(MI, QII).getReg() == DepReg) {
1268     return false;
1269   }
1270
1271   if (QII->isPostIncrement(PacketMI) &&
1272       PacketMI->getDesc().mayLoad() &&
1273       GetPostIncrementOperand(PacketMI, QII).getReg() == DepReg) {
1274     // if source is post_inc, or absolute-set addressing,
1275     // it can not feed into new value store
1276     //  r3 = memw(r2++#4)
1277     //  memw(r30 + #-1404) = r2.new -> can not be new value store
1278     // arch spec section: 5.4.2.1
1279     return false;
1280   }
1281
1282   // If the source that feeds the store is predicated, new value store must
1283   // also be also predicated.
1284   if (QII->isPredicated(PacketMI)) {
1285     if (!QII->isPredicated(MI))
1286       return false;
1287
1288     // Check to make sure that they both will have their predicates
1289     // evaluate identically
1290     unsigned predRegNumSrc = 0;
1291     unsigned predRegNumDst = 0;
1292     const TargetRegisterClass* predRegClass = NULL;
1293
1294     // Get predicate register used in the source instruction
1295     for(unsigned opNum = 0; opNum < PacketMI->getNumOperands(); opNum++) {
1296       if ( PacketMI->getOperand(opNum).isReg())
1297       predRegNumSrc = PacketMI->getOperand(opNum).getReg();
1298       predRegClass = QRI->getMinimalPhysRegClass(predRegNumSrc);
1299       if (predRegClass == &Hexagon::PredRegsRegClass) {
1300         break;
1301       }
1302     }
1303     assert ((predRegClass == &Hexagon::PredRegsRegClass ) &&
1304         ("predicate register not found in a predicated PacketMI instruction"));
1305
1306     // Get predicate register used in new-value store instruction
1307     for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) {
1308       if ( MI->getOperand(opNum).isReg())
1309       predRegNumDst = MI->getOperand(opNum).getReg();
1310       predRegClass = QRI->getMinimalPhysRegClass(predRegNumDst);
1311       if (predRegClass == &Hexagon::PredRegsRegClass) {
1312         break;
1313       }
1314     }
1315     assert ((predRegClass == &Hexagon::PredRegsRegClass ) &&
1316             ("predicate register not found in a predicated MI instruction"));
1317
1318     // New-value register producer and user (store) need to satisfy these
1319     // constraints:
1320     // 1) Both instructions should be predicated on the same register.
1321     // 2) If producer of the new-value register is .new predicated then store
1322     // should also be .new predicated and if producer is not .new predicated
1323     // then store should not be .new predicated.
1324     // 3) Both new-value register producer and user should have same predicate
1325     // sense, i.e, either both should be negated or both should be none negated.
1326
1327     if (( predRegNumDst != predRegNumSrc) ||
1328           QII->isDotNewInst(PacketMI) != QII->isDotNewInst(MI)  ||
1329           getPredicateSense(MI, QII) != getPredicateSense(PacketMI, QII)) {
1330       return false;
1331     }
1332   }
1333
1334   // Make sure that other than the new-value register no other store instruction
1335   // register has been modified in the same packet. Predicate registers can be
1336   // modified by they should not be modified between the producer and the store
1337   // instruction as it will make them both conditional on different values.
1338   // We already know this to be true for all the instructions before and
1339   // including PacketMI. Howerver, we need to perform the check for the
1340   // remaining instructions in the packet.
1341
1342   std::vector<MachineInstr*>::iterator VI;
1343   std::vector<MachineInstr*>::iterator VE;
1344   unsigned StartCheck = 0;
1345
1346   for (VI=CurrentPacketMIs.begin(), VE = CurrentPacketMIs.end();
1347       (VI != VE); ++VI) {
1348     SUnit* TempSU = MIToSUnit[*VI];
1349     MachineInstr* TempMI = TempSU->getInstr();
1350
1351     // Following condition is true for all the instructions until PacketMI is
1352     // reached (StartCheck is set to 0 before the for loop).
1353     // StartCheck flag is 1 for all the instructions after PacketMI.
1354     if (TempMI != PacketMI && !StartCheck) // start processing only after
1355       continue;                            // encountering PacketMI
1356
1357     StartCheck = 1;
1358     if (TempMI == PacketMI) // We don't want to check PacketMI for dependence
1359       continue;
1360
1361     for(unsigned opNum = 0; opNum < MI->getNumOperands(); opNum++) {
1362       if (MI->getOperand(opNum).isReg() &&
1363           TempSU->getInstr()->modifiesRegister(MI->getOperand(opNum).getReg(),
1364                                                QRI))
1365         return false;
1366     }
1367   }
1368
1369   // Make sure that for non POST_INC stores:
1370   // 1. The only use of reg is DepReg and no other registers.
1371   //    This handles V4 base+index registers.
1372   //    The following store can not be dot new.
1373   //    Eg.   r0 = add(r0, #3)a
1374   //          memw(r1+r0<<#2) = r0
1375   if (!QII->isPostIncrement(MI) &&
1376       GetStoreValueOperand(MI).isReg() &&
1377       GetStoreValueOperand(MI).getReg() == DepReg) {
1378     for(unsigned opNum = 0; opNum < MI->getNumOperands()-1; opNum++) {
1379       if (MI->getOperand(opNum).isReg() &&
1380           MI->getOperand(opNum).getReg() == DepReg) {
1381         return false;
1382       }
1383     }
1384     // 2. If data definition is because of implicit definition of the register,
1385     //    do not newify the store. Eg.
1386     //    %R9<def> = ZXTH %R12, %D6<imp-use>, %R12<imp-def>
1387     //    STrih_indexed %R8, 2, %R12<kill>; mem:ST2[%scevgep343]
1388     for(unsigned opNum = 0; opNum < PacketMI->getNumOperands(); opNum++) {
1389       if (PacketMI->getOperand(opNum).isReg() &&
1390           PacketMI->getOperand(opNum).getReg() == DepReg &&
1391           PacketMI->getOperand(opNum).isDef() &&
1392           PacketMI->getOperand(opNum).isImplicit()) {
1393         return false;
1394       }
1395     }
1396   }
1397
1398   // Can be dot new store.
1399   return true;
1400 }
1401
1402 // can this MI to promoted to either
1403 // new value store or new value jump
1404 bool HexagonPacketizerList::CanPromoteToNewValue( MachineInstr *MI,
1405                 SUnit *PacketSU, unsigned DepReg,
1406                 std::map <MachineInstr*, SUnit*> MIToSUnit,
1407                 MachineBasicBlock::iterator &MII)
1408 {
1409
1410   const HexagonRegisterInfo* QRI =
1411                             (const HexagonRegisterInfo *) TM.getRegisterInfo();
1412   if (!QRI->Subtarget.hasV4TOps() ||
1413       !IsNewifyStore(MI))
1414     return false;
1415
1416   MachineInstr *PacketMI = PacketSU->getInstr();
1417
1418   // Check to see the store can be new value'ed.
1419   if (CanPromoteToNewValueStore(MI, PacketMI, DepReg, MIToSUnit))
1420     return true;
1421
1422   // Check to see the compare/jump can be new value'ed.
1423   // This is done as a pass on its own. Don't need to check it here.
1424   return false;
1425 }
1426
1427 // Check to see if an instruction can be dot new
1428 // There are three kinds.
1429 // 1. dot new on predicate - V2/V3/V4
1430 // 2. dot new on stores NV/ST - V4
1431 // 3. dot new on jump NV/J - V4 -- This is generated in a pass.
1432 bool HexagonPacketizerList::CanPromoteToDotNew( MachineInstr *MI,
1433                               SUnit *PacketSU, unsigned DepReg,
1434                               std::map <MachineInstr*, SUnit*> MIToSUnit,
1435                               MachineBasicBlock::iterator &MII,
1436                               const TargetRegisterClass* RC )
1437 {
1438   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1439   // Already a dot new instruction.
1440   if (QII->isDotNewInst(MI) && !IsNewifyStore(MI))
1441     return false;
1442
1443   if (!isNewifiable(MI))
1444     return false;
1445
1446   // predicate .new
1447   if (RC == &Hexagon::PredRegsRegClass && isCondInst(MI))
1448       return true;
1449   else if (RC != &Hexagon::PredRegsRegClass &&
1450       !IsNewifyStore(MI)) // MI is not a new-value store
1451     return false;
1452   else {
1453     // Create a dot new machine instruction to see if resources can be
1454     // allocated. If not, bail out now.
1455     int NewOpcode = QII->GetDotNewOp(MI);
1456     const MCInstrDesc &desc = QII->get(NewOpcode);
1457     DebugLoc dl;
1458     MachineInstr *NewMI =
1459                     MI->getParent()->getParent()->CreateMachineInstr(desc, dl);
1460     bool ResourcesAvailable = ResourceTracker->canReserveResources(NewMI);
1461     MI->getParent()->getParent()->DeleteMachineInstr(NewMI);
1462
1463     if (!ResourcesAvailable)
1464       return false;
1465
1466     // new value store only
1467     // new new value jump generated as a passes
1468     if (!CanPromoteToNewValue(MI, PacketSU, DepReg, MIToSUnit, MII)) {
1469       return false;
1470     }
1471   }
1472   return true;
1473 }
1474
1475 // Go through the packet instructions and search for anti dependency
1476 // between them and DepReg from MI
1477 // Consider this case:
1478 // Trying to add
1479 // a) %R1<def> = TFRI_cdNotPt %P3, 2
1480 // to this packet:
1481 // {
1482 //   b) %P0<def> = OR_pp %P3<kill>, %P0<kill>
1483 //   c) %P3<def> = TFR_PdRs %R23
1484 //   d) %R1<def> = TFRI_cdnPt %P3, 4
1485 //  }
1486 // The P3 from a) and d) will be complements after
1487 // a)'s P3 is converted to .new form
1488 // Anti Dep between c) and b) is irrelevant for this case
1489 bool HexagonPacketizerList::RestrictingDepExistInPacket (MachineInstr* MI,
1490       unsigned DepReg,
1491       std::map <MachineInstr*, SUnit*> MIToSUnit) {
1492
1493   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1494   SUnit* PacketSUDep = MIToSUnit[MI];
1495
1496   for (std::vector<MachineInstr*>::iterator VIN = CurrentPacketMIs.begin(),
1497        VEN = CurrentPacketMIs.end(); (VIN != VEN); ++VIN) {
1498
1499     // We only care for dependencies to predicated instructions
1500     if(!QII->isPredicated(*VIN)) continue;
1501
1502     // Scheduling Unit for current insn in the packet
1503     SUnit* PacketSU = MIToSUnit[*VIN];
1504
1505     // Look at dependencies between current members of the packet
1506     // and predicate defining instruction MI.
1507     // Make sure that dependency is on the exact register
1508     // we care about.
1509     if (PacketSU->isSucc(PacketSUDep)) {
1510       for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) {
1511         if ((PacketSU->Succs[i].getSUnit() == PacketSUDep) &&
1512             (PacketSU->Succs[i].getKind() == SDep::Anti) &&
1513             (PacketSU->Succs[i].getReg() == DepReg)) {
1514           return true;
1515         }
1516       }
1517     }
1518   }
1519
1520   return false;
1521 }
1522
1523
1524 // Given two predicated instructions, this function detects whether
1525 // the predicates are complements
1526 bool HexagonPacketizerList::ArePredicatesComplements (MachineInstr* MI1,
1527      MachineInstr* MI2, std::map <MachineInstr*, SUnit*> MIToSUnit) {
1528
1529   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1530   // Currently can only reason about conditional transfers
1531   if (!QII->isConditionalTransfer(MI1) || !QII->isConditionalTransfer(MI2)) {
1532     return false;
1533   }
1534
1535   // Scheduling unit for candidate
1536   SUnit* SU = MIToSUnit[MI1];
1537
1538   // One corner case deals with the following scenario:
1539   // Trying to add
1540   // a) %R24<def> = TFR_cPt %P0, %R25
1541   // to this packet:
1542   //
1543   // {
1544   //   b) %R25<def> = TFR_cNotPt %P0, %R24
1545   //   c) %P0<def> = CMPEQri %R26, 1
1546   // }
1547   //
1548   // On general check a) and b) are complements, but
1549   // presence of c) will convert a) to .new form, and
1550   // then it is not a complement
1551   // We attempt to detect it by analyzing  existing
1552   // dependencies in the packet
1553
1554   // Analyze relationships between all existing members of the packet.
1555   // Look for Anti dependecy on the same predicate reg
1556   // as used in the candidate
1557   for (std::vector<MachineInstr*>::iterator VIN = CurrentPacketMIs.begin(),
1558        VEN = CurrentPacketMIs.end(); (VIN != VEN); ++VIN) {
1559
1560     // Scheduling Unit for current insn in the packet
1561     SUnit* PacketSU = MIToSUnit[*VIN];
1562
1563     // If this instruction in the packet is succeeded by the candidate...
1564     if (PacketSU->isSucc(SU)) {
1565       for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) {
1566         // The corner case exist when there is true data
1567         // dependency between candidate and one of current
1568         // packet members, this dep is on predicate reg, and
1569         // there already exist anti dep on the same pred in
1570         // the packet.
1571         if (PacketSU->Succs[i].getSUnit() == SU &&
1572             Hexagon::PredRegsRegClass.contains(
1573               PacketSU->Succs[i].getReg()) &&
1574             PacketSU->Succs[i].getKind() == SDep::Data &&
1575             // Here I know that *VIN is predicate setting instruction
1576             // with true data dep to candidate on the register
1577             // we care about - c) in the above example.
1578             // Now I need to see if there is an anti dependency
1579             // from c) to any other instruction in the
1580             // same packet on the pred reg of interest
1581             RestrictingDepExistInPacket(*VIN,PacketSU->Succs[i].getReg(),
1582                                         MIToSUnit)) {
1583            return false;
1584         }
1585       }
1586     }
1587   }
1588
1589   // If the above case does not apply, check regular
1590   // complement condition.
1591   // Check that the predicate register is the same and
1592   // that the predicate sense is different
1593   // We also need to differentiate .old vs. .new:
1594   // !p0 is not complimentary to p0.new
1595   return ((MI1->getOperand(1).getReg() == MI2->getOperand(1).getReg()) &&
1596           (getPredicateSense(MI1, QII) != getPredicateSense(MI2, QII)) &&
1597           (QII->isDotNewInst(MI1) == QII->isDotNewInst(MI2)));
1598 }
1599
1600 // initPacketizerState - Initialize packetizer flags
1601 void HexagonPacketizerList::initPacketizerState() {
1602
1603   Dependence = false;
1604   PromotedToDotNew = false;
1605   GlueToNewValueJump = false;
1606   GlueAllocframeStore = false;
1607   FoundSequentialDependence = false;
1608
1609   return;
1610 }
1611
1612 // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
1613 bool HexagonPacketizerList::ignorePseudoInstruction(MachineInstr *MI,
1614                                                     MachineBasicBlock *MBB) {
1615   if (MI->isDebugValue())
1616     return true;
1617
1618   // We must print out inline assembly
1619   if (MI->isInlineAsm())
1620     return false;
1621
1622   // We check if MI has any functional units mapped to it.
1623   // If it doesn't, we ignore the instruction.
1624   const MCInstrDesc& TID = MI->getDesc();
1625   unsigned SchedClass = TID.getSchedClass();
1626   const InstrStage* IS =
1627                     ResourceTracker->getInstrItins()->beginStage(SchedClass);
1628   unsigned FuncUnits = IS->getUnits();
1629   return !FuncUnits;
1630 }
1631
1632 // isSoloInstruction: - Returns true for instructions that must be
1633 // scheduled in their own packet.
1634 bool HexagonPacketizerList::isSoloInstruction(MachineInstr *MI) {
1635
1636   if (MI->isInlineAsm())
1637     return true;
1638
1639   if (MI->isEHLabel())
1640     return true;
1641
1642   // From Hexagon V4 Programmer's Reference Manual 3.4.4 Grouping constraints:
1643   // trap, pause, barrier, icinva, isync, and syncht are solo instructions.
1644   // They must not be grouped with other instructions in a packet.
1645   if (IsSchedBarrier(MI))
1646     return true;
1647
1648   return false;
1649 }
1650
1651 // isLegalToPacketizeTogether:
1652 // SUI is the current instruction that is out side of the current packet.
1653 // SUJ is the current instruction inside the current packet against which that
1654 // SUI will be packetized.
1655 bool HexagonPacketizerList::isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
1656   MachineInstr *I = SUI->getInstr();
1657   MachineInstr *J = SUJ->getInstr();
1658   assert(I && J && "Unable to packetize null instruction!");
1659
1660   const MCInstrDesc &MCIDI = I->getDesc();
1661   const MCInstrDesc &MCIDJ = J->getDesc();
1662
1663   MachineBasicBlock::iterator II = I;
1664
1665   const unsigned FrameSize = MF.getFrameInfo()->getStackSize();
1666   const HexagonRegisterInfo* QRI =
1667                       (const HexagonRegisterInfo *) TM.getRegisterInfo();
1668   const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
1669
1670   // Inline asm cannot go in the packet.
1671   if (I->getOpcode() == Hexagon::INLINEASM)
1672     llvm_unreachable("Should not meet inline asm here!");
1673
1674   if (isSoloInstruction(I))
1675     llvm_unreachable("Should not meet solo instr here!");
1676
1677   // A save callee-save register function call can only be in a packet
1678   // with instructions that don't write to the callee-save registers.
1679   if ((QII->isSaveCalleeSavedRegsCall(I) &&
1680        DoesModifyCalleeSavedReg(J, QRI)) ||
1681       (QII->isSaveCalleeSavedRegsCall(J) &&
1682        DoesModifyCalleeSavedReg(I, QRI))) {
1683     Dependence = true;
1684     return false;
1685   }
1686
1687   // Two control flow instructions cannot go in the same packet.
1688   if (IsControlFlow(I) && IsControlFlow(J)) {
1689     Dependence = true;
1690     return false;
1691   }
1692
1693   // A LoopN instruction cannot appear in the same packet as a jump or call.
1694   if (IsLoopN(I) && (   IsDirectJump(J)
1695                      || MCIDJ.isCall()
1696                      || QII->isDeallocRet(J))) {
1697     Dependence = true;
1698     return false;
1699   }
1700   if (IsLoopN(J) && (   IsDirectJump(I)
1701                      || MCIDI.isCall()
1702                      || QII->isDeallocRet(I))) {
1703     Dependence = true;
1704     return false;
1705   }
1706
1707   // dealloc_return cannot appear in the same packet as a conditional or
1708   // unconditional jump.
1709   if (QII->isDeallocRet(I) && (   MCIDJ.isBranch()
1710                                || MCIDJ.isCall()
1711                                || MCIDJ.isBarrier())) {
1712     Dependence = true;
1713     return false;
1714   }
1715
1716
1717   // V4 allows dual store. But does not allow second store, if the
1718   // first store is not in SLOT0. New value store, new value jump,
1719   // dealloc_return and memop always take SLOT0.
1720   // Arch spec 3.4.4.2
1721   if (QRI->Subtarget.hasV4TOps()) {
1722     if (MCIDI.mayStore() && MCIDJ.mayStore() &&
1723        (QII->isNewValueInst(J) || QII->isMemOp(J) || QII->isMemOp(I))) {
1724       Dependence = true;
1725       return false;
1726     }
1727
1728     if ((QII->isMemOp(J) && MCIDI.mayStore())
1729         || (MCIDJ.mayStore() && QII->isMemOp(I))
1730         || (QII->isMemOp(J) && QII->isMemOp(I))) {
1731       Dependence = true;
1732       return false;
1733     }
1734
1735     //if dealloc_return
1736     if (MCIDJ.mayStore() && QII->isDeallocRet(I)){
1737       Dependence = true;
1738       return false;
1739     }
1740
1741     // If an instruction feeds new value jump, glue it.
1742     MachineBasicBlock::iterator NextMII = I;
1743     ++NextMII;
1744     if (NextMII != I->getParent()->end() && QII->isNewValueJump(NextMII)) {
1745       MachineInstr *NextMI = NextMII;
1746
1747       bool secondRegMatch = false;
1748       bool maintainNewValueJump = false;
1749
1750       if (NextMI->getOperand(1).isReg() &&
1751           I->getOperand(0).getReg() == NextMI->getOperand(1).getReg()) {
1752         secondRegMatch = true;
1753         maintainNewValueJump = true;
1754       }
1755
1756       if (!secondRegMatch &&
1757            I->getOperand(0).getReg() == NextMI->getOperand(0).getReg()) {
1758         maintainNewValueJump = true;
1759       }
1760
1761       for (std::vector<MachineInstr*>::iterator
1762             VI = CurrentPacketMIs.begin(),
1763              VE = CurrentPacketMIs.end();
1764            (VI != VE && maintainNewValueJump); ++VI) {
1765         SUnit* PacketSU = MIToSUnit[*VI];
1766
1767         // NVJ can not be part of the dual jump - Arch Spec: section 7.8
1768         if (PacketSU->getInstr()->getDesc().isCall()) {
1769           Dependence = true;
1770           break;
1771         }
1772         // Validate
1773         // 1. Packet does not have a store in it.
1774         // 2. If the first operand of the nvj is newified, and the second
1775         //    operand is also a reg, it (second reg) is not defined in
1776         //    the same packet.
1777         // 3. If the second operand of the nvj is newified, (which means
1778         //    first operand is also a reg), first reg is not defined in
1779         //    the same packet.
1780         if (PacketSU->getInstr()->getDesc().mayStore()               ||
1781             PacketSU->getInstr()->getOpcode() == Hexagon::ALLOCFRAME ||
1782             // Check #2.
1783             (!secondRegMatch && NextMI->getOperand(1).isReg() &&
1784              PacketSU->getInstr()->modifiesRegister(
1785                                NextMI->getOperand(1).getReg(), QRI)) ||
1786             // Check #3.
1787             (secondRegMatch &&
1788              PacketSU->getInstr()->modifiesRegister(
1789                                NextMI->getOperand(0).getReg(), QRI))) {
1790           Dependence = true;
1791           break;
1792         }
1793       }
1794       if (!Dependence)
1795         GlueToNewValueJump = true;
1796       else
1797         return false;
1798     }
1799   }
1800
1801   if (SUJ->isSucc(SUI)) {
1802     for (unsigned i = 0;
1803          (i < SUJ->Succs.size()) && !FoundSequentialDependence;
1804          ++i) {
1805
1806       if (SUJ->Succs[i].getSUnit() != SUI) {
1807         continue;
1808       }
1809
1810       SDep::Kind DepType = SUJ->Succs[i].getKind();
1811
1812       // For direct calls:
1813       // Ignore register dependences for call instructions for
1814       // packetization purposes except for those due to r31 and
1815       // predicate registers.
1816       //
1817       // For indirect calls:
1818       // Same as direct calls + check for true dependences to the register
1819       // used in the indirect call.
1820       //
1821       // We completely ignore Order dependences for call instructions
1822       //
1823       // For returns:
1824       // Ignore register dependences for return instructions like jumpr,
1825       // dealloc return unless we have dependencies on the explicit uses
1826       // of the registers used by jumpr (like r31) or dealloc return
1827       // (like r29 or r30).
1828       //
1829       // TODO: Currently, jumpr is handling only return of r31. So, the
1830       // following logic (specificaly IsCallDependent) is working fine.
1831       // We need to enable jumpr for register other than r31 and then,
1832       // we need to rework the last part, where it handles indirect call
1833       // of that (IsCallDependent) function. Bug 6216 is opened for this.
1834       //
1835       unsigned DepReg = 0;
1836       const TargetRegisterClass* RC = NULL;
1837       if (DepType == SDep::Data) {
1838         DepReg = SUJ->Succs[i].getReg();
1839         RC = QRI->getMinimalPhysRegClass(DepReg);
1840       }
1841       if ((MCIDI.isCall() || MCIDI.isReturn()) &&
1842           (!IsRegDependence(DepType) ||
1843             !IsCallDependent(I, DepType, SUJ->Succs[i].getReg()))) {
1844         /* do nothing */
1845       }
1846
1847       // For instructions that can be promoted to dot-new, try to promote.
1848       else if ((DepType == SDep::Data) &&
1849                CanPromoteToDotNew(I, SUJ, DepReg, MIToSUnit, II, RC) &&
1850                PromoteToDotNew(I, DepType, II, RC)) {
1851         PromotedToDotNew = true;
1852         /* do nothing */
1853       }
1854
1855       else if ((DepType == SDep::Data) &&
1856                (QII->isNewValueJump(I))) {
1857         /* do nothing */
1858       }
1859
1860       // For predicated instructions, if the predicates are complements
1861       // then there can be no dependence.
1862       else if (QII->isPredicated(I) &&
1863                QII->isPredicated(J) &&
1864           ArePredicatesComplements(I, J, MIToSUnit)) {
1865         /* do nothing */
1866
1867       }
1868       else if (IsDirectJump(I) &&
1869                !MCIDJ.isBranch() &&
1870                !MCIDJ.isCall() &&
1871                (DepType == SDep::Order)) {
1872         // Ignore Order dependences between unconditional direct branches
1873         // and non-control-flow instructions
1874         /* do nothing */
1875       }
1876       else if (MCIDI.isConditionalBranch() && (DepType != SDep::Data) &&
1877                (DepType != SDep::Output)) {
1878         // Ignore all dependences for jumps except for true and output
1879         // dependences
1880         /* do nothing */
1881       }
1882
1883       // Ignore output dependences due to superregs. We can
1884       // write to two different subregisters of R1:0 for instance
1885       // in the same cycle
1886       //
1887
1888       //
1889       // Let the
1890       // If neither I nor J defines DepReg, then this is a
1891       // superfluous output dependence. The dependence must be of the
1892       // form:
1893       //  R0 = ...
1894       //  R1 = ...
1895       // and there is an output dependence between the two instructions
1896       // with
1897       // DepReg = D0
1898       // We want to ignore these dependences.
1899       // Ideally, the dependence constructor should annotate such
1900       // dependences. We can then avoid this relatively expensive check.
1901       //
1902       else if (DepType == SDep::Output) {
1903         // DepReg is the register that's responsible for the dependence.
1904         unsigned DepReg = SUJ->Succs[i].getReg();
1905
1906         // Check if I and J really defines DepReg.
1907         if (I->definesRegister(DepReg) ||
1908             J->definesRegister(DepReg)) {
1909           FoundSequentialDependence = true;
1910           break;
1911         }
1912       }
1913
1914       // We ignore Order dependences for
1915       // 1. Two loads unless they are volatile.
1916       // 2. Two stores in V4 unless they are volatile.
1917       else if ((DepType == SDep::Order) &&
1918                !I->hasOrderedMemoryRef() &&
1919                !J->hasOrderedMemoryRef()) {
1920         if (QRI->Subtarget.hasV4TOps() &&
1921             // hexagonv4 allows dual store.
1922             MCIDI.mayStore() && MCIDJ.mayStore()) {
1923           /* do nothing */
1924         }
1925         // store followed by store-- not OK on V2
1926         // store followed by load -- not OK on all (OK if addresses
1927         // are not aliased)
1928         // load followed by store -- OK on all
1929         // load followed by load  -- OK on all
1930         else if ( !MCIDJ.mayStore()) {
1931           /* do nothing */
1932         }
1933         else {
1934           FoundSequentialDependence = true;
1935           break;
1936         }
1937       }
1938
1939       // For V4, special case ALLOCFRAME. Even though there is dependency
1940       // between ALLOCAFRAME and subsequent store, allow it to be
1941       // packetized in a same packet. This implies that the store is using
1942       // caller's SP. Hense, offset needs to be updated accordingly.
1943       else if (DepType == SDep::Data
1944                && QRI->Subtarget.hasV4TOps()
1945                && J->getOpcode() == Hexagon::ALLOCFRAME
1946                && (I->getOpcode() == Hexagon::STrid
1947                    || I->getOpcode() == Hexagon::STriw
1948                    || I->getOpcode() == Hexagon::STrib)
1949                && I->getOperand(0).getReg() == QRI->getStackRegister()
1950                && QII->isValidOffset(I->getOpcode(),
1951                                      I->getOperand(1).getImm() -
1952                                      (FrameSize + HEXAGON_LRFP_SIZE)))
1953       {
1954         GlueAllocframeStore = true;
1955         // Since this store is to be glued with allocframe in the same
1956         // packet, it will use SP of the previous stack frame, i.e
1957         // caller's SP. Therefore, we need to recalculate offset according
1958         // to this change.
1959         I->getOperand(1).setImm(I->getOperand(1).getImm() -
1960                                         (FrameSize + HEXAGON_LRFP_SIZE));
1961       }
1962
1963       //
1964       // Skip over anti-dependences. Two instructions that are
1965       // anti-dependent can share a packet
1966       //
1967       else if (DepType != SDep::Anti) {
1968         FoundSequentialDependence = true;
1969         break;
1970       }
1971     }
1972
1973     if (FoundSequentialDependence) {
1974       Dependence = true;
1975       return false;
1976     }
1977   }
1978
1979   return true;
1980 }
1981
1982 // isLegalToPruneDependencies
1983 bool HexagonPacketizerList::isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
1984   MachineInstr *I = SUI->getInstr();
1985   assert(I && SUJ->getInstr() && "Unable to packetize null instruction!");
1986
1987   const unsigned FrameSize = MF.getFrameInfo()->getStackSize();
1988
1989   if (Dependence) {
1990
1991     // Check if the instruction was promoted to a dot-new. If so, demote it
1992     // back into a dot-old.
1993     if (PromotedToDotNew) {
1994       DemoteToDotOld(I);
1995     }
1996
1997     // Check if the instruction (must be a store) was glued with an Allocframe
1998     // instruction. If so, restore its offset to its original value, i.e. use
1999     // curent SP instead of caller's SP.
2000     if (GlueAllocframeStore) {
2001       I->getOperand(1).setImm(I->getOperand(1).getImm() +
2002                                              FrameSize + HEXAGON_LRFP_SIZE);
2003     }
2004
2005     return false;
2006   }
2007   return true;
2008 }
2009
2010 MachineBasicBlock::iterator
2011 HexagonPacketizerList::addToPacket(MachineInstr *MI) {
2012
2013     MachineBasicBlock::iterator MII = MI;
2014     MachineBasicBlock *MBB = MI->getParent();
2015
2016     const HexagonInstrInfo *QII = (const HexagonInstrInfo *) TII;
2017
2018     if (GlueToNewValueJump) {
2019
2020       ++MII;
2021       MachineInstr *nvjMI = MII;
2022       assert(ResourceTracker->canReserveResources(MI));
2023       ResourceTracker->reserveResources(MI);
2024       if ((QII->isExtended(MI) || QII->isConstExtended(MI)) &&
2025           !tryAllocateResourcesForConstExt(MI)) {
2026         endPacket(MBB, MI);
2027         ResourceTracker->reserveResources(MI);
2028         assert(canReserveResourcesForConstExt(MI) &&
2029                "Ensure that there is a slot");
2030         reserveResourcesForConstExt(MI);
2031         // Reserve resources for new value jump constant extender.
2032         assert(canReserveResourcesForConstExt(MI) &&
2033                "Ensure that there is a slot");
2034         reserveResourcesForConstExt(nvjMI);
2035         assert(ResourceTracker->canReserveResources(nvjMI) &&
2036                "Ensure that there is a slot");
2037
2038       } else if (   // Extended instruction takes two slots in the packet.
2039         // Try reserve and allocate 4-byte in the current packet first.
2040         (QII->isExtended(nvjMI)
2041             && (!tryAllocateResourcesForConstExt(nvjMI)
2042                 || !ResourceTracker->canReserveResources(nvjMI)))
2043         || // For non-extended instruction, no need to allocate extra 4 bytes.
2044         (!QII->isExtended(nvjMI) &&
2045               !ResourceTracker->canReserveResources(nvjMI)))
2046       {
2047         endPacket(MBB, MI);
2048         // A new and empty packet starts.
2049         // We are sure that the resources requirements can be satisfied.
2050         // Therefore, do not need to call "canReserveResources" anymore.
2051         ResourceTracker->reserveResources(MI);
2052         if (QII->isExtended(nvjMI))
2053           reserveResourcesForConstExt(nvjMI);
2054       }
2055       // Here, we are sure that "reserveResources" would succeed.
2056       ResourceTracker->reserveResources(nvjMI);
2057       CurrentPacketMIs.push_back(MI);
2058       CurrentPacketMIs.push_back(nvjMI);
2059     } else {
2060       if (   (QII->isExtended(MI) || QII->isConstExtended(MI))
2061           && (   !tryAllocateResourcesForConstExt(MI)
2062               || !ResourceTracker->canReserveResources(MI)))
2063       {
2064         endPacket(MBB, MI);
2065         // Check if the instruction was promoted to a dot-new. If so, demote it
2066         // back into a dot-old
2067         if (PromotedToDotNew) {
2068           DemoteToDotOld(MI);
2069         }
2070         reserveResourcesForConstExt(MI);
2071       }
2072       // In case that "MI" is not an extended insn,
2073       // the resource availability has already been checked.
2074       ResourceTracker->reserveResources(MI);
2075       CurrentPacketMIs.push_back(MI);
2076     }
2077     return MII;
2078 }
2079
2080 //===----------------------------------------------------------------------===//
2081 //                         Public Constructor Functions
2082 //===----------------------------------------------------------------------===//
2083
2084 FunctionPass *llvm::createHexagonPacketizer() {
2085   return new HexagonPacketizer();
2086 }
2087