From 2370fb29d4538479af9eb94fc666a5ce09fcb492 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 8 Mar 2025 09:59:31 -0800 Subject: Ch20 reg (#166) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * READMEs * Update README.md * Update README.md * Move printing into print dir * Move codegen into codegen * Framework for Reg Alloc * First cut BuildLRG RegMask.EMPTY -> null * Setup for first simple split * First cut split code for mismatch regs * Live Ranges U-F BuildLRG for Phi Add CmpFX86 * FPR return CallEndX86 needed to tell fp return from gpr ret Call has no output regs. * Next cut regalloc Building IFG. Coloring. Some nested spilling Optimize divf/con -> mul times inverse * RISC-V basic isel (#156) * Initial push Major CodeGen cleanup; most static globals move into the CodeGen object. * Minor progress bug with mutual recursion * Add test from pr#148 * First cut x86 "port" Only "return 0;", no registers, no encoding, but yah gotta start somewhere * Update README.md * Update README.md * Update ListScheduler.java * command line launcher for simple Parser bug fref in args Some new test cases. * Add basic RegMask for more than 64 bits of register mask. Add calling convention basics to X86; con+ret RegMasks. GCM computes CFG for all users. Drop unused MultiUse. Pick up reg-pressure aware ListScheduler. Re-layout CodeGen file to get code & data chunks nearer each other. minor Ary extension * ASM Printer InstSel handles folding 2+ ideal ops into 1 machine op * handle instSel for some control flow Bool,If,CProj,Region,Phi Handle 2-op expansions Shuffle instSel graph walk back again. * Basic if-block inst selects and asm prints * Add mul-by-coinstant to shift * left shift codegen basic * exclude RSP from *write* mask * 2-arg add (not immediate) mul-by-small constant opt. Some utilities. * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * inst select for new struct allocation * Float, bitwise and arithmetic operands codegen x86-64 (#150) * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * float ops without imm values * merge * merge * inst select for new struct allocation * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * float ops without imm values * merge * merge * Rebased on ch 19 * Update tests --------- Co-authored-by: Cliff Click * cleanup after merge alpha-sort helper fcns implicit test vs zero/null * Add LEA op asm print works on ideal nodes for all tests * Minor cleanup lea * merge2 * merge3 * GCM for float ops fixed, other cleanup - small extensions * x86 addressing modes during inst select Drop New taking inits; just follow with initializing stores. Simplifies inst selelection which otherwise needs to undo this optimization and emit following init stores. Basic load/store for now, op-to-mem comes later add same becomes Shl by 1. Drop DivF-immiedate * call setup * extended ch13, 14,15,16 (#153) * merge2 * merge3 * Fix a few minor fuzzer bugs * Force array layout ld/st get size (but not signed/unsigned) Add unsigned LT for later range checks. * Fix a bunch of float issues was deleting required inputs * simpler invariant defensive copy inputs for simpler invariant in complex sharing patterns inc/dec form (just the opcode now). * Call & CallR X86 instructions * merge2 * Add-from-memory op Remove FP immediate forms. * Remove name from TFP Never shoulda been there (but was convenient for awhile). Moved into FunNode, found by checking the linker table with a TFP. * remove debug prints add check for bad call convention fix 3 tests (bad merge?) * cleanup call convention abi Needs more love at some point... * one more cleanup ABI * New (#154) * merge2 * merge3 * GCM for float ops fixed, other cleanup - small extensions * call setup * merge2 * remove debug prints add check for bad call convention fix 3 tests (bad merge?) * cleanup call convention abi Needs more love at some point... * one more cleanup ABI --------- Co-authored-by: Cliff Click * Add CmpMem form Common addressing mode print LEA can skip a base * Add a AddFMemX86 A bunch of mem op patterns are missing, hopefully they are just cut-n-paste from the existing patterns. * Docs * XMM reg mask fix Minor README updates * Allow inverted cmp/mem narrowing stores can bypass an AndMask Array length loads do not need control Some missing print info * Support "*ptr op= val" at least for MemAdd * missed golden rule update * Array len is u32 load-after-store zero/sign-extends if the store is truncating * One more missed case * riscv init * added not imm form bitwise shifts and ops plus test cases * addressing modes(high chance it'll get deleted) * fix minor bug * delete non existing matches * replace RegMask.Empty with null * riscv handle store and load, fltRisch uses risc reg now * load float into GPR and then later in RA do hard split. * minor changes * turn off ch20 tests * Update Chapter20Test.java --------- Co-authored-by: Cliff Click * Bring pr/154 to ch 20 RISC5 changes. Some missing x86 ops. Still needs some calling convention love. * First cut regalloc working Biased coloring; tracking splits around a LRG. Separate split for self-conflicts. postColor to remove junk splits. Some minor riscv fixes. * Compile some riscv codes If SplitEmptyMask does not apply, fall back to normal split. Missing CmpFRISC. Renamed riscv flags. RetRISC handls FPR remove extra RegMask constructurs * Progress reg alloc Handle multi-node projections. A little smarter about 2-addr scheduling RegAlloc must-have single registers removes from other masks instead of interfering; had the mask removal backwards in a few cases. LRG/RegMask COW expand masks before mutating. Clone small constants instead of spilling. Alloc & ProjX86 get output reg masks. Full print large reg masks with sp+offset * UF LRGs can be null during coloring * Finish UF find * README updates * Fix ch19 mis-merge? * x86 call args, risc5 load/store regs * Push RISC WMASK avoid writing to RSP * Progress calling convention allocations Call unlinks before reg alloc. CallEnd tracks RPC CallX86 requires TFP for correct ABI Bias Color tracks 2-addr. RPC gets a mask/stack-slot Clean up call/fun ABI Fix mask RET, RET_F Fix print stack slot Remove isMultiHead, isMultiTail Better all-asm print * Beef up Newton test * Clean pass normal tests New fcn print upgrades several golden rule tests. Move the unlink-all from the walk::err call (which IS used during IterPeeps) to GCM. CallEnd upgrades return type based on constant call. Fix unlink to also unlink CallEnd Constant TFP print checks constant Tested an untested Load * Arm basics, minor changes in riscv (#160) * Initial push Major CodeGen cleanup; most static globals move into the CodeGen object. * Minor progress bug with mutual recursion * Add test from pr#148 * First cut x86 "port" Only "return 0;", no registers, no encoding, but yah gotta start somewhere * Update README.md * Update README.md * Update ListScheduler.java * command line launcher for simple Parser bug fref in args Some new test cases. * Add basic RegMask for more than 64 bits of register mask. Add calling convention basics to X86; con+ret RegMasks. GCM computes CFG for all users. Drop unused MultiUse. Pick up reg-pressure aware ListScheduler. Re-layout CodeGen file to get code & data chunks nearer each other. minor Ary extension * ASM Printer InstSel handles folding 2+ ideal ops into 1 machine op * handle instSel for some control flow Bool,If,CProj,Region,Phi Handle 2-op expansions Shuffle instSel graph walk back again. * Basic if-block inst selects and asm prints * Add mul-by-coinstant to shift * left shift codegen basic * exclude RSP from *write* mask * 2-arg add (not immediate) mul-by-small constant opt. Some utilities. * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * inst select for new struct allocation * Float, bitwise and arithmetic operands codegen x86-64 (#150) * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * float ops without imm values * merge * merge * inst select for new struct allocation * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * float ops without imm values * merge * merge * Rebased on ch 19 * Update tests --------- Co-authored-by: Cliff Click * cleanup after merge alpha-sort helper fcns implicit test vs zero/null * Add LEA op asm print works on ideal nodes for all tests * Minor cleanup lea * merge2 * merge3 * GCM for float ops fixed, other cleanup - small extensions * x86 addressing modes during inst select Drop New taking inits; just follow with initializing stores. Simplifies inst selelection which otherwise needs to undo this optimization and emit following init stores. Basic load/store for now, op-to-mem comes later add same becomes Shl by 1. Drop DivF-immiedate * call setup * extended ch13, 14,15,16 (#153) * merge2 * merge3 * Fix a few minor fuzzer bugs * Force array layout ld/st get size (but not signed/unsigned) Add unsigned LT for later range checks. * Fix a bunch of float issues was deleting required inputs * simpler invariant defensive copy inputs for simpler invariant in complex sharing patterns inc/dec form (just the opcode now). * Call & CallR X86 instructions * merge2 * Add-from-memory op Remove FP immediate forms. * Remove name from TFP Never shoulda been there (but was convenient for awhile). Moved into FunNode, found by checking the linker table with a TFP. * remove debug prints add check for bad call convention fix 3 tests (bad merge?) * cleanup call convention abi Needs more love at some point... * one more cleanup ABI * New (#154) * merge2 * merge3 * GCM for float ops fixed, other cleanup - small extensions * call setup * merge2 * remove debug prints add check for bad call convention fix 3 tests (bad merge?) * cleanup call convention abi Needs more love at some point... * one more cleanup ABI --------- Co-authored-by: Cliff Click * Add CmpMem form Common addressing mode print LEA can skip a base * Add a AddFMemX86 A bunch of mem op patterns are missing, hopefully they are just cut-n-paste from the existing patterns. * Docs * XMM reg mask fix Minor README updates * Allow inverted cmp/mem narrowing stores can bypass an AndMask Array length loads do not need control Some missing print info * Support "*ptr op= val" at least for MemAdd * missed golden rule update * Array len is u32 load-after-store zero/sign-extends if the store is truncating * One more missed case * riscv init * added not imm form bitwise shifts and ops plus test cases * addressing modes(high chance it'll get deleted) * fix minor bug * delete non existing matches * replace RegMask.Empty with null * riscv handle store and load, fltRisch uses risc reg now * load float into GPR and then later in RA do hard split. * minor changes * turn off ch20 tests * Update Chapter20Test.java * add riscv port to readme * arm init * work in progress * arm2 bs * work in progress * clearnup arm * fixed main pr problems * regmask extra comments --------- Co-authored-by: Cliff Click * Update Chapter20Test.java * Weaken range-check test since no range checks... test cannot fail (pass) * Fix issue #161 Error adding 'null' and '5' * bug fixs, cloning constants Fix bug missing Find. Fix bug setDef does unordered removal from basic blocks. Use cloned constants for spilling. * RA fixes SplitSelfConflict MUST split before uses and after defs. Split global constants across functions Missing find in union; Inserting split after new inserted wrong place Pre-remove null LRGs before color. Bias color hunts through Phis Shorten InstructionSelection. Rename !unified() to leader() AddMemX86 is 2-addr Add CastXXX to preserve register across cast. * Allow a killMap to kill regs. Bugfix scheduler. Bugfix spiller - self-conflict order depended on hashtable iteration order, which depended on System.hashCode which would vary run to run. Improvements to coloring Improvements to spill quality testing * Added flags-kill for XOR * Missing add-deps from fuzzer * Update Chapter14Test.java * remove jukn files * minimal "make release" * Add regkills in IFG building Fix bug LRG union stats Adjust self-conflict splits to be slightly less aggressive In every use-side split, dont split-after-split same block. NewNode is a multi, does not define a register * RA improvements Attempt to commute to keep reg-masks compatible. Clones with kills (x86 XOR killing flags to zero) fail before the flag-def. Bugfix failed to color last lrg. More smarts on picking trivial LRGs during coloring Drop isSplit, add SplitNode Pass regalloc round to all splits for debugging Self-conflict no split on loop backedge. Handle split that gets made goes dead No-reg-mask spilling handles case with many def/uses. Add DivIX86 BrainFuck, MergeSort now allocate as testing * Push l,ast change, unbreak branch * Finally pass the `new [u8]` double-copy test * Fix several ARM reg setup problems Finish Split bypass check ARM: rsp is also a fixed zero, in R31. R0 is a valid register. CallArm prints args, passes TFP for arg selection. Does not return a register. All CallEndARM which DOES return a register. Parms missing tfp for float args. ProjARM after a New missing regs. RetARM missing RPC. Remove hopeful DivIX86 * Bunch of minor arm, risc fixes small constants not cloning * Much ARM fixage One More Go-Round with Better Biased Colors Fix bug picking deepest spills to bias. ARM: remove default 2-address. Fix regmask overflow. Rename some ops to be canonical. * Fixes to release Port does not have to be in a Simple named directory. Call convention is just a string, no enum Missed some tests running RISC, ARM. * Minor release change to allow another foreign port * Allowing non-Simple repo ports Expanding public API slightly so alternative (non-Simple repo) ports can happen. RegMask supports single-bit-set and a long bitmask. Bugfix GCM splitting multiple global constants. Bugfix LCM grabbing a projection vs multi Bugfix RegAlloc when avoiding splitting a clonable Source code in release More timing in CodeGen * Cleanup call ABI presentation Everybody uses the same names, same code shapes * Caller save regs ...not callee save yet * Expose caller save regs * More x86,risc,arm call convention fixes Collect callee and caller save masks (inverts of each other, except for spills). Reorg layout to be closer to each other; remove dead mask definitions; add final keyword * Callee-save registers Callee-save registers and masks and inserting LRGs for same and spilling and picking good spills. Insert CalleeSaveNodes and edges to RetXXXs and RegMasks for those edges. Iterators for regmask. Better printing post-allocation * RegMask supports 128 bits All regs available arm, risc. MergeSort compiles & runs * Fix risc5 compares No flags on risc5. Branch takes 2 inputs (one can be imm12). Float compare only sets a GPR to 0/1. Bool has a isFloat Common risc5 imm-form handling * yank MulIRISC * fix arg flags reg Arm split op can spill flags bugfix RegAlloc 1st real >=64bit reg num * Update Chapter20Test.java * Turn off transpile tests which are broken for some time now * A lot more readme * better flags ListScheduler stalls cmp/jmp in the same block; avoids some flags spills. Make CmpIX86/ARM rematieralize. Bugfix: remove some include x86/risc/arm in other dirs. Canonicalize boilerplate fcn order * regalloc improves Use FltRISC, not clonable requires a spill from int->flt regs. new splits track origin LRG, so later splits in the same pass know what lrg a spilled input is. * RA improvements & fixes Bugfix on split loop-depth computation. Track killmask kills, which are always capacity kills and require more spilling. Rename the riscv registers canonically, so I can tell them part! Definitely no GP or TP in Simple. Node insertAfter bypass a little more conservative. * RA bugfix remove unified failed live ranges * easier access for remote ports debug support * Lots more comments * bugfix infinite peep cycle on (17 ^ 3.14), i.e. bad program * Fix imm12 shift --------- Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- .gitignore | 1 + README.md | 26 +- chapter02/README.md | 15 + chapter09/README.md | 8 + .../java/com/seaofnodes/simple/node/AddNode.java | 5 + .../java/com/seaofnodes/simple/node/MulNode.java | 5 + .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/node/AddNode.java | 5 + .../java/com/seaofnodes/simple/node/MulNode.java | 5 + .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/node/AddNode.java | 5 + .../java/com/seaofnodes/simple/node/MulNode.java | 5 + .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/node/AddNode.java | 5 + .../java/com/seaofnodes/simple/node/MulNode.java | 5 + .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/node/AddNode.java | 6 + .../java/com/seaofnodes/simple/node/MulNode.java | 5 + .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/Chapter17Test.java | 7 +- .../main/java/com/seaofnodes/simple/Parser.java | 2 +- .../java/com/seaofnodes/simple/node/AddNode.java | 9 +- .../java/com/seaofnodes/simple/node/MulNode.java | 8 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + chapter19/README.md | 97 +++- .../main/java/com/seaofnodes/simple/CodeGen.java | 2 +- .../java/com/seaofnodes/simple/ListScheduler.java | 4 +- .../main/java/com/seaofnodes/simple/Parser.java | 2 +- .../main/java/com/seaofnodes/simple/RegMask.java | 8 + .../java/com/seaofnodes/simple/node/AddNode.java | 11 +- .../com/seaofnodes/simple/node/CallEndNode.java | 2 +- .../java/com/seaofnodes/simple/node/CallNode.java | 2 + .../java/com/seaofnodes/simple/node/MulNode.java | 6 + .../simple/node/cpus/riscv/AddFRISC.java | 30 ++ .../simple/node/cpus/riscv/AddIRISC.java | 39 ++ .../seaofnodes/simple/node/cpus/riscv/AddRISC.java | 36 ++ .../simple/node/cpus/riscv/AndIRISC.java | 40 ++ .../seaofnodes/simple/node/cpus/riscv/AndRISC.java | 41 ++ .../simple/node/cpus/riscv/CBranchRISC.java | 49 ++ .../simple/node/cpus/riscv/CallRISC.java | 37 ++ .../simple/node/cpus/riscv/CallRRISC.java | 31 ++ .../simple/node/cpus/riscv/CmpIRISC.java | 44 ++ .../seaofnodes/simple/node/cpus/riscv/CmpRISC.java | 28 ++ .../simple/node/cpus/riscv/DivFRISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/DivRISC.java | 33 ++ .../seaofnodes/simple/node/cpus/riscv/FltRISC.java | 39 ++ .../seaofnodes/simple/node/cpus/riscv/FunRISC.java | 22 + .../simple/node/cpus/riscv/I2F8RISC.java | 29 ++ .../seaofnodes/simple/node/cpus/riscv/IntRISC.java | 43 ++ .../simple/node/cpus/riscv/LoadRISC.java | 34 ++ .../simple/node/cpus/riscv/MemOpRISC.java | 36 ++ .../simple/node/cpus/riscv/MulFRISC.java | 30 ++ .../simple/node/cpus/riscv/MulIRISC.java | 35 ++ .../seaofnodes/simple/node/cpus/riscv/MulRISC.java | 33 ++ .../seaofnodes/simple/node/cpus/riscv/NewRISC.java | 44 ++ .../seaofnodes/simple/node/cpus/riscv/OrIRISC.java | 43 ++ .../seaofnodes/simple/node/cpus/riscv/OrRISC.java | 43 ++ .../simple/node/cpus/riscv/ParmRISC.java | 25 + .../simple/node/cpus/riscv/ProjRISC.java | 23 + .../seaofnodes/simple/node/cpus/riscv/RetRISC.java | 48 ++ .../seaofnodes/simple/node/cpus/riscv/SetRISC.java | 35 ++ .../simple/node/cpus/riscv/SllIRISC.java | 40 ++ .../seaofnodes/simple/node/cpus/riscv/SllRISC.java | 36 ++ .../simple/node/cpus/riscv/SraIRISC.java | 43 ++ .../seaofnodes/simple/node/cpus/riscv/SraRISC.java | 42 ++ .../simple/node/cpus/riscv/SrlIRISC.java | 43 ++ .../seaofnodes/simple/node/cpus/riscv/SrlRISC.java | 38 ++ .../simple/node/cpus/riscv/StoreRISC.java | 40 ++ .../simple/node/cpus/riscv/SubFRISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/SubRISC.java | 29 ++ .../seaofnodes/simple/node/cpus/riscv/TFPRISC.java | 43 ++ .../simple/node/cpus/riscv/XorIRISC.java | 45 ++ .../seaofnodes/simple/node/cpus/riscv/XorRISC.java | 43 ++ .../seaofnodes/simple/node/cpus/riscv/riscv.java | 329 +++++++++++++ .../simple/node/cpus/x86_64_v2/AddFMemX86.java | 2 +- .../simple/node/cpus/x86_64_v2/AndX86.java | 33 ++ .../simple/node/cpus/x86_64_v2/CallEndX86.java | 37 ++ .../simple/node/cpus/x86_64_v2/CallRX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CallX86.java | 3 +- .../simple/node/cpus/x86_64_v2/CmpIX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CmpX86.java | 3 +- .../simple/node/cpus/x86_64_v2/FltX86.java | 2 +- .../simple/node/cpus/x86_64_v2/FunX86.java | 4 +- .../simple/node/cpus/x86_64_v2/IntX86.java | 2 +- .../simple/node/cpus/x86_64_v2/JmpX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MemAddX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MulIX86.java | 2 +- .../simple/node/cpus/x86_64_v2/NewX86.java | 4 +- .../simple/node/cpus/x86_64_v2/OrIX86.java | 2 +- .../simple/node/cpus/x86_64_v2/OrX86.java | 33 ++ .../simple/node/cpus/x86_64_v2/ParmX86.java | 7 +- .../simple/node/cpus/x86_64_v2/ProjX86.java | 6 +- .../simple/node/cpus/x86_64_v2/RetX86.java | 8 +- .../simple/node/cpus/x86_64_v2/SarIX86.java | 37 ++ .../simple/node/cpus/x86_64_v2/SarX86.java | 24 +- .../simple/node/cpus/x86_64_v2/ShlX86.java | 39 ++ .../simple/node/cpus/x86_64_v2/ShrIX86.java | 1 + .../simple/node/cpus/x86_64_v2/ShrX86.java | 38 ++ .../simple/node/cpus/x86_64_v2/StoreX86.java | 2 +- .../simple/node/cpus/x86_64_v2/TFPX86.java | 2 +- .../simple/node/cpus/x86_64_v2/XorIX86.java | 2 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 122 +++-- .../java/com/seaofnodes/simple/Chapter13Test.java | 13 + .../java/com/seaofnodes/simple/Chapter19Test.java | 33 ++ chapter20/Makefile | 12 +- chapter20/README.md | 428 ++++++++++++++++- chapter20/docs/ifg_trim.pdf | Bin 0 -> 155190 bytes chapter20/docs/pardoe.docx | Bin 0 -> 22583 bytes .../java/com/seaofnodes/simple/ASMPrinter.java | 140 ------ .../src/main/java/com/seaofnodes/simple/Ary.java | 19 +- .../main/java/com/seaofnodes/simple/CodeGen.java | 288 ------------ .../com/seaofnodes/simple/GlobalCodeMotion.java | 241 ---------- .../com/seaofnodes/simple/GraphVisualizer.java | 288 ------------ .../main/java/com/seaofnodes/simple/IRPrinter.java | 279 ----------- .../main/java/com/seaofnodes/simple/IterPeeps.java | 9 +- .../main/java/com/seaofnodes/simple/JSViewer.java | 402 ---------------- .../java/com/seaofnodes/simple/ListScheduler.java | 231 --------- .../main/java/com/seaofnodes/simple/Machine.java | 21 - .../main/java/com/seaofnodes/simple/Parser.java | 6 +- .../main/java/com/seaofnodes/simple/RegMask.java | 39 -- .../src/main/java/com/seaofnodes/simple/SB.java | 1 - .../com/seaofnodes/simple/SimpleWebSocket.java | 148 ------ .../com/seaofnodes/simple/codegen/BuildLRG.java | 91 ++++ .../com/seaofnodes/simple/codegen/CodeGen.java | 338 +++++++++++++ .../simple/codegen/GlobalCodeMotion.java | 281 +++++++++++ .../java/com/seaofnodes/simple/codegen/IFG.java | 521 +++++++++++++++++++++ .../java/com/seaofnodes/simple/codegen/LRG.java | 220 +++++++++ .../seaofnodes/simple/codegen/ListScheduler.java | 258 ++++++++++ .../com/seaofnodes/simple/codegen/Machine.java | 22 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 502 ++++++++++++++++++++ .../com/seaofnodes/simple/codegen/RegMask.java | 142 ++++++ .../java/com/seaofnodes/simple/node/AddNode.java | 9 + .../java/com/seaofnodes/simple/node/AndNode.java | 9 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 10 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 25 +- .../java/com/seaofnodes/simple/node/CProjNode.java | 2 +- .../com/seaofnodes/simple/node/CallEndNode.java | 24 +- .../java/com/seaofnodes/simple/node/CallNode.java | 29 +- .../com/seaofnodes/simple/node/CalleeSaveNode.java | 25 + .../java/com/seaofnodes/simple/node/CastNode.java | 8 +- .../com/seaofnodes/simple/node/ConstantNode.java | 8 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/DivFNode.java | 11 +- .../java/com/seaofnodes/simple/node/FunNode.java | 25 +- .../java/com/seaofnodes/simple/node/IfNode.java | 6 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 4 +- .../com/seaofnodes/simple/node/LogicalNode.java | 4 +- .../seaofnodes/simple/node/MachConcreteNode.java | 2 +- .../java/com/seaofnodes/simple/node/MachNode.java | 18 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 1 + .../java/com/seaofnodes/simple/node/MemOpNode.java | 10 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 + .../java/com/seaofnodes/simple/node/NeverNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 104 +++- .../java/com/seaofnodes/simple/node/PhiNode.java | 5 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 1 - .../com/seaofnodes/simple/node/RegionNode.java | 4 +- .../com/seaofnodes/simple/node/ReturnNode.java | 3 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 1 + .../java/com/seaofnodes/simple/node/SplitNode.java | 22 + .../java/com/seaofnodes/simple/node/StartNode.java | 5 +- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/node/XCtrlNode.java | 3 +- .../seaofnodes/simple/node/cpus/arm/AddARM.java | 34 ++ .../seaofnodes/simple/node/cpus/arm/AddFARM.java | 31 ++ .../seaofnodes/simple/node/cpus/arm/AddIARM.java | 51 ++ .../seaofnodes/simple/node/cpus/arm/AndARM.java | 38 ++ .../seaofnodes/simple/node/cpus/arm/AndIARM.java | 56 +++ .../seaofnodes/simple/node/cpus/arm/AsrARM.java | 40 ++ .../seaofnodes/simple/node/cpus/arm/AsrIARM.java | 41 ++ .../seaofnodes/simple/node/cpus/arm/BranchARM.java | 48 ++ .../seaofnodes/simple/node/cpus/arm/CallARM.java | 45 ++ .../simple/node/cpus/arm/CallEndARM.java | 35 ++ .../seaofnodes/simple/node/cpus/arm/CallRRARM.java | 32 ++ .../seaofnodes/simple/node/cpus/arm/CmpARM.java | 30 ++ .../seaofnodes/simple/node/cpus/arm/CmpFARM.java | 31 ++ .../seaofnodes/simple/node/cpus/arm/CmpIARM.java | 54 +++ .../seaofnodes/simple/node/cpus/arm/CmpMemARM.java | 4 + .../seaofnodes/simple/node/cpus/arm/DivARM.java | 33 ++ .../seaofnodes/simple/node/cpus/arm/DivFARM.java | 30 ++ .../seaofnodes/simple/node/cpus/arm/FloatARM.java | 36 ++ .../seaofnodes/simple/node/cpus/arm/FunARM.java | 21 + .../seaofnodes/simple/node/cpus/arm/I2F8ARM.java | 29 ++ .../seaofnodes/simple/node/cpus/arm/IntARM.java | 38 ++ .../seaofnodes/simple/node/cpus/arm/LoadARM.java | 37 ++ .../seaofnodes/simple/node/cpus/arm/LslARM.java | 41 ++ .../seaofnodes/simple/node/cpus/arm/LslIARM.java | 42 ++ .../seaofnodes/simple/node/cpus/arm/LsrARM.java | 40 ++ .../seaofnodes/simple/node/cpus/arm/LsrIARM.java | 41 ++ .../seaofnodes/simple/node/cpus/arm/MemOpARM.java | 58 +++ .../seaofnodes/simple/node/cpus/arm/MulARM.java | 34 ++ .../seaofnodes/simple/node/cpus/arm/MulFARM.java | 30 ++ .../seaofnodes/simple/node/cpus/arm/MulIARM.java | 43 ++ .../seaofnodes/simple/node/cpus/arm/NewARM.java | 31 ++ .../com/seaofnodes/simple/node/cpus/arm/OrARM.java | 42 ++ .../seaofnodes/simple/node/cpus/arm/OrIARM.java | 40 ++ .../seaofnodes/simple/node/cpus/arm/ParmARM.java | 25 + .../seaofnodes/simple/node/cpus/arm/ProjARM.java | 23 + .../seaofnodes/simple/node/cpus/arm/RetARM.java | 49 ++ .../seaofnodes/simple/node/cpus/arm/SetARM.java | 41 ++ .../seaofnodes/simple/node/cpus/arm/SplitARM.java | 22 + .../seaofnodes/simple/node/cpus/arm/StoreARM.java | 52 ++ .../seaofnodes/simple/node/cpus/arm/SubARM.java | 30 ++ .../seaofnodes/simple/node/cpus/arm/SubFARM.java | 32 ++ .../seaofnodes/simple/node/cpus/arm/TFPARM.java | 37 ++ .../seaofnodes/simple/node/cpus/arm/XorARM.java | 41 ++ .../seaofnodes/simple/node/cpus/arm/XorIARM.java | 43 ++ .../com/seaofnodes/simple/node/cpus/arm/arm.java | 385 +++++++++++++++ .../com/seaofnodes/simple/node/cpus/arm/i2f8.java | 4 + .../simple/node/cpus/riscv/AddFRISC.java | 30 ++ .../simple/node/cpus/riscv/AddIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/AddRISC.java | 29 ++ .../simple/node/cpus/riscv/AndIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/AndRISC.java | 38 ++ .../simple/node/cpus/riscv/BranchRISC.java | 47 ++ .../simple/node/cpus/riscv/CallEndRISC.java | 35 ++ .../simple/node/cpus/riscv/CallRISC.java | 44 ++ .../simple/node/cpus/riscv/CallRRISC.java | 35 ++ .../simple/node/cpus/riscv/CastRISC.java | 18 + .../simple/node/cpus/riscv/DivFRISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/DivRISC.java | 32 ++ .../seaofnodes/simple/node/cpus/riscv/FltRISC.java | 31 ++ .../seaofnodes/simple/node/cpus/riscv/FunRISC.java | 21 + .../simple/node/cpus/riscv/I2F8RISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/ImmRISC.java | 40 ++ .../seaofnodes/simple/node/cpus/riscv/IntRISC.java | 35 ++ .../simple/node/cpus/riscv/LoadRISC.java | 40 ++ .../simple/node/cpus/riscv/MemOpRISC.java | 57 +++ .../simple/node/cpus/riscv/MulFRISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/MulRISC.java | 32 ++ .../seaofnodes/simple/node/cpus/riscv/NewRISC.java | 29 ++ .../seaofnodes/simple/node/cpus/riscv/OrIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/OrRISC.java | 39 ++ .../simple/node/cpus/riscv/ParmRISC.java | 26 + .../simple/node/cpus/riscv/ProjRISC.java | 25 + .../seaofnodes/simple/node/cpus/riscv/RetRISC.java | 48 ++ .../simple/node/cpus/riscv/SetFRISC.java | 33 ++ .../simple/node/cpus/riscv/SetIRISC.java | 17 + .../seaofnodes/simple/node/cpus/riscv/SetRISC.java | 33 ++ .../simple/node/cpus/riscv/SllIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/SllRISC.java | 37 ++ .../simple/node/cpus/riscv/SplitRISC.java | 21 + .../simple/node/cpus/riscv/SraIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/SraRISC.java | 38 ++ .../simple/node/cpus/riscv/SrlIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/SrlRISC.java | 38 ++ .../simple/node/cpus/riscv/StoreRISC.java | 56 +++ .../simple/node/cpus/riscv/SubFRISC.java | 30 ++ .../seaofnodes/simple/node/cpus/riscv/SubRISC.java | 29 ++ .../seaofnodes/simple/node/cpus/riscv/TFPRISC.java | 39 ++ .../simple/node/cpus/riscv/XorIRISC.java | 11 + .../seaofnodes/simple/node/cpus/riscv/XorRISC.java | 41 ++ .../seaofnodes/simple/node/cpus/riscv/riscv.java | 361 ++++++++++++++ .../simple/node/cpus/x86_64_v2/AddFMemX86.java | 14 +- .../simple/node/cpus/x86_64_v2/AddFX86.java | 4 + .../simple/node/cpus/x86_64_v2/AddIX86.java | 2 + .../simple/node/cpus/x86_64_v2/AddMemX86.java | 7 +- .../simple/node/cpus/x86_64_v2/AddX86.java | 6 +- .../simple/node/cpus/x86_64_v2/AndIX86.java | 2 + .../simple/node/cpus/x86_64_v2/AndX86.java | 34 ++ .../simple/node/cpus/x86_64_v2/CallEndX86.java | 35 ++ .../simple/node/cpus/x86_64_v2/CallRX86.java | 20 +- .../simple/node/cpus/x86_64_v2/CallX86.java | 21 +- .../simple/node/cpus/x86_64_v2/CastX86.java | 18 + .../simple/node/cpus/x86_64_v2/CmpFX86.java | 29 ++ .../simple/node/cpus/x86_64_v2/CmpIX86.java | 18 +- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 4 +- .../simple/node/cpus/x86_64_v2/CmpX86.java | 2 + .../simple/node/cpus/x86_64_v2/DivFX86.java | 2 + .../simple/node/cpus/x86_64_v2/DivX86.java | 14 +- .../simple/node/cpus/x86_64_v2/FltX86.java | 13 +- .../simple/node/cpus/x86_64_v2/FunX86.java | 7 +- .../simple/node/cpus/x86_64_v2/I2f8X86.java | 2 + .../simple/node/cpus/x86_64_v2/IntX86.java | 26 +- .../simple/node/cpus/x86_64_v2/JmpX86.java | 8 +- .../simple/node/cpus/x86_64_v2/LeaX86.java | 2 + .../simple/node/cpus/x86_64_v2/LoadX86.java | 6 +- .../simple/node/cpus/x86_64_v2/MemAddX86.java | 6 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 18 +- .../simple/node/cpus/x86_64_v2/MulFX86.java | 4 + .../simple/node/cpus/x86_64_v2/MulIX86.java | 9 +- .../simple/node/cpus/x86_64_v2/MulX86.java | 5 +- .../simple/node/cpus/x86_64_v2/NewX86.java | 27 +- .../simple/node/cpus/x86_64_v2/OrIX86.java | 5 +- .../simple/node/cpus/x86_64_v2/OrX86.java | 35 ++ .../simple/node/cpus/x86_64_v2/ParmX86.java | 9 +- .../simple/node/cpus/x86_64_v2/ProjX86.java | 12 +- .../simple/node/cpus/x86_64_v2/RetX86.java | 26 +- .../simple/node/cpus/x86_64_v2/SarIX86.java | 39 ++ .../simple/node/cpus/x86_64_v2/SarX86.java | 17 +- .../simple/node/cpus/x86_64_v2/SetX86.java | 4 +- .../simple/node/cpus/x86_64_v2/ShlIX86.java | 2 + .../simple/node/cpus/x86_64_v2/ShlX86.java | 39 ++ .../simple/node/cpus/x86_64_v2/ShrIX86.java | 2 + .../simple/node/cpus/x86_64_v2/ShrX86.java | 40 ++ .../simple/node/cpus/x86_64_v2/SplitX86.java | 21 + .../simple/node/cpus/x86_64_v2/StoreX86.java | 12 +- .../simple/node/cpus/x86_64_v2/SubFX86.java | 2 + .../simple/node/cpus/x86_64_v2/SubX86.java | 2 + .../simple/node/cpus/x86_64_v2/TFPX86.java | 13 +- .../simple/node/cpus/x86_64_v2/XorIX86.java | 5 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 263 +++++++---- .../com/seaofnodes/simple/print/ASMPrinter.java | 163 +++++++ .../seaofnodes/simple/print/GraphVisualizer.java | 287 ++++++++++++ .../com/seaofnodes/simple/print/IRPrinter.java | 328 +++++++++++++ .../java/com/seaofnodes/simple/print/JSViewer.java | 405 ++++++++++++++++ .../seaofnodes/simple/print/SimpleWebSocket.java | 149 ++++++ .../com/seaofnodes/simple/type/TypeFunPtr.java | 4 +- .../com/seaofnodes/simple/type/TypeStruct.java | 1 + .../java/com/seaofnodes/simple/type/TypeTuple.java | 2 + .../java/com/seaofnodes/simple/BrainFuckTest.java | 14 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 1 + .../java/com/seaofnodes/simple/Chapter02Test.java | 1 + .../java/com/seaofnodes/simple/Chapter03Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 1 + .../java/com/seaofnodes/simple/Chapter05Test.java | 1 + .../java/com/seaofnodes/simple/Chapter06Test.java | 1 + .../java/com/seaofnodes/simple/Chapter07Test.java | 1 + .../java/com/seaofnodes/simple/Chapter08Test.java | 1 + .../java/com/seaofnodes/simple/Chapter09Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 1 + .../java/com/seaofnodes/simple/Chapter11Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 14 + .../java/com/seaofnodes/simple/Chapter14Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 13 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 1 + .../java/com/seaofnodes/simple/Chapter17Test.java | 7 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 13 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 88 ++-- .../java/com/seaofnodes/simple/Chapter20Test.java | 185 +++++++- .../src/test/java/com/seaofnodes/simple/Eval2.java | 4 +- .../src/test/java/com/seaofnodes/simple/Main.java | 2 + .../java/com/seaofnodes/simple/MergeSortTest.java | 12 +- .../java/com/seaofnodes/simple/SchedulerTest.java | 1 + .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 2 +- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 2 +- pom.xml | 1 - 339 files changed, 11634 insertions(+), 2620 deletions(-) create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddFRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CBranchRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CmpIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CmpRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivFRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FunRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/I2F8RISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LoadRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MulFRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MulIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MulRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NewRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/OrIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/OrRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ParmRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ProjRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SllIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SllRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubFRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorRISC.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrX86.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlX86.java create mode 100644 chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrX86.java create mode 100644 chapter20/docs/ifg_trim.pdf create mode 100644 chapter20/docs/pardoe.docx delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/ASMPrinter.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/CodeGen.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/GraphVisualizer.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/IRPrinter.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/JSViewer.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/ListScheduler.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/Machine.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/RegMask.java delete mode 100644 chapter20/src/main/java/com/seaofnodes/simple/SimpleWebSocket.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/Machine.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/CalleeSaveNode.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AddARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AddFARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AddIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AsrARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/AsrIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallEndARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CallRRARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpFARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/CmpMemARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/DivARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/DivFARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/FloatARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/I2F8ARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/IntARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/LoadARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/LslARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/LslIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/LsrARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/LsrIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/MemOpARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/MulARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/MulFARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/MulIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/NewARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/OrIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/ParmARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/ProjARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SplitARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/StoreARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SubARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/SubFARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/XorIARM.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/arm/i2f8.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddFRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AddRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallEndRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CallRRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/CastRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivFRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/DivRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FltRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/FunRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/I2F8RISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ImmRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/IntRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/LoadRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MemOpRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MulFRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/MulRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/NewRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/OrIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/OrRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ParmRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/ProjRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/RetRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetFRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SllIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SllRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SplitRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubFRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorRISC.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CastX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpFX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/print/GraphVisualizer.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/print/IRPrinter.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/print/JSViewer.java create mode 100644 chapter20/src/main/java/com/seaofnodes/simple/print/SimpleWebSocket.java diff --git a/.gitignore b/.gitignore index 4fe6bc54..45ae6585 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ # Java stuff # Compiled class file *.class +build/ # Log file *.log diff --git a/README.md b/README.md index d48d7d77..5eeccb1e 100644 --- a/README.md +++ b/README.md @@ -29,32 +29,38 @@ the backend starts with levering Java: the Evaluator (first appears in Chapter The following is a rough plan, subject to change. -Each chapter will be self-sufficient and complete; in the sense that each chapter will fully implement -a subset of the Simple language, and include everything that was created in the previous chapter. -Each chapter will also include a detailed commentary on relevant aspects of the -Sea Of Nodes intermediate representation. +Each chapter will be self-sufficient and complete; in the sense that each +chapter will fully implement a subset of the Simple language, and include +everything that was created in the previous chapter. Each chapter will also +include a detailed commentary on relevant aspects of the Sea Of Nodes +intermediate representation. -The Simple language will be styled after a subset of C or Java +The Simple language is styled after a subset of C or Java. * [Chapter 1](chapter01/README.md): Script that returns an integer literal, i.e., an empty function that takes no arguments and returns a single integer value. The `return` statement. * [Chapter 2](chapter02/README.md): Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding. * [Chapter 3](chapter03/README.md): Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant. -* [Chapter 4](chapter04/README.md): A non-constant external variable input named `arg`. Binary and Comparison operators involving constants and `arg`. Non-zero values will be truthy. Peephole optimizations involving algebraic simplifications. +* [Chapter 4](chapter04/README.md): A non-constant external variable input + named `arg`. Binary and Comparison operators involving constants and `arg`. + Non-zero values will be truthy. Peephole optimizations involving algebraic + simplifications. * [Chapter 5](chapter05/README.md): `if` statement. CFG construction. * [Chapter 6](chapter06/README.md): Peephole optimization around dead control flow. -* [Chapter 7](chapter07/README.md): `while` statement. Looping construct - eager phi approach. -* [Chapter 8](chapter08/README.md): Looping construct continued, lazy phi creation, `break` and `continue` statements. +* [Chapter 7](chapter07/README.md): `while` statement; looping constructs - eager phi approach. +* [Chapter 8](chapter08/README.md): Looping constructs continued, lazy phi creation, `break` and `continue` statements. * [Chapter 9](chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. -* [Chapter 10](chapter10/README.md): User defined Struct types. Memory effects: general memory edges in SSA. Equivalence class aliasing. Null pointer analysis. Peephole optimization around load-after-store/store-after-store. +* [Chapter 10](chapter10/README.md): User defined Struct types. Memory effects: + general memory edges in SSA. Equivalence class aliasing. Null pointer + analysis. Peephole optimization around load-after-store/store-after-store. * [Chapter 11](chapter11/README.md): Global Code Motion - Scheduling. * [Chapter 12](chapter12/README.md): Float type. * [Chapter 13](chapter13/README.md): Nested references in Structs. * [Chapter 14](chapter14/README.md): Narrow primitive types (e.g. bytes) * [Chapter 15](chapter15/README.md): One dimensional static length array type, with array loads and stores. * [Chapter 16](chapter16/README.md): Constructors -* [Chapter 17](chapter17/README.md): Mutability & Syntax Sugar: `var`, `val`, `x+=y`, `for(init;test;next)body` +* [Chapter 17](chapter17/README.md): Mutability & Syntax Sugar: `var`, `val`, `x+=y`, `for(init; test; next) body` * [Chapter 18](chapter18/README.md): Functions and calls. * [Chapter 19](chapter19/README.md): Instruction selection and portable compilation * [Chapter 20](chapter20/README.md): Graph Coloring Register Allocation diff --git a/chapter02/README.md b/chapter02/README.md index 444664dd..8799863f 100644 --- a/chapter02/README.md +++ b/chapter02/README.md @@ -42,6 +42,18 @@ We extend the set of nodes by adding following additional node types. | Div | Data | Divide a value by another | Two data nodes, values are divided, order matters | Result of the division | | Minus | Data | Negate a value | One data node, value is negated | Result of the unary minus | + +## *Value* equality vs *Reference* equality + +In much of Simple, Nodes are looked up (`find()` calls) via *reference* +equality. This is by far the most common case. In [Chapter +9](../chapter09/README.md) we introduce *value* equality for the first time. +In both cases the choice of value-vs-reference equality is intentional: it is +*never* correct to "just pick one or the other kind of equality". When in +doubt check the context: only *Global Value Numbering* uses value equality; +everywhere we mean reference equality. + + ## Peephole Optimizations Nodes in the graph can be peephole-optimized. The graph is viewed through a @@ -141,6 +153,7 @@ starting in [Chapter 4](../chapter04/README.md) and [Chapter There are other important properties of the Lattice that we discuss in [Chapter 4](../chapter04/README.md) and [Chapter 10](../chapter10/README.md), such as the "meet" and "join" operators and their rules. + ## Nodes Pre Peephole Optimization The following visual shows how the graph looks like pre-peephole optimization: @@ -152,10 +165,12 @@ The following visual shows how the graph looks like pre-peephole optimization: * The edges from Constants to Start are shown in dotted lines as these are not true control edges * We label each edge with its position in the node's list of inputs. + ## Post-peephole ![Example Visual](./docs/02-post-peephole-ex1.svg) + ## Demonstration To demonstrate how the optimisation works, let's consider the following code: ``` diff --git a/chapter09/README.md b/chapter09/README.md index 2ea99ac0..d3b55a19 100644 --- a/chapter09/README.md +++ b/chapter09/README.md @@ -48,6 +48,14 @@ get the same result - and can be shared. constant 17 is not the same as 99, but both are the same `ConstantNode` class and label. The `eq` and `hash` calls check (or hash) these extra bits. +Note the intentional *value* equality here. In many places in Simple we use +*reference* equality - e.g. node/edge maintenance is via reference equality, not +value equality, so e.g. the `Utils.find()` call finds via reference. Through +out the Simple project whenever a Node lookup is happening, beware if its via +*value* or *reference* equality; this is not always explicitly called out but +should be obvious from context. + + Since we edit the graph a lot, Nodes can have their inputs change which changes their hash which means they can't be found in the GVN table. E.g. we swap out the `Add` for a `Con` in: diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/AddNode.java index 48350957..67eacd3a 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -173,4 +173,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/MulNode.java index 8c8a6e0a..16915a1c 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -55,4 +55,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter13/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter13/src/test/java/com/seaofnodes/simple/Chapter13Test.java index b425fd85..59f08963 100644 --- a/chapter13/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter13/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -130,6 +130,19 @@ return n.i; catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); } } + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { Parser parser = new Parser( diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java index 9d425f7a..bd1a9dcd 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -183,4 +183,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java index f231a97b..6f679462 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -58,4 +58,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 0edb2d51..807badd5 100644 --- a/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter14/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -130,6 +130,19 @@ return n.i; catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); } } + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { Parser parser = new Parser( diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..97d2bb9b 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -184,4 +184,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java index f231a97b..6f679462 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -58,4 +58,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 416aba31..ab8ea902 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -130,6 +130,19 @@ return n.i; catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); } } + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { Parser parser = new Parser( diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..97d2bb9b 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -184,4 +184,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java index b5ef91e9..949af27a 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -60,4 +60,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 165d23e5..73fff8fd 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -129,6 +129,19 @@ return n.i; catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); } } + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { Parser parser = new Parser( diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java index 0834a381..4007df91 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -44,6 +44,7 @@ public class AddNode extends Node { public Node idealize () { Node lhs = in(1); Node rhs = in(2); + if( rhs.err() != null ) return null; Type t2 = rhs._type; // Add of 0. We do not check for (0+x) because this will already @@ -184,4 +185,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/MulNode.java index b5ef91e9..949af27a 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -60,4 +60,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 30d9b147..eeb28f1d 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -129,6 +129,19 @@ return n.i; catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } } + @Test + public void testNullRef4() { + Parser parser = new Parser("-null-5/null-5;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test public void testNullRef5() { + Parser parser = new Parser("return null+42;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { Parser parser = new Parser( diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java index 4a7e959a..1ca9a515 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -11,12 +11,7 @@ public class Chapter17Test { @Test public void testJig() { - Parser parser = new Parser(""" -int i = 0; -i=i=1; -return i; - //return 3.14; -"""); + Parser parser = new Parser("return 1;"); StopNode stop = parser.parse().iterate(); assertEquals("return 1;", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index c16e3267..ad617b2b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -1725,6 +1725,6 @@ public class Parser { public final Lexer _loc; // file:line:charoff err //String msg = "src:"+_line_number+":"+(_position-_line_start)+" "+errorMessage; - ParseException( String msg, Lexer loc ) { super(msg); _loc = loc; assert loc!=null; } + ParseException( String msg, Lexer loc ) { super(msg); _loc = loc; } } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java index e6704ea6..21f8ad87 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; - import java.util.BitSet; public class AddNode extends Node { @@ -44,6 +44,7 @@ public class AddNode extends Node { public Node idealize () { Node lhs = in(1); Node rhs = in(2); + if( rhs.err()!=null ) return null; Type t2 = rhs._type; // Add of 0. We do not check for (0+x) because this will already @@ -184,4 +185,10 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public Parser.ParseException err() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; + if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(1)._type,null); + if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(2)._type,null); + return null; + } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/MulNode.java index b5ef91e9..a1544d3d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class MulNode extends Node { @@ -60,4 +60,10 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public Parser.ParseException err() { + if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return null; + if( !(in(1)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(1)._type,null); + if( !(in(2)._type instanceof TypeInteger) ) return Parser.error("Cannot '"+label()+"' " + in(2)._type,null); + return null; + } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 6aa64bf9..de722026 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -127,6 +127,19 @@ return n.i; catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } } + @Test + public void testNullRef4() { + CodeGen code = new CodeGen("-null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test public void testNullRef5() { + CodeGen code = new CodeGen("return null+42;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { CodeGen code = new CodeGen( diff --git a/chapter19/README.md b/chapter19/README.md index 1e2074cf..87a4c3a6 100644 --- a/chapter19/README.md +++ b/chapter19/README.md @@ -90,4 +90,99 @@ the `Cmp/SetXX` opcode sequence. The X86 `Jxx` takes in `FLAGS` and not a `0/1`, so the `Jxx` will skip the `SetXX` and directly use the `Cmp`. Using the ideal `Bool` directly will require the `SetXX`. i.e. `return a==3` will match to a `CmpX86 RAX,#3; SetEQ RAX; ret;` whereas a `if( a==3 )` will match -to a `CmpX86 RAX,#3; jeq;` \ No newline at end of file +to a `CmpX86 RAX,#3; jeq;` + +## RISC-V port + +In the `node/cpus/riscv` directory is a `riscv.java` port to a RISC-V. +This port supports 32 64-bit GPRs, and 32 floating-point registers. +There is a pattern matcher for matching riscv ops from idealized Simple +Sea-of-Nodes. Currently, we are targeting `RVA23U64`. + +### Normal instruction selection + +Works the same way as **X86_64_V2**, since riscv doesn't have *complex* addressing modes, greedy +pattern matching doesn't apply to most of the cases. Ops without any special behavior simply do the lookup. + +### Restricted ISA +RISC-V is a restricted ISA with simple addressing modes and overloads. +E.g `lea` is not present. + + +### Branching +In `x86_64_v2`, branching requires a comparison instruction to set flags, +followed by a jump instruction that uses those flags. +In contrast, RISC-V includes all necessary operands within the +branch instruction itself, eliminating the need for a separate +comparison step. + +E.g +``` +beq x10, x11, some_label +``` + +`CBranchRISC` implements this behavior. +### No R-Flags +No R-flags exist in RiSC-V. To obtain similar functionality: + +We can set the value of registers based on the result of the comparison this way explicitly. +``` +xor a0, a0, a1 +seqz a0, a0 +``` +After the first `xor` - `a0` will be zero if `a0` and `a1` are equal. +The `seqz` instruction will set `a0` to 1 if `a0` is zero from the previous operation. +This matches `SetRISC` in the `nodes/cpus/riscv` port. + +### Fixed instruction length +RISC-V instructions have fixed length of 32 bits(in most cases) which means that we can benefit +from displacements in the encoding side. + +E.g +``` +flw fa5, 0(a0) +flw fa4, 12(a0) +fadd.s fa0, fa5, fa4 +``` +(No load is needed prior to `flw`) + +### ABI names(registers) +In `RISC-V`, general-purpose registers (`GPRs`) range from `x0` to `x31`, and floating-point registers range +from `f0` to `f31`. + +To enhance readability and align with calling conventions, RISC-V defines ABI names for registers, providing more intuitive aliases +instead of raw register numbers. + + + +| Register | Alias | Usage | Saved By | +|----------|-------|------------------------------|----------| +| x10 | a0 | Function arguments/return values | Caller | +| x11 | a1 | Function arguments/return values | Caller | +| x12 | a2 | Function arguments | Caller | +| x13 | a3 | Function arguments | Caller | +| x14 | a4 | Function arguments | Caller | +| x15 | a5 | Function arguments | Caller | +| x16 | a6 | Function arguments | Caller | +| x17 | a7 | Function arguments | Caller | + +When passing in arguments to a function, the first 8 arguments from the caller are passed in registers `a0` to `a7`. + +### Load floats +Currently, floating-point constants are first loaded into an `integer GPR` before being converted into a floating-point register. +This process is rewritten in the RA stage as: + + +```` +lui a0, 262144 +fmv.w.x fa0, a0 +```` +For non-constant values, we use a broader register mask that +supports both GPRs and FPRs. This implementation can be found in: +`nodes/cpus/riscv/LoadRISC`. + + + + + + diff --git a/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java index c48a4162..eb8dd4aa 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -204,7 +204,7 @@ public class CodeGen { // If n is a MachConcrete, then its part of a multi-node expansion. // It does not need instruction selection (already selected!) // but it does need its inputs walked. - if( n instanceof MachConcreteNode || n instanceof MemOpX86 ) { + if( n instanceof MachConcreteNode || n instanceof MemOpX86) { for( int i=0; i < n.nIns(); i++ ) n._inputs.set(i, _instSelect(n.in(i),map) ); return n; diff --git a/chapter19/src/main/java/com/seaofnodes/simple/ListScheduler.java b/chapter19/src/main/java/com/seaofnodes/simple/ListScheduler.java index 18055e19..efca945a 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/ListScheduler.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/ListScheduler.java @@ -41,7 +41,7 @@ public abstract class ListScheduler { } private void computeSingleRDef(CFGNode bb, Node n) { - RegMaskRW rmask = n instanceof MachNode mach ? mach.outregmap().copy() : null; + RegMaskRW rmask = n instanceof MachNode mach && mach.outregmap()!=null ? mach.outregmap().copy() : null; for( Node use : n._outputs ) { // Remote use, so this is a remote def if( use!=null && use.cfg0()!=bb ) _rdef = true; @@ -205,7 +205,7 @@ public abstract class ListScheduler { for( int i=1; i> #"); + _ti.print(sb); + } + + @Override public String op() { return "srai"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraRISC.java new file mode 100644 index 00000000..2d50ceaa --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SraRISC.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +// Right Shift Arithmetic +public class SraRISC extends MachConcreteNode implements MachNode { + + SraRISC(Node sra) {super(sra);} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return riscv.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "sra rd, rs1, rs2" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "sra"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java new file mode 100644 index 00000000..f7ad6c25 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlIRISC.java @@ -0,0 +1,43 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; +import java.lang.StringBuilder; + + +// Right Shift Logical Immediate +public class SrlIRISC extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + SrlIRISC(Node srl, TypeInteger ti) {super(srl); _inputs.pop(); _ti = ti;} + + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return riscv.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "srli dst << #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" >> #"); + _ti.print(sb); + } + + @Override public String op() { return "srli"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlRISC.java new file mode 100644 index 00000000..25d62688 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SrlRISC.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; +import java.util.BitSet; +import java.lang.StringBuilder; + +// Right Shift Logical +public class SrlRISC extends MachConcreteNode implements MachNode { + SrlRISC(Node srli) {super(srli);} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return riscv.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "srl rd, rs1, rs2" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "srl"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java new file mode 100644 index 00000000..9fbd7c12 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StoreNode; + +import java.io.ByteArrayOutputStream; +import java.util.BitSet; + + +// sw rs2,offset(rs1) +public class StoreRISC extends MemOpRISC { + StoreRISC( StoreNode st) { + super(st, st); + } + + @Override public RegMask regmap(int i) { + return riscv.RMASK; + } + + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return null; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { + + } + + @Override public String op() { return "st"+_sz; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubFRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubFRISC.java new file mode 100644 index 00000000..e6a0b8e4 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubFRISC.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class SubFRISC extends MachConcreteNode implements MachNode{ + SubFRISC(Node subf) {super(subf);} + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return riscv.FMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.FMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 0; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Default on double precision for now(64 bits) + // General form: "fsub.d rd = src1 - src2 + @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 op() { return "subf"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubRISC.java new file mode 100644 index 00000000..6fb0e0ef --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SubRISC.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +public class SubRISC extends MachConcreteNode implements MachNode { + SubRISC( Node sub ) { super(sub); } + + // Register mask allowed on input i. + @Override public RegMask regmap(int i) { assert i==1 || i==2; return riscv.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + // Output is same register as input#1 + @Override public int twoAddress() { return 0; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form: "sub # rd = rs1 - rs2" + @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 op() { return "sub"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java new file mode 100644 index 00000000..b508541a --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/TFPRISC.java @@ -0,0 +1,43 @@ +package com.seaofnodes.simple.node.cpus.riscv; + + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.cpus.x86_64_v2.TFPX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; + +import java.io.ByteArrayOutputStream; + +public class TFPRISC extends ConstantNode implements MachNode{ + TFPRISC(ConstantNode con) {super(con);} + // Register mask allowed on input i. 0 for no register. + @Override public RegMask regmap(int i) { return null; } + // General int registers + @Override public RegMask outregmap() { return x86_64_v2.RMASK; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // Human-readable form appended to the SB. Things like the encoding, + // indentation, leading address or block labels not printed here. + // Just something like "ld4\tR17=[R18+12] // Load array base". + // General form: "op\tdst=src+src" + @Override public void asm(CodeGen code, SB sb) { + String reg = code.reg(this); + if( _con == Type.NIL ) + sb.p(reg).p(",").p(reg); + else + _con.print(sb.p(reg).p(" #")); + } + + @Override public String op() { + if( _con == Type.NIL ) + return "xor"; + return "ldx"; // Some fancier encoding + } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java new file mode 100644 index 00000000..3d53ee64 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorIRISC.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +public class XorIRISC extends MachConcreteNode implements MachNode{ + final TypeInteger _ti; + XorIRISC(Node xor, TypeInteger ti) {super(xor); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + assert i==1 || i==2; + + return riscv.RMASK; } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "rd = rs1 ^ imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" ^ #"); + _ti.print(sb); + } + + @Override public String op() { return "xori"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorRISC.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorRISC.java new file mode 100644 index 00000000..2f34529e --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/XorRISC.java @@ -0,0 +1,43 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.MachConcreteNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeInteger; + +import java.io.ByteArrayOutputStream; + +public class XorRISC extends MachConcreteNode implements MachNode { + + XorRISC(Node or) { + super(or); + } + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + assert i==1 || i==2; + return riscv.RMASK; + } + + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return riscv.RMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 0; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: # # rd = rs1 ^ rs2 + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java new file mode 100644 index 00000000..399eebca --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -0,0 +1,329 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.simple.Machine; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.*; +import com.seaofnodes.simple.type.*; + +public class riscv extends Machine{ + @Override public String name() {return "riscv";} + + // Using ABI names instead of register names + public static int ZERO = 0, RA = 1, SP = 2, GP = 3, TP = 4, T0 = 5, T1 = 6, T2 = 7; + public static int S0 = 8, S1 = 9, A0 = 10, A1 = 11, A2 = 12, A3 = 13, A4 = 14, A5 = 15; + public static int A6 = 16, A7 = 17, S2 = 18, S3 = 19, S4 = 20, S5 = 21, S6 = 22, S7 = 23; + public static int S8 = 24, S9 = 25, S10 = 26, S11 = 27, T3 = 28, T4 = 29, T5 = 30, T6 = 31; + + // FP registers + public static int F0 = 32, F1 = 33, F2 = 34, F3 = 35, F4 = 36, F5 = 37, F6 = 38, F7 = 39; + public static int FS0 = 40, FS1 = 41, FA0 = 42, FA1 = 43, FA2 = 44, FA3 = 45, FA4 = 46, FA5 = 47; + public static int FA6 = 48, FA7 = 49, FS2 = 50, FS3 = 51, FS4 = 52, FS5 = 53, FS6 = 54, FS7 = 55; + public static int FS8 = 56, FS9 = 57, FS10 = 58, FS11 = 59, FT8 = 60, FT9 = 61, FT10 = 62, FT11 = 63; + + public static int FLAGS = 64; + + // General purpose register mask: pointers and ints, not floats + public static RegMask RMASK = new RegMask(0b11111111111111111111111111111111); + // Float mask from(ft0–ft11) + public static RegMask FMASK = new RegMask(0b11111111111111111111111111111111); + + // Return single int/ptr register + public static RegMask RET_MASK = new RegMask(A0); + + // Arguments masks + public static RegMask A0_MASK = new RegMask(1L< addf(addf); + case AddNode add -> add(add); + case AndNode and -> and(and); + case BoolNode bool -> cmp(bool); + case CallEndNode cend -> new CallEndNode((CallNode) cend.in(0)); + case CallNode call -> call(call); + case CProjNode c -> new CProjNode(c); + case ConstantNode con -> con(con); + case DivFNode divf -> new DivFRISC(divf); + case DivNode div -> new DivRISC(div); + case FunNode fun -> new FunRISC(fun); + case IfNode iff -> jmp(iff); + case LoadNode ld -> ld(ld); + case MemMergeNode mem -> new MemMergeNode(mem); + case MulFNode mulf -> new MulFRISC(mulf); + case MulNode mul -> mul(mul); + case NewNode nnn -> new NewRISC(nnn); + case OrNode or -> or(or); + case ParmNode parm -> new ParmRISC(parm); + case PhiNode phi -> new PhiNode(phi); + case ProjNode prj -> prj(prj); + case ReadOnlyNode read -> new ReadOnlyNode(read); + case ReturnNode ret -> new RetRISC(ret, ret.fun()); + case SarNode sar -> sra(sar); + case ShlNode shl -> sll(shl); + case ShrNode shr -> srl(shr); + case StartNode start -> new StartNode(start); + case StopNode stop -> new StopNode(stop); + case StoreNode st -> st(st); + case SubFNode subf -> new SubFRISC(subf); + case SubNode sub -> sub(sub); + case ToFloatNode tfn -> i2f8(tfn); + case XorNode xor -> xor(xor); + + case LoopNode loop -> new LoopNode(loop); + case RegionNode region -> new RegionNode(region); + default -> throw Utils.TODO(); + }; + } + + private Node addf(AddFNode addf) { + return new AddFRISC(addf); + } + + private Node add(AddNode add) { + Node rhs = add.in(2); + if( rhs instanceof ConstantNode off && off._con instanceof TypeInteger toff ) { + return new AddIRISC(add, toff); + } + return new AddRISC(add); + } + + private Node and(AndNode and) { + if( and.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) + return new AndIRISC(and, ti); + return new AndRISC(and); + } + + private Node cmp(BoolNode bool) { + Node cmp = _cmp(bool); + return new SetRISC(cmp, bool.op()); + } + + private Node call(CallNode call) { + if( call.fptr() instanceof ConstantNode con && con._con instanceof TypeFunPtr tfp ) + return new CallRISC(call, tfp); + return new CallRRISC(call); + } + + private Node _cmp(BoolNode bool) { + Node rhs = bool.in(2); + + return rhs instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new CmpIRISC(bool, ti) + : new CmpRISC(bool); + } + + private Node con( ConstantNode con ) { + return switch( con._con ) { + case TypeInteger ti -> new IntRISC(con); + case TypeFloat tf -> new IntRISC(con); + case TypeFunPtr tfp -> new TFPRISC(con); + case TypeMemPtr tmp -> new ConstantNode(con); + case TypeNil tn -> throw Utils.TODO(); + // TOP, BOTTOM, XCtrl, Ctrl, etc. Never any executable code. + case Type t -> new ConstantNode(con); + }; + } + + private Node jmp( IfNode iff ) { + // If/Bool combos will match to a Cmp/Set which sets flags. + // Most general arith ops will also set flags, which the Jmp needs directly. + // Loads do not set the flags, and will need an explicit TEST + if( !(iff.in(1) instanceof BoolNode) ) + iff.setDef(1,new BoolNode.EQ(iff.in(1),new ConstantNode(TypeInteger.ZERO))); + return new CBranchRISC(iff, ((BoolNode)iff.in(1)).op()); + } + + private Node or(OrNode or) { + if(or.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new OrIRISC(or, ti); + + return new OrRISC(or); + } + + private Node xor(XorNode xor) { + if(xor.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new XorIRISC(xor, ti); + return new XorRISC(xor); + } + + private Node sra(SarNode sar) { + if( sar.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new SraIRISC(sar, ti); + return new SraRISC(sar); + } + + private Node srl(ShrNode shr) { + if( shr.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new SrlIRISC(shr, ti); + return new SrlRISC(shr); + } + + private Node sll(ShlNode sll) { + if( sll.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) + return new SllIRISC(sll, ti); + return new SllRISC(sll); + } + + private Node sub(SubNode sub) { + return sub.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new AddIRISC(sub, TypeInteger.constant(-ti.value())) + : new SubRISC(sub); + } + + private Node i2f8(ToFloatNode tfn) { + assert tfn.in(1)._type instanceof TypeInteger ti; + return new I2F8RISC(tfn); + } + + private Node prj(ProjNode prj) { + return new ProjRISC(prj); + } + + private Node ld(LoadNode ld) { + return new LoadRISC(ld); + } + + private Node st(StoreNode st) { + return new StoreRISC(st); + } + + private Node mul(MulNode mul) { + return mul.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti + ? new MulIRISC(mul, ti) + : new MulRISC(mul); + } +} + diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java index 4f75edcd..4bb24fa3 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AddFMemX86.java @@ -12,7 +12,7 @@ public class AddFMemX86 extends MemOpX86 { } @Override public RegMask regmap(int i) { - if( i==1 ) return RegMask.EMPTY; // Memory + if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base if( i==3 ) return x86_64_v2.RMASK; // index if( i==4 ) return x86_64_v2.XMASK; // value diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java new file mode 100644 index 00000000..45cf2b22 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class AndX86 extends MachConcreteNode implements MachNode{ + AndX86(Node and) { + super(and); + } + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; } + + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "and dst & #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "and"; } +} + diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java new file mode 100644 index 00000000..55ab90c9 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallEndX86.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.CodeGen; +import com.seaofnodes.simple.RegMask; +import com.seaofnodes.simple.node.CallEndNode; +import com.seaofnodes.simple.node.MachNode; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeFunPtr; +import java.io.ByteArrayOutputStream; + +public class CallEndX86 extends CallEndNode implements MachNode { + final TypeFunPtr _tfp; + CallEndX86( CallEndNode cend ) { + super(cend); + _tfp = (TypeFunPtr)cend.call().fptr()._type; + } + + @Override public String label() { return op(); } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { throw Utils.TODO(); } + @Override public RegMask outregmap(int idx) { + if( idx != 2 ) return null; + return _tfp._ret instanceof TypeFloat ? x86_64_v2.RET_FMASK : x86_64_v2.RET_MASK; + } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + @Override public void asm(CodeGen code, SB sb) { } + + @Override public String op() { return "cend"; } + +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java index 31d303ed..99260a27 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -13,7 +13,7 @@ public class CallRX86 extends CallNode implements MachNode { @Override public RegMask regmap(int i) { return i==_inputs._len ? x86_64_v2.WMASK // Function call target - : x86_64_v2.callInMask(i); // Normal argument + : x86_64_v2.callInMask(tfp(),i); // Normal argument } @Override public RegMask outregmap() { return x86_64_v2.RET_MASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index 9c246c24..b3e3bbe8 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -20,11 +20,12 @@ public class CallX86 extends CallNode implements MachNode { @Override public String label() { return op(); } @Override public RegMask regmap(int i) { - return x86_64_v2.callInMask(i); // Normal argument + return x86_64_v2.callInMask(tfp(),i); // Normal argument } @Override public RegMask outregmap() { return x86_64_v2.RET_MASK; } @Override public String name() { return _name; } + @Override public TypeFunPtr tfp() { return _tfp; } // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java index 2fa7fbb1..ea526f33 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import java.io.ByteArrayOutputStream; -// Compare immediate. Sets flags. +// Compare immediate. Sets flags.(RFLAGS) public class CmpIX86 extends MachConcreteNode implements MachNode { final int _imm; final String _bop; diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java index 6b502249..d8ebb12d 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import java.io.ByteArrayOutputStream; +// Compare. Sets flags.(RFLAGS) public class CmpX86 extends MachConcreteNode implements MachNode { CmpX86( Node cmp ) { super(cmp); } @@ -16,7 +17,7 @@ public class CmpX86 extends MachConcreteNode implements MachNode { throw Utils.TODO(); } - // General form: "add dst += src" + // General form: "cmp reg1, reg2" @Override public void asm(CodeGen code, SB sb) { String dst = code.reg(this); if( dst!="FLAGS" ) sb.p(dst).p(" = "); diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java index 21529f7b..5e1190da 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java @@ -13,7 +13,7 @@ public class FltX86 extends ConstantNode implements MachNode { FltX86(ConstantNode con ) { super(con); } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // General int registers @Override public RegMask outregmap() { return x86_64_v2.XMASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java index f969fae4..8b0f016a 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FunX86.java @@ -10,9 +10,9 @@ public class FunX86 extends FunNode implements MachNode { FunX86( FunNode fun ) { super(fun); } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // Register mask allowed as a result. 0 for no register. - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { return null; } // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java index 2cd27c14..566a7293 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/IntX86.java @@ -16,7 +16,7 @@ public class IntX86 extends ConstantNode implements MachNode { } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // General int registers @Override public RegMask outregmap() { return x86_64_v2.WMASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java index 7cf4444c..2262e847 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java @@ -26,7 +26,7 @@ public class JmpX86 extends IfNode implements MachNode { throw Utils.TODO(); } @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.FLAGS_MASK; } - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { return null; } // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java index 418f63f3..a6cdbd05 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemAddX86.java @@ -11,7 +11,7 @@ public class MemAddX86 extends MemOpX86 { } // Register mask allowed as a result. 0 for no register. - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { return null; } // General form: "add [base + idx<<2 + 12] += src" diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 1e678a0b..b94ea5ae 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -59,7 +59,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { // Register mask allowed on input i. @Override public RegMask regmap(int i) { - if( i==1 ) return RegMask.EMPTY; // Memory + if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base if( i==3 ) return x86_64_v2.RMASK; // index if( i==4 ) return x86_64_v2.RMASK; // value diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java index 7508cf4c..e9eb17fc 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MulIX86.java @@ -12,7 +12,7 @@ public class MulIX86 extends MachConcreteNode implements MachNode { // Register mask allowed on input i. // This is the normal calling convention @Override public RegMask regmap(int i) { - // assert i==1; + assert i==1; return x86_64_v2.WMASK; } // Register mask allowed as a result. 0 for no register. @Override public RegMask outregmap() { return x86_64_v2.WMASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java index 4396a917..f9778845 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NewX86.java @@ -14,7 +14,7 @@ public class NewX86 extends NewNode implements MachNode { // Size if( i==1 ) return x86_64_v2.RDI_MASK; // All the memory alias edges - return RegMask.EMPTY; + return null; } @Override public RegMask outregmap() { throw Utils.TODO(); } @@ -23,7 +23,7 @@ public class NewX86 extends NewNode implements MachNode { @Override public RegMask outregmap(int i) { if( i == 1 ) return x86_64_v2.RET_MASK; // All the memory aliases edges - return RegMask.EMPTY; + return null; } // Encoding is appended into the byte array; size is returned diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java index 513962c2..d3940838 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrIX86.java @@ -19,7 +19,7 @@ public class OrIX86 extends MachConcreteNode implements MachNode { // Register mask allowed on input i. // This is the normal calling convention @Override public RegMask regmap(int i) { - //assert i==1; + assert i==1; return x86_64_v2.WMASK; } // Register mask allowed as a result. 0 for no register. @Override public RegMask outregmap() { return x86_64_v2.WMASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrX86.java new file mode 100644 index 00000000..7c25bdae --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/OrX86.java @@ -0,0 +1,33 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class OrX86 extends MachConcreteNode implements MachNode{ + OrX86(Node or) { + super(or); + } + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; } + + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "and dst & #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "or"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java index 8a439644..0fcc922d 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; import com.seaofnodes.simple.RegMask; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.ParmNode; import com.seaofnodes.simple.node.MachNode; import java.io.ByteArrayOutputStream; @@ -11,11 +9,12 @@ public class ParmX86 extends ParmNode implements MachNode { final RegMask _rmask; ParmX86( ParmNode parm ) { super(parm); - _rmask = x86_64_v2.callInMask(_idx); + // default to int + _rmask = x86_64_v2.callInMask(fun().sig(),_idx); } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // Register mask allowed as a result. Calling convention register @Override public RegMask outregmap() { return _rmask; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java index 2849b232..77fd7d34 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ProjX86.java @@ -12,9 +12,11 @@ public class ProjX86 extends ProjNode implements MachNode { ProjX86( ProjNode p ) { super(p); } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // Register mask allowed as a result. 0 for no register. - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { + return ((MachNode)in(0)).outregmap(_idx); + } // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java index e6219ff4..21db209c 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RetX86.java @@ -21,15 +21,15 @@ public class RetX86 extends ReturnNode implements MachNode { // This is the normal calling convention @Override public RegMask regmap(int i) { return switch( i ) { - case 0 -> RegMask.EMPTY; - case 1 -> RegMask.EMPTY; + case 0 -> null; + case 1 -> null; case 2 -> x86_64_v2.RET_MASK; - case 3 -> RegMask.EMPTY; // RPC is always on stack + case 3 -> null; // RPC is always on stack default -> throw Utils.TODO(); }; } // Register mask allowed as a result. 0 for no register. - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { return null; } // Encoding is appended into the byte array; size is returned @Override public int encoding(ByteArrayOutputStream bytes) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java new file mode 100644 index 00000000..f5337ee8 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java @@ -0,0 +1,37 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import java.io.ByteArrayOutputStream; + +// Arithmetic Right Shift +public class SarIX86 extends MachConcreteNode implements MachNode { + final TypeInteger _ti; + SarIX86(Node sar, TypeInteger ti) {super(sar); _inputs.pop(); _ti = ti;} + + // Register mask allowed on input i. + // This is the normal calling convention + @Override public RegMask regmap(int i) { + // assert i==1; + return x86_64_v2.RMASK; } + // Register mask allowed as a result. 0 for no register. + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "sari dst << #imm" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" >> #"); + _ti.print(sb); + } + + @Override public String op() { return "sari"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java index 3d907eef..cb0b18bf 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarX86.java @@ -8,17 +8,19 @@ import java.io.ByteArrayOutputStream; import java.util.BitSet; import java.lang.StringBuilder; - -public class SarX86 extends MachConcreteNode implements MachNode { - final TypeInteger _ti; - SarX86(Node sar, TypeInteger ti) {super(sar); _inputs.pop(); _ti = ti;} +public class SarX86 extends MachConcreteNode implements MachNode{ + SarX86(Node sar) {super(sar);} // Register mask allowed on input i. // This is the normal calling convention + + // CL register must be used for input(2) @Override public RegMask regmap(int i) { - // assert i==1; - return x86_64_v2.RMASK; } - // Register mask allowed as a result. 0 for no register. + if(i == 1) return x86_64_v2.WMASK; + if(i == 2) return x86_64_v2.RCX_MASK; + throw Utils.TODO(); + } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } // Output is same register as input#1 @@ -30,11 +32,11 @@ public class SarX86 extends MachConcreteNode implements MachNode { } // General form - // General form: "sari dst << #imm" + // General form: "sar dst >> src" @Override public void asm(CodeGen code, SB sb) { - sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" >> #"); - _ti.print(sb); + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); } - @Override public String op() { return "sari"; } + @Override public String op() { return "sar"; } + } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlX86.java new file mode 100644 index 00000000..b95f9f46 --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlX86.java @@ -0,0 +1,39 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class ShlX86 extends MachConcreteNode implements MachNode { + ShlX86(Node shl) { + super(shl); + }; + + // Register mask allowed on input i. + // This is the normal calling convention + + // CL register must be used for input(2) + @Override public RegMask regmap(int i) { + if(i == 1) return x86_64_v2.WMASK; + if(i == 2) return x86_64_v2.RCX_MASK; + throw Utils.TODO(); + } + + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "shl dst << src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "shl"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java index 08cae93e..80115ff2 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java @@ -8,6 +8,7 @@ import java.io.ByteArrayOutputStream; import java.util.BitSet; import java.lang.StringBuilder; +// Logical Right Shift public class ShrIX86 extends MachConcreteNode implements MachNode{ final TypeInteger _ti; ShrIX86(Node shr, TypeInteger ti) {super(shr); _inputs.pop(); _ti = ti;} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrX86.java new file mode 100644 index 00000000..43fc730b --- /dev/null +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrX86.java @@ -0,0 +1,38 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import java.io.ByteArrayOutputStream; + +public class ShrX86 extends MachConcreteNode implements MachNode { + ShrX86(Node shr) { + super(shr); + }; + // Register mask allowed on input i. + // This is the normal calling convention + + // CL register must be used for input(2) + @Override public RegMask regmap(int i) { + if(i == 1) return x86_64_v2.WMASK; + if(i == 2) return x86_64_v2.RCX_MASK; + throw Utils.TODO(); + } + + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + // Output is same register as input#1 + @Override public int twoAddress() { return 1; } + + // Encoding is appended into the byte array; size is returned + @Override public int encoding(ByteArrayOutputStream bytes) { + throw Utils.TODO(); + } + + // General form + // General form: "shr dst >>> src" + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))); + } + + @Override public String op() { return "shr"; } +} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java index c9191b87..734f39de 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java @@ -19,7 +19,7 @@ public class StoreX86 extends MemOpX86 { } // Register mask allowed as a result. 0 for no register. - @Override public RegMask outregmap() { return RegMask.EMPTY; } + @Override public RegMask outregmap() { return null; } // General form: "stN [base + idx<<2 + 12],val" @Override public void asm(CodeGen code, SB sb) { diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java index bd88011f..c7edfcc4 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/TFPX86.java @@ -12,7 +12,7 @@ import java.io.ByteArrayOutputStream; public class TFPX86 extends ConstantNode implements MachNode { TFPX86( ConstantNode con ) { super(con); } // Register mask allowed on input i. 0 for no register. - @Override public RegMask regmap(int i) { return RegMask.EMPTY; } + @Override public RegMask regmap(int i) { return null; } // General int registers @Override public RegMask outregmap() { return x86_64_v2.WMASK; } diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java index 795fa814..d71a49dc 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/XorIX86.java @@ -11,7 +11,7 @@ import com.seaofnodes.simple.type.TypeInteger; import java.io.ByteArrayOutputStream; -public class XorIX86 extends MachConcreteNode implements MachNode { +public class XorIX86 extends MachConcreteNode implements MachNode { final TypeInteger _ti; XorIX86(Node xor, TypeInteger ti) {super(xor); _inputs.pop(); _ti = ti;} diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 45ae19dc..ddb2dcd6 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -28,7 +28,8 @@ public class x86_64_v2 extends Machine { public static RegMask FLAGS_MASK = new RegMask(1L< callInArgSystemV(idx); - case CodeGen.CallingConv.Win64 -> callInArgWin64 (idx); + static int callInArg( TypeFunPtr tfp, int idx ) { + int[] cargs = switch( CodeGen.CODE._callingConv ) { + case CodeGen.CallingConv.SystemV -> CALLINARG_SYSTEMV_INT; + case CodeGen.CallingConv.Win64 -> CALLINARG_WIN64_INT; }; + if( idx < 2 ) return -1; + if( idx >= cargs.length ) + throw Utils.TODO(); // Pass on stack slot + if( tfp.arg(idx-2) instanceof TypeFloat ) + return XMM0 + (idx-2); + return cargs[idx]; } // WIN64(param passing) - static RegMask[] CALLINMASK_WIN64 = new RegMask[] { - RegMask.EMPTY, - RegMask.EMPTY, + static int[] CALLINARG_WIN64_INT = new int[] { + -1, // Control, no register + -1, // Memory, no register + RCX, + RDX, + R08, + R09, + }; + static RegMask[] CALLINARG_WIN64_MASK = new RegMask[] { + null, // Control, no register + null, // Memory, no register RCX_MASK, RDX_MASK, R08_MASK, R09_MASK, - RegMask.EMPTY, - RegMask.EMPTY }; - static int[] CALLINARG_WIN64 = new int[] { - 0, // Control, no register - 0, // Memory, no register - RCX, // - RDX, - R08, - R09, - 0, - 0, - }; - static int callInArgWin64( int idx ) { return CALLINARG_WIN64[idx]; } // caller saved(win64) public static final long WIN64_ABI_CALLER_SAVED = @@ -93,20 +111,9 @@ public class x86_64_v2 extends Machine { // callee saved(win64) public static final long WIN64_ABI_CALLEE_SAVED = ~WIN64_ABI_CALLER_SAVED; - // SystemV(param passing) - static RegMask[] CALLINMASK_SYSTEMV = new RegMask[] { - RegMask.EMPTY, - RegMask.EMPTY, - RDI_MASK, - RSI_MASK, - RDX_MASK, - RCX_MASK, - R08_MASK, - R09_MASK - }; - static int[] CALLINARG_SYSTEMV = new int[] { - 0, // Control, no register - 0, // Memory, no register + static int[] CALLINARG_SYSTEMV_INT = new int[] { + -1, // Control, no register + -1, // Memory, no register RDI, RSI, RDX, @@ -114,8 +121,16 @@ public class x86_64_v2 extends Machine { R08, R09, }; - static int callInArgSystemV( int idx ) { return CALLINARG_SYSTEMV[idx]; } - + static RegMask[] CALLINARG_SYSTEMV_MASK = new RegMask[] { + null, // Control, no register + null, // Memory, no register + RDI_MASK, + RSI_MASK, + RDX_MASK, + RCX_MASK, + R08_MASK, + R09_MASK, + }; // caller saved(systemv) // caller saved(win64) public static final long SYSTEMV_ABI_CALLER_SAVED = @@ -124,15 +139,22 @@ public class x86_64_v2 extends Machine { public static final long SYSTEMV_ABI_CALLE_SAVED = ~SYSTEMV_ABI_CALLER_SAVED; - static RegMask callInMask( int idx ) { - return switch( CodeGen.CODE._callingConv ) { - case CodeGen.CallingConv.SystemV -> CALLINMASK_SYSTEMV[idx]; - case CodeGen.CallingConv.Win64 -> CALLINMASK_WIN64 [idx]; + static RegMask callInMask( TypeFunPtr tfp, int idx ) { + RegMask[] cargs = switch( CodeGen.CODE._callingConv ) { + case CodeGen.CallingConv.SystemV -> CALLINARG_SYSTEMV_MASK; + case CodeGen.CallingConv.Win64 -> CALLINARG_WIN64_MASK; }; + if( idx < 2 ) return null; + if( idx >= cargs.length ) + throw Utils.TODO(); // Pass on stack slot + if( tfp.arg(idx-2) instanceof TypeFloat ) + return XMMS[idx-2]; + return cargs[idx]; } // Create a split op; any register to any register, including stack slots - @Override public Node split() { + @Override + public Node split() { throw Utils.TODO(); } @@ -153,7 +175,7 @@ public class x86_64_v2 extends Machine { case AddNode add -> add(add); case AndNode and -> and(and); case BoolNode bool -> cmp(bool); - case CallEndNode cend -> new CallEndNode((CallNode)cend.in(0)); + case CallEndNode cend -> new CallEndX86(cend); case CallNode call -> call(call); case CProjNode c -> new CProjNode(c); case ConstantNode con -> con(con); @@ -247,7 +269,7 @@ public class x86_64_v2 extends Machine { private Node and(AndNode and) { if( and.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) return new AndIX86(and, ti); - throw Utils.TODO(); + return new AndX86(and); } private Node call(CallNode call) { @@ -315,7 +337,7 @@ public class x86_64_v2 extends Machine { private Node or(OrNode or) { if( or.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) return new OrIX86(or, ti); - throw Utils.TODO(); + return new OrX86(or); } private Node prj( ProjNode prj ) { @@ -324,20 +346,20 @@ public class x86_64_v2 extends Machine { private Node sar( SarNode sar ) { if( sar.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti) - return new SarX86(sar, ti); - throw Utils.TODO(); + return new SarIX86(sar, ti); + return new SarX86(sar); } private Node shl( ShlNode shl ) { if( shl.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) return new ShlIX86(shl, ti); - throw Utils.TODO(); + return new ShlX86(shl); } private Node shr(ShrNode shr) { if( shr.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ) return new ShrIX86(shr, ti); - throw Utils.TODO(); + return new ShrX86(shr); } private Node st( StoreNode st ) { diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter13Test.java index d05fd7d8..005a3dd4 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -127,6 +127,19 @@ return n.i; catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } } + @Test + public void testNullRef4() { + CodeGen code = new CodeGen("-null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + + @Test public void testNullRef5() { + CodeGen code = new CodeGen("return null+42;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); } + } + @Test public void testEmpty() { CodeGen code = new CodeGen( diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java index a4857a01..990c4c32 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -179,6 +179,39 @@ return arg1 * arg; assertEquals("return (mul,(inc,arg),arg);", code._stop.toString()); } + @Test + public void testBasic18() { + CodeGen code = new CodeGen( + """ + int arg1 = arg + 1; + return arg1 << arg; + """); + code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (shl,(inc,arg),arg);", code._stop.toString()); + } + + @Test + public void testBasic19() { + CodeGen code = new CodeGen( + """ + int arg1 = arg + 1; + return arg1 >> arg; + """); + code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (sar,(inc,arg),arg);", code._stop.toString()); + } + + @Test + public void testBasic20() { + CodeGen code = new CodeGen( + """ + int arg1 = arg + 1; + return arg1 >>> arg; + """); + code.parse().opto().typeCheck().instSelect("x86_64_v2", "SystemV").GCM().localSched(); + assertEquals("return (shr,(inc,arg),arg);", code._stop.toString()); + } + @Test public void testToFloat() { CodeGen code = new CodeGen(""" diff --git a/chapter20/Makefile b/chapter20/Makefile index 4c1e1f49..f96cfea3 100644 --- a/chapter20/Makefile +++ b/chapter20/Makefile @@ -53,7 +53,7 @@ endif default: $(default_targets) # Compile just the out-of-date files -$(main_classes): build/classes/main/%class: $(SRC)/%java +$(main_classes): $(CLZDIR)/main/%class: $(SRC)/%java @echo "compiling " $@ " because " $? @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) @@ -64,7 +64,7 @@ $(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes) @javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas) # Base launch line for JVM tests -JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test" +JVM=nice java -ea -cp "$(CLZDIR)/main${SEP}${jars}${SEP}$(CLZDIR)/test" tests: $(default_targets) @echo "testing " $(test_cp) @@ -75,6 +75,14 @@ fuzzer: $(default_targets) @echo "fuzzing " $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +# Build a Simple jar +release: build/release/simple.jar + +# Build a Simple jar +build/release/simple.jar: $(main_classes) $(test_classes) + @echo "jarring " $@ " because " $? + @[ -d $(dir $@) ] || mkdir -p $(dir $@) + @jar cf build/release/simple.jar -C $(CLZDIR)/main . -C $(CLZDIR)/test . -C $(SRC)/$(SIMPLE) . -C $(TST)/$(SIMPLE) . # Launch viewer view: $(main_classes) diff --git a/chapter20/README.md b/chapter20/README.md index d3d0fddd..ae2b9df0 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -1,9 +1,433 @@ # Chapter 20: Graph Coloring Register Allocation -This is a Briggs-Chaitan-Click allocator, and is very similar to the one used +## Some Reading Material + +This is a Briggs-Chaitin-Click allocator, and is very similar to the one used in HotSpot's C2 allocator for the past 25 years with great success. +Wikipedia has a nice overview of register allocation in general: https://en.wikipedia.org/wiki/Register_allocation + +Chaitin's original: https://en.wikipedia.org/wiki/Register_allocation#CITEREFChaitin1982 + +Briggs additions: https://dl.acm.org/doi/10.1145/177492.177575 + +There are several other useful link that can be found by searching for Briggs +or Chaitin in combination. Basically there was a spate of register allocation +improvements in this era that made it into many high-end mainstream compilers. + +I've included a very old unpublished paper on speeding up graph coloring +allocators: [Interference Graph Triming](docs/ifg_trim.pdf). + You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter19...linear-chapter20) it to the previous chapter. -## Registers + +## The Basic Theory + +The reading material includes several explainations of the basic concepts, but +at the risk of being redundant I'll present a short version again here. + +I assume you (the reader) know *why* register allocation is required: machine +registers are a high value finite resource, and as with all finite resources +they need to be allocated well. + +Graph Coloring is one such allocation method; machine registers are treated as +colors; a *live range interference graph* is built, with each *live range* +requiring its own register/color. Coloring the graph ensures every live range +gets a unique register, specificially when it overlaps or *interferes* with +another live range. + +A successful coloring ends the allocation and after some bookkeeping the +program is ready for e.g. code emission. A failed coloring requires spilling +or splitting conflicting live ranges; in this allocator we will be doing live +range *splitting*. Splitting live ranges makes them more colorable; they +become shorter with fewer interfering other live ranges. Generally large +functions might require a few rounds of splitting before becoming colorable. +Since the problem is NP-complete there are no guarantees here, the final +allocation quality becomes heavily dependent on splitting and coloring +heuristics. + +Hence, much of the "high theory" will be used to drive the core coloring +algorithm, but much of the "actual success" will depend on a large collection +of heuristics. + +### Coloring Rounds + +Coloring proceeds in rounds until we get a coloring: + +- Build the Live Ranges; live ranges require the same register for all + instructions in the live range. Phi functions will force unrelated def/use + edges to become part of the same live range and this can drive large + interconnected live ranges with a lot of conflicts. Some hardware ops + require the same register for both inputs and outputs (X86 is notorious here) + which also makes fewer larger live ranges. We'll be using the disjoint + Union-Find algorithm to rapidly build up live ranges in one forward pass over + the program. + +- Build the Inteference Graph: every live range which is alive at the same time + as any other, now *interferes* or conflicts. This is built using a LIVE-ness + pass, which is a backwards pass over the CFG, and can require more than one + pass according to loop nesting depth. The data structure here is generally a + 2-D bitset, triangulated to cut its size in half. As part of LIVE, we'll + also have a set of reaching defs per-block. + +- Color the interference graph. Nodes (live ranges) in the graph which are + strictly low degree (more available registers than neighbors) will guaranteed + get a color. These can be removed from the graph - since they will + guaranteed get a register (color) because they have so few conflicting + neighbors. Removing these trivial nodes makes more nodes go trivial, and + this process repeats until either we run out (and are guaranteed a coloring) + or we find a high-degree clique: a set of mutually interfering live ranges + where none of them are guaranteed a color. In this case we pull an "at risk" + live range out; this one might not color. Once the graph is emptied, we + reverse and re-insert the live ranges, coloring as we go. All the trivial + live ranges will color; the at-risk ones may or may not. + +- If every live range gets a color, then Register Allocation is done. If not, + we enter a round of splitting. Live ranges which did not color are now split + via a series of heuristics into lots of small live ranges. Splitting has a + tension: too much and you got a lot of spills (and a generally poor + allocation). Too little, and you remain uncolorable - and do not make + progress towards an allocation. Once we're done splitting, we start a new + round of coloring (Building the Live Ranges, then the Interference Graph, + then Coloring). + + +## Registers and Register Masks + +Registers are the thing that Register Allocation is all about! They are +represented as a small dense integer, starting up from 0, and the numbering +generally follows from the hardware encodings. So for an X86_64, RAX will be +register 0, RCX register 1 and so on up to the 16 GPRs. The XMM registers at +16 and go up to 32. Register numbers must be unique; this is how the register +allocator tracks them. + +#### Why a RegMask class and not a simple `long`? + +A collection of registers live in a Register Mask. For smaller and simpler +machines it suffices to make such masks an i64 or i128 (64 or 128 bit +integers), and this presentation is by far the better way to go... if all +register allocations can fit in this bit limitation. The allocator will need +bits for stack-based parameters and for splits which cannot get a register. +For a 32-register machine like the X86, add 1 for flags - gives 33 registers. +Using a Java `long` has 64 bits, leaving 31 for spills and stack passing. This +is adequate for nearly all allocations; only the largest allocations will run +this out. However, if we move to a chip with 64 registers we'll immediately +run out, and need at least a 128 bit mask. Since you cannot *return* a 128 +bit value directly in Java, Simple will pick up a `RegMask` class object. + +#### Stack Slots + +One of the Click extensions is this notion of treating "stack slots" are Just +Another Register. They get colored like other registers, which in turn leads +to very efficient use of the stack; C2 is known for having very small stack +frames. Another benefit is callee save registers will get split preferentially +(they have very long lifetime and only one def on entry and one use on +exit)... which the splits then end up coloring to the stack, building the call +prolog and epilog naturally. This allocator will not otherwise dedicate any +effort to stack frame management; it will "fall out in the wash". + +Many of the register masks are immutable; e.g. allowed registers for particular +opcodes, or describing registers for calling conventions. Other masks +represent mutable bitsets with the allocator routinely masking off bits when +accumulating a set of constraints. To help keep these uses apart, the +`RegMask` class includes mutable and immutable variants. + + +### Callee/Caller Save Registers + +In this allocator, callee- and caller-save registers get almost no special +treatment and no special prolog nor epilog is built to save and restore them. +At the start of the allocator, SoN graph edges are added between each `Return` +and a `CalleeSave` from each `Fun`. These edges are given register masks +pinning them to the callee-save set as defined by the normal ABI. + +Callee-save live ranges thus have a single def (a `CalleeSave` at function +start) and a single use (the `Return`), are cheap to spill and free a register +over a large area - they make ideal spill candidates. When the allocator needs +to spill something to get some more registers, these will be the first to +spill. A prolog and epilog will get built as a consequence of the normal live +range splitting process. + +`Calls` kill the caller-save registers (just the inverted callee-save mask), +and this is computed during the normal interference graph building process just +like any other operation that kills registers. Killing a bunch of registers at +a call typically removes all the free registers from whatever is currently +alive - and will thus force spilling... which will quickly end up spilling +callee-save registers as ideal candidates. + + +## Live Ranges + +A live range is a set of nodes and edges which must get the same register. +Live ranges form an interconnected web with almost no limits on their shape. +Live ranges also gather the set of register constraints from all their parts. + +Live ranges are held in `LRG` class instances. Most of the fields in this +class are for spill heuristics, but there are a few key ones that define what a +LRG is. `RegAlloc` has several functions dealing with LRGs, including a lookup +table from Nodes i.e., a mapping from `Node` to `LRG` (which is very similar to +having a dedicated LRG field in each Node... except that LRGs are only used +during RegAlloc and the field would be dead weight otherwise). + +LRGs have a unique dense integer `_lrg` number which names the LRG. New `_lrg` +numbers come from the `RegAlloc._lrg_num` counter. LRGs can be unioned +together - +[this is the Union-Find algorithm](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) +- and when this happens the lower numbered `_lrg` wins. Unioning only happens +during `BuildLRG` and happens because either a `Phi` is forcing all its inputs +and outputs into the same register, or because of a 2-address instruction. +LRGs have matching `union` and `find` calls, and a set `_leader` field. + +Post-allocation the `LRG._reg` field holds the chosen register. During +allocation the `LRG._mask` field holds the set of available registers, +typically all the defaults, minus various conflicts. + +The `LRG._adj` holds a list of adjacent neighbors as part of the larger +Interference Graph, and is only used during the Coloring phase. +[See more about graphs here.](https://en.wikipedia.org/wiki/Graph_(abstract_data_type)) +This is a "adjacency list" form of a Graph description, and is built from the +IFG's 2-D collection of bits (itself a 1-D list of `BitSet`s). Graph coloring +register allocation is one of the few places where changing the layout of a +data structure mid-algorithm pays out. + +The rest of the fields are dedicated to various spilling heuristics: + +- `_machDef` `_machUse` `_uidx` - A sample def and use. +- `_splitDef` `_splitUse` - Sample splits involved with this LRG; biased + coloring attempts to align register choices to remove these. +- `_selfConflicts` - A partial set of *self-conflicting* nodes. These are + detected during the Interference Graph build phase, and require aggressive + splitting. +- `_1regDefCnt` `_1regUseCnt` - Count of defs and uses which are pinned to a + single register. These typically require a hard-split just before (use) or + after (def) to free up the register choices. +- `_killed` - LRG lost all registers due to an op killing its available + registers; commonly happens to LRGs which span a `Call` and generally + requires splitting some callee-save live range (spilling a callee-save + register) and move the LRG into the now available register. + + +## Live Ranges and Conflicts + +If the live range `_mask` field goes empty, you might have a *hard conflict* or +have gotten *killed*. Live ranges can self-interfere, making a +*self-conflict*. During coloring you might discover an uncolorable clique of +interfering live ranges, leading to a *capacity spill*. This leads to a set of +levels of conflicts within a live range (and thus a different heuristics for +handling them). + +### Hard-Conflicts + +A live range can have a *hard confict*: conflicting register requirements, +leading to no valid register choices. The obvious case is an incoming +parameter fixed in e.g. `rdx` but also required as an exit value in `rax`. You +can't pick both registers at once, so a split is required. During the build +live ranges phase, every register constraint from every def and use are AND'd +together; the `RegMask` might lose all valid registers, or remain with just a +handful of register choices. + +Hard-conflicts are usually found while build live ranges, and will trigger a +round of splitting before building the interference graph or coloring. They +can also be found during interference graph building, generally caused by a +1-register kill. + +### Avoiding interferences + +Once of the Click extensions to the Briggs-Chaitin allocator is to take +advantage of register constraints to lower the interference graph degree (which +otherwise becomes an O(n^2) edge collection). If a live range LR1 is reduced +to a single register (such as a call argument requiring `rdx`) and would +otherwise conflict with another live range LR2 which has more choices - we +remove `rdx` from the LR2's choices. Without having `rdx`, LR1 and LR2 have no +registers in common - and hence do not conflict. We just don't add the +interference graph edge between them. Call argument restrictions are very +common and this kind of edge-removal can dramatically shrink the O(n^2) edge +collection - and hence speedup allocation by a large constant factor. + +### Self-Conflicts + +A live-range can *self-conflict* be alive twice with 2 different values but +require the same register. This live range *must* split and thus picks up a +copy from the split. This happens with loop-carried dependencies as seen in +e.g. a simple `fib` program: + +```java + int x=1, y=1; + while( true ) { + tmp = x + y; + y = x; + x = tmp; + }; + +``` + +In SoN SSA form: +```java + int x0 = 1, y0 = 1; + while( true ) { + x1 = phi(x0,x2); + y1 = phi(y0,x1); + x2 = x1 + y1; + } +``` + +The variables `x0,x1,x2,y0,y1` all form part of the same live range, since they +are all joined by `Phis`. However, `x1` and `y1` hold different values from +different iterations of `fib`. The SSA form does not have a copy, but the +register-allocated form - just like the original code - DOES require a copy. + +Self-conflicts are found during building the interference graph, and will +trigger a round of splits before attempting the coloring phase. + + +## Coloring Heuristics + +Both register coloring and register splitting are full of heuristics, and the +quality of these heuristics goes a long way to deciding the quality of the +final allocation. Graph coloring is NP-complete; there is no efficient +algorithm for coloring and many programs are simply not colorable without +splitting in any case. + + +### Biased Coloring + +Biased coloring is a heuristic that attempts to "pick a better color" or "bias +the color choice", such that a Split is removed. A Split splits one live range +into two; sometimes some are inserted that are not required (i.e., over- +splitting has already happened). If one side (live range) of a split is +already colored and we can color the other side (live range) the same color - +then this split can be removed. If neither side is colored, but one or the +other side is recursively connected to a colored live range, we can still bias +the color in the hopes that a chain of splits will all get the same color and +thus all get removed. + +When the coloring process is reversing, and colors are being picked for live +ranges, we often have many register choices. A first choice is made +arbitrarily (lowest numbered register), and then we go looking for a better +color. Biased coloring inspects first a sample def (if there is only one, then +the One Def is inspected), and then a sample use. Inspection looks to see if +"the other side" of a split is already colored; if so, and that color is +available it is choosen. If there is a split, but it is not colored - we +recursively repeat the process on that split's other side. This is also done +for the other input of two-address ops and one of a Phi node inputs. + +In all cases, the goal is to pick a valid available color - that might also +eventually be pick-able for this Split's other side - and lead to this split +having the same color for both sides, and then being removed. + + +### Pick Risky + +Here we are forced to pick one of several *live ranges* that form a large +clique: they have too many mutual neighbors so that no one of them is +guaranteed a color. There is a conflicting tension here: + +Picking a live range with a large "area" (i.e. covering much of the program), +and low "cost" to spill (i.e. fewer defs and uses, and outside of loops) will +give a large win. A register will become free over a large part of the program +and allow coloring to success elsewhere. The normal ABI callee-save registers +are ideal in this case, defined on entry and used only on exit they cover the +entire program. Also, spilling means only a single split on entry and another +at exit. Spilling such live ranges basically builds a classic function +prolog/epilog sequence. Here though, the allocator is allowed to e.g. spill +outside a fast-path exit. + +``` + // No registers saved if the initial RDI is null + test rdi + jne BIG_AND_SLOW + xor rax,rax + ret // Fast path exit: null argument means null result +BIG_AND_SLOW: + add rsp,#12 + mov [rsp+0],rbx // begin spilling callee-save registers + mov [rsp+4],r12 // + // lots of code needing callee-save registers +``` + +The other side of the tension is to pick live ranges that are likely to color +more by chance. If a live range is "very nearly colorable" - say only one more +neighbor than available registers/colors then by chance (and Biased Coloring) +some neighbors might use the same color... freeing up a color and allowing this +risky live range to color after all. + + +## Splitting + +Here we failed to get a coloring - and need to split. Some specific live +ranges did not color and we will need to decide how to split. Again there are +tensions here: too much splitting leads to a bad allocation, to little leads to +no-progress bugs (manifested as too many rounds of splitting past some +arbitrary cutoff). + +We start by looking at each spilling live range in turn, and deciding +on a splitting strategy. + + +### Split Self Conflict + +Self-conflict live ranges are discovered during the "Build the Interference +Graph" stage. If this happens we don't attempt a coloring (its nonsensical +with self conflicts), but go straight to splitting. During the IFG building we +gathered a subset of the conflicting definitions for this live range. Now +we visit all those definition points and insert spills: + +- Before slot #1 on a Phi (which breaks loop-entry Phis from the loop-body) and + also after the Phi. +- Before a two-address instruction, breaking the live range before the op from + afterwards. +- Before any use that extends a live range. + +This set of splits is fairly aggressive... but test cases requiring a split in +each of the listed locations are including in Chapter 20's test cases. We +cannot even attempt a color while we have self conflicts, so its important to +break up these live ranges quickly. This tends to over-split and the allocator +leans on Biased Coloring to remove some of the extras. + + +### Split Hard Conflict + +Hard conflicts are discovered during the "Build the Live Ranges" pass for +direct def/use conflicts (e.g. defined in `rdi` and used in `rax`). They also +can be discovered during the "Build the Interference Graph" pass (e.g. incoming +argument in `rdi` used later in the program and killed by a `Call`). + +For simple hard-conflicts, we have the exact def and use kept in the Live Range +itself. We split once after the def and once before the use (and only on sides +with restricted registers). + +For more complex cases we use the capacity spilling/loop-nest technique. + + +### Split By Loop Nest + +Here we typically see capacity spills: we just need more registers. This +easily happens when a `Call` crushes all the temporary registers and we need to +carry some values past the call - but it can also happen any time we have a +larger function with lots of things going on at once. + +The heuristic here is to split *around* loops, attempting to keep some free +registers available so the hot loop body does not spill. Live ranges are split +into successively deeper loop nests in progressive rounds of splitting, and in +the final case will split once after each def and before each use, even in the +innermost loop. + +The heurstic starts by discovering the min and max loop depth for all defs and +uses. If these vary, we will split *around* the outermost loop, putting in +splits at the loop border and keeping an inner untouched live range that has no +constraints from outside. If this fails to color, on the next round of +splitting the outermost loop will have moved in one layer, and we will be +splitting around the next inner loop nest. This process repeats until we end +up splitting in the inner-most loops. + + +## Post Allocation + +After a successful coloring, we want to pull out any same-same register splits. +A quick pass over the splits and after checking registers, we pull out the +useless splits (and track the rest for "scoring" our allocation). We'll also +bypass some split-after-splits, which can remove some redundant copying. + +The registers remain available in the `RegAlloc` object via `alloc.regnum( Node n )` +and will be used by a following instruction encoding pass. \ No newline at end of file diff --git a/chapter20/docs/ifg_trim.pdf b/chapter20/docs/ifg_trim.pdf new file mode 100644 index 00000000..d952fd4f Binary files /dev/null and b/chapter20/docs/ifg_trim.pdf differ diff --git a/chapter20/docs/pardoe.docx b/chapter20/docs/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/chapter20/docs/pardoe.docx differ diff --git a/chapter20/src/main/java/com/seaofnodes/simple/ASMPrinter.java b/chapter20/src/main/java/com/seaofnodes/simple/ASMPrinter.java deleted file mode 100644 index 5cc13210..00000000 --- a/chapter20/src/main/java/com/seaofnodes/simple/ASMPrinter.java +++ /dev/null @@ -1,140 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.SB; -import com.seaofnodes.simple.type.TypeFunPtr; -import com.seaofnodes.simple.type.TypeMem; -import com.seaofnodes.simple.type.TypeRPC; - -public abstract class ASMPrinter { - - public static SB print(SB sb, CodeGen code) { - if( code._cfg==null ) - return sb.p("Need _cfg set, run after GCM"); - - // instruction address - int iadr = 0; - for( int i=0; i