diff options
36 files changed, 132 insertions, 159 deletions
diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 8975a165..806c985d 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -237,9 +237,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 6989d0b9..a91aabb1 100644 --- a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -1,17 +1,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; public class Chapter01Test { - @Rule - public ExpectedException exceptionRule = ExpectedException.none(); - @Test public void testSimpleProgram() { Parser parser = new Parser("return 1;"); @@ -60,9 +55,12 @@ public class Chapter01Test { @Test public void testBad3() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected integer literal"); - new Parser("return --12;").parse(); + try { + new Parser("return --12;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected integer literal",e.getMessage()); + } } @Test @@ -78,9 +76,12 @@ public class Chapter01Test { // Negative numbers require unary operator support that is not in scope @Test public void testBad5() { - exceptionRule.expect(RuntimeException.class); - exceptionRule.expectMessage("Syntax error, expected integer literal"); - new Parser("return -100;").parse(); + try { + new Parser("return -100;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected integer literal",e.getMessage()); + } } @Test diff --git a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java index f106bd47..72da8eeb 100644 --- a/chapter02/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter02/src/main/java/com/seaofnodes/simple/Parser.java @@ -287,9 +287,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java index 4fb5b6ed..90fcbd27 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/Parser.java @@ -399,9 +399,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java index 3359f14e..e75567a5 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/Parser.java @@ -442,9 +442,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java index 8a02766f..0fd52788 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java @@ -512,9 +512,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index 83eaa099..5a844f0e 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -513,9 +513,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java index fa576700..b5fcbeaf 100644 --- a/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter06/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; diff --git a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java index b4418ced..ecca0618 100644 --- a/chapter07/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter07/src/main/java/com/seaofnodes/simple/Parser.java @@ -583,9 +583,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 99e35d0a..ea348968 100644 --- a/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter07/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Rule; import org.junit.Test; -import org.junit.rules.ExpectedException; import static org.junit.Assert.*; diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index eae6e0c6..47e7c2c4 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -630,9 +630,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java index c4ce71eb..1827bae2 100644 --- a/chapter09/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter09/src/main/java/com/seaofnodes/simple/Parser.java @@ -651,9 +651,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 05485d8c..d78d5358 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter10/docs/10-grammar.md b/chapter10/docs/10-grammar.md index 01863e7f..29ca7762 100644 --- a/chapter10/docs/10-grammar.md +++ b/chapter10/docs/10-grammar.md @@ -92,6 +92,7 @@ multiplicativeExpression unaryExpression : ('-') unaryExpression + | '!' unaryExpression | primaryExpression ; diff --git a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java index 9a1b4465..dbb2d172 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/Parser.java @@ -821,9 +821,8 @@ public class Parser { return new String(_input, start, --_position - start); } - // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>(){}+-/*!".indexOf(ch) != -1; } private String parsePunctuation() { diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java index adcb6b59..6e8d218f 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter11/README.md b/chapter11/README.md index 21cd3457..b461f3b7 100644 --- a/chapter11/README.md +++ b/chapter11/README.md @@ -1,10 +1,10 @@ -# Chapter 11 +# Chapter 11: Global Code Motion The original input source program defines a sequence in which things happen. As we parse the program into Sea of Nodes representation and perform various optimizations, this sequence is not fully maintained. The optimized Sea of Nodes graph is driven more -by dependencies between nodes rather that the sequence of instructions in the original source program. +by dependencies between nodes rather that the sequence of instructions in the original source program. -Our goal in this chapter is to look at how we can recover a schedule for executing instructions from an +Our goal in this chapter is to look at how we can recover a schedule for executing instructions from an optimized Sea of Nodes graph. This schedule needs to preserve the semantics of the original source program, but is otherwise allowed to reorder the execution of instructions. @@ -20,19 +20,19 @@ Since this is a complex topic, we will present a high level summary first and th The Sea of Nodes graph has two virtual graphs within it. -* There is a control flow graph, represented by certain node types, such as Start, If, Region, etc. +* There is a control flow graph, represented by certain node types, such as Start, If, Region, etc. * There is a data graph, primarily driven by Def-Use edges between nodes that produce or consume values or memory. From a scheduling point of view, the control flow graph is fixed, and immovable. -However, the nodes that consume or produce data values/memory have some flexibility in terms of when they are executed. The goal of the +However, the nodes that consume or produce data values/memory have some flexibility in terms of when they are executed. The goal of the scheduling algorithm is to find the best placement of these nodes so that they are both optimum and correct. At its core, the scheduling algorithm works in two phases: -* Schedule Early - in this phase, we do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the +* Schedule Early - in this phase, we do an upward DFS walk on the "inputs" of each Node, starting from the bottom (Stop). We schedule each data node to the first control block where they are dominated by their inputs. -* Schedule Late - in this phase we do a downward DFS walk on the "outputs" of each Node starting from the top (Start), and move data nodes to a block between the first block calculated above, - and the last control block where they dominate all their uses. The placement is subject to the condition that it is in the shallowest loop nest possible, and is as control dependent as possible. +* Schedule Late - in this phase we do a downward DFS walk on the "outputs" of each Node starting from the top (Start), and move data nodes to a block between the first block calculated above, + and the last control block where they dominate all their uses. The placement is subject to the condition that it is in the shallowest loop nest possible, and is as control dependent as possible. Additionally, the placement of Load instructions must ensure correct ordering between Loads and Stores of the same memory location. ## Scheduling Walk Through @@ -78,12 +78,12 @@ The snip below shows the main changes in the graph:  -* The store `.f=` now has an anti-dependency on the load `.f`; this ensures that the store is scheduled after the load, as required by program semantics. We discuss anti-dependencies in detail later. -* Observe also that the store `.f=` is now bound to the True branch of the If node. +* The store `.f=` now has an anti-dependency on the load `.f`; this ensures that the store is scheduled after the load, as required by program semantics. We discuss anti-dependencies in detail later. +* Observe also that the store `.f=` is now bound to the True branch of the If node. ## Scheduling a Loop -We show another example, this time involving a loop. +We show another example, this time involving a loop. ```java struct S { int f; } @@ -122,18 +122,18 @@ We have already alluded to several components of the GCM algorithm in passing ab * When a program has an infinite loop, it poses a problem for the algo, as nodes can be unreachable from the Stop node. To work around this issue, we need to discover infinite loops and create a dummy edge connecting the loop to the Stop node. * Loops are already identified in the Simple SoN graph, so we do not need a loop discovery step. However, we need to compute the loop depth associated with each CFG node. -* In [Chapter 6](../chapter06/README.md) we explained the concept of Dominators. Dominators are key to the GCM algo, and we extend our incremental dominator discovery algo to +* In [Chapter 6](../chapter06/README.md) we explained the concept of Dominators. Dominators are key to the GCM algo, and we extend our incremental dominator discovery algo to ensure that it meets the requirements of the algo. * We already mentioned the two phases of the algo - the Early Scheduling and the Late Scheduling. * In addition, we need to add anti-dependency edges between Loads and Stores in certain scenarios to enforce correct execution order. -* There are a few changes to our Node hierarchy to help us implement the GCM algo more conveniently. These changes do not conceptually alter the Node hierarchy we inherited from the previous chapters. +* There are a few changes to our Node hierarchy to help us implement the GCM algo more conveniently. These changes do not conceptually alter the Node hierarchy we inherited from the previous chapters. ## Identification of Basic Blocks in SoN graph The Sea of Nodes graph already captures the programs control flow graph. This information is implicit in the control nodes and edges from control nodes to other types of nodes. To recap, Control starts at the Start node, via a projection that is bound to the name `$ctrl`. As the control flows in the program, this name binding gets updated, and control is -passed around, until it reaches the Stop node. +passed around, until it reaches the Stop node. The Basic Block structure of the CFG can be easily constructed by recognizing that certain control nodes start a Basic Block, whereas certain others end a BB. @@ -279,7 +279,7 @@ class RegionNode extends CFGNode { } class LoopNode extends RegionNode { // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) - @Override public CFGNode idom() { return entry(); } + @Override public CFGNode idom() { return entry(); } } class StartNode extends CFGNode { @Override public CFGNode idom() { return null; } @@ -329,7 +329,7 @@ class LoopNode extends RegionNode { class StartNode extends CFGNode { @Override public int loopDepth() { return (_loopDepth=1); } } -class StopNode extends CFGNode { +class StopNode extends CFGNode { @Override public int loopDepth() { return (_loopDepth=1); } } ``` @@ -517,7 +517,7 @@ We call these edges anti-dependencies because they do not represent the Def-Use We compute anti-dependencies DURING running schedule late. This is because we rely on the early-schedule, and the late-schedule of the Load's uses (before scheduling the Load). Looking backwards from the Load we follow the memory edge to the "memory definer" - a start-mem-projection, or a phi-mem, or a store. -We look forwards from the mem-def to all its mem-def users. There is always at least one; there may be many. These completely (all of it) and exactly (no doubling up) cover the forward memory space, sort of like a network flow problem - but we limit our analysis to same-alias, +We look forwards from the mem-def to all its mem-def users. There is always at least one; there may be many. These completely (all of it) and exactly (no doubling up) cover the forward memory space, sort of like a network flow problem - but we limit our analysis to same-alias, because for example, a start-mem-proj produces all aliases. This gives us a candidate set of mem-defs; some of these need the anti-dependency on the Load, but not all. Since we're in the middle of "schedule late", we have already computed all the late schedules of a Load's users, and we have the Loads "Least Common Ancestor" of uses, the LCA or late position. @@ -553,7 +553,7 @@ The implementation is shown below. } return lca; } - + private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Walk store blocks "reach" from its scheduled location to its earliest for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { @@ -577,4 +577,4 @@ Please watch the following video for a detailed walk through of the implementati * [Coffee Compiler Club - 26 June 2024](https://www.youtube.com/watch?v=HnN2YzmFb-8&t=0s) [^1]: Cliff Click. (1995). - Global Code Motion Global Value Numbering.
\ No newline at end of file + Global Code Motion Global Value Numbering. diff --git a/chapter11/docs/11-grammar.md b/chapter11/docs/11-grammar.md index 0aaf0619..9370024e 100644 --- a/chapter11/docs/11-grammar.md +++ b/chapter11/docs/11-grammar.md @@ -11,7 +11,7 @@ statement : returnStatement | structDeclaration | declStatement - | blockStatment + | blockStatment | expressionStatement | ifStatement | whileStatement @@ -26,7 +26,7 @@ field fields : field+ - ; + ; structDeclaration : 'struct' IDENTIFIER '{' fields '}' @@ -39,10 +39,10 @@ whileStatement breakStatement : 'break' ';' ; - + continueStatement : 'continue' ';' - ; + ; ifStatement : 'if' '(' expression ')' statement ('else' statement)? @@ -77,26 +77,27 @@ returnStatement expression : comparisonExpression ; - + comparisonExpression : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* ; - + additiveExpression - : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* ; - + multiplicativeExpression : unaryExpression (('*' | '/') unaryExpression)* ; unaryExpression : ('-') unaryExpression + | '!' unaryExpression | primaryExpression ; newExpression - : 'new' IDENTIFIER + : 'new' IDENTIFIER ; fieldExpression @@ -118,11 +119,11 @@ INTEGER_LITERAL : [1-9][0-9]* | [0] ; - + IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; - + NON_DIGIT: [a-zA-Z_]; DEC_DIGIT: [0-9]; -```
\ No newline at end of file +``` diff --git a/chapter11/docs/build-graphs.sh b/chapter11/docs/build-graphs.sh deleted file mode 100644 index 839a36ba..00000000 --- a/chapter11/docs/build-graphs.sh +++ /dev/null @@ -1,9 +0,0 @@ -dot -Tsvg graph1.gv > graph1.svg -dot -Tsvg graph2.gv > graph2.svg -dot -Tsvg graph3.gv > graph3.svg -dot -Tsvg graph4.gv > graph4.svg -dot -Tsvg graph5.gv > graph5.svg -dot -Tsvg graph6.gv > graph6.svg -dot -Tsvg graph7.gv > graph7.svg -dot -Tsvg graph8.gv > graph8.svg - diff --git a/chapter11/docs/graph1.gv b/chapter11/docs/graph1.gv index 97815f63..74c54fdb 100644 --- a/chapter11/docs/graph1.gv +++ b/chapter11/docs/graph1.gv @@ -73,4 +73,4 @@ return i; Return25 -> Region23[taillabel=0 color=red]; Return25 -> Load16[taillabel=1]; Return25 -> Phi_224[taillabel=2 color=blue]; -}
\ No newline at end of file +} diff --git a/chapter11/docs/graph4.gv b/chapter11/docs/graph4.gv index 190e83dd..f6958ccb 100644 --- a/chapter11/docs/graph4.gv +++ b/chapter11/docs/graph4.gv @@ -104,4 +104,4 @@ return v; Return37 -> If16:p1[taillabel=0 color=red]; Return37 -> new9[taillabel=1]; Return37 -> Phi_230[taillabel=2 color=blue]; -}
\ No newline at end of file +} diff --git a/chapter11/docs/graph5.gv b/chapter11/docs/graph5.gv index 9ebc11cb..f89a83ac 100644 --- a/chapter11/docs/graph5.gv +++ b/chapter11/docs/graph5.gv @@ -110,4 +110,4 @@ return v; Return37 -> If16:p1[taillabel=0 color=red]; Return37 -> new9[taillabel=1]; Return37 -> Phi_230[taillabel=2 color=blue]; -}
\ No newline at end of file +} diff --git a/chapter11/docs/graph6.gv b/chapter11/docs/graph6.gv index b108c44d..dfd07d7e 100644 --- a/chapter11/docs/graph6.gv +++ b/chapter11/docs/graph6.gv @@ -110,4 +110,4 @@ return v; Return37 -> If16:p1[taillabel=0 color=red]; Return37 -> new9[taillabel=1]; Return37 -> Phi_230[taillabel=2 color=blue]; -}
\ No newline at end of file +} diff --git a/chapter11/docs/graph7.gv b/chapter11/docs/graph7.gv index e9e380ff..18be364b 100644 --- a/chapter11/docs/graph7.gv +++ b/chapter11/docs/graph7.gv @@ -20,4 +20,4 @@ digraph chapter11 { edge [ fontname=Helvetica, fontsize=8 ]; Loop8 -> Start2:p0[taillabel=1 color=red]; Loop8 -> Loop8[taillabel=2 color=red constraint=false]; -}
\ No newline at end of file +} diff --git a/chapter11/docs/graph8.gv b/chapter11/docs/graph8.gv index 4189dae8..1a7b231d 100644 --- a/chapter11/docs/graph8.gv +++ b/chapter11/docs/graph8.gv @@ -42,4 +42,4 @@ return 0; Return21 -> Con_4[taillabel=1]; Loop8 -> Start2:p0[taillabel=1 color=red]; Loop8 -> Never18:p1[taillabel=2 color=red constraint=false]; -}
\ No newline at end of file +} diff --git a/chapter11/pom.xml b/chapter11/pom.xml index fb238068..7bbd7cb1 100644 --- a/chapter11/pom.xml +++ b/chapter11/pom.xml @@ -11,4 +11,4 @@ <artifactId>chapter11</artifactId> <packaging>jar</packaging> <name>Chapter 11</name> -</project>
\ No newline at end of file +</project> diff --git a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java index e3f29b3d..f3ac25b1 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/Utils.java @@ -55,4 +55,4 @@ public class Utils { // Fold a 64bit hash into 32 bits public static int fold( long x ) { return (int)((x>>32) ^ x); } -}
\ No newline at end of file +} diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 81b0d173..c10dc510 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -16,7 +14,7 @@ public class Chapter01Test { StopNode stop = parser.parse(); StartNode start = Parser.START; ReturnNode ret = (ReturnNode)stop.in(0); - + assertTrue(ret.ctrl() instanceof CProjNode); Node expr = ret.expr(); if( expr instanceof ConstantNode con ) { @@ -37,14 +35,66 @@ public class Chapter01Test { assertEquals(TypeInteger.constant(0),con._type); } + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'ret'",e.getMessage()); + } + } @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); } } + + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + + @Test + public void testBad6() { + try { + new Parser("return100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'return100'",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 351cdb16..2deba460 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -2,14 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter02Test { - + @Test public void testParseGrammar() { Parser parser = new Parser("return 1+2*3+-5;"); @@ -64,36 +62,5 @@ public class Chapter02Test { GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); } - - @Test - public void testBad1() { - try { - new Parser("ret").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Undefined name 'ret'",e.getMessage()); - } - } - @Test - public void testNotBad3() { - // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); - } - - @Test - public void testBad4() { - try { - new Parser("return 100").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, expected ;: ",e.getMessage()); - } - } - - @Test - public void testNotBad5() { - // this test used to fail in chapter 1 - assertEquals("return -100;", new Parser("return -100;").parse().print()); - } } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 8a11107d..407fbe48 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -2,14 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter03Test { - + @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); @@ -49,7 +47,7 @@ public class Chapter03Test { @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -58,7 +56,7 @@ public class Chapter03Test { } @Test - public void testBad6() { + public void testBad1() { try { new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); fail(); diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 57d464ef..317fe677 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -2,14 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter04Test { - + @Test public void testPeephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); @@ -37,7 +35,7 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } - + @Test public void testPeephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); @@ -51,7 +49,7 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testVarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -112,7 +110,7 @@ public class Chapter04Test { @Test public void testBug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -126,5 +124,5 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } - + } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 2c17113e..64f3a1d9 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; @@ -203,7 +201,7 @@ return a;"""); } @Test - public void testKeyword3() { + public void testKeyword3() { try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); @@ -212,14 +210,4 @@ return a;"""); } } - @Test - public void testBad7() { - try { - new Parser("return 1;}").parse(); - fail(); - } catch( RuntimeException e ) { - assertEquals("Syntax error, unexpected }",e.getMessage()); - } - } - } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 5e823f5d..fed34465 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -2,9 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 0685f6f9..f9251be7 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -2,15 +2,12 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; -import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter07Test { - @Test public void testExample() { Parser parser = new Parser( @@ -47,7 +44,6 @@ return a; @Test public void testWhileNested() { Parser parser = new Parser( - """ int sum = 0; int i = 0; @@ -240,4 +236,5 @@ return a; assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } + } diff --git a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 82b04c60..730da36a 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; diff --git a/chapter11/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter11/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 29a6853c..51e39cd0 100644 --- a/chapter11/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter11/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -134,16 +134,16 @@ public class Fuzzer { new ScriptGenerator(rand, sb, true).genProgram(); try { var parser = new Parser(sb.toString()); - + var stop = parser.parse(); int parse_peeps= Node.ITER_CNT; int parse_nops = Node.ITER_NOP_CNT; double parse_nop_ratio = (double)parse_nops/parse_peeps; int nids = Node.UID(); if( nids <= max_nids ) return max_nids; - + double parse_peeps_per_node = (double)parse_peeps/nids; - + stop.iterate(); int iter_peeps= Node.ITER_CNT; int iter_nops = Node.ITER_NOP_CNT; @@ -174,7 +174,7 @@ public class Fuzzer { check(sb.toString(), valid, seed); } - + /** * Check that no exceptions happened. * @return true if no exception happened |