[GR-71793] A collection of new optimisations for IntegerEqualsNode

[default-jamc]

Overview

Hi,

I noticed that there may be several new optimisations that can be added to IntegerEqualsNode, specifically relating to AbsNode, NotNode, NegateNode, SubNode and ConditionalNode.

// AbsNode/NotNode optimisation
(1) ~x == abs(x) |-> false
    when bits(x) >= 1

// NotNode/NegateNode optimisation
(2) -x == ~x |-> false
    when bits(x) >= 1

// NegateNode/SubNode optimisation
(3) -x == (y - x) |-> y == 0

// NegateNode optimisations
(4) -x == 0 |-> x == 0
(5) -x == -y |-> x == y

// NotNode optimisations
(6) ~x == 0 |-> x == -1
(7) ~x == -1 |-> x == 0
(8) ~x == ~y |-> x == y

// ConditionalNode optimisations
(9) (c ? x : y) == x |-> c 
    when (x != y) after evaluation
(10) (c ? y : x) == x |-> !c 
    when (x != y) after evaluation

These optimisations have also been formally verified in an interactive theorem prover (Isabelle/HOL).

Considerations

Optimisations with conditions

Four of the optimisations, namely (1), (2), (9) and (10), only hold when particular conditions are met. Specifically:

• For (1) and (2), x's stamp must have at least one bit (assuming that an IntegerStamp with 0 bits is valid, and any two operands with such a stamp are considered equal).
• For (9) and (10), x must not be equal to y after they are evaluated (See Potential bug in IntegerEqualsNode create method #6907).

Commutativity permutations

• All of the optimisations (except for (5) and (8)) have an additional permutation owing to IntegerEqualsNode's commutativity property.

Optimisation (#)	Optimisation	Permutations
1	~x == abs(x)	abs(x) == ~x
2	-x == ~x	~x == -x
3	-x == (y - x)	(y - x) == -x
4	-x == 0	0 == -x
6	~x == 0	0 == ~x
7	~x == -1	-1 == ~x
9	(c ? x : y) == x	x == (c ? x : y)
10	(c ? y : x) == x	x == (c ? y : x)

Pre-existing solutions

• It seems as though a syntactically different (but mathematically equivalent) variant of optimisation (3) is already considered by IntegerEqualsNode. This implementation could be extended to account for optimisation (3).

// Pre-existing optimisations
(x - y) == x |-> y == 0

x == (x - y) |-> y == 0

https://github.com/oracle/graal/blob/master/compiler/src/jdk.graal.compiler/src/jdk/graal/compiler/nodes/calc/IntegerEqualsNode.java#L211-L225

Sample Program

I used the following sample program to determine whether these optimisations provide any runtime speed improvements. For each optimisation, I changed the Unoptimised and Optimised lines to match its unoptimised and optimised version.

public class BinaryExprTest {

  public static void main(String[] args) {
    long start = System.nanoTime();
    long sum = 0;
    for (int i = 1; i < 1000000; i++) {
      sum += calculate(i);
    }
    System.out.println(sum);
    long end = System.nanoTime();
    System.out.println("Time taken: " + ((end - start) / 1000000) + "ms");
  }

  static int calculate(int i) {
    int m = 1;
    int s = i;
    boolean condition = false;
    for (int j = 1; j < 1000; j++) {
      s = s * 137 + j;
      m = calc2(s,j);

      //condition = (-m == ~m); // Unoptimised
      condition = (false);       // Optimised

    }

    return (condition) ? 1 : 2;
  }

  static int calc2(int i, int j) {
    int x = i;
    for (int y = 0; y < 10; y++) {
      x = x + ((j + (i*17)) + y);
    }

    return x;
  }
}

The table below provides an overview of the runtime speed improvements for each optimisation. These runtimes were calculated as an average of running the program several times.

Note that in the sample program, x = m, y = s, and (for optmisations (9) & (10)), c = ((calc2(j,j)) == (i*j+9)).

Optimisation (#)	Unoptimised version	Optimised version	Unoptimised runtime	Optimised runtime	Runtime difference
1	~x == abs(x)	false	3088ms	54ms	-98%
2	-x == ~x	false	2859ms	48ms	-98%
3	-x == (y - x)	y == 0	2801ms	1230ms	-56%
4	-x == 0	x == 0	2782ms	2510ms	-9%
5	-x == -y	x == y	3083ms	2512ms	-18%
6	~x == 0	x == -1	2783ms	2505ms	-9%
7	~x == -1	x == 0	2781ms	2512ms	-9%
8	~x == ~y	x == y	3083ms	2509ms	-18%
9	(c ? x : y) == x	c	3465ms	178ms	-94%
10	(c ? y : x) == x	!c	3476ms	171ms	-95%

Unit Test

I also wrote a set of JUnit tests to check whether these optimisations are applied.

For each optimisation, its corresponding @Test method defines the expected counts of relevant nodes in the post-canonicalization graph. These graphs are then checked to determine whether their node counts match those expected.

package jdk.graal.compiler.core.test;

import jdk.graal.compiler.nodes.calc.AbsNode;
import jdk.graal.compiler.nodes.calc.ConditionalNode;
import jdk.graal.compiler.nodes.calc.IntegerEqualsNode;
import jdk.graal.compiler.nodes.calc.NegateNode;
import jdk.graal.compiler.nodes.calc.NotNode;
import jdk.graal.compiler.nodes.calc.SubNode;
import jdk.graal.compiler.nodes.StructuredGraph;
import jdk.graal.compiler.nodes.ValueNode;
import org.junit.Test;

import java.util.HashMap;

public class NewOptimisationsTest extends GraalCompilerTest {

    /* Optimisations */

    /**
     * (1) (~x == abs(x)) |-> false
     * */
    public static boolean notAbs(int x) {
        return (~x == Math.abs(x));
    }

    /**
     * (2) (-x == ~x) |-> false
     * */
    public static boolean notNegate(int x) {
        return (-x == ~x);
    }

    /**
     * (3) (-x == (y - x)) |-> (y == 0)
     * */
    public static boolean negateSub(int x, int y) {
        return (-x == (y - x));
    }

    /**
     * (4) (-x == 0) |-> (x == 0)
     * */
    public static boolean negateZero(int x) {
        return (-x == 0);
    }

    /**
     * (5) (-x == -y) |-> (x == y)
     * */
    public static boolean negateBoth(int x, int y) {
        return (-x == -y);
    }

    /**
     * (6) (~x == 0) |-> x == -1
     * */
    public static boolean notZero(int x) {
        return (~x == 0);
    }

    /**
     * (7) (~x == -1) |-> x == 0
     * */
    public static boolean notAllOnes(int x) {
        return (~x == -1);
    }

    /**
     * (8) (~x == ~y) |-> (x == y)
     * */
    public static boolean notBoth(int x, int y) {
        return (~x == ~y);
    }

    /**
     * (9) ((c ? x : y) == x) |-> c
     * */
    public static boolean conditional(boolean c, int x, int y) {
        return ((c ? x : y) == x);
    }

    /**
     * (10) ((c ? y : x) == x) |-> !c
     * */
    public static boolean notConditional(boolean c, int x, int y) {
        return ((c ? y : x) == x);
    }

    /* Tests */

    @Test
    public void notAbsTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(IntegerEqualsNode.class, 0);
        nodeCounts.put(NotNode.class, 0);
        nodeCounts.put(AbsNode.class, 0);

        checkOptimisationApplied("notAbs", nodeCounts);
    }

    @Test
    public void notNegateTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NegateNode.class, 0);
        nodeCounts.put(NotNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 0);

        checkOptimisationApplied("notNegate", nodeCounts);
    }

    @Test
    public void negateSubTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NegateNode.class, 0);
        nodeCounts.put(SubNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("negateSub", nodeCounts);
    }

    @Test
    public void negateZeroTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NegateNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("negateZero", nodeCounts);
    }

    @Test
    public void negateBothTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NegateNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("negateBoth", nodeCounts);
    }

    @Test
    public void notZeroTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NotNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("notZero", nodeCounts);
    }

    @Test
    public void notAllOnesTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NotNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("notAllOnes", nodeCounts);
    }

    @Test
    public void notBothTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(NotNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 1);

        checkOptimisationApplied("notBoth", nodeCounts);
    }

    @Test
    public void conditionalTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(ConditionalNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 0);

        checkOptimisationApplied("conditional", nodeCounts);
    }

    @Test
    public void notConditionalTest() {
        HashMap<Class<? extends ValueNode>, Integer> nodeCounts = new HashMap<>();

        nodeCounts.put(ConditionalNode.class, 0);
        nodeCounts.put(IntegerEqualsNode.class, 0);
        nodeCounts.put(NotNode.class, 1);

        checkOptimisationApplied("notConditional", nodeCounts);
    }

    /* Helper methods */

    private void checkOptimisationApplied(String methodName, HashMap<Class<? extends ValueNode>, Integer> nodeCounts) {
        System.out.println("Unoptimised graph:");
        StructuredGraph graph = parseForCompile(getResolvedJavaMethod(methodName));
        printNodes(graph, nodeCounts);

        System.out.println("Optimised graph:");
        createCanonicalizerPhase().apply(graph, getProviders());
        printNodes(graph, nodeCounts);

        // Check for expected optimisation
        assertTrue(correctNodeCounts(graph, nodeCounts));
    }

    /**
     * Prints the name and occurrence of each node type in nodeCounts, in the given graph.
     * */
    private void printNodes(StructuredGraph graph, HashMap<Class<? extends ValueNode>, Integer> nodeCounts) {
        System.out.println("Nodes in graph: ");
        for (Class<? extends ValueNode> node : nodeCounts.keySet()) {
            System.out.println(node.getName() + ": " + graph.getNodes().filter(node).count());
        }
    }

    /**
     * Returns true if the graph contains the expected amount of nodes of each type specified by nodeCounts.
     * */
    private boolean correctNodeCounts(StructuredGraph graph, HashMap<Class<? extends ValueNode>, Integer> nodeCounts) {
        for (Class<? extends ValueNode> node : nodeCounts.keySet()) {
            if (graph.getNodes().filter(node).count() != nodeCounts.get(node)) {
                return false;
            }
        }
        return true;
    }
}

