summaryrefslogtreecommitdiff
path: root/chapter10
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2024-05-13 15:35:19 -0700
committerGitHub <noreply@github.com>2024-05-13 15:35:19 -0700
commit492786481ed69edb847f5ebfa9a24a95d08aedb8 (patch)
tree38f36a27984b1e80abac6d9cfa7aedc113d0c71b /chapter10
parent555604e0c870e10720e4baeabe93a2b0ae5a60c9 (diff)
downloadSimple-492786481ed69edb847f5ebfa9a24a95d08aedb8.tar.gz
Simple-492786481ed69edb847f5ebfa9a24a95d08aedb8.zip
Bugfix 78 (#81)
* Missing idepth for LoopNode * backedge code removing a Parser keep Stop subsuming a node parser yet needs * Missing addDep * LoadNode cloning peep better profit The LoadNode cloning peep cannot clone around a Loop unless its profit on the backedge, otherwise might infinitely clone around backedge. peep: x - (-y) is x+y peep: -(-x) is x * Drop alias from Field Field is intended to be a part of a Type; as such is abstract, immutable, and true for ALL Time and all TypeStructs which have the same field. Drop the alias and struct from Field. Drop field reset. The alias#s are decided in the Parser, and have a lifetime for the compilation unit; the Fields have infinite lifetime. Minor bugfix idepth caching * Remove emacs junk file
Diffstat (limited to 'chapter10')
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/Parser.java32
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/Utils.java7
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java43
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java3
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java18
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/MinusNode.java14
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/Node.java16
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java2
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java3
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java24
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java17
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/node/SubNode.java6
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/type/Field.java62
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/type/Type.java4
-rw-r--r--chapter10/src/main/java/com/seaofnodes/simple/type/TypeStruct.java12
-rw-r--r--chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java18
-rw-r--r--chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java16
-rw-r--r--chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java28
18 files changed, 163 insertions, 162 deletions
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java
index b9535208..def37bae 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java
@@ -70,12 +70,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();
_lexer = new Lexer(source);
_scope = new ScopeNode();
@@ -167,7 +167,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");
}
@@ -289,7 +289,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
@@ -585,11 +585,13 @@ public class Parser {
/**
* Return a NewNode but also generate instructions to initialize it.
*/
- private Node newStruct(TypeStruct obj) {
+ private Node newStruct( TypeStruct obj ) {
Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole();
- for (Field field: obj._fields) {
- memAlias(field, new StoreNode(field, memAlias(field), n, initValue).peephole());
+ int alias = START._aliasStarts.get(obj._name);
+ for( Field field : obj._fields ) {
+ memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, initValue).peephole());
+ alias++;
}
return n.unkeep();
}
@@ -598,8 +600,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
@@ -615,22 +618,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());
}
/**
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/Utils.java b/chapter10/src/main/java/com/seaofnodes/simple/Utils.java
index e3f29b3d..9f23593e 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/Utils.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/Utils.java
@@ -55,4 +55,11 @@ public class Utils {
// Fold a 64bit hash into 32 bits
public static int fold( long x ) { return (int)((x>>32) ^ x); }
+
+ public static boolean eq(String s0, String s1) {
+ if( s0==s1 ) return true;
+ assert s0==s0.intern();
+ assert s1==s1.intern();
+ return false;
+ }
} \ No newline at end of file
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 103232f1..53ae1096 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter10/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, null);
+ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
+ super(name, alias, memSlice, memPtr, null);
+ _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 Utils.eq(_name,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/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 96ce71eb..ea1489c4 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -25,6 +25,7 @@ public class LoopNode extends RegionNode {
return inProgress() ? null : super.idealize();
}
- // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
+ // Bypass Region idom, same as the default idom() using use entry in(1) instead of in(0)
+ @Override int idepth() { return _idepth(1); }
@Override Node idom() { return entry(); }
}
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index dd68120c..08e08bbf 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -7,13 +7,15 @@ 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, Node value) {
+ public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
super(null, memSlice, memPtr, value);
- this._field = field;
+ _name = name;
+ _alias = alias;
}
public Node mem() { return in(1); }
@@ -22,19 +24,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/chapter10/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 524f63a0..9b687613 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter10/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/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
index 9ae81ac3..5c9b283e 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -257,10 +257,11 @@ public abstract class Node {
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
@@ -561,16 +562,17 @@ public abstract class Node {
/**
- * Immediate dominator tree depth, used to approximate a real IDOM during
- * parsing where we do not have the whole program, and also peepholes
- * change the CFG incrementally.
+ * Immediate dominator tree depth, used to approximate a real IDOM depth
+ * during parsing where we do not have the whole program, and also
+ * peepholes change the CFG incrementally.
* <p>
* See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
*/
- public int _idepth;
- int idepth() { return _idepth==0 ? idom()._idepth+1 : _idepth; }
+ public int _idepth; // IDOM depth approx; Zero is unset; non-zero is cached legit
+ final int _idepth(int idx) { return _idepth==0 ? (_idepth=in(idx).idepth()+1) : _idepth; }
+ int idepth() { return _idepth(0); }
- // Return the immediate dominator of this Node and compute dom tree depth.
+ // Return the immediate dominator of this Node.
Node idom() { return in(0); }
// Make a shallow copy (same class) of this Node, with given inputs and
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 08fe047c..dd67bd06 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter10/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.
Node idom = region().in(nullx);
while( idom.in(0) != iff ) idom = idom.idom();
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 8a50eb56..843ce733 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter10/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/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 42b38503..4b7e02a8 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter10/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;
/**
* The Start node represents the start of the function.
@@ -17,10 +18,16 @@ public class StartNode extends 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<>();
}
/**
@@ -28,20 +35,21 @@ public class StartNode extends 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/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 00d75f02..8d264601 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter10/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 Utils.eq(_name,st._name); // Equiv class aliasing is perfect
setDef(1,st.mem());
return this;
}
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/SubNode.java
index f81ae6d0..760177d7 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter10/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 &&
@@ -35,6 +35,10 @@ public class SubNode extends Node {
if( in(1)==in(2) )
return new ConstantNode(TypeInteger.constant(0));
+ // x - (-y) is x+y
+ if( in(2) instanceof MinusNode minus )
+ return new AddNode(in(1),minus.in(1));
+
return null;
}
diff --git a/chapter10/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter10/src/main/java/com/seaofnodes/simple/type/Field.java
index 179eacf5..56626482 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/chapter10/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 Utils.eq(_fname,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/chapter10/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter10/src/main/java/com/seaofnodes/simple/type/Type.java
index 34e66a0c..aa0ba1ea 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter10/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/chapter10/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter10/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index a98093b2..29102675 100644
--- a/chapter10/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/chapter10/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
diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 36ad19ae..4a4ef8be 100644
--- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -13,6 +13,24 @@ import static org.junit.Assert.fail;
public class Chapter10Test {
+ @Test
+ public void testFuzzer() {
+ Parser parser = new Parser(
+"""
+struct s0 {
+ int v0;
+}
+s0 v5 = new s0;
+int v6 = new s0.v0;
+s0? arg=v5;
+if( arg ) v5 = new s0;
+else v6 = 0;
+s0 v7=v5;
+return 0;
+""");
+ StopNode stop = parser.parse(false).iterate(false);
+ assertEquals("return 0;", stop.toString());
+ }
@Test
public void testStruct() {
diff --git a/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java
index f18fb306..f9c580cc 100644
--- a/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter10/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/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 15f65f39..8622eb25 100644
--- a/chapter10/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter10/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 {