[dragontamer]

All instructions are implemented with logic gates. In fact. All instructions today are likely NAND gates.

Have you ever seen a WallaceTree multiplier? A good sequence that shows how XOR and AND gates can implement multiply.

Now, if multiply + XOR gets the new function you want, it's likely better than whatever the original compiler output.

[agent327]

That was not the claim. The claim was that assembler was made up out of sequences of OR/AND/XOR, and that claim is demonstrably false.

[astrange]

"Made up of" isn't helpful. All assembly languages are equivalent to a sequence of bit operations. (…if you ignore side effects and memory operations.)

In fact there's several different single operations you can build them all out of: https://en.wikipedia.org/wiki/One-instruction_set_computer#I...

So you take your assembly instructions, write a sufficiently good model of assembly instructions<>bit operations, write a cost model (byte size of the assembly works as a cheap one), and then search for assembly instructions that perform the equivalent operation and minimize the cost model.

Like here: https://theory.stanford.edu/~aiken/publications/papers/asplo...

[viraptor]

You're missing forest for the trees and lacking information to discuss this really. Check out this paper and similar ones if you want to learn about this area: https://arxiv.org/pdf/1711.04422

[dragontamer]

What do you think implements assembly language?

Answer: Verilog or VHDL. And these all synthesize down to AND/OR/XOR gates and eventually converted into NAND gates only.

Every assembly language statement is either data movement, or logic, or some combination of the two.

-------

We are talking about SAT solvers and superoptimizers. Are you at all familiar with this domain? Or have you even done a basic search on what the subject matter is?

[saagarjha]

Computers are not programmed on the level of logic gates. If you want to do that, design an FPGA.

[dragontamer]

Superoptimizers take this stuff into consideration.

Which is what the parent post was talking about, the rare superoptimizer.

[LtWorf]

If you want something optimised… "equivalent" isn't going to do it.