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, 203 insertions, 0 deletions

diff --git a/chapter19/docs/lattice.gv b/chapter19/docs/lattice.gv
new file mode 100644
index 00000000..8661082d
--- /dev/null
+++ b/chapter19/docs/lattice.gv
@@ -0,0 +1,203 @@
+digraph Lattice {
+    compound = true;
+    // Define nodes
+    splines=false;
+    node [shape=circle, style=filled];
+    nodesep=0.2;
+    ranksep=0.2;
+
+    TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white];
+    BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white];
+
+    // ----------------------
+    // Control
+    XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval];
+    CTRL  [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval];
+
+    TOP   -> XCTRL;
+    XCTRL -> CTRL;
+    CTRL  -> BOT;
+
+    // ----------------------
+    // Integers
+    INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval];
+    INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval];
+
+    INT_HI    [label="[min>max]" , fillcolor=lightblue, shape=oval];
+    INT_XBOOL [label="[1...0]", fillcolor=lightblue, shape=oval];
+    INT_CON   [label="constants", fillcolor=lightblue, shape=oval];
+    INT_CON0  [label="0", fillcolor=lightblue];
+    INT_CON1  [label="1", fillcolor=lightblue];
+    INT_BOOL  [label="[0...1]", fillcolor=lightblue,shape=oval];
+    INT_LO    [label="[min<max]" , fillcolor=lightblue, shape=oval];
+
+    TOP        -> INT_TOP;
+    INT_TOP    -> INT_HI;
+    INT_HI     -> INT_XBOOL;
+    INT_XBOOL  -> INT_CON0;
+    INT_XBOOL  -> INT_CON1;
+    INT_HI     -> INT_CON;
+    INT_CON0   -> INT_BOOL;
+    INT_CON1   -> INT_BOOL;
+    INT_BOOL   -> INT_LO;
+    INT_CON    -> INT_LO;
+    INT_LO     -> INT_BOT;
+    INT_BOT    -> BOT;
+
+    INT_CON0 -> INT_CON1 -> INT_CON [style=invis];
+
+    // ----------------------
+    // Floats
+    FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval];
+    FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval];
+
+    FLT_CON64  [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval];
+    FLT_CON32  [label="32b consts", fillcolor=aqua, shape=oval];
+    FLT_CONPI  [label="3.14159...", fillcolor=aqua, shape=oval];
+    FLT_X32    [label="~f32", fillcolor=aqua];
+    FLT_CON0   [label="0."  , fillcolor=aqua];
+    FLT_32     [label="f32" , fillcolor=aqua];
+
+    TOP       -> FLT_TOP;
+    FLT_TOP   -> FLT_CON64
+    FLT_TOP   -> FLT_CONPI
+    FLT_CON64 -> FLT_BOT
+    FLT_CONPI -> FLT_BOT
+    
+    FLT_TOP   -> FLT_X32;
+    FLT_X32   -> FLT_CON0;
+    FLT_X32   -> FLT_CON32;
+    FLT_CON0  -> FLT_32;
+    FLT_CON32 -> FLT_32;
+    FLT_32    -> FLT_BOT
+    
+    FLT_BOT   -> BOT;
+
+    FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis];
+
+
+    // ----------------------
+    // Pointers, just a boolean nil/not and a struct
+    PTR  [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TR><TD BGCOLOR="green"><FONT color="white">*ptr</FONT></TD></TR>
+        <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+      </TABLE>
+    >];
+    PTR0  [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TR><TD BGCOLOR="green"><FONT color="white">*ptr?</FONT></TD></TR>
+        <TR><TD BGCOLOR="lightgreen">struct</TD></TR>
+      </TABLE>
+    >];
+    
+    TOP  -> PTR;
+    PTR  -> PTR0;
+    PTR0 -> BOT;
+
+    // ----------------------
+    // Structs
+    STRUCT_TOP    [label=<<B>⊤</B >:struct>, fillcolor=lightgreen, shape=oval];
+    STRUCT_BOT    [label=<<B>⊥</B>:struct>, fillcolor=lightgreen, shape=oval];
+
+    STRUCT_S1  [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+      </TABLE>
+    >];
+    STRUCT_S2  [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+        <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+      </TABLE>
+    >];
+    STRUCT_SN  [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+        <TR><TD BGCOLOR="lightgreen">...  </TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+        <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR>
+      </TABLE>
+    >];
+
+
+    TOP          -> STRUCT_TOP;
+    STRUCT_TOP   -> STRUCT_S1;
+    STRUCT_TOP   -> STRUCT_S2;
+    STRUCT_TOP   -> STRUCT_SN;
+    STRUCT_S1    -> STRUCT_BOT;
+    STRUCT_S2    -> STRUCT_BOT;
+    STRUCT_SN    -> STRUCT_BOT;
+    STRUCT_BOT   -> BOT;
+
+    STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis];
+
+    // ----------------------
+    // Memory
+    MEM_TOP       [label=<<B>⊤</B >:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+    MEM_BOT       [label=<<B>⊥</B>:mem>, fillcolor=blue, fontcolor=white, shape=oval];
+    MEM_ALIAS1    [label="#1"     , fillcolor=blue, fontcolor=white];
+    MEM_ALIASDOTS [label="..."    , fillcolor=blue, fontcolor=white, shape=oval];
+    MEM_ALIASN    [label="#n"     , fillcolor=blue, fontcolor=white];
+
+    TOP          -> MEM_TOP;
+    MEM_TOP      -> MEM_ALIAS1;
+    MEM_TOP      -> MEM_ALIASDOTS;
+    MEM_TOP      -> MEM_ALIASN;
+    MEM_ALIAS1   -> MEM_BOT;
+    MEM_ALIASDOTS -> MEM_BOT;
+    MEM_ALIASN    -> MEM_BOT;
+    MEM_BOT       -> BOT;
+
+    MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis];
+
+    // ----------------------
+    // Tuples
+
+    TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval];
+    TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval];
+
+    TUPLE1 [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+        <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+      </TABLE>
+    >];
+    TUPLE2 [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+        <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+        <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+      </TABLE>
+    >];
+    TUPLEN [shape=none, fillcolor=none, label=<
+      <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
+        <TH><TD BGCOLOR="pink">Tuple</TD></TH>
+        <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+        <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR>
+        <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR>
+      </TABLE>
+    >];
+
+
+    TOP -> TUPLE_TOP;
+    TUPLE_TOP -> TUPLE1;
+    TUPLE_TOP -> TUPLE2;
+    TUPLE_TOP -> TUPLEN;
+    TUPLE1 -> TUPLE_BOT;
+    TUPLE2 -> TUPLE_BOT;
+    TUPLEN -> TUPLE_BOT;
+    TUPLE_BOT -> BOT;
+
+    // ----------------------
+    // Additional customization
+    {rank=same; TOP;}
+    {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP}
+    {rank=same; INT_CON; INT_CON0; INT_CON1;
+                FLT_CON32; FLT_CON64;  FLT_CON0; FLT_CONPI;
+                STRUCT_S1; STRUCT_S2; STRUCT_SN;
+                MEM_ALIAS1;  MEM_ALIASDOTS; MEM_ALIASN;
+                TUPLE1; TUPLE2; TUPLEN;
+    }
+    {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT}
+    {rank=same; BOT;}
+}