[GR-53019] Potential new optimisation for IntegerEqualsNode

[default-jamc]

Overview

Hi,

I noticed that there may be another optimisation that can be added to IntegerEqualsNode. Specifically, comparing the And and Or of two values is equivalent to comparing the values directly.

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

 Commutativity permutations:
 ((x & y) == (y | x)) -> (x == y)
 ((x | y) == (x & y)) -> (x == y)
 ((x | y) == (y & x)) -> (x == y)

This optimisation has also been formally verified in an interactive theorem prover (Isabelle/HOL).

Sample Program

I've written a sample program to demonstrate the speed-up of this optimisation:

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 * 6 + j;
      m = calc2(s,j);

      //condition = ((m & s) == (m | s)); // Unoptimised
      condition = (m == s);       // 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*10)) + y);
    }

    return x;
  }
}

The optimised version is around 15-20% faster than the unoptimised version, yielding runtimes of approximately 3.7s and 4.5s, respectively.

Unit Test

I've also written a JUnit test to check whether this optimisation is applied:

package jdk.graal.compiler.core.test;

import jdk.graal.compiler.nodes.StructuredGraph;
import jdk.graal.compiler.nodes.calc.AndNode;
import jdk.graal.compiler.nodes.calc.IntegerEqualsNode;
import jdk.graal.compiler.nodes.calc.OrNode;
import org.junit.Test;

public class NewOptimizationTest extends GraalCompilerTest {

    // ((x & y) == (x | y)) |-> (x == y)
    public static boolean andOrEquals1(int x, int y) {
        return ((x & y) == (x | y));
    }

    public static boolean andOrEquals2(int x, int y) {
        return ((x & y) == (y | x));
    }

    public static boolean andOrEquals3(int x, int y) {
        return ((x | y) == (x & y));
    }

    public static boolean andOrEquals4(int x, int y) {
        return ((x | y) == (y & x));
    }

    private void checkNodes(String methodName) {
        StructuredGraph graph = parseForCompile(getResolvedJavaMethod(methodName));

        System.out.println("(Before) Nodes in graph: ");
        System.out.println("IntegerEquals: " + graph.getNodes().filter(IntegerEqualsNode.class).count());
        System.out.println("And: " + graph.getNodes().filter(AndNode.class).count());
        System.out.println("Or: " + graph.getNodes().filter(OrNode.class).count());

        createCanonicalizerPhase().apply(graph, getProviders());

        System.out.println("(After) Nodes in graph: ");
        System.out.println("IntegerEquals: " + graph.getNodes().filter(IntegerEqualsNode.class).count());
        System.out.println("And: " + graph.getNodes().filter(AndNode.class).count());
        System.out.println("Or: " + graph.getNodes().filter(OrNode.class).count());

        // If there are no AndNodes or OrNodes in the graph, the optimisation was applied
        assertTrue(graph.getNodes().filter(AndNode.class).count() == 0);
        assertTrue(graph.getNodes().filter(OrNode.class).count() == 0);
    }

    @Test
    public void testOptimization1() {
        checkNodes("andOrEquals1");
    }

    @Test
    public void testOptimization2() {
        checkNodes("andOrEquals2");
    }

    @Test
    public void testOptimization3() {
        checkNodes("andOrEquals3");
    }

    @Test
    public void testOptimization4() {
        checkNodes("andOrEquals4");
    }
}

Running this test produces the following output:

MxJUnitCore
JUnit version 4.12
.(Before) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
(After) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
E
testOptimization1(jdk.graal.compiler.core.test.NewOptimizationTest)
java.lang.AssertionError
	...
.(Before) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
(After) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
E
testOptimization2(jdk.graal.compiler.core.test.NewOptimizationTest)
java.lang.AssertionError
	...
.(Before) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
(After) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
E
testOptimization3(jdk.graal.compiler.core.test.NewOptimizationTest)
java.lang.AssertionError
	...
.(Before) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
(After) Nodes in graph: 
IntegerEquals: 1
And: 1
Or: 1
E
testOptimization4(jdk.graal.compiler.core.test.NewOptimizationTest)
java.lang.AssertionError
	...

Time: 0.79
There were 4 failures:
1) jdk.graal.compiler.core.test.NewOptimizationTest#testOptimization1
java.lang.AssertionError
	...
2) jdk.graal.compiler.core.test.NewOptimizationTest#testOptimization2
java.lang.AssertionError
	...
3) jdk.graal.compiler.core.test.NewOptimizationTest#testOptimization3
java.lang.AssertionError
	...
4) jdk.graal.compiler.core.test.NewOptimizationTest#testOptimization4
java.lang.AssertionError
	...

FAILURES!!!
Tests run: 4,  Failures: 4
...

[davleopo]

@gergo- can you have a look ?