<commit_before>//===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that performs load / store related peephole
// optimizations. This pass should be run after register allocation.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "arm-ldst-opt"
#include "ARM.h"
#include "ARMAddressingModes.h"
#include "ARMBaseInstrInfo.h"
#include "ARMMachineFunctionInfo.h"
#include "ARMRegisterInfo.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;

STATISTIC(NumLDMGened , "Number of ldm instructions generated");
STATISTIC(NumSTMGened , "Number of stm instructions generated");
STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");

/// ARMAllocLoadStoreOpt - Post- register allocation pass the combine
/// load / store instructions to form ldm / stm instructions.

namespace {
  struct ARMLoadStoreOpt : public MachineFunctionPass {
    static char ID;
    ARMLoadStoreOpt() : MachineFunctionPass(&ID) {}

    const TargetInstrInfo *TII;
    const TargetRegisterInfo *TRI;
    ARMFunctionInfo *AFI;
    RegScavenger *RS;
    bool isThumb2;

    virtual bool runOnMachineFunction(MachineFunction &Fn);

    virtual const char *getPassName() const {
      return "ARM load / store optimization pass";
    }

  private:
    struct MemOpQueueEntry {
      int Offset;
      unsigned Position;
      MachineBasicBlock::iterator MBBI;
      bool Merged;
      MemOpQueueEntry(int o, int p, MachineBasicBlock::iterator i)
        : Offset(o), Position(p), MBBI(i), Merged(false) {}
    };
    typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
    typedef MemOpQueue::iterator MemOpQueueIter;

    bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                  int Offset, unsigned Base, bool BaseKill, int Opcode,
                  ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
                  DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs);
    void MergeOpsUpdate(MachineBasicBlock &MBB,
                        MemOpQueue &MemOps,
                        unsigned memOpsBegin,
                        unsigned memOpsEnd,
                        unsigned insertAfter,
                        int Offset,
                        unsigned Base,
                        bool BaseKill,
                        int Opcode,
                        ARMCC::CondCodes Pred,
                        unsigned PredReg,
                        unsigned Scratch,
                        DebugLoc dl,
                        SmallVector<MachineBasicBlock::iterator, 4> &Merges);
    void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
                      int Opcode, unsigned Size,
                      ARMCC::CondCodes Pred, unsigned PredReg,
                      unsigned Scratch, MemOpQueue &MemOps,
                      SmallVector<MachineBasicBlock::iterator, 4> &Merges);

    void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
    bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator &MBBI);
    bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator MBBI,
                                  const TargetInstrInfo *TII,
                                  bool &Advance,
                                  MachineBasicBlock::iterator &I);
    bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator MBBI,
                                   bool &Advance,
                                   MachineBasicBlock::iterator &I);
    bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
    bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
  };
  char ARMLoadStoreOpt::ID = 0;
}

static int getLoadStoreMultipleOpcode(int Opcode) {
  switch (Opcode) {
  case ARM::LDR:
    NumLDMGened++;
    return ARM::LDM;
  case ARM::STR:
    NumSTMGened++;
    return ARM::STM;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    NumLDMGened++;
    return ARM::t2LDM;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    NumSTMGened++;
    return ARM::t2STM;
  case ARM::VLDRS:
    NumVLDMGened++;
    return ARM::VLDMS;
  case ARM::VSTRS:
    NumVSTMGened++;
    return ARM::VSTMS;
  case ARM::VLDRD:
    NumVLDMGened++;
    return ARM::VLDMD;
  case ARM::VSTRD:
    NumVSTMGened++;
    return ARM::VSTMD;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

static bool isT2i32Load(unsigned Opc) {
  return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
}

static bool isi32Load(unsigned Opc) {
  return Opc == ARM::LDR || isT2i32Load(Opc);
}

static bool isT2i32Store(unsigned Opc) {
  return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
}

static bool isi32Store(unsigned Opc) {
  return Opc == ARM::STR || isT2i32Store(Opc);
}

/// MergeOps - Create and insert a LDM or STM with Base as base register and
/// registers in Regs as the register operands that would be loaded / stored.
/// It returns true if the transformation is done.
bool
ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
                          MachineBasicBlock::iterator MBBI,
                          int Offset, unsigned Base, bool BaseKill,
                          int Opcode, ARMCC::CondCodes Pred,
                          unsigned PredReg, unsigned Scratch, DebugLoc dl,
                          SmallVector<std::pair<unsigned, bool>, 8> &Regs) {
  // Only a single register to load / store. Don't bother.
  unsigned NumRegs = Regs.size();
  if (NumRegs <= 1)
    return false;

  ARM_AM::AMSubMode Mode = ARM_AM::ia;
  bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode);
  if (isAM4 && Offset == 4) {
    if (isThumb2)
      // Thumb2 does not support ldmib / stmib.
      return false;
    Mode = ARM_AM::ib;
  } else if (isAM4 && Offset == -4 * (int)NumRegs + 4) {
    if (isThumb2)
      // Thumb2 does not support ldmda / stmda.
      return false;
    Mode = ARM_AM::da;
  } else if (isAM4 && Offset == -4 * (int)NumRegs) {
    Mode = ARM_AM::db;
  } else if (Offset != 0) {
    // If starting offset isn't zero, insert a MI to materialize a new base.
    // But only do so if it is cost effective, i.e. merging more than two
    // loads / stores.
    if (NumRegs <= 2)
      return false;

    unsigned NewBase;
    if (isi32Load(Opcode))
      // If it is a load, then just use one of the destination register to
      // use as the new base.
      NewBase = Regs[NumRegs-1].first;
    else {
      // Use the scratch register to use as a new base.
      NewBase = Scratch;
      if (NewBase == 0)
        return false;
    }
    int BaseOpc = !isThumb2
      ? ARM::ADDri
      : ((Base == ARM::SP) ? ARM::t2ADDrSPi : ARM::t2ADDri);
    if (Offset < 0) {
      BaseOpc = !isThumb2
        ? ARM::SUBri
        : ((Base == ARM::SP) ? ARM::t2SUBrSPi : ARM::t2SUBri);
      Offset = - Offset;
    }
    int ImmedOffset = isThumb2
      ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset);
    if (ImmedOffset == -1)
      // FIXME: Try t2ADDri12 or t2SUBri12?
      return false;  // Probably not worth it then.

    BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase)
      .addReg(Base, getKillRegState(BaseKill)).addImm(Offset)
      .addImm(Pred).addReg(PredReg).addReg(0);
    Base = NewBase;
    BaseKill = true;  // New base is always killed right its use.
  }

  bool isDPR = Opcode == ARM::VLDRD || Opcode == ARM::VSTRD;
  bool isDef = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
  Opcode = getLoadStoreMultipleOpcode(Opcode);
  MachineInstrBuilder MIB = (isAM4)
    ? BuildMI(MBB, MBBI, dl, TII->get(Opcode))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(ARM_AM::getAM4ModeImm(Mode)).addImm(Pred).addReg(PredReg)
    : BuildMI(MBB, MBBI, dl, TII->get(Opcode))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(ARM_AM::getAM5Opc(Mode, false, isDPR ? NumRegs<<1 : NumRegs))
        .addImm(Pred).addReg(PredReg);
  MIB.addReg(0); // Add optional writeback (0 for now).
  for (unsigned i = 0; i != NumRegs; ++i)
    MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef)
                     | getKillRegState(Regs[i].second));

  return true;
}

// MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on
// success.
void ARMLoadStoreOpt::
MergeOpsUpdate(MachineBasicBlock &MBB,
               MemOpQueue &memOps,
               unsigned memOpsBegin,
               unsigned memOpsEnd,
               unsigned insertAfter,
               int Offset,
               unsigned Base,
               bool BaseKill,
               int Opcode,
               ARMCC::CondCodes Pred,
               unsigned PredReg,
               unsigned Scratch,
               DebugLoc dl,
               SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
  // First calculate which of the registers should be killed by the merged
  // instruction.
  SmallVector<std::pair<unsigned, bool>, 8> Regs;
  const unsigned insertPos = memOps[insertAfter].Position;
  for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
    const MachineOperand &MO = memOps[i].MBBI->getOperand(0);
    unsigned Reg = MO.getReg();
    bool isKill = MO.isKill();

    // If we are inserting the merged operation after an unmerged operation that
    // uses the same register, make sure to transfer any kill flag.
    for (unsigned j = memOpsEnd, e = memOps.size(); !isKill && j != e; ++j)
      if (memOps[j].Position<insertPos) {
        const MachineOperand &MOJ = memOps[j].MBBI->getOperand(0);
        if (MOJ.getReg() == Reg && MOJ.isKill())
          isKill = true;
      }

    Regs.push_back(std::make_pair(Reg, isKill));
  }

  // Try to do the merge.
  MachineBasicBlock::iterator Loc = memOps[insertAfter].MBBI;
  Loc++;
  if (!MergeOps(MBB, Loc, Offset, Base, BaseKill, Opcode,
                Pred, PredReg, Scratch, dl, Regs))
    return;

  // Merge succeeded, update records.
  Merges.push_back(prior(Loc));
  for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
    // Remove kill flags from any unmerged memops that come before insertPos.
    if (Regs[i-memOpsBegin].second)
      for (unsigned j = memOpsEnd, e = memOps.size(); j != e; ++j)
        if (memOps[j].Position<insertPos) {
          MachineOperand &MOJ = memOps[j].MBBI->getOperand(0);
          if (MOJ.getReg() == Regs[i-memOpsBegin].first && MOJ.isKill())
            MOJ.setIsKill(false);
        }
    MBB.erase(memOps[i].MBBI);
    memOps[i].Merged = true;
  }
}

/// MergeLDR_STR - Merge a number of load / store instructions into one or more
/// load / store multiple instructions.
void
ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
                          unsigned Base, int Opcode, unsigned Size,
                          ARMCC::CondCodes Pred, unsigned PredReg,
                          unsigned Scratch, MemOpQueue &MemOps,
                          SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
  bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode);
  int Offset = MemOps[SIndex].Offset;
  int SOffset = Offset;
  unsigned insertAfter = SIndex;
  MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
  DebugLoc dl = Loc->getDebugLoc();
  const MachineOperand &PMO = Loc->getOperand(0);
  unsigned PReg = PMO.getReg();
  unsigned PRegNum = PMO.isUndef() ? UINT_MAX
    : ARMRegisterInfo::getRegisterNumbering(PReg);

  for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
    int NewOffset = MemOps[i].Offset;
    const MachineOperand &MO = MemOps[i].MBBI->getOperand(0);
    unsigned Reg = MO.getReg();
    unsigned RegNum = MO.isUndef() ? UINT_MAX
      : ARMRegisterInfo::getRegisterNumbering(Reg);
    // AM4 - register numbers in ascending order.
    // AM5 - consecutive register numbers in ascending order.
    if (Reg != ARM::SP &&
        NewOffset == Offset + (int)Size &&
        ((isAM4 && RegNum > PRegNum) || RegNum == PRegNum+1)) {
      Offset += Size;
      PRegNum = RegNum;
    } else {
      // Can't merge this in. Try merge the earlier ones first.
      MergeOpsUpdate(MBB, MemOps, SIndex, i, insertAfter, SOffset,
                     Base, false, Opcode, Pred, PredReg, Scratch, dl, Merges);
      MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch,
                   MemOps, Merges);
      return;
    }

    if (MemOps[i].Position > MemOps[insertAfter].Position)
      insertAfter = i;
  }

  bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1;
  MergeOpsUpdate(MBB, MemOps, SIndex, MemOps.size(), insertAfter, SOffset,
                 Base, BaseKill, Opcode, Pred, PredReg, Scratch, dl, Merges);
  return;
}

