[LLVMdev] Efficient Pattern matching in Instruction Combine

[Sean Silva]

On Fri, Aug 15, 2014 at 11:41 AM, suyog sarda <sardask01 at gmail.com> wrote:

>
>
>
> On Thu, Aug 14, 2014 at 4:09 AM, Daniel Berlin <dberlin at dberlin.org>
> wrote:
>
>> Even if you can't implement such an algorithm sanely, ISTM that
>> auto-generating this code from a table (or whatever), and choosing
>> canonical results (to avoid a fixpoint issue), rather than what seems
>> to be hand-additions of every possible set of minimizations on three
>> variables, is still a better solution, no?
>>
>> At least then you wouldn't have human errors, and a growing file that
>> makes any of the non-trivial transforms easy to miss in the noise.
>>
>>
> That's what exactly i thought, basically to have auto generating minimized
> expression,
> instead of hand writing code for every pattern.
>
> Few links i found -
>
> http://sontrak.com/
>
> http://sourceforge.net/projects/truthtablesolve/
>
> This might take much more time to implement, my immediate goal is to
> improve matching capabilities.
>
>
Daniel's suggestion could actually could be done pretty easily. (assume for
now that we are most interested in boolean expressions over 3 variables).
There are two parts:

1. Add some code that evaluates a given 3-arg boolean expression at each of
the 2^3 == 8 values, creating an 8-bit index.

2. Create a table of 2^8 == 256 entries (not *too* much work to do by hand)
which has the "preferred" representation for each boolean function of 3
variables.

Then, you just use the 8-bit index to look in the table for the "preferred"
form of the expression. This approach could get a lot of "bang for your
buck" without much code complexity or implementation difficulty.

The same could be done for 2-variable expressions easily (might be a good
starting point). For 4-variable expressions, it might be more difficult
since the table would need 2^(2^4) == 16k entries.

-- Sean Silva


> Regards,
> Suyog
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140815/84338d0f/attachment.html>