TensorComprehensions
TensorComprehensions copied to clipboard
facebookresearch
Allow computed expressions on the left-hand-side
This also needs support in polyhedral dependence analysis, putting a block for now
I pushed the polyhedral support for scattering to this branch directly. Requesting @nicolasvasilache to review my code.
Given that the tests already passed without the polyhedral support, should there be new tests that exercise it?
Given that the tests already passed without the polyhedral support, should there be new tests that exercise it?
Good call! I added polyhedral tests and by doing so found a behavior that looks incorrect. Given a simple "gather" TC O(A(i)) = B(i), I get an error:
this statement includes reduction variable 'i' but does not specify a reduction.:
def scatter(int32(N) A, int32(M) B) -> (O) {
O(A(i)) = B(i)
~~~~~~~~~~~~~~... <--- HERE
}
It looks like range inference on the LHS does not look inside indirect accesses. Ideally, I would prefer a compilation warning here saying something like "required precondition A(i) is unique forall i will not be checked in runtime" (because that's our assumption).
A(i) would have to be injective and surjective for that scatter to define a total function. We need to decide on the semantics for repeated values on A(i) and values that are never hit. It sounds like you're saying is we should permit race conditions on the writes, and we leave values that are never written as whatever is already in the buffer.
If that's the case, then I think tc2halide is correct, and we just need to get sema.h to relax and not throw that error.
Reviving this. I made Sema look inside the subscript expressions on the LHS so it no longer complains at that level. In particular, it accepts things like O(i + 2) = A(i) + B(i) which it previously considered to be reductions, and thus failing.
However, on the stupid scattering example O(A(i)) = B(i), range inference now complains about LHS index being unbounded. It indeed is, and as Andrew mentioned, i->A(i) must be a bijective relation for this to be correct. We can insert a very expensive runtime check, but I'm not sure it's a good idea so I'm inclined to just disallow that for now.
Thoughts, @abadams @nicolasvasilache ?
My inclination would be to make O(A(i)) = B(i) work if A(i) has known bounds (e.g. it's a uint8).
On Wed, Apr 25, 2018 at 03:25:21PM +0000, ftynse wrote:
Reviving this. I made Sema look inside the subscript expressions on the LHS so it no longer complains at that level. In particular, it accepts things like
O(i + 2) = A(i) + B(i)which it previously considered to be reductions, and thus failing.However, on the stupid scattering example
O(A(i)) = B(i), range inference now complains about LHS index being unbounded. It indeed is, and as Andrew mentioned, i->A(i) must be a bijective relation for this to be correct. We can insert a very expensive runtime check, but I'm not sure it's a good idea so I'm inclined to just disallow that for now.
Would it be an option to simply require users to write
O(i) = B(invA(i)) instead?
skimo
If they knew the inverse of A, they'd probably already be done. The code that inverts A is something like:
invA(A(i)) = i
My inclination would be to make O(A(i)) = B(i) work if A(i) has known bounds (e.g. it's a uint8).
And infer 0:256 as bounds for O?
What about O(i + A(j+k)) = C(i,j,k) ? And what would the inferred bounds be in this case?
Thank you for your pull request. We require contributors to sign our Contributor License Agreement, and yours has expired.
Before we can review or merge your code, we need you to email [email protected] with your details so we can update your status.
