GlobalISel: add combiner for indexed loads and stores

[t.p.northover]

Summary

The goal here is to implement a roughly equivalent combiner to the DAG one. There are still a few edge-cases we miss, but those are all heuristics rather than correctness issues so probably not essential to begin with. See the FIXMEs for details.

The main intentional difference over the DAG situation is that PRE_DEC and POST_DEC didn't really seem relevant since address computations are carried out via G_GEP rather than add/sub. Therefore we just have pre/post indexed and a target will be expected to inspect the operands for negativity if it matters.

Since this doesn't add any real target support, testing is via a special option that overrides any legality claims the target might make. When there is enough target support that can be removed.

The other thing that might be worth thinking about is the proliferation of generic load/store instructions. I decided this didn't bother me particularly since indexed operations tend to be selected by C++ code anyway, but the combinatorial multiplication would be a bit annoying if TableGen had to cope too.

[arsenm]

llvm/include/llvm/Target/GenericOpcodes.td

770

Needs explanation of what an indexed load is

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

70

Typo of

[paquette]

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

459–460

I think it's safe to use getOpcodeDef from Utils here. It looks through copies but I don't think that's an issue here.

Then you can just do this to get a G_GEP or null:

MachineInstr *AddrDef = getOpcodeDef(TargetOpcode::G_GEP, Addr, MRI);

461

Should this be !MRI.hasOneUse(Addr)?

475

I think you can probably use getDefIgnoringCopies here?

488–491

Should this have some debug output for consistency?

515–517

bool IsPre = findPreIndexCandidate(MI, Addr, Base, Offset) would be a bit simpler I guess?

Then you could just go

if (!IsPre && !findPostIndexCandidate(MI, Addr, Base, Offset))
  return false;

But meh

551–552

Any reason this isn't MIB.addUse(Base) and MIB.addUse(Offset)?

555

Probably worth mentioning earlier in that our ultimate goal is to delete this.

Also, I don't *think* you need to actually delete AddrDef. It has no uses at this point so it should automatically be cleaned up.

(With that in mind, I guess you don't really have to check that AddrDef has a single use, although I'm not entirely sure if that would ever be beneficial.)

[aditya_nandakumar]

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

76

We have an implementation in CSEMIRBuilder.cpp which also checks dominance. We should merge the implementations (or re-use).

86

Any chance you can include examples (with MIR transformation as a comment) on what this is supposed to do?

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

555

Like @paquette said, there's no need to explicitly delete AddrDef - when the combiner gets to that instruction, if it's dead it should remove it.

[t.p.northover]

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

76

That implementation looks more like isPredecessor, since it doesn't rely on MachineDominanceTree information. I suppose I could put a common implementation in Utils.h.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

461

Nope, it's making sure there are uses *other* than the load/store we'll be making indexed (otherwise why bother).

555

Turns out it's needed because otherwise the transformation breaks SSA form.

[t.p.northover]

Updated according to most comments.

[aemerson]

On the addition of these opcodes themselves, I don't have a particularly strong opinion. It's unfortunate that we need yet more opcodes but I guess trying to do this analysis during selection might be harder to do because of the partially selected MF, and with the potential code duplication for each target that wants it.

My one concern is with adding the machine dominator analysis the the pipeline at -O0. Is there a significant compile time cost? It's ok if we can pay for it by reducing the amount of code to analyze but we should run the numbers to check.

[t.p.northover]

My one concern is with adding the machine dominator analysis the the pipeline at -O0. Is there a significant compile time cost?

Doesn't look like it. I did a few runs of the test-suite, and it came out at maybe 1% difference but the numbers were pretty noisy. I'd be inclined to leave it, though it would certainly be possible to only use MachineDominator at higher levels.

It's ok if we can pay for it by reducing the amount of code to analyze but we should run the numbers to check.

I doubt this is the kind of optimization that would pay for itself in that way.

[aemerson]

In D66287#1642767, @t.p.northover wrote:

My one concern is with adding the machine dominator analysis the the pipeline at -O0. Is there a significant compile time cost?

Doesn't look like it. I did a few runs of the test-suite, and it came out at maybe 1% difference but the numbers were pretty noisy. I'd be inclined to leave it, though it would certainly be possible to only use MachineDominator at higher levels.

Is that running the entire combine or just the MDT? If the latter, it's still non-negligible, but if there are code size savings to be had then its ok for me.

It's ok if we can pay for it by reducing the amount of code to analyze but we should run the numbers to check.

I doubt this is the kind of optimization that would pay for itself in that way.

[t.p.northover]

Changed my mind and only run MachineDominator above O0. The faff involved in estimating the performance penalty properly just isn't worth the small amount of work to make the issue go away.

[t.p.northover]