static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
                                       unsigned Bytes, unsigned Limit,
                                       ARMCC::CondCodes Pred, unsigned PredReg){
  unsigned MyPredReg = 0;
  if (!MI)
    return false;
  if (MI->getOpcode() != ARM::t2SUBri &&
      MI->getOpcode() != ARM::t2SUBrSPi &&
      MI->getOpcode() != ARM::t2SUBrSPi12 &&
      MI->getOpcode() != ARM::tSUBspi &&
      MI->getOpcode() != ARM::SUBri)
    return false;

  // Make sure the offset fits in 8 bits.
  if (Bytes <= 0 || (Limit && Bytes >= Limit))
    return false;

  unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME
  return (MI->getOperand(0).getReg() == Base &&
          MI->getOperand(1).getReg() == Base &&
          (MI->getOperand(2).getImm()*Scale) == Bytes &&
          llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
          MyPredReg == PredReg);
}

static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
                                       unsigned Bytes, unsigned Limit,
                                       ARMCC::CondCodes Pred, unsigned PredReg){
  unsigned MyPredReg = 0;
  if (!MI)
    return false;
  if (MI->getOpcode() != ARM::t2ADDri &&
      MI->getOpcode() != ARM::t2ADDrSPi &&
      MI->getOpcode() != ARM::t2ADDrSPi12 &&
      MI->getOpcode() != ARM::tADDspi &&
      MI->getOpcode() != ARM::ADDri)
    return false;

  if (Bytes <= 0 || (Limit && Bytes >= Limit))
    // Make sure the offset fits in 8 bits.
    return false;

  unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME
  return (MI->getOperand(0).getReg() == Base &&
          MI->getOperand(1).getReg() == Base &&
          (MI->getOperand(2).getImm()*Scale) == Bytes &&
          llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
          MyPredReg == PredReg);
}

static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
  switch (MI->getOpcode()) {
  default: return 0;
  case ARM::LDR:
  case ARM::STR:
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
  case ARM::t2STRi8:
  case ARM::t2STRi12:
  case ARM::VLDRS:
  case ARM::VSTRS:
    return 4;
  case ARM::VLDRD:
  case ARM::VSTRD:
    return 8;
  case ARM::LDM:
  case ARM::STM:
  case ARM::t2LDM:
  case ARM::t2STM:
    return (MI->getNumOperands() - 5) * 4;
  case ARM::VLDMS:
  case ARM::VSTMS:
  case ARM::VLDMD:
  case ARM::VSTMD:
    return ARM_AM::getAM5Offset(MI->getOperand(1).getImm()) * 4;
  }
}

/// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
/// register into the LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
///
/// stmia rn, <ra, rb, rc>
/// rn := rn + 4 * 3;
/// =>
/// stmia rn!, <ra, rb, rc>
///
/// rn := rn - 4 * 3;
/// ldmia rn, <ra, rb, rc>
/// =>
/// ldmdb rn!, <ra, rb, rc>
bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
                                               MachineBasicBlock::iterator MBBI,
                                               bool &Advance,
                                               MachineBasicBlock::iterator &I) {
  MachineInstr *MI = MBBI;
  unsigned Base = MI->getOperand(0).getReg();
  unsigned Bytes = getLSMultipleTransferSize(MI);
  unsigned PredReg = 0;
  ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
  int Opcode = MI->getOpcode();
  bool isAM4 = Opcode == ARM::LDM || Opcode == ARM::t2LDM ||
    Opcode == ARM::STM || Opcode == ARM::t2STM;

  if (isAM4) {
    if (ARM_AM::getAM4WBFlag(MI->getOperand(1).getImm()))
      return false;

    // Can't use the updating AM4 sub-mode if the base register is also a dest
    // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
    for (unsigned i = 3, e = MI->getNumOperands(); i != e; ++i) {
      if (MI->getOperand(i).getReg() == Base)
        return false;
    }

    ARM_AM::AMSubMode Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm());
    if (MBBI != MBB.begin()) {
      MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::db, true));
        MI->getOperand(4).setReg(Base);
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      } else if (Mode == ARM_AM::ib &&
                 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::da, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      }
    }

    if (MBBI != MBB.end()) {
      MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
      if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
          isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
        return true;
      } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
                 isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
        return true;
      }
    }
  } else {
    // VLDM{D|S}, VSTM{D|S} addressing mode 5 ops.
    if (ARM_AM::getAM5WBFlag(MI->getOperand(1).getImm()))
      return false;

    ARM_AM::AMSubMode Mode = ARM_AM::getAM5SubMode(MI->getOperand(1).getImm());
    unsigned Offset = ARM_AM::getAM5Offset(MI->getOperand(1).getImm());
    if (MBBI != MBB.begin()) {
      MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::db, true, Offset));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      }
    }

    if (MBBI != MBB.end()) {
      MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::ia, true, Offset));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
      }
      return true;
    }
  }

  return false;
}

static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) {
  switch (Opc) {
  case ARM::LDR: return ARM::LDR_PRE;
  case ARM::STR: return ARM::STR_PRE;
  case ARM::VLDRS: return ARM::VLDMS;
  case ARM::VLDRD: return ARM::VLDMD;
  case ARM::VSTRS: return ARM::VSTMS;
  case ARM::VSTRD: return ARM::VSTMD;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    return ARM::t2LDR_PRE;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return ARM::t2STR_PRE;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) {
  switch (Opc) {
  case ARM::LDR: return ARM::LDR_POST;
  case ARM::STR: return ARM::STR_POST;
  case ARM::VLDRS: return ARM::VLDMS;
  case ARM::VLDRD: return ARM::VLDMD;
  case ARM::VSTRS: return ARM::VSTMS;
  case ARM::VSTRD: return ARM::VSTMD;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    return ARM::t2LDR_POST;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return ARM::t2STR_POST;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

/// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
/// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
                                               MachineBasicBlock::iterator MBBI,
                                               const TargetInstrInfo *TII,
                                               bool &Advance,
                                               MachineBasicBlock::iterator &I) {
  MachineInstr *MI = MBBI;
  unsigned Base = MI->getOperand(1).getReg();
  bool BaseKill = MI->getOperand(1).isKill();
  unsigned Bytes = getLSMultipleTransferSize(MI);
  int Opcode = MI->getOpcode();
  DebugLoc dl = MI->getDebugLoc();
  bool isAM5 = Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
    Opcode == ARM::VSTRD || Opcode == ARM::VSTRS;
  bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
  if (isAM2 && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0)
    return false;
  else if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
    return false;
  else if (isT2i32Load(Opcode) || isT2i32Store(Opcode))
    if (MI->getOperand(2).getImm() != 0)
      return false;

  bool isLd = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
  // Can't do the merge if the destination register is the same as the would-be
  // writeback register.
  if (isLd && MI->getOperand(0).getReg() == Base)
    return false;

  unsigned PredReg = 0;
  ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
  bool DoMerge = false;
  ARM_AM::AddrOpc AddSub = ARM_AM::add;
  unsigned NewOpc = 0;
  // AM2 - 12 bits, thumb2 - 8 bits.
  unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100);
  if (MBBI != MBB.begin()) {
    MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
    if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) {
      DoMerge = true;
      AddSub = ARM_AM::sub;
      NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
    } else if (!isAM5 &&
               isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) {
      DoMerge = true;
      NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
    }
    if (DoMerge)
      MBB.erase(PrevMBBI);
  }

  if (!DoMerge && MBBI != MBB.end()) {
    MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
    if (!isAM5 &&
        isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) {
      DoMerge = true;
      AddSub = ARM_AM::sub;
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
    } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) {
      DoMerge = true;
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
    }
    if (DoMerge) {
      if (NextMBBI == I) {
        Advance = true;
        ++I;
      }
      MBB.erase(NextMBBI);
    }
  }

  if (!DoMerge)
    return false;

  bool isDPR = NewOpc == ARM::VLDMD || NewOpc == ARM::VSTMD;
  unsigned Offset = 0;
  if (isAM5)
    Offset = ARM_AM::getAM5Opc((AddSub == ARM_AM::sub)
                               ? ARM_AM::db
                               : ARM_AM::ia, true, (isDPR ? 2 : 1));
  else if (isAM2)
    Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
  else
    Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
  if (isLd) {
    if (isAM5)
      // VLDMS, VLDMD
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(Offset).addImm(Pred).addReg(PredReg)
        .addReg(Base, getDefRegState(true)) // WB base register
        .addReg(MI->getOperand(0).getReg(), RegState::Define);
    else if (isAM2)
      // LDR_PRE, LDR_POST,
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
        .addReg(Base, RegState::Define)
        .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
    else
      // t2LDR_PRE, t2LDR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
        .addReg(Base, RegState::Define)
        .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
  } else {
    MachineOperand &MO = MI->getOperand(0);
    if (isAM5)
      // VSTMS, VSTMD
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc)).addReg(Base).addImm(Offset)
        .addImm(Pred).addReg(PredReg)
        .addReg(Base, getDefRegState(true)) // WB base register
        .addReg(MO.getReg(), getKillRegState(MO.isKill()));
    else if (isAM2)
      // STR_PRE, STR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
        .addReg(MO.getReg(), getKillRegState(MO.isKill()))
        .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
    else
      // t2STR_PRE, t2STR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
        .addReg(MO.getReg(), getKillRegState(MO.isKill()))
        .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
  }
  MBB.erase(MBBI);

  return true;
}

/// isMemoryOp - Returns true if instruction is a memory operations (that this
/// pass is capable of operating on).
static bool isMemoryOp(const MachineInstr *MI) {
  if (MI->hasOneMemOperand()) {
    const MachineMemOperand *MMO = *MI->memoperands_begin();

    // Don't touch volatile memory accesses - we may be changing their order.
    if (MMO->isVolatile())
      return false;

    // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is not.
    if (MMO->getAlignment() < 4)
      return false;
  }

  int Opcode = MI->getOpcode();
  switch (Opcode) {
  default: break;
  case ARM::LDR:
  case ARM::STR:
    return MI->getOperand(1).isReg() && MI->getOperand(2).getReg() == 0;
  case ARM::VLDRS:
  case ARM::VSTRS:
    return MI->getOperand(1).isReg();
  case ARM::VLDRD:
  case ARM::VSTRD:
    return MI->getOperand(1).isReg();
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return MI->getOperand(1).isReg();
  }
  return false;
}<commit_msg>Stay away from str <undef> in ARMLoadStoreOpt. This pass does not understand <undef> operands, and can cause scavenger failures when it translates <kill,undef> to <kill>.<commit_after>//===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that performs load / store related peephole
// optimizations. This pass should be run after register allocation.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "arm-ldst-opt"
#include "ARM.h"
#include "ARMAddressingModes.h"
#include "ARMBaseInstrInfo.h"
#include "ARMMachineFunctionInfo.h"
#include "ARMRegisterInfo.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterScavenging.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;

STATISTIC(NumLDMGened , "Number of ldm instructions generated");
STATISTIC(NumSTMGened , "Number of stm instructions generated");
STATISTIC(NumVLDMGened, "Number of vldm instructions generated");
STATISTIC(NumVSTMGened, "Number of vstm instructions generated");
STATISTIC(NumLdStMoved, "Number of load / store instructions moved");
STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation");
STATISTIC(NumSTRDFormed,"Number of strd created before allocation");
STATISTIC(NumLDRD2LDM,  "Number of ldrd instructions turned back into ldm");
STATISTIC(NumSTRD2STM,  "Number of strd instructions turned back into stm");
STATISTIC(NumLDRD2LDR,  "Number of ldrd instructions turned back into ldr's");
STATISTIC(NumSTRD2STR,  "Number of strd instructions turned back into str's");

/// ARMAllocLoadStoreOpt - Post- register allocation pass the combine
/// load / store instructions to form ldm / stm instructions.

namespace {
  struct ARMLoadStoreOpt : public MachineFunctionPass {
    static char ID;
    ARMLoadStoreOpt() : MachineFunctionPass(&ID) {}

    const TargetInstrInfo *TII;
    const TargetRegisterInfo *TRI;
    ARMFunctionInfo *AFI;
    RegScavenger *RS;
    bool isThumb2;

