From 08d33f808db30936b273582bcfaddcbc5a57c112 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 6 May 2025 13:44:10 -0700 Subject: Chapter 23: Methods and Revisiting Types MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> --- src/main/java/com/seaofnodes/simple/Ary.java | 228 ---------- src/main/java/com/seaofnodes/simple/IterPeeps.java | 2 + src/main/java/com/seaofnodes/simple/Parser.java | 493 ++++++++++++++------- src/main/java/com/seaofnodes/simple/SB.java | 99 ----- src/main/java/com/seaofnodes/simple/Utils.java | 53 --- .../com/seaofnodes/simple/codegen/Coalesce.java | 4 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 66 ++- .../com/seaofnodes/simple/codegen/ElfFile.java | 3 +- .../com/seaofnodes/simple/codegen/Encoding.java | 24 +- .../simple/codegen/GlobalCodeMotion.java | 6 +- .../java/com/seaofnodes/simple/codegen/IFG.java | 4 +- .../java/com/seaofnodes/simple/codegen/LRG.java | 7 +- .../com/seaofnodes/simple/codegen/LinkMem.java | 2 +- .../seaofnodes/simple/codegen/ListScheduler.java | 4 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 8 +- .../com/seaofnodes/simple/codegen/RegMask.java | 4 +- .../java/com/seaofnodes/simple/node/AddNode.java | 9 +- .../java/com/seaofnodes/simple/node/ArithNode.java | 9 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 4 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 7 +- .../java/com/seaofnodes/simple/node/CProjNode.java | 2 +- .../com/seaofnodes/simple/node/CallEndMach.java | 2 +- .../com/seaofnodes/simple/node/CallEndNode.java | 10 +- .../java/com/seaofnodes/simple/node/CallNode.java | 10 +- .../java/com/seaofnodes/simple/node/CastMach.java | 2 +- .../java/com/seaofnodes/simple/node/CastNode.java | 15 +- .../com/seaofnodes/simple/node/ConFldOffNode.java | 43 ++ .../com/seaofnodes/simple/node/ConstantNode.java | 38 +- .../com/seaofnodes/simple/node/ExternNode.java | 6 +- .../java/com/seaofnodes/simple/node/FunNode.java | 9 +- .../java/com/seaofnodes/simple/node/IfNode.java | 6 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 41 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 24 +- .../seaofnodes/simple/node/MachConcreteNode.java | 2 +- .../java/com/seaofnodes/simple/node/MachNode.java | 2 + .../com/seaofnodes/simple/node/MemMergeNode.java | 9 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 2 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 3 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 2 +- .../java/com/seaofnodes/simple/node/NewNode.java | 34 +- src/main/java/com/seaofnodes/simple/node/Node.java | 7 +- .../java/com/seaofnodes/simple/node/NotNode.java | 4 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 11 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 77 +++- .../com/seaofnodes/simple/node/ReadOnlyMach.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 8 +- .../com/seaofnodes/simple/node/ReturnNode.java | 15 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 111 +++-- .../java/com/seaofnodes/simple/node/SplitNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 11 +- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 15 +- .../com/seaofnodes/simple/node/StructNode.java | 9 +- .../seaofnodes/simple/node/cpus/arm/AddARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AddFARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AddIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AndARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AndIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AsrARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/AsrIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/BranchARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/CallARM.java | 6 +- .../seaofnodes/simple/node/cpus/arm/CallRRARM.java | 4 +- .../seaofnodes/simple/node/cpus/arm/CmpARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/CmpFARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/CmpIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/DivARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/DivFARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/FloatARM.java | 4 +- .../seaofnodes/simple/node/cpus/arm/FunARM.java | 4 +- .../seaofnodes/simple/node/cpus/arm/I2F8ARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/IntARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LoadARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LslARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LslIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LsrARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/LsrIARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/MemOpARM.java | 5 +- .../seaofnodes/simple/node/cpus/arm/MulARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/MulFARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/NegARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/NewARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/NotARM.java | 3 +- .../com/seaofnodes/simple/node/cpus/arm/OrARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/OrIARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/SetARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/SplitARM.java | 5 +- .../seaofnodes/simple/node/cpus/arm/StoreARM.java | 4 +- .../seaofnodes/simple/node/cpus/arm/SubARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/SubFARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/SubIARM.java | 5 +- .../seaofnodes/simple/node/cpus/arm/TFPARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/TMPARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/UJmpARM.java | 3 +- .../seaofnodes/simple/node/cpus/arm/XorARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/XorIARM.java | 7 +- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/AUIPC.java | 3 +- .../simple/node/cpus/riscv/AddFRISC.java | 2 +- .../simple/node/cpus/riscv/AddIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/AddRISC.java | 2 +- .../simple/node/cpus/riscv/AndIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/AndRISC.java | 2 +- .../simple/node/cpus/riscv/BranchRISC.java | 3 +- .../simple/node/cpus/riscv/CallRISC.java | 6 +- .../simple/node/cpus/riscv/CallRRISC.java | 4 +- .../simple/node/cpus/riscv/DivFRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/DivRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/FltRISC.java | 4 +- .../seaofnodes/simple/node/cpus/riscv/FunRISC.java | 4 +- .../simple/node/cpus/riscv/I2F8RISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/ImmRISC.java | 2 +- .../simple/node/cpus/riscv/Int8RISC.java | 5 +- .../seaofnodes/simple/node/cpus/riscv/IntRISC.java | 2 +- .../com/seaofnodes/simple/node/cpus/riscv/LUI.java | 2 +- .../simple/node/cpus/riscv/LoadRISC.java | 2 +- .../simple/node/cpus/riscv/MemOpRISC.java | 4 +- .../simple/node/cpus/riscv/MulFRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/MulRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/NegRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/NewRISC.java | 3 +- .../seaofnodes/simple/node/cpus/riscv/NotRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/OrIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/OrRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/RetRISC.java | 4 +- .../simple/node/cpus/riscv/SetFRISC.java | 2 +- .../simple/node/cpus/riscv/SetIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/SetRISC.java | 2 +- .../simple/node/cpus/riscv/SllIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/SllRISC.java | 2 +- .../simple/node/cpus/riscv/SplitRISC.java | 4 +- .../simple/node/cpus/riscv/SraIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/SraRISC.java | 2 +- .../simple/node/cpus/riscv/SrlIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/SrlRISC.java | 2 +- .../simple/node/cpus/riscv/StoreRISC.java | 4 +- .../simple/node/cpus/riscv/SubFRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/SubRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/TFPRISC.java | 3 +- .../seaofnodes/simple/node/cpus/riscv/TMPRISC.java | 2 +- .../simple/node/cpus/riscv/UJmpRISC.java | 3 +- .../simple/node/cpus/riscv/XorIRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/XorRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 2 +- .../simple/node/cpus/x86_64_v2/AddFMemX86.java | 4 +- .../simple/node/cpus/x86_64_v2/AddFX86.java | 2 +- .../simple/node/cpus/x86_64_v2/AddIX86.java | 4 +- .../simple/node/cpus/x86_64_v2/AddMemX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CallRX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CallX86.java | 4 +- .../simple/node/cpus/x86_64_v2/CmpFX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CmpIX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CmpX86.java | 2 +- .../simple/node/cpus/x86_64_v2/DivFX86.java | 2 +- .../simple/node/cpus/x86_64_v2/DivX86.java | 2 +- .../simple/node/cpus/x86_64_v2/FltX86.java | 2 +- .../simple/node/cpus/x86_64_v2/FunX86.java | 2 +- .../simple/node/cpus/x86_64_v2/I2f8X86.java | 2 +- .../simple/node/cpus/x86_64_v2/ImmX86.java | 2 +- .../simple/node/cpus/x86_64_v2/IntX86.java | 2 +- .../simple/node/cpus/x86_64_v2/JmpX86.java | 3 +- .../simple/node/cpus/x86_64_v2/LeaX86.java | 2 +- .../simple/node/cpus/x86_64_v2/LoadX86.java | 9 +- .../simple/node/cpus/x86_64_v2/MemAddX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 4 +- .../simple/node/cpus/x86_64_v2/MulFX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MulIX86.java | 4 +- .../simple/node/cpus/x86_64_v2/MulX86.java | 2 +- .../simple/node/cpus/x86_64_v2/NegX86.java | 3 +- .../simple/node/cpus/x86_64_v2/NewX86.java | 2 +- .../simple/node/cpus/x86_64_v2/NotX86.java | 2 +- .../simple/node/cpus/x86_64_v2/RegX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SarIX86.java | 5 +- .../simple/node/cpus/x86_64_v2/SarX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SetX86.java | 3 +- .../simple/node/cpus/x86_64_v2/ShlIX86.java | 5 +- .../simple/node/cpus/x86_64_v2/ShlX86.java | 2 +- .../simple/node/cpus/x86_64_v2/ShrIX86.java | 5 +- .../simple/node/cpus/x86_64_v2/ShrX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SplitX86.java | 4 +- .../simple/node/cpus/x86_64_v2/StoreX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SubFX86.java | 2 +- .../simple/node/cpus/x86_64_v2/TFPX86.java | 2 +- .../simple/node/cpus/x86_64_v2/TMPX86.java | 8 +- .../simple/node/cpus/x86_64_v2/UJmpX86.java | 3 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 5 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 11 +- .../seaofnodes/simple/print/GraphVisualizer.java | 8 +- .../com/seaofnodes/simple/print/IRPrinter.java | 10 +- .../java/com/seaofnodes/simple/print/JSViewer.java | 10 +- .../seaofnodes/simple/print/SimpleWebSocket.java | 2 +- src/main/java/com/seaofnodes/simple/sys/sys.smp | 58 --- .../java/com/seaofnodes/simple/type/Field.java | 124 ++++-- src/main/java/com/seaofnodes/simple/type/Type.java | 370 ++++++++++++++-- .../com/seaofnodes/simple/type/TypeConAry.java | 53 ++- .../com/seaofnodes/simple/type/TypeConAryB.java | 6 +- .../com/seaofnodes/simple/type/TypeConAryI.java | 6 +- .../java/com/seaofnodes/simple/type/TypeFloat.java | 55 ++- .../com/seaofnodes/simple/type/TypeFunPtr.java | 234 +++++++--- .../com/seaofnodes/simple/type/TypeInteger.java | 79 ++-- .../java/com/seaofnodes/simple/type/TypeMem.java | 87 ++-- .../com/seaofnodes/simple/type/TypeMemPtr.java | 87 ++-- .../java/com/seaofnodes/simple/type/TypeNil.java | 14 +- .../java/com/seaofnodes/simple/type/TypePtr.java | 18 +- .../java/com/seaofnodes/simple/type/TypeRPC.java | 13 +- .../com/seaofnodes/simple/type/TypeStruct.java | 491 +++++++++++++------- .../java/com/seaofnodes/simple/type/TypeTuple.java | 113 ++--- src/main/java/com/seaofnodes/simple/util/Ary.java | 229 ++++++++++ .../java/com/seaofnodes/simple/util/AryInt.java | 192 ++++++++ src/main/java/com/seaofnodes/simple/util/SB.java | 99 +++++ .../java/com/seaofnodes/simple/util/Utils.java | 53 +++ 212 files changed, 2804 insertions(+), 1558 deletions(-) delete mode 100644 src/main/java/com/seaofnodes/simple/Ary.java delete mode 100644 src/main/java/com/seaofnodes/simple/SB.java delete mode 100644 src/main/java/com/seaofnodes/simple/Utils.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java delete mode 100644 src/main/java/com/seaofnodes/simple/sys/sys.smp create mode 100644 src/main/java/com/seaofnodes/simple/util/Ary.java create mode 100644 src/main/java/com/seaofnodes/simple/util/AryInt.java create mode 100644 src/main/java/com/seaofnodes/simple/util/SB.java create mode 100644 src/main/java/com/seaofnodes/simple/util/Utils.java (limited to 'src/main/java/com/seaofnodes') diff --git a/src/main/java/com/seaofnodes/simple/Ary.java b/src/main/java/com/seaofnodes/simple/Ary.java deleted file mode 100644 index f43179ad..00000000 --- a/src/main/java/com/seaofnodes/simple/Ary.java +++ /dev/null @@ -1,228 +0,0 @@ -package com.seaofnodes.simple; - -import java.lang.StringBuilder; -import java.lang.reflect.Array; -import java.util.*; - -// ArrayList with saner syntax -public class Ary extends AbstractList implements List { - public E[] _es; - public int _len; - - public Ary(E[] es) { this(es,es.length); } - public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; } - @SuppressWarnings("unchecked") - public Ary(Class clazz) { this((E[]) Array.newInstance(clazz, 1),0); } - - /** @return list is empty */ - public boolean isEmpty() { return _len==0; } - /** @return active list length */ - public int len() { return _len; } - public int size() { return len(); } - - /** @param i element index - * @return element being returned; throws if OOB - * @exception AIOOBE if !(0 <= i < _len) - */ - public E get( int i ) { return at(i); } - public E at( int i ) { - range_check(i); - return _es[i]; - } - public E atX( int i ) { - if( i >= _len ) return null; - return _es[i]; - } - - /** @return last element */ - public E last( ) { return at(_len-1); } - - /** Add element in amortized constant time - * @param e Element to add at end of list - **/ - public E push( E e ) { - if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); - return (_es[_len++] = e); - } - /** @return remove and return last element */ - public E pop( ) { - return _len==0 ? null : _es[--_len]; - } - @Override public E removeLast() { return pop(); } - - - /** Add element in amortized constant time - * @param e Element to add at end of list - * @return true */ - public boolean add( E e ) { - if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); - _es[_len++] = e; - return true; - } - - /** Fast, constant-time, element removal. Does not preserve order - * @param i element to be removed - * @return element removed */ - public E del( int i ) { - range_check(i); - E tmp = _es[i]; - _es[i]=_es[--_len]; - return tmp; - } - - /** Slow, linear-time, element removal. Preserves order. - * @param i element to be removed - * @return element removed */ - @Override public E remove( int i ) { - range_check(i); - E e = _es[i]; - System.arraycopy(_es,i+1,_es,i,(--_len)-i); - return e; - } - - /** Slow, linear-time, element insertion. Preserves order. - * @param i where to insert - * @return element inserted */ - public E insert( E e, int i ) { - setLen(_len+1); - System.arraycopy(_es,i,_es,i+1,_len-i); - _es[i] = e; - return e; - } - - - /** Remove all elements */ - public void clear( ) { _len=0; } - - /** Set existing element - * @param i element to set - * @param e value to set - * @return old value - * @exception AIOOBE if !(0 <= i < _len) - */ - public E set( int i, E e ) { - range_check(i); - E old = _es[i]; - _es[i] = e; - return old; - } - - /** Set existing element - * @param i element to set - * @param e value to set - * @return old value - * @exception AIOOBE if !(0 <= i < _len) - */ - public E setX( int i, E e ) { - if( i >= _len ) { - while( i >= _es.length ) _es = Arrays.copyOf( _es, _es.length << 1 ); - _len = i+1; - } - E old = _es[i]; - _es[i] = e; - return old; - } - - public Ary setLen( int len ) { - if( len > _len ) - while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); - _len = len; - while( _es.length > (len<<1) ) // Shrink if hugely too large - _es = Arrays.copyOf(_es,_es.length>>1); - Arrays.fill(_es,len,_es.length,null); - return this; - } - - public E swap( int i, int j ) { - range_check(i); - range_check(j); - E tmp = _es[i]; - if( i==j ) return tmp; - _es[i] = _es[j]; - _es[j] = tmp; - return tmp; - } - - - /** @param c Collection to be added */ - public boolean addAll( Collection c ) { - if( c==null ) return false; - for( E e : c ) add(e); - return true; - } - public Ary addAll( Iterable it ) { for( E e : it ) add(e); return this; } - - /** @param es Array to be added */ - public Ary addAll( F[] es ) { - if( es==null || es.length==0 ) return this; - while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); - System.arraycopy(es,0,_es,_len,es.length); - _len += es.length; - return this; - } - - /** @param c Collection to be added */ - public Ary addAll( Ary c ) { - if( c==null || c._len==0 ) return this; - while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); - System.arraycopy(c._es,0,_es,_len,c._len); - _len += c._len; - return this; - } - - /** @return compact array version */ - public E[] asAry() { return Arrays.copyOf(_es,_len); } - - /** Find the first matching element using ==, or -1 if none. Note that - * most del calls shuffle the list, so the first element might be random. - * @param e Element to find - * @return index of first matching element, or -1 if none */ - public int find( E e ) { - for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; - return -1; - } - - - /** @return an iterator */ - @Override public Iterator iterator() { return new Iter(); } - private class Iter implements Iterator { - int _i=0; - @Override public boolean hasNext() { return _i<_len; } - @Override public E next() { return _es[_i++]; } - } - - @Override public String toString() { - StringBuilder sb = new StringBuilder().append('{'); - for( int i=0; i<_len; i++ ) { - if( i>0 ) sb.append(','); - if( _es[i] != null ) sb.append(_es[i].toString()); - } - return sb.append('}').toString(); - } - - private void range_check( int i ) { - if( i < 0 || i>=_len ) - throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); - } - - // Note that the hashCode() and equals() are not invariant to changes in the - // underlying array. If the hashCode() is used (e.g., inserting into a - // HashMap) and the then the array changes, the hashCode() will change also. - @Override public boolean equals( Object o ) { - if( this==o ) return true; - if( !(o instanceof Ary ary) ) return false; - if( _len != ary._len ) return false; - if( _es == ary._es ) return true; - for( int i=0; i<_len; i++ ) - if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) ) - return false; - return true; - } - @Override public int hashCode( ) { - int sum=_len; - for( int i=0; i<_len; i++ ) - sum += _es[i]==null ? 0 : _es[i].hashCode(); - return sum; - } - -} diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 66e8a4a8..9ae4231e 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.JSViewer; import java.util.Arrays; @@ -81,6 +82,7 @@ public class IterPeeps { // there's a new user), and replace in the graph. if( x != n ) { for( Node z : n. _inputs ) _work.push(z); + for( Node z : x._outputs ) _work.push(z); n.subsume(x); } } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 23e9ddee..8a6b1967 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,7 +4,9 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.GraphVisualizer; import com.seaofnodes.simple.type.*; - +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.node.ScopeNode.Kind; import java.util.*; /** @@ -82,8 +84,7 @@ public class Parser { FunNode _fun; // Current function being parsed // 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. + // `type.str()` call. public static HashMap TYPES = defaultTypes(); // Mapping from a type name to the constructor for a Type. @@ -152,7 +153,7 @@ public class Parser { _xScopes.push(_scope); // Parse whole program, as-if function header "{ int arg -> body }" - parseFunctionBody(_code._main,loc(),"arg"); + parseFunctionBody( _code._main,loc(),"arg"); // Kill an empty default main. Keep only if it was explicitly defined // (programmer asked for a "main") or it has stuff (i.e. beginner @@ -188,10 +189,16 @@ public class Parser { /** * Parses a function body, assuming the header is parsed. */ - private ReturnNode parseFunctionBody(TypeFunPtr sig, Lexer loc, String... ids) { + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, String... ids) { + // If this is a method, record & restore the existing struct fields, + // which are also the struct initializers. The method might update + // mutable fields, so when the function parse is done reset back to + // pre-function-parse values. + Node[] preParse = new Node[_scope.nIns()]; + for( int i=0; i<_scope.nIns(); i++ ) + preParse[i] = _scope.in(i)==null ? null : _scope.in(i).keep(); + // Stack parser state on the local Java stack, and unstack it later - Node oldctrl = ctrl().keep(); - Node oldmem = _scope.mem().keep(); FunNode oldfun = _fun; ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; @@ -206,7 +213,7 @@ public class Parser { Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).peephole(); // Build a multi-exit return point for all function returns - RegionNode r = new RegionNode((Lexer)null,null,null).init(); + RegionNode r = new RegionNode( null,null,null).init(); assert r.inProgress(); PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null).init(); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); @@ -215,10 +222,11 @@ public class Parser { assert ret.inProgress(); _code._stop.addDef(ret); + // Pre-call the function from Start, with worse-case arguments. This // represents all the future, yet-to-be-parsed functions calls and // external calls. - _scope.push(ScopeNode.Kind.Function); + _scope.push(new Kind.Func()); ctrl(fun); // Scope control from function // Private mem alias tracking per function MemMergeNode mem = new MemMergeNode(true); @@ -237,8 +245,13 @@ public class Parser { last = parseStatement(); // Last expression is the return except for the top-level main - if( ctrl()._type==Type.CONTROL && fun.sig() != _code._main ) - fun.addReturn(ctrl(), _scope.mem().merge(), last); + if( ctrl()._type==Type.CONTROL ) + if( fun.sig() != _code._main ) + fun.addReturn(ctrl(), _scope.mem().merge(), 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(); @@ -259,9 +272,10 @@ public class Parser { _fun = oldfun; _breakScope = breakScope; _continueScope = continueScope; - // Reset control and memory to pre-function parsing days - ctrl(oldctrl.unkeep()); - _scope.mem(oldmem.unkeep()); + + // Reset all fields to pre-parse days + for( int i=0; i than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth - while( cur._lexSize.size() > _breakScope._lexSize.size() ) + while( cur.depth() > _breakScope.depth() ) cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the @@ -470,7 +484,7 @@ public class Parser { if( toScope == null ) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._lexSize.size() <= _breakScope._lexSize.size(); + assert toScope.depth() <= _breakScope.depth(); toScope.ctrl(toScope.mergeScopes(cur,loc()).peephole()); return toScope; } @@ -521,11 +535,11 @@ public class Parser { // Parse predicate require("("); var pred = require(parseAsgn(), ")"); - return parseTrinary(pred,true,"else"); + return parseTrinary(pred,"else"); } // Parse a conditional expression, merging results. - private Node parseTrinary( Node pred, boolean stmt, String fside ) { + private Node parseTrinary( Node pred, String fside ) { pred.keep(); // IfNode takes current control and predicate @@ -541,7 +555,15 @@ public class Parser { // Parse the true side ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection _scope.addGuards(ifT,pred,false); // Up-cast predicate - Node lhs = (stmt ? parseStatement() : parseAsgn()).keep(); // Parse true-side + // Parse true-side flavor + Node lhs = switch( fside ) { + case "else" -> parseStatement(); // if( pred ) stmts; + case ":" -> parseAsgn(); // pred ? asgn; + case "&&" -> parseLogical(); // pred && expr + case "||" -> pred; // pred || expr_is_ignored + default -> throw Utils.TODO(); + }; + lhs.keep(); _scope.removeGuards(ifT); // See if a one-sided def was made: "if(pred) int x = 1;" and throw. @@ -557,17 +579,23 @@ public class Parser { // Up-cast predicate, even if not else clause, because predicate can // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;` _scope.addGuards(ifF,pred,true); - boolean doRHS = match(fside); - Node rhs = (doRHS - ? (stmt ? parseStatement() : parseAsgn()) - : con(lhs._type.makeZero())).keep(); + // Parse false-side flavor + boolean doRHS = false; // RHS is optional for if/else and trinary + Node rhs = switch( fside ) { + case "else" -> (doRHS=match(fside)) ? parseStatement() : con(lhs._type.makeZero()); + case ":" -> (doRHS=match(fside)) ? parseAsgn() : con(lhs._type.makeZero()); + case "&&" -> rhs = pred; + case "||" -> rhs = parseLogical(); + default -> throw Utils.TODO(); + }; + rhs.keep(); _scope.removeGuards(ifF); if( doRHS ) fScope = _scope; pred.unkeep(); // Check the trinary widening int/flt - if( !stmt ) { + if( !fside.equals("else") ) { rhs = widenInt( rhs.unkeep(), lhs._type ).keep(); lhs = widenInt( lhs.unkeep(), rhs._type ).keep(); } @@ -581,10 +609,10 @@ public class Parser { // Merge results RegionNode r = ctrl(tScope.mergeScopes(fScope,loc())); - Node ret = peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs.unkeep(),rhs.unkeep())); + Node ret = peep(new PhiNode("",lhs._type.meet(rhs._type).glb(false),r,lhs.unkeep(),rhs.unkeep())); // Immediately fail e.g. `arg ? 7 : ptr` ParseException err; - if( !stmt && (err=ret.err()) !=null ) throw err; + if( !fside.equals("else") && (err=ret.err()) !=null ) throw err; r.peephole(); return ret; } @@ -621,27 +649,37 @@ public class Parser { private Node parseAsgn() { int old = pos(); String name = _lexer.matchId(); + int old_pre_equals = pos(); // Just a plain expression, no assignment. // Distinguish `var==expr` from `var=expr` if( name==null || KEYWORDS.contains(name) || !matchOpx('=','=') ) { pos(old); return parseExpression(); } - // Parse assignment expression - Node expr = parseAsgn(); - - // Final variable to update + // Find variable to update Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); + // If a method var, allow nested blocks and methods, but not fcns or other structs. + // Else safety check for accessing fields out of function scope. + if( instance(def) ) { + pos(old_pre_equals); // setup for `self.name = expr` + Node self = _scope.in(_scope.lookup("self")); // Insert self reference + return parsePostfixName(self,name); + } + // TOP fields are for late-initialized fields; these have never // been written to, and this must be the final write. Other writes // outside the constructor need to check the final bit. if( _scope.in(def._idx)._type!=Type.TOP && def._final && - // Inside a constructor, final assign is OK, outside nope - !(_scope.inConstructor() && def._idx >= _scope._lexSize.last()) ) + // Inside an allocation, final assign is OK, outside nope. + // The alloc() call added the allocation scope + !(_scope.inAllocation() && def._idx >= _scope._kinds.last(-1)._lexSize) ) throw error("Cannot reassign final '"+name+"'"); + // Parse assignment expression + Node expr = parseAsgn(); + // Lift expression, based on type Node lift = liftExpr(expr.keep(), def.type(), def._final, true); // Update @@ -653,7 +691,7 @@ public class Parser { // Make finals deep; widen ints to floats; narrow wide int types. // Early error if types do not match variable. private Node liftExpr( Node expr, Type t, boolean xfinal, boolean isLoad ) { - if( expr._type instanceof TypeMemPtr tmp && tmp.isFRef() ) + if( expr._type instanceof TypeMemPtr tmp && TYPES.get(tmp._obj._name).isFRef() ) throw error("Must define forward ref "+tmp._obj._name); // Final is deep on ptrs if( xfinal && t instanceof TypeMemPtr tmp ) { @@ -662,7 +700,7 @@ public class Parser { } // 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()))); + expr = peep(new AddNode(peep(new CastNode(t,ctrl(),expr)),off(tmp._obj,"[]"))); // Auto-widen int to float expr = widenInt( expr, t ); // Auto-narrow wide ints to narrow ints. For loads, emit code to force @@ -674,7 +712,7 @@ public class Parser { // Type is sane if( et!=Type.BOTTOM && !et.shallowISA(t) ) - throw error("Type " + et.str() + " is not of declared type " + t.str()); + expr = peep(new CastNode(t,null,expr)); return expr; } @@ -715,6 +753,7 @@ public class Parser { String name = requireId(); // Optional initializing expression follows boolean xfinal = false; + boolean fld_final = false; // Field is final, but not deeply final Node expr; if( match("=") ) { expr = isExternDecl() @@ -722,14 +761,18 @@ public class Parser { : parseAsgn(); // TOP means val and val is always final xfinal = (t==Type.TOP) || + expr instanceof ExternNode || // BOTTOM is var and var is always not-final (t!=Type.BOTTOM && // no Bang AND !hasBang && + // Locals are not-final by default + !_scope.inFunction() && // not-null (expecting null to be set to not-null) expr._type != Type.NIL && // Pointers are final by default; int/flt are not-final by default. (t instanceof TypeNil)); + // var/val, then type comes from expression if( inferType ) { if( expr._type==Type.NIL ) @@ -760,11 +803,15 @@ public class Parser { // the constructor and that's when we'll discover the type. case Type tt -> { assert tt==Type.BOTTOM; yield con(tt); } }; + // Nullable fields are set in the constructor, but remain shallow final. + // e.g. final pointer to a r/w array + if( t instanceof TypeNil tn && !tn.nullable() && !hasBang ) + fld_final = true; } // Lift expression, based on type Node lift = liftExpr(expr, t, xfinal, true); - + // Rebuild the deep RO 't', not returned from liftExpr if( xfinal && t instanceof TypeMemPtr tmp ) t = tmp.makeRO(); @@ -773,7 +820,7 @@ public class Parser { if( !lift._type.isa(t) ) lift = peep(new CastNode(t,null,lift)); // Define a new name - if( !_scope.define(name,t,xfinal,lift, loc) ) + if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); return lift; } @@ -793,30 +840,46 @@ public class Parser { String typeName = requireId(); if( old!=null ) typeName = old+"."+typeName; _nestedType = typeName; + // New declared or forward-ref type + TypeStruct ts = TYPES.get(typeName) instanceof TypeMemPtr tmp ? tmp._obj : TypeStruct.open(typeName); + TYPES.put(typeName,TypeMemPtr.make(ts)); // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(ScopeNode.Kind.Constructor); + _scope.push(new Kind.Define(TypeMemPtr.make(ts))); require("{"); - while (!peek('}') && !_lexer.isEOF()) + int lexlen = _scope._kinds.last()._lexSize, nvar=lexlen; + while (!peek('}') && !_lexer.isEOF()) { parseStatement().isKill(); + while( nvar < _scope._vars._len ) { + Var v = _scope.var(nvar++); + if( !v.isFRef() ) { + ts = ts.add( Field.make( v._name, v.type(), _code.getALIAS(), v._final, v._final && _scope.in( v._idx )._type != Type.TOP ) ); + TYPES.put( typeName, TypeMemPtr.make( ts ) ); + } + } + } - // Grab the declarations and build fields and a Struct - int lexlen = _scope._lexSize.last(); + // Count struct declarations int varlen = _scope._vars._len; - StructNode s = new StructNode(); - Ary fs = new Ary<>(Field.class); - for( int i=lexlen; i type }` or `{ type }`. @@ -916,7 +979,7 @@ public class Parser { Type t0 = type(); // Either return or first arg if( t0==null ) return posT(old); // Not a function if( match("}") ) // No-arg function { -> type } - return TypeFunPtr.make(match("?"),TypeTuple.BOT,t0); + return TypeFunPtr.make(match("?"),false,TypeFunPtr.TEMPTY,t0); Ary ts = new Ary<>(Type.class); ts.push(t0); // First argument while( true ) { @@ -924,7 +987,7 @@ public class Parser { Type ret = type(); if( ret==null || !match("}") ) return posT(old); // Not a function - return TypeFunPtr.make(match("?"),TypeTuple.make(ts.asAry()),ret); + return TypeFunPtr.make(match("?"),false,ts.asAry(),ret); } Type t1 = type(); if( t1==null ) return posT(old); // Not a function @@ -949,8 +1012,8 @@ public class Parser { * @return an expression {@link Node}, never {@code null} */ private Node parseExpression() { - Node expr = parseBitwise(); - return match("?") ? parseTrinary(expr,false,":") : expr; + Node expr = parseLogical(); + return match("?") ? parseTrinary(expr,":") : expr; } /** @@ -961,13 +1024,25 @@ public class Parser { * * @return a bitwise expression {@link Node}, never {@code null} */ + + private Node parseLogical() { + Node lhs = parseBitwise(); + while (true) { + if( false ) ; + else if( match("&&") ) lhs = parseTrinary(lhs, "&&"); + else if( match("||") ) lhs = parseTrinary(lhs, "||"); + else break; + } + return lhs; + } + private Node parseBitwise() { Node lhs = parseComparison(); while( true ) { if( false ) ; - else if( match("&") ) lhs = new AndNode(loc(),lhs,null); - else if( match("|") ) lhs = new OrNode(loc(),lhs,null); - else if( match("^") ) lhs = new XorNode(loc(),lhs,null); + else if( matchOp('&') ) lhs = new AndNode(loc(),lhs,null); + else if( matchOp('|') ) lhs = new OrNode(loc(),lhs,null); + else if( match ("^") ) lhs = new XorNode(loc(),lhs,null); else break; lhs.setDef(2,parseComparison()); lhs = peep(lhs); @@ -1103,14 +1178,17 @@ public class Parser { } if (match("-")) return peep(new MinusNode(parseUnary()).widen()); if (match("!")) return peep(new NotNode(parseUnary())); - return parsePostfix(parsePrimary()); + // Else be a primary expression + return parsePrimary(); } /** * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral | true | false | null | new Type | '(' expression ')' | Id['++','--']
+     *     primaryExpr : integerLiteral | "string" | 'char' | true | false | null |
+     *                   new Type | '(' expression ')' | Id['++','--'] |
+     *                   [static.]* Id
      *
