diff options
| author | Cliff Click <cliffc@acm.org> | 2023-10-28 20:35:29 -0700 |
|---|---|---|
| committer | Dibyendu Majumdar <dibyendumajumdar@users.noreply.github.com> | 2023-11-01 18:56:50 +0000 |
| commit | 0a669bf5fa11a63516ea8f5316b0079c2eee4bde (patch) | |
| tree | 9ce49fae3cf37489413e1b5ec42a2747d60442ef /chapter05/README.md | |
| parent | 2c7e86d4350ed115922e80e6bfc1aef30a881f75 (diff) | |
| download | Simple-0a669bf5fa11a63516ea8f5316b0079c2eee4bde.tar.gz Simple-0a669bf5fa11a63516ea8f5316b0079c2eee4bde.zip | |
Update README
Add true/false
Diffstat (limited to 'chapter05/README.md')
| -rw-r--r-- | chapter05/README.md | 68 |
1 files changed, 43 insertions, 25 deletions
diff --git a/chapter05/README.md b/chapter05/README.md index bea9545b..8929dfad 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -31,47 +31,65 @@ Here is a recap of the nodes introduced in previous chapters: Following new nodes are introduced in this chapter: -| Node Name | Type | Chapter | Description | Inputs | Value | -|-----------|---------|---------|----------------------------------------------------------------------|------------------------------------------------------------------------------------------------|---------------------------------------------------------------| -| If | Control | 5 | Represents an `if` condition, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values, one for true branch, another for false | -| Region | Control | 5 | Represents a merge point from multiple control flow | An input for each control flow that is merging | Merged control | -| Phi | Data | 5 | Represents the phi function that picks a value based on control flow | A region control node, and multiple data nodes that provide values from multiple control flows | Result is the extracted value depending on control flow taken | -| Stop | Control | 5 | Represents termination of the program | One or more Return nodes | None | +| Node Name | Type | Chapter | Description | Inputs | Value | +|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------| +| If | Control | 5 | A branching test, sub type of `MultiNode` | A control node and a data predicate node | A tuple of two values: one for true, one for false | +| Region | Control | 5 | A merge point for multiple control flow | An input for each control flow that is merging | Merged control | +| Phi | Data | 5 | A phi function picks a value based on control flow | A Region, and data nodes for each control path | Depends on control flow path taken | +| Stop | Control | 5 | Termination of the program | One or more Return nodes | None | ## `If` Nodes -`If` node takes in both control and data (predicate expression) and routes the control token to one of the two control flows, represented by the `Proj` nodes. +`If` node takes in both control and data (predicate expression) and routes the +control token to one of the two control flows, represented by true and false +`Proj` nodes. ## `Phi` Nodes -The `Phi` reads in both data and control, and outputs a data value. The control input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are one each for the control inputs to that `Region`. -The result computed by a `Phi` depends both on the data and the matching control input. At most one control input to the `Region` can be active at a time. The `Phi` passes through the data value from the matching input [[1]](#1). +A `Phi` reads in both data and control, and outputs a data value. The control +input to the `Phi` points to a `Region` node. The data inputs to the `Phi` are +one each for the control inputs to that `Region`. The result computed by a +`Phi` depends both on the data and the matching control input. At most one +control input to the `Region` can be active at a time, and the `Phi` passes +through the data value from the matching input [[1]](#1). ## `Region` Nodes -`Region` nodes were originally introduced to replace Basic Blocks in the IR [[3]](#3). However, we do not assign a `Region` to every node in the graph; we insert a `Region` node at a merge point where it takes control from each predecessor control edge, and produces -a merged control as output. Data flows via `Phi` nodes at these merge points. +`Region` nodes were originally introduced to replace Basic Blocks in the IR +[[3]](#3). However, we do not assign a `Region` to every node in the graph; we +insert a `Region` node at a merge point where it takes control from each +predecessor control edge, and produces a merged control as output. Data flows +via `Phi` nodes at these merge points. ## Parsing of `If` statement -When we parse an `if` statement, the control flow splits at that point. We must track the names being updated in each part of the `if` statement, and then merge them at the end. -The implementation follows the description in [[2]](#2). +When we parse an `if` statement, the control flow splits at that point. We +must track the names being updated in each part of the `if` statement, and then +merge them at the end. The implementation follows the description in +[[2]](#2). This involves following: -* We create an `IfNode` with the current control token, i.e. the node mapped to `$ctrl`, and the `if` predicate expression as inputs. -* We add two `ProjNodes` - one for the `True` branch (call if `ifT`), and the other for the `False` branch (call it `ifF`) - these extract values from the tuple result of the `IfNode`. -* We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains all the stack levels as the original, and moreover the new node is added as a user of all the names that are currently bound. -* The original `ScopeNode` is saved. -* We set the duplicate `ScopeNode` as current. -* We set control token to the `True` projection node `ifT`. -* We parse the true branch of the `if` statement. -* We reset the original `ScopeNode` as current. -* We set control token to the `False` projection node `ifF`. -* If there is an `else` statement we parse it. -* At this point we have two `ScopeNode`s; the original one, potentially updated by the `False` branch, and the duplicate one, potentially updated by the `True` branch. +* We create an `IfNode` with the current control token, i.e. the node mapped to + `$ctrl`, and the `if` predicate expression as inputs. +* We add two `ProjNodes` - one for the `True` branch (call if `ifT`), and the + other for the `False` branch (call it `ifF`) - these extract values from the + tuple result of the `IfNode`. +* We duplicate the current `ScopeNode`. The duplicated `ScopeNode` contains + all the same symbol tables as the original, and has the same edges. +* We set control token to the `True` projection node `ifT`, and parse the true + branch of the `if` statement. +* We reset the dupped `ScopeNode` as current. +* We set control token to the `False` projection node `ifF`, and if there is an + `else` statement we parse it. +* At this point we have two `ScopeNode`s; the original one, potentially updated + by the `True` branch, and the duplicate one, potentially updated by the + `False` branch. * We create a `Region` node to represent a merge point. -* We compare the two `ScopeNode`s. We create `Phi` nodes for any names whose bindings differ. The `Phi` nodes take the `Region` node as the control input and the two data nodes from each of the `ScopeNode`s. The name binding is updated to point to the `Phi` node. +* We *merge* the two `ScopeNode`s. We create `Phi` nodes for any names whose + bindings differ. The `Phi` nodes take the `Region` node as the control input + and the two data nodes from each of the `ScopeNode`s. The name binding is + updated to point to the `Phi` node. * Finally, we set the `Region` node as the control token, and discard the duplicated `ScopeNode`. ## Example |