    virtual bool runOnMachineFunction(MachineFunction &Fn);

    virtual const char *getPassName() const {
      return "ARM load / store optimization pass";
    }

  private:
    struct MemOpQueueEntry {
      int Offset;
      unsigned Position;
      MachineBasicBlock::iterator MBBI;
      bool Merged;
      MemOpQueueEntry(int o, int p, MachineBasicBlock::iterator i)
        : Offset(o), Position(p), MBBI(i), Merged(false) {}
    };
    typedef SmallVector<MemOpQueueEntry,8> MemOpQueue;
    typedef MemOpQueue::iterator MemOpQueueIter;

    bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,
                  int Offset, unsigned Base, bool BaseKill, int Opcode,
                  ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch,
                  DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs);
    void MergeOpsUpdate(MachineBasicBlock &MBB,
                        MemOpQueue &MemOps,
                        unsigned memOpsBegin,
                        unsigned memOpsEnd,
                        unsigned insertAfter,
                        int Offset,
                        unsigned Base,
                        bool BaseKill,
                        int Opcode,
                        ARMCC::CondCodes Pred,
                        unsigned PredReg,
                        unsigned Scratch,
                        DebugLoc dl,
                        SmallVector<MachineBasicBlock::iterator, 4> &Merges);
    void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base,
                      int Opcode, unsigned Size,
                      ARMCC::CondCodes Pred, unsigned PredReg,
                      unsigned Scratch, MemOpQueue &MemOps,
                      SmallVector<MachineBasicBlock::iterator, 4> &Merges);

    void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps);
    bool FixInvalidRegPairOp(MachineBasicBlock &MBB,
                             MachineBasicBlock::iterator &MBBI);
    bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator MBBI,
                                  const TargetInstrInfo *TII,
                                  bool &Advance,
                                  MachineBasicBlock::iterator &I);
    bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator MBBI,
                                   bool &Advance,
                                   MachineBasicBlock::iterator &I);
    bool LoadStoreMultipleOpti(MachineBasicBlock &MBB);
    bool MergeReturnIntoLDM(MachineBasicBlock &MBB);
  };
  char ARMLoadStoreOpt::ID = 0;
}

static int getLoadStoreMultipleOpcode(int Opcode) {
  switch (Opcode) {
  case ARM::LDR:
    NumLDMGened++;
    return ARM::LDM;
  case ARM::STR:
    NumSTMGened++;
    return ARM::STM;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    NumLDMGened++;
    return ARM::t2LDM;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    NumSTMGened++;
    return ARM::t2STM;
  case ARM::VLDRS:
    NumVLDMGened++;
    return ARM::VLDMS;
  case ARM::VSTRS:
    NumVSTMGened++;
    return ARM::VSTMS;
  case ARM::VLDRD:
    NumVLDMGened++;
    return ARM::VLDMD;
  case ARM::VSTRD:
    NumVSTMGened++;
    return ARM::VSTMD;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

static bool isT2i32Load(unsigned Opc) {
  return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8;
}

static bool isi32Load(unsigned Opc) {
  return Opc == ARM::LDR || isT2i32Load(Opc);
}

static bool isT2i32Store(unsigned Opc) {
  return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8;
}

static bool isi32Store(unsigned Opc) {
  return Opc == ARM::STR || isT2i32Store(Opc);
}

/// MergeOps - Create and insert a LDM or STM with Base as base register and
/// registers in Regs as the register operands that would be loaded / stored.
/// It returns true if the transformation is done.
bool
ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB,
                          MachineBasicBlock::iterator MBBI,
                          int Offset, unsigned Base, bool BaseKill,
                          int Opcode, ARMCC::CondCodes Pred,
                          unsigned PredReg, unsigned Scratch, DebugLoc dl,
                          SmallVector<std::pair<unsigned, bool>, 8> &Regs) {
  // Only a single register to load / store. Don't bother.
  unsigned NumRegs = Regs.size();
  if (NumRegs <= 1)
    return false;

  ARM_AM::AMSubMode Mode = ARM_AM::ia;
  bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode);
  if (isAM4 && Offset == 4) {
    if (isThumb2)
      // Thumb2 does not support ldmib / stmib.
      return false;
    Mode = ARM_AM::ib;
  } else if (isAM4 && Offset == -4 * (int)NumRegs + 4) {
    if (isThumb2)
      // Thumb2 does not support ldmda / stmda.
      return false;
    Mode = ARM_AM::da;
  } else if (isAM4 && Offset == -4 * (int)NumRegs) {
    Mode = ARM_AM::db;
  } else if (Offset != 0) {
    // If starting offset isn't zero, insert a MI to materialize a new base.
    // But only do so if it is cost effective, i.e. merging more than two
    // loads / stores.
    if (NumRegs <= 2)
      return false;

    unsigned NewBase;
    if (isi32Load(Opcode))
      // If it is a load, then just use one of the destination register to
      // use as the new base.
      NewBase = Regs[NumRegs-1].first;
    else {
      // Use the scratch register to use as a new base.
      NewBase = Scratch;
      if (NewBase == 0)
        return false;
    }
    int BaseOpc = !isThumb2
      ? ARM::ADDri
      : ((Base == ARM::SP) ? ARM::t2ADDrSPi : ARM::t2ADDri);
    if (Offset < 0) {
      BaseOpc = !isThumb2
        ? ARM::SUBri
        : ((Base == ARM::SP) ? ARM::t2SUBrSPi : ARM::t2SUBri);
      Offset = - Offset;
    }
    int ImmedOffset = isThumb2
      ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset);
    if (ImmedOffset == -1)
      // FIXME: Try t2ADDri12 or t2SUBri12?
      return false;  // Probably not worth it then.

    BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase)
      .addReg(Base, getKillRegState(BaseKill)).addImm(Offset)
      .addImm(Pred).addReg(PredReg).addReg(0);
    Base = NewBase;
    BaseKill = true;  // New base is always killed right its use.
  }

  bool isDPR = Opcode == ARM::VLDRD || Opcode == ARM::VSTRD;
  bool isDef = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
  Opcode = getLoadStoreMultipleOpcode(Opcode);
  MachineInstrBuilder MIB = (isAM4)
    ? BuildMI(MBB, MBBI, dl, TII->get(Opcode))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(ARM_AM::getAM4ModeImm(Mode)).addImm(Pred).addReg(PredReg)
    : BuildMI(MBB, MBBI, dl, TII->get(Opcode))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(ARM_AM::getAM5Opc(Mode, false, isDPR ? NumRegs<<1 : NumRegs))
        .addImm(Pred).addReg(PredReg);
  MIB.addReg(0); // Add optional writeback (0 for now).
  for (unsigned i = 0; i != NumRegs; ++i)
    MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef)
                     | getKillRegState(Regs[i].second));

  return true;
}

// MergeOpsUpdate - call MergeOps and update MemOps and merges accordingly on
// success.
void ARMLoadStoreOpt::
MergeOpsUpdate(MachineBasicBlock &MBB,
               MemOpQueue &memOps,
               unsigned memOpsBegin,
               unsigned memOpsEnd,
               unsigned insertAfter,
               int Offset,
               unsigned Base,
               bool BaseKill,
               int Opcode,
               ARMCC::CondCodes Pred,
               unsigned PredReg,
               unsigned Scratch,
               DebugLoc dl,
               SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
  // First calculate which of the registers should be killed by the merged
  // instruction.
  SmallVector<std::pair<unsigned, bool>, 8> Regs;
  const unsigned insertPos = memOps[insertAfter].Position;
  for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
    const MachineOperand &MO = memOps[i].MBBI->getOperand(0);
    unsigned Reg = MO.getReg();
    bool isKill = MO.isKill();

    // If we are inserting the merged operation after an unmerged operation that
    // uses the same register, make sure to transfer any kill flag.
    for (unsigned j = memOpsEnd, e = memOps.size(); !isKill && j != e; ++j)
      if (memOps[j].Position<insertPos) {
        const MachineOperand &MOJ = memOps[j].MBBI->getOperand(0);
        if (MOJ.getReg() == Reg && MOJ.isKill())
          isKill = true;
      }

    Regs.push_back(std::make_pair(Reg, isKill));
  }

  // Try to do the merge.
  MachineBasicBlock::iterator Loc = memOps[insertAfter].MBBI;
  Loc++;
  if (!MergeOps(MBB, Loc, Offset, Base, BaseKill, Opcode,
                Pred, PredReg, Scratch, dl, Regs))
    return;

  // Merge succeeded, update records.
  Merges.push_back(prior(Loc));
  for (unsigned i = memOpsBegin; i < memOpsEnd; ++i) {
    // Remove kill flags from any unmerged memops that come before insertPos.
    if (Regs[i-memOpsBegin].second)
      for (unsigned j = memOpsEnd, e = memOps.size(); j != e; ++j)
        if (memOps[j].Position<insertPos) {
          MachineOperand &MOJ = memOps[j].MBBI->getOperand(0);
          if (MOJ.getReg() == Regs[i-memOpsBegin].first && MOJ.isKill())
            MOJ.setIsKill(false);
        }
    MBB.erase(memOps[i].MBBI);
    memOps[i].Merged = true;
  }
}

/// MergeLDR_STR - Merge a number of load / store instructions into one or more
/// load / store multiple instructions.
void
ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex,
                          unsigned Base, int Opcode, unsigned Size,
                          ARMCC::CondCodes Pred, unsigned PredReg,
                          unsigned Scratch, MemOpQueue &MemOps,
                          SmallVector<MachineBasicBlock::iterator, 4> &Merges) {
  bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode);
  int Offset = MemOps[SIndex].Offset;
  int SOffset = Offset;
  unsigned insertAfter = SIndex;
  MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI;
  DebugLoc dl = Loc->getDebugLoc();
  const MachineOperand &PMO = Loc->getOperand(0);
  unsigned PReg = PMO.getReg();
  unsigned PRegNum = PMO.isUndef() ? UINT_MAX
    : ARMRegisterInfo::getRegisterNumbering(PReg);

  for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) {
    int NewOffset = MemOps[i].Offset;
    const MachineOperand &MO = MemOps[i].MBBI->getOperand(0);
    unsigned Reg = MO.getReg();
    unsigned RegNum = MO.isUndef() ? UINT_MAX
      : ARMRegisterInfo::getRegisterNumbering(Reg);
    // AM4 - register numbers in ascending order.
    // AM5 - consecutive register numbers in ascending order.
    if (Reg != ARM::SP &&
        NewOffset == Offset + (int)Size &&
        ((isAM4 && RegNum > PRegNum) || RegNum == PRegNum+1)) {
      Offset += Size;
      PRegNum = RegNum;
    } else {
      // Can't merge this in. Try merge the earlier ones first.
      MergeOpsUpdate(MBB, MemOps, SIndex, i, insertAfter, SOffset,
                     Base, false, Opcode, Pred, PredReg, Scratch, dl, Merges);
      MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch,
                   MemOps, Merges);
      return;
    }

    if (MemOps[i].Position > MemOps[insertAfter].Position)
      insertAfter = i;
  }

  bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1;
  MergeOpsUpdate(MBB, MemOps, SIndex, MemOps.size(), insertAfter, SOffset,
                 Base, BaseKill, Opcode, Pred, PredReg, Scratch, dl, Merges);
  return;
}

static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base,
                                       unsigned Bytes, unsigned Limit,
                                       ARMCC::CondCodes Pred, unsigned PredReg){
  unsigned MyPredReg = 0;
  if (!MI)
    return false;
  if (MI->getOpcode() != ARM::t2SUBri &&
      MI->getOpcode() != ARM::t2SUBrSPi &&
      MI->getOpcode() != ARM::t2SUBrSPi12 &&
      MI->getOpcode() != ARM::tSUBspi &&
      MI->getOpcode() != ARM::SUBri)
    return false;

  // Make sure the offset fits in 8 bits.
  if (Bytes <= 0 || (Limit && Bytes >= Limit))
    return false;

  unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME
  return (MI->getOperand(0).getReg() == Base &&
          MI->getOperand(1).getReg() == Base &&
          (MI->getOperand(2).getImm()*Scale) == Bytes &&
          llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
          MyPredReg == PredReg);
}

