[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, a variant of (#6429). Specifically, comparing the Xor of two values against the Not of one of them is equivalent to comparing the other value to -1.

 ((x ^ y) == (~x)) -> (y == -1)

 Commutativity permutations:
 ((y ^ x) == (~x)) -> (y == -1)
 ((~x) == (x ^ y)) -> (y == -1)
 ((~x) == (y ^ x)) -> (y == -1)

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

Sample Program

To determine whether this optimisation provided a speed-up, I used the same sample program as in (#8679) but changed the unoptimised and optimised lines to:

condition = ((m ^ s) == ~m) // Unoptimised
condition = (s == -1)       // Optimised

The optimised version is around 35% faster than the unoptimised version, yielding runtimes of approximately 1.29s and 1.98s, 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.IntegerEqualsNode;
import jdk.graal.compiler.nodes.calc.NotNode;
import jdk.graal.compiler.nodes.calc.XorNode;
import org.junit.Test;

public class NewOptimizationTest extends GraalCompilerTest {

    // ((x ^ y) == ~x) |-> (y == -1)
    public static boolean xorNotNeutral1(int x, int y) {
        return ((x ^ y) == ~x);
    }

    public static boolean xorNotNeutral2(int x, int y) {
        return ((y ^ x) == ~x);
    }

    public static boolean xorNotNeutral3(int x, int y) {
        return (~x == (x ^ y));
    }

    public static boolean xorNotNeutral4(int x, int y) {
        return (~x == (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("Xor: " + graph.getNodes().filter(XorNode.class).count());
        System.out.println("Not: " + graph.getNodes().filter(NotNode.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("Xor: " + graph.getNodes().filter(XorNode.class).count());
        System.out.println("Not: " + graph.getNodes().filter(NotNode.class).count());

        // If there are no XorNodes or NotNodes in the graph, the optimisation was applied
        assertTrue(graph.getNodes().filter(XorNode.class).count() == 0);
        assertTrue(graph.getNodes().filter(NotNode.class).count() == 0);
    }

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

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

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

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

Running this test produces the following output:

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

Time: 0.673
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
...