[LLVMdev] Efficient Pattern matching in Instruction Combine

[Duncan P. N. Exon Smith]

> On 2014-Aug-07, at 09:46, suyog sarda <sardask01 at gmail.com> wrote:
> 
> Hi,
> 
> All, Duncan, Rafael, David, Nick.
> 
> This is regarding pattern matching in InstructionCombine pass.
> 
> We use 'match' functions many times, but it doesn't do the pattern matching
> effectively.
> 
> e.x. Lets take pattern :
> 
> (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
> 
> (B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C
> 
> Both the patterns above are same, since ^ is commutative in Op0. 

It'd be interesting if you could find a design that also treated these
the same:

    (B ^ A) | ((A ^ B) ^ C) -> (A ^ B) | C
    (B ^ A) | ((B ^ C) ^ A) -> (A ^ B) | C
    (B ^ A) | ((C ^ A) ^ B) -> (A ^ B) | C

I.e., `^` is also associative.

> 
> But, 'match' pattern has to be written for both the patterns separately
> since 'match' identifies pattern as it (like regular expression) and doesn't 
> have the logic to determine that 'A^B' and 'B^A' are same.
> 
> I propose to improve 'match' functions where we can include the logic
> to determine if an operation is commutative or not. If it is commutative,
> then a single 'match' call should be able to detect both 'A^B' and 'B^A'.
> So, basically we will modify the commutative 'match' functions.
> 
> There will be various permutations of it where one of the operand might be
> a constant (I guess this is handled already as constant are re-associated to
> RHS). 
> 
> I will try to dig more on this.
> 
> Inputs/suggestions/comments on improving match functions are most awaited. :)
> 
> Regards,
> Suyog
> 
> -- 
> With regards,
> Suyog Sarda