static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base,
                                       unsigned Bytes, unsigned Limit,
                                       ARMCC::CondCodes Pred, unsigned PredReg){
  unsigned MyPredReg = 0;
  if (!MI)
    return false;
  if (MI->getOpcode() != ARM::t2ADDri &&
      MI->getOpcode() != ARM::t2ADDrSPi &&
      MI->getOpcode() != ARM::t2ADDrSPi12 &&
      MI->getOpcode() != ARM::tADDspi &&
      MI->getOpcode() != ARM::ADDri)
    return false;

  if (Bytes <= 0 || (Limit && Bytes >= Limit))
    // Make sure the offset fits in 8 bits.
    return false;

  unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME
  return (MI->getOperand(0).getReg() == Base &&
          MI->getOperand(1).getReg() == Base &&
          (MI->getOperand(2).getImm()*Scale) == Bytes &&
          llvm::getInstrPredicate(MI, MyPredReg) == Pred &&
          MyPredReg == PredReg);
}

static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) {
  switch (MI->getOpcode()) {
  default: return 0;
  case ARM::LDR:
  case ARM::STR:
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
  case ARM::t2STRi8:
  case ARM::t2STRi12:
  case ARM::VLDRS:
  case ARM::VSTRS:
    return 4;
  case ARM::VLDRD:
  case ARM::VSTRD:
    return 8;
  case ARM::LDM:
  case ARM::STM:
  case ARM::t2LDM:
  case ARM::t2STM:
    return (MI->getNumOperands() - 5) * 4;
  case ARM::VLDMS:
  case ARM::VSTMS:
  case ARM::VLDMD:
  case ARM::VSTMD:
    return ARM_AM::getAM5Offset(MI->getOperand(1).getImm()) * 4;
  }
}

/// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base
/// register into the LDM/STM/VLDM{D|S}/VSTM{D|S} op when possible:
///
/// stmia rn, <ra, rb, rc>
/// rn := rn + 4 * 3;
/// =>
/// stmia rn!, <ra, rb, rc>
///
/// rn := rn - 4 * 3;
/// ldmia rn, <ra, rb, rc>
/// =>
/// ldmdb rn!, <ra, rb, rc>
bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB,
                                               MachineBasicBlock::iterator MBBI,
                                               bool &Advance,
                                               MachineBasicBlock::iterator &I) {
  MachineInstr *MI = MBBI;
  unsigned Base = MI->getOperand(0).getReg();
  unsigned Bytes = getLSMultipleTransferSize(MI);
  unsigned PredReg = 0;
  ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
  int Opcode = MI->getOpcode();
  bool isAM4 = Opcode == ARM::LDM || Opcode == ARM::t2LDM ||
    Opcode == ARM::STM || Opcode == ARM::t2STM;

  if (isAM4) {
    if (ARM_AM::getAM4WBFlag(MI->getOperand(1).getImm()))
      return false;

    // Can't use the updating AM4 sub-mode if the base register is also a dest
    // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined.
    for (unsigned i = 3, e = MI->getNumOperands(); i != e; ++i) {
      if (MI->getOperand(i).getReg() == Base)
        return false;
    }

    ARM_AM::AMSubMode Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm());
    if (MBBI != MBB.begin()) {
      MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::db, true));
        MI->getOperand(4).setReg(Base);
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      } else if (Mode == ARM_AM::ib &&
                 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::da, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      }
    }

    if (MBBI != MBB.end()) {
      MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
      if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) &&
          isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
        return true;
      } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) &&
                 isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
        return true;
      }
    }
  } else {
    // VLDM{D|S}, VSTM{D|S} addressing mode 5 ops.
    if (ARM_AM::getAM5WBFlag(MI->getOperand(1).getImm()))
      return false;

    ARM_AM::AMSubMode Mode = ARM_AM::getAM5SubMode(MI->getOperand(1).getImm());
    unsigned Offset = ARM_AM::getAM5Offset(MI->getOperand(1).getImm());
    if (MBBI != MBB.begin()) {
      MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::db, true, Offset));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        MBB.erase(PrevMBBI);
        return true;
      }
    }

    if (MBBI != MBB.end()) {
      MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
      if (Mode == ARM_AM::ia &&
          isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) {
        MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::ia, true, Offset));
        MI->getOperand(4).setReg(Base);  // WB to base
        MI->getOperand(4).setIsDef();
        if (NextMBBI == I) {
          Advance = true;
          ++I;
        }
        MBB.erase(NextMBBI);
      }
      return true;
    }
  }

  return false;
}

