diff options
| -rw-r--r-- | .github/workflows/maven.yml | 18 | ||||
| -rw-r--r-- | .gitignore | 177 | ||||
| -rw-r--r-- | README.md | 43 | ||||
| -rw-r--r-- | chapter01/README.md | 5 | ||||
| -rw-r--r-- | chapter01/docs/01-grammar.md | 39 | ||||
| -rw-r--r-- | chapter01/pom.xml | 14 | ||||
| -rw-r--r-- | language/.gitignore | 28 | ||||
| -rw-r--r-- | language/README.md | 6 | ||||
| -rw-r--r-- | language/examples/all-features.lang | 21 | ||||
| -rw-r--r-- | language/pom.xml | 80 | ||||
| -rw-r--r-- | language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 | 170 | ||||
| -rw-r--r-- | pom.xml | 50 |
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 @@ -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 @@ -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 |