diff options
Diffstat (limited to 'chapter31/src/main/java')
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; |
