From 1d548b46f087baa0a364bdd69efb15dedbcc2387 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 17 Jul 2024 18:11:56 +0100 Subject: Chapter 12: Floats MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Robert Obkircher --- README.md | 2 +- docs/chapter12/12-grammar.md | 134 +++++ docs/chapter12/Makefile | 12 + docs/chapter12/README.md | 58 ++ docs/chapter12/lattice.gv | 182 +++++++ docs/chapter12/lattice.svg | 598 +++++++++++++++++++++ .../com/seaofnodes/simple/GlobalCodeMotion.java | 12 +- src/main/java/com/seaofnodes/simple/IterPeeps.java | 2 + src/main/java/com/seaofnodes/simple/Parser.java | 125 ++--- .../java/com/seaofnodes/simple/node/AddFNode.java | 44 ++ .../java/com/seaofnodes/simple/node/AddNode.java | 2 + .../java/com/seaofnodes/simple/node/BoolNode.java | 31 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 9 +- .../java/com/seaofnodes/simple/node/DivFNode.java | 46 ++ .../java/com/seaofnodes/simple/node/DivNode.java | 1 + .../java/com/seaofnodes/simple/node/LoadNode.java | 10 +- .../java/com/seaofnodes/simple/node/LoopNode.java | 9 +- .../com/seaofnodes/simple/node/MinusFNode.java | 36 ++ .../java/com/seaofnodes/simple/node/MinusNode.java | 1 + .../java/com/seaofnodes/simple/node/MulFNode.java | 51 ++ .../java/com/seaofnodes/simple/node/MulNode.java | 1 + .../java/com/seaofnodes/simple/node/MultiNode.java | 8 + .../java/com/seaofnodes/simple/node/NeverNode.java | 4 +- src/main/java/com/seaofnodes/simple/node/Node.java | 24 +- .../java/com/seaofnodes/simple/node/NotNode.java | 4 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 4 +- .../com/seaofnodes/simple/node/RegionNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/node/SubFNode.java | 44 ++ .../java/com/seaofnodes/simple/node/SubNode.java | 2 + .../com/seaofnodes/simple/node/ToFloatNode.java | 30 ++ src/main/java/com/seaofnodes/simple/type/Type.java | 11 +- .../java/com/seaofnodes/simple/type/TypeFloat.java | 101 ++++ .../java/com/seaofnodes/simple/Chapter08Test.java | 1 - .../java/com/seaofnodes/simple/Chapter09Test.java | 1 - .../java/com/seaofnodes/simple/Chapter10Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 42 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 64 +++ .../java/com/seaofnodes/simple/SchedulerTest.java | 4 +- .../com/seaofnodes/simple/evaluator/Evaluator.java | 24 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 119 ++-- 42 files changed, 1679 insertions(+), 188 deletions(-) create mode 100644 docs/chapter12/12-grammar.md create mode 100644 docs/chapter12/Makefile create mode 100644 docs/chapter12/README.md create mode 100644 docs/chapter12/lattice.gv create mode 100644 docs/chapter12/lattice.svg create mode 100644 src/main/java/com/seaofnodes/simple/node/AddFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/DivFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MinusFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/MulFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/SubFNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/ToFloatNode.java create mode 100644 src/main/java/com/seaofnodes/simple/type/TypeFloat.java create mode 100644 src/test/java/com/seaofnodes/simple/Chapter12Test.java diff --git a/README.md b/README.md index 49765066..ab59d04d 100644 --- a/README.md +++ b/README.md @@ -49,7 +49,7 @@ The Simple language will be styled after a subset of C or Java * [Chapter 9](docs/chapter09/README.md): Global Value Numbering. Iterative peepholes to fixpoint. Worklists. * [Chapter 10](docs/chapter10/README.md): User defined Struct types. Memory effects: general memory edges in SSA. Equivalence class aliasing. Null pointer analysis. Peephole optimization around load-after-store/store-after-store. * [Chapter 11](docs/chapter11/README.md): Global Code Motion - Scheduling. -* Chapter 12: Float type. +* [Chapter 12](docs/chapter12/README.md): Float type. * Chapter 13: Nested references in Structs. * Chapter 14: Narrow primitive types (e.g. bytes) * Chapter 15: One dimensional static length array type, with array loads and stores. diff --git a/docs/chapter12/12-grammar.md b/docs/chapter12/12-grammar.md new file mode 100644 index 00000000..f0fe2e40 --- /dev/null +++ b/docs/chapter12/12-grammar.md @@ -0,0 +1,134 @@ +# Grammar for Chapter 12 + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatment + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatment + | metaStatement + ; + +PRIMTYPE + : 'int' + | 'flt' + ; + +field + : PRIMTYPE IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + +metaStatement + : '#showGraph' ';' + ; + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpresson '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/Makefile b/docs/chapter12/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter12/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter12/README.md b/docs/chapter12/README.md new file mode 100644 index 00000000..8f4a2d2d --- /dev/null +++ b/docs/chapter12/README.md @@ -0,0 +1,58 @@ +# Chapter 12: Floats + +# Table of Contents + +1. [Float](#floats) + +In this chapter, we add a floating point type and values. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12) it to the previous chapter. + +## Floats + +Floating point values start with the `flt` type and compute IEEE754 64-bit arithmetic. +Integer expressions auto-widen to floats when involved in a float expression. + +```java +flt f = 0.5; +int x = 2; +f = f+x; // Auto-widen x to 2.0, result is 2.5 +f = f+true; // Since bools are just synonyms for integers 0,1 they auto-widen also +``` + +There is no corresponding way right now to round a `flt` back to an `int`: +```java +int x = 3.14; // error +``` + +Here is Newton's method to a square root: +```java +flt guess = arg; // Initial guess is just argument +while( true ) { + // Next guess from Newton's method + flt next = (arg/guess + guess)/2; + // Break if hit fixed point + if( next == guess ) break; + guess = next; +} +return guess; +``` +When run with argument 2.0, produces 1.414213562373095. + +Floating point operations have their own Nodes: + +| Node | Op | +|------------------------|----------------------| +| AddF, SubF, MulF, DivF | Basic binary FP ops | +| MinusF | Unary negate | +| EQF, LTF, LEF | FP compare operators | + +And their own section in the Type lattice: + +Within the Type Lattice, we now add the following domain: + +* Float type - Float values. The same shape as the Integer values, but floats + with a TOP, BOT and constants + +![Graph1](./lattice.svg) + diff --git a/docs/chapter12/lattice.gv b/docs/chapter12/lattice.gv new file mode 100644 index 00000000..eec7cc1d --- /dev/null +++ b/docs/chapter12/lattice.gv @@ -0,0 +1,182 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.6; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_MINDOTS [label="...", fillcolor=lightblue, shape=oval]; + INT_ZERO [label="0" , fillcolor=lightblue]; + INT_MAXDOTS [label="...", fillcolor=lightblue, shape=oval]; + + TOP -> INT_TOP; + INT_TOP -> INT_MINDOTS; + INT_TOP -> INT_ZERO; + INT_TOP -> INT_MAXDOTS; + INT_MINDOTS -> INT_BOT; + INT_ZERO -> INT_BOT; + INT_MAXDOTS -> INT_BOT; + INT_BOT -> BOT; + + INT_MINDOTS -> INT_ZERO -> INT_MAXDOTS [style=invis]; + + // ---------------------- + // Integers + FLT_TOP [label=<⊤:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<⊥:flt>, fillcolor=aqua, shape=oval]; + + FLT_MINDOTS [label="...", fillcolor=aqua, shape=oval]; + FLT_ZERO [label="0" , fillcolor=aqua]; + FLT_MAXDOTS [label="...", fillcolor=aqua, shape=oval]; + + TOP -> FLT_TOP; + FLT_TOP -> FLT_MINDOTS; + FLT_TOP -> FLT_ZERO; + FLT_TOP -> FLT_MAXDOTS; + FLT_MINDOTS -> FLT_BOT; + FLT_ZERO -> FLT_BOT; + FLT_MAXDOTS -> FLT_BOT; + FLT_BOT -> BOT; + + FLT_MINDOTS -> FLT_ZERO -> FLT_MAXDOTS [style=invis]; + + // ---------------------- + // Pointers, just a boolean nil/not and a struct + PTR [shape=none, fillcolor=none, label=< + + + +
*ptr
struct
+ >]; + PTR0 [shape=none, fillcolor=none, label=< + + + +
*ptr?
struct
+ >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<⊤:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<⊥:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + + +
fieldint/ptr
+ >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + + + +
fieldint/ptr
fieldint/ptr
+ >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + + + + +
fieldint/ptr
... int/ptr
fieldint/ptr
+ >]; + + + TOP -> STRUCT_TOP; + STRUCT_TOP -> STRUCT_S1; + STRUCT_TOP -> STRUCT_S2; + STRUCT_TOP -> STRUCT_SN; + STRUCT_S1 -> STRUCT_BOT; + STRUCT_S2 -> STRUCT_BOT; + STRUCT_SN -> STRUCT_BOT; + STRUCT_BOT -> BOT; + + STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; + + // ---------------------- + // Memory + MEM_TOP [label=<⊤:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<⊥:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white]; + MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_ALIAS1; + MEM_TOP -> MEM_ALIASDOTS; + MEM_TOP -> MEM_ALIASN; + MEM_ALIAS1 -> MEM_BOT; + MEM_ALIASDOTS -> MEM_BOT; + MEM_ALIASN -> MEM_BOT; + MEM_BOT -> BOT; + + MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
Tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
Tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
Tuple
type
...
type
+ >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // ---------------------- + // Additional customization + {rank=same; TOP;} + {rank=same; INT_TOP; FLT_TOP; XCTRL; STRUCT_TOP; MEM_TOP; TUPLE_TOP} + {rank=same; INT_MINDOTS; INT_ZERO; INT_MAXDOTS; + FLT_MINDOTS; FLT_ZERO; FLT_MAXDOTS; + STRUCT_S1; STRUCT_S2; STRUCT_SN; + MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN;} + {rank=same; INT_BOT; FLT_BOT; CTRL; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter12/lattice.svg b/docs/chapter12/lattice.svg new file mode 100644 index 00000000..1bb4f692 --- /dev/null +++ b/docs/chapter12/lattice.svg @@ -0,0 +1,598 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +FLT_TOP + +⊤ +:flt + + + +TOP->FLT_TOP + + + + + +PTR + + + +*ptr + + +struct + + + +TOP->PTR + + + + + +STRUCT_TOP + +⊤ +:struct + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤ +:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_MINDOTS + +... + + + +INT_TOP->INT_MINDOTS + + + + + +INT_ZERO + +0 + + + +INT_TOP->INT_ZERO + + + + + +INT_MAXDOTS + +... + + + +INT_TOP->INT_MAXDOTS + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_MINDOTS->INT_BOT + + + + + + +INT_ZERO->INT_BOT + + + + + + +INT_MAXDOTS->INT_BOT + + + + + +FLT_MINDOTS + +... + + + +FLT_TOP->FLT_MINDOTS + + + + + +FLT_ZERO + +0 + + + +FLT_TOP->FLT_ZERO + + + + + +FLT_MAXDOTS + +... + + + +FLT_TOP->FLT_MAXDOTS + + + + + +FLT_BOT + +⊥ +:flt + + + +FLT_BOT->BOT + + + + + +FLT_MINDOTS->FLT_BOT + + + + + + +FLT_ZERO->FLT_BOT + + + + + + +FLT_MAXDOTS->FLT_BOT + + + + + +PTR0 + + + +*ptr? + + +struct + + + +PTR->PTR0 + + + + + +PTR0->BOT + + + + + +STRUCT_S1 + + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + + + +field + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_SN + + + +field + + + + + + + + +int/ptr + + +...   + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_SN + + + + + +STRUCT_BOT + +⊥ +:struct + + + +STRUCT_BOT->BOT + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_SN->STRUCT_BOT + + + + + +MEM_ALIAS1 + +#1 + + + +MEM_TOP->MEM_ALIAS1 + + + + + +MEM_ALIASDOTS + +... + + + +MEM_TOP->MEM_ALIASDOTS + + + + + +MEM_ALIASN + +#n + + + +MEM_TOP->MEM_ALIASN + + + + + +MEM_BOT + +⊥ +:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS1->MEM_BOT + + + + + + +MEM_ALIASDOTS->MEM_BOT + + + + + + +MEM_ALIASN->MEM_BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 14540d46..4e0a31d5 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -10,7 +10,6 @@ public abstract class GlobalCodeMotion { // Node.use(0) is always a block tail (either IfNode or head of the // following block). There are no unreachable infinite loops. public static void buildCFG( StopNode stop ) { - fixLoops(stop); schedEarly(); Parser.SCHEDULED = true; schedLate(Parser.START); @@ -20,7 +19,7 @@ public abstract class GlobalCodeMotion { // Backwards walk on the CFG only, looking for unreachable code - which has // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the // loop becomes reachable. Also, set loop nesting depth - private static void fixLoops(StopNode stop) { + static void fixLoops(StopNode stop) { // Backwards walk from Stop, looking for unreachable code BitSet visit = new BitSet(); HashSet unreach = new HashSet<>(); @@ -120,7 +119,7 @@ public abstract class GlobalCodeMotion { ns[i].setDef(0,late[i]); } - // Forwards post-order pass. Schedule all outputs first, then draw an + // Forwards post-order pass. Schedule all outputs first, then draw a // idom-tree line from the LCA of uses to the early schedule. Schedule is // legal anywhere on this line; pick the most control-dependent (largest // idepth) in the shallowest loop nest. @@ -148,13 +147,13 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - lca = use_block(n,use, late).idom(lca); + lca = use_block(n,use, late)._idom(lca,null); // Loads may need anti-dependencies, raising their LCA if( n instanceof LoadNode load ) lca = find_anti_dep(lca,load,early,late); - // Walk up from the LCA to the early, looking for best place. This is the + // Walk up from the LCA to the early, looking for best place. This is // lowest execution frequency, approximated by least loop depth and // deepest control flow. CFGNode best = lca; @@ -214,6 +213,7 @@ public abstract class GlobalCodeMotion { break; case LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return + case NeverNode never: break; default: throw Utils.TODO(); } } @@ -226,7 +226,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk.idom(lca); // Raise Loads LCA + lca = stblk._idom(lca,null); // Raise Loads LCA if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index b2b76777..121d0233 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -92,6 +92,8 @@ public abstract class IterPeeps { n.kill(); // Just plain dead } + // Break infinite loops, forcing a Never-branch to exit + GlobalCodeMotion.fixLoops(stop); if( show ) System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null)); GlobalCodeMotion.buildCFG(stop); diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index e367f499..1a223726 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -56,6 +56,7 @@ public class Parser { add("continue"); add("else"); add("false"); + add("flt"); add("if"); add("int"); add("new"); @@ -76,13 +77,15 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a Struct name to a Struct. - public static Map OBJS = new HashMap<>(); + // Mapping from a type name to a Type. + public static HashMap TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); - OBJS.clear(); + TYPES.clear(); + TYPES.put("int",TypeInteger.BOT); + TYPES.put("flt",TypeFloat .BOT); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); @@ -157,7 +160,6 @@ public class Parser { private Node parseStatement() { if( false ) return null; else if (matchx("return") ) return parseReturn(); - else if (matchx("int") ) return parseDecl(TypeInteger.BOT); else if (match ("{") ) return require(parseBlock(),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); @@ -174,13 +176,14 @@ public class Parser { /** * Parse a struct field. * 
-     *     int IDENTIFIER ;
+     *     type IDENTIFIER ;
      *