Thanks Amara. r371384.

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h

 namespace llvm {
 
 class GISelChangeObserver;
 class MachineIRBuilder;
 class MachineRegisterInfo;
 class MachineInstr;
 class MachineOperand;
 class GISelKnownBits;
+class MachineDominatorTree;
 
 struct PreferredTuple {
   LLT Ty;                // The result type of the extend.
   unsigned ExtendOpcode; // G_ANYEXT/G_SEXT/G_ZEXT
   MachineInstr *MI;
 };
 
 class CombinerHelper {
 protected:
   MachineIRBuilder &Builder;
   MachineRegisterInfo &MRI;
   GISelChangeObserver &Observer;
   GISelKnownBits *KB;
+  MachineDominatorTree *MDT;
 
 public:
   CombinerHelper(GISelChangeObserver &Observer, MachineIRBuilder &B,
-                 GISelKnownBits *KB = nullptr);
+                 GISelKnownBits *KB = nullptr,
+                 MachineDominatorTree *MDT = nullptr);
 
   /// MachineRegisterInfo::replaceRegWith() and inform the observer of the changes
   void replaceRegWith(MachineRegisterInfo &MRI, Register FromReg, Register ToReg) const;
 
   /// Replace a single register operand with a new register and inform the
   /// observer of the changes.
   void replaceRegOpWith(MachineRegisterInfo &MRI, MachineOperand &FromRegOp,
                         Register ToReg) const;
 
   /// If \p MI is COPY, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineCopy(MachineInstr &MI);
   bool matchCombineCopy(MachineInstr &MI);
   void applyCombineCopy(MachineInstr &MI);
 
+  /// \brief \returns true if \p DefMI precedes \p UseMI or they are the same
+  /// instruction. Both must be in the same basic block.
+  bool isPredecessor(MachineInstr &DefMI, MachineInstr &UseMI);
+
+  /// \brief \returns true of \p DefMI dominates \p UseMI. By definition an
+  /// instruction dominates itself.
+  ///
+  /// If we haven't been provided with a MachineDominatorTree during
+  /// construction, this function returns a conservative result that tracks just
+  /// a single basic block.
+  bool dominates(MachineInstr &DefMI, MachineInstr &UseMI);
+
   /// If \p MI is extend that consumes the result of a load, try to combine it.
   /// Returns true if MI changed.
   bool tryCombineExtendingLoads(MachineInstr &MI);
   bool matchCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
   void applyCombineExtendingLoads(MachineInstr &MI, PreferredTuple &MatchInfo);
 
+  /// Combine \p MI into a pre-indexed or post-indexed load/store operation if
+  /// legal and the surrounding code makes it useful.
+  bool tryCombineIndexedLoadStore(MachineInstr &MI);
+
   bool matchCombineBr(MachineInstr &MI);
   bool tryCombineBr(MachineInstr &MI);
 
   /// Optimize memcpy intrinsics et al, e.g. constant len calls.
   /// /p MaxLen if non-zero specifies the max length of a mem libcall to inline.
   bool tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen = 0);
 
   /// Try to transform \p MI by using all of the above
   /// combine functions. Returns true if changed.
   bool tryCombine(MachineInstr &MI);
 
 private:
   // Memcpy family optimization helpers.
   bool optimizeMemcpy(MachineInstr &MI, Register Dst, Register Src,
                       unsigned KnownLen, unsigned DstAlign, unsigned SrcAlign,
                       bool IsVolatile);
   bool optimizeMemmove(MachineInstr &MI, Register Dst, Register Src,
                       unsigned KnownLen, unsigned DstAlign, unsigned SrcAlign,
                       bool IsVolatile);
   bool optimizeMemset(MachineInstr &MI, Register Dst, Register Val,
                       unsigned KnownLen, unsigned DstAlign, bool IsVolatile);
+
+  /// Given a non-indexed load or store instruction \p MI, find an offset that
+  /// can be usefully and legally folded into it as a post-indexing operation.
+  ///
+  /// \returns true if a candidate is found.
+  bool findPostIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
+                              Register &Offset);
+
+  /// Given a non-indexed load or store instruction \p MI, find an offset that
+  /// can be usefully and legally folded into it as a pre-indexing operation.
+  ///
+  /// \returns true if a candidate is found.
+  bool findPreIndexCandidate(MachineInstr &MI, Register &Addr, Register &Base,
+                             Register &Offset);
 };
 } // namespace llvm
 
 #endif

llvm/include/llvm/CodeGen/TargetLowering.h

public:
   virtual bool getPostIndexedAddressParts(SDNode * /*N*/, SDNode * /*Op*/,
                                           SDValue &/*Base*/,
                                           SDValue &/*Offset*/,
                                           ISD::MemIndexedMode &/*AM*/,
                                           SelectionDAG &/*DAG*/) const {
     return false;
   }
 
