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, 260 insertions, 10 deletions

diff --git a/chapter14/README.md b/chapter14/README.md
index a08499d1..496cbb8c 100644
--- a/chapter14/README.md
+++ b/chapter14/README.md
@@ -1,11 +1,25 @@
 # Chapter 14: Narrow types
 
+# Table of Contents
+
+1. [Narrow Word Types](#narrow-or-sub-word-types)
+2. [OverFlow handling](#overflow-handling)
+3. [Integer ranges](#integer-ranges)
+4. [Bitwise operations](#examples)
+5. [Precedence](#precedence)
+6. [Type lattice](#type-implementation)
+7. [Nodes](#nodes)
+
+
 In this chapter, we add sub-word integer types.
 
 You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter14) 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-chapter13...linear-chapter14) it to the previous chapter.
 
 ## Narrow or sub-word types
 
+Narrow or sub-worded integer types refer to integer data types that occupy less memory (fewer bits) than the standard or "full-width"(Typically 32, or 64 bits) integer types provided by a system or programming language.
+
+
 As a prelude to arrays, especially arrays of bytes common in all networking
 codes, Simple needs some way to manipulate sub-word integer types.
 Computations are always done in 64 bits for both integer and float ops, but
@@ -49,19 +63,242 @@ Similarly, floats can be limited to IEEE754 32-bit standard format and will be
 rounded when assigned, and inflated to 64-bits when loaded.
 
 The complete list of primitive types is now:
+
+| Data Type | Size (Bits) | Description                                                  |
+|-----------|-------------|--------------------------------------------------------------|
+| `int`, `i64` | 64          | 64-bit signed integer, matching modern hardware.           |
+| `u64`       | 64          | **Not implemented**, hints at behavior beyond 64-bit.      |
+| `i32`       | 32          | 32-bit signed integer, sign-extended on load.              |
+| `u32`       | 32          | 32-bit unsigned integer, zero-extended on load.            |
+| `i16`       | 16          | 16-bit signed integer, sign-extended on load.              |
+| `u16`       | 16          | 16-bit unsigned integer, zero-extended on load.            |
+| `i8`        | 8           | 8-bit signed integer, sign-extended on load.               |
+| `u8`        | 8           | 8-bit unsigned integer, zero-extended on load.             |
+| `i1`        | 1           | 1-bit signed integer, sign-extended on load.               |
+| `u1`        | 1           | 1-bit unsigned integer, zero-extended on load.             |
+| `bool`      | 1           | Alias for `u1`.                                            |
+| `flt`, `f64`| 64          | IEEE 754 64-bit floating-point number, often called a double. |
+| `f32`       | 32          | IEEE 754 32-bit floating-point number.                     |
+
+## Overflow handling
+
+An integer overflow occurs when you attempt to store inside an integer variable a value that is larger than the maximum value the variable can hold.
+There are several cases of overflow:
+
+#### Unsigned(fixed-width) integer overflow:
+
+```java 
+u8 a = 255; 
+u8 b = a + 1; // match u8 type against expr.type
+// a = 256 
+// u8 = [0...255]
+return b;
+```
+The expression type does not match the type that was provided. expr: ConstantNode(256) t: u8(0, 255)
+```java
+private Node parseExpressionStatement() {
+    Type t = type(); // u8 = [0...255]
+    ...
+    // expr.type = TypeInteger(256);
+    // Auto-narrow wide ints to narrow ints
+    expr = zsMask(expr,t);
+}
+```
+Since it is unsigned we just do a bitmask on the new value that overflows the specified type:
+The operands to the "bitwise AND" are the values(256) and the mask(255, max boundary).
+This is called truncating.
+
+`ZsMask:`
+```java 
+    // zero/sign extend.  "i" is limited to either classic unsigned (min==0) or
+    // classic signed (min=minus-power-of-2); max=power-of-2-minus-1.
+private Node zsMask(Node val, Type t ) {
+    if( !(val._type instanceof TypeInteger tval && t instanceof TypeInteger t0 && !tval.isa(t0)) ) {
+        if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) )
+            return val;
+        // Float rounding
+        return new RoundF32Node(val).peephole();
+    }
+    if( t0._min==0 )        // Unsigned
+        return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole();
+    // Signed extension
+    int shift = Long.numberOfLeadingZeros(t0._max)-1;
+    Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole();
+    if( shf._type==TypeInteger.ZERO )
+        return val;
+    return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole();
+}
+```
+
+The truncation is done by the `AndNode`:
+```java
+...
+if( t0._min==0 )       // Unsigned
+        return new AndNode(val,con(t0._max)).peephole();
+```
+Since they are constants, after calling peephole it truns into`256 & 255` = 0;
+Output:
+```
+return 0; 
+```
+
+#### Maximum integer overflow
+```java 
+i64 a = 9223372036854775807; 
+i64 b = a + 1;
+return b;
+```
+When we are computing the addition, we make sure they don't overflow:
+
+`AddNode.overflow:`
+```java 
+private static boolean overflow( long x, long y ) {
+    if(    (x ^      y ) < 0 ) return false; // unequal signs, never overflow
+    return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow
+}
+```
+`AddNode.compute`
+```java 
+...
+// Fold ranges like {0-1} + {2-3} into {2-4}.
+if( !overflow(i1._min,i2._min) &&
+    !overflow(i1._max,i2._max) )
+    return TypeInteger.make(i1._min+i2._min,i1._max+i2._max);
+```
+Here **x + y** overflows and becomes **negative**, x ^ negative = negative. Any negative number is less than 0, so it returns true.
+If it **overflows** we just return the bottom type of TypeInteger.
+```
+       return TypeInteger.BOT; // []
+```
+However, in our case we are dealing with constants, so we just allow the overflow naturally here:
 ```java
-int, i64  // 64-bits, matching modern hardware
-// u64    // NOT implemented, as it hints at some kind of >64 bit behavior
-i32, u32  // 32 bits, sign or zero extended on load
-i16, u16  // 16 bits, sign or zero extended on load
- i8,  u8  //  8 bits, sign or zero extended on load
- i1,  u1  //  1 bit , sign or zero extended on load
-bool      // Same as u1 
-flt, f64  // IEEE 754 64-bit float, sometimes called a "double"
-f32       // IEEE 754 32-bit float
+// i1: 9223372036854775807
+// i2: 1
+// i1 + i2 will overflow.
+return TypeInteger.constant(i1.value()+i2.value()); // -9223372036854775808;
 ```
 
+#### Adding constant ranges
+```java 
+u8 a = 12; 
+u8 b = 13;
+u8 c = 124;
+u8 d = a + b + c;
+return d;
+```
+if `is_con` is true, then generally we can state: `min = max`.
+Such that:
+```java
+public static TypeInteger make(boolean is_con, long con) {
+    return make(is_con ? con : (con==0 ? Long.MAX_VALUE : Long.MIN_VALUE),
+                is_con ? con : (con==0 ? Long.MIN_VALUE : Long.MAX_VALUE));
+```
+- This results in: 
+```java
+return make(con, con);
+```
 
+`value()` is only called in constants, e.g  `_min == _max;` invariants holds, then since
+both `min_` and `max_` are equal, we can return either one.
+
+This is the same as regular additions:
+```java 
+public long value() { assert isConstant(); return _min; } 
+```
+
+#### Truncate(2)
+
+```java 
+u8 a = arg;  // arg & 255
+u8 b = arg;  // arg & 255(same as a)
+u8 c = a + b; // (arg&255)*2, type = TypeInteger.BOT
+return c; // (((arg&255)*2)&255), type = TypeInteger.U8 
+```
+
+Same as before, **arg** turns into **(arg&255)**, this node is then inserted into the **GVN** table and  **b** retrieves this value.
+The AddNode peephole will change them into `((arg&255)*2`, and put on extra mask 
+on the expression to keep it in the valid boundaries.
+
+
+## Integer ranges
+Link hacker's delight here.
+
+For range math, visit:[^1]
+## Bitwise operations
+We support the following bitwise operators:
+And `&`, Or `|`, Xor `^`, Shift left `<<`, Shift right `>>`, Shift right zero `>>>`
+
+| Operator                 | Symbol  | Description                                                                                             |
+|--------------------------|---------|---------------------------------------------------------------------------------------------------------|
+| **And**                  | `&`     | Performs a bitwise AND operation.                                                                       |
+| **Or**                   | `\|`        | Performs a bitwise OR (inclusive OR) operation.                                                         |
+| **Xor**                  | `^`     | Performs a bitwise XOR (exclusive OR) operation.                                                        |
+| **Shift Left**           | `<<`    | Shifts bits to the left, filling with zeros.                                                            |
+| **Shift Right**          | `>>`    | Shifts bits to the right, any vacated bit postions are filled by replicating the value of the sign bit. |
+| **Unsigned Right Shift** | `>>>`   | Shifts bits to the right, any vacated bit postions are always filled with zero                          |
+
+Note `>>>` is a logical shift and not an arithmetic shift.
+
+####  AndNode:
+
+##### lhs & -1 = lhs;
+```java 
+// And of -1.  We do not check for (-1&x) because this will already
+// canonicalize to (x&-1)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==-1 )
+return lhs;
+
+```
+
+#### OrNode:
+##### lhs | 0 = lhs;
+```java
+// Or of 0.  We do not check for (0|x) because this will already
+// canonicalize to (x|0)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+return lhs;
+
+```
+
+#### Shift right
+lhs >> 0 = lhs;
+```java
+// Sar of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+    return lhs;
+```
+
+#### Shift left
+lhs << 0 = lhs;
+```java
+// Shl of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+    return lhs;
+
+```
+#### Unsigned right shift
+lhs >>> 0 = lhs;
+```java
+// Shr of 0.
+if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 )
+return lhs;
+```
+
+#### XorNode:
+##### lhs ^ 0 = lhs;
+```java
+// Xor of 0.  We do not check for (0^x) because this will already
+// canonicalize to (x^0)
+if( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+    return lhs;
+
+```
+### precedence
+
+Bitwise operators have the lowest precedence, e.g
+```
+arg + 123 & 3 = (arg + 123) & 3
+```
 
 ## Type Implementation
 
@@ -85,8 +322,18 @@ The <font style="background-color:aqua">TypeFloat</font> class is also reworked
 
 ![Graph1](./docs/lattice.svg)
 
+### meet:
 
-
+Meet of two ranges:
+```java
+@Override
+public Type xmeet(Type other) {
+// Invariant from caller: 'this' != 'other' and same class (TypeInteger)
+TypeInteger i = (TypeInteger)other; // Contract
+return make(Math.min(_min,i._min), Math.max(_max,i._max));
+}
+```
+Combine all values that could possibly occur within either range.
 
 ## Nodes
 
@@ -98,3 +345,6 @@ slightly different `idealize()` calls.
 
 
 
+[^1]:  Hacker's delight.
+    4-2 Propagating Bounds through Add's and Subtract's
+