[DAGCombiner] Unify Lifetime and memory Op aliasing.

[niravd]

Summary

Rework BaseIndexOffset and isAlias to fully work with lifetime nodes
and fold in lifetime alias analysis.

This is mostly NFCI.

[courbet]

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

37

What about using:

Optional<int64_t> Offset;

To avoid mistakes when handling IsOffsetValid ?

80

s/BasePtr0/Op0/

86

s/Ptr/N/

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

19374

why = 0 ? For consistency, it would be better to use it on all variables or none.

19378

Please do not use implicit capture. It makes things harder to reason about. In particular, here, it hides the fact that there is actually no capture.

19394

please add a comment to explain ~0.
The original code had // Be conservative if we don't know the extents of the object.

Actually I'm not sure how the new code ensures that we never return true for isAlias, because the large size only means that we're saying that the lifetime aliases all memory after the base ptr, not before.

19402

Easier to read in my opinion:

struct MemUseCharacteristics {
  SDValue BasePtr;
  int64_t Offset = 0;
  unsigned NumBytes = 0;
  MachineMemOperand* MMO = nullptr;
  bool IsVolatile = false;
};

auto getMemUseCharacteristics = [](SDNode *N) -> MemUseCharacteristics {
  ...
  if (const auto *LN = cast<LifetimeSDNode>(N))
      return {LN->getOperand(1),
                             LN->hasOffset() ? LN->getOffset() : 0,
                             LN->hasOffset() ? LN->getSize() : ~0,
                             nullptr, false /*isVolatile*/);
  return {};
}

const MemUseCharacteristics MUC0 = getMemUseCharacteristics(Op0);
const MemUseCharacteristics MUC1 = getMemUseCharacteristics(Op1);

19432

BTW:
I'm not sure about this. For example, can we always reorder two writes of different values to invariant memory ? IIUC isInvariant() is about reading, but I could see some cases (e.g. hardware control) where invariant memory cares about write ordering.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

268

I don't get the comment.

270

please clang-format the patch.

[niravd]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

19432

We shouldn't have to worry about semantically non-standard memory call like hardware control should be volatile already which precludes most alias improvements.

[niravd]

Address comments.

[niravd]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

19394

I've wrapped it in an optional as we conservatively never use the size without the offset.

[courbet]

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

36–37

