<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Aug 14, 2014 at 3:53 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote"><div class="">On Wed, Aug 13, 2014 at 9:37 AM, suyog sarda <span dir="ltr"><<a href="mailto:sardask01@gmail.com" target="_blank">sardask01@gmail.com</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Thanks Sean for the reference.<div><br></div><div>I will go through it and see if i can implement it for generic boolean expression minimization.</div>

</div></blockquote><div><br></div></div><div>Hi Suyog,</div><div><br></div><div>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.</div>

<div><br></div><div>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.</div>

<div><br></div><div><br></div><div>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.</div>
<span class="HOEnZb"><font color="#888888">
<div><br></div></font></span></div></div></div></blockquote><div><br></div><div>Even i realize now that it might take some time. Actually, i am trying to get accustomed to whole LLVM </div><div>infrastructure by visiting every module, and submitting some patches wherever i can find good opportunity </div>
<div>to improve the code. </div><div><br></div><div>While visiting instcombine pass and submitting patches for few boolean patterns, i somehow found it </div><div>inconvenient to manually code for each and every permutation of the pattern. Hence, my original </div>
<div>discussion was how can we improve matchers to reduce the code size (might improve compile time as well).</div><div>'Reassociate' pass should do this, but as demonstrated earlier, it might complicate things restricting 'instcombine' </div>
<div>to perform efficiently. </div><div><br></div><div>One way would be to write instcombine patches keeping in mind various optimization opportunities </div><div>created by the reassociation pass. </div><div><br></div><div>
e.x reassociate re-orders '~' to RHS. So ~a&b will be converted to b&~a.</div><div><br></div><div>Hence, whenever we write instcombine code, we should write - match(m_Value(B), m_Not(m_Value(A)))</div><div>
instead of match(m_Not(m_Value(A)), m_Value(B)).</div><div><br></div><div>Second approach might be to improve the matchers itself so that a single call should be sufficient to </div><div>identify a&b and b&a (not sure at this time how can we do this).</div>
<div><br></div><div>Thinking on the similar line, the discussion got extended to general boolean minimization :)<br></div><div><br></div><div>My immediate goal is to improve matching mechanism.</div><div><br></div><div>Regards,</div>
<div>Suyog</div></div>
</div></div>