isl codegen: trivially redundant conditionals

[Uday Reddy B]

With barvinok at its latest tip barvinok-0.41.8, code generation for this spec below yields an AST with guards '1 == 0' a couple of times in the 'if' nodes. Would be good to simplify these away. Updated isl submodule to dc16f8e3d62c9e808ef86ffe82c2b93ac1446da3 and this is solved - update barvinok?

$ ./iscc
codegen [p0] -> { C0[i0, i1, i2, i3] -> [i0, i1, i2, i3] : exists (e0, e1, e2: 0 <= p0 <= 48 and 0 <= i3 <= 127 and -2 + i1 <= 2e0 <= i1 and e2 >= 0 and e2 >= -128p0 + 784i0 + 28e0 and e2 >= -128p0 + 784i0 and -128p0 + 28e1 <= e2 <= 27 - 128p0 + 28e1 and e2 <= 783 - 128p0 + 784i0 and e2 <= 27 - 128p0 + 784i0 + 28e0 and e2 <= 127 and -2 - 256p0 + i2 + 56e1 <= 2e2 <= -256p0 + i2 + 56e1)};
if (p0 >= 0 && p0 <= 48)
  for (int c0 = 8 * p0 / 49; c0 <= (8 * p0 + 7) / 49; c0 += 1)
    for (int c1 = max(0, 9 * p0 - 56 * c0 + (p0 + 1) / 7 - 1); c1 <= min(56, 9 * p0 - 56 * c0 + (p0 + 6) / 7 + 10); c1 += 1)
      if (c1 <= 2 || 32 * p0 + 7 * (c1 / 2) + 38 >= 196 * c0 + 7 * c1 || 1 == 0 || 1 == 0)
        for (int c2 = max(max(0, 256 * p0 - 1568 * c0 - 1512), 256 * p0 - 1568 * c0 - 28 * c1); c2 <= min(min(56, 256 * p0 - 1568 * c0 + 256), 256 * p0 - 1568 * c0 - 28 * c1 + 312); c2 += 1)
          if ((c1 <= 2 && 1568 * c0 + c2 >= 256 * p0) || (8 * p0 >= 49 * c0 + 2 && c2 >= 49 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 >= 10 * p0 - 2 * ((3 * p0 + 6) / 7)) || (256 * p0 >= 1568 * c0 + c2 + 1 && c2 <= 48 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 + 2 * ((24 * p0 + c2) / 56) >= 10 * p0) || (c1 >= 3 && 392 * c0 + 7 * c1 >= 64 * p0 + 2 && 1568 * c0 + 28 * c1 + c2 >= 256 * p0 + 57 && 256 * p0 + 312 >= 28 * (c1 % 2) + 1568 * c0 + 28 * c1 + c2) || (392 * c0 + 7 * c1 == 64 * p0 + 1 && c2 >= 53))
            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

While on this, is there a way (through the interactive tool) to set options to fully separate and avoid all 'if' conditionals here? Programmatically, using the following still leads to the above AST with conditionals, i.e., the separation isn't happening.

  isl_union_map *optionsMap =
      isl_union_map_empty(isl_space_range(isl_union_map_get_space(schedule)));
  // Avoid the generation of guards by splitting the domain of the schedule
  // dimensions into pieces with a fixed set of statements.
  optionsMap = setUniverse(optionsMap, schedule, "separate");
  isl_ast_build *build = isl_ast_build_alloc(isl_union_map_get_ctx(schedule));
  build = isl_ast_build_set_options(build, optionsMap);
  isl_ast_node *tree = isl_ast_build_node_from_schedule_map(build, schedule);
  isl_ast_dump(tree);

-Uday

[Uday Reddy B]

On the separation part:

codegen input

[p0] -> { C0[i0, i1, i2, i3] -> [i0, i1, i2, i3] : exists (e0, e1, e2: 0 <= p0 <= 48 and 0 <= i3 <= 127 and -2 + i1 <= 2e0 <=
i1 and e2 >= 0 and e2 >= -128p0 + 784i0 + 28e0 and e2 >= -128p0 + 784i0 and -128p0 + 28e1 <= e2 <= 27 - 128p0 + 28e1 and e2 <=
 783 - 128p0 + 784i0 and e2 <= 27 - 128p0 + 784i0 + 28e0 and e2 <= 127 and -2 - 256p0 + i2 + 56e1 <= 2e2 <= -256p0 + i2 + 56e1
) }

AST generated with options to separate everywhere and avoid disjunctions:

---------------------------

isl_union_map *optionsMap =
      isl_union_map_empty(isl_space_range(isl_union_map_get_space(schedule)));
  // Avoid the generation of guards by splitting the domain of the schedule
  // dimensions into pieces with a fixed set of statements.
  optionsMap = setUniverse(optionsMap, schedule, "separate");
  isl_ast_build *build = isl_ast_build_alloc(isl_union_map_get_ctx(schedule));
  build = isl_ast_build_set_options(build, optionsMap);

  // Disallow 'if' conditionals.
  isl_options_set_ast_build_allow_or(isl_union_map_get_ctx(schedule), 0);

  isl_ast_node *tree = isl_ast_build_node_from_schedule_map(build, schedule);

---------------------------------------

It may be useful to explicitly specify in the manual that separation isn't guaranteed. For example, here: 32 * p0 + 7 * (c1 / 2) + 38 >= 196 * c0 + 7 * c1 would appear to be a blocker for separation on `c1`.

if (p0 >= 0 && p0 <= 48)
  for (int c0 = 8 * p0 / 49; c0 <= (8 * p0 + 7) / 49; c0 += 1)
    for (int c1 = max(0, 9 * p0 - 56 * c0 + (p0 + 1) / 7 - 1); c1 <= min(56, 9 * p0 - 56 * c0 + (p0 + 6) / 7 + 10); c1 += 1) {

      if (c1 <= 2)

        for (int c2 = max(max(0, 256 * p0 - 1568 * c0 - 1512), 256 * p0 - 1568 * c0 - 28 * c1); c2 <= min(min(56, 256 * p0 - 1568 * c0 + 256), 256 * p0 - 1568 * c0 - 28 * c1 + 312); c2 += 1) {

          if (c1 <= 2 && 1568 * c0 + c2 >= 256 * p0)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (8 * p0 >= 49 * c0 + 2 && c2 >= 49 && 256 * p0 >= 1568 * c0 + c2 + 1 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 >= 10 * p0 - 2 * ((3 * p0 + 6) / 7))

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (256 * p0 >= 1568 * c0 + c2 + 1 && c2 <= 48 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 + 2 * ((24 * p0 + c2) / 56) >= 10 * p0)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (c1 >= 3 && 392 * c0 + 7 * c1 >= 64 * p0 + 2 && 1568 * c0 + 28 * c1 + c2 >= 256 * p0 + 57 && 256 * p0 + 312 >= 28 * (c1 % 2) + 1568 * c0 + 28 * c1 + c2)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (8 * p0 >= 49 * c0 + 3 && 392 * c0 + 7 * c1 == 64 * p0 + 1 && c2 >= 53)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);
        }

      if (c1 >= 3 && 32 * p0 + 7 * (c1 / 2) + 38 >= 196 * c0 + 7 * c1)

        for (int c2 = max(max(0, 256 * p0 - 1568 * c0 - 1512), 256 * p0 - 1568 * c0 - 28 * c1); c2 <= min(min(56, 256 * p0 - 1568 * c0 + 256), 256 * p0 - 1568 * c0 - 28 * c1 + 312); c2 += 1) {

          if (c1 <= 2 && 1568 * c0 + c2 >= 256 * p0)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (8 * p0 >= 49 * c0 + 2 && c2 >= 49 && 256 * p0 >= 1568 * c0 + c2 + 1 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 >= 10 * p0 - 2 * ((3 * p0 + 6) / 7))

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (256 * p0 >= 1568 * c0 + c2 + 1 && c2 <= 48 && 256 * p0 + 56 >= 1568 * c0 + 28 * c1 + c2 && 56 * c0 + c1 + 2 * ((24 * p0 + c2) / 56) >= 10 * p0)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (c1 >= 3 && 392 * c0 + 7 * c1 >= 64 * p0 + 2 && 1568 * c0 + 28 * c1 + c2 >= 256 * p0 + 57 && 256 * p0 + 312 >= 28 * (c1 % 2) + 1568 * c0 + 28 * c1 + c2)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);

          if (8 * p0 >= 49 * c0 + 3 && 392 * c0 + 7 * c1 == 64 * p0 + 1 && c2 >= 53)

            for (int c3 = 0; c3 <= 127; c3 += 1)
              C0(c0, c1, c2, c3);
        }
    }

-Uday

[Sven Verdoolaege]

On Mon, Apr 06, 2026 at 08:08:15AM +0530, Uday K Bondhugula wrote:
> With barvinok at its latest tip barvinok-0.41.8, code generation for this
> spec below yields an AST with guards '1 == 0' a couple of times in the 'if'
> nodes. Would be good to simplify these away. Updated isl submodule
> to dc16f8e3d62c9e808ef86ffe82c2b93ac1446da3 and this is solved - update
> barvinok?

