From 59a06668f3975c90459409e25e884b4b594cbe3b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 7 Nov 2024 14:17:20 -0800 Subject: Allow post ++, -- Fix eval auto-string result. Fix tests hacked because of this. Turn on BrainFuck in ch15,16,17, also disabled because of this. Use new features in BrainFuck. Fix bug not lifting forward refs; add a toString to Vars. Fix some missing addDeps. Remove large complex not-productive peep. Upcast after "while" tests. Improves a bunch of tests. Remove dead getBlockStart. --- .../main/java/com/seaofnodes/simple/Parser.java | 37 +++++++++----- .../java/com/seaofnodes/simple/node/CProjNode.java | 4 -- .../java/com/seaofnodes/simple/node/IfNode.java | 2 - .../java/com/seaofnodes/simple/node/LoadNode.java | 11 ++-- .../java/com/seaofnodes/simple/node/MemOpNode.java | 5 +- .../main/java/com/seaofnodes/simple/node/Node.java | 6 +-- .../com/seaofnodes/simple/node/RegionNode.java | 58 ---------------------- .../com/seaofnodes/simple/node/ReturnNode.java | 2 - .../com/seaofnodes/simple/node/ScopeMinNode.java | 20 ++++++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 18 ++++--- .../java/com/seaofnodes/simple/node/ShlNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 - .../java/com/seaofnodes/simple/node/StopNode.java | 2 - .../java/com/seaofnodes/simple/node/StoreNode.java | 12 +++-- .../main/java/com/seaofnodes/simple/type/Type.java | 3 ++ .../com/seaofnodes/simple/type/TypeMemPtr.java | 2 + .../com/seaofnodes/simple/type/TypeStruct.java | 13 +++-- 17 files changed, 86 insertions(+), 113 deletions(-) (limited to 'chapter17/src/main/java/com/seaofnodes') diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index d2a1a9ae..9710be30 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -96,7 +96,7 @@ public class Parser { // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not // have C-style '*ptr' references. - public final HashMap TYPES; + public static HashMap TYPES; // Mapping from a type name to the constructor for a Type. public final HashMap INITS; @@ -267,6 +267,7 @@ public class Parser { // the loop predicate. Note that body Scope is still our current scope. ctrl(ifF); _xScopes.push(_breakScope = _scope.dup()); + _breakScope.upcast(ifF,pred,true); // Up-cast predicate // No continues yet _continueScope = null; @@ -274,6 +275,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection + _scope.upcast(ifT,pred,false); // Up-cast predicate parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -302,7 +304,8 @@ public class Parser { // the scope is the exit scope after the exit test. _xScopes.pop(); _xScopes.push(exit); - return _scope = exit; + _scope = exit; + return _scope; } private ScopeNode jumpTo(ScopeNode toScope) { @@ -438,7 +441,7 @@ public class Parser { // need to check the final bit. if( _scope.in(def._idx)._type!=Type.TOP && def._final ) throw error("Cannot reassign final '"+name+"'"); - t = def._type; // Declared field type + t = def.type(); // Declared field type } // Auto-widen int to float @@ -527,7 +530,7 @@ public class Parser { for( int i=lexlen; i - * primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')' + * primaryExpr : integerLiteral | true | false | null | new Type | '(' expression ')' | Id['++','--'] * * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); - if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( match("(") ) return require(parseExpression(), ")"); if( matchx("new" ) ) return alloc(); // Expect an identifier now - String name = _lexer.matchId(); - if( name == null) throw errorSyntax("an identifier or expression"); - ScopeMinNode.Var n = _scope.lookup(name); - if( n!=null ) return _scope.in(n); - throw error("Undefined name '" + name + "'"); + ScopeMinNode.Var n = requireLookupId("an identifier or expression"); + Node rvalue = _scope.in(n).keep(); + if( matchx("++") ) _scope.update(n,new AddNode(rvalue,con( 1)).peephole()); + if( matchx("--") ) _scope.update(n,new AddNode(rvalue,con(-1)).peephole()); + return rvalue.unkeep(); + } + + ScopeMinNode.Var requireLookupId(String msg) { + String id = _lexer.matchId(); + if( id == null || KEYWORDS.contains(id) ) + throw errorSyntax(msg); + ScopeMinNode.Var n = _scope.lookup(id); + if( n==null ) + throw error("Undefined name '" + id + "'"); + return n; } /** diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 3d6fd1fa..d2f1bbe1 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -51,10 +51,6 @@ public class CProjNode extends CFGNode { return null; } - @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } @Override boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3cce89ab..41de4c82 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -66,6 +66,4 @@ public class IfNode extends CFGNode implements MultiNode { unreach.add((CProjNode)proj); super._walkUnreach(visit,unreach); } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d15d4f83..2c0afda2 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -33,10 +33,13 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem && - // No constant folding if ptr might null-check - _declaredType != mem._t && err()==null ) { - return _declaredType.join(mem._t); + 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); } return _declaredType; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index c7a1efec..82aab8ac 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -11,7 +10,9 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public final Type _declaredType; + // Declared type; not final because it might be a forward-reference + // which will be lazily improved when the reference is declared. + public Type _declaredType; public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { super(null, mem, ptr, off); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java index 462a403c..c67fb910 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -278,6 +278,7 @@ public abstract class Node implements OutNode { int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -419,7 +420,7 @@ public abstract class Node implements OutNode { * And more folding: * 
   ary + ((idx<<2) + 16)
* And during code-gen: - * 
   MOV4 Rary,Ridx,16 // or some such hardware-specific notation
+ * 
   MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation
*

* {@link #idealize} has a very specific calling convention: *

    @@ -542,9 +543,6 @@ public abstract class Node implements OutNode { /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 941de76b..a55bb479 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -72,65 +72,9 @@ public class RegionNode extends CFGNode { p1.in(0) instanceof IfNode iff ) return iff.ctrl(); - - // Look for direct uses of a guarded expression, and replace with the guard result. - if( !(idom() instanceof StartNode) && // Dead or dying - !(this instanceof LoopNode) ) { - VISIT.clear(); - boolean progress = false; - outer: - for( int i=1; i=0; - _update(_vars.at(idx),n); + update(_vars.at(idx),n); } - Var _update( ScopeNode.Var v, Node st ) { + public Var update( ScopeNode.Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -151,7 +151,7 @@ public class ScopeNode extends ScopeMinNode { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,new PhiNode(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,new PhiNode(v._name, v.glb(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value @@ -223,9 +223,9 @@ public class ScopeNode extends ScopeMinNode { // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation Var v = _vars.at(i); - Node lhs = this.in(this._update(v,null)); - Node rhs = that.in(that._update(v,null)); - setDef(i, new PhiNode(v._name, v._type, r, lhs, rhs).peephole()); + Node lhs = this.in(this.update(v,null)); + Node rhs = that.in(that.update(v,null)); + setDef(i, new PhiNode(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -268,6 +268,8 @@ public class ScopeNode extends ScopeMinNode { // This Scope looks for direct variable uses, or certain simple // combinations, and replaces the variable with the upcast variant. public Node upcast( Node ctrl, Node pred, boolean invert ) { + if( ctrl._type == Type.XCONTROL || pred.isDead() ) + return null; // Dead, do not do anything // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java index b67d985a..6fd951e4 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -44,7 +44,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java index c03a4b06..d82030f8 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -44,6 +44,4 @@ public class StartNode extends CFGNode implements MultiNode { @Override void _walkUnreach( BitSet visit, HashSet unreach ) { } @Override public int loopDepth() { return (_loopDepth=1); } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..5a02190a 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -84,6 +84,4 @@ public class StopNode extends CFGNode { GlobalCodeMotion.buildCFG(this); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 7b1bddd5..8e3e6693 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -42,9 +42,15 @@ public class StoreNode extends MemOpNode { public Type compute() { Type val = val()._type; TypeMem mem = (TypeMem)mem()._type; // Invariant - Type t = mem._alias==_alias - ? val.meet(mem._t) // Meet into existing memory - : Type.BOTTOM; + 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; + val = val.join(_declaredType); + t = val.meet(mem._t); + } return TypeMem.make(_alias,t); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java index 989eff9e..7467be79 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java @@ -179,6 +179,9 @@ public class Type { */ public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; } + // Is forward-reference + public boolean isFRef() { return false; } + // ---------------------------------------------------------- // Size in bits to hold an instance of this type. diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index ec059b8f..449bf89e 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -57,6 +57,8 @@ public class TypeMemPtr extends Type { @Override public TypeMemPtr glb() { return make(_obj.glb(),true); } + // Is forward-reference + @Override public boolean isFRef() { return _obj.isFRef(); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override public Type nonZero() { return VOIDPTR; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4e4d1305..39011ce2 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -36,7 +36,7 @@ public class TypeStruct extends Type { 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 make(String name) { return make(name, (Field[])null); } + public static TypeStruct makeFRef(String name) { return make(name, (Field[])null); } // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { @@ -47,8 +47,8 @@ public class TypeStruct extends Type { } // A pair of self-cyclic types - private static final TypeStruct S1F = make("S1"); - private static final TypeStruct S2F = make("S2"); + private static final TypeStruct S1F = makeFRef("S1"); + private static final TypeStruct S2F = makeFRef("S2"); public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) }); private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) }); @@ -89,8 +89,8 @@ 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 this; - if( that._fields==null ) return that; + 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]; @@ -132,6 +132,9 @@ public class TypeStruct extends Type { return true; } + // Is forward-reference + @Override public boolean isFRef() { return _fields==null; } + @Override boolean eq(Type t) { TypeStruct ts = (TypeStruct)t; // Invariant -- cgit v1.2.3