From f0a6c6757a795b8e186de0076836a87acef59fa7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 15 Nov 2026 11:20:40 -0800 Subject: Graphics now allow resize Reorganize docs. Fix bugs X86 LOad+cmp scheduling. Math intrinsics --- .../simple/codegen/GlobalCodeMotion.java | 10 +++-- .../seaofnodes/simple/codegen/ListScheduler.java | 2 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 12 +++++- .../java/com/seaofnodes/simple/node/ModFNode.java | 49 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/node/ModNode.java | 16 +++++++ .../main/java/com/seaofnodes/simple/node/Node.java | 3 +- .../seaofnodes/simple/node/cpus/arm/ModARM.java | 29 +++++++++++++ .../com/seaofnodes/simple/node/cpus/arm/arm.java | 3 +- .../seaofnodes/simple/node/cpus/riscv/DivRISC.java | 17 ++++++-- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 1 + .../simple/node/cpus/x86_64_v2/CmpX86.java | 7 ++++ .../simple/node/cpus/x86_64_v2/DivX86.java | 36 ++++++++++++---- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 28 +++++++++++-- .../com/seaofnodes/simple/parser/Construction.java | 3 +- .../com/seaofnodes/simple/parser/Expressions.java | 4 +- .../java/com/seaofnodes/simple/parser/Lexer.java | 4 +- 16 files changed, 199 insertions(+), 25 deletions(-) create mode 100644 chapter31/src/main/java/com/seaofnodes/simple/node/ModFNode.java create mode 100644 chapter31/src/main/java/com/seaofnodes/simple/node/ModNode.java create mode 100644 chapter31/src/main/java/com/seaofnodes/simple/node/cpus/arm/ModARM.java (limited to 'chapter31/src/main/java') 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 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 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 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 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< 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< 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 writers=load.antiDeps(new Ary<>(Node.class)); + if( writers.isEmpty() ) return true; + var seen=new IdentityHashMap(); + Ary 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 * *
-     *     multiplicativeExpr : unaryExpr (('*' | '/') unaryExpr)*
+     *     multiplicativeExpr : unaryExpr (('*' | '/' | '%') unaryExpr)*
      * 
* @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; -- cgit v1.2.3