Code Sequence Matching in Graal

[Yudi Zheng]

Hi Jean-Philippe,

Please note that the assembler change is in: https://github.com/oracle/graal/commit/0b62c0c86c97286782c2e4c582d07d36f117c00e <https://github.com/oracle/graal/commit/0b62c0c86c97286782c2e4c582d07d36f117c00e>

Best regards,
-Yudi

> On 27 Aug 2018, at 22:10, Gilles Duboscq <gilles.m.duboscq at oracle.com> wrote:
> 
> Hi Jean-Philippe,
> 
> This kind of matching is typically done during the HIR to LIR transition.
> For example see the AMD64NodeMatchRules class e.g.,
> 
> ```
> @MatchRule("(Or (LeftShift=lshift value Constant) (UnsignedRightShift=rshift value Constant))")
> public ComplexMatchResult rotateLeftConstant(LeftShiftNode lshift, UnsignedRightShiftNode rshift) {
>    if ((lshift.getShiftAmountMask() & (lshift.getY().asJavaConstant().asInt() + rshift.getY().asJavaConstant().asInt())) == 0) {
>        return builder -> getArithmeticLIRGenerator().emitRol(operand(lshift.getX()), operand(lshift.getY()));
>    }
>    return null;
> } 
> ```
> 
> This rule is used to detect and emit "rotate" patterns to take advantage of the `rol` x86 instruction.
> You can see the "s-expression" language used to match parts of the graph.
> The code in the rule can then further inspect the HIR nodes to decide to do the special handling or not.
> 
> For ANDN i could imagine something like:
> 
> ```
> @MatchRule("(And a (Not b)")
> @MatchRule("(And (Not b) a")
> public ComplexMatchResult andNot(ValueNode a, ValueNode b) {
>    return builder -> getArithmeticLIRGenerator().emitAndNot(operand(a), operand(b));
> }
> ```
> 
> Note that i used 2 rules to capture the commutative case.
> (`emitAndNot` does not exist, you would have to implement it)
> 
> Note that Yudi currently has a PR that adds some of the code needed to emit those BMI instructions in the assembler (just the assembler part though, nothing for matching or generating the LIR).
> 
> I hope this helps.
> Gilles
> 
> On 27/08/18 18:18, Halimi, Jean-Philippe wrote:
>> 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
>> 
>>