Stream: compiler development

Topic: Understanding mono_ir and decision_tree

Anthony Bullard (Dec 05 2024 at 03:47):

Taking on my first issue in the IR phase and some of what happens in the decision_tree is hard to parse out. Can someone give a high level understanding of what we are trying to do here. Much appreciated!

Richard Feldman (Dec 05 2024 at 11:36):

I think @Folkert de Vries and @Ayaz Hafiz would probably be best able to describe what the decision tree does at a high level

Ayaz Hafiz (Dec 05 2024 at 18:18):

the decision tree algorithm comes from
http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf

Ayaz Hafiz (Dec 05 2024 at 18:18):

There's a ton of indirection because of the low level of the IR so it's very tricky to see what it's doing at the moment - we did a bad job making it easy to debug

Ayaz Hafiz (Dec 05 2024 at 18:19):

I believe there are some debug helpers to print out the state of the decision tree, at least there were a couple years ago

Ayaz Hafiz (Dec 05 2024 at 18:20):

The idea is to compile a when expression to an "efficient" tree of checks to perform to decide what branch to take

Ayaz Hafiz (Dec 05 2024 at 18:24):

For example, suppose you have the expression

x: [A [X, Y, Z], B [X, Y, Z]]
when x is
  A X -> foo1
  A Z -> foo2
  B Z -> foo3
  _ -> foo4

you want to compile this down to the "efficient" pattern

branch = when ~constructor(x) is # ~constructor is a fake function that returns the head constructor, i.e. A or B
  A ->
    when ~constructor(~payload(x, 0)) is # ~payload(t, n) is a fake function that returns the tag payload at index n
      X -> 1
      Y -> 2
      Z -> 4
  B ->
    when ~constructor(~payload(x, )) is
      X -> 4
      Y -> 4
      Z -> 3

when branch is
  1 -> foo1
  2 -> foo2
  3 -> foo3
  4 -> foo4

Anthony Bullard (Dec 05 2024 at 19:10):

Ok, I'm trying to figure out why the Can AST (for some when branches) seems to be coming out in mono_ir as something VERY different in some cases

Ayaz Hafiz (Dec 05 2024 at 20:51):

do you have an example?

Anthony Bullard (Dec 05 2024 at 20:52):

Yes I do: https://github.com/roc-lang/roc/issues/7302

Anthony Bullard (Dec 05 2024 at 22:15):

@Ayaz Hafiz Here you can see the output of the raw branches: https://github.com/gamebox/aoc-2024/blob/main/day3/puzzle2/output.txt

Anthony Bullard (Dec 05 2024 at 22:23):

With better output, you'll see first the raw branch, and then each flattened branch followed by the word "FLATTENED:"

Ayaz Hafiz (Dec 06 2024 at 00:23):

is the example reducable

Last updated: Jul 06 2025 at 12:14 UTC