*/ private Field parseField(String sname) { - if( matchx("int") ) // Currently only parsing "int" type fields - return require(Field.make(requireId().intern(),TypeInteger.BOT),";"); - throw errorSyntax("A field type is expected, only type 'int' is supported at present"); + Type t = type(); + if( t==null ) + throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); + return require(Field.make(requireId().intern(),t),";"); } /** @@ -193,7 +196,7 @@ public class Parser { private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); - if ( OBJS.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + if ( TYPES.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); ArrayList fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -204,7 +207,7 @@ public class Parser { require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); - OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names + TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names START.addMemProj(ts, _scope); // Insert memory edges return parseStatement(); } @@ -423,15 +426,17 @@ public class Parser { if( _scope.define(name,t,expr) == null ) throw error("Redefining name '" + name + "'"); } else { - Node n = _scope.lookup(name); - t = _scope.lookupDeclaredType(name); - if( n==null ) + if( _scope.lookup(name)==null ) throw error("Undefined name '" + name + "'"); - _scope.update(name,expr); + t = _scope.lookupDeclaredType(name); } + // Auto-widen int to float + if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) + expr = new ToFloatNode(expr).peephole(); + // Type is sane if( !expr._type.isa(t) ) throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - return expr; + return _scope.update(name,expr); } // Parse a type-or-null @@ -439,35 +444,13 @@ public class Parser { int old = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - if( tname.equals("int") ) return TypeInteger.BOT; - TypeStruct obj = OBJS.get(tname); - if( obj != null ) - return TypeMemPtr.make(obj,match("?")); - // Not a type; unwind the parse - _lexer._position = old; - return null; - } - - /** - * Parses a declStatement - * - * 
-     *     type name = expression ';'
-     *
- * @return an expression {@link Node} - */ - private Node parseDecl(Type t) { - var name = requireId(); - var expr = match(";") - // Assign a null value - ? new ConstantNode(t.makeInit()).peephole() - // Assign "= expr;" - : require(require("=").parseExpression(), ";"); - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - if( _scope.define(name,t,expr) == null ) - throw error("Redefining name '" + name + "'"); - return expr; + Type t = TYPES.get(tname); + if( t == null ) { + // Not a type; unwind the parse + _lexer._position = old; + return null; + } + return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t; } @@ -504,7 +487,7 @@ public class Parser { else break; // Peepholes can fire, but lhs is already "hooked", kept alive lhs.setDef(idx,parseAddition()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); if( negate ) // Extra negate for != lhs = new NotNode(lhs).peephole(); } @@ -527,7 +510,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -541,14 +524,14 @@ public class Parser { * @return a multiply expression {@link Node}, never {@code null} */ private Node parseMultiplication() { - var lhs = parseUnary(); + var lhs = parseUnary(); boolean mul; while( true ) { if( false ) ; else if( match("*") ) lhs = new MulNode(lhs,null); else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = lhs.peephole(); + lhs = lhs.widen().peephole(); } return lhs; } @@ -562,7 +545,7 @@ public class Parser { * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if (match("-")) return new MinusNode(parseUnary()).peephole(); + if (match("-")) return new MinusNode(parseUnary()).widen().peephole(); if (match("!")) return new NotNode(parseUnary()).peephole(); return parsePostfix(parsePrimary()); } @@ -576,15 +559,15 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); - TypeStruct obj = OBJS.get(structName); - if( obj == null) throw errorSyntax("Unknown struct type '" + structName + "'"); + Type t = TYPES.get(structName); + if( t == null || !(t instanceof TypeStruct obj) ) throw errorSyntax("Unknown struct type '" + structName + "'"); return newStruct(obj); } String name = _lexer.matchId(); @@ -630,6 +613,7 @@ public class Parser { throw error("Expected struct reference but got " + expr._type.str()); String name = requireId().intern(); + if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); int idx = ptr._obj==null ? -1 : ptr._obj.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); int alias = START._aliasStarts.get(ptr._obj._name)+idx; @@ -653,9 +637,10 @@ public class Parser { * * 
      *     integerLiteral: [1-9][0-9]* | [0]
+     *     floatLiteral: [1-9][0-9]* | [0]
      *
*/ - private ConstantNode parseIntegerLiteral() { + private ConstantNode parseLiteral() { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } @@ -810,19 +795,37 @@ public class Parser { return String.valueOf(peek()); } - boolean isNumber() {return isNumber(peek());} + boolean isNumber(char ch) {return Character.isDigit(ch);} + // Return a constant Type, either TypeInteger or TypeFloat private Type parseNumber() { - String snum = parseNumberString(); - if (snum.length() > 1 && snum.charAt(0) == '0') - throw error("Syntax error: integer values cannot start with '0'"); - return TypeInteger.constant(Long.parseLong(snum)); + int old = _position; + int len = isLongOrDouble(); + if( len > 0 ) { + if( len > 1 && _input[old]=='0' ) + throw error("Syntax error: integer values cannot start with '0'"); + return TypeInteger.constant(Long.parseLong(new String(_input,old,len))); + } + return TypeFloat.constant(Double.parseDouble(new String(_input,old,-len))); } private String parseNumberString() { - int start = _position; - while (isNumber(nextChar())) ; - return new String(_input, start, --_position - start); + int old = _position; + int len = Math.abs(isLongOrDouble()); + _position += len; + return new String(_input,old,len); + } + + // Return +len that ends a long + // Return -len that ends a double + private int isLongOrDouble() { + int old = _position; + char c; + while( Character.isDigit(c=nextChar()) ) ; + if( !(c=='e' || c=='.') ) + return --_position - old; + while( Character.isDigit(c=nextChar()) || c=='e' || c=='.' ) ; + return -(--_position - old); } // First letter of an identifier diff --git a/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/src/main/java/com/seaofnodes/simple/node/AddFNode.java new file mode 100644 index 00000000..7d4e2910 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class AddFNode extends Node { + public AddFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "AddF"; } + + @Override public String glabel() { return "+"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("+"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()+i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Add of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new AddFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 2cc0b465..48350957 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -106,6 +106,7 @@ public class AddNode extends Node { static Node phiCon(Node op, boolean rotate) { Node lhs = op.in(1); Node rhs = op.in(2); + if( rhs._type==TypeInteger.TOP ) return null; // LHS is either a Phi of constants, or another op with Phi of constants PhiNode lphi = pcon(lhs,op); if( rotate && lphi==null && lhs.nIns() > 2 ) { @@ -171,4 +172,5 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override Node copyF() { return new AddFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 9c15f01b..48faefd2 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -1,7 +1,10 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeFloat; import com.seaofnodes.simple.type.TypeMemPtr; import java.util.BitSet; @@ -34,10 +37,17 @@ abstract public class BoolNode extends Node { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); } - return in(1)._type.meet(in(2)._type); + if( in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); + } + return TypeInteger.BOT; } - abstract boolean doOp(long lhs, long rhs); + boolean doOp(long lhs, long rhs) { throw Utils.TODO(); } + boolean doOp(double lhs, double rhs) { throw Utils.TODO(); } + Node copyF(Node lhs, Node rhs) { throw Utils.TODO(); } @Override public Node idealize() { @@ -49,11 +59,9 @@ abstract public class BoolNode extends Node { if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { // con==noncon becomes noncon==con - if( in(1) instanceof ConstantNode ) - return new EQ(in(2),in(1)); + if( in(1) instanceof ConstantNode || in(1)._nid > in(2)._nid ) // Equals sorts by NID otherwise: non.high == non.low becomes non.low == non.high - else if( in(1)._nid > in(2)._nid ) - return new EQ(in(2),in(1)); + return in(1)._type instanceof TypeFloat ? new EQF(in(2),in(1)) : new EQ(in(2),in(1)); } // Equals X==0 becomes a !X if( (in(2)._type == TypeInteger.ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) @@ -69,7 +77,12 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } Node copyF() { return new EQF(null,null); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } Node copyF() { return new LTF(null,null); }} + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } Node copyF() { return new LEF(null,null); } } + + public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copyF() { return null; } } + public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copyF() { return null; } } + public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copyF() { return null; } } + } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b605071b..07ba0fa4 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -52,16 +52,17 @@ public abstract class CFGNode extends Node { public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } // Return the immediate dominator of this Node and compute dom tree depth. - public CFGNode idom() { return cfg(0); } + public CFGNode idom(Node dep) { return cfg(0); } + public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode idom(CFGNode rhs) { + public CFGNode _idom(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { var comp = lhs.idepth() - rhs.idepth(); - if( comp >= 0 ) lhs = lhs.idom(); - if( comp <= 0 ) rhs = rhs.idom(); + if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java new file mode 100644 index 00000000..36fd4524 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class DivFNode extends Node { + public DivFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "DivF"; } + + @Override public String glabel() { return "/"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("/"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()/i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Div of 1. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new DivFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 08ce70b8..e0c95019 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -40,4 +40,5 @@ public class DivNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } + @Override Node copyF() { return new DivFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 296237f4..244a0919 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -61,9 +61,13 @@ public class LoadNode extends MemOpNode { if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); - return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) { + if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate + + Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); + return new PhiNode(_name,_type,memphi.region(),ld1,ld2); + } } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index c662dee6..22862cb9 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -30,7 +30,7 @@ public class LoopNode extends RegionNode { // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } // 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(Node dep) { return entry(); } @Override public int loopDepth() { if( _loopDepth!=0 ) return _loopDepth; // Was already set @@ -60,8 +60,11 @@ public class LoopNode extends RegionNode { // directly on the If) we found our exit. CFGNode x = back(); while( x != this ) { - if( x instanceof CProjNode exit ) - return; // Found an exit, not an infinite loop + if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { + Node other = iff.cproj(1-exit._idx); + if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit ) + return; // Found an exit, not an infinite loop + } x = x.idom(); } // Found a no-exit loop. Insert an exit diff --git a/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java new file mode 100644 index 00000000..9727f58b --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MinusFNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class MinusFNode extends Node { + public MinusFNode(Node in) { super(null, in); } + + @Override public String label() { return "MinusF"; } + + @Override public String glabel() { return "-"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("(-"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0) + return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0; + return TypeFloat.BOT; + } + + @Override + public Node idealize() { + // -(-x) is x + if( in(1) instanceof MinusFNode minus ) + return minus.in(1); + + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 9b687613..ae8e9e1b 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -33,4 +33,5 @@ public class MinusNode extends Node { return null; } + @Override Node copyF() { return new MinusFNode(null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MulFNode.java b/src/main/java/com/seaofnodes/simple/node/MulFNode.java new file mode 100644 index 00000000..2d44a9fb --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MulFNode.java @@ -0,0 +1,51 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class MulFNode extends Node { + public MulFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "MulF"; } + + @Override public String glabel() { return "*"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("*"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()*i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new MulFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 7e9f88a2..8c8a6e0a 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -54,4 +54,5 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } + @Override Node copyF() { return new MulFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 379e140d..ac9c0045 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -9,4 +9,12 @@ public interface MultiNode extends OutNode { return prj; return null; } + + // Find a projection by index + default CProjNode cproj( int idx ) { + for( Node out : outs() ) + if( out instanceof CProjNode prj && prj._idx==idx ) + return prj; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java index f50d3503..e77ed653 100644 --- a/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; + import java.util.BitSet; // "Never true" for infinite loop exits @@ -13,7 +15,7 @@ public class NeverNode extends IfNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); } - @Override public Type compute() { return TypeInteger.BOT; } + @Override public Type compute() { return TypeTuple.IF_BOTH; } @Override public Node idealize() { return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index fc49ad6a..52282737 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,10 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IRPrinter; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; import java.util.*; import java.util.function.Function; @@ -236,6 +236,7 @@ public abstract class Node implements OutNode { */ public void kill( ) { unlock(); + moveDepsToWorklist(); assert isUnused(); // Has no uses, so it is dead _type=null; // Flag as dead while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes @@ -546,6 +547,27 @@ public abstract class Node implements OutNode { /** Pinned in the schedule */ public boolean isPinned() { return false; } + // Semantic change to the graph (so NOT a peephole), used by the Parser. + // If any input is a float, flip to a float-flavored opcode and widen any + // non-float input. + public final Node widen() { + if( !hasFloatInput() ) return this; + Node flt = copyF(); + if( flt==null ) return this; + for( int i=1; itop, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index a07dc140..ebed8dd1 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -100,10 +100,10 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)region().in(nullx); - while( idom.in(0) != iff ) idom = idom.idom(); + while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index dcc7ccef..d5105614 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -99,12 +99,12 @@ public class RegionNode extends CFGNode { return _idepth=d; } - @Override public CFGNode idom() { + @Override public CFGNode idom(Node dep) { CFGNode lca = null; // Walk the LHS & RHS idom trees in parallel until they match, or either fails. // Because this does not cache, it can be linear in the size of the program. for( int i=1; i unreach ) { } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 94b2ad6d..ab567bae 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -59,7 +59,7 @@ public class StopNode extends CFGNode { d = Math.max(d,((CFGNode)n).idepth()+1); return _idepth=d; } - @Override public CFGNode idom() { return null; } + @Override public CFGNode idom(Node dep) { return null; } @Override public int loopDepth() { return (_loopDepth=1); } diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java new file mode 100644 index 00000000..b591718d --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; + +import java.util.BitSet; + +public class SubFNode extends Node { + public SubFNode(Node lhs, Node rhs) { super(null, lhs, rhs); } + + @Override public String label() { return "SubF"; } + + @Override public String glabel() { return "-"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + in(1)._print0(sb.append("("), visited); + in(2)._print0(sb.append("-"), visited); + return sb.append(")"); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeFloat i0 && + in(2)._type instanceof TypeFloat i1) { + if (i0.isConstant() && i1.isConstant()) + return TypeFloat.constant(i0.value()-i1.value()); + } + return in(1)._type.meet(in(2)._type); + } + + @Override + public Node idealize() { + Node lhs = in(1); + Type t2 = in(2)._type; + + // Sub of 0. + if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) + return lhs; + + return null; + } + @Override Node copy(Node lhs, Node rhs) { return new SubFNode(lhs,rhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 5ddcdb68..f0c77743 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -31,6 +31,7 @@ public class SubNode extends Node { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); } + return in(1)._type.meet(in(2)._type); } @@ -48,4 +49,5 @@ public class SubNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } + @Override Node copyF() { return new SubFNode(null,null); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java new file mode 100644 index 00000000..1d147cf6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -0,0 +1,30 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.BitSet; + +public class ToFloatNode extends Node { + public ToFloatNode(Node lhs) { super(null, lhs); } + + @Override public String label() { return "ToFloat"; } + + @Override public String glabel() { return "(flt)"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return in(1)._print0(sb.append("(flt)"), visited); + } + + @Override + public Type compute() { + if (in(1)._type instanceof TypeInteger i0 && i0.isConstant() ) + return TypeFloat.constant(i0.value()); + return TypeFloat.BOT; + } + + @Override public Node idealize() { return null; } + @Override Node copy(Node lhs, Node rhs) { return new ToFloatNode(lhs); } +} diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index aa0ba1ea..f3152719 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -33,11 +33,12 @@ public class Type { static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) static final byte TSIMPLE = 4; // End of the Simple Types static final byte TINT = 5; // All Integers; see TypeInteger - static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel - static final byte TMEM = 7; // All memory (alias 0) or A slice of memory - with specific alias - static final byte TMEMPTR = 8; // Memory pointer type - static final byte TSTRUCT = 9; // Structs; tuples with named fields - static final byte TFLD =10; // Fields into struct + static final byte TFLT = 6; // All Integers; see TypeInteger + static final byte TTUPLE = 7; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TMEM = 8; // All memory (alias 0) or A slice of memory - with specific alias + static final byte TMEMPTR = 9; // Memory pointer type + static final byte TSTRUCT =10; // Structs; tuples with named fields + static final byte TFLD =11; // Fields into struct public final byte _type; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java new file mode 100644 index 00000000..36bc61f5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -0,0 +1,101 @@ +package com.seaofnodes.simple.type; + +import java.util.ArrayList; + +/** + * Float Type + */ +public class TypeFloat extends Type { + + public final static TypeFloat TOP = make(false, 0); + public final static TypeFloat BOT = make(false, 1); + public final static TypeFloat ZERO= make(true , 0); + + public final boolean _is_con; + + /** + * The constant value or + * if not constant then 1=bottom, 0=top. + */ + public final double _con; + + private TypeFloat(boolean is_con, double con) { + super(TFLT); + _is_con = is_con; + _con = con; + } + public static TypeFloat make(boolean is_con, double con) { + return new TypeFloat(is_con,con).intern(); + } + + public static TypeFloat constant(double con) { return make(true, con); } + + public static void gather(ArrayList ts) { ts.add(ZERO); ts.add(BOT); } + + // FIXME this display format is problematic + // In visualizer '#' gets prepended if its a constant + @Override + public StringBuilder _print(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append(_con); + } + + @Override public String str() { + if( this==TOP ) return "~flt"; + if( this==BOT ) return "flt"; + return ""+_con; + } + + /** + * Display Type name in a format that's good for IR printer + */ + @Override + public StringBuilder typeName(StringBuilder sb) { + if( this==TOP ) return sb.append("FltTop"); + if( this==BOT ) return sb.append("FltBot"); + return sb.append("Int"); + } + + @Override + public boolean isHighOrConst() { return _is_con || _con==0; } + + @Override + public boolean isConstant() { return _is_con; } + + public double value() { return _con; } + + @Override + public Type xmeet(Type other) { + // Invariant from caller: 'this' != 'other' and same class (TypeFloat) + TypeFloat i = (TypeFloat)other; // Contract + // BOT wins + if ( this==BOT ) return this; + if ( i ==BOT ) return i ; + // TOP loses + if ( i ==TOP ) return this; + if ( this==TOP ) return i ; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return BOT; + } + + @Override + public Type dual() { + if( isConstant() ) return this; // Constants are a self-dual + return _con==0 ? BOT : TOP; + } + + @Override + public Type glb() { return BOT; } + + @Override public TypeFloat makeInit() { return ZERO; } + + @Override + int hash() { return (int)(Double.hashCode(_con) ^ (_is_con ? 0 : 0x4000)); } + @Override + public boolean eq( Type t ) { + TypeFloat i = (TypeFloat)t; // Contract + return _con==i._con && _is_con==i._is_con; + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 98fd181b..6aa74125 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 2abce3cb..64bbf245 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; -import org.junit.BeforeClass; import org.junit.Test; import org.junit.Ignore; diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 7371ff18..4a9521b9 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,7 +1,12 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.*; import org.junit.Test; + +import java.util.Arrays; + import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -259,7 +264,6 @@ while(arg) { v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; - } return ret; """); diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index fdf56b56..a8b09226 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -292,7 +292,7 @@ else { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString()); + assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString()); } @@ -434,7 +434,7 @@ while(1) arg = arg+ptr.v; """); StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); + assertEquals("Stop[ return 0; return 0; ]", stop.toString()); } @Test @@ -496,7 +496,7 @@ return v; @Test public void testExample2() { Parser parser = new Parser( - """ + """ struct S { int f; } S v = new S; int i = arg; @@ -507,7 +507,7 @@ while (arg > 0) { arg = arg - 1; } return v; -"""); + """); StopNode stop = parser.parse().iterate(); //assertEquals("return new S;", stop.toString()); } @@ -528,38 +528,4 @@ return s.f; assertEquals(1L, Evaluator.evaluate(stop, 1)); assertEquals(0L, Evaluator.evaluate(stop, 2)); } - - @Test - public void testScheduleUse() { - Parser parser = new Parser( -""" -int v0=0; -while(0>=0) { - int v1=0; - v1=v0; - if(v1*0) - v0=-v1; -} -return 0; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - } - - @Test - public void testLoopCarriedDep() { - Parser parser = new Parser( -""" -int v0=0; -{ - int v1=0; - while(v1) { - v1=1+(v0!=0); - v0=v1/0; - } -} -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return 0;", stop.toString()); - } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java new file mode 100644 index 00000000..af8fdfe9 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; + + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter12Test { + @Test + public void testJig() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testFloat() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testSquareRoot() { + Parser parser = new Parser( +""" +flt guess = arg; +while( 1 ) { + flt next = (arg/guess + guess)/2; + if( next == guess ) break; + guess = next; +} +return guess; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return Phi(Loop9,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); + assertEquals(3.0, Evaluator.evaluate(stop, 9)); + assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testFPOps() { + Parser parser = new Parser( +""" +flt x = arg; +return x+1==x; +"""); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 1)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index 32c9c0c5..5def2782 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -46,7 +46,7 @@ S v0=new S; if(arg) v0.f=1; return v0; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); var eval = new Evaluator(stop); assertObj(eval.evaluate(0, 10), "S", 0L); assertObj(eval.evaluate(1, 10), "S", 1L); @@ -65,7 +65,7 @@ i=v.f; if (arg) v.f=1; return i; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); var eval = new Evaluator(stop); assertEquals(2L, eval.evaluate(0, 10)); assertEquals(2L, eval.evaluate(1, 10)); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 4a405a3b..3512d2e9 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -2,10 +2,7 @@ package com.seaofnodes.simple.evaluator; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.Field; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.type.TypeMemPtr; -import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.type.*; import java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; @@ -80,6 +77,10 @@ public class Evaluator { long in2 = vall(div.in(2)); return in2 == 0 ? 0 : vall(div.in(1)) / in2; } + private double div(DivFNode div) { + double in2 = vald(div.in(2)); + return in2 == 0 ? 0 : vald(div.in(1)) / in2; + } private Object alloc(NewNode alloc) { var type = ((TypeMemPtr)alloc.compute())._obj; @@ -115,10 +116,16 @@ public class Evaluator { if (v instanceof Number n) return n.longValue(); throw new AssertionError("Not a long " + v); } + private double vald(Node node) { + var v = val(node); + if (v instanceof Number n) return n.doubleValue(); + throw new AssertionError("Not a double " + v); + } private Object cons(ConstantNode cons) { var type = cons.compute(); if (type instanceof TypeInteger i) return i.value(); + if (type instanceof TypeFloat i) return i.value(); assert type instanceof TypeMemPtr; return null; } @@ -127,15 +134,24 @@ public class Evaluator { return switch (node) { case ConstantNode cons -> cons(cons); case AddNode add -> vall(add.in(1)) + vall(add.in(2)); + case AddFNode add -> vald(add.in(1)) + vald(add.in(2)); + case BoolNode.EQF eq -> vald(eq.in(1)) == vald(eq.in(2)) ? 1L : 0L; + case BoolNode.LEF le -> vald(le.in(1)) <= vald(le.in(2)) ? 1L : 0L; + case BoolNode.LTF lt -> vald(lt.in(1)) < vald(lt.in(2)) ? 1L : 0L; case BoolNode.EQ eq -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; case BoolNode.LE le -> vall(le.in(1)) <= vall(le.in(2)) ? 1L : 0L; case BoolNode.LT lt -> vall(lt.in(1)) < vall(lt.in(2)) ? 1L : 0L; case DivNode div -> div(div); + case DivFNode div -> div(div); case MinusNode minus -> -vall(minus.in(1)); + case MinusFNode minus -> -vald(minus.in(1)); case MulNode mul -> vall(mul.in(1)) * vall(mul.in(2)); + case MulFNode mul -> vald(mul.in(1)) * vald(mul.in(2)); case NotNode not -> isTrue(val(not.in(1))) ? 0L : 1L; case SubNode sub -> vall(sub.in(1)) - vall(sub.in(2)); + case SubFNode sub -> vald(sub.in(1)) - vald(sub.in(2)); case CastNode cast -> val(cast.in(1)); + case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); case NewNode alloc -> alloc(alloc); diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 155063ab..b8437b50 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -22,6 +22,7 @@ public class ScriptGenerator { private static final int MAX_NAME_LENGTH = 10; private static final int MAX_BLOCK_DEPTH = 4; private static final int MAX_EXPRESSION_DEPTH = 10; + private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; /** * Number of spaces per indentation @@ -68,7 +69,7 @@ public class ScriptGenerator { } private static class TypeStruct extends Type { - record Field (String name, Type type) {} + record Field (String name, Type type, TypeStruct struct) {} final Field[] fields; final TypeNullable nullable = new TypeNullable(this); TypeStruct(String name, Field[] fields) { @@ -89,7 +90,21 @@ public class ScriptGenerator { } - private static final Type TYPE_INT = new Type("int"); + private static final Type TYPE_FLT = new Type("flt"); + + private static class TypeInt extends Type { + + TypeInt() { + super("int"); + } + + @Override + boolean isa(Type other) { + return super.isa(other) || other == TYPE_FLT; + } + } + + private static final Type TYPE_INT = new TypeInt(); private static class Variable { @@ -343,7 +358,9 @@ public class ScriptGenerator { * @return A random type */ private Type getType() { - if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT; + int t = random.nextInt(10); + if( t<5 || structs.isEmpty() ) return TYPE_INT; + if( t<7 ) return TYPE_FLT; var idx = random.nextInt(structs.size()); TypeStruct struct = structs.get(idx); if (random.nextBoolean()) return struct.nullable; @@ -411,17 +428,18 @@ public class ScriptGenerator { public int genStruct() { var name = getStructName(); var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; + var struct = new TypeStruct(name, fields); sb.append("struct ").append(name).append(" {\n"); indentation += INDENTATION; for (int i=0; i 3) { @@ -561,7 +579,7 @@ public class ScriptGenerator { */ public int genWhile() { sb.append("while("); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") "); loopDepth++; genStatementBlock(); @@ -587,17 +605,17 @@ public class ScriptGenerator { indentation += INDENTATION; String name = getVarName(); printIndentation().append("int ").append(name).append("="); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); addVariable(name, TYPE_INT); printIndentation().append("while(").append(name).append("<"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") {\n"); indentation += INDENTATION; depth--; loopDepth++; printIndentation().append(name).append("=").append(name).append("+"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); genStatements(); loopDepth--; @@ -621,7 +639,7 @@ public class ScriptGenerator { sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name); if (!(type instanceof TypeNullable) || random.nextBoolean()) { sb.append("="); - genExpression(type); + genExpression(type, true); } sb.append(";"); addVariable(name, type); @@ -656,7 +674,7 @@ public class ScriptGenerator { declared = field.type; } sb.append("="); - genExpression(declared); + genExpression(declared, true); sb.append(";"); return 0; } @@ -668,7 +686,7 @@ public class ScriptGenerator { public int genReturn() { var type = getType(); sb.append("return "); - genExpression(type); + genExpression(type, true); sb.append(";"); return FLAG_STOP; } @@ -677,70 +695,91 @@ public class ScriptGenerator { * Generate a binary expression. * This method does not care about operator precedence. */ - public void genExpression(Type type) { - if (generateInvalid()) type = getType(); - if (type != TYPE_INT) { - genUnary(type); + public void genExpression(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); + if (type != TYPE_INT && type != TYPE_FLT) { + genUnary(type, false); return; } var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { - genUnary(TYPE_INT); + genUnary(type, false); sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); } - genUnary(TYPE_INT); + genUnary(type, false); } /** * Generate a unary expression. */ - public void genUnary(Type type) { - if (generateInvalid()) type = getType(); - if (type != TYPE_INT) { - genSuffix(type); + public void genUnary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); + if (type != TYPE_INT && type != TYPE_FLT) { + genSuffix(type, false); return; } var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); } - genSuffix(TYPE_INT); + genSuffix(type, false); + } + + public TypeStruct.Field getField(Type type) { + int n=0; + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) n++; + } + } + if (n==0) return null; + n = random.nextInt(n); + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) if (n--==0) return f; + } + } + throw new AssertionError(); } /** * Generate */ - public void genSuffix(Type type) { - if (generateInvalid()) type = getType(); - if (type == TYPE_INT && random.nextBoolean()) { - var t = getType(); + public void genSuffix(Type type, boolean change) { + genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH); + } + + public void genSuffixRecursive(Type type, boolean change, int depth) { + if (change && generateInvalid()) type = getType(); + if (depth > 0 && random.nextBoolean()) { if (generateInvalid()) { var field = getRandomName(); - genPrimary(t); + var t = getType(); + genSuffixRecursive(t, true, depth-1); sb.append(".").append(field); return; - } else if (t instanceof TypeStruct s && s.fields.length > 0) { - var field = s.fields[random.nextInt(s.fields.length)]; - if (field.type == TYPE_INT) { - genPrimary(t); + } else { + var field = getField(type); + if (field != null) { + genSuffixRecursive(field.struct, true, depth-1); sb.append(".").append(field.name); return; } } } - genPrimary(type); + genPrimary(type, false); } /** * Generate a primary expression. */ - public void genPrimary(Type type) { - if (generateInvalid()) type = getType(); + public void genPrimary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); var rand = random.nextInt(10); if (rand == 0 && exprDepth != 0) { sb.append("("); exprDepth--; - genExpression(type); + genExpression(type, false); exprDepth++; sb.append(")"); } else if (rand < 6) { @@ -755,13 +794,15 @@ public class ScriptGenerator { */ public void genConst(Type type) { if (generateInvalid()) type = getType(); - if (type == TYPE_INT) { + if (type == TYPE_INT || (type == TYPE_FLT && random.nextBoolean())) { var rand = random.nextInt(10); switch (rand) { case 0 -> sb.append("true"); case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } + } else if (type == TYPE_FLT) { + sb.append(random.nextFloat()); } else if (type instanceof TypeNullable n) { if (random.nextBoolean()) { sb.append("null"); -- cgit v1.2.3