JUnit test output

Running mx unittest NewOptimisationsTest produces the following output:

MxJUnitCore
JUnit version 4.13.2
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 2
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 2
E
notBothTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.ConditionalNode: 1
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 2
jdk.graal.compiler.nodes.calc.NotNode: 0
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.ConditionalNode: 1
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 2
jdk.graal.compiler.nodes.calc.NotNode: 0
E
notConditionalTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
E
notNegateTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
E
notAllOnesTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
E
negateZeroTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
jdk.graal.compiler.nodes.calc.SubNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 1
jdk.graal.compiler.nodes.calc.SubNode: 1
E
negateSubTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.ConditionalNode: 1
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 2
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.ConditionalNode: 1
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 2
E
conditionalTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
E
notZeroTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 2
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.NegateNode: 2
E
negateBothTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...
.Unoptimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.AbsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
Optimised graph:
Nodes in graph: 
jdk.graal.compiler.nodes.calc.IntegerEqualsNode: 1
jdk.graal.compiler.nodes.calc.AbsNode: 1
jdk.graal.compiler.nodes.calc.NotNode: 1
E
notAbsTest(jdk.graal.compiler.core.test.NewOptimisationsTest)
java.lang.AssertionError
	...

Time: 2.36
There were 10 failures:
1) jdk.graal.compiler.core.test.NewOptimisationsTest#notBothTest
java.lang.AssertionError
2) jdk.graal.compiler.core.test.NewOptimisationsTest#notConditionalTest
java.lang.AssertionError
3) jdk.graal.compiler.core.test.NewOptimisationsTest#notNegateTest
java.lang.AssertionError
4) jdk.graal.compiler.core.test.NewOptimisationsTest#notAllOnesTest
java.lang.AssertionError
5) jdk.graal.compiler.core.test.NewOptimisationsTest#negateZeroTest
java.lang.AssertionError
6) jdk.graal.compiler.core.test.NewOptimisationsTest#negateSubTest
java.lang.AssertionError
7) jdk.graal.compiler.core.test.NewOptimisationsTest#conditionalTest
java.lang.AssertionError
8) jdk.graal.compiler.core.test.NewOptimisationsTest#notZeroTest
java.lang.AssertionError
9) jdk.graal.compiler.core.test.NewOptimisationsTest#negateBothTest
java.lang.AssertionError
10) jdk.graal.compiler.core.test.NewOptimisationsTest#notAbsTest
java.lang.AssertionError

FAILURES!!!
Tests run: 10,  Failures: 10

...

[oubidar-Abderrahim]

Thank you for sharing this, we'll take a look into it as soon as possible.

[gergo-]

Thank you for these proposed optimizations, @default-jamc . These seem worth adding. Would you be interested in opening a PR yourself?

For testing, it would probably make most sense to have these in IntegerEqualsCanonicalizationTest, following the convention there: For each pattern, have a test snippet demonstrating the pattern and a reference snippet demonstrating the optimized version, then call the test method to show that the graphs for the two are equal after canonicalization.