path: root/src/main/java/com/seaofnodes/simple/node/Node.java

package com.seaofnodes.simple.node;

import com.seaofnodes.print.BaseNode;

import com.seaofnodes.simple.IterPeeps;
import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.codegen.CodeGen;
import com.seaofnodes.simple.codegen.GlobalBits;
import com.seaofnodes.simple.print.IRPrinter;
import com.seaofnodes.simple.type.*;
import com.seaofnodes.simple.util.*;
import java.util.*;
import java.util.function.Function;
import static com.seaofnodes.simple.codegen.CodeGen.CODE;

/**
 * All Nodes in the Sea of Nodes IR inherit from the Node class.
 * The Node class provides common functionality used by all subtypes.
 * Subtypes of Node specialize by overriding methods.
 */
public abstract class Node extends BaseNode<Node> implements Cloneable {

    /**
     * Inputs to the node. These are use-def references to Nodes.
     * <p>
     * Generally fixed length, ordered, nulls allowed, no unused trailing space.
     * Ordering is required because e.g. "a/b" is different from "b/a".
     * The first input (offset 0) is often a {@link CFGNode} node.
     */
    public Ary<Node> _inputs;

    /**
     * Outputs reference Nodes that are not null and have this Node as an
     * input.  These nodes are users of this node, thus these are def-use
     * references to Nodes.
     * <p>
     * Outputs directly match inputs, making a directed graph that can be
     * walked in either direction.  These outputs are typically used for
     * efficient optimizations but otherwise have no semantics meaning.
     */
     public Ary<Node> _outputs;

    /**
     * Current computed type for this Node.  This value changes as the graph
     * changes and more knowledge is gained about the program.
     */
    public Type _type;

    Node(Node... inputs) {
        super(CODE.getUID()); // allocate unique dense ID
        _inputs = new Ary<>(Node.class);
        Collections.addAll(_inputs,inputs);
        _outputs = new Ary<>(Node.class);
        for( Node n : _inputs )
            if( n != null )
                n.addUse( this );
    }

    // Make a Node using the existing arrays of nodes.
    // Used by any pass rewriting all Node classes but not the edges.
    Node( Node n ) {
        super(CODE.getUID()); // allocate unique dense ID
        assert CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Select.ordinal();
        _inputs  = new Ary<>(n==null ? new Node[0] : n._inputs.asAry());
        _outputs = new Ary<>(Node.class);
        _type = n==null ? Type.BOTTOM : n._type;
        _deps = null;
        _hash = 0;
    }

