summaryrefslogtreecommitdiff
path: root/chapter05
diff options
context:
space:
mode:
authorThalia Archibald <thalia@archibald.dev>2024-06-21 06:13:09 -0700
committerGitHub <noreply@github.com>2024-06-21 14:13:09 +0100
commite5f4f7b85fbb91a293a7d89d7b85adfbaeeb51f4 (patch)
tree9b6ecc7ef37b1ec7f08efed6f908f478dc551e03 /chapter05
parenta749c244bea3e2774d453165cbd18ed52863a8f5 (diff)
downloadSimple-e5f4f7b85fbb91a293a7d89d7b85adfbaeeb51f4.tar.gz
Simple-e5f4f7b85fbb91a293a7d89d7b85adfbaeeb51f4.zip
Format whitespace (#86)
* Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces
Diffstat (limited to 'chapter05')
-rw-r--r--chapter05/README.md22
-rw-r--r--chapter05/docs/05-grammar.md16
-rw-r--r--chapter05/docs/05-graph2.gv2
-rw-r--r--chapter05/docs/05-graph3.gv2
-rw-r--r--chapter05/docs/05-graph4.gv2
-rw-r--r--chapter05/docs/05-graph5.gv2
-rw-r--r--chapter05/docs/05-graph6.gv2
-rw-r--r--chapter05/docs/05-graph8.gv2
-rw-r--r--chapter05/pom.xml2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java18
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/Parser.java20
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/Utils.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java22
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java4
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java6
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java4
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java6
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java8
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/Node.java28
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java6
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java4
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java4
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java8
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/type/Type.java4
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java2
-rw-r--r--chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java2
-rw-r--r--chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java56
32 files changed, 133 insertions, 133 deletions
diff --git a/chapter05/README.md b/chapter05/README.md
index f06e5e15..cf95b545 100644
--- a/chapter05/README.md
+++ b/chapter05/README.md
@@ -16,7 +16,7 @@ The following new nodes are introduced in this chapter:
|-----------|---------|---------|----------------------------------------------------|------------------------------------------------|----------------------------------------------------|
| 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 flows | 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 |
+| 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 | All return nodes of the function | None |
## Recap
@@ -27,7 +27,7 @@ Here is a recap of the nodes introduced in previous chapters:
|-----------|----------------|---------|------------------------------------------------|-------------------------------------------------------------------------------|----------------------------------------------------------------------------|
| Multi | Abstract class | 4 | A node that has a tuple result | | A tuple |
| Start | Control | 1 | Start of function, now a MultiNode | | A tuple with a ctrl token and an `arg` data node |
-| Proj | Data | 4 | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index |
+| Proj | Data | 4 | Projection nodes extract values from MultiNode | A MultiNode and index | Result is the extracted value from the input MultiNode at offset index |
| Bool | Data | 4 | Represents results of a comparison operator | Two data nodes | Result is a comparison, represented as integer value where 1=true, 0=false |
| Not | Data | 4 | Logical not | One data node | Result converts 0 to 1 and vice versa |
| Return | Control | 1 | End of function | Predecessor control node and a data node for the return value of the function | Return value of the function |
@@ -77,7 +77,7 @@ However:
> intermediate representation such as a CFG. We need a way to serialize the graph and get
> back the control dependences. We do this with a simple global code motion algorithm.[^3]
-Thus, we do not associate a control edge on every data node in the graph.
+Thus, we do not associate a control edge on every data node in the graph.
We insert a `Region` node at a merge point where it takes control from each
predecessor's control edge, and produces a merged control as output. Data flows
@@ -105,7 +105,7 @@ This involves following:
`else` statement we parse it.
7. 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.
+ `False` branch.
8. We create a `Region` node to represent a merge point.
9. 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
@@ -117,7 +117,7 @@ Implementation is in [`parseIf` method in `Parser`](https://github.com/SeaOfNode
## Operations on ScopeNodes
-As explained above, we duplicate ScopeNodes and merge them at a later point. There are some
+As explained above, we duplicate ScopeNodes and merge them at a later point. There are some
subtleties in how this is implemented that is worth going over.
### Duplicating a ScopeNode
@@ -139,7 +139,7 @@ At the merge point we merge two ScopeNodes. The goals are:
2) A new Region node is created representing the merged control flow. The phis have this region node as the first input.
3) After the merge is completed, the duplicate is discarded, and its use of each of the nodes is also deleted.
-The merging logic takes advantage of that fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode.
+The merging logic takes advantage of that fact that the two ScopeNodes have the bound nodes in the same order in the list of inputs. This was ensured during duplicating the ScopeNode.
Although only the innermost occurrence of a name can have its binding changed, we scan all the nodes in our input list, and simply ignore ones where the binding has not changed.
For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes/Simple/blob/main/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java#L164-L173)
@@ -149,12 +149,12 @@ For implementation [see `ScopeNode.mergeScopes()`](https://github.com/SeaOfNodes
We show the graph for the following code snippet:
```java
-int a = 1;
-if (arg == 1)
- a = arg+2;
+int a = 1;
+if (arg == 1)
+ a = arg+2;
else
- a = arg-3;
-return a;
+ a = arg-3;
+return a;
```
### Before Merging
diff --git a/chapter05/docs/05-grammar.md b/chapter05/docs/05-grammar.md
index 9af39c05..65be4bf7 100644
--- a/chapter05/docs/05-grammar.md
+++ b/chapter05/docs/05-grammar.md
@@ -10,7 +10,7 @@ program
statement
: returnStatement
| declStatement
- | blockStatment
+ | blockStatment
| expressionStatement
| ifStatement
| metaStatement
@@ -43,15 +43,15 @@ returnStatement
expression
: comparisonExpression
;
-
+
comparisonExpression
: additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)*
;
-
+
additiveExpression
- : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
+ : multiplicativeExpression (('+' | '-') multiplicativeExpression)*
;
-
+
multiplicativeExpression
: unaryExpression (('*' | '/') unaryExpression)*
;
@@ -73,11 +73,11 @@ INTEGER_LITERAL
: [1-9][0-9]*
| [0]
;
-
+
IDENTIFIER
: NON_DIGIT (NON_DIGIT | DIGIT)*
;
-
+
NON_DIGIT: [a-zA-Z_];
DEC_DIGIT: [0-9];
-``` \ No newline at end of file
+```
diff --git a/chapter05/docs/05-graph2.gv b/chapter05/docs/05-graph2.gv
index 2adb3da5..12506e85 100644
--- a/chapter05/docs/05-graph2.gv
+++ b/chapter05/docs/05-graph2.gv
@@ -75,4 +75,4 @@ return a;
Scope1_0:"Scope1_0_$ctrl" -> Region17;
Scope1_0:"Scope1_0_arg" -> Start2:p1;
Scope1_1:"Scope1_1_a" -> Phi_a18;
-} \ No newline at end of file
+}
diff --git a/chapter05/docs/05-graph3.gv b/chapter05/docs/05-graph3.gv
index 7e049c9c..277bed48 100644
--- a/chapter05/docs/05-graph3.gv
+++ b/chapter05/docs/05-graph3.gv
@@ -63,4 +63,4 @@ return a;
Phi_a18 -> Sub16[taillabel=2];
Return19 -> Region17[taillabel=0 color=red];
Return19 -> Phi_a18[taillabel=1];
-} \ No newline at end of file
+}
diff --git a/chapter05/docs/05-graph4.gv b/chapter05/docs/05-graph4.gv
index ac3dcdd7..88120b4a 100644
--- a/chapter05/docs/05-graph4.gv
+++ b/chapter05/docs/05-graph4.gv
@@ -60,4 +60,4 @@ return a;
Phi_a17 -> EQNode7[taillabel=2];
Return18 -> Region16[taillabel=0 color=red];
Return18 -> Phi_a17[taillabel=1];
-} \ No newline at end of file
+}
diff --git a/chapter05/docs/05-graph5.gv b/chapter05/docs/05-graph5.gv
index b6bfd5f2..b03e90b5 100644
--- a/chapter05/docs/05-graph5.gv
+++ b/chapter05/docs/05-graph5.gv
@@ -57,4 +57,4 @@ return a;
EQNode20 -> Phi_a19[taillabel=2];
Return21 -> Region16[taillabel=0 color=red];
Return21 -> EQNode20[taillabel=1];
-} \ No newline at end of file
+}
diff --git a/chapter05/docs/05-graph6.gv b/chapter05/docs/05-graph6.gv
index f888e8e9..1ad7b94a 100644
--- a/chapter05/docs/05-graph6.gv
+++ b/chapter05/docs/05-graph6.gv
@@ -55,4 +55,4 @@ return c;
Phi_c17 -> Con_6[taillabel=2];
Return19 -> Region16[taillabel=0 color=red];
Return19 -> Phi_c17[taillabel=1];
-} \ No newline at end of file
+}
diff --git a/chapter05/docs/05-graph8.gv b/chapter05/docs/05-graph8.gv
index bef29b93..2af43847 100644
--- a/chapter05/docs/05-graph8.gv
+++ b/chapter05/docs/05-graph8.gv
@@ -126,4 +126,4 @@ return a;
edge [style=dashed color=cornflowerblue];
Scope1_0:"Scope1_0_arg" -> Start2:p1;
Scope1_1:"Scope1_1_a" -> Phi_a34;
-} \ No newline at end of file
+}
diff --git a/chapter05/pom.xml b/chapter05/pom.xml
index 8fe63444..49991f74 100644
--- a/chapter05/pom.xml
+++ b/chapter05/pom.xml
@@ -11,4 +11,4 @@
<artifactId>chapter05</artifactId>
<packaging>jar</packaging>
<name>Chapter 5</name>
-</project> \ No newline at end of file
+</project>
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 1c3e314c..c35a4e32 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -21,7 +21,7 @@ public class GraphVisualizer {
sb.append("/*\n");
sb.append(parser.src());
sb.append("\n*/\n");
-
+
// To keep the Scopes below the graph and pointing up into the graph we
// need to group the Nodes in a subgraph cluster, and the scopes into a
// different subgraph cluster. THEN we can draw edges between the
@@ -35,10 +35,10 @@ public class GraphVisualizer {
// Merge multiple edges hitting the same node. Makes common shared
// nodes much prettier to look at.
sb.append("\tconcentrate=\"true\";\n");
-
+
// Just the Nodes first, in a cluster no edges
nodes(sb, all);
-
+
// Now the scopes, in a cluster no edges
for (ScopeNode sn: parser._xScopes)
scopes(sb, sn);
@@ -49,7 +49,7 @@ public class GraphVisualizer {
// Walk the Scope edges
for (ScopeNode sn: parser._xScopes)
scopeEdges(sb, sn);
-
+
sb.append("}\n");
return sb.toString();
}
@@ -90,7 +90,7 @@ public class GraphVisualizer {
}
sb.append("</TR>\n");
sb.append("\t\t\t</TABLE>>\n\t\t");
-
+
} else {
// control nodes have box shape
// other nodes are ellipses, i.e. default shape
@@ -102,7 +102,7 @@ public class GraphVisualizer {
}
sb.append("];\n");
}
-
+
// Force Region & Phis to line up
for( Node n : all ) {
if( n instanceof RegionNode region ) {
@@ -114,7 +114,7 @@ public class GraphVisualizer {
sb.append("}\n");
}
}
-
+
sb.append("\t}\n"); // End Node cluster
}
@@ -179,7 +179,7 @@ public class GraphVisualizer {
}
}
}
-
+
// Walk the scope edges
private void scopeEdges( StringBuilder sb, ScopeNode scopenode ) {
sb.append("\tedge [style=dashed color=cornflowerblue];\n");
@@ -202,7 +202,7 @@ public class GraphVisualizer {
level++;
}
}
-
+
/**
* Finds all nodes in the graph.
*/
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 99d38686..ff58fc25 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -13,7 +13,7 @@ import java.util.*;
* This is a simple recursive descent parser. All lexical analysis is done here as well.
*/
public class Parser {
-
+
/**
* A Global Static, unique to each compilation. This is a public, so we
* can make constants everywhere without having to thread the StartNode
@@ -54,7 +54,7 @@ public class Parser {
add("true");
}};
-
+
/**
* We clone ScopeNodes when control flows branch; it is useful to have
* a list of all active ScopeNodes for purposes of visualization of the SoN graph
@@ -75,12 +75,12 @@ public class Parser {
@Override
public String toString() { return _lexer.toString(); }
-
+
String src() { return new String( _lexer._input ); }
// Debugging utility to find a Node by index
public static Node find(int nid) { return START.find(nid); }
-
+
private Node ctrl() { return _scope.ctrl(); }
private Node ctrl(Node n) { return _scope.ctrl(n); }
@@ -101,7 +101,7 @@ public class Parser {
return STOP;
}
-
+
/**
* Parses a block
*
@@ -165,7 +165,7 @@ public class Parser {
ctrl(ifT); // set ctrl token to ifTrue projection
parseStatement(); // Parse true-side
ScopeNode tScope = _scope;
-
+
// Parse the false side
_scope = fScope; // Restore scope, then parse else block if any
ctrl(ifF); // Ctrl token is now set to ifFalse projection
@@ -176,7 +176,7 @@ public class Parser {
if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
throw error("Cannot define a new name on one arm of an if");
-
+
// Merge results
_scope = tScope;
_xScopes.pop(); // Discard pushed from graph display
@@ -465,7 +465,7 @@ public class Parser {
skipWhiteSpace();
return peek()==ch;
}
-
+
// Return an identifier or null
String matchId() {
skipWhiteSpace();
@@ -492,7 +492,7 @@ public class Parser {
return TypeInteger.constant(Long.parseLong(snum));
}
- // First letter of an identifier
+ // First letter of an identifier
private boolean isIdStart(char ch) {
return Character.isAlphabetic(ch) || ch == '_';
}
@@ -508,7 +508,7 @@ public class Parser {
return new String(_input, start, --_position - start);
}
- //
+ //
private boolean isPunctuation(char ch) {
return "=;[]<>()+-/*".indexOf(ch) != -1;
}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Utils.java b/chapter05/src/main/java/com/seaofnodes/simple/Utils.java
index 4d663c25..45f15327 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Utils.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Utils.java
@@ -36,4 +36,4 @@ public class Utils {
return i;
return -1;
}
-} \ No newline at end of file
+}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 87304f28..081c9276 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -6,7 +6,7 @@ public class AddNode extends Node {
public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
@Override public String label() { return "Add"; }
-
+
@Override public String glabel() { return "+"; }
@Override
@@ -15,7 +15,7 @@ public class AddNode extends Node {
in(2)._print0(sb.append("+"));
return sb.append(")");
}
-
+
@Override
public Type compute() {
@@ -42,13 +42,13 @@ public class AddNode extends Node {
// canonicalize to (x+0)
if( t2 instanceof TypeInteger i && i.value()==0 )
return lhs;
-
+
// Add of same to a multiply by 2
if( lhs==rhs )
return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
// Goal: a left-spine set of adds, with constants on the rhs (which then fold).
-
+
// Move non-adds to RHS
if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
return swap12();
@@ -66,7 +66,7 @@ public class AddNode extends Node {
return spline_cmp(lhs,rhs) ? swap12() : null;
// Now we only see (add add non)
-
+
// Do we have (x + con1) + con2?
// Replace with (x + (con1+con2) which then fold the constants
if( lhs.in(2)._type.isConstant() && t2.isConstant() )
@@ -76,7 +76,7 @@ public class AddNode extends Node {
// Do we have ((x + (phi cons)) + con) ?
// Do we have ((x + (phi cons)) + (phi cons)) ?
// Push constant up through the phi: x + (phi con0+con0 con1+con1...)
-
+
// Note that this is the exact reverse of Phi pulling a common op
// down to reduce total op-count. We don't get in an endless push-
// up push-down peephole cycle because the constants all fold first.
@@ -91,12 +91,12 @@ public class AddNode extends Node {
}
// Now we sort along the spline via rotates, to gather similar things together.
-
+
// Do we rotate (x + y) + z
// into (x + z) + y ?
if( spline_cmp(lhs.in(2),rhs) )
return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2));
-
+
return null;
}
@@ -108,16 +108,16 @@ public class AddNode extends Node {
static boolean spline_cmp( Node hi, Node lo ) {
if( lo._type.isConstant() ) return false;
if( hi._type.isConstant() ) return true ;
-
+
if( lo instanceof PhiNode && lo.allCons() ) return false;
if( hi instanceof PhiNode && hi.allCons() ) return true ;
if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
-
+
// Same category of "others"
return lo._nid > hi._nid;
}
-
+
@Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); }
}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 61259d2c..7a4a087e 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -10,7 +10,7 @@ abstract public class BoolNode extends Node {
}
abstract String op(); // String opcode name
-
+
@Override
public String label() { return getClass().getSimpleName(); }
@@ -39,7 +39,7 @@ abstract public class BoolNode extends Node {
@Override
public Node idealize() {
- // Compare of same
+ // Compare of same
if( in(1)==in(2) )
return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index ba6f55d7..1086037d 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -21,10 +21,10 @@ public class ConstantNode extends Node {
super(Parser.START);
_con = type;
}
-
+
@Override
public String label() { return ""+_con; }
-
+
@Override
public String uniqueName() { return "Con_" + _nid; }
@@ -32,7 +32,7 @@ public class ConstantNode extends Node {
StringBuilder _print1(StringBuilder sb) {
return _con._print(sb);
}
-
+
@Override
public Type compute() { return _con; }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 01314c74..bf025453 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -16,7 +16,7 @@ public class DivNode extends Node {
in(2)._print0(sb.append("/"));
return sb.append(")");
}
-
+
@Override
public Type compute() {
if (in(1)._type instanceof TypeInteger i0 &&
@@ -32,6 +32,6 @@ public class DivNode extends Node {
@Override
public Node idealize() { return null; }
-
+
@Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 08924563..0d59ef25 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -7,15 +7,15 @@ public class MinusNode extends Node {
public MinusNode(Node in) { super(null, in); }
@Override public String label() { return "Minus"; }
-
+
@Override public String glabel() { return "-"; }
-
+
@Override
StringBuilder _print1(StringBuilder sb) {
in(1)._print0(sb.append("(-"));
return sb.append(")");
}
-
+
@Override
public Type compute() {
if (in(1)._type instanceof TypeInteger i0)
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 0f21f67a..2dbdd695 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -7,7 +7,7 @@ public class MulNode extends Node {
public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
@Override public String label() { return "Mul"; }
-
+
@Override public String glabel() { return "*"; }
@Override
@@ -34,16 +34,16 @@ public class MulNode extends Node {
Node rhs = in(2);
Type t1 = lhs._type;
Type t2 = rhs._type;
-
+
// Mul of 1. We do not check for (1*x) because this will already
// canonicalize to (x*1)
if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 )
return lhs;
-
+
// Move constants to RHS: con*arg becomes arg*con
if ( t1.isConstant() && !t2.isConstant() )
return swap12();
-
+
return null;
}
@Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 81c90f68..7ba1aa19 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,7 +1,7 @@
package com.seaofnodes.simple.node;
public abstract class MultiNode extends Node {
-
+
public MultiNode(Node... inputs) { super(inputs); }
}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
index 810f931b..5412108b 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -74,9 +74,9 @@ public abstract class Node {
// ------------------------------------------------------------------------
-
+
// Debugger Printing.
-
+
// {@code toString} is what you get in the debugger. It has to print 1
// line (because this is what a debugger typically displays by default) and
// has to be robust with broken graph/nodes.
@@ -100,7 +100,7 @@ public abstract class Node {
// Every Node implements this.
abstract StringBuilder _print1(StringBuilder sb);
-
+
/**
* Gets the ith input node
* @param i Offset of the input node
@@ -117,19 +117,19 @@ public abstract class Node {
public boolean isUnused() { return nOuts() == 0; }
public boolean isCFG() { return false; }
-
+
/**
* Change a <em>def</em> into a Node. Keeps the edges correct, by removing
* the corresponding <em>use->def</em> edge. This may make the original
* <em>def</em> go dead. This function is co-recursive with {@link #kill}.
* <p>
-
+
* This method is the normal path for altering a Node, because it does the
* proper default edge maintenance. It also <em>immediately</em> kills
* Nodes that lose their last use; at times care must be taken to avoid
* killing Nodes that are being used without having an output Node. This
* definitely happens in the middle of recursive {@link #peephole} calls.
- *
+ *
* @param idx which def to set
* @param new_def the new definition
* @return new_def for flow coding
@@ -188,7 +188,7 @@ public abstract class Node {
old_def.kill(); // Kill old def
}
}
-
+
/**
* Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
* to null. This may recursively kill more Nodes and is basically dead
@@ -211,7 +211,7 @@ public abstract class Node {
public <N extends Node> N unkeep() { delUse(null); return (N)this; }
// ------------------------------------------------------------------------
// Graph-based optimizations
-
+
/**
* We allow disabling peephole opt so that we can observe the
* full graph, vs the optimized graph.
@@ -236,7 +236,7 @@ public abstract class Node {
public final Node peephole( ) {
// Compute initial or improved Type
Type type = _type = compute();
-
+
if (_disablePeephole)
return this; // Peephole optimizations turned off
@@ -245,13 +245,13 @@ public abstract class Node {
return deadCodeElim(new ConstantNode(type).peephole());
// Future chapter: Global Value Numbering goes here
-
+
// Ask each node for a better replacement
Node n = idealize();
if( n != null ) // Something changed
// Recursively optimize
return deadCodeElim(n.peephole());
-
+
return this; // No progress
}
@@ -271,7 +271,7 @@ public abstract class Node {
}
return m;
}
-
+
/**
* This function needs to be
* <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
@@ -340,7 +340,7 @@ public abstract class Node {
// ------------------------------------------------------------------------
// Peephole utilities
-
+
// Swap inputs without letting either input go dead during the swap.
Node swap12() {
Node tmp = in(1);
@@ -348,7 +348,7 @@ public abstract class Node {
_inputs.set(2,tmp);
return this;
}
-
+
// does this node contain all constants?
// Ignores in(0), as is usually control.
boolean allCons() {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java
index 5dd6a86e..e3683646 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -7,15 +7,15 @@ public class NotNode extends Node {
public NotNode(Node in) { super(null, in); }
@Override public String label() { return "Not"; }
-
+
@Override public String glabel() { return "!"; }
-
+
@Override
StringBuilder _print1(StringBuilder sb) {
in(1)._print0(sb.append("(!"));
return sb.append(")");
}
-
+
@Override
public Type compute() {
if( in(1)._type instanceof TypeInteger i0 )
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 716d03d9..374e1183 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -5,7 +5,7 @@ import com.seaofnodes.simple.type.Type;
public class PhiNode extends Node {
final String _label;
-
+
public PhiNode(String label, Node... inputs) { super(inputs); _label = label; }
@Override public String label() { return "Phi_"+_label; }
@@ -36,7 +36,7 @@ public class PhiNode extends Node {
return in(1);
// Pull "down" a common data op. One less op in the world. One more
- // Phi, but Phis do not make code.
+ // Phi, but Phis do not make code.
// Phi(op(A,B),op(Q,R),op(X,Y)) becomes
// op(Phi(A,Q,X), Phi(B,R,Y)).
Node op = in(1);
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index b78a3e28..2826d192 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -10,7 +10,7 @@ public class ProjNode extends Node {
// Debugging label
public final String _label;
-
+
public ProjNode(MultiNode ctrl, int idx, String label) {
super(ctrl);
_idx = idx;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index d0d3eb06..c9d6c9c8 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -19,7 +19,7 @@ public class ReturnNode extends Node {
public Node ctrl() { return in(0); }
public Node expr() { return in(1); }
-
+
@Override
public String label() { return "Return"; }
@@ -29,7 +29,7 @@ public class ReturnNode extends Node {
}
@Override public boolean isCFG() { return true; }
-
+
@Override
public Type compute() {
return new TypeTuple(ctrl()._type,expr()._type);
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 543d0f83..32045fbc 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -28,8 +28,8 @@ public class ScopeNode extends Node {
_scopes = new Stack<>();
_type = Type.BOTTOM;
}
-
-
+
+
@Override public String label() { return "Scope"; }
@Override
@@ -65,7 +65,7 @@ public class ScopeNode extends Node {
names[syms.get(name)] = name;
return names;
}
-
+
@Override public Type compute() { return Type.BOTTOM; }
@Override public Node idealize() { return null; }
@@ -152,7 +152,7 @@ public class ScopeNode extends Node {
dup.addDef(in(i));
return dup;
}
-
+
/**
* Merges the names whose node bindings differ, by creating Phi node for such names
* The names could occur at all stack levels, but a given name can only differ in the
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
index e94c24e0..022e276d 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -13,7 +13,7 @@ import com.seaofnodes.simple.type.TypeTuple;
public class StartNode extends MultiNode {
final TypeTuple _args;
-
+
public StartNode(Type[] args) {
super();
_args = new TypeTuple(args);
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 9ec39373..a30256f9 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -28,7 +28,7 @@ public class StopNode extends Node {
public ReturnNode ret() {
return nIns()==1 ? (ReturnNode)in(0) : null;
}
-
+
@Override
public Type compute() {
return Type.BOTTOM;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 41d7d092..0d0ed7dc 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -16,7 +16,7 @@ public class SubNode extends Node {
in(2)._print0(sb.append("-"));
return sb.append(")");
}
-
+
@Override
public Type compute() {
if (in(1)._type instanceof TypeInteger i0 &&
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
index 4cee0d3c..2179d3db 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -4,7 +4,7 @@ package com.seaofnodes.simple.type;
/**
* These types are part of a Monotone Analysis Framework,
* @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>.
- * <p>
+ * <p>
* The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a>
* <p>
* This wild lattice theory will be needed later to allow us to easily beef up
@@ -15,7 +15,7 @@ package com.seaofnodes.simple.type;
* actual implementation is darn near trivial and is generally really obvious
* what we're doing with it. Right now, it's just simple integer math to do
* simple constant folding e.g. 1+2 == 3 stuff.
- */
+ */
public class Type {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 3037e45f..9fb4b853 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -28,7 +28,7 @@ public class TypeInteger extends Type {
public boolean isTop() { return !_is_con && _con==0; }
public boolean isBot() { return !_is_con && _con==1; }
- @Override
+ @Override
public StringBuilder _print(StringBuilder sb) {
if (isTop()) return sb.append("IntTop");
if (isBot()) return sb.append("IntBot");
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 3db639cf..33417eb2 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -1,7 +1,7 @@
package com.seaofnodes.simple.type;
public class TypeTuple extends Type {
-
+
public final Type[] _types;
public TypeTuple(Type... _types) {
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index e914f7c5..97666d27 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -26,7 +26,7 @@ return a;""");
StopNode ret = parser.parse(true);
assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
}
-
+
@Test
public void testChapter5Test() {
Parser parser = new Parser(
@@ -41,20 +41,20 @@ return c;""", TypeInteger.BOT);
StopNode ret = parser.parse(true);
assertEquals("return Phi(Region16,4,3);", ret.toString());
}
-
+
@Test
public void testChapter5Return2() {
Parser parser = new Parser(
"""
-if( arg==1 )
- return 3;
-else
- return 4;
+if( arg==1 )
+ return 3;
+else
+ return 4;
#showGraph;""", TypeInteger.BOT);
StopNode stop = parser.parse();
assertEquals("Stop[ return 3; return 4; ]", stop.toString());
}
-
+
@Test
public void testChapter5IfMergeB() {
Parser parser = new Parser(
@@ -140,50 +140,50 @@ return a;""");
StopNode stop = new Parser("return true;").parse();
assertEquals("return 1;",stop.toString());
}
-
+
@Test
public void testChapter5HalfDef() {
- try {
+ try {
new Parser("if( arg==1 ) int b=2; return b;").parse();
fail();
} catch( RuntimeException e ) {
assertEquals("Cannot define a new name on one arm of an if",e.getMessage());
}
}
-
+
@Test
public void testChapter5HalfDef2() {
- try {
+ try {
new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse();
fail();
} catch( RuntimeException e ) {
assertEquals("Undefined name 'b'",e.getMessage());
}
}
-
+
@Test
public void testChapter5BadNum() {
- try {
+ try {
new Parser("return 1-;").parse();
fail();
} catch( RuntimeException e ) {
assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage());
}
}
-
+
@Test
public void testChapter5Keyword1() {
- try {
+ try {
new Parser("int true=0; return true;").parse();
fail();
} catch( RuntimeException e ) {
assertEquals("Expected an identifier, found 'true'",e.getMessage());
}
}
-
+
@Test
public void testChapter5Keyword2() {
- try {
+ try {
new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse();
fail();
} catch( RuntimeException e ) {
@@ -193,14 +193,14 @@ return a;""");
@Test
public void testChapter5Keyword3() {
- try {
+ try {
new Parser("int a=1; ififif(arg)inta=2;return a;").parse();
fail();
} catch( RuntimeException e ) {
assertEquals("Syntax error, expected =: (",e.getMessage());
}
}
-
+
@Test
public void testChapter4Peephole() {
Parser parser = new Parser("return 1+arg+2; #showGraph;");
@@ -228,7 +228,7 @@ return a;""");
StopNode ret = parser.parse();
assertEquals("return (arg*2);", ret.print());
}
-
+
@Test
public void testChapter4Peephole3() {
Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
@@ -242,7 +242,7 @@ return a;""");
StopNode ret = parser.parse();
assertEquals("return arg;", ret.print());
}
-
+
@Test
public void testChapter4VarArg() {
Parser parser = new Parser("return arg; #showGraph;");
@@ -303,7 +303,7 @@ return a;""");
@Test
public void testChapter4Bug3() {
- try {
+ try {
new Parser("inta=1; return a;").parse();
fail();
} catch( RuntimeException e ) {
@@ -317,7 +317,7 @@ return a;""");
StopNode ret = parser.parse();
assertEquals("return (-arg);", ret.print());
}
-
+
@Test
public void testVarDecl() {
Parser parser = new Parser("int a=1; return a;");
@@ -357,7 +357,7 @@ return a;""");
@Test
public void testSelfAssign() {
- try {
+ try {
new Parser("int a=a; return a;").parse();
fail();
} catch( RuntimeException e ) {
@@ -426,7 +426,7 @@ return a;""");
StopNode stop = parser.parse();
StartNode start = Parser.START;
ReturnNode ret = (ReturnNode)stop.in(0);
-
+
assertTrue(ret.ctrl() instanceof ProjNode);
Node expr = ret.expr();
if( expr instanceof ConstantNode con ) {
@@ -449,7 +449,7 @@ return a;""");
@Test
public void testBad1() {
- try {
+ try {
new Parser("ret").parse();
fail();
} catch( RuntimeException e ) {
@@ -459,7 +459,7 @@ return a;""");
@Test
public void testBad2() {
- try {
+ try {
new Parser("return 0123;").parse();
fail();
} catch( RuntimeException e ) {
@@ -475,7 +475,7 @@ return a;""");
@Test
public void testBad4() {
- try {
+ try {
new Parser("return 100").parse();
fail();
} catch( RuntimeException e ) {