diff options
Diffstat (limited to 'chapter18/src/main/java/com')
33 files changed, 506 insertions, 377 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java index c0b34263..aad9bf31 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -115,7 +115,7 @@ public abstract class IterPeeps { int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; Node changed = stop.walk( n -> { Node m = n; - if( n.compute().isa(n._type) && (!n.iskeep() || n._nid<=5) ) { // Types must be forwards, even if on worklist + if( n.compute().isa(n._type) && (!n.iskeep() || n._nid<=6) ) { // Types must be forwards, even if on worklist if( WORK.on(n) ) return null; m = n.peepholeOpt(); if( m==null ) return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java b/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java index d208fc0c..7b8f2631 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/JSViewer.java @@ -198,7 +198,7 @@ public class JSViewer implements AutoCloseable { if( level==0 && n!=null && n.nIns()>2 ) { sb.i().p("<TR>"); for( int m=2; m<n.nIns(); m++ ) - cell(sb,"#"+m,n.in(m),"m"+m); + cell(sb,"#"+m,n.alias(m),"m"+m); sb.p("</TR>\n"); // End scope level } // Scope variables, empty if none diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 04af20f7..f7b7d0e9 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -24,6 +24,7 @@ public class Parser { public static StartNode START; public static ConstantNode ZERO; // Very common node, cached here + public static ConstantNode NIL; // Very common node, cached here public static XCtrlNode XCTRL; // Very common node, cached here // Next available memory alias number @@ -110,7 +111,8 @@ public class Parser { _continueScope = _breakScope = null; START = new StartNode(arg); STOP = new StopNode(source); - ZERO = con(0).keep(); + ZERO = con(TypeInteger.ZERO).keep(); + NIL = con(Type.NIL).keep(); XCTRL= new XCtrlNode().peephole().keep(); ALIAS = 2; // alias 0 for the control, 1 for memory TYPES = defaultTypes(); @@ -124,9 +126,9 @@ public class Parser { return new HashMap<>() {{ put("bool",TypeInteger.U1 ); put("byte",TypeInteger.U8 ); - put("f32" ,TypeFloat .B32); - put("f64" ,TypeFloat .BOT); - put("flt" ,TypeFloat .BOT); + put("f32" ,TypeFloat .F32); + put("f64" ,TypeFloat .F64); + put("flt" ,TypeFloat .F64); put("i16" ,TypeInteger.I16); put("i32" ,TypeInteger.I32); put("i64" ,TypeInteger.BOT); @@ -170,7 +172,7 @@ public class Parser { for( StructNode init : INITS.values() ) init.unkeep().kill(); INITS.clear(); - if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); + if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); STOP.peephole(); JSViewer.show(); if( show ) showGraph(); @@ -207,7 +209,6 @@ public class Parser { private Node parseStatement() { if( false ) return null; else if (matchx("return") ) return parseReturn(); - else if (match ("{") ) return require(parseBlock(false),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); else if (matchx("for") ) return parseFor(); @@ -216,6 +217,11 @@ public class Parser { else if (matchx("struct") ) return parseStruct(); else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";") ) return null; // Empty statement + // Break ambiguity around leading function types and starting a block + else if (peek('{') && !isTypeFun() ) { + match("{"); + return require(parseBlock(false),"}"); + } // Declaration or normal assignment/expression else return parseDeclarationStatement(); } @@ -378,7 +384,7 @@ public class Parser { return toScope; } - private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } + private void checkLoopActive() { if (_breakScope == null) throw error("No active loop for a break or continue"); } private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } private Node parseBreak () { @@ -602,13 +608,16 @@ public class Parser { // var is always not-final, final if no Bang AND TMP since primitives are not-final by default (t!=Type.BOTTOM && !hasBang && (t instanceof TypeMemPtr)); // var/val, then type comes from expression - if( inferType ) + if( inferType ) { + if( expr._type==Type.NIL ) + throw error("a not-null/non-zero expression"); t = expr._type.glb(); + } } else { if( inferType && !_scope.inCon() ) throw errorSyntax("=expression"); - expr = con(t.makeInit()); + expr = t instanceof TypeMemPtr tn ? (tn._nil==3 ? NIL : con(Type.TOP)) : (t==Type.BOTTOM ? con(t) : ZERO); } // Lift expression, based on type @@ -632,11 +641,11 @@ public class Parser { * @return The statement following the struct */ private Node parseStruct() { - if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); + if (_xScopes.size() > 1) throw error("struct declarations can only appear in top level scope"); String typeName = requireId(); Type t = TYPES.get(typeName); if( t!=null && !(t instanceof TypeMemPtr tmp && tmp.isFRef() ) ) - throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + throw error("struct '" + typeName + "' cannot be redefined"); // A Block scope parse, and inspect the scope afterward for fields. _scope.push(true); @@ -655,7 +664,7 @@ public class Parser { fs[i-lexlen] = Field.make(v._name,v.type(),ALIAS++,v._final); } TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); - TYPES.put(typeName, TypeMemPtr.make(ts)); + TYPES.put(typeName, TypeMemPtr.make((byte)2,ts)); INITS.put(typeName,s.peephole().keep()); // Done with struct/block scope require("}"); @@ -673,23 +682,28 @@ public class Parser { // t = int|i8|i16|i32|i64|u8|u16|u32|u64|byte|bool | flt|f32|f64 | val | var | struct[?] private Type type() { int old1 = pos(); + // Only type with a leading `{` is a function pointer... + if( peek('{') ) return typeFunPtr(); + + // Otherwise you get a type name String tname = _lexer.matchId(); if( tname==null ) return null; + // Convert the type name to a type. Type t0 = TYPES.get(tname); // No new types as keywords if( t0 == null && KEYWORDS.contains(tname) ) return posT(old1); - Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type + if( t0 == Type.BOTTOM || t0 == Type.TOP ) return t0; // var/val type inference + Type t1 = t0 == null ? TypeMemPtr.make((byte)2,TypeStruct.makeFRef(tname)) :t0; // Null: assume a forward ref type // Nest arrays and '?' as needed Type t2 = t1; while( true ) { - assert !(t2 instanceof TypeStruct); if( match("?") ) { if( !(t2 instanceof TypeMemPtr tmp) ) throw error("Type "+t0+" cannot be null"); - if( tmp._nil ) throw error("Type "+t2+" already allows null"); - t2 = TypeMemPtr.make(tmp._obj,true); + if( tmp._nil==3 ) throw error("Type "+t2+" already allows null"); + t2 = tmp.makeFrom((byte)3); } else if( match("[]") ) { t2 = typeAry(t2); } else @@ -712,7 +726,7 @@ public class Parser { // Make an array type of t private TypeMemPtr typeAry( Type t ) { - if( t instanceof TypeMemPtr tmp && !tmp._nil ) + if( t instanceof TypeMemPtr tmp && (tmp._nil==1|| tmp._nil==2) ) throw error("Arrays of reference types must always be nullable"); String tname = "["+t.str()+"]"; Type ta = TYPES.get(tname); @@ -720,20 +734,44 @@ public class Parser { // Need make an array type. TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); assert ts.str().equals(tname); - TypeMemPtr tary = TypeMemPtr.make(ts); + TypeMemPtr tary = TypeMemPtr.make((byte)2,ts); TYPES.put(tname,tary); return tary; } - // Fixup forward refs lazily. Basically a Union-Find flavored read - // barrier. - Type lazyFRef(Type t) { - //if( !t.isFRef() ) return t; - //Type def = Parser.TYPES.get(((TypeMemPtr)t)._obj._name); - throw Utils.TODO(); + // A function type is `{ type... -> type }` or `{ type }`. + private Type typeFunPtr() { + int old = pos(); // Record lexer position + match("{"); // Skip already-peeked '{' + Type t0 = type(); // Either return or first arg + if( t0==null ) return posT(old); // Not a function + if( match("}") ) // No-arg function { -> type } + throw Utils.TODO(); + Ary<Type> ts = new Ary<>(Type.class); + ts.push(null); // Return filled in later + ts.push(t0); // First argument + while( true ) { + if( match("->") ) { // End of arguments, parse return + Type ret = type(); + if( ret==null ) return posT(old); + ts.set(0,ret); + if( !match("}") ) return posT(old); // Not a function + return TypeFunPtr.make(TypeTuple.make(ts.asAry()),match("?")); + } + Type t1 = type(); + if( t1==null ) return posT(old); // Not a function + ts.push(t1); + } } + // True if a TypeFunPtr, without advancing parser + private boolean isTypeFun() { + int old = pos(); + if( typeFunPtr()==null ) return false; + pos(old); + return true; + } /** * Parse an expression of the form: @@ -908,7 +946,7 @@ public class Parser { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; - if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( matchx("null" ) ) return NIL; if( match("(") ) return require(parseAsgn(), ")"); if( matchx("new" ) ) return alloc(); // Expect an identifier now @@ -1021,7 +1059,7 @@ public class Parser { // Initial values for every field for( int i = 0; i < len; i++ ) ns[2+len+i] = init.get(i+idx); - Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); + Node nnn = new NewNode(TypeMemPtr.make((byte)2,obj), ns).peephole(); for( int i = 0; i < len; i++ ) memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); return new ProjNode(nnn,1,obj._name).peephole(); @@ -1032,7 +1070,7 @@ public class Parser { int base = ary.aryBase (); int scale= ary.aryScale(); Node size = peep(new AddNode(con(base),peep(new ShlNode(len.keep(),con(scale))))); - ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeInit())); + ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeZero())); return newStruct(ary,size,0,ALTMP); } @@ -1061,10 +1099,6 @@ public class Parser { else if( match("[") ) name = "[]"; else return expr; // No postfix - // Sanity check expr for being a reference - if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error("Expected reference but got " + expr._type.str()); - // Happens when parsing known dead code, which often has other typing // issues. Since the code is dead, possibly due to inlining, lets not // spoil the user experience with error messages. @@ -1072,6 +1106,14 @@ public class Parser { // Exit out via parsing the trailing expression return matchOpx('=','=') ? parseAsgn() : parsePostfix(con(Type.TOP)); + // + if( expr._type==Type.NIL ) + throw error("Accessing unknown field '" + name + "' from 'null'"); + + // Sanity check expr for being a reference + if( !(expr._type instanceof TypeMemPtr ptr) ) + throw error("Expected reference but got " + expr._type.str()); + // Sanity check field name for existing TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr + "'"); @@ -1162,7 +1204,7 @@ public class Parser { * </pre> */ private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } - public static Node con( long con ) { return con(TypeInteger.constant(con)); } + public static Node con( long con ) { return con==0 ? ZERO : con(TypeInteger.constant(con)); } public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } public Node peep( Node n ) { // Peephole, then improve with lexically scoped guards @@ -1212,13 +1254,11 @@ public class Parser { throw errorSyntax(syntax); } - RuntimeException errorSyntax(String syntax) { - return error("Syntax error, expected " + syntax + ": " + _lexer.getAnyNextToken()); - } - - public static RuntimeException error( String errorMessage ) { - return new RuntimeException(errorMessage); + RuntimeException errorSyntax(String syntax) { return _errorSyntax("expected "+syntax); } + private RuntimeException _errorSyntax(String msg) { + return _lexer.error("Syntax error, "+msg+": " + _lexer.getAnyNextToken()); } + RuntimeException error(String msg) { return _lexer.error(msg); } //////////////////////////////////// // Lexer components @@ -1230,6 +1270,11 @@ public class Parser { // Tracks current position in input buffer private int _position = 0; + // + private int _line_number = 1; + // Start of current line + private int _line_start = 0; + /** * Record the source text for lexing */ @@ -1263,9 +1308,16 @@ public class Parser { // Just crash if misused public byte peek(int off) { return _input[_position+off]; } + private void inc() { + if( _position++ < _input.length && _input[_position-1] == '\n' ) { + _line_number++; + _line_start = _position; + } + } + // Does not honor LF, so caller must roll back position on a LF private char nextChar() { char ch = peek(); - _position++; + inc(); return ch; } @@ -1279,13 +1331,13 @@ public class Parser { */ private void skipWhiteSpace() { while( true ) { - if( isWhiteSpace() ) _position++; + if( isWhiteSpace() ) inc(); // Skip // to end of line else if( _position+2 < _input.length && _input[_position ] == '/' && _input[_position+1] == '/') { - _position += 2; - while( !isEOF() && _input[_position] != '\n' ) _position++; + inc(); inc(); + while( !isEOF() && _input[_position] != '\n' ) inc(); } else break; } } @@ -1297,6 +1349,7 @@ public class Parser { // then advance the cursor past syntax. // Return false otherwise, and do not advance the cursor. boolean match(String syntax) { + assert syntax.indexOf('\n')==-1; // No newlines in match skipWhiteSpace(); int len = syntax.length(); if (_position + len > _input.length) return false; @@ -1319,7 +1372,7 @@ public class Parser { skipWhiteSpace(); if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c1 ) return false; - _position++; + inc(); return true; } @@ -1357,7 +1410,8 @@ public class Parser { 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))); + long i = Long.parseLong(new String(_input,old,len)); + return TypeInteger.constant(i); } return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); } @@ -1419,5 +1473,11 @@ public class Parser { if( ch0 == '-' && ch1 == '-' ) { _position += 2; return (char)-1; } return 0; } + + public RuntimeException error( String errorMessage ) { + // file:line:charoff err + //String msg = "src:"+_line_number+":"+(_position-_line_start)+" "+errorMessage; + return new RuntimeException(errorMessage); + } } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java index 0834a381..e6704ea6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -48,7 +48,7 @@ public class AddNode extends Node { // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if( t2 instanceof TypeInteger i && i.isConstant() && i.value()==0 ) + if( t2 == TypeInteger.ZERO ) return lhs; // Add of same to a multiply by 2 diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 7126806d..bf8f7455 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -2,10 +2,7 @@ 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 com.seaofnodes.simple.type.*; import java.util.BitSet; import static com.seaofnodes.simple.type.TypeInteger.*; @@ -35,6 +32,10 @@ abstract public class BoolNode extends Node { public TypeInteger compute() { Type t1 = in(1)._type; Type t2 = in(2)._type; + // Exactly equals? + if( in(1)==in(2) ) + // LT fails, both EQ and LE succeed + return this instanceof LT ? TypeInteger.FALSE : TypeInteger.TRUE; if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); if( t1 instanceof TypeInteger i1 && @@ -43,7 +44,7 @@ abstract public class BoolNode extends Node { if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && f1.isConstant() && f2.isConstant() ) - return TypeInteger.constant(doOp(f1.value(), f2.value()) ? 1 : 0); + return doOp(f1.value(), f2.value()) ? TypeInteger.TRUE : TypeInteger.FALSE; return BOOL; } @@ -55,7 +56,7 @@ abstract public class BoolNode extends Node { public Node idealize() { // Compare of same if( in(1)==in(2) ) - return new ConstantNode(doOp(ZERO,ZERO)); + return this instanceof LT ? Parser.ZERO : new ConstantNode(TypeInteger.TRUE); // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { @@ -66,7 +67,7 @@ abstract public class BoolNode extends Node { return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1)); } // Equals X==0 becomes a !X - if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) + if( (in(2)._type == ZERO || in(2)._type == Type.NIL) ) return new NotNode(in(1)); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/DivNode.java index 76e98678..0d5ed297 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class DivNode extends Node { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java index 513b4721..dcd2d4c7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,9 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.type.*; import java.util.BitSet; import java.util.HashSet; @@ -37,14 +35,14 @@ public class IfNode extends CFGNode implements MultiNode { Type t = pred._type; // High types mean NEITHER side is reachable. // Wait until the type falls to decide which way to go. - if( t == Type.TOP || t == TypeInteger.TOP ) + if( t.isHigh() ) return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable if( t.isConstant() ) - return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; - // Integers allow non-zero ranges: "1-65535" - if( t.makeZero().meet(t) != t ) + return (t==Type.NIL || t==TypeInteger.ZERO) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + // If adding a zero makes a difference, the predicate must not have a zero/null + if( !t.makeZero().isa(t) ) return TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; @@ -57,7 +55,7 @@ public class IfNode extends CFGNode implements MultiNode { if( !pred()._type.isHighOrConst() ) for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) { - setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); + setDef(1,new ConstantNode(TypeInteger.constant(prj._idx==0?1:0)).peephole()); return this; } return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 82aab8ac..818d6352 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -48,7 +49,7 @@ public abstract class MemOpNode extends Node { // Already an error, but better error messages come from elsewhere if( ptr == Type.BOTTOM ) return null; // Better be a not-nil TMP - if( ptr instanceof TypeMemPtr tmp && !tmp._nil ) + if( ptr instanceof TypeMemPtr tmp && tmp._nil==2 ) return null; return "Might be null accessing '" + _name + "'"; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MinusFNode.java index 9727f58b..2b749ba3 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MinusFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -22,7 +22,7 @@ public class MinusFNode extends Node { public Type compute() { if (in(1)._type instanceof TypeFloat i0) return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; - return TypeFloat.BOT; + return TypeFloat.F64; } @Override diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 760a4274..dd2cbd26 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -21,13 +21,11 @@ public class MinusNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 ) { - if( i0.isHigh() ) return TypeInteger.TOP; - if( i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE ) - return TypeInteger.BOT; + if( in(1)._type.isHigh() ) return TypeInteger.TOP; + if( in(1)._type instanceof TypeInteger i0 && + !(i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE) ) return TypeInteger.make(-i0._max,-i0._min); - } - return TypeInteger.TOP.meet(in(1)._type); + return TypeInteger.BOT; } @Override diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/NewNode.java index ddb1e09a..54defe13 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -17,15 +17,16 @@ public class NewNode extends Node implements MultiNode { public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); + assert ptr._nil!=3; _ptr = ptr; _len = ptr._obj._fields.length; // Control in slot 0 assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; // Malloc-length in slot 1 - assert nodes[1]._type instanceof TypeInteger; + assert nodes[1]._type instanceof TypeInteger || nodes[1]._type==Type.NIL; for( int i=0; i<_len; i++ ) { // Memory slices for all fields. - assert nodes[2+ i]._type instanceof TypeMem; + assert nodes[2+ i]._type.isa(TypeMem.BOT); // Value slices for all fields. assert nodes[2 + _len + i]._type != null; } @@ -57,7 +58,8 @@ public class NewNode extends Node implements MultiNode { ts[0] = Type.CONTROL; ts[1] = _ptr; for( int i=0; i<fs.length; i++ ) { - TypeMem mem = (TypeMem)in(i+2)._type; + Type mt = in(i+2)._type; + TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)in(i+2)._type; Type tfld = in(2+_len+i)._type.meet(mem._t); ts[i+2] = TypeMem.make(fs[i]._alias,tfld); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index e23a128a..1a595f49 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -359,8 +359,9 @@ public abstract class Node implements OutNode { if( n != null ) // Something changed return n; // Report progress - if( old==_type ) ITER_NOP_CNT++; - return old==_type ? null : this; // Report progress + if( old!=_type ) return this; // Report progress; + ITER_NOP_CNT++; + return null; // No progress } public static int ITER_CNT, ITER_NOP_CNT; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/NotNode.java index 664d7c7b..d71e0fe6 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -18,25 +18,13 @@ public class NotNode extends Node { } @Override - public Type compute() { + public TypeInteger compute() { Type t0 = in(1)._type; - if( t0.isHigh() ) return TypeInteger.BOOL.dual(); - switch( t0 ) { - case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOOL); - case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; - case TypeMemPtr p0: - // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot - // If input in null then true - // If input is not null ptr then false - if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE; - if( !p0._nil ) return TypeInteger.FALSE; - return TypeInteger.BOOL; - case Type t: - if( t0.getClass() != Type.class ) - // Only doing NOT on ints and ptrs - throw Utils.TODO(); - return TypeInteger.BOOL; - } + if( t0.isHigh() ) return TypeInteger.BOOL.dual(); + if( t0 == Type.NIL || t0 == TypeInteger.ZERO ) return TypeInteger.TRUE; + if( t0 instanceof TypeNil tn && tn._nil==2 ) return TypeInteger.FALSE; + if( t0 instanceof TypeInteger i && (i._min > 0 || i._max < 0) ) return TypeInteger.FALSE; + return TypeInteger.BOOL; } @Override diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 407cf378..c0557639 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.Utils; - +import com.seaofnodes.simple.type.TypeNil; import java.util.BitSet; public class PhiNode extends Node { @@ -47,7 +47,7 @@ public class PhiNode extends Node { // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type - Type t = _declaredType.lub(); + Type t = Type.TOP; for (int i = 1; i < nIns(); i++) // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. @@ -101,10 +101,12 @@ public class PhiNode extends Node { // then replace with plain val. if( nIns()==3 ) { int nullx = -1; - if( in(1)._type == in(1)._type.makeInit() ) nullx = 1; - if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; + if( in(1)._type == in(1)._type.makeZero() ) nullx = 1; + if( in(2)._type == in(2)._type.makeZero() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); + if( val instanceof CastNode cast ) + val = cast.in(1); if( r.idom(this).addDep(this) 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)r.in(nullx); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 44d3a587..8311405d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -30,7 +30,7 @@ public class RoundF32Node extends Node { Type t1 = lhs._type; // RoundF32 of float - if( t1 instanceof TypeFloat tf && tf._sz==32 ) + if( t1 instanceof TypeFloat tf && tf._f32 ) return lhs; return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java index 59cec99c..4270ef88 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class SarNode extends Node { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index f69461cc..e9a4eb82 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -70,7 +70,7 @@ public class ScopeMinNode extends Node { public Node in( Var v ) { return in(v._idx); } - Node alias( int alias ) { + public Node alias( int alias ) { return in(alias<nIns() && in(alias)!=null ? alias : 1); } @@ -114,7 +114,7 @@ public class ScopeMinNode extends Node { //Var v = _vars.at(i); Node lhs = this._mem(i,null); Node rhs = that._mem(i,null); - alias(i, new PhiNode(Parser.memName(i), TypeMem.BOT, r, lhs, rhs).peephole()); + alias(i, new PhiNode(Parser.memName(i), lhs._type.glb().meet(rhs._type.glb()), r, lhs, rhs).peephole()); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 0d8ad2fc..e720a58f 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.*; import static com.seaofnodes.simple.Utils.TODO; @@ -230,7 +228,7 @@ public class ScopeNode extends ScopeMinNode { * @return A new node representing the merge point */ public RegionNode mergeScopes(ScopeNode that) { - RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); + RegionNode r = ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); mem()._merge(that.mem(),r); this ._merge(that ,r); that.kill(); // Kill merged scope @@ -296,29 +294,28 @@ public class ScopeNode extends ScopeMinNode { pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); // This is a zero/null test. // Compute the positive test type. - Type tnz = pred._type.nonZero(); - Type tcast = tnz.join(pred._type); - if( tcast != pred._type ) { - Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep(); - _guards.add(pred); - _guards.add(cast); - replace(pred,cast); - } + Type tnz = pred._type.nonZero(); + _addGuard(tnz,ctrl,pred); // Compute the negative test type. if( pred instanceof NotNode not ) { Node npred = not.in(1); Type tzero = npred._type.makeZero(); - Type tzcast= tzero.join(npred._type); - if( tzcast != npred._type ) { - Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep(); - _guards.add(npred); - _guards.add( cast); - replace(npred,cast); - } + _addGuard(tzero,ctrl,npred); + } + } + + private void _addGuard(Type guard, Node ctrl, Node pred) { + Type tcast = guard.join(pred._type); + if( tcast != pred._type ) { + Node cast = new CastNode(tcast,ctrl,pred.keep()).peephole().keep(); + _guards.add(pred); + _guards.add(cast); + replace(pred,cast); } } + // Remove matching pred/cast pairs from this guarded region. public void removeGuards( Node ctrl ) { assert ctrl instanceof CFGNode; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java index e167fd68..d3639ed7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -44,7 +44,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java index b8c226bd..6f4a2c6c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class ShrNode extends Node { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 44a56a93..5bc88aa5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -71,7 +71,7 @@ public class StoreNode extends MemOpNode { return this; } - // Simple store-after-new on same address. Should pick up the + // Simple store-after-new on same address. Should pick up // an init-store being stomped by a first user store. if( mem() instanceof ProjNode st && st .in(0) instanceof NewNode nnn && ptr() instanceof ProjNode ptr && ptr.in(0) == nnn && @@ -86,7 +86,7 @@ public class StoreNode extends MemOpNode { val()._type.isHighOrConst() && // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. - //checkOnlyUse(st) && + checkOnlyUse(st) && // Folding away a broken store err()==null ) { nnn.setDef(nnn.findAlias(_alias),val()); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SubNode.java index 5d6c2643..339c65ca 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class SubNode extends Node { @@ -25,6 +24,9 @@ public class SubNode extends Node { Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -35,9 +37,6 @@ public class SubNode extends Node { i2._min != Long.MIN_VALUE ) return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); } - // Sub of same is 0 - if( in(1)==in(2) ) - return TypeInteger.ZERO; return TypeInteger.BOT; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 1d147cf6..4557a29e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -21,8 +21,8 @@ public class ToFloatNode extends Node { @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) - return TypeFloat.constant(i0.value()); - return TypeFloat.BOT; + return i0.value()==0 ? Type.NIL : TypeFloat.constant(i0.value()); + return TypeFloat.F64; } @Override public Node idealize() { return null; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java index 39f7fcc2..1ed75fe4 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java @@ -37,7 +37,7 @@ public class Field extends Type { @Override public Field makeRO() { return _final ? this : make(_fname,_type.makeRO(),_alias,true); } @Override public boolean isFinal() { return _final && _type.isFinal(); } - public static final Field TEST = make("test",TypeInteger.ZERO,-2,false); + public static final Field TEST = make("test",Type.NIL,-2,false); public static void gather(ArrayList<Type> ts) { ts.add(TEST); } @Override Field xmeet( Type that ) { @@ -52,12 +52,7 @@ public class Field extends Type { @Override public Field glb() { Type glb = _type.glb(); - return glb==_type ? this : make(_fname,glb,_alias,_final); - } - - @Override public Field lub() { - Type lub = _type.lub(); - return lub==_type ? this : make(_fname,lub,_alias,_final); + return (glb==_type && _final) ? this : make(_fname,glb,_alias,true); } // Override in subclasses diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java index 70e2dccf..5104f080 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java @@ -31,39 +31,48 @@ public class Type { static final byte TTOP = 1; // Top (ANY) static final byte TCTRL = 2; // Ctrl flow bottom 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 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 - static final byte TARRAY =12; // Array - static final byte TFUNPTR =13; // Function + static final byte TNIL = 4; // low null of all flavors + static final byte TXNIL = 5; // high or choice null + static final byte TSIMPLE = 6; // End of the Simple Types + + static final byte TPTR = 7; // All nil-able scalar values + static final byte TINT = 8; // All Integers; see TypeInteger + static final byte TFLT = 9; // All Floats ; see TypeFloat + static final byte TMEMPTR =10; // Memory pointer to a struct type + static final byte TFUNPTR =11; // Function pointer; unique signature and code address (just a bit) + static final byte TTUPLE =12; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TMEM =13; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TSTRUCT =14; // Structs; tuples with named fields + static final byte TFLD =15; // Named fields in structs public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl","nil","~nil"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ).intern(); // ALL public static final Type TOP = new Type( TTOP ).intern(); // ANY public static final Type CONTROL = new Type( TCTRL ).intern(); // Ctrl public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl + public static final Type NIL = new Type( TNIL ).intern(); // low null of all flavors + public static final Type XNIL = new Type( TXNIL ).intern(); // high or choice null public static Type[] gather() { ArrayList<Type> ts = new ArrayList<>(); ts.add(BOTTOM); ts.add(CONTROL); - Field.gather(ts); + ts.add(NIL); + ts.add(XNIL); + TypeNil.gather(ts); + TypePtr.gather(ts); TypeInteger.gather(ts); TypeFloat.gather(ts); - TypeMem.gather(ts); TypeMemPtr.gather(ts); + TypeFunPtr.gather(ts); + TypeMem.gather(ts); + Field.gather(ts); TypeStruct.gather(ts); TypeTuple.gather(ts); - TypeFunPtr.gather(ts); int sz = ts.size(); for( int i = 0; i < sz; i++ ) ts.add(ts.get(i).dual()); @@ -71,12 +80,12 @@ public class Type { } // Is high or on the lattice centerline. - public boolean isHigh () { return _type==TTOP || _type==TXCTRL; } - public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; } + public boolean isHigh () { return _type==TTOP || _type==TXCTRL || _type==TXNIL; } + public boolean isHighOrConst() { return isHigh() || isConstant(); } // Strict constant values, things on the lattice centerline. // Excludes both high and low values - public boolean isConstant() { return false; } + public boolean isConstant() { return _type==TNIL; } // ---------------------------------------------------------- @@ -88,7 +97,7 @@ public class Type { // to be immutable once defined. The rationale for interning is // *correctness* with cyclic type definitions. Simple structural recursive // checks go exponential with merely sharing, but with cycles they will - // stack overflow and crash. Intering means we do not need to have sharing + // stack overflow and crash. Interning means we do not need to have sharing // checks with every type compare, only during interning. // Factory method which interns "this" @@ -127,6 +136,9 @@ public class Type { if( t == this ) return this; // Same-type is always safe in the subclasses if( _type==t._type ) return xmeet(t); + // TypeNil vs TypeNil meet + if( this instanceof TypeNil ptr0 && t instanceof TypeNil ptr1 ) + return ptr0.nmeet(ptr1); // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". if( is_simple() ) return this.xmeet(t ); if( t.is_simple() ) return t .xmeet(this); @@ -141,18 +153,27 @@ public class Type { // ANY meet anything is thing; thing meet ALL is ALL if( _type==TBOT || t._type==TTOP ) return this; if( _type==TTOP || t._type==TBOT ) return t; - // 'this' is {TCTRL,TXCTRL} + + // RHS TypeNil vs NIL/XNIL + if( _type== TNIL ) return t instanceof TypeNil ptr ? ptr.meet0() : (t._type==TXNIL ? TypePtr.PTR : BOTTOM); + if( _type== TXNIL ) return t instanceof TypeNil ptr ? ptr.meetX() : (t._type== TNIL ? TypePtr.PTR : BOTTOM); + // 'this' is only {TCTRL,TXCTRL} + // Other non-simple RHS things bottom out if( !t.is_simple() ) return BOTTOM; - // 't' is {TCTRL,TXCTRL} + // If RHS is NIL/XNIL + if( t._type==TNIL || t._type==TXNIL ) return BOTTOM; + // Both are {TCTRL,TXCTRL} and unequal to each other return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; } public Type dual() { return switch( _type ) { - case TBOT -> TOP; - case TTOP -> BOTTOM; - case TCTRL -> XCONTROL; - case TXCTRL -> CONTROL; + case TBOT -> TOP; + case TTOP -> BOTTOM; + case TCTRL ->XCONTROL; + case TXCTRL-> CONTROL; + case TNIL ->XNIL; + case TXNIL -> NIL; default -> throw Utils.TODO(); // Should not reach here }; } @@ -168,19 +189,13 @@ public class Type { // True if this "isa" t; e.g. 17 isa TypeInteger.BOT public boolean isa( Type t ) { return meet(t)==t; } - /** Compute greatest lower bound in the lattice */ - public Type glb() { return _type==TCTRL ? CONTROL : BOTTOM; } - /** Compute least upper bound in the lattice */ - public Type lub() { return _type==TCTRL ? XCONTROL : TOP; } + public Type nonZero() { return TypePtr.NPTR; } - // Make an initial/default version of this type. Typically, 0 for integers - // and null for nullable pointers. - public Type makeInit() { return this; } // Make a zero version of this type, 0 for integers and null for pointers. - public Type makeZero() { return null; } - // Make a non-zero version of this type, if possible. Integers attempt to - // exclude zero from their range and pointers become not-null. - public Type nonZero() { return glb(); } + public Type makeZero() { return Type.NIL; } + + /** Compute greatest lower bound in the lattice */ + public Type glb() { return Type.NIL; } // Is forward-reference public boolean isFRef() { return false; } @@ -207,7 +222,7 @@ public class Type { return print(new SB()).toString(); } - public SB print(SB sb) { return is_simple() ? sb.p(STRS[_type]) : sb;} + public SB print(SB sb) { return sb.p(str()); } public SB gprint(SB sb) { return print(sb); } // This is used by error messages, and is a shorted print. diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index a11eec90..143adbcd 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -6,104 +6,90 @@ import java.util.ArrayList; /** * Float Type */ -public class TypeFloat extends Type { +public class TypeFloat extends TypeNil { - public final static TypeFloat TOP = make((byte)-64, 0); - public final static TypeFloat T32 = make((byte)-32, 0); - public final static TypeFloat ZERO= make((byte) 0, 0); - public final static TypeFloat B32 = make((byte) 32, 0); - public final static TypeFloat BOT = make((byte) 64, 0); + public final static TypeFloat ONE = constant(1.0); + public final static TypeFloat F32 = make((byte)3, true, 0); + public final static TypeFloat NF64 = make((byte)2,false, 0); + public final static TypeFloat F64 = make((byte)3,false, 0); - /** +/-64 for double; +/-32 for float, or 0 for constants */ - public final byte _sz; + // true for 32bits, false for 64bits + public final boolean _f32; /** * The constant value or 0 */ public final double _con; - private TypeFloat(byte sz, double con) { - super(TFLT); - _sz = sz ; + private TypeFloat(byte nil, boolean f32, double con) { + super(TFLT,nil); + assert !isConstant() || ((float)con == con) == f32; + _f32 = f32; _con = con; } - private static TypeFloat make(byte sz, double con) { - return new TypeFloat(sz,con).intern(); + private static TypeFloat make(byte nil, boolean f32, double con) { + return new TypeFloat(nil,f32,con).intern(); + } + @Override public TypeFloat makeFrom(byte nil) { + return nil==_nil ? this : make(nil,_f32,_con); } - public static TypeFloat constant(double con) { return make((byte)0, con); } - - public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); ts.add(B32); ts.add(constant(3.141592653589793)); } + public static TypeFloat constant(double con) { assert con!=0; return make((byte)2,((float)con)==con, con); } - // FIXME this display format is problematic - // In visualizer '#' gets prepended if its a constant - @Override - public SB print(SB sb) { - if( this==TOP ) return sb.p("FltTop"); - if( this==T32 ) return sb.p("F32Top"); - if( this==B32 ) return sb.p("F32Bot"); - if( this==BOT ) return sb.p("FltBot"); - return sb.p(_con); - } + public static void gather(ArrayList<Type> ts) { ts.add(F64); ts.add(F32); ts.add(constant(3.141592653589793)); } @Override public String str() { - if( this==TOP ) return "~flt"; - if( this==T32 ) return "~f32"; - if( this==B32 ) return "f32"; - if( this==BOT ) return "flt"; - return ""+_con+(isF32() ? "f" : ""); + if( isConstant() ) + return ""+_con+(_f32 ? "f" : ""); + String s = ""; + if( isHigh() ) s = "~"; + if( 1 <= _nil && _nil <= 2 ) // Disallow nil? + s += "n"; + s += "f"; + s += _f32 ? "32" : "lt"; + return s; } - boolean isF32() { return ((float)_con)==_con; } - @Override public boolean isHigh() { return _sz< 0; } - @Override public boolean isHighOrConst() { return _sz<=0; } - @Override public boolean isConstant() { return _sz==0; } - - @Override public int log_size() { - int sz = _sz==0 ? (isF32() ? 32 : 64) : Math.abs(_sz); - return _sz==32 ? 2 : 3; - } + @Override public boolean isConstant() { return _con!=0; } + @Override public int log_size() { return _f32 ? 2 : 3; } public double value() { return _con; } @Override - public Type xmeet(Type other) { - // Invariant from caller: 'this' != 'other' and same class (TypeFloat) + public TypeFloat xmeet(Type other) { + // Invariant from caller: 'this' != 'other' and same class (TypeFloat). TypeFloat i = (TypeFloat)other; // Contract - // Larger size in i1, smaller in i0 - TypeFloat i0 = _sz < i._sz ? this : i; - TypeFloat i1 = _sz < i._sz ? i : this; - - if( i1._sz== 64 ) return BOT; - if( i0._sz==-64 ) return i1; - if( i1._sz== 32 ) - return i0._sz==0 && !i0.isF32() ? BOT : B32; - if( i1._sz!= 0 ) return i1; - // i1 is a constant - if( i0._sz==-32 ) - return i1.isF32() ? i1 : BOT; - // Since both are constants, and are never equals (contract) unequals - // constants fall to bottom - return i0.isF32() && i1.isF32() ? B32 : BOT; + if( isConstant() && i.isHigh() ) return i._f32 && ! _f32 ? NF64 : this; + if( i.isConstant() && isHigh() ) return _f32 && !i._f32 ? NF64 : i ; + + + // From online Karnaugh map; if both values are small the result is + // small, otherwise the result is small if the otherside is high. + boolean f32 = (_f32&i._f32) | (i.isHigh()&_f32) | (isHigh()&i._f32); + return make(xmeet0(i), f32, 0); } @Override public Type dual() { - if( _sz==0 ) return this; // Constants are a self-dual - return make((byte)-_sz,0); + if( isConstant() ) return this; // Constants are a self-dual + return make(dual0(),_f32,0); } - @Override public Type glb() { return BOT; } - @Override public Type lub() { return TOP; } - @Override public TypeFloat makeInit() { return ZERO; } - @Override public TypeFloat makeZero() { return ZERO; } + // RHS is NIL + @Override Type meet0() { + // From high, falling to the least Float that contains a zero + return isHigh() || _f32 ? F32 : F64; + } + + + @Override public Type glb() { return F64; } @Override - int hash() { return (int)(Double.hashCode(_con) ^ _sz); } + int hash() { return (int)(Double.hashCode(_con) ^ (_f32 ? 2048 : 0) ^ super.hash()); } @Override public boolean eq( Type t ) { TypeFloat i = (TypeFloat)t; // Contract - return _con==i._con && _sz==i._sz; + return _con==i._con && _f32==i._f32 && super.eq(i); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 3a0c91ea..9d4e5795 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -32,6 +32,8 @@ public class TypeFunPtr extends Type { } public static TypeFunPtr make( TypeTuple sig, long fidxs ) { return new TypeFunPtr(sig,fidxs).intern(); } + // Make a TFP with all functions + public static TypeFunPtr make( TypeTuple sig, boolean nil ) { return new TypeFunPtr(sig,-2|(nil ? 1 : 0)).intern(); } public static TypeFunPtr BOT = make(TypeTuple.SIGBOT,-1); public static TypeFunPtr TOP = BOT.dual(); @@ -51,12 +53,8 @@ public class TypeFunPtr extends Type { public TypeFunPtr dual() { return TypeFunPtr.make(_sig.dual(), ~_fidxs); } @Override public TypeFunPtr glb() { throw Utils.TODO(); } - @Override public TypeFunPtr lub() { throw Utils.TODO(); } // Is forward-reference @Override public boolean isFRef() { return false; } - @Override public Type makeInit() { return (_fidxs&1)==1 ? NULLPTR : Type.TOP; } - @Override public Type makeZero() { return NULLPTR; } - @Override public Type nonZero() { return VOIDPTR; } @Override public boolean isHigh() { return this==TOP; } @Override public boolean isConstant() { return Long.bitCount(_fidxs)==1; } @@ -73,38 +71,48 @@ public class TypeFunPtr extends Type { return _sig == ptr._sig && _fidxs == ptr._fidxs; } + + @Override public String str() { + if( this== NULLPTR) return "null"; + if( this== VOIDPTR) return "*void"; + return print(new SB()).toString(); + } + // [void,name,MANY]*[,?] - @Override - public SB print(SB sb) { + @Override public SB print(SB sb) { if( this== NULLPTR) return sb.p("null"); if( this== VOIDPTR) return sb.p("*void"); sb.p("{ "); for( int i=1; i<_sig._types.length; i++ ) _sig._types[i].print(sb).p(" "); _sig._types[0].print(sb.p("-> ")); - sb.p(String.format(" #%X",_fidxs)); - sb.p("}"); + sb.p(" #"); + long fidxs = _fidxs&-2; // Strip off the null flag bit + String fidx = fidxs==0 ? "" + : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) + : fidxs == -2 ? "ALL" + : "b"+Long.toBinaryString(fidxs); // Just some function bits + sb.p(fidx).p("}"); if( (_fidxs&1)==1 ) sb.p("?"); return sb; } - @Override - public SB gprint(SB sb) { + + @Override public SB gprint(SB sb) { if( this== NULLPTR) return sb.p("null"); if( this== VOIDPTR) return sb.p("*void"); sb.p("{ "); for( int i=1; i<_sig._types.length; i++ ) _sig._types[i].gprint(sb).p(" "); _sig._types[0].gprint(sb.p("-> ")); - sb.p(String.format(" #%X",_fidxs)); - sb.p("}"); + sb.p(" #"); + long fidxs = _fidxs&-2; // Strip off the null flag bit + String fidx = fidxs==0 ? "" + : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) + : fidxs == -2 ? "ALL" + : "b"+Long.toBinaryString(fidxs); // Just some function bits + sb.p(fidx).p("}"); if( (_fidxs&1)==1 ) sb.p("?"); return sb; } - @Override public String str() { - if( this== NULLPTR) return "null"; - if( this== VOIDPTR) return "*void"; - return print(new SB()).toString(); - } - } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 2be4f4d8..77b280f3 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -9,17 +9,19 @@ import java.util.ArrayList; */ public class TypeInteger extends Type { - public final static TypeInteger TOP = make(false, 0); - public final static TypeInteger BOT = make(false, 1); public final static TypeInteger ZERO= make(0,0); - public final static TypeInteger U1 = make(0,1); - public final static TypeInteger BOOL= U1; public final static TypeInteger FALSE=ZERO; public final static TypeInteger TRUE= make(1,1); + + public final static TypeInteger I1 = make(-1,0); public final static TypeInteger I8 = make(-128,127); public final static TypeInteger I16 = make(-32768,32767); public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1); + public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE); + public final static TypeInteger TOP = BOT.dual(); + public final static TypeInteger U1 = make(0,1); + public final static TypeInteger BOOL= U1; 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); @@ -27,45 +29,50 @@ public class TypeInteger extends Type { /** * Describes an integer *range* - everything from min to max; both min and * max are inclusive. If min==max, this is a constant. - * + * <br> * If min <= max, this is a below center (towards bottom). * If min > max, this is an above center (towards top). */ public final long _min, _max; - private TypeInteger(long min, long max) { super(TINT); _min = min; _max = max; } - public static TypeInteger make(long lo, long hi) { return new TypeInteger(lo,hi).intern(); } - public static TypeInteger make(boolean is_con, long con) { - return make(is_con ? con : (con==0 ? Long.MAX_VALUE : Long.MIN_VALUE), - is_con ? con : (con==0 ? Long.MIN_VALUE : Long.MAX_VALUE)); + private TypeInteger(long min, long max) { + super(TINT); + _min = min; + _max = max; } - public static TypeInteger constant(long con) { return make(true, con); } + // Strict non-zero contract + public static TypeInteger make(long lo, long hi) { return new TypeInteger(lo,hi).intern(); } - public static void gather(ArrayList<Type> ts) { ts.add(ZERO); ts.add(BOT); ts.add(U1); ts.add(U8); } + public static TypeInteger constant(long con) { return make(con, con); } - // FIXME this display format is problematic - // In visualizer '#' gets prepended if its a constant - @Override - public SB print(SB sb) { return sb.p(str()); } + public static void gather(ArrayList<Type> ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); } @Override public String str() { - if( this==TOP ) return "~int"; - if( this==BOT ) return "int"; - if( this==BOOL) return ("bool"); - if( this==I8 ) return ("i8"); - if( this==I16 ) return ("i16"); - if( this==I32 ) return ("i32"); - if( this==U8 ) return ("u8"); - if( this==U16 ) return ("u16"); - if( this==U32 ) return ("u32"); if( isConstant() ) return ""+_min; - return "["+_min+"-"+_max+"]"; + long lo = _min, hi = _max; + String x = ""; + if( hi < lo ) { + lo = _max; hi = _min; + x = "~"; + } + return x+_str(lo,hi); + } + private static String _str(long lo, long hi) { + if( lo==Long.MIN_VALUE && hi==Long.MAX_VALUE ) return "int"; + if( lo== 0 && hi== 1 ) return "bool"; + if( lo== -1 && hi== 0 ) return "i1"; + if( lo== -128 && hi== 127 ) return "i8"; + if( lo== -32768 && hi== 32767 ) return "i16"; + if( lo== -1L<<31 && hi==(1L<<31)-1 ) return "i32"; + if( lo== 0 && hi== 255 ) return "u8"; + if( lo== 0 && hi== 65535 ) return "u16"; + if( lo== 0 && hi==(1L<<32)-1 ) return "u32"; + return "["+lo+"-"+hi+"]"; } - @Override public boolean isHigh () { return _min > _max; } - @Override public boolean isHighOrConst() { return _min >= _max; } - @Override public boolean isConstant () { return _min == _max; } + @Override public boolean isHigh () { return _min > _max; } + @Override public boolean isConstant() { return _min == _max; } @Override public int log_size() { if( this==I8 || this==U8 || this==BOOL ) return 0; // 1<<0 == 1 bytes @@ -84,8 +91,6 @@ public class TypeInteger extends Type { public long mask() { if( isHigh() ) return 0; if( isConstant() ) return _min; - //if( _min<0 ) return -1L; - //if( _max==Long.MAX_VALUE ) return -1L; // Those bit positions which differ min to max long x = _min ^ _max; // Highest '1' bit in the differ set. Since the range is from min to @@ -105,19 +110,17 @@ public class TypeInteger extends Type { } @Override public TypeInteger dual() { return make(_max,_min); } - @Override public TypeInteger glb() { return BOT; } - @Override public TypeInteger lub() { return TOP; } - @Override public TypeInteger makeInit() { return ZERO; } - @Override public TypeInteger makeZero() { return ZERO; } + @Override public TypeInteger nonZero() { if( isHigh() ) return this; if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL if( _max==0 ) return make(_min,-1); return this; } - @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); } - @Override - public boolean eq( Type t ) { + @Override public Type makeZero() { return TypeInteger.ZERO; } + @Override public TypeInteger glb() { return BOT; } + @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } + @Override public boolean eq( Type t ) { TypeInteger i = (TypeInteger)t; // Contract return _min==i._min && _max==i._max; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 007a18d6..60b3612f 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -25,7 +25,7 @@ public class TypeMem extends Type { public static final TypeMem TOP = make(0, Type.TOP ); public static final TypeMem BOT = make(0, Type.BOTTOM); - public static void gather(ArrayList<Type> ts) { ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } + public static void gather(ArrayList<Type> ts) { ts.add(make(1,Type.NIL)); ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } @Override TypeMem xmeet(Type t) { @@ -45,25 +45,20 @@ public class TypeMem extends Type { } @Override public Type glb() { return make(_alias,_t.glb()); } - @Override public Type lub() { return make(_alias,_t.lub()); } - @Override - int hash() { return 9876543 + _alias + _t.hashCode(); } + @Override int hash() { return 9876543 + _alias + _t.hashCode(); } - @Override - boolean eq(Type t) { + @Override boolean eq(Type t) { TypeMem that = (TypeMem) t; // Invariant return _alias == that._alias && _t == that._t; } - @Override - public SB print(SB sb) { + @Override public SB print(SB sb) { sb.p("#"); if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); return _t.print(sb.p(_alias).p(":")); } - @Override - public SB gprint(SB sb) { + @Override public SB gprint(SB sb) { sb.p("#"); if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); return _t.gprint(sb.p(_alias).p(":")); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index b675eef5..d17cfd39 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; import java.util.ArrayList; /** @@ -12,9 +13,9 @@ import java.util.ArrayList; * The distinguished *$BOT ptr represents union of *void and Null. * The distinguished *$TOP ptr represents the dual of *$BOT. */ -public class TypeMemPtr extends Type { +public class TypeMemPtr extends TypeNil { // A TypeMemPtr is pair (obj,nil) - // where obj is a TypeStruct, possibly TypeStruct.BOT + // where obj is a TypeStruct, possibly TypeStruct.BOT/TOP // where nil is an explicit null is allowed or not // Examples: @@ -24,82 +25,70 @@ public class TypeMemPtr extends Type { // (TOP ,true ) - a nil public final TypeStruct _obj; - public final boolean _nil; - private TypeMemPtr(TypeStruct obj, boolean nil) { - super(TMEMPTR); + private TypeMemPtr(byte nil, TypeStruct obj) { + super(TMEMPTR,nil); assert obj!=null; _obj = obj; - _nil = nil; } - public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } - public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } - public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(obj, _nil); } - public TypeMemPtr makeFrom(boolean nil) { return nil==_nil ? this : make(_obj, nil); } + public static TypeMemPtr make(byte nil, TypeStruct obj) { return new TypeMemPtr(nil, obj).intern(); } + public static TypeMemPtr make(TypeStruct obj) { return make((byte)3, obj); } + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj); } + @Override public TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil,_obj); } @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); } @Override public boolean isFinal() { return _obj.isFinal(); } // An abstract pointer, pointing to either a Struct or an Array. - // Can also be null or not. - public static TypeMemPtr BOT = make(TypeStruct.BOT,true); + // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} + public static TypeMemPtr BOT = make((byte)3, TypeStruct.BOT); public static TypeMemPtr TOP = BOT.dual(); - // An abstract null (can be Struct or Array) or not-null C void* - public static TypeMemPtr NULLPTR = make(TypeStruct.TOP,true); - public static TypeMemPtr VOIDPTR = NULLPTR.dual(); // A bottom mix of not-null ptrs, like C's void* but not null + public static TypeMemPtr NOTBOT = make((byte)2,TypeStruct.BOT); - public static TypeMemPtr TEST= make(TypeStruct.TEST,false); - public static void gather(ArrayList<Type> ts) { ts.add(NULLPTR); ts.add(BOT); ts.add(TEST); } + public static TypeMemPtr TEST= make((byte)2, TypeStruct.TEST); + public static void gather(ArrayList<Type> ts) { ts.add(NOTBOT); ts.add(BOT); ts.add(TEST); } @Override - Type xmeet(Type t) { + public TypeNil xmeet(Type t) { TypeMemPtr that = (TypeMemPtr) t; - return TypeMemPtr.make((TypeStruct)_obj.meet(that._obj), _nil | that._nil); + return TypeMemPtr.make(xmeet0(that), (TypeStruct)_obj.meet(that._obj)); } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } + public TypeMemPtr dual() { return TypeMemPtr.make( dual0(), _obj.dual()); } - @Override public TypeMemPtr glb() { return make(_obj.glb(),true ); } - @Override public TypeMemPtr lub() { return make(_obj.lub(),false); } + // RHS is NIL + @Override Type meet0() { + // NOT DOING DUAL + return _nil==3 ? this : make((byte)3,_obj); + } + + @Override public TypeMemPtr glb() { return make((byte)3,_obj.glb()); } // Is forward-reference @Override public boolean isFRef() { return _obj.isFRef(); } - @Override public Type makeInit() { return _nil ? NULLPTR : Type.TOP; } - @Override public Type makeZero() { return NULLPTR; } - @Override public Type nonZero() { return VOIDPTR; } - - @Override public boolean isHigh() { return this==TOP; } - @Override public boolean isConstant() { return this==NULLPTR; } - @Override public boolean isHighOrConst() { return this==TOP || this==NULLPTR; } @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers - @Override - int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } + @Override int hash() { return _obj.hashCode() ^ super.hash(); } - @Override - boolean eq(Type t) { + @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _obj == ptr._obj && _nil == ptr._nil; - } - - // [void,name,MANY]*[,?] - @Override - public SB print(SB sb) { - if( this== NULLPTR) return sb.p("null"); - if( this== VOIDPTR) return sb.p("*void"); - return _obj.print(sb.p("*")).p(_nil ? "?" : ""); - } - @Override - public SB gprint(SB sb) { - if( this== NULLPTR) return sb.p("null"); - if( this== VOIDPTR) return sb.p("*void"); - return _obj.gprint(sb.p("*")).p(_nil ? "?" : ""); + return _obj == ptr._obj && super.eq(ptr); } @Override public String str() { - if( this== NULLPTR) return "null"; - if( this== VOIDPTR) return "*void"; - return "*"+_obj.str()+(_nil ? "?" : ""); + if( this== NOTBOT) return "*void"; + if( this== BOT) return "*void?"; + return x()+"*"+_obj.str()+q(); } + @Override public SB print(SB sb) { + if( this== NOTBOT) return sb.p("*void"); + if( this== BOT) return sb.p("*void?"); + return _obj.print(sb.p(x()).p("*")).p(q()); + } + @Override public SB gprint(SB sb) { + if( this== NOTBOT) return sb.p("*void"); + if( this== BOT) return sb.p("*void?"); + return _obj.gprint(sb.p(x()).p("*")).p(q()); + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeNil.java new file mode 100644 index 00000000..d8003d50 --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -0,0 +1,57 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import java.util.ArrayList; + +/** + * Nil-able Scalar types + */ +public abstract class TypeNil extends Type { + // 0 = high-subclass choice nil + // 1 = high-subclass no nil + // 2 = low -subclass no nil + // 3 = low -subclass also nil + public final byte _nil; + + TypeNil(byte t, byte nil ) { super(t); _nil = nil; } + + public static void gather(ArrayList<Type> ts) { } + + abstract TypeNil makeFrom(byte nil); + + byte xmeet0(TypeNil that) { return (byte)Math.max(_nil,that._nil); } + + byte dual0() { return (byte)(3-_nil); } + + // RHS is NIL + abstract Type meet0(); + + // RHS is XNIL + Type meetX() { + return _nil==0 ? XNIL : (_nil<=2 ? TypePtr.NPTR : TypePtr.PTR); + } + + Type nmeet(TypeNil tn) { + // Invariants: both are TypeNil subclasses and unequal classes. + // If this is TypePtr, we went to TypePtr.nmeet and not here. + // If that is TypePtr, this is not (invariant); reverse and go again. + if( tn instanceof TypePtr ts ) return ts.nmeet(this); + + // Two mismatched TypeNil, no Scalar. + if( _nil==0 && tn._nil==0 ) return XNIL; + if( _nil<=2 && tn._nil<=2 ) return TypePtr.NPTR; + return TypePtr.PTR; + } + + @Override public boolean isHigh () { return _nil <= 1; } + @Override public boolean isConstant () { return false; } + @Override public boolean isHighOrConst() { return isHigh() || isConstant(); } + + final String q() { return _nil == 1 || _nil == 2 ? "" : "?"; } + final String x() { return isHigh() ? "~" : ""; } + + int hash() { return _nil<<17; } + + boolean eq(TypeNil ptr) { return _nil == ptr._nil; } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypePtr.java new file mode 100644 index 00000000..e9091c25 --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -0,0 +1,53 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import java.util.ArrayList; + +/** + * Represents a Scalar; a single register-sized value. + */ +public class TypePtr extends TypeNil { + + private TypePtr(byte nil) { super(TPTR,nil); } + + // An abstract pointer, pointing to either a Struct or an Array. + // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} + public static TypePtr XPTR = new TypePtr((byte)0).intern(); + public static TypePtr XNPTR= new TypePtr((byte)1).intern(); + public static TypePtr NPTR = new TypePtr((byte)2).intern(); + public static TypePtr PTR = new TypePtr((byte)3).intern(); + private static final TypePtr[] PTRS = new TypePtr[]{XPTR,XNPTR,NPTR,PTR}; + + public static void gather(ArrayList<Type> ts) { ts.add(PTR); ts.add(NPTR); } + + TypeNil makeFrom(byte nil) { throw Utils.TODO(); } + + @Override public TypeNil xmeet(Type t) { + TypePtr that = (TypePtr) t; + return PTRS[xmeet0(that)]; + } + + @Override public TypePtr dual() { return PTRS[dual0()]; } + + // High scalar loses, low scalar wins + @Override TypeNil nmeet(TypeNil tn) { + if( _nil==0 ) return tn; // High scalar loses + if( _nil==1 ) return tn.makeFrom(xmeet0(tn)); // High scalar loses + if( _nil==2 ) return tn._nil==3 ? PTR : NPTR; // Low scalar wins + return PTR; // this + } + + + // RHS is NIL + @Override Type meet0() { return isHigh() ? NIL : PTR; } + // RHS is XNIL + // 0->xscalar, 1->nscalar, 2->nscalar, 3->scalar + @Override Type meetX() { return _nil==0 ? XNIL : (_nil==3 ? PTR : NPTR); } + + @Override public TypePtr glb() { return PTR; } + + private static final String[] STRS = new String[]{"~ptr","~nptr","nptr","ptr"}; + @Override public String str() { return STRS[_nil]; } + @Override public SB print(SB sb) { return sb.p(str()); } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index c3ee5eb3..35bbe36c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -49,7 +49,7 @@ public class TypeStruct extends Type { // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { - assert !(body instanceof TypeMemPtr tmp && !tmp._nil); + assert body instanceof TypeInteger || (body instanceof TypeNil tn && tn._nil==3); return make("[" + body.str() + "]", Field.make("#" ,len , lenAlias,true ), Field.make("[]",body,bodyAlias,false)); @@ -58,10 +58,10 @@ public class TypeStruct extends Type { // A pair of self-cyclic types private static final TypeStruct S1F = makeFRef("S1"); private static final TypeStruct S2F = makeFRef("S2"); - public static final TypeStruct S1 = make("S1", Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) ); - private static final TypeStruct S2 = make("S2", Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) ); + public static final TypeStruct S1 = make("S1", Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make((byte)2,S2F),-2, false) ); + private static final TypeStruct S2 = make("S2", Field.make("b", TypeFloat .F64, -3, false), Field.make("s1",TypeMemPtr.make((byte)2,S1F),-4, false) ); - private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2); + private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeInteger.BOT,-2); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } @@ -143,22 +143,6 @@ public class TypeStruct extends Type { return false; return true; } - @Override public TypeStruct lub() { - if( _lub() ) return this; - // Need to glb each field - Field[] flds = new Field[_fields.length]; - for( int i=0; i<_fields.length; i++ ) - flds[i] = _fields[i].lub(); - return make(_name,flds); - } - private boolean _lub() { - if( _fields!=null ) - for( Field f : _fields ) - if( f.lub() != f ) - return false; - return true; - } - // Is forward-reference @Override public boolean isFRef() { return _fields==null; } |