Implementing loop fusion in ISL

[Emil Vatai]

Hello!

I'm trying to implement loop fusion in ISL. My best guess what that means is Figure 3 from the Schedule tree paper.

As I understand it, it would require a sequence node with N children to have (at least) one of its children removed, i.e. to become a sequence node with N-1 children, but I can't find a function in the ISL API which would do something like that. So for a sequence node of N children to become a sequence of N-1 children, the only option I see is to rebuild it. That just seems wrong... so I'm asking for hints on how to get started with implementing loop fusion in ISL.

Best,
E

[Sven Verdoolaege]

It shouldn't be too difficult to do that externally, but once
you come up with a good design, one or more extra primitives
could be added to isl itself.
I actually have an implementation from 10 years ago,
but I never put it in master exactly because I'm not sure about the interface.

What you could do externally.

If you don't want to fuse all the children of a sequence,
you first need to isolate those that you do want to fuse.
Take the filters of the children of the original sequence node,
collect them in an isl_union_set_list, replacing the filters
of the nodes you want to fuse by a single (union) filter.
Insert a new sequence node on top of the original sequence node.

To merge all band node children of a sequence,
take their partial schedules, intersect them with the corresponding
filters and take the union.
Introduce a new band node on top of the sequence using
isl_schedule_insert_partial_schedule.
If you want, you can then also delete the original band nodes,
but this is not strictly required since they will mostly be ignored
during AST generation.

skimo

[Emil Vatai]

Ok, recreating a new sequence node is doable, but even what you described (collecting the filter), how do I "transplant" the subtrees? i.e. if F_1, ...F_N are the original filter nodes of the sequence, and let's say I want to merge F_k and F_k+1, then I create a new seqence node with filters F_1,.., F_k-1, F_u, F_k+2... F_N where F_u = F_k union F_k+1. But F_1,..,F_k-1 and F_k+2,..F_N don't have any children in the new sequence node! So how do I transplant, e.g. the subtree under old F_1 to be under new F_1? Do I need to traverse those subtrees and recreate them under the new filter nodes? (And similarly, there should a sequence under the fused band node with the two subtrees from under the two original band nodes).

By any chance is this where I need to use one of those `graft` functions? I never successfully managed to use them... I got something like graft needs to have a domain... (I will look into it in more detail if I get a confirmation that this is indeed the function I'm looking for). 

Bonus question! (which is kinda a related) How to "get a subtree"? isl_schedule_node feels like a "pointer" within an `isl_schedule`, and e.g. `isl_schedule_node_get_child()` is described as "obtain a copy of a given child without destroying the current node", which (I think) is a bit confusing. Say, if I get such a copy and start messing with the rest of the tree, what happens to the original tree? (I will test this -- but I think the docs are kinda confusing here...). 

Anyway, the main question is, "how to get a subtree (so I can transplant it as described above)?". There was a similar question on this mailing list, and you replied with "what transformation do you want to implement?" to the guy asking it. Hope it is clear how it relates to the fusion.

Best,

Emil

Currently I have this (0, 1, 2 mod3 were on separate branches, and I want to merge 0 and 1). This is the state after inserting the new sequence node with the merged 0 and 1 (mod3) branch.

domain: "[N] -> { S_0[i, j] : 0 < i < N and 0 <= j < N }"
child:
  sequence:
  - filter: "[N] -> { S_0[i, j] : (i) mod 3 = 0 or (-1 + i) mod 3 = 0 }"
    child:
      # YOU ARE HERE
      sequence:
      - filter: "[N] -> { S_0[i, j] : (i) mod 3 = 0 }"
        child:
          schedule: "[N] -> L_0[{ S_0[i, j] -> [(i)] }]"
          child:
            schedule: "[N] -> L_1[{ S_0[i, j] -> [(j)] }]"
      - filter: "[N] -> { S_0[i, j] : (-1 + i) mod 3 = 0 }"
        child:
          schedule: "[N] -> L_0[{ S_0[i, j] -> [(i)] }]"
          child:
            schedule: "[N] -> L_1[{ S_0[i, j] -> [(j)] }]"
      - filter: "[N] -> { S_0[i, j] : (1 + i) mod 3 = 0 }"
  - filter: "[N] -> { S_0[i, j] : (1 + i) mod 3 = 0 }"
    child:
      schedule: "[N] -> L_0[{ S_0[i, j] -> [(i)] }]"
      child:
        schedule: "[N] -> L_1[{ S_0[i, j] -> [(j)] }]"

and when I try to delete "YOU ARE HERE" node, it says "can only delete node with a single child" (which kinda makes me want to ask a bonus bonus quesiont: how to delete a sequence node? I can think only about isl_schedule_node_cut which deletes the whole subtree)

[Emil Vatai]

oh. wait... that actually worked!? Sorry, I see I might have been stupid again. I need more branches/longer sequence and to re check! Maybe only deletion of the empty "branch" remains?!

--

---
You received this message because you are subscribed to the Google Groups "isl Development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to isl-developme...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/isl-development/5d0f695a-cd2c-49a9-ab9a-8c805989c37en%40googlegroups.com.

--

Emil Vatai

[Sven Verdoolaege]

On Thu, Dec 14, 2023 at 01:21:23AM -0800, Emil Vatai wrote:
> Bonus question! (which is kinda a related) How to "get a subtree"?
> isl_schedule_node feels like a "pointer" within an `isl_schedule`, and e.g.
> `isl_schedule_node_get_child()` is described as "obtain a copy of a given
> child without destroying the current node", which (I think) is a bit
> confusing. Say, if I get such a copy and start messing with the rest of the
> tree, what happens to the original tree? (I will test this -- but I think
> the docs are kinda confusing here...).

If you make modifications, you get a node in a new tree and the old tree
is preserved.
This is a general principle in isl. The input object(s) of a function
are never modified (semantically, at least).

Why would you want to delete that sequence node?
And what would deleting a sequence node mean?

On Thu, Dec 14, 2023 at 11:13:59PM +0900, Emil Vatai wrote:
> oh. wait... that actually worked!? Sorry, I see I might have been stupid
> again. I need more branches/longer sequence and to re check! Maybe only
> deletion of the empty "branch" remains?!

I don't know what this refers to.

skimo

[Sven Verdoolaege]

On Thu, Dec 14, 2023 at 01:21:23AM -0800, Emil Vatai wrote:

> Bonus question! (which is kinda a related) How to "get a subtree"?
> isl_schedule_node feels like a "pointer" within an `isl_schedule`, and e.g.
> `isl_schedule_node_get_child()` is described as "obtain a copy of a given
> child without destroying the current node", which (I think) is a bit
> confusing. Say, if I get such a copy and start messing with the rest of the
> tree, what happens to the original tree? (I will test this -- but I think
> the docs are kinda confusing here...).

Where did you find this description?

I found this:

The schedule tree can be traversed through the use of
C<isl_schedule_node> objects that point to a particular
position in the schedule tree. Whenever a C<isl_schedule_node>
is used to modify a node in the schedule tree, the original schedule
tree is left untouched and the modifications are performed to a copy
of the tree. The returned C<isl_schedule_node> then points to
this modified copy of the tree.

skimo

[Emil Vatai]

> If you make modifications, you get a node in a new tree and the old tree
> is preserved.
> This is a general principle in isl.  The input object(s) of a function
> are never modified (semantically, at least).

 

Yes. That's clear. But a schedule_node is kinda a pointer, and some operations work on schedule_node's (i.e. on the pointer and not the schedule tree itself) -- so if I understand correctly, when you copy a schedule_node you're actually copying a schedule tree which is not explicitly stated. (oh, and now I see that this copying of the schedule tree actually happens even when you modify the schedule tree through the node, you don't even need to copy the node).

 


> Why would you want to delete that sequence node?
> And what would deleting a sequence node mean?

 

tl;dr: I didn't check properly the result of the insert_sequence calls, so I relied with something stupid which is safe to ignore ^_^

The long answer:

Let's assume that we have a sequence node with N children (N filter nodes) and we want to fuse children with index k and k+1. So we'd expect to end up with 2 sequence nodes (instead of the original one), one sequence node with N-1 (unfused/original) children and the other with 2 children (where the fusion happens). I expected the following steps will need to happen:
step0. I start with a seq node with N children (let's call this node seqN)
step1. insert a new seq node above seqN with N-1 (unfused) children (let's call this node seqN-1) and
step2. insert a new seq node below seqN with 2 children (let's call it seq2) then
=> the result I expected here (from top to bottom) seqN-1, seqN, seq2.

"Deleting a sequence node" (in my naive head) would have been step3. removing seqN, i.e. to be left only with "seqN-1 and seq2". But only step1 did what I expected. (= give you "seqN-1, above seqN"). but I didn't realise that insert_sequence() doesn't just insert and "empty" sequence node (sequence node with filters as leaves/empty) but it also does the "transplanting" of the subtrees (i.e. all the unfused subtrees of seqN will be the subtrees of seqN-1 node and the filter nodes in seqN will become leaves/empty). With this discovery I realised that inserting seq2 "deletes" the seqN.

Everything is working now and I hope to prepare a recommended implementation soon.

As for:

> Where did you find this description?

Well from the user manual obviously ^_^ the text above `isl_schedule_node_get_child(` at https://libisl.sourceforge.io/user.html#Schedule-Trees

--
Emil Vatai

[Emil Vatai]

Hi Sven! (resending to mailing list)

I thought my fusion implementation works (because it looked good as a schedule tree). However, no matter what I do with it, I can't seem to make isl generate fused code, i.e. the loops look fused in the schedule tree but the code generated is the same as before fusion! [[[Do you know the "'well yes, but actually no!' pirate" gif?]]]

I wrote a MWE (attached) which hopefully demonstrates the problem (and also shows exactly how I implemented fusion). Basically there are two string literals obtained by dumping a schedule node: fused_str and unfused_str. At the beginning of main, the node_str variable is assigned either fused_str or unfused_str. node_str is converted into an isl_schedule_node and dumped, and then code is generated from it (via isl_ast_node_print). 

-> When unfused_str is used, my implementation of fusion is applied before code generation and I get 2 outer loops + sequence of 3 loops in the middle (which corresponds to the original schedule, despite the fusion being applied).

-> When code is generated from fused_str, it generates 3 nested loops with a sequence in the innermost loop. The funny thing is that I got fused_str by copying the yaml dump of the schedule node after my fusion was applied to it.

Best,

Emil

--

Emil Vatai

[Emil Vatai]

And the forgotten attachment.

--

Emil Vatai

[Sven Verdoolaege]

On Fri, Jun 14, 2024 at 03:45:06PM +0900, Emil Vatai wrote:
> int main(int argc, char *argv[]) {
>
> isl_ctx *ctx = isl_ctx_alloc_with_pet_options();
> char *node_str = unfused_str;
> // node_str = fused_str; /// UNCOMMENT ME!!!!!!!!!!!
> isl_schedule *sched = isl_schedule_read_from_str(ctx, node_str);
> isl_schedule_node *node = isl_schedule_get_root(sched);
> node = isl_schedule_node_first_child(node);
> node = isl_schedule_node_first_child(node);
> node = isl_schedule_node_first_child(node);
> if (node_str == unfused_str)
> node = complete_fuse(node);
> isl_schedule_node_dump(node);
>
> isl_ast_build *build = isl_ast_build_alloc(ctx);
> isl_ast_node *ast_node = isl_ast_build_node_from_schedule(build, sched);

You're calling AST generation on the original schedule
(obtained from isl_schedule_read_from_str),
not on the modified schedule.

skimo

[Emil Vatai]

Huge thanks (especially for the quick answer). Based on this I found the bug in my original code.

--

Emil Vatai