search

enso-org / enso

Hybrid visual and textual functional programming.
https://enso.org
Apache License 2.0
7.34k stars 323 forks source link

Avoid IR traversal by converting (some of) our `Pass`es to mini passes #10981

Open JaroslavTulach opened 4 weeks ago

JaroslavTulach commented 4 weeks ago

After discussing this idea @hubertp pointed out there is a prior work - read at Miniphases: compilation using modular and efficient tree transformations.

Current State

Enso static compiler currently works on IR tree. The work is performed by many IR passes. Each Pass gets IR tree as an input and is supposed to return copy of the IR tree as output. This is very inefficient:

Goal

Rather than passing the whole IR as data and letting each Pass to implement the traversal itself, let's:

By doing this we:

Impact

A lot of Passes may be eligible for the mini passes approach. Usually they just invoke transformExpression with a single partial function - all of them are eligible for rewrite:

Pre-requisite

We need generic traversal function. Right now there is ir.Expression.transformExpression, but we need such a transform function for every IR element. See:

JaroslavTulach commented 1 week ago

When at it please design the traversing architecture to be ready for parallelization by fork join pool.

enso-bot[bot] commented 1 week ago

Pavel Marek reports a new STANDUP for today (2024-09-26):

Progress: - Skeleton of mini pass framework implementation in #11191

enso-bot[bot] commented 1 week ago

Pavel Marek reports a new STANDUP for today (2024-09-27):

Progress: - Migrating LambdaToShorthandLambda to mini IR pass.

enso-bot[bot] commented 4 days ago

Pavel Marek reports a new STANDUP for today (2024-09-30):

Progress: - Fix for unable to boot enso on MacOS - https://github.com/enso-org/enso/actions/runs/11104391535/job/30848357375?pr=11212

GitHub
Fix booting enso on MacOS · enso-org/enso@e524ce3
Hybrid visual and textual functional programming. Contribute to enso-org/enso development by creating an account on GitHub.
enso-bot[bot] commented 3 days ago

Pavel Marek reports a new STANDUP for today (2024-10-01):

Progress: - Migrating TailCall to mini pass.

enso-bot[bot] commented 2 days ago

Pavel Marek reports a new STANDUP for today (2024-10-02):

Progress: - Remove parentIr from the prepare method.

JaroslavTulach commented 1 day ago

Hello Pavel, I have a problem understanding following part of your standup:

* `Expression.withNewChildren` cannot be implemented via `mapExpression`.
  * `Application.Prefix.mapExpressions` is recursive!

As far as I see, there is no recursion in Application.Prefix.mapExpressions. Here is my example:

enso.master$ git diff
diff --git engine/runtime-parser/src/test/java/org/enso/compiler/core/EnsoParserTest.java engine/runtime-parser/src/test/java/org/enso/compiler/core/EnsoParserTest.java
index 256d415952..2596841789 100644
--- engine/runtime-parser/src/test/java/org/enso/compiler/core/EnsoParserTest.java
+++ engine/runtime-parser/src/test/java/org/enso/compiler/core/EnsoParserTest.java
@@ -37,6 +37,27 @@ public class EnsoParserTest {
     """, true, true, true);
   }

+  @Test
+  public void testApplicationShallowTraversal() {
+    var ir = compile("""
+    fn x y z = x ((y 2) (z 1))
+    """);
+    java.util.function.BiConsumer<String, IR> log =
+        (prefix, fst) -> {
+          System.out.println(prefix + fst.getClass().getSimpleName() + ":" + fst.showCode());
+        };
+    ir.mapExpressions(
+        (fst) -> {
+          log.accept("first level: ", fst);
+          fst.mapExpressions(
+              (snd) -> {
+                log.accept("  second level: ", snd);
+                return snd;
+              });
+          return fst;
+        });
+  }
+
   @Test
   public void testLocationsApplicationsAndMethodCalls() {
     parseTest("""

it runs and prints:

first level: Prefix:((x) ((((y) 2)) ((z) 1)))
  second level: Literal:x
  second level: Prefix:((((y) 2)) ((z) 1))

e.g. only first and second level is iterated. Not the whole tree composed of Application.Prefix elements. If you really believe some implementation of mapExpressions is recursive - can you please support such claim with an example that demonstrates the recursiveness?

Expression.withNewChildren cannot be implemented via mapExpression.

Is this claim based on the previous (not proved) one? Or is there some other reason why it doesn't seem possible?

Akirathan commented 9 hours ago

Is this claim based on the previous (not proved) one? Or is there some other reason why it doesn't seem possible?

@JaroslavTulach Sorry for not being precise. Let's look closely at your example.

Put

  "Deep traversal" should {
    "XX work" in {
      implicit val ctx: ModuleContext = mkModuleContext

      def log(prefix: String, fst: IR) = {
        println(prefix + fst.getClass.getSimpleName + ":" + fst.showCode())
      }

      val ir =
        """
          |fn x y z = x ((y 2) (z 1))
          |""".stripMargin.preprocessModule.analyse
      // prefix is `x ((y 2) (z 1))` expression
      val prefix = ir.bindings(0)
        .asInstanceOf[Method.Explicit]
        .body
        .asInstanceOf[Function.Lambda]
        .body
        .asInstanceOf[Application.Prefix]
      prefix.function.asInstanceOf[Name.Literal].name shouldEqual "x"
      prefix.arguments should have size 1
      val arg = prefix.arguments(0).asInstanceOf[CallArgument.Specified]
      arg.value.isInstanceOf[Application.Prefix] shouldBe true
      prefix.mapExpressions { fst =>
        log("first level: ", fst)
        fst.mapExpressions { snd =>
          log("  second level: ", snd)
          snd
        }
      }
    }
  }

At the end of TailCallTest.scala. The IR for prefix looks like this: prefix

As you can see, the prefix direct children is Literal and CallArgument.Specified. But CallArgument.Specified is skipped in mapExpressions:

first level: Literal:x
first level: Prefix:((((y) 2)) ((z) 1))
  second level: Prefix:((y) 2)
  second level: Prefix:((z) 1)

The relevant code is arguments.map(_.mapExpressions(fn)) in Application.Prefix.mapExpressions

TL;DR; We cannot rely on mapExpressions in withNewChildren. It may not be recursive, but it skips some IR elements and maps the function on their children (Prefix skips CallArgument.Specified and calls fn on their values).

JaroslavTulach commented 7 hours ago

OK, that's indeed a different problem than being recursive:

We cannot rely on mapExpressions in withNewChildren. ... it skips some IR elements and maps the function on their children (Prefix skips CallArgument.Specified and calls fn on their values).

Yes, obviously mapExpression deals only with IR.Expression and not with the rest of children. But maybe we want to traverse just Expression as stated here.