summaryrefslogtreecommitdiff
path: root/chapter31/src/main/java/com
diff options
context:
space:
mode:
Diffstat (limited to 'chapter31/src/main/java/com')
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java10
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java2
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java12
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/ModFNode.java49
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/ModNode.java16
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/Node.java3
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/ModARM.java29
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java3
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java17
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java1
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java7
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java36
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java28
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/parser/Construction.java3
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/parser/Expressions.java4
-rw-r--r--chapter31/src/main/java/com/seaofnodes/simple/parser/Lexer.java4
16 files changed, 199 insertions, 25 deletions
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter31/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index 86cb2e98..83c0677d 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
@@ -141,10 +141,11 @@ public abstract class GlobalCodeMotion {
if( def!=null && !(def instanceof PhiNode) )
_schedEarly(def,code,start);
- // An existing edge 0 already supplies control (or a Phi/Proj binding).
- if( n.in(0)==null ) {
+ // A memory op's control is a lower bound, not a complete early schedule:
+ // instruction selection may have folded in an operand defined later.
+ if( n.in(0)==null || n instanceof MemOpNode ) {
// Schedule at deepest input
- CFGNode early = start; // Maximally early, lowest idepth
+ CFGNode early = n.in(0) instanceof CFGNode ctrl ? ctrl : start;
for( int i=1; i<n.nIns(); i++ )
if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() )
early = n.in(i).cfg0(); // Latest/deepest input
@@ -251,6 +252,9 @@ public abstract class GlobalCodeMotion {
if( use != null )
lca = use_block(n,use, late).domLCA(lca,null);
+ assert lca!=null && early.dominates(lca,null) :
+ "Early schedule must dominate uses of "+n.getClass().getSimpleName()+"#"+n._nid;
+
// Loads may need anti-dependencies, raising their LCA
if( n instanceof MemOpNode load && load._isLoad )
lca = find_anti_dep(lca,load,early,late,anti, antideps);
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/chapter31/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
index c3b603e5..f90d8d4e 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
@@ -49,7 +49,7 @@ public abstract class ListScheduler {
else
computeSingleRDef(bb,n);
- if( n instanceof NewNode || n instanceof CallNode )
+ if( n instanceof NewNode || n instanceof CallNode || n instanceof ModFNode )
bb.fun()._hasCalls = true;
return this;
}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter31/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 1b335c50..303fd355 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -184,6 +184,7 @@ public class RegAlloc {
if( bb instanceof CallEndMach cend ) cend.cacheRegs(_code);
for( Node n : bb._outputs )
if( n instanceof NewNode nnn ) nnn.cacheRegs(_code);
+ else if( n instanceof ModFNode mod ) mod.cacheRegs(_code);
}
// Expensive assert: useful when chasing cross-function allocator edges.
//assert verifyFunctionLocalEdges();
@@ -680,7 +681,14 @@ public class RegAlloc {
if( cfg==def.cfg0() && def.nOuts()==1 && !singleReg )
return;
}
- makeSplit(def,kind,round,lrg,umask).insertBefore(n, i);
+ // If isolating a loop Phi's uses did not relieve pressure, cloning its
+ // constant input again cannot help: it still forces the Phi into a GPR.
+ // A real transfer on this retry lets the Phi live on the stack.
+ Node split = n instanceof PhiNode phi && phi.region() instanceof LoopNode &&
+ lrg._machUse instanceof SplitNode prior && prior._round<round &&
+ !lrg._mask.isEmpty() && def instanceof MachNode mach && mach.isClone()
+ ? makeSplit(kind,round,lrg) : makeSplit(def,kind,round,lrg,umask);
+ split.insertBefore(n, i);
// Keep the def-side transfer: a kill between the two copies may be
// exactly why this range split. Coalescing can join them when safe.
}
@@ -742,6 +750,8 @@ public class RegAlloc {
// Raise frame size by max stack args passed to New
if( n instanceof NewNode nnn )
maxReg = Math.max(maxReg,nnn._xslot);
+ if( n instanceof ModFNode mod )
+ maxReg = Math.max(maxReg,mod._xslot);
if( !(n instanceof SplitNode ) ) continue;
int defreg = lrg(n )._reg;
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/ModFNode.java b/chapter31/src/main/java/com/seaofnodes/simple/node/ModFNode.java
new file mode 100644
index 00000000..17d7e36c
--- /dev/null
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/ModFNode.java
@@ -0,0 +1,49 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.isa.Arm64;
+import com.seaofnodes.isa.RiscV;
+import com.seaofnodes.isa.X86;
+import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.cpus.arm.arm;
+import com.seaofnodes.simple.node.cpus.riscv.riscv;
+import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.SB;
+
+/** Floating remainder has no SSE/ARM/RISC-V instruction: emit a helper call. */
+public class ModFNode extends MachConcreteNode implements MachNode {
+ private RegMask _lhs, _rhs, _ret, _kills;
+ public int _xslot;
+ public ModFNode(ModNode mod) { super(mod); }
+ @Override public String op() { return "modf"; }
+ public void cacheRegs(CodeGen code) {
+ TypeFunPtr sig=TypeFunPtr.make(false,new Type[]{TypeFloat.F64,TypeFloat.F64},TypeFloat.F64);
+ _lhs=code._mach.callArgMask(sig,2,0,code._cCallingConv);
+ _rhs=code._mach.callArgMask(sig,3,0,code._cCallingConv);
+ _ret=code._mach.retMask(sig);
+ RegMaskRW kills=code._cCallerSave.copy();
+ if( code._mach instanceof arm ) kills.set(arm.FLAGS);
+ int base=code._mach.regs().length+cfg0().fun()._maxArgSlot;
+ _xslot=base+code._mach.maxArgSlot(sig,code._cCallingConv);
+ for( int i=base; i<_xslot; i++ ) kills.set(i);
+ _kills=kills;
+ }
+ @Override public RegMask regmap(int i) { return i==1 ? _lhs : i==2 ? _rhs : null; }
+ @Override public RegMask outregmap() { return _ret; }
+ @Override public RegMask killmap() { return _kills; }
+ @Override public void encoding(Encoding enc) {
+ enc.external(this,"simple_f64_mod");
+ switch( machine().name() ) {
+ case "x86_64_v2" -> X86.call(enc);
+ case "arm" -> enc.add4(Arm64.b(Arm64.OP_CALL,0));
+ case "riscv" -> {
+ enc.add4(RiscV.u_type(RiscV.OP_AUIPC,riscv.T0,0));
+ enc.add4(RiscV.i_type(RiscV.OP_JALR,riscv.RPC,0,riscv.T0,0));
+ }
+ default -> throw new IllegalStateException(machine().name());
+ }
+ }
+ @Override public void asm(CodeGen code, SB sb) {
+ sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" % ").p(code.reg(in(2)));
+ }
+ @Override public String comment() { return "call simple_f64_mod"; }
+}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/ModNode.java b/chapter31/src/main/java/com/seaofnodes/simple/node/ModNode.java
new file mode 100644
index 00000000..7c1a9238
--- /dev/null
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/ModNode.java
@@ -0,0 +1,16 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.TypeInteger;
+
+public class ModNode extends ArithNode {
+ public ModNode(Node lhs, Node rhs) { super(null,lhs,rhs); }
+ public ModNode(Node lhs, Node rhs, byte mode) { super(null,lhs,rhs,mode); }
+ @Override public Tag serialTag() { return Tag.Mod; }
+ @Override public String op() { return "%"; }
+ @Override boolean allowFloat() { return true; }
+
+ @Override long doOp(long x, long y) { return y==0 ? 0 : x%y; }
+ @Override double doOp(double x, double y) { return x%y; }
+ @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { return TypeInteger.BOT; }
+ @Override Node copy(Node lhs, Node rhs) { return new ModNode(lhs,rhs,_mode); }
+}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter31/src/main/java/com/seaofnodes/simple/node/Node.java
index d4c0794c..ad4f47e0 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -77,7 +77,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
New,Never,Not,Or,Parm,Phi,Proj,PtrToInt,
ReadOnly,Return,Region,RoundF32,
Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub,
- ToInteger,ToFloat,XCtrl,Xor,F64Bits,F64FromBits;
+ ToInteger,ToFloat,XCtrl,Xor,F64Bits,F64FromBits,Mod;
public static final Tag[] VALS = values();
public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) {
return switch(this) {
@@ -117,6 +117,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
case Call -> CallNode.make(bais,strs);
case CallEnd-> CallEndNode.make(bais ,types);
case CLInit -> new CLInitNode(bais,strs);
+ case Mod -> new ModNode(null,null,(byte)bais.packed1());
case CProj -> CProjNode.make(bais,strs);
case Con -> ConstantNode.make(bais ,types);
case Escape-> EscapeNode.make(bais ,types);
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/ModARM.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/ModARM.java
new file mode 100644
index 00000000..bd29ba3f
--- /dev/null
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/ModARM.java
@@ -0,0 +1,29 @@
+package com.seaofnodes.simple.node.cpus.arm;
+
+import com.seaofnodes.isa.Arm64;
+import com.seaofnodes.simple.codegen.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.util.SB;
+
+public class ModARM extends MachConcreteNode implements MachNode {
+ private static final RegMask REGS=new RegMask(arm.WR_BITS & ~(1L<<arm.X16));
+ ModARM(Node mod) { super(mod); }
+ @Override public String op() { return "mod"; }
+ @Override public RegMask regmap(int i) { return REGS; }
+ @Override public RegMask outregmap() { return REGS; }
+ @Override public RegMask killmap() { return new RegMask(1L<<arm.X16,1L); }
+ @Override public void encoding(Encoding enc) {
+ int lhs=enc.reg(in(1)), rhs=enc.reg(in(2)), dst=enc.reg(this);
+ enc.add4(Arm64.imm_inst(Arm64.OPI_CMP,0,rhs,31)); // CMP rhs,0
+ enc.add4(Arm64.b_cond(Arm64.OP_BRANCH,20,Arm64.COND.EQ));
+ enc.add4(Arm64.madd(Arm64.OP_DIV,rhs,3,lhs,arm.X16)); // SDIV x16,lhs,rhs
+ enc.add4(Arm64.madd(Arm64.OP_MUL,rhs,31,arm.X16,arm.X16)); // MUL x16,x16,rhs
+ enc.add4(Arm64.r_reg(Arm64.OP_SUB,0,arm.X16,0,lhs,dst)); // SUB dst,lhs,x16
+ enc.add4(Arm64.b(Arm64.OP_UJMP,8));
+ enc.add4(Arm64.mov(Arm64.OP_MOVZ,0,0,dst));
+ }
+ @Override public void asm(CodeGen code, SB sb) {
+ sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" % ").p(code.reg(in(2)));
+ }
+ @Override public String comment() { return "SDIV/MUL/SUB; kill x16, flags; zero guarded"; }
+}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
index 2d47edf5..55a9cdb0 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
@@ -28,7 +28,7 @@ public class arm extends Machine {
public static final int D16 = 48, D17 = 49, D18 = 50, D19 = 51, D20 = 52, D21 = 53, D22 = 54, D23 = 55;
public static final int D24 = 56, D25 = 57, D26 = 58, D27 = 59, D28 = 60, D29 = 61, D30 = 62, D31 = 63;
- static final int FLAGS = 64;
+ public static final int FLAGS = 64;
static final int MAX_REG = 65;
public static final int D_OFFSET = 32;
@@ -318,6 +318,7 @@ public class arm extends Machine {
case CProjNode c -> new CProjNode(c);
case ConstantNode con-> con(con);
case DivNode div -> div.mode()==2 ? new DivFARM(div) : new DivARM(div);
+ case ModNode mod -> mod.mode()==2 ? new ModFNode(mod) : new ModARM(mod);
case EscapeNode esc -> new EscapeNode(esc);
case FunNode fun -> new FunARM(fun);
case FunPtrNode fptr -> fptr(fptr);
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java
index 515ffa47..691979ec 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java
@@ -1,17 +1,26 @@
package com.seaofnodes.simple.node.cpus.riscv;
+import com.seaofnodes.isa.RiscV;
import com.seaofnodes.simple.util.SB;
import com.seaofnodes.simple.codegen.*;
import com.seaofnodes.simple.node.*;
public class DivRISC extends MachConcreteNode implements MachNode{
- public DivRISC(Node div) {super(div);}
- @Override public String op() { return "div"; }
+ private final boolean _mod;
+ public DivRISC(Node div) {super(div); _mod=div instanceof ModNode;}
+ @Override public String op() { return _mod ? "mod" : "div"; }
@Override public RegMask regmap(int i) { return riscv.RMASK; }
@Override public RegMask outregmap() { return riscv.WMASK; }
- @Override public void encoding( Encoding enc ) { riscv.r_type(enc,this,4,1); }
+ @Override public void encoding( Encoding enc ) {
+ // RISC-V returns -1 for DIV by zero, and the dividend for REM by zero.
+ // Both ideal operations instead return zero.
+ enc.add4(RiscV.b_type(RiscV.OP_BRANCH,1,enc.reg(in(2)),(short)riscv.ZERO,12));
+ enc.add4(RiscV.i_type(RiscV.OP_IMM,enc.reg(this),0,riscv.ZERO,0));
+ enc.add4(RiscV.j_type(RiscV.OP_JAL,riscv.ZERO,8));
+ riscv.r_type(enc,this,_mod ? 6 : 4,1);
+ }
@Override public void asm(CodeGen code, SB sb) {
- sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" / ").p(code.reg(in(2)));
+ sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(_mod ? " % " : " / ").p(code.reg(in(2)));
}
}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
index 976d1a52..70585732 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java
@@ -222,6 +222,7 @@ public class riscv extends Machine {
case CProjNode c -> new CProjNode(c);
case ConstantNode con -> con(con);
case DivNode div -> div.mode()==2 ? new DivFRISC(div) : new DivRISC(div);
+ case ModNode mod -> mod.mode()==2 ? new ModFNode(mod) : new DivRISC(mod);
case EscapeNode esc -> new EscapeNode(esc);
case FunNode fun -> new FunRISC(fun);
case FunPtrNode fptr -> fptr(fptr);
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java
index 7faea17b..f8e652df 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java
@@ -7,6 +7,12 @@ import com.seaofnodes.simple.util.SB;
public class CmpX86 extends MachConcreteNode implements MachNode {
CmpX86( Node add ) { super(add); }
+ private CmpX86(CmpX86 cmp) {
+ super((Node)null);
+ addDef(null);
+ addDef(cmp.in(1));
+ addDef(cmp.in(2));
+ }
@Override public String op() { return "cmp"; }
@Override public RegMask regmap(int i) { return x86_64_v2.RMASK; }
@Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; }
@@ -16,6 +22,7 @@ public class CmpX86 extends MachConcreteNode implements MachNode {
// compared to some normal registers - and those normal registers might not
// be spilling!
@Override public boolean isClone() { return true; }
+ @Override public Node copy() { return new CmpX86(this); }
@Override public void encoding( Encoding enc ) {
X86.reg(enc,0x3B,enc.reg(in(1)),enc.reg(in(2)));
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java
index 9f375a80..7607913f 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java
@@ -6,20 +6,42 @@ import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.util.SB;
public class DivX86 extends MachConcreteNode implements MachNode {
- DivX86( Node div ) { super(div); }
- @Override public String op() { return "div"; }
+ private final boolean _mod;
+ DivX86( Node div ) { super(div); _mod=div instanceof ModNode; }
+ @Override public String op() { return _mod ? "mod" : "div"; }
@Override public RegMask regmap(int i) {
return (i==1) ? x86_64_v2.RAX_MASK : x86_64_v2.DIV_MASK;
}
- @Override public RegMask outregmap() { return x86_64_v2.RAX_MASK; }
- @Override public RegMask killmap() { return x86_64_v2.RDX_MASK; }
+ @Override public RegMask outregmap() { return _mod ? x86_64_v2.RDX_MASK : x86_64_v2.RAX_MASK; }
+ @Override public RegMask killmap() {
+ return new RegMask((1L<<(_mod ? x86_64_v2.RAX : x86_64_v2.RDX)) | (1L<<x86_64_v2.FLAGS));
+ }
@Override public void encoding( Encoding enc ) {
- X86.divide(enc,enc.reg(in(2)));
+ int rhs=enc.reg(in(2)), dst=enc.reg(this);
+ // IDIV faults on zero and MIN_VALUE/-1. Handle both before issuing it.
+ X86.reg(enc,0x85,rhs,rhs); // TEST rhs,rhs
+ enc.add1(0x0F).add1(0x84);
+ int zero=enc._bits.size(); enc.add4(0); // JZ zero
+ X86.imm(enc,0x81,7,rhs,-1); // CMP rhs,-1
+ enc.add1(0x0F).add1(0x85);
+ int divide=enc._bits.size(); enc.add4(0); // JNE divide
+ if( _mod ) X86.reg(enc,0x33,dst,dst);
+ else X86.unary(enc,0xF7,3,dst); // NEG wraps MIN_VALUE, like ideal division.
+ enc.add1(0xE9);
+ int minusOne=enc._bits.size(); enc.add4(0); // JMP done
+ enc.patch4(divide,enc._bits.size()-divide-4);
+ X86.divide(enc,rhs);
+ enc.add1(0xE9);
+ int done=enc._bits.size(); enc.add4(0); // JMP done
+ enc.patch4(zero,enc._bits.size()-zero-4);
+ X86.reg(enc,0x33,dst,dst);
+ enc.patch4(minusOne,enc._bits.size()-minusOne-4);
+ enc.patch4(done,enc._bits.size()-done-4);
}
// General form: "div dst /= src"
@Override public void asm(CodeGen code, SB sb) {
- sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" / ").p(code.reg(in(2)));
+ sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(_mod ? " % " : " / ").p(code.reg(in(2)));
}
- @Override public String comment() { return "kill rdx"; }
+ @Override public String comment() { return (_mod ? "kill rax" : "kill rdx")+", flags; zero and -1 guarded"; }
}
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
index dc15b185..d4714953 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
@@ -4,6 +4,8 @@ import com.seaofnodes.simple.codegen.*;
import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.type.*;
import com.seaofnodes.simple.util.Utils;
+import com.seaofnodes.simple.util.Ary;
+import java.util.IdentityHashMap;
public class x86_64_v2 extends Machine {
public x86_64_v2( CodeGen code ) {}
@@ -305,6 +307,7 @@ public class x86_64_v2 extends Machine {
case GuardNode guard -> new GuardMach(guard);
case ConstantNode con -> con(con);
case DivNode div -> div.mode()==2 ? new DivFX86(div) : new DivX86(div);
+ case ModNode mod -> mod.mode()==2 ? new ModFNode(mod) : new DivX86(mod);
case EscapeNode esc -> new EscapeNode(esc);
case FunNode fun -> new FunX86(fun);
case FunPtrNode fptr -> fptr(fptr);
@@ -354,7 +357,7 @@ public class x86_64_v2 extends Machine {
return new AddFX86(add);
Node lhs = add.in(1);
Node rhs = add.in(2);
- if( lhs instanceof LoadNode ld && ld.nOuts() == 1 && ld.declaredType().log_size() >= 3)
+ if( lhs instanceof LoadNode ld && ld.declaredType().log_size() >= 3 && canFoldLoad(ld,rhs) )
return new AddMemX86(add, address(ld), ld.ptr(), idx, off, scale, 0, rhs);
// Attempt a full LEA-style break down.
// Returns one of AddX86, AddIX86, LeaX86, or LHS
@@ -430,11 +433,11 @@ public class x86_64_v2 extends Machine {
// Since cmp does not record a BOP, SetX/Jmp need to know if the CMP is swapped.
// Vs memory
- if( lhs instanceof LoadNode ld && ld.nOuts() == 1 && rhs._type.isa(ld.declaredType()) )
+ if( lhs instanceof LoadNode ld && rhs._type.isa(ld.declaredType()) && canFoldLoad(ld,rhs) )
return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(rhs), val, false);
// Operands swap in the encoding directly, no need for Set/Jmp to swap `bop`
- if( rhs instanceof LoadNode ld && ld.nOuts() == 1 && lhs._type.isa(ld.declaredType()) &&
+ if( rhs instanceof LoadNode ld && lhs._type.isa(ld.declaredType()) && canFoldLoad(ld,lhs) &&
(!(lhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value())) ||
bool.op()=="==" || bool.op()=="!=") )
return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(lhs), val, true );
@@ -451,6 +454,25 @@ public class x86_64_v2 extends Machine {
return new CmpX86(bool);
}
+ // The other operand must not depend on a writer which must follow this
+ // load. Fusing them would move the read across that write (or form a
+ // scheduling cycle). Control dependencies count too, including calls.
+ private static boolean canFoldLoad(LoadNode load, Node value) {
+ if( load.nOuts()!=1 ) return false;
+ Ary<Node> writers=load.antiDeps(new Ary<>(Node.class));
+ if( writers.isEmpty() ) return true;
+ var seen=new IdentityHashMap<Node,Boolean>();
+ Ary<Node> work=new Ary<>(Node.class);
+ work.push(value);
+ while( !work.isEmpty() ) {
+ Node n=work.pop();
+ if( seen.put(n,Boolean.TRUE)!=null ) continue;
+ if( writers.find(n)!=-1 ) return false;
+ for( Node def : n._inputs ) if( def!=null ) work.push(def);
+ }
+ return true;
+ }
+
private Node con( ConstantNode con ) {
if( !con._con.isConstant() )
return ConstantNode.raw(con); // Default unknown caller inputs
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/parser/Construction.java b/chapter31/src/main/java/com/seaofnodes/simple/parser/Construction.java
index 6dec8ac1..7797cae4 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/parser/Construction.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/parser/Construction.java
@@ -56,7 +56,8 @@ import com.seaofnodes.simple.util.Ary;
* binding denotes the allocator. Private-memory Parms therefore need no
* fictitious external default or constructor-specific transfer function.
* InitView and Construct are erased by the existing TypeCheck walk. There is
- * no extra construction pass; see docs/construction-groups.md.
+ * no extra construction pass; see chapter29/docs/construction-groups.md
+ * from the repository root, and chapter29/README.md for the introduction.
*/
final class Construction {
private final Parser P;
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/parser/Expressions.java b/chapter31/src/main/java/com/seaofnodes/simple/parser/Expressions.java
index 6486aba8..ffc96f57 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/parser/Expressions.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/parser/Expressions.java
@@ -233,7 +233,7 @@ final class Expressions {
* Parse an multiplicativeExpr expression
*
* <pre>
- * multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+ * multiplicativeExpr : unaryExpr (('*' | '/' | '%') unaryExpr)*
* </pre>
* @return a multiply expression {@link Node}, never {@code null}
*/
@@ -242,6 +242,7 @@ final class Expressions {
while( true ) {
if( P.match("*") ) lhs = new MulNode(lhs,null);
else if( P.match("/") ) lhs = new DivNode(lhs,null);
+ else if( P.match("%") ) lhs = new ModNode(lhs,null);
else break;
lhs.setDef(2,parseUnary());
lhs = P.peep(lhs);
@@ -341,6 +342,7 @@ final class Expressions {
case '-' -> new SubNode(lhs,rhs);
case '*' -> new MulNode(lhs,rhs);
case '/' -> new DivNode(lhs,rhs);
+ case '%' -> new ModNode(lhs,rhs);
case '|' -> new OrNode(null,lhs,rhs);
case '&' -> new AndNode(null,lhs,rhs);
case '^' -> new XorNode(P.loc(),lhs,rhs);
diff --git a/chapter31/src/main/java/com/seaofnodes/simple/parser/Lexer.java b/chapter31/src/main/java/com/seaofnodes/simple/parser/Lexer.java
index 62dd054e..8633f2be 100644
--- a/chapter31/src/main/java/com/seaofnodes/simple/parser/Lexer.java
+++ b/chapter31/src/main/java/com/seaofnodes/simple/parser/Lexer.java
@@ -325,7 +325,7 @@ public class Lexer {
//
private boolean isPunctuation(char ch) {
- return "=;[]<>()+-/*&|^".indexOf(ch) != -1;
+ return "=;[]<>()+-/*%&|^".indexOf(ch) != -1;
}
private String parsePunctuation() {
@@ -350,7 +350,7 @@ public class Lexer {
if( match(">>=" ) ) return SAR;
if( _position+2 >= _input.length ) return 0;
char ch0 = (char)_input[_position];
- if( "+-/*&|^".indexOf(ch0) == -1 ) return 0;
+ if( "+-/*%&|^".indexOf(ch0) == -1 ) return 0;
char ch1 = (char)_input[_position+1];
if( ch1 == '=' ) { _position += 2; return ch0; }
if( isIdLetter((char)_input[_position+2]) ) return 0;