================
@@ -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]);
----------------
kasuga-fj wrote:
Does the following implementation match your intention?
https://github.com/kasuga-fj/llvm-project/commit/e8f6f57a3ac87d1a926309a2730ca182b92e3201
As for the existing regression tests, their results have not changed.
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
