HexagonGlobalScheduler.cpp

Go to the documentation of this file.

 
//===----- HexagonGlobalScheduler.cpp - Global Scheduler ------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Basic infrastructure for the global scheduling + Hexagon pull-up pass.
// Currently run at the very end of code generation for Hexagon, cleans
// up lost scheduling opportunities. Currently breaks liveness, so no passes
// that rely on liveness info should run afterwards. Will be fixed in future
// versions.
//
//===----------------------------------------------------------------------===//
#include "Hexagon.h"
#include "HexagonGlobalRegion.h"
#include "HexagonRegisterInfo.h"
#include "HexagonSubtarget.h"
#include "HexagonVLIWPacketizer.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/PseudoSourceValue.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
#include <list>
#include <map>
 
#define DEBUG_TYPE "global_sched"
 
using namespace llvm;
 
STATISTIC(HexagonNumPullUps, "Number of instructions pull-ups");
STATISTIC(HexagonNumDualJumps, "Number of dual jumps formed");
 
static cl::opt<bool> DisablePullUp("disable-pull-up", cl::Hidden,
                                   cl::desc("Disable Hexagon pull-up pass"));
 
static cl::opt<bool> EnableSpeculativePullUp(
    "enable-speculative-pull-up", cl::Hidden,
    cl::desc("Enable speculation during Hexagon pull-up pass"));
 
static cl::opt<bool> EnableLocalPullUp(
    "enable-local-pull-up", cl::Hidden, cl::init(true),
    cl::desc("Enable same BB pull during Hexagon pull-up pass"));
 
static cl::opt<bool> AllowSpeculateLoads(
    "speculate-loads-on-pull-up", cl::Hidden, cl::init(true),
    cl::desc("Allow speculative loads during Hexagon pull-up pass"));
 
static cl::opt<bool> AllowCmpBranchLoads(
    "cmp-branch-loads-pull-up", cl::Hidden, cl::init(true),
    cl::desc("Allow compare-branch loads during Hexagon pull-up pass"));
 
static cl::opt<bool> AllowUnlikelyPath("unlikely-path-pull-up", cl::Hidden,
                                       cl::init(true),
                                       cl::desc("Allow unlikely path pull up"));
 
static cl::opt<bool>
    PerformDualJumps("dual-jump-in-pull-up", cl::Hidden, cl::init(true),
                     cl::desc("Perform dual jump formation during pull up"));
 
static cl::opt<bool> AllowDependentPullUp(
    "enable-dependent-pull-up", cl::Hidden, cl::init(true),
    cl::desc("Perform dual jump formation during pull up"));
 
static cl::opt<bool>
    AllowBBPeelPullUp("enable-bb-peel-pull-up", cl::Hidden, cl::init(true),
                      cl::desc("Peel a reg copy out of a BBloop"));
 
static cl::opt<bool> PreventCompoundSeparation(
    "prevent-compound-separation", cl::Hidden,
    cl::desc("Do not destroy existing compounds during pull up"));
 
static cl::opt<bool> PreventDuplexSeparation(
    "prevent-duplex-separation", cl::Hidden, cl::init(true),
    cl::desc("Do not destroy existing duplexes during pull up"));
 
static cl::opt<unsigned> MainCandidateQueueSize("pull-up-main-queue-size",
                                                cl::Hidden, cl::init(8));
 
static cl::opt<unsigned> SecondaryCandidateQueueSize("pull-up-sec-queue-size",
                                                     cl::Hidden, cl::init(2));
 
static cl::opt<bool> PostPullUpOpt(
    "post-pull-up-opt", cl::Hidden, cl::init(true),
    cl::desc("Enable opt. exposed by pull-up e.g., remove redundant jumps"));
 
static cl::opt<bool> SpeculateNonPredInsn(
    "speculate-non-pred-insn", cl::Hidden, cl::init(true),
    cl::desc("Speculate non-predicable instructions in parent BB"));
 
static cl::opt<bool>
    DisableCheckBundles("disable-hexagon-check-bundles", cl::Hidden,
                        cl::init(true),
                        cl::desc("Disable Hexagon check bundles pass"));
 
static cl::opt<bool>
    WarnOnBundleSize("warn-on-bundle-size", cl::Hidden,
                     cl::desc("Hexagon check bundles and warn on size"));
 
static cl::opt<bool>
    ForceNoopHazards("force-noop-hazards", cl::Hidden, cl::init(false),
                     cl::desc("Force noop hazards in scheduler"));
static cl::opt<bool> OneFloatPerPacket(
    "single-float-packet", cl::Hidden,
    cl::desc("Allow only one single floating point instruction in a packet"));
static cl::opt<bool> OneComplexPerPacket(
    "single-complex-packet", cl::Hidden,
    cl::desc("Allow only one complex instruction in a packet"));
 
namespace llvm {
FunctionPass *createHexagonGlobalScheduler();
void initializeHexagonGlobalSchedulerPass(PassRegistry &);
} // namespace llvm
 
namespace {
class HexagonGlobalSchedulerImpl;
 
class HexagonGlobalScheduler : public MachineFunctionPass {
public:
  static char ID;
  HexagonGlobalScheduler() : MachineFunctionPass(ID) {
    initializeHexagonGlobalSchedulerPass(*PassRegistry::getPassRegistry());
  }
 
  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequiredID(MachineDominatorsID);
    AU.addRequired<MachineLoopInfoWrapperPass>();
    AU.addRequired<AAResultsWrapperPass>();
    AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
    AU.addRequired<MachineBlockFrequencyInfoWrapperPass>();
    AU.addRequired<MachineDominatorTreeWrapperPass>();
    MachineFunctionPass::getAnalysisUsage(AU);
  }
 
  StringRef getPassName() const override { return "Hexagon Global Scheduler"; }
 
  bool runOnMachineFunction(MachineFunction &Fn) override;
};
char HexagonGlobalScheduler::ID = 0;
 
// Describes a single pull-up candidate.
class PullUpCandidate {
  MachineBasicBlock::instr_iterator CandidateLocation;
  MachineBasicBlock::iterator HomeBundle;
  bool DependentOp;
  signed BenefitCost;
  std::vector<MachineInstr *> Backtrack;
 
public:
  PullUpCandidate(MachineBasicBlock::instr_iterator MII) {
    CandidateLocation = MII;
    BenefitCost = 0;
  }
 
  PullUpCandidate(MachineBasicBlock::instr_iterator MII,
                  MachineBasicBlock::iterator HomeBundle,
                  std::vector<MachineInstr *> &backtrack, bool DependentOp,
                  signed Cost)
      : CandidateLocation(MII), HomeBundle(HomeBundle),
        DependentOp(DependentOp), BenefitCost(Cost) {
    // Copy of the backtrack.
    Backtrack = backtrack;
  }
 
  void populate(MachineBasicBlock::instr_iterator &MII,
                MachineBasicBlock::iterator &WorkPoint,
                std::vector<MachineInstr *> &backtrack, bool &dependentOp) {
    MII = CandidateLocation;
    WorkPoint = HomeBundle;
    backtrack = Backtrack;
    dependentOp = DependentOp;
  }
 
  signed getCost() { return BenefitCost; }
 
  MachineInstr *getCandidate() { return &*CandidateLocation; }
 
  void dump() {
    dbgs() << "Cost(" << BenefitCost;
    dbgs() << ") Dependent(" << DependentOp;
    dbgs() << ") backtrack size(" << Backtrack.size() << ")\t";
    CandidateLocation->dump();
  }
};
 
/// PullUpCandidateSorter - A Sort utility for pull-up candidates.
struct PullUpCandidateSorter {
  PullUpCandidateSorter() {}
  bool operator()(PullUpCandidate *LHS, PullUpCandidate *RHS) {
    return LHS->getCost() > RHS->getCost();
  }
};
 
// Describes a single pull-up opportunity: location to which
// pull-up is possible with additional information about it.
// Also contains a list of pull-up candidates for this location.
class PullUpState {
  friend class HexagonGlobalSchedulerImpl;
  // Available opportunity for pull-up.
  // FAIAP a bundle with an empty slot.
  MachineBasicBlock::iterator HomeLocation;
  // Home bundle copy. This is here for speed of iteration.
  SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> HomeBundle;
  // Multiple candidates for the Home location.
  SmallVector<PullUpCandidate *, 8> PullUpCandidates;
 
  const HexagonInstrInfo *QII;
 
public:
  PullUpState(const HexagonInstrInfo *QII) : HomeLocation(NULL), QII(QII) {}
 
  ~PullUpState() { reset(); }
 
  void addPullUpCandidate(MachineBasicBlock::instr_iterator MII,
                          MachineBasicBlock::iterator HomeBundle,
                          std::vector<MachineInstr *> &backtrack,
                          bool DependentOp, signed Cost) {
    LLVM_DEBUG(dbgs() << "\t[addPullUpCandidate]: "; (*MII).dump());
    PullUpCandidate *PUI =
        new PullUpCandidate(MII, HomeBundle, backtrack, DependentOp, Cost);
    PullUpCandidates.push_back(PUI);
  }
 
  void dump() {
    unsigned element = 0;
    for (unsigned i = 0; i < HomeBundle.size(); i++) {
      dbgs() << "[" << element++;
      dbgs() << "] Home Duplex("
             << QII->getDuplexCandidateGroup(*HomeBundle[i]);
      dbgs() << ") Compound (" << QII->getCompoundCandidateGroup(*HomeBundle[i])
             << ") ";
      HomeBundle[i]->dump();
    }
    dbgs() << "\n";
    element = 0;
    for (SmallVector<PullUpCandidate *, 4>::iterator
             I = PullUpCandidates.begin(),
             E = PullUpCandidates.end();
         I != E; ++I) {
      dbgs() << "[" << element++ << "] Cand: Compound(";
      dbgs() << QII->getCompoundCandidateGroup(*(*I)->getCandidate()) << ") ";
      (*I)->dump();
    }
  }
 
  void reset() {
    HomeLocation = NULL;
    for (SmallVector<PullUpCandidate *, 4>::iterator
             I = PullUpCandidates.begin(),
             E = PullUpCandidates.end();
         I != E; ++I)
      delete *I;
    PullUpCandidates.clear();
    HomeBundle.clear();
  }
 
  void addHomeLocation(MachineBasicBlock::iterator WorkPoint) {
    reset();
    HomeLocation = WorkPoint;
  }
 
  unsigned haveCandidates() { return PullUpCandidates.size(); }
};
 
class HexagonGlobalSchedulerImpl : public HexagonPacketizerList {
  // List of PullUp regions for this function.
  std::vector<BasicBlockRegion *> PullUpRegions;
  // Map of approximate distance for each BB from the
  // function base.
  DenseMap<MachineBasicBlock *, unsigned> BlockToInstOffset;
  // Keep track of multiple pull-up candidates.
  PullUpState CurrentState;
  // Empty basic blocks as a result of pull-up.
  std::vector<MachineBasicBlock *> EmptyBBs;
  // Save all the Speculated MachineInstr that were moved
  // FROM MachineBasicBlock because we don't want to have
  // more than one speculated instructions pulled into one packet.
  // TODO: This can be removed once we have a use-def dependency chain
  // for all the instructions in a function.
  std::map<MachineInstr *, MachineBasicBlock *> SpeculatedIns;
  // All the regs and their aliases used by an instruction.
  std::map<MachineInstr *, std::vector<unsigned>> MIUseSet;
  // All the regs and their aliases defined by an instruction.
  std::map<MachineInstr *, std::vector<unsigned>> MIDefSet;
 
  AliasAnalysis *AA;
  const MachineBranchProbabilityInfo *MBPI;
  const MachineBlockFrequencyInfo *MBFI;
  const MachineRegisterInfo *MRI;
  const MachineFrameInfo &MFI;
  const HexagonRegisterInfo *QRI;
  const HexagonInstrInfo *QII;
  MachineLoopInfo &MLI;
  MachineDominatorTree &MDT;
  MachineInstrBuilder Ext;
  MachineInstrBuilder Nop;
  const unsigned PacketSize;
  TargetSchedModel TSchedModel;
 
public:
  // Ctor.
  HexagonGlobalSchedulerImpl(MachineFunction &MF, MachineLoopInfo &MLI,
                             MachineDominatorTree &MDT, AliasAnalysis *AA,
                             const MachineBranchProbabilityInfo *MBPI,
                             const MachineBlockFrequencyInfo *MBFI,
                             const MachineRegisterInfo *MRI,
                             const MachineFrameInfo &MFI,
                             const HexagonRegisterInfo *QRI);
  HexagonGlobalSchedulerImpl(const HexagonGlobalSchedulerImpl &) = delete;
  HexagonGlobalSchedulerImpl &
  operator=(const HexagonGlobalSchedulerImpl &) = delete;
 
  ~HexagonGlobalSchedulerImpl() {
    // Free regions.
    for (std::vector<BasicBlockRegion *>::iterator I = PullUpRegions.begin(),
                                                   E = PullUpRegions.end();
         I != E; ++I)
      delete *I;
    MF.deleteMachineInstr(Ext);
    MF.deleteMachineInstr(Nop);
  }
 
  // initPacketizerState - initialize some internal flags.
  void initPacketizerState() override;
 
  // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
  bool ignoreInstruction(MachineInstr *MI);
 
  // isSoloInstruction - return true if instruction MI can not be packetized
  // with any other instruction, which means that MI itself is a packet.
  bool isSoloInstruction(const MachineInstr &MI) override;
 
  // Add MI to packetizer state. Returns false if it cannot fit in the packet.
  bool incrementalAddToPacket(MachineInstr &MI);
 
  // formPullUpRegions - Top level call to form regions.
  bool formPullUpRegions(MachineFunction &Fn);
 
  // performPullUp - Top level call for pull-up.
  bool performPullUp();
 
  // performPullUpCFG - Top level call for pull-up CFG.
  bool performPullUpCFG(MachineFunction &Fn);
 
  // performExposedOptimizations -
  // Look for optimization opportunities after pullup.
  bool performExposedOptimizations(MachineFunction &Fn);
 
  // optimizeBranching -
  // 1. A conditional-jump transfers control to a BB with
  // jump as the only instruction.
  // if(p0) jump t1
  // // ...
  // t1: jump t2
  // 2. When a BB with a single conditional jump, jumps to succ-of-succ and
  // falls-through BB with only jump instruction.
  // { if(p0) jump t1 }
  // { jump t2 }
  // t1: { ... }
  MachineBasicBlock *optimizeBranches(MachineBasicBlock *MBB,
                                      MachineBasicBlock *TBB,
                                      MachineInstr *FirstTerm,
                                      MachineBasicBlock *FBB);
 
  // removeRedundantBranches -
  // 1. Remove jump to the layout successor.
  // 2. Remove multiple (dual) jump to the same target.
  bool removeRedundantBranches(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
                               MachineInstr *FirstTerm, MachineBasicBlock *FBB,
                               MachineInstr *SecondTerm);
 
  // optimizeDualJumps - optimize dual jumps in a packet
  // For now: Replace dual jump by single jump in case of a fall through.
  bool optimizeDualJumps(MachineBasicBlock *MBB, MachineBasicBlock *TBB,
                         MachineInstr *FirstTerm, MachineBasicBlock *FBB,
                         MachineInstr *SecondTerm);
 
  void GenUseDefChain(MachineFunction &Fn);
 
  // Return region pointer or null if none found.
  BasicBlockRegion *getRegionForMBB(std::vector<BasicBlockRegion *> &Regions,
                                    MachineBasicBlock *MBB);
 
  // Saves all the used-regs and their aliases in Uses.
  // Saves all the defined-regs and their aliases in Defs.
  void MIUseDefSet(MachineInstr *MI, std::vector<unsigned> &Defs,
                   std::vector<unsigned> &Uses);
 
  // This is a very useful debug utility.
  unsigned countCompounds(MachineFunction &Fn);
 
  // Check bundle counts
  void checkBundleCounts(MachineFunction &Fn);
 
private:
  // Get next BB to be included into the region.
  MachineBasicBlock *getNextPURBB(MachineBasicBlock *MBB, bool SecondBest);
 
  void setUsedRegs(BitVector &Set, unsigned Reg);
  bool AliasingRegs(unsigned RegA, unsigned RegB);
 
  // Test is true if the two MIs cannot be safely reordered.
  bool ReorderDependencyTest(MachineInstr *MIa, MachineInstr *MIb);
 
  bool canAddMIToThisPacket(
      MachineInstr *MI,
      SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle);
 
  bool pullUpPeelBBLoop(MachineBasicBlock *PredBB, MachineBasicBlock *LoopBB);
 
  MachineInstr *findBundleAndBranch(MachineBasicBlock *BB,
                                    MachineBasicBlock::iterator &Bundle);
 
  // Does this bundle have any slots left?
  bool ResourcesAvailableInBundle(BasicBlockRegion *CurrentRegion,
                                  MachineBasicBlock::iterator &TargetPacket);
 
  // Perform the actual move.
  MachineInstr *MoveAndUpdateLiveness(
      BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
      MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
      bool MovingDependentOp, MachineBasicBlock *OriginBB,
      MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
      MachineBasicBlock::iterator &SourceLocation,
      MachineBasicBlock::iterator &TargetPacket,
      MachineBasicBlock::iterator &NextMI,
      std::vector<MachineInstr *> &backtrack);
 
  // Updates incremental kill patterns along the backtrack.
  void updateKillAlongThePath(MachineBasicBlock *HomeBB,
                              MachineBasicBlock *OriginBB,
                              MachineBasicBlock::instr_iterator &Head,
                              MachineBasicBlock::instr_iterator &Tail,
                              MachineBasicBlock::iterator &SourcePacket,
                              MachineBasicBlock::iterator &TargetPacket,
                              std::vector<MachineInstr *> &backtrack);
 
  // Gather list of pull-up candidates.
  bool findPullUpCandidates(MachineBasicBlock::iterator &WorkPoint,
                            MachineBasicBlock::iterator &FromHere,
                            std::vector<MachineInstr *> &backtrack,
                            unsigned MaxCandidates);
 
  // See if the instruction could be pulled up.
  bool tryMultipleInstructions(
      MachineBasicBlock::iterator &RetVal, /* output parameter */
      std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
      MachineBasicBlock::iterator &NextMI,
      MachineBasicBlock::iterator &ToThisBBEnd,
      MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion = true);
 
  // Try to move MI into existing bundle.
  bool MoveMItoBundle(BasicBlockRegion *CurrentRegion,
                      MachineBasicBlock::instr_iterator &InstrToMove,
                      MachineBasicBlock::iterator &NextMI,
                      MachineBasicBlock::iterator &TargetPacket,
                      MachineBasicBlock::iterator &SourceLocation,
                      std::vector<MachineInstr *> &backtrack,
                      bool MovingDependentOp, bool PathInRegion);
 
  // Insert temporary MI copy into MBB.
  MachineBasicBlock::instr_iterator
  insertTempCopy(MachineBasicBlock *MBB,
                 MachineBasicBlock::iterator &TargetPacket, MachineInstr *MI,
                 bool DeleteOldCopy);
 
  MachineBasicBlock::instr_iterator
  findInsertPositionInBundle(MachineBasicBlock::iterator &Bundle,
                             MachineInstr *MI, bool &LastInBundle);
 
  bool NeedToNewify(MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
                    MachineInstr *TargetPacket);
 
  bool CanNewifiedBeUsedInBundle(MachineBasicBlock::instr_iterator NewMI,
                                 unsigned DepReg, MachineInstr *TargetPacket);
 
  void addInstructionToExistingBundle(MachineBasicBlock *HomeBB,
                                      MachineBasicBlock::instr_iterator &Head,
                                      MachineBasicBlock::instr_iterator &Tail,
                                      MachineBasicBlock::instr_iterator &NewMI,
                                      MachineBasicBlock::iterator &TargetPacket,
                                      MachineBasicBlock::iterator &NextMI,
                                      std::vector<MachineInstr *> &backtrack);
 
  void removeInstructionFromExistingBundle(
      MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
      MachineBasicBlock::instr_iterator &Tail,
      MachineBasicBlock::iterator &SourceLocation,
      MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
      std::vector<MachineInstr *> &backtrack);
 
  // Check for conditional register operaton.
  bool MIsCondAssign(MachineInstr *BMI, MachineInstr *MI,
                     SmallVector<unsigned, 4> &Defs);
 
  // Test all the conditions required for instruction to be
  // speculative. These are just required conditions, cost
  // or benefit should be computed elsewhere.
  bool canMIBeSpeculated(MachineInstr *MI, MachineBasicBlock *ToBB,
                         MachineBasicBlock *FromBB,
                         std::vector<MachineInstr *> &backtrack);
 
  // See if this branch target belongs to the current region.
  bool isBranchWithinRegion(BasicBlockRegion *CurrentRegion, MachineInstr *MI);
 
  // A collection of low level utilities.
  bool MIsAreDependent(MachineInstr *MIa, MachineInstr *MIb);
  bool MIsHaveTrueDependency(MachineInstr *MIa, MachineInstr *MIb);
  bool canReorderMIs(MachineInstr *MIa, MachineInstr *MIb);
  bool canCauseStall(MachineInstr *MI, MachineInstr *MJ);
  bool canThisMIBeMoved(MachineInstr *MI,
                        MachineBasicBlock::iterator &WorkPoint,
                        bool &MovingDependentOp, int &Cost);
  bool MIisDualJumpCandidate(MachineInstr *MI,
                             MachineBasicBlock::iterator &WorkPoint);
  bool DemoteToDotOld(MachineInstr *MI);
  bool isNewifiable(MachineBasicBlock::instr_iterator MII, unsigned DepReg,
                    MachineInstr *TargetPacket);
  bool IsNewifyStore(MachineInstr *MI);
  bool isJumpOutOfRange(MachineInstr *MI);
  bool IsDualJumpFirstCandidate(MachineInstr *MI);
  bool IsDualJumpFirstCandidate(MachineBasicBlock *MBB);
  bool IsDualJumpFirstCandidate(MachineBasicBlock::iterator &TargetPacket);
  bool IsNotDualJumpFirstCandidate(MachineInstr *MI);
  bool isJumpOutOfRange(MachineInstr *UnCond, MachineInstr *Cond);
  bool IsDualJumpSecondCandidate(MachineInstr *MI);
  bool tryAllocateResourcesForConstExt(MachineInstr *MI, bool UpdateState);
  bool isCompoundPair(MachineInstr *MIa, MachineInstr *MIb);
  bool doesMIDefinesPredicate(MachineInstr *MI, SmallVector<unsigned, 4> &Defs);
  bool AnalyzeBBBranches(MachineBasicBlock *MBB, MachineBasicBlock *&TBB,
                         MachineInstr *&FirstTerm, MachineBasicBlock *&FBB,
                         MachineInstr *&SecondTerm);
  inline bool multipleBranchesFromToBB(MachineBasicBlock *BB) const;
};
} // namespace
 
INITIALIZE_PASS_BEGIN(HexagonGlobalScheduler, "global-sched",
                      "Hexagon Global Scheduler", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfoWrapperPass)
INITIALIZE_PASS_END(HexagonGlobalScheduler, "global-sched",
                    "Hexagon Global Scheduler", false, false)
 
/// HexagonGlobalSchedulerImpl Ctor.
HexagonGlobalSchedulerImpl::HexagonGlobalSchedulerImpl(
    MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT,
    AliasAnalysis *AA, const MachineBranchProbabilityInfo *MBPI,
    const MachineBlockFrequencyInfo *MBFI, const MachineRegisterInfo *MRI,
    const MachineFrameInfo &MFI, const HexagonRegisterInfo *QRI)
    : HexagonPacketizerList(MF, MLI, AA, nullptr, false), PullUpRegions(0),
      CurrentState((const HexagonInstrInfo *)TII), AA(AA), MBPI(MBPI),
      MBFI(MBFI), MRI(MRI), MFI(MFI), QRI(QRI), MLI(MLI), MDT(MDT),
      PacketSize(MF.getSubtarget().getSchedModel().IssueWidth) {
  QII = (const HexagonInstrInfo *)TII;
  Ext = BuildMI(MF, DebugLoc(), QII->get(Hexagon::A4_ext));
  Nop = BuildMI(MF, DebugLoc(), QII->get(Hexagon::A2_nop));
  TSchedModel.init(&MF.getSubtarget());
}
 
// Return bundle size without debug instructions.
static unsigned nonDbgBundleSize(MachineBasicBlock::iterator &TargetPacket) {
  MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
  MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
  unsigned count = 0;
  for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
    if (MII->isDebugInstr())
      continue;
    count++;
  }
  return count;
}
 
/// The pass main entry point.
bool HexagonGlobalScheduler::runOnMachineFunction(MachineFunction &Fn) {
  auto &HST = Fn.getSubtarget<HexagonSubtarget>();
  if (DisablePullUp || !HST.usePackets() || skipFunction(Fn.getFunction()))
    return false;
 
  const MachineRegisterInfo *MRI = &Fn.getRegInfo();
  const MachineFrameInfo &MFI = Fn.getFrameInfo();
  const HexagonRegisterInfo *QRI = HST.getRegisterInfo();
  MachineLoopInfo &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
  MachineDominatorTree &MDT =
      getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
  const MachineBranchProbabilityInfo *MBPI =
      &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
  const MachineBlockFrequencyInfo *MBFI =
      &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI();
  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
  // Preserve comounds if Opt Size.
  const Function &F = Fn.getFunction();
  if (F.hasOptSize() && PreventCompoundSeparation.getNumOccurrences() == 0)
    PreventCompoundSeparation = true;
 
  // Instantiate the Scheduler.
  HexagonGlobalSchedulerImpl GlobalSchedulerState(Fn, MLI, MDT, AA, MBPI, MBFI,
                                                  MRI, MFI, QRI);
 
  // DFA state table should not be empty.
  assert(GlobalSchedulerState.getResourceTracker() && "Empty DFA table!");
 
  // Loop over all of the basic blocks.
  // PullUp regions are basically traces with no side entrances.
  // Might want to traverse BB by frequency.
  GlobalSchedulerState.checkBundleCounts(Fn);
 
  // Pullup does not handle hazards yet.
  if (!DisablePullUp.getPosition() && ForceNoopHazards)
    return true;
 
  LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
  GlobalSchedulerState.GenUseDefChain(Fn);
  GlobalSchedulerState.formPullUpRegions(Fn);
  GlobalSchedulerState.performPullUp();
  GlobalSchedulerState.performPullUpCFG(Fn);
  if (PostPullUpOpt) {
    GlobalSchedulerState.formPullUpRegions(Fn);
    GlobalSchedulerState.performExposedOptimizations(Fn);
  }
  LLVM_DEBUG(GlobalSchedulerState.countCompounds(Fn));
 
  return true;
}
 
/// Allocate resources (i.e. 4 bytes) for constant extender. If succeess, return
/// true, otherwise, return false.
bool HexagonGlobalSchedulerImpl::tryAllocateResourcesForConstExt(
    MachineInstr *MI, bool UpdateState = true) {
  if (ResourceTracker->canReserveResources(*Ext)) {
    // We do not always want to change the state of ResourceTracker.
    // When we do not want to change it, we need to test for additional
    // corner cases.
    if (UpdateState)
      ResourceTracker->reserveResources(*Ext);
    else if (CurrentPacketMIs.size() >= PacketSize - 1)
      return false;
    return true;
  }
 
  return false;
}
 
