4 ms·

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 s

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.

saagarjha 1y ago
Computers are not programmed on the level of logic gates. If you want to do that, design an FPGA.
- dragontamer 1y ago
  Superoptimizers take this stuff into consideration. Which is what the parent post was talking about, the rare superoptimizer.
agent327 1y ago
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 1y ago
  "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#Instruction_types 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/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...
- viraptor 1y ago
  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 https://arxiv.org/pdf/1711.04422
- dragontamer 1y ago
  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?
LtWorf 1y ago
If you want something optimised… "equivalent" isn't going to do it.

saagarjha 1y ago

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

dragontamer 1y ago
Superoptimizers take this stuff into consideration. Which is what the parent post was talking about, the rare superoptimizer.

agent327 1y ago

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 1y ago
"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#Instruction_types 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/asplos06.pdf https://theory.stanford.edu/~aiken/publications/papers/asplo...
viraptor 1y ago
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 https://arxiv.org/pdf/1711.04422
dragontamer 1y ago
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?

LtWorf 1y ago

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