diff options
Diffstat (limited to 'chapter07')
29 files changed, 142 insertions, 142 deletions
diff --git a/chapter07/README.md b/chapter07/README.md index 3e6a7692..03181d18 100644 --- a/chapter07/README.md +++ b/chapter07/README.md @@ -22,7 +22,7 @@ In general, we will rewrite the looping construct as follows: ```java loop_head: -if( !(arg < 10) ) +if( !(arg < 10) ) goto loop_exit; arg = arg + 1; goto loop_head; @@ -39,7 +39,7 @@ From an SSA[^1] point of view, since `arg` flows back, it requires a `phi` node // loop_head: arg2 = phi(arg1, arg3); -if( !(arg2 < 10) ) +if( !(arg2 < 10) ) goto loop_exit; arg3 = arg2 + 1; goto loop_head; @@ -47,11 +47,11 @@ goto loop_head; loop_exit: ``` -Notice that the phi for `arg2` refers to `arg3`, which is not known at the time we parse the `while` loop predicate. This is the crux of the problem that we need +Notice that the phi for `arg2` refers to `arg3`, which is not known at the time we parse the `while` loop predicate. This is the crux of the problem that we need to solve in order to successfully construct the Sea of Nodes graph, which is always in SSA form. Recall from [Chapter 5](../chapter05/README.md) that when parsing `if` statements, we clone the symbol tables as we go past the `if` predicate. -Later we merge the two sets of symbol tables at a `Region` - creating phis for all names that encountered a change in definition within the two +Later we merge the two sets of symbol tables at a `Region` - creating phis for all names that encountered a change in definition within the two branches of the `if` statement. In the case of the `if` statement, the phis are created at the merge point when we already know the definitions that are being merged. @@ -69,10 +69,10 @@ created until we complete parsing the loop body. This is because our phis are no ## Detailed Steps -1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, - the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is +1. We start by creating a new subclass of `Region`, the `Loop`. The `Loop` gets two control inputs, + the first is the entry point, i.e. the current binding to `$ctrl`, and second (`null`) is a placeholder for the back edge that is set after loop is parsed. The absence of a back edge is used as an indicator to switch off peepholes of the region and - associated phis. + associated phis. ```java ctrl(new LoopNode(ctrl(),null).peephole()); @@ -87,13 +87,13 @@ created until we complete parsing the loop body. This is because our phis are no // Make a new Scope for the body. _scope = _scope.dup(true); ``` - + Note that the `dup` call is given an argument `true`. This triggers creating phis. The code that creates the phis in the `dup()` method is shown below. ```java // boolean loop=true if this is a loop region - + String[] names = reverseNames(); // Get the variable names dup.add_def(ctrl()); // Control input is just copied for( int i=1; i<nIns(); i++ ) { @@ -108,7 +108,7 @@ created until we complete parsing the loop body. This is because our phis are no } } ``` - + Inside the `else` block both the duplicated scope and the original scope get the same phi node. 3. Next we set up the `if` condition, very much like we do with regular ifs. @@ -124,8 +124,8 @@ created until we complete parsing the loop body. This is because our phis are no Node ifF = new ProjNode(ifNode, 1, "False").peephole(); ``` -4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, - therefore `$ctrl` in the exit scope is set to the `False` projection. +4. We make another clone of the current scope. This will be the exit scope that will live after the loop ends, + therefore `$ctrl` in the exit scope is set to the `False` projection. The exit scope captures any side effects of the loop's predicate. ```java @@ -143,7 +143,7 @@ created until we complete parsing the loop body. This is because our phis are no ``` 6. After the loop body is parsed, we go back and process all the phis we created earlier. - + ```java // The true branch loops back, so whatever is current control gets // added to head loop as input @@ -169,7 +169,7 @@ created until we complete parsing the loop body. This is because our phis are no ``` 7. Finally, both the original scope (head) we started with, and the duplicate created for the body are killed. - At exit the false control is the current control (step 4), and exit scope is set as the current scope. + At exit the false control is the current control (step 4), and exit scope is set as the current scope. ```java // At exit the false control is the current control, and @@ -228,4 +228,4 @@ return b; Efficiently computing static single assignment form and the control dependence graph, in ACM Transactions on Programming Languages and Systems, 13(4):451-490, 1991. [^2]: Click, C. (1995). - Combining Analyses, Combining Optimizations, 103.
\ No newline at end of file + Combining Analyses, Combining Optimizations, 103. diff --git a/chapter07/docs/07-grammar.md b/chapter07/docs/07-grammar.md index 50a2a129..29a730b6 100644 --- a/chapter07/docs/07-grammar.md +++ b/chapter07/docs/07-grammar.md @@ -10,7 +10,7 @@ program statement : returnStatement | declStatement - | blockStatment + | blockStatment | expressionStatement | ifStatement | whileStatement @@ -48,15 +48,15 @@ returnStatement expression : comparisonExpression ; - + comparisonExpression : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* ; - + additiveExpression - : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* ; - + multiplicativeExpression : unaryExpression (('*' | '/') unaryExpression)* ; @@ -78,11 +78,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/chapter07/pom.xml b/chapter07/pom.xml index 28d119b5..2f063952 100644 --- a/chapter07/pom.xml +++ b/chapter07/pom.xml @@ -11,4 +11,4 @@ <artifactId>chapter07</artifactId> <packaging>jar</packaging> <name>Chapter 7</name> -</project>
\ No newline at end of file +</project> diff --git a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 64ffc771..07f1af21 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -30,7 +30,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 @@ -50,7 +50,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges nodes(sb, all); - + // Now the scopes, in a cluster no edges for( ScopeNode scope : parser._xScopes ) scope( sb, scope ); @@ -61,7 +61,7 @@ public class GraphVisualizer { // Walk the active Scope edges for( ScopeNode scope : parser._xScopes ) scopeEdges( sb, scope ); - + sb.append("}\n"); return sb.toString(); } @@ -195,13 +195,13 @@ public class GraphVisualizer { sb.append(" color=red"); // Backedges do not add a ranking constraint if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) - sb.append(" constraint=false"); + sb.append(" constraint=false"); sb.append("];\n"); } } } } - + // Walk the scope edges private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); @@ -226,7 +226,7 @@ public class GraphVisualizer { level++; } } - + /** * Finds all nodes in the graph. */ diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java index 7cc52e78..349b2ce7 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter07/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 @@ -55,7 +55,7 @@ public class Parser { add("while"); }}; - + /** * 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 @@ -76,12 +76,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); } @@ -102,7 +102,7 @@ public class Parser { return STOP; } - + /** * Parses a block * @@ -236,7 +236,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 @@ -247,7 +247,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 @@ -536,7 +536,7 @@ public class Parser { skipWhiteSpace(); return peek()==ch; } - + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -563,7 +563,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 == '_'; } @@ -579,7 +579,7 @@ public class Parser { return new String(_input, start, --_position - start); } - // + // private boolean isPunctuation(char ch) { return "=;[]<>()+-/*".indexOf(ch) != -1; } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Utils.java b/chapter07/src/main/java/com/seaofnodes/simple/Utils.java index 4d663c25..45f15327 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter07/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/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java index d23fa7c5..8f3e5a98 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -8,7 +8,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 @@ -17,7 +17,7 @@ public class AddNode extends Node { in(2)._print0(sb.append("+"), visited); return sb.append(")"); } - + @Override public Type compute() { @@ -44,13 +44,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(); @@ -69,7 +69,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() ) @@ -83,12 +83,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; } @@ -106,11 +106,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; @@ -132,7 +132,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. @@ -141,16 +141,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/chapter07/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/BoolNode.java index d65fbf14..0c32d50d 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -12,7 +12,7 @@ abstract public class BoolNode extends Node { } abstract String op(); // String opcode name - + @Override public String label() { return getClass().getSimpleName(); } @@ -41,7 +41,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/chapter07/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 0e13d2f2..13006bfb 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -23,10 +23,10 @@ public class ConstantNode extends Node { super(Parser.START); _con = type; } - + @Override public String label() { return ""+_con; } - + @Override public String uniqueName() { return "Con_" + _nid; } @@ -34,9 +34,9 @@ public class ConstantNode extends Node { StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con._print(sb); } - + @Override public boolean isMultiTail() { return true; } - + @Override public Type compute() { return _con; } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/DivNode.java index b0e12547..2213d2e7 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -18,7 +18,7 @@ public class DivNode extends Node { in(2)._print0(sb.append("/"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && @@ -34,6 +34,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/chapter07/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/IfNode.java index e573010d..0f414c08 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -47,7 +47,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/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java index aeb8a7f9..81f707ec 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -24,5 +24,5 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } + @Override Node idom() { return entry(); } } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8a96693d..3d944fd4 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -9,15 +9,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, BitSet visited) { in(1)._print0(sb.append("(-"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/MulNode.java index 70e6c0db..2e701a4e 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -9,7 +9,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 @@ -36,12 +36,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/chapter07/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 81c90f68..7ba1aa19 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter07/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/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java index d9d9366f..35b07781 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter07/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. @@ -140,10 +140,10 @@ public abstract class Node { public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } - + // ------------------------------------------------------------------------ // Graph Node & Edge manipulation - + /** * Gets the ith input node * @param i Offset of the input node @@ -160,19 +160,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 @@ -193,7 +193,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. @@ -242,7 +242,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 @@ -276,10 +276,10 @@ public abstract class Node { } kill(); } - + // ------------------------------------------------------------------------ // Graph-based optimizations - + /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. @@ -304,7 +304,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 @@ -313,13 +313,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 } @@ -339,7 +339,7 @@ public abstract class Node { } return m; } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -408,7 +408,7 @@ public abstract class Node { // ------------------------------------------------------------------------ // Peephole utilities - + // Swap inputs without letting either input go dead during the swap. Node swap12() { Node tmp = in(1); @@ -416,7 +416,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/chapter07/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/NotNode.java index 04e6c75b..39df410d 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -9,15 +9,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, BitSet visited) { in(1)._print0(sb.append("(!"), visited); return sb.append(")"); } - + @Override public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java index e6cf338b..2a4ff52a 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; 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; } @@ -35,7 +35,7 @@ public class PhiNode extends Node { @Override public Type compute() { if( !(region() instanceof RegionNode r) || r.inProgress() ) - return Type.BOTTOM; + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -53,7 +53,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); @@ -85,7 +85,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/chapter07/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 79ba9d13..c263502d 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -12,7 +12,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/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 768c9558..acaadaf1 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; public class RegionNode extends Node { public RegionNode(Node... nodes) { super(nodes); } - + @Override public String label() { return "Region"; } diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 4dea773a..312058b9 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -21,7 +21,7 @@ public class ReturnNode extends Node { public Node ctrl() { return in(0); } public Node expr() { return in(1); } - + @Override public String label() { return "Return"; } @@ -31,7 +31,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/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 80a09ff4..a4fcbe65 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter07/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 @@ -59,7 +59,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; } @@ -157,7 +157,7 @@ public class ScopeNode extends Node { } 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 @@ -176,7 +176,7 @@ public class ScopeNode extends Node { that.kill(); // Kill merged scope return r.unkeep().peephole(); } - + // Merge the backedge scope into this loop head scope // We set the second input to the phi from the back edge (i.e. loop body) public void endLoop(ScopeNode back, ScopeNode exit ) { diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java index 19d03e0f..01f1485a 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -15,7 +15,7 @@ import java.util.BitSet; public class StartNode extends MultiNode { final TypeTuple _args; - + public StartNode(Type[] args) { super(); _args = new TypeTuple(args); diff --git a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java index a0aacf2b..417790d9 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -30,7 +30,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/chapter07/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter07/src/main/java/com/seaofnodes/simple/node/SubNode.java index 1484ab8a..4a06fcb3 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -18,7 +18,7 @@ public class SubNode extends Node { in(2)._print0(sb.append("-"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && diff --git a/chapter07/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter07/src/main/java/com/seaofnodes/simple/type/Type.java index f88403a5..2f0e6171 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter07/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/chapter07/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter07/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 93f5eae3..b30e21d8 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter07/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/chapter07/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter07/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index f8c3b3c8..0f8b95bd 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter07/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/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java index efcf90f5..9afcc49a 100644 --- a/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -41,7 +41,7 @@ return a; StopNode stop = parser.parse(true); assertEquals("return Phi(Region23,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } - + @Test public void testChapter7WhileNested() { Parser parser = new Parser( @@ -540,7 +540,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( @@ -555,20 +555,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( @@ -654,50 +654,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 ) { @@ -707,14 +707,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;"); @@ -742,7 +742,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;"); @@ -756,7 +756,7 @@ return a;"""); StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testChapter4VarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -817,7 +817,7 @@ return a;"""); @Test public void testChapter4Bug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -831,7 +831,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;"); @@ -871,7 +871,7 @@ return a;"""); @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -940,7 +940,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 ) { @@ -963,7 +963,7 @@ return a;"""); @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -973,7 +973,7 @@ return a;"""); @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { @@ -989,7 +989,7 @@ return a;"""); @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { |