================
@@ -755,6 +769,43 @@ bool llvm::validateDelinearizationResult(ScalarEvolution
&SE,
if (!isKnownLessThan(&SE, Subscript, Size))
return false;
}
+
+ // The offset computation is as follows:
+ //
+ // Offset = I_n +
+ // S_n * I_{n-1} +
+ // ... +
+ // (S_2 * ... * S_n) * I_1
+ //
+ // Regarding this as a function from (I_1, I_2, ..., I_n) to integers, it
+ // must be injective. To guarantee it, the above calculation must not
+ // overflow. Since we have already checked that 0 <= I_k < S_k for k = 2..n,
+ // the minimum and maximum values occur in the following cases:
+ //
+ // Min = [I_1][0]...[0] = S_2 * ... * S_n * I_1
+ // Max = [I_1][S_2-1]...[S_n-1]
+ // = (S_2 * ... * S_n) * I_1 +
+ // (S_2 * ... * S_{n-1}) * (S_2 - 1) +
+ // ... +
+ // (S_n - 1)
+ // = (S_2 * ... * S_n) * I_1 +
+ // (S_2 * ... * S_n) - 1 (can be proved by induction)
+ //
+ const SCEV *Prod = SE.getOne(Sizes[0]->getType());
+ for (const SCEV *Size : drop_end(Sizes)) {
+ Prod = MulOverflow(Prod, Size);
+ if (!Prod)
+ return false;
+ }
+ const SCEV *Min = MulOverflow(Prod, Subscripts[0]);
----------------
Meinersbur wrote:
For the first dimension, it takes the concrete subscript, for every other
dimension it assumes the largest possible subscript. Would we get a better
estimate combining both sources of knowledge by the max of those
(`SCEVMaxExpr(Subscripts[i],Size[i]-1)`)?
https://github.com/llvm/llvm-project/pull/169902
_______________________________________________
llvm-branch-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
