diff options
Diffstat (limited to 'src')
138 files changed, 2588 insertions, 954 deletions
diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 6f307785..ea618757 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -3,7 +3,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.text.ParseException; + import java.util.*; /** @@ -23,7 +23,7 @@ public class Parser { public final CodeGen _code; // The Lexer. Thin wrapper over a byte[] buffer with a cursor. - private final Lexer _lexer; + private Lexer _lexer; /** * Current ScopeNode - ScopeNodes change as we parse code, but at any point of time @@ -83,7 +83,7 @@ public class Parser { // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not // have C-style '*ptr' references. - public static HashMap<String, Type> TYPES; + public static HashMap<String, Type> TYPES = defaultTypes(); // Mapping from a type name to the constructor for a Type. public final HashMap<String, StructNode> INITS; @@ -91,7 +91,6 @@ public class Parser { public Parser(CodeGen code, TypeInteger arg) { _code = code; - _lexer = new Lexer(code._src); _scope = new ScopeNode(); _continueScope = _breakScope = null; ZERO = con(TypeInteger.ZERO).keep(); @@ -132,7 +131,9 @@ public class Parser { private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } public void parse() { - _xScopes.push(_scope); + // Graph callbacks during scope setup need a source position. + _lexer = new Lexer(com.seaofnodes.simple.sys.SYS); + _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null, _lexer); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null, _lexer); @@ -140,6 +141,16 @@ public class Parser { ctrl(XCTRL); _scope.mem(con(TypeMem.BOT)); + // Parse the sys import + while( !_lexer.isEOF() ) { + parseStatement(); + _lexer.skipWhiteSpace(); + } + + // Reset lexer for program text + _lexer = new Lexer(_code._src); + _xScopes.push(_scope); + // Parse whole program, as-if function header "{ int arg -> body }" parseFunctionBody(_code._main,loc(),"arg"); @@ -148,9 +159,10 @@ public class Parser { // default main). FunNode main = _code.link(_code._main); StopNode stop = _code._stop; - if( main.ret().expr() instanceof ConstantNode && main.ret().mem().in(0)==main && stop.nIns() > 1 ) { + if( main.ret().expr()._type==Type.TOP && main.uctrl()==null ) { // Kill an empty default main; so it does not attempt to put a // "main" in any final ELF file + main.setDef(1,XCTRL); // Delete default start input stop.delDef(stop._inputs.find(main.ret())); } else { // We have a non-empty default main. @@ -188,7 +200,7 @@ public class Parser { ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; - FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,null,_code._start)); + FunNode fun = _fun = (FunNode)peep(new FunNode(loc(),sig,_nestedType,null,_code._start)); // Once the function header is available, install in linker table - // allowing recursive functions. Linker matches on declared args and // exact fidx, and ignores the return (because the fidx will only match @@ -225,9 +237,14 @@ public class Parser { while (!peek('}') && !_lexer.isEOF()) last = parseStatement(); - // Last expression is the return + // Last expression is the return except for the top-level main if( ctrl()._type==Type.CONTROL ) - fun.addReturn(ctrl(), _scope.mem(), last); + if( fun.sig() != _code._main ) + fun.addReturn(ctrl(), _scope.mem(), last); + else { + fun.setDef(1,XCTRL); // Kill default main + _code.addAll(fun._outputs); + } // Pop off the inProgress node on the multi-exit Region merge assert r.inProgress(); @@ -285,8 +302,7 @@ public class Parser { * @return a {@link Node} or {@code null} */ private Node parseStatement() { - if( false ) return null; - else if (matchx("return") ) return parseReturn(); + if( matchx("return") ) return parseReturn(); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); else if (matchx("for") ) return parseFor(); @@ -400,7 +416,7 @@ public class Parser { // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection _scope.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate - parseStatement(); // Parse loop body + parseStatement().isKill(); // Parse loop body _scope.removeGuards(ifT); // Merge the loop bottom into other continue statements @@ -437,8 +453,11 @@ public class Parser { // At exit the false control is the current control, and // the scope is the exit scope after the exit test. - _xScopes.pop(); - _xScopes.push(exit); + // During sys parsing, there is no xscope here. + if( !_xScopes.isEmpty() ) { + _xScopes.pop(); + _xScopes.push( exit ); + } _scope = exit; return ZERO; } @@ -622,7 +641,7 @@ public class Parser { throw error("Cannot reassign final '"+name+"'"); // Lift expression, based on type - Node lift = liftExpr(expr.keep(), def.type()); + Node lift = liftExpr(expr.keep(), def.type(), true); // Update _scope.update(name,lift); // Return un-lifted expr @@ -631,19 +650,30 @@ public class Parser { // Apply declared access permissions; widen floats and narrow integers. // Early error if types do not match variable. - private Node liftExpr( Node expr, Type t ) { - assert !(expr._type instanceof TypeMemPtr tmp) || !tmp.isFRef(); + private Node liftExpr( Node expr, Type t, boolean isLoad ) { + if( expr._type instanceof TypeMemPtr tmp && tmp.isFRef() ) + throw error("Must define forward ref "+tmp._obj._name); // Read-only access is deep; a fixed binding alone does not remove access. if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) { expr = peep(new ReadOnlyNode(expr)); } + // Auto-widen array to i64 (cast ptr to raw int bits) + if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) + expr = peep(new AddNode(peep(new CastNode(t,ctrl(),expr)),con(tmp._obj.aryBase()))); // Auto-widen int to float expr = widenInt( expr, t ); - // Auto-narrow wide ints to narrow ints - expr = zsMask(expr,t); + // Auto-narrow wide ints to narrow ints. For loads, emit code to force + // the loaded value to match the declared sign/zero bits. For stores, + // just force the type, acting "as if" the store silently truncates. + if( expr._type instanceof TypeFloat && t instanceof TypeInteger ) + expr = peep(new ToIntegerNode(expr)); + Type et = expr._type; + if( isLoad ) { expr = zsMask(expr,t); et = expr._type; } + else if( et instanceof TypeInteger && t instanceof TypeInteger ) et=t; + // Type is sane - if( expr._type!=Type.BOTTOM && (!expr._type.shallowISA(t) || !expr._type.accessISA(t)) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); + if( et!=Type.BOTTOM && (!et.shallowISA(t) || !et.accessISA(t)) ) + throw error("Type " + et.str() + " is not of declared type " + t.str()); return expr; } @@ -659,7 +689,10 @@ public class Parser { * exprAsgn = var '=' exprAsgn | expr */ private Node parseDeclarationStatement() { + int old = pos(); Type t = type(); + if( peek('.') ) // Ambiguity static vars: "type.var", parse as expression + { pos(old); t=null; } if( t == null ) return require(parseAsgn(),";"); @@ -676,9 +709,9 @@ public class Parser { if( t instanceof TypeMemPtr tmp ) { Type base = TYPES.get(tmp._obj._name); TypeMemPtr ptr = (TypeMemPtr)base; - return (tmp._ro ? ptr.makeRO() : ptr).makeNullable(); + return ptr.withAccess(tmp._ro).makeNullable(); } - return t.glb(); + return t.glb(false); } // The binding modifier sits immediately before the name. It never @@ -701,7 +734,9 @@ public class Parser { // Optional initializing expression follows Node expr; if( match("=") ) { - expr = parseAsgn(); + expr = isExternDecl() + ? externDecl(name,t) + : parseAsgn(); // var/val, then type comes from expression if( inferType ) { if( expr._type==Type.NIL ) @@ -709,14 +744,17 @@ public class Parser { t = expr._type; if( !xfinal ) t = inferredType(t); // Widen if not final } - if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - _code.link(tfp)._name = name; + // expr is a constant function + if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( expr instanceof ExternNode ) t = expr._type; // Upgrade declared type to exact function + else _code.link(tfp).setName(name); // Assign debug name to Simple function + } } else { // Need an expression to infer the type. // Also, if not-null then need an initializing expression. // Allowed in a class def, because type/init will happen in the constructor. - if( (inferType || (t instanceof TypeNil tn && !tn.nullable() )) && !_scope.inCon() ) + if( (inferType || (t instanceof TypeNil tn && !tn.nullable() )) && !_scope.inConstructor() ) throw errorSyntax("=expression"); // Initial value for uninitialized struct fields. expr = switch( t ) { @@ -732,7 +770,7 @@ public class Parser { } // Lift expression, based on type - Node lift = liftExpr(expr, t); + Node lift = liftExpr(expr, t, true); // Lift type to the declaration. This will report as an error later if // we cannot lift the type. @@ -748,23 +786,23 @@ public class Parser { /** * Parse a struct declaration, and return the following statement. - * Only allowed in top level scope. - * Structs cannot be redefined. + * Structs cannot be redefined, but can be nested. * - * @return The statement following the struct + * @return zero */ + private String _nestedType; private Node parseStruct() { - if (_xScopes.size() > 1) throw error("struct declarations can only appear in top level scope"); + // "struct" already parsed, so expect the struct name next. + String old = _nestedType; String typeName = requireId(); - Type t = TYPES.get(typeName); - if( t!=null && !(t instanceof TypeMemPtr tmp && tmp.isFRef() ) ) - throw error("struct '" + typeName + "' cannot be redefined"); + if( old!=null ) typeName = old+"."+typeName; + _nestedType = typeName; // A Block scope parse, and inspect the scope afterward for fields. _scope.push(ScopeNode.Kind.Constructor); require("{"); while (!peek('}') && !_lexer.isEOF()) - parseStatement(); + parseStatement().isKill(); // Grab the declarations and build fields and a Struct int lexlen = _scope._lexSize.last(); @@ -772,15 +810,19 @@ public class Parser { StructNode s = new StructNode(); Ary<Field> fs = new Ary<>(Field.class); for( int i=lexlen; i<varlen; i++ ) { - s.addDef(_scope.in(i)); - Var v = _scope._vars.at(i); - if( !v.isFRef() ) // Promote to outer scope, not defined here - fs.push(Field.make(v._name,v.type(),_code.getALIAS(),v._final)); + Var v = _scope.var(i); + if( v.isFRef() ) continue; // Promote to outer scope, not defined here + s.addDef(_scope.in(i)); // Keep the program code to generate instance + fs.push(Field.make(v._name,v.type(),_code.getALIAS(),v._final)); } + // Save instance default constructor TypeStruct ts = s._ts = TypeStruct.make(typeName, fs.asAry()); + s.setType(s.compute()); // Do not call peephole, in case the entire struct is a big plain constant TYPES.put(typeName, TypeMemPtr.make(ts)); - INITS.put(typeName,s.peephole().keep()); + INITS.put(typeName,s.keep()); + // Done with struct/block scope + _nestedType = old; require("}"); require(";"); _scope.pop(); @@ -811,6 +853,20 @@ public class Parser { if( t0 == null && KEYWORDS.contains(tname) ) return posT(old1); if( t0 == Type.BOTTOM || t0 == Type.TOP ) return t0; // var/val type inference + + // Check for subtype. + while( true ) { + int old2 = pos(); + if( !match(".") ) break; + String sname = _lexer.matchId(); + if( sname==null ) { pos(old2); break; } + String tsname = tname+"."+sname; + t0 = TYPES.get(tsname); + if( t0==null ) { pos(old2); t0 = TYPES.get(tname); break; } + tname = tsname; + } + + // Still no type found? Assume forward reference Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) :t0; // Null: assume a forward ref type // A qualifier before the name applies to the struct reference, not // to an enclosing array. Arrays have their own [] / [~] qualifier. @@ -843,13 +899,12 @@ public class Parser { int old2 = pos(); if( !match("!") ) match("~"); String id = _lexer.matchId(); - if( !(peek(',') || peek(';') || match("->")) ) - return posT(old1); - pos(old2); // Reset lexer to reparse - if( id==null ) + if( !(peek(',') || peek(';') || match("->")) || id==null ) return posT(old1); // Reset lexer to reparse + pos(old2); // Reset lexer to reparse // Yes a forward ref, so declare it TYPES.put(tname,((TypeMemPtr)t1).withAccess(false)); + // Return the (array, final) type return t2; } @@ -866,10 +921,9 @@ public class Parser { if( t instanceof TypeMemPtr ptr && (ptr._obj._fields==null || !ptr._obj.isAry()) && ary._fields[1]._type instanceof TypeMemPtr old ) t = old.withAccess(ptr._ro); - return TypeMemPtr.make(TypeStruct.makeAry(TypeInteger.U32,ary._fields[0]._alias,t,ary._fields[1]._alias)); + return TypeMemPtr.make(TypeStruct.makeAry(tname,TypeInteger.U32,ary._fields[0]._alias,t,ary._fields[1]._alias)); } - // Need make an array type. - TypeStruct ts = TypeStruct.makeAry(TypeInteger.U32,_code.getALIAS(),t,_code.getALIAS()); + TypeStruct ts = TypeStruct.makeAry(tname,TypeInteger.U32,_code.getALIAS(),t,_code.getALIAS()); assert ts.str().equals(tname); TypeMemPtr tary = TypeMemPtr.make(ts); TYPES.put(tname,tary); @@ -1083,12 +1137,28 @@ public class Parser { */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); + if( _lexer.peek('"') ) return newString(parseString()); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return NIL; + if( match ("'" ) ) return parseChar(); if( match ("(" ) ) return require(parseAsgn(), ")"); if( matchx("new" ) ) return alloc(); if( match ("{" ) ) return require(func(),"}"); + + // Parse static variable lookup: `type.fld` in the type namespace + Type t = type(); + if( t!=null && match(".") ) { + String fld = requireId(); + TypeMemPtr tmp = ((TypeMemPtr)t); + String tname = tmp._obj._name; + StructNode init = INITS.get(tname); + int idx = tmp._obj.find(fld); + if( idx == -1 ) + throw error("Accessing unknown STATIC field"); + return init.in(idx); + } + // Expect an identifier now Var n = requireLookupId(); Node rvalue = _scope.in(n); @@ -1137,12 +1207,13 @@ public class Parser { }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return liftExpr(peep(op.widen()),t); + return liftExpr(peep(op.widen()),t,true); } // Expect an ID here. If not found, assume a forward reference function Var requireLookupId() { + // Try in the normal variable namespace String id = _lexer.matchId(); if( id == null || KEYWORDS.contains(id) ) throw errorSyntax("an identifier or expression"); @@ -1261,6 +1332,18 @@ public class Parser { ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeZero())); return newStruct(ary,size,0,ALTMP); } + private Node newString(String s) { + TypeMemPtr tmp = typeAry(TypeInteger.U8); + int lenAlias = tmp._obj.field("#" )._alias; + int elemAlias = tmp._obj.field("[]")._alias; + TypeConAryB con = TypeConAryB.make(s); + Type elem = con.elem(); + // Make a TMP, not-null (byte)2, singleton (true) (requires text + // strings are hash-interned), with a TypeStruct having a constant + // array body. + TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[u8]", TypeInteger.U32, lenAlias, elem, elemAlias, true, con),true); + return con(str.makeRO()); + } // Memory is one hidden SSA variable, including across branches and loops. private Node mem() { return _scope.mem(); } @@ -1301,14 +1384,12 @@ public class Parser { throw error("Accessing unknown field '" + name + "' from 'null'"); // Sanity check expr for being a reference - if( !(expr._type instanceof TypeMemPtr ptr) ) { + if( !(expr._type instanceof TypeMemPtr ptr) ) throw error( "Expected "+(name=="#" || name=="[]" ? "array" : "reference")+" but found " + 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 + "'"); - TypeStruct base = ptr._obj.isAry() ? ptr._obj : tmp._obj; + // Find the field from the Type. Lookup in the base object field names. + TypeStruct base = ptr._obj; + assert !base.isFRef(); int fidx = base.find(name); if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); @@ -1329,7 +1410,7 @@ public class Parser { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( matchOpx('=','=') ) { Node val = parseAsgn().keep(); - Node lift = liftExpr( val, tf ); + Node lift = liftExpr( val, tf, false ); store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null); return val.unkeep(); // "obj.a = expr" returns the expression while updating memory @@ -1404,7 +1485,7 @@ public class Parser { // Make a concrete function type, with a fidx TypeFunPtr tfp = _code.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); - return con(ret._fun.sig()); + return new FunPtrNode(ret._fun.sig(),ret).peephole(); } /** @@ -1417,10 +1498,10 @@ public class Parser { if( expr._type == Type.NIL ) throw error("Calling a null function pointer"); if( !(expr instanceof FRefNode) && !expr._type.isa(TypeFunPtr.BOT) ) - throw error("Expected a function but got "+expr._type.glb().str()); + throw error("Expected a function but got "+expr._type.glb(false).str()); expr.keep(); // Keep while parsing args - Ary<Node> args = new Ary<Node>(Node.class); + Ary<Node> args = new Ary<>( Node.class ); args.push(null); // Space for ctrl,mem args.push(null); while( !peek(')') ) { @@ -1458,6 +1539,21 @@ public class Parser { return new ProjNode(cend,2,"#2").peephole(); } + // Just after parsing "type foo = " can parse `"C"` + private boolean isExternDecl( ) { + int old = pos(); + String s = parseString(); + if( "C".equals(s) ) return true; + pos(old); + return false; + } + // External linked constant + private Node externDecl( String ex, Type t ) { + if( t instanceof TypeFunPtr tfp ) // Generic TFP from type parse + t = _code.makeFun(tfp._sig,tfp._ret); // Get a FIDX, becomes a constant + return new ExternNode(t,ex).peephole(); + } + /** * Parse integer literal * @@ -1474,6 +1570,50 @@ public class Parser { return _scope.upcastGuard(n.peephole()); } + // Parse a string or null + private String parseString() { + if( !peek('"') ) return null; + _lexer.inc(); + StringBuilder sb = new StringBuilder(); + while( !_lexer.isEOF() ) { + char c = _lexer.nextChar(); + if( c=='"' ) return sb.toString(); + if( c!='\\' ) { + sb.append(c); + continue; + } + if( _lexer.isEOF() ) + throw error("Unclosed string"); + sb.append(escapedChar("string")); + } + throw error("Unclosed string"); + } + + private char escapedChar(String kind) { + char esc = _lexer.nextChar(); + return switch( esc ) { + case '0' -> '\u0000'; + case 'n' -> '\n'; + case 't' -> '\t'; + case 'r' -> '\r'; + case '\\' -> '\\'; + case '"' -> '"'; + case '\'' -> '\''; + default -> throw error("Unknown "+kind+" escape \\\\"+esc); + }; + } + + // Already parsed "'" + private Node parseChar() { + if( _lexer.isEOF() ) throw error("Unclosed character"); + char c = _lexer.nextChar(); + if( c=='\\' ) { + if( _lexer.isEOF() ) throw error("Unclosed character"); + c = escapedChar("character"); + } + return require(con(TypeInteger.constant(c)),"'"); + } + ////////////////////////////////// // Utilities for lexical analysis @@ -1617,7 +1757,15 @@ public class Parser { _input[_position ] == '/' && _input[_position+1] == '/') { inc(); inc(); - while( !isEOF() && _input[_position] != '\n' ) inc(); + while( !isEOF() && _input[_position] != '\n' ) + inc(); + } else if( _position+2 < _input.length && + _input[_position ] == '/' && + _input[_position+1] == '*') { + // Skip /*comment*/ + while( !isEOF() && !(_input[_position-1] == '*' && _input[_position] == '/')) + inc(); + inc(); } else break; } } diff --git a/src/main/java/com/seaofnodes/simple/Var.java b/src/main/java/com/seaofnodes/simple/Var.java index 6e621875..14295395 100644 --- a/src/main/java/com/seaofnodes/simple/Var.java +++ b/src/main/java/com/seaofnodes/simple/Var.java @@ -9,11 +9,13 @@ import com.seaofnodes.simple.type.*; public class Var { public final String _name; // Declared name + // These fields are not final for forward reference late updates or + // promotions. public int _idx; // index in containing scope private Type _type; // Declared type public boolean _final; // Final field - public Parser.Lexer _loc; // Source location public boolean _fref; // Forward ref + public Parser.Lexer _loc; // Source location public Var(int idx, String name, Type type, boolean xfinal, Parser.Lexer loc ) { this(idx,name,type,xfinal,loc,false); @@ -23,8 +25,8 @@ public class Var { _name = name; _type = type; _final = xfinal; - _loc = loc; _fref = fref; + _loc = loc; } // Raw declared type, without resolving a forward reference while printing. public Type _type() { return _type; } @@ -34,10 +36,6 @@ public class Var { Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); return (_type=_type.meet(def)); } - public Type lazyGLB() { - Type t = type(); - return t instanceof TypeMemPtr ? t : t.glb(); - } // Forward reference variables (not types) must be BOTTOM and // distinct from inferred variables @@ -47,8 +45,8 @@ public class Var { assert isFRef() && xfinal; _type = type; _final = true; - _loc = loc; _fref = false; + _loc = loc; } @Override public String toString() { diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 2c44cb05..8a3d6322 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -24,7 +24,7 @@ public class CodeGen { Opto, // Run ideal optimizations TypeCheck, // Last check for bad programs LoopTree, // Build a loop tree; break infinite loops - InstSelect, // Convert to target hardware nodes + Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule RegAlloc, // Register allocation @@ -38,6 +38,7 @@ public class CodeGen { public final String _src; // Compile-time known initial argument type public final TypeInteger _arg; + // --------------------------- public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); } public CodeGen( String src, TypeInteger arg, long workListSeed ) { @@ -57,14 +58,15 @@ public class CodeGen { public CodeGen driver( Phase phase ) { return driver(phase,null,null); } public CodeGen driver( Phase phase, String cpu, String callingConv ) { if( _phase==null ) parse(); - if( _phase.ordinal() < phase.ordinal() ) opto(); - if( _phase.ordinal() < phase.ordinal() ) typeCheck(); - if( _phase.ordinal() < phase.ordinal() ) loopTree(); - if( _phase.ordinal() < phase.ordinal() && cpu != null ) instSelect(cpu,callingConv); - if( _phase.ordinal() < phase.ordinal() ) GCM(); - if( _phase.ordinal() < phase.ordinal() ) localSched(); - if( _phase.ordinal() < phase.ordinal() ) regAlloc(); - if( _phase.ordinal() < phase.ordinal() ) encode(); + int p1 = phase.ordinal(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Opto .ordinal() ) opto(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.TypeCheck .ordinal() ) typeCheck(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LoopTree .ordinal() ) loopTree(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Select .ordinal() && cpu != null ) instSelect(cpu,callingConv); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Schedule .ordinal() ) GCM(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LocalSched.ordinal() ) localSched(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.RegAlloc .ordinal() ) regAlloc(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Encoding .ordinal() ) encode(); return this; } @@ -121,7 +123,7 @@ public class CodeGen { return TypeFunPtr.make((byte)2,sig,ret, 1L<<fidx ); } // Signature for MAIN - public TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM); + public final TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM); // Reverse from a constant function pointer to the IR function being called public FunNode link( TypeFunPtr tfp ) { assert tfp.isConstant(); @@ -176,6 +178,25 @@ public class CodeGen { // Pessimistic peephole optimization on a worklist _iter.iterate(this); + + // Not really a true optimistic pass, but look for unlinked functions. + // This can be removed, which may trigger another round of pessimistic. + // This is the point where we flip from a virtual Call Graph (any call + // can call any function) to having a correct (but conservative) CG. + + FunNode main = link(_main); + for( int i=0; i<_start.nOuts(); i++ ) { + Node use = _start.out(i); + if( use instanceof FunNode fun && + fun.nIns()==2 && fun.in(1)==_start && fun != main && !fun.hasPtr() && + (fun._name==null || fun._name.startsWith("sys.")) ) { + add(fun).setDef(1,Parser.XCTRL); + addAll(fun._outputs); + i--; + } + } + _iter.iterate(this); + _tOpto = (int)(System.currentTimeMillis() - t0); // TODO: @@ -219,7 +240,7 @@ public class CodeGen { _phase = Phase.LoopTree; long t0 = System.currentTimeMillis(); // Build the loop tree, fix never-exit loops - _start.buildLoopTree(_stop); + _start.buildLoopTree(_start,_stop); _tLoopTree = (int)(System.currentTimeMillis() - t0); return this; } @@ -247,7 +268,7 @@ public class CodeGen { public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); } public CodeGen instSelect( String cpu, String callingConv, String base ) { assert _phase.ordinal() == Phase.LoopTree.ordinal(); - _phase = Phase.InstSelect; + _phase = Phase.Select; _callingConv = callingConv; @@ -278,14 +299,14 @@ public class CodeGen { _rpcMask = new RegMask(_mach.rpc()); _retMasks[3] = _rpcMask; - // Convert to machine ops long t0 = System.currentTimeMillis(); _uid = 1; // All new machine nodes reset numbering var map = new IdentityHashMap<Node,Node>(); _instSelect( _stop, map ); _stop = ( StopNode)map.get(_stop ); - _start = (StartNode)map.get(_start); + StartNode start = (StartNode)map.get(_start); + _start = start==null ? new StartNode(_start) : start; _instOuts(_stop,visit()); _visit.clear(); _tInsSel = (int)(System.currentTimeMillis() - t0); @@ -310,14 +331,14 @@ public class CodeGen { // Produce a machine node from n; map it to flag as done so stops cycles. map.put(n, x=_mach.instSelect(n) ); + // Stop retains the callable body. Its lifetime edge is not a machine operand. + if( n instanceof FunPtrNode ) x._inputs.pop(); // Walk machine op and replace inputs with mapped inputs for( int i=0; i < x.nIns(); i++ ) x._inputs.set(i, _instSelect(x.in(i),map) ); if( x instanceof MachNode mach ) mach.postSelect(this); // Post selection action - // Updates forward edges only. - n._outputs.clear(); return x; } @@ -340,7 +361,7 @@ public class CodeGen { // Global schedule (code motion) nodes public CodeGen GCM() { - assert _phase.ordinal() <= Phase.InstSelect.ordinal(); + assert _phase.ordinal() <= Phase.Select.ordinal(); _phase = Phase.Schedule; long t0 = System.currentTimeMillis(); @@ -439,8 +460,10 @@ public class CodeGen { String printCFG() { if( _cfg==null ) return "no CFG"; SB sb = new SB(); - for( CFGNode cfg : _cfg ) - IRPrinter.printLine(cfg,sb); + for( CFGNode cfg : _cfg ) { + sb.fix(8,""+(int)cfg._idepth); + IRPrinter.printLine( cfg, sb ); + } return sb.toString(); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index d1d20919..88af3f27 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -274,8 +274,6 @@ public class ElfFile { int start_global = num+1; // Add one to skip the final .rela.text local symbol for( Symbol a: symbols._symbols ) a._index = start_global++; - int bigConIdx = start_global; - start_global += enc._bigCons.size(); // create .text relocations DataSection text_rela = new DataSection(".rela.text", 4 /* SHT_RELA */); @@ -299,10 +297,10 @@ public class ElfFile { // Write relocations for the constant pool for( Encoding.Relo relo : enc._bigCons.values() ) { - Symbol glob = new Symbol("GLOB$"+bigConIdx, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); + Symbol glob = new Symbol("CPOOL$"+start_global, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); glob._value = relo._target; - glob._size = 1 << relo._t.log_size(); - glob._index = bigConIdx++; + glob._size = relo._t.size(); + glob._index = start_global++; symbols.push(glob); write8(text_rela._contents, relo._opStart+relo._off); write8(text_rela._contents, ((long)glob._index << 32L) | relo._elf ); @@ -314,6 +312,7 @@ public class ElfFile { text_rela._info = text._index; pushSection(text_rela); + // Final .rela.text symbol Symbol sym = new Symbol(text_rela._name, num++, SYM_BIND_LOCAL, SYM_TYPE_SECTION); sym._name_pos = text_rela._name_pos; sym._size = text_rela.size(); diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 81f195b1..aad19090 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -50,13 +50,15 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { public final Node _op; public final Type _t; // Constant type public final int _align; // Log alignment, captured for diagnostic display + public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 - public int _target; // Where constant is finally placede + public int _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; - _align = t.log_size(); + _align = t.alignment(); + _structSize = t instanceof TypeStruct ts ? ts.size() : 0; } } public final HashMap<Node,Relo> _bigCons = new HashMap<>(); @@ -142,8 +144,8 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { final HashMap<Node,String> _externals = new HashMap<>(); - public Encoding external( Node call, String extern ) { - _externals.put(call,extern); + public Encoding external( Node n, String extern ) { + _externals.put(n,extern); return this; } @@ -187,12 +189,10 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { Ary<CFGNode> rpo = new Ary<>(CFGNode.class); rpos.put(_code._start.loop(),rpo); BitSet visit = _code.visit(); - //IdentityHashMap<CFGNode,LoopNode> looptail = new IdentityHashMap<>(); rpo.add(_code._stop); for( Node n : _code._start._outputs ) if( n instanceof FunNode fun ) { int x = rpo._len; - //_rpo_cfg2(fun, visit, rpo, looptail); _rpo_cfg(fun, visit, rpos ); assert rpo.at(x) instanceof ReturnNode; } @@ -363,11 +363,6 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { slide = 0; for( int i=0; i<len; i++ ) { CFGNode bb = _code._cfg.at(i); - // Functions pad to align 16 - if( bb instanceof FunNode ) { - int newStart = _opStart[bb._nid]+slide; - slide += (newStart+15 & -16)-newStart; - } _opStart[bb._nid] += slide; // Slide down all other (non-CFG) ops in the block for( Node n : bb._outputs ) @@ -391,6 +386,23 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } + // Go again, inserting padding on function headers. Since no + // short-jumps span function headers, the padding will not make any + // short jumps fail. + for( int i=0; i<len; i++ ) { + CFGNode bb = _code._cfg.at(i); + // Functions pad to align 16 + if( bb instanceof FunNode ) { + int newStart = _opStart[bb._nid]+slide; + slide += (newStart+15 & -16)-newStart; + } + _opStart[bb._nid] += slide; + for( Node n : bb._outputs ) + if( n instanceof MachNode && !(n instanceof CFGNode) ) + _opStart[n._nid] += slide; + } + + // Copy/slide the bits to make space for all the longer branches int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1]; if( grow > 0 ) { // If no short-form ops, nothing to do here @@ -426,31 +438,71 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { void writeConstantPool( BAOS bits, boolean patch ) { padN(16,bits); + // radix sort the big constants by alignment + Ary<Relo>[] raligns = new Ary[5]; + for( Node op : _bigCons.keySet() ) { + Relo relo = _bigCons.get(op); + int align = relo._t.alignment(); + Ary<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>(Relo.class)) : raligns[align]; + relos.add(relo); + } + + + // Types can be used more than once; collapse the dups HashMap<Type,Integer> targets = new HashMap<>(); - // By log size - for( int log = 3; log >= 0; log-- ) { - // Write the 8-byte constants - for( Node op : _bigCons.keySet() ) { - Relo relo = _bigCons.get(op); - if( relo._t.log_size()==log ) { - // Map from relo to constant start and patch - Integer target = targets.get(relo._t); - if( target==null ) { - targets.put(relo._t,target = bits.size()); - // Put constant into code space. - if( relo._t instanceof TypeTuple tt ) // Constant tuples put all entries - for( Type tx : tt._types ) - addN(log,tx,bits); - else - addN(log,relo._t,bits); + // By alignment + for( int align = 4; align >= 0; align-- ) { + Ary<Relo> relos = raligns[align]; + if( relos == null ) continue; + for( Relo relo : relos ) { + // Map from relo to constant start and patch + Integer target = targets.get(relo._t); + if( target==null ) { + targets.put(relo._t,target = bits.size()); + // Write constant into constant pool + switch( relo._t ) { + case TypeTuple tt -> cpool(align,bits,tt); + case TypeStruct ts -> cpool(bits,ts); + // Simple primitive (e.g. larger int, float) + default -> addN(align,relo._t,bits); } - relo._target = target; - relo._opStart= _opStart[op._nid]; - // Go ahead and locally patch in-memory - if( patch ) - ((RIPRelSize)op).patch(this, relo._opStart, _opLen[op._nid], relo._target - relo._opStart); } + // Record target address and opcode start + relo._target = target; + relo._opStart= _opStart[relo._op._nid]; + // Go ahead and locally patch in-memory + if( patch ) + ((RIPRelSize)relo._op).patch(this, relo._opStart, _opLen[relo._op._nid], relo._target - relo._opStart); + } + } + } + + // Constant tuples put all entries at same alignment + private void cpool(int align, BAOS bits, TypeTuple tt) { + for( Type tx : tt._types ) + addN(align,tx,bits); + } + + // Structs use internal field layout + private void cpool( BAOS bits, TypeStruct ts ) { + // Field order by offset + int[] layout = ts.layout(); + int off=0; // offset in the struct + for( int fn=0; fn<ts._fields.length; fn++ ) { + Field f = ts._fields[layout[fn]]; + int foff = ts. offset(layout[fn]); + // Pad up to field + while( off < foff ) { bits.write(0); off++; }; + // Constant array fields are special + if( f._fname=="[]" ) { // Must be a constant array + ts._con.write(bits); // Write the constant array bits + off += ts._con.len(); + } else { + int log = f._type.log_size(); + if( f._fname=="#" ) addN(log,ts._con.len(),bits); // Must be a constant array + else addN(log,f._type ,bits); + off += 1<<log; } } } @@ -459,14 +511,16 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // A series of libc/external calls that Simple can link against in a JIT. // Since no runtime in the JVM process, using magic numbers for the CPU // emulators to pick up on. - public static int SENTINAL_CALLOC = -4; + public static int SENTINEL_CALLOC = -4; + public static int SENTINEL_WRITE = -8; void patchGlobalRelocations() { for( Node src : _externals.keySet() ) { int start = _opStart[src._nid]; String dst = _externals.get(src); int target = switch( dst ) { - case "calloc" -> SENTINAL_CALLOC; + case "calloc" -> SENTINEL_CALLOC; + case "write" -> SENTINEL_WRITE ; default -> throw Utils.TODO(); }; ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start); diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 447a6df1..530336d6 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -32,7 +32,6 @@ public abstract class GlobalCodeMotion { // Post-Order of CFG private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) { - if( use instanceof CallNode call ) call.unlink_all(); if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that if( def instanceof ReturnNode && use instanceof CallEndNode ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bc5fae8d..89850c8c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -409,7 +409,7 @@ abstract public class IFG { int best=sptr; int bestScore = pickRiskyScore(color_stack[best]); for( int i=sptr+1; i<color_stack.length; i++ ) { - if( bestScore == 999999 ) return best; // Already max score + if( bestScore == 1000000 ) return best; // Already max score int iScore = pickRiskyScore(color_stack[i]); if( iScore > bestScore ) { best = i; bestScore = iScore; } @@ -426,13 +426,25 @@ abstract public class IFG { // Picking a live range that is very close to coloring might allow it to // color despite being risky. private static int pickRiskyScore( LRG lrg ) { + // Pick single-def clonables that are not right next to their single-use. + // Failing to color these will clone them closer to their uses. + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { + Node def = (Node)lrg._machDef; + Node use = (Node)lrg._machUse; + CFGNode cfg = def.cfg0(); + if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR + // Same block, but not close + cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) + return 1000000; + } + // Always pick callee-save registers as being very large area recovered // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) - return 999998; + return 1000000-2-lrg._mask.firstReg(); if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 999999; + return 1000000-1; // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost // and "area" for benefit @@ -443,36 +455,39 @@ abstract public class IFG { if( mask.size1() ) return reg; // Check chain of splits up the def-chain. Take first allocated // register, and if it's available in the mask, take it. - Node defSplit = lrg._splitDef, useSplit = lrg._splitUse; - int tidx, cnt=0; + Node def = lrg._splitDef, use = lrg._splitUse; + int tidx=0, cnt=0; - while( (tidx=biasable(defSplit)) != 0 || biasable(useSplit) != 0 ) { + while( def != null || use != null ) { if( cnt++ > 10 ) break; - if( tidx != 0 ) { - short bias = biasColor( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColor( alloc, def, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) defSplit = null; // Kill this side, no more searching - } else defSplit = null; + if( bias == -2 ) def = null; // Kill this side, no more searching + else if( (tidx=biasable(def)) == 0 ) def = null; + } - if( biasable(useSplit) != 0 ) { - short bias = biasColor( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColor( alloc, use, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) useSplit = null; // Kill this side, no more searching - } else useSplit = null; + if( bias == -2 ) use = null; // Kill this side, no more searching + else if( biasable(use)==0 ) use = null; + } - if( defSplit != null ) { - short bias = biasColorNeighbors( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColorNeighbors( alloc, def, mask ); if( bias >= 0 ) return bias; // Advance def side - defSplit = defSplit.in(tidx); - if( alloc.lrg(defSplit)==null ) defSplit=null; + def = def.in(tidx); + if( alloc.lrg(def)==null ) def=null; } - if( useSplit != null ) { - short bias = biasColorNeighbors( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColorNeighbors( alloc, use, mask ); if( bias >= 0 ) return bias; - useSplit = useSplit.out(0); + use = use.out(0); + if( biasable(use)==0 ) use=null; } } @@ -481,7 +496,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode ) return 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java index 2766414f..a95faefc 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.type.TypeInteger; abstract public class Machine { // Human readable machine name. Something like "x86-64" or "arm" or "risc5" @@ -94,4 +95,14 @@ Pre-alloc Post-Alloc SP+48 RPC // registers. public abstract short maxArgSlot(TypeFunPtr tfp); + // Only the declared C result width describes the physical return register. + // Simple functions already return canonical full-width integer values. + protected static TypeInteger cReturn(ProjNode prj) { + if( prj._idx==2 && prj.in(0) instanceof CallEndNode cend && + cend.call().fptr() instanceof ExternNode ext && + ((TypeFunPtr)ext._con).ret() instanceof TypeInteger ret && ret.log_size()<3 ) + return ret; + return null; + } + } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index dd3d2acb..5a641490 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -172,7 +172,7 @@ public class RegAlloc { } // Cache reg masks for New and Call for( CFGNode bb : _code._cfg ) { - if( bb instanceof CallEndNode cend ) cend.cacheRegs(_code); + if( bb instanceof CallEndMach cend ) cend.cacheRegs(_code); for( Node n : bb._outputs ) if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } @@ -467,16 +467,17 @@ public class RegAlloc { if( def._type==Type.TOP ) return; // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); + // Use-side RegMask, if available + RegMask umask = n instanceof MachNode mach ? mach.regmap(i) : null; // Def is a split ? if( skip && def instanceof SplitNode ) { - boolean singleReg = n instanceof MachNode mach && mach.regmap(i)!=null && mach.regmap(i).size1(); + boolean singleReg = umask!=null && umask.size1(); // Same block, multiple registers, split is only used by n, // assume this is good enough and do not split again. if( cfg==def.cfg0() && def.nOuts()==1 && !singleReg ) return; } - RegMask use = n instanceof MachNode mach ? mach.regmap(i) : null; - makeSplit(def,kind,round,lrg,use).insertBefore(n, i); + makeSplit(def,kind,round,lrg,umask).insertBefore(n, i); // Skip split-of-split same block if( skip && def instanceof SplitNode && cfg==def.cfg0() ) n.in(i).setDefOrdered(1,def.in(1)); @@ -523,13 +524,13 @@ public class RegAlloc { private void postColor() { int maxReg = -1; for( CFGNode bb : _code._cfg ) { // For all ops - if( bb instanceof FunNode fun ) + if( bb instanceof FunNode ) maxReg = -1; // Reset for new function // Compute frame size, based on arguments and largest reg seen if( bb instanceof ReturnNode ret ) ret.fun().computeFrameAdjust(_code,maxReg); // Raise frame size by max stack args passed, even if ignored - if( bb instanceof CallEndNode cend ) + if( bb instanceof CallEndMach cend ) maxReg = Math.max(maxReg,cend._xslot); for( int j=0; j<bb.nOuts(); j++ ) { diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 62b33ada..3a5528ef 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,41 +1,27 @@ package com.seaofnodes.simple.node; - import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; +import java.util.BitSet; import static com.seaofnodes.simple.Parser.con; -public class AddNode extends Node { +public class AddNode extends ArithNode { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Add"; } - - @Override protected String format() { return "(%1+%2)"; } - - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i1 && - t2 instanceof TypeInteger i2 ) { - if (i1.isConstant() && i2.isConstant()) - return TypeInteger.constant(i1.value()+i2.value()); - // Fold ranges like {0-1} + {2-3} into {2-4}. - if( !overflow(i1._min,i2._min) && - !overflow(i1._max,i2._max) ) - return TypeInteger.make(i1._min+i2._min,i1._max+i2._max); - } + @Override public String op() { return "+"; } + + @Override long doOp( long x, long y ) { return x + y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { + // Fold ranges like {0-1} + {2-3} into {2-4}. + if( !overflow(x._min,y._min) && + !overflow(x._max,y._max) ) + return TypeInteger.make(x._min+y._min,x._max+y._max); return TypeInteger.BOT; } - static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow - return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow - } @Override public Node idealize () { Node lhs = in(1); @@ -106,7 +92,7 @@ public class AddNode extends Node { if( spine_cmp(lhs.in(2),rhs,this) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); - return null; + return super.idealize(); } // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or, Xor. @@ -183,10 +169,4 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } - @Override public Parser.ParseException err() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; - if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(1)._type,null); - if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(2)._type,null); - return null; - } } diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index b425a6ce..9957472b 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -4,28 +4,16 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; - -public class AndNode extends LogicalNode { +public class AndNode extends ArithNode { public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "And"; } @Override public String op() { return "&"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()&i1.value()); - // Sharpen allowed bits if either value is narrowed - long mask = i0.mask() & i1.mask(); - return mask < 0 ? TypeInteger.BOT : TypeInteger.make(0,mask); - } - return TypeInteger.BOT; + @Override long doOp( long x, long y ) { return x & y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { + // Sharpen allowed bits if either value is narrowed + long mask = x.mask() & y.mask(); + return mask < 0 ? TypeInteger.BOT : TypeInteger.make(0,mask); } @Override @@ -51,9 +39,10 @@ public class AndNode extends LogicalNode { // 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; + if( phicon!=null ) + return phicon; - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new AndNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java new file mode 100644 index 00000000..e94ccbc6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -0,0 +1,95 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public abstract class ArithNode extends Node { + // Source location for late reported errors + Parser.Lexer _loc; + + public ArithNode( Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } + abstract String op(); + + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + return p.open().n(in(1)).p(op()).n(in(2)).close(); + } + + abstract long doOp(long x, long y); + abstract TypeInteger doOp(TypeInteger x, TypeInteger y); + + // Generic airthmetic op math: high returns high; low returns low; 2 + // constants fold; only 2 non-constants call specialized math. + @Override + public final TypeInteger compute() { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger x && + t2 instanceof TypeInteger y ) + return x.isConstant() && y.isConstant() + ? con(x,y) + : doOp(x,y); + return TypeInteger.BOT; + } + + private TypeInteger con( Type t1, Type t2 ) { + return TypeInteger.constant( doOp( ((TypeInteger)t1).value(), ((TypeInteger)t2).value()) ); + } + + // Check for "op(Phi(con,x),Phi(con,y))" and push-up through the Phi. + // Note that this is the exact reverse of Phi pulling a common op down + // to reduce total op-count. We don't get in an endless push-up + // push-down peephole cycle because the constants all fold first. + // Returns "Phi(op(con,con),op(x,y))". + + // This check is slightly different from the + + // Expected to be called after other ideal checks are done. + @Override public Node idealize() { + if( in(1) instanceof PhiNode lhs && + in(2) instanceof PhiNode rhs && + lhs.nIns() >= 2 && !lhs.inProgress() && + lhs.region()==rhs.region() ) { + // Profit check: only 1 instance of `this` will remain, all the + // others will fold to constants. + int cnt=0; + for( int i=1; i<lhs.nIns(); i++ ) + if( isCon(lhs,rhs,i) ) + cnt++; + if( lhs.nIns()-1 - cnt <= 1 ) { + // Profit! Push up-phi and fold + Node[] ns = new Node[lhs.nIns()]; + ns[0] = lhs.in(0); + for( int i=1; i<lhs.nIns(); i++ ) { + ns[i] = isCon(lhs,rhs,i) + ? new ConstantNode(con(lhs.in(i)._type, rhs.in(i)._type)).peephole() + : copy(lhs.in(i), rhs.in(i)).peephole(); + } + String label = lhs._label==rhs._label ? lhs._label : lhs._label + rhs._label; + return new PhiNode(label,lhs._declaredType,ns).peephole(); + } + } + return null; + } + + static boolean isCon( PhiNode lhs, PhiNode rhs, int i ) { + return lhs.in(i)._type.isConstant() && rhs.in(i)._type.isConstant(); + } + + + static boolean overflow( long x, long y ) { + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow + } + + @Override public Parser.ParseException err() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; + if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(1)._type,_loc); + if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(2)._type,_loc); + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index d6a126f5..21ac59d3 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -123,9 +123,24 @@ abstract public class BoolNode extends Node { Node copyF() { return new LEF(null,null); } } - public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } public boolean isFloat() { return true; } } - public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } public boolean isFloat() { return true; } } - public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } public boolean isFloat() { return true; } } + public static class EQF extends EQ { + public EQF(Node lhs, Node rhs) { super(lhs,rhs); } + @Override boolean doOp(double lhs, double rhs) { return lhs == rhs; } + @Override public boolean isFloat() { return true; } + @Override Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } + } + public static class LTF extends LT { + public LTF(Node lhs, Node rhs) { super(lhs,rhs); } + @Override boolean doOp(double lhs, double rhs) { return lhs < rhs; } + @Override public boolean isFloat() { return true; } + @Override Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } + } + public static class LEF extends LE { + public LEF(Node lhs, Node rhs) { super(lhs,rhs); } + @Override boolean doOp(double lhs, double rhs) { return lhs <= rhs; } + @Override public boolean isFloat() { return true; } + @Override Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } + } // Unsigned less that, for range checks. Not directly user writable. public static class ULT extends BoolNode { diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 47dfa311..4f346ee3 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -133,7 +133,19 @@ public abstract class CFGNode extends Node { // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves // also refer to *their* containing LoopNode, as well as have their depth. // Start contains the function bodies at depth 0; real loops add depth. - public void buildLoopTree(StopNode stop) { + public void buildLoopTree(StartNode start, StopNode stop) { + // Unlink all linked calls. This can remove RPC constants which + // shuffled the StartNode outputs so requires a while loop. + boolean done=false; + while(!done) { + done = true; + for( Node use : start._outputs ) + if( use instanceof FunNode fun ) + for( Node c : fun._inputs ) + if( c instanceof CallNode call ) + { call.unlink_all(); done=false; } + } + _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); _bltWalk(2,null,stop, new BitSet()); } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndMach.java b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java new file mode 100644 index 00000000..47cab07a --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.codegen.*; + +public class CallEndMach extends CallEndNode implements MachNode { + public CallEndMach( CallEndNode n ) { super(n); } + // MachNode specifics, shared across all CPUs + public int _xslot; + private RegMask _retMask; + private RegMask _kills; + public void cacheRegs(CodeGen code) { + // Return mask depends on TFP (either GPR or FPR) + _retMask = code._mach.retMask(call().tfp()); + // Kill mask is all caller-saves, and any mirror stack slots for args + // in registers. + RegMaskRW kills = code._callerSave.copy(); + // Start of stack slots + int maxReg = code._mach.regs().length; + // Incoming function arg slots, all low numbered in the RA + int fslot = fun()._maxArgSlot; + // Killed slots for this calls outgoing args + int xslot = code._mach.maxArgSlot(call().tfp()); + _xslot = (maxReg+fslot)+xslot; + for( int i=0; i<xslot; i++ ) + kills.set((maxReg+fslot)+i); + _kills = kills; + } + public String op() { return "cend"; } + public RegMask regmap(int i) { return null; } + public RegMask outregmap() { return null; } + public RegMask outregmap(int idx) { return idx==2 ? _retMask : null; } + public RegMask killmap() { return _kills; } + public void encoding( Encoding enc ) { } + public void asm(CodeGen code, SB sb) { } +} diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 47e80ca9..94f5ee49 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -24,6 +24,11 @@ public class CallEndNode extends CFGNode implements MultiNode { public CallNode call() { return (CallNode)in(0); } + @Override public CFGNode idom(Node dep) { + // Folding the idom is the one inlining Return + return _folding ? cfg(1) : super.idom(dep); + } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { p.p("cend( "); @@ -38,7 +43,6 @@ public class CallEndNode extends CFGNode implements MultiNode { if( !(in(0) instanceof CallNode call) ) return TypeTuple.RET.dual(); Type ret = Type.BOTTOM; - TypeMem mem = TypeMem.BOT; if( addDep(call.fptr())._type instanceof TypeFunPtr tfp ) { ret = tfp.ret(); // Here, if I can figure out I've found *all* callers, then I can meet @@ -71,10 +75,10 @@ public class CallEndNode extends CFGNode implements MultiNode { assert fun.in(1) instanceof StartNode && fun.in(2)==call; // Disallow self-recursive inlining (loop unrolling by another name) CFGNode idom = call; - while( !(idom instanceof FunNode) ) + while( idom!=null && !(idom instanceof FunNode) ) idom = idom.idom(); // Inline? - if( idom != fun ) { + if( idom != null && idom != fun ) { // Trivial inline: rewrite _folding = true; // Rewrite Fun so the normal RegionNode ideal collapses @@ -196,33 +200,4 @@ public class CallEndNode extends CFGNode implements MultiNode { return _folding ? in(1).in(idx) : null; } - // ------------ - // MachNode specifics, shared across all CPUs - public int _xslot; - private RegMask _retMask; - private RegMask _kills; - public void cacheRegs(CodeGen code) { - // Return mask depends on TFP (either GPR or FPR) - _retMask = code._mach.retMask(call().tfp()); - // Kill mask is all caller-saves, and any mirror stack slots for args - // in registers. - RegMaskRW kills = code._callerSave.copy(); - // Start of stack slots - int maxReg = code._mach.regs().length; - // Incoming function arg slots, all low numbered in the RA - int fslot = fun()._maxArgSlot; - // Killed slots for this calls outgoing args - int xslot = code._mach.maxArgSlot(call().tfp()); - _xslot = (maxReg+fslot)+xslot; - for( int i=0; i<xslot; i++ ) - kills.set((maxReg+fslot)+i); - _kills = kills; - } - public String op() { return "cend"; } - public RegMask regmap(int i) { return null; } - public RegMask outregmap() { return null; } - public RegMask outregmap(int idx) { return idx==2 ? _retMask : null; } - public RegMask killmap() { return _kills; } - public void encoding( Encoding enc ) { } - public void asm(CodeGen code, SB sb) { } } diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 70c71d43..3bf873fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -34,7 +34,8 @@ public class CallNode extends CFGNode { public String name() { if( fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { FunNode fun = CodeGen.CODE.link(tfp); - return fun==null ? null : fun._name; + if( fun !=null ) return fun._name; + if( fptr() instanceof ExternNode ex ) return ex._extern; } return null; } @@ -164,6 +165,9 @@ public class CallNode extends CFGNode { if( !arg(i+2)._type.isa(tfp.arg(i)) || !arg(i+2)._type.accessISA(tfp.arg(i)) ) return Parser.error( "Argument #"+i+" isa "+arg(i+2)._type+", but must be a "+tfp.arg(i), _loc); + if( tfp.fidxs() < 0 ) + throw Utils.TODO(); // Infinite unknown TFPs? Should be fairly precise CG + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CastARM.java b/src/main/java/com/seaofnodes/simple/node/CastMach.java index a5a4e112..92822433 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CastARM.java +++ b/src/main/java/com/seaofnodes/simple/node/CastMach.java @@ -1,18 +1,19 @@ -package com.seaofnodes.simple.node.cpus.arm; +package com.seaofnodes.simple.node; import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; -import com.seaofnodes.simple.node.CastNode; -import com.seaofnodes.simple.node.MachNode; -public class CastARM extends CastNode implements MachNode { - public CastARM( CastNode cast ) { super(cast); } +/** + * Cast a pointer to read-only + */ +public class CastMach extends CastNode implements MachNode { + public CastMach( CastNode n ) { super(n); } @Override public String op() { return label(); } @Override public RegMask regmap(int i) { assert i==1; return RegMask.FULL; } @Override public RegMask outregmap() { return RegMask.FULL; } @Override public int twoAddress( ) { return 1; } @Override public void encoding( Encoding enc ) { } - @Override public void asm(CodeGen code, SB sb) { _t.print(sb.p(code.reg(in(1))).p(" isa ")); } + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(in(1))); } } diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index 5598acd8..8ae7b327 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -6,6 +6,8 @@ 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.TypeMemPtr; + // Upcast (join) the input to a t. Used after guard test to lift an input. // Can also be used to make a type-assertion if ctrl is null. @@ -34,6 +36,9 @@ public class CastNode extends Node { @Override public Type compute() { + // Cast array to int + if( _t == TypeInteger.BOT && in(1)._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) + return _t; return in(1)._type.join(_t); } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index c4a41e5d..d3ac24a7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -33,6 +33,10 @@ public class ConstantNode extends Node { public static Node make( Type type ) { if( type==Type. CONTROL ) return new CtrlNode(); if( type==Type.XCONTROL ) return new XCtrlNode(); + if( type instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.notNull() ) { + FunNode fun = CodeGen.CODE.link(tfp); + if( fun!=null && !fun.isDead() ) return new FunPtrNode(tfp,fun.ret()); + } return new ConstantNode(type); } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 70631c0a..7b5ae16c 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -1,28 +1,17 @@ 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 { +public class DivNode extends ArithNode { public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Div"; } + @Override public String op() { return "//"; } - @Override protected String format() { return "(%1/%2)"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i1 && - t2 instanceof TypeInteger i2 ) { - if (i1.isConstant() && i2.isConstant()) - return i2.value() == 0 - ? TypeInteger.ZERO - : TypeInteger.constant(i1.value()/i2.value()); - } + @Override long doOp( long x, long y ) { return y==0 ? 0 : x / y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; } @@ -31,7 +20,7 @@ public class DivNode extends Node { // Div of 1. if( in(2)._type == TypeInteger.TRUE && in(1)._type instanceof TypeInteger ) return in(1); - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/src/main/java/com/seaofnodes/simple/node/ExternNode.java new file mode 100644 index 00000000..093cc2cb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -0,0 +1,21 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.util.BitSet; + +/** + A constant with external linkage. + */ + +public class ExternNode extends ConstantNode { + public final String _extern; + public ExternNode(Type t, String ex) { super(t); _extern = ex; } + + @Override public String label() { return "#"+_con+":"+_extern; } + + @Override public boolean eq(Node n) { return this==n; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index eb1e8259..5f67f859 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -22,7 +22,7 @@ public class FunNode extends RegionNode { public String _name; // Debug name - public FunNode( Parser.Lexer loc, TypeFunPtr sig, Node... nodes ) { super(loc,nodes); _sig = sig; } + public FunNode( Parser.Lexer loc, TypeFunPtr sig, String name, Node... nodes ) { super(loc,nodes); _name=name; _sig = sig; } public FunNode( FunNode fun ) { super( fun, fun==null ? null : fun._loc ); if( fun!=null ) { @@ -60,6 +60,16 @@ public class FunNode extends RegionNode { public void setRet(ReturnNode ret) { _ret=ret; } public ReturnNode ret() { assert _ret!=null; return _ret; } + // Direct calls are known; any other use of an address may have unknown callers. + public boolean hasPtr() { + for( Node use : ret()._outputs ) + if( use instanceof FunPtrNode ) + for( Node user : use._outputs ) + if( !(user instanceof CallNode call) || call.fptr()!=use || + call._inputs.find(use)!=call.nIns()-1 ) return true; + return false; + } + // Signature can improve over time public TypeFunPtr sig() { return _sig; } public void setSig( TypeFunPtr sig ) { @@ -70,10 +80,17 @@ public class FunNode extends RegionNode { } } + public void setName( String name ) { + if( _name==null ) _name=name; + else _name += "."+name; + } + @Override public Type compute() { // Only dead if no callers after SCCP - return Type.CONTROL; + if( unknownCallers() ) + return Type.CONTROL; + return super.compute(); } @Override @@ -117,10 +134,10 @@ public class FunNode extends RegionNode { // unless folding then just a ID on input#1 @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start - @Override public CFGNode idom(Node dep) { return cfg(1); } + @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : cfg(1); } // Always in-progress until we run out of unknown callers - public boolean unknownCallers() { return in(1) instanceof StartNode; } + public boolean unknownCallers() { return nIns()<2 || in(1) instanceof StartNode; } @Override public boolean inProgress() { return unknownCallers(); } diff --git a/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java new file mode 100644 index 00000000..43242c32 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java @@ -0,0 +1,12 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.TypeFunPtr; + +// A function address keeps its body alive, even without a linked Call. +public class FunPtrNode extends ConstantNode { + public FunPtrNode(TypeFunPtr tfp, ReturnNode ret) { + super(tfp); + addDef(ret); + } + public ReturnNode ret() { return (ReturnNode)in(1); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LogicalNode.java b/src/main/java/com/seaofnodes/simple/node/LogicalNode.java deleted file mode 100644 index 6ac16d31..00000000 --- a/src/main/java/com/seaofnodes/simple/node/LogicalNode.java +++ /dev/null @@ -1,27 +0,0 @@ -package com.seaofnodes.simple.node; - -import com.seaofnodes.print.ExprPrinter; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeInteger; - -public abstract class LogicalNode extends Node { - // Source location for late reported errors - Parser.Lexer _loc; - - public LogicalNode(Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } - abstract String op(); - - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { - return p.open().n(in(1)).p(op()).n(in(2)).close(); - } - - - @Override public Parser.ParseException err() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; - if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(1)._type,_loc); - if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+op()+"' " + in(2)._type,_loc); - return null; - } -} diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index f86d7518..265132dc 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,7 +26,7 @@ public class LoopNode extends RegionNode { } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index adfc80a5..db667e6d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -78,7 +78,6 @@ public abstract class MemOpNode extends Node { _declaredType = Type.BOTTOM; } - // static String mlabel(String name) { return "[]".equals(name) ? "ary" : ("#".equals(name) ? "len" : name); } String mlabel() { return mlabel(_name); } @@ -90,7 +89,7 @@ public abstract class MemOpNode extends Node { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return _printMach(p); } protected ExprPrinter<Node> _printMach(ExprPrinter<Node> p) { throw Utils.TODO(); } - + public int log_size() { return _declaredType.log_size(); } // Extra conditions for factoring matching memory operations through a Phi. // The caller has already checked the opcode, input shape and control. diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 66e26163..cd67b8fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -17,7 +17,7 @@ public class MinusNode extends Node { public Type compute() { 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) ) + i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE ) return TypeInteger.make(-i0._max,-i0._min); return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index ac97725c..6e1dc053 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,29 +1,18 @@ 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 MulNode extends Node { +public class MulNode extends ArithNode { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Mul"; } + @Override public String op() { return "*"; } - @Override protected String format() { return "(%1*%2)"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i1 && - t2 instanceof TypeInteger i2 ) { - if( i1==TypeInteger.ZERO || i2==TypeInteger.ZERO) - return TypeInteger.ZERO; - if (i1.isConstant() && i2.isConstant()) - return TypeInteger.constant(i1.value()*i2.value()); - } + @Override long doOp( long x, long y ) { return x * y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; } @@ -67,14 +56,8 @@ public class MulNode extends Node { Node phicon = AddNode.phiCon(this,true); if( phicon!=null ) return phicon; - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } - @Override public Parser.ParseException err() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; - if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(1)._type.glb(),null); - if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(2)._type.glb(),null); - return null; - } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 8b0647d0..fff1ab14 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -37,7 +37,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public Ary<Node> _outputs; + public Ary<Node> _outputs; /** * Current computed type for this Node. This value changes as the graph @@ -59,7 +59,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // Used by any pass rewriting all Node classes but not the edges. Node( Node n ) { super(CODE.getUID()); // allocate unique dense ID - assert CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.InstSelect.ordinal(); + assert CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Select.ordinal(); _inputs = new Ary<>(n==null ? new Node[0] : n._inputs.asAry()); _outputs = new Ary<>(Node.class); _type = n==null ? Type.BOTTOM : n._type; @@ -188,7 +188,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { // Shortcut for "popping" until n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. - void popUntil(int n) { + public void popUntil(int n) { unlock(); while( nIns() > n ) { Node old_def = _inputs.pop(); @@ -204,9 +204,9 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { * code elimination. */ public void kill( ) { + assert isUnused(); // Has no uses, so it is dead unlock(); moveDepsToWorklist(); - assert isUnused(); // Has no uses, so it is dead _type=null; // Flag as dead while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes Node old_def = _inputs.removeLast(); @@ -241,6 +241,10 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { if( unkeep().isUnused() ) kill(); } + public void isKill() { + if( isUnused() ) + kill(); + } // Replace self with nnn in the graph, making 'this' go dead public void subsume( Node nnn ) { diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 1cd8bafc..d16dd194 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -4,24 +4,13 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; -import java.util.BitSet; - -public class OrNode extends LogicalNode { +public class OrNode extends ArithNode { public OrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "Or"; } @Override public String op() { return "|"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()|i1.value()); - } + @Override long doOp( long x, long y ) { return x | y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; } @@ -47,7 +36,7 @@ public class OrNode extends LogicalNode { Node phicon = AddNode.phiCon(this,true); if( phicon!=null ) return phicon; - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new OrNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index c3a0cf21..3e8e3711 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -38,4 +38,8 @@ public class ParmNode extends PhiNode { // Always in-progress until we run out of unknown callers @Override public boolean inProgress() { return fun().inProgress(); } + + @Override public boolean eq( Node n ) { + return ((ParmNode)n)._idx==_idx && super.eq(n); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index e075ea5c..8aa123f7 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -50,7 +50,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.glb().dual();//Type.TOP; + Type t = _declaredType.glb(false).dual();//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. @@ -167,7 +167,7 @@ public class PhiNode extends Node { } PhiNode phi = j==1 && op instanceof MemOpNode mem ? new MemPhiNode(_label,mem._alias,ins) - : PhiNode.make(_label,t.glb(),ins); + : PhiNode.make(_label,t.glb(false),ins); x = phi.peephole(); } cp.addDef(x); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CastRISC.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyMach.java index c404aaa5..86d17f9b 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CastRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyMach.java @@ -1,18 +1,19 @@ -package com.seaofnodes.simple.node.cpus.riscv; +package com.seaofnodes.simple.node; import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; -import com.seaofnodes.simple.node.CastNode; -import com.seaofnodes.simple.node.MachNode; -public class CastRISC extends CastNode implements MachNode { - public CastRISC( CastNode cast ) { super(cast); } +/** + * Cast a pointer to read-only + */ +public class ReadOnlyMach extends ReadOnlyNode implements MachNode { + public ReadOnlyMach( ReadOnlyNode n ) { super(n); } @Override public String op() { return label(); } @Override public RegMask regmap(int i) { assert i==1; return RegMask.FULL; } @Override public RegMask outregmap() { return RegMask.FULL; } @Override public int twoAddress( ) { return 1; } @Override public void encoding( Encoding enc ) { } - @Override public void asm(CodeGen code, SB sb) { _t.print(sb.p(code.reg(in(1))).p(" isa ")); } + @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(in(1))); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java index d79f2815..94c1b6f6 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -4,7 +4,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; - /** * Cast a pointer to read-only */ @@ -24,4 +23,5 @@ public class ReadOnlyNode extends Node { return in(1); return null; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index d321da42..429be229 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -3,29 +3,17 @@ 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 SarNode extends LogicalNode { +public class SarNode extends ArithNode { public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "Sar"; } @Override public String op() { return ">>"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1) { - if( i0 == TypeInteger.ZERO ) - return TypeInteger.ZERO; - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()>>i1.value()); - if( i1.isConstant() ) { - int log = (int)i1.value(); - return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); - } + @Override long doOp( long x, long y ) { return x >> y; } + @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { + if( y.isConstant() ) { + int log = (int)y.value(); + return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); } return TypeInteger.BOT; } @@ -42,7 +30,7 @@ public class SarNode extends LogicalNode { // TODO: x >> 3 >> (y ? 1 : 2) ==> x >> (y ? 4 : 5) - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new SarNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8d3e3089..44f0bc05 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -32,7 +32,10 @@ public class ScopeNode extends Node { // Size of each nested lexical scope public final Ary<Integer> _lexSize; - // Lexical scope is one of normal Block, constructor or function + // Lexical scope is typed: + // - Block scope - basic block scoping + // - Constructor - struct type is defined, and here we give values to all fields + // - Function - out-of-scope lookups restricted to final constants public enum Kind { Block, Constructor, Function }; public final Ary<Kind> _kinds; @@ -56,7 +59,7 @@ public class ScopeNode extends Node { int j=1; for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { p.p("| "); j++; } - Var v = _vars.get(i); + Var v = _vars.at(i); p.p(v._type().print(new SB())); p.p(" "); if( v._final ) p.p("!"); @@ -76,6 +79,7 @@ public class ScopeNode extends Node { public Node ctrl() { return in(0); } public Node mem() { return in(lookup(MEM0)); } + public Var var(int i) { return _vars.at(i); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -90,7 +94,7 @@ public class ScopeNode extends Node { public <N extends Node> N ctrl(N n) { return setDef(0,n); } public Node mem(Node n) { update(MEM0,n); return n; } - public void push(Kind kind) { + public void push( Kind kind ) { assert _lexSize._len==_kinds._len; _lexSize.push(_vars.size()); _kinds .push(kind); @@ -99,11 +103,11 @@ public class ScopeNode extends Node { // Pop a lexical scope public void pop() { assert _lexSize._len==_kinds._len; - promote(); + promote(); // Promote forward references to the next outer scope int n = _lexSize.pop(); _kinds.pop(); - popUntil(n); - _vars.setLen(n); + popUntil(n); // Pop off inputs going out of scope + _vars.setLen(n); // Pop off variables going out of scope } @@ -112,7 +116,7 @@ public class ScopeNode extends Node { public void promote() { int n = _lexSize.last(); for( int i=n; i<nIns(); i++ ) { - Var v = _vars.at(i); + Var v = var(i); if( !v.isFRef() ) continue; if( _lexSize._len==1 ) throw Parser.error("Undefined name '" + v._name + "'",v._loc); @@ -134,7 +138,7 @@ public class ScopeNode extends Node { return false; } - public boolean inCon() { return _kinds.last() == Kind.Constructor; } + public boolean inConstructor() { return _kinds.last() == Kind.Constructor; } // Is v outside any current function scope? public boolean outOfFunction( Var v ) { @@ -148,9 +152,9 @@ public class ScopeNode extends Node { // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan // typically hits many dozens of variables. - int find( String name ) { + public int find( String name ) { for( int i=_vars.size()-1; i>=0; i-- ) - if( _vars.at(i)._name.equals(name) ) + if( var(i)._name.equals(name) ) return i; return -1; } @@ -162,7 +166,7 @@ public class ScopeNode extends Node { assert _lexSize.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory if( _lexSize._len > 0 ) for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) { - Var n = _vars.at(i); + Var n = var(i); if( n._name.equals(name) ) { if( !n.isFRef() ) return false; // Double define FRefNode fref = (FRefNode)in(n._idx); // Get forward ref @@ -189,11 +193,11 @@ public class ScopeNode extends Node { public Var lookup( String name ) { int idx = find(name); // -1 is missed in all scopes, not found - return idx == -1 ? null : update(_vars.at(idx),null); + return idx == -1 ? null : update(var(idx),null); } /** - * If the name is present in any scope, then redefine else null + * Redefine an existing name * * @param name Name being redefined * @param n The node to bind to the name @@ -201,7 +205,7 @@ public class ScopeNode extends Node { public void update( String name, Node n ) { int idx = find(name); assert idx>=0; - update(_vars.at(idx),n); + update(var(idx),n); } public Var update( Var v, Node st ) { @@ -215,7 +219,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,PhiNode.make(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v.type(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } assert !v._final || st==null || canInit(v); @@ -281,7 +285,7 @@ public class ScopeNode extends Node { if( in(i) != that.in(i) ) { // No need for redundant Phis // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation - Var v = _vars.at(i); + Var v = var(i); Node lhs = this.in(this.update(v,null)); Node rhs = that.in(that.update(v,null)); setDef(i, PhiNode.make(v._name, v.type(), r, lhs, rhs).peephole()); @@ -292,7 +296,7 @@ public class ScopeNode extends Node { // Forward refs are copied to the other side, "as if" they were there all along. public void balanceIf( ScopeNode scope ) { for( int i = nIns(); i < scope.nIns(); i++ ) { - Var n = scope._vars.at(i); + Var n = scope.var(i); if( n.isFRef() ) { // RHS has forward refs _vars.add(n); // Copy to LHS addDef(scope.in(i)); diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index afd20062..e2951784 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -3,25 +3,22 @@ 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 ShlNode extends LogicalNode { +public class ShlNode extends ArithNode { public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "Shl"; } @Override public String op() { return "<<"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if( i0 == TypeInteger.ZERO ) - return TypeInteger.ZERO; - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()<<i1.value()); + @Override long doOp( long x, long y ) { return x << y; } + @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { + if( x == TypeInteger.ZERO ) + return TypeInteger.ZERO; + if( y.isConstant() ) { + int shf = (int)y.value(); + // If no overflow, shift endpoints + if( !(((x._min<<shf)>>shf) != x._min || + ((x._max<<shf)>>shf) != x._max ) ) + return TypeInteger.make(x._min<<shf,x._max<<shf); } return TypeInteger.BOT; } @@ -45,7 +42,7 @@ public class ShlNode extends LogicalNode { // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5) - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new ShlNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 587e1631..0023431f 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -3,27 +3,15 @@ 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 ShrNode extends LogicalNode { +public class ShrNode extends ArithNode { public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "Shr"; } @Override public String op() { return ">>>"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if (t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if( i0 == TypeInteger.ZERO ) - return TypeInteger.ZERO; - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()>>>i1.value()); - } - return TypeInteger.BOT; + @Override long doOp( long x, long y ) { return x >>> y; } + @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { + return x == TypeInteger.ZERO ? x : TypeInteger.BOT; } @Override @@ -38,7 +26,7 @@ public class ShrNode extends LogicalNode { // TODO: x >>> 3 >>> (y ? 1 : 2) ==> x >>> (y ? 4 : 5) - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new ShrNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index c88dbf51..298c24a9 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -24,11 +24,15 @@ public class StopNode extends CFGNode { @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { // For the sake of many old tests, and single value prints as "return val" - if( ret()!=null ) return p.n(ret()); + ReturnNode ret1 = ret(); + if( ret1!=null ) return p.n(ret1); p.p("Stop[ "); for( Node ret : _inputs ) - if( ret!=null ) - p.n(ret).p(" "); + if( ret!=null ) { + String name = ((ReturnNode)ret).fun()._name; + if( name== null || !name.startsWith("sys.") ) + p.n(ret).p(" "); + } return p.p("]"); } @@ -38,7 +42,13 @@ public class StopNode extends CFGNode { // If a single Return, return it. // Otherwise, null because ambiguous. public ReturnNode ret() { - return nIns()==1 && in(0) instanceof ReturnNode ret ? ret : null; + Node ret1 = this; + for( Node ret : _inputs ) { + String name = ((ReturnNode)ret).fun()._name; + if( name==null || !name.startsWith("sys.") ) + ret1 = ret1==this ? ((ReturnNode)ret) : null; + } + return ret1==this ? null : (ReturnNode)ret1; } @Override @@ -50,7 +60,7 @@ public class StopNode extends CFGNode { public Node idealize() { int len = nIns(); for( int i=0; i<nIns(); i++ ) - if( ((ReturnNode)in(i)).fun().isDead() ) + if( addDep(((ReturnNode)in(i)).fun()).isDead() ) delDef(i--); if( len != nIns() ) return this; return null; diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a5b09663..ecda014b 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -85,12 +85,23 @@ public class StoreNode extends MemOpNode { } } - // Store of zero after alloc - if( mem() instanceof ProjNode prj && prj.in(0) instanceof NewNode && - prj.in(0)==ptr().in(0) && // Same NewNode memory & pointer - (val()._type==TypeInteger.ZERO || val()._type==Type.NIL ) ) - return mem(); - + // Store will chop high order bits off; math to change those bits can be dropped. + if( val() instanceof SarNode shr && + shr.in(1) instanceof ShlNode shl && + shr.in(2)._type.isConstant() && + shl.in(2)._type.isConstant() ) { + TypeInteger shrC = (TypeInteger) shr.in(2)._type; + + // size of the thing that sign-extends + int base_size = (1 << shr.in(1)._type.log_size()) << 3; + int not_affected_bits = base_size - (int) shrC.value(); + int store_size = (1 << log_size()) << 3; + // if the store is unrelated to the shift amount, then get rid of the shift + if( shl.in(2)._type == shr.in(2)._type && shrC.value() >= store_size && not_affected_bits >= store_size) { + setDef(4, shl.in(1)); + return this; + } + } return null; } @@ -154,8 +165,6 @@ public class StoreNode extends MemOpNode { TypeMemPtr tmp = (TypeMemPtr)ptr()._type; if( (tmp._ro || tmp._obj.field(_name)._final) && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); - //Type t = val()._type; - //return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 9bf6d83e..2c4fed39 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -1,35 +1,26 @@ 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 { +public class SubNode extends ArithNode { public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Sub"; } + @Override public String op() { return "-"; } - @Override protected String format() { return "(%1-%2)"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; + @Override long doOp( long x, long y ) { return x - y; } + @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { // 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()) - return TypeInteger.constant(i1.value()-i2.value()); - // Fold ranges like {2-3} - {0-1} into {1-3}. - if( !AddNode.overflow(i1._min,-i2._max) && - !AddNode.overflow(i1._max,-i2._min) && - i2._min != Long.MIN_VALUE ) - return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); - } + // Fold ranges like {2-3} - {0-1} into {1-3}. + if( !AddNode.overflow(x._min,-y._max) && + !AddNode.overflow(x._max,-y._min) && + y._min != Long.MIN_VALUE ) + return TypeInteger.make(x._min-y._max,x._max-y._min); return TypeInteger.BOT; } @@ -55,7 +46,7 @@ public class SubNode extends Node { if( lhs instanceof MinusNode minus ) return new MinusNode(new AddNode(minus.in(1),rhs).peephole()); - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 034e352a..75cea98e 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -3,24 +3,14 @@ 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 XorNode extends LogicalNode { +public class XorNode extends ArithNode { public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs); } @Override public String label() { return "Xor"; } @Override public String op() { return "^"; } - - @Override - public Type compute() { - Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) - return TypeInteger.TOP; - if( t1 instanceof TypeInteger i0 && - t2 instanceof TypeInteger i1 ) { - if( i0.isConstant() && i1.isConstant() ) - return TypeInteger.constant(i0.value()^i1.value()); - } + @Override long doOp( long x, long y ) { return x ^ y; } + @Override TypeInteger doOp( TypeInteger x, TypeInteger y ) { return TypeInteger.BOT; } @@ -46,7 +36,7 @@ public class XorNode extends LogicalNode { Node phicon = AddNode.phiCon(this,true); if( phicon!=null ) return phicon; - return null; + return super.idealize(); } @Override Node copy(Node lhs, Node rhs) { return new XorNode(_loc,lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java index 57d7ef7c..dd2d9e2c 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java @@ -9,13 +9,13 @@ import com.seaofnodes.simple.type.TypeFunPtr; public class CallARM extends CallNode implements MachNode, RIPRelSize { final TypeFunPtr _tfp; final String _name; - CallARM(CallNode call, TypeFunPtr tfp) { super(call); _inputs.pop(); // Pop constant target assert tfp.isConstant(); _tfp = tfp; - _name = CodeGen.CODE.link(tfp)._name; + FunNode fun = CodeGen.CODE.link(tfp); + _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls } @Override public String op() { return "call"; } @@ -24,9 +24,12 @@ public class CallARM extends CallNode implements MachNode, RIPRelSize { @Override public TypeFunPtr tfp() { return _tfp; } @Override public RegMask regmap(int i) { return arm.callInMask(_tfp,i,fun()._maxArgSlot); } @Override public RegMask outregmap() { return null; } + @Override public int nargs() { return nIns()-2; } // Minus control, memory, fptr @Override public void encoding( Encoding enc ) { - enc.relo(this); + FunNode fun = CodeGen.CODE.link(_tfp); + if( fun==null ) enc.external(this,_name); + else enc.relo(this); // BL enc.add4(Arm64.b(Arm64.OP_CALL,0)); // Target patched at link time } @@ -40,7 +43,7 @@ public class CallARM extends CallNode implements MachNode, RIPRelSize { } @Override public void asm(CodeGen code, SB sb) { - sb.p(_name).p(" "); + sb.p(_name); for( int i=0; i<nargs(); i++ ) sb.p(code.reg(arg(i+2))).p(" "); sb.unchar(2); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallEndARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallEndARM.java deleted file mode 100644 index b3c2f6c2..00000000 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallEndARM.java +++ /dev/null @@ -1,8 +0,0 @@ -package com.seaofnodes.simple.node.cpus.arm; - -import com.seaofnodes.simple.node.CallEndNode; -import com.seaofnodes.simple.node.MachNode; - -public class CallEndARM extends CallEndNode implements MachNode { - CallEndARM( CallEndNode cend ) { super(cend); } -} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/ExtendARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/ExtendARM.java new file mode 100644 index 00000000..6fec7a77 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/ExtendARM.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.isa.Arm64; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.SB; + +// Convert a narrow C return register to Simple's full-width integer value. +public class ExtendARM extends MachConcreteNode { + final int _bits; + final boolean _signed; + ExtendARM(ProjNode prj, TypeInteger ret) { + super(prj); + _inputs.set(0,null); + _inputs.add(new ProjARM(prj)); + _bits = 8 << ret.log_size(); + _signed = ret._min < 0; + } + @Override public String op() { return (_signed ? "sext" : "zext")+_bits; } + @Override public RegMask regmap(int i) { return arm.RMASK; } + @Override public RegMask outregmap() { return arm.WMASK; } + @Override public void encoding(Encoding enc) { + short dst = enc.reg(this), src = enc.reg(in(1)); + // SBFM/UBFM aliases: sign/zero extend the low byte, short or int. + enc.add4(Arm64.imm_shift(_signed ? Arm64.OPI_ASR : Arm64.OPI_LSR,0,_bits-1,src,dst)); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java index 6209397d..6bc2fe08 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java @@ -21,8 +21,6 @@ public class FloatARM extends ConstantNode implements MachNode, RIPRelSize { @Override public void encoding( Encoding enc ) { enc.largeConstant(this,_con,0,-1/*TODO: ARM-style ELF patching*/); short dst = (short)(enc.reg(this) - arm.D_OFFSET); - double d = ((TypeFloat)_con).value(); - long x = Double.doubleToRawLongBits(d); enc.add4(Arm64.load_pc(Arm64.OPF_ARM, 0, dst)); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java index 1f2b6a37..720a14c1 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.ConstantNode; import com.seaofnodes.simple.node.MachNode; -import com.seaofnodes.simple.node.cpus.riscv.riscv; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeFunPtr; public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { @@ -26,21 +26,22 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { } @Override public byte encSize(int delta) { - if( -(1L<<12) <= delta && delta < (1L<<12) ) return 4; - throw Utils.TODO(); + return 8; } // Delta is from opcode start @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { short rpc = enc.reg(this); if(opLen == 8 ) { - // opstart of add - int next = opStart + opLen; + // ARM encoding delta is from PC & 0xFFF + int target = opStart+delta; + int base = opStart & ~0xFFF; + delta = target-base; int adrp_delta = delta >> 12; // patch upper 20 bits via adrp enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, adrp_delta >> 2, rpc)); // low 12 bits via add - enc.patch4(next, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, rpc)); + enc.patch4(opStart+4, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, rpc)); } else { // should not happen as one instruction is 4 byte, and TFP arm encodes 2. throw Utils.TODO(); @@ -51,4 +52,5 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { String reg = code.reg(this); _con.print(sb.p(reg).p(" #")); } + @Override public boolean eq(Node n) { return this==n; } } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/TMPARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/TMPARM.java new file mode 100644 index 00000000..adbaa8c2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/TMPARM.java @@ -0,0 +1,54 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.isa.Arm64; +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMemPtr; + +public class TMPARM extends ConstantNode implements MachNode, RIPRelSize { + TMPARM( ConstantNode con ) { super(con); } + @Override public String op() { return "ldp"; } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return arm.WMASK; } + @Override public boolean isClone() { return true; } + @Override public TMPARM copy() { return new TMPARM(this); } + @Override public void encoding( Encoding enc ) { + enc.largeConstant(this,((TypeMemPtr)_con)._obj,0,-1); + short dst = enc.reg(this); + // adrp x0, 0 + enc.add4(Arm64.adrp(1,0, Arm64.OP_ADRP, 0,dst)); + // add x0, x0, 0 + arm.imm_inst(enc,Arm64.OPI_ADD,0, dst); + } + + @Override public byte encSize(int delta) { + return 8; + } + + // Delta is from opcode start + @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { + short dst = enc.reg(this); + if(opLen == 8 ) { + // ARM encoding delta is from PC & 0xFFF + int target = opStart+delta; + int base = opStart & ~0xFFF; + delta = target-base; + int adrp_delta = delta >> 12; + // patch upper 20 bits via adrp + enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, adrp_delta >> 2, dst)); + // low 12 bits via add + enc.patch4(opStart+4, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, dst)); + } else { + throw Utils.TODO(); + } + } + + @Override public void asm(CodeGen code, SB sb) { + String reg = code.reg(this); + _con.print(sb.p(reg).p(" #")); + } + @Override public boolean eq(Node n) { return this==n; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 66a59fde..ddd9797b 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -224,6 +224,8 @@ public class arm extends Machine { if( idx==0 ) return CodeGen.CODE._rpcMask; if( idx==1 ) return null; // Count floats in signature up to index + if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence + // Count floats in signature up to index int fcnt=0; for( int i=2; i<idx; i++ ) if( tfp.arg(i-2) instanceof TypeFloat) @@ -277,47 +279,47 @@ public class arm extends Machine { // Instruction selection @Override public Node instSelect(Node n ) { return switch( n ) { - case AddFNode addf -> new AddFARM(addf); - case AddNode add -> add(add); - case AndNode and -> and(and); - case BoolNode bool -> cmp(bool); - case CallNode call -> call(call); - case CastNode cast -> new CastARM(cast); - case CallEndNode cend -> new CallEndARM(cend); - case CProjNode c -> new CProjNode(c); - case ConstantNode con -> con(con); - case DivFNode divf -> new DivFARM(divf); - case DivNode div -> new DivARM(div); - case FunNode fun -> new FunARM(fun); - case IfNode iff -> jmp(iff); - case LoadNode ld -> ld(ld); - case MemMergeNode mem -> new MemMergeNode(mem); - case MinusNode neg -> new NegARM(neg); - case MulFNode mulf -> new MulFARM(mulf); - case MulNode mul -> new MulARM(mul); - case NewNode nnn -> new NewARM(nnn); - case NotNode not -> new NotARM(not); - case OrNode or -> or(or); - case ParmNode parm -> new ParmARM(parm); + case AddFNode addf -> new AddFARM(addf); + case AddNode add -> add(add); + case AndNode and -> and(and); + case BoolNode bool -> cmp(bool); + case CallNode call -> call(call); + case CastNode cast -> new CastMach(cast); + case CallEndNode cend-> new CallEndMach(cend); + case CProjNode c -> new CProjNode(c); + case ConstantNode con-> con(con); + case DivFNode divf -> new DivFARM(divf); + case DivNode div -> new DivARM(div); + case FunNode fun -> new FunARM(fun); + case IfNode iff -> jmp(iff); + case LoadNode ld -> ld(ld); + case MemMergeNode mem-> new MemMergeNode(mem); + case MinusNode neg -> new NegARM(neg); + case MulFNode mulf -> new MulFARM(mulf); + case MulNode mul -> new MulARM(mul); + case NewNode nnn -> new NewARM(nnn); + case NotNode not -> new NotARM(not); + case OrNode or -> or(or); + case ParmNode parm -> new ParmARM(parm); case BulkMemPhiNode phi -> new BulkMemPhiNode(phi); case MemPhiNode phi -> new MemPhiNode(phi); - case PhiNode phi -> new PhiNode(phi); - case ProjNode prj -> new ProjARM(prj); - case ReadOnlyNode read -> new ReadOnlyNode(read); - case ReturnNode ret -> new RetARM(ret,ret.fun()); - case SarNode sar -> asr(sar); - case ShlNode shl -> lsl(shl); - case ShrNode shr -> lsr(shr); + case PhiNode phi -> new PhiNode(phi); + case ProjNode prj -> prj(prj); + case ReadOnlyNode read -> new ReadOnlyMach(read); + case ReturnNode ret -> new RetARM(ret,ret.fun()); + case SarNode sar -> asr(sar); + case ShlNode shl -> lsl(shl); + case ShrNode shr -> lsr(shr); case StartNode start -> new StartNode(start); - case StopNode stop -> new StopNode(stop); - case StoreNode st -> st(st); - case SubFNode subf -> new SubFARM(subf); - case SubNode sub -> sub(sub); - case ToFloatNode tfn-> new I2F8ARM(tfn); + case StopNode stop -> new StopNode(stop); + case StoreNode st -> st(st); + case SubFNode subf -> new SubFARM(subf); + case SubNode sub -> sub(sub); + case ToFloatNode tfn -> new I2F8ARM(tfn); case ToIntegerNode cvt -> new F8ToIARM(cvt); - case XorNode xor -> xor(xor); + case XorNode xor -> xor(xor); - case LoopNode loop -> new LoopNode(loop); + case LoopNode loop -> new LoopNode(loop); case RegionNode region-> new RegionNode(region); default -> throw Utils.TODO(); }; @@ -365,13 +367,13 @@ public class arm extends Machine { private Node con( ConstantNode con ) { if( !con._con.isConstant() ) return new ConstantNode( con ); // Default unknown caller inputs return switch( con._con ) { - case TypeInteger ti -> new IntARM(con); - case TypeFloat tf -> new FloatARM(con); - case TypeFunPtr tfp -> new TFPARM(con); - case TypeMemPtr tmp -> new ConstantNode(con); - case TypeNil tn -> throw Utils.TODO(); - // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. - case Type t -> t==Type.NIL ? new IntARM(con) : new ConstantNode(con); + case TypeInteger ti -> new IntARM(con); + case TypeFloat tf -> new FloatARM(con); + case TypeFunPtr tfp -> new TFPARM(con); + case TypeMemPtr tmp -> new TMPARM(con); + case TypeNil tn -> throw Utils.TODO(); + // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. + case Type t -> t==Type.NIL ? new IntARM(con) : new ConstantNode(con); }; } @@ -445,4 +447,9 @@ public class arm extends Machine { return mop; } + private Node prj(ProjNode prj) { + TypeInteger ret = cReturn(prj); + return ret==null ? new ProjARM(prj) : new ExtendARM(prj,ret); + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallEndRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallEndRISC.java deleted file mode 100644 index 7df68e77..00000000 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallEndRISC.java +++ /dev/null @@ -1,8 +0,0 @@ -package com.seaofnodes.simple.node.cpus.riscv; - -import com.seaofnodes.simple.node.CallEndNode; -import com.seaofnodes.simple.node.MachNode; - -public class CallEndRISC extends CallEndNode implements MachNode { - CallEndRISC( CallEndNode cend ) { super(cend); } -} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java index 2b3232c3..ff50a67f 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java @@ -14,23 +14,26 @@ public class CallRISC extends CallNode implements MachNode, RIPRelSize { assert tfp.isConstant(); _inputs.pop(); // Pop constant target _tfp = tfp; - _name = CodeGen.CODE.link(tfp)._name; + FunNode fun = CodeGen.CODE.link(tfp); + _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls } @Override public String op() { return "call"; } @Override public String label() { return op(); } - @Override public RegMask regmap(int i) { - return riscv.callInMask(_tfp,i,fun()._maxArgSlot); - } - @Override public RegMask outregmap() { return riscv.RPC_MASK; } @Override public String name() { return _name; } @Override public TypeFunPtr tfp() { return _tfp; } + @Override public RegMask regmap(int i) { return riscv.callInMask(_tfp,i,fun()._maxArgSlot); } + @Override public RegMask outregmap() { return riscv.RPC_MASK; } + @Override public int nargs() { return nIns()-2; } // Minus control, memory, fptr @Override public void encoding( Encoding enc ) { // Short form +/-4K: beq r0,r0,imm12 // Long form: auipc rX,imm20/32; jal r0,[rX+imm12/32] - enc.relo(this); - enc.add4(RiscV.j_type(RiscV.OP_JAL, riscv.RPC, 0)); + FunNode fun = CodeGen.CODE.link(_tfp); + if( fun==null ) enc.external(this,_name); + else enc.relo(this); + short rpc = enc.reg(this); + enc.add4(RiscV.j_type(RiscV.OP_JAL, rpc, 0)); } // Delta is from opcode start @@ -42,8 +45,9 @@ public class CallRISC extends CallNode implements MachNode, RIPRelSize { // Delta is from opcode start @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { + short rpc = enc.reg(this); if( opLen==4 ) { - enc.patch4(opStart,RiscV.j_type(RiscV.OP_JAL, riscv.RPC, delta)); + enc.patch4(opStart,RiscV.j_type(RiscV.OP_JAL, rpc, delta)); } else { throw Utils.TODO(); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ExtendRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ExtendRISC.java new file mode 100644 index 00000000..c2e93159 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ExtendRISC.java @@ -0,0 +1,32 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.isa.RiscV; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.SB; + +// Convert a narrow C return register to Simple's full-width integer value. +public class ExtendRISC extends MachConcreteNode { + final int _bits; + final boolean _signed; + ExtendRISC(ProjNode prj, TypeInteger ret) { + super(prj); + _inputs.set(0,null); + _inputs.add(new ProjRISC(prj)); + _bits = 8 << ret.log_size(); + _signed = ret._min < 0; + } + @Override public String op() { return (_signed ? "sext" : "zext")+_bits; } + @Override public RegMask regmap(int i) { return riscv.RMASK; } + @Override public RegMask outregmap() { return riscv.WMASK; } + @Override public void encoding(Encoding enc) { + short dst = enc.reg(this), src = enc.reg(in(1)); + int shift = 64-_bits; + enc.add4(RiscV.i_type(RiscV.OP_IMM,dst,1,src,shift)); + enc.add4(RiscV.i_type(RiscV.OP_IMM,dst,5,dst,shift | (_signed ? 0x400 : 0))); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java index 9f6dec78..3dbb40d1 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java @@ -17,7 +17,7 @@ public class FltRISC extends ConstantNode implements MachNode, RIPRelSize { @Override public FltRISC copy() { return new FltRISC(this); } @Override public void encoding( Encoding enc ) { - enc.largeConstant(this,_con, 0, -1/*TODO: RISC5 style patching*/); + enc.largeConstant(this,_con, 0, -1); short dst = (short)(enc.reg(this) - riscv.F_OFFSET); short tmp = (short)riscv.T6; // AUIPC dst,#hi20_constant_pool @@ -28,7 +28,6 @@ public class FltRISC extends ConstantNode implements MachNode, RIPRelSize { @Override public RegMask killmap() { return new RegMask(riscv.T6); } // Delta is from opcode start. - // TODO: always size 8? @Override public byte encSize(int delta) { return 8; } // Delta is from opcode start diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java index dd41589c..ceea98e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java @@ -42,8 +42,7 @@ abstract public class ImmRISC extends MachConcreteNode implements MachNode { @Override public void encoding( Encoding enc ) { short dst = enc.reg(this ); short src = enc.reg(in(1)); - int body = RiscV.i_type(opcode(), dst, func3(), src, _imm12 & 0xFFF); - enc.add4(body); + enc.add4(RiscV.i_type(opcode(), dst, func3(), src, _imm12 & 0xFFF)); } // General form: "addi rd = rs1 + imm" diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/Int8RISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/Int8RISC.java new file mode 100644 index 00000000..fabb3b9d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/Int8RISC.java @@ -0,0 +1,48 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.isa.RiscV; +import com.seaofnodes.simple.node.ConstantNode; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.MachNode; + +// Special instruction for loading 8 byte constants from the constant pool. + +public class Int8RISC extends ConstantNode implements MachNode, RIPRelSize { + public Int8RISC(ConstantNode con) { super(con); } + + @Override public String op() { return "ld8"; } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return riscv.WMASK; } + @Override public boolean isClone() { return true; } + @Override public Int8RISC copy() { return new Int8RISC(this); } + + @Override public byte encSize(int delta) { return 8; } + + @Override public void encoding( Encoding enc ) { + short dst = enc.reg(this); + short tmp = (short)riscv.T6; + enc.largeConstant(this,_con, 0, -1); + // AUIPC dst,#hi20_constant_pool + enc.add4(RiscV.u_type(RiscV.OP_AUIPC, tmp, 0)); + // Load dst,[dst+#low12_constant_pool] + enc.add4(RiscV.i_type(RiscV.OP_LOAD, dst, 0b11, tmp, 0)); + } + @Override public RegMask killmap() { return new RegMask(riscv.T6); } + + // Delta is from opcode start + @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { + short dst = enc.reg(this); + short tmp = (short)riscv.T6; + // AUIPC dst,#hi20_constant_pool + enc.patch4(opStart , RiscV.u_type(RiscV.OP_AUIPC, tmp, delta>>12)); + // Load dst,[dst+#low12_constant_pool] + enc.patch4(opStart+4, RiscV.i_type(RiscV.OP_LOAD, dst, 0b11, tmp, delta & 0xFFF)); + } + + @Override public void asm(CodeGen code, SB sb) { + _con.print(sb.p(code.reg(this)).p(" = #")); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LUI.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LUI.java index 596e11cd..deaa3b59 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LUI.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LUI.java @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class LUI extends ConstantNode implements MachNode { public LUI( int imm20 ) { super(TypeInteger.constant(imm20)); - assert riscv.imm20Exact((TypeInteger)_con); + assert (imm20 & 0xFFF)==0; } @Override public RegMask regmap(int i) { return null; } @Override public RegMask outregmap() { return riscv.WMASK; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java index 41ab37be..c2025a3d 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java @@ -36,8 +36,9 @@ public abstract class MemOpRISC extends MemOpNode implements MachNode { if(this instanceof StoreRISC) { if( _declaredType == TypeInteger. I8 || _declaredType == TypeInteger.U8 || _declaredType == TypeInteger.BOOL) func3=0; // SB if( _declaredType == TypeInteger.I16 || _declaredType == TypeInteger.U16 ) func3=1; // SH - if( _declaredType == TypeInteger.I32 || _declaredType == TypeInteger.U32 || _declaredType instanceof TypeMemPtr) func3=2; // SW - if( _declaredType == TypeInteger.BOT ) func3=3; // SD + if( _declaredType == TypeInteger.I32 || _declaredType == TypeInteger.U32 ) func3=2; // SW + if( _declaredType instanceof TypeMemPtr) func3=3; // SD + if( _declaredType == TypeInteger.BOT ) func3=3; // SD if( func3 == -1 ) throw Utils.TODO(); return func3; } @@ -51,9 +52,10 @@ public abstract class MemOpRISC extends MemOpNode implements MachNode { if( _declaredType == TypeInteger.U32 ) func3=6; // LWU // float - if(_declaredType == TypeFloat.F32) func3 = 2; // fLW fSW - if(_declaredType == TypeFloat.F64) func3 = 3; // fLD fSD - if( _declaredType instanceof TypeMemPtr ) func3=3; // 8 byte pointers + if( _declaredType == TypeFloat.F32) func3 = 2; // fLW fSW + if( _declaredType == TypeFloat.F64) func3 = 3; // fLD fSD + + if( _declaredType instanceof TypeMemPtr) func3 = 3; // 8 byte pointers (pick ld) if( func3 == -1 ) throw Utils.TODO(); return func3; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java index 49b1cad9..48171483 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java @@ -5,7 +5,9 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.Node; public class SraIRISC extends ImmRISC { - public SraIRISC( Node and, int imm) { super(and,imm); } + public SraIRISC( Node and, int imm) { + super(and,imm | (0x20 << 5)); + } @Override int opcode() { return RiscV.OP_IMM; } @Override int func3() { return 5;} @Override public String glabel() { return ">>"; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index 3cb7cc2d..03e06f83 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -27,7 +27,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return _sz >= '4' ? riscv.MEM_MASK : riscv.RMASK; // No byte/short FP stores + if( i==4 ) return _sz >= '4' + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java index 1d3c5920..d7da5ba1 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.ConstantNode; import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeFunPtr; public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize { @@ -20,11 +21,9 @@ public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize { short dst = enc.reg(this); TypeFunPtr tfp = (TypeFunPtr)_con; // auipc t0,0 - int auipc = RiscV.u_type(RiscV.OP_AUIPC, dst, 0); + enc.add4(RiscV.u_type(RiscV.OP_AUIPC, dst, 0)); // addi t1,t0 + #0 - int addi = RiscV.i_type(RiscV.OP_IMM, dst, 0, dst, 0); - enc.add4(auipc); - enc.add4(addi); + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 0, dst, 0)); } @Override public byte encSize(int delta) { return 8; } @@ -45,5 +44,5 @@ public class TFPRISC extends ConstantNode implements MachNode, RIPRelSize { @Override public void asm(CodeGen code, SB sb) { _con.print(sb.p(code.reg(this)).p(" #")); } - + @Override public boolean eq(Node n) { return this==n; } } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TMPRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TMPRISC.java new file mode 100644 index 00000000..46b8aace --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TMPRISC.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.isa.RiscV; +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMemPtr; + +public class TMPRISC extends ConstantNode implements MachNode, RIPRelSize { + TMPRISC(ConstantNode con) { super(con); } + @Override public String op() { return "ldp"; } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return riscv.WMASK; } + @Override public boolean isClone() { return true; } + @Override public TMPRISC copy() { return new TMPRISC(this); } + @Override public void encoding( Encoding enc ) { + enc.largeConstant(this,((TypeMemPtr)_con)._obj,0,-1); + short dst = enc.reg(this); + // AUIPC dst,#hi20_constant_pool + enc.add4(RiscV.u_type(RiscV.OP_AUIPC, dst, 0)); + // addi dst,[dst+#low12_constant_pool] + enc.add4(RiscV.i_type(RiscV.OP_IMM, dst, 0, dst, 0)); + } + + @Override public byte encSize(int delta) { return 8; } + + // Delta is from opcode start + @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { + short dst = enc.reg(this); + // Round the high part because ADDI's low 12 bits are signed. + enc.patch4(opStart , RiscV.u_type(RiscV.OP_AUIPC, dst, (delta+0x800)>>12)); + // ADDI dst,dst,#low12_constant_pool + enc.patch4(opStart+4, RiscV.i_type(RiscV.OP_IMM, dst, 0, dst, delta & 0xFFF)); + } + + @Override public void asm(CodeGen code, SB sb) { + _con.print(sb.p(code.reg(this)).p(" #")); + } + @Override public boolean eq(Node n) { return this==n; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java index df96d10b..ebdf9fa8 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java @@ -6,6 +6,7 @@ import com.seaofnodes.simple.node.Node; public class XorIRISC extends ImmRISC { public XorIRISC( Node and, int imm) { super(and,imm); } + public XorIRISC( Node and, int imm, boolean pop) { super(and,imm,pop); } @Override int opcode() { return RiscV.OP_IMM; } @Override int func3() { return 4; } @Override public String glabel() { return "^"; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 335347e9..f2d1e0b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -137,6 +137,7 @@ public class riscv extends Machine { static RegMask callInMask( TypeFunPtr tfp, int idx, int maxArgSlot ) { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; + if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence // Count floats in signature up to index int fcnt=0; for( int i=2; i<idx; i++ ) @@ -197,7 +198,7 @@ public class riscv extends Machine { // shift left 32 to clear out the upper 32 bits. // shift right SIGNED to sign-extend upper 32 bits; then shift 12 more to clear out lower 12 bits. // shift left 12 to re-center the bits. - return ti.isConstant() && (((ti.value()<<32)>>>44)<<12) == ti.value(); + return ti.isConstant() && (((ti.value()<<32)>>44)<<12) == ti.value(); } @Override public Node instSelect( Node n ) { @@ -207,8 +208,8 @@ public class riscv extends Machine { case AndNode and -> and(and); case BoolNode bool -> cmp(bool); case CallNode call -> call(call); - case CastNode cast -> new CastRISC(cast); - case CallEndNode cend -> new CallEndRISC(cend); + case CastNode cast -> new CastMach(cast); + case CallEndNode cend -> new CallEndMach(cend); case CProjNode c -> new CProjNode(c); case ConstantNode con -> con(con); case DivFNode divf -> new DivFRISC(divf); @@ -228,7 +229,7 @@ public class riscv extends Machine { case MemPhiNode phi -> new MemPhiNode(phi); case PhiNode phi -> new PhiNode(phi); case ProjNode prj -> prj(prj); - case ReadOnlyNode read-> new ReadOnlyNode(read); + case ReadOnlyNode read-> new ReadOnlyMach(read); case ReturnNode ret -> new RetRISC(ret, ret.fun()); case SarNode sar -> sra(sar); case ShlNode shl -> sll(shl); @@ -302,7 +303,7 @@ public class riscv extends Machine { ? new SetIRISC(bool, (int)ti.value(),false) : new SetRISC(bool, false); // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` - case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1); + case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1,false); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` case "==" -> new SetIRISC(new SubRISC(bool),1,true,false); default -> throw Utils.TODO(); @@ -325,12 +326,12 @@ public class riscv extends Machine { } // Need more complex sequence for larger constants... or a load // from a constant pool, which does not need an extra register - throw Utils.TODO(); + yield new Int8RISC(con); } // Load from constant pool case TypeFloat tf -> new FltRISC(con); case TypeFunPtr tfp -> new TFPRISC(con); - case TypeMemPtr tmp -> throw Utils.TODO(); + case TypeMemPtr tmp -> new TMPRISC(con); case TypeNil tn -> throw Utils.TODO(); // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. case Type t -> t==Type.NIL ? new IntRISC(con) : new ConstantNode(con); @@ -391,6 +392,8 @@ public class riscv extends Machine { } private Node prj(ProjNode prj) { + TypeInteger ret = cReturn(prj); + if( ret!=null ) return new ExtendRISC(prj,ret); return new ProjRISC(prj); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java index 569be754..c55f975c 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddIX86.java @@ -1,5 +1,9 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.node.Node; public class AddIX86 extends ImmX86 { @@ -10,4 +14,10 @@ public class AddIX86 extends ImmX86 { @Override public String glabel() { return "+"; } @Override int opcode() { return 0x81; } @Override int mod() { return 0; } + @Override public final void encoding( Encoding enc ) { + if( _imm== 1 || _imm== -1 ) { + short dst = enc.reg(this); // Also src1 + X86.unary(enc,0xFF,_imm==1 ? 0 : 1,dst); + } else super.encoding(enc); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java deleted file mode 100644 index ce8b993f..00000000 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java +++ /dev/null @@ -1,8 +0,0 @@ -package com.seaofnodes.simple.node.cpus.x86_64_v2; - -import com.seaofnodes.simple.node.CallEndNode; -import com.seaofnodes.simple.node.MachNode; - -public class CallEndX86 extends CallEndNode implements MachNode { - CallEndX86( CallEndNode cend ) { super(cend); } -} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index c97037e2..3d450040 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; +import com.seaofnodes.isa.X86; import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; -import com.seaofnodes.simple.node.CallNode; -import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeFunPtr; public class CallX86 extends CallNode implements MachNode, RIPRelSize { @@ -14,7 +14,8 @@ public class CallX86 extends CallNode implements MachNode, RIPRelSize { _inputs.pop(); // Pop constant target assert tfp.isConstant(); _tfp = tfp; - _name = CodeGen.CODE.link(tfp)._name; + FunNode fun = CodeGen.CODE.link(tfp); + _name = fun==null ? ((ExternNode)call.fptr())._extern : fun._name; // Can be null for extern calls } @Override public String op() { return "call"; } @Override public String label() { return op(); } @@ -25,7 +26,10 @@ public class CallX86 extends CallNode implements MachNode, RIPRelSize { @Override public int nargs() { return nIns()-2; } // Minus control, memory, fptr @Override public void encoding( Encoding enc ) { - enc.relo(this).add1(0xe8).add4(0); + FunNode fun = CodeGen.CODE.link(_tfp); + if( fun==null ) enc.external(this,_name); + else enc.relo(this); + X86.call(enc); } // Delta is from opcode start, but X86 measures from the end of the 5-byte encoding diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CastX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CastX86.java deleted file mode 100644 index 9537cfb3..00000000 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CastX86.java +++ /dev/null @@ -1,16 +0,0 @@ -package com.seaofnodes.simple.node.cpus.x86_64_v2; - -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.codegen.*; -import com.seaofnodes.simple.node.CastNode; -import com.seaofnodes.simple.node.MachNode; - -public class CastX86 extends CastNode implements MachNode { - CastX86( CastNode cast ) { super(cast); } - @Override public String op() { return label(); } - @Override public RegMask regmap(int i) { assert i==1; return RegMask.FULL; } - @Override public RegMask outregmap() { return RegMask.FULL; } - @Override public int twoAddress( ) { return 1; } - @Override public void encoding( Encoding enc ) { } - @Override public void asm(CodeGen code, SB sb) { _t.print(sb.p(code.reg(in(1))).p(" isa ")); } -} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java index bf8f1631..942400f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java @@ -12,7 +12,7 @@ public class CmpMemX86 extends MemOpX86 { CmpMemX86( BoolNode bool, LoadNode ld, Node base, Node idx, int off, int scale, int imm, Node val, boolean swap ) { super(bool,ld, base, idx, off, scale, imm, val ); _swap = swap; - assert !_swap || val() == null || bool.op()=="==" || bool.op()=="!="; // Cannot swap with immediate + assert !_swap || val() != null || bool.op()=="==" || bool.op()=="!="; // Cannot swap with immediate } @Override public String op() { return ((val()==null && _imm==0) ? "test" : "cmp") + _sz; } @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java index e3cbe75f..27246db5 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java @@ -10,6 +10,12 @@ public class CmpX86 extends MachConcreteNode implements MachNode { @Override public String op() { return "cmp"; } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } + // This one is marginal: cloning a Cmp[reg,reg] means stretching the + // lifetimes of 2 normal registers in exchange for shortening a flags + // register lifetime. Spilling flags is (probably) relatively expensive + // compared to some normal registers - and those normal registers might not + // be spilling! + @Override public boolean isClone() { return true; } @Override public void encoding( Encoding enc ) { X86.reg(enc,0x3B,enc.reg(in(1)),enc.reg(in(2))); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java index e61f576c..5d061ae1 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java @@ -9,7 +9,7 @@ public class DivX86 extends MachConcreteNode implements MachNode { DivX86( Node div ) { super(div); } @Override public String op() { return "div"; } @Override public RegMask regmap(int i) { - return (i==1) ? x86_64_v2.RAX_MASK : x86_64_v2.RMASK; + return (i==1) ? x86_64_v2.RAX_MASK : x86_64_v2.DIV_MASK; } @Override public RegMask outregmap() { return x86_64_v2.RAX_MASK; } @Override public RegMask killmap() { return x86_64_v2.RDX_MASK; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ExtendX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ExtendX86.java new file mode 100644 index 00000000..bd40bae7 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ExtendX86.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.SB; + +// Convert a narrow C return register to Simple's full-width integer value. +public class ExtendX86 extends MachConcreteNode { + final int _bits; + final boolean _signed; + ExtendX86(ProjNode prj, TypeInteger ret) { + super(prj); + _inputs.set(0,null); + _inputs.add(new ProjX86(prj)); + _bits = 8 << ret.log_size(); + _signed = ret._min < 0; + } + @Override public String op() { return (_signed ? "sext" : "zext")+_bits; } + @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + @Override public void encoding(Encoding enc) { + X86.extend(enc,_bits,_signed,enc.reg(this),enc.reg(in(1))); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java index b87e7f47..08c9b4c9 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java @@ -16,11 +16,12 @@ public abstract class ImmX86 extends MachConcreteNode implements MachNode { @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.WMASK; } @Override public int twoAddress() { return 1; } + @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } abstract int opcode(); abstract int mod(); - @Override public final void encoding( Encoding enc ) { + @Override public void encoding( Encoding enc ) { X86.imm(enc,opcode(),mod(),enc.reg(this),_imm); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java index 6c7ecbbc..22a1a7ae 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java @@ -14,6 +14,7 @@ public class MemAddX86 extends MemOpX86 { } // Register mask allowed as a result. 0 for no register. @Override public RegMask outregmap() { return null; } + @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } @Override public void encoding( Encoding enc ) { X86.addMem(enc,enc.reg(val()),_imm,enc.reg(ptr()),enc.reg(idx()),_off,_scale); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java index 2c1ce261..4a7e24d0 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java @@ -7,8 +7,8 @@ import com.seaofnodes.simple.codegen.*; public class MulIX86 extends MachConcreteNode implements MachNode { final int _imm; - MulIX86( Node mul, int imm ) { - super(mul); + MulIX86( Node add, int imm ) { + super(add); _inputs.pop(); // Pop the constant input _imm = imm; // Record the constant } @@ -16,14 +16,11 @@ public class MulIX86 extends MachConcreteNode implements MachNode { @Override public String glabel() { return "*"; } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.WMASK; } - // Retain Chapter 21's allocation contract: output is also input #1. - @Override public int twoAddress() { return 1; } - - // IMUL encodes a destination register, unlike ImmX86's opcode extension. + // Rare 3-address form @Override public final void encoding( Encoding enc ) { X86.imul(enc,enc.reg(this),enc.reg(in(1)),_imm); } - // General form: "muli dst = src * #imm" + // General form: "addi dst += #imm" @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" * #").p(_imm); } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java index 8dc749ee..50c8e974 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java @@ -9,6 +9,7 @@ public abstract class RegX86 extends MachConcreteNode { RegX86( Node add ) { super(add); } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } @Override public int twoAddress() { return 1; } abstract int opcode(); @Override public void encoding( Encoding enc ) { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java index d0c6157c..8723af91 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java @@ -49,4 +49,5 @@ public class TFPX86 extends ConstantNode implements MachNode, RIPRelSize { else _con.print(sb.p(reg).p(" = #")); } + @Override public boolean eq(Node n) { return this==n; } } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java new file mode 100644 index 00000000..027b2e01 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeMemPtr; + +public class TMPX86 extends ConstantNode implements MachNode, RIPRelSize{ + TMPX86(ConstantNode con ) { super(con); } + @Override public String op() { return "ldp"; } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + @Override public boolean isClone() { return true; } + @Override public Node copy() { return new TMPX86(this); } + + @Override public void encoding( Encoding enc ) { + short dst = enc.reg(this); + X86.rexF(dst, 0, 0, true, enc); + enc.add1(0x8D).add1(X86.modrm(X86.MOD.INDIRECT, dst, 0b101)).add4(0); + enc.largeConstant(this,((TypeMemPtr)_con)._obj,7-4,2/*ELF encoding PC32*/); + } + + // Delta is from opcode start + @Override public byte encSize(int delta) { return (byte)7; } + + // Delta is from opcode start + @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { + enc.patch4(opStart+opLen-4,delta-opLen); + } + + @Override public void asm(CodeGen code, SB sb) { + _con.print(sb.p(code.reg(this)).p(" = #")); + } + @Override public boolean eq(Node n) { return this==n; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 1b7cf775..7ddd17d4 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -43,6 +43,8 @@ public class x86_64_v2 extends Machine { static RegMask XMASK = new RegMask(FP_BITS); static RegMask FLAGS_MASK = new RegMask(FLAGS); static RegMask RPC_MASK = new RegMask(RPC); + // Divide mask: exclude RDX:RAX + static RegMask DIV_MASK = new RegMask(RD_BITS & ~(1L<<RAX) & ~(1L<<RDX)); static final long SPILLS = -(1L << MAX_REG); static final RegMask SPLIT_MASK = new RegMask(WR_BITS | FP_BITS /* | (1L<<FLAGS)*/ | SPILLS, -1L ); @@ -61,7 +63,7 @@ public class x86_64_v2 extends Machine { public static RegMask XMM0_MASK = new RegMask(XMM0); // Encoding - public static int REX = 0x40; + public static int REX = 0x40; public static int REX_W = 0x48; public static int REX_WR = 0x4C; public static int REX_WRB= 0x4D; @@ -98,6 +100,7 @@ public class x86_64_v2 extends Machine { static RegMask callInMask( TypeFunPtr tfp, int idx, int maxArgSlot ) { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; + if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence return switch( CodeGen.CODE._callingConv ) { case "SystemV" -> callSys5 (tfp,idx,maxArgSlot); case "Win64" -> callWin64(tfp,idx,maxArgSlot); @@ -252,9 +255,9 @@ public class x86_64_v2 extends Machine { case AndNode and -> and(and); case BoolNode bool -> cmp(bool); case CProjNode c -> new CProjNode(c); - case CallEndNode cend -> new CallEndX86(cend); + case CallEndNode cend -> new CallEndMach(cend); case CallNode call -> call(call); - case CastNode cast -> new CastX86(cast); + case CastNode cast -> new CastMach(cast); case ConstantNode con -> con(con); case DivFNode divf -> new DivFX86(divf); case DivNode div -> new DivX86(div); @@ -273,7 +276,7 @@ public class x86_64_v2 extends Machine { case MemPhiNode phi -> new MemPhiNode(phi); case PhiNode phi -> new PhiNode(phi); case ProjNode prj -> prj(prj); - case ReadOnlyNode read-> new ReadOnlyNode(read); + case ReadOnlyNode read-> new ReadOnlyMach(read); case ReturnNode ret -> new RetX86(ret, ret.fun()); case SarNode sar -> sar(sar); case ShlNode shl -> shl(shl); @@ -410,15 +413,16 @@ public class x86_64_v2 extends Machine { } private Node con( ConstantNode con ) { - if(!con._con.isConstant()) return new ConstantNode(con); // Default unknown caller inputs + if( !con._con.isConstant() ) + return new ConstantNode(con); // Default unknown caller inputs return switch (con._con) { - case TypeInteger ti -> new IntX86(con); - case TypeFloat tf -> new FltX86(con); - case TypeFunPtr tfp -> new TFPX86(con); - case TypeMemPtr tmp -> throw Utils.TODO(); - case TypeNil tn -> throw Utils.TODO(); - // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. - case Type t -> t == Type.NIL ? new IntX86(con) : new ConstantNode(con); + case TypeInteger ti -> new IntX86(con); + case TypeFloat tf -> new FltX86(con); + case TypeFunPtr tfp -> new TFPX86(con); + case TypeMemPtr tmp -> new TMPX86(con); + case TypeNil tn -> throw Utils.TODO(); + // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. + case Type t -> t == Type.NIL ? new IntX86(con) : new ConstantNode(con); }; } @@ -455,6 +459,8 @@ public class x86_64_v2 extends Machine { } private Node prj( ProjNode prj ) { + TypeInteger ret = cReturn(prj); + if( ret!=null ) return new ExtendX86(prj,ret); return new ProjX86(prj); } diff --git a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 09ebd51b..1cc83813 100644 --- a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -68,7 +68,7 @@ public final class ASMPrinter extends AssemblyAdapter<Node> { var data=new ArrayList<Data>(); for( Encoding.Relo r : relos ) { int align=1<<r._align; - int size=align; + int size=r._t instanceof TypeStruct ? (r._structSize+align-1)&-align : align; if( r._t instanceof TypeTuple t ) size=align*t._types.length; data.add(new Data(r._t,r._t.str(),r._align,size)); } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index b9aabba3..3d10a80c 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 21's view of the IR; browser, transport and layout are shared. */ +/** Chapter 22's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String edgeName(Node n, int i) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index d8d0e216..22b6beba 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 21's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 22's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private CodeGen _code; public SimpleGraphObserver() { super(new SimpleGraphAdapter()); } diff --git a/src/main/java/com/seaofnodes/simple/sys.java b/src/main/java/com/seaofnodes/simple/sys.java new file mode 100644 index 00000000..45106770 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/sys.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; + + +/** Default included namespaces for Simple. + + You can think of this as {@code #include <stdio.h>} for C or {@code import java.lang.*} for Java. + */ +public abstract class sys { + + public static final String SYS; + + static { + try { + SYS = Files.readString(Path.of("src/main/smp/sys.smp")); + } + catch( Exception e ) { + throw new RuntimeException(e); + } + } + +} diff --git a/src/main/java/com/seaofnodes/simple/sys/sys.smp b/src/main/java/com/seaofnodes/simple/sys/sys.smp new file mode 100644 index 00000000..4ac925db --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/sys/sys.smp @@ -0,0 +1,58 @@ +// -*- mode: java; -*- + +// top-level default import +struct sys { + // libc bindings + /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */ + struct libc { + i32 errno = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } write = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } read = "C"; + // status + { i32 -> i32 } _exit = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; + }; + struct ary { + val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + for( int i=0; i<len; i++ ) + dst[i+doff] = src[i+soff]; + return dst; + }; + }; + struct io { + // Print string to stdout + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return sys.libc.write(1,ptr,str#); + }; + + // Return stdin as a u8[] + val stdin = { -> + var buf = new u8[8*1024]; + i64 ptr = buf; + int len = 0; + while( true ) { + int rez = sys.libc.read(0,ptr,buf#); + if( rez < 0 ) sys.libc._exit(sys.libc.errno); + len += rez; + if( rez < buf# ) + break; + sys.libc._exit(-2); // Need to implement + } + // Compress + var dst = new u8[len]; + return sys.ary.copy(dst,0,buf,0,len); + }; + + }; +}; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index c93f82e7..94afcd26 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -51,8 +51,10 @@ public class Field extends Type { @Override public Field dual() { return make(_fname,_type.dual(),_alias,!_final); } - @Override public Field glb() { - Type glb = _type.glb(); + @Override public boolean isConstant() { return _type.isConstant(); } + + @Override public Field glb(boolean mem) { + Type glb = _type.glb(mem); return (glb==_type && _final) ? this : make(_fname,glb,_alias,true); } @@ -70,5 +72,5 @@ public class Field extends Type { return _type.print(sb.p(_final?"":"!").p(_fname).p(":").p(_alias).p(" : ")); } - @Override public String str() { return _fname; } + @Override public String str() { return (_final?"":"!")+_fname; } } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 96b2c6ef..4fad33cb 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -44,7 +44,8 @@ public class Type { 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 - static final byte TRPC =16; // Return Program Control (Return PC or RPC) + static final byte TCONARY =16; // Constant array + static final byte TRPC =17; // Return Program Control (Return PC or RPC) public final byte _type; @@ -75,6 +76,7 @@ public class Type { TypeStruct.gather(ts); TypeTuple.gather(ts); TypeRPC.gather(ts); + TypeConAry.gather(ts); int sz = ts.size(); for( int i = 0; i < sz; i++ ) ts.add(ts.get(i).dual()); @@ -160,6 +162,7 @@ public class Type { // 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; @@ -200,8 +203,9 @@ public class Type { // Make a zero version of this type, 0 for integers and null for pointers. public Type makeZero() { return Type.NIL; } - /** Compute greatest lower bound in the lattice */ - public Type glb() { return Type.BOTTOM; } + /** Compute greatest lower bound in the lattice. If values are in memory, + * ints and floats cannot widen. */ + public Type glb(boolean mem) { return Type.BOTTOM; } // Writable array slots are invariant in their element access permissions. // Otherwise an alias could insert a readonly pointer into a writable slot. @@ -222,7 +226,9 @@ public class Type { // Sizes are expected to be between 1 and 64 bits. // Size 0 means this either takes no space (such as a known-zero field) // or isn't a scalar to be stored in memory. - public int log_size() { return 3; } + public int log_size () { return 3; } // log-size of a type; log_size for a struct is usually undefined + public int size() { return 1<<log_size(); } + public int alignment() { return log_size(); } // alignment; for structs, max align of Fields // ---------------------------------------------------------- // Useful in the debugger, which calls toString everywhere. diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java new file mode 100644 index 00000000..692450d0 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -0,0 +1,69 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.Utils; +import java.util.ArrayList; +import java.io.ByteArrayOutputStream; + +/** + * Represents a constant array of primitives + */ +public class TypeConAry<A> extends Type { + boolean _any; + // One of byte,short,int,long,float,double array + public final A _ary; + + TypeConAry( boolean any, A ary ) { super(TCONARY); _any = any; _ary = ary; } + private static final TypeConAry TOP = new TypeConAry(true ,null).intern(); + public static final TypeConAry BOT = new TypeConAry(false,null).intern(); + public static void gather(ArrayList<Type> ts) { + ts.add(BOT); + ts.add(TypeConAryB.ABC); + ts.add(TypeConAryB.ABCD); + ts.add(TypeConAryI.I123); + } + + @Override public String str() { return (_any?"~":"") + "[]"; } + @Override public boolean isConstant() { return true; } + @Override public TypeConAry dual() { + if( this== BOT ) return TOP; + if( this== TOP ) return BOT; + return this; + } + + @Override Type xmeet(Type t) { + TypeConAry ary = (TypeConAry)t; // Invariant + if( this==TOP ) return ary ; + if( ary ==TOP ) return this; + assert _ary!=ary._ary; // Already interned and this!=t + return BOT; + } + + // Meet-over-elements type + public Type elem() { + if( _ary==null ) + return _any ? TOP : BOTTOM; + int len = len(); + long min = Long.MAX_VALUE; + long max = Long.MIN_VALUE; + for( int i=0; i<len; i++ ) { + min = Math.min(min,at(i)); + max = Math.max(max,at(i)); + } + return TypeInteger.make(min,max); + } + public long at(int idx) { throw Utils.TODO(); } + public int len() { throw Utils.TODO(); } + @Override public int alignment() { return 0; } + public void write( ByteArrayOutputStream baos ) { throw Utils.TODO(); } + + @Override boolean eq(Type t) { + TypeConAry ary = (TypeConAry)t; // Invariant + return _any==ary._any && ary._ary==null; + } + + @Override int hash() { + assert _ary==null; + return _any ? 1024 : 0; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java new file mode 100644 index 00000000..b56beb47 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -0,0 +1,18 @@ +package com.seaofnodes.simple.type; + +import java.util.Arrays; +import java.io.ByteArrayOutputStream; + +public class TypeConAryB extends TypeConAry<byte[]> { + private TypeConAryB(byte[] bs) { super(false,bs); } + public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(bs).intern(); } + public static TypeConAryB make( String s ) { return make(s.getBytes()); } + static final TypeConAryB ABC = make("abc"); + static final TypeConAryB ABCD = make("abcd"); + @Override public long at(int idx) { return _ary[idx]; } + @Override public int len() { return _ary.length; } + @Override public String str() { return "[\""+new String(_ary)+"\"]"; } + @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryB)t)._ary); } + @Override int hash() { return Arrays.hashCode(_ary); } + @Override public void write( ByteArrayOutputStream baos ) { baos.write(_ary,0,_ary.length); } +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java new file mode 100644 index 00000000..4859e839 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -0,0 +1,13 @@ +package com.seaofnodes.simple.type; + +import java.util.Arrays; + +public class TypeConAryI extends TypeConAry<int[]> { + private TypeConAryI(int[] bs) { super(false,bs); } + public static TypeConAryI make( int[] bs ) { return new TypeConAryI(bs).intern(); } + static final TypeConAryI I123 = make(new int[]{1,2,3}); + @Override public String str() { return "[i32]"; } + @Override public int alignment() { return 2; } + @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } + @Override int hash() { return Arrays.hashCode(_ary); } +} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index aa205149..a0940f8b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -81,7 +81,7 @@ public class TypeFloat extends Type { } @Override public Type makeZero() { return FZERO; } - @Override public Type glb() { return F64; } + @Override public Type glb(boolean mem) { return mem ? (isHigh() ? dual() : this) : F64; } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz ^ (1<<17)); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 1bd73732..e6701360 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -59,7 +59,7 @@ public class TypeFunPtr extends TypeNil { // RHS is NIL; do not deep-dual when crossing the centerline @Override public Type meet0() { return _nil==3 ? this : make((byte)3,_sig,_ret,_fidxs); } - @Override public TypeFunPtr glb() { return make((byte)3,_sig,_ret,-1L); } + @Override public TypeFunPtr glb(boolean mem) { return make((byte)3,_sig,_ret,-1L); } @Override public boolean isHigh () { return _nil <= 1 || (_nil==2 && _fidxs==0); } @Override public boolean isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index cccb85a5..59378ef3 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -75,11 +75,17 @@ public class TypeInteger extends Type { @Override public boolean isConstant() { return _min == _max; } @Override public int log_size() { + if( isHigh() ) return 0; // High types are dead, and should never hit code emission. if( this==I8 || this==U8 || this==BOOL ) return 0; // 1<<0 == 1 bytes if( this==I16 || this==U16 ) return 1; // 1<<1 == 2 bytes if( this==I32 || this==U32 ) return 2; // 1<<2 == 4 bytes if( this==BOT ) return 3; // 1<<3 == 8 bytes - if( isHighOrConst() ) return 0; + if( isConstant() ) { // just const here + if (-0xFF <= _min && _min <= 0xFF) return 0; + else if (-0xFFFF <= _min && _min <= 0xFFFF) return 1; + else if (-0xFFFFFFFFL <= _min && _min <= 0xFFFFFFFFL) return 2; + else return 3; + } throw Utils.TODO(); } @@ -119,7 +125,7 @@ public class TypeInteger extends Type { return this; } @Override public Type makeZero() { return ZERO; } - @Override public TypeInteger glb() { return BOT; } + @Override public Type glb(boolean mem) { return mem ? (isHigh() ? dual() : this) : BOT; } @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } @Override public boolean eq( Type t ) { TypeInteger i = (TypeInteger)t; // Contract diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index fe393a88..74bcbd8f 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -50,7 +50,8 @@ public class TypeMem extends Type { } @Override public boolean isHigh() { return _t.isHigh(); } - @Override public Type glb() { return make(_alias,_t.glb()); } + @Override public int log_size() { throw Utils.TODO(); } + @Override public Type glb(boolean mem) { return make(_alias,_t.glb(true)); } @Override int hash() { return 9876543 + _alias + _t.hashCode(); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 98e92bca..34033119 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -28,25 +28,29 @@ public class TypeMemPtr extends TypeNil { // Deep read-only access through this pointer; independent of slot finality. public boolean _ro; + public final boolean _one; // Singleton instance - private TypeMemPtr(byte nil, TypeStruct obj) { + private TypeMemPtr(byte nil, TypeStruct obj, boolean singleton) { super(TMEMPTR,nil); assert obj!=null; _obj = obj; _ro = obj==TypeStruct.BOT; + _one = singleton; } - static TypeMemPtr make(byte nil, TypeStruct obj) { return new TypeMemPtr(nil, obj).intern(); } + public static TypeMemPtr make(byte nil, TypeStruct obj, boolean one) { return new TypeMemPtr(nil, obj, one).intern(); } + static TypeMemPtr make(byte nil, TypeStruct obj) { return make(nil, obj, false); } + public static TypeMemPtr make (TypeStruct obj) { return make((byte)2, obj); } public static TypeMemPtr makeNullable(TypeStruct obj) { return make((byte)3, obj); } - public static TypeMemPtr make(TypeStruct obj) { return new TypeMemPtr((byte)2, obj).intern(); } - public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj).withAccess(_ro); } + + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one).withAccess(_ro); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } - @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil,_obj).withAccess(_ro); } + @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one).withAccess(_ro); } @Override public TypeMemPtr makeRO() { return withAccess(true); } @Override public boolean isFinal() { return _ro; } public TypeMemPtr withAccess(boolean ro) { if( _ro==ro ) return this; - TypeMemPtr ptr = new TypeMemPtr(_nil, _obj); + TypeMemPtr ptr = new TypeMemPtr(_nil, _obj, _one); ptr._ro = ro; return ptr.intern(); } @@ -73,15 +77,16 @@ public class TypeMemPtr extends TypeNil { @Override public TypeNil xmeet(Type t) { TypeMemPtr that = (TypeMemPtr) t; - return TypeMemPtr.make(xmeet0(that), (TypeStruct)_obj.meet(that._obj)).withAccess(_ro | that._ro); + return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), _one & that._one).withAccess(_ro | that._ro); } @Override - public TypeMemPtr dual() { return TypeMemPtr.make( dual0(), _obj.dual()).withAccess(!_ro); } + public TypeMemPtr dual() { return make( dual0(), _obj.dual(), !_one).withAccess(!_ro); } // RHS is NIL; do not deep-dual when crossing the centerline @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj).withAccess(_ro); } + @Override public boolean isConstant() { return _one && _obj.isConstant(); } // True if this "isa" t up to named structures @Override public boolean shallowISA( Type t ) { @@ -94,17 +99,17 @@ public class TypeMemPtr extends TypeNil { throw Utils.TODO(); // return _obj.shallowISA(that._obj); } - @Override public TypeMemPtr glb() { return make((byte)3,_obj.glb()).withAccess(true); } + @Override public TypeMemPtr glb(boolean mem) { return make((byte)3,_obj.glb(true)).withAccess(true); } // Is forward-reference @Override public boolean isFRef() { return _obj.isFRef(); } @Override public int log_size() { return 3; } // (1<<3)==8-byte pointers - @Override int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash(); } + @Override int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _ro==ptr._ro && _obj == ptr._obj && super.eq(ptr); + return _ro==ptr._ro && _obj == ptr._obj && _one == ptr._one && super.eq(ptr); } @Override public String str() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/src/main/java/com/seaofnodes/simple/type/TypeNil.java index aee623ba..3902c40b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeNil.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -48,7 +48,7 @@ public abstract class TypeNil extends Type { @Override public boolean isConstant () { return false; } @Override public boolean isHighOrConst() { return isHigh() || isConstant(); } - @Override public Type glb() { return Type.NIL; } + @Override public Type glb(boolean mem) { return Type.NIL; } public boolean notNull() { return _nil==1 || _nil==2; } public boolean nullable() { return _nil==3; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/src/main/java/com/seaofnodes/simple/type/TypePtr.java index e9091c25..d9de5cd7 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -45,7 +45,7 @@ public class TypePtr extends TypeNil { // 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; } + @Override public TypePtr glb(boolean mem) { return PTR; } private static final String[] STRS = new String[]{"~ptr","~nptr","nptr","ptr"}; @Override public String str() { return STRS[_nil]; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 990c5fcf..cde0bc93 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -24,15 +24,18 @@ public class TypeStruct extends Type { // "bottom out" is again the forward-ref struct. public final String _name; public final Field[] _fields; + public final TypeConAry _con; // Optional, constant array contents - TypeStruct(String name, Field[] fields) { + private TypeStruct(String name, TypeConAry con, Field[] fields) { super(TSTRUCT); _name = name; _fields = fields; + _con = con; } // All fields directly listed - public static TypeStruct make(String name, Field... fields) { return new TypeStruct(name, fields).intern(); } + public static TypeStruct make(String name, TypeConAry con, Field... fields) { return new TypeStruct(name, con, fields).intern(); } + public static TypeStruct make(String name, Field... fields) { return make(name, TypeConAry.BOT, fields); } public static final TypeStruct TOP = make("$TOP",new Field[0]); public static final TypeStruct BOT = make("$BOT",new Field[0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); @@ -48,12 +51,16 @@ public class TypeStruct extends Type { } // Array - public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { + public static TypeStruct makeAry(String name, TypeInteger len, int lenAlias, Type body, int bodyAlias) { + return makeAry(name,len,lenAlias,body,bodyAlias,false,TypeConAry.BOT); + } + public static TypeStruct makeAry(String name, TypeInteger len, int lenAlias, Type body, int bodyAlias, boolean efinal, TypeConAry con) { assert body instanceof TypeInteger || body instanceof TypeFloat || (body instanceof TypeNil tn && tn.nullable()); - assert len.isa(TypeInteger.U32); - return make("[" + body.str() + "]", + assert efinal || con==TypeConAry.BOT; // No mutable constant arrays + return make(name, + con, Field.make("#" ,len , lenAlias,true ), - Field.make("[]",body,bodyAlias,false)); + Field.make("[]",body,bodyAlias,efinal)); } // A pair of self-cyclic types @@ -62,9 +69,11 @@ public class TypeStruct extends Type { 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.U32,-1,TypeInteger.BOT,-2); + private static final TypeStruct ARY = makeAry("[i64]",TypeInteger.U32,-1,TypeInteger.BOT,-2); + private static final TypeStruct STR = makeAry("[u8]",TypeInteger.U32,-1,TypeInteger.U8,-2); + private static final TypeStruct HELLO= makeAry("[u8]",TypeInteger.constant(3),-1,TypeInteger.U8,-2,true,TypeConAryB.ABC); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); ts.add(STR); ts.add(HELLO); } // Find field index by name public int find(String fname) { @@ -114,7 +123,8 @@ public class TypeStruct extends Type { return BOT; flds[i] = (Field)f0.meet(f1); } - return make(_name,flds); + TypeConAry con = (TypeConAry)_con.meet(that._con); + return make(_name, con, flds); } @Override @@ -125,22 +135,23 @@ public class TypeStruct extends Type { Field[] flds = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) flds[i] = _fields[i].dual(); - return make(_name,flds); + TypeConAry con = _con.dual(); + return make(_name,con,flds); } // Keeps the same struct, but lower-bounds all fields. - @Override public TypeStruct glb() { - if( _glb() ) return this; + @Override public TypeStruct glb(boolean mem) { + if( _glb(mem) ) 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].glb(); + flds[i] = _fields[i].glb(mem); return make(_name,flds); } - private boolean _glb() { + private boolean _glb(boolean mem) { if( _fields!=null ) for( Field f : _fields ) - if( f.glb() != f ) + if( f.glb(mem) != f ) return false; return true; } @@ -156,10 +167,56 @@ public class TypeStruct extends Type { return true; } + @Override public boolean isConstant() { + int len = _fields.length; + // If we have a constant array, then ignore the last 2 array fields- + // they are effectively constant. + + // Fields are given sizes according to their types at *offset time*. + // And thus layout, packing & padding are determined by the Types + // at *offset-time*, which means *offset-time* has to be picked + // when types are Stable - post/during TypeCheck. + + // The array-length field is shared with other like-sized arrays, so + // you are allowed to mix "abc" and "very_hugh_>256_char_string" and + // the resulting TMP can query the length field (getting 3 or >256 + // respectively), and reading from a prolly 16bit length field. + + // Basically asking: forward-flow declared-types, are these compatible? + // Only array-lengths have an issue here? So internally name fields + // `#0` or `#1` or `#2` or `#3`. + // + // Also means I cannot track exact array length without losing the + // "declared type requires a 4-byte field". + // + // Same-same for all fields in a struct, space in memory is based on + // declared-type at least, possible (future work) optimized where all + // memory versions of the same field get a smaller footprint (or even a + // constant past or moved into prototype) past construction + + if( _con!=TypeConAry.BOT ) len -= 2; + // Check all fields for being constant + for( int i=0; i<len; i++ ) + if( !_fields[i].isConstant() ) + return false; + return true; + } + + // log_size for a struct is not defined, unless its exactly some power of + // 2. *Total size* is well-defined, and is available in the offsets. + @Override public int log_size() { throw Utils.TODO(); } + @Override public int size() { return offset(_fields.length); } + @Override public int alignment() { + int align = 0; + for( Field f : _fields ) + align = Math.max(align, (f._fname!="[]" || _con==TypeConAry.BOT ? f._type : _con).alignment()); + return align; + } + @Override boolean eq(Type t) { TypeStruct ts = (TypeStruct)t; // Invariant - if( !_name.equals(ts._name) ) + if( !_name.equals(ts._name) || _con!=ts._con ) return false; if( _fields == ts._fields ) return true; if( _fields==null || ts._fields==null ) return false; @@ -177,19 +234,17 @@ public class TypeStruct extends Type { if( _fields != null ) for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode(); - return Utils.fold(hash); + return Utils.fold(hash ^ _con.hashCode()); } @Override public SB print(SB sb) { if( this==BOT ) return sb.p("StructBot"); if( this==TOP ) return sb.p("StructTop"); - if( _fields == null ) return sb.p(_name); // Forward reference struct, just print the name - if( isAry() ) { - if( !isFinal() ) sb.p("!"); - return sb.p(_name); // Skip printing generic array fields - } + if( _con!=TypeConAry.BOT ) return sb.p(_con.str()); sb.p(_name); + if( _fields == null || isAry() ) // Forward reference struct, just print the name + return sb.p(isFinal() ? "" : "!"); sb.p(" {"); for( Field f : _fields ) f._type.print(sb).p(f._final ? " " : " !").p(f._fname).p("; "); @@ -204,11 +259,11 @@ public class TypeStruct extends Type { @Override public String str() { if( this==BOT ) return "StructBot"; if( this==TOP ) return "StructTop"; - return _name; + return _con==TypeConAry.BOT ? _name : _con.str(); } - public boolean isAry() { return _fields.length==2 && _fields[1]._fname.equals("[]"); } + public boolean isAry() { return _fields.length>=2 && _fields[_fields.length-1]._fname=="[]"; } public int aryBase() { assert isAry(); @@ -231,14 +286,12 @@ public class TypeStruct extends Type { // Compute a layout for a collection of fields assert _fields != null; // No forward refs - // Array layout is different: len,[pad],body... - if( isAry() ) - return _offs = new int[]{ 0, _fields[1]._type.log_size() < 3 ? 4 : 8 }; - // Compute a layout - int[] cnts = new int[4]; // Count of fields at log field size - for( Field f : _fields ) - cnts[f._type.log_size()]++; // Log size is 0(byte), 1(i16/u16), 2(i32/f32), 3(i64/dbl) + int[] cnts = new int[5]; // Count of fields at log field size + int flen = _fields.length; + if( isAry() ) flen--; // Array field is aligned differently + for( int i=0; i<flen; i++ ) + cnts[_fields[i]._type.log_size()]++; // Log size is 0(byte), 1(i16/u16), 2(i32/f32), 3(i64/dbl) int off = 0, idx = 0; // Base common struct fields go here, e.g. Mark/Klass // Compute offsets to the start of each power-of-2 aligned fields. int[] offs = new int[4]; @@ -249,14 +302,38 @@ public class TypeStruct extends Type { // Assign offsets to all fields. // Really a hidden radix sort. _offs = new int[_fields.length+1]; - for( Field f : _fields ) { - int log = f._type.log_size(); + for( int i=0; i<flen; i++ ) { + int log = _fields[i]._type.log_size(); _offs[idx++] = offs[log]; // Field offset offs[log] += 1<<log; // Next field offset at same alignment cnts[log]--; // Count down, should be all zero at end } - _offs[_fields.length] = (off+7)& ~7; // Round out to max alignment + + // Array bits + if( isAry() ) { + // Pad out to the element alignment + int align = (_fields[flen]._fname!="[]" || _con==TypeConAry.BOT ? _fields[flen]._type : _con).alignment(); + off = (off + ((1<<align)-1)) & -(1<<align); + _offs[flen] = off; + if( _con!=TypeConAry.BOT ) + _offs[flen+1] = off+_con.len(); + } else + _offs[flen] = off; // Max struct size, no trailing padding return _offs; } + // Field order with increasing offset + public int[] layout() { + offset(0); + int len = _offs.length; + int[] is = new int[len]; + for( int i=0; i<len; i++ ) is[i] = i; + // Stoopid hand rolled bubble sort + for( int i=0; i<len; i++ ) + for( int j=i+1; j<len; j++ ) + if( _offs[is[j]] < _offs[is[i]] ) + { int tmp = is[i]; is[i] = is[j]; is[j] = tmp; } + return is; + } + } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index d3b19b52..bc57871a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; import java.util.ArrayList; public class TypeTuple extends Type { @@ -48,11 +49,10 @@ public class TypeTuple extends Type { return make(ts); } - @Override - public Type glb() { + @Override public Type glb(boolean mem) { Type[] ts = new Type[_types.length]; for( int i=0; i<_types.length; i++ ) - ts[i] = _types[i].glb(); + ts[i] = _types[i].glb(mem); return make(ts); } @@ -63,12 +63,13 @@ public class TypeTuple extends Type { return true; } - @Override public int log_size() { + @Override public int log_size() { throw Utils.TODO(); } + @Override public int alignment() { assert isConstant(); - int log_size = 0; + int align = 0; for( Type t : _types ) - log_size = Math.max(log_size,t.log_size()); - return log_size; + align = Math.max(align,t.alignment()); + return align; } public Type ret() { assert _types.length==3; return _types[2]; } diff --git a/src/main/smp/sys.smp b/src/main/smp/sys.smp new file mode 100644 index 00000000..ede08d63 --- /dev/null +++ b/src/main/smp/sys.smp @@ -0,0 +1,57 @@ +// -*- mode: java; -*- + +// top-level default import +struct sys { + // libc bindings + /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */ + struct libc { + i32 errno = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } write = "C"; + // fd buf len -> len + { i32 i64 u32 -> u32 } read = "C"; + // status + { i32 -> i32 } _exit = "C"; + // addr len prot flags fd off -> void* + { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; + // mmap flags + i32 PROT_EXEC = 4; + i32 PROT_READ = 1; + i32 PROT_WRITE= 2; + i32 PROT_NONE = 0; + i32 MAP_PRIVATE = 2; + i32 MAP_ANON = 32; + }; + struct ary { + val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + for( int i=0; i<len; i++ ) + dst[i+doff] = src[i+soff]; + return dst; + }; + }; + struct io { + // Print string to stdout + val p = { u8[~] str -> + i64 ptr = str; // cast array base to i64 + return sys.libc.write(1,ptr,str#); + }; + + // Return stdin as a u8[] + val stdin = { -> + var buf = new u8[8*1024]; + i64 ptr = buf; + int len = 0; + while( true ) { + int rez = sys.libc.read(0,ptr,buf#); + if( rez < 0 ) sys.libc._exit(sys.libc.errno); + len += rez; + if( rez < buf# ) + break; + sys.libc._exit(-2); // Need to implement + } + // Compress + var dst = new u8[len]; + return sys.ary.copy(dst,0,buf,0,len); + }; + }; +}; diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index aa6fada0..9f626805 100644 --- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -20,7 +20,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 146, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 28, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; @@ -28,7 +28,7 @@ public class BrainFuckTest { for( int i=0; i<brain_fuck.length(); i++ ) assertEquals(brain_fuck.charAt(i), R5.ld1z(ptr+4+i)); - EvalArm64 A5 = TestArm64.build("brain_fuck", 0, 34, false); + EvalArm64 A5 = TestArm64.build("brain_fuck", 0, 28, false); int trap_arm = A5.step(100000); assertEquals(0,trap_arm); assertEquals(0,trap); diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index cddbdfcf..ac9adacc 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -25,9 +25,9 @@ public class Chapter01Test { public void testZero() { CodeGen code = new CodeGen("return 0;"); code.parse(); - for( Node use : code._start._outputs ) - if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) - assertEquals(TypeInteger.constant(0),con._type); + Node use = code.expr(); + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) + assertEquals(TypeInteger.constant(0),con._type); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 401f346f..551880b1 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -128,14 +128,14 @@ while(v1+arg) { } """); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("Stop[ ]", code.print()); // No explicit return: omit default main. } @Test public void testWhile0() { - CodeGen code = new CodeGen("while(0) continue; if(0) arg=0;"); + CodeGen code = new CodeGen("while(0) continue; if(0) arg=0; return arg;"); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("return arg;", code.print()); } @Test @@ -145,6 +145,7 @@ if(0) while(0) { int arg=arg; while(0) {} } +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); @@ -209,7 +210,7 @@ return -0+0+0; public void testFuzz3() { CodeGen code = new CodeGen("int v0=0; while(0==69) while(v0) return 0;"); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("Stop[ ]", code.print()); // The only return is unreachable. } @Test @@ -255,7 +256,7 @@ while(0==1) while(v0) v0=1+v0; """); code.parse().opto(); - assertEquals("return 0;", code.print()); + assertEquals("Stop[ ]", code.print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 91505f41..bcb73eb9 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -362,6 +362,7 @@ if(0) { v0=v2; } } +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); @@ -436,6 +437,7 @@ while(0) {} } } } } +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 0b4ad8ec..d8b072a2 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -132,15 +132,15 @@ return n.i; @Test public void testNullRef4() { - CodeGen code = new CodeGen("-null-5/null-5;"); + CodeGen code = new CodeGen("return -null-5/null-5;"); try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } } @Test public void testNullRef5() { CodeGen code = new CodeGen("return null+42;"); try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } } @Test @@ -148,6 +148,7 @@ return n.i; CodeGen code = new CodeGen( """ struct S{}; +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index f0fe7dcd..c342eeed 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -176,7 +176,7 @@ while(v1) break; return v1; """); code.parse().opto(); - assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", code.print()); + assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", code.print()); assertEquals("1", Eval2.eval(code, 0)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index cb92277f..074cd8ba 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -255,10 +255,10 @@ return new flt; public void testBad1() { CodeGen code = new CodeGen( """ -int is = new int[2]; +flt is = new int[2]; """); try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Type *[int] is not of declared type int",e.getMessage()); } + catch( Exception e ) { assertEquals("Type *[int] is not of declared type flt",e.getMessage()); } } @Test @@ -325,6 +325,7 @@ while(0) {} u32 v7=0; int v8=0; while(0<--1>>>---(v7*0==v8)) {} +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); @@ -349,6 +350,7 @@ else { } } } +return 0; """); code.parse().opto(); assertEquals("return 0;", code.print()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 7c0af028..6eb4d6f4 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -140,7 +140,7 @@ while(arg--) { } return a; """); - code.parse().opto().typeCheck().GCM(); + code.parse().opto().typeCheck(); assertEquals("return Phi(Loop,1,Phi(Loop,2,Phi_a));", code._stop.toString()); assertEquals("1", Eval2.eval(code, 0)); assertEquals("2", Eval2.eval(code, 1)); @@ -185,7 +185,7 @@ var sq = { int x -> return sq(arg)+sq(3); """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return (#2+#2); return (Parm_x(sq,int)*x); ]", code._stop.toString()); + assertEquals("Stop[ return (Parm_x(sq,int)*x); return (#2+#2); ]", code._stop.toString()); assertEquals("13", Eval2.eval(code, 2)); } @@ -223,7 +223,7 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(3); """); code.parse().opto(); - assertEquals("Stop[ return #2; return (Parm_x($fun1,int,3)*x); return (Parm_x($fun2,int,3)<<1); ]", code._stop.toString()); + assertEquals("Stop[ return (Parm_x($fun2,int,3)<<1); return (Parm_x($fun1,int,3)*x); return #2; ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } @@ -233,7 +233,7 @@ return fcn(3); public void testFcn5() { CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); code.parse().opto().typeCheck(); - assertEquals("Stop[ return #2; return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*#2)); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*#2)); return #2; ]", code._stop.toString()); assertEquals( "1", Eval2.eval(code, 0)); assertEquals( "1", Eval2.eval(code, 1)); assertEquals( "2", Eval2.eval(code, 2)); @@ -265,7 +265,7 @@ val g = {->2;}; return 2; """); code.parse().opto().typeCheck().GCM(); - assertEquals("Stop[ return 1; return 1; return 2; ]", code._stop.toString()); + assertEquals("Stop[ return 2; return 1; return 1; ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 0)); } @@ -283,7 +283,7 @@ for(;;) { } """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return #2; return Parm_i(x,int); ]", code._stop.toString()); + assertEquals("Stop[ return Parm_i(x,int); return #2; ]", code._stop.toString()); assertEquals("3", Eval2.eval(code, 0)); } @@ -321,7 +321,7 @@ val fcn = { !Person?[] !ps, int x -> var ps = new !Person?[2]; ps[0] = new Person; ps[1] = new Person; -fcn(ps,1); +return fcn(ps,1); """); code.driver(Phase.LocalSched); assertEquals("return 0;", code._stop.toString()); @@ -356,6 +356,7 @@ for(;;) { if (i2i(2) == arg) break; i2i = null; } +return 0; """); try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Might be null calling { int -> int #1}?",e.getMessage()); } @@ -454,7 +455,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(o,int); ]", code._stop.toString()); + assertEquals("Stop[ return Parm_i(i2i.o,int); return Phi(Region,#2,1); ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/src/test/java/com/seaofnodes/simple/Chapter19Test.java index c53a8e11..4564e513 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -22,7 +22,7 @@ public class Chapter19Test { con.toString(); org.junit.Assert.assertNull(call.name()); - var fun = new FunNode(null,tfp); + var fun = new FunNode(null,tfp,"printerTarget"); fun._name = "printerTarget"; fun.addDef(code._start); code.link(fun); @@ -295,6 +295,7 @@ for( int i=0; i<A#; i++ ) A[i] = i; for( int i=0; i<A#; i++ ) B[i] += A[i]; +return 0; """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return 0;", code.print()); @@ -339,7 +340,7 @@ val fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun1,int),x); return (shli,Parm_x($fun2,int)); ]", code.print()); + assertEquals("Stop[ return (shli,Parm_x($fun2,int)); return (mul,Parm_x($fun1,int),x); return (add,#2,(muli,#2)); ]", code.print()); } @Test @@ -350,7 +351,7 @@ val sq = { int x -> x*x; }; return sq(arg) + sq(3); """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print()); + assertEquals("Stop[ return (mul,Parm_x(sq,int),x); return (add,#2,#2); ]", code.print()); } @Test public void testSelectedMemory() { diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index e63fb32e..3575e461 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; @@ -76,6 +78,7 @@ return f(s); @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector(); + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } @@ -104,9 +107,8 @@ return f(s); } static void testCPU(String src, String cpu, String os, int spills, String stop) { - CodeGen code = new CodeGen(src); + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); - com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); SpillStats.record(code,"Chapter20",cpu,os); SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop!=null ) assertEquals(stop,code._stop.toString()); @@ -146,7 +148,7 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"x86_64_v2", "SystemV",40,null); testTarget(src,"riscv" , "SystemV",17,null); testTarget(src,"arm" , "SystemV",18,null); } @@ -175,9 +177,9 @@ return sqrt(farg) + sqrt(farg+2.0); @Test public void testAlloc2() { String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; - testTarget(src,"x86_64_v2","SystemV",4,"return .[];"); - testTarget(src,"riscv","SystemV",8,"return .[];"); - testTarget(src,"arm","SystemV",9,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"riscv","SystemV",6,"return .[];"); + testTarget(src,"arm","SystemV",6,"return .[];"); } @Test @@ -193,7 +195,7 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testTarget(src,"x86_64_v2", "SystemV",7,"return .[];"); + testTarget(src,"x86_64_v2", "SystemV",5,"return .[];"); testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } @@ -236,9 +238,14 @@ s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testTarget(src,"x86_64_v2", "SystemV",15,null); - testTarget(src,"riscv" , "SystemV", 10,null); - testTarget(src,"arm" , "SystemV", 10,null); + // Without an explicit return, default main must be removed completely. + // Seed 0 previously left a loop with a missing branch successor. + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + new CodeGen(src,com.seaofnodes.simple.type.TypeInteger.BOT,0) + .driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + testTarget(src,"x86_64_v2", "SystemV",0,null); + testTarget(src,"riscv" , "SystemV",1,null); + testTarget(src,"arm" , "SystemV",0,null); } @Test @@ -339,8 +346,8 @@ for( int pc = 0; pc < program#; pc++ ) { return output; """; testTarget(src,"x86_64_v2", "SystemV",40,null); - testTarget(src,"riscv" , "SystemV",146,null); - testTarget(src,"arm" , "SystemV",34,null); + testTarget(src,"riscv" , "SystemV",28,null); + testTarget(src,"arm" , "SystemV",28,null); //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. diff --git a/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java index bc300217..b81483d8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -21,7 +21,7 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,23,null); + Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,40,null); Chapter21Test.testCPU(src,"riscv" , "SystemV",19,null); Chapter21Test.testCPU(src,"arm" , "SystemV",19,null); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/src/test/java/com/seaofnodes/simple/Chapter21Test.java index a51ae3bc..2c91de0d 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -4,6 +4,7 @@ import com.seaofnodes.isa.eval.EvalRisc5; import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -103,39 +104,6 @@ public class Chapter21Test { } - @Test public void testNarrowStores() throws IOException { - for( String type : new String[]{"i8","u8","i16","u16"} ) { - String src = "struct S { "+type+" x; }; !S !s = new S; s.x = arg; return 0;"; - CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); - int stores=0; - for( var bb : code._cfg ) - for( var node : bb.outs() ) - if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { - stores++; - assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); - } - assertEquals(1,stores); - byte[] image = new byte[1<<20]; - byte[] bits = code._encoding.bits(); - System.arraycopy(bits,0,image,0,bits.length); - EvalRisc5 cpu = new EvalRisc5(image,1<<16); - cpu.regs[riscv.A0] = 0x8765; - assertEquals(0,cpu.step(100)); - assertEquals(type.endsWith("8") ? 0x65 : 0x8765, - type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); - code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); - stores=0; - for( var bb : code._cfg ) - for( var node : bb.outs() ) - if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { - stores++; - assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); - } - assertEquals(1,stores); - } - } - - @Test public void testArmCallInstructions() { EvalArm64 cpu = new EvalArm64(new byte[512],256); for( int delta : new int[]{4,32,-4} ) { @@ -238,6 +206,52 @@ public class Chapter21Test { } + @Test public void testNarrowStores() throws IOException { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + String src = "struct S { "+type+" x; }; !S !s = new S; s.x = arg; return 0;"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { + stores++; + assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); + } + assertEquals(1,stores); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu.regs[riscv.A0] = 0x8765; + assertEquals(0,cpu.step(100)); + assertEquals(type.endsWith("8") ? 0x65 : 0x8765, + type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); + code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); + stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + @Test public void testNativeExitStatus() throws IOException { + Path source = Path.of("build/objs/nativeExit.c"); + Files.createDirectories(source.getParent()); + Files.writeString(source,"int main() { return 7; }\n"); + try { + TestC.gcc(source.toString(),null,null,false, + "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : "")); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Program exit status")); + return; + } + fail("A failing native program must fail the test, even with empty stdout"); + } + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } @Test public void testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); } @Test public void testRisc64BitStore() { @@ -278,8 +292,7 @@ public class Chapter21Test { } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); SpillStats.record(code,"Chapter21",cpu,os); SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) @@ -422,7 +435,7 @@ public class Chapter21Test { @Test public void testPerson() throws IOException { String person = "6\n"; - TestC.run("person", person, 0); + TestC.run("person21", person, 0); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start @@ -433,7 +446,7 @@ public class Chapter21Test { int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build("person", ps, 0, false); + EvalRisc5 R5 = TestRisc5.build("person21", ps, 0, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -449,7 +462,7 @@ public class Chapter21Test { assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("person", ps, 0, false); + EvalArm64 A5 = TestArm64.build("person21", ps, 0, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); diff --git a/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/src/test/java/com/seaofnodes/simple/Chapter22Test.java new file mode 100644 index 00000000..2d94b8f0 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -0,0 +1,411 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.isa.eval.EvalArm64; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; +import com.seaofnodes.simple.codegen.CodeGen; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; + +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import org.junit.Ignore; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter22Test { + + @Test public void testNarrowCReturnsEmulated() { + String[] types = {"i8","u8","i16","u16","i32","u32","int"}; + long[] values = {0xa5a5a5a500000000L,0xa5a5a5a50000007fL,0xa5a5a5a500000080L, + 0xa5a5a5a500007fffL,0xa5a5a5a500008000L,0xa5a5a5a57fffffffL, + 0xa5a5a5a580000000L,0xa5a5a5a5ffffffffL}; + for( String target : new String[]{"arm","riscv"} ) + for( int i=0; i<types.length; i++ ) { + String src = "{"+types[i]+"} c_narrow=\"C\"; return c_narrow();"; + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,target,"SystemV"); + var enc = code._encoding; + // Link the external call to a tiny independent native stub. + var call = code._stop.walk(n -> n instanceof com.seaofnodes.simple.node.CallNode ? n : null); + int start = enc._opStart[call._nid]; + ((com.seaofnodes.simple.codegen.RIPRelSize)call).patch(enc,start,enc._opLen[call._nid],0x1000-start); + for( long value : values ) { + long expected = switch(i) { + case 0 -> (byte)value; case 1 -> value&255; + case 2 -> (short)value; case 3 -> value&65535; + case 4 -> (int)value; case 5 -> value&0xffffffffL; + default -> value; + }; + byte[] image = new byte[1<<16]; + byte[] bits = enc.bits(); + System.arraycopy(bits,0,image,0,bits.length); + if( target.equals("arm") ) { + EvalArm64 cpu = new EvalArm64(image,1<<15); + // MOVZ X0,0x1100; LDR X0,[X0]; RET X30. + cpu._pc = enc._opStart[code.link(code._main)._nid]; + cpu.st4(0x1000,0xd2822000); cpu.st4(0x1004,0xf9400000); + cpu.st4(0x1008,0xd65f03c0); + cpu.st8(0x1100,value); + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + assertEquals(types[i],expected,cpu.regs[0]); + } else { + EvalRisc5 cpu = new EvalRisc5(image,1<<15); + // AUIPC a0,0; LD a0,12(a0); RET. + cpu._pc = enc._opStart[code.link(code._main)._nid]; + cpu.st4(0x1000,0x00000517); cpu.st4(0x1004,0x00c53503); + cpu.st4(0x1008,0x00008067); + // RV64 widens even u32 returns by sign-extending bit 31. + cpu.st8(0x100c,i==6 ? value : (int)expected); + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + assertEquals(types[i],expected,cpu.regs[riscv.A0]); + } + } + } + } + + @Test public void testNarrowCReturns() throws IOException { + String src = """ + {i8} c_i8="C"; {u8} c_u8="C"; + {i16} c_i16="C"; {u16} c_u16="C"; + {i32} c_i32="C"; {u32} c_u32="C"; + {int} c_i64="C"; + val test_i8={->return c_i8();}; + val test_u8={->return c_u8();}; + val test_i16={->return c_i16();}; + val test_u16={->return c_u16();}; + val test_i32={->return c_i32();}; + val test_u32={->return c_u32();}; + val test_i64={->return c_i64();}; + val test_cmp={->return c_i32()==-1;}; + """; + for( String conv : new String[]{"SystemV","Win64"} ) + TestC.run(src,conv,conv.equals("SystemV") ? "sysv_abi" : "ms_abi", + "src/test/java/com/seaofnodes/simple/progs/c_returns.c", + "build/objs/c_returns"+conv,"S","",-1); + } + + + + @Test public void testReturnedFunctions() throws IOException { + for( String src : new String[]{"return {->42;};", "val f={->42;}; return f;", "return sys.io.p;"} ) + for( String target : new String[]{"riscv","arm"} ) { + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,target,"SystemV").exportELF(null); + byte[] image = new byte[1<<16]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + boolean library = src.contains("sys.io.p"); + // u8[]: four-byte length followed by its bytes. + image[0x2000]=2; image[0x2004]='o'; image[0x2005]='k'; + int entry = code._encoding._opStart[code.link(code._main)._nid]; + if( target.equals("riscv") ) { + EvalRisc5 cpu = new EvalRisc5(image,1<<15); + cpu._pc = entry; + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + cpu._pc = (int)cpu.regs[riscv.A0]; // Call the returned address. + cpu.regs[riscv.A0] = 0x2000; + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + if( library ) assertEquals("ok",cpu._stdout.toString()); + else assertEquals(42,cpu.regs[riscv.A0]); + } else { + EvalArm64 cpu = new EvalArm64(image,1<<15); + cpu._pc = entry; + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + cpu._pc = (int)cpu.regs[0]; + cpu.regs[0] = 0x2000; + assertEquals(0,cpu.step(1000)); + assertEquals(0,cpu._pc); + if( library ) assertEquals("ok",cpu._stdout.toString()); + else assertEquals(42,cpu.regs[0]); + } + } + CodeGen unused = new CodeGen("({->42;}); return 0;").parse().opto(); + assertEquals(1,unused._stop.nIns()); + } + + @Test public void testReturnedFunctionsNative() throws IOException { + String src = "val factory={int x -> if(x) return {->42;}; return {->43;};}; val printer={->return sys.io.p;};"; + String obj = "build/objs/funptr.o"; + new CheckedCodeGen(src).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,obj); + assertEquals("ok",TestC.gcc(obj,"","src/test/java/com/seaofnodes/simple/progs/funptr.c",false, + "build/objs/funptr"+(TestC.OS.startsWith("Windows") ? ".exe" : ""))); + } + + @Test public void testRiscvRightShifts() { + // SRAI, SRLI, SRA, SRL: a0 = -32 shifted by 4. + int[] ops = {0x40455513,0x00455513,0x40b55533,0x00b55533}; + for( int i=0; i<ops.length; i++ ) { + EvalRisc5 r5 = new EvalRisc5(new byte[1<<16],1<<15); + r5.st4(0,ops[i]); + r5.regs[riscv.A0] = -32; + r5.regs[riscv.A0+1] = 4; + assertEquals(0,r5.step(1)); + assertEquals((i&1)==0 ? -2L : 0x0fff_ffff_ffff_fffeL,r5.regs[riscv.A0]); + } + } + + @Test public void testRiscvPointerRelocation() { + CodeGen code = new CheckedCodeGen("return \"x\";").driver(CodeGen.Phase.Encoding,"riscv","SystemV"); + var enc = code._encoding; + assertEquals(1,enc._bigCons.size()); + var ptr = (com.seaofnodes.simple.node.cpus.riscv.TMPRISC)enc._bigCons.keySet().iterator().next(); + int start = enc._opStart[ptr._nid]; + for( int delta : new int[]{0x7ff,0x800,0xfff,0x1000,0x1800,-1,-0x800,-0x801} ) { + ptr.patch(enc,start,enc._opLen[ptr._nid],delta); + // Place the program above zero so backward targets are valid addresses. + byte[] image = new byte[1<<16]; + System.arraycopy(enc.bits(),0,image,0x4000,enc._bits.size()); + EvalRisc5 r5 = new EvalRisc5(image,1<<15); + r5._pc = 0x4000; + assertEquals(0,r5.step(100)); + assertEquals(0x4000+start+delta,r5.regs[riscv.A0]); + } + } + + @Test public void testSubZeroTypeError() { + try { + new CodeGen("return null-0;").parse().opto().typeCheck(); + fail("Subtraction must reject null even when the other operand is zero"); + } catch( Parser.ParseException e ) { + assertEquals("Cannot '-' null",e.getMessage()); + } + } + + @Test public void testInfiniteReturn() { + String src = "struct S { int i; }; !S !s = new S; while(1) s.i++; return s.i;"; + testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); + testCPU(src,"riscv","SystemV",0,"return Top;"); + testCPU(src,"arm","SystemV",0,"return Top;"); + } + + + @Test @Ignore + public void testJig() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); + //String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); + testCPU(src,"x86_64_v2", "Win64" ,-1,null); + testCPU(src,"riscv" , "SystemV",-1,null); + testCPU(src,"arm" , "SystemV",-1,null); + } + + static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + SpillStats.record(code,"Chapter22",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + if( stop != null ) + assertEquals(stop, code._stop.toString()); + return code; + } + + + static int testCPUSize( String src, String cpu, String os, int spills, String stop ) { + return testCPU(src,cpu,os,spills,stop)._encoding._bits.size(); + } + + // Should not fold away + @Test public void testSextFail() throws IOException { + String src = """ +struct Person { i32 age;}; +!Person !p = new Person; +p.age = (arg<<17)>>17; +return 0; +"""; + assertEquals(46, testCPUSize(src, "x86_64_v2","Win64",2,"return 0;")); + assertEquals(60, testCPUSize(src, "riscv","SystemV",4,"return 0;")); + assertEquals(56, testCPUSize(src, "arm","SystemV",4,"return 0;")); + + // do assertEquals here + EvalRisc5 R5 = TestRisc5.build("sext_str_not_fold_away", 0, 4, false); + int trap = R5.step(100); + assertEquals(0,trap); + + EvalArm64 A5 = TestArm64.build("sext_str_not_fold_away", 0, 4, false); + trap = A5.step(100); + assertEquals(0,trap); + + } + + // Should not fold away + @Test public void testSextFail2() throws IOException { + String src = """ + + struct Person { i32 age;}; + !Person !p = new Person; + p.age = (arg<<48)>>48; + return 0; + """; + + EvalRisc5 R5 = TestRisc5.build("sext_str_not_fold_away_2", 0, 4, false); + int trap = R5.step(100); + assertEquals(0,trap); + + EvalArm64 A5 = TestArm64.build("sext_str_not_fold_away_2", 0, 4, false); + int trap_arm = A5.step(100); + assertEquals(0,trap_arm); + + assertEquals(46, testCPUSize(src, "x86_64_v2","Win64",2,"return 0;")); + assertEquals(60, testCPUSize(src, "riscv","SystemV",4,"return 0;")); + assertEquals(56, testCPUSize(src, "arm","SystemV",4,"return 0;")); + + } + + // Should fold away + @Test public void testSextSuccess() throws IOException { + String src = """ +// Should fold away sign extend +struct Person { i8 age;}; +!Person !p = new Person; +p.age = (arg<<48)>>48; +return 0; + """; + + EvalRisc5 R5 = TestRisc5.build("sext_str_fold_away", 0, 5, false); + int trap = R5.step(100); + assertEquals(0,trap); + + EvalArm64 A5 = TestArm64.build("sext_str_fold_away", 0, 5, false); + int trap_arm = A5.step(100); + assertEquals(0,trap_arm); + + assertEquals(41, testCPUSize(src, "x86_64_v2","Win64",2,"return 0;")); + assertEquals(56, testCPUSize(src, "riscv","SystemV",5,"return 0;")); + assertEquals(52, testCPUSize(src, "arm","SystemV",5,"return 0;")); + // do assertEquals here + } + + + // Int now is changed to 4 bytes. + @Test public void testPerson() throws IOException { + String person = "6\n"; + TestC.run("person", person, 0); + + // Memory layout starting at PS: + int ps = 1<<16; // Person array pointer starts at heap start + // Person[3] = { len,pad,P0,P1,P2 }; // sizeof = 4*8 + // P0 = { age } // sizeof=8 + int p0 = ps+4*8+0*8; + // P1 = { age } // sizeof=8 + int p1 = ps+4*8+1*8; + // P2 = { age } // sizeof=8 + int p2 = ps+4*8+2*8; + EvalRisc5 R5 = TestRisc5.build("person", ps, 0, false); + R5.regs[riscv.A1] = 1; // Index 1 + R5.st8(ps,3); // Length + R5.st8(ps+1*8,p0); + R5.st8(ps+2*8,p1); + R5.st8(ps+3*8,p2); + R5.st8(p0, 5); // age= 5 + R5.st8(p1,17); // age=17 + R5.st8(p2,60); // age=60 + + int trap = R5.step(100); + assertEquals(0,trap); + assertEquals( 5+0,R5.ld8(p0)); + assertEquals(17+1,R5.ld8(p1)); + assertEquals(60+0,R5.ld8(p2)); + + EvalArm64 A5 = TestArm64.build("person", ps, 0, false); + A5.regs[arm.X1] = 1; // Index 1 + A5.st8(ps, 3); + A5.st8(ps+1*8,p0); + A5.st8(ps+2*8,p1); + A5.st8(ps+3*8,p2); + A5.st8(p0, 5); // age= 5 + A5.st8(p1,17); // age=17 + A5.st8(p2,60); // age=60 + + int trap_arm = A5.step(100); + assertEquals(0,trap_arm); + assertEquals( 5+0, A5.ld8(p0)); + assertEquals(17+1, A5.ld8(p1)); + assertEquals(60+0, A5.ld8(p2)); + } + + @Test + public void testCoRecur() { + String src = """ +struct A { !B? !b; !C? !c; i64 ax; val az = x*2; }; +struct B { !A? !a; !C? !c; f32 bx; val bz = x*3; }; +struct C { !A? !a; !B? !b; f64 cx; val cz = x*x; }; +!A !aa = new A{ ax=17; }; +!B !bb = new B{ bx=3.14; a = aa; }; +!C !cc = new C{ cx=2.73; a = aa; b = bb; }; +aa.b = bb; +aa.c = cc; +bb.c = cc; +val x = 5; // aa.az; // Error to self-define forward ref +return cc.cz; +"""; + CodeGen code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals("return 25;", code._stop.toString()); + assertEquals("25", Eval2.eval(code, 0)); + } + + @Test + public void testHelloWorld() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/helloWorld.smp")); + TestC.run(src,TestC.CALL_CONVENTION,null,null,"build/objs/helloWorld","","Hello, World!",0); + + // Evaluate on RISC5 emulator + EvalRisc5 R5 = TestRisc5.build("helloWorld", 0, 2, false); + int trap = R5.step(100); + assertEquals(0,trap); + assertEquals(0,R5.regs[riscv.A0]); + assertEquals("Hello, World!",R5._stdout.toString()); + + // Evaluate on ARM emulator + EvalArm64 arm = TestArm64.build("helloWorld", 0, 2, false); + trap = arm.step(100); + assertEquals(0,trap); + assertEquals(0,arm.regs[0]); + assertEquals("Hello, World!",arm._stdout.toString()); + } + + @Test + public void testFinalArray() { + String src = """ +int N=4; +i32[] !is = new i32[N]; +for( int i=0; i<N; i++ ) + is[i] = i*i; +val sum = { i32[~] is -> // final array + int sum=0; + for( int i=0; i<is#; i++ ) + sum += is[i]; + return sum; +}; +return sum(is); +"""; + CodeGen code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals("return Phi(Loop,0,(Phi_sum+.[]));", code._stop.toString()); + assertEquals("14", Eval2.eval(code, 0)); + } + + + @Test @Ignore + public void testEcho() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/echo.smp")); + TestC.run(src,TestC.CALL_CONVENTION,null,null,"build/objs/echo","","",0); + + // Evaluate on RISC5 emulator + EvalRisc5 R5 = TestRisc5.build("echo", 0, 2, false); + int trap = R5.step(100); + assertEquals(0,trap); + assertEquals(0,R5.regs[riscv.A0]); + + // Evaluate on ARM emulator + EvalArm64 arm = TestArm64.build("echo", 0, 2, false); + trap = arm.step(100); + assertEquals(0,trap); + assertEquals(0,arm.regs[0]); + } + + +} diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java index a855350e..bbf88f1a 100644 --- a/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -114,12 +114,10 @@ public abstract class Eval2 { public static String eval( CodeGen code, long arg ) { return eval(code,arg,1000); } public static String eval( CodeGen code, long arg, int timeout ) { + if( code._start.uctrl()==null ) return ""; // The empty program SB trace = null; // new SB(); // TRACE, set to null for off, new SB() for on // Force local scheduling phase - if( code._phase.ordinal() < CodeGen.Phase.TypeCheck .ordinal() ) code.typeCheck(); - if( code._phase.ordinal() < CodeGen.Phase.LoopTree .ordinal() ) code.loopTree(); - if( code._phase.ordinal() < CodeGen.Phase.Schedule .ordinal() ) code.GCM(); - if( code._phase.ordinal() < CodeGen.Phase.LocalSched.ordinal() ) code.localSched(); + code.driver(CodeGen.Phase.LocalSched); // Set global, so don't have to pass everywhere CODE = code; @@ -300,9 +298,9 @@ public abstract class Eval2 { // Fetch without unboxing, searching up-Frame static Object val( Node n ) { return F.get(n); } // Fetch and unbox as primitive long - static long x( Node n ) { Object d = F.get(n); return d==null ? 0 : (Long) F.get(n); } + static long x( Node n ) { Object d = F.get(n); return d==null ? 0 : (Long)d; } // Fetch and unbox as primitive double - static double d( Node n ) { Object d = F.get(n); return d==null ? 0 : (Double)F.get(n); } + static double d( Node n ) { Object d = F.get(n); return d==null ? 0 : (Double)d; } // Fetch and unbox a function constant static TypeFunPtr tfp(Node n) { return (TypeFunPtr)F.get(n); } // Fetch and unbox a closure @@ -358,10 +356,19 @@ public abstract class Eval2 { } private static Object load( LoadNode ld ) { - TypeMemPtr tmp = (TypeMemPtr)ld.ptr()._type; - Object[] fs = (Object[])val(ld.ptr()); + Object f = val(ld.ptr()); + // Check for dense constant array + if( f instanceof TypeMemPtr tmp ) { + assert tmp._obj._con != TypeConAry.BOT; + if( ld._name.equals("#") ) + return (long)tmp._obj._con.len(); + int idx = offToIdx(x(ld.off()),tmp._obj); + return tmp._obj._con.at(idx); + } + Object[] fs = (Object[])f; if( ld._name.equals("#") ) return (long)fs.length; + TypeMemPtr tmp = (TypeMemPtr)ld.ptr()._type; int idx = tmp._obj.isAry() ? offToIdx(x(ld.off()),tmp._obj) : tmp._obj.find(ld._name); diff --git a/src/test/java/com/seaofnodes/simple/LiteralTest.java b/src/test/java/com/seaofnodes/simple/LiteralTest.java new file mode 100644 index 00000000..2375f213 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/LiteralTest.java @@ -0,0 +1,65 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.TypeConAryB; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; +import org.junit.Test; +import static org.junit.Assert.*; + +public class LiteralTest { + private static final String[] ESCAPES = {"\\0", "\\n", "\\t", "\\r", "\\\\", "\\\"", "\\'"}; + private static final int[] VALUES = {0, 10, 9, 13, 92, 34, 39}; + + @Test public void testStringEscapes() { + for (int i = 0; i < ESCAPES.length; i++) + assertString(ESCAPES[i], new byte[]{(byte)VALUES[i]}); + assertString("a\\\"b\\\\c\\0d", new byte[]{97, 34, 98, 92, 99, 0, 100}); + assertString("", new byte[]{}); + assertString("plain", new byte[]{112, 108, 97, 105, 110}); + } + + private static void assertString(String text, byte[] expected) { + var code = new CodeGen("return \"" + text + "\";").parse().opto().typeCheck(); + TypeMemPtr ptr = (TypeMemPtr)code.expr()._type; + TypeConAryB bytes = (TypeConAryB)ptr._obj._con; + assertArrayEquals(text, expected, bytes._ary); + } + + @Test public void testCharacterEscapes() { + for (int i = 0; i < ESCAPES.length; i++) + assertCharacter(ESCAPES[i], VALUES[i]); + assertCharacter("A", 65); + } + + private static void assertCharacter(String text, int expected) { + var code = new CodeGen("return '" + text + "';").parse().opto().typeCheck(); + assertEquals(text, expected, ((TypeInteger)code.expr()._type).value()); + } + + @Test public void testMalformedStrings() { + assertBadLiteral("return \"\\q\";", "Unknown string escape"); + assertBadLiteral("return \"abc", "Unclosed string"); + assertBadLiteral("return \"abc\\", "Unclosed string"); + // The quote closes the string at EOF; the missing token is the semicolon. + assertBadLiteral("return \"plain\"", ";"); + } + + @Test public void testMalformedCharacters() { + assertBadLiteral("return '\\q';", "Unknown character escape"); + assertBadLiteral("return '", "Unclosed character"); + assertBadLiteral("return '\\", "Unclosed character"); + assertBadLiteral("return '';", "Syntax error"); + assertBadLiteral("return 'ab';", "Syntax error"); + assertBadLiteral("return 'a", "Syntax error"); + } + + private static void assertBadLiteral(String src, String message) { + try { + new CodeGen(src).parse(); + fail("Accepted malformed literal: " + src); + } catch (Parser.ParseException e) { + assertTrue(e.getMessage(), e.getMessage().contains(message)); + } + } +} diff --git a/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index 1ce2cd34..4bd36256 100644 --- a/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -9,6 +9,7 @@ import com.seaofnodes.simple.codegen.RegAllocTestSupport; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; +import com.seaofnodes.simple.type.TypeMemPtr; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; @@ -152,8 +153,9 @@ public class MemoryEncodingTest { assertNotNull(code._stop.walk(n -> { if( n instanceof MemMergeNode mem && mem.in(0) instanceof CProjNode exit && exit.in(0) instanceof NeverNode ) { - assertTrue(mem.alias(2) instanceof MemPhiNode); - assertTrue(mem.alias(3) instanceof MemPhiNode); + var fields = ((TypeMemPtr)Parser.TYPES.get("S"))._obj._fields; + assertTrue(mem.alias(fields[0]._alias) instanceof MemPhiNode); + assertTrue(mem.alias(fields[1]._alias) instanceof MemPhiNode); return mem; } return null; @@ -173,7 +175,7 @@ public class MemoryEncodingTest { c.append("if(memory(").append(arg).append(")!=").append(expected(p,arg)).append("LL) return ").append(arg+1).append(";\n"); c.append("return 0;\n}\n"); Files.writeString(Path.of(file+".c"),c); - TestC._run("val memory = { int arg -> "+SOURCES[p]+" };", + TestC.run("val memory = { int arg -> "+SOURCES[p]+" };", TestC.CALL_CONVENTION,"",file+".c",file,"S","",-1); } } diff --git a/src/test/java/com/seaofnodes/simple/Simple.java b/src/test/java/com/seaofnodes/simple/Simple.java index 705b086a..cd795fae 100644 --- a/src/test/java/com/seaofnodes/simple/Simple.java +++ b/src/test/java/com/seaofnodes/simple/Simple.java @@ -17,7 +17,7 @@ public class Simple { static final int DUMP_AFTER_OPTO = 1<<1; static final int DUMP_AFTER_TYPE_CHECK = 1<<2; static final int DUMP_AFTER_LOOP_TREE = 1<<3; - static final int DUMP_AFTER_INSTR_SELECT = 1<<4; + static final int DUMP_AFTER_SELECT = 1<<4; static final int DUMP_AFTER_GCM = 1<<5; static final int DUMP_AFTER_LOCAL_SCHED = 1<<6; static final int DUMP_AFTER_REG_ALLOC = 1<<7; @@ -30,32 +30,29 @@ public class Simple { static final int DUMP_DISASSEMBLE = 1<<31; - static String system_cpu = null; - static String system_abi = null; - static void usage() { System.out.println( """ -simple <input-file> [options] [--eval|--run ...] +simple [options] <input-file> ...args... Options: - --dump - dump final intermediate representation - --dump-after-parse - dump intermediate representation after parse - --dump-after-opto - dump intermediate representation after opto pass - --dump-after-type-check - dump intermediate representation after type check pass - --dump-after-instr-select - dump intermediate representation after instrution selection pass - --dump-after-gcm - dump intermediate representation after GCM pass - --dump-after-local-sched - dump intermediate representation after local scheduling pass - --dump-after-reg-alloc - dump intermediate representation after register allocation pass - --dump-after-encode - dump intermediate representation after encoding pass - --dump-after-all - dump intermediate representation after all passes - -S - dump generated assembler code - --eval ... - evaluate the compiled code in emulator - --run ... - run the compiled code natively - --dump-size - print the size of generated code - --dump-time - print compilation and execution times - --cpu <cpu-name> - use specific CPU (x86_64_v2, riscv, arm) - --abi <abi-name> - use speific ABI variant (SystemV) - --target - print native CPU and ABI + --dump - dump final intermediate representation + --dump-after-parse - dump intermediate representation after parse + --dump-after-opto - dump intermediate representation after opto pass + --dump-after-type-check - dump intermediate representation after type check pass + --dump-after-select - dump intermediate representation after instrution selection pass + --dump-after-gcm - dump intermediate representation after GCM pass + --dump-after-local-sched - dump intermediate representation after local scheduling pass + --dump-after-reg-alloc - dump intermediate representation after register allocation pass + --dump-after-encode - dump intermediate representation after encoding pass + --dump-after-all - dump intermediate representation after all passes + -S - dump generated assembler code + --eval - evaluate the compiled code in emulator + --run - run the compiled code natively; this is the default + --dump-size - print the size of generated code + --dump-time - print compilation and execution times + --cpu <cpu-name> - use specific CPU (x86_64_v2, riscv, arm) + --abi <abi-name> - use speific ABI variant (SystemV) + --target - print native CPU and ABI --version --help """ @@ -63,20 +60,17 @@ Options: System.exit(0); } - static void bad_usage() { - System.err.println("ERROR: Invalid usage (use --help)"); + static void bad_usage() { bad("Invalid usage (use --help)"); } + static RuntimeException bad(String err) { + System.err.println("ERROR: "+err); System.exit(1); + return new RuntimeException(err); } static void target() { - if (system_cpu == null || system_abi == null) { - System.err.println("ERROR: Unknown target"); - System.exit(1); - } - System.out.print(system_cpu); + System.out.print(TestC.CPU_PORT); System.out.print("-"); - System.out.println(system_abi); - System.exit(0); + System.out.println(TestC.CALL_CONVENTION); } static void dump(CodeGen code, int dump, int pass) { @@ -87,11 +81,11 @@ Options: case DUMP_AFTER_OPTO -> "After OPTO:"; case DUMP_AFTER_TYPE_CHECK -> "After Type Check:"; case DUMP_AFTER_LOOP_TREE -> "After Loop Tree:"; - case DUMP_AFTER_INSTR_SELECT -> "After Instruction Selection:"; + case DUMP_AFTER_SELECT -> "After Code Selection:"; case DUMP_AFTER_GCM -> "After GCM:"; case DUMP_AFTER_LOCAL_SCHED -> "After Local Scheduling:"; case DUMP_AFTER_REG_ALLOC -> "After Register Allocation:"; - case DUMP_AFTER_ENCODE -> "After Instruction Encoding:"; + case DUMP_AFTER_ENCODE -> "After Encoding:"; case DUMP_FINAL -> "Final:"; default -> throw Utils.TODO(); }); @@ -106,24 +100,24 @@ Options: double t, total = 0; total += t = code._tParse / 1e3; - System.out.println(String.format("Parsing Time: %.3f sec", t)); + System.out.printf( "Parsing Time: %.3f sec%n", t); total += t = code._tOpto / 1e3; - System.out.println(String.format("Optimization Time: %.3f sec", t)); + System.out.printf( "Optimization Time: %.3f sec%n", t); total += t = code._tTypeCheck / 1e3; - System.out.println(String.format("Type Checking Time: %.3f sec", t)); + System.out.printf( "Type Checking Time: %.3f sec%n", t); total += t = code._tLoopTree / 1e3; - System.out.println(String.format("Loop Tree Time: %.3f sec", t)); + System.out.printf( "Loop Tree Time: %.3f sec%n", t); total += t = code._tInsSel / 1e3; - System.out.println(String.format("Instruction Selection Time: %.3f sec", t)); + System.out.printf( "Code Selection Time: %.3f sec%n", t); total += t = code._tGCM / 1e3; - System.out.println(String.format("GCM Time: %.3f sec", t)); + System.out.printf( "GCM Time: %.3f sec%n", t); total += t = code._tLocal / 1e3; - System.out.println(String.format("Local Scheduling Time: %.3f sec", t)); + System.out.printf( "Local Scheduling Time: %.3f sec%n", t); total += t = code._tRegAlloc / 1e3; - System.out.println(String.format("Register Allocation Time: %.3f sec", t)); + System.out.printf( "Register Allocation Time: %.3f sec%n", t); total += t = code._tEncode / 1e3; - System.out.println(String.format("Instruction Encoding Time: %.3f sec", t)); - System.out.println(String.format("TOTAL COMPILATION TIME: %.3f sec", total)); + System.out.printf( "Encoding Time: %.3f sec%n", t); + System.out.printf( "TOTAL COMPILATION TIME: %.3f sec%n", total); } static String getInput() throws IOException { @@ -134,9 +128,8 @@ Options: public static void main(String[] args) throws Exception { String input_filename = null; - boolean use_stdin = false; boolean do_eval = false; - boolean do_run = false; + boolean do_run = true; boolean do_codegen = false; boolean do_print_size = false; boolean do_print_time = false; @@ -146,77 +139,61 @@ Options: String cpu = null; String abi = null; - // TODO: autodetect - system_cpu = "x86_64_v2"; - system_abi = "SystemV"; - // Parse command line -loop: for (int i = 0; i < args.length; i++) { + int i; for( i = 0; i < args.length; i++ ) { String arg = args[i]; - if (arg.charAt(0) == '-') { - switch (arg) { - case "-": use_stdin = true; break; - case "--dump": dump |= DUMP_FINAL; break; - case "--dump-after-parse": dump |= DUMP_AFTER_PARSE; break; - case "--dump-after-opto": dump |= DUMP_AFTER_OPTO; break; - case "--dump-after-type-check": dump |= DUMP_AFTER_TYPE_CHECK; break; - case "--dump-after-loop-tree": dump |= DUMP_AFTER_LOOP_TREE; break; - case "--dump-after-instr-select": dump |= DUMP_AFTER_INSTR_SELECT; break; - case "--dump-after-gcm": dump |= DUMP_AFTER_GCM; break; - case "--dump-after-local-sched": dump |= DUMP_AFTER_LOCAL_SCHED; break; - case "--dump-after-reg-alloc": dump |= DUMP_AFTER_REG_ALLOC; break; - case "--dump-after-encode": dump |= DUMP_AFTER_ENCODE; break; - case "--dump-after-all": dump |= DUMP_AFTER_ALL; break; - case "-S": dump |= DUMP_DISASSEMBLE; break; - case "--eval": do_eval = true; first_arg = i + 1; break loop; - case "--run": do_run = true; first_arg = i + 1; break loop; - case "--dump-size": do_print_size = true; break; - case "--dump-time": do_print_time = true; break; - case "--cpu": if (cpu != null - || i + 1 >= args.length - || args[i + 1].charAt(0) == '-') bad_usage(); - cpu = args[i + 1]; - i++; - break; - case "--abi": if (abi != null - || i + 1 >= args.length - || args[i + 1].charAt(0) == '-') bad_usage(); - abi = args[i + 1]; - i++; - break; - case "--target": target(); - case "--version": throw Utils.TODO(); - case "--help": usage(); - default: bad_usage(); - } - } else { - if (input_filename != null || use_stdin) bad_usage(); + if( arg.charAt(0) != '-' ) { input_filename = arg; + break; } - } - if (input_filename == null && !use_stdin) { - System.err.println("ERROR: no input file' (use --help)"); - System.exit(1); + switch (arg) { + case "-": input_filename=""; break; + case "--dump": dump |= DUMP_FINAL; break; + case "--dump-after-parse": dump |= DUMP_AFTER_PARSE; break; + case "--dump-after-opto": dump |= DUMP_AFTER_OPTO; break; + case "--dump-after-type-check": dump |= DUMP_AFTER_TYPE_CHECK; break; + case "--dump-after-loop-tree": dump |= DUMP_AFTER_LOOP_TREE; break; + case "--dump-after-select": dump |= DUMP_AFTER_SELECT; break; + case "--dump-after-gcm": dump |= DUMP_AFTER_GCM; break; + case "--dump-after-local-sched": dump |= DUMP_AFTER_LOCAL_SCHED; break; + case "--dump-after-reg-alloc": dump |= DUMP_AFTER_REG_ALLOC; break; + case "--dump-after-encode": dump |= DUMP_AFTER_ENCODE; break; + case "--dump-after-all": dump |= DUMP_AFTER_ALL; break; + case "-S": dump |= DUMP_DISASSEMBLE; break; + case "--eval": do_eval = true ; do_run = false; break; + case "--run": do_run = true ; break; + case "--norun": do_run = false; break; + case "--dump-size": do_print_size = true; break; + case "--dump-time": do_print_time = true; break; + case "--cpu": if (cpu != null || i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); + cpu = args[++i]; + break; + case "--abi": if (abi != null || i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); + abi = args[++i]; + break; + case "--target": target(); break; + case "--version": throw Utils.TODO(); + case "--help": usage(); + default: bad_usage(); + } } + if (input_filename == null) throw bad("no input file' (use --help)"); + if( !input_filename.isEmpty() && !input_filename.endsWith(".smp") ) + throw bad("File extension must be .smp"); + String base = input_filename.substring(0,input_filename.length()-4); + if (do_run || (dump & DUMP_DISASSEMBLE) != 0 || do_print_size) { - if (cpu == null) cpu = system_cpu; - if (abi == null) abi = system_abi; - if (cpu == null || abi == null) { - System.err.println("ERROR: Cannot compile for unknown target"); - System.exit(1); - } + if (cpu == null) cpu = TestC.CPU_PORT; + if (abi == null) abi = TestC.CALL_CONVENTION; do_codegen = true; } // Read input file try { - src = use_stdin ? getInput() : Files.readString(Path.of(input_filename)); - } catch(IOException e) { - System.err.println("ERROR: Cannot read input file"); - System.exit(1); - } + src = input_filename.isEmpty() ? getInput() : Files.readString(Path.of(input_filename)); + } catch( IOException e ) { throw bad("Cannot read input file: "+input_filename); } // Compilation pipeline CodeGen code = new CodeGen(src); @@ -234,8 +211,8 @@ loop: for (int i = 0; i < args.length; i++) { dump(code, dump, DUMP_AFTER_LOOP_TREE); if (do_codegen) { - code.instSelect(PORTS, cpu, abi); - dump(code, dump, DUMP_AFTER_INSTR_SELECT); + code.instSelect(cpu, abi, PORTS); + dump(code, dump, DUMP_AFTER_SELECT); } code.GCM(); @@ -250,6 +227,8 @@ loop: for (int i = 0; i < args.length; i++) { code.encode(); dump(code, dump, DUMP_AFTER_ENCODE); + + code.exportELF(base+".o"); } dump(code, dump, DUMP_FINAL); @@ -259,7 +238,7 @@ loop: for (int i = 0; i < args.length; i++) { } if (do_print_size) { - System.out.println(String.format("Code Size: %d", code._encoding._bits.size())); + System.out.printf( "Code Size: %d%n", code._encoding._bits.size()); } if (do_print_time) { @@ -269,19 +248,19 @@ loop: for (int i = 0; i < args.length; i++) { if (do_eval) { // TODO: Support for evaluation of functions with different argument numbers and types long t = System.currentTimeMillis(); - long arg = (first_arg < args.length) ? Integer.valueOf(args[first_arg]) : 0; + long arg = (i+1 < args.length) ? Integer.parseInt(args[i+1]) : 0; System.out.println(Eval2.eval(code, arg, 100000)); if (do_print_time) { - System.out.println(String.format("EXECUTION TIME: %.3f sec", - (System.currentTimeMillis() - t) / 1e3)); + System.out.printf( "EXECUTION TIME: %.3f sec%n", + (System.currentTimeMillis() - t) / 1e3); } - } else if (do_run) { - if (cpu != system_cpu || abi != system_abi) { - System.err.println("ERROR: cannot run code on not native target"); - System.exit(1); - } - - throw Utils.TODO(); + } + if (do_run) { + if ( !TestC.CPU_PORT.equals( cpu ) || !TestC.CALL_CONVENTION.equals( abi ) ) + throw bad("cannot run code on not native target"); + String exe = TestC.OS.startsWith("Windows") ? base+".exe" : base; + String result = com.seaofnodes.simple.TestC.gcc(base+".o", null, null, true, exe); + System.out.print(result); } } } diff --git a/src/test/java/com/seaofnodes/simple/SpillStats.java b/src/test/java/com/seaofnodes/simple/SpillStats.java index 318a6e33..82cffef8 100644 --- a/src/test/java/com/seaofnodes/simple/SpillStats.java +++ b/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -26,6 +26,13 @@ public class SpillStats extends RunListener { code._regAlloc._spills+","+code._regAlloc._spillScaled); } + // The same native helpers serve old and new program cohorts. + public static void recordNative(CodeGen code, String cpu, String abi) { + String cohort = ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter22Test.class + ? "Chapter22" : "Chapter21"; + record(code,cohort,cpu,abi); + } + // Keep running every CPU and native result check when measuring quality. // A changed golden still makes spill-stats fail at the end. public static void checkSpills(int expected, int actual) { @@ -39,7 +46,7 @@ public class SpillStats extends RunListener { } public static void main(String[] args) throws ClassNotFoundException { - if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","BrainFuckTest","MergeSortTest"}; + if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","Chapter22Test","BrainFuckTest","MergeSortTest"}; Class<?>[] tests = new Class<?>[args.length]; for( int i=0; i<args.length; i++ ) tests[i] = Class.forName("com.seaofnodes.simple."+args[i]); @@ -48,7 +55,8 @@ public class SpillStats extends RunListener { junit.addListener(ACTIVE); Result result = junit.run(tests); boolean passed = result.wasSuccessful() && ACTIVE._qualityFailures==0; - if( !passed ) System.out.println("FAILED test run: totals are not a complete comparison."); + if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + else if( !passed ) System.out.println("Spill expectations differ; allocation and runtime checks passed."); System.out.println("cohort,cpu,abi,allocations,splits,scaled"); for( var row : ACTIVE._totals.entrySet() ) { long[] sum = row.getValue(); diff --git a/src/test/java/com/seaofnodes/simple/TestArm64.java b/src/test/java/com/seaofnodes/simple/TestArm64.java index e4bc38a0..a22063eb 100644 --- a/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple; import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -23,9 +25,8 @@ public class TestArm64 { public static EvalArm64 build( String dir, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); - com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); - SpillStats.record(code,"Chapter21","arm","SystemV"); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); + SpillStats.recordNative(code,"arm","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/src/test/java/com/seaofnodes/simple/TestC.java b/src/test/java/com/seaofnodes/simple/TestC.java index b3e21ea7..44c06128 100644 --- a/src/test/java/com/seaofnodes/simple/TestC.java +++ b/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,10 +1,11 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; +import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; -import java.io.InputStream; -import java.io.IOException; +import java.util.concurrent.TimeUnit; import static org.junit.Assert.*; // Call a C driver program, which calls a Simple-generated .o, and self-checks. @@ -16,8 +17,8 @@ public abstract class TestC { public static final String CALL_CONVENTION = OS.startsWith("Windows") ? "Win64" : "SystemV"; public static final String CPU_PORT = switch( CPU ) { - case "amd64" -> "x86_64_v2"; - default -> throw Utils.TODO("Map Yer CPU Port Here"); + case "amd64" -> "x86_64_v2"; + default -> throw Utils.TODO("Map Yer CPU Port Here"); }; public static void run( String file, int spills ) throws IOException { run(file,"",spills); } @@ -35,54 +36,69 @@ public abstract class TestC { // Compile and export Simple String src = Files.readString(Path.of(sfile)); - _run(src,CALL_CONVENTION,"",cfile,efile,"S",expected,spills); + run(src,CALL_CONVENTION,"",cfile,efile,"S",expected,spills); } - static void _run( String src, String simple_conv, String c_conv, String cfile, String efile, String xtn, String expected, int spills ) throws IOException { + public static void run( String src, String simple_conv, String c_conv, String cfile, String efile, String xtn, String expected, int spills ) throws IOException { String bin = efile+xtn; String obj = bin+".o"; + String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF - CodeGen code = new CodeGen(src).driver( CPU_PORT, simple_conv, obj); - com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); - SpillStats.record(code,"Chapter21",CPU_PORT,simple_conv); + CodeGen code = new CheckedCodeGen(src).driver( CPU_PORT, simple_conv, obj); + SpillStats.recordNative(code,CPU_PORT,simple_conv); + String result = gcc(obj, c_conv, cfile, false, exe ); + assertEquals(expected,result); + + // Allocation quality not degraded + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + } + + public static String gcc( String obj, String c_conv, String cfile, boolean stdin, String... args ) throws IOException { + + // Compile the C program. Compiling code and constants in the low + // 2Gig. Pointers are 64b BUT since always in the low 2G all the + // high bits are zero - and Simple code can be emitted treating + // pointers as 4bytes. + var params = new Ary<>(String.class); + params.add("gcc"); + if( cfile!=null ) params.add(cfile); // Associated C driver, usually has a `main` + params.addAll(new String[] { + obj, + "-lm", // Picks up 'sqrt' for newtonFloat tests to compare + "-g", + "-o", + args[0], + }); + // Calling convention for C calls, if any + if( cfile!=null ) { + params.add("-D"); + params.add("CALL_CONV="+c_conv); + } - // Compile the C program - var params = new String[] { - //if (USE_WSL) "wsl.exe"; - "gcc", - cfile, - obj, - "-lm", // Picks up 'sqrt' for newtonFloat tests to compare - "-g", - "-o", - bin, - "-D", - "CALL_CONV="+c_conv, - }; - Process gcc = new ProcessBuilder(params).redirectErrorStream(true).start(); - int error; - try { error = gcc.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + // Run GCC to link (optionally compile C driver code) + Process gcc = new ProcessBuilder(params.asAry()).redirectErrorStream(true).start(); + int exit; + try { + boolean normal = gcc.waitFor(2, TimeUnit.SECONDS); + exit = normal ? gcc.exitValue() : -1; // no exit??? + } catch( InterruptedException e ) { + throw new IOException("interrupted"); + } String result = new String(gcc.getInputStream().readAllBytes()); - if( error!=0 ) { - System.err.println("gcc error code: "+error); + if( exit!=0 ) { + System.err.println("gcc error code: "+exit); System.err.println(result); } - assertEquals( 0, error ); + assertEquals( 0, exit ); //assertTrue(result.isEmpty()); // No data in error stream // Execute results - Process smp = new ProcessBuilder(bin).redirectErrorStream(true).start(); - try { error = smp.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } - result = new String(smp.getInputStream().readAllBytes()); - if( error!=0 ) { - System.err.println("exec error code: "+error); - System.err.println(result); - } - assertEquals( 0, error ); - assertEquals(expected,result); - - // Allocation quality not degraded - SpillStats.checkSpills(spills,code._regAlloc._spillScaled); - + ProcessBuilder smp = new ProcessBuilder(args); + if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT); + Process p = smp.start(); + try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + result = new String(p.getInputStream().readAllBytes()); + assertEquals("Program exit status",0,exit); + return result; } } diff --git a/src/test/java/com/seaofnodes/simple/TestRisc5.java b/src/test/java/com/seaofnodes/simple/TestRisc5.java index 1289575d..ace2a7ea 100644 --- a/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.isa.eval.EvalRisc5; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.Node; @@ -22,9 +23,8 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String dir, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); - com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); - SpillStats.record(code,"Chapter21","riscv","SystemV"); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); + SpillStats.recordNative(code,"riscv","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index dee033bc..551bddad 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -20,9 +20,9 @@ public class TypeTest { TypeStruct s2 = TypeStruct.make("s2", new Field[]{ Field.make("a", TypeInteger.BOT,-3, false), Field.make("b", TypeInteger.BOT,-4, false) }); - Assert.assertEquals(s1.makeRO(), s1.glb()); + Assert.assertEquals(s1.makeRO(), s1.glb(false)); Assert.assertNotEquals(s1, s1.dual()); - Assert.assertEquals(s1.makeRO(), s1.dual().glb()); + Assert.assertEquals(s1.makeRO(), s1.dual().glb(false)); TypeMem m1 = TypeMem.make(1,TypeNil.NIL); TypeMem m2 = TypeMem.make(2,TypeInteger.U16); @@ -38,9 +38,9 @@ public class TypeTest { Assert.assertEquals(TypeMem.make(0,Type.BOTTOM), m1.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(TypeMem.make(1,Type.BOTTOM), m1.glb()); + Assert.assertEquals(TypeMem.make(1,Type.BOTTOM), m1.glb(false)); Assert.assertEquals(TypeMem.make(1,Type.XNIL), m1.dual()); - Assert.assertEquals(m4.dual(), m4.glb().dual()); + Assert.assertEquals(m4.dual(), m4.glb(false).dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); @@ -55,11 +55,11 @@ public class TypeTest { Assert.assertEquals(s2, ptr2nil._obj); Assert.assertNotEquals(ptr1, ptr2); - Assert.assertNotEquals(ptr1, ptr1.glb()); - Assert.assertEquals(ptr1nil.makeFrom(s1.glb()).makeRO(), ptr1.glb()); + Assert.assertNotEquals(ptr1, ptr1.glb(false)); + Assert.assertEquals(ptr1nil.makeFrom(s1.glb(false)).makeRO(), ptr1.glb(false)); Assert.assertEquals(ptr1, ptr1.dual().dual()); - Assert.assertEquals(ptr1.glb().makeFrom(s1.dual().glb()), ptr1.dual().glb()); + Assert.assertEquals(ptr1.glb(false).makeFrom(s1.dual().glb(false)), ptr1.dual().glb(false)); Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false), ptr1.meet(ptr2nil)); Assert.assertEquals(ptr1nil, ptr1.meet(TypeNil.NIL)); diff --git a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 739eba3b..2d9860a6 100644 --- a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -118,6 +118,16 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,new RegAlloc(code))); } + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + public static void topPhi() { // Either arm can be the synthetic exit. Both predecessors share a // block here so making TOP live would conflict with the real value. diff --git a/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java index 368c243b..0914d916 100644 --- a/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java +++ b/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86; import org.junit.Test; import static org.junit.Assert.*; @@ -11,7 +12,7 @@ public class X86EncodingTest { @Test public void testLogicalNotRegisters() { CodeGen code = new CodeGen("return !arg;") - .driver(CodeGen.Phase.InstSelect, "x86_64_v2", "SystemV"); + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); assertNotNull("Must exercise logical not", not); int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; @@ -50,6 +51,31 @@ public class X86EncodingTest { """); com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); } + + @Test + public void testMultiplyImmediateRegisters() { + // Destination, source, expected REX and ModRM. Cross the register-8 + // boundary in both directions, with low/low and high/high controls. + int[][] cases = {{1, 9, 0x49, 0xC9}, {9, 1, 0x4C, 0xC9}, + {1, 2, 0x48, 0xCA}, {9, 10, 0x4D, 0xCA}}; + for (int immediate : new int[]{11, -11, 123456789, -123456789}) { + CodeGen code = new CodeGen("return arg * " + immediate + ";") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var mul = code._stop.walk(n -> n instanceof MulIX86 ? n : null); + assertNotNull("Must exercise immediate multiply", mul); + for (int[] regs : cases) { + var enc = new FixedRegisterEncoding( + code, mul, regs[0], mul.in(1), regs[1]); + ((MulIX86)mul).encoding(enc); + boolean small = immediate == 11 || immediate == -11; + assertEquals("REX for dst=" + regs[0] + ", src=" + regs[1], regs[2], enc.read1(0)); + assertEquals(small ? 0x6B : 0x69, enc.read1(1)); + assertEquals(regs[3], enc.read1(2)); + assertEquals(small ? 4 : 7, enc._bits.size()); + assertEquals(immediate, small ? (byte)enc.read1(3) : enc.read4(3)); + } + } + } @Test public void testMemoryCompare64Immediate32() { for (int immediate : new int[]{123456789, -123456789}) { diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 167a5b24..79547c0d 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -97,7 +97,7 @@ public class ScriptGenerator { private static final List<TypeInt> INTTYPES = new ArrayList<>(); static { - for( var e : Parser.defaultTypes().entrySet() ) { + for( var e : Parser.TYPES.entrySet() ) { if( e.getValue() instanceof TypeInteger ) { INTTYPES.add(new TypeInt(e.getKey())); } diff --git a/src/test/java/com/seaofnodes/simple/progs/c_returns.c b/src/test/java/com/seaofnodes/simple/progs/c_returns.c new file mode 100644 index 00000000..6d0ff2fe --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/c_returns.c @@ -0,0 +1,28 @@ +#include <stdint.h> +#include <stdio.h> + +uint64_t c_bits; +// Legal narrow C returns: unused RAX bits deliberately contain garbage. +#define RET(name) __asm__(".text\n.globl " #name "\n" #name ":\nmovq c_bits(%rip), %rax\nret\n"); +RET(c_i8) RET(c_u8) RET(c_i16) RET(c_u16) RET(c_i32) RET(c_u32) RET(c_i64) +#define DECL(name) extern int64_t __attribute__((CALL_CONV)) name(void); +DECL(test_i8) DECL(test_u8) DECL(test_i16) DECL(test_u16) +DECL(test_i32) DECL(test_u32) DECL(test_i64) DECL(test_cmp) + +int main(void) { + uint64_t values[] = {0xa5a5a5a500000000ULL, 0xa5a5a5a50000007fULL, + 0xa5a5a5a500000080ULL, 0xa5a5a5a500007fffULL, 0xa5a5a5a500008000ULL, + 0xa5a5a5a57fffffffULL, 0xa5a5a5a580000000ULL, 0xa5a5a5a5ffffffffULL}; + for(unsigned i=0; i<sizeof(values)/sizeof(values[0]); i++) { + c_bits=values[i]; + int64_t actual[]={test_i8(),test_u8(),test_i16(),test_u16(),test_i32(),test_u32(),test_i64(),test_cmp()}; + int64_t expected[]={(int8_t)c_bits,(uint8_t)c_bits,(int16_t)c_bits,(uint16_t)c_bits, + (int32_t)c_bits,(uint32_t)c_bits,(int64_t)c_bits,(int32_t)c_bits==-1}; + for(unsigned j=0; j<8; j++) + if(actual[j]!=expected[j]) { + printf("case %u type %u: %lld != %lld\n",i,j,(long long)actual[j],(long long)expected[j]); + return 1; + } + } + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/echo.smp b/src/test/java/com/seaofnodes/simple/progs/echo.smp new file mode 100644 index 00000000..8eafd73b --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/echo.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +// Echo stdin to stdout. +return sys.io.p( sys.io.stdin() ); diff --git a/src/test/java/com/seaofnodes/simple/progs/funptr.c b/src/test/java/com/seaofnodes/simple/progs/funptr.c new file mode 100644 index 00000000..7545992d --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/funptr.c @@ -0,0 +1,15 @@ +#include <assert.h> +#include <stdint.h> + +typedef int64_t (*Function)(void); +typedef int64_t (*Printer)(void *); +extern Function factory(int64_t); +extern Printer printer(void); + +int main(void) { + assert(factory(1)() == 42); + assert(factory(0)() == 43); + struct { uint32_t length; char data[2]; } text = {2, {'o','k'}}; + printer()(&text); + return 0; +} diff --git a/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp b/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/src/test/java/com/seaofnodes/simple/progs/jig.smp b/src/test/java/com/seaofnodes/simple/progs/jig.smp index 1daeee09..29987d8e 100644 --- a/src/test/java/com/seaofnodes/simple/progs/jig.smp +++ b/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -1,2 +1,16 @@ // -*- mode: java; -*- -return 0; +val _fib = {int n -> + int temp=0; + int f1=1; + int f2=1; + int i=n; + while( i>1 ){ + temp = f1+f2; + f1=f2; + f2=temp; + i=i-1; + } + return f2; +}; + +_fib(10); diff --git a/src/test/java/com/seaofnodes/simple/progs/person.smp b/src/test/java/com/seaofnodes/simple/progs/person.smp index b5e6ee90..94e2cdde 100644 --- a/src/test/java/com/seaofnodes/simple/progs/person.smp +++ b/src/test/java/com/seaofnodes/simple/progs/person.smp @@ -1,6 +1,6 @@ // -*-java-*- struct Person { - int age; + i32 age; }; val fcn = { !Person?[] ps, int x -> diff --git a/src/test/java/com/seaofnodes/simple/progs/person21.c b/src/test/java/com/seaofnodes/simple/progs/person21.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/person21.c @@ -0,0 +1,34 @@ +#include <stdio.h> +#include <stdbool.h> +#include <stdlib.h> + +typedef struct Person { + int age; +} Person; + +typedef struct PersonArray { + unsigned int length; + int pad; + Person* data[]; +} PersonArray; + +__attribute__ ((CALL_CONV)) +extern void fcn(PersonArray* people, int index); + +int main() { + Person base[5] = {{25},{1},{18},{45},{60}}; + unsigned char buf[8+8*5]; + PersonArray* people_array = (PersonArray*)buf; + people_array->length=5; + for (int i=0; i<people_array->length; i++) people_array->data[i] = &base[i]; + + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + + printf("%d\n", people_array->data[1]->age); // expected: 6 + + return 0; +}
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/person21.smp b/src/test/java/com/seaofnodes/simple/progs/person21.smp new file mode 100644 index 00000000..b5e6ee90 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/person21.smp @@ -0,0 +1,9 @@ +// -*-java-*- +struct Person { + int age; +}; + +val fcn = { !Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +};
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp b/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp new file mode 100644 index 00000000..1a36fb99 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp @@ -0,0 +1,4 @@ +struct Person { i32 age;}; +!Person !p = new Person; +p.age += arg; +return p.age; diff --git a/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp b/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp new file mode 100644 index 00000000..57b37477 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp @@ -0,0 +1,4 @@ +struct Person {i64 age;} +!Person !p = new Person; +p.age += arg; +return p.age; diff --git a/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp b/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp new file mode 100644 index 00000000..7d7fdce7 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp @@ -0,0 +1,5 @@ +// Should fold away sign extend +struct Person { i8 age;}; +!Person !p = new Person; +p.age = (arg<<48)>>48; +return 0;
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp b/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp new file mode 100644 index 00000000..4d6ca3a3 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp @@ -0,0 +1,4 @@ +struct Person { i32 age;}; +!Person !p = new Person; +p.age = (arg<<17)>>17; +return 0;
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp b/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp new file mode 100644 index 00000000..5c96c060 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp @@ -0,0 +1,4 @@ +struct Person { i32 age;}; +!Person !p = new Person; +p.age = (arg<<48)>>48; +return 0;
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/progs/store_peep.smp b/src/test/java/com/seaofnodes/simple/progs/store_peep.smp new file mode 100644 index 00000000..c3feddd5 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/progs/store_peep.smp @@ -0,0 +1,3 @@ +i64 a = 123456789012345; +i32 b = a; // truncate high order bits +return b;
\ No newline at end of file |