diff options
Diffstat (limited to 'chapter06')
35 files changed, 138 insertions, 139 deletions
diff --git a/chapter06/README.md b/chapter06/README.md index 6f7f3baa..cb265f5b 100644 --- a/chapter06/README.md +++ b/chapter06/README.md @@ -28,7 +28,7 @@ The entire revised Lattice is shown below:  -## Peephole of `if` +## Peephole of `if` * Our general strategy is to continue parsing the entire `if` statement even if we know that one branch is dead. * This approach creates dead nodes which get cleaned up by dead code @@ -44,7 +44,7 @@ The entire revised Lattice is shown below: important observation is that *we __can__ kill the `If` node after __both__ the `Proj` nodes have been created*, because any subsequent control flow can only see the `Proj` nodes. -* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the +* To ensure this, we add a dummy user to `If` before creating the first `Proj` and remove it immediately after, allowing the second `Proj` to trigger a dead code elimination of the `If`. * The live `Proj` gets replaced by the parent of `If`, whereas the dead `Proj` gets replaced by "~Ctrl". * The parsing then continues as normal. @@ -52,7 +52,7 @@ The entire revised Lattice is shown below: * Again keeping with our strategy we merge as normal, including creating `Phi` nodes. * The `Region` may have have one of its inputs as "~Ctrl". This will be seen by the `Phi` which then optimizes itself. If the `Phi` has just one live - input, the `Phi` peephole replaces itself with the remaining input. + input, the `Phi` peephole replaces itself with the remaining input. * Finally, at the end, when the `Region` node is peepholed, we see that it has only one live input and no Phi uses and can be replaced with its one live input. @@ -154,28 +154,28 @@ outer `if`. In compiler parlance, we say that the outer `if` dominates the inner There is a generic way to determine this type of domination; it involves constructing a dominator tree. For details of how to do this, please refer to the paper `A Simple, Fast Dominance Algorithm`.[^1] -However, constructing a dominator tree is an expensive operation; one that we would not like to +However, constructing a dominator tree is an expensive operation; one that we would not like to do in the middle of parsing. Fortunately, since we do not have loops yet, we do not have back edges in our control flow graph. Our control flow graph is essentially hierarchical, tree like. Thus, a simple form of dominator identification is possible. The main idea is that we can assign a `depth` to each control node, this represents the node's depth in the hierarchy. We can compute this depth incrementally as we need to. The nodes that are deeper in the hierarchy -have a greater depth than the ones above. +have a greater depth than the ones above. -Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, +Secondly we know that for our control nodes, except for `Region`s, there is only one incoming control edge, which means that most control nodes have a single immediate dominating control node. `Region` nodes are different as they can have one or more control edges; but, we know that for `if` statements, a `Region` node has exactly two control inputs, one from each branch of the `if`. To find the immediate dominator of a `Region` node in the limited scenario of an `if`, we can follow the immediate dominator of each branch until we find the common ancestor node that dominates both the branches. -If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that +If this ancestor node is also an `if` and its predicate is the same as the current `if`, then we know that the outcome of the present `if` is fully determined. The code that does this check is in the [`compute` method of the `if`](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java#L38-L45). -The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. +The `idom` method in `Node` provides a default implementation of the depth based immediate dominator calculation. `Region`'s [override this](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java#L57-L74) to implement the more complex search described above. It turns out that to simplify the example above, we need a [further peephole in our `Add` node](https://github.com/SeaOfNodes/Simple/blob/main/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java#L64-L67). @@ -185,4 +185,4 @@ With all these changes, the outcome of the peephole is just what we would like t  [^1]: Cooper, K. D. Cooper, Harvey, T. J., and Kennedy, K. (2001). - A Simple, Fast Dominance Algorithm.
\ No newline at end of file + A Simple, Fast Dominance Algorithm. diff --git a/chapter06/docs/06-grammar.md b/chapter06/docs/06-grammar.md index ea779a5a..4cf1cac6 100644 --- a/chapter06/docs/06-grammar.md +++ b/chapter06/docs/06-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/chapter06/docs/06-graph1-post.gv b/chapter06/docs/06-graph1-post.gv index 59214346..31480991 100644 --- a/chapter06/docs/06-graph1-post.gv +++ b/chapter06/docs/06-graph1-post.gv @@ -26,4 +26,4 @@ return 1; Stop3 -> Return13[taillabel=0 color=red]; Return13 -> Start2:p0[taillabel=0 color=red]; Return13 -> Con_12[taillabel=1]; -}
\ No newline at end of file +} diff --git a/chapter06/docs/06-graph1-pre.gv b/chapter06/docs/06-graph1-pre.gv index b04fa2f9..2bfdd23d 100644 --- a/chapter06/docs/06-graph1-pre.gv +++ b/chapter06/docs/06-graph1-pre.gv @@ -49,4 +49,4 @@ return 1; Region14 -> If7:p1[taillabel=2 color=red]; Return16 -> Region14[taillabel=0 color=red]; Return16 -> Con_15[taillabel=1]; -}
\ No newline at end of file +} diff --git a/chapter06/docs/06-graph2-post.gv b/chapter06/docs/06-graph2-post.gv index dacd80fd..61ae2ca1 100644 --- a/chapter06/docs/06-graph2-post.gv +++ b/chapter06/docs/06-graph2-post.gv @@ -30,4 +30,4 @@ return a; Return17 -> Start2:p0[taillabel=0 color=red]; Return17 -> Con_13[taillabel=1]; Stop3 -> Return17[taillabel=0 color=red]; -}
\ No newline at end of file +} diff --git a/chapter06/docs/06-graph3-nonconst.gv b/chapter06/docs/06-graph3-nonconst.gv index 0746be85..7cd4e8e2 100644 --- a/chapter06/docs/06-graph3-nonconst.gv +++ b/chapter06/docs/06-graph3-nonconst.gv @@ -83,4 +83,4 @@ return a+b; Add24 -> Phi_a22[taillabel=2]; Return25 -> Region21[taillabel=0 color=red]; Return25 -> Add24[taillabel=1]; -}
\ No newline at end of file +} diff --git a/chapter06/docs/06-graph3-true.gv b/chapter06/docs/06-graph3-true.gv index 8fdcc5df..9739169c 100644 --- a/chapter06/docs/06-graph3-true.gv +++ b/chapter06/docs/06-graph3-true.gv @@ -32,4 +32,4 @@ return a+b; Stop3 -> Return29[taillabel=0 color=red]; Return29 -> Start2:p0[taillabel=0 color=red]; Return29 -> Con_28[taillabel=1]; -}
\ No newline at end of file +} diff --git a/chapter06/docs/build-graphs.sh b/chapter06/docs/build-graphs.sh index 44d2de3a..6b3f5bb2 100644 --- a/chapter06/docs/build-graphs.sh +++ b/chapter06/docs/build-graphs.sh @@ -10,4 +10,3 @@ dot -Tsvg 06-graph4-nonconst.gv > 06-graph4-nonconst.svg dot -Tsvg 06-graph4-true.gv > 06-graph4-true.svg dot -Tsvg 06-graph4-arg2.gv > 06-graph4-arg2.svg dot -Tsvg lattice.gv > lattice.svg - diff --git a/chapter06/docs/lattice.gv b/chapter06/docs/lattice.gv index 2cf27452..e533ad4a 100644 --- a/chapter06/docs/lattice.gv +++ b/chapter06/docs/lattice.gv @@ -61,4 +61,4 @@ digraph Lattice { INT_MAX; TUPLE} {rank=same; INT_BOT; CTRL} {rank=same; BOT;} -}
\ No newline at end of file +} diff --git a/chapter06/pom.xml b/chapter06/pom.xml index 7a9b466d..fb852b3d 100644 --- a/chapter06/pom.xml +++ b/chapter06/pom.xml @@ -11,4 +11,4 @@ <artifactId>chapter06</artifactId> <packaging>jar</packaging> <name>Chapter 6</name> -</project>
\ No newline at end of file +</project> diff --git a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 704d4802..b30dd450 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index dec0fa57..54c5b15c 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/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 * @@ -166,7 +166,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 @@ -177,7 +177,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 @@ -466,7 +466,7 @@ public class Parser { skipWhiteSpace(); return peek()==ch; } - + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -493,7 +493,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 == '_'; } @@ -509,7 +509,7 @@ public class Parser { return new String(_input, start, --_position - start); } - // + // private boolean isPunctuation(char ch) { return "=;[]<>()+-/*".indexOf(ch) != -1; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java index 4d663c25..45f15327 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5ef9c94a..b37785f6 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter06/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(); @@ -67,7 +67,7 @@ public class AddNode extends Node { return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // 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() ) @@ -81,12 +81,12 @@ public class AddNode extends Node { if( phicon!=null ) return phicon; // 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; } @@ -104,11 +104,11 @@ public class AddNode extends Node { lphi = pcon(lhs.in(2)); // Will rotate with the Phi push } if( lphi==null ) return null; - + // RHS is a constant or a Phi of constants if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) return null; - + // If both are Phis, must be same Region if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) return null; @@ -130,7 +130,7 @@ public class AddNode extends Node { static PhiNode pcon(Node op) { return op instanceof PhiNode phi && phi.allCons() ? phi : null; } - + // Compare two off-spline nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? // Generally constants always go right, then Phi-of-constants, then muls, then others. @@ -139,16 +139,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/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 4eeef873..a9ec6838 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index ba6f55d7..1086037d 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java index 01314c74..bf025453 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java index 1b0fdac7..34846e99 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -43,7 +43,7 @@ public class IfNode extends MultiNode { // Repeated test, dominated on one side. Test result is the same. ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) : null; // Repeated test not dominated on one side - + return TypeTuple.IF_BOTH; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 08924563..0d59ef25 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java index 31683a4e..0380c079 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter06/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,12 +34,12 @@ 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(); diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 81c90f68..7ba1aa19 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java index 4fbcf940..97ba68ab 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -46,7 +46,7 @@ public abstract class Node { */ public Type _type; - + /** * Immediate dominator tree depth, used to approximate a real IDOM during * parsing where we do not have the whole program, and also peepholes @@ -55,7 +55,7 @@ public abstract class Node { * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ int _idepth; - + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -84,9 +84,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. @@ -110,7 +110,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 @@ -127,19 +127,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 @@ -160,7 +160,7 @@ public abstract class Node { // Return self for easy flow-coding return new_def; } - + // Remove the numbered input, compressing the inputs in-place. This // shuffles the order deterministically - which is suitable for Region and // Phi, but not for every Node. @@ -209,7 +209,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 @@ -232,7 +232,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. @@ -257,7 +257,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 @@ -266,13 +266,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 } @@ -292,7 +292,7 @@ public abstract class Node { } return m; } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -361,7 +361,7 @@ public abstract class Node { // ------------------------------------------------------------------------ // Peephole utilities - + // Swap inputs without letting either input go dead during the swap. Node swap12() { Node tmp = in(1); @@ -369,7 +369,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/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java index 5dd6a86e..e3683646 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java index d435ea01..15088e08 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter06/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; } @@ -40,7 +40,7 @@ public class PhiNode extends Node { return live; // 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); @@ -72,7 +72,7 @@ public class PhiNode extends Node { */ private Node singleUniqueInput() { Node live = null; - for( int i=1; i<nIns(); i++ ) + for( int i=1; i<nIns(); i++ ) if( region().in(i)._type != Type.XCONTROL && in(i) != this ) if( live == null || live == in(i) ) live = in(i); else return null; diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java index ef957507..e3a0e44a 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 104735d5..bb7998a3 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -71,5 +71,5 @@ public class RegionNode extends Node { if( lhs==null ) return null; _idepth = lhs._idepth+1; return (_idom=lhs); - } + } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index ba2b83ac..6130d050 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 76fe98b9..a7a04a42 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java index fd0f6c18..c5a45876 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java index c8056fbe..01574dc7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java index 41d7d092..0d0ed7dc 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java index f88403a5..2f0e6171 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 93f5eae3..b30e21d8 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter06/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/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index f8c3b3c8..0f8b95bd 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter06/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/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java index d0e55cc7..fbafad2f 100644 --- a/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -309,7 +309,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( @@ -324,20 +324,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( @@ -423,50 +423,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 ) { @@ -476,14 +476,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;"); @@ -511,7 +511,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;"); @@ -525,7 +525,7 @@ return a;"""); StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testChapter4VarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -586,7 +586,7 @@ return a;"""); @Test public void testChapter4Bug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -600,7 +600,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;"); @@ -640,7 +640,7 @@ return a;"""); @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -709,7 +709,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 ) { @@ -732,7 +732,7 @@ return a;"""); @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -742,7 +742,7 @@ return a;"""); @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { @@ -758,7 +758,7 @@ return a;"""); @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { |