diff options
21 files changed, 210 insertions, 173 deletions
diff --git a/chapter11/README.md b/chapter11/README.md index a2dc753c..4c5b6412 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -123,7 +123,7 @@ We have already alluded to several components of the GCM algorithm in passing ab infinite loops and create a dummy edge connecting the loop to the Stop node. * Loops are already identified in the Simple SoN graph, so we do not need a loop discovery step. However, we need to compute the loop depth associated with each CFG node. * In [Chapter 6](../chapter06/README.md) we explained the concept of Dominators. Dominators are key to the GCM algo, and we extend our incremental dominator discovery algo to - ensure that it meets the requirements of the algo (TODO did we enhance it in this chapter?). + ensure that it meets the requirements of the algo. * We already mentioned the two phases of the algo - the Early Scheduling and the Late Scheduling. * In addition, we need to add anti-dependency edges between Loads and Stores in certain scenarios to enforce correct execution order. * There are a few changes to our Node hierarchy to help us implement the GCM algo more conveniently. These changes do not conceptually alter the Node hierarchy we inherited from the previous chapters. @@ -482,8 +482,21 @@ The code for computing the late schedule is shown below. ## Inserting Anti Dependencies -To ensure that Loads and Stores to the same memory location are correctly ordered, -we insert anti-dependencies when a Load's path up the dominator tree crosses the path of a Store that is the user of the Load's memory input. +To ensure that Loads and Stores to the same memory location are correctly ordered, we insert an edge from the Load to the Store as described below. +We call these edges anti-dependencies because they do not represent the Def-Use dependency that we normally capture in SoN, and are purely present as scheduling constraints. + +We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load). + +Looking backwards from the Load we follow the memory edge to the "memory definer" - a start-mem-projection, or a phi-mem, or a store. +We look forwards from the mem-def to all its mem-def users. There is always at least one; there may be many. These completely (all of it) and exactly (no doubling up) cover the forward memory space, sort of like a network flow problem - but we limit our analysis to same-alias, +because for example, a start-mem-proj produces all aliases. This gives us a candidate set of mem-defs; some of these need the anti-dependency on the Load, but not all. + +Since we're in the middle of "schedule late", we have already computed all the late schedules of a Load's users, and we have the Loads "Least Common Ancestor" of uses, the LCA or late position. +We inspect the set of mem-defs that might impact the Load, and either add an anti-dependency from Store to Load, or raise the Loads effective LCA. +For Phi mem-defs, we look at the Phi inputs and place an effective use on that block; this will be used to raise the Load's LCA. +For stores, we do the same - until/unless we find stores with the SAME block as the Load's LCA. Then we add the anti-dependency edge to force ordering within the same block. + +The implementation is shown below. ```java private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java index 523c72de..7e957d9d 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/Parser.java @@ -76,12 +76,12 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; + // Mapping from a Struct name to a Struct. public static Map<String, TypeStruct> OBJS = new HashMap<>(); public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); - Type.reset(); OBJS.clear(); SCHEDULED = false; _lexer = new Lexer(source); @@ -178,7 +178,7 @@ public class Parser { */ private Field parseField(String sname) { if( matchx("int") ) // Currently only parsing "int" type fields - return require(Field.make(sname,TypeInteger.BOT,requireId()),";"); + return require(Field.make(requireId().intern(),TypeInteger.BOT),";"); throw errorSyntax("A field type is expected, only type 'int' is supported at present"); } @@ -300,7 +300,7 @@ public class Parser { cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the - // continue + // "continue" if (toScope == null) return cur; // toScope is either the break scope, or a scope that was created here @@ -598,8 +598,11 @@ public class Parser { */ private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - for( Field field: obj._fields ) - memAlias(field, new StoreNode(field, memAlias(field), n, ZERO).peephole()); + int alias = START._aliasStarts.get(obj._name); + for( Field field : obj._fields ) { + memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, ZERO).peephole()); + alias++; + } return n.unkeep(); } @@ -607,8 +610,9 @@ public class Parser { // variables are prefixed by $ so they cannot be referenced in Simple code. // Using vars has the benefit that all the existing machinery of scoping // and phis work as expected - private Node memAlias(Field fld ) { return _scope.lookup(fld.aliasName() ); } - private Node memAlias(Field fld, Node st) { return _scope.update(fld.aliasName(), st); } + private Node memAlias(int alias ) { return _scope.lookup(memName(alias) ); } + private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); } + public static String memName(int alias) { return ("$"+alias).intern(); } /** * Parse postfix expression. For now this is just a field @@ -624,22 +628,23 @@ public class Parser { if( !(expr._type instanceof TypeMemPtr ptr) ) throw error("Expected struct reference but got " + expr._type.str()); - String name = requireId(); - Field field = ptr._obj==null ? null : ptr._obj.get(name); - if( field == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - field = field.glb(); // Even if the parser knows the field is a high type, use the low one + String name = requireId().intern(); + int idx = ptr._obj==null ? -1 : ptr._obj.find(name); + if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + int alias = START._aliasStarts.get(ptr._obj._name)+idx; if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - memAlias(field, new StoreNode(field, memAlias(field), expr, val).peephole()); + memAlias(alias, new StoreNode(name, alias, memAlias(alias), expr, val).peephole()); return expr; // "obj.a = expr" returns the expression while updating memory } } - return parsePostfix(new LoadNode(field, memAlias(field), expr).peephole()); + Type declaredType = ptr._obj._fields[idx]._type; + return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole()); } /** @@ -799,6 +804,7 @@ public class Parser { String getAnyNextToken() { if (isEOF()) return ""; if (isIdStart(peek())) return parseId(); + if (isNumber(peek())) return parseNumberString(); if (isPunctuation(peek())) return parsePunctuation(); return String.valueOf(peek()); } @@ -807,13 +813,16 @@ public class Parser { boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - int start = _position; - while (isNumber(nextChar())) ; - String snum = new String(_input, start, --_position - start); + String snum = parseNumberString(); if (snum.length() > 1 && snum.charAt(0) == '0') throw error("Syntax error: integer values cannot start with '0'"); return TypeInteger.constant(Long.parseLong(snum)); } + private String parseNumberString() { + int start = _position; + while (isNumber(nextChar())) ; + return new String(_input, start, --_position - start); + } // First letter of an identifier private boolean isIdStart(char ch) { diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/DivNode.java index ed1a233c..ba06d037 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter11/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/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d728b818..4ed06da4 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -12,29 +12,31 @@ import java.util.BitSet; */ public class LoadNode extends MemOpNode { + Type _declaredType; /** * Load a value from a ptr.field. * - * @param field The struct field we are loading + * @param name The field we are loading * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct from where we load a field */ - public LoadNode(Field field, Node memSlice, Node memPtr) { - super(field, memSlice, memPtr); + public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { + super(name, alias, memSlice, memPtr); + _declaredType = glb; } @Override public String label() { return "Load"; } @Override - public String glabel() { return "."+_field._fname; } + public String glabel() { return "."+_name; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_field._fname); } + StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } @Override public Type compute() { - return _field._type; + return _declaredType; } @Override @@ -43,23 +45,34 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && ptr() == st.ptr() ) { // Must check same object - assert _field==st._field; // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } - // Push a Load up through a Phi, as long as it collapses on at least one arm. - // BEFORE (2 Sts, 1 Ld): AFTER (1 St): + // Push a Load up through a Phi, as long as it collapses on at least + // one arm. If at a Loop, the backedge MUST collapse - else we risk + // spinning the same transform around the loop indefinitely. + // BEFORE (2 Sts, 1 Ld): AFTER (1 St, 0 Ld): // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode phi && phi.nIns()== 3 && - ((phi.in(1) instanceof StoreNode st1 && ptr()==st1.ptr() && phi.in(2)!=phi ) || - (phi.in(2) instanceof StoreNode st2 && ptr()==st2.ptr() && phi.in(1)!=phi ) ) ) { - Node ld1 = new LoadNode(_field,phi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_field,phi.in(2),ptr()).peephole(); - return new PhiNode(_field._fname,_type,phi.region(),ld1,ld2); + if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + // Profit on RHS/Loop backedge + if( profit(memphi,2) || + // Else must not be a loop to count profit on LHS. + (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { + Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); + return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + } } return null; } + + // Profitable if we find a matching Store on this Phi arm. + private boolean profit(PhiNode phi, int idx) { + Node px = phi.in(idx); + return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); + } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index a8fb18ec..7f8d060a 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -7,16 +7,18 @@ import com.seaofnodes.simple.type.TypeMemPtr; /** * Convenience common base for Load and Store. */ -abstract class MemOpNode extends Node { +public abstract class MemOpNode extends Node { - protected Field _field; + public final String _name; + public final int _alias; - public MemOpNode(Field field, Node memSlice, Node memPtr) { + public MemOpNode(String name, int alias, Node memSlice, Node memPtr) { super(null, memSlice, memPtr); - _field = field; + _name = name; + _alias = alias; } - public MemOpNode(Field field, Node memSlice, Node memPtr, Node value) { - this(field, memSlice, memPtr); + public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { + this(name, alias, memSlice, memPtr); addDef(value); } @@ -26,19 +28,17 @@ abstract class MemOpNode extends Node { @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant - return _field.equals(mem._field); + return _alias==mem._alias; // When comparing types error to use "equals"; always use "==" } @Override - int hash() { - return _field._alias; - } + int hash() { return _alias; } @Override String err() { Type ptr = ptr()._type; return (ptr==Type.BOTTOM || (ptr instanceof TypeMemPtr tmp && tmp._nil) ) - ? "Might be null accessing '" + _field.str() + "'" + ? "Might be null accessing '" + _name + "'" : null; } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 524f63a0..9b687613 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter11/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) @@ -26,5 +26,11 @@ public class MinusNode extends Node { } @Override - public Node idealize() { return null; } + public Node idealize() { + // -(-x) is x + if( in(1) instanceof MinusNode minus ) + return minus.in(1); + + return null; + } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/MulNode.java index d63d2cb1..7e9f88a2 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter11/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/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java index 3532dbdd..fc49ad6a 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java @@ -85,6 +85,8 @@ public abstract class Node implements OutNode { // ------------------------------------------------------------------------ + // 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. @@ -255,10 +257,11 @@ public abstract class Node implements OutNode { public <N extends Node> N keep() { return addUse(null); } // Remove bogus null. public <N extends Node> N unkeep() { - assert Utils.find(_outputs, null) != -1; delUse(null); return (N)this; } + // Test "keep" status + public boolean iskeep() { return Utils.find(_outputs,null) != -1; } // Replace self with nnn in the graph, making 'this' go dead @@ -355,7 +358,7 @@ public abstract class Node implements OutNode { private Node deadCodeElim(Node m) { // If self is going dead and not being returned here (Nodes returned // from peephole commonly have no uses (yet)), then kill self. - if( m != this && isUnused() ) { + if( m != this && isUnused() && !isDead() ) { // Killing self - and since self recursively kills self's inputs we // might end up killing 'm', which we are returning as a live Node. // So we add a bogus extra null output edge to stop kill(). diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 46cc3369..a07dc140 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -100,7 +100,7 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom() instanceof IfNode iff && iff.pred()==val ) { + if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)region().in(nullx); while( idom.in(0) != iff ) idom = idom.idom(); diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 0b7eeb46..dcc7ccef 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -36,6 +36,7 @@ public class RegionNode extends CFGNode { @Override public Node idealize() { if( inProgress() ) return null; + // Delete dead paths into a Region int path = findDeadInput(); if( path != 0 && // Do not delete the entry path of a loop (ok to remove the back @@ -62,6 +63,15 @@ public class RegionNode extends CFGNode { // If down to a single input, become that input if( nIns()==2 && !hasPhi() ) return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own + + // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" + if( !hasPhi() && // No Phi users, just a control user + in(1) instanceof ProjNode p1 && + in(2) instanceof ProjNode p2 && + p1.in(0)==p2.in(0) && + p1.in(0) instanceof IfNode iff ) + return iff.ctrl(); + return null; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8a50eb56..843ce733 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -237,7 +237,8 @@ public class ScopeNode extends Node { IterPeeps.addAll(phi._outputs); phi.moveDepsToWorklist(); if( in != phi ) { - phi.subsume(in); + if( !phi.iskeep() ) // Keeping phi around for parser elsewhere + phi.subsume(in); setDef(i,in); // Set the update back into Scope } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java index 4365c608..62fc8a6b 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; - import java.util.Arrays; import java.util.BitSet; +import java.util.HashMap; import java.util.HashSet; /** @@ -18,10 +19,16 @@ public class StartNode extends CFGNode implements MultiNode { // This field is NOT final, because the tuple expands as we add memory aliases TypeTuple _args; + // The alias number of the first field in the struct. + // + public final HashMap<String,Integer> _aliasStarts; + + public StartNode(Type[] args) { super(); _args = TypeTuple.make(args); _type = _args; + _aliasStarts = new HashMap<>(); } /** @@ -29,20 +36,21 @@ public class StartNode extends CFGNode implements MultiNode { * as the key. */ public void addMemProj( TypeStruct ts, ScopeNode scope) { - if( ts._fields.length==0 ) return; // No projections to add int len = _args._types.length; - int max = ts._fields[ts._fields.length-1]._alias; // Max alias - if( len > max ) return; // Already big enough + _aliasStarts.put(ts._name,len); + // resize the tuple's type array to include all fields of the struct - Type[] args = Arrays.copyOf(_args._types, max+1); + int max = len + ts._fields.length; + Type[] args = Arrays.copyOf(_args._types, max); + // The new members of the tuple get a mem type with an alias - for( int alias = len; alias <= max; alias++ ) + for( int alias = len; alias < max; alias++ ) args[alias] = TypeMem.make(alias); _type = _args = TypeTuple.make(args); // For each of the fields we now add a mem projection. Note that the // alias matches the slot of the field in the tuple - for( int alias = len; alias <= max; alias++ ) { - String name = "$"+alias; + for( int alias = len; alias < max; alias++ ) { + String name = Parser.memName(alias); Node n = new ProjNode(this, alias, name).peephole(); scope.define(name, args[alias], n); } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 00d75f02..7c41e767 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -11,32 +12,30 @@ import java.util.BitSet; public class StoreNode extends MemOpNode { /** - * @param field The struct field we are assigning to + * @param name The struct field we are assigning to * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(Field field, Node memSlice, Node memPtr, Node value) { - super(field, memSlice, memPtr, value); + public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { + super(name, alias, memSlice, memPtr, value); } @Override public String label() { return "Store"; } @Override - public String glabel() { return "."+_field._fname+" ="; } + public String glabel() { return "."+_name+" ="; } @Override public boolean isMem() { return true; } public Node val() { return in(3); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(".").append(_field._fname).append("=").append( val()).append(";"); + return sb.append(".").append(_name).append("=").append( val()).append(";"); } @Override - public Type compute() { - return TypeMem.make(_field._alias); - } + public Type compute() { return TypeMem.make(_alias); } @Override public Node idealize() { @@ -49,7 +48,7 @@ public class StoreNode extends MemOpNode { // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { - assert _field==st._field; // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java index 663b005c..7137f38e 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -36,6 +36,14 @@ public class SubNode extends Node { if( in(1)==in(2) ) return Parser.ZERO; + // x - (-y) is x+y + if( in(2) instanceof MinusNode minus ) + return new AddNode(in(1),minus.in(1)); + + // (-x) - y is -(x+y) + if( in(1) instanceof MinusNode minus ) + return new MinusNode(new AddNode(minus.in(1),in(2)).peephole()); + return null; } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java index 179eacf5..e1c337d4 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/Field.java @@ -8,78 +8,46 @@ import java.util.ArrayList; */ public class Field extends Type { - /** - * Represents the starting alias ID - which is 2 because then it nicely - * slots into Start's projections. Start already uses slots 0-1. - */ - private static final int _RESET_ALIAS_ID = 2; + // The pair {fieldName,type} uniquely identifies a field. - /** - * Alias ID generator - we start at 2 because START uses 0 and 1 slots, - * by starting at 2, our alias ID is nicely mapped to a slot in Start. - */ - private static int _ALIAS_ID = _RESET_ALIAS_ID; - - // The triple {structName,type,fieldName} uniquely identifies a field. - - // Struct name - public final String _sname; - // Type of the field - public final Type _type; // Field name public final String _fname; + // Type of the field + public final Type _type; - // Convenience field: Owning TypeStruct - public TypeStruct _obj; - - // Convenience field: unique alias number - public final int _alias; - - private Field(String sname, Type type, String fname, int alias) { + private Field(String fname, Type type ) { super(TFLD); - _sname = sname; - _type = type; _fname = fname; - _alias = alias; + _type = type; } // Make with existing alias - private static Field make( String sname, Type type, String fname, int alias ) { - return new Field(sname,type,fname,alias).intern(); - } - // Make with new alias - public static Field make( String sname, Type type, String fname ) { - Field fld = make(sname,type,fname,_ALIAS_ID).intern(); - if( fld._alias == _ALIAS_ID ) - _ALIAS_ID++; - return fld; + public static Field make( String fname, Type type ) { + return new Field(fname,type).intern(); } - public static final Field TEST = make("test",TypeInteger.ZERO,"test"); + public static final Field TEST = make("test",TypeInteger.ZERO); public static void gather(ArrayList<Type> ts) { ts.add(TEST); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant - assert _sname.equals(fld._sname); assert _fname.equals(fld._fname); - return make(_sname,_type.meet(fld._type),_fname); + return make(_fname,_type.meet(fld._type)); } @Override - public Field dual() { return make(_sname,_type.dual(),_fname,_alias); } - - public String aliasName() { return "$"+_alias; }; + public Field dual() { return make(_fname,_type.dual()); } @Override public Field glb() { - return make(_sname,_type.glb(),_fname,_alias); + return make(_fname,_type.glb()); } // Override in subclasses - int hash() { return _sname.hashCode() ^ _type.hashCode() ^ _fname.hashCode(); } + int hash() { return _fname.hashCode() ^ _type.hashCode(); } boolean eq(Type t) { Field f = (Field)t; - return _sname.equals(f._sname) && _type==f._type && _fname.equals(f._fname); + return _fname.equals(f._fname) && _type==f._type; } @@ -89,8 +57,4 @@ public class Field extends Type { } @Override public String str() { return _fname; } - - static void resetField() { - _ALIAS_ID = _RESET_ALIAS_ID; - } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter11/src/main/java/com/seaofnodes/simple/type/Type.java index 34e66a0c..aa0ba1ea 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/Type.java @@ -184,8 +184,4 @@ public class Type { // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } - - public static void reset() { - Field.resetField(); - } } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4fcbb638..29102675 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -18,8 +18,6 @@ public class TypeStruct extends Type { super(Type.TSTRUCT); _name = name; _fields = fields; - for( Field f : _fields ) - f._obj = this; } public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } @@ -30,11 +28,11 @@ public class TypeStruct extends Type { public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); } - public Field get(String fname) { - for( Field f : _fields ) - if( f._fname.equals(fname) ) - return f; - return null; + public int find(String fname) { + for( int i=0; i<_fields.length; i++ ) + if( _fields[i]._fname.equals(fname) ) + return i; + return -1; } @Override @@ -110,11 +108,11 @@ public class TypeStruct extends Type { @Override public StringBuilder _print(StringBuilder sb) { - sb.append(_name).append(" {"); + sb.append(_name).append(" {\n"); for( Field f : _fields ) { sb.append(" ").append(f._fname).append(":"); f._type._print(sb); - sb.append(";"); + sb.append(";\n"); } return sb.append("}"); } diff --git a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index f522542d..01bcbe9f 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -43,7 +43,8 @@ public class TypeTuple extends Type { for( Type t : _types ) t._print(sb).append(","); sb.setLength(sb.length()-1); - return sb.append("]"); + sb.append("]"); + return sb; } @Override public String str() { return _print(new StringBuilder()).toString(); } @@ -57,8 +58,7 @@ public class TypeTuple extends Type { for( Type t : _types ) t.typeName(sb).append(","); sb.setLength(sb.length()-1); - sb.append("]"); - return sb; + return sb.append("]"); } public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 451d3da2..06065702 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,13 +1,41 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.*; import org.junit.Test; +import java.util.Arrays; + import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter10Test { + @Test + public void testFuzzer() { + Parser parser = new Parser( +""" +int a = arg/3; +int b = arg*5; +int x = arg*7; +int y = arg/11; +int p; int g; int h; +if( (arg/13)==0 ) { + p = x + y; + g = x; + h = y; +} else { + p = a + b; + g = a; + h = b; +} +int r = g+h; +return p-r; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 0;", stop.toString()); + } @Test public void testStruct() { @@ -167,7 +195,8 @@ while(arg) { return ret; """); try { parser.parse(true).iterate(true); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } + catch( Exception e ) { + assertEquals("Might be null accessing 'v0'", e.getMessage()); } } @Test diff --git a/chapter11/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter11/src/test/java/com/seaofnodes/simple/TypeTest.java index f18fb306..f9c580cc 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -13,19 +13,19 @@ public class TypeTest { @Test public void testTypeAdHoc() { TypeStruct s1 = TypeStruct.make("s1", new Field[]{ - Field.make("s1", TypeInteger.BOT, "a"), - Field.make("s1", TypeInteger.BOT, "b") }); + Field.make("a", TypeInteger.BOT), + Field.make("b", TypeInteger.BOT) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ - Field.make("s2", TypeInteger.BOT, "a"), - Field.make("s2", TypeInteger.BOT, "b") }); + Field.make("a", TypeInteger.BOT), + Field.make("b", TypeInteger.BOT) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - TypeMem m1 = TypeMem.make(s1.get("a")._alias); - TypeMem m2 = TypeMem.make(s1.get("b")._alias); - TypeMem m3 = TypeMem.make(s2.get("a")._alias); - TypeMem m4 = TypeMem.make(s2.get("b")._alias); + TypeMem m1 = TypeMem.make(1); + TypeMem m2 = TypeMem.make(2); + TypeMem m3 = TypeMem.make(3); + TypeMem m4 = TypeMem.make(4); Assert.assertNotEquals(m1, m2); Assert.assertNotEquals(m2, m3); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 2447a36a..4a405a3b 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -29,30 +29,10 @@ public class Evaluator { } } - private static final MethodHandle get_MemOpNode_field; - - static { - try { - var MemOpNode = Class.forName("com.seaofnodes.simple.node.MemOpNode"); - var field = MemOpNode.getDeclaredField("_field"); - field.setAccessible(true); - get_MemOpNode_field = MethodHandles.lookup().unreflectGetter(field); - } catch (Exception e) { - throw new ExceptionInInitializerError(e); - } - } - - private static int getFieldIndex(TypeStruct struct, Node memop) { - Field field; - try { - field = (Field)get_MemOpNode_field.invoke(memop); - } catch (Throwable e) { - throw new RuntimeException(e); - } - for(int i=0;i<struct._fields.length;i++) { - if (struct._fields[i]._alias == field._alias) return i; - } - throw new AssertionError("Field "+field._fname+" of struct " +field._sname + " not found in struct " + struct._name); + private static int getFieldIndex(TypeStruct struct, MemOpNode memop) { + int idx = struct.find(memop._name); + if( idx >= 0 ) return idx; + throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); } public enum Status { |