Ch19 (#155)

* 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 <cliffc@acm.org>

* 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 <cliffc@acm.org>

* 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 <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

1 files changed, 93 insertions, 0 deletions

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