[DAG] Teach findBaseOffset to interpret indexes of indexed memory operations

[niravd]

Summary

Indexed outputs are addition / subtractions and can be interpreted as such.

[efriedma]

There are two aspects to this patch:

1. Correctness: are we correctly distinguishing indexed loads and stores from unindexed loads and stores?
2. Performance: are we optimizing indexed loads and stores as aggressively as possible?

This patch looks like it's mixing up the two. Please separate it into two patches, so we can evaluate the two aspects separately.

[niravd]

clang-format and fix missing check that we're using EA output in address calc.

[RKSimon]

CC llvm-commits in all llvm patches

[niravd]

Factored out the indexed memory operation correctness check into D417101.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

133

Maybe add a LLVM_FALLTHROUGH and default case here?

[niravd]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

133

We'd still need to have a trailing break after the switch (or a do-loop-again varaible) to drop out of the while loop because of the other 2 cases.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

133

You're right - my mistake.

[RKSimon]

I don't have any more comments anyone else @efriedma @jyknight @hfinkel ?

[jyknight]

Looks reasonable to me, modulo style nit.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

127

This is a confusing way to write this. It gets the correct answer, but I'd prefer if the load/store result value numbers (0 for store, 1 for load) were just explicitly spelled out with a conditional.

[niravd]

This was landed in rL323539.

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

bool equalBaseIndex(BaseIndexOffset &Other, const SelectionDAG &DAG) {
     int64_t Off;
     return equalBaseIndex(Other, DAG, Off);
   }
 
   bool equalBaseIndex(BaseIndexOffset &Other, const SelectionDAG &DAG,
                       int64_t &Off);
 
   /// Parses tree in Ptr for base, index, offset addresses.
-  static BaseIndexOffset match(SDValue Ptr, const SelectionDAG &DAG);
+  static BaseIndexOffset match(LSBaseSDNode *N, const SelectionDAG &DAG);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

