diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
11 files changed, 77 insertions, 51 deletions
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..caa7ff44 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,11 @@ 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, long workListSeed, boolean reset ) { CODE = this; + if( reset ) Type.reset(); + _main = makeFun(TypeFunPtr.MAIN); _phase = null; _callingConv = null; _start = new StartNode(arg); @@ -119,18 +122,15 @@ public class CodeGen { // are structurally equal. public final HashMap<Node,Node> _gvn = new HashMap<>(); - // Compute "function indices": FIDX. - // Each new request at the same signature gets a new FIDX. - private final HashMap<TypeTuple,Integer> 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<<fidx ); + return fun.makeFrom(fidx); } // Signature for MAIN - public final TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM); + public final TypeFunPtr _main; // Reverse from a constant function pointer to the IR function being called public FunNode link( TypeFunPtr tfp ) { assert tfp.isConstant(); @@ -186,24 +186,44 @@ public class CodeGen { // Pessimistic peephole optimization on a worklist _iter.iterate(this); + // OPTIMISTIC PASS GOES HERE + // Not really a true optimistic pass, but look for unlinked functions. // This can be removed, which may trigger another round of pessimistic. // This is the point where we flip from a virtual Call Graph (any call // can call any function) to having a correct (but conservative) CG. + int progress = 0; + while( progress != _start.nOuts() ) { + progress = _start.nOuts(); + FunNode main = link(_main); + for( int i=0; i<_start.nOuts(); i++ ) { + Node use = _start.out(i); + if( use instanceof FunNode fun && + fun.nIns()==2 && fun.in(1)==_start && fun != main && + (fun._name==null || fun._name.startsWith("sys.")) ) { + add(fun).setDef(1,Parser.XCTRL); + addAll(fun._outputs); + i--; + } + } + _iter.iterate(this); + } - FunNode main = link(_main); + // Freeze field sizes; do struct layouts; convert field offsets into + // constants. for( int i=0; i<_start.nOuts(); i++ ) { Node use = _start.out(i); - if( use instanceof FunNode fun && - fun.nIns()==2 && fun.in(1)==_start && fun != main && - (fun._name==null || fun._name.startsWith("sys.")) ) { - add(fun).setDef(1,Parser.XCTRL); - addAll(fun._outputs); + if( use instanceof ConFldOffNode off ) { + TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name); + off.subsume( off.asOffset(tmp._obj) ); i--; } } _iter.iterate(this); + // To help with testing, sort StopNode returns by NID + Arrays.sort(_stop._inputs._es,0,_stop.nIns(),(x,y) -> x._nid - y._nid ); + _tOpto = (int)(System.currentTimeMillis() - t0); // TODO: @@ -212,7 +232,7 @@ public class CodeGen { // loop unroll, peel, RCE, etc return this; } - public <N extends Node> N add( N n ) { return (N)_iter.add(n); } + public <N extends Node> N add( N n ) { return _iter.add(n); } public void addAll( Ary<Node> 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<<log; } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 04a119c2..520a18a3 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.IterPeeps.WorkList; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; import java.util.*; public abstract class GlobalCodeMotion { diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index fdd4e2f9..6dd6fbf1 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.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/LRG.java b/src/main/java/com/seaofnodes/simple/codegen/LRG.java index ec254a2e..009ddcdb 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/LRG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/LRG.java @@ -1,10 +1,9 @@ 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.util.Ary; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; import java.util.IdentityHashMap; /** A Live Range diff --git a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java index e1e849e6..2415203d 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java +++ b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.util.Utils; // In-memory linking public class LinkMem { diff --git a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index de4fadc4..ddf5a679 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.IterPeeps.WorkList; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; import java.util.*; public abstract class ListScheduler { diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 57d0d90c..da521082 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.node.*; import java.util.Arrays; import java.util.BitSet; @@ -398,8 +398,8 @@ public class RegAlloc { // If the minLoopDepth is less than the maxLoopDepth: for-all defs and // uses, if at minLoopDepth or lower, split after def and before use. for( Node n : _ns ) { - if( n instanceof SplitNode ) continue; // Ignoring splits; since spilling need to split in a deeper loop - if( n.isDead() ) continue; // Some Clonable went dead by other spill changes + if( n instanceof SplitNode && min!=max ) continue; // Ignoring splits; since spilling need to split in a deeper loop + if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes // If this is a 2-address commutable op (e.g. AddX86, MulX86) and the rhs has only a single user, // commute the inputs... which chops the LHS live ranges' upper bound to just the RHS. if( n instanceof MachNode mach && lrg(n)==lrg && mach.twoAddress()==1 && mach.commutes() && n.in(2).nOuts()==1 ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index ec0c4e30..c7dda1da 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.Utils; /** RegMask * A "register mask" - 1 bit set for each allowed register. In addition, |