diff options
Diffstat (limited to 'chapter05')
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 ) { |