diff options
Diffstat (limited to 'chapter22')
21 files changed, 326 insertions, 92 deletions
diff --git a/chapter22/README.md b/chapter22/README.md index ef2304d0..b32451f2 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -277,7 +277,7 @@ struct sstr { // Array contents are immutable. // Still figuring out good syntax for this. u8 #; - u8 []!; // Trailing '!'? Makes primitive array contents *immutable* and requires constructor syntax + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax }; // Construction requires a function that produces the array contents. @@ -341,9 +341,9 @@ struct gstr { // aka germanString, or blend string and register "streg" } // Using inlined object (see below). All these strings are short and are // represented as packed integers in a 64b register. -gstr *prize1 = "gold"; -gstr *prize2 = "silver"; -gstr *prize3 = "bronze"; +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; ``` @@ -399,7 +399,7 @@ ref.c.len(); val.c.len(); // Function arguments use the same typing, so can pass-by-value -val math.sin = { Complex *c -> ... }; // Passes a complex by value +val math.sin = { *Complex c -> ... }; // Passes a complex by value math.sin(ref.*c); // Requires de-reference to pass by value math.sin(val. c); // Pass by value diff --git a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java index 5b9a3820..ab43e1a9 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/Parser.java @@ -132,8 +132,7 @@ public class Parser { private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } public void parse() { - _lexer = new Lexer(_code._src); - _xScopes.push(_scope); + _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); @@ -141,8 +140,18 @@ public class Parser { ctrl(XCTRL); _scope.mem(new MemMergeNode(false)); - // Parse whole program, as-if function header "{ int arg -> body }" + // Parse the sys import + _lexer = new Lexer(com.seaofnodes.simple.sys.sys.SYS); + 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"); // Kill an empty default main. Keep only if it was explicitly defined @@ -222,15 +231,6 @@ public class Parser { _scope.define(ids[i], t, false, new ParmNode(ids[i],i+2,t,fun,con(t)).peephole(), loc); } - //// If top-level parser, parse the sys import - //if( fun.sig()==_code._main ) { - // Lexer old = _lexer; - // _lexer = new Lexer(com.seaofnodes.simple.sys.sys.SYS); - // while(!_lexer.isEOF() ) - // parseStatement(); - // _lexer = old; - //} - // Parse the body Node last=ZERO; while (!peek('}') && !_lexer.isEOF()) @@ -771,10 +771,13 @@ public class Parser { * * @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(); + if( old!=null ) typeName = old+"."+typeName; + _nestedType = typeName; // A Block scope parse, and inspect the scope afterward for fields. _scope.push(ScopeNode.Kind.Constructor); @@ -782,6 +785,7 @@ public class Parser { while (!peek('}') && !_lexer.isEOF()) parseStatement().isKill(); + // Grab the declarations and build fields and a Struct int lexlen = _scope._lexSize.last(); int varlen = _scope._vars._len; @@ -795,10 +799,12 @@ public class Parser { } // 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(); @@ -827,6 +833,19 @@ 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 // Nest arrays and '?' as needed @@ -837,6 +856,9 @@ public class Parser { throw error("Type "+t0+" cannot be null"); if( tmp.nullable() ) throw error("Type "+t2+" already allows null"); t2 = tmp.makeNullable(); + } else if( match("[~]") ) { + TypeMemPtr tmp = typeAry(t2); + t2 = tmp.makeFrom(tmp._obj.makeRO()); } else if( match("[]") ) { t2 = typeAry(t2); } else @@ -866,8 +888,7 @@ public class Parser { String tname = "["+t.str()+"]"; Type ta = TYPES.get(tname); if( ta != null ) return (TypeMemPtr)ta; - // 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); @@ -1081,12 +1102,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 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); @@ -1135,6 +1172,7 @@ public class Parser { // 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"); @@ -1251,6 +1289,19 @@ 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; + TypeInteger len = TypeInteger.constant(s.length()); + 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]", len, lenAlias, elem, elemAlias, true, con),true); + return con(str); + } // We set up memory aliases by inserting special vars in the scope these // variables are prefixed by $ so they cannot be referenced in Simple code. @@ -1638,6 +1689,7 @@ public class Parser { } else if( _position+2 < _input.length && _input[_position ] == '/' && _input[_position+1] == '*') { + // Skip /*comment*/ while( !isEOF() && !(_input[_position-1] == '*' && _input[_position] == '/')) inc(); inc(); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index bc7de99a..6aaa3396 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -140,8 +140,8 @@ public class Encoding { 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; } @@ -426,12 +426,12 @@ public class Encoding { HashMap<Type,Integer> targets = new HashMap<>(); - // By log size - for( int log = 3; log >= 0; log-- ) { + // By alignment + for( int align = 4; align >= 0; align-- ) { // Write the 8-byte constants for( Node op : _bigCons.keySet() ) { Relo relo = _bigCons.get(op); - if( relo._t.log_size()==log ) { + if( relo._t.alignment()==align ) { // Map from relo to constant start and patch Integer target = targets.get(relo._t); if( target==null ) { @@ -439,9 +439,9 @@ public class Encoding { // 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); + addN(align,tx,bits); else - addN(log,relo._t,bits); + addN(align,relo._t,bits); } relo._target = target; relo._opStart= _opStart[op._nid]; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 79844816..971b52ae 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -130,7 +130,7 @@ public class PhiNode extends Node { return false; } for( int j=1; j<in(1).nIns(); j++ ) - if( op.in(j) instanceof ScopeNode || (op.in(j)==null && in(1).in(j)!=null) ) + if( op.in(j) instanceof ScopeNode || (op.in(j)==null ^ in(1).in(j)==null) ) return false; // Lazy Phi input } return true; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java index 63d418ff..2823d7d1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java @@ -8,13 +8,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"; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java index 5aff94d3..ad70a661 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java @@ -13,7 +13,8 @@ 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"; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index f6e67fb4..3110dbb4 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -2,8 +2,7 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; 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 +13,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 +25,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); + enc.add1(0xe8).add4(0); } // Delta is from opcode start, but X86 measures from the end of the 5-byte encoding diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java new file mode 100644 index 00000000..00219576 --- /dev/null +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TMPX86.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +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{ + private byte _encSize; + 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); + _encSize = (byte)(x86_64_v2.rexF(dst, 0, 0, false, enc) + 1/*Op*/ + 1/*MODRM*/ + 4/*offset*/); + enc.add1(0x8D).add1(x86_64_v2.modrm(x86_64_v2.MOD.INDIRECT, dst, 0b101)).add4(0); + enc.largeConstant(this,((TypeMemPtr)_con)._obj,_encSize-4,2/*ELF encoding PC32*/); + } + + // Delta is from opcode start + @Override public byte encSize(int delta) { + // TODO: 1-byte RIP offset? + return (byte)_encSize; + } + + // 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(" = #")); + } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 23c12ae7..0751a612 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -499,15 +499,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); }; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp b/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp index 8c470716..64c1b93e 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp +++ b/chapter22/src/main/java/com/seaofnodes/simple/sys/sys.smp @@ -5,6 +5,6 @@ struct sys { // libc bindings struct libc { /** https://www.man7.org/linux/man-pages/man2/write.2.html */ - { i32 u8[] i32 -> i32 } write = "C"; + { i32 u8[~] i32 -> i32 } write = "C"; }; }; diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter22/src/main/java/com/seaofnodes/simple/type/Field.java index bd67735a..ad96369b 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/Field.java @@ -51,6 +51,8 @@ public class Field extends Type { @Override public Field dual() { return make(_fname,_type.dual(),_alias,!_final); } + @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/chapter22/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter22/src/main/java/com/seaofnodes/simple/type/Type.java index 38414dcf..bc98f358 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter22/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; @@ -219,7 +222,8 @@ 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 alignment() { return log_size(); } // alignment; for structs, max align of Fields // ---------------------------------------------------------- // Useful in the debugger, which calls toString everywhere. diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java new file mode 100644 index 00000000..b57926bb --- /dev/null +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -0,0 +1,66 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import java.util.ArrayList; + +/** + * 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); + TypeConAryB.gather(ts); + TypeConAryI.gather(ts); + } + + @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; + } + + 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); + } + long at(int idx) { throw Utils.TODO(); } + int len() { throw Utils.TODO(); } + @Override public int alignment() { return 0; } + + @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/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java new file mode 100644 index 00000000..8a212867 --- /dev/null +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -0,0 +1,19 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; +import java.util.Arrays; + +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"); + public static void gather(ArrayList<Type> ts) { ts.add(ABC); ts.add(ABCD); } + @Override long at(int idx) { return _ary[idx]; } + @Override int len() { return _ary.length; } + @Override public int alignment() { return 0; } + @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); } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java new file mode 100644 index 00000000..2a5900c7 --- /dev/null +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -0,0 +1,15 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; +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(); } + private static final TypeConAryI I123 = make(new int[]{1,2,3}); + public static void gather(ArrayList<Type> ts) { ts.add(I123); } + @Override public String str() { return "[i32]"; } + @Override public int alignment() { return 3; } + @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } + @Override int hash() { return Arrays.hashCode(_ary); } +} diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 67ed65a9..78605e81 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -25,18 +25,22 @@ public class TypeMemPtr extends TypeNil { // (TOP ,true ) - a nil public final TypeStruct _obj; + 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; + _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); } + + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } - @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil,_obj); } + @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one); } @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); } @Override public boolean isFinal() { return _obj.isFinal(); } @@ -52,15 +56,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)); + return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), _one & that._one); } @Override - public TypeMemPtr dual() { return TypeMemPtr.make( dual0(), _obj.dual()); } + public TypeMemPtr dual() { return make( dual0(), _obj.dual(), !_one); } // RHS is NIL; do not deep-dual when crossing the centerline @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj); } + @Override public boolean isConstant() { return _one && _obj.isConstant(); } // True if this "isa" t up to named structures @Override public boolean shallowISA( Type t ) { @@ -79,11 +84,11 @@ public class TypeMemPtr extends TypeNil { @Override public int log_size() { return 3; } // (1<<3)==8-byte pointers - @Override int hash() { return _obj.hashCode() ^ super.hash(); } + @Override int hash() { return _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _obj == ptr._obj && super.eq(ptr); + return _obj == ptr._obj && _one == ptr._one && super.eq(ptr); } @Override public String str() { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 13105d20..0855bee8 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter22/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,7 +135,8 @@ 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. @@ -156,10 +167,30 @@ public class TypeStruct extends Type { return true; } + @Override public boolean isConstant() { + // Check all fields for being constant + for( int i=0; i<_fields.length; i++ ) + if( !_fields[i].isConstant() ) + // Last field checks for a constant array + if( i<_fields.length-1 || !isAry() || _con==TypeConAry.BOT ) + 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 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,14 +208,14 @@ 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( _con!=TypeConAry.BOT ) return sb.p(_con.str()); sb.p(_name); - if( _fields == null ) return sb; // Forward reference struct, just print the name - if( isAry() ) return sb; // Skip printing generic array fields + if( _fields == null || isAry() ) return sb; // Forward reference struct, just print the name sb.p(" {"); for( Field f : _fields ) f._type.print(sb).p(f._final ? " " : " !").p(f._fname).p("; "); @@ -192,7 +223,7 @@ public class TypeStruct extends Type { } @Override public SB gprint( SB sb ) { return sb.p(_name); } - @Override public String str() { return _name; } + @Override public String str() { return _con==TypeConAry.BOT ? _name : _con.str(); } public boolean isAry() { return _fields.length==2 && _fields[1]._fname.equals("[]"); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index c9f88efa..bc57871a 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter22/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 { @@ -62,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 0cf7f254..3bf379cd 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -51,7 +51,7 @@ return cc.cz; @Test @Ignore 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); + TestC.run(src,TestC.CALL_CONVENTION,null,null,"build/objs/helloWorld","","Hello, World!",13); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp b/chapter22/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp index 97400501..16ef4bc6 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp +++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/helloWorld.smp @@ -1,2 +1,2 @@ // -*- mode: java; -*- -return sys.libc.write(1,"Hello, World!\n",14); +return sys.libc.write(1,"Hello, World!",13); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp index 073200e3..b3bbf722 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp +++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -1,15 +1,10 @@ // -*- mode: java; -*- -//8942465726750756914 -while(0) { - struct s0 { - byte v0; - i32 v1; - i8 v2; - }; - s0 !JHRiBybfX=new s0; - while(1<<JHRiBybfX.v2) {} - int v3=JHRiBybfX.v1; - while(JHRiBybfX.v2) - v3=JHRiBybfX.v0; -} -return 0;
\ No newline at end of file +struct s0 { + u16 v0; + i16 v3; + u32 v5; +}; +return new s0.v3; +if(0) + while(new s0.v5+new s0.v5) return 0; +return new s0.v0; |