+/// Check if we can delinearize the subscripts. If the SCEVs representing the
+/// source and destination array references are recurrences on a nested loop,
+/// this function flattens the nested recurrences into separate recurrences
+/// for each loop level.
+bool DependenceAnalysis::tryDelinearize(const SCEV *SrcSCEV,
+ const SCEV *DstSCEV,
+ SmallVectorImpl<Subscript> &Pair,
+ const SCEV *ElementSize) const {
+ const SCEVUnknown *SrcBase =
+ dyn_cast<SCEVUnknown>(SE->getPointerBase(SrcSCEV));
+ const SCEVUnknown *DstBase =
+ dyn_cast<SCEVUnknown>(SE->getPointerBase(DstSCEV));
+
+ if (!SrcBase || !DstBase || SrcBase != DstBase)
+ return false;
+
+ SrcSCEV = SE->getMinusSCEV(SrcSCEV, SrcBase);
+ DstSCEV = SE->getMinusSCEV(DstSCEV, DstBase);
+
+ const SCEVAddRecExpr *SrcAR = dyn_cast<SCEVAddRecExpr>(SrcSCEV);
+ const SCEVAddRecExpr *DstAR = dyn_cast<SCEVAddRecExpr>(DstSCEV);
+ if (!SrcAR || !DstAR || !SrcAR->isAffine() || !DstAR->isAffine())
+ return false;
+
+ // First step: collect parametric terms in both array references.
+ SmallVector<const SCEV *, 4> Terms;
+ SrcAR->collectParametricTerms(*SE, Terms);
+ DstAR->collectParametricTerms(*SE, Terms);
+
+ // Second step: find subscript sizes.
+ SmallVector<const SCEV *, 4> Sizes;
+ SE->findArrayDimensions(Terms, Sizes, ElementSize);
+
+ // Third step: compute the access functions for each subscript.
+ SmallVector<const SCEV *, 4> SrcSubscripts, DstSubscripts;
+ SrcAR->computeAccessFunctions(*SE, SrcSubscripts, Sizes);
+ DstAR->computeAccessFunctions(*SE, DstSubscripts, Sizes);
+
+ // Fail when there is only a subscript: that's a linearized access function.
+ if (SrcSubscripts.size() < 2 || DstSubscripts.size() < 2 ||
+ SrcSubscripts.size() != DstSubscripts.size())
+ return false;
+
+ int size = SrcSubscripts.size();
+
+ DEBUG({
+ dbgs() << "\nSrcSubscripts: ";
+ for (int i = 0; i < size; i++)
+ dbgs() << *SrcSubscripts[i];
+ dbgs() << "\nDstSubscripts: ";
+ for (int i = 0; i < size; i++)
+ dbgs() << *DstSubscripts[i];
+ });
+
+ // The delinearization transforms a single-subscript MIV dependence test into
+ // a multi-subscript SIV dependence test that is easier to compute. So we
+ // resize Pair to contain as many pairs of subscripts as the delinearization
+ // has found, and then initialize the pairs following the delinearization.
+ Pair.resize(size);
+ for (int i = 0; i < size; ++i) {
+ Pair[i].Src = SrcSubscripts[i];
+ Pair[i].Dst = DstSubscripts[i];
+
+ // FIXME: we should record the bounds SrcSizes[i] and DstSizes[i] that the
+ // delinearization has found, and add these constraints to the dependence
+ // check to avoid memory accesses overflow from one dimension into another.
+ // This is related to the problem of determining the existence of data
+ // dependences in array accesses using a different number of subscripts: in
+ // C one can access an array A[100][100]; as A[0][9999], *A[9999], etc.
+ }
+
+ return true;
+}