static bool IsSchedBarrier(const MachineInstr *MI) {
  return MI->getOpcode() == Hexagon::Y2_barrier;
}
 
static bool IsIndirectCall(const MachineInstr *MI) {
  return MI->getOpcode() == Hexagon::J2_callr;
}
 
#ifndef NDEBUG
static void DumpLinked(MachineInstr *MI) {
  if (MI->isBundledWithPred())
    dbgs() << "^";
  else
    dbgs() << " ";
  if (MI->isBundledWithSucc())
    dbgs() << "v";
  else
    dbgs() << " ";
  MI->dump();
}
 
static void DumpPacket(MachineBasicBlock::instr_iterator MII) {
  if (MII == MachineBasicBlock::instr_iterator()) {
    dbgs() << "\tNULL\n";
    return;
  }
  MachineInstr *MI = &*MII;
  MachineBasicBlock *MBB = MI->getParent();
  // Uninserted instruction.
  if (!MBB) {
    dbgs() << "\tUnattached: ";
    DumpLinked(MI);
    return;
  }
  dbgs() << "\t";
  DumpLinked(MI);
  if (MI->isBundle()) {
    MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
    for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
         ++MII) {
      dbgs() << "\t\t*";
      DumpLinked(&*MII);
    }
  }
}
 
static void DumpPacket(MachineBasicBlock::instr_iterator MII,
                       MachineBasicBlock::instr_iterator BBEnd) {
  if (MII == BBEnd) {
    dbgs() << "\tBBEnd\n";
    return;
  }
 
  DumpPacket(MII);
}
#endif
 
static bool isBranch(MachineInstr *MI) {
  if (MI->isBundle()) {
    MachineBasicBlock::instr_iterator MII = MI->getIterator();
    MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
    for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
         ++MII) {
      if (MII->isBranch())
        return true;
    }
  } else
    return MI->isBranch();
  return false;
}
 
/// Any of those must not be first dual jump. Everything else is OK.
bool HexagonGlobalSchedulerImpl::IsNotDualJumpFirstCandidate(MachineInstr *MI) {
  if (MI->isCall() || (MI->isBranch() && !QII->isPredicated(*MI)) ||
      MI->isReturn() || QII->isEndLoopN(MI->getOpcode()))
    return true;
  return false;
}
 
/// These four functions clearly belong in HexagonInstrInfo.cpp.
/// Is this MI could be first dual jump instruction?
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(MachineInstr *MI) {
  if (!PerformDualJumps)
    return false;
  if (MI->isBranch() && QII->isPredicated(*MI) && !QII->isNewValueJump(*MI) &&
      !MI->isIndirectBranch() && !QII->isEndLoopN(MI->getOpcode()))
    return true;
  // Missing loopN here, but not sure if there will be any benefit from it.
  return false;
}
 
/// This version covers the whole packet.
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
    MachineBasicBlock::iterator &TargetPacket) {
  if (!PerformDualJumps)
    return false;
  MachineInstr *MI = &*TargetPacket;
 
  if (MI->isBundle()) {
    // If this is a bundle, it must be the last bundle in BB.
    if (&(*MI->getParent()->rbegin()) != MI)
      return false;
 
    MachineBasicBlock::instr_iterator MII = MI->getIterator();
    MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
    // If there is a control flow op in this packet, this is the case
    // we look for, even if they are dependent on other members.
    for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
         ++MII)
      if (IsNotDualJumpFirstCandidate(&*MII))
        return false;
  } else
    return IsDualJumpFirstCandidate(MI);
 
  return true;
}
 
/// This version cover whole BB. There could be a BB
/// with no control flow in it. In this case we can still pull-up a jump
/// into it. Negative proof.
bool HexagonGlobalSchedulerImpl::IsDualJumpFirstCandidate(
    MachineBasicBlock *MBB) {
  if (!PerformDualJumps)
    return false;
 
  for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
                                         MBBEnd = MBB->instr_end();
       MII != MBBEnd; ++MII) {
    MachineInstr *MI = &*MII;
    if (MI->isDebugInstr())
      continue;
    if (!MI->isBundle() && IsNotDualJumpFirstCandidate(MI))
      return false;
  }
  return true;
}
 
/// Is this MI could be second dual jump instruction?
bool HexagonGlobalSchedulerImpl::IsDualJumpSecondCandidate(MachineInstr *MI) {
  if (!PerformDualJumps)
    return false;
  if ((MI->isBranch() && !QII->isNewValueJump(*MI) && !MI->isIndirectBranch() &&
       !QII->isEndLoopN(MI->getOpcode())) ||
      (MI->isCall() && !IsIndirectCall(MI)))
    return true;
  return false;
}
 
// Since we have no exact knowledge of code layout,
// allow some safety buffer for jump target.
// This is measured in bytes.
static const unsigned SafetyBuffer = 200;
 
static MachineBasicBlock::instr_iterator
getHexagonFirstInstrTerminator(MachineBasicBlock *MBB) {
  MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
  MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
  MachineBasicBlock::instr_iterator MII = MIB;
  while (MII != MIE) {
    if (!MII->isBundle() && MII->isTerminator())
      return MII;
    ++MII;
  }
  return MIE;
}
 
/// Check if a given instruction is:
/// - a jump to a distant target
/// - that exceeds its immediate range
/// If both conditions are true, it requires constant extension.
bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *MI) {
  if (!MI || !MI->isBranch())
    return false;
  MachineBasicBlock *MBB = MI->getParent();
  auto FirstTerm = getHexagonFirstInstrTerminator(MBB);
  if (FirstTerm == MBB->instr_end())
    return false;
 
  unsigned InstOffset = BlockToInstOffset[MBB];
  unsigned Distance = 0;
  MachineBasicBlock::instr_iterator FTMII = FirstTerm;
 
  // To save time, estimate exact position of a branch instruction
  // as one at the end of the MBB.
  // Number of instructions times typical instruction size.
  InstOffset += (QII->nonDbgBBSize(MBB) * HEXAGON_INSTR_SIZE);
 
  MachineBasicBlock *TBB = NULL, *FBB = NULL;
  SmallVector<MachineOperand, 4> Cond;
 
  // Try to analyze this branch.
  if (QII->analyzeBranch(*MBB, TBB, FBB, Cond, false)) {
    // Could not analyze it. See if this is something we can recognize.
    // If it is a NVJ, it should always have its target in
    // a fixed location.
    if (QII->isNewValueJump(*FirstTerm))
      TBB = FirstTerm->getOperand(QII->getCExtOpNum(*FirstTerm)).getMBB();
  }
  if (TBB && (MI == &*FirstTerm)) {
    Distance =
        (unsigned)std::abs((long long)InstOffset - BlockToInstOffset[TBB]) +
        SafetyBuffer;
    LLVM_DEBUG(dbgs() << "\tFirst term offset(" << Distance << "): ";
               FirstTerm->dump());
    return !QII->isJumpWithinBranchRange(*FirstTerm, Distance);
  }
  if (FBB) {
    // Look for second terminator.
    FTMII++;
    MachineInstr *SecondTerm = &*FTMII;
    assert(FTMII != MBB->instr_end() &&
           (SecondTerm->isBranch() || SecondTerm->isCall()) &&
           "Bad second terminator");
    if (MI != SecondTerm)
      return false;
    // Analyze the second branch in the BB.
    Distance =
        (unsigned)std::abs((long long)InstOffset - BlockToInstOffset[FBB]) +
        SafetyBuffer;
    LLVM_DEBUG(dbgs() << "\tSecond term offset(" << Distance << "): ";
               FirstTerm->dump());
    return !QII->isJumpWithinBranchRange(*SecondTerm, Distance);
  }
  return false;
}
 
/// Returns true if an instruction can be promoted to .new predicate
/// or new-value store.
/// Performs implicit version checking.
bool HexagonGlobalSchedulerImpl::isNewifiable(
    MachineBasicBlock::instr_iterator MII, unsigned DepReg,
    MachineInstr *TargetPacket) {
  MachineInstr *MI = &*MII;
  if (QII->isDotNewInst(*MI) ||
      !CanNewifiedBeUsedInBundle(MII, DepReg, TargetPacket))
    return false;
  return (QII->isPredicated(*MI) && QII->getDotNewPredOp(*MI, nullptr) > 0) ||
         QII->mayBeNewStore(*MI);
}
 
bool HexagonGlobalSchedulerImpl::DemoteToDotOld(MachineInstr *MI) {
  int NewOpcode = QII->getDotOldOp(*MI);
  MI->setDesc(QII->get(NewOpcode));
  return true;
}
 
// initPacketizerState - Initialize packetizer flags
void HexagonGlobalSchedulerImpl::initPacketizerState(void) {
  CurrentPacketMIs.clear();
  return;
}
 
// ignorePseudoInstruction - Ignore bundling of pseudo instructions.
bool HexagonGlobalSchedulerImpl::ignoreInstruction(MachineInstr *MI) {
  if (MI->isDebugInstr())
    return true;
 
  // We must print out inline assembly
  if (MI->isInlineAsm())
    return false;
 
  // We check if MI has any functional units mapped to it.
  // If it doesn't, we ignore the instruction.
  const MCInstrDesc &TID = MI->getDesc();
  unsigned SchedClass = TID.getSchedClass();
  const InstrStage *IS =
      ResourceTracker->getInstrItins()->beginStage(SchedClass);
  unsigned FuncUnits = IS->getUnits();
  return !FuncUnits;
}
 
// isSoloInstruction: - Returns true for instructions that must be
// scheduled in their own packet.
bool HexagonGlobalSchedulerImpl::isSoloInstruction(const MachineInstr &MI) {
  if (MI.isInlineAsm())
    return true;
 
  if (MI.isEHLabel())
    return true;
 
  // From Hexagon V4 Programmer's Reference Manual 3.4.4 Grouping constraints:
  // trap, pause, barrier, icinva, isync, and syncht are solo instructions.
  // They must not be grouped with other instructions in a packet.
  if (IsSchedBarrier(&MI))
    return true;
 
  if (MI.getOpcode() == Hexagon::A2_nop)
    return true;
 
  return false;
}
 
/// Return region ptr or null if non found.
BasicBlockRegion *HexagonGlobalSchedulerImpl::getRegionForMBB(
    std::vector<BasicBlockRegion *> &Regions, MachineBasicBlock *MBB) {
  for (std::vector<BasicBlockRegion *>::iterator I = Regions.begin(),
                                                 E = Regions.end();
       I != E; ++I) {
    if ((*I)->findMBB(MBB))
      return *I;
  }
  return NULL;
}
 
/// Select best candidate to form regions.
static inline bool selectBestBB(BlockFrequency &BBaFreq, unsigned BBaSize,
                                BlockFrequency &BBbFreq, unsigned BBbSize) {
  if (BBaFreq.getFrequency() > BBbFreq.getFrequency())
    return true;
  // TODO: This needs fine tuning.
  // if (BBaSize < BBbSize)
  //  return true;
  if (BBaFreq.getFrequency() == BBbFreq.getFrequency())
    return true;
  return false;
}
 
/// Returns BB pointer if one of MBB successors should be added to the
/// current PullUp Region, NULL otherwise.
/// If SecondBest is defined, get next one after Best match.
/// Most of the time, since we practically always have only two successors,
/// this is "the other" BB successor which still matches original
/// selection criterion.
MachineBasicBlock *
HexagonGlobalSchedulerImpl::getNextPURBB(MachineBasicBlock *MBB,
                                         bool SecondBest = false) {
  if (!MBB)
    return NULL;
 
  BlockFrequency BestBlockFreq = BlockFrequency(0);
  unsigned BestBlockSize = 0;
  MachineBasicBlock *BestBB = NULL;
  MachineBasicBlock *SecondBestBB = NULL;
 
  // Catch single BB loops.
  for (MachineBasicBlock *Succ : MBB->successors())
    if (Succ == MBB)
      return NULL;
 
  // Iterate through successors to MBB.
  for (MachineBasicBlock *Succ : MBB->successors()) {
    BlockFrequency BlockFreq = MBFI->getBlockFreq(Succ);
 
    LLVM_DEBUG(dbgs() << "\tsucc BB(" << Succ->getNumber() << ") freq("
                      << BlockFreq.getFrequency() << ")");
 
    if (!SecondBest && getRegionForMBB(PullUpRegions, Succ))
      continue;
 
    // If there is more then one predecessor to this block, do not include it.
    // It means there is a side entrance to it.
    if (Succ->pred_size() > 1)
      continue;
 
    // If this block is a target of an indirect branch, it should
    // also not be included.
    if (Succ->isEHPad() || Succ->hasAddressTaken())
      continue;
 
    // Get BB edge frequency.
    BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(MBB, Succ);
    LLVM_DEBUG(dbgs() << "\tedge with freq(" << EdgeFreq.getFrequency()
                      << ")\n");
 
    if (selectBestBB(EdgeFreq, QII->nonDbgBBSize(Succ), BestBlockFreq,
                     BestBlockSize)) {
      BestBlockFreq = EdgeFreq;
      BestBlockSize = QII->nonDbgBBSize(Succ);
      SecondBestBB = BestBB;
      BestBB = Succ;
    } else if (!SecondBestBB) {
      SecondBestBB = Succ;
    }
  }
  if (SecondBest)
    return SecondBestBB;
  else
    return BestBB;
}
 
/// Form region to perform pull-up.
bool HexagonGlobalSchedulerImpl::formPullUpRegions(MachineFunction &Fn) {
  const Function &F = Fn.getFunction();
  // Check for single-block functions and skip them.
  if (std::next(F.begin()) == F.end())
    return false;
 
  // Compute map for BB distances.
  // Offset of the current instruction from the start.
  unsigned InstOffset = 0;
 
  LLVM_DEBUG(dbgs() << "****** Form PullUpRegions **************\n");
  // Loop over all basic blocks.
  // PullUp regions are basically traces with no side entrances.
  for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
       ++MBB) {
    if (MBB->getAlignment() > llvm::Align(1)) {
      // Although we don't know the exact layout of the final code, we need
      // to account for alignment padding somehow. This heuristic pads each
      // aligned basic block according to the alignment value.
      int ByteAlign = MBB->getAlignment().value() - 1;
      InstOffset = (InstOffset + ByteAlign) & ~(ByteAlign);
    }
    // Remember BB layout offset.
    BlockToInstOffset[&*MBB] = InstOffset;
    for (MachineBasicBlock::instr_iterator MII = MBB->instr_begin(),
                                           MIE = MBB->instr_end();
         MII != MIE; ++MII)
      if (!MII->isBundle())
        InstOffset += QII->getSize(*MII);
 
    // If this BB is already in a region, move on.
    if (getRegionForMBB(PullUpRegions, &*MBB))
      continue;
 
    LLVM_DEBUG(dbgs() << "\nRoot BB(" << MBB->getNumber() << ") name("
                      << MBB->getName() << ") size(" << QII->nonDbgBBSize(&*MBB)
                      << ") freq(" << printBlockFreq(*MBFI, *MBB)
                      << ") pred_size(" << MBB->pred_size() << ") in_func("
                      << MBB->getParent()->getFunction().getName() << ")\n");
 
    BasicBlockRegion *PUR = new BasicBlockRegion(TII, QRI, &*MBB);
    PullUpRegions.push_back(PUR);
 
    for (MachineBasicBlock *MBBR = getNextPURBB(&*MBB); MBBR;
         MBBR = getNextPURBB(MBBR)) {
      LLVM_DEBUG(dbgs() << "Add BB(" << MBBR->getNumber() << ") name("
                        << MBBR->getName() << ") size("
                        << QII->nonDbgBBSize(MBBR) << ") freq("
                        << printBlockFreq(*MBFI, *MBBR) << ") in_func("
                        << MBBR->getParent()->getFunction().getName() << ")\n");
      PUR->addBBtoRegion(MBBR);
    }
  }
  return true;
}
 
/// Return true if MI is an instruction we are unable to reason about
/// (like something with unmodeled memory side effects).
static inline bool isGlobalMemoryObject(MachineInstr *MI) {
  if (MI->hasUnmodeledSideEffects() || MI->hasOrderedMemoryRef() ||
      MI->isCall() ||
      (MI->getOpcode() == Hexagon::J2_jump && !MI->getOperand(0).isMBB()))
    return true;
  return false;
}
 
// This MI might have either incomplete info, or known to be unsafe
// to deal with (i.e. volatile object).
static inline bool isUnsafeMemoryObject(MachineInstr *MI) {
  if (!MI || MI->memoperands_empty())
    return true;
 
  // We purposefully do no check for hasOneMemOperand() here
  // in hope to trigger an assert downstream in order to
  // finish implementation.
  if ((*MI->memoperands_begin())->isVolatile() || MI->hasUnmodeledSideEffects())
    return true;
 
  if (!(*MI->memoperands_begin())->getValue())
    return true;
 
  return false;
}
 
/// This returns true if the two MIs could be memory dependent.
static bool MIsNeedChainEdge(AliasAnalysis *AA, const TargetInstrInfo *TII,
                             MachineInstr *MIa, MachineInstr *MIb) {
  // Cover a trivial case - no edge is need to itself.
  if (MIa == MIb)
    return false;
 
  if (TII->areMemAccessesTriviallyDisjoint(*MIa, *MIb))
    return false;
 
  if (isUnsafeMemoryObject(MIa) || isUnsafeMemoryObject(MIb))
    return true;
 
  // If we are dealing with two "normal" loads, we do not need an edge
  // between them - they could be reordered.
  if (!MIa->mayStore() && !MIb->mayStore())
    return false;
 
  // To this point analysis is generic. From here on we do need AA.
  if (!AA)
    return true;
 
  MachineMemOperand *MMOa = *MIa->memoperands_begin();
  MachineMemOperand *MMOb = *MIb->memoperands_begin();
 
  // TODO: Need to handle multiple memory operands.
  // if either instruction has more than one memory operand, punt.
  if (!(MIa->hasOneMemOperand() && MIb->hasOneMemOperand()))
    return true;
 
  if (!MMOa->getSize().hasValue() || !MMOb->getSize().hasValue())
    return true;
 
  assert((MMOa->getOffset() >= 0) && "Negative MachineMemOperand offset");
  assert((MMOb->getOffset() >= 0) && "Negative MachineMemOperand offset");
  assert((MMOa->getSize().hasValue() && MMOb->getSize().hasValue()) &&
         "Size 0 memory access");
 
  // If the base address of the two memoperands is the same. For instance,
  // x and x+4, then we can easily reason about them using the offset and size
  // of access.
  if (MMOa->getValue() == MMOb->getValue()) {
    if (MMOa->getOffset() > MMOb->getOffset()) {
      uint64_t offDiff = MMOa->getOffset() - MMOb->getOffset();
      return !(MMOb->getSize().getValue() <= offDiff);
    } else if (MMOa->getOffset() < MMOb->getOffset()) {
      uint64_t offDiff = MMOb->getOffset() - MMOa->getOffset();
      return !(MMOa->getSize().getValue() <= offDiff);
    }
    // MMOa->getOffset() == MMOb->getOffset()
    return true;
  }
 
  int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
  int64_t Overlapa = MMOa->getSize().getValue() + MMOa->getOffset() - MinOffset;
  int64_t Overlapb = MMOb->getSize().getValue() + MMOb->getOffset() - MinOffset;
 
  AliasResult AAResult =
      AA->alias(MemoryLocation(MMOa->getValue(), Overlapa, MMOa->getAAInfo()),
                MemoryLocation(MMOb->getValue(), Overlapb, MMOb->getAAInfo()));
 
  return (AAResult != AliasResult::NoAlias);
}
 
/// Gather register def/uses from MI.
/// This treats possible (predicated) defs
/// as actually happening ones (conservatively).
static inline void parseOperands(MachineInstr *MI,
                                 SmallVector<unsigned, 4> &Defs,
                                 SmallVector<unsigned, 8> &Uses) {
  Defs.clear();
  Uses.clear();
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
 
    if (MO.isReg()) {
      unsigned Reg = MO.getReg();
      if (!Reg)
        continue;
      assert(Register::isPhysicalRegister(Reg));
      if (MO.isUse())
        Uses.push_back(MO.getReg());
      if (MO.isDef())
        Defs.push_back(MO.getReg());
    } else if (MO.isRegMask()) {
      for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
        if (MO.clobbersPhysReg(R))
          Defs.push_back(R);
    }
  }
}
 
void HexagonGlobalSchedulerImpl::MIUseDefSet(MachineInstr *MI,
                                             std::vector<unsigned> &Defs,
                                             std::vector<unsigned> &Uses) {
  Defs.clear();
  Uses.clear();
  assert(!MI->isBundle() && "Cannot parse regs of a bundle.");
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
 
    if (MO.isReg()) {
      unsigned Reg = MO.getReg();
      if (!Reg)
        continue;
      assert(Register::isPhysicalRegister(Reg));
      std::vector<unsigned> &Refs = MO.isUse() ? Uses : Defs;
      for (MCRegAliasIterator AI(MO.getReg(), QRI, true); AI.isValid(); ++AI)
        Refs.push_back(*AI);
    } else if (MO.isRegMask()) {
      for (unsigned R = 1, NR = Hexagon::NUM_TARGET_REGS; R != NR; ++R)
        if (MO.clobbersPhysReg(R))
          Defs.push_back(R);
    }
  }
}
 
/// Some apparent dependencies are not actually restricting us since there
/// is a delay between assignment and actual usage, like in case of a call.
/// There could be more cases here, but this one seems the most obvious.
static bool isDelayedUseException(MachineInstr *MIa, MachineInstr *MIb) {
  if (MIa->isCall() && !MIb->isCall())
    return true;
  if (!MIa->isCall() && MIb->isCall())
    return true;
  return false;
}
 
/// This is a check for resources availability and dependency
/// for an MI being tried for an existing bundle.
/// This is needed because we can:
///   - save time by filtering out trivial cases
///   - we want to reuse infrastructure that does not really knows
///     how to deal with parallel semantics of a bundle that already
///     exists. For instance, the following case:
///     SI %R6<def> = L2_ploadrif_io %P0<kill>, %R7, 4;
///     SJ %R6<def> = A2_tfr %R0;
///     will be happily allowed by isLegalToPacketizeTogether since in serial
///     semantics it never happens, and even if it does, it is legal. Not so
///     for when we __speculatively__ trying and MI for a bundle.
///
/// Note:  This is not equivalent to MIsAreDependent().
/// MIsAreDependent only understands serial semantics.
/// These are OK to packetize together:
///  %R0<def> = L2_loadri_io %R18, 76; mem:LD4[%sunkaddr226](tbaa=!"int")
///  %R2<def> = ASL %R0<kill>, 3; flags:  Inside bundle
///
bool HexagonGlobalSchedulerImpl::canAddMIToThisPacket(
    MachineInstr *MI,
    SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> &Bundle) {
  if (!MI)
    return false;
  LLVM_DEBUG(dbgs() << "\n\t[canAddMIToThisPacket]: "; MI->dump());
 
  // Const extenders need custom resource checking...
  // Should be OK if we can update the check everywhere.
  if ((QII->isConstExtended(*MI) || QII->isExtended(*MI) ||
       isJumpOutOfRange(MI)) &&
      !tryAllocateResourcesForConstExt(MI, false))
    return false;
 
  // Ask DFA if machine resource is available for MI.
  if (!ResourceTracker->canReserveResources(*MI) || !shouldAddToPacket(*MI)) {
    LLVM_DEBUG(dbgs() << "\tNo DFA resources.\n");
    return false;
  }
 
  SmallVector<unsigned, 4> BundleDefs;
  SmallVector<unsigned, 8> BundleUses;
  SmallVector<unsigned, 4> Defs;
  SmallVector<unsigned, 8> Uses;
  MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
  MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
 
  parseOperands(MI, Defs, Uses);
  for (SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE>::iterator
           BI = Bundle.begin(),
           BE = Bundle.end();
       BI != BE; ++BI) {
    BundleDefs.clear();
    BundleUses.clear();
    parseOperands(*BI, BundleDefs, BundleUses);
 
    MachineInstr *Inst1 = *BI;
    MachineInstr *Inst2 = MI;
 
    if (Inst1->getParent() && OneFloatPerPacket && QII->isFloat(*Inst1) &&
        QII->isFloat(*Inst2))
      return false;
 
    if (Inst1->getParent() && OneComplexPerPacket && QII->isComplex(*Inst1) &&
        QII->isComplex(*Inst2))
      return false;
 
    if (PreventCompoundSeparation)
      if (QII->getCompoundCandidateGroup(**BI)) {
        if (!FirstCompound)
          FirstCompound = *BI;
        else {
          SecondCompound = *BI;
          if (isCompoundPair(FirstCompound, SecondCompound)) {
            if (MI->mayLoad() || MI->mayStore()) {
              LLVM_DEBUG(dbgs() << "\tPrevent compound destruction.\n");
              return false;
            }
          }
        }
      }
    if (PreventDuplexSeparation)
      if (QII->getDuplexCandidateGroup(**BI)) {
        if (!FirstDuplex)
          FirstDuplex = *BI;
        else {
          SecondDuplex = *BI;
          if (QII->isDuplexPair(*FirstDuplex, *SecondDuplex)) {
            if (MI->mayLoad() || MI->mayStore()) {
              LLVM_DEBUG(dbgs() << "\tPrevent duplex destruction.\n");
              return false;
            }
          }
        }
      }
 
    for (unsigned i = 0; i < Defs.size(); i++) {
      // Check for multiple definitions in the same packet.
      for (unsigned j = 0; j < BundleDefs.size(); j++)
        // Multiple defs in the same packet.
        // Calls are OK here.
        // Also if we have multiple defs of PC, this simply means we are
        // dealing with dual jumps.
        if (AliasingRegs(Defs[i], BundleDefs[j]) &&
            !isDelayedUseException(MI, *BI) &&
            !(IsDualJumpFirstCandidate(*BI) && IsDualJumpSecondCandidate(MI))) {
          LLVM_DEBUG(dbgs() << "\tMultiple defs.\n\t"; MI->dump();
                     dbgs() << "\t"; (*BI)->dump());
          return false;
        }
 
      // See if we are creating a swap case as we go, and disallow
      // it for now.
      // Also, this is not OK:
      //  if (!p0) r7 = r5
      //  if (!p0) r5 = #0
      // But this is fine:
      //  if (!p0) r7 = r5
      //  if (p0) r5 = #0
      // Aslo - this is not a swap, but an opportunity to newify:
      // %P1<def> = C2_cmpeqi %R0, 0; flags:
      // %R0<def> = L2_ploadrif_io %P1<kill>, %R29, 8;
      // TODO: Handle this.
      for (unsigned j = 0; j < BundleUses.size(); j++)
        if (AliasingRegs(Defs[i], BundleUses[j])) {
          for (unsigned k = 0; k < BundleDefs.size(); k++)
            for (unsigned l = 0; l < Uses.size(); l++) {
              if (AliasingRegs(BundleDefs[k], Uses[l]) &&
                  !isDelayedUseException(MI, *BI)) {
                LLVM_DEBUG(dbgs() << "\tSwap detected:\n\t"; MI->dump();
                           dbgs() << "\t"; (*BI)->dump());
                return false;
              }
            }
        }
    }
 
    for (unsigned i = 0; i < Uses.size(); i++) {
      // Check for true data dependency.
      for (unsigned j = 0; j < BundleDefs.size(); j++)
        if (AliasingRegs(Uses[i], BundleDefs[j]) &&
            !isDelayedUseException(MI, *BI)) {
          LLVM_DEBUG(dbgs() << "\tImmediate Use detected on reg("
                            << printReg(Uses[i], QRI) << ")\n\t";
                     MI->dump(); dbgs() << "\t"; (*BI)->dump());
          // TODO: This could be an opportunity for newifying:
          //  %P0<def> = C2_cmpeqi %R26, 0
          //  %R26<def> = A2_tfr %R0<kill>
          // if (CanPromoteToDotNew(MI, Uses[i]))
          //  LLVM_DEBUG(dbgs() << "\tCan promoto to .new form.\n");
          // else
          return false;
        }
    }
 
    // For calls we also check callee save regs.
    if ((*BI)->isCall()) {
      for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
        for (unsigned i = 0; i < Defs.size(); i++) {
          if (AliasingRegs(Defs[i], *I)) {
            LLVM_DEBUG(dbgs() << "\tAlias with call.\n");
            return false;
          }
        }
      }
    }
 
    // If this is return, we are probably speculating (otherwise
    // we could not pull in there) and will not win from pulling
    // into this location anyhow.
    // Example: a side exit.
    // if (!p0) dealloc_return
    // TODO: Can check that we do not overwrite return value
    // and proceed.
    if ((*BI)->isBarrier()) {
      LLVM_DEBUG(dbgs() << "\tBarrier interference.\n");
      return false;
    }
 
    // \ref-manual (7.3.4) A loop setup packet in loopN or spNloop0 cannot
    // contain a speculative indirect jump,
    // a new-value compare jump or a dealloc_return.
    // Speculative indirect jumps (predicate + .new + indirect):
    // if ([!]Ps.new) jumpr:t Rs
    // if ([!]Ps.new) jumpr:nt Rs
    // @note: We don't want to pull across a call to be on the safe side.
    if (QII->isLoopN(*MI) &&
        ((QII->isPredicated(**BI) && QII->isPredicatedNew(**BI) &&
          QII->isJumpR(**BI)) ||
         QII->isNewValueJump(**BI) || QII->isDeallocRet(**BI) ||
         (*BI)->isCall())) {
      LLVM_DEBUG(dbgs() << "\tLoopN pull interference.\n");
      return false;
    }
 
    // The opposite is also true.
    if (QII->isLoopN(**BI) &&
        ((QII->isPredicated(*MI) && QII->isPredicatedNew(*MI) &&
          QII->isJumpR(*MI)) ||
         QII->isNewValueJump(*MI) || QII->isDeallocRet(*MI) || MI->isCall())) {
      LLVM_DEBUG(dbgs() << "\tResident LoopN.\n");
      return false;
    }
 
    // @todo \ref-manual 7.6.1
    // Presence of NVJ adds more restrictions.
    if (QII->isNewValueJump(**BI) &&
        (MI->mayStore() || MI->getOpcode() == Hexagon::S2_allocframe ||
         MI->isCall())) {
      LLVM_DEBUG(dbgs() << "\tNew val Jump.\n");
      return false;
    }
 
    // For memory operations, check aliasing.
    // First, be conservative on these objects. Might be overly constraining,
    // so recheck.
    if (isGlobalMemoryObject(*BI) || isGlobalMemoryObject(MI))
      // Currently it catches things like this:
      // S2_storerinew_io %R29, 32, %R16
      // S2_storeri_io %R29, 68, %R0
      // which we can reason about.
      // TODO: revisit.
      return false;
 
    // If packet has a new-value store, MI can't be a store instruction.
    if (QII->isNewValueStore(**BI) && MI->mayStore()) {
      LLVM_DEBUG(dbgs() << "\tNew Value Store to store.\n");
      return false;
    }
 
    if ((QII->isMemOp(**BI) && MI->mayStore()) ||
        (QII->isMemOp(*MI) && (*BI)->mayStore())) {
      LLVM_DEBUG(
          dbgs() << "\tSlot 0 not available for store because of memop.\n");
      return false;
    }
 
    // If any of these is true, check aliasing.
    if ((MI->mayLoad() && (*BI)->mayStore()) ||
        (MI->mayStore() && (*BI)->mayLoad()) ||
        (MI->mayStore() && (*BI)->mayStore())) {
      if (MIsNeedChainEdge(AA, TII, MI, *BI)) {
        LLVM_DEBUG(dbgs() << "\tAliasing detected:\n\t"; MI->dump();
                   dbgs() << "\t"; (*BI)->dump());
        return false;
      }
    }
    // Do not move an instruction to this packet if this packet
    // already contains a speculated instruction.
    std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
    MIMoved = SpeculatedIns.find(*BI);
    if ((MIMoved != SpeculatedIns.end()) &&
        (MIMoved->second != (*BI)->getParent())) {
      LLVM_DEBUG(
          dbgs() << "This packet already contains a speculated instruction";
          (*BI)->dump(););
      return false;
    }
  }
 
  // Do not pull-up vector instructions because these instructions have
  // multi-cycle latencies, and the pull-up pass doesn't correctly account
  // for instructions that stall for more than one cycle.
  if (QII->isHVXVec(*MI))
    return false;
 
  return true;
}
 
