diff options
8 files changed, 249 insertions, 19 deletions
diff --git a/chapter04/Makefile b/chapter04/Makefile new file mode 100644 index 00000000..c7724bc7 --- /dev/null +++ b/chapter04/Makefile @@ -0,0 +1,98 @@ +SHELL := /bin/bash +.DELETE_ON_ERROR: + +# for printing variable values +# usage: make print-VARIABLE +# > VARIABLE = value_of_variable +print-% : ; @echo $* = $($*) + +# literal space +space := $() $() + +# Decide OS-specific questions +# jar-file seperator +ifeq ($(OS),Windows_NT) + SEP = ; +else + SEP = : +endif +# Find a reasonable ctags. +CTAGS = $(shell which ctags) +# Hack for MacOS: /usr/bin/ctags is unfriendly, so look for ctags from brew +ifeq ($(UNAME),Darwin) + CTAGS = $(shell brew list ctags 2> /dev/null | grep bin/ctags) +endif + +# Fun Args to javac. Mostly limit to java8 source definitions, and fairly +# aggressive lint warnings. +JAVAC_ARGS = -g + +# Source code +SIMPLE := com/seaofnodes/simple +SRC := src/main/java +TST := src/test/java +CLZDIR:= build/classes +main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java) +test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) +main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) +test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) +test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) +classes = $(main_classes) $(test_classes) +# All the libraries +libs = $(wildcard lib/*jar) +jars = $(subst $(space),$(SEP),$(libs)) + + +default_targets := $(main_classes) $(test_classes) +# Optionally add ctags to the default target if a reasonable one was found. +ifneq ($(CTAGS),) +default_targets += tags +endif + +default: $(default_targets) + +# Compile just the out-of-date files +$(main_classes): build/classes/main/%class: $(SRC)/%java + @echo "compiling " $@ " because " $? + @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main + @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) + +$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) + @echo "compiling " $@ " because " $? + @[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test + @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas) + +# Base launch line for JVM tests +JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" + +tests: $(default_targets) + @echo "testing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore $(test_cp) + +fuzzer: $(default_targets) + @echo "fuzzing " $(test_cp) + @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap + + +.PHONY: clean +clean: + rm -rf build + rm -f TAGS + (find . -name "*~" -exec rm {} \; 2>/dev/null; exit 0) + +# Download libs from maven +lib: lib/junit-4.12.jar lib/hamcrest-core-1.3.jar + +# Jars +lib/junit-4.12.jar: + @[ -d lib ] || mkdir -p lib + @(cd lib; wget https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar) + +lib/hamcrest-core-1.3.jar: + @[ -d lib ] || mkdir -p lib + @(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar) + +# Build emacs tags (part of a tasty emacs ide experience) +tags: $(main_javas) $(test_javas) + @rm -f TAGS + @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) diff --git a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java index 032b4867..de5565ab 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java @@ -52,7 +52,9 @@ public class Parser { * List of keywords disallowed as identifiers */ private static final HashSet<String> KEYWORDS = new HashSet<>(){{ + add("bool"); add("break"); + add("byte"); add("continue"); add("else"); add("false"); @@ -64,8 +66,11 @@ public class Parser { add("return"); add("struct"); add("true"); - add("while"); + add("u1"); + add("u16"); + add("u32"); add("u8"); + add("while"); }}; @@ -85,9 +90,14 @@ public class Parser { Node.reset(); IterPeeps.reset(); TYPES.clear(); - TYPES.put("int",TypeInteger.BOT); - //TYPES.put("u8" ,TypeInteger.U8 ); - TYPES.put("flt",TypeFloat .BOT); + TYPES.put("bool",TypeInteger.U1 ); + TYPES.put("byte",TypeInteger.U8 ); + TYPES.put("flt" ,TypeFloat .BOT); + TYPES.put("int" ,TypeInteger.BOT); + TYPES.put("u1" ,TypeInteger.U1 ); + TYPES.put("u8" ,TypeInteger.U8 ); + TYPES.put("u16" ,TypeInteger.U16); + TYPES.put("u32" ,TypeInteger.U32); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -435,6 +445,9 @@ public class Parser { // Auto-widen int to float if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) expr = new ToFloatNode(expr).peephole(); + // Auto-narrow wide ints to narrow ints + if( expr._type instanceof TypeInteger e0 && t instanceof TypeInteger t0 && !e0.isa(t) ) + expr = new AndNode(expr,new ConstantNode(TypeInteger.constant(t0._max-t0._min)).peephole()).peephole(); // Auto-deepen forward ref types Type e = expr._type; if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) @@ -476,7 +489,27 @@ public class Parser { * </pre> * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { return parseComparison(); } + private Node parseExpression() { return parseBitwise(); } + + /** + * Parse an bitwise expression + * + * <pre> + * bitwise : compareExpr (('&' | '|' | '^') compareExpr)* + * </pre> + * @return a bitwise expression {@link Node}, never {@code null} + */ + private Node parseBitwise() { + Node lhs = parseComparison(); + while( true ) { + if( false ) ; + else if( match("&") ) lhs = new AndNode(lhs,null); + else break; + lhs.setDef(2,parseComparison()); + lhs = lhs.peephole(); + } + return lhs; + } /** * Parse an expression of the form: @@ -640,6 +673,9 @@ public class Parser { else { Node val = parseExpression(); Type glb = base._fields[idx]._type; + // Auto-truncate when storing to narrow fields + if( !val._type.isa(glb) && glb instanceof TypeInteger t0) + val = new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max-t0._min)).peephole()).peephole(); memAlias(alias, new StoreNode(name, alias,glb, memAlias(alias), expr, val, false).peephole()); return expr; // "obj.a = expr" returns the expression while updating memory } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java new file mode 100644 index 00000000..1a3995d4 --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -0,0 +1,57 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.BitSet; + +public class AndNode extends Node { + public AndNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "And"; } + + @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 TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(i0.value()&i1.value()); + } + return TypeInteger.BOT; + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // And of -1. We do not check for (0&x) because this will already + // canonicalize to (x&0) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 ) + return rhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + // Do we have ((x & (phi cons)) & con) ? + // Do we have ((x & (phi cons)) & (phi cons)) ? + // Push constant up through the phi: x & (phi con0&con0 con1&con1...) + Node phicon = AddNode.phiCon(this,true); + if( phicon!=null ) return phicon; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new AndNode(lhs,rhs); } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java index d846fcef..382f78ae 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java @@ -93,10 +93,8 @@ public abstract class Node implements OutNode { @Override public final String toString() { return print(); } - // This is a *deep* print. This version will fail on cycles, which we will - // correct later when we can parse programs with loops. We print with a - // tik-tok style; the common _print0 calls the per-Node _print1, which - // calls back to _print0; + // This is a *deep* print. We print with a tik-tok style; the common + // _print0 calls the per-Node _print1, which calls back to _print0; public final String print() { return _print0(new StringBuilder(), new BitSet()).toString(); } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 0932a202..f40c7480 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -54,7 +54,7 @@ public class TypeFloat extends Type { public StringBuilder typeName(StringBuilder sb) { if( this==TOP ) return sb.append("FltTop"); if( this==BOT ) return sb.append("FltBot"); - return sb.append("Int"); + return sb.append("Flt"); } @Override public boolean isHigh() { return this==TOP; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index d3f9b66e..c84a4c13 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -15,6 +15,8 @@ public class TypeInteger extends Type { public final static TypeInteger FALSE=ZERO; public final static TypeInteger TRUE= make(1,1); public final static TypeInteger U8 = make(0,255); + public final static TypeInteger U16 = make(0,65535); + public final static TypeInteger U32 = make(0,(1L<<32)-1); /** * Describes an integer *range* - everything from min to max; both min and @@ -39,16 +41,15 @@ public class TypeInteger extends Type { // 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("IntTop"); - if( this==BOT ) return sb.append("IntBot"); - if( isConstant() ) return sb.append(_min); - return sb.append("[").append(_min).append("-").append(_max).append("]"); - } + public StringBuilder print(StringBuilder sb) { return sb.append(str()); } @Override public String str() { if( this==TOP ) return "~int"; if( this==BOT ) return "int"; + if( this==BOOL) return ("bool"); + if( this==U8 ) return ("u8"); + if( this==U16 ) return ("u16"); + if( this==U32 ) return ("u32"); if( isConstant() ) return ""+_min; return "["+_min+"-"+_max+"]"; } diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 8eceb0fa..99c08f16 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -169,6 +169,6 @@ n.i = 3.14; return n.i; """); try { parser.parse(true).iterate(true); fail(); } - catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); } + catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); } } } diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 4bf04b88..f76e1903 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -42,11 +42,51 @@ return c; """ u8 b = 123; b = b + 456;// Truncate -return 67; +return b; """); StopNode stop = parser.parse(false).iterate(false); assertEquals("return 67;", stop.toString()); - assertEquals(67, Evaluator.evaluate(stop, 0)); + assertEquals(67L, Evaluator.evaluate(stop, 0)); } + @Test + public void testU1() { + Parser parser = new Parser( +""" +bool b = 123; +b = b + 456;// Truncate +u1 c = b; // No more truncate needed +return c; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testAnd() { + Parser parser = new Parser( +""" +int b = 123; +b = b+456 & 31; // Precedence +return b; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 3;", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testRefLoad() { + Parser parser = new Parser( +""" +struct Foo { u1 b; } +Foo f = new Foo; +f.b = 123; +return f.b; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } } |