From bc312c990a24f703a3085406f714c2503f461ef3 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 3 Dec 2023 23:23:04 +0000 Subject: Chapter 7: While Statement MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher --- docs/chapter07/README.md | 244 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 244 insertions(+) create mode 100644 docs/chapter07/README.md (limited to 'docs/chapter07/README.md') diff --git a/docs/chapter07/README.md b/docs/chapter07/README.md new file mode 100644 index 00000000..6486904b --- /dev/null +++ b/docs/chapter07/README.md @@ -0,0 +1,244 @@ +# Chapter 7: While Statement + +# Table of Contents + +1. [Dealing With Back Edges](#dealing-with-back-edges) +2. [New Node Types](#new-node-types) +3. [Detailed Steps](#detailed-steps) +4. [Visualization](#visualization) +5. [Nested Loops](#nested-loops) +5. [Loop With Nested If](#loop-with-nested-if) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter07) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter06...linear-chapter07) it to the previous chapter. + + +In this chapter we introduce the `while` statement. + +Here is the [complete language grammar](07-grammar.md) for this chapter. + + +## Dealing With Back Edges + +The complication introduced by looping constructs is that variables flow back into the body of the loop on iteration. +For example: + +```java +while(arg < 10) { + arg = arg + 1; +} +return arg; +``` + +The variable `arg` is assigned a new value inside the body of the loop, and this then flows back into the body of the loop. + +In general, we will rewrite the looping construct as follows: + +```java +loop_head: +if( !(arg < 10) ) + goto loop_exit; +arg = arg + 1; +goto loop_head; + +loop_exit: +``` + +Above is for illustration only, we do not have labels and `goto` statements in the language. + +From an SSA[^1] point of view, since `arg` flows back, it requires a `phi` node at the head. Conceptually we would like the outcome to be: + +```java +// arg1 represents incoming arg +// +loop_head: +arg2 = phi(arg1, arg3); +if( !(arg2 < 10) ) + goto loop_exit; +arg3 = arg2 + 1; +goto loop_head; + +loop_exit: +``` + +Notice that the phi for `arg2` refers to `arg3`, which is not known at the time we parse the `while` loop predicate. This is the crux of the problem that we need +to solve in order to successfully construct the Sea of Nodes graph, which is always in SSA form. + +Recall from [Chapter 5](../chapter05/README.md) that when parsing `if` statements, we clone the symbol tables as we go past the `if` predicate. +Later we merge the two sets of symbol tables at a `Region` - creating phis for all names that encountered a change in definition within the two +branches of the `if` statement. In the case of the `if` statement, the phis are created at the merge point when we already know the definitions +that are being merged. + +The essential idea for loop constructs is to eagerly create phis for all names in the symbol tables *before* we enter the loop's `if` condition, +since we do not know which names will be redefined inside the body of the loop. When the loop terminates, we go back and remove unnecessary +phis. We call this approach the "eager phi" approach.[^2] + +In [Chapter 8](../chapter08) we will implement a "lazy phi" approach that creates phis only when we encounter redefinition of a name. + +## New Node Types + +Our list of nodes remains the same as in [Chapter 5](../chapter05/README.md), however, we create a subtype of `Region` named `Loop` to better +encapsulate some of the additional logic required. Loop and Phi peepholes defer rewrites that need the back edge +until we complete parsing the loop body. Other nodes continue to optimize normally. + +## Detailed Steps + +1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, + the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is + set after the loop is parsed. A missing back edge marks the Loop and associated Phis as incomplete, + so their peepholes wait for the inputs needed by each rewrite. + + ```java + ctrl(new LoopNode(ctrl(),null).peephole()); + ``` + + The newly created region becomes the current control. + +2. We duplicate the current Scope node. This involves duplicating all the symbols at + every level with the scope, and creating phis for every symbol except the `$ctrl` binding. + + ```java + // Make a new Scope for the body. + _scope = _scope.dup(true); + ``` + + Note that the `dup` call is given an argument `true`. This triggers creating phis. The code + that creates the phis in the `dup()` method is shown below. + + ```java + // boolean loop=true if this is a loop region + + String[] names = reverseNames(); // Get the variable names + dup.add_def(ctrl()); // Control input is just copied + for( int i=1; ikeep().peephole(); + // Setup projection nodes + Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); + Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + ``` + +4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, + therefore `$ctrl` in the exit scope is set to the `False` projection. + The exit scope captures any side effects of the loop's predicate. + + ```java + // The exit scope, accounting for any side effects in the predicate + var exit = _scope.dup(); + exit.ctrl(ifF); + ``` + +5. We now set the control to the `True` projection and parse the loop body. + + ```java + // Parse the true side, which corresponds to loop body + ctrl(ifT); // set ctrl token to ifTrue projection + parseStatement(); // Parse loop body + ``` + +6. After the loop body is parsed, we go back and process all the phis we created earlier. + + ```java + // The true branch loops back, so whatever is current control gets + // added to head loop as input + head.endLoop(_scope, exit); + ``` + + The `endLoop` method sets the second control of the loop region to the control from the back edge. + It then goes through all the phis and sets the second data input on the phi to the corresponding entry + from the loop body; phis that were not used are peepholed and get replaced by the original input. + + ```java + Node ctrl = ctrl(); + ctrl.set_def(2,back.ctrl()); + for( int i=1; i