From fe08995cca0196850855c0f81619d264cf66b716 Mon Sep 17 00:00:00 2001 From: Darrick Wiebe Date: Sun, 30 Mar 2025 15:33:43 -0400 Subject: Make RegMaskRW public and add mutating or; Fix coelesce bug (#186) * Make RegMaskRW public and add union to it. * Rename union to or * Split popular non-constant * Fix coelesce bug --------- Co-authored-by: Cliff Click --- .../com/seaofnodes/simple/codegen/Coalesce.java | 6 ++--- .../java/com/seaofnodes/simple/codegen/LRG.java | 4 ++- .../com/seaofnodes/simple/codegen/RegAlloc.java | 2 +- .../com/seaofnodes/simple/codegen/RegMask.java | 22 --------------- .../com/seaofnodes/simple/codegen/RegMaskRW.java | 31 ++++++++++++++++++++++ .../seaofnodes/simple/node/cpus/riscv/RetRISC.java | 2 +- 6 files changed, 39 insertions(+), 28 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java (limited to 'chapter21/src') diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java index 89dde46f..255e4e5e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -37,7 +37,7 @@ abstract public class Coalesce { if( v1 != v2 ) { LRG ov1 = v1, ov2 = v2; // Get the smaller neighbor count in v1 - if( (v1._adj==null ? 0 : v1._adj._len) > (v2._adj==null ? 0 : v2._adj._len) ) + if( v1.nadj() > v2.nadj() ) { v1 = v2; v2 = alloc.lrg(n); } int v2len = v2._adj==null ? 0 : v2._adj._len; // See that they do not conflict (coalescing would make a self-conflict) @@ -58,9 +58,9 @@ abstract public class Coalesce { // Most constrained mask RegMask mask = v1._mask==v2._mask ? v1._mask : v1._mask.copy().and(v2._mask); // Check for capacity - if( v2._adj!=null && v2._adj._len >= mask.size() ) { + if( v2.nadj() >= mask.size() ) { // Fails capacity, will not be trivial colorable - v2._adj.setLen(v2len); + if( v2._adj!=null ) v2._adj.setLen(v2len); continue; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java index db5a3242..2e56e050 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java @@ -62,6 +62,8 @@ public class LRG { // Adjacent Live Range neighbors. Only valid during coloring Ary _adj; + public int nadj() { return _adj==null ? 0 : _adj._len; } + void addNeighbor(LRG lrg) { if( _adj==null ) _adj = new Ary<>(LRG.class); _adj.push(lrg); @@ -80,7 +82,7 @@ public class LRG { } // More registers than neighbors - boolean lowDegree() { return (_adj==null ? 0 : _adj._len) < _mask.size(); } + boolean lowDegree() { return nadj() < _mask.size(); } LRG( short lrg ) { _lrg = lrg; _reg = -1; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 9c0f5f51..ceb75d64 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -288,7 +288,7 @@ public class RegAlloc { // all uses by class to split for( int j=0; j < def._outputs._len; j++ ) { Node use = def._outputs.at(j); - if( use instanceof MachNode mach ) { + if( use instanceof MachNode mach && use!=split ) { // Check all use inputs for n, in case there's several for( int i = 1; i < use.nIns(); i++ ) // Find a def input, and check register class diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index df53c7ca..88ce8627 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -119,25 +119,3 @@ public class RegMask { } } -// Mutable regmask(writable) -class RegMaskRW extends RegMask { - public RegMaskRW(long x, long y) { super(x,y); } - // clears bit at position r. Returns true if the mask is still not empty. - public boolean clr(int r) { - if( r < 64 ) _bits0 &= ~(1L<<(r )); - else _bits1 &= ~(1L<<(r-64)); - return _bits0!=0 || _bits1!=0; - } - @Override RegMaskRW and( RegMask mask ) { - if( mask==null ) return this; - _bits0 &= mask._bits0; - _bits1 &= mask._bits1; - return this; - } - @Override RegMaskRW sub( RegMask mask ) { - if( mask==null ) return this; - _bits0 &= ~mask._bits0; - _bits1 &= ~mask._bits1; - return this; - } -} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java new file mode 100644 index 00000000..6fa5344f --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java @@ -0,0 +1,31 @@ +package com.seaofnodes.simple.codegen; + +// Mutable regmask(writable) +public class RegMaskRW extends RegMask { + public RegMaskRW(long x, long y) { super(x,y); } + // clears bit at position r. Returns true if the mask is still not empty. + public boolean clr(int r) { + if( r < 64 ) _bits0 &= ~(1L<<(r )); + else _bits1 &= ~(1L<<(r-64)); + return _bits0!=0 || _bits1!=0; + } + @Override RegMaskRW and( RegMask mask ) { + if( mask==null ) return this; + _bits0 &= mask._bits0; + _bits1 &= mask._bits1; + return this; + } + @Override RegMaskRW sub( RegMask mask ) { + if( mask==null ) return this; + _bits0 &= ~mask._bits0; + _bits1 &= ~mask._bits1; + return this; + } + public RegMaskRW or( RegMask mask ) { + if( mask!=null ) { + _bits0 |= mask._bits0; + _bits1 |= mask._bits1; + } + return this; + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java index e04d3691..87927242 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java @@ -41,7 +41,7 @@ public class RetRISC extends ReturnNode implements MachNode { // Prints return reg (either A0 or FA0), RPC (always R1) and then // the callee-save registers. for( int i=2; i