[DAG] Teach BaseIndexOffset to correctly handle with indexed operations

[niravd]

Summary

BaseIndexOffset address analysis incorrectly ignores offsets folded
into indexed memory operations causing potential errors in alias
analysis of pre-indexed operations.

[efriedma]

I would prefer to have a regression test, but it's okay if you can't come up with a way to write one.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

90 ↗

(On Diff #128521)

Does this need to be something like "BaseIndexOffset(Base, N->getOffset(), 0, false);"? Currently, it looks like this code is discarding the increment.

[niravd]

Correct failing on non-constant indices.

[niravd]

In D41701#966881, @efriedma wrote:

I would prefer to have a regression test, but it's okay if you can't come up with a way to write one.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

90 ↗

(On Diff #128521)

Good catch. This won't work on pre-decrement though as we'd need the negated index. I've changed it to mark such cases as returning no information and modifying other uses to check for a null base.

[efriedma]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13360 ↗

(On Diff #128771)

Does this null check still work properly given that BaseIndexOffset::match can return a null base?

[niravd]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13360 ↗

(On Diff #128771)

The indexed check @ line 13350 precludes the new case from happening here.

[efriedma]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

13360 ↗

(On Diff #128771)

Oh, I see.

llvm/trunk/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/trunk/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.
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.getBase().getNode() && BasePtr1.getBase().getNode()) {
     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.
     if (auto *A = dyn_cast<FrameIndexSDNode>(BasePtr0.getBase()))
       if (auto *B = dyn_cast<FrameIndexSDNode>(BasePtr1.getBase())) {
         MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
         // If the base are the same frame index but the we couldn't find a
         // constant offset, (indices are different) be conservative.
         if (A != B && (!MFI.isFixedObjectIndex(A->getIndex()) ||
                        !MFI.isFixedObjectIndex(B->getIndex())))
           return false;
       }
 
     bool IsFI0 = isa<FrameIndexSDNode>(BasePtr0.getBase());
     bool IsFI1 = isa<FrameIndexSDNode>(BasePtr1.getBase());
     bool IsGV0 = isa<GlobalAddressSDNode>(BasePtr0.getBase());
     bool IsGV1 = isa<GlobalAddressSDNode>(BasePtr1.getBase());
     bool IsCV0 = isa<ConstantPoolSDNode>(BasePtr0.getBase());
     bool IsCV1 = isa<ConstantPoolSDNode>(BasePtr1.getBase());
 
     // If of mismatched base types or checkable indices we can check
     // they do not alias.
     if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) ||
          (IsGV0 != IsGV1) || (IsCV0 != IsCV1)) &&
         (IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1))
       return false;
+  }
 
-  // If we know required SrcValue1 and SrcValue2 have relatively large alignment
-  // compared to the size and offset of the access, we may be able to prove they
-  // do not alias. This check is conservative for now to catch cases created by
-  // splitting vector types.
+  // If we know required SrcValue1 and SrcValue2 have relatively large
+  // alignment compared to the size and offset of the access, we may be able
+  // to prove they do not alias. This check is conservative for now to catch
+  // cases created by splitting vector types.
   int64_t SrcValOffset0 = Op0->getSrcValueOffset();
   int64_t SrcValOffset1 = Op1->getSrcValueOffset();
   unsigned OrigAlignment0 = Op0->getOriginalAlignment();
   unsigned OrigAlignment1 = Op1->getOriginalAlignment();
   if (OrigAlignment0 == OrigAlignment1 && SrcValOffset0 != SrcValOffset1 &&
       NumBytes0 == NumBytes1 && OrigAlignment0 > NumBytes0) {
     int64_t OffAlign0 = SrcValOffset0 % OrigAlignment0;
     int64_t OffAlign1 = SrcValOffset1 % OrigAlignment1;
 
-    // There is no overlap between these relatively aligned accesses of similar
-    // size. Return no alias.
+    // There is no overlap between these relatively aligned accesses of
+    // similar size. Return no alias.
     if ((OffAlign0 + NumBytes0) <= OffAlign1 ||
         (OffAlign1 + NumBytes1) <= OffAlign0)
       return false;
   }
 
   bool UseAA = CombinerGlobalAA.getNumOccurrences() > 0
                    ? CombinerGlobalAA
                    : DAG.getSubtarget().useAA();

 // 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/trunk/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/trunk/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/Support/Casting.h"
 #include <cstdint>
 
 using namespace llvm;
 
 bool BaseIndexOffset::equalBaseIndex(BaseIndexOffset &Other,
                                      const SelectionDAG &DAG, int64_t &Off) {
+  // Conservatively fail if we a match failed..
+  if (!Base.getNode() || !Other.Base.getNode())
+    return false;
   // Initial Offset difference.
   Off = Other.Offset - Offset;
 
   if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) {
     // Trivial match.
     if (Other.Base == Base)
       return true;
 
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 // If unknown, give up now.
+      return BaseIndexOffset(SDValue(), SDValue(), 0, false);
+  } else if (N->getAddressingMode() == ISD::PRE_DEC) {
+    if (auto *C = dyn_cast<ConstantSDNode>(N->getOffset()))
+      Offset -= C->getSExtValue();
+    else // If unknown, give up now.
+      return BaseIndexOffset(SDValue(), SDValue(), 0, false);
+  }
+
   // 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))) {
       // Only consider ORs which act as adds.
       if (Base->getOpcode() == ISD::OR &&
           !DAG.MaskedValueIsZero(Base->getOperand(0), C->getAPIntValue()))
         break;
       Offset += C->getSExtValue();