+  /// Returns true if the specified base+offset is a legal indexed addressing
+  /// mode for this target. \p MI is the load or store instruction that is being
+  /// considered for transformation.
+  virtual bool isIndexingLegal(MachineInstr &MI, Register Base, Register Offset,
+                               bool IsPre, MachineRegisterInfo &MRI) const {
+    return false;
+  }
+
   /// Return the entry encoding for a jump table in the current function.  The
   /// returned value is a member of the MachineJumpTableInfo::JTEntryKind enum.
   virtual unsigned getJumpTableEncoding() const;
 
   virtual const MCExpr *
   LowerCustomJumpTableEntry(const MachineJumpTableInfo * /*MJTI*/,
                             const MachineBasicBlock * /*MBB*/, unsigned /*uid*/,
                             MCContext &/*Ctx*/) const {

llvm/include/llvm/Support/TargetOpcodes.def

 HANDLE_TARGET_OPCODE(G_LOAD)
 
 /// Generic signext load
 HANDLE_TARGET_OPCODE(G_SEXTLOAD)
 
 /// Generic zeroext load
 HANDLE_TARGET_OPCODE(G_ZEXTLOAD)
 
+/// Generic indexed load (including anyext load)
+HANDLE_TARGET_OPCODE(G_INDEXED_LOAD)
+
+/// Generic indexed signext load
+HANDLE_TARGET_OPCODE(G_INDEXED_SEXTLOAD)
+
+/// Generic indexed zeroext load
+HANDLE_TARGET_OPCODE(G_INDEXED_ZEXTLOAD)
+
 /// Generic store.
 HANDLE_TARGET_OPCODE(G_STORE)
 
+/// Generic indexed store.
+HANDLE_TARGET_OPCODE(G_INDEXED_STORE)
+
 /// Generic atomic cmpxchg with internal success check.
 HANDLE_TARGET_OPCODE(G_ATOMIC_CMPXCHG_WITH_SUCCESS)
 
 /// Generic atomic cmpxchg.
 HANDLE_TARGET_OPCODE(G_ATOMIC_CMPXCHG)
 
 /// Generic atomicrmw.
 HANDLE_TARGET_OPCODE(G_ATOMICRMW_XCHG)

llvm/include/llvm/Target/GenericOpcodes.td

 // Generic zero-extended load. Expects a MachineMemOperand in addition to explicit operands.
 def G_ZEXTLOAD : GenericInstruction {
   let OutOperandList = (outs type0:$dst);
   let InOperandList = (ins ptype1:$addr);
   let hasSideEffects = 0;
   let mayLoad = 1;
 }
 
+def G_INDEXED_LOAD : GenericInstruction {
+  let OutOperandList = (outs type0:$dst, ptype1:$newaddr);
+  let InOperandList = (ins ptype1:$addr, type2:$offset, unknown:$am);
+  let hasSideEffects = 0;
+  let mayLoad = 1;
+}
+
+def G_INDEXED_SEXTLOAD : GenericInstruction {
+  let OutOperandList = (outs type0:$dst, ptype1:$newaddr);
+  let InOperandList = (ins ptype1:$addr, type2:$offset, unknown:$am);
+  let hasSideEffects = 0;
+  let mayLoad = 1;
+}
+
+def G_INDEXED_ZEXTLOAD : GenericInstruction {
+  let OutOperandList = (outs type0:$dst, ptype1:$newaddr);
+  let InOperandList = (ins ptype1:$addr, type2:$offset, unknown:$am);
+  let hasSideEffects = 0;
+  let mayLoad = 1;
+}
+
 // Generic store. Expects a MachineMemOperand in addition to explicit operands.
 def G_STORE : GenericInstruction {
   let OutOperandList = (outs);
   let InOperandList = (ins type0:$src, ptype1:$addr);
   let hasSideEffects = 0;
   let mayStore = 1;
 }
 
+def G_INDEXED_STORE : GenericInstruction {
+  let OutOperandList = (outs ptype0:$newaddr);
+  let InOperandList = (ins type1:$src, ptype0:$addr, ptype2:$offset,
+                           unknown:$am);
+  let hasSideEffects = 0;
+  let mayStore = 1;
+}
+
 // Generic atomic cmpxchg with internal success check. Expects a
 // MachineMemOperand in addition to explicit operands.
 def G_ATOMIC_CMPXCHG_WITH_SUCCESS : GenericInstruction {
   let OutOperandList = (outs type0:$oldval, type1:$success);
   let InOperandList = (ins type2:$addr, type0:$cmpval, type0:$newval);
   let hasSideEffects = 0;
   let mayLoad = 1;
   let mayStore = 1;

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp

 //===-- lib/CodeGen/GlobalISel/GICombinerHelper.cpp -----------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
 #include "llvm/CodeGen/GlobalISel/Combiner.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/Target/TargetMachine.h"
 
 #define DEBUG_TYPE "gi-combiner"
 
 using namespace llvm;
 
+// Option to allow testing of the combiner while no targets know about indexed
+// addressing.
+static cl::opt<bool>
+    ForceLegalIndexing("force-legal-indexing", cl::Hidden, cl::init(false),
+                       cl::desc("Force all indexed operations to be "
+                                "legal for the GlobalISel combiner"));
+
+
 CombinerHelper::CombinerHelper(GISelChangeObserver &Observer,
-                               MachineIRBuilder &B, GISelKnownBits *KB)
+                               MachineIRBuilder &B, GISelKnownBits *KB,
+                               MachineDominatorTree *MDT)
     : Builder(B), MRI(Builder.getMF().getRegInfo()), Observer(Observer),
-      KB(KB) {
+      KB(KB), MDT(MDT) {
   (void)this->KB;
 }
 
 void CombinerHelper::replaceRegWith(MachineRegisterInfo &MRI, Register FromReg,
                                     Register ToReg) const {
   Observer.changingAllUsesOfReg(MRI, FromReg);
 
   if (MRI.constrainRegAttrs(ToReg, FromReg))
for (auto *UseMO : Uses) {
     // This is free on many targets.
     InsertInsnsWithoutSideEffectsBeforeUse(Builder, MI, *UseMO, InsertTruncAt);
   }
 
   MI.getOperand(0).setReg(ChosenDstReg);
   Observer.changedInstr(MI);
 }
 
+bool CombinerHelper::isPredecessor(MachineInstr &DefMI, MachineInstr &UseMI) {
+  assert(DefMI.getParent() == UseMI.getParent());
+  if (&DefMI == &UseMI)
+    return false;
+
+  // Loop through the basic block until we find one of the instructions.
+  MachineBasicBlock::const_iterator I = DefMI.getParent()->begin();
+  for (; &*I != &DefMI && &*I != &UseMI; ++I)
+    return &*I == &DefMI;
+
+  llvm_unreachable("Block must contain instructions");
+}
+
+bool CombinerHelper::dominates(MachineInstr &DefMI, MachineInstr &UseMI) {
+  if (MDT)
+    return MDT->dominates(&DefMI, &UseMI);
+  else if (DefMI.getParent() != UseMI.getParent())
+    return false;
+
+  return isPredecessor(DefMI, UseMI);
+}
+
+bool CombinerHelper::findPostIndexCandidate(MachineInstr &MI, Register &Addr,
+                                            Register &Base, Register &Offset) {
+  auto &MF = *MI.getParent()->getParent();
+  const auto &TLI = *MF.getSubtarget().getTargetLowering();
+
+  unsigned Opcode = MI.getOpcode();
+  assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
+         Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
+
+  Base = MI.getOperand(1).getReg();
+  MachineInstr *BaseDef = MRI.getUniqueVRegDef(Base);
+  if (BaseDef && BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX)
+    return false;
+
+  LLVM_DEBUG(dbgs() << "Searching for post-indexing opportunity for: " << MI);
+
+  for (auto &Use : MRI.use_instructions(Base)) {
+    if (Use.getOpcode() != TargetOpcode::G_GEP)
+      continue;
+
+    Offset = Use.getOperand(2).getReg();
+    if (!ForceLegalIndexing &&
+        !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ false, MRI)) {
+      LLVM_DEBUG(dbgs() << "    Ignoring candidate with illegal addrmode: "
+                        << Use);
+      continue;
+    }
+
+    // Make sure the offset calculation is before the potentially indexed op.
+    // FIXME: we really care about dependency here. The offset calculation might
+    // be movable.
+    MachineInstr *OffsetDef = MRI.getUniqueVRegDef(Offset);
+    if (!OffsetDef || !dominates(*OffsetDef, MI)) {
+      LLVM_DEBUG(dbgs() << "    Ignoring candidate with offset after mem-op: "
+                        << Use);
+      continue;
+    }
+
+    // FIXME: check whether all uses of Base are load/store with foldable
+    // addressing modes. If so, using the normal addr-modes is better than
+    // forming an indexed one.
+
+    bool MemOpDominatesAddrUses = true;
+    for (auto &GEPUse : MRI.use_instructions(Use.getOperand(0).getReg())) {
+      if (!dominates(MI, GEPUse)) {
+        MemOpDominatesAddrUses = false;
+        break;
+      }
+    }
+
+    if (!MemOpDominatesAddrUses) {
+      LLVM_DEBUG(
+          dbgs() << "    Ignoring candidate as memop does not dominate uses: "
+                 << Use);
+      continue;
+    }
+
+    LLVM_DEBUG(dbgs() << "    Found match: " << Use);
+    Addr = Use.getOperand(0).getReg();
+    return true;
+  }
+
+  return false;
+}
+
+bool CombinerHelper::findPreIndexCandidate(MachineInstr &MI, Register &Addr,
+                                           Register &Base, Register &Offset) {
+  auto &MF = *MI.getParent()->getParent();
+  const auto &TLI = *MF.getSubtarget().getTargetLowering();
+
+  unsigned Opcode = MI.getOpcode();
+  assert(Opcode == TargetOpcode::G_LOAD || Opcode == TargetOpcode::G_SEXTLOAD ||
+         Opcode == TargetOpcode::G_ZEXTLOAD || Opcode == TargetOpcode::G_STORE);
+
+  Addr = MI.getOperand(1).getReg();
+  MachineInstr *AddrDef = MRI.getUniqueVRegDef(Addr);
+  if (!AddrDef || AddrDef->getOpcode() != TargetOpcode::G_GEP ||
+      MRI.hasOneUse(Addr))
+    return false;
+
+  Base = AddrDef->getOperand(1).getReg();
+  Offset = AddrDef->getOperand(2).getReg();
+
+  LLVM_DEBUG(dbgs() << "Found potential pre-indexed load_store: " << MI);
+
+  if (!ForceLegalIndexing &&
+      !TLI.isIndexingLegal(MI, Base, Offset, /*IsPre*/ true, MRI)) {
+    LLVM_DEBUG(dbgs() << "    Skipping, not legal for target");
+    return false;
+  }
+
+  MachineInstr *BaseDef = MRI.getUniqueVRegDef(Base);
+  if (BaseDef->getOpcode() == TargetOpcode::G_FRAME_INDEX) {
+    LLVM_DEBUG(dbgs() << "    Skipping, frame index would need copy anyway.");
+    return false;
+  }
+
+  if (MI.getOpcode() == TargetOpcode::G_STORE) {
+    // Would require a copy.
+    if (Base == MI.getOperand(0).getReg()) {
+      LLVM_DEBUG(dbgs() << "    Skipping, storing base so need copy anyway.");
+      return false;
+    }
+
+    // We're expecting one use of Addr in MI, but it could also be the
+    // value stored, which isn't actually dominated by the instruction.
+    if (MI.getOperand(0).getReg() == Addr)
+      return false;
+  }
+
+  // FIXME: check whether all uses of the base pointer are constant GEPs. That
+  // might allow us to end base's liveness here by adjusting the constant.
+
+  for (auto &UseMI : MRI.use_instructions(Addr)) {
+    if (!dominates(MI, UseMI)) {
+      LLVM_DEBUG(dbgs() << "    Skipping, does not dominate all addr uses.");
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool CombinerHelper::tryCombineIndexedLoadStore(MachineInstr &MI) {
+  unsigned Opcode = MI.getOpcode();
+  if (Opcode != TargetOpcode::G_LOAD && Opcode != TargetOpcode::G_SEXTLOAD &&
+      Opcode != TargetOpcode::G_ZEXTLOAD && Opcode != TargetOpcode::G_STORE)
+    return false;
+
+  bool IsStore = Opcode == TargetOpcode::G_STORE;
+  Register Addr, Base, Offset;
+  bool IsPre = false;
+  if (findPreIndexCandidate(MI, Addr, Base, Offset))
+    IsPre = true;
+  else if (!findPostIndexCandidate(MI, Addr, Base, Offset))
+    return false;
+
+
+  unsigned NewOpcode;
+  switch (Opcode) {
+  case TargetOpcode::G_LOAD:
+    NewOpcode = TargetOpcode::G_INDEXED_LOAD;
+    break;
+  case TargetOpcode::G_SEXTLOAD:
+    NewOpcode = TargetOpcode::G_INDEXED_SEXTLOAD;
+    break;
+  case TargetOpcode::G_ZEXTLOAD:
+    NewOpcode = TargetOpcode::G_INDEXED_ZEXTLOAD;
+    break;
+  case TargetOpcode::G_STORE:
+    NewOpcode = TargetOpcode::G_INDEXED_STORE;
+    break;
+  default:
+    llvm_unreachable("Unknown load/store opcode");
+  }
+
+  MachineInstr &AddrDef = *MRI.getUniqueVRegDef(Addr);
+  MachineIRBuilder MIRBuilder(MI);
+  auto MIB = MIRBuilder.buildInstr(NewOpcode);
+  if (IsStore) {
+    MIB.addDef(Addr);
+    MIB.addUse(MI.getOperand(0).getReg());
+  } else {
+    MIB.addDef(MI.getOperand(0).getReg());
+    MIB.addDef(Addr);
+  }
+
+  MIB.addReg(Base);
+  MIB.addReg(Offset);
+  MIB.addImm(IsPre);
+  MI.eraseFromParent();
+  AddrDef.eraseFromParent();
+
+  LLVM_DEBUG(dbgs() << "    Combinined to indexed operation");
+  return true;
+}
+
 bool CombinerHelper::matchCombineBr(MachineInstr &MI) {
   assert(MI.getOpcode() == TargetOpcode::G_BR && "Expected a G_BR");
   // Try to match the following:
   // bb1:
   //   %c(s32) = G_ICMP pred, %a, %b
   //   %c1(s1) = G_TRUNC %c(s32)
   //   G_BRCOND %c1, %bb2
   //   G_BR %bb3
bool CombinerHelper::tryCombineMemCpyFamily(MachineInstr &MI, unsigned MaxLen) {
   if (ID == Intrinsic::memset)
     return optimizeMemset(MI, Dst, Src, KnownLen, DstAlign, IsVolatile);
   return false;
 }
 
 bool CombinerHelper::tryCombine(MachineInstr &MI) {
   if (tryCombineCopy(MI))
     return true;
-  return tryCombineExtendingLoads(MI);
+  if (tryCombineExtendingLoads(MI))
+    return true;
+  if (tryCombineIndexedLoadStore(MI))
+    return true;
+  return false;
 }

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

 #include "llvm/Support/MathExtras.h"
 #include "llvm/Target/TargetLoweringObjectFile.h"
 #include "llvm/Target/TargetMachine.h"
 #include <cctype>
 using namespace llvm;
 
 /// NOTE: The TargetMachine owns TLOF.
 TargetLowering::TargetLowering(const TargetMachine &tm)
     : TargetLoweringBase(tm) {}
 
 const char *TargetLowering::getTargetNodeName(unsigned Opcode) const {
   return nullptr;
 }
 
 bool TargetLowering::isPositionIndependent() const {
   return getTargetMachine().isPositionIndependent();
 }

llvm/lib/Target/AArch64/AArch64PreLegalizerCombiner.cpp

 //===----------------------------------------------------------------------===//
 
 #include "AArch64TargetMachine.h"
 #include "llvm/CodeGen/GlobalISel/Combiner.h"
 #include "llvm/CodeGen/GlobalISel/CombinerHelper.h"
 #include "llvm/CodeGen/GlobalISel/CombinerInfo.h"
 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "aarch64-prelegalizer-combiner"
 
 using namespace llvm;
 using namespace MIPatternMatch;
 
 namespace {
 class AArch64PreLegalizerCombinerInfo : public CombinerInfo {
   GISelKnownBits *KB;
+  MachineDominatorTree *MDT;
 
 public:
   AArch64PreLegalizerCombinerInfo(bool EnableOpt, bool OptSize, bool MinSize,
-                                  GISelKnownBits *KB)
+                                  GISelKnownBits *KB, MachineDominatorTree *MDT)
       : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false,
                      /*LegalizerInfo*/ nullptr, EnableOpt, OptSize, MinSize),
-        KB(KB) {}
+        KB(KB), MDT(MDT) {}
   virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI,
                        MachineIRBuilder &B) const override;
 };
 
 bool AArch64PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer,
                                               MachineInstr &MI,
                                               MachineIRBuilder &B) const {
-  CombinerHelper Helper(Observer, B, KB);
+  CombinerHelper Helper(Observer, B, KB, MDT);
 
   switch (MI.getOpcode()) {
   default:
     return false;
   case TargetOpcode::COPY:
     return Helper.tryCombineCopy(MI);
   case TargetOpcode::G_BR:
     return Helper.tryCombineBr(MI);
   case TargetOpcode::G_LOAD:
   case TargetOpcode::G_SEXTLOAD:
-  case TargetOpcode::G_ZEXTLOAD:
-    return Helper.tryCombineExtendingLoads(MI);
+  case TargetOpcode::G_ZEXTLOAD: {
+    bool Changed = false;
+    Changed |= Helper.tryCombineExtendingLoads(MI);
+    Changed |= Helper.tryCombineIndexedLoadStore(MI);
+    return Changed;
+  }
+  case TargetOpcode::G_STORE:
+    return Helper.tryCombineIndexedLoadStore(MI);
   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
     switch (MI.getIntrinsicID()) {
     case Intrinsic::memcpy:
     case Intrinsic::memmove:
     case Intrinsic::memset: {
       // If we're at -O0 set a maxlen of 32 to inline, otherwise let the other
       // heuristics decide.
       unsigned MaxLen = EnableOpt ? 0 : 32;

 }
 
 void AArch64PreLegalizerCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
   AU.setPreservesCFG();
   getSelectionDAGFallbackAnalysisUsage(AU);
   AU.addRequired<GISelKnownBitsAnalysis>();
   AU.addPreserved<GISelKnownBitsAnalysis>();
+  AU.addRequired<MachineDominatorTree>();
+  AU.addPreserved<MachineDominatorTree>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 AArch64PreLegalizerCombiner::AArch64PreLegalizerCombiner() : MachineFunctionPass(ID) {
   initializeAArch64PreLegalizerCombinerPass(*PassRegistry::getPassRegistry());
 }
 
 bool AArch64PreLegalizerCombiner::runOnMachineFunction(MachineFunction &MF) {
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
   auto *TPC = &getAnalysis<TargetPassConfig>();
   const Function &F = MF.getFunction();
   bool EnableOpt =
       MF.getTarget().getOptLevel() != CodeGenOpt::None && !skipFunction(F);
   GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF);
+  MachineDominatorTree *MDT = &getAnalysis<MachineDominatorTree>();
   AArch64PreLegalizerCombinerInfo PCInfo(EnableOpt, F.hasOptSize(),
-                                         F.hasMinSize(), KB);
+                                         F.hasMinSize(), KB, MDT);
   Combiner C(PCInfo, TPC);
   return C.combineMachineInstrs(MF, /*CSEInfo*/ nullptr);
 }
 
 char AArch64PreLegalizerCombiner::ID = 0;
 INITIALIZE_PASS_BEGIN(AArch64PreLegalizerCombiner, DEBUG_TYPE,
                       "Combine AArch64 machine instrs before legalization",
                       false, false)

llvm/test/CodeGen/AArch64/GlobalISel/combiner-load-store-indexing.ll

+; RUN: llc -mtriple=arm64-apple-ios -global-isel -global-isel-abort=1 -verify-machineinstrs -stop-after=aarch64-prelegalizer-combiner -force-legal-indexing %s -o - | FileCheck %s
+
+define i8* @test_simple_load_pre(i8* %ptr) {
+; CHECK-LABEL: name: test_simple_load_pre
+; CHECK: [[BASE:%.*]]:_(p0) = COPY $x0
+; CHECK: [[OFFSET:%.*]]:_(s64) = G_CONSTANT i64 42
+; CHECK-NOT: G_GEP
+; CHECK: {{%.*}}:_(s8), [[NEXT:%.*]]:_(p0) = G_INDEXED_LOAD [[BASE]], [[OFFSET]](s64), 1
+; CHECK: $x0 = COPY [[NEXT]](p0)
+
+  %next = getelementptr i8, i8* %ptr, i32 42
+  load volatile i8, i8* %next
+  ret i8* %next
+}
+
+define void @test_load_multiple_dominated(i8* %ptr, i1 %tst, i1 %tst2) {
+; CHECK-LABEL: name: test_load_multiple_dominated
+; CHECK: [[BASE:%.*]]:_(p0) = COPY $x0
+; CHECK: [[OFFSET:%.*]]:_(s64) = G_CONSTANT i64 42
+; CHECK-NOT: G_GEP
+; CHECK: {{%.*}}:_(s8), [[NEXT:%.*]]:_(p0) = G_INDEXED_LOAD [[BASE]], [[OFFSET]](s64), 1
+; CHECK: $x0 = COPY [[NEXT]](p0)
+  %next = getelementptr i8, i8* %ptr, i32 42
+  br i1 %tst, label %do_load, label %end
+
+do_load:
+  load volatile i8, i8* %next
+  br i1 %tst2, label %bb1, label %bb2
+
+bb1:
+  store volatile i8* %next, i8** undef
+  ret void
+
+bb2:
+  call void @bar(i8* %next)
+  ret void
+
+end:
+  ret void
+}
+
+define i8* @test_simple_store_pre(i8* %ptr) {
+; CHECK-LABEL: name: test_simple_store_pre
+; CHECK: [[BASE:%.*]]:_(p0) = COPY $x0
+; CHECK: [[VAL:%.*]]:_(s8) = G_CONSTANT i8 0
+; CHECK: [[OFFSET:%.*]]:_(s64) = G_CONSTANT i64 42
+; CHECK-NOT: G_GEP
+; CHECK: [[NEXT:%.*]]:_(p0) = G_INDEXED_STORE [[VAL]](s8), [[BASE]], [[OFFSET]](s64), 1
+; CHECK: $x0 = COPY [[NEXT]](p0)
+
+  %next = getelementptr i8, i8* %ptr, i32 42
+  store volatile i8 0, i8* %next
+  ret i8* %next
+}
+
+; The potentially pre-indexed address is used as the value stored. Converting
+; would produce the value too late but only by one instruction.
+define i64** @test_store_pre_val_loop(i64** %ptr) {
+; CHECK-LABEL: name: test_store_pre_val_loop
+; CHECK: G_GEP
+; CHECK: G_STORE %
+
+  %next = getelementptr i64*, i64** %ptr, i32 42
+  %next.p0 = bitcast i64** %next to i64*
+  store volatile i64* %next.p0, i64** %next
+  ret i64** %next
+}
+
+; Potentially pre-indexed address is used between GEP computing it and load.
+define i8* @test_load_pre_before(i8* %ptr) {
+; CHECK-LABEL: name: test_load_pre_before
+; CHECK: G_GEP
+; CHECK: BL @bar
+; CHECK: G_LOAD %
+
+  %next = getelementptr i8, i8* %ptr, i32 42
+  call void @bar(i8* %next)
+  load volatile i8, i8* %next
+  ret i8* %next
+}
+
+; Materializing the base into a writable register (from sp/fp) would be just as
+; bad as the original GEP.
+define i8* @test_alloca_load_pre() {
+; CHECK-LABEL: name: test_alloca_load_pre
+; CHECK: G_GEP
+; CHECK: G_LOAD %
+
+  %ptr = alloca i8, i32 128
+  %next = getelementptr i8, i8* %ptr, i32 42
+  load volatile i8, i8* %next
+  ret i8* %next
+}
+
+; Load does not dominate use of its address. No indexing.
+define i8* @test_pre_nodom(i8* %in, i1 %tst) {
+; CHECK-LABEL: name: test_pre_nodom
+; CHECK: G_GEP
+; CHECK: G_LOAD %
+
+  %next = getelementptr i8, i8* %in, i32 16
+  br i1 %tst, label %do_indexed, label %use_addr
+
+do_indexed:
+  %val = load i8, i8* %next
+  store i8 %val, i8* @var
+  store i8* %next, i8** @varp8
+  br label %use_addr
+
+use_addr:
+  ret i8* %next
+}
+
+define i8* @test_simple_load_post(i8* %ptr) {
+; CHECK-LABEL: name: test_simple_load_post
+; CHECK: [[BASE:%.*]]:_(p0) = COPY $x0
+; CHECK: [[OFFSET:%.*]]:_(s64) = G_CONSTANT i64 42
+; CHECK-NOT: G_GEP
+; CHECK: {{%.*}}:_(s8), [[NEXT:%.*]]:_(p0) = G_INDEXED_LOAD [[BASE]], [[OFFSET]](s64), 0
+; CHECK: $x0 = COPY [[NEXT]](p0)
+
+  %next = getelementptr i8, i8* %ptr, i32 42
+  load volatile i8, i8* %ptr
+  ret i8* %next
+}
+
+define i8* @test_simple_load_post_gep_after(i8* %ptr) {
+; CHECK-LABEL: name: test_simple_load_post_gep_after
+; CHECK: [[BASE:%.*]]:_(p0) = COPY $x0
+; CHECK: BL @get_offset
+; CHECK: [[OFFSET:%.*]]:_(s64) = COPY $x0
+; CHECK: {{%.*}}:_(s8), [[ADDR:%.*]]:_(p0) = G_INDEXED_LOAD [[BASE]], [[OFFSET]](s64), 0
+; CHECK: $x0 = COPY [[ADDR]](p0)
+
+  %offset = call i64 @get_offset()
+  load volatile i8, i8* %ptr
+  %next = getelementptr i8, i8* %ptr, i64 %offset
+  ret i8* %next
+}
+
+define i8* @test_load_post_keep_looking(i8* %ptr) {
+; CHECK: name: test_load_post_keep_looking
+; CHECK: G_INDEXED_LOAD
+
+  %offset = call i64 @get_offset()
+  load volatile i8, i8* %ptr
+  %intval = ptrtoint i8* %ptr to i8
+  store i8 %intval, i8* @var
+
+  %next = getelementptr i8, i8* %ptr, i64 %offset
+  ret i8* %next
+}
+
+; Base is frame index. Using indexing would need copy anyway.
+define i8* @test_load_post_alloca() {
+; CHECK-LABEL: name: test_load_post_alloca
+; CHECK: G_GEP
+; CHECK: G_LOAD %
+
+  %ptr = alloca i8, i32 128
+  %next = getelementptr i8, i8* %ptr, i32 42
+  load volatile i8, i8* %ptr
+  ret i8* %next
+}
+
+; Offset computation does not dominate the load we might be indexing.
+define i8* @test_load_post_gep_offset_after(i8* %ptr) {
+; CHECK-LABEL: name: test_load_post_gep_offset_after
+; CHECK: G_LOAD %
+; CHECK: BL @get_offset
+; CHECK: G_GEP
+
+  load volatile i8, i8* %ptr
+  %offset = call i64 @get_offset()
+  %next = getelementptr i8, i8* %ptr, i64 %offset
+  ret i8* %next
+}
+
+declare void @bar(i8*)
+declare i64 @get_offset()
+@var = global i8 0
+@varp8 = global i8* null

llvm/test/CodeGen/AArch64/GlobalISel/gisel-commandline-option.ll

 
 ; RUN: llc -mtriple=aarch64-- -fast-isel=0 -global-isel=false \
 ; RUN:   -debug-pass=Structure %s -o /dev/null 2>&1 -verify-machineinstrs=0 \
 ; RUN:   | FileCheck %s --check-prefix DISABLED
 
 ; ENABLED:       IRTranslator
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  Analysis for ComputingKnownBits
+; ENABLED-NEXT:  MachineDominator Tree Construction
 ; ENABLED-NEXT:  PreLegalizerCombiner
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  Analysis containing CSE Info
 ; ENABLED-NEXT:  Legalizer
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-NEXT:  RegBankSelect
 ; VERIFY-NEXT:   Verify generated machine code
 ; ENABLED-O0-NEXT:  Localizer

llvm/test/CodeGen/AArch64/GlobalISel/legalizer-info-validation.mir

 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: G_SEXTLOAD (opcode {{[0-9]+}}): 2 type indices, 0 imm indices
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: G_ZEXTLOAD (opcode {{[0-9]+}}): 2 type indices, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
+# DEBUG-NEXT: G_INDEXED_LOAD (opcode 64): 3 type indices, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: G_INDEXED_SEXTLOAD (opcode 65): 3 type indices, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: G_INDEXED_ZEXTLOAD (opcode 66): 3 type indices, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: G_STORE (opcode {{[0-9]+}}): 2 type indices, 0 imm indices
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
+# DEBUG-NEXT: G_INDEXED_STORE (opcode 68): 3 type indices, 0 imm indices
+# DEBUG-NEXT: .. type index coverage check SKIPPED: no rules defined
+# DEBUG-NEXT: .. imm index coverage check SKIPPED: no rules defined
 # DEBUG-NEXT: G_ATOMIC_CMPXCHG_WITH_SUCCESS (opcode {{[0-9]+}}): 3 type indices, 0 imm indices
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: G_ATOMIC_CMPXCHG (opcode {{[0-9]+}}): 2 type indices, 0 imm indices
 # DEBUG-NEXT: .. opcode {{[0-9]+}} is aliased to {{[0-9]+}}
 # DEBUG-NEXT: .. type index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: .. imm index coverage check SKIPPED: user-defined predicate detected
 # DEBUG-NEXT: G_ATOMICRMW_XCHG (opcode {{[0-9]+}}): 2 type indices, 0 imm indices

llvm/test/CodeGen/AArch64/O0-pipeline.ll

 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       IRTranslator
 ; CHECK-NEXT:       Analysis for ComputingKnownBits
+; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       AArch64PreLegalizerCombiner
 ; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       Legalizer
 ; CHECK-NEXT:       RegBankSelect
 ; CHECK-NEXT:       Localizer
 ; CHECK-NEXT:       InstructionSelect
 ; CHECK-NEXT:       ResetMachineFunction
 ; CHECK-NEXT:       AArch64 Instruction Selection