From 5ebbfe4813289ec520160c112f3b30d10b0eeb5f Mon Sep 17 00:00:00 2001 From: dibyendumajumdar Date: Sat, 28 Oct 2023 14:16:43 +0100 Subject: Add descriptions of the new node types in Chapter 5. Add references to Cliff's thesis. --- chapter05/README.md | 30 +++++++++++++++++++++++++++++- 1 file changed, 29 insertions(+), 1 deletion(-) (limited to 'chapter05/README.md') diff --git a/chapter05/README.md b/chapter05/README.md index a5c6f52f..bea9545b 100644 --- a/chapter05/README.md +++ b/chapter05/README.md @@ -34,13 +34,28 @@ 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 | None | +| 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 | +## `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. + +## `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). + +## `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. + ## 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). This involves following: @@ -92,3 +107,16 @@ Below is the graph after we created a `Region` node and merged the two definitio * Observe that the duplicate `ScopeNode` has been discarded. * `a` is now bound to the `Phi` node. * The `Phi` node's inputs are the `Region` node and the `Add` node from the `True` branch, and `Sub` node from the `False` branch. + +## References +[1] +Click, C. (1995). +Combining Analyses, Combining Optimizations, 132. + +[2] +Click, C. (1995). +Combining Analyses, Combining Optimizations, 102-103. + +[3] +Click, C. (1995). +Combining Analyses, Combining Optimizations, 129. \ No newline at end of file -- cgit v1.2.3