From 34e7282dd7c58b49702c7ecd9f80a46398efd0c1 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 7 Feb 2025 08:58:36 -0800 Subject: Ch19 (#155) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * 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 * 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 * 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 * 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. * 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 --------- Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- chapter19/README.md | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 93 insertions(+) create mode 100644 chapter19/README.md (limited to 'chapter19/README.md') diff --git a/chapter19/README.md b/chapter19/README.md new file mode 100644 index 00000000..1e2074cf --- /dev/null +++ b/chapter19/README.md @@ -0,0 +1,93 @@ +Ch# 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. + + +## Portable Compilation + +A new abstract `Machine` class is added, one per unique CPU port. `Machine` +defines a name for the port, names for all registers, and how to generate +machine Nodes from *ideal* Nodes. `Machine` also allows generating *split* ops +and *jumps*, both used by the machine independent compiler parts during +code-gen. + +A new CallingConv enum is added, to allow picking between various calling conventions. + +## The Instruction Selection Phase + +A new *InstructionSelection* compile phase is added before *Global Code +Motion*. It is optional, but will replace the *ideal* Nodes with machine- +specific variants. Instruction selection is called with the target CPU name; +the porting code is looked up and used then. This allows the Java +implementation at least the ability to add CPU ports lazily. + + +## Machine Specific Nodes + +We add a notion of "machine specific" Nodes, which implement the `Mach` +interface. `Mach` nodes define incoming and outgoing registers for every +instruction, their bit encodings and user representations. Later we'll add +function unit information for a better local schedule. + + +## Clean up CodeGen compile driver + +More static globals move into the CodeGen object, which is passed around at all +the top level drivers. It's not passed into the Node constructors, hence not +into the idealize() calls, which remains the majority of cases needing a static +global. In short the compiler gets a lot more functional, and a big step +towards concurrent or multi-threaded compilation. + + + +## Registers and Register Masks + +`Machines` define registers as small dense integers. The Register Allocator +will use these numbers when allocating. The mappings from small integers to +machine registers is up to the porter, but there's usally an obvious +one-to-one. For the X86, 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. + +A `RegMask` Register Mask class holds onto bitsets of allowed registers. Most +machine ops are limited to some subset of all registers, and the allowed sets +are written as a RegMask. Most RegMasks are immutable, e.g. the set of allowed +registers into a `Mul` operation, but the register allocator will make +extensive use of mutable register sets. + +Calling conventions dictate many fixed registers, and in practice tend to +really "bind up" the set of allowed registers. + + +## An X86_64_V2 port, with SystemV or Win64 calling conventions + +In the `node/cpus/x86_64_v2` directory is a `x86_64_v2.java` port to an X86 64 +V2. This port supports 16 64-bit GPRs, 32 XMM registers and the X86 flags. +There is a pattern matcher for matching X86 ops from idealized Simple +Sea-of-Nodes. Except for the addressing modes pattern matcher matches nearly +one-for-one X86 ops from ideal nodes. + +### Normal instruction selection + +The instSelect phase walks the ideal graph, and maintains a mapping +from ideal-to-machine ops. It does a greedy pattern match, first come first +match. Ops without any special behavior simply do the local lookup e.g. an +`Mul` exactly matches to an X86 `MulX86` directly. The RHS of most matches can +be an immediate constant, matching an immediate-flavored version (`MulIX86`). + +### Addressing Modes + +For many X86 operations, if one of the inputs is a `Load`, the X86 can use an +op-from-memory variant. There's a specific `address()` call in the X86 matcher +that looks for the various kinds of addressing modes and will build memory- +specific variations. These all need to be called out specifically, but with a +simple one-line match and one-line allocation of the memory version. + +### Compare vs Jmp + +In simple, a `BoolNode` produces a `0/1` value. On an X86 this is done with +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 -- cgit v1.2.3