Merge pull request #2 from dibyendumajumdar/main

Initial framework for the project

12 files changed, 648 insertions, 3 deletions

diff --git a/.github/workflows/maven.yml b/.github/workflows/maven.yml
new file mode 100644
index 00000000..48ad1d91
--- /dev/null
+++ b/.github/workflows/maven.yml
@@ -0,0 +1,18 @@
+name: Java CI with Maven
+
+on: [push]
+
+jobs:
+  test:
+
+    runs-on: ubuntu-latest
+
+    steps:
+      - uses: actions/checkout@v3
+      - name: Set up JDK 17
+        uses: actions/setup-java@v3
+        with:
+          java-version: '17'
+          distribution: 'temurin'
+      - name: Build with Maven
+        run: mvn --batch-mode --update-snapshots verify
\ No newline at end of file
diff --git a/.gitignore b/.gitignore
index 524f0963..a8c78987 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+# Java stuff
 # Compiled class file
 *.class
 
@@ -22,3 +23,179 @@
 # virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
 hs_err_pid*
 replay_pid*
+
+# Gradle stuff
+.gradle
+**/build/
+!src/**/build/
+
+# Ignore Gradle GUI config
+gradle-app.setting
+
+# Avoid ignoring Gradle wrapper jar file (.jar files are usually ignored)
+!gradle-wrapper.jar
+
+# Avoid ignore Gradle wrappper properties
+!gradle-wrapper.properties
+
+# Cache of project
+.gradletasknamecache
+
+
+# Covers JetBrains IDEs: IntelliJ, RubyMine, PhpStorm, AppCode, PyCharm, CLion, Android Studio, WebStorm and Rider
+# Reference: https://intellij-support.jetbrains.com/hc/en-us/articles/206544839
+
+# User-specific stuff
+.idea/**/workspace.xml
+.idea/**/tasks.xml
+.idea/**/usage.statistics.xml
+.idea/**/dictionaries
+.idea/**/shelf
+
+# AWS User-specific
+.idea/**/aws.xml
+
+# Generated files
+.idea/**/contentModel.xml
+
+# Sensitive or high-churn files
+.idea/**/dataSources/
+.idea/**/dataSources.ids
+.idea/**/dataSources.local.xml
+.idea/**/sqlDataSources.xml
+.idea/**/dynamic.xml
+.idea/**/uiDesigner.xml
+.idea/**/dbnavigator.xml
+
+# Gradle
+.idea/**/gradle.xml
+.idea/**/libraries
+
+# Gradle and Maven with auto-import
+# When using Gradle or Maven with auto-import, you should exclude module files,
+# since they will be recreated, and may cause churn.  Uncomment if using
+# auto-import.
+# .idea/artifacts
+# .idea/compiler.xml
+# .idea/jarRepositories.xml
+# .idea/modules.xml
+# .idea/*.iml
+# .idea/modules
+# *.iml
+# *.ipr
+
+# CMake
+cmake-build-*/
+
+# Mongo Explorer plugin
+.idea/**/mongoSettings.xml
+
+# File-based project format
+*.iws
+
+# IntelliJ
+out/
+
+# mpeltonen/sbt-idea plugin
+.idea_modules/
+
+# JIRA plugin
+atlassian-ide-plugin.xml
+
+# Cursive Clojure plugin
+.idea/replstate.xml
+
+# SonarLint plugin
+.idea/sonarlint/
+
+# Crashlytics plugin (for Android Studio and IntelliJ)
+com_crashlytics_export_strings.xml
+crashlytics.properties
+crashlytics-build.properties
+fabric.properties
+
+# Editor-based Rest Client
+.idea/httpRequests
+
+# Android studio 3.1+ serialized cache file
+.idea/caches/build_file_checksums.ser
+
+
+target/
+pom.xml.tag
+pom.xml.releaseBackup
+pom.xml.versionsBackup
+pom.xml.next
+release.properties
+dependency-reduced-pom.xml
+buildNumber.properties
+.mvn/timing.properties
+# https://github.com/takari/maven-wrapper#usage-without-binary-jar
+.mvn/wrapper/maven-wrapper.jar
+
+# Eclipse stuff
+.metadata
+bin/
+tmp/
+*.tmp
+*.bak
+*.swp
+*~.nib
+local.properties
+.settings/
+.loadpath
+.recommenders
+
+# External tool builders
+.externalToolBuilders/
+
+# Locally stored "Eclipse launch configurations"
+*.launch
+
+# PyDev specific (Python IDE for Eclipse)
+*.pydevproject
+
+# CDT-specific (C/C++ Development Tooling)
+.cproject
+
+# CDT- autotools
+.autotools
+
+# Java annotation processor (APT)
+.factorypath
+
+# PDT-specific (PHP Development Tools)
+.buildpath
+
+# sbteclipse plugin
+.target
+
+# Tern plugin
+.tern-project
+
+# TeXlipse plugin
+.texlipse
+
+# STS (Spring Tool Suite)
+.springBeans
+
+# Code Recommenders
+.recommenders/
+
+# Annotation Processing
+.apt_generated/
+.apt_generated_test/
+
+# Scala IDE specific (Scala & Java development for Eclipse)
+.cache-main
+.scala_dependencies
+.worksheet
+
+# Eclipse Gradle plugin generated files
+# Eclipse Core
+.project
+# JDT-specific (Eclipse Java Development Tools)
+.classpath
+
+.idea/*
+*.iml
\ No newline at end of file
diff --git a/README.md b/README.md
index ba068fb9..8acd8585 100644
--- a/README.md
+++ b/README.md
@@ -2,9 +2,46 @@
 A Simple showcase for the Sea-of-Nodes compiler IR
 
 This repo is intended to demonstrate the Sea-of-Nodes compiler IR.  
-The Sea-of-Nodes is the core IR inside of HotSpot's C2 compiler and Google's V8 compiler and Sun/Oracle's Graal compiler.
+
+The Sea-of-Nodes is the core IR inside of HotSpot's C2 compiler 
+and Google's V8 compiler and Sun/Oracle's Graal compiler.
+
 Since we are show casing the SoN IR, the *language* being implemented is less important.  
 We're using a very simple language similar to C or Java, but with far fewer features.
-The Sea-of-Nodes is used for machine code generation in these industrial strength systems - but for this demonstration the backend is both difficult and less important.
-This repo also is not intended to be a complete language in any sense, and so the backend will probably start with levering C or Java. 
+The Sea-of-Nodes is used for machine code generation in these industrial 
+strength systems - but for this demonstration the backend is both difficult 
+and less important.
+
+This repo also is not intended to be a complete language in any sense, 
+and so the backend will probably start with levering C or Java.
+
+## Chapters
+
+The following is a rough plan, subject to change.
+
+Each chapter will be self-sufficient and complete; in the sense that each chapter will fully implement 
+a subset of the simple language, and include everything that was created in the previous chapter. 
+Each chapter will also include a detailed commentary on relevant aspects of the 
+Sea Of Nodes intermediate representation.
+
+The simple language will be a small subset of C. 
 
+* [Language](language/README.md): Simple language grammar.
+* [Chapter 1](chapter01/README.md): Empty script - i.e. empty function that takes no args and returns nothing, and has empty body.
+* Chapter 2: Simple binary arithmetic such as addition, subtraction, multiplication, division with constants. Peephole optimization / simple constant folding.
+* Chapter 3: Graphical Visualization of Sea of Nodes IR.
+* Chapter 4: Local variables, and assignment statements. Read on RHS, SSA, more peephole optimization if local is a constant.
+* Chapter 5: Binary and Comparison operators involving constants and variables. Non-zero values will be truthy.
+* Chapter 6: `if` statement.  CFG construction, peephole optimization around dead control flow.
+* Chapter 7: `while` statement. 
+* Chapter 8: Global Value Numbering.
+* Chapter 9: Function calls.
+* Chapter 10: Boolean operators `&&`, `||` and `!` including short circuit.
+* Chapter 11: `float` type.
+* Chapter 12: Memory effects: general memory edges in SSA. Peephole optimization around load-after-store/store-after-store.
+* Chapter 13: Equivalence class aliasing, fine grained peephole optimizations. Free ptr-to analysis in SoN; but does not handle aliasing in arrays.
+* Chapter 14: One dimensional static length array type. Array load/store.
+* Chapter 15: Global Code Motion - unwind SoN to CFG. Scheduling.
+* Chapter 16: Instruction selection, BURS.
+* Chapter 17: Backend register allocation.
+* Chapter 18: Garbage Collection.
\ No newline at end of file
diff --git a/chapter01/README.md b/chapter01/README.md
new file mode 100644
index 00000000..a641c4ad
--- /dev/null
+++ b/chapter01/README.md
@@ -0,0 +1,5 @@
+# Chapter 1
+Simple start and end node for basic empty script.
+
+
+* [Grammar](docs/01-grammar.md)
\ No newline at end of file
diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md
new file mode 100644
index 00000000..92ed7357
--- /dev/null
+++ b/chapter01/docs/01-grammar.md
@@ -0,0 +1,39 @@
+# Grammar for Chapter 1
+
+```antlrv4
+grammar SimpleLanguage;
+
+program
+    : declaration* statement+ EOF
+    ;
+
+declaration
+    : type IDENTIFIER ';'
+    ;
+
+type
+    : 'int'
+    ;
+
+statement
+    : 'if' '(' expression ')' statement
+    | 'if' '(' expression ')' statement 'else' statement
+    | 'while' '(' expression ')' statement
+    | IDENTIFIER '=' expression ';'
+    | '{' declaration* statement+ '}'
+    | 'break' ';'
+    ;
+
+expression
+    : primaryExpression                                             # PrimaryExpression_
+    | expression ('*' | '/' ) expression                            # ArithmeticOrLogicalExpression
+    | expression ('+' | '-') expression                             # ArithmeticOrLogicalExpression
+    ;
+
+primaryExpression
+    :
+    | INTEGER_LITERAL
+    | IDENTIFIER
+    | '(' expression ')'
+    ;
+```
\ No newline at end of file
diff --git a/chapter01/pom.xml b/chapter01/pom.xml
new file mode 100644
index 00000000..2204bde8
--- /dev/null
+++ b/chapter01/pom.xml
@@ -0,0 +1,14 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+    <parent>
+        <groupId>com.seaofnodes</groupId>
+        <artifactId>simple</artifactId>
+        <version>1.0</version>
+    </parent>
+    <artifactId>chapter01</artifactId>
+    <packaging>jar</packaging>
+    <name>Chapter 1</name>
+</project>
\ No newline at end of file
diff --git a/language/.gitignore b/language/.gitignore
new file mode 100644
index 00000000..58314a2c
--- /dev/null
+++ b/language/.gitignore
@@ -0,0 +1,28 @@
+# Compiled class file
+*.class
+
+# Log file
+*.log
+
+# BlueJ files
+*.ctxt
+
+# Mobile Tools for Java (J2ME)
+.mtj.tmp/
+
+# Package Files #
+*.jar
+*.war
+*.nar
+*.ear
+*.zip
+*.tar.gz
+*.rar
+
+# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
+hs_err_pid*
+
+target/*
+
+.idea
+*.iml
\ No newline at end of file
diff --git a/language/README.md b/language/README.md
new file mode 100644
index 00000000..09593ab5
--- /dev/null
+++ b/language/README.md
@@ -0,0 +1,6 @@
+# Simple Demo Language
+
+The language is a small subset of the C language.
+
+The grammar of the language is not yet finalized, but for the current definition,
+please look at [grammar](src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4).
\ No newline at end of file
diff --git a/language/examples/all-features.lang b/language/examples/all-features.lang
new file mode 100644
index 00000000..132e4b9c
--- /dev/null
+++ b/language/examples/all-features.lang
@@ -0,0 +1,21 @@
+int i;
+int j;
+
+i = 0;
+j = 100;
+while ( 1 )
+{
+    i = i + 1;
+    j = j - 1;
+    if (i >= j)
+        break;
+}
+
+if (1)
+    i = i + 5;
+else if (2)
+    i = i - 1;
+else
+{
+    j = 0;
+}
\ No newline at end of file
diff --git a/language/pom.xml b/language/pom.xml
new file mode 100644
index 00000000..7d748aa1
--- /dev/null
+++ b/language/pom.xml
@@ -0,0 +1,80 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+	xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+	<modelVersion>4.0.0</modelVersion>
+    <parent>
+        <groupId>com.seaofnodes</groupId>
+        <artifactId>simple</artifactId>
+        <version>1.0</version>
+    </parent>
+	<artifactId>language-grammar</artifactId>
+	<packaging>jar</packaging>
+	<name>SeaOfNodes Demo Simple Language Grammar</name>
+	<properties>
+		<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+		<maven.compiler.target>17</maven.compiler.target>
+		<maven.compiler.source>17</maven.compiler.source>
+		<antlr4test-maven-plugin.version>1.22</antlr4test-maven-plugin.version>
+		<antlr.version>4.11.1</antlr.version>
+		<antlr4test-maven-plugin.version>1.21</antlr4test-maven-plugin.version>
+		<junit.version>4.13.2</junit.version>
+	</properties>
+	<dependencies>
+		<dependency>
+			<groupId>org.antlr</groupId>
+			<artifactId>antlr4-runtime</artifactId>
+			<version>${antlr.version}</version>
+			<type>jar</type>
+			<scope>compile</scope>
+		</dependency>
+	</dependencies>
+	<build>
+		<pluginManagement>
+			<plugins>
+				<plugin>
+					<groupId>org.apache.maven.plugins</groupId>
+					<artifactId>maven-compiler-plugin</artifactId>
+					<version>3.10.1</version>
+				</plugin>
+			</plugins>
+		</pluginManagement>
+		<plugins>
+			<plugin>
+				<groupId>org.antlr</groupId>
+				<artifactId>antlr4-maven-plugin</artifactId>
+				<version>${antlr.version}</version>
+				<configuration>
+					<visitor>true</visitor>
+					<listener>true</listener>
+				</configuration>
+				<executions>
+					<execution>
+						<phase>generate-sources</phase>
+						<goals>
+							<goal>antlr4</goal>
+						</goals>
+					</execution>
+				</executions>
+			</plugin>
+			<plugin>
+				<groupId>com.khubla.antlr</groupId>
+				<artifactId>antlr4test-maven-plugin</artifactId>
+				<version>${antlr4test-maven-plugin.version}</version>
+				<configuration>
+					<verbose>false</verbose>
+					<showTree>false</showTree>
+					<entryPoint>program</entryPoint>
+					<grammarName>SimpleLanguage</grammarName>
+					<packageName>com.seaofnodes.simple.antlr</packageName>
+					<exampleFiles>examples/</exampleFiles>
+				</configuration>
+				<executions>
+					<execution>
+						<goals>
+							<goal>test</goal>
+						</goals>
+					</execution>
+				</executions>
+			</plugin>
+		</plugins>
+	</build>
+</project>
diff --git a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4
new file mode 100644
index 00000000..6779e5a2
--- /dev/null
+++ b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4
@@ -0,0 +1,170 @@
+grammar SimpleLanguage;
+
+program
+    : declaration* statement+ EOF
+    ;
+
+declaration
+    : type IDENTIFIER ';'
+    ;
+
+type
+    : 'int'
+    ;
+
+statement
+    : 'if' '(' expression ')' statement
+    | 'if' '(' expression ')' statement 'else' statement
+    | 'while' '(' expression ')' statement
+    | IDENTIFIER '=' expression ';'
+    | '{' declaration* statement+ '}'
+    | 'break' ';'
+    ;
+
+expression
+    : primaryExpression                                             # PrimaryExpression_
+    | ('-' | '!') expression                                        # UnaryExpression
+    | expression ('*' | '/' ) expression                            # ArithmeticOrLogicalExpression
+    | expression ('+' | '-') expression                             # ArithmeticOrLogicalExpression
+    | expression ('==' | '!='| '>'| '<'| '>='| '<=') expression     # ComparisonExpression
+    | expression '&&' expression                                    # BooleanExpression
+    | expression '||' expression                                    # BooleanExpression
+    ;
+
+primaryExpression
+    :
+    | INTEGER_LITERAL
+    | IDENTIFIER
+    | '(' expression ')'
+    ;
+
+///////////////////////////////////////////////////////////////////
+
+IDENTIFIER
+    :   IDENTIFIER_NONDIGIT
+        (   IDENTIFIER_NONDIGIT
+        |   DEC_DIGIT
+        )*
+    ;
+
+fragment
+IDENTIFIER_NONDIGIT
+    :   NON_DIGIT
+    |   UNIVERSAL_CHARACTER_NAME
+    ;
+
+fragment
+NON_DIGIT
+    :   [a-zA-Z_]
+    ;
+
+
+fragment
+UNIVERSAL_CHARACTER_NAME
+    :   '\\u' HEX_QUAD
+    |   '\\U' HEX_QUAD HEX_QUAD
+    ;
+
+fragment
+HEX_QUAD
+    :   HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
+    ;
+
+// tokens char and string
+CHAR_LITERAL
+   : '\''
+   (
+      ~['\\\n\r\t]
+      | QUOTE_ESCAPE
+      | ASCII_ESCAPE
+      | UNICODE_ESCAPE
+   ) '\''
+   ;
+
+STRING_LITERAL
+   : '"'
+   (
+      ~["]
+      | QUOTE_ESCAPE
+      | ASCII_ESCAPE
+      | UNICODE_ESCAPE
+      | ESC_NEWLINE
+   )* '"'
+   ;
+RAW_STRING_LITERAL: 'r' RAW_STRING_CONTENT;
+fragment RAW_STRING_CONTENT: '#' RAW_STRING_CONTENT '#' | '"' .*? '"';
+BYTE_LITERAL: 'b\'' (. | QUOTE_ESCAPE | BYTE_ESCAPE) '\'';
+
+BYTE_STRING_LITERAL: 'b"' (~["] | QUOTE_ESCAPE | BYTE_ESCAPE)* '"';
+RAW_BYTE_STRING_LITERAL: 'br' RAW_STRING_CONTENT;
+fragment ASCII_ESCAPE: '\\x' OCT_DIGIT HEX_DIGIT | COMMON_ESCAPE;
+fragment BYTE_ESCAPE: '\\x' HEX_DIGIT HEX_DIGIT | COMMON_ESCAPE;
+fragment COMMON_ESCAPE: '\\' [nrt\\0];
+fragment UNICODE_ESCAPE
+   : '\\u{' HEX_DIGIT HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? HEX_DIGIT? '}'
+   ;
+fragment QUOTE_ESCAPE: '\\' ['"];
+fragment ESC_NEWLINE: '\\' '\n';
+
+// number
+INTEGER_LITERAL
+   :
+   (
+      DEC_LITERAL
+      | BIN_LITERAL
+      | OCT_LITERAL
+      | HEX_LITERAL
+   ) INTEGER_SUFFIX?
+   ;
+DEC_LITERAL: DEC_DIGIT (DEC_DIGIT | '_')*;
+HEX_LITERAL: '0x' '_'* HEX_DIGIT (HEX_DIGIT | '_')*;
+OCT_LITERAL: '0o' '_'* OCT_DIGIT (OCT_DIGIT | '_')*;
+BIN_LITERAL: '0b' '_'* [01] [01_]*;
+FLOAT_LITERAL
+   : DEC_LITERAL
+   (
+      '.' DEC_LITERAL
+   )? FLOAT_EXPONENT? FLOAT_SUFFIX?
+   ;
+
+fragment INTEGER_SUFFIX
+   : 'u8'
+   | 'u16'
+   | 'u32'
+   | 'u64'
+   | 'u128'
+   | 'usize'
+   | 'i8'
+   | 'i16'
+   | 'i32'
+   | 'i64'
+   | 'i128'
+   | 'isize'
+   ;
+
+fragment FLOAT_SUFFIX: 'f32' | 'f64';
+fragment FLOAT_EXPONENT: [eE] [+-]? '_'* DEC_LITERAL;
+fragment OCT_DIGIT: [0-7];
+fragment DEC_DIGIT: [0-9];
+fragment HEX_DIGIT: [0-9a-fA-F];
+
+
+WHITESPACE
+    :   [ \t]+
+        -> skip
+    ;
+
+NEWLINE
+    :   (   '\r' '\n'?
+        |   '\n'
+        )
+        -> skip
+    ;
+
+LINE_COMMENT
+    :   '//' ~[\r\n]*
+        -> skip
+    ;
+
+
+ANY: . ;
\ No newline at end of file
diff --git a/pom.xml b/pom.xml
new file mode 100644
index 00000000..9f9601d9
--- /dev/null
+++ b/pom.xml
@@ -0,0 +1,50 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0
+                             http://maven.apache.org/maven-v4_0_0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+
+    <groupId>com.seaofnodes</groupId>
+    <artifactId>simple</artifactId>
+    <packaging>pom</packaging>
+    <version>1.0</version>
+    <name>SeaOfNodes Simple Programming Language</name>
+    <description>A simple language implementation to demonstrate Sea of Nodes IR</description>
+    <url>https://github.com/SeaOfNodes/Simple</url>
+    <licenses>
+        <license>
+            <name>Apache License Version 2.0</name>
+            <url>http://www.apache.org/licenses/LICENSE-2.0</url>
+        </license>
+    </licenses>
+
+    <modules>
+        <module>language</module>
+        <module>chapter01</module>
+    </modules>
+
+    <properties>
+        <maven.compiler.source>17</maven.compiler.source>
+        <maven.compiler.target>17</maven.compiler.target>
+        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+        <junit.version>4.13.2</junit.version>
+    </properties>
+
+    <dependencies>
+        <dependency>
+            <groupId>junit</groupId>
+            <artifactId>junit</artifactId>
+            <version>${junit.version}</version>
+        </dependency>
+    </dependencies>
+
+    <build>
+        <plugins>
+            <plugin>
+                <groupId>org.apache.maven.plugins</groupId>
+                <artifactId>maven-surefire-plugin</artifactId>
+                <version>3.1.2</version>
+            </plugin>
+        </plugins>
+    </build>
+</project>
\ No newline at end of file