Code Sequence Matching in Graal

[Halimi, Jean-Philippe]

Dear all,



I'd like to share my diagnosis with respect to what needs to be done to add new BMI instructions in Graal. Typically, BMI instructions replace specific code sequences for performance purposes.



Currently implemented BMI instructions are invoke intrinsics: they will replace method invokes by the appropriate x86 instruction. They are matched during a method's graph building process. For instance, the following code will match LZCNT:



if (arch.getFeatures().contains(AMD64.CPUFeature.LZCNT) && arch.getFlags().contains(AMD64.Flag.UseCountLeadingZerosInstruction)) {

            r.register1("numberOfLeadingZeros", type, new InvocationPlugin() {

                @Override

                public boolean apply(GraphBuilderContext b, ResolvedJavaMethod targetMethod, Receiver receiver, ValueNode value) {

                    ValueNode folded = AMD64CountLeadingZerosNode.tryFold(value);

                    if (folded != null) {

                       b.addPush(JavaKind.Int, folded);

                    } else {

                        b.addPush(JavaKind.Int, new AMD64CountLeadingZerosNode(value));

                    }

                    return true;

                }

            });

        }



The "numberOfLeadingZeros" method will then be replaced by LZCNT instruction (embedded in AMD64CountLeadingZerosNode) if possible.



Now, for the rest of the instructions we want to support (ANDN, BLSI, BLSMSK and BLSR), there are no invokes that correspond to the instructions. Therefore, we want to do a graph parsing to detect specific patterns that match the instructions we want to support. For instance, for ANDN, we may want to match the following pattern:



Mov r0, 0x0

Load r1, val

Sub r0, r0, r1

And r2, r1, r0



Additionally, I have not found a graph traversal infrastructure that would allow us to do pattern matching. Do we agree that we need such capability in Graal in order to move forward with this? We could, for instance, add a new compiler pass that would match specific patterns.



I'd like to hear your thoughts first as this is my first significant contribution to the project. :-)



Thanks,



Jp