Ch10 (#74)

* Chapter 10 start

* #67 language grammar for chapter 10

* #67 Fix chapter title

* #67 Fix typo

* #67 assignment to fields

* #67 Struct var decl must be initialized

* #67 Start to describe memory and aliasing

* #67 revision

* #67 Start to describe how we construct the graph

* #67 Start to describe how we construct the graph

* #67 Start to describe how we construct the graph

* #67 Parse struct declaration

* #67 WIP parse expressions and statements involving struct vars

* #67 WIP parse store expressions

* #67 WIP parse load expressions

* #67 WIP first go at adding aliases and memslices

* #67 WIP A store should get bound to the $mem alias replacing previous node

* #67 WIP Add MergeMem node

* Update script generator to new features (#68)

* #67 WIP Drop MergeMem node

* #67 WIP Drop MergeMem node

* #67 WIP Improve parsing of postfix expressions

* #67 WIP Improve parsing of postfix expressions

* #67 WIP Update xmeet - these types can only meet another of the same type

* #67 WIP Phi's compute should return input type if input is a MemPtr even if region is in progress because parser needs the correct type

* #67 WIP If a null meets a non-null ptr then non-null wins; but ideally we want to retain type of null so we do not have this problem

* #67 WIP If a null meets a non-null ptr then non-null then the result is type|null

* #67 WIP Fix TypeMemPtr.eq() and also intern struct types

* #67 WIP Add missing hash and eq implementations
Also refactor common code to get field from ptr

* #67 Add START as input to New (as proxy for Mem).
Other minor adjustments

* #67 Phis widen type inside a loop during parse

* #67 Fix redeclaration bug

* #67 Small refactor

* #67 Add an LLVM inspired IR printer based on post by Yasser A

* #67 Add instructions to initialize fields of a struct after a new

* #67 Make New's ctrl input the current ctrl rather than Start

* #67 Refactor to make it cleaner

* #67 Fix bug - interned types should be cleared

* #67 Fix bug - new node must be kept so that its not prematurely killed

* #67 Fix bug - we must do a depp comparison of structs because types get interned and we can't easily clear the interned types across runs, this means we can end up with structs retaining definitions from older runs.

* #67 Refactor

* #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input

* #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input

* #67 Tidy up printing and add expected result on tests

* #67 Refactor TypeStruct

* #67 Refactor TypeStruct
When printing IR in new format - show the projection index

* #67 Revise the lattice for ptr types to make it more complete

* #67 Revise the lattice for mem and struct types. Add initial test

* #67 Refactor how we compute phi type

* #67 Refactor how we compute phi type

* #67 Use the generated graph but an edge is missing in the graph - to be investigated

* #67 One more tweek

* Partial work on ch10, some tests busted

Revamp Types Mem, MemPtr, Struct, FIeld.
Add tests to enforce theoretical rules properties.,
Add parsing "?" to allow nullable types.
Enhance GraphViz to show off mem  better.
Strip trailing WS in many files.

* Strip trailing WS

* Post-peephole errors

Some nicer error reporting for types.
Mem Projs following StartNode are indexed by alias, but may have "holes" in the set of projs.

* WS cleanup

* Simplify TMP dual

Add more test type
Rename test type so makefile picks it up
Failing 1 test

* Scopes and Phis track declared type

...not the initial type.

* A fuzzer found bug

* Some changes on the fuzzer and maybe faster reducer (#69)

* WS and printing changes

* Kotlin style null checks (partial)

Allow `ptr=rand?; if( ptr ) ptr.field` where the if-test upcasts the ptr to not-null.
Field assignments are expressions not statements: `if( (ptr.fld=rez) !=null ) .... `
Many WS changes.

* missed cleanup

* Fuzzer update (#71)

* Update script generator

* Fix script generator

* Reset type cache to prevent alias blowup (#70)

* Reset type cache to prevent alias blowup

* Remove the default intern

Just reset the UNIQUE_ALIAS number.  Intern table doesn't care, that's the whole point of the intern table.  Passes existing tests, but fuzzer finds some new stuff

* Fix a few of the fuzzer bugs

More to come

* Fix one more fuzzer bug

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

* Fix script generated generating invalid code

* Greatly simplify Cast usage

Casts peephole normally.
Added needed Phi optimizations to remove excess  casts.

Fuzzer bug fixes:
Need a plain kill unused on worklist.
MemOp error handles aTOP/BOT input.

* #67 Add description of lattice to the doc
Update grammar - add the '?' nullable syntax
Rename VOID to PTR

* #67 Some renames

* #67 some more text re lattice

* #67 Fix the alias ID start to 2

* #67 Revise lattice diagram and doc

* #67 Start describing the parser changes and Null Pointer analysis

* #67 Draw lattice diagram using graphviz

* #67 Revisions to text

* #67 Improve description of alias classes

* #67 Some renames to make code clearer

* #67 Describe null pointer analysis

* Fix script generated generating invalid code (#72)

* updates to readme

shorter example names to make a nicer graph

* #67 Revise top level README

* #67 Revise top level README

---------

Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <xmilia.hermit@gmail.com>

1 files changed, 284 insertions, 0 deletions

diff --git a/chapter10/README.md b/chapter10/README.md
new file mode 100644
index 00000000..c4045513
--- /dev/null
+++ b/chapter10/README.md
@@ -0,0 +1,284 @@
+# Chapter 10
+
+In this chapter:
+
+* We add user defined struct types in the Simple language.
+* We introduce the concept of Memory, Memory Pointers and Aliasing.
+* We add new nodes to represent operations on memory - such as creating new instance of a struct, storing and loading struct fields.
+
+Here is the [complete language grammar](docs/10-grammar.md) for this chapter.
+
+## Memory
+
+In previous chapters, we dealt with scalar values that fit into a single
+machine register.  We now introduce aggregate values of `struct` type; these
+have reference semantics and thus do not behave like register values, even if
+the struct would fit into a register.  To support values of such a type, we
+need the concept of `Memory`.
+
+The core ideas regarding `Memory` are:
+
+* The program starts and stops with a single `Memory` value that encapsulates
+  the whole of available memory; `Start` produces memory and `Return` consumes
+  memory.  
+
+* Each `struct` and field carves up this memory into "alias classes", a unique
+  class for each combination of struct and field.
+
+* Memory in different alias classes *never* aliases; memory in the same alias
+  class *always* aliases.  This is sometimes called "equivalence class"
+  aliasing.  
+  
+* Equivalence class aliasing can be directly represented in the Sea of Nodes,
+  as such we will not use any other side-structure for aliasing.  This also
+  means with normal peepholes we can do alias-based optimizations such as
+  load/store bypassing or load forwarding without needing to consult any side
+  structure, or make alias tracking modifications when we alter the graph.
+
+
+### Alias Classes
+
+Aliasing describes a situation in which a data location in memory can be
+accessed through multiple symbolic names (variables) in the program.  Modifying
+the data through one name implicitly modifies the values associated with all
+the aliased names.
+
+Data accesses to the same alias class (struct+field) are serialized as defined
+by the source program; data in other classes is allowed to be accessed in
+parallel.  
+
+Simple, like Java, is a strongly typed language.  Therefore, two variables that
+have incompatible types cannot possibly be names to the same location in
+memory.  We can use type information to determine which symbols alias,
+i.e., potentially reference the same location in memory.  We
+divide/slice all memory into disjoint alias classes.
+
+We implement the "alias class" as a unique integer ID assigned to each field in
+a struct, where distinct struct types have their own set of ids.  Thus, every
+field in every struct type is a new alias class.  In later chapters as we
+implement arrays and subtyping, our strategy for assigning alias classes will
+be enhanced.
+
+For background information and overview of type based alias analysis, please
+refer to the paper `Type Based Alias Analysis`.[^1] Our approach is a form of
+TBAA similar to the "FieldTypeDecl" algorithm described in the paper.  We do
+not track aliasing by instance of a Struct type.
+
+
+### Implementation of Alias Classes
+
+For example, suppose we have declared two struct types like so:
+
+```
+struct Vec2D { int x; int y; }
+struct Vec3D { int x; int y; int z; }
+```
+
+Then we can imagine assigning following alias class IDs
+
+| Struct type | Field | Alias |
+| ----------- | ----- | ----- |
+| Vec2D       | x     | 1     |
+| Vec2D       | y     | 2     |
+| Vec3D       | x     | 3     |
+| Vec3D       | y     | 4     |
+| Vec3D       | z     | 5     |
+
+So at this point we have sliced memory into 5 distinct alias classes.
+Note that the `x` and `y` in `Vec2D` do not alias `x` and `y` in `Vec3D`.
+
+In this chapter we do not have inheritance or sub-typing. But if we had subtyping and `Vec3D` 
+was a subtype of `Vec2D` then `x` and `y` would alias and would be given the same alias class.
+
+## Extensions to Intermediate Representation
+
+We add following new Node types to support memory operations:
+
+| Node Name | Type | Description                      | Inputs                                                    | Value                                  |
+|-----------|------|----------------------------------|-----------------------------------------------------------|----------------------------------------|
+| New       | Mem  | Create ptr to new object         | Control, Struct type                                      | Ptr value                              |
+| Store     | Mem  | Stores a value in a struct field | Memory slice (aliased by struct+field), Ptr, Field, Value | Memory slice (aliased by struct+field) |
+| Load      | Mem  | Loads a value from a field       | Memory slice (aliased by struct+field), Ptr, Field        | Value loaded                           |
+| Cast      | Data | Upcasts a value                  | Control, Data, type                                       | Upcast value                           | 
+
+
+* New takes the current control as an input so that it is pinned correctly in
+  the control flow.  Conceptually the control input is also a proxy for all
+  memory that originates from the Start node.
+
+* Above, "Ptr" refers to the base address of the allocated object.  Ptrs can represent different values in loops.
+* A "Memory Slice" represents a slice of memory where all stores and loads alias.  Different slices do not alias.
+
+Additionally, the following Node types will be enhanced:
+
+| Node Name | Type    | Changes                                                          |
+|-----------|---------|------------------------------------------------------------------|
+| Start     | Control | Start will produce the initial Memory projections, one per slice |
+| Return    | Control | Will merge all memory slices                                     |
+
+## Enhanced Type Lattice
+
+The Type Lattice for Simple has a major revision in this chapter. 
+
+![Graph1](./docs/lattice.svg)
+
+Within the Type Lattice, we now have the following type domains:
+
+* Control type - this represents control flow
+* Integer type - Integer values
+* Struct type (new) - Represents user defined struct types, a struct type is allowed to have members of Integer type only in this chapter
+  * `$TOP` represents local Top for struct type; all we know about the type is that it is a struct but, we do not know if it is a specific struct, or all possible structs, etc.
+  * `$BOT` represents local Bottom for struct type; we definitely know the value can take all possible struct types.
+* Pointer type (new) - Represents a pointer to a struct type
+  * `null` is a pointer to non-existent memory object
+  * We use the prefix `*` to mean pointer-to. Thus `*S1` means pointer to `S1`, `*$TOP` means pointer to `$TOP`.
+  * `*void` is a synonym for `*$BOT` - i.e. it represents a Non-Null pointer to all possible struct types, akin to `void *` in C except not null.
+  * `?` suffix represents the union of a pointer to some type and `null`.
+  * `null` pointer evaluates to False and non-null pointers evaluate to True, as in C.
+* Memory (new) - Represents memory and memory slices
+  * `MEM#TOP` - Nothing known about a slice 
+  * `#n` - refers to a memory slice
+  * `MEM#BOT` - all of memory
+
+We make use of following operations on the lattice.
+
+* The `meet` operation takes two types and computes the greatest lower bound
+  type.  While not true for all lattices, in the our lattice this can be
+  thought of as set union (ORing) of its input types (as sets).
+  * Example, meet of `*S1` and `*S2` results in `*void` - there is no lattice
+    element for exactly both `{*S1,*S2}`, so we drop down to the nearest
+    element containing both (and maybe more), which is `*void*`.
+  * Meet of `*S1` and struct `Null` results in `*S1?`
+  * Meet of `*void` and `Null` results in `*$BOT?`; bear in mind that `*void` is a synonym for `*$BOT`.
+  * Meet of `1` and `2` results in `Int Bot`.
+  * Meet of `#1` and `#2` results in `MEM#BOT`.
+* The `dual` operation is symmetric across the lattice centerline.  Types directly on the centerline are their own dual.
+  * Find the corresponding node of the lattice after inverting the lattice.
+    * Thus, dual of `Top` is `Bot`.
+    * The dual of `*$TOP` is `*$BOT?`.
+  * For structs, the dual is obtained by computing the dual of each struct member. Thus, dual of `*S1` is not `*S1?`.
+  
+* The `join` operation takes two types and computes the least upper bound type.
+  Similar to `meet` this can thought of as set intersection (ANDing) of its input types.  
+  Because our lattice structure is simple, we compute `join` with a well known identity: 
+  `JOIN(x,y) === MEET(x.dual,y.dual).dual`
+  * Example, join of `*S1` and `*S2` results in `*$TOP`.
+  * Join of `1` and `2` results in `Int Top`.
+  * Join of `*void` and `Null` results in `*$TOP`.
+
+As we construct the Sea of Nodes graph, we ensure that values stay inside the
+domain they are created in - that is ptr fields will never contain ints
+(obviously)... nor even the generic `TOP` and `BOT`.  There are a couple of
+nuances worth highlighting.  
+
+* When Phis are created, the initial type of the Phi is based on the declared
+  type of its first input.  This is a pessimistic type assignment because we do
+  not yet know what other types will be met.
+
+* When all the inputs of the Phi are known, we start with the local Top of the
+  declared type, and then compute a meet of all the input types.  This
+  computation results in a more refined type for the Phi.
+
+## Parser Enhancements
+
+In previous chapters the only available type was Integer.  Now, variables can
+be of Integer type or pointer to Struct types.  To support this, the Parser now
+tracks the declared type of a variable (used to only be Integer!).  The
+declared type of a variable defines the set of values that can be legitimately
+assigned to the variable.  The Sea of Nodes graph also tracks the actual type
+of values assigned to variables, these type transitions are defined by the Type
+lattice described in the previous section.
+
+## Null Pointer Analysis
+
+The Simple language syntax allows a pointer variable to be specified as
+Null-able - and it prevents ever throwing a Null Pointer Exception.  The
+compiler tries to decide in a null check is needed, and if needed and missing
+the compiler rejects the program (asking the user to insert a null check).
+
+When the Parser encounters conditions that test the truthiness of a pointer variable, it uses this knowledge to refine the type information in the branches that follow.
+
+Here are two motivating examples:
+
+```java
+struct Bar { int a; }
+Bar? bar = new Bar;
+if (arg) bar = null;
+if( bar ) bar.a = 1;
+```
+
+If `bar` is not `null` above, then we would like to allow the assignment to
+`bar.a`.  If the final line lacked the null check, e.g. a plain `bar.a = 1;`,
+then `Java` would compile this program but throw a NPE, and Simple rejects the
+program pointing out a null check is required.
+
+
+```java
+struct Bar { int a; }
+Bar? bar = new Bar;
+if (arg) bar = null;
+int rez = 3;
+if( !bar ) rez=4;
+else bar.a = 1;
+```
+
+If `bar` is `null` then we would like `!bar` to evaluate to `true`. In the else
+branch we know `bar` is not null, hence the assignment to `bar.a` should be
+allowed.
+
+To enable this behaviour, we make following enhancements.
+
+* We track the null-ness of a pointer in the Type system, and hence in every
+  Node that ptr type flows through.
+  
+* We "wrap" the predicate of an `If` node with an up-cast when we see that the
+  predicate is a ptr value.  The up-cast removes the null possibility on the
+  true branch making it legal to use the pointer.
+  
+* The up-cast is done using a `Cast` op with the type `*void`.  This does a
+  lattice JOIN of the original type and `*void`.  This JOIN operation preserves
+  everything we already know about ptr, and also adds the new knowledge that
+  the ptr is not-null.
+ 
+* The up-cast is represented by the `CastNode` op, and if applicable, we
+  replace all occurrences of the original predicate with the up-cast in the
+  current scope.  The change is local to each branch of the `If`; occuring
+  separately for the true and the false branches of the `If` (and the false
+  branch inverts the predicate).
+  
+* The up-cast peepholes normally; if its input's type is a super type of the
+  up-cast, then the `CastNode` can be removed. See `ScopeNode.upcast()` method,
+  and `CastNode`.
+
+* When computing a type for Not, we produce an Integer type when its input is a
+  ptr.  When the input is a `null` we convert to `1` and when is a not `null`
+  ptr value, we convert to `0`.  See `NotNode.compute()`.
+  
+
+## Examples
+
+We now look at some examples.
+
+### Example 1
+
+This is a simple example illustrating how loads and stores are ordered based on aliasing.
+
+```java
+struct Vec2D { int x; int y; }
+
+Vec2D v = new Vec2D;
+v.x = 1;
+if (arg)
+    v.y = 2;
+else
+    v.y = 3;
+return v;
+```
+
+The graph from above will have the shape:
+
+![Graph1](./docs/example1.svg)
+
+
+[^1]: Diwan A., McKinley K.S., Moss J.E.B. (1998).
+  Type Based Alias Analysis.
\ No newline at end of file