* @return a primary {@link Node}, never {@code null} */ @@ -1121,43 +1199,96 @@ public class Parser { 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(),"}"); + if( match ("(" ) ) return parsePostfix(require(parseAsgn(), ")")); + if( matchx("new" ) ) return parsePostfix(alloc()); + if( match ("{" ) ) return parsePostfix(require(func(),"}")); // Parse static variable lookup: `type.fld` in the type namespace + // CNC: not a full type parse, just a typename parse + int pos = pos(); 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); + if( t!=null ) { + if( peek('.') ) + return parsePostfix(con(t)); + //pos(pos); // TODO: not a `type.fld` + //return null; + throw Utils.TODO(); } // Expect an identifier now - Var n = requireLookupId(); - Node rvalue = _scope.in(n); + + // - if null, make fref, normal var handling + // - if final constant, normal var handling + // - if method var, scan skipping blocks & methods, must hit correct struct no fcns + // - if normal var, scan skipping blocks, allowing last fcn + // - NO fcns nested in methods, NO methods nested in fcns + + String id = _lexer.matchId(); + if( id == null || KEYWORDS.contains(id) ) + throw errorSyntax("an identifier or expression"); + Var var = _scope.lookup(id); + + if( var==null ) { + // If missing, assume a forward reference + _scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc()); + var = _scope.lookup(id); + } + + // If a method var, allow nested blocks and methods, but not fcns or other structs. + // Else safety check for accessing fields out of function scope. + if( instance(var) ) { + Node self = _scope.in(_scope.lookup("self")); // Insert self reference + return parsePostfixName(self,id); + } + + // Load local value + Node rvalue = _scope.in(var); if( rvalue._type == Type.BOTTOM ) - if( rvalue instanceof FRefNode ) return rvalue; - else throw error("Cannot read uninitialized field '"+n._name+"'"); + if( rvalue instanceof FRefNode ) + return parsePostfix(rvalue); + else throw error("Cannot read uninitialized field '"+id+"'"); + // Check for assign-update, x += e0; char ch = _lexer.matchOperAssign(); - if( ch==0 ) return rvalue; - Node op = opAssign(ch,rvalue,n._final,n.type(),n._name); - _scope.update(n,op); + if( ch==0 ) // Normal primary, check for postfix updates + return parsePostfix(rvalue); + // Assign-update direct into Scope + Node op = opAssign(ch,rvalue, var.type() ); + _scope.update(var,op); return postfix(ch) ? rvalue.unkeep() : op; } + // true if instance variable lookup (var is in any number of nested blocks, + // then an instance function then inside a struct declaration). + private boolean instance(Var var ) { + // If a method var, allow nested blocks and methods, but not fcns or other structs + Kind kind = _scope.kind(var); + if( kind instanceof Kind.Define ) { + for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) { + Kind xkind = _scope._kinds.at(i); + if( xkind instanceof Kind.Block ) continue; + if( xkind instanceof Kind.Func ) { + if( _scope._kinds.at(i-1)==kind ) + return true; // Instance variable: lookup in a method in a decl + } + throw Utils.TODO(); + } + } else { + // If a normal var, allow any nested blocks, and a last fcn - + // but not functions further out (which involves capture). + Node def = _scope.in(var._idx); + for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) + if( _scope._kinds.at(i) instanceof Kind.Func && + !(def instanceof FRefNode) && !(var._final && def._type.isConstant()) ) + throw error("Variable '"+var._name+"' is out of function scope and must be a final constant"); + } + return false; + } + // Check for assign-update, "x += e0". // Returns "x + e0"; the caller assigns value. // if ch is postfix, then lhs is kept and caller will unkeep and return it. - private Node opAssign(char ch, Node lhs, boolean xfinal, Type t, String name ) { - if( xfinal ) - throw error("Cannot reassign final '"+name+"'"); + private Node opAssign( char ch, Node lhs, Type t ) { // RHS of the update. lhs.keep(); // Alive across parseAsgn Node rhs = @@ -1184,30 +1315,6 @@ 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"); - Var n = _scope.lookup(id); - // If missing, assume a forward reference - if( n==null ) { - _scope.define(id, FRefNode.FREF_TYPE, true, XCTRL, loc()); - n = _scope.lookup(id); - } else { - // Lookup worked on an out-of-function value. - if( _scope.outOfFunction(n) ) { - // No closures, so this has to be a final constant (which - // includes forward refs) - Node def = _scope.in(n._idx); - if( !(def instanceof FRefNode) && !(n._final && def._type.isConstant()) ) - throw error("Variable '"+n._name+"' is out of function scope and must be a final constant"); - } - } - return n; - } - /** Parse an allocation */ @@ -1222,7 +1329,7 @@ public class Parser { if( !(len._type instanceof TypeInteger) ) throw error("Cannot allocate an array with length "+len._type); require("]"); - TypeMemPtr tmp = typeAry(t); + TypeMemPtr tmp = typeAry(t,false); return newArray(tmp._obj,len); } @@ -1241,19 +1348,23 @@ public class Parser { if( hasConstructor ) { idx = _scope.nIns(); // Push a scope, and pre-assign all struct fields. - _scope.push(ScopeNode.Kind.Block); + _scope.push(new Kind.Block()); Lexer loc = loc(); for( int i=0; i ALTMP = new Ary<>(Node.class); private Node newArray(TypeStruct ary, Node len) { - int base = ary.aryBase (); + ConFldOffNode base = off(ary, "[]"); int scale= ary.aryScale(); - Node size = peep(new AddNode(con(base),peep(new ShlNode(null,len.keep(),con(scale))))); - ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeZero())); + Node size = peep(new AddNode(base,peep(new ShlNode(null,len.keep(),con(scale))))); + ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._t.makeZero())); return newStruct(ary,size,0,ALTMP); } private Node newString(String s) { - TypeMemPtr tmp = typeAry(TypeInteger.U8); + TypeMemPtr tmp = typeAry(TypeInteger.U8,true); int lenAlias = tmp._obj.field("#" )._alias; int elemAlias = tmp._obj.field("[]")._alias; TypeConAryB con = TypeConAryB.make(s); @@ -1312,7 +1425,8 @@ public class Parser { // 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); + TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", TypeInteger.constant(s.length()), lenAlias, con, elemAlias, true),true); + assert str.isConstant(); return con(str); } @@ -1341,9 +1455,24 @@ public class Parser { if( match(".") ) name = requireId(); else if( match("#") ) name = "#"; else if( match("[") ) name = "[]"; - else if( match("(") ) return parsePostfix(require(functionCall(expr),")")); + else if( match("(") ) return parsePostfix(require(functionCall(expr,null),")")); else return expr; // No postfix + return parsePostfixName(expr,name); + } + + /** + * Parse postfix expression; this can be a field expression, an array + * lookup or a postfix operator like '#' + * + * 
+     *     expr ['++' | '--' ]                 // Postfix unary write operator
+     *     expr [ [op]= expr ]                 // Field reference
+     *     expr ('[' expr ']')* [ [op]= expr ] // Array reference
+     *
+ */ + private Node parsePostfixName(Node expr, String name) { + if( expr._type==Type.NIL ) throw error("Accessing unknown field '" + name + "' from 'null'"); @@ -1352,23 +1481,25 @@ public class Parser { throw error( "Expected "+(name=="#" || name=="[]" ? "array" : "reference")+" but found " + expr._type.str() ); // Find the field from the Type. Lookup in the base object field names. + TypeMemPtr ptr2 = (TypeMemPtr)TYPES.get(ptr._obj._name); + ptr = (TypeMemPtr)ptr.join(ptr2);// Upgrade to latest TYPES TypeStruct base = ptr._obj; - assert !base.isFRef(); int fidx = base.find(name); - if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + if( fidx == -1 ) + throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); // Get field type and layout offset from base type and field index fidx Field f = base._fields[fidx]; // Field from field index - Type tf = f._type; + Type tf = f._t; if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); // Field offset; fixed for structs, computed for arrays Node off = (name.equals("[]") // If field is an array body // Array index math - ? peep(new AddNode(con(base.aryBase()),peep(new ShlNode(null,require(parseAsgn(),"]"),con(base.aryScale()))))) + ? peep(new AddNode(off(base,"[]"),peep(new ShlNode(null,require(parseAsgn(),"]"),con(base.aryScale()))))) // Struct field offsets are hardwired - : con(base.offset(fidx))).keep(); + : off(base,name)).keep(); // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( matchOpx('=','=') ) { @@ -1384,7 +1515,12 @@ public class Parser { return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } - Node load = new LoadNode(loc(),name, f._alias, tf, memAlias(f._alias), expr.keep(), off); + // Keep expr for possible store update + expr.keep(); + // Load field + Node load = f._one && INITS.containsKey( base._name ) + ? INITS.get(base._name).in(base.find(name)) + : new LoadNode(loc(),name, f._alias, tf, memAlias(f._alias), expr, off); // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. @@ -1394,8 +1530,8 @@ public class Parser { // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" char ch = _lexer.matchOperAssign(); if( ch!=0 ) { - Node op = opAssign(ch,load,f._final,tf,name); - Node st = new StoreNode(loc(), name, f._alias, tf, memAlias(f._alias), expr.unkeep(), off, op, false); + Node op = opAssign(ch,load, tf ); + Node st = new StoreNode(loc(), name, f._alias, tf, memAlias(f._alias), expr.unkeep(), off.unkeep(), op, false); // Arrays include control, as a proxy for a safety range check. // Structs don't need this; they only need a NPE check which is // done via the type system. @@ -1403,8 +1539,25 @@ public class Parser { memAlias(f._alias, peep(st)); load = postfix(ch) ? load.unkeep() : op; // And use the original loaded value as the result - } else expr.unkill(); - off.unkill(); + return load; + //throw Utils.TODO(); // NO POSTFIX AFTER STORE, JUST RETURN + } else { + off.unkill(); + // Method call: Loaded a function from a named field, AND the base + // field type is final. + if( load._type instanceof TypeFunPtr && name!="[]" && + !(load instanceof ExternNode) && + ((TypeMemPtr)TYPES.get(base._name))._obj.field(name)._final && + // And calling a function + match("(") ) { + return parsePostfix(require(functionCall(load,expr),")")); + } + + // Drop expr, keeping load alive + load.keep(); + expr.unkill(); + load.unkeep(); + } return parsePostfix(load); } @@ -1440,6 +1593,17 @@ public class Parser { private Node func() { Ary ts = new Ary<>(Type.class); Ary ids = new Ary<>(String.class); + + // Defined in constructor? Add `self` argument. "static" calls still + // add a `self` they just ignore it. + if( _scope._kinds.last() instanceof Kind.Define define ) { + // Upgrade defined struct to latest fields + TypeMemPtr tmp = (TypeMemPtr)TYPES.get(define._tmp._obj._name); + ts .push(tmp); + ids.push("self"); + } + + // Parse other arguments _lexer.skipWhiteSpace(); Lexer loc = loc(); // First argument location while( true ) { @@ -1452,7 +1616,7 @@ public class Parser { } require("->"); // Make a concrete function type, with a fidx - TypeFunPtr tfp = _code.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); + TypeFunPtr tfp = _code.makeFun(TypeFunPtr.make(false,false,ts.asAry(),Type.BOTTOM)); ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry()); return con(ret._fun.sig()); } @@ -1463,16 +1627,18 @@ public class Parser { * ( arg* ) * */ - private Node functionCall(Node expr) { - if( expr._type == Type.NIL ) + private Node functionCall(Node fcn, Node self) { + if( fcn._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(false).str()); - expr.keep(); // Keep while parsing args + if( !(fcn instanceof FRefNode) && !fcn._type.isa(TypeFunPtr.BOT) ) + throw error("Expected a function but got "+fcn._type.glb(false).str()); + fcn.keep(); // Keep while parsing args Ary args = new Ary<>( Node.class ); args.push(null); // Space for ctrl,mem args.push(null); + if( self != null ) // Method call has a self + args.push(self); while( !peek(')') ) { Node arg = parseAsgn(); if( arg==null ) break; @@ -1482,7 +1648,7 @@ public class Parser { // Control & memory after parsing args args.set(0,ctrl().keep()); args.set(1,_scope.mem().merge().keep()); - args.push(expr); // Function pointer + args.push(fcn); // Function pointer // Unkeep them all for( Node arg : args ) arg.unkeep(); @@ -1521,8 +1687,8 @@ public class Parser { } // 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 + if( t instanceof TypeFunPtr tfp ) // Generic TFP from type parse + t = _code.makeFun(tfp); // Get a FIDX, becomes a constant return new ExternNode(t,ex).peephole(); } @@ -1537,6 +1703,7 @@ public class Parser { private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } public static Node con( long con ) { return con==0 ? ZERO : con(TypeInteger.constant(con)); } public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } + public static ConFldOffNode off( TypeStruct base, String fname ) { return (ConFldOffNode)(new ConFldOffNode(base._name,fname).peephole()); } public Node peep( Node n ) { // Peephole, then improve with lexically scoped guards return _scope.upcastGuard(n.peephole()); @@ -1565,6 +1732,7 @@ public class Parser { private boolean match (String syntax) { return _lexer.match (syntax); } // Match must be "exact", not be followed by more id letters private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + private boolean matchOp(char c0 ) { return _lexer.matchOp(c0); } private boolean matchOpx(char c0, char c1) { return _lexer.matchOpx(c0,c1); } // Return true and do NOT skip if 'ch' is next private boolean peek(char ch) { return _lexer.peek(ch); } @@ -1740,6 +1908,16 @@ public class Parser { _position -= syntax.length(); return false; } + // Match this char, and the next char must be different. + // Handles '&&' vs '&' + boolean matchOp( char c0 ) { + skipWhiteSpace(); + if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c0 ) + return false; + inc(); + return true; + } + // Match these two characters in a row boolean matchOpx(char c0, char c1) { skipWhiteSpace(); if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c1 ) @@ -1861,4 +2039,5 @@ public class Parser { //String msg = "src:"+_line_number+":"+(_position-_line_start)+" "+errorMessage; ParseException( String msg, Lexer loc ) { super(msg); _loc = loc; } } + } diff --git a/src/main/java/com/seaofnodes/simple/SB.java b/src/main/java/com/seaofnodes/simple/SB.java deleted file mode 100644 index 978fbed9..00000000 --- a/src/main/java/com/seaofnodes/simple/SB.java +++ /dev/null @@ -1,99 +0,0 @@ -package com.seaofnodes.simple; - -/** Tight/tiny StringBuilder wrapper. - * Short short names on purpose; so they don't obscure the printing. - * Can't believe this wasn't done long, long ago. */ -public final class SB { - private final StringBuilder _sb; - private int _indent = 0; - public SB( ) { _sb = new StringBuilder( ); } - public SB(String s) { _sb = new StringBuilder(s); } - public SB p( String s ) { _sb.append(s); return this; } - public SB p( float s ) { - if( Float.isNaN(s) ) - _sb.append( "Float.NaN"); - else if( Float.isInfinite(s) ) { - _sb.append(s > 0 ? "Float.POSITIVE_INFINITY" : "Float.NEGATIVE_INFINITY"); - } else _sb.append(s); - return this; - } - public SB p( double s ) { - if( Double.isNaN(s) ) - _sb.append("Double.NaN"); - else if( Double.isInfinite(s) ) { - _sb.append(s > 0 ? "Double.POSITIVE_INFINITY" : "Double.NEGATIVE_INFINITY"); - } else _sb.append(s); - return this; - } - public SB p( char s ) { _sb.append(s); return this; } - public SB p( int s ) { _sb.append(s); return this; } - public SB p( long s ) { _sb.append(s); return this; } - public SB p( boolean s) { _sb.append(s); return this; } - // 1 byte, 2 hex digits, 8 bits - public SB hex1(int s) { - int digit = (s>>4) & 0xf; - _sb.append((char)((digit <= 9 ? '0' : ('A'-10))+digit)); - digit = s & 0xf; - _sb.append((char)((digit <= 9 ? '0' : ('A'-10))+digit)); - return this; - } - // 2 bytes, 4 hex digits, 16 bits, Big Endian - public SB hex2(int s) { return hex1(s>> 8).hex1(s); } - // 4 bytes, 8 hex digits, 32 bits, Big Endian - public SB hex4(int s) { return hex2(s>>16).hex2(s); } - // 8 bytes, 16 hex digits, 64 bits, Big Endian - public SB hex8(long s) { return hex4((int)(s>>32)).hex4((int)s); } - - // Fixed width field - public SB fix( int sz, String s ) { - for( int i=0; i void del(ArrayList array, int i) { - E last = array.removeLast(); - if (i < array.size()) array.set(i, last); - } - - /** - * Search a list for an element by reference - * - * @param ary List to search in - * @param x Object to be searched - * @return >= 0 on success, -1 on failure - */ - public static int find( ArrayList ary, E x ) { - for( int i=0; i= 0 on success, -1 on failure - */ - public static int find( E[] ary, E x ) { - for( int i=0; i>>n); } - - // Fold a 64bit hash into 32 bits - public static int fold( long x ) { return (int)((x>>32) ^ x); } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java index e2fac779..689ceceb 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import java.util.IdentityHashMap; diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index adb71413..6c958f32 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,13 +1,14 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.*; +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; import java.io.IOException; -import java.util.BitSet; -import java.util.HashMap; -import java.util.IdentityHashMap; +import java.util.*; @SuppressWarnings("unchecked") public class CodeGen { @@ -37,9 +38,13 @@ public class CodeGen { public final TypeInteger _arg; // --------------------------- - public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); } - public CodeGen( String src, TypeInteger arg, long workListSeed ) { + public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L, true ); } + public CodeGen( String src, TypeInteger arg) { this(src, arg==null ? TypeInteger.BOT : arg, 123L, true ); } + + public CodeGen( String src, TypeInteger arg, long workListSeed, boolean reset ) { CODE = this; + if( reset ) Type.reset(); + _main = makeFun(TypeFunPtr.MAIN); _phase = null; _callingConv = null; _start = new StartNode(arg); @@ -119,18 +124,15 @@ public class CodeGen { // are structurally equal. public final HashMap _gvn = new HashMap<>(); - // Compute "function indices": FIDX. - // Each new request at the same signature gets a new FIDX. - private final HashMap FIDXS = new HashMap<>(); - public TypeFunPtr makeFun( TypeTuple sig, Type ret ) { - Integer i = FIDXS.get(sig); - int fidx = i==null ? 0 : i; - FIDXS.put(sig,fidx+1); // Track count per sig + // + private int _fidx =0; + public TypeFunPtr makeFun( TypeFunPtr fun ) { + int fidx = _fidx++; assert fidx<64; // TODO: need a larger FIDX space - return TypeFunPtr.make((byte)2,sig,ret, 1L< x._nid - y._nid ); + _tOpto = (int)(System.currentTimeMillis() - t0); // TODO: @@ -212,7 +234,7 @@ public class CodeGen { // loop unroll, peel, RCE, etc return this; } - public N add( N n ) { return (N)_iter.add(n); } + public N add( N n ) { return _iter.add(n); } public void addAll( Ary ary ) { _iter.addAll(ary); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 0eaaae7b..8f9e2981 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.Encoding.BAOS; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.codegen.Encoding.BAOS; +import com.seaofnodes.simple.util.Ary; import java.io.*; import java.nio.ByteBuffer; import java.nio.ByteOrder; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index db799b98..1065cd9f 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,11 +1,11 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.io.ByteArrayOutputStream; import java.util.*; @@ -45,6 +45,9 @@ public class Encoding { public int [] _opStart; // Start of opcodes, by _nid public byte[] _opLen; // Length of opcodes, by _nid + // Function headers now padded when printing + public boolean _padFunHeads; + // Big Constant relocation info. public static class Relo { public final Node _op; @@ -290,6 +293,9 @@ public class Encoding { // Fall/false into a full block, Jump/true to an empty block. if( f.nOuts()>1 && t.nOuts()==1 ) return false; if( t.nOuts()>1 && f.nOuts()==1 ) return true ; + // Jump to a merge point, assuming other things are jumping there as well + if( f.out(0) instanceof RegionNode ) return true ; + if( t.out(0) instanceof RegionNode ) return false; // Everything else equal, use pre-order return t._pre > f._pre; } @@ -397,7 +403,7 @@ public class Encoding { if( n instanceof MachNode && !(n instanceof CFGNode) ) _opStart[n._nid] += slide; } - + _padFunHeads = true; // Copy/slide the bits to make space for all the longer branches int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1]; @@ -414,6 +420,7 @@ public class Encoding { } _bits.set(bits,bits.length); } + } @@ -492,12 +499,11 @@ public class Encoding { 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(); + ((TypeConAry)f._t).write(bits); + off += ((TypeConAry)f._t).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); + int log = f._t.log_size(); + addN(log,f._t,bits); off += 1<= 2 && !lhs.inProgress() && - lhs.region()==rhs.region() ) { + lhs.region()==rhs.region() && + lhs.nIns()>2 && // A 1-input Phi will collapse already + // Disallow with self-looping phi; these will collapse + (lhs.in(2)!=lhs && rhs.in(2)!=rhs) ) { // Profit check: only 1 instance of `this` will remain, all the // others will fold to constants. int cnt=0; @@ -73,7 +76,7 @@ public abstract class ArithNode extends Node { : 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 new PhiNode(label,lhs._minType,ns).peephole(); } } 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 301e1517..2765c308 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import static com.seaofnodes.simple.type.TypeInteger.*; @@ -33,7 +33,7 @@ abstract public class BoolNode extends Node { Type t2 = in(2)._type; // Exactly equals? if( t1.isHigh() || t2.isHigh() ) - return BOOL.dual(); + return (TypeInteger)BOOL.dual(); if( in(1)==in(2) ) // LT fails, both EQ and LE succeed return this instanceof LT ? FALSE : TRUE; diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 1dddc171..b9c70e5f 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import java.util.HashMap; import java.util.HashSet; @@ -59,7 +59,7 @@ public abstract class CFGNode extends Node { // Used by the encoding / final BB layout public CFGNode uctrlSkipEmpty() { CFGNode x = this, y; - while( x.nOuts() == 1 && (y=x.uctrl())!=null ) // Skip empty blocks + while( x.nOuts() == 1 && (y=x.uctrl())!=null && !(y instanceof CallNode) ) // Skip empty blocks x = y; return x; } @@ -89,6 +89,7 @@ public abstract class CFGNode extends Node { var comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); + if( lhs==null || rhs==null ) return null; } return lhs; } diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 94770f16..a6e21ea0 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; public class CProjNode extends CFGNode { diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndMach.java b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java index 47cab07a..d26ea33b 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndMach.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndMach.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.util.SB; public class CallEndMach extends CallEndNode implements MachNode { public CallEndMach( CallEndNode n ) { super(n); } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index cf3f337c..d95af697 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -74,10 +74,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 instanceof FunNode) && idom!=null ) idom = idom.idom(); // Inline? - if( idom != fun ) { + if( idom != fun && idom != null ) { // Trivial inline: rewrite _folding = true; // Rewrite Fun so the normal RegionNode ideal collapses @@ -86,6 +86,11 @@ public class CallEndNode extends CFGNode implements MultiNode { fun.setDef(2,call.ctrl()); // Bypass the Call; fun.ret().setDef(3,null); // Return is folding also CodeGen.CODE.addAll(fun._outputs); + // Repeat defs 1 layer down, for users of Parm (Phis) + for( Node parm : fun._outputs ) + if( parm instanceof ParmNode ) + CodeGen.CODE.addAll(parm._outputs); + // Inlining immediately blows all cache idepth fields past the inline point. // Bump the global version number invalidating them en-masse. CodeGen.CODE.invalidateIDepthCaches(); @@ -105,5 +110,4 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Node pcopy(int idx) { return _folding ? in(1).in(idx) : null; } - } diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index 8b243e87..ba08c87a 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -1,11 +1,11 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; /** @@ -162,8 +162,10 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i * Constants have no semantic inputs. However, we set Start as an input to * Constants to enable a forward graph walk. This edge carries no semantic @@ -26,8 +22,7 @@ public class ConstantNode extends Node { super(new Node[]{CodeGen.CODE._start}); _con = _type = type; } - public ConstantNode( Node con, Type t ) { super(con); _con = t; } - public ConstantNode( ConstantNode con ) { this(con,con._type); } + public ConstantNode( ConstantNode con ) { super(con); _con = con._type; } public static Node make( Type type ) { if( type==Type. CONTROL ) return new CtrlNode(); @@ -36,10 +31,8 @@ public class ConstantNode extends Node { } @Override public String label() { return "#"+_con; } - @Override public String glabel() { return _con.gprint(new SB().p("#")).toString(); } - - @Override - public String uniqueName() { return "Con_" + _nid; } + @Override public String glabel() { return "#"+_con.gprint(); } + @Override public String uniqueName() { return "Con_" + _nid; } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -48,23 +41,12 @@ public class ConstantNode extends Node { if( fun!=null && fun._name != null ) return sb.append("{ ").append(fun._name).append("}"); } - return sb.append(_con==null ? "---" : _con.print(new SB())); + return sb.append(_con==null ? "---" : _con.toString()); } @Override public boolean isConst() { return true; } - - @Override - public Type compute() { return _con; } - - @Override - public Node idealize() { return null; } - - @Override - public boolean eq(Node n) { - ConstantNode con = (ConstantNode)n; // Contract - return _con==con._con; - } - - @Override - int hash() { return _con.hashCode(); } + @Override public Type compute() { return _con; } + @Override public Node idealize() { return null; } + @Override public boolean eq(Node n) { return _con==((ConstantNode)n)._con; } + @Override int hash() { return _con.hashCode(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/src/main/java/com/seaofnodes/simple/node/ExternNode.java index 33fc0c1e..a10bb84a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -1,10 +1,10 @@ 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.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.util.SB; import java.util.BitSet; /** @@ -16,7 +16,7 @@ public class ExternNode extends ConstantNode { public ExternNode(Type t, String ex) { super(t); _extern = ex; } @Override public String label() { return "#"+_con+":"+_extern; } - @Override public String glabel() { return _con.gprint(new SB().p("#")).p(":").p(_extern).toString(); } + @Override public String glabel() { return _con.print(new SB().p("#"), new BitSet(), true).p(":").p(_extern).toString(); } @Override public String uniqueName() { return "Extern_" + _nid; } @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 81fa627a..4bd0fd97 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -1,13 +1,14 @@ package com.seaofnodes.simple.node; - -import com.seaofnodes.simple.*; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import static com.seaofnodes.simple.codegen.CodeGen.CODE; @@ -125,10 +126,10 @@ public class FunNode extends RegionNode { return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1); } // Bypass Region idom, always assume idom is Start - @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : cfg(1); } + @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : (nIns()>1 ? cfg(1) : null); } // Always in-progress until we run out of unknown callers - public boolean unknownCallers() { return nIns()<2 || 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/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 5d90449e..c5d687e5 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; public class IfNode extends CFGNode implements MultiNode { @@ -87,8 +87,8 @@ public class IfNode extends CFGNode implements MultiNode { return switch( bop ) { case "<" -> ">" ; case "<=" -> ">="; - case "==" -> "!="; - case "!=" -> "=="; + case "==" -> "=="; + case "!=" -> "!="; case ">" -> "<" ; case ">=" -> "<="; default -> throw Utils.TODO(); diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index eebe94a3..b58ea498 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; /** @@ -33,15 +34,21 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem ) { - // Update declared forward ref to the actual - if( _declaredType.isFRef() && mem._t instanceof TypeMemPtr tmp && !tmp.isFRef() ) - _declaredType = tmp; - // No lifting if ptr might null-check - if( err()==null ) - return _declaredType.join(mem._t); + if( !(mem()._type instanceof TypeMem mem) ) + return _declaredType; // No memory yet? Declared type + assert !_declaredType.isFRef(); + // No lifting if ptr might null-check + if( err()!=null || !(ptr()._type instanceof TypeMemPtr tmp) ) + return _declaredType; // No pointer yet? Declared type + Type t = tmp._obj.field(_name)._t; + if( t instanceof TypeConAry ary ) { + t = ary.elem(); // TODO: if offset is known, can peek the constant } - return _declaredType; + // Lift from declared type and memory input + t = t.join(_declaredType).join(mem._t); + if( _declaredType.isFinal() ) + t = t.makeRO(); // Deep final applied + return t; } @Override @@ -49,6 +56,11 @@ public class LoadNode extends MemOpNode { Node ptr = ptr(); Node mem = mem(); + if( mem instanceof CastNode cast ) { + setDef(1,cast.in(1)); + return this; + } + // Simple Load-after-Store on same address. if( mem instanceof StoreNode st && ptr == st.ptr() && off() == st.off() ) { // Must check same object @@ -58,7 +70,11 @@ public class LoadNode extends MemOpNode { // Simple load-after-MemMerge to a known alias can bypass. Happens when inlining. if( mem instanceof MemMergeNode mem2 ) { - setDef(1,mem2.alias(_alias)); + Node memA = mem2.alias(_alias); + for( Node ld : memA._outputs ) + if( ld instanceof LoadNode ) + CodeGen.CODE.add(ld); + setDef(1,memA); return this; } @@ -111,6 +127,7 @@ public class LoadNode extends MemOpNode { default: throw Utils.TODO(); } break; + case CastNode cast: mem = cast.in(1); break; case MemMergeNode merge: mem = merge.alias(_alias); break; default: @@ -147,7 +164,7 @@ public class LoadNode extends MemOpNode { // Load a flavored zero from a New private Node zero(NewNode nnn) { TypeStruct ts = nnn._ptr._obj; - Type zero = ts._fields[ts.findAlias(_alias)]._type.makeZero(); + Type zero = ts._fields[ts.findAlias(_alias)]._t.makeZero(); return castRO(new ConstantNode(zero).peephole()); } @@ -187,7 +204,7 @@ public class LoadNode extends MemOpNode { Node px = phi.in(idx); if( px==null ) return false; if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; - if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) return true; + if( px instanceof StoreNode st1 && ptr()==addDep(st1.ptr() )&& off()==st1.off() ) return true; addDep(px); return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index ec9055dc..fc50e17f 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -1,11 +1,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import java.util.HashSet; @@ -48,7 +48,7 @@ public class LoopNode extends RegionNode { x = x.idom(); } // Found a no-exit loop. Insert an exit - NeverNode iff = new NeverNode(back()); // Ideal never-branch + NeverNode iff = (NeverNode)new NeverNode(back()).peephole(); // Ideal never-branch CProjNode t = new CProjNode(iff,0,"True" ).init(); CProjNode f = new CProjNode(iff,1,"False").init(); setDef(2,t); // True continues loop, False (never) exits loop @@ -78,17 +78,19 @@ public class LoopNode extends RegionNode { expr = new PhiNode(r,expr).init(); } // Append new Never exit - ctrl.addDef(f ); - mem .addDef(memout); - expr.addDef(top); + ctrl.keep().addDef(f ); + mem .keep().addDef(memout); + expr.keep().addDef(top); } else { - ctrl = f; - mem = memout; - expr = top; + ctrl = f .keep(); + mem = memout.keep(); + expr = top .keep(); } - ret.setDef(0,ctrl); - ret.setDef(1,mem ); - ret.setDef(2,expr); + ret.setDef(0,ctrl.unkeep()); + ret.setDef(1,mem .unkeep()); + ret.setDef(2,expr.unkeep()); + ret._type = null; // This may LIFT the Return type, from [XCtrl,mem,expr] to [Ctrl,mem,expr] + ret.setType(ret.compute()); return stop; } diff --git a/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java b/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java index b01b3308..9440a7ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MachConcreteNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.Utils; import java.io.ByteArrayOutputStream; import java.util.BitSet; diff --git a/src/main/java/com/seaofnodes/simple/node/MachNode.java b/src/main/java/com/seaofnodes/simple/node/MachNode.java index f63b3651..c0b3af66 100644 --- a/src/main/java/com/seaofnodes/simple/node/MachNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MachNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; public interface MachNode { diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 9f2fdd16..19acc5b9 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -67,9 +67,12 @@ public class MemMergeNode extends Node { // Fold defaults into the default boolean progress=false, allDefault=true; - for( int i=2; i 0 || i._max < 0) ) return TypeInteger.FALSE; diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 32e41f54..a14a4fb9 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.BitSet; @@ -13,7 +12,7 @@ public class ParmNode extends PhiNode { super(label,declaredType,inputs); _idx = idx; } - public ParmNode(ParmNode parm) { super(parm, parm._label, parm._declaredType); _idx = parm._idx; } + public ParmNode(ParmNode parm) { super(parm, parm._label, parm._minType ); _idx = parm._idx; } @Override public String label() { return MemOpNode.mlabel(_label); } @@ -37,14 +36,8 @@ public class ParmNode extends PhiNode { } - @Override - public Node idealize() { - if( inProgress() ) return null; - return super.idealize(); - } - // Always in-progress until we run out of unknown callers - @Override public boolean inProgress() { return fun().inProgress(); } + @Override public boolean inProgress() { return in(0) instanceof FunNode fun && 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 971b52ae..fcbacbc9 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,25 +1,34 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; public class PhiNode extends Node { public final String _label; - // The Phi type we compute must stay within the domain of the Phi. - // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. - final Type _declaredType; - - public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } - public PhiNode(PhiNode phi, String label, Type declaredType) { super(phi); _label = label; _type = _declaredType = declaredType; } - public PhiNode(PhiNode phi) { super(phi); _label = phi._label; _declaredType = phi._declaredType; } + // The Phi type we compute must stay within the domain of the Phi. Example + // Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. + Type _minType; + public PhiNode(String label, Type minType, Node... inputs) { + super(inputs); + _label = label; + assert minType!=null; + _minType = minType; + } + // Used by ParmNode + public PhiNode(PhiNode phi, String label, Type minType) { super(phi); _label = label; _type = _minType = minType; } + // Used by instruction Selection + public PhiNode(PhiNode phi) { this(phi,phi._label,phi._minType ); } + // Used by the infinite-loop exit breaker public PhiNode(RegionNode r, Node sample) { super(new Node[]{r}); _label = ""; - _declaredType = sample._type; + _minType = sample._type; while( nIns() < r.nIns() ) addDef(sample); } @@ -44,7 +53,7 @@ public class PhiNode extends Node { } public CFGNode region() { return (CFGNode)in(0); } - @Override public boolean isMem() { return _declaredType instanceof TypeMem; } + @Override public boolean isMem() { return _minType instanceof TypeMem; } @Override public boolean isPinned() { return true; } @Override @@ -52,14 +61,19 @@ public class PhiNode extends Node { if( !(region() instanceof RegionNode r) ) return region()._type==Type.XCONTROL ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. - if( r.inProgress() ) return _declaredType; + if( r.inProgress() ) return _minType; // Set type to local top of the starting type - Type t = _declaredType.glb(false).dual();//Type.TOP; + //Type t = _minType.dual(); + Type t = Type.TOP; for (int i = 1; i < nIns(); i++) // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. - if( addDep(r.in(i))._type != Type.XCONTROL ) + if( addDep(r.in(i))._type != Type.XCONTROL ) { + if( in(i)._type==Type.BOTTOM ) + return Type.BOTTOM; t = t.meet(in(i)._type); + } + t = t.join( _minType ); return t; } @@ -67,19 +81,40 @@ public class PhiNode extends Node { public Node idealize() { if( !(region() instanceof RegionNode r ) ) return in(1); // Input has collapse to e.g. starting control. + // Can upgrade minType even while in-progress + if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { + TypeMemPtr tmp2 = (TypeMemPtr)CodeGen.CODE.P.TYPES.get(tmp._obj._name); + if( tmp2!=null && tmp2 != _minType ) { + _minType = tmp2; + return this; + } + } if( r.inProgress() || r.nIns()<=1 ) return null; // Input is in-progress // If we have only a single unique input, become it. Node live = singleUniqueInput(); - if (live != null) - return live; + if( live != null ) { + if( live._type.isa(_type) ) + return live; + // Keep the Phi upcast + return new CastNode(_type,null,live); + } // No bother if region is going to fold dead paths soon for( int i=1; i3 && // No Phi users, just a control user in(1) instanceof CProjNode p1 && in(2) instanceof CProjNode p2 && addDep(p1.in(0))==addDep(p2.in(0)) && @@ -57,8 +57,8 @@ public class RegionNode extends CFGNode { return delDef(2); } - // Flatten stack regions (no loops involved) - if( getClass() == RegionNode.class ) { + // Flatten stacked regions (no loops involved) + if( getClass() == RegionNode.class && nIns()>2 ) { for( int i=1; i2 && !hasMidUser(region) ) { assert !region.inProgress(); @@ -130,7 +130,7 @@ public class RegionNode extends CFGNode { if( use instanceof PhiNode ) { for( Node data : use._outputs ) { if( !(data instanceof PhiNode phi2) || phi2.region()!=this ) - { addDep(use); addDep(data); return true; } + { addDep(use); if( data!=null ) addDep(data); return true; } } } else { addDep(use); return true; } // Control user diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b4173871..7971733a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,12 +1,12 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.RegMask; import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.codegen.RegMask; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; /** @@ -61,11 +61,10 @@ public class ReturnNode extends CFGNode { // Upgrade signature based on return type Type ret = expr()._type; TypeFunPtr fcn = _fun.sig(); - assert ret.isa(fcn.ret()); - if( ret != fcn.ret() ) + if( ret != fcn.ret() && ret.isa(fcn.ret()) ) _fun.setSig(fcn.makeFrom(ret)); - // If dead (cant be reached; infinite loop), kill the exit values + // If dead (cannot be reached; infinite loop), kill the exit values if( ctrl()._type==Type.XCONTROL && !(mem() instanceof ConstantNode && expr() instanceof ConstantNode) ) { Node top = new ConstantNode(Type.TOP).peephole(); @@ -100,8 +99,8 @@ public class ReturnNode extends CFGNode { // Merge path into the One True Return RegionNode r = (RegionNode)ctrl(); // Assert that the Phis are in particular outputs; not reordered or shuffled - PhiNode mem = (PhiNode)r.out(0); assert mem._declaredType == TypeMem.BOT; - PhiNode rez = (PhiNode)r.out(1); assert rez._declaredType == Type.BOTTOM; + PhiNode mem = (PhiNode)r.out(0); assert mem._minType == TypeMem.BOT; + PhiNode rez = (PhiNode)r.out(1); assert rez._minType == Type.BOTTOM; // Pop "inProgress" null off r ._inputs.pop(); mem._inputs.pop(); diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3127e491..36746a81 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,8 +1,13 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.*; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Var; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.Utils; + import java.util.*; /** @@ -19,18 +24,26 @@ public class ScopeNode extends MemMergeNode { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; - // All active/live variables in all nested scopes, all run together + // All active/live variables in all nested scopes, all run together. + // Maps 1-to-1 to the _inputs array. public final Ary _vars; - // Size of each nested lexical scope - public final Ary _lexSize; - // 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 static class Kind { + // Basic block scoping + public static class Block extends Kind { } + // Function scope + public static class Func extends Kind { } + // Struct definition, mapping types to fields + public static class Define extends Kind { public Define(TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } + // Struct allocation, mapping values to fields + public static class Alloc extends Kind { public Alloc (TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } + + public int _lexSize; // Number of Vars in this scope + } public final Ary _kinds; + // Lexical scope nesting depth + public int depth() { return _kinds._len; } // Extra guards; tested predicates and casted results private final Ary _guards; @@ -38,10 +51,9 @@ public class ScopeNode extends MemMergeNode { // A new ScopeNode public ScopeNode() { super(true); - _vars = new Ary<>(Var .class); - _lexSize= new Ary<>(Integer.class); - _kinds = new Ary<>(Kind .class); - _guards = new Ary<>(Node .class); + _vars = new Ary<>(Var .class); + _kinds = new Ary<>(Kind.class); + _guards = new Ary<>(Node.class); } @Override public String label() { return "Scope"; } @@ -51,9 +63,9 @@ public class ScopeNode extends MemMergeNode { sb.append("Scope[ "); int j=1; for( int i=0; i=0; i-- ) + if( v._idx >= _kinds.at(i)._lexSize ) + return _kinds.at(i); + throw Utils.TODO(); + } + + // Return the kind for the defining scope, or a function scope if found + // first. Block scopes means the variable can be r/w directly in the + // scope, Function scopes require final constants (no capture), and + // Constructor scopes mean an instance variable reference. + + // Walk up-lexical scope looking for defining lexical Kind. + // - Skip any amount of nested block scopes + // - Walking out of a function requires v be a final constant (for now) - + // and we can stop walking. + + // - Walking out of a method and (skipping Blocks) into the matching struct + // is OK, and this is a instance var load. + + // - Walking out of a method and into the wrong struct is an error; + // including nested structs containing (no nested classes yet) + + // Returns error, forward-ref, ok containing struct, ok containing function/block. - // Is v outside any current function scope? - public boolean outOfFunction( Var v ) { - for( int i=_lexSize._len-1; i>=0 && v._idx<_lexSize.at(i); i-- ) - if( _kinds.at(i)==Kind.Function ) - return true; - return false; + public String outOfFunction( Var v ) { + //if( v==null ) return null; // Prolly forward reference + //int i; for( i=_lexSize._len-1; i>=0 && v._idx<_lexSize.at(i); i-- ) + // if( _kinds.at(i)=="{->}" ) return "{->}"; + //return _kinds.at(i); + throw Utils.TODO(); } @@ -149,9 +185,9 @@ public class ScopeNode extends MemMergeNode { * Create a new variable name in the current scope */ public boolean define( String name, Type declaredType, boolean xfinal, Node init, Parser.Lexer loc ) { - 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-- ) { + assert _kinds.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory + if( depth() > 0 ) + for( int i=_vars.size()-1; i>=_kinds.last()._lexSize; i-- ) { Var n = var(i); if( n._name.equals(name) ) { if( !n.isFRef() ) return false; // Double define @@ -214,7 +250,7 @@ public class ScopeNode extends MemMergeNode { : loop.setDef(v._idx,new PhiNode(v._name, v.type(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } - assert !v._final || st==null; + //assert !v._final || st==null; if( st!=null ) setDef(v._idx,st); // Set new value return v; } @@ -240,7 +276,6 @@ public class ScopeNode extends MemMergeNode { // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging dup._vars .addAll(_vars ); - dup._lexSize.addAll(_lexSize); dup._kinds .addAll(_kinds ); dup._guards .addAll(_guards ); // The dup'd guards all need dup'd keepers, to keep proper accounting diff --git a/src/main/java/com/seaofnodes/simple/node/SplitNode.java b/src/main/java/com/seaofnodes/simple/node/SplitNode.java index 3a1ed011..d061cdbd 100644 --- a/src/main/java/com/seaofnodes/simple/node/SplitNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SplitNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.SB; import java.util.BitSet; public abstract class SplitNode extends MachConcreteNode { diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index f40203b4..e3806de7 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -6,11 +6,11 @@ import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; import java.util.HashSet; -import static com.seaofnodes.simple.Utils.TODO; +import static com.seaofnodes.simple.util.Utils.TODO; /** * The Start node represents the start of the function. - * + *

* Start initially has 1 input (arg) from outside and the initial control. * In ch10 we also add mem aliases as structs get defined; each field in struct * adds a distinct alias to Start's tuple. @@ -19,7 +19,7 @@ public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super((Parser.Lexer)null,null); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super(null,null); _arg = arg; _type = compute(); } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } @Override public String label() { return "Start"; } @@ -29,13 +29,12 @@ public class StartNode extends LoopNode implements MultiNode { return sb.append(label()); } - @Override public boolean blockHead() { return true; } - @Override public CFGNode cfg0() { return null; } + @Override public CFGNode cfg0() { return null; } // Get the one control following; error to call with more than one e.g. an // IfNode or other multi-way branch. For Start, its "main" @Override public CFGNode uctrl() { - // Find "main", its the start. + // Find "main", it's the start. CFGNode C = null; for( Node use : _outputs ) if( use instanceof FunNode fun && fun.sig().isa(CodeGen.CODE._main) ) diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index b65535f1..4b03bf4e 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.Utils; import java.util.BitSet; public class StopNode extends CFGNode { diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 9b561bed..5fb274db 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -40,14 +40,16 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { Type val = val()._type; - TypeMem mem = (TypeMem)mem()._type; // Invariant + Type mem0 = mem()._type; + if( mem0 == Type.TOP ) return TypeMem.TOP; + TypeMem mem = (TypeMem)mem0; // Invariant if( mem == TypeMem.TOP ) return TypeMem.TOP; Type t = Type.BOTTOM; // No idea on field contents // Same alias, lift val to the declared type and then meet into other fields if( mem._alias == _alias ) { - // Update declared forward ref to the actual - if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) - _declaredType = tmp; + assert !_declaredType.isFRef(); + // Sharpen memory value; required for narrowing stores where the parser inserts + // zero/sign masking and somebody reads the TypeMem type. val = val.join(_declaredType); t = val.meet(mem._t); } @@ -57,6 +59,11 @@ public class StoreNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof CastNode cast ) { + setDef(1,cast.in(1)); + return this; + } + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && diff --git a/src/main/java/com/seaofnodes/simple/node/StructNode.java b/src/main/java/com/seaofnodes/simple/node/StructNode.java index 4efc0de9..b5b59b81 100644 --- a/src/main/java/com/seaofnodes/simple/node/StructNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.SB; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.SB; import java.util.BitSet; /** @@ -9,7 +9,8 @@ import java.util.BitSet; */ public class StructNode extends Node { - public TypeStruct _ts; + public final TypeStruct _ts; + public StructNode(TypeStruct ts) { _ts=ts; assert !ts._open; } @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); } @@ -19,7 +20,7 @@ public class StructNode extends Node { sb.append(_ts._name).append(" {"); for( int i=0; i\n"); // Add the scope level sb.append("\t\t\t").append(level).append(""); - int lexStart=scope._lexSize.at(level); + int lexStart = scope._kinds.at(level)._lexSize; for( int j=lexStart; j").append(v._name).append(""); @@ -243,7 +243,7 @@ public class GraphVisualizer { while( def instanceof ScopeNode lazy ) def = lazy.in(v._idx); if( def==null ) continue; - while( level < scope._lexSize.size() && v._idx >= scope._lexSize.at(level) ) + while( level < scope.depth() && v._idx >= scope._kinds.at(level)._lexSize ) level++; String scopeName = makeScopeName(scope, level-1); sb.append("\t") diff --git a/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index c6e478c5..d1265bef 100644 --- a/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -1,11 +1,11 @@ package com.seaofnodes.simple.print; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -61,7 +61,7 @@ public abstract class IRPrinter { if( n instanceof CFGNode || n instanceof MultiNode ) { if( !gap ) sb.p("\n"); // Blank before multihead if( n instanceof FunNode fun ) - fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" "),false).p("----------------------\n"); + fun.sig().print(sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ")).p("----------------------\n"); printLine( n, sb ); // Print head while( --i >= 0 ) { Node t = rpos.get(i); @@ -72,7 +72,7 @@ public abstract class IRPrinter { FunNode fun = ret.fun(); sb.p("--- "); if( fun != null ) - fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" "),false); + fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); sb.p("----------------------\n"); } if( !(n instanceof CallNode) ) { diff --git a/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/src/main/java/com/seaofnodes/simple/print/JSViewer.java index 76c64c71..62ff0001 100644 --- a/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ b/src/main/java/com/seaofnodes/simple/print/JSViewer.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.print; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.io.IOException; import java.nio.file.Paths; import java.util.Collection; @@ -192,14 +192,14 @@ public class JSViewer implements AutoCloseable { private static void scope( SB sb, ScopeNode scope ) { sb.i().p("node [shape=plaintext];\n"); int last = scope.nIns(); - int max = scope._lexSize.size()+1; // One more than lexsize + int max = scope.depth()+1; // One more than lexsize for( int i = 0; i < max; i++ ) { int level = max-i-1; String scopeName = makeScopeName(scope, level); sb.i().p("subgraph cluster_").p(scopeName).p(" {\n").ii(); // Magic "cluster_" in the subgraph name sb.i().p(scopeName).p(" [label=<\n").ii(); sb.i().p("\n"); - int lexStart = level==0 ? 0 : scope._lexSize.at(level-1); + int lexStart = level==0 ? 0 : scope._kinds.at(level-1)._lexSize; // Special for memory ScopeMinNode MemMergeNode n = scope.nIns()>1 ? scope.mem() : null; @@ -365,7 +365,7 @@ public class JSViewer implements AutoCloseable { while( def instanceof ScopeNode lazy ) def = lazy.in(v._idx); if( def==null ) continue; - while( level < scope._lexSize.size() && v._idx >= scope._lexSize.at(level) ) + while( level < scope.depth() && v._idx >= scope._kinds.at(level)._lexSize ) level++; String scopeName = makeScopeName(scope, level); sb.i() diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java b/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java index 7655213d..4077533d 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.print; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.Utils; import java.io.*; import java.net.ServerSocket; import java.net.Socket; diff --git a/src/main/java/com/seaofnodes/simple/sys/sys.smp b/src/main/java/com/seaofnodes/simple/sys/sys.smp deleted file mode 100644 index 4ac925db..00000000 --- a/src/main/java/com/seaofnodes/simple/sys/sys.smp +++ /dev/null @@ -1,58 +0,0 @@ -// -*- mode: java; -*- - -// top-level default import -struct sys { - // libc bindings - /** https://www.man7.org/linux/man-pages/man2/.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 - 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 ad96369b..b2b2deca 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import java.util.*; /** * Represents a field in a struct. This is not a Type in the type system. @@ -12,65 +12,125 @@ public class Field extends Type { // The pair {fieldName,type} uniquely identifies a field. // Field name - public final String _fname; + public String _fname; // Type of the field - public final Type _type; + public Type _t; // Unique memory alias, not sensibly part of a "type" but very convenient here. - public final int _alias; + public int _alias; // Field must be written to exactly once, no more, no less - public final boolean _final; + public boolean _final; + // Field is final in the declaration; value is the same for all instances + // and will be moved to the class object + public boolean _one; - private Field(String fname, Type type, int alias, boolean xfinal ) { - super(TFLD); + private static final Ary FREE = new Ary<>(Field.class); + private Field(String fname, Type type, int alias, boolean xfinal, boolean one ) { super(TFLD); init(fname,type,alias,xfinal,one); } + private Field init(String fname, Type type, int alias, boolean xfinal, boolean one ) { _fname = fname; - _type = type; + _t = type; _alias = alias; _final = xfinal; + _one = one; + return this; } - // Make with existing alias - public static Field make( String fname, Type type, int alias, boolean xfinal ) { - return new Field(fname,type,alias,xfinal).intern(); + + // Return a filled-in Field; either from free list or alloc new. + private static Field malloc(String fname, Type type, int alias, boolean xfinal, boolean one ) { + return FREE.isEmpty() ? new Field(fname,type,alias,xfinal,one) : FREE.pop().init(fname,type,alias,xfinal,one); + } + // Malloc-from + public Field malloc( ) { return malloc(_fname,null,_alias,_final,_one); } + @Override Field free(Type t) { + Field f = (Field)t; + assert !f.isFree() && !f._terned; + f._t = null; + f._dual = null; + f._hash = 0; + FREE.push(f); + return this; + } + @Override boolean isFree() { return _t ==null; } + + // Make and intern with listed fields + public static Field make( String fname, Type type, int alias, boolean xfinal, boolean one ) { + Field f = malloc(fname,type,alias,xfinal,one); + Field f2 = f.intern(); + if( f2==f ) return f; + return VISIT.isEmpty() ? f2.free(f) : f2.delayFree(f); } public Field makeFrom( Type type ) { - return type == _type ? this : new Field(_fname,type,_alias,_final).intern(); + return type == _t ? this : make(_fname,type,_alias,_final,_one); + } + public Field makeFrom( boolean xfinal ) { + return xfinal == _final ? this : make(_fname,_t,_alias,xfinal,_one); } - @Override public Field makeRO() { return _final ? this : make(_fname,_type.makeRO(),_alias,true); } - @Override public boolean isFinal() { return _final && _type.isFinal(); } - public static final Field TEST = make("test",Type.NIL,-2,false); - public static final Field TEST2= make("test",Type.NIL,-2,true); - public static void gather(ArrayList ts) { ts.add(TEST); ts.add(TEST2); } + // Cycle-making-breaking + void setType(Type t) { assert _t ==null; _t = t; } + + public static final Field BOT = make(" ",Type.BOTTOM,-999,true,false); + public static final Field TEST = make("test",Type.NIL,-2,false,false); + public static final Field TEST2 = make("test",Type.NIL,-2,true, false); + public static final Field FLT = make("flt ",TypeFloat.F32,-2,false,false); + public static void gather(ArrayList ts) { ts.add(TEST); ts.add(TEST2); ts.add(FLT); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant - assert _fname.equals(fld._fname); + if( this==BOT || fld==BOT ) return BOT; + if( this==BOT.dual() ) return fld ; + if( fld ==BOT.dual() ) return this; + if( _fname!=fld._fname ) { assert !_fname.equals(fld._fname); return BOT; } assert _alias==fld._alias; - return make(_fname,_type.meet(fld._type),_alias,_final | fld._final); + assert _one ==fld._one ; + return make(_fname, _t.meet(fld._t ),_alias,_final | fld._final, _one); } @Override - public Field dual() { return make(_fname,_type.dual(),_alias,!_final); } + Field xdual() { return malloc(_fname, _t.dual(),_alias,!_final,_one); } - @Override public boolean isConstant() { return _type.isConstant(); } + @Override Field rdual() { + if( _dual!=null ) return dual(); + assert !_terned; + Field d = malloc(_fname,null,_alias,!_final,_one); + (_dual = d)._dual = this; // Cross link duals + d._t = _t._terned ? _t.dual() : _t.rdual(); + return d; + } - @Override public Field glb(boolean mem) { - Type glb = _type.glb(mem); - return (glb==_type && _final) ? this : make(_fname,glb,_alias,true); + @Override boolean _isConstant() { return _t._isConstant(); } + @Override boolean _isFinal() { return _final && _t._isFinal(); } + @Override Field _makeRO() { return _final ? this : make(_fname, _t._makeRO(),_alias,true,_one); } + boolean isGLB2() { return _final && _t._isGLB(true); } + Field glb2() { + Type glb = _t._glb(true); + return (glb== _t && _final ) ? this : make(_fname,glb,_alias,true,_one); } + @Override Field _close() { return makeFrom( _t._close()); } // Override in subclasses - int hash() { return _fname.hashCode() ^ _type.hashCode() ^ _alias ^ (_final ? 1024 : 0); } + int hash() { return _fname.hashCode() ^ _t.hashCode() ^ _alias ^ (_final ? 1024 : 0) ^ (_one ? 2048 : 0); } - boolean eq(Type t) { + private boolean static_eq( Field f ) { + return _fname.equals(f._fname) && _alias==f._alias && _final==f._final && _one==f._one && _t !=null && f._t !=null; + } + @Override boolean eq( Type t ) { + Field f = (Field)t; + return static_eq(f) && _t ==f._t; + } + @Override boolean cycle_eq(Type t) { Field f = (Field)t; - return _fname.equals(f._fname) && _type==f._type && _alias==f._alias && _final==f._final; + return static_eq(f) && _t.cycle_eq(f._t ); } + @Override int nkids() { return 1; } + @Override Type at( int idx ) { return _t; } + @Override void set( int idx, Type t ) { _t = t; } @Override - public SB print( SB sb ) { - return _type.print(sb.p(_final?"":"!").p(_fname).p(":").p(_alias).p(" : ")); + public SB _print( SB sb, BitSet visit, boolean html ) { + sb.p(_final?"":"!").p(_one?"$":"").p(_fname).p(":").p(_alias).p(" : "); + return _t ==null ? sb.p("---") : _t.print(sb,visit,html); } - @Override public String str() { return (_final?"":"!")+_fname; } + @Override public String str() { return (_final?"":"!")+(_one?"$":"")+_fname; } } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index a44cdd61..b7a8408e 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,9 +1,7 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; -import java.util.HashMap; +import com.seaofnodes.simple.util.*; +import java.util.*; /** * These types are part of a Monotone Analysis Framework, @@ -21,8 +19,33 @@ import java.util.HashMap; * simple constant folding e.g. 1+2 == 3 stuff. */ -public class Type { +public class Type /*implements Cloneable*/ { + // Interning tables + + // Main intern table; a collection of all unique types. static final HashMap INTERN = new HashMap<>(); + // Starting intern table; used to rapidly reset the main table between tests + private static final HashMap INTERN0= new HashMap<>(); + // Lifetime management during cyclic installs is complex; this is used to + // track created-but-already-interned objects + private static final Ary FREES = new Ary<>(Type.class); + // "visit" bit management, based solely on _uid + static final BitSet BITS = new BitSet(); + + // "visit" bit management. Key varies by kind of visit: + + // - "close" an open cyclic type. Used by the Parser, it will hit on + // same-named structs, even if the structs have different states of + // completion/fields. + // - "uid/name" - Either the UID or name works (unlike "close" which must + // use the name). Used to make cyclic copies with changes, like make + // read-only where there should be only 1 copy of a name in a cycle. + // - "pair of uids" - For recursive MEET, where we need to key off two types + static final HashMap VISIT = new HashMap<>(); + + // Every Type has a UID to allow visit bits on cyclic visits + private static int UID=1; + public char _uid; // Unique ID for every type // ---------------------------------------------------------- // Simple types are implemented fully here. "Simple" means: the code and @@ -38,33 +61,42 @@ public class Type { static final byte TPTR = 7; // All nil-able scalar values static final byte TINT = 8; // All Integers; see TypeInteger static final byte TFLT = 9; // All Floats ; see TypeFloat - static final byte TMEMPTR =10; // Memory pointer to a struct type - static final byte TFUNPTR =11; // Function pointer; unique signature and code address (just a bit) + static final byte TCONARY =10; // Constant array + static final byte TRPC =11; // Return Program Control (Return PC or RPC) static final byte TTUPLE =12; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM =13; // All memory (alias 0) or A slice of memory - with specific alias - static final byte TSTRUCT =14; // Structs; tuples with named fields - static final byte TFLD =15; // Named fields in structs - static final byte TCONARY =16; // Constant array - static final byte TRPC =17; // Return Program Control (Return PC or RPC) + static final byte TCYCLIC =13; // Has internal pointers, needs recursive treatment + static final byte TMEMPTR =13; // Memory pointer to a struct type + static final byte TFUNPTR =14; // Function pointer; unique signature and code address (just a bit) + static final byte TMEM =15; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TSTRUCT =16; // Structs; tuples with named fields + static final byte TFLD =17; // Named fields in structs + + // Basic RTTI, useful for a lot of fast tests. public final byte _type; + public boolean _terned; public boolean is_simple() { return _type < TSIMPLE; } private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl","null","~nil"}; - protected Type(byte type) { _type = type; } + static final int[] CNTS = new int[TFLD+1]; + protected Type(byte type) { + _type = type; // RTTI + _uid = (char)UID++; // A unique ID for every type + assert _uid!=0; // Overflow + CNTS[type]++; + } public static final Type BOTTOM = new Type( TBOT ).intern(); // ALL - public static final Type TOP = new Type( TTOP ).intern(); // ANY + public static final Type TOP = BOTTOM.dual(); public static final Type CONTROL = new Type( TCTRL ).intern(); // Ctrl - public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl + public static final Type XCONTROL = CONTROL.dual(); public static final Type NIL = new Type( TNIL ).intern(); // low null of all flavors - public static final Type XNIL = new Type( TXNIL ).intern(); // high or choice null + public static final Type XNIL = NIL.dual(); public static Type[] gather() { ArrayList ts = new ArrayList<>(); ts.add(BOTTOM); ts.add(CONTROL); ts.add(NIL); - ts.add(XNIL); TypeNil.gather(ts); TypePtr.gather(ts); TypeInteger.gather(ts); @@ -77,6 +109,7 @@ public class Type { 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()); @@ -87,10 +120,6 @@ public class Type { public boolean isHigh () { return _type==TTOP || _type==TXCTRL || _type==TXNIL; } public boolean isHighOrConst() { return isHigh() || isConstant(); } - // Strict constant values, things on the lattice centerline. - // Excludes both high and low values - public boolean isConstant() { return _type==TNIL; } - // ---------------------------------------------------------- // Notes on Type interning: At the moment it is not easy to reset the @@ -106,14 +135,68 @@ public class Type { // Factory method which interns "this" @SuppressWarnings("unchecked") - public T intern() { - T nnn = (T)INTERN.get(this); - if( nnn==null ) - INTERN.put(nnn=(T)this,this); - return nnn; + T intern() { + //assert check(); + assert !_terned; // Do not ask for already-interned + T t2 = (T)INTERN.get(this); + if( t2!=null ) { + assert t2._dual != null; // Prior is complete with dual + assert this != t2; // Do not hashcons twice, should not get self back + return t2; // Return prior + } + // Mid recursive type construction + if( !VISIT.isEmpty() && _type >= TCYCLIC ) { + // No intern attempt at all + return (T)this; + } + // Not in type table + _dual = null; // No dual yet + INTERN.put(this,this); // Put in table without dual + _terned = true; + //Util.hash_quality_check_per(INTERN,"INTERN"); + T d = xdual(); // Compute dual without requiring table lookup, and not setting name + _dual = d; + if( this==d ) return d; // Self-symmetric? Dual is self + assert !equals(d); // Self-symmetric is handled by caller + assert d._dual==null; // Else dual-dual not computed yet + assert INTERN.get(d)==null; + d._dual = (T)this; + INTERN.put(d,d); // Install dual also + d._terned = true; + //assert check(); + return (T)this; + } + + // Recursive visit elsewhere, interns with dual already + T _intern() { + //assert check(); + assert !_terned; + Type t = INTERN.get(this); + if( t!=null ) return (T)t.delayFree(this).delayFree(_dual); + assert !INTERN.containsKey( _dual ); + INTERN.put(this,this); + INTERN.put(_dual,_dual); + _terned = _dual._terned = true; + //assert check(); + return (T)this; } - private int _hash; // Hash cache; not-zero when set. + private static boolean check() { + for( Type t : INTERN.keySet() ) { + Type t2 = INTERN.get(t); + assert t==t2; + } + return true; + } + + public static Type find(int uid) { + for( Type t : INTERN.keySet() ) + if( t._uid==uid ) return t; + return null; + } + + + int _hash; // Hash cache; not-zero when set. @Override public final int hashCode() { if( _hash!=0 ) return _hash; @@ -132,8 +215,42 @@ public class Type { return eq(t); } // Overridden in subclasses; subclass can assume "this!=t" and java classes are same - boolean eq(Type t) { return true; } + boolean eq(Type t) { return this==t; } + boolean cycle_eq(Type t) { assert _type < TCYCLIC; return eq(t); } + // A pair of uids + int pid( Type that ) { + return _uid < that._uid ? (_uid<<16 | that._uid) : (that._uid<<16 | _uid); + } + // At/Set child at 'idx' to t + Type at ( int idx ) { throw Utils.TODO(); } + void set( int idx, Type t ) { throw Utils.TODO(); } + int nkids() { assert _type < TTUPLE; return 0; } // Number of kids + + + // Clear and re-insert the basic Type INTERN table + public static void reset() { + VISIT.clear(); + FREES.clear(); + if( INTERN0.isEmpty() ) { + // First time run all and collect basic types + Type t = TypeRPC .BOT; // Force class load, intern + Type u = TypeTuple.BOT; // Force class load, intern + Type w = TypePtr .PTR; // Force class load, intern + INTERN0.putAll(INTERN); + } else { + // Later times, reset back to first time + VISIT.put(0,CONTROL); // Defeat assert + for( Iterator it = INTERN.keySet().iterator(); it.hasNext(); ) { + Type t = it.next(); + if( !INTERN0.containsKey(t) ) + { t._terned=false; t.free(t); } + it.remove(); + } + VISIT.clear(); + INTERN.putAll(INTERN0); + } + } // ---------------------------------------------------------- public final Type meet(Type t) { @@ -172,18 +289,24 @@ public class Type { return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; } - public Type dual() { - return switch( _type ) { - case TBOT -> TOP; - case TTOP -> BOTTOM; - case TCTRL ->XCONTROL; - case TXCTRL-> CONTROL; - case TNIL ->XNIL; - case TXNIL -> NIL; + + // The dual is pre-computed on creation and available "for free" thereafter + Type _dual; + public final T dual() { return (T)_dual; } + + T xdual() { + return (T)new Type(switch( _type ) { + case TBOT -> TTOP; + case TTOP -> TBOT; + case TCTRL -> TXCTRL; + case TXCTRL-> TCTRL; + case TNIL -> TXNIL; + case TXNIL -> TNIL; default -> throw Utils.TODO(); // Should not reach here - }; + }); } + // ---------------------------------------------------------- // Our lattice is defined with a MEET and a DUAL. // JOIN is dual of meet of both duals. @@ -203,18 +326,157 @@ 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. If values are in memory, - * ints and floats cannot widen. */ - public Type glb(boolean mem) { return Type.BOTTOM; } - // Is forward-reference public boolean isFRef() { return false; } - // All reachable struct Fields are final - public boolean isFinal() { return true; } + // ---------------------------------------------------------- - // Make all reachable struct Fields final - public Type makeRO() { return this; } + // Cyclic types! Flag the start of a cyclic type by putting a sentinel in + // VISIT (and eventually clearing VISIT when done). Then do a normal + // recursive descent visit of all types; this will accumilate types without + // interning them. When done we have to visit the possibly cyclic type and + // intern the whole cycle, possibly hitting the entire cycle on a prior + // interned cycle. Any sub-part might also be interned, including whole + // disjoint cycles. + + // E.g. a new type: "A<->B -> C1<->D1" gets created; the "C1<->D1" cycle + // already exists as "C0<->D0", but the "A<->B" cycle is new. The "A<->B" + // cycle will get interned - except the pointer to C1 needs to get replaced + // with C0. The "C1<->D1" cycle gets freed and "B" will point to the + // "C0<->D0" cycle. + + Type recurOpen() { assert VISIT.isEmpty(); VISIT.put(0L,BOTTOM); return this; } + Type recurClose() { + VISIT.remove(0L); // Just ignore the sentinel + Ary ts = new Ary<>(Type.class); + ts.addAll(VISIT.values()); + if( ts.find(this)== -1 ) ts.add(this); + + // Pass #1: replace already interned fields + assert BITS.isEmpty(); + for( int i=0; i T delayFree(Type free) { + assert !free._terned; + FREES.push(free); + return (T)this; + } + + final Type install() { + if( this instanceof TypeStruct ) { + Type x = _intern(); // Stop the recursion + assert x==this; + } + int nkids = nkids(); + for( int i=0; i false; + case TNIL -> false; + case TCTRL -> true; + case TXCTRL -> false; + case TXNIL -> false; + case TTOP -> false; + default -> throw Utils.TODO(); + }; + } + public final Type glb(boolean mem) { + if( isGLB(mem) ) return this; + Type glb = recurOpen()._glb(mem).recurClose(); + assert this.isa(glb); + return glb; + } + Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } + + Type _close() { return this; } // ---------------------------------------------------------- @@ -231,11 +493,21 @@ public class Type { // This is a more verbose dev-friendly print. @Override public final String toString() { - return print(new SB()).toString(); + return print(new SB(), new BitSet(), false).toString(); } - - public SB print(SB sb) { return sb.p(str()); } - public SB gprint(SB sb) { return print(sb); } + public final String gprint() { + return print(new SB(), new BitSet(), true).toString(); + } + public final SB print(SB sb) { return print(sb, new BitSet(), false); } + public final SB gprint(SB sb) { return print(sb, new BitSet(), true ); } + + // Used during recursive printing, or combined with SB Node printing + public final SB print(SB sb, BitSet visit, boolean html ) { + if( visit.get(_uid) ) return sb.p(str()); + visit.set(_uid); + return _print(sb,visit,html); + } + SB _print(SB sb, BitSet visit, boolean html ) { return sb.p(str()); } // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 29496af6..d4003f87 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.io.ByteArrayOutputStream; +import java.util.ArrayList; /** * Represents a constant array of primitives @@ -13,9 +13,8 @@ public class TypeConAry extends Type { // 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(); + TypeConAry( boolean any, byte type, A ary ) { super(type); _any = any; _ary = ary; } + public static final TypeConAry BOT = new TypeConAry(false, TINT, null).intern(); public static void gather(ArrayList ts) { ts.add(BOT); TypeConAryB.gather(ts); @@ -23,42 +22,56 @@ public class TypeConAry extends Type { } @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; + @Override TypeConAry xdual() { + if( _ary==null ) + return new TypeConAry(!_any,_type,null); return this; } @Override Type xmeet(Type t) { + if( t instanceof TypeInteger ti ) return imeet(ti); TypeConAry ary = (TypeConAry)t; // Invariant - if( this==TOP ) return ary ; - if( ary ==TOP ) return this; + if( this==BOT ) return BOT; + if( ary ==BOT ) return BOT; + if( this==BOT.dual() ) return ary ; + if( ary ==BOT.dual() ) return this; assert _ary!=ary._ary; // Already interned and this!=t - return BOT; + return elem().meet(ary.elem()); + } + Type imeet( TypeInteger ti ) { + if( this==BOT.dual() ) return ti; + if( this==BOT ) return BOT; + Type elem = elem(); + if( !(elem instanceof TypeInteger) ) return BOTTOM; + if( ti.isHigh() && elem.isa(ti.dual()) ) + return this; + return elem.meet(ti); } + + @Override public boolean isHigh() { return this==TOP; } + @Override boolean _isConstant() { return true; } + // Meet-over-elements type public Type elem() { if( _ary==null ) - return _any ? TOP : BOTTOM; + return _any ? Type.TOP : BOTTOM; int len = len(); long min = Long.MAX_VALUE; long max = Long.MIN_VALUE; for( int i=0; i { - private TypeConAryB(byte[] bs) { super(false,bs); } + private TypeConAryB(byte[] bs) { super(false,TINT,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 ts) { ts.add(ABC); ts.add(ABCD); } - @Override public long at(int idx) { return _ary[idx]; } + @Override public long at8(int idx) { return _ary[idx]; } @Override public int len() { return _ary.length; } - @Override public int alignment() { return 0; } + @Override public int log_size() { 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/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index f888a93d..924e3d73 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -4,12 +4,14 @@ import java.util.ArrayList; import java.util.Arrays; public class TypeConAryI extends TypeConAry { - private TypeConAryI(int[] bs) { super(false,bs); } + private TypeConAryI(int[] bs) { super(false,TINT,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 ts) { ts.add(I123); } + @Override public long at8(int idx) { return _ary[idx]; } + @Override public int len() { return _ary.length; } + @Override public int log_size() { return 2; } @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 a0940f8b..f3de581c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.Ary; import java.util.ArrayList; /** @@ -9,30 +10,38 @@ import java.util.ArrayList; */ public class TypeFloat extends Type { - public final static TypeFloat ONE = constant(1.0); - public final static TypeFloat FZERO = constant(0.0); - public final static TypeFloat F32 = make(32, 0); - public final static TypeFloat F64 = make(64, 0); - // - high -64, high -32, con 0, low +32, low +64 - public final byte _sz; + public byte _sz; /** * The constant value or 0 */ - public final double _con; + public double _con; - private TypeFloat(byte sz, double con) { - super(TFLT); - _sz = sz; - _con = con; - } + private static final Ary FREE = new Ary<>(TypeFloat.class); + private TypeFloat(byte sz, double con) { super(TFLT); init(sz,con); } + private TypeFloat init( byte sz, double con ) { _sz = sz; _con = con; return this; } + public static TypeFloat malloc(byte sz, double con) { return FREE.isEmpty() ? new TypeFloat(sz,con) : FREE.pop().init(sz,con); } private static TypeFloat make(int sz, double con) { - return new TypeFloat((byte)sz,con).intern(); + TypeFloat f = malloc((byte)sz,con); + TypeFloat t2 = f.intern(); + return t2==f ? f : t2.free(f); + } + @Override TypeFloat free(Type t) { + TypeFloat f = (TypeFloat)t; + f._hash = 0; + f._dual=null; + FREE.push(f); + return this; } public static TypeFloat constant(double con) { return make(0, con); } + public final static TypeFloat ONE = constant(1.0); + public final static TypeFloat FZERO = constant(0.0); + public final static TypeFloat F32 = make(32, 0); + public final static TypeFloat F64 = make(64, 0); + public static void gather(ArrayList ts) { ts.add(F64); ts.add(F32); ts.add(constant(3.141592653589793)); } @Override public String str() { @@ -48,7 +57,6 @@ public class TypeFloat extends Type { private boolean isF32() { return ((float)_con)==_con; } @Override public boolean isHigh () { return _sz< 0; } - @Override public boolean isConstant() { return _sz==0; } @Override public int log_size() { return _sz==32 || _sz==-32 ? 2 : 3; } public double value() { return _con; } @@ -76,13 +84,20 @@ public class TypeFloat extends Type { } @Override - public Type dual() { - return isConstant() ? this : make(-_sz,0); // Constants are a self-dual + TypeFloat xdual() { + return _isConstant() ? this : new TypeFloat((byte)-_sz,0); // Constants are a self-dual } - @Override public Type makeZero() { return FZERO; } - @Override public Type glb(boolean mem) { return mem ? (isHigh() ? dual() : this) : F64; } + @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } + @Override Type _glb(boolean mem) { + if( !mem ) return F64; + if( _isConstant() ) return isF32() ? F32 : F64; + return isHigh() ? dual() : this; + } + @Override boolean _isConstant() { return _sz==0; } + + @Override public Type makeZero() { return FZERO; } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz ^ (1<<17)); } @Override diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index abfcf1e3..b21dd451 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -1,9 +1,9 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; -import java.util.HashMap; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.Ary; +import java.util.*; /** * Represents a Pointer to a function. @@ -19,86 +19,220 @@ import java.util.HashMap; */ public class TypeFunPtr extends TypeNil { // A TypeFunPtr is Signature and a set of functions. - public final TypeTuple _sig; - public final Type _ret; + public Type[] _sig; + public Type _ret; + // TODO: + boolean _open; // Extra args are true:BOTTOM, false:TOP // Cheesy easy implementation for a small set; 1 bit per unique function - // within the TypeTuple. Can be upgraded to a BitSet for larger classes of - // functions. Negative means "these 63 concrete bits plus infinite unknown more" - public final long _fidxs; // 63 unique functions per signature - - private TypeFunPtr(byte nil, TypeTuple sig, Type ret, long fidxs) { - super(TFUNPTR,nil); + // within the same Type[]. Can be upgraded to a BitSet for larger classes + // of functions. Negative means "these 63 concrete bits plus infinite + // unknown more" + public long _fidxs; // 63 unique functions per signature + + private static final Ary FREE = new Ary<>(TypeFunPtr.class); + private TypeFunPtr(byte nil, boolean open, Type[] sig, Type ret, long fidxs) { super(TFUNPTR,nil); init(nil,open,sig,ret,fidxs); } + private TypeFunPtr init(byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { assert sig != null; - _sig = sig; - _ret = ret; - _fidxs = fidxs; + _nil = nil; + _open = open; + _sig = sig; + _ret = ret; + _fidxs= fidxs; + return this; + } + static TypeFunPtr malloc( byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { + return FREE.isEmpty() ? new TypeFunPtr(nil,open,sig,ret,fidxs) : FREE.pop().init(nil,open,sig,ret,fidxs); + } + @Override TypeFunPtr free(Type t) { + TypeFunPtr fun = (TypeFunPtr)t; + assert !fun.isFree() && !fun._terned; + fun._sig = null; + fun._ret = null; + fun._dual = null; + fun._hash = 0; + FREE.push(fun); + return this; } + @Override boolean isFree() { return _sig==null; } + + // All fields directly listed + public static TypeFunPtr make( byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { + TypeFunPtr fun = malloc(nil,open,sig,ret,fidxs); + TypeFunPtr f2 = fun.intern(); + if( f2==fun ) return fun; + return VISIT.isEmpty() ? f2.free(fun) : f2.delayFree(fun); + } + public static TypeFunPtr make( boolean nil, boolean open, Type[] sig, Type ret ) { return make((byte)(nil ? 3 : 2),open,sig,ret,-1); } + + + @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } + public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } + public TypeFunPtr makeFrom( int fidx ) { return make((byte)2, _open, _sig,_ret,1L< ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); ts.add(MAIN); } + public static final Type[] TEMPTY = new Type[0]; + static final Type[] TINT = new Type[]{TypeInteger.BOT}; + static final Type[] TINTMEM = new Type[]{TypeInteger.BOT,TypeFloat.F32}; + static final Type[] TINTINT = new Type[]{TypeInteger.BOT,TypeInteger.BOT}; + public static TypeFunPtr BOT = make((byte)3,true ,TEMPTY,Type.BOTTOM,-1); + public static TypeFunPtr TEST = make((byte)2,false,TINTMEM,TypeInteger.BOT, 1); + public static TypeFunPtr TEST0 = make((byte)3,false,TINTMEM,TypeInteger.BOT, 3); + public static TypeFunPtr MAIN = make((byte)3,false,TINT ,Type.BOTTOM,-1); // Main can return anything + public static TypeFunPtr CALLOC= make((byte)3,false,TINTINT,TypeMemPtr .BOT,-1); + public static void gather(ArrayList ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); ts.add(MAIN);ts.add(CALLOC); } @Override Type xmeet(Type t) { TypeFunPtr that = (TypeFunPtr) t; - return TypeFunPtr.make(xmeet0(that),(TypeTuple)_sig.meet(that._sig), _ret.meet(that._ret), _fidxs | that._fidxs); + // if equal, no matters. + // if short is BOT, chop ; recurPre on short. + // if short is TOP, copy long; recurPre on long. + TypeFunPtr min = _sig.length < that._sig.length ? this : that; + if( _sig.length != that._sig.length && (min._open ^ min==this) ) + return that.xmeet(this); + // Recurse all common fields + Type[] args = new Type[_sig.length]; + for( int i=0; i "),g,_ret).p(" #"); - if( isHigh() ) sb.p("~"); + if( _sig!=null ) + for( Type t : _sig ) + sb.p(t.str()).p(" "); // Short form in signature + _ret.print(sb.p(html ? "→ " : "-> "),visit,html).p(" #"); + // Print fidxs + return sb.p(printFIDX()).p("}").p(q()); + } + String printFIDX() { + String tilde = isHigh() ? "~" : ""; long fidxs = isHigh() ? ~_fidxs : _fidxs; String fidx = fidxs==0 ? "" : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) : fidxs == -1 ? "ALL" : "b"+Long.toBinaryString(fidxs); // Just some function bits - return sb.p(fidx).p("}").p(q()); + return tilde+fidx; } // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) { int fidxs = Long.numberOfTrailingZeros(fidxs); ... } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 59378ef3..99f237a9 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -1,24 +1,54 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; /** * Integer Type */ public class TypeInteger extends Type { + /** + * Describes an integer *range* - everything from min to max; both min and + * max are inclusive. If min==max, this is a constant. + *
+ * If min <= max, this is a below center (towards bottom). + * If min > max, this is an above center (towards top). + */ + public long _min, _max; + + private static final Ary FREE = new Ary<>(TypeInteger.class); + private TypeInteger(long min, long max) { super(TINT); init(min,max); } + private TypeInteger init(long min, long max) { _min = min; _max = max; return this; } + public static TypeInteger malloc(long lo, long hi) { return FREE.isEmpty() ? new TypeInteger(lo,hi) : FREE.pop().init(lo,hi); } + public static TypeInteger make(long lo, long hi) { + TypeInteger i = malloc(lo,hi); + TypeInteger t2 = i.intern(); + return t2==i ? i : t2.free(i); + } + @Override TypeInteger free(Type t) { + TypeInteger i = (TypeInteger)t; + i._min = i._max = 0; + i._hash = 0; + i._dual = null; + FREE.push(i); + return this; + } + + public static TypeInteger constant(long con) { return make(con, con); } public final static TypeInteger ZERO= make(0,0); public final static TypeInteger FALSE=ZERO; public final static TypeInteger TRUE= make(1,1); + public final static TypeInteger TWO = make(2,2); // Shows up in some Simple tests as the starting argument public final static TypeInteger I1 = make(-1,0); public final static TypeInteger I8 = make(-128,127); public final static TypeInteger I16 = make(-32768,32767); public final static TypeInteger I32 = make(-1L<<31,(1L<<31)-1); public final static TypeInteger BOT = make(Long.MIN_VALUE,Long.MAX_VALUE); - public final static TypeInteger TOP = BOT.dual(); + public final static TypeInteger TOP = (TypeInteger)BOT.dual(); public final static TypeInteger U1 = make(0,1); public final static TypeInteger BOOL= U1; @@ -26,30 +56,10 @@ public class TypeInteger extends Type { public final static TypeInteger U16 = make(0,65535); public final static TypeInteger U32 = make(0,(1L<<32)-1); - /** - * Describes an integer *range* - everything from min to max; both min and - * max are inclusive. If min==max, this is a constant. - *
- * If min <= max, this is a below center (towards bottom). - * If min > max, this is an above center (towards top). - */ - public final long _min, _max; - - private TypeInteger(long min, long max) { - super(TINT); - _min = min; - _max = max; - } - - // Strict non-zero contract - public static TypeInteger make(long lo, long hi) { return new TypeInteger(lo,hi).intern(); } - - public static TypeInteger constant(long con) { return make(con, con); } - public static void gather(ArrayList ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); } @Override public String str() { - if( isConstant() ) return ""+_min; + if( _isConstant() ) return ""+_min; long lo = _min, hi = _max; String x = ""; if( hi < lo ) { @@ -59,7 +69,7 @@ public class TypeInteger extends Type { return x+_str(lo,hi); } private static String _str(long lo, long hi) { - if( lo==Long.MIN_VALUE && hi==Long.MAX_VALUE ) return "int"; + if( lo==Long.MIN_VALUE && hi==Long.MAX_VALUE ) return "i64"; if( lo== 0 && hi== 1 ) return "bool"; if( lo== -1 && hi== 0 ) return "i1"; if( lo== -128 && hi== 127 ) return "i8"; @@ -72,7 +82,6 @@ public class TypeInteger extends Type { } @Override public boolean isHigh () { return _min > _max; } - @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. @@ -110,12 +119,15 @@ public class TypeInteger extends Type { @Override public Type xmeet(Type other) { + if( other instanceof TypeConAry ary ) return ary.imeet(this); // Invariant from caller: 'this' != 'other' and same class (TypeInteger) TypeInteger i = (TypeInteger)other; // Contract return make(Math.min(_min,i._min), Math.max(_max,i._max)); } - @Override public TypeInteger dual() { return make(_max,_min); } + @Override TypeInteger xdual() { + return _min==_max ? this : malloc(_max,_min); + } @Override public TypeInteger nonZero() { if( isHigh() ) return this; @@ -125,10 +137,17 @@ public class TypeInteger extends Type { return this; } @Override public Type makeZero() { return ZERO; } - @Override public Type glb(boolean mem) { return mem ? (isHigh() ? dual() : this) : BOT; } + @Override boolean _isConstant() { return _min == _max; } + @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } + @Override Type _glb(boolean mem) { + if( !mem ) return BOT; + // GLB is not well-defined in memory; depends on the size of the memory field + if( _isConstant() ) return BOT; + return isHigh() ? dual() : this; + } + @Override int hash() { return Utils.fold(_min) * Utils.fold(_max); } @Override public boolean eq( Type t ) { - TypeInteger i = (TypeInteger)t; // Contract - return _min==i._min && _max==i._max; + return t instanceof TypeInteger i && _min==i._min && _max==i._max; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 63fb30ce..99b19c75 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.lang.Long; -import java.util.BitSet; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; +import java.util.BitSet; /** @@ -13,24 +13,44 @@ import java.util.ArrayList; public class TypeMem extends Type { // Which slice of memory? - // 0 means TOP, no slice. - // 0 means BOT, all memory. - // N means slice#N. - public final int _alias; - public final Type _t; // Memory contents, some scalar type - - private TypeMem(int alias, Type t) { - super(TMEM); - assert alias!=0 || (t==Type.TOP || t==Type.BOTTOM); + // 1 and TOP means no slice. + // 1 and BOT means all memory. + // N means alias slice#N. + public int _alias; + public Type _t; // Memory contents, some scalar type + + private static final Ary FREE = new Ary<>(TypeMem.class); + private TypeMem(int alias, Type t) { super(TMEM); init(alias,t); } + private TypeMem init(int alias, Type t) { + assert alias>1 || (t==Type.TOP || t==Type.BOTTOM); _alias = alias; _t = t; + return this; + } + @Override TypeMem free(Type t) { + TypeMem mem = (TypeMem)t; + mem._alias= -99; + mem._dual = null; + mem._hash = 0; + FREE.push(mem); + return this; + } + @Override boolean isFree() { return _alias == -99; } + + public static TypeMem malloc(int alias, Type t) { + return FREE.isEmpty() ? new TypeMem(alias,t) : FREE.pop().init(alias,t); + } + public static TypeMem make(int alias, Type t) { + TypeMem f = malloc(alias,t); + TypeMem f2 = f.intern(); + if( f2==f ) return f; + return VISIT.isEmpty() ? f2.free(f) : f2.delayFree(f); } - public static TypeMem make(int alias, Type t) { return new TypeMem(alias,t).intern(); } - public static final TypeMem TOP = make(0, Type.TOP ); - public static final TypeMem BOT = make(0, Type.BOTTOM); + public static final TypeMem TOP = make(1, Type.TOP ); + public static final TypeMem BOT = make(1, Type.BOTTOM); - public static void gather(ArrayList ts) { ts.add(make(1,Type.NIL)); ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } + public static void gather(ArrayList ts) { ts.add(make(2,Type.NIL)); ts.add(make(2,TypeInteger.ZERO)); ts.add(BOT); } @Override TypeMem xmeet(Type t) { @@ -39,19 +59,28 @@ public class TypeMem extends Type { if( that==TOP ) return this; if( this==BOT ) return BOT; if( that==BOT ) return BOT; - int alias = _alias==that._alias ? _alias : 0; + int alias = _alias==that._alias ? _alias : 1; Type mt = _t.meet(that._t); return make(alias,mt); } @Override - public Type dual() { - return make(_alias,_t.dual()); + Type xdual() { return _t._dual==_t ? this : malloc(_alias,_t.dual()); } + + @Override TypeMem rdual() { + if( _dual!=null ) return dual(); + assert !_terned; + TypeMem d = malloc(_alias,null); + (_dual = d)._dual = this; // Cross link duals + d._t = _t._terned ? _t.dual() : _t.rdual(); + return d; } @Override public boolean isHigh() { return _t.isHigh(); } @Override public int log_size() { throw Utils.TODO(); } - @Override public Type glb(boolean mem) { return make(_alias,_t.glb(true)); } + @Override boolean _isFinal() { return _t._isFinal(); } + @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } + @Override public Type _glb(boolean mem) { return make(_alias,_t._glb(true)); } @Override int hash() { return 9876543 + _alias + _t.hashCode(); } @@ -60,15 +89,19 @@ public class TypeMem extends Type { return _alias == that._alias && _t == that._t; } - @Override public SB print(SB sb) { - sb.p("#"); - if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); - return _t.print(sb.p(_alias).p(":")); + @Override boolean cycle_eq(Type t) { + TypeMem that = (TypeMem) t; // Invariant + return _alias == that._alias && _t.cycle_eq(that._t); } - @Override public SB gprint(SB sb) { + + @Override int nkids() { return 1; } + @Override Type at( int idx ) { return _t; } + @Override void set( int idx, Type t ) { _t = t; } + + @Override public SB _print(SB sb, BitSet visit, boolean html) { sb.p("#"); if( _alias==0 ) return sb.p(_t._type==TTOP ? "TOP" : "BOT"); - return _t.gprint(sb.p(_alias).p(":")); + return _t.print(sb.p(_alias).p(":"),visit,html); } @Override public String str() { return toString(); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 78605e81..6041155d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -1,8 +1,9 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; +import java.util.*; /** * Represents a Pointer to memory. @@ -24,16 +25,35 @@ public class TypeMemPtr extends TypeNil { // (BOT ,false) - a not-nil void* (unspecified struct) // (TOP ,true ) - a nil - public final TypeStruct _obj; - public final boolean _one; // Singleton instance + public TypeStruct _obj; + public boolean _one; // Singleton instance - private TypeMemPtr(byte nil, TypeStruct obj, boolean singleton) { - super(TMEMPTR,nil); - assert obj!=null; - _obj = obj; - _one = singleton; + private static final Ary FREE = new Ary<>(TypeMemPtr.class); + private TypeMemPtr(byte nil, TypeStruct obj, boolean one) { super(TMEMPTR,nil); init(nil,obj,one); } + private TypeMemPtr init(byte nil, TypeStruct obj, boolean one) { _nil=nil; _obj=obj; _one=one; return this; } + // Return a filled-in TypeMemPtr; either from free list or alloc new. + private static TypeMemPtr malloc(byte nil, TypeStruct obj, boolean one) { + return FREE.isEmpty() ? new TypeMemPtr(nil,obj,one) : FREE.pop().init(nil,obj,one); } - public static TypeMemPtr make(byte nil, TypeStruct obj, boolean one) { return new TypeMemPtr(nil, obj, one).intern(); } + + // All fields directly listed + public static TypeMemPtr make(byte nil, TypeStruct obj, boolean one) { + TypeMemPtr tmp = malloc(nil, obj, one); + TypeMemPtr t2 = tmp.intern(); + if( t2==tmp ) return tmp; + return VISIT.isEmpty() ? t2.free(tmp) : t2.delayFree(tmp); + } + @Override TypeMemPtr free(Type t) { + TypeMemPtr tmp = (TypeMemPtr)t; + tmp._nil = -99; + tmp._obj = null; + tmp._dual = null; + tmp._hash = 0; + FREE.push(tmp); + return this; + } + @Override boolean isFree() { return _obj==null; } + 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); } @@ -41,8 +61,6 @@ public class TypeMemPtr extends TypeNil { 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, _one); } - @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); } - @Override public boolean isFinal() { return _obj.isFinal(); } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} @@ -56,16 +74,32 @@ public class TypeMemPtr extends TypeNil { @Override public TypeNil xmeet(Type t) { TypeMemPtr that = (TypeMemPtr) t; + assert !isFree() && !that.isFree(); return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), _one & that._one); } @Override - public TypeMemPtr dual() { return make( dual0(), _obj.dual(), !_one); } + TypeMemPtr xdual() { return malloc( dual0(), _obj.dual(), _one); } + + @Override TypeMemPtr rdual() { + if( _dual!=null ) return dual(); + assert !_terned; + TypeMemPtr d = malloc(dual0(), null, _one); + (_dual = d)._dual = this; // Cross link duals + d._obj = _obj._terned ? _obj.dual() : _obj.rdual(); + return d; + } - // RHS is NIL; do not deep-dual when crossing the centerline + // RHS is NIL; do not deep-dual when crossing the center line @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj); } - @Override public boolean isConstant() { return _one && _obj.isConstant(); } + @Override boolean _isConstant() { return _one && _obj._isConstant(); } + @Override boolean _isFinal() { return _obj._isFinal(); } + @Override TypeMemPtr _makeRO() { return makeFrom(_obj._makeRO()); } + @Override boolean _isGLB(boolean mem) { return _obj.isGLB2(); } + @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2()); } + @Override TypeMemPtr _close() { return makeFrom(_obj._close()); } + // True if this "isa" t up to named structures @Override public boolean shallowISA( Type t ) { @@ -78,7 +112,6 @@ public class TypeMemPtr extends TypeNil { throw Utils.TODO(); // return _obj.shallowISA(that._obj); } - @Override public TypeMemPtr glb(boolean mem) { return make((byte)3,_obj.glb(true)); } // Is forward-reference @Override public boolean isFRef() { return _obj.isFRef(); } @@ -88,8 +121,17 @@ public class TypeMemPtr extends TypeNil { @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _obj == ptr._obj && _one == ptr._one && super.eq(ptr); + return super.eq(ptr) && _one == ptr._one && _obj == ptr._obj; } + @Override boolean cycle_eq(Type t) { + if( t._type != TMEMPTR ) return false; + TypeMemPtr ptr = (TypeMemPtr)t; // Invariant + return super.eq(ptr) && _one == ptr._one && _obj.cycle_eq(ptr._obj); + } + + @Override int nkids() { return 1; } + @Override Type at( int idx ) { return _obj; } + @Override void set( int idx, Type t ) { _obj = (TypeStruct)t; } @Override public String str() { if( this== NOTBOT) return "*void"; @@ -97,14 +139,9 @@ public class TypeMemPtr extends TypeNil { return x()+"*"+_obj.str()+q(); } - @Override public SB print(SB sb) { - if( this== NOTBOT) return sb.p("*void"); - if( this== BOT) return sb.p("*void?"); - return _obj.print(sb.p(x()).p("*")).p(q()); - } - @Override public SB gprint(SB sb) { + @Override SB _print(SB sb, BitSet visit, boolean html ) { if( this== NOTBOT) return sb.p("*void"); if( this== BOT) return sb.p("*void?"); - return _obj.gprint(sb.p(x()).p("*")).p(q()); + return _obj.print(sb.p(x()).p("*"),visit,html).p(q()); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/src/main/java/com/seaofnodes/simple/type/TypeNil.java index 3902c40b..56d73b00 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeNil.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; /** @@ -12,7 +12,7 @@ public abstract class TypeNil extends Type { // 1 = high-subclass no nil // 2 = low -subclass no nil // 3 = low -subclass also nil - final byte _nil; + byte _nil; TypeNil(byte t, byte nil ) { super(t); _nil = nil; } @@ -45,18 +45,18 @@ public abstract class TypeNil extends Type { } @Override public boolean isHigh () { return _nil <= 1; } - @Override public boolean isConstant () { return false; } @Override public boolean isHighOrConst() { return isHigh() || isConstant(); } - @Override public Type glb(boolean mem) { return Type.NIL; } - public boolean notNull() { return _nil==1 || _nil==2; } public boolean nullable() { return _nil==3; } + @Override boolean _isConstant() { return false; } + @Override Type _glb(boolean mem) { return Type.NIL; } + final String q() { return _nil == 1 || _nil == 2 ? "" : "?"; } final String x() { return isHigh() ? "~" : ""; } int hash() { return _nil<<17; } - boolean eq(TypeNil ptr) { return _nil == ptr._nil; } + @Override boolean eq(Type ptr) { return ptr instanceof TypeNil nil && _nil ==nil._nil; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/src/main/java/com/seaofnodes/simple/type/TypePtr.java index d9de5cd7..75478119 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -1,13 +1,15 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; +import java.util.BitSet; /** * Represents a Scalar; a single register-sized value. */ public class TypePtr extends TypeNil { + private static final String[] STRS = new String[]{"~ptr","~nptr","nptr","ptr"}; private TypePtr(byte nil) { super(TPTR,nil); } @@ -15,8 +17,8 @@ public class TypePtr extends TypeNil { // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} public static TypePtr XPTR = new TypePtr((byte)0).intern(); public static TypePtr XNPTR= new TypePtr((byte)1).intern(); - public static TypePtr NPTR = new TypePtr((byte)2).intern(); - public static TypePtr PTR = new TypePtr((byte)3).intern(); + public static TypePtr NPTR = (TypePtr)XNPTR.dual(); + public static TypePtr PTR = (TypePtr)XPTR.dual(); private static final TypePtr[] PTRS = new TypePtr[]{XPTR,XNPTR,NPTR,PTR}; public static void gather(ArrayList ts) { ts.add(PTR); ts.add(NPTR); } @@ -28,7 +30,7 @@ public class TypePtr extends TypeNil { return PTRS[xmeet0(that)]; } - @Override public TypePtr dual() { return PTRS[dual0()]; } + @Override TypePtr xdual() { return new TypePtr((byte)(3-_nil)); } // High scalar loses, low scalar wins @Override TypeNil nmeet(TypeNil tn) { @@ -45,9 +47,9 @@ 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(boolean mem) { return PTR; } + boolean _isGLB(boolean mem) { return this==PTR; } + @Override TypePtr _glb(boolean mem) { return PTR; } - private static final String[] STRS = new String[]{"~ptr","~nptr","nptr","ptr"}; @Override public String str() { return STRS[_nil]; } - @Override public SB print(SB sb) { return sb.p(str()); } + @Override public SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index ec2f5f0a..bd5e2923 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.BitSet; import java.util.HashSet; @@ -48,10 +48,6 @@ public class TypeRPC extends Type { return "$["+(_any ? "-" : "")+_rpcs+"]"; } - @Override public boolean isConstant() { - return !_any && _rpcs.size()==1; - } - @Override public TypeRPC xmeet(Type other) { TypeRPC rpc = (TypeRPC)other; @@ -87,7 +83,10 @@ public class TypeRPC extends Type { } @Override - public Type dual() { return make(!_any,_rpcs); } + Type xdual() { return new TypeRPC(!_any,_rpcs); } + + @Override boolean _isConstant() { return !_any && _rpcs.size()==1; } + @Override boolean _isGLB(boolean mem) { return true; } @Override int hash() { return _rpcs.hashCode() ^ (_any ? -1 : 0) ; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 66a37d41..73fecdab 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.util.*; +import java.util.*; /** * Represents a struct type. @@ -11,69 +11,129 @@ public class TypeStruct extends Type { // A Struct has a name and a set of fields; the fields themselves have // names, types and aliases. The name has no semantic meaning, but is - // useful for debugging. Briefly during parsing a Struct can be a - // forward-ref; in this case the _fields array is null. - - // Its illegal to attempt to load a field from a forward-ref struct. - - // Example: "int rez = new S.x; struct S { int x; } return rez;" // Error, S not defined - // Rewrite: "struct S { int x; } int rez = new S.x; return rez;" // Ok, no forward ref - // - // During the normal optimization run, struct types "bottom out" at further - // struct references, so we don't have to handle e.g. cyclic types. The - // "bottom out" is again the forward-ref struct. - public final String _name; - public final Field[] _fields; - public final TypeConAry _con; // Optional, constant array contents - - private TypeStruct(String name, TypeConAry con, Field[] fields) { + // useful for debugging. + + // During parsing a mid-declaration struct is flagged as a "open". It is + // treated as having infinite fields with correct name and type BOTTOM. + + public String _name; // Struct name + public boolean _open; // infinite fields are all true:BOTTOM, false:TOP + public Field[] _fields; + + private TypeStruct(String name, boolean open, Field[] fields) { super(TSTRUCT); _name = name; + _open = open; _fields = fields; - _con = con; } + private static final Ary FREE = new Ary<>(TypeStruct.class); + // Return a filled-in TypeStruct; either from free list or alloc new. + private static TypeStruct malloc(String name, boolean open, Field[] fields) { + if( FREE.isEmpty() ) return new TypeStruct(name,open,fields); + TypeStruct ts = FREE.pop(); + assert ts.isFree(); + ts._name = name; + ts._open = open; + ts._fields = fields; + return ts; + } + // Free ts; return this. + @Override TypeStruct free(Type t) { + TypeStruct ts = (TypeStruct)t; + assert !ts.isFree() && !ts._terned; + ts._fields = null; + ts._offs = null; + ts._dual = null; + ts._hash = 0; + FREE.push(ts); + return this; + } + @Override boolean isFree() { return _fields==null; } + + // All fields directly listed - 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}); - // Forward-ref version - public static TypeStruct makeFRef(String name) { return make(name, (Field[])null); } - // Make a read-only version - @Override public TypeStruct makeRO() { - if( isFinal() ) return this; - Field[] flds = new Field[_fields.length]; - for( int i=0; i ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); ts.add(STR); ts.add(HELLO); } + public static final TypeStruct BOT = open("$STRUCT"); + public static final TypeStruct TOP = BOT.dual(); + public static final TypeStruct TEST= make("test",false,Field.TEST); + private static final TypeStruct ARY = makeAry("[]i64",TypeInteger.U32,-1,TypeInteger.BOT,-2,false); + private static final TypeStruct STR = makeAry("[]u8" ,TypeInteger.U32,-1,TypeInteger.U8 ,-4,false); + private static final TypeStruct ABC = makeAry("[]u8",TypeInteger.constant(3),-1,TypeConAryB.ABC,-4,true); + + // A pair of self-cyclic types + private static final TypeStruct SINT0 = open("%SINT"); + private static final TypeStruct SFLT0 = open("%SFLT"); + private static final TypeStruct SINT1 = SINT0.add(Field.make("a", TypeInteger.U32, -1, false, false)).add(Field.make("s2",TypeMemPtr.make((byte)2,SFLT0),-2, false, false)); + private static final TypeStruct SFLT1 = SFLT0.add(Field.make("b", TypeFloat .F32, -3, false, false)).add(Field.make("s1",TypeMemPtr.make((byte)2,SINT1),-4, false, false)); + public static final TypeStruct SFLT2 = SFLT1.close(); + + + public static void gather(ArrayList ts) { + ts.add(BOT); + ts.add(TEST); + ts.add(ARY); + ts.add(STR); + ts.add(ABC); + ts.add(SINT0); + ts.add(SFLT0); + ts.add(SINT1); + ts.add(SFLT1); + ts.add(SFLT2); + ts.add(((TypeMemPtr)(SFLT2.field("s1")._t))._obj); + // Break cyclic init: built a struct + Field fcalloc = Field.make("calloc",TypeFunPtr.CALLOC,-2,true,true); + TypeStruct scalloc = make("calloc",false,fcalloc); + ts.add(scalloc); + + } // Find field index by name public int find(String fname) { @@ -95,10 +155,10 @@ public class TypeStruct extends Type { return -1; } - @Override - Type xmeet(Type t) { + TypeStruct xmeet(Type t) { TypeStruct that = (TypeStruct) t; + assert !isFree() && !that.isFree(); if( this==TOP ) return that; if( that==TOP ) return this; if( this==BOT ) return BOT; @@ -112,96 +172,154 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know - if( this._fields==null ) return that; - if( that._fields==null ) return this; - if( _fields.length != that._fields.length ) return BOT; - // Just do field meets - Field[] flds = new Field[_fields.length]; - for( int i=0; i<_fields.length; i++ ) { + + // if equal, no matters. + // if short is BOT, chop ; recurPre on short. + // if short is TOP, copy long; recurPre on long. + TypeStruct min = _fields.length < that._fields.length ? this : that; + if( _fields.length != that._fields.length && (min._open ^ min==this) ) + return that.xmeet(this); + + // Check all other fields are sanely similar; same struct type but + // different field contents (e.g. field "age" is either 'int' or '18'). + int len = Math.min(_fields.length,that._fields.length); + for( int i=0; i256_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=2 && _fields[_fields.length-1]._fname=="[]"; } @@ -262,7 +411,7 @@ public class TypeStruct extends Type { } public int aryScale() { assert isAry(); - return _fields[1]._type.log_size(); + return _fields[1]._t.log_size(); } @@ -273,42 +422,44 @@ public class TypeStruct extends Type { return _offs[idx]; } private int[] offsets() { // Field byte offsets + assert CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); // Compute a layout for a collection of fields assert _fields != null; // No forward refs // Compute a layout - 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=0; i-- ) { - offs[i] = off; - off += cnts[i]<