From f9cb030376b0b53369a1340b751a1fb83d81db2e Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Fri, 21 Feb 2014 18:15:11 +0000 Subject: [PATCH] normalize the last delinearized dimension in the dependence test, we used to discard some information that the delinearization provides: the size of the innermost dimension of an array, i.e., the size of scalars stored in the array, and the remainder of the delinearization that provides the offset from which the array reads start, i.e., the base address of the array. To avoid losing this data in the rest of the data dependence analysis, the fix is to multiply the access function in the last delinearized dimension by its size, effectively making the size of the last dimension to always be in bytes, and then add the remainder of delinearization to the last subscript, effectively making the last subscript start at the base address of the array. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201867 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/DependenceAnalysis.cpp | 19 +++++++++++++++++-- 1 file changed, 17 insertions(+), 2 deletions(-) diff --git a/lib/Analysis/DependenceAnalysis.cpp b/lib/Analysis/DependenceAnalysis.cpp index 6f9effa127a..b655be5a135 100644 --- a/lib/Analysis/DependenceAnalysis.cpp +++ b/lib/Analysis/DependenceAnalysis.cpp @@ -3189,8 +3189,8 @@ DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, return false; SmallVector SrcSubscripts, DstSubscripts, SrcSizes, DstSizes; - SrcAR->delinearize(*SE, SrcSubscripts, SrcSizes); - DstAR->delinearize(*SE, DstSubscripts, DstSizes); + const SCEV *RemainderS = SrcAR->delinearize(*SE, SrcSubscripts, SrcSizes); + const SCEV *RemainderD = DstAR->delinearize(*SE, DstSubscripts, DstSizes); int size = SrcSubscripts.size(); // Fail when there is only a subscript: that's a linearized access function. @@ -3210,6 +3210,21 @@ DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, if (SrcSizes[i] != DstSizes[i]) return false; + // When the difference in remainders is different than a constant it might be + // that the base address of the arrays is not the same. + const SCEV *DiffRemainders = SE->getMinusSCEV(RemainderS, RemainderD); + if (!isa(DiffRemainders)) + return false; + + // Normalize the last dimension: integrate the size of the "scalar dimension" + // and the remainder of the delinearization. + DstSubscripts[size-1] = SE->getMulExpr(DstSubscripts[size-1], + DstSizes[size-1]); + SrcSubscripts[size-1] = SE->getMulExpr(SrcSubscripts[size-1], + SrcSizes[size-1]); + SrcSubscripts[size-1] = SE->getAddExpr(SrcSubscripts[size-1], RemainderS); + DstSubscripts[size-1] = SE->getAddExpr(DstSubscripts[size-1], RemainderD); + #ifndef NDEBUG DEBUG(errs() << "\nSrcSubscripts: "); for (int i = 0; i < size; i++) -- 2.34.1