ISL allows illegal split? (aka what am I doing wrong?)

[Emil Vatai]

Hi!

I take this code:

  for (int j = 0; j < _PB_H; j++) {
    tm1 = 0.0; // S_0
    for (int i = 0; i < _PB_W; i++) {
      y1[i][j] = imgOut[i][j] + tm1; // S_1
      tm1 = imgOut[i][j]; // S_2
    }
  }

I split the first loop (by manipulating the schedule tree in ISL), and get something like this:

  for (int j = 0; j < _PB_H; j++) {
    tm1 = 0.0; // S_0
  for (int j = 0; j < _PB_H; j++) {
    for (int i = 0; i < _PB_W; i++) {
      y1[i][j] = imgOut[i][j] + tm1; // S_1
      tm1 = imgOut[i][j]; // S_2
    }
  }

When I check the legality, ISL says it is legal, but looking at it, I'd say it is not legal (tm1 is reset to 0.0 for each column j, and updated from imgOut[i][j] after each row).

--

After providing everything to the "access info" object, I calculate the "flow". After that, I apply the schedule to the dependencies (which are the may-dependencies from the flow) and look at the delta as the legality check.

These are the dependencies I'm getting, and they don't quite seem right to me (namely, I don't see the S_2[j,i] -> S_0[j'] for j'>j dependency).

deps: [_PB_H, _PB_W] -> {
  S_0[j] -> S_1[j', i] : 0 <= j < _PB_H and j < j' < _PB_H and 0 < i < _PB_W;
  S_0[j] -> S_1[j' = j, i] : 0 <= j < _PB_H and 0 < i < _PB_W;
  S_0[j] -> S_1[j', i = 0] : _PB_W > 0 and 0 <= j < _PB_H and j < j' < _PB_H;
  S_0[j] -> S_1[j' = j, i = 0] : _PB_W > 0 and 0 <= j < _PB_H;
  S_2[j, i] -> S_1[j', i'] : 0 <= j < _PB_H and 0 <= i < _PB_W and j < j' < _PB_H and 0 < i' < _PB_W;
  S_2[j, i] -> S_1[j' = j, i'] : 0 <= j < _PB_H and 0 <= i < _PB_W and i < i' < _PB_W;
  S_2[j, i] -> S_1[j', i' = 0] : 0 <= j < _PB_H and 0 <= i < _PB_W and j <j' < _PB_H
  }

I'm probably doing something wrong -- any help/feedback is welcome.

A "minimal breaking example" (bad_deps.c) which does the whole transformation and legality check (with an input bdi.c file) is provided.

Best,
E

[Sven Verdoolaege]

On Tue, Nov 04, 2025 at 07:53:04PM -0800, Emil Vatai wrote:
> Hi!
>
> I take this code:
>
> for (int j = 0; j < _PB_H; j++) {
> tm1 = 0.0; // S_0
> for (int i = 0; i < _PB_W; i++) {
> y1[i][j] = imgOut[i][j] + tm1; // S_1
> tm1 = imgOut[i][j]; // S_2
> }
> }
>
> I split the first loop (by manipulating the schedule tree in ISL), and get
> something like this:
>
> for (int j = 0; j < _PB_H; j++) {
> tm1 = 0.0; // S_0
> for (int j = 0; j < _PB_H; j++) {
> for (int i = 0; i < _PB_W; i++) {
> y1[i][j] = imgOut[i][j] + tm1; // S_1
> tm1 = imgOut[i][j]; // S_2
> }
> }
>
> When I check the legality, ISL says it is legal, but looking at it, I'd say
> it is not legal (tm1 is reset to 0.0 for each column j, and updated from
> imgOut[i][j] after each row).

AFAICT, you are only checking whether RAW dependencies are not violated,
and they are not.
However, you are not checking the WAR dependencies, and it's those
that are violated by the transformation.

> After providing everything to the "access info" object, I calculate the
> "flow". After that, I apply the schedule to the dependencies (which are the
> may-dependencies from the flow) and look at the delta as the legality check.
>
> These are the dependencies I'm getting, and they don't quite seem right to
> me (namely, I don't see the S_2[j,i] -> S_0[j'] for j'>j dependency).

There is no flow dependency from S_2 to S_0.
There is an output dependency, but AFAICT, you are not computing those.

> static __isl_give isl_union_flow *
> _get_flow_from_scop(__isl_keep pet_scop *scop) {
> isl_union_map *reads, *may_writes, *must_source, *kills, *must_writes;
> isl_union_access_info *access;
> isl_schedule *schedule;
> isl_union_flow *flow;
> reads = pet_scop_get_may_reads(scop);
> access = isl_union_access_info_from_sink(reads);
>
> kills = pet_scop_get_must_kills(scop);
> must_writes = pet_scop_get_tagged_must_writes(scop);
> kills = isl_union_map_union(kills, must_writes);

It doesn't make sense to mix untagged and tagged accesses.

Since your sinks are untagged accesses, the other accesses
should be untagged as well.

skimo

[Emil Vatai]

Thanks for the answer. 

So if I wan't to do WAR deps check, I just "flip" the sink and the source? Something like this? (see attachment -- the RAW deps are also modified, hopefully for better readability and the tagged vs untagged was a typo/autocomplete missclick). 

With these two, can I guarantee that the modified schedule is legal - or is there anything else I should be checking?

Best,

E

--

Emil Vatai

[Sven Verdoolaege]

On Fri, Nov 07, 2025 at 07:32:01PM +0900, Emil Vatai wrote:
> Thanks for the answer.
>
> So if I wan't to do WAR deps check, I just "flip" the sink and the source?
> Something like this? (see attachment -- the RAW deps are also modified,
> hopefully for better readability and the tagged vs untagged was a
> typo/autocomplete missclick).

Essentially, yes, although you may also want to treat writes
as potential sources, if you also want to compute WAW depedencies.

> With these two, can I guarantee that the modified schedule is legal - or is
> there anything else I should be checking?

That all depends on what you want to do with the schedule.
If you also need to make sure that final data that is written
to variables remains the same, then you need to make sure that
the last write remains the last write.
Preserving WAW dependencies would ensure this.

skimo