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

diff --git a/chapter19/docs/index.html b/chapter19/docs/index.html
new file mode 100644
index 00000000..06e19e2c
--- /dev/null
+++ b/chapter19/docs/index.html
@@ -0,0 +1,218 @@
+<!DOCTYPE html style="height: 100%; margin:0">
+<meta charset="utf-8">
+<title>Simple Viewer</title>
+<script src="d3.v7.min.js"></script>
+<script src="graphviz.umd.js"></script>
+<script src="d3-graphviz.js"></script>
+
+<body style="height: 100%; margin:0">
+
+  <div style="display:flex; flex-flow:column; height: 100%;">
+    <div style="position:fixed; top:0; left:0; height:20%; width:30%;" >
+      <div align="center" >Simple Program:</div>
+      <textarea
+        id="program"
+        autofocus="true"
+        name="Program"
+        defaultValue="return 0;"
+        ></textarea>
+    </div>
+    <div id="fill" style="flex: 1 1 auto"> </div>
+    <div id="graph" style="flex: 0 1 auto; align-self:center;"> </div>
+
+    <div style="display:flex; flex-flow:row; flex: 0 1 auto; align-self:center;">
+      <style>
+        .button { color:white; background-color:black; font-size:20px; min-width:30px }
+      </style>
+      <button id="doPrev" type="button" onclick="doPrev()" class="button">&#11164;</button>
+      <div id="N"   style="font-size: 20px; border-style: ridge; min-width: 50px; text-align: right; padding-right: 10px;">0</div>
+      <button id="doNext" type="button" onclick="doNext()" class="button">&#11166;</button>
+      <div id="len" style="font-size: 20px;                      min-width: 50px; text-align: right; padding-right: 10px;">0</div>
+      <button id="doExit" type="button" onclick="doExit()" class="button">Exit</button>
+    </div>
+  </div>
+
+
+<script>
+
+  var _timer;    // Shutdown timer if server goes silent
+  var N=0 ;      // Which dot/graph is being displayed
+  var dots=[];   // An array of DOT strings
+  var done;      // No more DOTs from server
+  // Graphviz renderer
+  var graphviz = d3.select("#graph").graphviz()
+      .transition(function () {
+          return d3.transition("main")
+              .ease(d3.easeLinear)
+              .delay(0)
+              .duration(500);
+      });
+
+  // Websocket.  :-P
+  const socket = new WebSocket("ws://localhost:12345");
+
+  // Read user program
+  const DOC_PROG = document.getElementById('program');
+  // Default value seems to be ignored???
+  DOC_PROG.value="return 0;";
+  function get_program() {
+    console.log("get_program");
+    var src = DOC_PROG.value;
+    console.log(src);
+    // Reset visualizer state before sending
+    updateN(0);
+    dots=[];
+    done=false;
+    // Send program; will start getting DOT frames shortly
+    socket.send(src);
+    // Once the program is sent, timer starts
+    _timer = setTimeout("close()",100000)
+  };
+  DOC_PROG.onchange=get_program;
+
+  // Go forwards in the animation
+  function doNext() {
+    updateN(N+1);
+    if( N < dots.length ) {
+      render(N-1,N,1);
+    } else {
+      N = dots.length;
+      socket.send("+"); // Block awaiting server next frame
+    }
+  }
+
+  // Go back in the animation
+  function doPrev() {
+    if( N>0 ) {
+      updateN(N-1);
+      if( N < dots.length-1 ) {
+        render(N+1,N,-1);
+      }
+    }
+  }
+
+  // exit
+  function doExit() { socket.send(null); close(); };
+
+  // Update step counter display and buttons
+  function updateN(newN) {
+    N = newN;
+    DOC_PREV = document.getElementById("doPrev");
+    DOC_NEXT = document.getElementById("doNext");
+
+    if( N==0 && !DOC_PREV.disabled ) {
+      DOC_PREV.disabled = true;
+      DOC_PREV.style.backgroundColor = "grey";
+    }
+    if( N>0 && DOC_PREV.disabled ) {
+      DOC_PREV.disabled = false;
+      DOC_PREV.style.backgroundColor = "black";
+    }
+    if( N <dots.length && DOC_NEXT.disabled ) {
+      // Indicate stall, no next frame from server
+      DOC_NEXT.textContent = "\u2B9E";
+      DOC_NEXT.disabled = false;
+      DOC_NEXT.style.backgroundColor = "black";
+    }
+    if( N==dots.length && !DOC_NEXT.disabled ) {
+      // Indicate stall, no next frame from server
+      DOC_NEXT.textContent = "...";
+      DOC_NEXT.disabled = true;
+      DOC_NEXT.style.backgroundColor = "grey";
+    }
+    document.getElementById("N")  .textContent = N==dots.length ? (">"+(N-1)) : N;
+    document.getElementById("len").textContent = dots.length;
+  };
+
+
+  // Render an animation, from idx to end by step.
+  // 'end' is inclusive.
+  var renderActive = -1;
+  function render(idx, end, step) {
+    old = renderActive;
+    renderActive = (end+step);
+    // No active, so start rendering
+    if( old == -1 )
+      _rend(idx,end+step,step);
+  }
+  // Render an animation in a 'for' loop of frames
+  // until we hit the end.  Looping is done via callbacks.
+  // end is exclusive.
+  var aix = -1; // Last DOT rendered
+  function _rend(idx,end,step) {
+    // Skip animation if already rendered/showing on screen
+    if( idx==aix ) _rendNext(idx,end,step);
+    else {
+      aix = idx;
+      var str = dots[idx].indexOf("// POS: ");
+      console.log(str);
+      if( str == -1 ) DOC_PROG.setSelectionRange(0,0);
+      else {
+        var pos = Number(dots[idx].substring(str+8,str+12));
+        console.log(pos,pos+1);
+        document.getElementById("program").focus();
+        document.getElementById("program").setSelectionRange(pos,pos+1);
+      }
+      graphviz.renderDot(dots[idx]).on("end", () => _rendNext(idx,end,step))
+    }
+  }
+  function _rendNext(idx,end,step) {
+    // Not at end so...
+    if( idx+step != end )
+      // Render next step
+      _rend(idx+step,end,step);
+    else {
+      // All desired frames rendered
+      if( renderActive == end ) {
+        renderActive = -1; // all frames done
+      } else {
+        // Skip-a-few and render the last asked for
+        _rend(renderActive-1,renderActive,1)
+      }
+    }
+  };
+
+
+  socket.onopen = () => { console.log('WebSocket connection opened'); };
+
+  // receive message from server; either a shutdown or a new graph
+  socket.onmessage = (event) => {
+    clearTimeout(_timer);  _timer=null;
+    const dot = event.data;
+    console.log("Received:", dot.substring(0,40));
+
+    if( dot == "!" ) {
+      // Server requests client resets
+      get_program();
+
+    } else if( dot == "#" ) {
+      // Server sent final frame
+      done = true;
+
+    } else if( dot.startsWith("digraph") ) {
+      // Received a new graph
+      dots.push(dot);
+      //console.log(dot);
+      updateN(N);
+      socket.send("+"); // Get another frame
+      // If at-end, receiving a graph immediately renders
+      if( dots.length==1 )
+        graphviz.renderDot(dots[0]);
+      else if( N+1 == dots.length )
+        render(N-1,N,1);
+      // After render, hang around until user clicks things
+      console.log("GRAPHVIZ done; N="+N+"; dots="+dots.length);
+
+    } else {
+      console.error('Server sent unexpected: ',dot);
+      get_program();
+    }
+  };
+
+  socket.onclose = () => { close(); }
+  socket.onerror = (error) => {
+    console.error('WebSocket error:', error);
+  };
+
+</script>
+</body>