From fc7d2bce649854982a3c16de164bbaafec11bc27 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Tam=C3=A1s=20Hadh=C3=A1zy?= <85063808+Hels15@users.noreply.github.com> Date: Sat, 5 Apr 2025 19:38:40 +0100 Subject: Ch20 encoding (#194) * 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 * READMEs * Update README.md * Update README.md * Move printing into print dir * Move codegen into codegen * Framework for Reg Alloc * riscv init * added not imm form bitwise shifts and ops plus test cases * addressing modes(high chance it'll get deleted) * First cut BuildLRG RegMask.EMPTY -> null * fix minor bug * Setup for first simple split * First cut split code for mismatch regs * delete non existing matches * replace RegMask.Empty with null * 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. * riscv handle store and load, fltRisch uses risc reg now * load float into GPR and then later in RA do hard split. * minor changes * Next cut regalloc Building IFG. Coloring. Some nested spilling Optimize divf/con -> mul times inverse * turn off ch20 tests * Update Chapter20Test.java * 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 * add riscv port to readme * arm init * 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 * work in progress * README updates * Fix ch19 mis-merge? * x86 call args, risc5 load/store regs * arm2 bs * Push RISC WMASK avoid writing to RSP * work in progress * clearnup arm * 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 * fixed main pr problems * regmask extra comments * 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. * encoding init * encoding init 2 * rex fix * indirect addressing modes * setop change opcode, rename FLOAT_OFFSET * mask sib and modrm with 3 bits, 4th bit goes into rex. * sign extend div with cqo * idiv input is fixed to rax and RMASK, grab input from second slot when encoding * encoding of newx86 * tfp and CallEndNode encoding * sib improvement * more cleanups * more cleanups * 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 * fixed order of operands * base rex fixup * more bug fix * remove jukn files * minimal "make release" * further fixes * minor fixes * minor fixes * minor fixes * base != -1 check, precedence fix * 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 * 64 bit encoding for gpr(s) load * 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 * 8 bit imm support * conditional jump fix * Push l,ast change, unbreak branch * XOR remove extra opcode, imm size supports 8 bit. * 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 * 64 bit imm for alu ops encoded in extra reg then use it in Op as an operand * Bunch of minor arm, risc fixes small constants not cloning * jump invert encoding * warning comment * 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 * better split encoding and fix CallInMask * notNode * fix callInMask * riscv init * riscv basic ALU ops and types of instructions * 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 * riscv indirect addressing and function calls * Cleanup call ABI presentation Everybody uses the same names, same code shapes * Caller save regs ...not callee save yet * Expose caller save regs * Store Risc adjustments, no imm in MemOpRISC * specific print encoding for cpus * merge fixup * 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 * lui fix up with 32 bit immediates * 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 * added flags splitting * 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 * extend test cases * imm encoding, flags fixed * grep for Todo: relocs * float riscv fixed * flags for set * lui fix for small bits [0, 12] * arm init * arm last touches * fmov still needs fix * minor fixes * minor fixes(2) * got rid of unnecessary stuff * create ch21 * remove encodings from chapter20 dir * 1/2 pass cleaning up ARM encoding API * ARM encoding compiles * Risc R_TYPE and I_TYPE * Progress RISC encodings Missing lots of stuff still * progress risc encoding * Bring back `make view` * risc encodings compile * Update README.md * Fold up redundant OP/OP-FP risc5 encoding * x86 mem opcodes first cut break out MemOp encodings into parts; change x86 indirectAdr to use Encoding class, remove redundant asserts & code * x86 mem op encodings * x86 reg+imm forms * most reg-reg forms * More x86 encodings * Last few encodings * switch to binary literals over decimals for opcodes * logical immediates fixed, bitwise ops imm forms * tfp and setArm fixed * PC relative float for riscv * readme init * Merged pr/169 * Fixed the array1 test encodings Clean up branch invert logic during BB layout Cleanup branch target printing for RISC,ARM ImmRISC ops mask imm12 to 12 bits Fix NewRISC; hardcode RPC as part of call Fix RISC inverting branchs >,>= * floatarm encoding * tfparm and intarm * uncontional jump encoding for arm and riscv * smarter IntARM, Intx86 does not always include rex. * REX after PREFIX * fixup load and store indirect * updated rex prefix, if its 0x40 then its not needed * Rex fix for floats, got rid of unnecessary stuff. * rename to camel case, better param name * add test export * merged * store opt * store and load optimised forms handled * tfp patch * Store/load float arm/riscv/x64 * got rid of debug print * splits for x86, riscv and arm * readme fixups * Create ASimpleReply.md * Update ASimpleReply.md * Update ASimpleReply.md * Update ASimpleReply.md * Update ASimpleReply.md * Update ASimpleReply.md * fix global symbol numbering for constants * ASimpleReply setup * fix TFP pathc on arm and riscv, keep symbols in good order. * fix opcode for store and loads, memOpRisc for Store and splitting * replace hard coded opcodes with major opcodes * Update README.md * replace hard coded opcodes with major opcodes * Fix some formatting (#184) * Fix title in chapter 19 * Wrap nseted scope images onto newlines in chapter 3 * add asserts and fix reg numbering * add asserts and fix reg numbering * minor updates * revert changes * remove constant pool from encoder TODO: add flag for JIT * extend test cases * minor fixes * minor fixes * update float test case --------- Co-authored-by: Cliff Click Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> --- ASimpleReply.md | 70 ++++++++++++++++++++++ ASimpleReply/ASimpleReply2.md | 29 +++++++++ ASimpleReply/ASimpleReplyChain.md | 31 ++++++++++ chapter03/README.md | 8 ++- chapter19/README.md | 2 +- chapter20/Makefile | 2 +- .../java/com/seaofnodes/simple/print/JSViewer.java | 2 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 7 ++- .../com/seaofnodes/simple/codegen/ElfFile.java | 56 ++++++++++++++--- .../com/seaofnodes/simple/codegen/Encoding.java | 5 ++ .../seaofnodes/simple/node/cpus/riscv/SetRISC.java | 4 +- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 3 +- .../simple/node/cpus/x86_64_v2/FltX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SarIX86.java | 35 +++++++++-- .../simple/node/cpus/x86_64_v2/ShlIX86.java | 36 +++++++++-- .../simple/node/cpus/x86_64_v2/ShrIX86.java | 31 ++++++++-- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 35 +++++------ .../com/seaofnodes/simple/progs/newtonFloat.smp | 12 ++-- 18 files changed, 313 insertions(+), 57 deletions(-) create mode 100644 ASimpleReply.md create mode 100644 ASimpleReply/ASimpleReply2.md create mode 100644 ASimpleReply/ASimpleReplyChain.md diff --git a/ASimpleReply.md b/ASimpleReply.md new file mode 100644 index 00000000..b208658f --- /dev/null +++ b/ASimpleReply.md @@ -0,0 +1,70 @@ + +A Simple Reply to https://www.reddit.com/r/Compilers/comments/1jjldhu/land_ahoy_leaving_the_sea_of_nodes/ + +Because reddit crashes when I try to post this. + +## prolog +I kept quiet for awhile on this one, as any response I make is going to sound either defensive or mis-aligned, and in some sense that's right. Also chat/email/IRC are terrible places to hold in-depth tech discussions. But I've had quite a number of people rise up to the defense of SoN both here and in other forums, so I finally decided to join the fray. :-P +Looking at the design choices, it seems clear to me that V8 hobbled itself from the start. V8 made a number of choices leading to a number of problems which in my mind have obvious fixes. + +## Effects +*Equivalence class aliasing* is a powerful tool, and a key part of SoN. It appears to me that V8 threw this away from the start, and then spent the next several years dealing with its lack. + +#### "Too many nodes on the effects chain" +Equivalence class aliasing comes for free, literally free, in any strongly typed language. It comes directly out of the parser (be it JVM bytecodes, Simple, C), and need not be ever touched again. With it, Java/Simple/C have very sparse and clean effects chains. Definitely not "too many". + +JS is *not* strongly typed, so there's an engineering tradeoff being made. I was under the belief that V8 (and other JS engines) used *specialization* aggressively to bring back strong typing in code regions; in those areas again ECA should just work directly. + +#### "Managing the effect and control chains manually is hard" +Equivalence class aliasing is *directly* represented in SoN, as just normal nodes and edges. There's no special handling for it anywhere, the normal graph maintenance functions manipulate those nodes and edges just the same as they do anything else. Two nodes that might alias directly have connecting edges, nodes that do not - do not, and hence *cannot* be influenced about what happens in other alias classes. +As result of those two observations (free to obtain from strong typing, normal node/edge maintenance) this form of effect handling is been vastly simpler to build and maintain, and vastly faster to use than any other compiled I've ever worked on - and that's quite a few. 25yrs of C2 on Java shows that it can be very effective for performance and plenty fast in a JIT. + +Me thinks V8 did itself no favors here. + +## Control on Effect nodes +Guard tests for correctness: either null checks on fields or range checks on arrays. Perhaps for JS (and certainly C2/Java) also some type/specialization checks. C2 also adds a control edge to guard effect nodes. These then get optimized away (controlling edge removed) in one of two generic ways: + +(1) *Lattice*: For null and type checks there is a Node `Type` which includes things like null-ness or sub-classing. Not-null pointers are known not-null based on the type; null checks against them constant-fold, etc. (The `Types` form a *lattice* with strong properties like symmetric, complete, bounded (ranked), and *meet* is commutative and associative.) + +After a guarding test we can lift the type - using a Cast tied to the guard test, where the Cast does a lattice *join* (not *meet*). Effect nodes that need that guard pick up the Cast on the base pointer - not the control edge. If, later, we prove the Cast's *join* is useless e.g. `_t.join(in(1)._type)==_t`, the Cast constant folds away, and the effect Node can now float more freely. This analysis (comes as part of the normal c-prop) removes > 90% of Java's casting needs. + +(2) The other generic test is range-checks, which start life as a direct control edge dependency. These generally do not trivially fold away - something with all constant sizes and array indices might, but mostly no. Then C2 runs *Range Check Elimination*, a special pass just for Java safe arrays, and removes dynamically nearly all of them. I would expect to see the same come from any serious safe-language optimization. + +## Debugging +Yeah, don't use graphs to debug. Use normal ASCII dumps like the ones being shown in this article. That's what *I* do anyways. Certainly I didn't have access to fast easy graph layouts back when C2 started, I just debugged it "the normal way". +Graphs are nice for intuition but they don't scale well. That being said I've seen more recent successes in getting better graphs-for-debug scenarios (don't use D3, sucks on cycles, dump to a file; file watcher picks up and refreshes window, keep graph window visible aside of editor, etc). Maybe I'll revisit this, but for now, for me, ASCII dumps rule. + +## Complex schedule +The Click thesis scheduler missed out on anti-dependencies. C2 - and then the easier to read Simple Chapter 10 corrected this. The algorithm is fast and simple enough, no more complex than e.g. the natural loop finding version of SCC. Source code is available from Simple. + +### Late arriving control flow from expanding small "diamonds" +Yup, same solution for C2; I kept things like `min` or `max` as single pure nodes. At some late point in the game they expanded. For things as trivial as `min` which does NOT need any internal registers - I expanded them in the encoding phase post RA. For more complex things, I expanded them just after Global Code Motion brought me back to an official CFG. + +In any case, this problem (and its solution) seem... trivial to me. Doesn't carry much weight on the IR choice argument; each IR has its issues all will need dozens of such "fixes". + +## Visitation order + +#### "Finding a good visitation order is hard" +Yes, so don't bother. Use a worklist! Hard guaranteed linear time to completion, fast and simple. Back-edges are needed and they are well worth the cost. I start C2 without them, couldn't get closure with a few passes, added backedges and everything got lots *faster*. Edge maintenance code deals with the work, so I don't have to think about it, its all cache-resident L1 hits. Fast, fast, fast. + +## Other things? + +#### "Dead code elimination" +free with backedges; basically when the backedge/ref-count drops to zero, recursively delete nodes. There's maybe 10 lines dedicated to this in Simple. + +#### "Hard to introduce new control flow" +Hello compiler writers? Sorry, can't hardly believe this one; editing a CFG is morally the same as editing the SoN, what's the issue? In the specific `min` case, the goal is to pick a place in the CFG to expand... which means a place needs to be picked, which for SoN usually means after Global Code Motion when "places" (e.g. classic CFG) is available again. + +#### "Hard to figure out what's inside a loop" +Again, Hello compiler writers? C2 certainly does lots of aggressive loop optimizations - which start by running a standard SCC, finding loop headers, walking the graph area constrained by the loop, producing a loop body for further manipulations... yada yada. Basically, I build loops and a loop tree via the Olde Fashioned method of running SCC. + +#### "Compiling is slow" +Compiling is fast. He-said-She-said. Neen-neener. Data? Perf discussions with facts? Apples to apples comparisons? No? So how about "compilation speed vs code quality didn't meet our goals"? + +#### "Cache-unfriendly" +Same (lack of) argument. Certainly when I did C2 I was highly focused on cache-friendly and based on the vast compile speedup I obtained over all competitions (at that time every AOT compiler, GCC, LLVM) I was largely successful. C2 compiles take far less footprint (both cache and memory) that my "competitors". Mostly C2 compiles, despite aggressive inlining, fit easily in L2, nearly always in L1. Getting this right is important, so I suspect other things happened to make it miss for V8. But also... no numbers from me either, so neen-neener again. + +## postlog +I'll point out most of the above discussion is things that surely made V8's life harder - and slower - and are things I never would have done. OTOH I've not done a JS compiler, so I have no facts here also. + +Cliff diff --git a/ASimpleReply/ASimpleReply2.md b/ASimpleReply/ASimpleReply2.md new file mode 100644 index 00000000..62f1a5ba --- /dev/null +++ b/ASimpleReply/ASimpleReply2.md @@ -0,0 +1,29 @@ +# A Simple Reply (2) + +Hi Dadals, we got to stop meeting like this. + +The whole reply chain: + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReplyChain.md + +I find long, involved, multi-part discussions difficult to follow because +basically we're really having 8 unrelated technical discussions. I broke up my +replies so each part is easier to consider on its own. + + +# Reply - Using t effect chains based on equivalence classes + +# Reply - "Guard tests for correctness" + +# Reply - "Graphs are nice for intuition but they don't scale well." + +# Reply - "Use a worklist!" +I think we agree, at least in theory, here. + +# Reply - Late arriving control flow from expanding small "diamonds" + +# Reply - "Data? Perf discussions with facts? Apples to apples comparisons? No?" + +# Reply - Hard to introduce new control flow + +# Reply - It's easy in Simple diff --git a/ASimpleReply/ASimpleReplyChain.md b/ASimpleReply/ASimpleReplyChain.md new file mode 100644 index 00000000..2d53a8ee --- /dev/null +++ b/ASimpleReply/ASimpleReplyChain.md @@ -0,0 +1,31 @@ +# A Simple Reply ... Chain + +Hi Dadals, we got to stop meeting like this. + +### Original message: + +https://v8.dev/blog/leaving-the-sea-of-nodes +https://www.reddit.com/r/Compilers/comments/1jjldhu/land_ahoy_leaving_the_sea_of_nodes/ + +### Cliff's Reply: + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply.md + +### Dadal's Reply: + +https://gist.github.com/DadaIsCrazy/8ce07d409f8f74bad7b36e74b77a3129 + +### Cliff's Reply(2): + +(first, this reply-chain to gather all the parts) + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReply2.md + + + +[room for more conversations] + +No conversations here, its just the chain. + +Cliff + diff --git a/chapter03/README.md b/chapter03/README.md index 35075e7e..ddb9fafa 100644 --- a/chapter03/README.md +++ b/chapter03/README.md @@ -167,10 +167,12 @@ scope and deeper indices representing more nested scopes. Popping returns the current scope and moves to the outer one. There is a direct one-to-one mapping between each index and its corresponding scope. -The first nested scope(04-08) +The first nested scope(04-08): + ![Graph4](./docs/03-graph4.svg) -The second nested scope(09-13) +The second nested scope(09-13): + ![Graph5](./docs/03-graph5.svg) - In both cases the index which represents the deepness of the scope is 1. @@ -192,4 +194,4 @@ The graph for above, is displayed below. ![Graph2](./docs/03-graph3.svg) The return node has the constant `8` as its data value! When the parsing ends -and the scope at level 0 is removed, only the `return 8` remains. \ No newline at end of file +and the scope at level 0 is removed, only the `return 8` remains. diff --git a/chapter19/README.md b/chapter19/README.md index 87a4c3a6..a866876d 100644 --- a/chapter19/README.md +++ b/chapter19/README.md @@ -1,4 +1,4 @@ -Ch# Chapter 19: Instruction Selection and Portable Compilation +# Chapter 19: Instruction Selection and Portable Compilation You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19) 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-chapter18...linear-chapter19) it to the previous chapter. diff --git a/chapter20/Makefile b/chapter20/Makefile index f96cfea3..c5d8fa71 100644 --- a/chapter20/Makefile +++ b/chapter20/Makefile @@ -87,7 +87,7 @@ build/release/simple.jar: $(main_classes) $(test_classes) # Launch viewer view: $(main_classes) @echo "viewing " - @$(JVM) com.seaofnodes.simple.JSViewer + @$(JVM) com.seaofnodes.simple.print.JSViewer .PHONY: clean clean: diff --git a/chapter20/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/chapter20/src/main/java/com/seaofnodes/simple/print/JSViewer.java index 76c64c71..a2b674c9 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/print/JSViewer.java @@ -72,7 +72,7 @@ public class JSViewer implements AutoCloseable { public static void show() { if( SERVER!=null && SHOW ) _show(); } private static void _show() { // Skip util we at least get the Parse object made - if( CODE._phase==null || CODE._phase.ordinal() < CodeGen.Phase.Parse.ordinal() ) + if( CODE._phase == null ) return; boolean midParse = CODE._phase == CodeGen.Phase.Parse; Stack xScopes = midParse ? CODE.P._xScopes : null; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 64ea8201..f5d32dd2 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -308,16 +308,21 @@ public class CodeGen { // --------------------------- // Encoding public int _tEncode; + public boolean _JIT; public Encoding _encoding; - public CodeGen encode() { + public CodeGen encode(boolean jit) { assert _phase == Phase.RegAlloc; _phase = Phase.Encoding; long t0 = System.currentTimeMillis(); _encoding = new Encoding(this); + _JIT = jit; _encoding.encode(); _tEncode = (int)(System.currentTimeMillis() - t0); return this; } + public CodeGen encode() { + return encode(false); + } // Encoded binary, no relocation info public byte[] binary() { return _encoding.bits(); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 223911ba..62bcfcde 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -228,6 +228,30 @@ public class ElfFile { } } + public final HashMap _bigCons = new HashMap<>(); + private void encodeConstants(SymbolSection symbols, DataSection rdata) { + int cnt = 0; + for (Map.Entry e : _code._encoding._bigCons.entrySet()) { + if (_bigCons.get(e.getValue()) != null) { + continue; + } + + Symbol glob = new Symbol("GLOB$"+cnt, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); + glob._value = rdata._contents.size(); + symbols.push(glob); + + Type t = e.getValue(); + if ( t instanceof TypeFloat tf ) { + write8(rdata._contents, Double.doubleToLongBits(tf._con)); + } else { + throw Utils.TODO(); + } + + glob._size = rdata._contents.size() - glob._value; + _bigCons.put(e.getValue(), glob); + cnt++; + } + } public void export(String fname) throws IOException { DataSection strtab = new DataSection(".strtab", 3 /* SHT_SYMTAB */); // first byte is reserved for an empty string @@ -253,6 +277,8 @@ public class ElfFile { // populate function symbols encodeFunctions(symbols, text); + // populate big constants + encodeConstants(symbols, rdata); int idx = 1; for( Section s : _sections ) { @@ -267,8 +293,9 @@ public class ElfFile { int num = 1; for( Symbol s : symbols._loc ) s._index = num++; + // extra space for .rela.text int start_global = symbols._loc.size(); - for(Symbol a: symbols._symbols) + for(Symbol a: symbols._symbols) { a._index = start_global++; // create .text relocations @@ -276,16 +303,31 @@ public class ElfFile { for( Node n : _code._encoding._externals.keySet()) { int nid = n._nid; String extern = _code._encoding._externals.get(n); - if(!extern.isEmpty()) throw Utils.TODO(); - // Todo: fix this up later when external functions will be in TU - //int sym_id = _funcs.get(extern)._index; - int sym_id = 0; + + Symbol sym = new Symbol(extern, 0, SYM_BIND_GLOBAL, SYM_TYPE_NOTYPE); + sym._index = start_global++; + symbols.push(sym); + + int offset = _code._encoding._opStart[nid] + _code._encoding._opLen[nid] - 4; + + // u64 offset + write8(text_rela._contents, offset); + // u64 info + write8(text_rela._contents, ((long)sym._index << 32L) | 4L /* PLT32 */); + // i64 addend + write8(text_rela._contents, -4); + } + + // relocations to constants + for (Map.Entry e : _code._encoding._bigCons.entrySet()) { + int nid = e.getKey()._nid; + int sym_id = _bigCons.get(e.getValue())._index; int offset = _code._encoding._opStart[nid] + _code._encoding._opLen[nid] - 4; // u64 offset write8(text_rela._contents, offset); // u64 info - write8(text_rela._contents, ((long)sym_id << 32L) | 4L /* PLT32 */); + write8(text_rela._contents, ((long)sym_id << 32L) | 2L /* PC32 */); // i64 addend write8(text_rela._contents, -4); } @@ -295,7 +337,7 @@ public class ElfFile { text_rela._info = text._index; pushSection(text_rela); - Symbol sym = new Symbol(text_rela._name, idx++, SYM_BIND_LOCAL, SYM_TYPE_SECTION); + Symbol sym = new Symbol(text_rela._name, num, SYM_BIND_LOCAL, SYM_TYPE_SECTION); sym._name_pos = text_rela._name_pos; sym._size = text_rela.size(); symbols.push(sym); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 0f9aac89..f90ce96a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -151,9 +151,14 @@ public class Encoding { // Record opcode start and length. writeEncodings(); + // ELF handles big constants, they + // are accessed by RIP-relative addressing. + + if(_code._JIT) writeConstantPool(true); // Short-form RIP-relative support: replace long encodings with short // encodings and compact the code, changing all the offsets. compactShortForm(); + } // Basic block layout: invert branches to keep blocks in-order; insert diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java index 636c5a5f..8d4a2f71 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SetRISC.java @@ -4,7 +4,7 @@ import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; -// corresponds to slt (and NOT sltu, slti, sltiu) +// corresponds to slt sltu public class SetRISC extends MachConcreteNode implements MachNode { final boolean _unsigned; public SetRISC( Node cmp, boolean unsigned ) { super(cmp); _unsigned=unsigned; } @@ -12,7 +12,7 @@ public class SetRISC extends MachConcreteNode implements MachNode { @Override public RegMask regmap(int i) { return riscv.RMASK; } @Override public RegMask outregmap() { return riscv.WMASK; } @Override public void encoding( Encoding enc ) { - riscv.r_type(enc,this,_unsigned ? 0b011 : 0x010,0); + riscv.r_type(enc,this,_unsigned ? 0b011 : 0b010,0); } @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))); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java index f6f3474f..921fa336 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java @@ -15,13 +15,14 @@ public class CmpMemX86 extends MemOpX86 { @Override public void encoding( Encoding enc ) { // REX.W + 81 /7 id CMP r/m64, imm32 | REX.W + 39 /r CMP r/m64,r64 // CMP [mem], imm32 + short ptr = enc.reg(ptr()); short idx = enc.reg(idx()); short src = enc.reg(val()); enc.add1(x86_64_v2.rex(src, ptr, idx)); // opcode varies by immediate - enc.add1( src == -1 ? 0x39 : 0x81 ); + enc.add1( src == -1 ? 0x81 : 0x39); // includes modrm x86_64_v2.indirectAdr(_scale, idx, ptr, _off, src == -1 ? 7 : src, enc); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java index 708269bd..c9df7b99 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/FltX86.java @@ -4,7 +4,7 @@ import com.seaofnodes.simple.SB; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; -public class FltX86 extends ConstantNode implements MachNode, RIPRelSize { +public class FltX86 extends ConstantNode implements MachNode, RIPRelSize{ private byte _encSize; FltX86(ConstantNode con ) { super(con); } @Override public String op() { return "ld8"; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java index d6c977a5..6d6aa89c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SarIX86.java @@ -1,12 +1,39 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; +import com.seaofnodes.simple.SB; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.codegen.RegMask; +import com.seaofnodes.simple.node.MachNode; import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.*; + // Arithmetic Right Shift -public class SarIX86 extends ImmX86 { - SarIX86( Node add, int imm ) { super(add,imm); assert x86_64_v2.imm8(imm); } +public class SarIX86 extends MachConcreteNode implements MachNode { + final int _imm; + SarIX86( Node sari, int imm ) { super(sari); assert x86_64_v2.imm8(imm); _inputs.pop(); _imm = imm; } @Override public String op() { return "sari"; } @Override public String glabel() { return ">>"; } - @Override int opcode() { return 0xC1; } - @Override int mod() { return 7; } + int opcode() { return 0xC1; } + int mod() { return 7; } + + @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + @Override public void encoding(Encoding enc) { + short dst = enc.reg(this); // Also src1 + enc.add1(x86_64_v2.rex(0, dst, 0)); + enc.add1( opcode()); + + enc.add1( x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, mod(), dst) ); + + // immediate(4 bytes) 32 bits or (1 byte)8 bits + if( x86_64_v2.imm8(_imm) ) enc.add1(_imm); + else enc.add4(_imm); + } + + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" ").p(glabel()).p("= #").p(_imm); + } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java index 35818a91..c53e0ea9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShlIX86.java @@ -2,10 +2,38 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; import com.seaofnodes.simple.node.Node; -public class ShlIX86 extends ImmX86 { - ShlIX86( Node add, int imm ) { super(add,imm); } +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; + +public class ShlIX86 extends MachConcreteNode implements MachNode { + final int _imm; + ShlIX86( Node shli, int imm ) { + super(shli); + assert x86_64_v2.imm8(imm); + _inputs.pop(); // Pop constant input off + _imm = imm; + } + public int opcode() { return 0xC1; } + public int mod() { return 4; } + + @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + @Override public String op() { return "shli"; } @Override public String glabel() { return "<<"; } - @Override int opcode() { return 0xC1; } - @Override int mod() { return 4; } + @Override public void encoding(Encoding enc) { + short dst = enc.reg(this); // Also src1 + enc.add1(x86_64_v2.rex(0, dst, 0)); + enc.add1( opcode()); + + enc.add1( x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, mod(), dst) ); + + // immediate(4 bytes) 32 bits or (1 byte)8 bits + if( x86_64_v2.imm8(_imm) ) enc.add1(_imm); + else enc.add4(_imm); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" ").p(glabel()).p("= #").p(_imm); + } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java index 0e96962b..c79b8817 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ShrIX86.java @@ -2,10 +2,33 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; import com.seaofnodes.simple.node.Node; -public class ShrIX86 extends ImmX86 { - ShrIX86( Node add, int imm ) { super(add,imm); } +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; + +public class ShrIX86 extends MachConcreteNode implements MachNode { + final int _imm; + ShrIX86( Node shri, int imm ) { super(shri); assert x86_64_v2.imm8(imm); _inputs.pop(); _imm = imm; } @Override public String op() { return "shri"; } @Override public String glabel() { return ">>>"; } - @Override int opcode() { return 0xC1; } - @Override int mod() { return 5; } + int opcode() { return 0xC1; } + int mod() { return 5; } + + @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + + @Override public void encoding(Encoding enc) { + short dst = enc.reg(this); // Also src1 + enc.add1(x86_64_v2.rex(0, dst, 0)); + enc.add1( opcode()); + + enc.add1( x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, mod(), dst) ); + + // immediate(4 bytes) 32 bits or (1 byte)8 bits + if( x86_64_v2.imm8(_imm) ) enc.add1(_imm); + else enc.add4(_imm); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" ").p(glabel()).p("= #").p(_imm); + } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 39048f2d..bf8f92ad 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -146,31 +146,24 @@ public class x86_64_v2 extends Machine { public static void indirectAdr( int scale, short index, short base, int offset, int reg, Encoding enc ) { // Assume indirect assert 0 <= base && base < 16; - assert index != RSP; + assert -1 <= index && index < 16 && index != RSP; MOD mod = MOD.INDIRECT; // is 1 byte enough or need more? if( offset != 0 ) mod = imm8(offset) - ? MOD.INDIRECT_disp8 - : MOD.INDIRECT_disp32; + ? MOD.INDIRECT_disp8 + : MOD.INDIRECT_disp32; - // needs to pick optimal displacement mod if we want to encode base - // when we only have base = RSP then we still need displacement added so ti becomes: [RSP+RSP*1+0x0] - // RSP as index in this case is special and refers to: [base + disp8] - if( mod == MOD.INDIRECT && (base == RBP || base == R13) ) + if( mod == MOD.INDIRECT && (base == RBP || base == R13) ) { mod = MOD.INDIRECT_disp8; + } else if( index == -1 && (base == RSP || base == R12) ) { + index = RSP; + } - // special encoding for [base +offset] if( index == -1 ) { - // Case for mov reg, [disp] (load) - enc.add1(modrm(offset == 0 ? MOD.INDIRECT_disp8 : mod, reg, x86_64_v2.RSP)); - enc.add1(sib(scale, x86_64_v2.RSP, base)); - // special case - // still add zero it is part of SIB byte - if(offset == 0) enc.add1(offset); + enc.add1(modrm(mod, reg, base)); } else { - // rsp is hard-coded here(0x04) enc.add1(modrm(mod, reg, x86_64_v2.RSP)); enc.add1(sib(scale, index, base)); } @@ -592,20 +585,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 SarIX86(sar, (int)(ti.value() & 0x03f) ); + if( sar.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm8(ti.value())) + return new SarIX86(sar, (int)(ti.value() & 0xff) ); 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, (int)(ti.value() & 0x03f) ); + if( shl.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm8(ti.value())) + return new ShlIX86(shl, (int)(ti.value() & 0xff) ); 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, (int)(ti.value() & 0x03f) ); + if( shr.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm8(ti.value()) ) + return new ShrIX86(shr, (int)(ti.value() & 0xff) ); return new ShrX86(shr); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp index b41fc26e..50419959 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp +++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp @@ -1,11 +1,11 @@ // -*- mode: java; -*- // Newtons approximation to the square root -val sqrt = { flt x -> - flt epsilon = 1e-57; - flt guess = x; - while( 1 ) { +val test_sqrt = { flt x -> + flt epsilon = 1e-57; + flt guess = x; + while( 1 ) { flt next = (x/guess + guess)/2; if( guess-epsilon <= next & next <= guess+epsilon ) return guess; guess = next; - } -}; + } +}; \ No newline at end of file -- cgit v1.2.3