/// Test is true if the two MIs cannot be safely reordered.
bool HexagonGlobalSchedulerImpl::ReorderDependencyTest(MachineInstr *MIa,
                                                       MachineInstr *MIb) {
  SmallVector<unsigned, 4> DefsA;
  SmallVector<unsigned, 4> DefsB;
  SmallVector<unsigned, 8> UsesA;
  SmallVector<unsigned, 8> UsesB;
 
  parseOperands(MIa, DefsA, UsesA);
  parseOperands(MIb, DefsB, UsesB);
 
  for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
                                          IDAE = DefsA.end();
       IDA != IDAE; ++IDA) {
    for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
                                            IUBE = UsesB.end();
         IUB != IUBE; ++IUB)
      // True data dependency.
      if (AliasingRegs(*IDA, *IUB))
        return true;
 
    for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
                                            IDBE = DefsB.end();
         IDB != IDBE; ++IDB)
      // Output dependency.
      if (AliasingRegs(*IDA, *IDB))
        return true;
  }
 
  for (SmallVector<unsigned, 4>::iterator IDB = DefsB.begin(),
                                          IDBE = DefsB.end();
       IDB != IDBE; ++IDB) {
    for (SmallVector<unsigned, 8>::iterator IUA = UsesA.begin(),
                                            IUAE = UsesA.end();
         IUA != IUAE; ++IUA)
      // True data dependency.
      if (AliasingRegs(*IDB, *IUA))
        return true;
  }
 
  // Do not reorder two calls...
  if (MIa->isCall() && MIb->isCall())
    return true;
 
  // For calls we also check callee save regs.
  if (MIa->isCall())
    for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
      for (unsigned i = 0; i < DefsB.size(); i++) {
        if (AliasingRegs(DefsB[i], *I))
          return true;
      }
    }
 
  if (MIb->isCall())
    for (const uint16_t *I = QRI->getCalleeSavedRegs(&MF); *I; ++I) {
      for (unsigned i = 0; i < DefsA.size(); i++) {
        if (AliasingRegs(DefsA[i], *I))
          return true;
      }
    }
 
  // For memory operations, check aliasing.
  // First, be conservative on these objects.
  // Might be overly constraining, so recheck.
  if ((isGlobalMemoryObject(MIa)) || (isGlobalMemoryObject(MIb)))
    return true;
 
  // If any of these is true, check aliasing.
  if (((MIa->mayLoad() && MIb->mayStore()) ||
       (MIa->mayStore() && MIb->mayLoad()) ||
       (MIa->mayStore() && MIb->mayStore())) &&
      MIsNeedChainEdge(AA, TII, MIa, MIb))
    return true;
 
  return false;
}
 
/// Serial semantics.
bool HexagonGlobalSchedulerImpl::MIsAreDependent(MachineInstr *MIa,
                                                 MachineInstr *MIb) {
  if (MIa == MIb)
    return false;
 
  if (ReorderDependencyTest(MIa, MIb)) {
    LLVM_DEBUG(dbgs() << "\t\t[MIsAreDependent]:\n\t\t"; MIa->dump();
               dbgs() << "\t\t"; MIb->dump());
    return true;
  }
  return false;
}
 
/// Serial semantics.
bool HexagonGlobalSchedulerImpl::MIsHaveTrueDependency(MachineInstr *MIa,
                                                       MachineInstr *MIb) {
  if (MIa == MIb)
    return false;
 
  SmallVector<unsigned, 4> DefsA;
  SmallVector<unsigned, 4> DefsB;
  SmallVector<unsigned, 8> UsesA;
  SmallVector<unsigned, 8> UsesB;
 
  parseOperands(MIa, DefsA, UsesA);
  parseOperands(MIb, DefsB, UsesB);
 
  for (SmallVector<unsigned, 4>::iterator IDA = DefsA.begin(),
                                          IDAE = DefsA.end();
       IDA != IDAE; ++IDA) {
    for (SmallVector<unsigned, 8>::iterator IUB = UsesB.begin(),
                                            IUBE = UsesB.end();
         IUB != IUBE; ++IUB)
      // True data dependency.
      if (AliasingRegs(*IDA, *IUB))
        return true;
  }
  return false;
}
 
/// Sequential semantics. Can these two MIs be reordered?
/// Moving MIa from "behind" to "in front" of MIb.
bool HexagonGlobalSchedulerImpl::canReorderMIs(MachineInstr *MIa,
                                               MachineInstr *MIb) {
  if (!MIa || !MIb)
    return false;
 
  // Within bundle semantics are parallel.
  if (MIa->isBundle()) {
    MachineBasicBlock::instr_iterator MII = MIa->getIterator();
    MachineBasicBlock::instr_iterator MIIE = MIa->getParent()->instr_end();
    for (++MII; MII != MIIE && MII->isInsideBundle(); ++MII) {
      if (MII->isDebugInstr())
        continue;
      if (MIsAreDependent(&*MII, MIb))
        return false;
    }
    return true;
  }
  return !MIsAreDependent(MIa, MIb);
}
 
static inline bool MIMustNotBePulledUp(MachineInstr *MI) {
  if (MI->isInlineAsm() || MI->isEHLabel() || IsSchedBarrier(MI))
    return true;
  return false;
}
 
static inline bool MIShouldNotBePulledUp(MachineInstr *MI) {
  if (MI->isBranch() || MI->isReturn() || MI->isCall() || MI->isBarrier() ||
      MI->isTerminator() || MIMustNotBePulledUp(MI))
    return true;
  return false;
}
 
// Only approve dual jump candidate:
// It is a branch, and we move it to last packet of the target location.
bool HexagonGlobalSchedulerImpl::MIisDualJumpCandidate(
    MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint) {
  if (!PerformDualJumps || !IsDualJumpSecondCandidate(MI) ||
      MIMustNotBePulledUp(MI) || ignoreInstruction(MI))
    return false;
 
  MachineBasicBlock *FromThisBB = MI->getParent();
  MachineBasicBlock *ToThisBB = WorkPoint->getParent();
 
  LLVM_DEBUG(dbgs() << "\t\t[MIisDualJumpCandidate] To BB("
                    << ToThisBB->getNumber() << ") From BB("
                    << FromThisBB->getNumber() << ")\n");
  // If the question is about the same BB, we do not want to get
  // dual jump involved - it is a different case.
  if (FromThisBB == ToThisBB)
    return false;
 
  // Dual jump could only be done on neigboring BBs.
  // The FromThisBB must only have one predecessor - the basic
  // block we are trying to merge.
  if ((*(FromThisBB->pred_begin()) != ToThisBB) ||
      (std::next(FromThisBB->pred_begin()) != FromThisBB->pred_end()))
    return false;
 
  // If this block is a target of an indirect branch, it should
  // also not be included.
  if (FromThisBB->isEHPad() || FromThisBB->hasAddressTaken())
    return false;
 
  // Now we must preserve original fall through paths. In fact we
  // might be dealing with 3way branching.
  MachineBasicBlock *ToTBB = NULL, *ToFBB = NULL;
 
  if (ToThisBB->succ_size() == 2) {
    // Check the branch from target block.
    // If we have two successors, we must understand the branch.
    SmallVector<MachineOperand, 4> ToCond;
    if (!QII->analyzeBranch(*ToThisBB, ToTBB, ToFBB, ToCond, false)) {
      // Have the branch. Check the topology.
      LLVM_DEBUG(dbgs() << "\t\tToThisBB has two successors: TBB("
                        << ToTBB->getNumber() << ") and FBB(";
                 if (ToFBB) dbgs() << ToFBB->getNumber() << ").\n";
                 else dbgs() << "None"
                             << ").\n";);
      if (ToTBB == FromThisBB) {
        // If the from BB is not the fall through, we can only handle case
        // when second branch is unconditional jump.
        return false;
      } else if (ToFBB == FromThisBB || !ToFBB) {
        // If the fall through path of ToBB is our FromBB, we have more freedom
        // of operation.
        LLVM_DEBUG(dbgs() << "\t\tFall through jump target.\n");
      }
    } else {
      LLVM_DEBUG(dbgs() << "\t\tUnable to analyze first branch.\n");
      return false;
    }
  } else if (ToThisBB->succ_size() == 1) {
    ToFBB = *ToThisBB->succ_begin();
    assert(ToFBB == FromThisBB && "Bad CFG layout");
  } else
    return false;
 
  // First unbundled control flow instruction in the BB.
  if (!MI->isBundled() && MI == &*FromThisBB->getFirstNonDebugInstr())
    return IsDualJumpFirstCandidate(WorkPoint);
 
  return false;
}
 
// Check whether moving MI to MJ's packet would cause a stall from a previous
// packet.
bool HexagonGlobalSchedulerImpl::canCauseStall(MachineInstr *MI,
                                               MachineInstr *MJ) {
  SmallVector<unsigned, 4> DefsMJI;
  SmallVector<unsigned, 8> UsesMJI;
  SmallVector<unsigned, 4> DefsMI;
  SmallVector<unsigned, 8> UsesMI;
  parseOperands(MI, DefsMI, UsesMI);
 
  for (auto Use : UsesMI) {
    int UseIdx = MI->findRegisterUseOperandIdx(Use, /*TRI=*/nullptr);
    if (UseIdx == -1)
      continue;
    bool ShouldBreak = false;
    int BundleCount = 0;
    for (MachineBasicBlock::instr_iterator
             Begin = MJ->getParent()->instr_begin(),
             MJI = MJ->getIterator();
         MJI != Begin; --MJI) {
      if (MJI->isBundle()) {
        ++BundleCount;
        continue;
      }
      parseOperands(&*MJI, DefsMJI, UsesMJI);
      for (auto Def : DefsMJI) {
        if (Def == Use || AliasingRegs(Def, Use)) {
          int DefIdx = MJI->findRegisterDefOperandIdx(Def, /*TRI=*/nullptr);
          if (DefIdx >= 0) {
            int Latency =
                TSchedModel.computeOperandLatency(&*MJI, DefIdx, MI, UseIdx);
            if (Latency > BundleCount)
              // There will be a stall if MI is moved to MJ's packet.
              return true;
            // We found the def for the use and it does not cause a stall.
            // Continue checking the next use for a potential stall.
            ShouldBreak = true;
            break;
          }
        }
      }
      if (ShouldBreak)
        break;
      if (!MJI->isBundled() && !MJI->isDebugInstr())
        ++BundleCount;
    }
  }
  return false;
}
 
/// Analyze this instruction. If this is an unbundled instruction, see
/// if it in theory could be packetized.
/// If it is already part of a packet, see if it has internal
/// dependencies to this packet.
bool HexagonGlobalSchedulerImpl::canThisMIBeMoved(
    MachineInstr *MI, MachineBasicBlock::iterator &WorkPoint,
    bool &MovingDependentOp, int &Cost) {
  if (!MI)
    return false;
  // By default, it is a normal move.
  MovingDependentOp = false;
  Cost = 0;
  // If MI is a 'formed' compound not potential compound, bail out.
  if (QII->isCompoundBranchInstr(*MI))
    return false;
  // See if we can potentially break potential compound candidates,
  // and do not do it.
  if (PreventCompoundSeparation && MI->isBundled()) {
    enum HexagonII::CompoundGroup MICG = QII->getCompoundCandidateGroup(*MI);
    if (MICG != HexagonII::HCG_None) {
      // Check internal dependencies in the bundle.
      // First, find the bundle header.
      MachineBasicBlock::instr_iterator MII = MI->getIterator();
      for (--MII; MII->isBundled(); --MII)
        if (MII->isBundle())
          break;
 
      MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
      for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
           ++MII) {
        if (&(*MII) == MI)
          continue;
        if (isCompoundPair(&*MII, MI)) {
          LLVM_DEBUG(dbgs() << "\tPrevent Compound separation.\n");
          return false;
        }
      }
    }
  }
  // Same thing for duplex candidates.
  if (PreventDuplexSeparation && MI->isBundled()) {
    if (QII->getDuplexCandidateGroup(*MI) != HexagonII::HSIG_None) {
      // Check internal dependencies in the bundle.
      // First, find the bundle header.
      MachineBasicBlock::instr_iterator MII = MI->getIterator();
      for (--MII; MII->isBundled(); --MII)
        if (MII->isBundle())
          break;
 
      MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
      for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
           ++MII) {
        if ((&(*MII) != MI) && QII->isDuplexPair(*MII, *MI)) {
          LLVM_DEBUG(dbgs() << "\tPrevent Duplex separation.\n");
          return false;
        }
      }
    }
  }
 
  // If we perform dual jump formation during the pull-up,
  // then we want to consider several additional situations.
  // a) Allow moving of dependent instruction from a packet
  // b) Allow moving some control flow instructions if they meet
  //    dual jump criteria.
  if (MIisDualJumpCandidate(MI, WorkPoint)) {
    LLVM_DEBUG(dbgs() << "\t\tDual jump candidate:\t"; MI->dump());
    // Here we are breaking our general assumption about not moving dependent
    // instructions. To save us two more expensive checks down the line,
    // propagate the information directly.
    MovingDependentOp = true;
    return true;
  }
 
  // Any of these should not even be tried.
  if (MIShouldNotBePulledUp(MI) || ignoreInstruction(MI))
    return false;
  // Pulling up these instructions could put them
  // out of jump range/offset size.
  if (QII->isLoopN(*MI)) {
    unsigned dist_looplabel =
        BlockToInstOffset.find(MI->getOperand(0).getMBB())->second;
    unsigned dist_newloop0 =
        BlockToInstOffset.find(WorkPoint->getParent())->second;
    // Check if the jump in the last instruction is within range.
    unsigned Distance =
        (unsigned)std::abs((long long)dist_looplabel - dist_newloop0) +
        QII->nonDbgBBSize(WorkPoint->getParent()) * 4 + SafetyBuffer;
    const HexagonInstrInfo *HII = (const HexagonInstrInfo *)TII;
    if (!HII->isJumpWithinBranchRange(*MI, Distance)) {
      LLVM_DEBUG(dbgs() << "\nloopN cannot be moved since Distance: "
                        << Distance << " outside branch range.";);
      return false;
    }
    LLVM_DEBUG(dbgs() << "\nloopN can be moved since Distance: " << Distance
                      << " within branch range.";);
  }
  // If the def-set of an MI is one of the live-ins then MI should
  // kill that reg and no instruction before MI should use it.
  // For simplicity, allow only if MI is the first instruction in the MBB.
  std::map<MachineInstr *, std::vector<unsigned>>::const_iterator DefIter =
      MIDefSet.find(MI);
  MachineBasicBlock *MBB = MI->getParent();
  for (unsigned i = 0; DefIter != MIDefSet.end() && i < DefIter->second.size();
       ++i) {
    if (MBB->isLiveIn(DefIter->second[i]) &&
        &*MBB->getFirstNonDebugInstr() != MI)
      return false;
  }
  // If it is part of a bundle, analyze it.
  if (MI->isBundled()) {
    // Cannot move bundle header itself. This function is about
    // individual MI move.
    if (MI->isBundle())
      return false;
 
    // Check internal dependencies in the bundle.
    // First, find the bundle header.
    MachineBasicBlock::instr_iterator MII = MI->getIterator();
    for (--MII; MII->isBundled(); --MII)
      if (MII->isBundle())
        break;
 
    MachineBasicBlock::instr_iterator BBEnd = MI->getParent()->instr_end();
    for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
         ++MII) {
      if (MII->isDebugInstr())
        continue;
      if (MIsAreDependent(&*MII, MI)) {
        if (!AllowDependentPullUp) {
          LLVM_DEBUG(dbgs() << "\t\tDependent.\n");
          return false;
        } else {
          // There are a few cases that we can safely move a dependent
          // instruction away from this packet.
          // One example is an instruction setting a call operands.
          if ((MII->isCall() && !IsIndirectCall(&*MII)) ||
              IsDualJumpSecondCandidate(&*MII) || MI->isBranch()) {
            LLVM_DEBUG(dbgs() << "\t\tDependent, but allow to move.\n");
            MovingDependentOp = true;
            Cost -= 10;
            continue;
          } else {
            LLVM_DEBUG(dbgs() << "\t\tDependent, and do not allow for now.\n");
            return false;
          }
        }
      }
    }
  }
  return true;
}
 
/// Return true if MI defines a predicate and parse all defs.
bool HexagonGlobalSchedulerImpl::doesMIDefinesPredicate(
    MachineInstr *MI, SmallVector<unsigned, 4> &Defs) {
  bool defsPredicate = false;
  Defs.clear();
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
 
    // Regmasks are considered "implicit".
    if (!MO.isReg())
      continue;
    unsigned Reg = MO.getReg();
 
    if (!Reg || QRI->isFakeReg(Reg))
      continue;
 
    assert(Register::isPhysicalRegister(Reg));
 
    if (MO.isDef() && !MO.isImplicit()) {
      const TargetRegisterClass *RC = QRI->getMinimalPhysRegClass(Reg);
      if (RC == &Hexagon::PredRegsRegClass) {
        defsPredicate = true;
        Defs.push_back(MO.getReg());
      }
    }
  }
  return defsPredicate;
}
 
/// We have just tentatively added a predicated MI to an existing packet.
/// Now we need to determine if it needs to be changed to .new form.
/// It only handles compare/predicate right now.
/// TODO - clean this logic up.
/// TODO - generalize to handle any .new
bool HexagonGlobalSchedulerImpl::NeedToNewify(
    MachineBasicBlock::instr_iterator NewMI, unsigned *DepReg,
    MachineInstr *TargetPacket = NULL) {
  MachineBasicBlock::instr_iterator MII = NewMI;
  SmallVector<unsigned, 4> DefsA;
  SmallVector<unsigned, 4> DefsB;
  SmallVector<unsigned, 8> UsesB;
 
  // If this is not a normal bundle, we are probably
  // trying to size two lonesome instructions together,
  // and trying to say if one of them will need to be
  // newified. In this is the case we have something like this:
  //   BB#5:
  //    %P0<def> = CMPGEri %R4, 2
  //    S2_pstorerif_io %P0<kill>, %R29, 16, %R21<kill>
  //    BUNDLE %R7<imp-def>, %R4<imp-def>, %R7<imp-use>
  parseOperands(&*NewMI, DefsB, UsesB);
  if (TargetPacket && !TargetPacket->isBundled()) {
    if (doesMIDefinesPredicate(TargetPacket, DefsA)) {
      for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
                                              IAE = DefsA.end();
           IA != IAE; ++IA)
        for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
                                                IBE = UsesB.end();
             IB != IBE; ++IB)
          if (*IA == *IB) {
            *DepReg = *IA;
            return true;
          }
    }
    return false;
  }
 
  // Find bundle header.
  for (--MII; MII->isBundled(); --MII)
    if (MII->isBundle())
      break;
 
  // Iterate down, if there is data dependent cmp found, need to .newify.
  // Also, we can have the following:
  //   {
  //  p0 = r7
  //  if (!p0.new) jump:t .LBB4_18
  //  if (p0.new) r8 = zxth(r12)
  //   }
  MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
  for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
    if (MII == NewMI)
      continue;
    if (doesMIDefinesPredicate(&*MII, DefsA)) {
      for (SmallVector<unsigned, 4>::iterator IA = DefsA.begin(),
                                              IAE = DefsA.end();
           IA != IAE; ++IA)
        for (SmallVector<unsigned, 8>::iterator IB = UsesB.begin(),
                                                IBE = UsesB.end();
             IB != IBE; ++IB)
          // We do not have multiple predicate regs defined in any instruction,
          // if we ever will, this needs to be generalized.
          if (*IA == *IB) {
            *DepReg = *IA;
            return true;
          }
      DefsA.clear();
    }
  }
  LLVM_DEBUG(dbgs() << "\nNo need to newify:"; NewMI->dump());
  return false;
}
 
/// We know this instruction needs to be newified to be added to the packet,
/// but not all combinations are legal.
/// It is a complimentary check to NeedToNewify().
/// The packet actually contains the new instruction during the check.
bool HexagonGlobalSchedulerImpl::CanNewifiedBeUsedInBundle(
    MachineBasicBlock::instr_iterator NewMI, unsigned DepReg,
    MachineInstr *TargetPacket) {
  MachineBasicBlock::instr_iterator MII = NewMI;
  if (!TargetPacket || !TargetPacket->isBundled())
    return true;
 
  // Find the bundle header.
  for (--MII; MII->isBundled(); --MII)
    if (MII->isBundle())
      break;
 
  MachineBasicBlock::instr_iterator BBEnd = MII->getParent()->instr_end();
  for (++MII; MII != BBEnd && MII->isBundled() && !MII->isBundle(); ++MII) {
    // Effectively we look for the case of late predicates.
    // No additional checks at the time.
    if (MII == NewMI || !QII->isPredicateLate(MII->getOpcode()))
      continue;
    SmallVector<unsigned, 4> DefsA;
    if (!doesMIDefinesPredicate(&*MII, DefsA))
      continue;
    for (auto &IA : DefsA)
      if (IA == DepReg)
        return false;
  }
  return true;
}
 
/// setUsed - Set the register and its sub-registers as being used.
/// Similar to RegScavenger::setUsed().
void HexagonGlobalSchedulerImpl::setUsedRegs(BitVector &Set, unsigned Reg) {
  Set.reset(Reg);
  for (MCSubRegIterator SubRegs(Reg, QRI); SubRegs.isValid(); ++SubRegs)
    Set.reset(*SubRegs);
}
 
/// Are these two registers overlaping?
bool HexagonGlobalSchedulerImpl::AliasingRegs(unsigned RegA, unsigned RegB) {
  if (RegA == RegB)
    return true;
 
  for (MCSubRegIterator SubRegs(RegA, QRI); SubRegs.isValid(); ++SubRegs)
    if (RegB == *SubRegs)
      return true;
 
  for (MCSubRegIterator SubRegs(RegB, QRI); SubRegs.isValid(); ++SubRegs)
    if (RegA == *SubRegs)
      return true;
 
  return false;
}
 
/// Find use with this reg, and unmark the kill flag.
static inline void unmarkKillReg(MachineInstr *MI, unsigned Reg) {
  if (MI->isDebugInstr())
    return;
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI->getOperand(i);
 
    if (!MO.isReg())
      continue;
 
    if (MO.isKill() && (MO.getReg() == Reg))
      MO.setIsKill(false);
  }
}
 
/// Find use with this reg, and unmark the kill flag.
static inline void markKillReg(MachineInstr *MI, unsigned Reg) {
  if (MI->isDebugInstr())
    return;
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI->getOperand(i);
 
    if (!MO.isReg())
      continue;
 
    if (MO.isUse() && (MO.getReg() == Reg))
      MO.setIsKill(true);
  }
}
 
/// We have just moved an instruction that could have changed kill patterns
/// along the path it was moved. We need to update it.
void HexagonGlobalSchedulerImpl::updateKillAlongThePath(
    MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
    MachineBasicBlock::instr_iterator &Head,
    MachineBasicBlock::instr_iterator &Tail,
    MachineBasicBlock::iterator &SourcePacket,
    MachineBasicBlock::iterator &TargetPacket,
    std::vector<MachineInstr *> &backtrack) {
  // This is the instruction being moved.
  MachineInstr *MI = &*Head;
  MachineBasicBlock *CurrentBB = OriginBB;
  SmallSet<unsigned, 8> KilledUseSet;
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
    if (!MO.isReg())
      continue;
    unsigned Reg = MO.getReg();
    if (!Reg)
      continue;
 
    if (MO.isKill())
      KilledUseSet.insert(Reg);
  }
 
  // If there are no kills here, we are done.
  if (KilledUseSet.empty())
    return;
 
  LLVM_DEBUG(dbgs() << "\n[updateKillAlongThePath]\n");
  LLVM_DEBUG(dbgs() << "\t\tInstrToMove   :\t"; MI->dump());
  LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\n";
             DumpPacket(SourcePacket.getInstrIterator()));
  LLVM_DEBUG(dbgs() << "\t\tTargetPacket  :\n";
             DumpPacket(TargetPacket.getInstrIterator()));
  LLVM_DEBUG(dbgs() << "\tUpdate Kills. Need to update (" << KilledUseSet.size()
                    << ")kills. From BB (" << OriginBB->getNumber() << ")\n");
  LLVM_DEBUG(dbgs() << "\tMove path:\n");
  assert(!backtrack.empty() && "Empty back track");
 
  // We have pulled up an instruction, with one of its uses marked as kill.
  // If there is any other use of the same register along the move path,
  // and there are no side exits with killed register live-in along them,
  // we need to mark last use of that reg as kill.
  for (signed i = backtrack.size() - 1; i >= 0; --i) {
    LLVM_DEBUG(dbgs() << "\t\t[" << i << "]BB("
                      << backtrack[i]->getParent()->getNumber() << ")\t";
               backtrack[i]->dump());
    if (CurrentBB != backtrack[i]->getParent()) {
      LLVM_DEBUG(dbgs() << "\t\tChange BB from (" << CurrentBB->getNumber()
                        << ") to(" << backtrack[i]->getParent()->getNumber()
                        << ")\n");
      for (MachineBasicBlock::const_succ_iterator
               SI = backtrack[i]->getParent()->succ_begin(),
               SE = backtrack[i]->getParent()->succ_end();
           SI != SE; ++SI) {
        if (*SI == CurrentBB)
          continue;
 
        LLVM_DEBUG(dbgs() << "\t\tSide Exit:\n\t"; (*SI)->dump());
        // If any reg kill is live along this side exit, it is not
        // a kill any more.
        for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
                                                E = (*SI)->livein_end();
             I != E; ++I) {
          if (KilledUseSet.count((*I).PhysReg)) {
            LLVM_DEBUG(dbgs() << "\t\tReg (" << printReg((*I).PhysReg, QRI)
                              << ") is LiveIn along side exit.\n");
            KilledUseSet.erase((*I).PhysReg);
            unmarkKillReg(MI, (*I).PhysReg);
          }
          if (KilledUseSet.empty())
            return;
        }
      }
      CurrentBB = backtrack[i]->getParent();
    }
 
    // Done with the whole path.
    if (backtrack[i] == &*TargetPacket)
      return;
 
    // Starting the tracking. Do not update source bundle.
    // If TargetPacket == SourcePacket we have returned
    // in the previous check.
    if (backtrack[i] == &*SourcePacket)
      continue;
 
    // Ignore DBG_VALUE.
    if (backtrack[i]->isDebugInstr())
      continue;
 
    // Encountered an intermediary bundle. Process it.
    // Beware, sometimes check for backtrack[i] == TargetPacket
    // does not work, so this instruction could be one from the target bundle.
    SmallVector<unsigned, 4> Defs;
    SmallVector<unsigned, 8> Uses;
    MachineInstr *MIU = backtrack[i];
    parseOperands(MIU, Defs, Uses);
 
    for (SmallVector<unsigned, 8>::iterator IA = Uses.begin(), IAE = Uses.end();
         IA != IAE; ++IA) {
      if (KilledUseSet.count(*IA)) {
        // Now this is new kill point for this Reg.
        // Update the bundle, and any local uses.
        markKillReg(MIU, *IA);
 
        // Unmark the current MI.
        unmarkKillReg(MI, *IA);
 
        if (MIU->isBundle()) {
          // TODO: Can do this cleaner and faster.
          MachineBasicBlock::instr_iterator MII = MIU->getIterator();
          MachineBasicBlock::instr_iterator End = CurrentBB->instr_end();
          for (++MII; MII != End && MII->isInsideBundle(); ++MII)
            markKillReg(&*MII, *IA);
        }
 
        // We have updated this kill reg, if there are more, keep on going.
        KilledUseSet.erase(*IA);
 
        // If the set is exhausted, just leave.
        if (KilledUseSet.empty())
          return;
      }
    }
  }
}
 
/// This is houskeeping for bundle with instruction just added to it.
void HexagonGlobalSchedulerImpl::addInstructionToExistingBundle(
    MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
    MachineBasicBlock::instr_iterator &Tail,
    MachineBasicBlock::instr_iterator &NewMI,
    MachineBasicBlock::iterator &TargetPacket,
    MachineBasicBlock::iterator &NextMI,
    std::vector<MachineInstr *> &backtrack) {
  Tail = getBundleEnd(Head);
  LLVM_DEBUG(dbgs() << "\t\t\t[Add] Head home: "; DumpPacket(Head));
 
  // Old header to be deleted shortly.
  MachineBasicBlock::instr_iterator Outcast = Head;
  // Unbundle old header.
  if (Outcast->isBundle() && Outcast->isBundledWithSucc())
    Outcast->unbundleFromSucc();
 
  bool memShufDisabled = QII->getBundleNoShuf(*Outcast);
 
  // Create new bundle header and update MI flags.
  finalizeBundle(*HomeBB, ++Head, Tail);
  MachineBasicBlock::instr_iterator BundleMII = std::prev(Head);
  if (memShufDisabled)
    QII->setBundleNoShuf(BundleMII);
  --Head;
 
  LLVM_DEBUG(dbgs() << "\t\t\t[Add] New Head : "; DumpPacket(Head));
 
  // The old header could be listed in the back tracking,
  // so if it is, we need to update it.
  for (unsigned i = 0; i < backtrack.size(); ++i)
    if (backtrack[i] == &*Outcast)
      backtrack[i] = &*Head;
 
  // Same for top MI iterator.
  if (NextMI == Outcast)
    NextMI = Head;
 
  TargetPacket = Head;
  HomeBB->erase(Outcast);
}
 
/// This handles houskeeping for bundle with instruction just deleted from it.
/// We do not see the original moved instruction in here.
void HexagonGlobalSchedulerImpl::removeInstructionFromExistingBundle(
    MachineBasicBlock *HomeBB, MachineBasicBlock::instr_iterator &Head,
    MachineBasicBlock::instr_iterator &Tail,
    MachineBasicBlock::iterator &SourceLocation,
    MachineBasicBlock::iterator &NextMI, bool MovingDependentOp,
    std::vector<MachineInstr *> &backtrack) {
  // Empty BBs will be deleted shortly.
  if (HomeBB->empty()) {
    Head = MachineBasicBlock::instr_iterator();
    Tail = MachineBasicBlock::instr_iterator();
    return;
  }
 
  if (!SourceLocation->isBundle()) {
    LLVM_DEBUG(dbgs() << "\t\t\tOriginal instruction was not bundled.\n\t\t\t";
               SourceLocation->dump());
    // If original instruction was not bundled, and we have moved it
    // and it is in the back track, we probably want to remove it from there.
    LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New head: "; backtrack.back()->dump());
 
    for (unsigned i = 0; i < backtrack.size(); ++i) {
      if (backtrack[i] == &*SourceLocation) {
        // By definition, this should be the last instruction in the backtrack.
        assert((backtrack[i] == backtrack.back()) && "Lost back track");
        backtrack.pop_back();
      }
      // Point the main iterator to the next instruction.
      if (NextMI == SourceLocation)
        NextMI++;
    }
    SourceLocation = MachineBasicBlock::iterator();
    Head = MachineBasicBlock::instr_iterator();
    Tail = MachineBasicBlock::instr_iterator();
    return;
  }
 
  // The old header, soon to be deleted.
  MachineBasicBlock::instr_iterator Outcast = SourceLocation.getInstrIterator();
  LLVM_DEBUG(dbgs() << "\t\t\t[Rem] SourceLocation after bundle update: ";
             DumpPacket(Outcast));
 
  // If bundle has been already destroyed. BB->splat seems to do it some times
  // but not the other.
  // We already know that SourceLocation is bundle header.
  if (!SourceLocation->isBundledWithSucc()) {
    assert(!Head->isBundledWithSucc() && !Head->isBundledWithPred() &&
           "Bad bundle");
  } else {
    Head = SourceLocation.getInstrIterator();
    Tail = getBundleEnd(Head);
    unsigned Size = 0;
    unsigned BBSizeWithDbg = 0;
    MachineBasicBlock::const_instr_iterator I(Head);
    MachineBasicBlock::const_instr_iterator E = Head->getParent()->instr_end();
 
    for (++I; I != E && I->isBundledWithPred(); ++I) {
      ++BBSizeWithDbg;
      if (!I->isDebugInstr())
        ++Size;
    }
 
    LLVM_DEBUG(dbgs() << "\t\t\t[Rem] Size(" << Size << ") Head orig: ";
               DumpPacket(Head));
    // The old header, soon to be deleted.
    Outcast = Head;
 
    // The old Header is still counted here.
    if (Size > 1) {
      if (Outcast->isBundle() && Outcast->isBundledWithSucc())
        Outcast->unbundleFromSucc();
 
      bool memShufDisabled = QII->getBundleNoShuf(*Outcast);
      // The finalizeBundle() assumes that "original" sequence
      // it is finalizing is sequentially correct. That basically
      // means that swap case might not be handled properly.
      // I find insert point for the pull-up instruction myself,
      // and I should try to catch that swap case there, and refuse
      // to insert if I cannot guarantee correct serial semantics.
      // In the future, I need my own incremental "inserToBundle"
      // function.
      finalizeBundle(*HomeBB, ++Head, Tail);
      MachineBasicBlock::instr_iterator BundleMII = std::prev(Head);
      if (memShufDisabled)
        QII->setBundleNoShuf(BundleMII);
 
      --Head;
    } else if (Size == 1) {
      // There is only one non-debug instruction in the bundle.
      if (BBSizeWithDbg > 1) {
        // There are some debug instructions that should be unbundled too.
        MachineBasicBlock::instr_iterator I(Head);
        MachineBasicBlock::instr_iterator E = Head->getParent()->instr_end();
        for (++I; I != E && I->isBundledWithPred(); ++I) {
          I->unbundleFromPred();
          // Set Head to the non-debug instruction.
          if (!I->isDebugInstr())
            Head = I;
        }
      } else {
        // This means that only one original instruction is
        // left in the bundle. We need to "unbundle" it because the
        // rest of API will not like it.
        ++Head;
        if (Head->isBundledWithPred())
          Head->unbundleFromPred();
        if (Head->isBundledWithSucc())
          Head->unbundleFromSucc();
      }
    } else
      llvm_unreachable("Corrupt bundle");
  }
 
  LLVM_DEBUG(dbgs() << "\t\t\t[Rem] New Head : "; DumpPacket(Head));
  SourceLocation = Head;
 
  // The old header could be listed in the back tracking,
  // so if it is, we need to update it.
  for (unsigned i = 0; i < backtrack.size(); ++i)
    if (backtrack[i] == &*Outcast)
      backtrack[i] = &*Head;
 
  // Same for top MI iterator.
  if (NextMI == Outcast)
    NextMI = Head;
 
  HomeBB->erase(Outcast);
}
 
#ifndef NDEBUG
static void debugLivenessForBB(const MachineBasicBlock *MBB,
                               const TargetRegisterInfo *TRI) {
  LLVM_DEBUG(dbgs() << "\tLiveness for BB:\n"; MBB->dump());
  for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
                                              SE = MBB->succ_end();
       SI != SE; ++SI) {
    LLVM_DEBUG(dbgs() << "\tSuccessor BB (" << (*SI)->getNumber() << "):");
    for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
                                            E = (*SI)->livein_end();
         I != E; ++I)
      LLVM_DEBUG(dbgs() << "\t" << printReg((*I).PhysReg, TRI));
    LLVM_DEBUG(dbgs() << "\n");
  }
}
#endif
 
// Blocks should be considered empty if they contain only debug info;
// else the debug info would affect codegen.
static bool IsEmptyBlock(MachineBasicBlock *MBB) {
  if (MBB->empty())
    return true;
  for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
       MBBI != MBBE; ++MBBI) {
    if (!MBBI->isDebugInstr())
      return false;
  }
  return true;
}
 
/// Treat given instruction as a branch, go through its operands
/// and see if any of them is a BB address. If so, return it.
/// Return NULL otherwise.
static inline MachineBasicBlock *getBranchDestination(MachineInstr *MI) {
  if (!MI || !MI->isBranch() || MI->isBundle())
    return NULL;
 
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI->getOperand(i);
    if (MO.isMBB())
      return MO.getMBB();
  }
  return NULL;
}
 
/// Similar to HexagonInstrInfo::analyzeBranch but handles
/// serveral more general cases including parsing empty BBs when possible.
bool HexagonGlobalSchedulerImpl::AnalyzeBBBranches(MachineBasicBlock *MBB,
                                                   MachineBasicBlock *&TBB,
                                                   MachineInstr *&FirstTerm,
                                                   MachineBasicBlock *&FBB,
                                                   MachineInstr *&SecondTerm) {
  // Hexagon allowes up to two jumps in MBB.
  FirstTerm = NULL;
  SecondTerm = NULL;
 
  LLVM_DEBUG(dbgs() << "\n\t\tAnalyze Branches in BB(" << MBB->getNumber()
                    << ")\n");
  if (MBB->succ_size() == 0) {
    LLVM_DEBUG(dbgs() << "\n\t\tBlock has no successors.\n");
    return true;
  }
  // Find both jumps.
  // We largely rely on implied assumption that BB branching always
  // looks like this:
  //  J2_jumpf %P0, <BB#60>, %PC<imp-def>;
  //  J2_jump <BB#49>
  // Branches also could be in different packets.
  MachineBasicBlock::instr_iterator MIB = MBB->instr_begin();
  MachineBasicBlock::instr_iterator MIE = MBB->instr_end();
  MachineBasicBlock::instr_iterator MII = MIB;
 
  if (QII->nonDbgBBSize(MBB) == 1) {
    MII = MBB->getFirstNonDebugInstr().getInstrIterator();
    if (MII->isBranch())
      FirstTerm = &*MII;
  } else {
    // We have already eliminated the case when MIB == MIE.
    while (MII != MIE) {
      if (!MII->isBundle() && MII->isBranch()) {
        if (!FirstTerm)
          FirstTerm = &*MII;
        else
          SecondTerm = &*MII;
      }
      ++MII;
    }
  }
  if ((FirstTerm && FirstTerm->isIndirectBranch()) ||
      (SecondTerm && SecondTerm->isIndirectBranch())) {
    LLVM_DEBUG(dbgs() << "\n\t\tCannot analyze BB with indirect branch.");
    return true;
  }
  if ((FirstTerm && FirstTerm->getOpcode() == Hexagon::J2_jump &&
       !FirstTerm->getOperand(0).isMBB()) ||
      (SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
       !SecondTerm->getOperand(0).isMBB())) {
    LLVM_DEBUG(
        dbgs() << "\n\t\tCannot analyze BB with a branch out of function.");
    return true;
  }
 
  // Now try to analyze this branch.
  SmallVector<MachineOperand, 4> Cond;
  if (QII->analyzeBranch(*MBB, TBB, FBB, Cond, false)) {
    LLVM_DEBUG(dbgs() << "\t\tFail to analyze with analyzeBranch.\n");
    LLVM_DEBUG(dbgs() << "\t\tFirst term: "; if (FirstTerm) FirstTerm->dump();
               else dbgs() << "None\n";);
    // Could not analyze it. See if this is something we can recognize.
    TBB = getBranchDestination(FirstTerm);
  }
  // There are several cases not handled by HexagonInstrInfo::analyzeBranch.
  if (!TBB) {
    LLVM_DEBUG(dbgs() << "\t\tMissing TBB.\n");
    // There is a branch, but TBB is not found.
    // The BB could also be empty at this point. See if it is a trivial
    // layout case.
    if (MBB->succ_size() == 1) {
      TBB = *MBB->succ_begin();
      LLVM_DEBUG(dbgs() << "\t\tFall through TBB(" << TBB->getNumber()
                        << ").\n");
      return false;
    } else if (MBB->succ_size() == 2) {
      // This should cover majority of remaining cases.
      if (FirstTerm && SecondTerm &&
          (QII->isPredicated(*FirstTerm) || QII->isNewValueJump(*FirstTerm)) &&
          !QII->isPredicated(*SecondTerm)) {
        TBB = getBranchDestination(FirstTerm);
        FBB = getBranchDestination(SecondTerm);
        LLVM_DEBUG(dbgs() << "\t\tCanonical dual jump layout: TBB("
                          << TBB->getNumber() << ") FBB(" << FBB->getNumber()
                          << ").\n");
        return false;
      } else if (SecondTerm && SecondTerm->getOpcode() == Hexagon::J2_jump &&
                 SecondTerm->getOperand(0).isMBB()) {
        // Look at the second term if I know it, to find out what is the fall
        // through for this BB.
        FBB = SecondTerm->getOperand(0).getMBB();
        assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
        MachineBasicBlock *Succ0 = *MBB->succ_begin();
        MachineBasicBlock *Succ1 = *std::next(MBB->succ_begin());
        if (FBB == Succ0)
          TBB = Succ1;
        else
          TBB = Succ0;
        LLVM_DEBUG(dbgs() << "\t\tSecond br is J2_jump TBB(" << TBB->getNumber()
                          << ") FBB(" << FBB->getNumber() << ").\n");
        return false;
      } else {
        // This might be an empty BB but still with two
        // successors set. Try to use CFG layout to sort it out.
        // This could happen when last jump was pulled up from a BB, and
        // CFG is being updated. At that point this method is called and
        // returns best guess possible for TBB/FBB. Fortunately order of those
        // is irrelevant, and rather used a worklist for CFG update.
        MachineFunction::iterator MBBIter = MBB->getIterator();
        MachineFunction &MF = *MBB->getParent();
        (void)MF; // supress compiler warning
        // If there are no other clues, assume next sequential BB
        // in CFG as FBB.
        ++MBBIter;
        assert(MBBIter != MF.end() && "I give up.");
        FBB = &(*MBBIter);
        assert(MBB->succ_size() == 2 && "Expected exactly 2 successors");
        MachineBasicBlock *S0 = *MBB->succ_begin();
        MachineBasicBlock *S1 = *std::next(MBB->succ_begin());
        if (FBB == S0)
          TBB = S1;
        else if (FBB == S1) {
          TBB = S0;
        } else {
          // This case can arise when the layout successor basic block (++IMBB)
          // got empty during pull-up.
          // As a result, ++IMBB is not one of MBB's successors.
          MBBIter = MF.begin();
          while (!MBB->isSuccessor(&*MBBIter) && (MBBIter != MF.end()))
            ++MBBIter;
          assert(MBBIter != MF.end() && "Malformed BB with invalid successors");
          FBB = &*MBBIter;
          if (FBB == S0)
            TBB = S1;
          else
            TBB = S0;
        }
        LLVM_DEBUG(dbgs() << "\t\tUse layout TBB(" << TBB->getNumber()
                          << ") FBB(" << FBB->getNumber() << ").\n");
        return false;
      }
    }
    assert(!FirstTerm && "Bad BB");
    return true;
  }
  // Ok, we have TBB, but maybe missing FBB.
  if (!FBB && SecondTerm) {
    LLVM_DEBUG(dbgs() << "\t\tMissing FBB.\n");
    // analyzeBranch could lie to us, ignore it in this case.
    // For the canonical case simply take known branch targets.
    if ((QII->isPredicated(*FirstTerm) || QII->isNewValueJump(*FirstTerm)) &&
        !QII->isPredicated(*SecondTerm)) {
      FBB = getBranchDestination(SecondTerm);
    } else {
      // Second term is also predicated.
      // Use CFG layout. Assign layout successor as FBB.
      for (MachineBasicBlock *Succ : MBB->successors()) {
        if (MBB->isLayoutSuccessor(Succ))
          FBB = Succ;
      }
      if (FBB == NULL) {
        LLVM_DEBUG(dbgs() << "\nNo layout successor found.");
        LLVM_DEBUG(dbgs() << "Possibly the layout successor is an empty BB");
        return true;
      }
      if (TBB == FBB)
        LLVM_DEBUG(dbgs() << "Malformed branch with useless branch condition";);
    }
    LLVM_DEBUG(dbgs() << "\t\tSecond term: "; SecondTerm->dump());
  } else if (TBB && !FBB) {
    // If BB ends in endloop, and it is a single BB hw loop,
    // we will have a single terminator, but we can figure FBB
    // easily from CFG.
    if (MBB->succ_size() == 2) {
      MachineBasicBlock *S0 = *MBB->succ_begin();
      MachineBasicBlock *S1 = *std::next(MBB->succ_begin());
      if (TBB == S0)
        FBB = S1;
      else
        FBB = S0;
    }
  }
 
  LLVM_DEBUG(dbgs() << "\t\tFinal TBB(" << TBB->getNumber() << ").\n";
             if (FBB) dbgs() << "\t\tFinal FBB(" << FBB->getNumber() << ").\n";
             else dbgs() << "\t\tFinal FBB(None)\n";);
  return false;
}
 
/// updateBranches - Updates all branches to \p From in the basic block \p
/// InBlock to branches to \p To.
static void updateBranches(MachineBasicBlock &InBlock, MachineBasicBlock *From,
                           MachineBasicBlock *To) {
  for (MachineBasicBlock::instr_iterator BI = InBlock.instr_begin(),
                                         E = InBlock.instr_end();
       BI != E; ++BI) {
    MachineInstr *Inst = &*BI;
    // Ignore anything that is not a branch.
    if (!Inst->isBranch())
      continue;
    for (MachineInstr::mop_iterator OI = Inst->operands_begin(),
                                    OE = Inst->operands_end();
         OI != OE; ++OI) {
      MachineOperand &Opd = *OI;
      // Look for basic block "From".
      if (!Opd.isMBB() || Opd.getMBB() != From)
        continue;
      // Update it.
      Opd.setMBB(To);
    }
  }
}
 
/// Rewrite all predecessors of the old block to go to the fallthrough
/// instead.
/// NB: Collect predecessors into a snapshot vector before iterating to
/// avoid iterator invalidation on MBB's predecessor list. Each call to
/// ReplaceUsesOfBlockWith modifies both the successor list of Pred and
/// the predecessor list of MBB, which invalidates debug-mode iterators
/// (detected by _GLIBCXX_DEBUG).
static void updatePredecessors(MachineBasicBlock &MBB,
                               MachineBasicBlock *MFBB) {
  MachineFunction &MF = *MBB.getParent();
 
  if (MFBB->getIterator() == MF.end())
    return;
 
  // Snapshot the predecessor list to avoid iterator invalidation.
  SmallVector<MachineBasicBlock *, 4> Preds(MBB.pred_begin(), MBB.pred_end());
  for (MachineBasicBlock *Pred : Preds) {
    if (!Pred->isSuccessor(&MBB))
      continue;
    Pred->ReplaceUsesOfBlockWith(&MBB, MFBB);
    updateBranches(*Pred, &MBB, MFBB);
  }
}
 
static void UpdateCFG(MachineBasicBlock *HomeBB, MachineBasicBlock *OriginBB,
                      MachineInstr *MII, MachineBasicBlock *HomeTBB,
                      MachineBasicBlock *HomeFBB, MachineInstr *FTA,
                      MachineInstr *STA,
                      const MachineBranchProbabilityInfo *MBPI) {
  MachineBasicBlock *S2Add = NULL, *S2Remove = NULL;
  bool RemoveLSIfPresent = false;
  if ((&*MII == FTA) && MII->isConditionalBranch()) {
    LLVM_DEBUG(dbgs() << "\nNew firstterm conditional jump added to HomeBB";);
    S2Add = HomeTBB;
    S2Remove = HomeTBB;
  } else if ((&*MII == STA) && MII->isConditionalBranch()) {
    LLVM_DEBUG(dbgs() << "\nNew secondterm conditional jump added to HomeBB";);
    // AnalyzeBBBranches might not give correct information in this case.
    // The branch destination may be a symbol, not necessarily a block.
    if (MachineBasicBlock *Dest = getBranchDestination(MII)) {
      LLVM_DEBUG(dbgs() << "\nBranch destination for pulled instruction is BB#"
                        << Dest->getNumber(););
      S2Add = Dest;
      S2Remove = Dest;
    }
  } else if ((&*MII == FTA) && MII->isUnconditionalBranch()) {
    LLVM_DEBUG(dbgs() << "\nNew firstterm unconditional jump added to HomeBB";);
    S2Add = HomeTBB;
    S2Remove = HomeTBB;
    RemoveLSIfPresent = true;
  } else if ((&*MII == STA) && MII->isUnconditionalBranch()) {
    LLVM_DEBUG(
        dbgs() << "\nNew secondterm unconditional jump added to HomeBB";);
    S2Add = HomeFBB;
    S2Remove = HomeFBB;
    RemoveLSIfPresent = true;
  }
  if (S2Add && !HomeBB->isSuccessor(S2Add)) {
    HomeBB->addSuccessor(S2Add, MBPI->getEdgeProbability(OriginBB, S2Add));
  }
  if (S2Remove)
    OriginBB->removeSuccessor(S2Remove);
  if (RemoveLSIfPresent) {
    MachineFunction::iterator HomeBBLS = HomeBB->getIterator();
    ++HomeBBLS;
    if (HomeBBLS != HomeBB->getParent()->end() &&
        HomeBB->isLayoutSuccessor(&*HomeBBLS)) {
      LLVM_DEBUG(dbgs() << "\nRemoving LayoutSucc BB#" << HomeBBLS->getNumber()
                        << "from list of successors";);
      HomeBB->removeSuccessor(&*HomeBBLS);
    }
  }
}
 
/// Move instruction from/to BB, Update liveness info,
/// return pointer to the newly inserted and modified
/// instruction.
MachineInstr *HexagonGlobalSchedulerImpl::MoveAndUpdateLiveness(
    BasicBlockRegion *CurrentRegion, MachineBasicBlock *HomeBB,
    MachineInstr *InstrToMove, bool NeedToNewify, unsigned DepReg,
    bool MovingDependentOp, MachineBasicBlock *OriginBB,
    MachineInstr *OriginalInstruction, SmallVector<MachineOperand, 4> &Cond,
    MachineBasicBlock::iterator &SourceLocation,
    MachineBasicBlock::iterator &TargetPacket,
    MachineBasicBlock::iterator &NextMI,
    std::vector<MachineInstr *> &backtrack) {
  LLVM_DEBUG(
      dbgs() << "\n...............[MoveAndUpdateLiveness]..............\n");
  LLVM_DEBUG(dbgs() << "\t\tInstrToMove        :\t"; InstrToMove->dump());
  LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
             OriginalInstruction->dump());
  LLVM_DEBUG(dbgs() << "\t\tSourceLocation     :\t";
             DumpPacket(SourceLocation.getInstrIterator()));
  LLVM_DEBUG(dbgs() << "\t\tTargetPacket       :\t";
             DumpPacket(TargetPacket.getInstrIterator()));
 
  MachineBasicBlock::instr_iterator OriginalHead =
      SourceLocation.getInstrIterator();
  MachineBasicBlock::instr_iterator OriginalTail = getBundleEnd(OriginalHead);
  MachineBasicBlock::instr_iterator OutcastFrom =
      OriginalInstruction->getIterator();
 
  // Remove our temporary instruction.
  MachineBasicBlock::instr_iterator kill_it(InstrToMove);
  HomeBB->erase(kill_it);
 
  MachineBasicBlock::instr_iterator TargetHead(TargetPacket.getInstrIterator());
  MachineBasicBlock::instr_iterator TargetTail = getBundleEnd(TargetHead);
 
  LLVM_DEBUG(dbgs() << "\n\tTo BB before:\n"; debugLivenessForBB(HomeBB, QRI));
  LLVM_DEBUG(dbgs() << "\n\tFrom BB before:\n";
             debugLivenessForBB(OriginBB, QRI));
 
  // Before we perform the move, we need to collect the worklist
  // of BBs for liveness updated.
  std::list<MachineBasicBlock *> WorkList;
 
  // Insert into the work list all BBs along the backtrace.
  for (std::vector<MachineInstr *>::iterator RI = backtrack.begin(),
                                             RIE = backtrack.end();
       RI != RIE; RI++)
    WorkList.push_back((*RI)->getParent());
 
  // Only keep unique entries.
  // TODO: Use a different container here.
  WorkList.unique();
 
  // Move the original instruction.
  // If this instruction is inside a bundle, update the bundle.
  MachineBasicBlock::instr_iterator BBEnd =
      TargetHead->getParent()->instr_end();
  bool LastInstructionInBundle = false;
  MachineBasicBlock::instr_iterator MII = findInsertPositionInBundle(
      TargetPacket, &*OutcastFrom, LastInstructionInBundle);
 
  (void)BBEnd;
  LLVM_DEBUG(dbgs() << "\n\t\t\tHead target      : "; DumpPacket(TargetHead));
  LLVM_DEBUG(dbgs() << "\t\t\tTail target        : ";
             DumpPacket(TargetTail, BBEnd));
  LLVM_DEBUG(dbgs() << "\t\t\tInsert right before: "; DumpPacket(MII, BBEnd));
 
  MIBundleBuilder Bundle(&*TargetHead);
 
  // Actual move. One day liveness might be updated here.
  if (OriginalInstruction->isBundled()) {
    Bundle.insert(MII, OriginalInstruction->removeFromBundle());
    --MII;
  } else {
    // This is one case currently unhandled by Bundle.insert
    // and needs to be fixed upstream. Meanwhile use old way to handle
    // this odd case.
    if (OriginalInstruction->getIterator() == TargetTail) {
      LLVM_DEBUG(dbgs() << "\t\t\tSpecial case move.\n");
      MachineBasicBlock::instr_iterator MIIToPred = MII;
      --MIIToPred;
      LLVM_DEBUG(dbgs() << "\t\t\tInser after        : ";
                 DumpPacket(MIIToPred, BBEnd));
      // Unbundle it in its current location.
      if (OutcastFrom->isBundledWithSucc()) {
        OutcastFrom->clearFlag(MachineInstr::BundledSucc);
        OutcastFrom->clearFlag(MachineInstr::BundledPred);
      } else if (OutcastFrom->isBundledWithPred()) {
        OutcastFrom->unbundleFromPred();
      }
      HomeBB->splice(MII, OriginBB, OutcastFrom);
      if (!MII->isBundledWithPred())
        MII->bundleWithPred();
      if (!LastInstructionInBundle && !MII->isBundledWithSucc())
        MII->bundleWithSucc();
      // This is the instruction after which we have inserted.
      if (!MIIToPred->isBundledWithSucc())
        MIIToPred->bundleWithSucc();
    } else {
      Bundle.insert(MII, OriginalInstruction->removeFromParent());
      --MII;
    }
  }
  // Source location bundle is updated later in the
  // removeInstructionFromExistingBundle().
 
  LLVM_DEBUG(dbgs() << "\t\t\tNew packet head: "; DumpPacket(TargetHead));
  LLVM_DEBUG(dbgs() << "\t\t\tInserted op    : "; MII->dump());
  LLVM_DEBUG(dbgs() << "\n\tTo BB after move:\n";
             debugLivenessForBB(HomeBB, QRI));
  LLVM_DEBUG(dbgs() << "\n\tFrom BB after:\n";
             debugLivenessForBB(OriginBB, QRI));
 
  // Update kill patterns. Do it before we have predicated the moved
  // instruction.
  updateKillAlongThePath(HomeBB, OriginBB, MII, TargetTail, SourceLocation,
                         TargetPacket, backtrack);
  // I need to know:
  // - true/false predication
  // - do I need to .new it?
  // - do I need to .old it?
  // If the original instruction used new value operands,
  // it might need to be changed to the generic form
  // before further processing.
  if (QII->isDotNewInst(*MII)) {
    DemoteToDotOld(&*MII);
    LLVM_DEBUG(dbgs() << "\t\t\tDemoted to .old\t:"; MII->dump());
  }
 
  // We have previously checked whether this instruction could
  // be placed in this packet, including all possible transformations
  // it might need, so if any request will fail now, something is wrong.
  //
  // Need for predication and the exact condition is determined by
  // the path between original and current instruction location.
  if (!Cond.empty()) { // To be predicated
    LLVM_DEBUG(dbgs() << "\t\t\tPredicating:"; MII->dump());
    assert(TII->isPredicable(*MII) && "MII is not predicable");
    TII->PredicateInstruction(*MII, Cond);
    if (NeedToNewify) {
      assert((DepReg < std::numeric_limits<unsigned>::max()) &&
             "Invalid pred reg value");
      LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
                        << printReg(DepReg, QRI) << ").\n");
      int NewOpcode = QII->getDotNewPredOp(*MII, MBPI);
      MII->setDesc(QII->get(NewOpcode));
 
      // Now we need to mark newly created predicate operand as
      // internal read.
      // TODO: Better look for predicate operand.
      for (unsigned i = 0, e = MII->getNumOperands(); i != e; ++i) {
        MachineOperand &MO = MII->getOperand(i);
        if (!MO.isReg())
          continue;
        if (MO.isDef())
          continue;
        if (DepReg == MO.getReg())
          MO.setIsInternalRead();
      }
    }
    LLVM_DEBUG(dbgs() << "\t\t\tNew predicated form:\t"; MII->dump());
    // If the predicate has changed kill pattern, now we need to propagate
    // that again. This is important for liveness computation.
    updateKillAlongThePath(HomeBB, OriginBB, MII, TargetTail, SourceLocation,
                           TargetPacket, backtrack);
  }
 
  // Create new bundle header, remove the old one.
  addInstructionToExistingBundle(HomeBB, TargetHead, TargetTail, MII,
                                 TargetPacket, NextMI, backtrack);
 
  // If moved instruction was inside a bundle, update that bundle.
  removeInstructionFromExistingBundle(OriginBB, ++OriginalHead, OriginalTail,
                                      SourceLocation, NextMI, MovingDependentOp,
                                      backtrack);
 
  // If removed instruction could have been dependent on any
  // of the remaining ops, we need to oldify possible affected ones.
  LLVM_DEBUG(dbgs() << "\t\tTargetHead:\t"; DumpPacket(TargetHead, BBEnd));
  LLVM_DEBUG(dbgs() << "\t\tOriginalHead:\t"; DumpPacket(OriginalHead, BBEnd));
  LLVM_DEBUG(dbgs() << "\t\tOriginalInstruction:\t";
             DumpPacket(OriginalInstruction->getIterator(), BBEnd));
  LLVM_DEBUG(dbgs() << "\t\tOutcastFrom:\t"; DumpPacket(OutcastFrom, BBEnd));
 
  // Clean up the original source bundle on a global scope.
  if (OriginalHead != MachineBasicBlock::instr_iterator() &&
      QII->isEndLoopN(OriginalHead->getOpcode())) {
    // Single endloop left. Since it is not a real instruction,
    // we can simply add it to a non empty previous bundle, if one exist,
    // or let assembler to produce a fake bundle for it.
    LLVM_DEBUG(dbgs() << "\t\tOnly endloop in packet.\n");
    MachineBasicBlock::instr_iterator I(OriginalHead);
    if (OriginBB->begin() != I) {
      --I;
      if (I->isBundled()) {
        if (!I->isBundledWithSucc())
          I->bundleWithSucc();
        if (!OriginalHead->isBundledWithPred())
          OriginalHead->bundleWithPred();
      }
      // else we probably need to create a new bundle here.
      // SourceLocation = NULL;
    }
  } else if (MovingDependentOp &&
             OriginalHead != MachineBasicBlock::instr_iterator()) {
    if (OriginalHead->isBundled()) {
      for (MachineBasicBlock::instr_iterator J = ++OriginalHead;
           J != OriginalTail && J->isInsideBundle() && !J->isBundle(); ++J) {
        // Need to oldify it.
        if (MIsHaveTrueDependency(OriginalInstruction, &*J) &&
            QII->isDotNewInst(*J)) {
          LLVM_DEBUG(dbgs() << "\t\tDemoting to .old:\t"; J->dump());
          DemoteToDotOld(&*J);
        }
      }
    } else {
      // Single instruction left.
      if (MIsHaveTrueDependency(OriginalInstruction, &*OriginalHead) &&
          QII->isDotNewInst(*OriginalHead)) {
        LLVM_DEBUG(dbgs() << "\t\tDemoting to .old op:\t";
                   OriginalHead->dump());
        DemoteToDotOld(&*OriginalHead);
      }
    }
  }
 
  // Now we need to update liveness to all BBs involved
  // including those we might have "passed" through on the way here.
  LLVM_DEBUG(dbgs() << "\n\tTo BB after bundle update:\n"; HomeBB->dump());
  LLVM_DEBUG(dbgs() << "\n\n\tFrom BB after bundle update:\n";
             OriginBB->dump());
 
  // Update global liveness.
  LLVM_DEBUG(dbgs() << "\n\tWorkList:\t");
  for (std::list<MachineBasicBlock *>::iterator BBI = WorkList.begin(),
                                                BBIE = WorkList.end();
       BBI != BBIE; BBI++) {
    LLVM_DEBUG(dbgs() << "BB#" << (*BBI)->getNumber() << " ");
  }
  LLVM_DEBUG(dbgs() << "\n");
 
  do {
    MachineBasicBlock *BB = WorkList.back();
    WorkList.pop_back();
    CurrentRegion->getLivenessInfoForBB(BB)->UpdateLiveness(BB);
  } while (!WorkList.empty());
 
  // No need to analyze for empty BB or update CFG for same BB pullup.
  if (OriginBB == HomeBB)
    return &*TargetHead;
  // If the instruction moved was a branch we need to update the
  // successor/predecessor of OriginBB and HomeBB accordingly.
  MachineBasicBlock *HomeTBB, *HomeFBB;
  MachineInstr *FTA = NULL, *STA = NULL;
  bool HomeBBAnalyzed = !AnalyzeBBBranches(HomeBB, HomeTBB, FTA, HomeFBB, STA);
  if (MII->isBranch()) {
    if (HomeBBAnalyzed) {
      UpdateCFG(HomeBB, OriginBB, &*MII, HomeTBB, HomeFBB, FTA, STA, MBPI);
    } else {
      llvm_unreachable("Underimplememted AnalyzeBBBranches");
    }
  }
  // If we have exhausted the OriginBB clean it up.
  // Beware that we could have created dual conditional jumps, which
  // ultimately means we can have three way jumps.
  if (IsEmptyBlock(OriginBB) && !OriginBB->isEHPad() &&
      !OriginBB->hasAddressTaken() && !OriginBB->succ_empty()) {
    // Dead block? Unlikely, but check.
    LLVM_DEBUG(dbgs() << "Empty BB(" << OriginBB->getNumber() << ").\n");
    // Update region map.
    CurrentRegion->RemoveBBFromRegion(OriginBB);
    // Keep the list of empty basic blocks to be freed later.
    EmptyBBs.push_back(OriginBB);
    if (OriginBB->pred_empty() || OriginBB->succ_empty())
      return &*TargetHead;
 
    if (OriginBB->succ_size() == 1) {
      // Find empty block's successor.
      MachineBasicBlock *CommonFBB = *OriginBB->succ_begin();
      updatePredecessors(*OriginBB, CommonFBB);
      // Remove the only successor entry for empty BB.
      OriginBB->removeSuccessor(CommonFBB);
    } else {
      // Three way branching is not yet fully supported.
      assert((OriginBB->succ_size() == 2) && "Underimplemented 3way branch.");
      MachineBasicBlock *OriginTBB, *OriginFBB;
      MachineInstr *FTB = NULL, *STB = NULL;
 
      LLVM_DEBUG(dbgs() << "\tComplex case.\n");
      if (HomeBBAnalyzed &&
          !AnalyzeBBBranches(OriginBB, OriginTBB, FTB, OriginFBB, STB)) {
        assert(OriginFBB && "Missing Origin FBB");
        if (HomeFBB == OriginBB) {
          // OriginBB is FBB for HomeBB.
          if (HomeTBB == OriginTBB) {
            // Shared TBB target, common FBB.
            updatePredecessors(*OriginBB, OriginFBB);
          } else if (HomeTBB == OriginFBB) {
            // Shared TBB target, common FBB.
            updatePredecessors(*OriginBB, OriginTBB);
          } else {
            // Three way branch. Add new successor to HomeBB.
            updatePredecessors(*OriginBB, OriginFBB);
            // TODO: Update the weight as well.
            // Adding the successor to make updatePredecessor happy.
            HomeBB->addSuccessor(OriginBB);
            updatePredecessors(*OriginBB, OriginTBB);
          }
        } else if (HomeTBB == OriginBB) {
          // OriginBB is TBB for HomeBB.
          if (HomeFBB == OriginTBB) {
            // Shared TBB target, common FBB.
            updatePredecessors(*OriginBB, OriginFBB);
          } else if (HomeFBB == OriginFBB) {
            // Shared TBB target, common FBB.
            updatePredecessors(*OriginBB, OriginTBB);
          } else {
            // Three way branch. Add new successor to HomeBB.
            updatePredecessors(*OriginBB, OriginFBB);
            // TODO: Update the weight as well.
            // Adding the successor to make updatePredecessor happy.
            HomeBB->addSuccessor(OriginBB);
            updatePredecessors(*OriginBB, OriginTBB);
          }
        } else
          llvm_unreachable("CFG update failed");
        // The empty BB can now be relieved of its successors.
        OriginBB->removeSuccessor(OriginFBB);
        OriginBB->removeSuccessor(OriginTBB);
      } else
        llvm_unreachable("Underimplemented analyzeBranch");
    }
    LLVM_DEBUG(dbgs() << "Updated BB(" << HomeBB->getNumber() << ").\n";
               HomeBB->dump());
  }
  return &*TargetHead;
}
 
// Find where inside a given bundle current instruction should be inserted.
// Instruction will be inserted _before_ this position.
MachineBasicBlock::instr_iterator
HexagonGlobalSchedulerImpl::findInsertPositionInBundle(
    MachineBasicBlock::iterator &Bundle, MachineInstr *MI, bool &LastInBundle) {
  MachineBasicBlock::instr_iterator MII = Bundle.getInstrIterator();
  MachineBasicBlock *MBB = MII->getParent();
  MachineBasicBlock::instr_iterator BBEnd = MBB->instr_end();
  MachineBasicBlock::instr_iterator FirstBranch = BBEnd;
  MachineBasicBlock::instr_iterator LastBundledInstruction = BBEnd;
  MachineBasicBlock::instr_iterator DualJumpFirstCandidate = BBEnd;
 
  assert(MII->isBundle() && "Missing insert location");
  bool isDualJumpSecondCandidate = IsDualJumpSecondCandidate(MI);
  LastInBundle = false;
 
  for (++MII; MII != BBEnd && MII->isInsideBundle() && !MII->isBundle();
       ++MII) {
    if (MII->isBranch() && (FirstBranch == BBEnd))
      FirstBranch = MII;
    // If what we insert is a dual jump, we need to find
    // first jump, and insert new instruction after it.
    if (isDualJumpSecondCandidate && IsDualJumpFirstCandidate(&*MII))
      DualJumpFirstCandidate = MII;
    LastBundledInstruction = MII;
  }
 
  if (DualJumpFirstCandidate != BBEnd) {
    // First respect dual jumps.
    ++DualJumpFirstCandidate;
    if (DualJumpFirstCandidate == BBEnd ||
        DualJumpFirstCandidate == LastBundledInstruction)
      LastInBundle = true;
    return DualJumpFirstCandidate;
  } else if (FirstBranch != BBEnd) {
    // If we have no dual jumps, but do have a single
    // branch in the bundle, add our new instruction
    // right before it.
    return FirstBranch;
  } else if (LastBundledInstruction != BBEnd) {
    LastInBundle = true;
    return ++LastBundledInstruction;
  } else
    llvm_unreachable("Lost in bundle");
  return MBB->instr_begin();
}
 
/// This function for now needs to try to insert new instruction
/// in correct serial semantics fashion - i.e. find "correct" insert
/// point for instruction as if inserting in serial sequence.
MachineBasicBlock::instr_iterator HexagonGlobalSchedulerImpl::insertTempCopy(
    MachineBasicBlock *MBB, MachineBasicBlock::iterator &TargetPacket,
    MachineInstr *MI, bool DeleteOldCopy) {
  MachineBasicBlock::instr_iterator MII;
  MachineBasicBlock *CurrentBB = MI->getParent();
 
  assert(CurrentBB && "Corrupt instruction");
  // Create a temporary copy of the instruction we are considering.
  // LLVM refuses to deal with an instruction which was not inserted
  // to any BB. We can visit multiple BBs on the way "up", so we
  // create a temp copy of the original instruction and delete it later.
  // It is way cheaper than using splice and then
  // needing to undo it most of the time.
  MachineInstr *NewMI = MI->getParent()->getParent()->CloneMachineInstr(MI);
  // Make sure all bundling flags are cleared.
  if (NewMI->isBundledWithPred())
    NewMI->unbundleFromPred();
  if (NewMI->isBundledWithSucc())
    NewMI->unbundleFromSucc();
 
  if (DeleteOldCopy) {
    // Remove our temporary instruction.
    // MachineBasicBlock::erase method calls unbundleSingleMI()
    // prior to deletion, so we do not have to do it here.
    MachineBasicBlock::instr_iterator kill_it(MI);
    CurrentBB->erase(kill_it);
  }
 
  // If the original instruction used new value operands,
  // it might need to be changed to generic form
  // before further processing.
  if (QII->isDotNewInst(*NewMI))
    DemoteToDotOld(NewMI);
 
  // Insert new temporary instruction.
  // If this is the destination packet, insert the tmp after
  // its header. Otherwise, as second instr in BB.
  if (TargetPacket->getParent() == MBB) {
    MII = TargetPacket.getInstrIterator();
 
    if (MII->isBundled()) {
      bool LastInBundle = false;
      MachineBasicBlock::instr_iterator InsertBefore =
          findInsertPositionInBundle(TargetPacket, NewMI, LastInBundle);
      MIBundleBuilder Bundle(&*TargetPacket);
      Bundle.insert(InsertBefore, NewMI);
    } else
      MBB->insertAfter(MII, NewMI);
  } else {
    MII = MBB->instr_begin();
 
    // Skip debug instructions.
    while (MII->isDebugInstr())
      MII++;
 
    if (MII->isBundled()) {
      MIBundleBuilder Bundle(&*MII);
      Bundle.insert(++MII, NewMI);
    } else
      MBB->insertAfter(MII, NewMI);
  }
  return NewMI->getIterator();
}
 
// Check for a conditionally assigned register within the block.
bool HexagonGlobalSchedulerImpl::MIsCondAssign(MachineInstr *BMI,
                                               MachineInstr *MI,
                                               SmallVector<unsigned, 4> &Defs) {
  if (!QII->isPredicated(*BMI))
    return false;
  // Its a conditional instruction, now is it the same registers as MI?
  SmallVector<unsigned, 4> CondDefs;
  SmallVector<unsigned, 8> CondUses;
  parseOperands(BMI, CondDefs, CondUses);
 
  for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(), IDE = Defs.end();
       ID != IDE; ++ID) {
    for (SmallVector<unsigned, 4>::iterator CID = CondDefs.begin(),
                                            CIDE = CondDefs.end();
         CID != CIDE; ++CID) {
      if (AliasingRegs(*CID, *ID)) {
        LLVM_DEBUG(dbgs() << "\tFound conditional def, can't move\n";
                   BMI->dump());
        return true;
      }
    }
  }
  return false;
}
 
// Returns the Union of all the elements in Set1 and
// Union of all the elements in Set2 separately.
// Constraints:
// Set1 and Set2 should contain an entry for each element in Range.
template <typename ElemType, typename IndexType>
void Unify(std::vector<ElemType> Range,
           std::map<ElemType, std::vector<IndexType>> &Set1,
           std::map<ElemType, std::vector<IndexType>> &Set2,
           std::pair<std::vector<IndexType>, std::vector<IndexType>> &UnionSet,
           unsigned union_size = 100) {
  typedef
      typename std::map<ElemType, std::vector<IndexType>>::iterator PosIter_t;
  typedef typename std::vector<IndexType>::iterator IndexIter_t;
  std::vector<IndexType> &Union1 = UnionSet.first;
  std::vector<IndexType> &Union2 = UnionSet.second;
  Union1.resize(union_size, 0);
  Union2.resize(union_size, 0);
  LLVM_DEBUG(dbgs() << "\n\t\tElements in the range:\n";);
  typename std::vector<ElemType>::iterator iter = Range.begin();
  while (iter != Range.end()) {
    if ((*iter)->isDebugInstr()) {
      ++iter;
      continue;
    }
    LLVM_DEBUG((*iter)->dump());
    PosIter_t set1_pos = Set1.find(*iter);
    assert(set1_pos != Set1.end() &&
           "Set1 should contain an entry for each element in Range.");
    IndexIter_t set1idx = set1_pos->second.begin();
    while (set1idx != set1_pos->second.end()) {
      Union1[*set1idx] = 1;
      ++set1idx;
    }
    PosIter_t set2_pos = Set2.find(*iter);
    assert(set2_pos != Set2.end() &&
           "Set2 should contain an entry for each element in Range.");
    IndexIter_t set2idx = set2_pos->second.begin();
    while (set2idx != set2_pos->second.end()) {
      Union2[*set2idx] = 1;
      ++set2idx;
    }
    ++iter;
  }
}
 
static void UpdateBundle(MachineInstr *BundleHead) {
  assert(BundleHead->isBundle() && "Not a bundle header");
  if (!BundleHead)
    return;
  unsigned Size = BundleHead->getBundleSize();
  if (Size >= 2)
    return;
  if (Size == 1) {
    MachineBasicBlock::instr_iterator MIter = BundleHead->getIterator();
    MachineInstr *MI = &*(++MIter);
    MI->unbundleFromPred();
  }
  BundleHead->eraseFromParent();
}
 
/// Gatekeeper for instruction speculation.
/// If all MI defs are dead (not live-in) to any other
/// BB but the one we are moving into, and it could not cause
/// exception by early execution, allow it to be pulled up.
bool HexagonGlobalSchedulerImpl::canMIBeSpeculated(
    MachineInstr *MI, MachineBasicBlock *ToBB, MachineBasicBlock *FromBB,
    std::vector<MachineInstr *> &backtrack) {
  // For now disallow memory accesses from speculation.
  // Generally we can check if they potentially may trap/cause an exception.
  if (!EnableSpeculativePullUp || !MI || MI->mayStore())
    return false;
 
  LLVM_DEBUG(dbgs() << "\t[canMIBeSpeculated] From BB(" << FromBB->getNumber()
                    << "):\t";
             MI->dump());
  LLVM_DEBUG(dbgs() << "\tTo this BB:\n"; ToBB->dump());
 
  if (!ToBB->isSuccessor(FromBB))
    return false;
 
  // This is a very tricky topic. Speculating arithmetic instructions with
  // results dead out of a loop more times then required by number of
  // iterations is safe, while speculating loads can cause an exception.
  // Simplest of checks is to not cross loop exit edge, or in our case
  // do not pull-in to a loop exit BB, but there are implications for
  // non-natural loops (not recognized by LLVM as loops) and multi-threaded
  // code.
  if (AllowSpeculateLoads && MI->mayLoad()) {
    // Invariant loads should always be safe.
    if (!MI->isDereferenceableInvariantLoad())
      return false;
    LLVM_DEBUG(dbgs() << "\tSpeculating a Load.\n");
  }
 
  SmallVector<unsigned, 4> Defs;
  SmallVector<unsigned, 8> Uses;
  parseOperands(MI, Defs, Uses);
 
  // Do not speculate instructions that modify reserved global registers.
  for (unsigned R : Defs)
    if (MRI->isReserved(R) && QRI->isGlobalReg(R))
      return false;
 
  for (MachineBasicBlock::const_succ_iterator SI = ToBB->succ_begin(),
                                              SE = ToBB->succ_end();
       SI != SE; ++SI) {
    // TODO: Allow an instruction (I) which 'defines' the live-in reg (R)
    // along the path when I is the first instruction to use the R.
    // i.e., I kills R before any other instruction in the BB uses it.
    // TODO: We have already parsed live sets - reuse them.
    if (*SI == FromBB)
      continue;
    LLVM_DEBUG(dbgs() << "\tTarget succesor BB to check:\n"; (*SI)->dump());
    LLVM_DEBUG(
        for (MachineBasicBlock::const_succ_iterator SII = (*SI)->succ_begin(),
             SIE = (*SI)->succ_end();
             SII != SIE; ++SII)(*SII)
            ->dump());
    for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(),
                                            E = (*SI)->livein_end();
         I != E; ++I)
      for (SmallVector<unsigned, 4>::iterator ID = Defs.begin(),
                                              IDE = Defs.end();
           ID != IDE; ++ID) {
        if (AliasingRegs((*I).PhysReg, *ID))
          return false;
      }
 
    // Check the successor blocks for conditional define.
    // TODO: We should really test the whole path here.
    for (MachineBasicBlock::instr_iterator BI = (*SI)->instr_begin(),
                                           E = (*SI)->instr_end();
         BI != E; ++BI) {
      if (BI->isBundle() || BI->isDebugInstr())
        continue;
      LLVM_DEBUG(dbgs() << "\t\tcheck against:\t"; BI->dump());
      if (MIsCondAssign(&*BI, MI, Defs))
        return false;
    }
  }
  // Taking a very conservative approach during speculation.
  // Traverse the path (FromBB, ToBB] and make sure
  // that the def-use set of the instruction to be moved
  // are not modified.
  std::vector<MachineBasicBlock *> PathBB;
  for (unsigned i = 0; i < backtrack.size(); ++i) {
    // Insert unique BB along the path but skip FromBB
    MachineBasicBlock *MBB = backtrack[i]->getParent();
    if ((MBB != FromBB) &&
        (std::find(PathBB.begin(), PathBB.end(), MBB) == PathBB.end()))
      PathBB.push_back(MBB);
  }
  bool WaitingForTargetPacket = true;
  MachineBasicBlock::instr_iterator MII;
  std::vector<MachineInstr *> TraversalRange;
  LLVM_DEBUG(dbgs() << "\n\tElements in the range:");
  // TODO: Use just the backtrack to get TraversalRange because it
  // contains the path (only when speculated from a path in region).
  // Note: We check the dependency of instruction-to-move with
  // all the instructions (starting from backtrack[0]) in the parent BBs
  // because a BB might have a branching from in between due to packetization
  // and just checking packets in the backtrack won't be comprehensive.
  for (unsigned i = 0; i < PathBB.size(); ++i) {
    for (MII = PathBB[i]->instr_begin(); MII != PathBB[i]->instr_end(); ++MII) {
      // Skip instructions until the target packet is found.
      // although target packet is already checked for correctness,
      // it is good to check here to validate intermediate pullups.
      if (backtrack[0] == &*MII)
        WaitingForTargetPacket = false;
      if (WaitingForTargetPacket)
        continue;
      if (MII->isBundle())
        continue;
      // TODO: Ideally we should check that there is a `linear' control flow
      // in the TraversalRange in all possible manner. For e.g.,
      // BB0 { packet1: if(p0) indirect_jump BB1;
      //      packet2: jump BB2 }
      // BB1 { i1 }. In this case we should not pull `i1' into packet2.
      if (MII->isCall() || MII->isReturn() ||
          (MII->getOpcode() == Hexagon::J2_jump && !MII->getOperand(0).isMBB()))
        return false;
      if (MI != &*MII) {
        TraversalRange.push_back(&*MII);
        LLVM_DEBUG(MII->dump(););
      }
    }
  }
  // Get the union of def/use set of all the instructions along TraversalRange.
  std::pair<std::vector<unsigned>, std::vector<unsigned>> RangeDefUse;
  Unify(TraversalRange, MIDefSet, MIUseSet, RangeDefUse, QRI->getNumRegs());
  // No instruction (along TraversalRange) should 'define' the use set of MI
  for (unsigned j = 0; j < Uses.size(); ++j)
    if (RangeDefUse.first[Uses[j]]) {
      LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
                        << printReg(Uses[j], QRI););
      return false;
    }
  // No instruction (along TraversalRange) should 'define' or 'use'
  // the def set of MI
  for (unsigned j = 0; j < Defs.size(); ++j)
    if (RangeDefUse.first[Defs[j]] || RangeDefUse.second[Defs[j]]) {
      LLVM_DEBUG(dbgs() << "\n\t\tUnresolved dependency along path to HOME for "
                        << printReg(Defs[j], QRI););
      return false;
    }
  return true;
}
 
/// Try to move InstrToMove to TargetPacket using path stored in backtrack.
/// SourceLocation is current iterator point. It must be updated to the new
/// iteration location after all updates.
/// Alogrithm:
/// To move an instruction (I) from OriginBB through HomeBB via backtrack.
/// for each packet (i) in backtrack, analyzeBranch
/// case 1 (success)
///   case Pulling from conditional branch:
///     if I is predicable
///         Try to predicate on the branch condition
///     else
///         Try to speculate I to backtrack[i].
///   case Pulling from unconditional branch:
///         Just pullup. (TODO: Speculate here as well)
/// case 2 (fails)
///     Try to speculate I backtrack[i].
bool HexagonGlobalSchedulerImpl::MoveMItoBundle(
    BasicBlockRegion *CurrentRegion,
    MachineBasicBlock::instr_iterator &InstrToMove,
    MachineBasicBlock::iterator &NextMI,
    MachineBasicBlock::iterator &TargetPacket,
    MachineBasicBlock::iterator &SourceLocation,
    std::vector<MachineInstr *> &backtrack, bool MovingDependentOp,
    bool PathInRegion) {
  MachineBasicBlock *HomeBB = TargetPacket->getParent();
  MachineBasicBlock *OriginBB = InstrToMove->getParent();
  MachineBasicBlock *CurrentBB = OriginBB;
  MachineBasicBlock *CleanupBB = OriginBB;
  MachineBasicBlock *PreviousBB = OriginBB;
  MachineInstr *OriginalInstructionToMove = &*InstrToMove;
 
  assert(HomeBB && "Missing HomeBB");
  assert(OriginBB && "Missing OriginBB");
 
  LLVM_DEBUG(dbgs() << "\n.........[MoveMItoBundle]..............\n");
  LLVM_DEBUG(dbgs() << "\t\tInstrToMove   :\t"; InstrToMove->dump());
  LLVM_DEBUG(dbgs() << "\t\tTargetPacket  :\t";
             DumpPacket(TargetPacket.getInstrIterator()));
  LLVM_DEBUG(dbgs() << "\t\tSourceLocation:\t";
             DumpPacket(SourceLocation.getInstrIterator()));
 
  // We do not allow to move instructions in the same BB.
  if (HomeBB == OriginBB) {
    LLVM_DEBUG(dbgs() << "\t\tSame BB pull-up.\n");
    if (!EnableLocalPullUp)
      return false;
  }
 
  if (OneFloatPerPacket && QII->isFloat(*TargetPacket) &&
      QII->isFloat(*InstrToMove))
    return false;
 
  if (OneComplexPerPacket && QII->isComplex(*TargetPacket) &&
      QII->isComplex(*InstrToMove))
    return false;
 
  LLVM_DEBUG(dbgs() << "\t\tWay home:\n");
  // Test integrity of the back track.
  for (unsigned i = 0; i < backtrack.size(); ++i) {
    assert(backtrack[i]->getParent() && "Messed back track.");
    LLVM_DEBUG(dbgs() << "\t\t[" << i << "] BB("
                      << backtrack[i]->getParent()->getNumber() << ")\t";
               backtrack[i]->dump());
  }
  LLVM_DEBUG(dbgs() << "\n");
 
  bool NeedCleanup = false;
  bool NeedToPredicate = false;
  bool MINeedToNewify = false;
  unsigned DepReg = std::numeric_limits<unsigned>::max();
  bool isDualJump = false;
  SmallVector<MachineOperand, 4> Cond;
  SmallVector<MachineOperand, 4> PredCond;
  std::vector<MachineInstr *> PullUpPath;
  if (PathInRegion)
    PullUpPath = backtrack;
  else {
    PullUpPath.push_back(&*TargetPacket);
    PullUpPath.push_back(&*InstrToMove);
  }
 
  // Now start iterating over all instructions
  // preceeding the one we are trying to move,
  // and see if they could be reodered/bypassed.
  for (std::vector<MachineInstr *>::reverse_iterator RI = backtrack.rbegin(),
                                                     RIE = backtrack.rend();
       RI < RIE; ++RI) {
    // Once most of debug will be gone, this will be a real assert.
    // assert((backtrack.front() == ToThisBundle) && "Lost my way home.");
    MachineInstr *MIWH = *RI;
    if (QII->isDotNewInst(*InstrToMove)) {
      LLVM_DEBUG(dbgs() << "Cannot move a dot new instruction:";
                 InstrToMove->dump());
      if (NeedCleanup)
        CleanupBB->erase(InstrToMove);
      return false;
    }
    if (canCauseStall(&*InstrToMove, MIWH)) {
      if (NeedCleanup)
        CleanupBB->erase(InstrToMove);
      return false;
    }
    LLVM_DEBUG(dbgs() << "\t> Step home BB(" << MIWH->getParent()->getNumber()
                      << "):\t";
               DumpPacket(MIWH->getIterator()));
 
    // See if we cross a jump, and possibly change the form of instruction.
    // Passing through BBs with dual jumps in different packets
    // takes extra care.
    bool isBranchMIWH = isBranch(MIWH);
    if (((&*SourceLocation != MIWH) && isBranchMIWH) ||
        (CurrentBB != MIWH->getParent())) {
      LLVM_DEBUG(dbgs() << "\tChange BB from(" << CurrentBB->getNumber()
                        << ") to (" << MIWH->getParent()->getNumber() << ")\n");
      PreviousBB = CurrentBB;
      CurrentBB = MIWH->getParent();
 
      // See what kind of branch we are dealing with.
      MachineBasicBlock *PredTBB = NULL;
      MachineBasicBlock *PredFBB = NULL;
 
      if (QII->analyzeBranch(*CurrentBB, PredTBB, PredFBB, Cond, false)) {
        // We currently do not handle NV jumps of this kind:
        // if (cmp.eq(r0.new, #0)) jump:t .LBB12_69
        // TODO: Need to handle them.
        LLVM_DEBUG(dbgs() << "\tCould not analyze branch.\n");
 
        // This is the main point of lost performance.
        // We could try to speculate here, but for that we need accurate
        // liveness info, and it is not ready yet.
        if (!canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
                               PullUpPath)) {
          if (NeedCleanup)
            CleanupBB->erase(InstrToMove);
          return false;
        } else {
          // Save speculated instruction moved.
          SpeculatedIns.insert(
              std::make_pair(OriginalInstructionToMove, OriginBB));
          LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove"; InstrToMove->dump());
        }
 
        LLVM_DEBUG(dbgs() << "\tSpeculating.\n");
        // If we are speculating, we can come through a predication
        // into an unconditional branch...
        // For now simply bail out.
        // TODO: See if this ever happens.
        if (NeedToPredicate) {
          LLVM_DEBUG(dbgs()
                     << "\tUnderimplemented pred for speculative move.\n");
          if (NeedCleanup)
            CleanupBB->erase(InstrToMove);
          return false;
        }
        InstrToMove =
            insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove, NeedCleanup);
        NeedCleanup = true;
        NeedToPredicate = false;
        assert(!NeedToPredicate && "Need to handle predication for this case");
        CleanupBB = CurrentBB;
        // No need to recheck for resources - instruction did not change.
        LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
      } else {
        bool LocalNeedPredication = true;
        // We were able to analyze the branch.
        if (!isBranchMIWH && !PredTBB) {
          LLVM_DEBUG(dbgs() << "\tDo not need predicate for this case.\n");
          LocalNeedPredication = false;
        }
        // First see if this is a potential dual jump situation.
        if (IsDualJumpSecondCandidate(&*InstrToMove) &&
            IsDualJumpFirstCandidate(TargetPacket)) {
          LLVM_DEBUG(dbgs() << "\tPerforming unrestricted dual jump.\n");
          isDualJump = true;
        } else if (LocalNeedPredication && (PredFBB != PreviousBB)) {
          // Predicate instruction based on condition feeding it.
          // This is generally a statefull pull-up path.
          // Can this insn be predicated? If so, try to do it.
          if (TII->isPredicable(*InstrToMove)) {
            if (PredTBB) {
              if (PreviousBB != PredTBB) {
                // If we "came" not from TBB, we need to invert condition.
                if (TII->reverseBranchCondition(Cond)) {
                  LLVM_DEBUG(dbgs() << "\tUnable to invert condition.\n");
                  if (NeedCleanup)
                    CleanupBB->erase(InstrToMove);
                  return false;
                }
              }
              LLVM_DEBUG(dbgs() << "\tTBB(" << PredTBB->getNumber()
                                << ")InvertCondition("
                                << (PreviousBB != PredTBB) << ")\n");
            }
            // Create a new copy of the instruction we are trying to move.
            // It changes enough (new BB, predicated form) and untill we
            // reach home, we do not even know if it is going to work.
            InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
                                         NeedCleanup);
            NeedCleanup = true;
            NeedToPredicate = true;
            CleanupBB = CurrentBB;
 
            if (PredCond.empty() && // If not already predicated.
                TII->PredicateInstruction(*InstrToMove, Cond)) {
              LLVM_DEBUG(dbgs() << "\tNew predicated insn:\t";
                         InstrToMove->dump());
              // After predication some instruction could become const extended:
              // L2_loadrigp == "$dst=memw(#$global)"
              // L4_ploadrit_abs == "if ($src1) $dst=memw(##$global)"
              // Resource checking for those is different.
              if ((QII->isExtended(*InstrToMove) ||
                   QII->isConstExtended(*InstrToMove) ||
                   isJumpOutOfRange(&*InstrToMove)) &&
                  !tryAllocateResourcesForConstExt(&*InstrToMove, false)) {
                // If we cannot, do not modify the state.
                LLVM_DEBUG(dbgs()
                           << "\tEI Could not be added to the packet.\n");
                CleanupBB->erase(InstrToMove);
                return false;
              }
 
              if (!ResourceTracker->canReserveResources(*InstrToMove) ||
                  !shouldAddToPacket(*InstrToMove)) {
                // It will not fit in its new form...
                LLVM_DEBUG(dbgs() << "\tCould not be added in its new form.\n");
                CurrentBB->erase(InstrToMove);
                return false;
              }
 
              // Need also verify that we can newify it if we want to.
              if (NeedToNewify(InstrToMove, &DepReg, &*TargetPacket)) {
                if (isNewifiable(InstrToMove, DepReg, &*TargetPacket)) {
                  MINeedToNewify = true;
                  LLVM_DEBUG(dbgs() << "\t\t\tNeeds to NEWify on Reg("
                                    << printReg(DepReg, QRI) << ").\n");
                } else {
                  LLVM_DEBUG(dbgs() << "\tNon newifiable in this bundle: ";
                             InstrToMove->dump());
                  CleanupBB->erase(InstrToMove);
                  return false;
                }
              }
 
              LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
              PredCond = Cond;
              // Now the instruction uses the pred-reg as well.
              if (!Cond.empty() && (Cond.size() == 2)) {
                MIUseSet[OriginalInstructionToMove].push_back(Cond[1].getReg());
              }
              assert(((Cond.size() <= 2) &&
                      !(QII->isNewValueJump(Cond[0].getImm()))) &&
                     "Update MIUseSet for new-value compare jumps");
            } else {
              LLVM_DEBUG(dbgs() << "\tCould not predicate it\n");
              LLVM_DEBUG(dbgs() << "\tTrying to speculate!\t";
                         InstrToMove->dump());
              bool DistantSpeculation = false;
              std::vector<MachineInstr *> NonPredPullUpPath;
              unsigned btidx = 0;
              // Generate a backtrack path for instruction to be speculated.
              // Original backtrack may start from a different (ancestor)
              // target packet.
              while (btidx < backtrack.size()) {
                const MachineBasicBlock *btBB = backtrack[btidx]->getParent();
                if ((btBB == PreviousBB) || (btBB == CurrentBB))
                  NonPredPullUpPath.push_back(backtrack[btidx]);
                ++btidx;
              }
              // Speculate only to immediate predecessor.
              if (PreviousBB != CurrentBB) {
                if (*(PreviousBB->pred_begin()) != CurrentBB) {
                  // In a region there are no side entries.
                  DistantSpeculation = true;
                  LLVM_DEBUG(dbgs()
                                 << "\n\tMI not in immediate successor of BB#"
                                 << CurrentBB->getNumber() << ", MI is in BB#"
                                 << PreviousBB->getNumber(););
                }
                assert((PreviousBB->pred_size() < 2) &&
                       "Region with a side entry");
              }
              // TODO: Speculate ins. when pulled from unlikely path.
              if (DistantSpeculation || /*!PathInRegion ||*/
                  InstrToMove->mayLoad() || InstrToMove->mayStore() ||
                  InstrToMove->hasUnmodeledSideEffects() ||
                  !canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
                                     NonPredPullUpPath)) {
                CleanupBB->erase(InstrToMove);
                return false;
              } else {
                // Save speculated instruction moved.
                NeedToPredicate = false;
                SpeculatedIns.insert(
                    std::make_pair(OriginalInstructionToMove, OriginBB));
                LLVM_DEBUG(dbgs() << "\nPredicable+SpeculatedInsToMove";
                           InstrToMove->dump());
              }
            }
          } else {
            // This is a non-predicable instruction. We still can try to
            // speculate it here.
            LLVM_DEBUG(dbgs() << "\tNon predicable insn!\t";
                       InstrToMove->dump());
            // TODO: Speculate ins. when pulled from unlikely path.
            if (!SpeculateNonPredInsn || !PathInRegion ||
                InstrToMove->mayLoad() || InstrToMove->mayStore() ||
                InstrToMove->hasUnmodeledSideEffects() ||
                !canMIBeSpeculated(&*InstrToMove, CurrentBB, PreviousBB,
                                   PullUpPath)) {
              if (NeedCleanup)
                CleanupBB->erase(InstrToMove);
              return false;
            } else {
              // Save speculated instruction moved.
              SpeculatedIns.insert(
                  std::make_pair(OriginalInstructionToMove, OriginBB));
              LLVM_DEBUG(dbgs() << "\nNonPredicable+SpeculatedInsToMove";
                         InstrToMove->dump());
            }
 
            InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
                                         NeedCleanup);
            NeedCleanup = true;
            CleanupBB = CurrentBB;
          }
        } else {
          // No branch. Fall through.
          LLVM_DEBUG(dbgs() << "\tFall through BB.\n"
                            << "\tCurrentBB:" << CurrentBB->getNumber()
                            << "\tPreviousBB:" << PreviousBB->getNumber();
                     if (PredFBB) dbgs()
                     << "\tPredFBB:" << PredFBB->getNumber(););
          // Even though this is a fall though case, we still can
          // have a dual jump situation here with a CALL involved.
          // For now simply avoid it.
          if (IsDualJumpSecondCandidate(&*InstrToMove)) {
            llvm_unreachable("Dual jumps with known?");
            LLVM_DEBUG(dbgs() << "\tUnderimplemented dual jump formation.\n");
            if (NeedCleanup)
              CleanupBB->erase(InstrToMove);
            return false;
          }
 
          if (!CurrentBB->isSuccessor(PreviousBB)) {
            LLVM_DEBUG(dbgs() << "\tNon-successor fall through.\n");
            if (NeedCleanup)
              CleanupBB->erase(InstrToMove);
            return false;
          }
          SpeculatedIns.insert(
              std::make_pair(OriginalInstructionToMove, OriginBB));
          LLVM_DEBUG(dbgs() << "\nSpeculatedInsToMove+FallThroughBB";
                     InstrToMove->dump());
          // Create a temp copy.
          InstrToMove = insertTempCopy(CurrentBB, TargetPacket, &*InstrToMove,
                                       NeedCleanup);
          NeedCleanup = true;
          NeedToPredicate = false;
          CleanupBB = CurrentBB;
          LLVM_DEBUG(dbgs() << "\tUpdated BB:\n"; CurrentBB->dump());
        }
      }
    }
    // If we have reached Home, great.
    // Original check should have verified that instruction could be added
    // to the target packet, so here we do nothing for deps.
    if (MIWH == backtrack.front()) {
      LLVM_DEBUG(dbgs() << "\tHOME!\n");
      break;
    }
 
    // Test if we can reorder the two MIs.
    // The exception is when we are forming dual jumps - we can pull up
    // dependent instruction to the last bundle of an immediate predecesor
    // of the current BB if control flow permits it.
    // In this special case we also need to update the bundle we are moving
    // from.
    if (!(MovingDependentOp && (MIWH == &*SourceLocation)) &&
        !canReorderMIs(MIWH, &*InstrToMove)) {
      if (NeedCleanup)
        CleanupBB->erase(InstrToMove);
      return false;
    }
  }
  // We have previously tested this instruction, but has not updated the state
  // for it. Do it now.
  if (QII->isExtended(*InstrToMove) || QII->isConstExtended(*InstrToMove) ||
      isJumpOutOfRange(&*InstrToMove)) {
    if (!tryAllocateResourcesForConstExt(&*InstrToMove))
      llvm_unreachable("Missed dependency test");
  }
 
  // Ok. We can safely move this instruction all the way up.
  // We also potentially have a slot for it.
  // During move original instruction could have changed (becoming predicated).
  // Now try to place the final instance of it into the current packet.
  LLVM_DEBUG(dbgs() << "\nWant to move ";
             if (MovingDependentOp) dbgs() << "dependent op"; dbgs() << ": ";
             InstrToMove->dump(); dbgs() << "To BB:\n"; HomeBB->dump();
             dbgs() << "From BB:\n"; OriginBB->dump());
 
  // Keep these two statistics separately.
  if (!isDualJump)
    HexagonNumPullUps++;
  else
    HexagonNumDualJumps++;
 
  // This means we have not yet inserted the temp copy of InstrToMove
  // in the target bundle. We are probably inside the same BB.
  if (!NeedCleanup) {
    InstrToMove =
        insertTempCopy(HomeBB, TargetPacket, &*InstrToMove, NeedCleanup);
    NeedCleanup = true;
  }
 
  // No problems detected. Add it.
  // If we were adding InstrToMove to a single, not yet packetized
  // instruction, we need to create bundle header for it before proceeding.
  // Be carefull since endPacket also resets the DFA state.
  if (!TargetPacket->isBundle()) {
    LLVM_DEBUG(dbgs() << "\tForm a new bundle.\n");
    finalizeBundle(*HomeBB, TargetPacket.getInstrIterator(),
                   std::next(InstrToMove));
    LLVM_DEBUG(HomeBB->dump());
    // Now we need to adjust pointer to the newly created packet header.
    MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
    MII--;
 
    // Is it also on the way home?
    for (unsigned i = 0; i < backtrack.size(); ++i)
      if (backtrack[i] == &*TargetPacket)
        backtrack[i] = &*MII;
 
    // Is it where our next MI is pointing?
    if (NextMI == TargetPacket)
      NextMI = MII;
    TargetPacket = MII;
  }
 
  // Move and Update Liveness info.
  MoveAndUpdateLiveness(CurrentRegion, HomeBB, &*InstrToMove, MINeedToNewify,
                        DepReg, MovingDependentOp, OriginBB,
                        OriginalInstructionToMove, PredCond, SourceLocation,
                        TargetPacket, NextMI, backtrack);
 
  LLVM_DEBUG(dbgs() << "\n______Updated______\n"; HomeBB->dump();
             OriginBB->dump());
 
  return true;
}
 
/// Verify that we respect CFG layout during pull-up.
bool HexagonGlobalSchedulerImpl::isBranchWithinRegion(
    BasicBlockRegion *CurrentRegion, MachineInstr *MI) {
  assert(MI && MI->isBranch() && "Missing call info");
 
  MachineBasicBlock *MBB = MI->getParent();
  LLVM_DEBUG(dbgs() << "\t[isBranchWithinRegion] BB(" << MBB->getNumber()
                    << ") Branch instr:\t";
             MI->dump());
  // If there is only one successor, it is safe to pull.
  if (MBB->succ_size() <= 1)
    return true;
  // If there are multiple successors (jump table), we should
  // not allow pull up over this instruction.
  if (MBB->succ_size() > 2)
    return false;
 
  MachineBasicBlock *NextRegionBB;
  MachineBasicBlock *TBB, *FBB;
  MachineInstr *FirstTerm = NULL;
  MachineInstr *SecondTerm = NULL;
 
  if (AnalyzeBBBranches(MBB, TBB, FirstTerm, FBB, SecondTerm)) {
    LLVM_DEBUG(dbgs() << "\t\tAnalyzeBBBranches failed!\n");
    return false;
  }
 
  // If there is no jump in this BB, it simply falls through.
  if (!FirstTerm) {
    LLVM_DEBUG(dbgs() << "\t\tNo FirstTerm\n");
    return true;
  } else if (QII->isEndLoopN(FirstTerm->getOpcode())) {
    // We can easily analyze where endloop would take us
    // but here it would be pointless either way since
    // the region will not cross it.
    LLVM_DEBUG(dbgs() << "\t\tEndloop terminator\n");
    return false;
  }
  // On some occasions we see code like this:
  // BB#142: derived from LLVM BB %init, Align 4 (16 bytes)
  //  Live Ins: %R17 %R18
  //  Predecessors according to CFG: BB#2
  //  EH_LABEL <MCSym=.Ltmp35>
  //  J2_jump <BB#3>, %PC<imp-def>
  //  Successors according to CFG: BB#3(1048575) BB#138(1)
  // It breaks most assumptions about CFG layout, so untill we know
  // the source of it, let's have a safeguard.
  if (MBB->succ_size() > 1 && !TII->isPredicated(*FirstTerm) &&
      !QII->isNewValueJump(*FirstTerm)) {
    LLVM_DEBUG(dbgs() << "\t\tBadly formed BB.\n");
    return false;
  }
 
  LLVM_DEBUG(dbgs() << "\t\tFirstTerm:  "; FirstTerm->dump());
  LLVM_DEBUG(dbgs() << "\t\tSecondTerm: "; if (SecondTerm) SecondTerm->dump();
             else dbgs() << "None\n";);
 
  // All cases where there is only one branch in BB are OK to proceed.
  if (!SecondTerm)
    return true;
 
  assert(!QII->isEndLoopN(SecondTerm->getOpcode()) && "Found endloop.");
 
  // Find next BB in this region - if there is none, we will likely
  // stop pulling in the next check outside of this function.
  // This largely is don't care.
  NextRegionBB = CurrentRegion->findNextMBB(MBB);
  if (!NextRegionBB) {
    LLVM_DEBUG(dbgs() << "\t\tNo next BB in the region...\n");
    return true;
  }
  LLVM_DEBUG(dbgs() << "\t\tNextRegionBB(" << NextRegionBB->getNumber()
                    << ")\n");
  assert(TBB && "Corrupt BB layout");
  // This means we are trying to pull into a packet _before_ the first
  // branch in the MBB.
  if (MI == FirstTerm) {
    LLVM_DEBUG(dbgs() << "\t\tTBB(" << TBB->getNumber()
                      << ") NextBB in the region(" << NextRegionBB->getNumber()
                      << ")\n");
    return (TBB == NextRegionBB);
  }
  assert(FBB && "Corrupt BB layout");
  // This means we are trying to pull into the packet _after_ first branch,
  // and it is OK if we pull from the second branch target.
  // This pull is always speculative.
  if ((MI != SecondTerm)) {
    LLVM_DEBUG(dbgs() << "\t\tDual terminator not matching SecondTerm.\n");
    return false;
  }
  // Analyze the second branch in the BB.
  LLVM_DEBUG(dbgs() << "\t\tFBB(" << FBB->getNumber()
                    << ") NextBB in the region(" << NextRegionBB->getNumber()
                    << ")\n");
  return (FBB == NextRegionBB);
}
 
/// Check if a given instruction is:
/// - a jump to a distant target
/// - that exceeds its immediate range
/// If both conditions are true, it requires constant extension.
bool HexagonGlobalSchedulerImpl::isJumpOutOfRange(MachineInstr *UnCond,
                                                  MachineInstr *Cond) {
  if (!UnCond || !UnCond->isBranch())
    return false;
 
  MachineBasicBlock *UnCondBB = UnCond->getParent();
  MachineBasicBlock *CondBB = Cond->getParent();
  MachineInstr *FirstTerm = &*(CondBB->getFirstInstrTerminator());
  // This might be worth an assert.
  if (FirstTerm == &*CondBB->instr_end())
    return false;
 
  unsigned InstOffset = BlockToInstOffset[UnCondBB];
  unsigned Distance = 0;
 
  // To save time, estimate exact position of a branch instruction
  // as one at the end of the UnCondBB.
  // Number of instructions times typical instruction size.
  InstOffset += (QII->nonDbgBBSize(UnCondBB) * HEXAGON_INSTR_SIZE);
 
  MachineBasicBlock *TBB = NULL, *FBB = NULL;
  SmallVector<MachineOperand, 4> CondList;
 
  // Find the target of the unconditional branch in UnCondBB, which is returned
  // in TBB. Then use the CondBB to extract the FirsTerm. We desire to replace
  // the branch target in FirstTerm with the branch location from the UnCondBB,
  // provided it is within the distance of the opcode in FirstTerm.
  if (QII->analyzeBranch(*UnCondBB, TBB, FBB, CondList, false))
    // Could not analyze it. give up.
    return false;
 
  if (TBB && (Cond == FirstTerm)) {
    Distance =
        (unsigned)std::abs((long long)InstOffset - BlockToInstOffset[TBB]) +
        SafetyBuffer;
    return !QII->isJumpWithinBranchRange(*FirstTerm, Distance);
  }
  return false;
}
 
// findBundleAndBranch returns the branch instruction and the
// bundle which contains it. Null is returned if not found.
MachineInstr *HexagonGlobalSchedulerImpl::findBundleAndBranch(
    MachineBasicBlock *BB, MachineBasicBlock::iterator &Bundle) {
  // Find the conditional branch out of BB.
  if (!BB)
    return NULL;
  MachineInstr *CondBranch = NULL;
  Bundle = BB->end();
  for (MachineBasicBlock::instr_iterator MII = BB->getFirstInstrTerminator(),
                                         MBBEnd = BB->instr_end();
       MII != MBBEnd; ++MII) {
    MachineInstr *MI = &*MII;
    if (MII->isConditionalBranch()) {
      CondBranch = MI;
    }
  }
  if (!CondBranch)
    return NULL;
  MachineBasicBlock::instr_iterator MII = CondBranch->getIterator();
  if (!MII->isBundled())
    return NULL;
  // Find bundle header.
  for (--MII; MII->isBundled(); --MII)
    if (MII->isBundle()) {
      Bundle = MII;
      break;
    }
  return CondBranch;
}
 
// pullUpPeelBBLoop
// A single BB loop with a register copy at the beginning in its
// own bundle, benefits from eliminating the extra bundle. We do
// this by predicating the register copy in the predecessor BB, and
// again in the last bundle of the loop.
bool HexagonGlobalSchedulerImpl::pullUpPeelBBLoop(MachineBasicBlock *PredBB,
                                                  MachineBasicBlock *LoopBB) {
  if (!AllowBBPeelPullUp)
    return false;
  if (!LoopBB || !PredBB)
    return false;
 
  // We consider single BB loops only. Check for it here.
  if (LoopBB->isEHPad() || LoopBB->hasAddressTaken())
    return false;
  if (LoopBB->succ_size() != 2)
    return false;
  if (LoopBB->pred_size() != 2)
    return false;
  // Make sure one of the successors and one of the predecssors is to self.
  if (!(LoopBB->isSuccessor(LoopBB) && LoopBB->isPredecessor(LoopBB)))
    return false;
 
  // Find the none self successor block. We know we only have 2 successors.
  MachineBasicBlock *SuccBB = NULL;
  for (MachineBasicBlock::succ_iterator SI = LoopBB->succ_begin(),
                                        SE = LoopBB->succ_end();
       SI != SE; ++SI)
    if (*SI != LoopBB) {
      SuccBB = *SI;
      break;
    }
  if (!SuccBB)
    return false;
 
  // Find the conditional branch and its bundle inside PredBB.
  MachineBasicBlock::iterator PredBundle;
  MachineInstr *PredCondBranch = NULL;
  PredCondBranch = findBundleAndBranch(PredBB, PredBundle);
  if (!PredCondBranch)
    return false;
  if (PredBundle == PredBB->end())
    return false;
  LLVM_DEBUG(dbgs() << "PredBB's Branch: ");
  LLVM_DEBUG(dbgs() << *PredCondBranch);
 
  // Look for leading reg copy as single bundle and make sure its live in.
  MachineBasicBlock::instr_iterator FMI = LoopBB->instr_begin();
  // Skip debug instructions.
  while (FMI->isDebugInstr())
    FMI++;
 
  MachineInstr *RegMI = &*FMI;
  if (RegMI->isBundle())
    return false;
  int TfrOpcode = RegMI->getOpcode();
  if (TfrOpcode != Hexagon::A2_tfr && TfrOpcode != Hexagon::A2_tfr)
    return false;
  if (!(RegMI->getOperand(0).isReg() && RegMI->getOperand(1).isReg()))
    return false;
  unsigned InLoopReg = RegMI->getOperand(1).getReg();
  if (!LoopBB->isLiveIn(InLoopReg))
    return false;
 
  // Create a region to pass to ResourcesAvailableInBundle.
  BasicBlockRegion PUR(BasicBlockRegion(TII, QRI, PredBB));
  PUR.addBBtoRegion(LoopBB);
  PUR.addBBtoRegion(SuccBB);
 
  // Make sure we have space in PredBB's last bundle.
  if (!ResourcesAvailableInBundle(&PUR, PredBundle))
    return false;
  SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> PredBundlePkt(
      CurrentState.HomeBundle);
 
  // Find condition to use for predicating the reg copy into PredBB.
  MachineBasicBlock *TBB = NULL, *FBB = NULL;
  SmallVector<MachineOperand, 4> Cond;
  if (QII->analyzeBranch(*PredBB, TBB, FBB, Cond, false))
    return false;
  if (Cond.empty())
    return false;
 
  // Find condition to use for predicating the reg copy at the end of LoopBB.
  MachineBasicBlock *LTBB = NULL, *LFBB = NULL;
  SmallVector<MachineOperand, 4> LCond;
  if (QII->analyzeBranch(*LoopBB, LTBB, LFBB, LCond, false))
    return false;
  if (LCond.empty())
    return false;
 
  // Move predicated reg copy to previous BB's last bundle.
  if (!TII->isPredicable(*RegMI))
    return false;
  MachineInstr *InstrToMove =
      &*insertTempCopy(PredBB, PredBundle, RegMI, false);
  if (!canAddMIToThisPacket(InstrToMove, PredBundlePkt)) {
    PredBB->erase_instr(InstrToMove);
    return false;
  }
 
  if (!TII->PredicateInstruction(*InstrToMove, Cond)) {
    // Failed to predicate the copy reg.
    PredBB->erase_instr(InstrToMove);
    return false;
  }
 
  // Can we newify this instruction?
  unsigned DepReg = 0;
  if (NeedToNewify(InstrToMove->getIterator(), &DepReg, &*PredBundle) &&
      !isNewifiable(InstrToMove->getIterator(), DepReg, &*PredBundle)) {
    PredBB->erase_instr(InstrToMove);
    return false;
  }
  // Newify it, and then undo it if we determine we are using a .old.
  int NewOpcode = QII->getDotNewPredOp(*InstrToMove, MBPI);
  // Undo newify if we have a non .new predicated jump we are matching.
  if (!QII->isDotNewInst(*PredCondBranch))
    NewOpcode = QII->getDotOldOp(*InstrToMove);
  NewOpcode = QII->getInvertedPredicatedOpcode(NewOpcode);
  // Properly set the opcode on the new hoisted reg copy instruction.
  InstrToMove->setDesc(QII->get(NewOpcode));
  if (!incrementalAddToPacket(*InstrToMove)) {
    PredBB->erase_instr(InstrToMove);
    return false;
  }
 
  // Find the conditional branch and its bundle for LoopBB.
  MachineBasicBlock::iterator LoopBundle;
  MachineInstr *LoopCondBranch = NULL;
  LoopCondBranch = findBundleAndBranch(LoopBB, LoopBundle);
  if (!LoopCondBranch)
    return false;
  if (LoopBundle == LoopBB->end())
    return false;
  LLVM_DEBUG(dbgs() << "LoopBB's Branch: ");
  LLVM_DEBUG(dbgs() << *LoopCondBranch);
 
  // Make sure we have space in LoopBB's last bundle.
  if (!ResourcesAvailableInBundle(&PUR, LoopBundle))
    return false;
  SmallVector<MachineInstr *, HEXAGON_PACKET_SIZE> LoopBundlePkt(
      CurrentState.HomeBundle);
 
  // Move predicated reg copy to last bundle of LoopBB.
  MachineInstr *InstrToSink =
      &*insertTempCopy(LoopBB, LoopBundle, RegMI, false);
  if (!canAddMIToThisPacket(InstrToSink, LoopBundlePkt)) {
    // Get rid of previous instruction as well.
    PredBB->erase_instr(InstrToMove);
    LoopBB->erase_instr(InstrToSink);
    return false;
  }
 
  if (!TII->PredicateInstruction(*InstrToSink, LCond)) {
    // Get rid of previous instruction as well.
    PredBB->erase_instr(InstrToMove);
    LoopBB->erase_instr(InstrToSink);
    return false;
  }
  // Can we newify this instruction?
  if (NeedToNewify(InstrToSink->getIterator(), &DepReg, &*LoopBundle) &&
      !isNewifiable(InstrToSink->getIterator(), DepReg, &*LoopBundle)) {
    // Get rid of previous instruction as well.
    PredBB->erase_instr(InstrToMove);
    PredBB->erase_instr(InstrToSink);
    return false;
  }
  NewOpcode = QII->getDotNewPredOp(*InstrToSink, MBPI);
  // Undo newify if we have a non .new predicated jump we are matching.
  if (!QII->isDotNewInst(*LoopCondBranch))
    NewOpcode = QII->getDotOldOp(*InstrToSink);
  InstrToSink->setDesc(QII->get(NewOpcode));
  if (!incrementalAddToPacket(*InstrToSink)) {
    // Get rid of previous instruction as well.
    PredBB->erase_instr(InstrToMove);
    LoopBB->erase_instr(InstrToSink);
    return false;
  }
 
  // Remove old instruction.
  LoopBB->erase_instr(RegMI);
  // Set loop alignment to 32.
  LoopBB->setAlignment(llvm::Align(32));
 
  LLVM_DEBUG(dbgs() << "Peeled Single BBLoop copy\n");
  LLVM_DEBUG(dbgs() << *InstrToMove);
  LLVM_DEBUG(dbgs() << *InstrToSink);
  LLVM_DEBUG(dbgs() << *PredBB);
  LLVM_DEBUG(dbgs() << *LoopBB);
  LLVM_DEBUG(dbgs() << *SuccBB);
  LLVM_DEBUG(dbgs() << "--- BBLoop ---\n\n");
  return true;
}
 
bool HexagonGlobalSchedulerImpl::performPullUpCFG(MachineFunction &Fn) {
  const Function &F = Fn.getFunction();
  // Check for single-block functions and skip them.
  if (std::next(F.begin()) == F.end())
    return false;
  bool Changed = false;
  LLVM_DEBUG(dbgs() << "****** PullUpCFG **************\n");
 
  // Loop over all basic blocks, asking if 3 consecutive blocks are
  // the jump opportunity.
  MachineBasicBlock *PrevBlock = NULL;
  MachineBasicBlock *JumpBlock = NULL;
  for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
       ++MBB) {
    MachineBasicBlock *FallBlock = &*MBB;
    if (PrevBlock && JumpBlock) {
      Changed |= pullUpPeelBBLoop(PrevBlock, JumpBlock);
    }
    PrevBlock = JumpBlock;
    JumpBlock = FallBlock;
  }
  return Changed;
}
 
void HexagonGlobalSchedulerImpl::GenUseDefChain(MachineFunction &Fn) {
  std::vector<unsigned> Defs;
  std::vector<unsigned> Uses;
  for (MachineFunction::iterator MBBIter = Fn.begin(); MBBIter != Fn.end();
       ++MBBIter) {
    for (MachineBasicBlock::instr_iterator MIter = MBBIter->instr_begin();
         MIter != MBBIter->instr_end(); ++MIter) {
      if (MIter->isBundle() || MIter->isDebugInstr())
        continue;
      LLVM_DEBUG(dbgs() << "\n\nInserted Ins:"; MIter->dump());
      MIUseDefSet(&*MIter, Defs, Uses);
      LLVM_DEBUG(dbgs() << "\n\tDefs:";
                 for (unsigned i = 0; i < Defs.size(); ++i) dbgs()
                 << printReg(Defs[i], QRI) << ",");
      LLVM_DEBUG(dbgs() << "\n\tUses:";
                 for (unsigned i = 0; i < Uses.size(); ++i) dbgs()
                 << printReg(Uses[i], QRI) << ",");
      MIDefSet[&*MIter] = Defs;
      MIUseSet[&*MIter] = Uses;
    }
  }
}
 
// optimizeBranching -
// 1. A conditional-jump transfers control to a BB with
// jump as the only instruction.
// if(p0) jump t1
// // ...
// t1: jump t2
// 2. When a BB with a single conditional jump, jumps to succ-of-succ and
// falls-through BB with only jump instruction.
// { if(p0) jump t1 }
// { jump t2 }
// t1: { ... }
MachineBasicBlock *HexagonGlobalSchedulerImpl::optimizeBranches(
    MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
    MachineBasicBlock *FBB) {
  LLVM_DEBUG(dbgs() << "\n\t\t[optimizeBranching]\n");
  if ((TBB == MBB) || (FBB == MBB))
    LLVM_DEBUG(dbgs() << "Cannot deal with loops in BB#" << MBB->getNumber(););
 
  // LLVM_DEBUG(dbgs() << "\n\t\tTBBMIb:"; MII->dump(););
  // { if(p) jump t1; }
  // t1: { jump t2; }
  // --> { if(p) jump t2
  // remove t1: { jump t2; }, if it's address is not taken/not a landing pad.
  if (QII->nonDbgBBSize(TBB) == 1) {
    MachineInstr *TBBMIb = &*TBB->getFirstNonDebugInstr();
    if (TBBMIb->getOpcode() == Hexagon::J2_jump &&
        TBBMIb->getOperand(0).isMBB()) {
      MachineBasicBlock *NewTarget = TBBMIb->getOperand(0).getMBB();
      if (TBB == NewTarget) // Infinite loop.
        return NULL;
 
      LLVM_DEBUG(dbgs() << "\nSuboptimal branching in TBB");
      // Check if the jump in the last instruction is within range.
      int64_t InstOffset =
          BlockToInstOffset.find(MBB)->second + QII->nonDbgBBSize(MBB) * 4;
      unsigned Distance = (unsigned)std::abs(
          InstOffset - BlockToInstOffset.find(NewTarget)->second);
      if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
        LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
                          << " out of range.");
        return NULL;
      }
      // We need to make sure that the TBB is _not_ also a target for another
      // branch. This is suboptimal since theoretically we can update both
      // branches.
      if (!TBB->hasAddressTaken() && !TBB->isEHPad() && TBB->pred_size() == 1) {
        updatePredecessors(*TBB, NewTarget);
        // TBB has only one successor since only one J2_jump instr.
        TBB->removeSuccessor(TBB->succ_begin());
        TBBMIb->removeFromParent();
        if (!TBB->empty()) {
          // There are only debug instructions in TBB now. Move them to
          // the beginning of NewTarget.
          NewTarget->splice(NewTarget->getFirstNonPHI(), TBB, TBB->begin(),
                            TBB->end());
        }
        return TBB;
      } else {
        MBB->ReplaceUsesOfBlockWith(TBB, NewTarget);
        return NULL;
      }
    }
  }
  // { if(p) jump t1; } may contain more instructions
  // { jump t2; } --only one instruction
  // t1: {...}
  // TBB is layout successor of FBB, then we can change the branch target
  // for conditional jump and invert the predicate to remove jump t2.
  // { if(!p) jump t2; }
  // t1: {...}
  if (QII->nonDbgBBSize(FBB) == 1) {
    MachineInstr *FBBMIb = &*FBB->getFirstNonDebugInstr();
    if (FBBMIb->getOpcode() == Hexagon::J2_jump &&
        FBBMIb->getOperand(0).isMBB()) {
      MachineBasicBlock *NewTarget = FBBMIb->getOperand(0).getMBB();
      if (FBB->hasAddressTaken() || FBB->isEHPad() ||
          !FBB->isLayoutSuccessor(TBB) || (FBB == NewTarget /*Infinite loop*/))
        return NULL;
 
      LLVM_DEBUG(dbgs() << "\nSuboptimal branching in FBB");
      // Check if the jump in the last instruction is within range.
      int64_t InstOffset =
          BlockToInstOffset.find(MBB)->second + QII->nonDbgBBSize(MBB) * 4;
      unsigned Distance = (unsigned)std::abs(
          InstOffset - BlockToInstOffset.find(NewTarget)->second);
      if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
        LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
                          << " out of range.");
        return NULL;
      }
      if (!QII->invertAndChangeJumpTarget(*FirstTerm, NewTarget))
        return NULL;
      LLVM_DEBUG(dbgs() << "\nNew instruction:"; FirstTerm->dump(););
      updatePredecessors(*FBB, NewTarget);
      // Only one successor remains for FBB
      FBB->removeSuccessor(FBB->succ_begin());
      FBBMIb->removeFromParent();
      return FBB;
    }
  }
  return NULL;
}
 
// performExposedOptimizations -
// look for optimization opportunities after pullup.
// e.g. jump to adjacent targets
bool HexagonGlobalSchedulerImpl::performExposedOptimizations(
    MachineFunction &Fn) {
  // Check for single-block functions and skip them.
  if (std::next(Fn.getFunction().begin()) == Fn.getFunction().end())
    return true;
  LLVM_DEBUG(dbgs() << "\n\t\t[performExposedOptimizations]\n");
  // Erasing the empty basic blocks formed during pullup.
  std::vector<MachineBasicBlock *>::iterator ebb = EmptyBBs.begin();
  while (ebb != EmptyBBs.end()) {
    assert(IsEmptyBlock(*ebb) && "Pullup inserted packets into an empty BB");
    LLVM_DEBUG(dbgs() << "Removing BB(" << (*ebb)->getNumber()
                      << ") from parent.\n");
    (*ebb)->eraseFromParent();
    ++ebb;
  }
  MachineBasicBlock *TBB = NULL, *FBB = NULL;
  MachineInstr *FirstTerm = NULL, *SecondTerm = NULL;
 
  SmallVector<MachineBasicBlock *, 4> Erase;
 
  for (MachineBasicBlock &MBB : Fn) {
    if (MBB.succ_size() > 2 ||
        AnalyzeBBBranches(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
      LLVM_DEBUG(dbgs() << "\nAnalyzeBBBranches failed in BB#"
                        << MBB.getNumber() << "\n";);
      continue;
    }
    if (FirstTerm && QII->isCompoundBranchInstr(*FirstTerm))
      continue;
    if (TBB && FirstTerm &&
        removeRedundantBranches(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
      LLVM_DEBUG(dbgs() << "\nRemoved redundant branches in BB#"
                        << MBB.getNumber(););
      continue;
    }
    if (FirstTerm && SecondTerm &&
        optimizeDualJumps(&MBB, TBB, FirstTerm, FBB, SecondTerm)) {
      LLVM_DEBUG(dbgs() << "\nRemoved dual jumps in in BB#"
                        << MBB.getNumber(););
      continue;
    }
    if (TBB && FBB && FirstTerm && !SecondTerm) {
      MachineBasicBlock *MBBToErase =
          optimizeBranches(&MBB, TBB, FirstTerm, FBB);
      if (MBBToErase) {
        assert(IsEmptyBlock(MBBToErase) && "Erasing non-empty BB");
        Erase.push_back(MBBToErase);
        LLVM_DEBUG(dbgs() << "\nOptimized jump from BB#" << MBB.getNumber());
      }
    }
  }
  for (MachineBasicBlock *MBB : Erase)
    MBB->eraseFromParent();
 
  return false;
}
 
// 1. Remove jump to the layout successor.
// 2. Remove multiple (dual) jump to the same target.
bool HexagonGlobalSchedulerImpl::removeRedundantBranches(
    MachineBasicBlock *MBB, MachineBasicBlock *TBB, MachineInstr *FirstTerm,
    MachineBasicBlock *FBB, MachineInstr *SecondTerm) {
  bool Analyzed = false;
  LLVM_DEBUG(dbgs() << "\n\t\t[removeRedundantBranches]\n");
  MachineInstr *Head = NULL, *ToErase = NULL;
  if (!FBB && (FirstTerm->getOpcode() == Hexagon::J2_jump) &&
      MBB->isLayoutSuccessor(TBB)) {
    // Jmp layout_succ_basic_block <-- Remove
    LLVM_DEBUG(
        dbgs() << "\nRemoving Uncond. jump to the layout successor in BB#"
               << MBB->getNumber());
    ToErase = FirstTerm;
  } else if (SecondTerm && (TBB == FBB) &&
             (SecondTerm->getOpcode() == Hexagon::J2_jump)) {
    // If both branching instructions in same packet or are consecutive.
    // Jmp_c t1 <-- Remove
    // Jmp t1
    // @Note: If they are in different packets or if they are separated
    // by packet(s), this opt. cannot be done.
    MachineBasicBlock::instr_iterator FirstTermIter = FirstTerm->getIterator();
    MachineBasicBlock::instr_iterator SecondTermIter =
        SecondTerm->getIterator();
    if (++FirstTermIter == SecondTermIter) {
      LLVM_DEBUG(dbgs() << "\nRemoving multiple branching to same target in BB#"
                        << MBB->getNumber());
      // TODO: This might make the `p' register assignment instruction dead.
      // and can be removed.
      ToErase = FirstTerm;
    }
  } else if (SecondTerm && (SecondTerm->getOpcode() == Hexagon::J2_jump) &&
             FBB && MBB->isLayoutSuccessor(FBB)) {
    // Jmp_c t1
    // Jmp layout_succ_basic_block <-- Remove
    LLVM_DEBUG(dbgs() << "\nRemoving fall through branch in BB#"
                      << MBB->getNumber());
    ToErase = SecondTerm;
  } else if (SecondTerm && QII->PredOpcodeHasJMP_c(SecondTerm->getOpcode()) &&
             MBB->isLayoutSuccessor(getBranchDestination(SecondTerm))) {
    // Jmp_c t1
    // Jmp_c layout_succ_basic_block <-- Remove
    // In this case AnalyzeBBBranches might assign FBB to some other BB.
    // So using the jump target of SecondTerm to check.
    LLVM_DEBUG(dbgs() << "\nRemoving Cond. jump to the layout successor in BB#"
                      << MBB->getNumber());
    ToErase = SecondTerm;
  }
  // Remove the instruction from the BB
  if (ToErase) {
    if (ToErase->isBundled()) {
      Head = &*getBundleStart(ToErase->getIterator());
      ToErase->eraseFromBundle();
      UpdateBundle(Head);
    } else
      ToErase->eraseFromParent();
    Analyzed = true;
  }
  return Analyzed;
}
 
// ----- convert
// p = <expr>
// if(p) jump layout_succ_basic_block
// jump t
// ----- to
// p = <expr>
// if(!p) jump t
// for now only looking at the dual jump
bool HexagonGlobalSchedulerImpl::optimizeDualJumps(MachineBasicBlock *MBB,
                                                   MachineBasicBlock *TBB,
                                                   MachineInstr *FirstTerm,
                                                   MachineBasicBlock *FBB,
                                                   MachineInstr *SecondTerm) {
  LLVM_DEBUG(dbgs() << "\n******* optimizeDualJumps *******");
 
  bool Analyzed = false;
 
  if (QII->PredOpcodeHasJMP_c(FirstTerm->getOpcode()) &&
      (SecondTerm->getOpcode() == Hexagon::J2_jump)) {
 
    if (TBB == FBB) {
      LLVM_DEBUG(dbgs() << "\nBoth successors are the same.");
      return Analyzed;
    }
 
    // Do not optimize for dual jumps if this MBB
    // contains a speculatively pulled-up instruction.
    // A speculated instruction is more likely to be at the end of MBB.
    MachineBasicBlock::reverse_instr_iterator SII = MBB->instr_rbegin();
    while (SII != MBB->instr_rend()) {
      MachineInstr *SI = &*SII;
      std::map<MachineInstr *, MachineBasicBlock *>::iterator MIMoved;
      MIMoved = SpeculatedIns.find(SI);
      if ((MIMoved != SpeculatedIns.end()) &&
          (MIMoved->second != SI->getParent())) {
        return Analyzed;
      }
      ++SII;
    }
 
    LLVM_DEBUG(dbgs() << "\nCandidate for jump optimization in BB("
                      << MBB->getNumber() << ").\n";);
 
    // Predicated jump to layout successor followed by an unconditional jump.
    if (MBB->isLayoutSuccessor(TBB)) {
 
      // Check if the jump in the last instruction is within range.
      int64_t InstOffset =
          BlockToInstOffset.find(&*MBB)->second + QII->nonDbgBBSize(MBB) * 4;
      unsigned Distance =
          (unsigned)std::abs(InstOffset - BlockToInstOffset.find(FBB)->second) +
          SafetyBuffer;
      if (!QII->isJumpWithinBranchRange(*FirstTerm, Distance)) {
        LLVM_DEBUG(dbgs() << "\nUnconditional jump target:" << Distance
                          << " out of range.");
        return Analyzed;
      }
 
      // modify the second last -predicated- instruction (sense and target)
      LLVM_DEBUG(dbgs() << "\nFirst Instr:" << *FirstTerm;);
      LLVM_DEBUG(dbgs() << "\nSecond Instr:" << *SecondTerm;);
      LLVM_DEBUG(dbgs() << "\nOld Succ BB(" << TBB->getNumber() << ").";);
 
      QII->invertAndChangeJumpTarget(*FirstTerm, FBB);
 
      LLVM_DEBUG(dbgs() << "\nNew First Instruction:" << *FirstTerm;);
 
      // unbundle if there is only one instruction left
      MachineInstr *SecondHead, *FirstHead;
      FirstHead = FirstTerm->isBundled()
                      ? &*getBundleStart(FirstTerm->getIterator())
                      : nullptr;
      SecondHead = SecondTerm->isBundled()
                       ? &*getBundleStart(SecondTerm->getIterator())
                       : nullptr;
 
      // 1. Both unbundled, 2. FirstTerm inside bundle, second outside.
      if (!SecondHead)
        SecondTerm->eraseFromParent();
      else if (!FirstHead) {
        // 3. FirstHead outside, SecondHead inside.
        SecondTerm->eraseFromBundle();
        UpdateBundle(SecondHead);
      } else if (FirstHead == SecondHead) {
        // 4. Both are in the same bundle
        assert((FirstHead && SecondHead) && "Unbundled Instruction");
        SecondTerm->eraseFromBundle();
        if (SecondHead->getBundleSize() < 2)
          UpdateBundle(SecondHead);
      } else {
        // 5. Both are in different bundles
        SecondTerm->eraseFromBundle();
        UpdateBundle(SecondHead);
      }
      Analyzed = true;
    }
  }
  return Analyzed;
}
 
/// Are there any resources left in this bundle?
bool HexagonGlobalSchedulerImpl::ResourcesAvailableInBundle(
    BasicBlockRegion *CurrentRegion,
    MachineBasicBlock::iterator &TargetPacket) {
  MachineBasicBlock::instr_iterator MII = TargetPacket.getInstrIterator();
 
  // If this is a single instruction, form new packet around it.
  if (!TargetPacket->isBundle()) {
    if (ignoreInstruction(&*MII) || isSoloInstruction(*MII))
      return false;
 
    // Before we begin, we need to make sure that we do not
    // look at an unconditional jump outside the current region.
    if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, &*MII))
      return false;
 
    // Build up state for this new packet.
    // Note, we cannot create a bundle header for it,
    // so this "bundle" only exist in DFA state, and not in code.
    initPacketizerState();
    ResourceTracker->clearResources();
    CurrentState.addHomeLocation(MII);
    return incrementalAddToPacket(*MII);
  }
 
  MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
 
  // Build up state for this packet.
  initPacketizerState();
  ResourceTracker->clearResources();
  CurrentState.addHomeLocation(MII);
 
  for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
    if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
        MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
        MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION || MII->isEHLabel())
      continue;
 
    // Before we begin, we need to make sure that we do not
    // look at an unconditional jump outside the current region.
    // TODO: See if we can profit from handling this kind of cases:
    // B#15: derived from LLVM BB %if.then22
    // Predecessors according to CFG: BB#13
    // BUNDLE %PC<imp-def>, %P2<imp-use,kill>
    //   * J2_jumpf %P2<kill,internal>, <BB#17>, %PC<imp-def>; flags:
    //   * J2_jump <BB#18>, %PC<imp-def>; flags:
    // Successors according to CFG: BB#18(62) BB#17(62)
    // Curently we do not allow them.
    if (MII->isBranch() && !isBranchWithinRegion(CurrentRegion, &*MII))
      return false;
 
    if (!incrementalAddToPacket(*MII))
      return false;
  }
  return ResourceTracker->canReserveResources(*Nop);
}
 
/// Symmetrical. See if these two instructions are fit for compound pair.
bool HexagonGlobalSchedulerImpl::isCompoundPair(MachineInstr *MIa,
                                                MachineInstr *MIb) {
  enum HexagonII::CompoundGroup MIaG = QII->getCompoundCandidateGroup(*MIa),
                                MIbG = QII->getCompoundCandidateGroup(*MIb);
  // We have two candidates - check that this is the same register
  // we are talking about.
  unsigned Opcb = MIb->getOpcode();
  if (MIaG == HexagonII::HCG_C && MIbG == HexagonII::HCG_A &&
      (Opcb == Hexagon::A2_tfr || Opcb == Hexagon::A2_tfrsi))
    return true;
  unsigned Opca = MIa->getOpcode();
  if (MIbG == HexagonII::HCG_C && MIaG == HexagonII::HCG_A &&
      (Opca == Hexagon::A2_tfr || Opca == Hexagon::A2_tfrsi))
    return true;
  return (((MIaG == HexagonII::HCG_A && MIbG == HexagonII::HCG_B) ||
           (MIbG == HexagonII::HCG_A && MIaG == HexagonII::HCG_B)) &&
          (MIa->getOperand(0).getReg() == MIb->getOperand(0).getReg()));
}
 
// This is a weird situation when BB conditionally branches + falls through
// to layout successor. \ref bug17792
inline bool HexagonGlobalSchedulerImpl::multipleBranchesFromToBB(
    MachineBasicBlock *BB) const {
  if (BB->succ_size() != 1)
    return false;
  SmallVector<MachineInstr *, 2> Jumpers = QII->getBranchingInstrs(*BB);
  return ((Jumpers.size() == 1) && !Jumpers[0]->isUnconditionalBranch());
}
 
/// Gather a worklist of MaxCandidates pull-up candidates.
/// Compute relative cost.
bool HexagonGlobalSchedulerImpl::findPullUpCandidates(
    MachineBasicBlock::iterator &WorkPoint,
    MachineBasicBlock::iterator &FromHere,
    std::vector<MachineInstr *> &backtrack, unsigned MaxCandidates = 1) {
 
  const HexagonInstrInfo *QII = (const HexagonInstrInfo *)TII;
  MachineBasicBlock *FromThisBB = FromHere->getParent();
  bool MovingDependentOp = false;
  signed CostBenefit = 0;
 
  // Do not collect more than that many candidates.
  if (CurrentState.haveCandidates() >= MaxCandidates)
    return false;
 
  LLVM_DEBUG(dbgs() << "\n\tTry from BB(" << FromThisBB->getNumber() << "):\n";
             DumpPacket(FromHere.getInstrIterator()));
 
  if (FromHere->isBundle()) {
    MachineBasicBlock::instr_iterator MII = FromHere.getInstrIterator();
    for (++MII; MII != FromThisBB->instr_end() && MII->isInsideBundle();
         ++MII) {
      if (MII->isDebugInstr())
        continue;
      LLVM_DEBUG(dbgs() << "\tCandidate from BB("
                        << MII->getParent()->getNumber() << "): ";
                 MII->dump());
 
      // See if this instruction could be moved.
      if (!canThisMIBeMoved(&*MII, WorkPoint, MovingDependentOp, CostBenefit))
        continue;
 
      MachineBasicBlock::instr_iterator InstrToMove = MII;
      if (canAddMIToThisPacket(&*InstrToMove, CurrentState.HomeBundle)) {
        CostBenefit -= (backtrack.size() * 4);
        // Prefer instructions in empty packets.
        CostBenefit += (PacketSize - nonDbgBundleSize(FromHere)) * 2;
        // Prefer Compares.
        if (MII->isCompare())
          CostBenefit += 10;
        // Check duplex conditions;
        for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
          if (QII->isDuplexPair(*CurrentState.HomeBundle[i], *MII)) {
            LLVM_DEBUG(dbgs() << "\tGot real Duplex (bundle).\n");
            CostBenefit += 20;
          }
          if (isCompoundPair(CurrentState.HomeBundle[i], &*MII)) {
            LLVM_DEBUG(dbgs() << "\tGot compound (bundle).\n");
            CostBenefit += 40;
          }
        }
        // Create a record for this location.
        CurrentState.addPullUpCandidate(InstrToMove, WorkPoint, backtrack,
                                        MovingDependentOp, CostBenefit);
      } else
        LLVM_DEBUG(dbgs() << "\tNo resources in the target packet.\n");
    }
  }
  // This is a standalone instruction.
  // First see if this MI can even be moved. Cost model for a single instruction
  // should be rather different from moving something out of a bundle.
  else if (canThisMIBeMoved(&*FromHere, WorkPoint, MovingDependentOp,
                            CostBenefit)) {
    MachineBasicBlock::instr_iterator InstrToMove = FromHere.getInstrIterator();
    if (canAddMIToThisPacket(&*InstrToMove, CurrentState.HomeBundle)) {
      CostBenefit -= (backtrack.size() * 4);
      // Prefer Compares.
      if (InstrToMove->isCompare())
        CostBenefit += 10;
      // It is better to pull a single instruction in to a bundle - save
      // a cycle immediately.
      CostBenefit += 10;
      // Search for duplex match.
      for (unsigned i = 0; i < CurrentState.HomeBundle.size(); i++) {
        if (QII->isDuplexPair(*CurrentState.HomeBundle[i], *InstrToMove)) {
          LLVM_DEBUG(dbgs() << "\tGot real Duplex (single).\n");
          CostBenefit += 30;
        }
        if (isCompoundPair(CurrentState.HomeBundle[i], &*InstrToMove)) {
          LLVM_DEBUG(dbgs() << "\tGot compound (single).\n");
          CostBenefit += 50;
        }
      }
      // Create a record for this location.
      CurrentState.addPullUpCandidate(InstrToMove, WorkPoint, backtrack,
                                      MovingDependentOp, CostBenefit);
    } else
      LLVM_DEBUG(dbgs() << "\tNo resources for single in the target packet.\n");
  }
  return true;
}
 
/// Try to move a candidate MI.
/// The move can destroy all iterator system, so we have to drag them
/// around to keep them up to date.
bool HexagonGlobalSchedulerImpl::tryMultipleInstructions(
    MachineBasicBlock::iterator &RetVal, /* output parameter */
    std::vector<BasicBlockRegion *>::iterator &CurrentRegion,
    MachineBasicBlock::iterator &NextMI,
    MachineBasicBlock::iterator &ToThisBBEnd,
    MachineBasicBlock::iterator &FromThisBBEnd, bool PathInRegion) {
 
  MachineBasicBlock::instr_iterator MII;
  MachineBasicBlock::iterator WorkPoint;
  bool MovingDependentOp = false;
  std::vector<MachineInstr *> backtrack;
 
  LLVM_DEBUG(dbgs() << "\n\tTry Multiple candidates: \n");
 
  std::sort(CurrentState.PullUpCandidates.begin(),
            CurrentState.PullUpCandidates.end(), PullUpCandidateSorter());
  LLVM_DEBUG(CurrentState.dump());
  // Iterate through candidates in sorted order.
  for (SmallVector<PullUpCandidate *, 4>::iterator
           I = CurrentState.PullUpCandidates.begin(),
           E = CurrentState.PullUpCandidates.end();
       I != E; ++I) {
    (*I)->populate(MII, WorkPoint, backtrack, MovingDependentOp);
 
    MachineBasicBlock *FromThisBB = MII->getParent();
    MachineBasicBlock *ToThisBB = WorkPoint->getParent();
 
    LLVM_DEBUG(dbgs() << "\n\tCandidate: "; MII->dump());
    LLVM_DEBUG(dbgs() << "\tDependent(" << MovingDependentOp << ") FromBB("
                      << FromThisBB->getNumber() << ") ToBB("
                      << ToThisBB->getNumber() << ") to this packet:\n";
               DumpPacket(WorkPoint.getInstrIterator()));
 
    MachineBasicBlock::instr_iterator FromHereII = MII;
    if (MII->isInsideBundle()) {
      while (!FromHereII->isBundle())
        --FromHereII;
      LLVM_DEBUG(dbgs() << "\tFrom here:\n"; DumpPacket(FromHereII));
 
      MachineBasicBlock::iterator FromHere(FromHereII);
      // We have instruction that could be moved from its current position.
      if (MoveMItoBundle(*CurrentRegion, MII, NextMI, WorkPoint, FromHere,
                         backtrack, MovingDependentOp, PathInRegion)) {
        // If BB from which we pull is now empty, move on.
        if (IsEmptyBlock(FromThisBB)) {
          LLVM_DEBUG(dbgs() << "\n\tExhosted BB (bundle).\n");
          return false;
        }
        FromThisBBEnd = FromThisBB->end();
        ToThisBBEnd = ToThisBB->end();
 
        LLVM_DEBUG(dbgs() << "\n\tAfter updates(bundle to bundle):\n");
        LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
                   DumpPacket(WorkPoint.getInstrIterator()));
 
        // We should not increment current position,
        // but rather try one more time to pull from the same bundle.
        RetVal = WorkPoint;
        return true;
      } else
        LLVM_DEBUG(dbgs() << "\tCould not move packetized instr.\n");
    } else {
      MachineBasicBlock::iterator FromHere(FromHereII);
      if (MoveMItoBundle(*CurrentRegion, MII, NextMI, WorkPoint, FromHere,
                         backtrack, MovingDependentOp, PathInRegion)) {
 
        // If BB from which we pull is now empty, move on.
        if (IsEmptyBlock(FromThisBB)) {
          LLVM_DEBUG(dbgs() << "\n\tExhosted BB (single).\n");
          return false;
        }
        FromThisBBEnd = FromThisBB->end();
        ToThisBBEnd = ToThisBB->end();
 
        LLVM_DEBUG(dbgs() << "\tAfter updates (single to bundle):\n");
        LLVM_DEBUG(dbgs() << "\t\tWorkPoint: ";
                   DumpPacket(WorkPoint.getInstrIterator()));
        // We should not increment current position,
        // but rather try one more time to pull from the same bundle.
        RetVal = WorkPoint;
        return true;
      } else
        LLVM_DEBUG(dbgs() << "\tCould not move single.\n");
    }
  }
  LLVM_DEBUG(dbgs() << "\tNot a single candidate fit.\n");
  return false;
}
 
/// Main function. Iterate all current regions one at a time,
/// and look for pull-up opportunities.
/// Pseudo sequence:
/// - for all bundles and single instructions in region:
/// - see if resources are available (in the same cycle) - this is HOME.
/// - Starting from next BB in region, find an instruction that could be:
///   - removed from its current location
///   - added to underutilized bundle (including bundles with only one op)
/// - If so, trace path back to HOME and check that candidate could be
///   reordered with all the intermediate instructions.
bool HexagonGlobalSchedulerImpl::performPullUp() {
  std::vector<MachineInstr *> backtrack;
  MachineBasicBlock::iterator FromHere;
  MachineBasicBlock::iterator FromThisBBEnd;
 
  LLVM_DEBUG(dbgs() << "****** PullUpRegions ***********\n");
  // For all regions...
  for (std::vector<BasicBlockRegion *>::iterator
           CurrentRegion = PullUpRegions.begin(),
           E = PullUpRegions.end();
       CurrentRegion != E; ++CurrentRegion) {
 
    LLVM_DEBUG(dbgs() << "\n\nRegion with(" << (*CurrentRegion)->size()
                      << ")BBs\n");
 
    if (!EnableLocalPullUp && (*CurrentRegion)->size() < 2)
      continue;
 
    // For all MBB in the region... except the last one.
    // ...except when we want to allow local pull-up.
    for (auto ToThisBB = (*CurrentRegion)->getRootMBB(),
              LastBBInRegion = (*CurrentRegion)->getLastMBB();
         ToThisBB != LastBBInRegion; ++ToThisBB) {
      // If we do not want to allow same BB pull-up, take an early exit.
      if (!EnableLocalPullUp && (std::next(ToThisBB) == LastBBInRegion))
        break;
      if (multipleBranchesFromToBB(*ToThisBB))
        break;
 
      auto FromThisBB = ToThisBB;
      MachineBasicBlock::iterator ToThisBBEnd = (*ToThisBB)->end();
      MachineBasicBlock::iterator MI = (*ToThisBB)->begin();
 
      LLVM_DEBUG(dbgs() << "\n\tHome iterator moved to new BB("
                        << (*ToThisBB)->getNumber() << ")\n";
                 (*ToThisBB)->dump());
 
      // For all instructions in the BB.
      while (MI != ToThisBBEnd) {
        MachineBasicBlock::iterator WorkPoint = MI;
        ++MI;
 
        // Trivial check that there are unused resources
        // in the current location (cycle).
        while (ResourcesAvailableInBundle(*CurrentRegion, WorkPoint)) {
          LLVM_DEBUG(dbgs() << "\nxxxx Next Home in BB("
                            << (*ToThisBB)->getNumber() << "):\n";
                     DumpPacket(WorkPoint.getInstrIterator()));
          // Keep the path to the candidate.
          // It is the traveled path between home and work point.
          // Reset it for the new iteration.
          backtrack.clear();
 
          // The point of pull-up source (WorkPoint) could begin from the
          // current BB, but only if we allow pull-up in the same BB.
          // At the moment we do not.
          // We also do not process last block in the region,
          // so it is safe to always begin with the next BB in the region.
          // Start from "next" BB in the region.
          if (EnableLocalPullUp) {
            FromThisBB = ToThisBB;
            FromHere = WorkPoint;
            ++FromHere;
            FromThisBBEnd = (*FromThisBB)->end();
 
            // Initialize backtrack.
            // These are instructions between Home location
            // and the WorkPoint.
            for (MachineBasicBlock::iterator I = WorkPoint, IE = FromHere;
                 I != IE; ++I)
              backtrack.push_back(&*I);
          } else {
            FromThisBB = ToThisBB;
            ++FromThisBB;
            FromHere = (*FromThisBB)->begin();
            FromThisBBEnd = (*FromThisBB)->end();
 
            // Initialize backtrack.
            // These are instructions between Home location
            // and the end of the home BB.
            for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
                 I != IE; ++I)
              backtrack.push_back(&*I);
          }
 
          // Search for pull-up candidate.
          while (true) {
            // If this BB is over, move onto the next one
            // in this region.
            if (FromHere == FromThisBBEnd) {
              ++FromThisBB;
              // Refresh LastBBInRegion in case tryMultipleInstructions modified
              // the regions Elements vector, invalidating the iterator.
              LastBBInRegion = (*CurrentRegion)->getLastMBB();
              if (FromThisBB == LastBBInRegion)
                break;
              else {
                LLVM_DEBUG(dbgs() << "\n\tNext BB in this region\n";
                           (*FromThisBB)->dump());
                FromThisBBEnd = (*FromThisBB)->end();
                FromHere = (*FromThisBB)->begin();
                if (FromThisBBEnd == FromHere)
                  break;
              }
            }
            if ((*FromHere).isDebugInstr()) {
              ++FromHere;
              continue;
            }
            // This is a step Home.
            backtrack.push_back(&*FromHere);
            if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
                                      MainCandidateQueueSize))
              break;
            ++FromHere;
          }
          // Try to pull-up one of the selected candidates.
          if (!tryMultipleInstructions(/*output*/ WorkPoint, CurrentRegion, MI,
                                       ToThisBBEnd, FromThisBBEnd))
            break;
        }
      }
      // Refresh LastBBInRegion after potential CFG modifications.
      LastBBInRegion = (*CurrentRegion)->getLastMBB();
    }
    // AllowUnlikelyPath is on by default,
    // if we wish to disable it, we can do so here.
    if (!AllowUnlikelyPath)
      continue;
 
    // We have parsed the likely path through the region.
    // Now traverse the other (unlikely) path.
    //
    // Note: BasicBlockRegion uses a vector for MBB storage, so adding BBs to
    // the region while iterating could invalidate iterators. Collect the work
    // items first, then process them.
    std::vector<std::pair<MachineBasicBlock *, MachineBasicBlock *>>
        UnlikelyWork;
    UnlikelyWork.reserve((*CurrentRegion)->size());
    for (auto ToIt = (*CurrentRegion)->getRootMBB(),
              End = (*CurrentRegion)->getLastMBB();
         ToIt != End; ++ToIt) {
      MachineBasicBlock *ToBB = *ToIt;
      MachineBasicBlock *SecondBest = getNextPURBB(ToBB, true);
      if (SecondBest)
        UnlikelyWork.emplace_back(ToBB, SecondBest);
    }
 
    for (auto [ToBB, SecondBest] : UnlikelyWork) {
      LLVM_DEBUG(dbgs() << "\tFor BB:\n"; ToBB->dump());
      LLVM_DEBUG(dbgs() << "\tHave SecondBest:\n"; SecondBest->dump());
      // Adding this BB to the region should not be done if we
      // plan to reuse it(the region) again. For now it is OK.
      (*CurrentRegion)->addBBtoRegion(SecondBest);
      LLVM_DEBUG(dbgs() << "\tHome iterator moved to new BB("
                        << ToBB->getNumber() << ")\n";
                 ToBB->dump());
      MachineBasicBlock::iterator ToThisBBEnd = ToBB->end();
      MachineBasicBlock::iterator MI = ToBB->begin();
 
      // For all instructions in the BB.
      while (MI != ToThisBBEnd) {
        MachineBasicBlock::iterator WorkPoint = MI;
        ++MI;
 
        // Trivial check that there are unused resources
        // in the current location (cycle).
        while (ResourcesAvailableInBundle(*CurrentRegion, WorkPoint)) {
          LLVM_DEBUG(dbgs() << "\nxxxx Second visit Home in BB("
                            << ToBB->getNumber() << "):\n";
                     DumpPacket(WorkPoint.getInstrIterator()));
 
          FromHere = SecondBest->begin();
          FromThisBBEnd = SecondBest->end();
 
          // Keep the path to the candidate.
          backtrack.clear();
 
          // This is Home location.
          for (MachineBasicBlock::iterator I = WorkPoint, IE = ToThisBBEnd;
               I != IE; ++I)
            backtrack.push_back(&*I);
 
          while (true) {
            // If this BB is over, move onto the next one
            // in this region.
            if (FromHere == FromThisBBEnd) {
              LLVM_DEBUG(dbgs()
                         << "\tOnly do one successor for the second try\n");
              break;
            }
            if ((*FromHere).isDebugInstr()) {
              ++FromHere;
              continue;
            }
            // This is a step Home.
            backtrack.push_back(&*FromHere);
            if (!findPullUpCandidates(WorkPoint, FromHere, backtrack,
                                      SecondaryCandidateQueueSize))
              break;
            ++FromHere;
          }
          // Try to pull-up one of selected candidate.
          if (!tryMultipleInstructions(/*output*/ WorkPoint, CurrentRegion, MI,
                                       ToThisBBEnd, FromThisBBEnd, false))
            break;
        }
      }
    }
  }
  return true;
}
 
bool HexagonGlobalSchedulerImpl::incrementalAddToPacket(MachineInstr &MI) {
 
  LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
                    << ") adding:\t";
             MI.dump());
 
  if (!ResourceTracker->canReserveResources(MI) || !shouldAddToPacket(MI))
    return false;
 
  ResourceTracker->reserveResources(MI);
  CurrentPacketMIs.push_back(&MI);
  CurrentState.HomeBundle.push_back(&MI);
 
  if (QII->isExtended(MI) || QII->isConstExtended(MI) ||
      isJumpOutOfRange(&MI)) {
    // If at this point of time we cannot reserve resources,
    // this might mean that the packet came into the pull-up
    // pass already in danger of overflowing.
    // Nevertheless, since this is only a possibility of overflow
    // no error should be issued here.
    if (ResourceTracker->canReserveResources(*Ext)) {
      ResourceTracker->reserveResources(*Ext);
      LLVM_DEBUG(dbgs() << "\t[AddToPacket] (" << CurrentPacketMIs.size()
                        << ") adding:\t  immext_i\n");
      CurrentPacketMIs.push_back(Ext);
      CurrentState.HomeBundle.push_back(Ext);
      return true;
    } else {
      LLVM_DEBUG(dbgs() << "\t  Previous overflow possible.\n");
      return false;
    }
  }
  return true;
}
 
void HexagonGlobalSchedulerImpl::checkBundleCounts(MachineFunction &Fn) {
  if (DisableCheckBundles)
    return;
 
  unsigned BundleLimit = 4;
 
  for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
       MBBi != MBBe; ++MBBi) {
 
    for (MachineBasicBlock::iterator MI = MBBi->instr_begin(),
                                     ME = MBBi->instr_end();
         MI != ME; ++MI) {
      if (MI->isBundle()) {
        MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
        MachineBasicBlock::instr_iterator End = MII->getParent()->instr_end();
 
        unsigned InstrCount = 0;
 
        for (++MII; MII != End && MII->isInsideBundle(); ++MII) {
          if (MII->getOpcode() == TargetOpcode::DBG_VALUE ||
              MII->getOpcode() == TargetOpcode::IMPLICIT_DEF ||
              MII->getOpcode() == TargetOpcode::CFI_INSTRUCTION ||
              MII->isEHLabel() || QII->isEndLoopN(MII->getOpcode())) {
            continue;
          } else {
            InstrCount++;
          }
        }
        if (InstrCount > BundleLimit) {
          if (WarnOnBundleSize) {
            LLVM_DEBUG(dbgs() << "Warning bundle size exceeded " << *MI);
          } else {
            assert(0 && "Bundle size exceeded");
          }
        }
      }
    }
  }
}
 
/// Debugging only. Count compound and duplex opportunities.
unsigned HexagonGlobalSchedulerImpl::countCompounds(MachineFunction &Fn) {
  unsigned CompoundCount = 0;
  [[maybe_unused]] unsigned DuplexCount = 0;
  [[maybe_unused]] unsigned InstOffset = 0;
 
  // Loop over all basic blocks.
  for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); MBB != MBBe;
       ++MBB) {
    LLVM_DEBUG(dbgs() << "\n BB#" << MBB->getNumber() << " " << MBB->getName()
                      << " in_func "
                      << MBB->getParent()->getFunction().getName() << " \n");
    for (MachineBasicBlock::iterator MI = MBB->instr_begin(),
                                     ME = MBB->instr_end();
         MI != ME; ++MI) {
      if (MI->isDebugInstr())
        continue;
      if (MI->isBundle()) {
        MachineBasicBlock::instr_iterator MII = MI.getInstrIterator();
        MachineBasicBlock::instr_iterator MIE = MI->getParent()->instr_end();
        MachineInstr *FirstCompound = NULL, *SecondCompound = NULL;
        MachineInstr *FirstDuplex = NULL, *SecondDuplex = NULL;
        LLVM_DEBUG(dbgs() << "{\n");
 
        for (++MII; MII != MIE && MII->isInsideBundle() && !MII->isBundle();
             ++MII) {
          if (MII->isDebugInstr())
            continue;
          LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
          InstOffset += QII->getSize(*MII);
          if (QII->getCompoundCandidateGroup(*MII)) {
            if (!FirstCompound) {
              FirstCompound = &*MII;
              LLVM_DEBUG(dbgs() << "XX ");
            } else {
              SecondCompound = &*MII;
              LLVM_DEBUG(dbgs() << "YY ");
            }
          }
          if (QII->getDuplexCandidateGroup(*MII)) {
            if (!FirstDuplex) {
              FirstDuplex = &*MII;
              LLVM_DEBUG(dbgs() << "AA ");
            } else {
              SecondDuplex = &*MII;
              LLVM_DEBUG(dbgs() << "VV ");
            }
          }
          LLVM_DEBUG(MII->dump());
        }
        LLVM_DEBUG(dbgs() << "}\n");
        if (SecondCompound) {
          if (isCompoundPair(FirstCompound, SecondCompound)) {
            LLVM_DEBUG(dbgs() << "Compound pair (" << CompoundCount << ")\n");
            CompoundCount++;
          }
        }
        if (SecondDuplex) {
          if (QII->isDuplexPair(*FirstDuplex, *SecondDuplex)) {
            LLVM_DEBUG(dbgs() << "Duplex pair (" << DuplexCount << ")\n");
            DuplexCount++;
          }
        }
      } else {
        LLVM_DEBUG(dbgs() << "(" << InstOffset << ")\t");
        if (QII->getCompoundCandidateGroup(*MI))
          LLVM_DEBUG(dbgs() << "XX ");
        if (QII->getDuplexCandidateGroup(*MI))
          LLVM_DEBUG(dbgs() << "AA ");
        InstOffset += QII->getSize(*MI);
        LLVM_DEBUG(MI->dump());
      }
    }
  }
  LLVM_DEBUG(dbgs() << "Total compound(" << CompoundCount << ") duplex("
                    << DuplexCount << ")\n");
  return CompoundCount;
}
 
//===----------------------------------------------------------------------===//
//                         Public Constructor Functions
//===----------------------------------------------------------------------===//
 
FunctionPass *llvm::createHexagonGlobalScheduler() {
  return new HexagonGlobalScheduler();
}