From 1a9cac97df063af82516ca35bde34fde62d24c56 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: 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 * Update chapter06/README.md Co-authored-by: Yichen Yan * #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 Co-authored-by: Yichen Yan --- language/.gitignore | 28 ---- language/README.md | 6 - language/examples/all-features.lang | 21 --- language/pom.xml | 79 ---------- .../com/seaofnodes/simple/antlr/SimpleLanguage.g4 | 170 --------------------- 5 files changed, 304 deletions(-) delete mode 100644 language/.gitignore delete mode 100644 language/README.md delete mode 100644 language/examples/all-features.lang delete mode 100644 language/pom.xml delete mode 100644 language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 (limited to 'language') diff --git a/language/.gitignore b/language/.gitignore deleted file mode 100644 index 58314a2c..00000000 --- a/language/.gitignore +++ /dev/null @@ -1,28 +0,0 @@ -# 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 deleted file mode 100644 index 09593ab5..00000000 --- a/language/README.md +++ /dev/null @@ -1,6 +0,0 @@ -# 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 deleted file mode 100644 index 132e4b9c..00000000 --- a/language/examples/all-features.lang +++ /dev/null @@ -1,21 +0,0 @@ -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 deleted file mode 100644 index dbb4710e..00000000 --- a/language/pom.xml +++ /dev/null @@ -1,79 +0,0 @@ - - 4.0.0 - - com.seaofnodes - simple - 1.0 - - language-grammar - jar - SeaOfNodes Demo Simple Language Grammar - - UTF-8 - 21 - 21 - 1.22 - 4.11.1 - 4.13.2 - - - - org.antlr - antlr4-runtime - ${antlr.version} - jar - compile - - - - - - - org.apache.maven.plugins - maven-compiler-plugin - 3.10.1 - - - - - - org.antlr - antlr4-maven-plugin - ${antlr.version} - - true - true - - - - generate-sources - - antlr4 - - - - - - com.khubla.antlr - antlr4test-maven-plugin - ${antlr4test-maven-plugin.version} - - false - false - program - SimpleLanguage - com.seaofnodes.simple.antlr - examples/ - - - - - test - - - - - - - diff --git a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 b/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 deleted file mode 100644 index 6779e5a2..00000000 --- a/language/src/main/antlr4/com/seaofnodes/simple/antlr/SimpleLanguage.g4 +++ /dev/null @@ -1,170 +0,0 @@ -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 -- cgit v1.2.3