diff options
Diffstat (limited to 'chapter12/src/main/java')
10 files changed, 421 insertions, 37 deletions
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/.#Parser.java b/chapter12/src/main/java/com/seaofnodes/simple/.#Parser.java new file mode 100644 index 00000000..57c63c60 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/.#Parser.java @@ -0,0 +1 @@ +cliffc@CLIFF-CLICK-LAP.9640:1721544010
\ No newline at end of file diff --git a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java index 7e957d9d..6f8e41c6 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import java.util.*; +import java.io.ByteArrayInputStream; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate @@ -158,6 +159,7 @@ public class Parser { if( false ) return null; else if (matchx("return") ) return parseReturn(); else if (matchx("int") ) return parseDecl(TypeInteger.BOT); + else if (matchx("flt") ) return parseDecl(TypeFloat .BOT); else if (match ("{") ) return require(parseBlock(),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); @@ -462,6 +464,8 @@ public class Parser { ? new ConstantNode(t.makeInit()).peephole() // Assign "= expr;" : require(require("=").parseExpression(), ";"); + if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) + expr = new ToFloatNode(expr).peephole(); if( !expr._type.isa(t) ) throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); if( _scope.define(name,t,expr) == null ) @@ -490,20 +494,22 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); + BoolNode op; while( true ) { int idx=0; boolean negate=false; // Test for any local nodes made, and "keep" lhs during peepholes if( false ) ; - else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } - else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } - else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } - else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } - else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } - else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else if( match("==") ) { idx=2; op = new BoolNode.EQ(lhs, null); } + else if( match("!=") ) { idx=2; op = new BoolNode.EQ(lhs, null); negate=true; } + else if( match("<=") ) { idx=2; op = new BoolNode.LE(lhs, null); } + else if( match("<" ) ) { idx=2; op = new BoolNode.LT(lhs, null); } + else if( match(">=") ) { idx=1; op = new BoolNode.LE(null, lhs); } + else if( match(">" ) ) { idx=1; op = new BoolNode.LT(null, lhs); } else break; // Peepholes can fire, but lhs is already "hooked", kept alive - lhs.setDef(idx,parseAddition()); - lhs = lhs.peephole(); + op.setDef(idx,parseAddition()); + op = op.widen(); + lhs = op.peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); } @@ -519,13 +525,21 @@ public class Parser { * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { - Node lhs = parseMultiplication(); + Node lhs = parseMultiplication(); boolean add; while( true ) { - if( false ) ; - else if( match("+") ) lhs = new AddNode(lhs,null); - else if( match("-") ) lhs = new SubNode(lhs,null); + if( match("+") ) add=true; + else if( match("-") ) add=false; else break; - lhs.setDef(2,parseMultiplication()); + lhs.keep(); + var rhs = parseMultiplication(); + lhs.unkeep(); + if( lhs._type instanceof TypeFloat || rhs._type instanceof TypeFloat ) { + lhs = widen(lhs); + rhs = widen(rhs); + lhs = add ? new AddFNode(lhs,rhs) : new SubFNode(lhs,rhs); + } else { + lhs = add ? new AddNode (lhs,rhs) : new SubNode (lhs,rhs); + } lhs = lhs.peephole(); } return lhs; @@ -540,18 +554,31 @@ public class Parser { * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { - var lhs = parseUnary(); + var lhs = parseUnary(); boolean mul; while( true ) { - if( false ) ; - else if( match("*") ) lhs = new MulNode(lhs,null); - else if( match("/") ) lhs = new DivNode(lhs,null); + if( match("*") ) mul=true; + else if( match("/") ) mul=false; else break; - lhs.setDef(2,parseUnary()); + lhs.keep(); + var rhs = parseUnary(); + lhs.unkeep(); + if( lhs._type instanceof TypeFloat || rhs._type instanceof TypeFloat ) { + lhs = widen(lhs); + rhs = widen(rhs); + lhs = mul ? new MulFNode(lhs,rhs) : new DivFNode(lhs,rhs); + } else { + lhs = mul ? new MulNode (lhs,rhs) : new DivNode (lhs,rhs); + } lhs = lhs.peephole(); } return lhs; } + // int->float widen + public static Node widen(Node x) { + return x._type instanceof TypeFloat ? x : new ToFloatNode(x).peephole(); + } + /** * Parse a unary minus expression. * @@ -575,7 +602,7 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); if( matchx("false") ) return ZERO; @@ -652,9 +679,10 @@ public class Parser { * * <pre> * integerLiteral: [1-9][0-9]* | [0] + * floatLiteral: [1-9][0-9]* | [0] * </pre> */ - private ConstantNode parseIntegerLiteral() { + private ConstantNode parseLiteral() { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } @@ -809,19 +837,36 @@ public class Parser { return String.valueOf(peek()); } - boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} private Type parseNumber() { - 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)); + int old = _position; + int len = isLongOrDouble(); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + throw error("Syntax error: integer values cannot start with '0'"); + return TypeInteger.constant(Long.parseLong(new String(_input,old,len))); + } + return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); } private String parseNumberString() { - int start = _position; - while (isNumber(nextChar())) ; - return new String(_input, start, --_position - start); + int old = _position; + int len = Math.abs(isLongOrDouble()); + _position += len; + return new String(_input,old,len); + } + + // Return +len that ends a long + // Return -len that ends a double + private int isLongOrDouble() { + int old = _position; + char c; + while( Character.isDigit(c=nextChar()) ) ; + if( !(c=='e' || c=='.') ) + return --_position - old; + while( Character.isDigit(c=nextChar()) || c=='e' || c=='.' ) ; + return -(--_position - old); } // First letter of an identifier diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java new file mode 100644 index 00000000..cc416be7 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class AddFNode extends Node { + public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "AddF"; } + + @Override public String glabel() { return "+"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("+"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()+i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Add of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 9c15f01b..1d3a1031 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,7 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeMemPtr; import java.util.BitSet; @@ -37,7 +40,9 @@ abstract public class BoolNode extends Node { return in(1)._type.meet(in(2)._type); } - abstract boolean doOp(long lhs, long rhs); + boolean doOp(long lhs, long rhs) { throw Utils.TODO(); } + boolean doOp(double lhs, double rhs) { throw Utils.TODO(); } + BoolNode copyF(Node lhs, Node rhs) { throw Utils.TODO(); } @Override public Node idealize() { @@ -69,7 +74,19 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } + public BoolNode widen() { + if( !(in(1)._type instanceof TypeFloat || in(2)._type instanceof TypeFloat) ) return this; + Node in1 = Parser.widen(in(1)); + Node in2 = Parser.widen(in(2)); + return copyF(in1,in2); + } + + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } BoolNode copyF(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } BoolNode copyF(Node lhs, Node rhs) { return new LTF(lhs,rhs); }} + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } BoolNode copyF(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } + + public static class EQF extends BoolNode { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(double lhs, double rhs) { return lhs == rhs; } } + public static class LTF extends BoolNode { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(double lhs, double rhs) { return lhs < rhs; } } + public static class LEF extends BoolNode { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } } + } diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java new file mode 100644 index 00000000..3333b417 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class DivFNode extends Node { + public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "DivF"; } + + @Override public String glabel() { return "*"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()/i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Div of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new DivFNode(lhs,rhs); } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java new file mode 100644 index 00000000..2d44a9fb --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -0,0 +1,51 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class MulFNode extends Node { + public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "MulF"; } + + @Override public String glabel() { return "*"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()*i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + 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 TypeFloat i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new MulFNode(lhs,rhs); } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java new file mode 100644 index 00000000..aa2553f8 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class SubFNode extends Node { + public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "SubF"; } + + @Override public String glabel() { return "-"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("-"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()-i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Sub of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new SubFNode(lhs,rhs); } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java new file mode 100644 index 00000000..1d147cf6 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.BitSet; + +public class ToFloatNode extends Node { + public ToFloatNode(Node lhs) { super(null, lhs); } + + @Override public String label() { return "ToFloat"; } + + @Override public String glabel() { return "(flt)"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return in(1)._print0(sb.append("(flt)"), visited); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); + return TypeFloat.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToFloatNode(lhs); } +} diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java index aa0ba1ea..f3152719 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,11 +33,12 @@ public class Type { static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger - static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // All memory (alias 0) or A slice of memory - with specific alias - static final byte TMEMPTR = 8; // Memory pointer type - static final byte TSTRUCT = 9; // Structs; tuples with named fields - static final byte TFLD =10; // Fields into struct + static final byte TFLT = 6; // All Integers; see TypeInteger + static final byte TTUPLE = 7; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TMEM = 8; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TMEMPTR = 9; // Memory pointer type + static final byte TSTRUCT =10; // Structs; tuples with named fields + static final byte TFLD =11; // Fields into struct public final byte _type; diff --git a/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java new file mode 100644 index 00000000..36bc61f5 --- /dev/null +++ b/chapter12/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -0,0 +1,101 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; + +/** + * Float Type + */ +public class TypeFloat extends Type { + + public final static TypeFloat TOP = make(false, 0); + public final static TypeFloat BOT = make(false, 1); + public final static TypeFloat ZERO= make(true , 0); + + public final boolean _is_con; + + /** + * The constant value or + * if not constant then 1=bottom, 0=top. + */ + public final double _con; + + private TypeFloat(boolean is_con, double con) { + super(TFLT); + _is_con = is_con; + _con = con; + } + public static TypeFloat make(boolean is_con, double con) { + return new TypeFloat(is_con,con).intern(); + } + + public static TypeFloat constant(double con) { return make(true, con); } + + public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); } + + // FIXME this display format is problematic + // In visualizer '#' gets prepended if its a constant + @Override + public StringBuilder _print(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append(_con); + } + + @Override public String str() { + if( this==TOP ) return "~flt"; + if( this==BOT ) return "flt"; + return ""+_con; + } + + /** + * Display Type name in a format that's good for IR printer + */ + @Override + public StringBuilder typeName(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append("Int"); + } + + @Override + public boolean isHighOrConst() { return _is_con || _con==0; } + + @Override + public boolean isConstant() { return _is_con; } + + public double value() { return _con; } + + @Override + public Type xmeet(Type other) { + // Invariant from caller: 'this' != 'other' and same class (TypeFloat) + TypeFloat i = (TypeFloat)other; // Contract + // BOT wins + if ( this==BOT ) return this; + if ( i ==BOT ) return i ; + // TOP loses + if ( i ==TOP ) return this; + if ( this==TOP ) return i ; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return BOT; + } + + @Override + public Type dual() { + if( isConstant() ) return this; // Constants are a self-dual + return _con==0 ? BOT : TOP; + } + + @Override + public Type glb() { return BOT; } + + @Override public TypeFloat makeInit() { return ZERO; } + + @Override + int hash() { return (int)(Double.hashCode(_con) ^ (_is_con ? 0 : 0x4000)); } + @Override + public boolean eq( Type t ) { + TypeFloat i = (TypeFloat)t; // Contract + return _con==i._con && _is_con==i._is_con; + } +} |