From 555604e0c870e10720e4baeabe93a2b0ae5a60c9 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 7 May 2024 13:08:16 -0700 Subject: Fix a series of recent bugs (#79) Simplify idom usage; removes a difficult to maintain cache, which does add a (rare) big-O slowdown. Suggestions welcome. Cut outs for some peeps on various dead/dying graphs. --- .../main/java/com/seaofnodes/simple/Parser.java | 1 + .../com/seaofnodes/simple/node/ConstantNode.java | 12 +++---- .../java/com/seaofnodes/simple/node/LoadNode.java | 4 +-- .../java/com/seaofnodes/simple/node/LoopNode.java | 3 +- .../main/java/com/seaofnodes/simple/node/Node.java | 40 +++++++++------------- .../com/seaofnodes/simple/node/RegionNode.java | 31 ++++++++--------- .../java/com/seaofnodes/simple/node/StartNode.java | 4 +-- .../java/com/seaofnodes/simple/node/StopNode.java | 2 ++ .../java/com/seaofnodes/simple/node/StoreNode.java | 5 ++- 9 files changed, 47 insertions(+), 55 deletions(-) (limited to 'chapter10/src/main/java') diff --git a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java index 267e0eb4..b9535208 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java @@ -618,6 +618,7 @@ public class Parser { String name = requireId(); Field field = ptr._obj==null ? null : ptr._obj.get(name); if( field == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + field = field.glb(); // Even if the parser knows the field is a high type, use the low one if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index c4ea08b5..ca42c2dc 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -23,10 +23,10 @@ public class ConstantNode extends Node { super(Parser.START); _con = type; } - + @Override public String label() { return "#"+_con; } - + @Override public String uniqueName() { return "Con_" + _nid; } @@ -34,9 +34,9 @@ public class ConstantNode extends Node { StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con._print(sb); } - + @Override public boolean isMultiTail() { return true; } - + @Override public Type compute() { return _con; } @@ -51,8 +51,4 @@ public class ConstantNode extends Node { @Override int hash() { return _con.hashCode(); } - - // Dead control is its own idom root - Node idom() { return null; } - } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d37c6296..103232f1 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -53,8 +53,8 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof PhiNode phi && phi.nIns()== 3 && - ((phi.in(1) instanceof StoreNode st1 && ptr()==st1.ptr()) || - (phi.in(2) instanceof StoreNode st2 && ptr()==st2.ptr()) ) ) { + ((phi.in(1) instanceof StoreNode st1 && ptr()==st1.ptr() && phi.in(2)!=phi ) || + (phi.in(2) instanceof StoreNode st2 && ptr()==st2.ptr() && phi.in(1)!=phi ) ) ) { Node ld1 = new LoadNode(_field,phi.in(1),ptr()).peephole(); Node ld2 = new LoadNode(_field,phi.in(2),ptr()).peephole(); return new PhiNode(_field._fname,_type,phi.region(),ld1,ld2); diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 0b84f897..96ce71eb 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,5 +25,6 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } + // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) + @Override Node idom() { return entry(); } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java index 6a32c092..9ae81ac3 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java @@ -50,15 +50,6 @@ public abstract class Node { public Type _type; - /** - * Immediate dominator tree depth, used to approximate a real IDOM during - * parsing where we do not have the whole program, and also peepholes - * change the CFG incrementally. - *

- * See {@link ...} - */ - int _idepth; - /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -553,14 +544,11 @@ public abstract class Node { } /** - * Does this node contain all constants? - * Ignores in(0), as is usually control. - * In an input is not a constant, we add dep as - * a dependency to it, because dep can make progress - * if the input becomes a constant later. - * It is sufficient for one of the non-const - * inputs to have the dependency so we don't bother - * checking the rest. + * Does this node contain all constants? Ignores in(0), as is usually + * control. In an input is not a constant, we add dep as a dependency to + * it because dep can make progress if the input becomes a constant later. + * It is sufficient for one of the non-const inputs to have the dependency, + * so we don't bother checking the rest. */ boolean allCons(Node dep) { for( int i=1; i + * See {@link ...} + */ + public int _idepth; + int idepth() { return _idepth==0 ? idom()._idepth+1 : _idepth; } + // Return the immediate dominator of this Node and compute dom tree depth. - Node idom() { - Node idom = in(0); - if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth - if( _idepth==0 ) _idepth = idom._idepth+1; - return idom; - } + Node idom() { return in(0); } // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java index f06a8234..c4bd1572 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -56,14 +56,11 @@ public class RegionNode extends Node { IterPeeps.addAll(phi._outputs); } } - _idom = null; // Clear idom cache return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); } // If down to a single input, become that input - if( nIns()==2 && !hasPhi() ) { - _idom = null; // Clear idom cache + if( nIns()==2 && !hasPhi() ) return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own - } return null; } @@ -82,26 +79,28 @@ public class RegionNode extends Node { } // Immediate dominator of Region is a little more complicated. - private Node _idom; // Immediate dominator cache + @Override int idepth() { + if( _idepth!=0 ) return _idepth; + int d=0; + for( Node n : _inputs ) + if( n!=null ) + d = Math.max(d,n.idepth()); + return _idepth=d; + } + @Override Node idom() { - if( _idom != null ) { - if( _idom.isDead() ) _idom=null; - else return _idom; // Return cached copy - } if( nIns()==2 ) return in(1); // 1-input is that one input if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs - // Walk the LHS & RHS idom trees in parallel until they match, or either fails - Node lhs = in(1).idom(); - Node rhs = in(2).idom(); + // Walk the LHS & RHS idom trees in parallel until they match, or either fails. + // Because this does not cache, it can be linear in the size of the program. + Node lhs = in(1); + Node rhs = in(2); while( lhs != rhs ) { if( lhs==null || rhs==null ) return null; - var comp = lhs._idepth - rhs._idepth; + var comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = lhs.idom(); if( comp <= 0 ) rhs = rhs.idom(); } - if( lhs==null ) return null; - _idepth = lhs._idepth+1; - if( !IterPeeps.midAssert() ) _idom=lhs; return lhs; } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5cfeb5f9..42b38503 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -65,6 +65,6 @@ public class StartNode extends MultiNode { public Node idealize() { return null; } // No immediate dominator, and idepth==0 - @Override - Node idom() { return null; } + @Override int idepth() { return 0; } + @Override Node idom() { return null; } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0bf9eb66..3b5a7ce3 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -51,6 +51,8 @@ public class StopNode extends Node { return null; } + @Override public Node idom() { return null; } + public Node addReturn(Node node) { return addDef(node); } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8faf6d4b..00d75f02 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.Field; -import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -47,6 +45,7 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && // Must check same object + ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { -- cgit v1.2.3