Chapter 6 (#38)

* #37 Create chapter 6 skeleton

* #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too.
We have a _type field that is like an enum.

* #37 Revise Type.meet() - this is now final.
Subclasses can override xmeet() which is protected but
now handles simple types in Type itself.

* #37 Basic test for peephole of CFG

* #37 Revise compute of if

* #37 Revise compute of if

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP fix the chars inserted by IntelliJ

* #37 WIP Fix compute type in IfNode

* #37 WIP Null check region inputs

* #37 WIP Fix where we choose great grand parent instead of grand parent
Add new test

* #37 WIP More fixes and tests

* #37 WIP Some minor adjustments

* Cleanup folding dead IF tests

Remove isDeadCtrl & just test for the constant.
Remove DEAD_CTRL, doesn't properly reset between tests.
Move keep/unkeep to Node.
PhiNode has a proper compute() call.
ProjNode ideal is a lot simpler.
Region doesn't ever get a null.
Move the mergeScopes Region peep till after all Phis are added.
Type TOP and XCONTROL count as constants.
TypeTuple gets a toString

* #37 WIP Upate README

* #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed

* #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed

* #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes

* Region removes dead input paths

Remove region-folding in Return, If.
Add a Makefile.
Reformat triple-quote lines to be emacs-friendly.

* StopNode idealize

Return type sharpens to include control input.

* Remove !=, >=, >; use Not and <, <=, ==

Fix bug mixing rotating different ops.
Generalize Add fold constants; apply to Mul, EQ.
Fix Div.copy

* Fix bug rotating e.g. < or <=

Peep is only valid for associative ops

* #37 WIP Doc updates

* Work over the Ch6 Readme

Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis.  When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input.

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* #37 Backport type system changes to chapter 2

* #37 Backport type system changes to chapter 3

* #37 Backport type system changes to chapter 4

* #37 Backport type system changes to chapter 5

* #37 Merge chapter 5 updates from main.
Remove language grammar module as we describe the grammar incrementally in each chapter.

* #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole

* #37 Sync some updates to chapter 2

* #37 Sync some updates to chapter 3

* #37 Sync some updates to chapter 4

---------

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>

1 files changed, 92 insertions, 0 deletions

diff --git a/chapter06/Makefile b/chapter06/Makefile
new file mode 100644
index 00000000..f2839f15
--- /dev/null
+++ b/chapter06/Makefile
@@ -0,0 +1,92 @@
+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 17 -target 17
+
+# 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.%,$(test_javas))
+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)
+	$(JVM) org.junit.runner.JUnitCore $(test_cp)
+
+.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)