Index: llvm/trunk/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h +++ llvm/trunk/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h @@ -33,11 +33,13 @@ private: SDValue Base; SDValue Index; - int64_t Offset = 0; + Optional Offset; bool IsIndexSignExt = false; public: BaseIndexOffset() = default; + BaseIndexOffset(SDValue Base, SDValue Index, bool IsIndexSignExt) + : Base(Base), Index(Index), Offset(), IsIndexSignExt(IsIndexSignExt) {} BaseIndexOffset(SDValue Base, SDValue Index, int64_t Offset, bool IsIndexSignExt) : Base(Base), Index(Index), Offset(Offset), @@ -47,6 +49,7 @@ SDValue getBase() const { return Base; } SDValue getIndex() { return Index; } SDValue getIndex() const { return Index; } + bool hasValidOffset() const { return Offset.hasValue(); } // 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 @@ -72,16 +75,16 @@ return contains(DAG, BitSize, Other, OtherBitSize, BitOffset); } - // Returns true `BasePtr0` and `BasePtr1` can be proven to alias/not alias, in + // Returns true `Op0` and `Op1` 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 Optional NumBytes0, + const SDNode *Op1, + const Optional NumBytes1, + const SelectionDAG &DAG, bool &IsAlias); - /// Parses tree in Ptr for base, index, offset addresses. - static BaseIndexOffset match(const LSBaseSDNode *N, const SelectionDAG &DAG); + /// Parses tree in N for base, index, offset addresses. + static BaseIndexOffset match(const SDNode *N, const SelectionDAG &DAG); void print(raw_ostream& OS) const; void dump() const; Index: llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp =================================================================== --- llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp +++ llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp @@ -481,15 +481,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 @@ -15652,24 +15652,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()) @@ -19411,49 +19399,94 @@ } /// 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; + struct MemUseCharacteristics { + bool IsVolatile; + SDValue BasePtr; + int64_t Offset; + Optional NumBytes; + MachineMemOperand *MMO; + }; - // 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; + auto getCharacteristics = [](SDNode *N) -> MemUseCharacteristics { + 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 {LSN->isVolatile(), LSN->getBasePtr(), Offset /*base offset*/, + Optional(LSN->getMemoryVT().getStoreSize()), + LSN->getMemOperand()}; + } + if (const auto *LN = cast(N)) + return {false /*isVolatile*/, LN->getOperand(1), + (LN->hasOffset()) ? LN->getOffset() : 0, + (LN->hasOffset()) ? Optional(LN->getSize()) + : Optional(), + (MachineMemOperand *)nullptr}; + // Default. + return {false /*isvolatile*/, SDValue(), (int64_t)0 /*offset*/, + Optional() /*size*/, (MachineMemOperand *)nullptr}; + }; - if (Op1->isInvariant() && Op0->writeMem()) - return false; + MemUseCharacteristics MUC0 = getCharacteristics(Op0), + MUC1 = getCharacteristics(Op1); + + // If they are to the same address, then they must be aliases. + if (MUC0.BasePtr.getNode() && MUC0.BasePtr == MUC1.BasePtr && + MUC0.Offset == MUC1.Offset) + return true; - unsigned NumBytes0 = Op0->getMemoryVT().getStoreSize(); - unsigned NumBytes1 = Op1->getMemoryVT().getStoreSize(); + // If they are both volatile then they cannot be reordered. + if (MUC0.IsVolatile && MUC1.IsVolatile) + return true; + + if (MUC0.MMO && MUC1.MMO) { + if ((MUC0.MMO->isInvariant() && MUC1.MMO->isStore()) || + (MUC1.MMO->isInvariant() && MUC0.MMO->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, MUC0.NumBytes, Op1, MUC1.NumBytes, + DAG, IsAlias) && + !IsAlias) return IsAlias; + // The following all rely on MMO0 and MMO1 being valid. Fail conservatively if + // either are not known. + if (!MUC0.MMO || !MUC1.MMO) + 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 ((MUC0.MMO->isInvariant() && MUC1.MMO->isStore()) || + (MUC1.MMO->isInvariant() && MUC0.MMO->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 = MUC0.MMO->getOffset(); + int64_t SrcValOffset1 = MUC1.MMO->getOffset(); + unsigned OrigAlignment0 = MUC0.MMO->getBaseAlignment(); + unsigned OrigAlignment1 = MUC1.MMO->getBaseAlignment(); if (OrigAlignment0 == OrigAlignment1 && SrcValOffset0 != SrcValOffset1 && - NumBytes0 == NumBytes1 && OrigAlignment0 > NumBytes0) { + MUC0.NumBytes.hasValue() && MUC1.NumBytes.hasValue() && + *MUC0.NumBytes == *MUC1.NumBytes && OrigAlignment0 > *MUC0.NumBytes) { 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) + if ((OffAlign0 + *MUC0.NumBytes) <= OffAlign1 || + (OffAlign1 + *MUC1.NumBytes) <= OffAlign0) return false; } @@ -19466,17 +19499,16 @@ UseAA = false; #endif - if (UseAA && AA && - Op0->getMemOperand()->getValue() && Op1->getMemOperand()->getValue()) { + if (UseAA && AA && MUC0.MMO->getValue() && MUC1.MMO->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()) ); + int64_t Overlap0 = *MUC0.NumBytes + SrcValOffset0 - MinOffset; + int64_t Overlap1 = *MUC1.NumBytes + SrcValOffset1 - MinOffset; + AliasResult AAResult = AA->alias( + MemoryLocation(MUC0.MMO->getValue(), Overlap0, + UseTBAA ? MUC0.MMO->getAAInfo() : AAMDNodes()), + MemoryLocation(MUC1.MMO->getValue(), Overlap1, + UseTBAA ? MUC1.MMO->getAAInfo() : AAMDNodes())); if (AAResult == NoAlias) return false; } @@ -19487,15 +19519,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); @@ -19511,9 +19541,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; @@ -19531,16 +19561,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; } @@ -19602,7 +19624,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; Index: llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp =================================================================== --- llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp +++ llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp @@ -24,8 +24,10 @@ // 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; + Off = *Other.Offset - *Offset; if ((Other.Index == Index) && (Other.IsIndexSignExt == IsIndexSignExt)) { // Trivial match. @@ -79,26 +81,31 @@ return false; } -bool BaseIndexOffset::computeAliasing(const BaseIndexOffset &BasePtr0, - const int64_t NumBytes0, - const BaseIndexOffset &BasePtr1, - const int64_t NumBytes1, +bool BaseIndexOffset::computeAliasing(const SDNode *Op0, + const Optional NumBytes0, + const SDNode *Op1, + const Optional 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)) { + if (NumBytes0.hasValue() && NumBytes1.hasValue() && + BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) { // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the // following situations arise: IsAlias = !( // [----BasePtr0----] // [---BasePtr1--] // ========PtrDiff========> - (NumBytes0 <= PtrDiff) || + (*NumBytes0 <= PtrDiff) || // [----BasePtr0----] // [---BasePtr1--] // =====(-PtrDiff)====> - (PtrDiff + NumBytes1 <= 0)); // i.e. NumBytes1 < -PtrDiff. + (PtrDiff + *NumBytes1 <= 0)); // i.e. *NumBytes1 < -PtrDiff. return true; } // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be @@ -156,8 +163,8 @@ } /// Parses tree in Ptr for base, index, offset addresses. -BaseIndexOffset BaseIndexOffset::match(const LSBaseSDNode *N, - const SelectionDAG &DAG) { +static BaseIndexOffset matchLSNode(const LSBaseSDNode *N, + const SelectionDAG &DAG) { SDValue Ptr = N->getBasePtr(); // (((B + I*M) + c)) + c ... @@ -259,6 +266,18 @@ return BaseIndexOffset(Base, Index, Offset, IsIndexSignExt); } +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)