Index: llvm/include/llvm/Analysis/Delinearization.h =================================================================== --- llvm/include/llvm/Analysis/Delinearization.h +++ llvm/include/llvm/Analysis/Delinearization.h @@ -125,6 +125,15 @@ SmallVectorImpl &Subscripts, SmallVectorImpl &Sizes); +/// Implementation of fixed size array delinearization, can be reused +/// wherever needed with the llvm namespace. Tries to delinearize access +/// function for a fixed size multi-dimensional array, by deriving subscripts +/// from GEP instructions. Returns true upon success and false otherwise. +bool tryDelinearizeFixedSizeImpl(ScalarEvolution *SE, Instruction *Inst, + const SCEV *AccessFn, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes); + struct DelinearizationPrinterPass : public PassInfoMixin { explicit DelinearizationPrinterPass(raw_ostream &OS); Index: llvm/include/llvm/Analysis/DependenceAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/DependenceAnalysis.h +++ llvm/include/llvm/Analysis/DependenceAnalysis.h @@ -927,9 +927,9 @@ bool tryDelinearize(Instruction *Src, Instruction *Dst, SmallVectorImpl &Pair); - /// Tries to delinearize access function for a fixed size multi-dimensional - /// array, by deriving subscripts from GEP instructions. Returns true upon - /// success and false otherwise. + /// Tries to delinearize \p Src and \p Dst access functions for a fixed size + /// multi-dimensional array. Calls \p tryDelinearizeFixedSizeImpl() to + /// delinearize \p Src and \p Dst separately, bool tryDelinearizeFixedSize(Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, const SCEV *DstAccessFn, Index: llvm/include/llvm/Analysis/LoopCacheAnalysis.h =================================================================== --- llvm/include/llvm/Analysis/LoopCacheAnalysis.h +++ llvm/include/llvm/Analysis/LoopCacheAnalysis.h @@ -98,9 +98,10 @@ /// Attempt to delinearize the indexed reference. bool delinearize(const LoopInfo &LI); - bool tryDelinearizeFixedSize(ScalarEvolution *SE, Instruction *Src, - const SCEV *SrcAccessFn, - SmallVectorImpl &SrcSubscripts); + /// Attempt to delinearize \p AccessFn for fixed-size arrays. + bool tryDelinearizeFixedSize(const SCEV *AccessFn, + SmallVectorImpl &Subscripts, + SmallVectorImpl &Sizes); /// Return true if the index reference is invariant with respect to loop \p L. bool isLoopInvariant(const Loop &L) const; Index: llvm/lib/Analysis/Delinearization.cpp =================================================================== --- llvm/lib/Analysis/Delinearization.cpp +++ llvm/lib/Analysis/Delinearization.cpp @@ -521,6 +521,42 @@ return !Subscripts.empty(); } +bool llvm::tryDelinearizeFixedSizeImpl( + ScalarEvolution *SE, Instruction *Inst, const SCEV *AccessFn, + SmallVectorImpl &Subscripts, SmallVectorImpl &Sizes) { + Value *SrcPtr = getLoadStorePointerOperand(Inst); + const SCEVUnknown *SrcBase = cast(SE->getPointerBase(AccessFn)); + + // Check the simple case where the array dimensions are fixed size. + auto *SrcGEP = dyn_cast(SrcPtr); + if (!SrcGEP) + return false; + + getIndexExpressionsFromGEP(*SE, SrcGEP, Subscripts, Sizes); + + // Check that the two size arrays are non-empty and equal in length and + // value. + if (Sizes.empty() || Subscripts.size() <= 1) { + Subscripts.clear(); + return false; + } + + Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts(); + + // Check that for identical base pointers we do not miss index offsets + // that have been added before this GEP is applied. + if (SrcBasePtr != SrcBase->getValue()) { + Subscripts.clear(); + return false; + } + + assert(Subscripts.size() == Sizes.size() + 1 && + "Expected equal number of entries in the list of size and " + "subscript."); + + return true; +} + namespace { class Delinearization : public FunctionPass { Index: llvm/lib/Analysis/DependenceAnalysis.cpp =================================================================== --- llvm/lib/Analysis/DependenceAnalysis.cpp +++ llvm/lib/Analysis/DependenceAnalysis.cpp @@ -3315,13 +3315,13 @@ return true; } +/// Try to delinearize \p SrcAccessFn and \p DstAccessFn if the underlying +/// arrays accessed are fixed-size arrays. Return true if delinearization is +/// successful. bool DependenceInfo::tryDelinearizeFixedSize( Instruction *Src, Instruction *Dst, const SCEV *SrcAccessFn, const SCEV *DstAccessFn, SmallVectorImpl &SrcSubscripts, SmallVectorImpl &DstSubscripts) { - - Value *SrcPtr = getLoadStorePointerOperand(Src); - Value *DstPtr = getLoadStorePointerOperand(Dst); const SCEVUnknown *SrcBase = dyn_cast(SE->getPointerBase(SrcAccessFn)); const SCEVUnknown *DstBase = @@ -3329,41 +3329,26 @@ assert(SrcBase && DstBase && SrcBase == DstBase && "expected src and dst scev unknowns to be equal"); - // Check the simple case where the array dimensions are fixed size. - auto *SrcGEP = dyn_cast(SrcPtr); - auto *DstGEP = dyn_cast(DstPtr); - if (!SrcGEP || !DstGEP) + SmallVector SrcSizes; + SmallVector DstSizes; + if (!tryDelinearizeFixedSizeImpl(SE, Src, SrcAccessFn, SrcSubscripts, + SrcSizes) || + !tryDelinearizeFixedSizeImpl(SE, Dst, DstAccessFn, DstSubscripts, + DstSizes)) return false; - SmallVector SrcSizes, DstSizes; - getIndexExpressionsFromGEP(*SE, SrcGEP, SrcSubscripts, SrcSizes); - getIndexExpressionsFromGEP(*SE, DstGEP, DstSubscripts, DstSizes); - // Check that the two size arrays are non-empty and equal in length and // value. - if (SrcSizes.empty() || SrcSubscripts.size() <= 1 || - SrcSizes.size() != DstSizes.size() || + if (SrcSizes.size() != DstSizes.size() || !std::equal(SrcSizes.begin(), SrcSizes.end(), DstSizes.begin())) { SrcSubscripts.clear(); DstSubscripts.clear(); return false; } - Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts(); - Value *DstBasePtr = DstGEP->getOperand(0)->stripPointerCasts(); - - // Check that for identical base pointers we do not miss index offsets - // that have been added before this GEP is applied. - if (SrcBasePtr != SrcBase->getValue() || DstBasePtr != DstBase->getValue()) { - SrcSubscripts.clear(); - DstSubscripts.clear(); - return false; - } - - assert(SrcSubscripts.size() == DstSubscripts.size() && - SrcSubscripts.size() == SrcSizes.size() + 1 && - "Expected equal number of entries in the list of sizes and " - "subscripts."); + /// At this point we know \p SrcPtr is a \p GetElementPtrInst. + Value *SrcGEP = cast(getLoadStorePointerOperand(Src)); + Value *DstGEP = cast(getLoadStorePointerOperand(Dst)); // In general we cannot safely assume that the subscripts recovered from GEPs // are in the range of values defined for their corresponding array @@ -3390,8 +3375,8 @@ return true; }; - if (!AllIndiciesInRange(SrcSizes, SrcSubscripts, SrcPtr) || - !AllIndiciesInRange(DstSizes, DstSubscripts, DstPtr)) { + if (!AllIndiciesInRange(SrcSizes, SrcSubscripts, SrcGEP) || + !AllIndiciesInRange(DstSizes, DstSubscripts, DstGEP)) { SrcSubscripts.clear(); DstSubscripts.clear(); return false; Index: llvm/lib/Analysis/LoopCacheAnalysis.cpp =================================================================== --- llvm/lib/Analysis/LoopCacheAnalysis.cpp +++ llvm/lib/Analysis/LoopCacheAnalysis.cpp @@ -320,46 +320,21 @@ } bool IndexedReference::tryDelinearizeFixedSize( - ScalarEvolution *SE, Instruction *Src, const SCEV *SrcAccessFn, - SmallVectorImpl &SrcSubscripts) { - Value *SrcPtr = getLoadStorePointerOperand(Src); - const SCEVUnknown *SrcBase = - dyn_cast(SE->getPointerBase(SrcAccessFn)); - - // Check the simple case where the array dimensions are fixed size. - auto *SrcGEP = dyn_cast(SrcPtr); - if (!SrcGEP) + const SCEV *AccessFn, SmallVectorImpl &Subscripts, + SmallVectorImpl &ArraySizes) { + if (!llvm::tryDelinearizeFixedSizeImpl(&SE, &StoreOrLoadInst, AccessFn, + Subscripts, ArraySizes)) return false; - SmallVector SrcSizes; - getIndexExpressionsFromGEP(*SE, SrcGEP, SrcSubscripts, SrcSizes); - - // Check that the two size arrays are non-empty and equal in length and - // value. - if (SrcSizes.empty() || SrcSubscripts.size() <= 1) { - SrcSubscripts.clear(); - return false; - } - - Value *SrcBasePtr = SrcGEP->getOperand(0)->stripPointerCasts(); - - // Check that for identical base pointers we do not miss index offsets - // that have been added before this GEP is applied. - if (SrcBasePtr != SrcBase->getValue()) { - SrcSubscripts.clear(); - return false; - } - - assert(SrcSubscripts.size() == SrcSizes.size() + 1 && - "Expected equal number of entries in the list of size and " - "subscript."); - + /// Populate \p Sizes with scev expressions to be used in calculations later. for (auto Idx : seq(1, Subscripts.size())) - Sizes.push_back(SE->getConstant(Subscripts[Idx]->getType(), SrcSizes[Idx - 1])); + Sizes.push_back( + SE.getConstant(Subscripts[Idx]->getType(), ArraySizes[Idx - 1])); LLVM_DEBUG({ dbgs() << "Delinearized subscripts of fixed-size array\n" - << "SrcGEP:" << *SrcGEP << "\n"; + << "GEP:" << *getLoadStorePointerOperand(&StoreOrLoadInst) + << "\n"; }); return true; } @@ -386,8 +361,10 @@ } bool IsFixedSize = false; - // Try to delinearize fixed-size arrays. - if (tryDelinearizeFixedSize(&SE, &StoreOrLoadInst, AccessFn, Subscripts)) { + SmallVector ArraySizes; + /// Try to delinearize fixed-size arrays. + if (tryDelinearizeFixedSize(AccessFn, Subscripts, + ArraySizes)) { IsFixedSize = true; /// The last element of \p Sizes is the element size. Sizes.push_back(ElemSize);