Handling >= 2D (dynamic) arrays with PET

[Emil Vatai]

Hi,

Is it possible to detect scops with 2D (or more-D) dynamic arrays with PET, i.e. if a 2d array is implemented as a 1d array, and a[i, j] is a[i*N + j] (or something similar). I would guess that the answer is negative, since representing the [i,j] -> a[i*N+j] access relation is not possible as an isl object (maybe except maybe as a qpolynomial?)

Also, assuming that PET can't detect code contining a[N*i + j] would it be possible to modify PET to handle this?

Best,

E

[Sven Verdoolaege]

On Fri, May 01, 2026 at 12:45:57AM -0700, Emil Vatai wrote:
> Hi,
>
> Is it possible to detect scops with 2D (or more-D) dynamic arrays with PET,
> i.e. if a 2d array is implemented as a 1d array, and a[i, j] is a[i*N + j]
> (or something similar).

The best approach is to _not_ linearize the 2D array, i.e.,
to leave it at a[i][j].

> Also, assuming that PET can't detect code contining a[N*i + j] would it be
> possible to modify PET to handle this?

In theory it would be possible for pet to attempt to delinearize
the linearized accesses, but I don't think that's going to happen
anytime soon.
I believe Polly does perform some form of delinearization.

skimo

[Emil Vatai]

Thanks for the quick response.

On Fri, May 1, 2026 at 7:10 PM Sven Verdoolaege
<sven.ver...@telenet.be> wrote:
> The best approach is to _not_ linearize the 2D array, i.e.,
> to leave it at a[i][j].

I'd like to not touch the original input code which is linearized.

> In theory it would be possible for pet to attempt to delinearize
> the linearized accesses, but I don't think that's going to happen
> anytime soon.
> I believe Polly does perform some form of delinearization.

I'm thinking of implementing it myself. In theory, how could that be
handled? If you have time could you give me some pointers?

I had an idea I wanted to explore, but I came here to check first if
there is something I'm missing: I was working under the assumption
that the (quasi)affine isl sets/maps can't handle expressions such as
i*N+j i.e the rough image in my head about affine expressions is that
they are represented as a matrix, and each row is a constraint while
each column has a label which are N (and any other param) and i, j
(and any other iter) and "const", and the entry in the matrix under a
label is a constant multiplier of the param/iterator of the
corresponding row/constraint, ergo i*N is not a label and it's not a
constant multiplier of either i or N so it is not a valid term in an
affine set/map. So I thought that maybe PET could return qpolinomials
as the read/write access relations and modify the compute flow
function in isl to handle those.

And again, I don't know if this idea makse any sense... feedback would
be much appreciated.

Best,
E


--
Emil Vatai

[Sven Verdoolaege]

On Sat, May 02, 2026 at 05:51:59PM +0900, Emil Vatai wrote:
> On Fri, May 1, 2026 at 7:10 PM Sven Verdoolaege
> <sven.ver...@telenet.be> wrote:
> > In theory it would be possible for pet to attempt to delinearize
> > the linearized accesses, but I don't think that's going to happen
> > anytime soon.
> > I believe Polly does perform some form of delinearization.
>
> I'm thinking of implementing it myself. In theory, how could that be
> handled? If you have time could you give me some pointers?

https://www.cs.colostate.edu/~pouchet/doc/ics-article.15a.pdf

> I had an idea I wanted to explore, but I came here to check first if
> there is something I'm missing: I was working under the assumption
> that the (quasi)affine isl sets/maps can't handle expressions such as
> i*N+j i.e the rough image in my head about affine expressions is that
> they are represented as a matrix, and each row is a constraint while
> each column has a label which are N (and any other param) and i, j
> (and any other iter) and "const", and the entry in the matrix under a
> label is a constant multiplier of the param/iterator of the
> corresponding row/constraint, ergo i*N is not a label and it's not a
> constant multiplier of either i or N so it is not a valid term in an
> affine set/map. So I thought that maybe PET could return qpolinomials
> as the read/write access relations and modify the compute flow
> function in isl to handle those.

In the end, you'll end up doing some type of delinearization anyway,
or move to the whole different class of algorithms, some of which
may not even exist.
You're better off trying to delinearize as early as possible.

skimo

[Emil Vatai]

Thanks! 

Emil Vatai