/jog

Pattern-Based Peephole Optimizations with Java JIT Tests

Primary LanguageJavaApache License 2.0Apache-2.0

JOG

JOG is a framework that facilitates developing Java JIT peephole optimizations. JOG enables developers to write a pattern, in Java itself, that specifies desired code transformations by writing code before and after the optimization, as well as any necessary preconditions. Such patterns can be written in the same way that tests of the optimization are already written in OpenJDK. JOG translates each pattern into C/C++ code that can be integrated as a JIT optimization pass. JOG also generates Java tests for optimizations from patterns. Furthermore, JOG can automatically detect possible shadow relation between a pair of optimizations where the effect of the shadowed optimization is overridden by another.

Table of contents

  1. Requirements
  2. Example
  3. Hall of Fame
  4. Citation
  5. Contact

Requirements

  • Linux with GNU Bash (tested on Ubuntu 20.04 with GNU Bash 5.0.17(1)-release (x86_64-pc-linux-gnu))
  • JDK >=11

We also provide a docker image with pre-built OpenJDK and cloned jog repository.

docke pull zzqut/jog:latest

Example

Developers write Java JIT peephole optimizations in patterns, using JOG's DSL fully embedded in Java. For example, Example.java contains two patterns ADD2 and ADD7. ADD2 represents a peephole optimization that transforms (a - b) + (c - d) to (a + c) - (b + d), and ADD7 expresses a peephole optimization that transforms (a - b) + (b - c) to (a - c).

import jog.api.*;

import static jog.api.Action.*;

public class Example {

    @Pattern
    public void ADD2(long a, long b, long c, long d) {
        before((a - b) + (c - d));
        after((a + c) - (b + d));
    }

    @Pattern
    public void ADD7(long a, long b, long c) {
        before((a - b) + (b - c));
        after(a - c);
    }
}

From the patterns, JOG

  1. Generates C/C++ code that can be integrated as JIT optimization pass.

    JOG translates every pattern into corresponding optimization pass in C/C++.

    gen-code/addnode.cpp

    /* Automatically generated by jog from patterns: 
ADD2,
ADD7. */
Node* AddLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
// ADD2
{
Node* _JOG_in1 = in(1);
Node* _JOG_in11 = _JOG_in1 != NULL && 1 < _JOG_in1->req() ? _JOG_in1->in(1) : NULL;
Node* _JOG_in12 = _JOG_in1 != NULL && 2 < _JOG_in1->req() ? _JOG_in1->in(2) : NULL;
Node* _JOG_in2 = in(2);
Node* _JOG_in21 = _JOG_in2 != NULL && 1 < _JOG_in2->req() ? _JOG_in2->in(1) : NULL;
Node* _JOG_in22 = _JOG_in2 != NULL && 2 < _JOG_in2->req() ? _JOG_in2->in(2) : NULL;
if (_JOG_in1->Opcode() == Op_SubL
    && _JOG_in2->Opcode() == Op_SubL) {
return new SubLNode(phase->transform(new AddLNode(_JOG_in11, _JOG_in21)), phase->transform(new AddLNode(_JOG_in12, _JOG_in22)));
}
}

// ADD7
{
Node* _JOG_in1 = in(1);
Node* _JOG_in11 = _JOG_in1 != NULL && 1 < _JOG_in1->req() ? _JOG_in1->in(1) : NULL;
Node* _JOG_in12 = _JOG_in1 != NULL && 2 < _JOG_in1->req() ? _JOG_in1->in(2) : NULL;
Node* _JOG_in2 = in(2);
Node* _JOG_in21 = _JOG_in2 != NULL && 1 < _JOG_in2->req() ? _JOG_in2->in(1) : NULL;
Node* _JOG_in22 = _JOG_in2 != NULL && 2 < _JOG_in2->req() ? _JOG_in2->in(2) : NULL;
if (_JOG_in1->Opcode() == Op_SubL
    && _JOG_in2->Opcode() == Op_SubL
    && _JOG_in12 == _JOG_in21) {
return new SubLNode(_JOG_in11, _JOG_in22);
}
}
}

  2. Generates Java tests that can be used to test such optimizations.

    The IR test, written in Java using IR test framework, is a recommended approach in OpenJDK to testing JIT peephole optimizations. JOG can automatically generate a IR test from every pattern.

    gen-tests/TestAddLNode.java

    /*Automatically generated by jog from patterns: 
ADD2,
ADD7.*/
package compiler.c2.irTests;

import jdk.test.lib.Asserts;
import compiler.lib.ir_framework.*;

