# Chapter 7: While Statement [Previous: Chapter 6](../chapter06/README.md) | [Next: Chapter 8](../chapter08/README.md) # 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) 6. [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 within 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