[LLVMdev] Efficient Pattern matching in Instruction Combine

[suyog sarda]

On Thu, Aug 14, 2014 at 3:53 AM, Sean Silva <chisophugis at gmail.com> wrote:

>
> On Wed, Aug 13, 2014 at 9:37 AM, suyog sarda <sardask01 at gmail.com> wrote:
>
>> Thanks Sean for the reference.
>>
>> I will go through it and see if i can implement it for generic boolean
>> expression minimization.
>>
>
> Hi Suyog,
>
> One thing to keep in mind though is what you are trying to get out of all
> this work, as my suggestion might be a lot of work and there could be
> simpler solutions that meet your immediate needs.
>
> What do you see as the end-result for instcombine's capability with
> boolean expression simplification? Is there a particular goal that you are
> working towards? The same also some of the other folks (coworkers of
> yours?) that have been contributing similar instcombines lately.
>
>
> Also remember that basically anything that can be called a boolean
> minimization algorithm is going to have a worst-case exponential run time
> in the number of variables. An easy way to see this is that if your
> algorithm can decide "this expression simplifies to just False", then you
> can use it to solve SAT: if the expression simplifies to just False, then
> it is unsatisfiable, otherwise it is satisfiable.
>
>
Even i realize now that it might take some time. Actually, i am trying to
get accustomed to whole LLVM
infrastructure by visiting every module, and submitting some patches
wherever i can find good opportunity
to improve the code.

While visiting instcombine pass and submitting patches for few boolean
patterns, i somehow found it
inconvenient to manually code for each and every permutation of the
pattern. Hence, my original
discussion was how can we improve matchers to reduce the code size (might
improve compile time as well).
'Reassociate' pass should do this, but as demonstrated earlier, it might
complicate things restricting 'instcombine'
to perform efficiently.

One way would be to write instcombine patches keeping in mind various
optimization opportunities
created by the reassociation pass.

e.x reassociate re-orders '~' to RHS. So ~a&b will be converted to b&~a.

Hence, whenever we write instcombine code, we should write -
match(m_Value(B), m_Not(m_Value(A)))
instead of match(m_Not(m_Value(A)), m_Value(B)).

Second approach might be to improve the matchers itself so that a single
call should be sufficient to
identify a&b and b&a (not sure at this time how can we do this).

Thinking on the similar line, the discussion got extended to general
boolean minimization :)

My immediate goal is to improve matching mechanism.

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