If you need that, then you should indeed use a newer version of isl.

> $ ./iscc
> codegen [p0] -> { C0[i0, i1, i2, i3] -> [i0, i1, i2, i3] : exists (e0, e1,
> e2: 0 <= p0 <= 48 and 0 <= i3 <= 127 and -2 + i1 <= 2e0 <= i1 and e2 >= 0
> and e2 >= -128p0 + 784i0 + 28e0 and e2 >= -128p0 + 784i0 and -128p0 + 28e1
> <= e2 <= 27 - 128p0 + 28e1 and e2 <= 783 - 128p0 + 784i0 and e2 <= 27 -
> 128p0 + 784i0 + 28e0 and e2 <= 127 and -2 - 256p0 + i2 + 56e1 <= 2e2 <=
> -256p0 + i2 + 56e1)};

[..]

>
> While on this, is there a way (through the interactive tool) to set options
> to fully separate and avoid all 'if' conditionals here? Programmatically,

Is the set you are trying to iterate over convex?
If not, it may not even be possible to generate iteration code
without if-statements.
Do you have any additional information about this particular set that
makes you believe it should be possible to generate an AST in this way?

> using the following still leads to the above AST with conditionals, i.e.,
> the separation isn't happening.
>
> isl_union_map *optionsMap =
>
> isl_union_map_empty(isl_space_range(isl_union_map_get_space(schedule)));
> // Avoid the generation of guards by splitting the domain of the schedule
> // dimensions into pieces with a fixed set of statements.
> optionsMap = setUniverse(optionsMap, schedule, "separate");
> isl_ast_build *build =
> isl_ast_build_alloc(isl_union_map_get_ctx(schedule));
> build = isl_ast_build_set_options(build, optionsMap);
> isl_ast_node *tree = isl_ast_build_node_from_schedule_map(build,
> schedule);
> isl_ast_dump(tree);

AFAICT, there is only one statement involved, so the generated AST
is always "separate".

On Mon, Apr 06, 2026 at 08:19:13AM +0530, Uday K Bondhugula wrote:
> It may be useful to explicitly specify in the manual that separation isn't

> guaranteed. For example, here: 32 * p0 + 7 * (c1 / 2) + 38 >= 196 * c0 + 7

> * c1 would appear to be a blocker for separation on `c1`.

[..]

The AST again appears to involve only a single statement,
so it is trivially "separate".

Hmm... maybe you are confused by this description of the schedule map
ast generation option:

This is a single-dimensional space representing the schedule dimension(s)
to which ``separation'' should be applied. Separation tries to split
a loop into several pieces if this can avoid the generation of guards
inside the loop.

I guess this is a bit vague.
The corresponding option for schedule trees has a better explanation:

When this option is specified, the AST generator will
split the domain of the specified schedule dimension
into pieces with a fixed set of statements for which
instances need to be executed by the iterations in
the schedule domain part. This option tends to avoid
the generation of guards inside the corresponding loops.

AFAIR, the two have essentially the same meaning, but the description
of the second is a bit better.

skimo

[Uday Reddy B]

On Tue, 7 Apr 2026 at 01:46, Sven Verdoolaege <sven.ver...@telenet.be> wrote:

On Mon, Apr 06, 2026 at 08:08:15AM +0530, Uday K Bondhugula wrote:
> With barvinok at its latest tip barvinok-0.41.8, code generation for this
> spec below yields an AST with guards '1 == 0' a couple of times in the 'if'
> nodes. Would be good to simplify these away. Updated isl submodule
> to dc16f8e3d62c9e808ef86ffe82c2b93ac1446da3 and this is solved - update
> barvinok?

If you need that, then you should indeed use a newer version of isl.

> $ ./iscc
> codegen [p0] -> { C0[i0, i1, i2, i3] -> [i0, i1, i2, i3] : exists (e0, e1,
> e2: 0 <= p0 <= 48 and 0 <= i3 <= 127 and -2 + i1 <= 2e0 <= i1 and e2 >= 0
> and e2 >= -128p0 + 784i0 + 28e0 and e2 >= -128p0 + 784i0 and -128p0 + 28e1
> <= e2 <= 27 - 128p0 + 28e1 and e2 <= 783 - 128p0 + 784i0 and e2 <= 27 -
> 128p0 + 784i0 + 28e0 and e2 <= 127 and -2 - 256p0 + i2 + 56e1 <= 2e2 <=
> -256p0 + i2 + 56e1)};
[..]
>
> While on this, is there a way (through the interactive tool) to set options
> to fully separate and avoid all 'if' conditionals here? Programmatically,

Is the set you are trying to iterate over convex?
If not, it may not even be possible to generate iteration code
without if-statements.

I don't think it's convex, but I'm not sure if it can be iterated over without if statements. (My next email on this thread points to a constraint in the generated 'if' conditional that makes that not possible or hard.)

 

Do you have any additional information about this particular set that
makes you believe it should be possible to generate an AST in this way?

Not really at this point.

 

> using the following still leads to the above AST with conditionals, i.e.,
> the separation isn't happening.
>
>   isl_union_map *optionsMap =
>
> isl_union_map_empty(isl_space_range(isl_union_map_get_space(schedule)));
>   // Avoid the generation of guards by splitting the domain of the schedule
>   // dimensions into pieces with a fixed set of statements.
>   optionsMap = setUniverse(optionsMap, schedule, "separate");
>   isl_ast_build *build =
> isl_ast_build_alloc(isl_union_map_get_ctx(schedule));
>   build = isl_ast_build_set_options(build, optionsMap);
>   isl_ast_node *tree = isl_ast_build_node_from_schedule_map(build,
> schedule);
>   isl_ast_dump(tree);

AFAICT, there is only one statement involved, so the generated AST
is always "separate".

It looks like I completely missed the connection to multiple statements here. The documentation at the first place doesn't refer to multiple statements. It's written as if it applies even to a single statement, breaking its schedule domain into pieces to get rid of the conditionals, which is possible in several cases. Obvious example further below.

 

On Mon, Apr 06, 2026 at 08:19:13AM +0530, Uday K Bondhugula wrote:
> It may be useful to explicitly specify in the manual that separation isn't
> guaranteed. For example, here: 32 * p0 + 7 * (c1 / 2) + 38 >= 196 * c0 + 7
> * c1 would appear to be a blocker for separation on `c1`.

[..]

The AST again appears to involve only a single statement,
so it is trivially "separate".

Hmm... maybe you are confused by this description of the schedule map
ast generation option:

    This is a single-dimensional space representing the schedule dimension(s)
    to which ``separation'' should be applied.  Separation tries to split
    a loop into several pieces if this can avoid the generation of guards
    inside the loop.

I guess this is a bit vague.
The corresponding option for schedule trees has a better explanation:

Right - this doesn't say multiple statements. The 'loop' could simply have a single statement's instances.

 

    When this option is specified, the AST generator will
    split the domain of the specified schedule dimension
    into pieces with a fixed set of statements for which
    instances need to be executed by the iterations in
    the schedule domain part.  This option tends to avoid
    the generation of guards inside the corresponding loops.

AFAIR, the two have essentially the same meaning, but the description
of the second is a bit better.

Re-reading this - it's now clear that the separation is really for multiple statements and not index set splitting to avoid 'if's for a single one. Consider the following non-convex domain:

for (i = 0; i < 100; ++i) {

  if (i <= 10)

     S1;

   if (i >= 40)

     S1;

}

It's easily possible to generate an AST without 'if's. But this isn't the separation being referred to in the 'doc' - I recall now from the literature, given how the term has been used.

-Uday

skimo

[Sven Verdoolaege]

On Thu, Apr 09, 2026 at 06:04:29PM +0530, Uday K Bondhugula wrote:
> On Tue, 7 Apr 2026 at 01:46, Sven Verdoolaege <sven.ver...@telenet.be>
> wrote:
> > Is the set you are trying to iterate over convex?
> > If not, it may not even be possible to generate iteration code
> > without if-statements.
> >
>
> I don't think it's convex,

I have since checked and it is not.

> > When this option is specified, the AST generator will
> > split the domain of the specified schedule dimension
> > into pieces with a fixed set of statements for which
> > instances need to be executed by the iterations in
> > the schedule domain part. This option tends to avoid
> > the generation of guards inside the corresponding loops.
> >
> > AFAIR, the two have essentially the same meaning, but the description
> > of the second is a bit better.
> >
>
> Re-reading this - it's now clear that the separation is really for multiple
> statements and not index set splitting to avoid 'if's for a single one.
> Consider the following non-convex domain:
>
> for (i = 0; i < 100; ++i) {
> if (i <= 10)
> S1;
> if (i >= 40)
> S1;
> }
>
> It's easily possible to generate an AST without 'if's. But this isn't the
> separation being referred to in the 'doc' - I recall now from the
> literature, given how the term has been used.

There may initially have been a (tacit?) assumption that each statement
has a convex domain.
If the domain is a finite union of convex sets as in your example above,
then this could easily be handled in the same way.
However, if the domain is a projection as in your original set,
then it's a different matter.

skimo