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, 19 insertions, 2 deletions

diff --git a/chapter11/README.md b/chapter11/README.md
index 7c84e083..2a1c3903 100644
--- a/chapter11/README.md
+++ b/chapter11/README.md
@@ -1,5 +1,24 @@
 # Chapter 11: Global Code Motion
 
+# Table of Contents
+
+1. [High Level Overview](#high-level-overview)
+2. [Scheduling Walk Through](#scheduling-walk-through)
+3. [Scheduling a Loop](#scheduling-a-loop)
+4. [Components of the Global Code Motion Algorithm ](#components-of-the-global-code-motion-algorithm)
+5. [Identification of Basic Blocks in SoN graph](#identification-of-basic-blocks-in-son-graph)
+6. [Handling Infinite Loops](#handling-infinite-loops)
+7. [Dominators](#dominators)
+8. [Loop depth](#loop-depth)
+9. [Early Schedule](#early-schedule)
+10. [Late Schedule](#late-schedule)
+11. [Inserting Anti Dependencies](#inserting-anti-dependencies)
+12. [Video Walk Through](#video-walk-through)
+
+
+You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter11) 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-chapter10...linear-chapter11) it to the previous chapter.
+
+
 The original input source program defines a sequence in which things happen. As we parse the program into Sea of Nodes representation
 and perform various optimizations, this sequence is not fully maintained. The optimized Sea of Nodes graph is driven more
 by dependencies between nodes rather that the sequence of instructions in the original source program.
@@ -16,8 +35,6 @@ differences compared to the version described in the paper.
 
 Since this is a complex topic, we will present a high level summary first and then delve into the details.
 
-You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter11) 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-chapter10...linear-chapter11) it to the previous chapter.
-
 ## High Level Overview
 
 The Sea of Nodes graph has two virtual graphs within it.