From e5f4f7b85fbb91a293a7d89d7b85adfbaeeb51f4 Mon Sep 17 00:00:00 2001 From: Thalia Archibald Date: Fri, 21 Jun 2024 06:13:09 -0700 Subject: Format whitespace (#86) * Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces --- .../java/com/seaofnodes/simple/GraphEvaluator.java | 362 ++++++++++----------- .../com/seaofnodes/simple/GraphVisualizer.java | 12 +- .../main/java/com/seaofnodes/simple/IterPeeps.java | 2 +- .../main/java/com/seaofnodes/simple/Parser.java | 20 +- .../src/main/java/com/seaofnodes/simple/Utils.java | 2 +- .../java/com/seaofnodes/simple/node/AddNode.java | 26 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 4 +- .../com/seaofnodes/simple/node/ConstantNode.java | 8 +- .../java/com/seaofnodes/simple/node/DivNode.java | 4 +- .../java/com/seaofnodes/simple/node/IfNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 6 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 50 +-- .../java/com/seaofnodes/simple/node/NotNode.java | 6 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 4 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 4 +- .../com/seaofnodes/simple/node/ReturnNode.java | 4 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 8 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 4 +- .../java/com/seaofnodes/simple/node/SubNode.java | 2 +- .../main/java/com/seaofnodes/simple/type/Type.java | 18 +- .../com/seaofnodes/simple/type/TypeInteger.java | 4 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 6 +- 27 files changed, 287 insertions(+), 287 deletions(-) (limited to 'chapter09/src/main/java') diff --git a/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java index c4b349bd..9fc51c8e 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -1,181 +1,181 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; - -import java.util.Arrays; -import java.util.BitSet; -import java.util.HashMap; - -public class GraphEvaluator { - - public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } - - public record Result(ResultType type, long value) {} - - /** - * Find the start node from some node in the graph or null if there is no start node - */ - private static StartNode findStart(BitSet visit, Node node) { - if (node == null) return null; - if (node instanceof StartNode start) return start; - if( visit.get(node._nid) ) return null; - visit.set(node._nid); - for( Node def : node._inputs ) { - var res = findStart(visit,def); - if( res != null ) return res; - } - for( Node use : node._outputs ) { - var res = findStart(visit,use); - if( res != null ) return res; - } - return null; - } - - /** - * Find the control output from a control node - */ - private static Node findControl(Node control) { - for( Node use : control._outputs ) { - if (use.isCFG()) return use; - } - return null; - } - - /** - * Find the projection for a node - */ - private static ProjNode findProjection(Node node, int idx) { - for( Node use : node._outputs ) { - if (use instanceof ProjNode proj && proj._idx == idx) return proj; - } - return null; - } - - /** - * Cache values for phi and parameter projection nodes. - */ - private final HashMap cacheValues = new HashMap<>(); - /** - * Cache for loop phis as they can depend on itself or other loop phis - */ - private long[] loopPhiCache = new long[16]; - - private GraphEvaluator() { - } - - private long div(DivNode div) { - long in2 = getValue(div.in(2)); - return in2 == 0 ? 0 : getValue(div.in(1)) / in2; - } - - /** - * Calculate the value of a node - */ - private long getValue(Node node) { - var cache = cacheValues.get(node); - if (cache != null) return cache; - return switch (node) { - case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); - case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); - case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; - case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; - case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; - case DivNode div -> div(div); - case MinusNode minus -> -getValue(minus.in(1)); - case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); - case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; - case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); - default -> throw Utils.TODO("Unexpected node " + node); - }; - } - - /** - * Special case of latchPhis when phis can depend on phis of the same region. - */ - private void latchLoopPhis(RegionNode region, Node prev) { - int idx = Utils.find(region._inputs, prev); - assert idx > 0; - int i = 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) { - var value = getValue(phi.in(idx)); - if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); - loopPhiCache[i++] = value; - } - } - i = 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); - } - } - - /** - * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. - */ - private void latchPhis(RegionNode region, Node prev) { - int idx = Utils.find(region._inputs, prev); - assert idx > 0; - for( Node use : region._outputs ) { - if (use instanceof PhiNode phi) { - var value = getValue(phi.in(idx)); - cacheValues.put(phi, value); - } - } - } - - /** - * Run the graph until either a return is found or the number of loop iterations are done. - */ - private Result evaluate(StartNode start, long parameter, int loops) { - var parameter1 = findProjection(start, 1); - if (parameter1 != null) cacheValues.put(parameter1, parameter); - Node control = findProjection(start, 0); - Node prev = start; - while (control != null) { - Node next; - switch (control) { - case RegionNode region -> { - if (region instanceof LoopNode && region.in(1) != prev) { - if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); - latchLoopPhis(region, prev); - } else { - latchPhis(region, prev); - } - next = findControl(region); - } - case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); - case ReturnNode ret -> { - return new Result(ResultType.VALUE, getValue(ret.in(1))); - } - case ProjNode ignored -> next = findControl(control); - default -> throw Utils.TODO("Unexpected control node " + control); - } - prev = control; - control = next; - } - return new Result(ResultType.FALLTHROUGH, 0); - } - - public static long evaluate(Node graph) { - return evaluate(graph, 0); - } - - public static long evaluate(Node graph, long parameter) { - return evaluate(graph, parameter, 1000); - } - - public static long evaluate(Node graph, long parameter, int loops) { - var res = evaluateWithResult(graph, parameter, loops); - if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); - return res.value; - } - - public static Result evaluateWithResult(Node graph, long parameter, int loops) { - var start = findStart(new BitSet(), graph); - if (start == null) return new Result(ResultType.TIMEOUT, 0); - var evaluator = new GraphEvaluator(); - return evaluator.evaluate(start, parameter, loops); - } - -} +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.Arrays; +import java.util.BitSet; +import java.util.HashMap; + +public class GraphEvaluator { + + public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } + + public record Result(ResultType type, long value) {} + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if (node instanceof StartNode start) return start; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) return res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) return res; + } + return null; + } + + /** + * Find the control output from a control node + */ + private static Node findControl(Node control) { + for( Node use : control._outputs ) { + if (use.isCFG()) return use; + } + return null; + } + + /** + * Find the projection for a node + */ + private static ProjNode findProjection(Node node, int idx) { + for( Node use : node._outputs ) { + if (use instanceof ProjNode proj && proj._idx == idx) return proj; + } + return null; + } + + /** + * Cache values for phi and parameter projection nodes. + */ + private final HashMap cacheValues = new HashMap<>(); + /** + * Cache for loop phis as they can depend on itself or other loop phis + */ + private long[] loopPhiCache = new long[16]; + + private GraphEvaluator() { + } + + private long div(DivNode div) { + long in2 = getValue(div.in(2)); + return in2 == 0 ? 0 : getValue(div.in(1)) / in2; + } + + /** + * Calculate the value of a node + */ + private long getValue(Node node) { + var cache = cacheValues.get(node); + if (cache != null) return cache; + return switch (node) { + case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); + case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); + case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; + case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; + case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; + case DivNode div -> div(div); + case MinusNode minus -> -getValue(minus.in(1)); + case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); + case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; + case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); + default -> throw Utils.TODO("Unexpected node " + node); + }; + } + + /** + * Special case of latchPhis when phis can depend on phis of the same region. + */ + private void latchLoopPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + int i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); + loopPhiCache[i++] = value; + } + } + i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); + } + } + + /** + * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. + */ + private void latchPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + cacheValues.put(phi, value); + } + } + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + private Result evaluate(StartNode start, long parameter, int loops) { + var parameter1 = findProjection(start, 1); + if (parameter1 != null) cacheValues.put(parameter1, parameter); + Node control = findProjection(start, 0); + Node prev = start; + while (control != null) { + Node next; + switch (control) { + case RegionNode region -> { + if (region instanceof LoopNode && region.in(1) != prev) { + if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); + latchLoopPhis(region, prev); + } else { + latchPhis(region, prev); + } + next = findControl(region); + } + case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); + case ReturnNode ret -> { + return new Result(ResultType.VALUE, getValue(ret.in(1))); + } + case ProjNode ignored -> next = findControl(control); + default -> throw Utils.TODO("Unexpected control node " + control); + } + prev = control; + control = next; + } + return new Result(ResultType.FALLTHROUGH, 0); + } + + public static long evaluate(Node graph) { + return evaluate(graph, 0); + } + + public static long evaluate(Node graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + public static long evaluate(Node graph, long parameter, int loops) { + var res = evaluateWithResult(graph, parameter, loops); + if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + return res.value; + } + + public static Result evaluateWithResult(Node graph, long parameter, int loops) { + var start = findStart(new BitSet(), graph); + if (start == null) return new Result(ResultType.TIMEOUT, 0); + var evaluator = new GraphEvaluator(); + return evaluator.evaluate(start, parameter, loops); + } + +} diff --git a/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 657593d2..b4d64d4c 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -31,7 +31,7 @@ public class GraphVisualizer { sb.append("/*\n"); sb.append(stop._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 @@ -51,7 +51,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges nodes(sb, all); - + // Now the scopes, in a cluster no edges if( xScopes != null ) for( ScopeNode xscope : xScopes ) @@ -66,7 +66,7 @@ public class GraphVisualizer { for( ScopeNode xscope : xScopes ) if( !xscope.isDead() ) scopeEdges( sb, xscope ); - + sb.append("}\n"); return sb.toString(); } @@ -200,13 +200,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"); @@ -233,7 +233,7 @@ public class GraphVisualizer { level++; } } - + /** * Finds all nodes in the graph. */ diff --git a/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java index 8103103c..6dafd95f 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -99,7 +99,7 @@ public abstract class IterPeeps { // Visit ALL nodes and confirm the invariant: // Either you are on the WORK worklist OR running `iter()` makes no progress. - + // This invariant ensures that no progress is missed, i.e., when the // worklist is empty we have indeed done all that can be done. To help // with debugging, the {@code assert} is broken out in a place where it is easy to diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java index 5e7da8f8..b3aeeb22 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter09/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 @@ -57,7 +57,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 @@ -83,12 +83,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); } @@ -198,7 +198,7 @@ public class Parser { // No continues yet _continueScope = null; - + // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection @@ -281,7 +281,7 @@ public class Parser { ctrl(ifT.unkeep()); // 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.unkeep()); // Ctrl token is now set to ifFalse projection @@ -292,7 +292,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 @@ -604,7 +604,7 @@ public class Parser { skipWhiteSpace(); return peek()==ch; } - + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -631,7 +631,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 == '_'; } @@ -647,7 +647,7 @@ public class Parser { return new String(_input, start, --_position - start); } - // + // private boolean isPunctuation(char ch) { return "=;[]<>()+-/*".indexOf(ch) != -1; } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Utils.java b/chapter09/src/main/java/com/seaofnodes/simple/Utils.java index 4d663c25..45f15327 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5ffb821e..4e30bb55 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter09/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() { @@ -39,13 +39,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(); @@ -53,7 +53,7 @@ public class AddNode extends Node { // x+(-y) becomes x-y if( rhs instanceof MinusNode minus ) return new SubNode(lhs,minus.in(1)); - + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) // Do we have x + (y + z) ? @@ -73,7 +73,7 @@ public class AddNode extends Node { // the loop will peep as dead after a bit. if( lhs.in(1) == lhs ) return null; - + // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants // lhs.in(2) is con1 here @@ -91,12 +91,12 @@ public class AddNode extends Node { if( phicon!=null ) return phicon; // Now we sort along the spine via rotates, to gather similar things together. - + // Do we rotate (x + y) + z // into (x + z) + y ? if( spine_cmp(lhs.in(2),rhs,this) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); - + return null; } @@ -114,11 +114,11 @@ public class AddNode extends Node { lphi = pcon(lhs.in(2),op); // Will rotate with the Phi push } if( lphi==null ) return null; - + // RHS is a constant or a Phi of constants if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null ) return null; - + // If both are Phis, must be same Region if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) return null; @@ -147,7 +147,7 @@ public class AddNode extends Node { static PhiNode pcon(Node op, Node dep) { return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null; } - + // Compare two off-spine 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. @@ -165,10 +165,10 @@ public class AddNode extends Node { 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/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java index b4691b27..d3fcec95 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter09/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(); } @@ -40,7 +40,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/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index c4ea08b5..9e45198c 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java index ed1a233c..ba06d037 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter09/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 && @@ -33,6 +33,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/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java index 52486772..460dce51 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -42,10 +42,10 @@ public class IfNode extends MultiNode { // Else true branch is reachable if (t instanceof TypeInteger ti && ti.isConstant()) return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; - + return TypeTuple.IF_BOTH; } - + @Override public Node idealize() { // Hunt up the immediate dominator tree. If we find an identical if diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 0b84f897..c192bc20 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,5 +25,5 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } + @Override Node idom() { return entry(); } } diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 524f63a0..dd092c9e 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java index d63d2cb1..7e9f88a2 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter09/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 @@ -35,12 +35,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/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java index eced9a14..2743bd19 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter09/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); } // Find a projection by index diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java index 7c82ffd5..5eb9c076 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/Node.java @@ -49,7 +49,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 @@ -58,7 +58,7 @@ public abstract class Node { * See {@link ...} */ 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. @@ -88,9 +88,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. @@ -104,7 +104,7 @@ public abstract class Node { public final String print() { return _print0(new StringBuilder(), new BitSet()).toString(); } - + // This is the common print: check for repeats, check for DEAD and print // "DEAD" else call the per-Node print1. final StringBuilder _print0(StringBuilder sb, BitSet visited) { @@ -144,13 +144,13 @@ public abstract class Node { } public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } - + 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 @@ -166,19 +166,19 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } public boolean isCFG() { return false; } - + /** * Change a def into a Node. Keeps the edges correct, by removing * the corresponding use->def edge. This may make the original * def go dead. This function is co-recursive with {@link #kill}. *

- + * This method is the normal path for altering a Node, because it does the * proper default edge maintenance. It also immediately 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 @@ -200,7 +200,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. If the def goes dead, it is recursively @@ -255,7 +255,7 @@ public abstract class Node { old_def.kill(); // Kill old def } } - + /** * Kill a Node with no uses, by setting all of its defs * to null. This may recursively kill more Nodes, and is basically dead @@ -298,10 +298,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. @@ -390,7 +390,7 @@ public abstract class Node { } return m; } - + /** * This function needs to be * Monotonic @@ -421,7 +421,7 @@ public abstract class Node { return old; } - + /** * This function rewrites the current Node into a more "idealized" form. * This is the bulk of our peephole rewrite rules, and we use this to @@ -500,8 +500,8 @@ public abstract class Node { IterPeeps.addAll(_deps); _deps.clear(); } - - + + // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. public static final HashMap GVN = new HashMap<>(); @@ -539,7 +539,7 @@ public abstract class Node { _hash=0; // Out of table now } - + // Hash of opcode and inputs @Override public final int hashCode() { if( _hash != 0 ) return _hash; @@ -552,11 +552,11 @@ public abstract class Node { } // Subclasses add extra hash info (such as ConstantNodes constant) int hash() { return 0; } - - + + // ------------------------------------------------------------------------ // Peephole utilities - + // Swap inputs without letting either input go dead during the swap. Node swap12() { unlock(); // Hash is order dependent @@ -619,7 +619,7 @@ public abstract class Node { WVISIT.clear(); return rez; } - + private E _walk( Function pred ) { if( WVISIT.get(_nid) ) return null; // Been there, done that WVISIT.set(_nid); @@ -629,7 +629,7 @@ public abstract class Node { for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; return null; } - + /** * Debugging utility to find a Node by index */ diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java index ab0f4d01..7a520fec 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 2d03b655..ec4c6ad3 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter09/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; } @@ -59,7 +59,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); diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 115bc1eb..25f595a5 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 9468c395..c949c2b2 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -11,7 +11,7 @@ import java.util.BitSet; public class RegionNode extends Node { public RegionNode(Node... nodes) { super(nodes); } - + @Override public String label() { return "Region"; } @@ -78,7 +78,7 @@ public class RegionNode extends Node { return true; return false; } - + // Immediate dominator of Region is a little more complicated. private Node _idom; // Immediate dominator cache @Override Node idom() { diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c10d82d8..922a3649 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter09/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 TypeTuple.make(ctrl()._type,expr()._type); diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 6f72dea2..3abea54d 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -29,8 +29,8 @@ public class ScopeNode extends Node { _scopes = new Stack<>(); _type = Type.BOTTOM; } - - + + @Override public String label() { return "Scope"; } @Override @@ -64,7 +64,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; } @@ -191,7 +191,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/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5693f27b..e399138b 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter09/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 = TypeTuple.make(args); diff --git a/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java index dccc90a9..602feffc 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; public class StopNode extends Node { public final String _src; - + public StopNode(String src) { super(); _src = src; @@ -35,7 +35,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/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java index f81ae6d0..ce83122c 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter09/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/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java index ee6fb741..d0265e83 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/type/Type.java @@ -7,7 +7,7 @@ import java.util.HashMap; /** * These types are part of a Monotone Analysis Framework, * @see see for example this set of slides. - *

+ *

* The types form a lattice; @see a symmetric complete bounded (ranked) lattice. *

* This wild lattice theory will be needed later to allow us to easily beef up @@ -18,7 +18,7 @@ import java.util.HashMap; * 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 { static final HashMap INTERN = new HashMap<>(); @@ -59,11 +59,11 @@ public class Type { // Factory method which interns "this" protected T intern() { T nnn = (T)INTERN.get(this); - if( nnn==null ) + if( nnn==null ) INTERN.put(nnn=(T)this,this); return nnn; } - + private int _hash; // Hash cache; not-zero when set. @Override public final int hashCode() { @@ -74,7 +74,7 @@ public class Type { } // Override in subclasses int hash() { return _type; } - + @Override public final boolean equals( Object o ) { if( o==this ) return true; @@ -84,8 +84,8 @@ public class Type { } // Overridden in subclasses; subclass can assume "this!=t" and java classes are same boolean eq(Type t) { return true; } - - + + // ---------------------------------------------------------- public final Type meet(Type t) { // Shortcut for the self case @@ -114,7 +114,7 @@ public class Type { // True if this "isa" t; e.g. 17 isa TypeInteger.BOT public boolean isa( Type t ) { return meet(t)==t; } - + // ---------------------------------------------------------- // Our lattice is defined with a MEET and a DUAL. // JOIN is dual of meet of both duals. @@ -132,7 +132,7 @@ public class Type { default -> throw Utils.TODO(); // Should not reach here }; } - + // ---------------------------------------------------------- @Override public final String toString() { diff --git a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index df41a526..ba045603 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -28,7 +28,7 @@ public class TypeInteger extends Type { public static TypeInteger constant(long con) { return make(true, con); } - @Override + @Override public StringBuilder _print(StringBuilder sb) { if( this==TOP ) return sb.append("IntTop"); if( this==BOT ) return sb.append("IntBot"); @@ -63,7 +63,7 @@ public class TypeInteger extends Type { if( isConstant() ) return this; // Constants are a self-dual return _con==0 ? BOT : TOP; } - + @Override int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); } @Override diff --git a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 863c5b7d..e82ea00b 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter09/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; private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } @@ -23,7 +23,7 @@ public class TypeTuple extends Type { ts[i] = _types[i].dual(); return make(ts); } - + @Override public StringBuilder _print(StringBuilder sb) { sb.append("["); @@ -45,7 +45,7 @@ public class TypeTuple extends Type { for( Type type : _types ) sum ^= type.hashCode(); return sum; } - + @Override boolean eq( Type t ) { TypeTuple tt = (TypeTuple)t; // Contract -- cgit v1.2.3