/*@test
@library /test/lib /
@run driver compiler.c2.irTests.TestAddLNode*/
public class TestAddLNode {

    public static void main(String[] args) {
        TestFramework.run();
    }

    @Run(test = { "testADD2", "testADD7" })
    public void runMethod() {
        long a = RunInfo.getRandom().nextLong();
        long b = RunInfo.getRandom().nextLong();
        long c = RunInfo.getRandom().nextLong();
        long d = RunInfo.getRandom().nextLong();
        long min = Long.MIN_VALUE;
        long max = Long.MAX_VALUE;
        assertResult(0, 0, 0, 0);
        assertResult(a, b, c, d);
        assertResult(min, min, min, min);
        assertResult(max, max, max, max);
    }

    @DontCompile
    public void assertResult(long a, long b, long c, long d) {
        Asserts.assertEQ((a - b) + (c - d), testADD2(a, b, c, d));
        Asserts.assertEQ((a - b) + (b - c), testADD7(a, b, c));
    }

    // Checks (a - b) + (c - d) => (a + c) - (b + d)
    @Test
    @IR(counts = { IRNode.ADD, "2", IRNode.SUB, "1" })
    public long testADD2(long a, long b, long c, long d) {
        return (a - b) + (c - d);
    }

    // Checks (a - b) + (b - c) => a - c
    @Test
    @IR(failOn = { IRNode.ADD })
    @IR(counts = { IRNode.SUB, "1" })
    public long testADD7(long a, long b, long c) {
        return (a - b) + (b - c);
    }
}

  3. Detects any possible shadow relation between a pair of optimizations.

    Note that any expression matching (a - b) + (c - a) (ADD2) also matches (a - b) + (b - c) (ADD7), which means ADD2 can be applied wherever ADD7 can be applied, so the effect of ADD2 will shadow ADD7 if ADD2 is always applied before ADD7 in a compiler pass. JOG can automatically report the shadow relations.

    shadows.yml

    -
  shadowing:
    name: ADD2
    before: "(a - b) + (c - d)"
    precondition: []
  shadowed:
    -
      name: ADD7
      before: "(a - b) + (b - c)"
      precondition: []

To run the example, please run ./demo.sh:

$ ./demo.sh
Building JOG...
Reading the patterns from file Example.java...
See gen-code/ for generated compiler pass in C/C++.
See gen-tests/ for generated JIT optimization tests in Java.
Shadow relations:
Pattern ADD2 shadows ADD7

Hall Of Fame

Here is the list of pull requests we opened for OpenJDK:

New optimizations:

  • #6441: 8277882: New subnode ideal optimization: converting "c0 - (x + c1)" into "(c0 - c1) - x".

  • #6675: 8278114: New addnode ideal optimization: converting "x + x" into "x << 1".

  • #6858: 8279607: Existing optimization "~x+1" -> "- x" can be generalized to "~x+c" -> "(c-1)-x".

  • #7795: 8283094: Add Ideal transformation: x + (con - y) -> (x - y) + con.

  • #7376: 8281453: New optimization: convert ~x into -1-x when ~x is used in an arithmetic expression.

  • #7395: 8281518: New optimization: convert "(x|y)-(x^y)" into "x&y".

  • #16333: Add Ideal transformation: (~a) & (~b) => ~(a | b)

  • #16334: Add Ideal transformation: (~a) | (~b) => ~(a & b)

New tests:

  • #11049: 8297384: Add IR tests for existing idealizations of arithmetic nodes.

Fix detected shadowed optimizations:

  • #6752: 8278471: Remove unreached rules in AddNode::IdealIL.

Citation

If you use JOG in your research, please cite our ISSTA'23 paper and ICSE'24 Demo paper.

@inproceedings{zang23jog,
  author = {Zang, Zhiqiang and Thimmaiah, Aditya and Gligoric, Milos},
  title = {Pattern-Based Peephole Optimizations with {J}ava {JIT} Tests},
  booktitle = {International Symposium on Software Testing and Analysis},
  pages = {64--75},
  year= {2023},
  doi = {10.1145/3597926.3598038},
}
@inproceedings{zang24jogtool,
  title = {{JOG}: Java {JIT} Peephole Optimizations and Tests from Patterns},
  author = {Zang, Zhiqiang and Thimmaiah, Aditya and Gligoric, Milos},
  booktitle = {International Conference on Software Engineering, Tool Demonstrations Track},
  pages = {to apear},
  year= {2024},
  doi = {10.1145/3639478.3640040}
}

Contact

Let me (Zhiqiang Zang) know if you have any questions.