for (unsigned i = 0; i < ByteWidth; i++) {
     // All loads must share the same chain
     SDValue LChain = L->getChain();
     if (!Chain)
       Chain = LChain;
     else if (Chain != LChain)
       return SDValue();
 
     // Loads must share the same base address
-    BaseIndexOffset Ptr = BaseIndexOffset::match(L->getBasePtr(), DAG);
+    BaseIndexOffset Ptr = BaseIndexOffset::match(L, DAG);
     int64_t ByteOffsetFromBase = 0;
     if (!Base)
       Base = Ptr;
     else if (!Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
       return SDValue();
 
     // Calculate the offset of the current byte from the base address
     ByteOffsetFromBase += MemoryByteOffset(*P);
bool DAGCombiner::MergeStoresOfConstantsOrVecElts(
   AddToWorklist(NewChain.getNode());
   return true;
 }
 
 void DAGCombiner::getStoreMergeCandidates(
     StoreSDNode *St, SmallVectorImpl<MemOpLink> &StoreNodes) {
   // This holds the base pointer, index, and the offset in bytes from the base
   // pointer.
-  BaseIndexOffset BasePtr = BaseIndexOffset::match(St->getBasePtr(), DAG);
+  BaseIndexOffset BasePtr = BaseIndexOffset::match(St, DAG);
   EVT MemVT = St->getMemoryVT();
 
   SDValue Val = peekThroughBitcast(St->getValue());
   // We must have a base and an offset.
   if (!BasePtr.getBase().getNode())
     return;
 
   // Do not handle stores to undef base pointers.
   if (BasePtr.getBase().isUndef())
     return;
 
   bool IsConstantSrc = isa<ConstantSDNode>(Val) || isa<ConstantFPSDNode>(Val);
   bool IsExtractVecSrc = (Val.getOpcode() == ISD::EXTRACT_VECTOR_ELT ||
                           Val.getOpcode() == ISD::EXTRACT_SUBVECTOR);
   bool IsLoadSrc = isa<LoadSDNode>(Val);
   BaseIndexOffset LBasePtr;
   // Match on loadbaseptr if relevant.
   EVT LoadVT;
   if (IsLoadSrc) {
     auto *Ld = cast<LoadSDNode>(Val);
-    LBasePtr = BaseIndexOffset::match(Ld->getBasePtr(), DAG);
+    LBasePtr = BaseIndexOffset::match(Ld, DAG);
     LoadVT = Ld->getMemoryVT();
     // Load and store should be the same type.
     if (MemVT != LoadVT)
       return;
   }
   auto CandidateMatch = [&](StoreSDNode *Other, BaseIndexOffset &Ptr,
                             int64_t &Offset) -> bool {
     if (Other->isVolatile() || Other->isIndexed())
       return false;
     SDValue Val = peekThroughBitcast(Other->getValue());
     // Allow merging constants of different types as integers.
     bool NoTypeMatch = (MemVT.isInteger()) ? !MemVT.bitsEq(Other->getMemoryVT())
                                            : Other->getMemoryVT() != MemVT;
     if (IsLoadSrc) {
       if (NoTypeMatch)
         return false;
       // The Load's Base Ptr must also match
       if (LoadSDNode *OtherLd = dyn_cast<LoadSDNode>(Val)) {
-        auto LPtr = BaseIndexOffset::match(OtherLd->getBasePtr(), DAG);
+        auto LPtr = BaseIndexOffset::match(OtherLd, DAG);
         if (LoadVT != OtherLd->getMemoryVT())
           return false;
         if (!(LBasePtr.equalBaseIndex(LPtr, DAG)))
           return false;
       } else
         return false;
     }
     if (IsConstantSrc) {
       if (NoTypeMatch)
         return false;
       if (!(isa<ConstantSDNode>(Val) || isa<ConstantFPSDNode>(Val)))
         return false;
     }
     if (IsExtractVecSrc) {
       // Do not merge truncated stores here.
       if (Other->isTruncatingStore())
         return false;
       if (!MemVT.bitsEq(Val.getValueType()))
         return false;
       if (Val.getOpcode() != ISD::EXTRACT_VECTOR_ELT &&
           Val.getOpcode() != ISD::EXTRACT_SUBVECTOR)
         return false;
     }
-    Ptr = BaseIndexOffset::match(Other->getBasePtr(), DAG);
+    Ptr = BaseIndexOffset::match(Other, DAG);
     return (BasePtr.equalBaseIndex(Ptr, DAG, Offset));
   };
 
   // We looking for a root node which is an ancestor to all mergable
   // stores. We search up through a load, to our root and then down
   // through all children. For instance we will find Store{1,2,3} if
   // St is Store1, Store2. or Store3 where the root is not a load
   // which always true for nonvolatile ops. TODO: Expand
for (unsigned i = 0; i < NumConsecutiveStores; ++i) {
       // The memory operands must not be volatile.
       if (Ld->isVolatile() || Ld->isIndexed())
         break;
 
       // The stored memory type must be the same.
       if (Ld->getMemoryVT() != MemVT)
         break;
 
-      BaseIndexOffset LdPtr = BaseIndexOffset::match(Ld->getBasePtr(), DAG);
+      BaseIndexOffset LdPtr = BaseIndexOffset::match(Ld, DAG);
       // If this is not the first ptr that we check.
       int64_t LdOffset = 0;
       if (LdBasePtr.getBase().getNode()) {
         // The base ptr must be the same.
         if (!LdBasePtr.equalBaseIndex(LdPtr, DAG, LdOffset))
           break;
       } else {
         // Check that all other base pointers are the same as this one.
if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(Value)) {
     }
   }
 
   // Deal with elidable overlapping chained stores.
   if (StoreSDNode *ST1 = dyn_cast<StoreSDNode>(Chain))
     if (OptLevel != CodeGenOpt::None && ST->isUnindexed() &&
         ST1->isUnindexed() && !ST1->isVolatile() && ST1->hasOneUse() &&
         !ST1->getBasePtr().isUndef() && !ST->isVolatile()) {
-      BaseIndexOffset STBasePtr = BaseIndexOffset::match(ST->getBasePtr(), DAG);
-      BaseIndexOffset ST1BasePtr =
-          BaseIndexOffset::match(ST1->getBasePtr(), DAG);
+      BaseIndexOffset STBasePtr  = BaseIndexOffset::match(ST, DAG);
+      BaseIndexOffset ST1BasePtr = BaseIndexOffset::match(ST1, DAG);
       unsigned STBytes = ST->getMemoryVT().getStoreSize();
       unsigned ST1Bytes = ST1->getMemoryVT().getStoreSize();
       int64_t PtrDiff;
       // If this is a store who's preceeding store to a subset of the same
       // memory and no one other node is chained to that store we can
       // effectively drop the store. Do not remove stores to undef as they may
       // be used as data sinks.
 
bool DAGCombiner::isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const {
 
   if (Op1->isInvariant() && Op0->writeMem())
     return false;
 
   unsigned NumBytes0 = Op0->getMemoryVT().getStoreSize();
   unsigned NumBytes1 = Op1->getMemoryVT().getStoreSize();
 
   // Check for BaseIndexOffset matching.
-  BaseIndexOffset BasePtr0 = BaseIndexOffset::match(Op0->getBasePtr(), DAG);
-  BaseIndexOffset BasePtr1 = BaseIndexOffset::match(Op1->getBasePtr(), DAG);
+  BaseIndexOffset BasePtr0 = BaseIndexOffset::match(Op0, DAG);
+  BaseIndexOffset BasePtr1 = BaseIndexOffset::match(Op1, DAG);
   int64_t PtrDiff;
   if (BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff))
     return !((NumBytes0 <= PtrDiff) || (PtrDiff + NumBytes1 <= 0));
 
   // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be
   // able to calculate their relative offset if at least one arises
   // from an alloca. However, these allocas cannot overlap and we
   // can infer there is no alias.

 // to go from a partially-merged state to the desired final
 // fully-merged state.
 bool DAGCombiner::findBetterNeighborChains(StoreSDNode *St) {
   if (OptLevel == CodeGenOpt::None)
     return false;
 
   // This holds the base pointer, index, and the offset in bytes from the base
   // pointer.
-  BaseIndexOffset BasePtr = BaseIndexOffset::match(St->getBasePtr(), DAG);
+  BaseIndexOffset BasePtr = BaseIndexOffset::match(St, DAG);
 
   // We must have a base and an offset.
   if (!BasePtr.getBase().getNode())
     return false;
 
   // Do not handle stores to undef base pointers.
   if (BasePtr.getBase().isUndef())
     return false;
while (Index) {
     // If the chain has more than one use, then we can't reorder the mem ops.
     if (Index != St && !SDValue(Index, 0)->hasOneUse())
       break;
 
     if (Index->isVolatile() || Index->isIndexed())
       break;
 
     // Find the base pointer and offset for this memory node.
-    BaseIndexOffset Ptr = BaseIndexOffset::match(Index->getBasePtr(), DAG);
+    BaseIndexOffset Ptr = BaseIndexOffset::match(Index, DAG);
 
     // Check that the base pointer is the same as the original one.
     if (!BasePtr.equalBaseIndex(Ptr, DAG))
       break;
 
     // Walk up the chain to find the next store node, ignoring any
     // intermediate loads. Any other kind of node will halt the loop.
     SDNode *NextInChain = Index->getChain().getNode();

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

bool SelectionDAG::areNonVolatileConsecutiveLoads(LoadSDNode *LD,
   if (LD->isIndexed() || Base->isIndexed())
     return false;
   if (LD->getChain() != Base->getChain())
     return false;
   EVT VT = LD->getValueType(0);
   if (VT.getSizeInBits() / 8 != Bytes)
     return false;
 
-  SDValue Loc = LD->getOperand(1);
-  SDValue BaseLoc = Base->getOperand(1);
-
-  auto BaseLocDecomp = BaseIndexOffset::match(BaseLoc, *this);
-  auto LocDecomp = BaseIndexOffset::match(Loc, *this);
+  auto BaseLocDecomp = BaseIndexOffset::match(Base, *this);
+  auto LocDecomp = BaseIndexOffset::match(LD, *this);
 
   int64_t Offset = 0;
   if (BaseLocDecomp.equalBaseIndex(LocDecomp, *this, Offset))
     return (Dist * Bytes == Offset);
   return false;
 }
 
 /// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

if (auto *A = dyn_cast<FrameIndexSDNode>(Base))
                  MFI.getObjectOffset(A->getIndex());
           return true;
         }
   }
   return false;
 }
 
 /// Parses tree in Ptr for base, index, offset addresses.
-BaseIndexOffset BaseIndexOffset::match(SDValue Ptr, const SelectionDAG &DAG) {
+BaseIndexOffset BaseIndexOffset::match(LSBaseSDNode *N, const SelectionDAG &DAG) {
+  SDValue Ptr = N->getBasePtr();
+
   // (((B + I*M) + c)) + c ...
   SDValue Base = DAG.getTargetLoweringInfo().unwrapAddress(Ptr);
   SDValue Index = SDValue();
   int64_t Offset = 0;
   bool IsIndexSignExt = false;
 
+  // pre-inc/pre-dec ops are components of EA.
+  if (N->getAddressingMode() == ISD::PRE_INC) {
+    if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
+      Offset += C->getSExtValue();
+    else // bail out now.
+      return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
+  }
+  if (N->getAddressingMode() == ISD::PRE_DEC) {
+    if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
+      Offset -= C->getSExtValue();
+    else // bail out now.
+      return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
+  }
+
   // Consume constant adds & ors with appropriate masking.
-  while (Base->getOpcode() == ISD::ADD || Base->getOpcode() == ISD::OR) {
-    if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
+  while (true) {
+    switch (Base->getOpcode()) {
+      case ISD::OR:
         // Only consider ORs which act as adds.
-      if (Base->getOpcode() == ISD::OR &&
-          !DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue()))
+        if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1)))
+          if (DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue())) {
+            Offset += C->getSExtValue();
+            Base = Base->getOperand(0);
+            continue;
+          }
         break;
+      case ISD::ADD:
+        if (auto *C = dyn_cast<ConstantSDNode>(Base->getOperand(1))) {
           Offset += C->getSExtValue();
           Base = Base->getOperand(0);
           continue;
         }
         break;
+      case ISD::LOAD:
+      case ISD::STORE: {
+        auto *LSBase=cast<LSBaseSDNode>(Base.getNode());
+        if (LSBase->isIndexed())
+          if (auto *C = dyn_cast<ConstantSDNode>(LSBase->getOffset())) {
+            auto Off = C->getSExtValue();
+            if (LSBase->getAddressingMode() == ISD::PRE_DEC ||
+                LSBase->getAddressingMode() == ISD::POST_DEC)
+              Offset -= Off;
+            else
+              Offset += Off;
+            Base = LSBase->getBasePtr();
+            continue;
+          }
+        break;
+      }
+    }
+    // If we get here break out of the loop.
+    break;
   }
 
   if (Base->getOpcode() == ISD::ADD) {
     // TODO: The following code appears to be needless as it just
     //       bails on some Ptrs early, reducing the cases where we
     //       find equivalence. We should be able to remove this.
     // Inside a loop the current BASE pointer is calculated using an ADD and a
     // MUL instruction. In this case Base is the actual BASE pointer.

llvm/test/CodeGen/AArch64/arm64-abi-varargs.ll

 ; RUN: llc < %s -mtriple=arm64-apple-ios7.0.0 -mcpu=cyclone -enable-misched=false | FileCheck %s
 
 ; rdar://13625505
 ; Here we have 9 fixed integer arguments the 9th argument in on stack, the
 ; varargs start right after at 8-byte alignment.
 define void @fn9(i32* %a1, i32 %a2, i32 %a3, i32 %a4, i32 %a5, i32 %a6, i32 %a7, i32 %a8, i32 %a9, ...) nounwind noinline ssp {
 ; CHECK-LABEL: fn9:
 ; 9th fixed argument
 ; CHECK: ldr {{w[0-9]+}}, [sp, #64]
 ; CHECK: add [[ARGS:x[0-9]+]], sp, #72
 ; CHECK: add {{x[0-9]+}}, [[ARGS]], #8
 ; First vararg
 ; CHECK: ldr {{w[0-9]+}}, [sp, #72]
 ; Second vararg
 ; CHECK: ldr {{w[0-9]+}}, [{{x[0-9]+}}], #8
-; CHECK: add {{x[0-9]+}}, {{x[0-9]+}}, #8
 ; Third vararg
-; CHECK: ldr {{w[0-9]+}}, [{{x[0-9]+}}]
+; CHECK: ldr {{w[0-9]+}}, [{{x[0-9]+}}], #8
   %1 = alloca i32, align 4
   %2 = alloca i32, align 4
   %3 = alloca i32, align 4
   %4 = alloca i32, align 4
   %5 = alloca i32, align 4
   %6 = alloca i32, align 4
   %7 = alloca i32, align 4
   %8 = alloca i32, align 4

llvm/test/CodeGen/AArch64/swifterror.ll

 ; CHECK-APPLE: malloc
 ; CHECK-APPLE-DAG: orr [[ID:w[0-9]+]], wzr, #0x1
 ; CHECK-APPLE-DAG: add [[ARGS:x[0-9]+]], [[TMP:x[0-9]+]], #16
 ; CHECK-APPLE-DAG: strb [[ID]], [x0, #8]
 
 ; First vararg
 ; CHECK-APPLE-DAG: orr {{x[0-9]+}}, [[ARGS]], #0x8
 ; CHECK-APPLE-DAG: ldr {{w[0-9]+}}, [{{.*}}[[TMP]], #16]
-; CHECK-APPLE-DAG: add {{x[0-9]+}}, {{x[0-9]+}}, #8
 ; Second vararg
 ; CHECK-APPLE-DAG: ldr {{w[0-9]+}}, [{{x[0-9]+}}], #8
 ; CHECK-APPLE-DAG: add {{x[0-9]+}}, {{x[0-9]+}}, #16
 ; Third vararg
-; CHECK-APPLE: ldr {{w[0-9]+}}, [{{x[0-9]+}}]
+; CHECK-APPLE: ldr {{w[0-9]+}}, [{{x[0-9]+}}], #8
 
 ; CHECK-APPLE: mov x21, x0
 ; CHECK-APPLE-NOT: x21
 entry:
   %call = call i8* @malloc(i64 16)
   %call.0 = bitcast i8* %call to %swift_error*
   store %swift_error* %call.0, %swift_error** %error_ptr_ref
   %tmp = getelementptr inbounds i8, i8* %call, i64 8