================
@@ -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:
> Does the following implementation match your intention?
Yes.
If one is SCEVUnknown, one can take the other one. Only both being SCEVUnknown
would stop working. if SCEVMaxExprs cause SCEV to bail out because of
expression complexity, we cioud prioritize one of the expressions.
Aynway, what I prefer handling subscripts independent of whether they are
outermost, innermost, or in-between, but based on what information is
available.
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
