StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>1) Have you considered using <a href="http://en.wikipedia.org/wiki/Superoptimization" rel="nofollow noreferrer">Superoptimization</a> to choose instruction sequences for you? </p> <p>As an example, the GNU superoptimizer manufactures extremely short instruction sequences that will compute the equivalent of a function you provide to it. In your case, you'd provide a function implementing the boolean equation of interest.</p> <p>These tools often operate by enumerating the space of possible computations starting with the smallest, and deciding if an individual computation matches your computation goal. They can't necessarily provide solutions (let alone optimal ones) for very complex instructions, but if a modest number of instructions will succeed they often find a (unusual!) and very efficient sequence. XOR/NOR/ANDC would easily be in scope of the GNU superoptimizer. </p> <p>2) You might try using an algebraic simplifier provided with the right set of algebraic equivalences. We've used our <a href="http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html" rel="nofollow noreferrer">DMS Software Reengineering Toolkit</a>, a program transformation engine that accepts arbitrary rewrite rules and understands commutative and associative laws, to implement boolean simplifiers that involve various operators such as XOR and NOR. You need the rule applier, and a hill-climbing algorithm (climbing the hill with the least number of operators) and a backtracking algorithm. With a depth-first iterative deepening search you can find an optimal solution if the expression isn't too complex; with a branch and bound search search, you can find a solution quickly and then attempt to minimize its size. You even have a relatively good hueristic measure: operands so far not included in the computation. The biggest problem with an equational simplifier is that it won't take into account the register constraints or opportunities available with your specific instruction set.</p> <p>3) You can implement your own search (iterative deepening, branch and bound) over the sets of boolean instructions available to you, and include the constraints. (This is getting somewhat back to what the superoperoptimizers do). I've done this to compute minimal sequences of instructions to implement multiply-by-constant on x86, accounting for up to 3 registers and taking advantage of 3-operand instructions such as (load effective address) LEA X,[Y+K*Z] on registers X, Y, Z with constant K=1,2,4,8, ADD X,Y, SUB X,Y, MOV and NEG instructions. If you code this as a recursive program in any reasonable language, you can code one in a few hundred lines. (It produces some truly squirrely sequences).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload