VirtRegRewriter.cpp

      unsigned Reg = MO.getReg();
      if (MO.isDef()) {
        Defs.set(Reg);
        for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
          Defs.set(*AS);
      } else  {
        LocalUses.push_back(Reg);
        if (MO.isKill() && AllocatableRegs[Reg])
          Kills.push_back(Reg);
      }
    }

    for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
      unsigned Kill = Kills[i];
      if (!Defs[Kill] && !Uses[Kill] &&
          TRI->getPhysicalRegisterRegClass(Kill) == RC)
        return Kill;
    }
    for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
      unsigned Reg = LocalUses[i];
      Uses.set(Reg);
      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
        Uses.set(*AS);
    }

    MII = PrevMI;
  }

  return 0;
}

static
void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg,
                         const TargetRegisterInfo &TRI) {
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI->getOperand(i);
    if (MO.isReg() && MO.getReg() == VirtReg)
      substitutePhysReg(MO, PhysReg, TRI);
  }
}

namespace {

struct RefSorter {
  bool operator()(const std::pair<MachineInstr*, int> &A,
                  const std::pair<MachineInstr*, int> &B) {
    return A.second < B.second;
  }
};

// ***************************** //
// Local Spiller Implementation  //
// ***************************** //

class LocalRewriter : public VirtRegRewriter {
  MachineRegisterInfo *MRI;
  const TargetRegisterInfo *TRI;
  const TargetInstrInfo *TII;
  VirtRegMap *VRM;
  BitVector AllocatableRegs;
  DenseMap<MachineInstr*, unsigned> DistanceMap;

  MachineBasicBlock *MBB;       // Basic block currently being processed.

public:

  bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
                            LiveIntervals* LIs);

private:

  bool OptimizeByUnfold2(unsigned VirtReg, int SS,
                         MachineBasicBlock::iterator &MII,
                         std::vector<MachineInstr*> &MaybeDeadStores,
                         AvailableSpills &Spills,
                         BitVector &RegKills,
                         std::vector<MachineOperand*> &KillOps);

  bool OptimizeByUnfold(MachineBasicBlock::iterator &MII,
                        std::vector<MachineInstr*> &MaybeDeadStores,
                        AvailableSpills &Spills,
                        BitVector &RegKills,
                        std::vector<MachineOperand*> &KillOps);

  bool CommuteToFoldReload(MachineBasicBlock::iterator &MII,
                           unsigned VirtReg, unsigned SrcReg, int SS,
                           AvailableSpills &Spills,
                           BitVector &RegKills,
                           std::vector<MachineOperand*> &KillOps,
                           const TargetRegisterInfo *TRI);

  void SpillRegToStackSlot(MachineBasicBlock::iterator &MII,
                           int Idx, unsigned PhysReg, int StackSlot,
                           const TargetRegisterClass *RC,
                           bool isAvailable, MachineInstr *&LastStore,
                           AvailableSpills &Spills,
                           SmallSet<MachineInstr*, 4> &ReMatDefs,
                           BitVector &RegKills,
                           std::vector<MachineOperand*> &KillOps);

  void TransferDeadness(unsigned Reg, BitVector &RegKills,
                        std::vector<MachineOperand*> &KillOps);

  bool InsertEmergencySpills(MachineInstr *MI);

  bool InsertRestores(MachineInstr *MI,
                      AvailableSpills &Spills,
                      BitVector &RegKills,
                      std::vector<MachineOperand*> &KillOps);

  bool InsertSpills(MachineInstr *MI);

  void RewriteMBB(LiveIntervals *LIs,
                  AvailableSpills &Spills, BitVector &RegKills,
                  std::vector<MachineOperand*> &KillOps);
};
}

bool LocalRewriter::runOnMachineFunction(MachineFunction &MF, VirtRegMap &vrm,
                                         LiveIntervals* LIs) {
  MRI = &MF.getRegInfo();
  TRI = MF.getTarget().getRegisterInfo();
  TII = MF.getTarget().getInstrInfo();
  VRM = &vrm;
  AllocatableRegs = TRI->getAllocatableSet(MF);
  DEBUG(dbgs() << "\n**** Local spiller rewriting function '"
        << MF.getFunction()->getName() << "':\n");
  DEBUG(dbgs() << "**** Machine Instrs (NOTE! Does not include spills and"
        " reloads!) ****\n");
  DEBUG(MF.dump());

  // Spills - Keep track of which spilled values are available in physregs
  // so that we can choose to reuse the physregs instead of emitting
  // reloads. This is usually refreshed per basic block.
  AvailableSpills Spills(TRI, TII);

  // Keep track of kill information.
  BitVector RegKills(TRI->getNumRegs());
  std::vector<MachineOperand*> KillOps;
  KillOps.resize(TRI->getNumRegs(), NULL);

  // SingleEntrySuccs - Successor blocks which have a single predecessor.
  SmallVector<MachineBasicBlock*, 4> SinglePredSuccs;
  SmallPtrSet<MachineBasicBlock*,16> EarlyVisited;

  // Traverse the basic blocks depth first.
  MachineBasicBlock *Entry = MF.begin();
  SmallPtrSet<MachineBasicBlock*,16> Visited;
  for (df_ext_iterator<MachineBasicBlock*,
         SmallPtrSet<MachineBasicBlock*,16> >
         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
       DFI != E; ++DFI) {
    MBB = *DFI;
    if (!EarlyVisited.count(MBB))
      RewriteMBB(LIs, Spills, RegKills, KillOps);

    // If this MBB is the only predecessor of a successor. Keep the
    // availability information and visit it next.
    do {
      // Keep visiting single predecessor successor as long as possible.
      SinglePredSuccs.clear();
      findSinglePredSuccessor(MBB, SinglePredSuccs);
      if (SinglePredSuccs.empty())
        MBB = 0;
      else {
        // FIXME: More than one successors, each of which has MBB has
        // the only predecessor.
        MBB = SinglePredSuccs[0];
        if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
          Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
          RewriteMBB(LIs, Spills, RegKills, KillOps);
        }
      }
    } while (MBB);

    // Clear the availability info.
    Spills.clear();
  }

  DEBUG(dbgs() << "**** Post Machine Instrs ****\n");
  DEBUG(MF.dump());

  // Mark unused spill slots.
  MachineFrameInfo *MFI = MF.getFrameInfo();
  int SS = VRM->getLowSpillSlot();
  if (SS != VirtRegMap::NO_STACK_SLOT)
    for (int e = VRM->getHighSpillSlot(); SS <= e; ++SS)
      if (!VRM->isSpillSlotUsed(SS)) {
        MFI->RemoveStackObject(SS);
        ++NumDSS;
      }

  return true;
}

/// OptimizeByUnfold2 - Unfold a series of load / store folding instructions if
/// a scratch register is available.
///     xorq  %r12<kill>, %r13
///     addq  %rax, -184(%rbp)
///     addq  %r13, -184(%rbp)
/// ==>
///     xorq  %r12<kill>, %r13
///     movq  -184(%rbp), %r12
///     addq  %rax, %r12
///     addq  %r13, %r12
///     movq  %r12, -184(%rbp)
bool LocalRewriter::
OptimizeByUnfold2(unsigned VirtReg, int SS,
                  MachineBasicBlock::iterator &MII,
                  std::vector<MachineInstr*> &MaybeDeadStores,
                  AvailableSpills &Spills,
                  BitVector &RegKills,
                  std::vector<MachineOperand*> &KillOps) {

  MachineBasicBlock::iterator NextMII = llvm::next(MII);
  if (NextMII == MBB->end())
    return false;

  if (TII->getOpcodeAfterMemoryUnfold(MII->getOpcode(), true, true) == 0)
    return false;

  // Now let's see if the last couple of instructions happens to have freed up
  // a register.
  const TargetRegisterClass* RC = MRI->getRegClass(VirtReg);
  unsigned PhysReg = FindFreeRegister(MII, *MBB, RC, TRI, AllocatableRegs);
  if (!PhysReg)
    return false;

  MachineFunction &MF = *MBB->getParent();
  TRI = MF.getTarget().getRegisterInfo();
  MachineInstr &MI = *MII;
  if (!FoldsStackSlotModRef(MI, SS, PhysReg, TII, TRI, *VRM))
    return false;

  // If the next instruction also folds the same SS modref and can be unfoled,
  // then it's worthwhile to issue a load from SS into the free register and
  // then unfold these instructions.
  if (!FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, *VRM))
    return false;

  // Back-schedule reloads and remats.
  ComputeReloadLoc(MII, MBB->begin(), PhysReg, TRI, false, SS, TII, MF);

  // Load from SS to the spare physical register.
  TII->loadRegFromStackSlot(*MBB, MII, PhysReg, SS, RC);
  // This invalidates Phys.
  Spills.ClobberPhysReg(PhysReg);
  // Remember it's available.
  Spills.addAvailable(SS, PhysReg);
  MaybeDeadStores[SS] = NULL;

  // Unfold current MI.
  SmallVector<MachineInstr*, 4> NewMIs;
  if (!TII->unfoldMemoryOperand(MF, &MI, VirtReg, false, false, NewMIs))
    llvm_unreachable("Unable unfold the load / store folding instruction!");
  assert(NewMIs.size() == 1);
  AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg, *TRI);
  VRM->transferRestorePts(&MI, NewMIs[0]);
  MII = MBB->insert(MII, NewMIs[0]);
  InvalidateKills(MI, TRI, RegKills, KillOps);
  VRM->RemoveMachineInstrFromMaps(&MI);
  MBB->erase(&MI);
  ++NumModRefUnfold;

  // Unfold next instructions that fold the same SS.
  do {
    MachineInstr &NextMI = *NextMII;
    NextMII = llvm::next(NextMII);
    NewMIs.clear();
    if (!TII->unfoldMemoryOperand(MF, &NextMI, VirtReg, false, false, NewMIs))
      llvm_unreachable("Unable unfold the load / store folding instruction!");
    assert(NewMIs.size() == 1);
    AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg, *TRI);
    VRM->transferRestorePts(&NextMI, NewMIs[0]);
    MBB->insert(NextMII, NewMIs[0]);
    InvalidateKills(NextMI, TRI, RegKills, KillOps);
    VRM->RemoveMachineInstrFromMaps(&NextMI);
    MBB->erase(&NextMI);
    ++NumModRefUnfold;
    if (NextMII == MBB->end())
      break;
  } while (FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, *VRM));

  // Store the value back into SS.
  TII->storeRegToStackSlot(*MBB, NextMII, PhysReg, true, SS, RC);
  MachineInstr *StoreMI = prior(NextMII);
  VRM->addSpillSlotUse(SS, StoreMI);
  VRM->virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);

  return true;
}

/// OptimizeByUnfold - Turn a store folding instruction into a load folding
/// instruction. e.g.
///     xorl  %edi, %eax
///     movl  %eax, -32(%ebp)
///     movl  -36(%ebp), %eax
///     orl   %eax, -32(%ebp)
/// ==>
///     xorl  %edi, %eax
///     orl   -36(%ebp), %eax
///     mov   %eax, -32(%ebp)
/// This enables unfolding optimization for a subsequent instruction which will
/// also eliminate the newly introduced store instruction.
bool LocalRewriter::
OptimizeByUnfold(MachineBasicBlock::iterator &MII,
                 std::vector<MachineInstr*> &MaybeDeadStores,
                 AvailableSpills &Spills,
                 BitVector &RegKills,
                 std::vector<MachineOperand*> &KillOps) {
  MachineFunction &MF = *MBB->getParent();
  MachineInstr &MI = *MII;
  unsigned UnfoldedOpc = 0;
  unsigned UnfoldPR = 0;
  unsigned UnfoldVR = 0;
  int FoldedSS = VirtRegMap::NO_STACK_SLOT;
  VirtRegMap::MI2VirtMapTy::const_iterator I, End;
  for (tie(I, End) = VRM->getFoldedVirts(&MI); I != End; ) {
    // Only transform a MI that folds a single register.
    if (UnfoldedOpc)
      return false;
    UnfoldVR = I->second.first;
    VirtRegMap::ModRef MR = I->second.second;
    // MI2VirtMap be can updated which invalidate the iterator.
    // Increment the iterator first.
    ++I;
    if (VRM->isAssignedReg(UnfoldVR))
      continue;
    // If this reference is not a use, any previous store is now dead.
    // Otherwise, the store to this stack slot is not dead anymore.
    FoldedSS = VRM->getStackSlot(UnfoldVR);
    MachineInstr* DeadStore = MaybeDeadStores[FoldedSS];
    if (DeadStore && (MR & VirtRegMap::isModRef)) {
      unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS);
      if (!PhysReg || !DeadStore->readsRegister(PhysReg))
        continue;
      UnfoldPR = PhysReg;
      UnfoldedOpc = TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
                                                    false, true);
    }
  }

  if (!UnfoldedOpc) {
    if (!UnfoldVR)
      return false;

    // Look for other unfolding opportunities.
    return OptimizeByUnfold2(UnfoldVR, FoldedSS, MII, MaybeDeadStores, Spills,
                             RegKills, KillOps);
  }

  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || MO.getReg() == 0 || !MO.isUse())
      continue;
    unsigned VirtReg = MO.getReg();
    if (TargetRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg())
      continue;
    if (VRM->isAssignedReg(VirtReg)) {
      unsigned PhysReg = VRM->getPhys(VirtReg);
      if (PhysReg && TRI->regsOverlap(PhysReg, UnfoldPR))
        return false;
    } else if (VRM->isReMaterialized(VirtReg))
      continue;
    int SS = VRM->getStackSlot(VirtReg);
    unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
    if (PhysReg) {
      if (TRI->regsOverlap(PhysReg, UnfoldPR))
        return false;
      continue;
    }
    if (VRM->hasPhys(VirtReg)) {
      PhysReg = VRM->getPhys(VirtReg);
      if (!TRI->regsOverlap(PhysReg, UnfoldPR))
        continue;
    }

    // Ok, we'll need to reload the value into a register which makes
    // it impossible to perform the store unfolding optimization later.
    // Let's see if it is possible to fold the load if the store is
    // unfolded. This allows us to perform the store unfolding
    // optimization.
    SmallVector<MachineInstr*, 4> NewMIs;
    if (TII->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) {
      assert(NewMIs.size() == 1);
      MachineInstr *NewMI = NewMIs.back();
      NewMIs.clear();
      int Idx = NewMI->findRegisterUseOperandIdx(VirtReg, false);
      assert(Idx != -1);
      SmallVector<unsigned, 1> Ops;
      Ops.push_back(Idx);
      MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, NewMI, Ops, SS);
      if (FoldedMI) {
        VRM->addSpillSlotUse(SS, FoldedMI);
        if (!VRM->hasPhys(UnfoldVR))
          VRM->assignVirt2Phys(UnfoldVR, UnfoldPR);
        VRM->virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
        MII = MBB->insert(MII, FoldedMI);
        InvalidateKills(MI, TRI, RegKills, KillOps);
        VRM->RemoveMachineInstrFromMaps(&MI);
        MBB->erase(&MI);
        MF.DeleteMachineInstr(NewMI);
        return true;
      }
      MF.DeleteMachineInstr(NewMI);
    }
  }

  return false;
}

/// CommuteChangesDestination - We are looking for r0 = op r1, r2 and
/// where SrcReg is r1 and it is tied to r0. Return true if after
/// commuting this instruction it will be r0 = op r2, r1.
static bool CommuteChangesDestination(MachineInstr *DefMI,
                                      const TargetInstrDesc &TID,
                                      unsigned SrcReg,
                                      const TargetInstrInfo *TII,
                                      unsigned &DstIdx) {
  if (TID.getNumDefs() != 1 && TID.getNumOperands() != 3)
    return false;
  if (!DefMI->getOperand(1).isReg() ||
      DefMI->getOperand(1).getReg() != SrcReg)
    return false;
  unsigned DefIdx;
  if (!DefMI->isRegTiedToDefOperand(1, &DefIdx) || DefIdx != 0)
    return false;
  unsigned SrcIdx1, SrcIdx2;
  if (!TII->findCommutedOpIndices(DefMI, SrcIdx1, SrcIdx2))
    return false;
  if (SrcIdx1 == 1 && SrcIdx2 == 2) {
    DstIdx = 2;
    return true;
  }
  return false;
}

/// CommuteToFoldReload -
/// Look for
/// r1 = load fi#1
/// r1 = op r1, r2<kill>
/// store r1, fi#1
///
/// If op is commutable and r2 is killed, then we can xform these to
/// r2 = op r2, fi#1
/// store r2, fi#1
bool LocalRewriter::
CommuteToFoldReload(MachineBasicBlock::iterator &MII,
                    unsigned VirtReg, unsigned SrcReg, int SS,
                    AvailableSpills &Spills,
                    BitVector &RegKills,
                    std::vector<MachineOperand*> &KillOps,
                    const TargetRegisterInfo *TRI) {
  if (MII == MBB->begin() || !MII->killsRegister(SrcReg))
    return false;

  MachineFunction &MF = *MBB->getParent();
  MachineInstr &MI = *MII;
  MachineBasicBlock::iterator DefMII = prior(MII);
  MachineInstr *DefMI = DefMII;
  const TargetInstrDesc &TID = DefMI->getDesc();
  unsigned NewDstIdx;
  if (DefMII != MBB->begin() &&
      TID.isCommutable() &&
      CommuteChangesDestination(DefMI, TID, SrcReg, TII, NewDstIdx)) {
    MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
    unsigned NewReg = NewDstMO.getReg();
    if (!NewDstMO.isKill() || TRI->regsOverlap(NewReg, SrcReg))
      return false;
    MachineInstr *ReloadMI = prior(DefMII);
    int FrameIdx;
    unsigned DestReg = TII->isLoadFromStackSlot(ReloadMI, FrameIdx);
    if (DestReg != SrcReg || FrameIdx != SS)
      return false;
    int UseIdx = DefMI->findRegisterUseOperandIdx(DestReg, false);
    if (UseIdx == -1)
      return false;
    unsigned DefIdx;
    if (!MI.isRegTiedToDefOperand(UseIdx, &DefIdx))
      return false;
    assert(DefMI->getOperand(DefIdx).isReg() &&
           DefMI->getOperand(DefIdx).getReg() == SrcReg);

    // Now commute def instruction.
    MachineInstr *CommutedMI = TII->commuteInstruction(DefMI, true);
    if (!CommutedMI)
      return false;
    SmallVector<unsigned, 1> Ops;
    Ops.push_back(NewDstIdx);
    MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, CommutedMI, Ops, SS);
    // Not needed since foldMemoryOperand returns new MI.
    MF.DeleteMachineInstr(CommutedMI);
    if (!FoldedMI)
      return false;

    VRM->addSpillSlotUse(SS, FoldedMI);
    VRM->virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
    // Insert new def MI and spill MI.
    const TargetRegisterClass* RC = MRI->getRegClass(VirtReg);
    TII->storeRegToStackSlot(*MBB, &MI, NewReg, true, SS, RC);
    MII = prior(MII);
    MachineInstr *StoreMI = MII;
    VRM->addSpillSlotUse(SS, StoreMI);
    VRM->virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
    MII = MBB->insert(MII, FoldedMI);  // Update MII to backtrack.

    // Delete all 3 old instructions.
    InvalidateKills(*ReloadMI, TRI, RegKills, KillOps);
    VRM->RemoveMachineInstrFromMaps(ReloadMI);
    MBB->erase(ReloadMI);
    InvalidateKills(*DefMI, TRI, RegKills, KillOps);
    VRM->RemoveMachineInstrFromMaps(DefMI);
    MBB->erase(DefMI);
    InvalidateKills(MI, TRI, RegKills, KillOps);
    VRM->RemoveMachineInstrFromMaps(&MI);
    MBB->erase(&MI);

    // If NewReg was previously holding value of some SS, it's now clobbered.
    // This has to be done now because it's a physical register. When this
    // instruction is re-visited, it's ignored.
    Spills.ClobberPhysReg(NewReg);

    ++NumCommutes;
    return true;
  }

  return false;
}

/// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if
/// the last store to the same slot is now dead. If so, remove the last store.
void LocalRewriter::
SpillRegToStackSlot(MachineBasicBlock::iterator &MII,
                    int Idx, unsigned PhysReg, int StackSlot,
                    const TargetRegisterClass *RC,
                    bool isAvailable, MachineInstr *&LastStore,
                    AvailableSpills &Spills,
                    SmallSet<MachineInstr*, 4> &ReMatDefs,
                    BitVector &RegKills,
                    std::vector<MachineOperand*> &KillOps) {

  MachineBasicBlock::iterator oldNextMII = llvm::next(MII);
  TII->storeRegToStackSlot(*MBB, llvm::next(MII), PhysReg, true, StackSlot, RC);
  MachineInstr *StoreMI = prior(oldNextMII);
  VRM->addSpillSlotUse(StackSlot, StoreMI);
  DEBUG(dbgs() << "Store:\t" << *StoreMI);

  // If there is a dead store to this stack slot, nuke it now.
  if (LastStore) {
    DEBUG(dbgs() << "Removed dead store:\t" << *LastStore);
    ++NumDSE;
    SmallVector<unsigned, 2> KillRegs;
    InvalidateKills(*LastStore, TRI, RegKills, KillOps, &KillRegs);
    MachineBasicBlock::iterator PrevMII = LastStore;
    bool CheckDef = PrevMII != MBB->begin();
    if (CheckDef)
      --PrevMII;
    VRM->RemoveMachineInstrFromMaps(LastStore);
    MBB->erase(LastStore);
    if (CheckDef) {
      // Look at defs of killed registers on the store. Mark the defs
      // as dead since the store has been deleted and they aren't
      // being reused.
      for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) {
        bool HasOtherDef = false;
        if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef, TRI)) {
          MachineInstr *DeadDef = PrevMII;
          if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
            // FIXME: This assumes a remat def does not have side effects.
            VRM->RemoveMachineInstrFromMaps(DeadDef);
            MBB->erase(DeadDef);
            ++NumDRM;
          }
        }
      }
    }
  }

  // Allow for multi-instruction spill sequences, as on PPC Altivec.  Presume
  // the last of multiple instructions is the actual store.
  LastStore = prior(oldNextMII);

  // If the stack slot value was previously available in some other
  // register, change it now.  Otherwise, make the register available,
  // in PhysReg.
  Spills.ModifyStackSlotOrReMat(StackSlot);
  Spills.ClobberPhysReg(PhysReg);
  Spills.addAvailable(StackSlot, PhysReg, isAvailable);
  ++NumStores;
}

/// isSafeToDelete - Return true if this instruction doesn't produce any side
/// effect and all of its defs are dead.
static bool isSafeToDelete(MachineInstr &MI) {
  const TargetInstrDesc &TID = MI.getDesc();
  if (TID.mayLoad() || TID.mayStore() || TID.isCall() || TID.isTerminator() ||
      TID.isCall() || TID.isBarrier() || TID.isReturn() ||
      TID.hasUnmodeledSideEffects())
    return false;
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || !MO.getReg())
      continue;
    if (MO.isDef() && !MO.isDead())
      return false;
    if (MO.isUse() && MO.isKill())
      // FIXME: We can't remove kill markers or else the scavenger will assert.
      // An alternative is to add a ADD pseudo instruction to replace kill
      // markers.
      return false;
  }
  return true;
}

/// TransferDeadness - A identity copy definition is dead and it's being
/// removed. Find the last def or use and mark it as dead / kill.
void LocalRewriter::
TransferDeadness(unsigned Reg, BitVector &RegKills,
                 std::vector<MachineOperand*> &KillOps) {
  SmallPtrSet<MachineInstr*, 4> Seens;
  SmallVector<std::pair<MachineInstr*, int>,8> Refs;
  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
         RE = MRI->reg_end(); RI != RE; ++RI) {
    MachineInstr *UDMI = &*RI;
    if (UDMI->getParent() != MBB)
      continue;
    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
    if (DI == DistanceMap.end())
      continue;
    if (Seens.insert(UDMI))
      Refs.push_back(std::make_pair(UDMI, DI->second));
  }

  if (Refs.empty())
    return;
  std::sort(Refs.begin(), Refs.end(), RefSorter());

  while (!Refs.empty()) {
    MachineInstr *LastUDMI = Refs.back().first;
    Refs.pop_back();

    MachineOperand *LastUD = NULL;
    for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = LastUDMI->getOperand(i);
      if (!MO.isReg() || MO.getReg() != Reg)
        continue;
      if (!LastUD || (LastUD->isUse() && MO.isDef()))
        LastUD = &MO;
      if (LastUDMI->isRegTiedToDefOperand(i))
        break;
    }
    if (LastUD->isDef()) {
      // If the instruction has no side effect, delete it and propagate
      // backward further. Otherwise, mark is dead and we are done.
      if (!isSafeToDelete(*LastUDMI)) {
        LastUD->setIsDead();
        break;
      }
      VRM->RemoveMachineInstrFromMaps(LastUDMI);
      MBB->erase(LastUDMI);
    } else {
      LastUD->setIsKill();
      RegKills.set(Reg);
      KillOps[Reg] = LastUD;
      break;
    }
  }
}

/// InsertEmergencySpills - Insert emergency spills before MI if requested by
/// VRM. Return true if spills were inserted.
bool LocalRewriter::InsertEmergencySpills(MachineInstr *MI) {
  if (!VRM->hasEmergencySpills(MI))
    return false;
  MachineBasicBlock::iterator MII = MI;
  SmallSet<int, 4> UsedSS;
  std::vector<unsigned> &EmSpills = VRM->getEmergencySpills(MI);
  for (unsigned i = 0, e = EmSpills.size(); i != e; ++i) {
    unsigned PhysReg = EmSpills[i];
    const TargetRegisterClass *RC = TRI->getPhysicalRegisterRegClass(PhysReg);
    assert(RC && "Unable to determine register class!");
    int SS = VRM->getEmergencySpillSlot(RC);
    if (UsedSS.count(SS))
      llvm_unreachable("Need to spill more than one physical registers!");
    UsedSS.insert(SS);
    TII->storeRegToStackSlot(*MBB, MII, PhysReg, true, SS, RC);
    MachineInstr *StoreMI = prior(MII);
    VRM->addSpillSlotUse(SS, StoreMI);

    // Back-schedule reloads and remats.
    MachineBasicBlock::iterator InsertLoc =
      ComputeReloadLoc(llvm::next(MII), MBB->begin(), PhysReg, TRI, false, SS,
                       TII, *MBB->getParent());

    TII->loadRegFromStackSlot(*MBB, InsertLoc, PhysReg, SS, RC);

    MachineInstr *LoadMI = prior(InsertLoc);
    VRM->addSpillSlotUse(SS, LoadMI);
    ++NumPSpills;
    DistanceMap.insert(std::make_pair(LoadMI, DistanceMap.size()));
  }
  return true;
}

/// InsertRestores - Restore registers before MI is requested by VRM. Return
/// true is any instructions were inserted.
bool LocalRewriter::InsertRestores(MachineInstr *MI,
                                   AvailableSpills &Spills,
                                   BitVector &RegKills,
                                   std::vector<MachineOperand*> &KillOps) {
  if (!VRM->isRestorePt(MI))
    return false;
  MachineBasicBlock::iterator MII = MI;
  std::vector<unsigned> &RestoreRegs = VRM->getRestorePtRestores(MI);
  for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) {
    unsigned VirtReg = RestoreRegs[e-i-1];  // Reverse order.
    if (!VRM->getPreSplitReg(VirtReg))
      continue; // Split interval spilled again.
    unsigned Phys = VRM->getPhys(VirtReg);
    MRI->setPhysRegUsed(Phys);

    // Check if the value being restored if available. If so, it must be
    // from a predecessor BB that fallthrough into this BB. We do not
    // expect:
    // BB1:
    // r1 = load fi#1
    // ...
    //    = r1<kill>
    // ... # r1 not clobbered
    // ...
    //    = load fi#1
    bool DoReMat = VRM->isReMaterialized(VirtReg);
    int SSorRMId = DoReMat
      ? VRM->getReMatId(VirtReg) : VRM->getStackSlot(VirtReg);
    const TargetRegisterClass* RC = MRI->getRegClass(VirtReg);
    unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
    if (InReg == Phys) {
      // If the value is already available in the expected register, save
      // a reload / remat.
      if (SSorRMId)
        DEBUG(dbgs() << "Reusing RM#"
                     << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1);
      else
        DEBUG(dbgs() << "Reusing SS#" << SSorRMId);
      DEBUG(dbgs() << " from physreg "
                   << TRI->getName(InReg) << " for vreg"
                   << VirtReg <<" instead of reloading into physreg "
                   << TRI->getName(Phys) << '\n');
      ++NumOmitted;
      continue;
    } else if (InReg && InReg != Phys) {
      if (SSorRMId)
        DEBUG(dbgs() << "Reusing RM#"
                     << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1);
      else
        DEBUG(dbgs() << "Reusing SS#" << SSorRMId);
      DEBUG(dbgs() << " from physreg "
                   << TRI->getName(InReg) << " for vreg"
                   << VirtReg <<" by copying it into physreg "
                   << TRI->getName(Phys) << '\n');

      // If the reloaded / remat value is available in another register,
      // copy it to the desired register.

      // Back-schedule reloads and remats.
      MachineBasicBlock::iterator InsertLoc =
        ComputeReloadLoc(MII, MBB->begin(), Phys, TRI, DoReMat, SSorRMId, TII,
                         *MBB->getParent());

      TII->copyRegToReg(*MBB, InsertLoc, Phys, InReg, RC, RC);

      // This invalidates Phys.
      Spills.ClobberPhysReg(Phys);
      // Remember it's available.
      Spills.addAvailable(SSorRMId, Phys);

      // Mark is killed.
      MachineInstr *CopyMI = prior(InsertLoc);
      CopyMI->setAsmPrinterFlag(MachineInstr::ReloadReuse);
      MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg);
      KillOpnd->setIsKill();
      UpdateKills(*CopyMI, TRI, RegKills, KillOps);

      DEBUG(dbgs() << '\t' << *CopyMI);
      ++NumCopified;
      continue;
    }

    // Back-schedule reloads and remats.
    MachineBasicBlock::iterator InsertLoc =
      ComputeReloadLoc(MII, MBB->begin(), Phys, TRI, DoReMat, SSorRMId, TII,
                       *MBB->getParent());

    if (VRM->isReMaterialized(VirtReg)) {
      ReMaterialize(*MBB, InsertLoc, Phys, VirtReg, TII, TRI, *VRM);
    } else {
      const TargetRegisterClass* RC = MRI->getRegClass(VirtReg);
      TII->loadRegFromStackSlot(*MBB, InsertLoc, Phys, SSorRMId, RC);
      MachineInstr *LoadMI = prior(InsertLoc);
      VRM->addSpillSlotUse(SSorRMId, LoadMI);
      ++NumLoads;
      DistanceMap.insert(std::make_pair(LoadMI, DistanceMap.size()));
    }

    // This invalidates Phys.
    Spills.ClobberPhysReg(Phys);
    // Remember it's available.
    Spills.addAvailable(SSorRMId, Phys);

    UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps);
    DEBUG(dbgs() << '\t' << *prior(MII));
  }
  return true;
}

/// InsertEmergencySpills - Insert spills after MI if requested by VRM. Return
/// true if spills were inserted.
bool LocalRewriter::InsertSpills(MachineInstr *MI) {
  if (!VRM->isSpillPt(MI))
    return false;
  MachineBasicBlock::iterator MII = MI;
  std::vector<std::pair<unsigned,bool> > &SpillRegs =
    VRM->getSpillPtSpills(MI);
  for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
    unsigned VirtReg = SpillRegs[i].first;
    bool isKill = SpillRegs[i].second;
    if (!VRM->getPreSplitReg(VirtReg))
      continue; // Split interval spilled again.
    const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
    unsigned Phys = VRM->getPhys(VirtReg);
    int StackSlot = VRM->getStackSlot(VirtReg);
    MachineBasicBlock::iterator oldNextMII = llvm::next(MII);
    TII->storeRegToStackSlot(*MBB, llvm::next(MII), Phys, isKill, StackSlot,
                             RC);
    MachineInstr *StoreMI = prior(oldNextMII);
    VRM->addSpillSlotUse(StackSlot, StoreMI);
    DEBUG(dbgs() << "Store:\t" << *StoreMI);
    VRM->virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
  }
  return true;
}


/// rewriteMBB - Keep track of which spills are available even after the
/// register allocator is done with them.  If possible, avid reloading vregs.
void
LocalRewriter::RewriteMBB(LiveIntervals *LIs,
                          AvailableSpills &Spills, BitVector &RegKills,
                          std::vector<MachineOperand*> &KillOps) {

  DEBUG(dbgs() << "\n**** Local spiller rewriting MBB '"
               << MBB->getName() << "':\n");

  MachineFunction &MF = *MBB->getParent();

  // MaybeDeadStores - When we need to write a value back into a stack slot,
  // keep track of the inserted store.  If the stack slot value is never read
  // (because the value was used from some available register, for example), and
  // subsequently stored to, the original store is dead.  This map keeps track
  // of inserted stores that are not used.  If we see a subsequent store to the
  // same stack slot, the original store is deleted.
  std::vector<MachineInstr*> MaybeDeadStores;
  MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL);

  // ReMatDefs - These are rematerializable def MIs which are not deleted.
  SmallSet<MachineInstr*, 4> ReMatDefs;

  // Clear kill info.
  SmallSet<unsigned, 2> KilledMIRegs;
  RegKills.reset();
  KillOps.clear();
  KillOps.resize(TRI->getNumRegs(), NULL);

  DistanceMap.clear();
  for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end();
       MII != E; ) {
    MachineBasicBlock::iterator NextMII = llvm::next(MII);

    if (OptimizeByUnfold(MII, MaybeDeadStores, Spills, RegKills, KillOps))
      NextMII = llvm::next(MII);

    if (InsertEmergencySpills(MII))
      NextMII = llvm::next(MII);

    InsertRestores(MII, Spills, RegKills, KillOps);

    if (InsertSpills(MII))
      NextMII = llvm::next(MII);

    VirtRegMap::MI2VirtMapTy::const_iterator I, End;
    bool Erased = false;
    bool BackTracked = false;
    MachineInstr &MI = *MII;

    /// ReusedOperands - Keep track of operand reuse in case we need to undo
    /// reuse.
    ReuseInfo ReusedOperands(MI, TRI);
    SmallVector<unsigned, 4> VirtUseOps;
    for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
      MachineOperand &MO = MI.getOperand(i);
      if (!MO.isReg() || MO.getReg() == 0)
        continue;   // Ignore non-register operands.

      unsigned VirtReg = MO.getReg();
      if (TargetRegisterInfo::isPhysicalRegister(VirtReg)) {
        // Ignore physregs for spilling, but remember that it is used by this
        // function.
        MRI->setPhysRegUsed(VirtReg);
        continue;
      }

      // We want to process implicit virtual register uses first.
      if (MO.isImplicit())
        // If the virtual register is implicitly defined, emit a implicit_def
        // before so scavenger knows it's "defined".
        // FIXME: This is a horrible hack done the by register allocator to
        // remat a definition with virtual register operand.
        VirtUseOps.insert(VirtUseOps.begin(), i);
      else
        VirtUseOps.push_back(i);
    }

    // Process all of the spilled uses and all non spilled reg references.
    SmallVector<int, 2> PotentialDeadStoreSlots;
    KilledMIRegs.clear();
    for (unsigned j = 0, e = VirtUseOps.size(); j != e; ++j) {
      unsigned i = VirtUseOps[j];
      unsigned VirtReg = MI.getOperand(i).getReg();
      assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
             "Not a virtual register?");

      unsigned SubIdx = MI.getOperand(i).getSubReg();
      if (VRM->isAssignedReg(VirtReg)) {
        // This virtual register was assigned a physreg!
        unsigned Phys = VRM->getPhys(VirtReg);
        MRI->setPhysRegUsed(Phys);
        if (MI.getOperand(i).isDef())
          ReusedOperands.markClobbered(Phys);
        substitutePhysReg(MI.getOperand(i), Phys, *TRI);
        if (VRM->isImplicitlyDefined(VirtReg))
          // FIXME: Is this needed?
          BuildMI(*MBB, &MI, MI.getDebugLoc(),
                  TII->get(TargetOpcode::IMPLICIT_DEF), Phys);
        continue;
      }

      // This virtual register is now known to be a spilled value.
      if (!MI.getOperand(i).isUse())
        continue;  // Handle defs in the loop below (handle use&def here though)

      bool AvoidReload = MI.getOperand(i).isUndef();
      // Check if it is defined by an implicit def. It should not be spilled.
      // Note, this is for correctness reason. e.g.
      // 8   %reg1024<def> = IMPLICIT_DEF
      // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
      // The live range [12, 14) are not part of the r1024 live interval since
      // it's defined by an implicit def. It will not conflicts with live
      // interval of r1025. Now suppose both registers are spilled, you can
      // easily see a situation where both registers are reloaded before
      // the INSERT_SUBREG and both target registers that would overlap.
      bool DoReMat = VRM->isReMaterialized(VirtReg);
      int SSorRMId = DoReMat
        ? VRM->getReMatId(VirtReg) : VRM->getStackSlot(VirtReg);
      int ReuseSlot = SSorRMId;

      // Check to see if this stack slot is available.
      unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);

      // If this is a sub-register use, make sure the reuse register is in the
      // right register class. For example, for x86 not all of the 32-bit
      // registers have accessible sub-registers.
      // Similarly so for EXTRACT_SUBREG. Consider this:
      // EDI = op
      // MOV32_mr fi#1, EDI
      // ...
      //       = EXTRACT_SUBREG fi#1
      // fi#1 is available in EDI, but it cannot be reused because it's not in
      // the right register file.
      if (PhysReg && !AvoidReload && (SubIdx || MI.isExtractSubreg())) {
        const TargetRegisterClass* RC = MRI->getRegClass(VirtReg);
        if (!RC->contains(PhysReg))
          PhysReg = 0;
      }

      if (PhysReg && !AvoidReload) {
        // This spilled operand might be part of a two-address operand.  If this
        // is the case, then changing it will necessarily require changing the
        // def part of the instruction as well.  However, in some cases, we
        // aren't allowed to modify the reused register.  If none of these cases
        // apply, reuse it.
        bool CanReuse = true;
        bool isTied = MI.isRegTiedToDefOperand(i);
        if (isTied) {
          // Okay, we have a two address operand.  We can reuse this physreg as
          // long as we are allowed to clobber the value and there isn't an
          // earlier def that has already clobbered the physreg.
          CanReuse = !ReusedOperands.isClobbered(PhysReg) &&
            Spills.canClobberPhysReg(PhysReg);
        }