From 9ed409df4516e0089afbc7d5ccf9b029d431be04 Mon Sep 17 00:00:00 2001 From: Thalia Archibald Date: Sun, 3 Mar 2024 17:55:47 +0000 Subject: Chapter 9: Global Value Numbering and Iterative Peepholes Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Robert Obkircher Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe --- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 42 +++++++++++ .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 86 +++++++++++++++++++++- .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 2 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 32 ++++---- 4 files changed, 139 insertions(+), 23 deletions(-) (limited to 'src/test/java/com/seaofnodes/simple/fuzzer') diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 5fcd8764..936fb41e 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; @@ -107,6 +109,45 @@ public class Fuzzer { } } + /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + 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; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + /** * Run one test with the given seed. * @param seed The seed to use for generating this test case @@ -118,6 +159,7 @@ public class Fuzzer { check(sb.toString(), valid); } + /** * Check that no exceptions happened. * @return true if no exception happened diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 37a57e11..f13a51e1 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,14 +1,78 @@ package com.seaofnodes.simple.fuzzer; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + /** * Some utilities for the fuzzer. */ class FuzzerUtils { + /** + * Get the value of a private field + */ + @SuppressWarnings("unchecked") + public static T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Copy of Node.WVISIST + * Used to clear as exceptions might happen in the walk and left this bitset not cleared + */ + private static final BitSet NodeWalkVisit; + + /** + * Write access to Iterate.MID_ASSERT + * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing. + */ + private static final MethodHandle set_MID_ASSERT; + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + static { + try { + NodeWalkVisit = getFieldValue(Node.class, "WVISIT"); + set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT")); + } catch (Exception e) { + throw new ExceptionInInitializerError(e); + } + } + /** * Check that eiter one of the objects is null or that both are equal. */ @@ -50,9 +114,25 @@ class FuzzerUtils { * Parse script with peepholes enabled or disabled */ public static StopNode parse(String script, boolean runPeeps) { - var parser = new Parser(script); - Node._disablePeephole = !runPeeps; - return parser.parse(); + var err = System.err; + var out = System.out; + try { + System.setErr(NULL_PRINT_STREAM); + System.setOut(NULL_PRINT_STREAM); + try { + set_MID_ASSERT.invokeExact(false); + } catch (Throwable e) { + throw rethrow(e); + } + var parser = new Parser(script); + Node._disablePeephole = !runPeeps; + var stop = parser.parse(); + return runPeeps ? stop.iterate() : stop; + } finally { + NodeWalkVisit.clear(); + System.setErr(err); + System.setOut(out); + } } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java index b7fc18ec..2ef0a3fd 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -32,8 +32,8 @@ public class Reducer { new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "1"), new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), new Replace(Pattern.compile("\\d+\\+"), ""), new Replace(Pattern.compile("\\+\\d+"), ""), new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 148c2319..ad98f7e2 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -15,20 +15,6 @@ import java.util.Random; */ public class ScriptGenerator { - /** - * Get the list of keywords from the parser. - */ - @SuppressWarnings("unchecked") - private static HashSet getKeywords() { - try { - var field = Parser.class.getDeclaredField("KEYWORDS"); - field.setAccessible(true); - return (HashSet) field.get(new Parser("")); - } catch (Throwable e) { - throw new ExceptionInInitializerError(e); - } - } - /** * Number of spaces per indentation */ @@ -40,7 +26,15 @@ public class ScriptGenerator { /** * List of keywords not valid for identifiers. */ - private static final HashSet KEYWORDS = getKeywords(); + private static final HashSet KEYWORDS; + + static { + try { + KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS"); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } /** * Flag for a statement that it does not pass on control flow to the next statement. @@ -83,11 +77,11 @@ public class ScriptGenerator { /** * The depth of blocks allowed. */ - private int depth = 7; + private int depth = 20; /** * The depth of expressions allowed. */ - private int exprDepth = 3; + private int exprDepth = 30; /** * Current variables in scope. */ @@ -141,7 +135,7 @@ public class ScriptGenerator { * @return The random name generated */ private StringBuilder getRandomName() { - int len = random.nextInt(10) + 1; + int len = random.nextInt(30) + 1; StringBuilder sb = new StringBuilder(len); sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); for (int i=1; i