static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) {
  switch (Opc) {
  case ARM::LDR: return ARM::LDR_PRE;
  case ARM::STR: return ARM::STR_PRE;
  case ARM::VLDRS: return ARM::VLDMS;
  case ARM::VLDRD: return ARM::VLDMD;
  case ARM::VSTRS: return ARM::VSTMS;
  case ARM::VSTRD: return ARM::VSTMD;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    return ARM::t2LDR_PRE;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return ARM::t2STR_PRE;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) {
  switch (Opc) {
  case ARM::LDR: return ARM::LDR_POST;
  case ARM::STR: return ARM::STR_POST;
  case ARM::VLDRS: return ARM::VLDMS;
  case ARM::VLDRD: return ARM::VLDMD;
  case ARM::VSTRS: return ARM::VSTMS;
  case ARM::VSTRD: return ARM::VSTMD;
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
    return ARM::t2LDR_POST;
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return ARM::t2STR_POST;
  default: llvm_unreachable("Unhandled opcode!");
  }
  return 0;
}

/// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base
/// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible:
bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB,
                                               MachineBasicBlock::iterator MBBI,
                                               const TargetInstrInfo *TII,
                                               bool &Advance,
                                               MachineBasicBlock::iterator &I) {
  MachineInstr *MI = MBBI;
  unsigned Base = MI->getOperand(1).getReg();
  bool BaseKill = MI->getOperand(1).isKill();
  unsigned Bytes = getLSMultipleTransferSize(MI);
  int Opcode = MI->getOpcode();
  DebugLoc dl = MI->getDebugLoc();
  bool isAM5 = Opcode == ARM::VLDRD || Opcode == ARM::VLDRS ||
    Opcode == ARM::VSTRD || Opcode == ARM::VSTRS;
  bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR;
  if (isAM2 && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0)
    return false;
  else if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0)
    return false;
  else if (isT2i32Load(Opcode) || isT2i32Store(Opcode))
    if (MI->getOperand(2).getImm() != 0)
      return false;

  bool isLd = isi32Load(Opcode) || Opcode == ARM::VLDRS || Opcode == ARM::VLDRD;
  // Can't do the merge if the destination register is the same as the would-be
  // writeback register.
  if (isLd && MI->getOperand(0).getReg() == Base)
    return false;

  unsigned PredReg = 0;
  ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg);
  bool DoMerge = false;
  ARM_AM::AddrOpc AddSub = ARM_AM::add;
  unsigned NewOpc = 0;
  // AM2 - 12 bits, thumb2 - 8 bits.
  unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100);
  if (MBBI != MBB.begin()) {
    MachineBasicBlock::iterator PrevMBBI = prior(MBBI);
    if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) {
      DoMerge = true;
      AddSub = ARM_AM::sub;
      NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
    } else if (!isAM5 &&
               isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) {
      DoMerge = true;
      NewOpc = getPreIndexedLoadStoreOpcode(Opcode);
    }
    if (DoMerge)
      MBB.erase(PrevMBBI);
  }

  if (!DoMerge && MBBI != MBB.end()) {
    MachineBasicBlock::iterator NextMBBI = llvm::next(MBBI);
    if (!isAM5 &&
        isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) {
      DoMerge = true;
      AddSub = ARM_AM::sub;
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
    } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) {
      DoMerge = true;
      NewOpc = getPostIndexedLoadStoreOpcode(Opcode);
    }
    if (DoMerge) {
      if (NextMBBI == I) {
        Advance = true;
        ++I;
      }
      MBB.erase(NextMBBI);
    }
  }

  if (!DoMerge)
    return false;

  bool isDPR = NewOpc == ARM::VLDMD || NewOpc == ARM::VSTMD;
  unsigned Offset = 0;
  if (isAM5)
    Offset = ARM_AM::getAM5Opc((AddSub == ARM_AM::sub)
                               ? ARM_AM::db
                               : ARM_AM::ia, true, (isDPR ? 2 : 1));
  else if (isAM2)
    Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift);
  else
    Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes;
  if (isLd) {
    if (isAM5)
      // VLDMS, VLDMD
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc))
        .addReg(Base, getKillRegState(BaseKill))
        .addImm(Offset).addImm(Pred).addReg(PredReg)
        .addReg(Base, getDefRegState(true)) // WB base register
        .addReg(MI->getOperand(0).getReg(), RegState::Define);
    else if (isAM2)
      // LDR_PRE, LDR_POST,
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
        .addReg(Base, RegState::Define)
        .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
    else
      // t2LDR_PRE, t2LDR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg())
        .addReg(Base, RegState::Define)
        .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
  } else {
    MachineOperand &MO = MI->getOperand(0);
    if (isAM5)
      // VSTMS, VSTMD
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc)).addReg(Base).addImm(Offset)
        .addImm(Pred).addReg(PredReg)
        .addReg(Base, getDefRegState(true)) // WB base register
        .addReg(MO.getReg(), getKillRegState(MO.isKill()));
    else if (isAM2)
      // STR_PRE, STR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
        .addReg(MO.getReg(), getKillRegState(MO.isKill()))
        .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg);
    else
      // t2STR_PRE, t2STR_POST
      BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base)
        .addReg(MO.getReg(), getKillRegState(MO.isKill()))
        .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg);
  }
  MBB.erase(MBBI);

  return true;
}

/// isMemoryOp - Returns true if instruction is a memory operations (that this
/// pass is capable of operating on).
static bool isMemoryOp(const MachineInstr *MI) {
  if (MI->hasOneMemOperand()) {
    const MachineMemOperand *MMO = *MI->memoperands_begin();

    // Don't touch volatile memory accesses - we may be changing their order.
    if (MMO->isVolatile())
      return false;

    // Unaligned ldr/str is emulated by some kernels, but unaligned ldm/stm is
    // not.
    if (MMO->getAlignment() < 4)
      return false;
  }

  // str <undef> could probably be eliminated entirely, but for now we just want
  // to avoid making a mess of it.
  // FIXME: Use str <undef> as a wildcard to enable better stm folding.
  if (MI->getNumOperands() > 0 && MI->getOperand(0).isReg() &&
      MI->getOperand(0).isUndef())
    return false;

  int Opcode = MI->getOpcode();
  switch (Opcode) {
  default: break;
  case ARM::LDR:
  case ARM::STR:
    return MI->getOperand(1).isReg() && MI->getOperand(2).getReg() == 0;
  case ARM::VLDRS:
  case ARM::VSTRS:
    return MI->getOperand(1).isReg();
  case ARM::VLDRD:
  case ARM::VSTRD:
    return MI->getOperand(1).isReg();
  case ARM::t2LDRi8:
  case ARM::t2LDRi12:
  case ARM::t2STRi8:
  case ARM::t2STRi12:
    return MI->getOperand(1).isReg();
  }
  return false;
}
{'fraction_non_alphanumeric': 0.13798830368027704, 'fraction_numerical': 0.01167865156628209, 'mean_word_length': 2.5984487252845065, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 227, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 54, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4028804', 'n_tokens_mistral': 19300, 'n_tokens_neox': 19014, 'n_words': 4473}