    // Disk/serialized opcode tags
    public enum Tag {
        Add,And,EQ,NE,LT,LE,ULT,
        CallEnd,Call,ConFldOff,Con,CProj,
        Div,Escape,Extern,Fun,FunPtr,If,Load,Loop,
        MemMerge,Minus,Mul,
        New,Never,Not,Or,Parm,Phi,Proj,
        ReadOnly,Return,Region,RoundF32,
        Sar,Shl,Shr,Start,Stop,Store,Sub,ToFloat,
        XCtrl,Xor,StartCU,StopCU,Guard,MemPhi,BulkMemPhi,PtrToInt,ExternOffset,ToInteger;
        public static final Tag[] VALS = values();
        public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) {
            return switch(this) {
            case Add    -> new   AddNode(null,null,(byte)bais.packed1());
            case And    -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); }
            case Div    -> new   DivNode(null,null,(byte)bais.packed1());
            case If     -> new    IfNode(null,null);
            case Loop   -> new  LoopNode(null,null,null);
            case Minus  -> new MinusNode(null,(byte)bais.packed1());
            case Mul    -> new   MulNode(null,null,(byte)bais.packed1());
            case Never  -> new NeverNode(1.2f, null);
            case Not    -> new   NotNode(null);
            case Or     -> { int mode=bais.packed1(); assert mode==1; yield new OrNode(null,null,null); }
            case ReadOnly-> new ReadOnlyNode((Node)null);
            case Return ->new ReturnNode(null,null,null,null,null);
            case RoundF32-> new RoundF32Node(null);
            case PtrToInt-> new PtrToIntNode((Node)null);
            case Sar    -> { int mode=bais.packed1(); assert mode==1; yield new SarNode(null,null,null); }
            case Shl    -> { int mode=bais.packed1(); assert mode==1; yield new ShlNode(null,null,null); }
            case Shr    -> { int mode=bais.packed1(); assert mode==1; yield new ShrNode(null,null,null); }
            case Start  -> new StartNode(null,null,TypeInteger.BOT);
            case Sub    -> new   SubNode(null,null,(byte)bais.packed1());
            case ToFloat-> new ToFloatNode(null);
            case ToInteger-> new ToIntegerNode(null);
            case XCtrl  -> new XCtrlNode();
            case Xor    -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); }
            case Guard -> GuardNode.make(bais);

            case EQ    -> new  BoolNode.EQ (null,null,(byte)bais.packed1());
            case NE    -> new  BoolNode.NE (null,null,(byte)bais.packed1());
            case LT    -> new  BoolNode.LT (null,null,(byte)bais.packed1());
            case LE    -> new  BoolNode.LE (null,null,(byte)bais.packed1());
            case ULT   -> new  BoolNode.ULT(null,null,(byte)bais.packed1());

            case Call  ->      CallNode.make(bais);
            case CallEnd->  CallEndNode.make(bais     ,types);
            case CProj ->     CProjNode.make(bais,strs);
            case Con   ->  ConstantNode.make(bais     ,types);
            case Escape->    EscapeNode.make(bais     ,types);
            case Extern->    ExternNode.make(bais,strs,types);
            case ExternOffset-> new ExternOffsetNode(strs[bais.packed2()]);
            case FunPtr->   FunPtrNode.make(bais,     types);
            case Fun   ->       FunNode.make(bais,strs,types);
            case Load  ->       new LoadNode(bais,strs,types,fileAliases,aliases);
            case MemMerge->MemMergeNode.make(bais);
            case MemPhi->  MemPhiNode.make(bais,strs,types,fileAliases,aliases);
            case BulkMemPhi-> BulkMemPhiNode.make(bais,strs,types,fileAliases,aliases);
            case New   ->       NewNode.make(bais     ,types);
            case Parm  ->      ParmNode.make(bais,strs,types);
            case Phi   ->       PhiNode.make(bais,strs,types);
            case Proj  ->      ProjNode.make(bais,strs);
            case Store ->      new StoreNode(bais,strs,types,fileAliases,aliases);
            case Stop ->       StopNode.make(bais);
            case StartCU->  StartCUNode.make(bais,strs,types);
            case StopCU ->   StopCUNode.make(bais);
            case Region->    RegionNode.make(bais);

            default -> throw Utils.TODO("Should not reach here");
            };
        }
    };
    public Tag serialTag() { throw Utils.TODO(); }
    // Serialize extra data, including input counts
    public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {}

    // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
    public String label() { return serialTag().toString(); }

    public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }

    public boolean isConst() { return false; }

    // ------------------------------------------------------------------------
    // Graph Node & Edge manipulation

    @Override public String typeName() { return _type==null ? null : _type.toString(); }

    /**
     * Gets the ith input node
     * @param i Offset of the input node
     * @return Input node or null
     */
    public Node in(int i) { return _inputs.get(i); }
    public Node out(int i) { return _outputs.get(i); }
    public final Ary<Node> outs() { return _outputs; }

    public int nIns() { return _inputs.size(); }

    public int nOuts() { return _outputs.size(); }

    public boolean isUnused() { return nOuts() == 0; }

    public CFGNode cfg0() { return (CFGNode)in(0); }

    /**
     * Change a <em>def</em> into a Node.  Keeps the edges correct, by removing
     * the corresponding <em>use->def</em> edge.  This may make the original
     * <em>def</em> go dead.  This function is co-recursive with {@link #kill}.
     * <p>

     * This method is the normal path for altering a Node, because it does the
     * proper default edge maintenance.  It also <em>immediately</em> kills
     * Nodes that lose their last use; at times care must be taken to avoid
     * killing Nodes that are being used without having an output Node.  This
     * definitely happens in the middle of recursive {@link #peephole} calls.
     *
     * @param idx which def to set
     * @param new_def the new definition
     * @return new_def for flow coding
     */
    public <N extends Node> N setDef(int idx, N new_def ) {
        unlock();
        Node old_def = in(idx);
        if( old_def == new_def ) return new_def; // No change
        // If new def is not null, add the corresponding def->use edge
        // This needs to happen before removing the old node's def->use edge as
        // the new_def might get killed if the old node kills it recursively.
        if( new_def != null )
            new_def.addUse(this);
        // Set the new_def over the old (killed) edge
        _inputs.set(idx,new_def);
        if( old_def != null ) {        // If the old def exists, remove a def->use edge
            if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead
                old_def.kill();        // Kill old def
            else CODE.add(old_def);    // Else old lost a use, so onto worklist
        }
        moveDepsToWorklist();
        // Return new_def for easy flow-coding
        return new_def;
    }
    public <N extends Node> N setDefX(int idx, N new_def ) {
        while( nIns() <= idx ) addDef(null);
        return setDef(idx,new_def);
    }

    // Remove the numbered input, compressing the inputs in-place.  This
    // shuffles the order deterministically - which is suitable for Region and
    // Phi, but not for every Node.  If the def goes dead, it is recursively
    // killed, which may include 'this' Node.
    public Node delDef(int idx) {
        unlock();
        Node old_def = in(idx);
        _inputs.del(idx);
        if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead
            old_def.kill();     // Kill old def
        old_def.moveDepsToWorklist();
        return this;
    }

    // Insert the numbered input, sliding other inputs to the right
    public void insertDef(int idx, Node new_def) {
        _inputs.insert(null,idx);
        setDef(idx,new_def);
    }

    /**
     * Add a new def to an existing Node.  Keep the edges correct by
     * adding the corresponding <em>def->use</em> edge.
     *
     * @param new_def the new definition, appended to the end of existing definitions
     * @return new_def for flow coding
     */
    public Node addDef(Node new_def) {
        unlock();
        // Add use->def edge
        _inputs.add(new_def);
        // If new def is not null, add the corresponding def->use edge
        if( new_def != null )
            new_def.addUse(this);
        return new_def;
    }

    // Breaks the edge invariants, used temporarily
    @SuppressWarnings("unchecked")
    protected <N extends Node> N addUse(Node n) { _outputs.add(n); return (N)this; }

    // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
    // Return true if the output list is empty afterward.
    // Error is 'use' does not exist; ok for 'use' to be null.
    public boolean delUse( Node use ) {
        _outputs.del(_outputs.find(use));
        moveDepsToWorklist(); // User-count and anti-dependence queries can now change.
        return _outputs.isEmpty();
    }

    // Shortcut for "popping" until n nodes.  A "pop" is basically a
    // setDef(last,null) followed by lowering the nIns() count.
    public void popUntil(int n) {
        unlock();
        while( nIns() > n ) {
            Node old_def = _inputs.pop();
            if( old_def != null &&     // If it exists and
                old_def.delUse(this) ) // If we removed the last use, the old def is now dead
                old_def.kill();        // Kill old def
        }
    }
    public Node removeLast() {
        Node old_def = _inputs.pop();
        if( old_def != null )
            old_def.delUse(this);
        return old_def;
    }

    /**
     * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em>
     * to null.  This may recursively kill more Nodes, and is basically dead
     * code elimination.
     */
    public void kill( ) {
        assert isUnused();      // Has no uses, so it is dead
        unlock();
        moveDepsToWorklist();
        _type=null;             // Flag as dead
        while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes
            Node old_def = _inputs.removeLast();
            // Revisit neighbor because removed use
            if( old_def != null ) {
                if( CODE.add(old_def).delUse(this) )
                    old_def.kill(); // If we removed the last use, the old def is now dead
                old_def.moveDepsToWorklist(); // Use-count changes can enable distant rewrites.
            }
        }
        assert isDead();        // Really dead now
    }

    // Preserve CFG use-ordering when killing
    public void killOrdered() {
        CFGNode cfg = cfg0();
        cfg._outputs.remove(cfg._outputs.find(this));
        _inputs.set(0,null);
        kill();
    }

    // Mostly used for asserts and printing.
    public boolean isDead() { return isUnused() && nIns()==0 && _type==null; }

    // Shortcuts to stop DCE mid-parse
    // Add bogus null use to keep node alive
    public <N extends Node> N keep() { return addUse(null); }
    // Remove bogus null.
    @SuppressWarnings("unchecked")
    public <N extends Node> N unkeep() {
        delUse(null);
        return (N)this;
    }
    // Test "keep" status
    public boolean iskeep() { return _outputs.find(null) != -1; }
    public void unkill() {
        if( unkeep().isUnused() )
            kill();
    }
    public void isKill() {
        if( isUnused() )
            kill();
    }

    // Replace self with nnn in the graph, making 'this' go dead
    public void subsume( Node nnn ) {
        assert nnn!=this;
        while( nOuts() > 0 ) {
            Node n = _outputs.removeLast();
            n.unlock();
            int idx = n._inputs.find(this);
            n._inputs.set(idx,nnn);
            nnn.addUse(n);
            CODE.add(n);
            CODE.addAll(n._outputs);
        }
        kill();
    }

    // insert `this` immediately after `def` in the same basic block.
    public void insertAfter( Node def ) {
        CFGNode cfg = def.cfg0();
        int i = cfg._outputs.find(def)+1;
        if( cfg instanceof CallEndNode ) {
            cfg = cfg.uctrl();  i=0;
        } else if( def.in(0) instanceof MultiNode ) {
            assert i==0;
            i = cfg._outputs.find(def.in(0))+1;
        }

        while( cfg.out(i) instanceof PhiNode || cfg.out(i) instanceof CalleeSaveNode )  i++;
        cfg._outputs.insert(this,i);
        _inputs.set(0,cfg);
    }

    // Insert this in front of use.in(uidx) with this, and insert this
    // immediately before use in the basic block.
    public void insertBefore( Node use, int uidx ) {
        CFGNode cfg = use.cfg0();
        int i;
        if( use instanceof PhiNode phi ) {
            cfg = phi.region().cfg(uidx);
            if( cfg instanceof CProjNode && cfg.in(0) instanceof NeverNode nvr )
                cfg = nvr.cfg0();
            i = cfg.nOuts()-1;
        } else {
            i = cfg._outputs.find(use);
        }
        cfg._outputs.insert(this,i);
        _inputs.set(0,cfg);
        if( _inputs._len > 1 && this instanceof SplitNode )
            setDefOrdered(1,use.in(uidx));
        use.setDefOrdered(uidx,this);
    }

    public void setDefOrdered( int idx, Node def) {
        // If old is dying, remove from CFG ordered
        Node old = in(idx);
        if( old!=null && old.nOuts()==1 ) {
            CFGNode cfg = old.cfg0();
            if( cfg!=null ) {
                cfg._outputs.remove(cfg._outputs.find(old));
                old._inputs.set(0,null);
            }
        }
        setDef(idx,def);
    }

    public void removeSplit() {
        CFGNode cfg = cfg0();
        cfg._outputs.remove(cfg._outputs.find(this));
        _inputs.set(0,null);
        if( _inputs._len > 1 ) subsume(in(1));
    }

    // ------------------------------------------------------------------------
    // Graph-based optimizations

    /**
     * Try to peephole at this node and return a better replacement Node.
     * Always returns some not-null Node (often this).
     */
    public final Node peephole( ) {
        var obs = CODE._midAssert ? null : CODE._obs;
        if( obs != null ) obs.before(this);
        Node n = peepholeOpt();
        Node rez = n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n);
        if( obs != null ) obs.after(this, n==null ? null : rez, false);
        return rez;             // Cannot return null for no-progress
    }

    /**
     * Try to peephole at this node and return a better replacement Node if
     * possible.  We compute a {@link Type} and then check and replace:
     * <ul>
     * <li>if the Type {@link Type#isConstant}, we replace with a {@link ConstantNode}</li>
     * <li>in a future chapter we will look for a
     * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a>
     * to eliminate.</li>
     * <li>we ask the Node for a better replacement.  The "better replacement"
     * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes
     * {@code (x+(1+2))}.  By canonicalizing expressions we fold common addressing
     * math constants, remove algebraic identities and generally simplify the
     * code. </li>
     *
     * Unlike peephole above, this explicitly returns null for no-change, or not-null
     * for a better replacement (which can be this).
     * </ul>
     */
    public final Node peepholeOpt( ) {
        CODE.iterCnt();
        // Compute initial or improved Type
        Type old = setType(compute());

        // Replace constant computations from non-constants with a constant node.
        if( !isConst() && !(this instanceof ParmNode parm && parm.inProgress()) &&
            _type.isHighOrConst() )
            return ConstantNode.make(_type).peephole();

        // Global Value Numbering
        if( _hash==0 ) {
            Node n = CODE._gvn.get(this); // Will set _hash as a side effect
            if( n==null )
                CODE._gvn.put(this,this);  // Put in table now
            else {
                // Because of random worklist ordering, the two equal nodes
                // might have different types.  Because of monotonicity, both
                // types are valid.  To preserve monotonicity, the resulting
                // shared Node has to have the best of both types.
                n.setType(n._type.join(_type));
                _hash = 0; // Clear, since it never went in the table
                return deadCodeElim(n);// Return previous; does Common Subexpression Elimination
            }
        }

        // Ask each node for a better replacement
        Node n = idealize();
        if( n != null )         // Something changed
            return n;           // Report progress

        if( old!=_type ) return this; // Report progress;
        CODE.iterNop();
        return null;            // No progress
    }

    // m is the new Node, self is the old.
    // Return 'm', which may have zero uses but is alive nonetheless.
    // If self has zero uses (and is not 'm'), {@link #kill} self.
    private Node deadCodeElim(Node m) {
        // If self is going dead and not being returned here (Nodes returned
        // from peephole commonly have no uses (yet)), then kill self.
        if( m != this && isUnused() && !isDead() ) {
            // Killing self - and since self recursively kills self's inputs we
            // might end up killing 'm', which we are returning as a live Node.
            // So we add a bogus extra null output edge to stop kill().
            m.keep();      // Keep m alive
            kill();        // Kill self because replacing with 'm'
            m.unkeep();    // Okay to peephole m
        }
        return m;
    }

    /**
     * This function needs to be
     * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
     * as it is part of a Monotone Analysis Framework.
     * <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">See for example this set of slides</a>.
     * <p>
     * For Chapter 2, all our Types are really integer constants, and so all
     * the needed properties are trivially true, and we can ignore the high
     * theory.  Much later on, this will become important and allow us to do
     * many fancy complex optimizations trivially... because theory.
     * <p>
     * {@link #compute()} needs to be stand-alone, and cannot recursively call compute
     * on its inputs, because programs are cyclic (have loops!) and this will just
     * infinitely recurse until stack overflow.  Instead, compute typically
     * computes a new type from the {@link #_type} field of its inputs.
     */
    public abstract Type compute();

    // Set the type.  Assert monotonic progress.
    // If changing, add users to worklist.
    public Type setType(Type type) {
        Type old = _type;
        assert old == null || type.isa(old) : "Monotonicity test failed: "+this+"#"+_nid+" old="+old+" new="+type;
        //assert !type.hasClosedBuilder0(); // New types should not have closed builders
        if( old == type ) return old;
        _type = type;       // Set _type late for easier assert debugging
        CODE.addAll(_outputs);
        moveDepsToWorklist();
        return old;
    }

    @SuppressWarnings("unchecked")
    public <N extends Node> N init() { _type = compute(); return (N)this; }

    /**
     * This function rewrites the current Node into a more "idealized" form.
     * This is the bulk of our peephole rewrite rules, and we use this to
     * e.g. turn arbitrary collections of adds and multiplies with mixed
     * constants into a normal form that's easy for hardware to implement.
     * Example: An array addressing expression:
     * <pre>   ary[idx+1]</pre>
     * might turn into Sea-of-Nodes IR:
     * <pre>   (ary+12)+((idx+1) * 4)</pre>
     * This expression can then be idealized into:
     * <pre>   ary + ((idx*4) + (12 + (1*4)))</pre>
     * And more folding:
     * <pre>   ary + ((idx<<2) + 16)</pre>
     * And during code-gen:
     * <pre>   MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation </pre>
     * <p>
     * {@link #idealize} has a very specific calling convention:
     * <ul>
     * <li>If NO change is made, return {@code null}
     * <li>If ANY change is made, return not-null; this can be {@code this}
     * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it.
     * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}.
     * </ul>
     * <p>
     * Examples:
     * <table border="3">
     * <tr><th>    before       </th><th>       after     </th><th>return </th><th>comment  </th></tr>
     * <tr><td>{@code (x+5)    }</td><td>{@code   (x+5)  }</td><td>{@code null  }</td><td>No change</td></tr>
     * <tr><td>{@code (5+x)    }</td><td>{@code   (x+5)  }</td><td>{@code this  }</td><td>Swapped arguments</td></tr>
     * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr>
     * </table>
     *
     * The last entry deserves more discussion.  The new Node {@code (1+2)}
     * created in {@link #idealize} calls {@link #peephole} (which then folds
     * into a constant).  The other new Node {@code (x+3)} does not call
     * peephole, because it is returned and peephole itself will recursively
     * call peephole.
     * <p>
     * Since idealize calls peephole and peephole calls idealize, you must be
     * careful that all idealizations are <em>monotonic</em>: all transforms
     * remove some feature, so that the set of available transforms always
     * shrinks.  If you don't, you risk an infinite peephole loop!
     *
     * @return Either a new or changed node, or null for no changes.
     */
    public abstract Node idealize();

    // Some of the peephole rules get complex, and search further afield than
    // just the nearest neighbor.  These peepholes can fail the pattern match
    // on a node some distance away, and if that node ever changes we should
    // retry the peephole.  Track a set of Nodes dependent on `this`, and
    // revisit them if `this` changes.
    Ary<Node> _deps;
    public int nDeps() { return _deps == null ? 0 : _deps.size(); }
    public Node dep(int idx) { return _deps.at(idx); }

    private boolean addDepImpl( Node dep ) {
        // Running peepholes during the big assert cannot have side effects
        // like adding dependencies.
        if( CODE._midAssert ) return false;
        if( CODE._obs != null ) CODE._obs.dep(this, dep);
        if( dep._deps==null ) dep._deps = new Ary<>(Node.class);
        if( dep._deps   .find(this) != -1 ) return false; // Already on list
        if( dep._outputs.find(this) != -1 ) return false;
        return true;
    }

    /**
     * Add a node to the list of dependencies.  Only add it if it's not an input
     * or output of this node, that is, it is at least one step away.  The node
     * being added must benefit from this node being peepholed.
     */
    public <N extends Node> N addDep( N dep ) {
        if( !addDepImpl(dep) ) return dep;
        if( dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors
        dep._deps.add(this);
        return dep;
    }

    public <N extends Node> N addDepForwards( N dep ) {
        if( !addDepImpl(dep) ) return dep;
        dep._deps.add(this);
        return dep;
    }

    // Move the dependents onto a worklist, and clear for future dependents.
    public void moveDepsToWorklist( ) { moveDepsToWorklist(CODE._iter); }
    public void moveDepsToWorklist( IterPeeps iter ) {
        if( _deps == null ) return;
        iter.addAll(_deps);
        _deps.clear();
    }

    // Two nodes are equal if they have the same inputs and the same "opcode"
    // which means the same Java class, plus same internal parts.
    @Override public final boolean equals( Object o ) {
        if( o==this ) return true;
        if( o.getClass() != getClass() ) return false;
        Node n = (Node)o;
        int len = _inputs.size();
        if( len != n._inputs.size() ) return false;
        for( int i=0; i<len; i++ )
            if( in(i) != n.in(i) )
                return false;
        return eq(n);
    }
    // Subclasses add extra checks (such as ConstantNodes have same constant),
    // and can assume "this!=n" and has the same Java class.
    public boolean eq( Node n ) { return true; }

    // Cached hash.  If zero, then not computed AND this Node is NOT in the GVN
    // table - and can have its edges hacked (which will change his hash
    // anyway).  If Non-Zero then this Node is IN the GVN table, or is being
    // probed to see if it can be inserted.  His edges are "locked", because
    // hacking his edges will change his hash.
    int _hash;

    // If the _hash is set, then the Node is in the GVN table; remove it.
    void unlock() {
        if( _hash==0 ) return;
        Node old = CODE._gvn.remove(this); // Pull from table
        assert old==this;
        _hash=0;                // Out of table now
    }

    // Hash of opcode and inputs
    @Override public final int hashCode() {
        if( _hash != 0 ) return _hash;
        int hash = hash();
        for( Node n : _inputs )
            if( n != null )
                hash = hash ^ (hash<<17) ^ (hash>>13) ^ n._nid;
        if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing
        return (_hash=hash);
    }
    // Subclasses add extra hash info (such as ConstantNodes constant)
    int hash() { return 0; }

    // ------------------------------------------------------------------------
    //

    /** Is this Node Memory related */
    public boolean isMem() { return false; }

    // ------------------------------------------------------------------------
    // Peephole utilities

    // Swap inputs without letting either input go dead during the swap.
    public Node swap12() {
        unlock();               // Hash is order dependent
        _inputs.swap(1,2);
        return this;
    }

    /**
     * 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<nIns(); i++ )
            if( !(in(i)._type.isConstant()) ) {
                dep.addDep(in(i)); // If in(i) becomes a constant later, will trigger some peephole
                return false;
            }
        return true;
    }

    // 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.
    // Does not need to be implemented in isCFG() nodes.
    Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); }

    public Node copy() { return copyEmpty(); }

    // Exact-class copy with fresh identity and no edges.  Unlike machine
    // rematerialization copies, this never registers or copies input edges.
    public final Node copyEmpty() {
        Node n;
        try { n = (Node)clone(); }
        catch( Exception e ) { throw new RuntimeException(e); }
        n._nid = CODE.getUID(); // allocate unique dense ID
        n._inputs  = new Ary<>(Node.class);
        n._outputs = new Ary<>(Node.class);
        n._deps = null;
        n._hash = 0;
        return n;
    }

    // Report any post-optimize errors
    public Parser.ParseException err() { return null; }

    // Common integer constants
    public static ConstantNode con(long x) { return (ConstantNode)ConstantNode.make(TypeInteger.constant(x)).peephole(); }

    // Utility to walk the entire graph applying a function; return the first
    // not-null result.
    final public <E> E walk( Function<Node,E> pred ) {
        assert CODE._visit.isEmpty();
        E rez = _walk(pred);
        CODE._visit.clear();
        return rez;
    }

    private <E> E _walk( Function<Node,E> pred ) {
        if( CODE._visit.get(_nid) ) return null; // Been there, done that
        CODE._visit.set(_nid);
        E x = pred.apply(this);
        if( x != null ) return x;
        for( Node def : _inputs  )  if( def != null && (x = def._walk(pred)) != null ) return x;
        for( Node use : _outputs )  if( use != null && (x = use._walk(pred)) != null ) return x;
        return null;
    }

    public void gather(HashMap<String,Integer> strs ) { }

    // If a Type upgrade happens, put on worklist
    boolean _upgradeType( HashMap<String,Type> TYPES ) { return false; }
    public final void upgradeType( HashMap<String,Type> TYPES ) {
        Type old = _type;  _type = _type.upgradeType(TYPES);
        boolean progress = _upgradeType(TYPES);
        if( progress || old != _type ) {
            CODE.add(this);
            CODE.addAll(_outputs);
            if( _deps!=null ) CODE.addAll(_deps);
        }
    }

    /**
     * Debugging utility to find a Node by index
     */
    public Node find(int nid) { return _find(nid, new BitSet()); }
    private Node _find(int nid, BitSet bs) {
        if( bs.get(_nid) ) return null; // Been there, done that
        bs.set(_nid);
        if( _nid==nid ) return this;
        Node x;
        for( Node def : _inputs  )  if( def != null && (x = def._find(nid,bs)) != null ) return x;
        for( Node use : _outputs )  if( use != null && (x = use._find(nid,bs)) != null ) return x;
        return null;
    }
}