Maybe remove = 0 ?

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

 ///
 /// (load (i64 add (i64 copyfromreg %c)
 ///                (i64 signextend (i32 add (i32 signextend (i8 load %index))
 ///                                         (i32 1)))))
 class BaseIndexOffset {
 private:
   SDValue Base;
   SDValue Index;
   int64_t Offset = 0;
+  bool IsOffsetValid = false;
   bool IsIndexSignExt = false;
 
 public:
   BaseIndexOffset() = default;
+  BaseIndexOffset(SDValue Base, SDValue Index, bool IsIndexSignExt)
+      : Base(Base), Index(Index), Offset(0), IsOffsetValid(false),
+        IsIndexSignExt(IsIndexSignExt) {}
   BaseIndexOffset(SDValue Base, SDValue Index, int64_t Offset,
                   bool IsIndexSignExt)
-      : Base(Base), Index(Index), Offset(Offset),
+      : Base(Base), Index(Index), Offset(Offset), IsOffsetValid(true),
         IsIndexSignExt(IsIndexSignExt) {}
 
   SDValue getBase() { return Base; }
   SDValue getBase() const { return Base; }
   SDValue getIndex() { return Index; }
   SDValue getIndex() const { return Index; }
+  bool hasValidOffset() const { return IsOffsetValid; }
 
   // Returns true if `Other` and `*this` are both some offset from the same base
   // pointer. In that case, `Off` is set to the offset between `*this` and
   // `Other` (negative if `Other` is before `*this`).
   bool equalBaseIndex(const BaseIndexOffset &Other, const SelectionDAG &DAG,
                       int64_t &Off) const;
 
   bool equalBaseIndex(const BaseIndexOffset &Other,
bool contains(const SelectionDAG &DAG, int64_t BitSize,
                 int64_t &BitOffset) const;
 
   bool contains(const SelectionDAG &DAG, int64_t BitSize,
                 const BaseIndexOffset &Other, int64_t OtherBitSize) const {
     int64_t BitOffset;
     return contains(DAG, BitSize, Other, OtherBitSize, BitOffset);
   }
 
   // Returns true `BasePtr0` and `BasePtr1` can be proven to alias/not alias, in
   // which case `IsAlias` is set to true/false.
-  static bool computeAliasing(const BaseIndexOffset &BasePtr0,
-                              const int64_t NumBytes0,
-                              const BaseIndexOffset &BasePtr1,
-                              const int64_t NumBytes1, const SelectionDAG &DAG,
-                              bool &IsAlias);
+  static bool computeAliasing(const SDNode *Op0, const int64_t NumBytes0,
+                              const SDNode *Op1, const int64_t NumBytes1,
+                              const SelectionDAG &DAG, bool &IsAlias);
 
   /// Parses tree in Ptr for base, index, offset addresses.
-  static BaseIndexOffset match(const LSBaseSDNode *N, const SelectionDAG &DAG);
+  static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG);
 
   void print(raw_ostream& OS) const;
   void dump() const;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_SELECTIONDAGADDRESSANALYSIS_H

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

private:
     SDValue reduceBuildVecToShuffle(SDNode *N);
     SDValue createBuildVecShuffle(const SDLoc &DL, SDNode *N,
                                   ArrayRef<int> VectorMask, SDValue VecIn1,
                                   SDValue VecIn2, unsigned LeftIdx);
     SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
 
     /// Walk up chain skipping non-aliasing memory nodes,
     /// looking for aliasing nodes and adding them to the Aliases vector.
-    void GatherAllAliases(LSBaseSDNode *N, SDValue OriginalChain,
+    void GatherAllAliases(SDNode *N, SDValue OriginalChain,
                           SmallVectorImpl<SDValue> &Aliases);
 
     /// Return true if there is any possibility that the two addresses overlap.
-    bool isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const;
+    bool isAlias(SDNode *Op0, SDNode *Op1) const;
 
     /// Walk up chain skipping non-aliasing memory nodes, looking for a better
     /// chain (aliasing node.)
-    SDValue FindBetterChain(LSBaseSDNode *N, SDValue Chain);
+    SDValue FindBetterChain(SDNode *N, SDValue Chain);
 
     /// Try to replace a store and any possibly adjacent stores on
     /// consecutive chains with better chains. Return true only if St is
     /// replaced.
     ///
     /// Notice that other chains may still be replaced even if the function
     /// returns false.
     bool findBetterNeighborChains(StoreSDNode *St);
while (!Chains.empty()) {
     if (!Chain.hasOneUse())
       continue;
     switch (Chain.getOpcode()) {
     case ISD::TokenFactor:
       for (unsigned Nops = Chain.getNumOperands(); Nops;)
         Chains.push_back(Chain.getOperand(--Nops));
       break;
     case ISD::LIFETIME_START:
-    case ISD::LIFETIME_END: {
+    case ISD::LIFETIME_END:
       // We can forward past any lifetime start/end that can be proven not to
       // alias the node.
-      const auto *Lifetime = cast<LifetimeSDNode>(Chain);
-      if (!Lifetime->hasOffset())
-        break; // Be conservative if we don't know the extents of the object.
-
-      const BaseIndexOffset LifetimeBase(Lifetime->getOperand(1), SDValue(),
-                                         Lifetime->getOffset(), false);
-      bool IsAlias;
-      if (BaseIndexOffset::computeAliasing(LifetimeEndBase,
-                                           LifetimeEnd->getSize(), LifetimeBase,
-                                           Lifetime->getSize(), DAG, IsAlias) &&
-          !IsAlias) {
+      if (!isAlias(Chain.getNode(), N))
         Chains.push_back(Chain.getOperand(0));
-      }
       break;
-    }
     case ISD::STORE: {
       StoreSDNode *ST = dyn_cast<StoreSDNode>(Chain);
       if (ST->isVolatile() || ST->isIndexed())
         continue;
       const BaseIndexOffset StoreBase = BaseIndexOffset::match(ST, DAG);
       // If we store purely within object bounds just before its lifetime ends,
       // we can remove the store.
       if (LifetimeEndBase.contains(DAG, LifetimeEnd->getSize() * 8, StoreBase,
SDValue DAGCombiner::buildRsqrtEstimate(SDValue Op, SDNodeFlags Flags) {
   return buildSqrtEstimateImpl(Op, Flags, true);
 }
 
 SDValue DAGCombiner::buildSqrtEstimate(SDValue Op, SDNodeFlags Flags) {
   return buildSqrtEstimateImpl(Op, Flags, false);
 }
 
 /// Return true if there is any possibility that the two addresses overlap.
-bool DAGCombiner::isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const {
-  // If they are the same then they must be aliases.
-  if (Op0->getBasePtr() == Op1->getBasePtr()) return true;
+bool DAGCombiner::isAlias(SDNode *Op0, SDNode *Op1) const {
 
-  // If they are both volatile then they cannot be reordered.
-  if (Op0->isVolatile() && Op1->isVolatile()) return true;
+  SDValue BasePtr0, BasePtr1;
+  int64_t Offset0, Offset1;
+  unsigned NumBytes0 = 0, NumBytes1 = 0;
+  MachineMemOperand *MMO0, *MMO1;
+  bool IsVol0, IsVol1;
+
+  auto getMemUseCharacteristics = [&](SDNode *N) {
+    if (const auto *LSN = dyn_cast<LSBaseSDNode>(N)) {
+      int64_t Offset = 0;
+      if (auto *C = dyn_cast<ConstantSDNode>(LSN->getOffset()))
+        Offset = (LSN->getAddressingMode() == ISD::PRE_INC)
+                     ? C->getSExtValue()
+                     : (LSN->getAddressingMode() == ISD::PRE_DEC)
+                           ? -1 * C->getSExtValue()
+                           : 0;
+      return std::make_tuple(
+          LSN->getBasePtr(), Offset /*base offset*/, LSN->isVolatile(),
+          LSN->getMemoryVT().getStoreSize(), LSN->getMemOperand());
+    }
+    if (const auto *LN = cast<LifetimeSDNode>(N))
+      return std::make_tuple(LN->getOperand(1),
+                             (LN->hasOffset()) ? LN->getOffset() : 0,
+                             false /*isVolatile*/, (LN->hasOffset()) ? (unsigned)LN->getSize() : (~0),
+                             (MachineMemOperand *)nullptr);
+    // Default.
+    return std::make_tuple(SDValue(), (int64_t)0 /*offset*/,
+                           false /*isvolatile*/, (unsigned)0 /*size*/,
+                           (MachineMemOperand *)nullptr);
+  };
 
-  // If one operation reads from invariant memory, and the other may store, they
-  // cannot alias. These should really be checking the equivalent of mayWrite,
-  // but it only matters for memory nodes other than load /store.
-  if (Op0->isInvariant() && Op1->writeMem())
-    return false;
+  std::tie(BasePtr0, Offset0, IsVol0, NumBytes0, MMO0) =
+      getMemUseCharacteristics(Op0);
+  std::tie(BasePtr1, Offset1, IsVol1, NumBytes1, MMO1) =
+      getMemUseCharacteristics(Op1);
 
-  if (Op1->isInvariant() && Op0->writeMem())
-    return false;
+  // If they are to the same addressthen they must be aliases.
+  if (BasePtr0.getNode() && BasePtr0 == BasePtr1 && Offset0 == Offset1)
+    return true;
+
+  // If they are both volatile then they cannot be reordered.
+  if (IsVol0 && IsVol1)
+    return true;
 
-  unsigned NumBytes0 = Op0->getMemoryVT().getStoreSize();
-  unsigned NumBytes1 = Op1->getMemoryVT().getStoreSize();
+  if (MMO0 && MMO1) {
+    if ((MMO0->isInvariant() && MMO1->isStore()) ||
+        (MMO1->isInvariant() && MMO0->isStore()))
+      return false;
+  }
 
-  // Check for BaseIndexOffset matching.
   bool IsAlias;
-  if (BaseIndexOffset::computeAliasing(
-          BaseIndexOffset::match(Op0, DAG), NumBytes0,
-          BaseIndexOffset::match(Op1, DAG), NumBytes1, DAG, IsAlias))
+  if (BaseIndexOffset::computeAliasing(Op0, NumBytes0, Op1, NumBytes1, DAG,
+                                       IsAlias) &&
+      !IsAlias)
     return IsAlias;
 
+  // The following all rely on MMO0 and MMO1 being valid. Fail conservatively if
+  // either are not known.
+  if (!MMO0 || !MMO1)
+    return true;
+
+  // If one operation reads from invariant memory, and the other may store, they
+  // cannot alias. These should really be checking the equivalent of mayWrite,
+  // but it only matters for memory nodes other than load /store.
+  if ((MMO0->isInvariant() && MMO1->isStore()) ||
+      (MMO1->isInvariant() && MMO0->isStore()))
+    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.
-  int64_t SrcValOffset0 = Op0->getSrcValueOffset();
-  int64_t SrcValOffset1 = Op1->getSrcValueOffset();
-  unsigned OrigAlignment0 = Op0->getOriginalAlignment();
-  unsigned OrigAlignment1 = Op1->getOriginalAlignment();
+  int64_t SrcValOffset0 = MMO0->getOffset();
+  int64_t SrcValOffset1 = MMO1->getOffset();
+  unsigned OrigAlignment0 = MMO0->getBaseAlignment();
+  unsigned OrigAlignment1 = MMO1->getBaseAlignment();
   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.
     if ((OffAlign0 + NumBytes0) <= OffAlign1 ||
         (OffAlign1 + NumBytes1) <= OffAlign0)
       return false;
   }
 
   bool UseAA = CombinerGlobalAA.getNumOccurrences() > 0
                    ? CombinerGlobalAA
                    : DAG.getSubtarget().useAA();
 #ifndef NDEBUG
   if (CombinerAAOnlyFunc.getNumOccurrences() &&
       CombinerAAOnlyFunc != DAG.getMachineFunction().getName())
     UseAA = false;
 #endif
 
-  if (UseAA && AA &&
-      Op0->getMemOperand()->getValue() && Op1->getMemOperand()->getValue()) {
+  if (UseAA && AA && MMO0->getValue() && MMO1->getValue()) {
     // Use alias analysis information.
     int64_t MinOffset = std::min(SrcValOffset0, SrcValOffset1);
     int64_t Overlap0 = NumBytes0 + SrcValOffset0 - MinOffset;
     int64_t Overlap1 = NumBytes1 + SrcValOffset1 - MinOffset;
     AliasResult AAResult =
-        AA->alias(MemoryLocation(Op0->getMemOperand()->getValue(), Overlap0,
-                                 UseTBAA ? Op0->getAAInfo() : AAMDNodes()),
-                  MemoryLocation(Op1->getMemOperand()->getValue(), Overlap1,
-                                 UseTBAA ? Op1->getAAInfo() : AAMDNodes()) );
+        AA->alias(MemoryLocation(MMO0->getValue(), Overlap0,
+                                 UseTBAA ? MMO0->getAAInfo() : AAMDNodes()),
+                  MemoryLocation(MMO1->getValue(), Overlap1,
+                                 UseTBAA ? MMO1->getAAInfo() : AAMDNodes()));
     if (AAResult == NoAlias)
       return false;
   }
 
   // Otherwise we have to assume they alias.
   return true;
 }
 
static bool hasGluedOutput(SDNode *N) {
   auto LastValNo = N->getNumValues() - 1;
   bool hasChainOut = N->getValueType(LastValNo - 1) == MVT::Other;
   bool hasGlueOut = N->getValueType(LastValNo) == MVT::Glue;
   return hasChainOut && hasGlueOut;
 }
 
 /// Walk up chain skipping non-aliasing memory nodes,
 /// looking for aliasing nodes and adding them to the Aliases vector.
-void DAGCombiner::GatherAllAliases(LSBaseSDNode *N, SDValue OriginalChain,
+void DAGCombiner::GatherAllAliases(SDNode *N, SDValue OriginalChain,
                                    SmallVectorImpl<SDValue> &Aliases) {
   SmallVector<SDValue, 8> Chains;     // List of chains to visit.
   SmallPtrSet<SDNode *, 16> Visited;  // Visited node set.
 
   // Get alias information for node.
-  bool IsLoad = isa<LoadSDNode>(N) && !N->isVolatile();
-  const BaseIndexOffset LSBasePtr = BaseIndexOffset::match(N, DAG);
-  const unsigned LSNumBytes = N->getMemoryVT().getStoreSize();
+  const bool IsLoad = isa<LoadSDNode>(N) && !cast<LoadSDNode>(N)->isVolatile();
 
   // Starting off.
   Chains.push_back(OriginalChain);
   unsigned Depth = 0;
 
   // Attempt to improve chain by a single step
   std::function<bool(SDValue &)> ImproveChain = [&](SDValue &C) -> bool {
     switch (C.getOpcode()) {
     case ISD::EntryToken:
       // No need to mark EntryToken.
       C = SDValue();
       return true;
     case ISD::LOAD:
     case ISD::STORE: {
       // Get alias information for C.
-      auto LSChain = cast<LSBaseSDNode>(C.getNode());
-      bool IsOpLoad = isa<LoadSDNode>(C.getNode()) && !LSChain->isVolatile();
-      if ((IsLoad && IsOpLoad) || !isAlias(N, LSChain)) {
+      bool IsOpLoad = isa<LoadSDNode>(C.getNode()) &&
+                      !cast<LSBaseSDNode>(C.getNode())->isVolatile();
+      if ((IsLoad && IsOpLoad) || !isAlias(N, C.getNode())) {
         // Look further up the chain.
         C = C.getOperand(0);
         return true;
       }
       // Alias, so stop here.
       return false;
     }
 
case ISD::INLINEASM: {
       }
       return false;
     }
 
     case ISD::LIFETIME_START:
     case ISD::LIFETIME_END: {
       // We can forward past any lifetime start/end that can be proven not to
       // alias the memory access.
-      const auto *Lifetime = cast<LifetimeSDNode>(C);
-      if (!Lifetime->hasOffset())
-        return false; // Be conservative if we don't know the extents of the object.
-
-      const BaseIndexOffset LifetimePtr(Lifetime->getOperand(1), SDValue(),
-                                        Lifetime->getOffset(), false);
-      bool IsAlias;
-      if (BaseIndexOffset::computeAliasing(LifetimePtr, Lifetime->getSize(),
-                                           LSBasePtr, LSNumBytes, DAG,
-                                           IsAlias) && !IsAlias) {
+      if (!isAlias(N, C.getNode())) {
+        // Look further up the chain.
         C = C.getOperand(0);
         return true;
       }
       return false;
     }
 
     default:
       return false;
while (!Chains.empty()) {
     }
     // No Improved Chain Possible, treat as Alias.
     Aliases.push_back(Chain);
   }
 }
 
 /// Walk up chain skipping non-aliasing memory nodes, looking for a better chain
 /// (aliasing node.)
-SDValue DAGCombiner::FindBetterChain(LSBaseSDNode *N, SDValue OldChain) {
+SDValue DAGCombiner::FindBetterChain(SDNode *N, SDValue OldChain) {
   if (OptLevel == CodeGenOpt::None)
     return OldChain;
 
   // Ops for replacing token factor.
   SmallVector<SDValue, 8> Aliases;
 
   // Accumulate all the aliases to this node.
   GatherAllAliases(N, OldChain, Aliases);

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

 using namespace llvm;
 
 bool BaseIndexOffset::equalBaseIndex(const BaseIndexOffset &Other,
                                      const SelectionDAG &DAG,
                                      int64_t &Off) const {
   // Conservatively fail if we a match failed..
   if (!Base.getNode() || !Other.Base.getNode())
     return false;
+  if (!hasValidOffset() || !Other.hasValidOffset())
+    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;
 }
 
-bool BaseIndexOffset::computeAliasing(const BaseIndexOffset &BasePtr0,
+bool BaseIndexOffset::computeAliasing(const SDNode *Op0,
                                       const int64_t NumBytes0,
-                                      const BaseIndexOffset &BasePtr1,
+                                      const SDNode *Op1,
                                       const int64_t NumBytes1,
                                       const SelectionDAG &DAG, bool &IsAlias) {
+
+  BaseIndexOffset BasePtr0 = match(Op0, DAG);
+  BaseIndexOffset BasePtr1 = match(Op1, DAG);
+
   if (!(BasePtr0.getBase().getNode() && BasePtr1.getBase().getNode()))
     return false;
   int64_t PtrDiff;
   if (BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) {
     // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the
     // following situations arise:
     IsAlias = !(
         // [----BasePtr0----]
bool BaseIndexOffset::contains(const SelectionDAG &DAG, int64_t BitSize,
   }
   // Other starts strictly before *this, it cannot be fully contained.
   //    [-------*this---------]
   // [--Other--]
   return false;
 }
 
 /// Parses tree in Ptr for base, index, offset addresses.
-BaseIndexOffset BaseIndexOffset::match(const LSBaseSDNode *N,
+static BaseIndexOffset matchLSNode(const 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;
if (Index->getOpcode() == ISD::SIGN_EXTEND) {
       IsIndexSignExt = true;
     } else
       IsIndexSignExt = false;
     Base = PotentialBase;
   }
   return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt);
 }
 
+// returns boolean if offset is meaningful.
+BaseIndexOffset BaseIndexOffset::match(const SDNode *N,
+                             const SelectionDAG &DAG) {
+  if (const auto *LS0 = dyn_cast<LSBaseSDNode>(N))
+    return matchLSNode(LS0, DAG);
+  if (const auto *LN = dyn_cast<LifetimeSDNode>(N)) {
+    if (LN->hasOffset())
+      return BaseIndexOffset(LN->getOperand(1), SDValue(), LN->getOffset(),
+                             false);
+    return BaseIndexOffset(LN->getOperand(1), SDValue(), false);
+  }
+  return BaseIndexOffset();
+}
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 
 LLVM_DUMP_METHOD void BaseIndexOffset::dump() const {
   print(dbgs());
 }
 
 void BaseIndexOffset::print(raw_ostream& OS) const {