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

diff --git a/chapter10/Makefile b/chapter10/Makefile
new file mode 100644
index 00000000..c7724bc7
--- /dev/null
+++ b/chapter10/Makefile
@@ -0,0 +1,98 @@
+SHELL := /bin/bash
+.DELETE_ON_ERROR:
+
+# for printing variable values
+# usage: make print-VARIABLE
+#        > VARIABLE = value_of_variable
+print-%  : ; @echo $* = $($*)
+
+# literal space
+space := $() $()
+
+# Decide OS-specific questions
+# jar-file seperator
+ifeq ($(OS),Windows_NT)
+	SEP = ;
+else
+	SEP = :
+endif
+# Find a reasonable ctags.
+CTAGS = $(shell which ctags)
+# Hack for MacOS: /usr/bin/ctags is unfriendly, so look for ctags from brew
+ifeq ($(UNAME),Darwin)
+	CTAGS = $(shell brew list ctags 2> /dev/null | grep bin/ctags)
+endif
+
+# Fun Args to javac.  Mostly limit to java8 source definitions, and fairly
+# aggressive lint warnings.
+JAVAC_ARGS = -g
+
+# Source code
+SIMPLE := com/seaofnodes/simple
+SRC := src/main/java
+TST := src/test/java
+CLZDIR:= build/classes
+main_javas   := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java)
+test_javas   := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java)
+main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas))
+test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas))
+test_cp      := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java))
+classes = $(main_classes) $(test_classes)
+# All the libraries
+libs = $(wildcard lib/*jar)
+jars = $(subst $(space),$(SEP),$(libs))
+
+
+default_targets := $(main_classes) $(test_classes)
+# Optionally add ctags to the default target if a reasonable one was found.
+ifneq ($(CTAGS),)
+default_targets += tags
+endif
+
+default: $(default_targets)
+
+# Compile just the out-of-date files
+$(main_classes): build/classes/main/%class: $(SRC)/%java
+	@echo "compiling " $@ " because " $?
+	@[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main
+	@javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas)
+
+$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java $(main_classes)
+	@echo "compiling " $@ " because " $?
+	@[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test
+	@javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(test_javas)
+
+# Base launch line for JVM tests
+JVM=nice java -ea -cp "build/classes/main${SEP}${jars}${SEP}$(CLZDIR)/test"
+
+tests:	$(default_targets)
+	@echo "testing " $(test_cp)
+	@$(JVM) org.junit.runner.JUnitCore $(test_cp)
+
+fuzzer: $(default_targets)
+	@echo "fuzzing " $(test_cp)
+	@$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap
+
+
+.PHONY: clean
+clean:
+	rm -rf build
+	rm -f TAGS
+	(find . -name "*~" -exec rm {} \; 2>/dev/null; exit 0)
+
+# Download libs from maven
+lib:	lib/junit-4.12.jar  lib/hamcrest-core-1.3.jar
+
+# Jars
+lib/junit-4.12.jar:
+	@[ -d lib ] || mkdir -p lib
+	@(cd lib; wget https://repo1.maven.org/maven2/junit/junit/4.12/junit-4.12.jar)
+
+lib/hamcrest-core-1.3.jar:
+	@[ -d lib ] || mkdir -p lib
+	@(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar)
+
+# Build emacs tags (part of a tasty emacs ide experience)
+tags:	$(main_javas) $(test_javas)
+	@rm -f TAGS
+	@$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST)