diff --git a/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h b/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h --- a/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h +++ b/llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h @@ -34,19 +34,24 @@ 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 @@ -74,14 +79,12 @@ // 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; diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp --- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -480,15 +480,15 @@ /// 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 &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 @@ -15590,24 +15590,12 @@ 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(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(Chain); if (ST->isVolatile() || ST->isIndexed()) @@ -19379,40 +19367,83 @@ } /// 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 { + + 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(N)) { + int64_t Offset = 0; + if (auto *C = dyn_cast(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(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 they are both volatile then they cannot be reordered. - if (Op0->isVolatile() && Op1->isVolatile()) return true; + std::tie(BasePtr0, Offset0, IsVol0, NumBytes0, MMO0) = + getMemUseCharacteristics(Op0); + std::tie(BasePtr1, Offset1, IsVol1, NumBytes1, MMO1) = + getMemUseCharacteristics(Op1); - // 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; + // If they are to the same addressthen they must be aliases. + if (BasePtr0.getNode() && BasePtr0 == BasePtr1 && Offset0 == Offset1) + return true; - if (Op1->isInvariant() && Op0->writeMem()) - return false; + // 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; @@ -19434,17 +19465,16 @@ 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; } @@ -19472,15 +19502,13 @@ /// 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 &Aliases) { SmallVector Chains; // List of chains to visit. SmallPtrSet Visited; // Visited node set. // Get alias information for node. - bool IsLoad = isa(N) && !N->isVolatile(); - const BaseIndexOffset LSBasePtr = BaseIndexOffset::match(N, DAG); - const unsigned LSNumBytes = N->getMemoryVT().getStoreSize(); + const bool IsLoad = isa(N) && !cast(N)->isVolatile(); // Starting off. Chains.push_back(OriginalChain); @@ -19496,9 +19524,9 @@ case ISD::LOAD: case ISD::STORE: { // Get alias information for C. - auto LSChain = cast(C.getNode()); - bool IsOpLoad = isa(C.getNode()) && !LSChain->isVolatile(); - if ((IsLoad && IsOpLoad) || !isAlias(N, LSChain)) { + bool IsOpLoad = isa(C.getNode()) && + !cast(C.getNode())->isVolatile(); + if ((IsLoad && IsOpLoad) || !isAlias(N, C.getNode())) { // Look further up the chain. C = C.getOperand(0); return true; @@ -19555,16 +19583,8 @@ 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(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; } @@ -19627,7 +19647,7 @@ /// 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; diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp @@ -24,6 +24,8 @@ // 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; @@ -79,11 +81,15 @@ 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; @@ -156,7 +162,7 @@ } /// 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(); @@ -259,6 +265,19 @@ 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(N)) + return matchLSNode(LS0, DAG); + if (const auto *LN = dyn_cast(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)