3 ms·

I love this series! Does anybody know, if anyone ever made a version that outputs AMD64 assembly instead of 68000? Or some kind of gentle introduction to a re

I love this series! Does anybody know, if anyone ever made a version that outputs AMD64 assembly instead of 68000? Or some kind of gentle introduction to a reduced version of the AMD64 instruction set, so that I could do it myself? The instruction set is quite huge, so having a number of primitive commands that get the job done would be nice.

barrkel 7y ago
You can go along way with not much more than a couple dozen instructions (mnemonics, though when encoded with addressing modes it'll be more opcodes, but Jack's compiler delegates that work to the assembler). MOV, MOVZX, JMP, CALL, RET, CMP, TEST, Jcc, ADD, SUB, MUL, DIV, AND, OR, NOT, XOR, INC, DEC would about cover it for basic control flow and integer operations. Adding floating point arithmetic needs another dozen or so instructions. The x87 opcodes (FLD, FST, FADD etc.) are very easy to program against, since it's a stack machine - a post-order traversal of an expression tree is usually sufficient if the stack won't overflow, though SSE2 instructions are more usual for x64. Large portions of the full instruction set are vector operations which you wouldn't realistically be emitting for a didactic toy compiler. You can get by perfectly well without the string operations too.
- fizixer 7y ago
  I agree with you. However, a quick personal anecdote: I tried to create "assembler", in python, for just one instruction, MOV. And not even 64, or 32-bit, (it was either 16-bit or 8-bit). After scratching my head with all the corner cases, and handling about 80% of them, my python code looked like a complete mess. There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. [0] https://www.google.com/search?q=MOV+is+turing+complete https://www.google.com/search?q=MOV+is+turing+complete
  - nikeee 7y ago
    One simple way to show that MOV is turing complete is how this project does it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator This compiler compiles C to MOV instructions only.
  - blattimwind 7y ago
    MOV+ is a mnemonic for at least something like two or three dozen different opcodes though.
  - vidarh 7y ago
    But a compiler does not need to be able to generate every version in a generic way. You only need to generate the variations you're specifically intending to use.
  - wolfgke 7y ago
    > There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only access to a finite amount of memory while a Turing machine needs an infinite tape to work. So the proof must be false. In other words: only a mathematically idealized version of MOV might be Turing complete - but this cannot be the MOV that x86 implements.
    - chrisseaton 7y ago
      Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.
      - wolfgke 7y ago
        The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
        chrisseaton 7y ago
        If your program finishes without reaching the limit of tape then it doesn’t matter that the tape was limited. It’s not about classes of machines. A machine with a limited tape is a perfect approximation for the proper class of a machine with an unlimited tape if the limit is not reached for all programs you care about. Professors won’t be horrified - they also use the silent parenthetical constraint. Look for example at formal publications like Dolan’s and see how academics talk about it.
    - msla 7y ago
      If you want to be pedantic, let's get pedantic. Turing-completeness isn't a property of computational models, it's a property of problems. A problem is Turing-complete when it cannot be solved by any computational model less powerful than a Turing Machine, or other Turing-equivalent computational system, such as the Lambda Calculus. Moreover, a Turing machine does not have an infinite tape. It has an unbounded tape. Its tape is not limitless, it is extensible, such that a computation cannot fail due to running out of tape. Hey, you wanted to get pedantic. Finally, in practical land, the distinction between Turing-equivalent and non-Turing-equivalent is very relevant to real programming languages: Epigram is pointedly not Turing-equivalent, and therefore it's possible to prove programs in that language will halt. Moving away from Turing-equivalence frees you from the tyranny of the Halting Problem. https://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co https://scienceblogs.com/goodmath/2007/01/05/turing-equivale... https://en.wikipedia.org/wiki/Epigram_(programming_language) https://en.wikipedia.org/wiki/Epigram_(programming_language)
  - userbinator 7y ago
    I'm not sure what you mean by "corner cases" with MOV, unless you mean things like segment registers (which are rarely if ever going to be emitted by a compiler.) There's reg<imm, m/r<imm, and m/r<>reg. That last one makes up the majority of MOV instructions a compiler will emit. Also, the opcodes (and especially the ModRM) make far more sense when written in Octal - see http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt
  - cpeterso 7y ago
    Like the one instruction set computer (OISC) architecture? https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
nils-m-holm 7y ago
If 386 is sufficient: https://t3x.org/reload/index.html https://t3x.org/reload/index.html The later versions of the compiler even have an x86-64 backend. Or, if you want to skip assembly language entirely and compile directly to 386/ELF: https://t3x.org/t3x/book.html https://t3x.org/t3x/book.html
tyingq 7y ago
"a version that outputs AMD64 assembly" It's not based on the linked guide, but there's 8cc. Outputs x86-64 only. Diary of it being made: https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile... Github sources and history: https://github.com/rui314/8cc https://github.com/rui314/8cc The "gen.c" source file might be helpful for some of your questions about x86-64: https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff314820daf560cb987377/gen.c https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff31482...
userbinator 7y ago
There's an x86 version here: http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html 64-bit is almost entirely a superset of 32-bit, so that will at least get you started.

barrkel 7y ago

You can go along way with not much more than a couple dozen instructions (mnemonics, though when encoded with addressing modes it'll be more opcodes, but Jack's compiler delegates that work to the assembler). MOV, MOVZX, JMP, CALL, RET, CMP, TEST, Jcc, ADD, SUB, MUL, DIV, AND, OR, NOT, XOR, INC, DEC would about cover it for basic control flow and integer operations. Adding floating point arithmetic needs another dozen or so instructions. The x87 opcodes (FLD, FST, FADD etc.) are very easy to program against, since it's a stack machine - a post-order traversal of an expression tree is usually sufficient if the stack won't overflow, though SSE2 instructions are more usual for x64. Large portions of the full instruction set are vector operations which you wouldn't realistically be emitting for a didactic toy compiler. You can get by perfectly well without the string operations too.

fizixer 7y ago
I agree with you. However, a quick personal anecdote: I tried to create "assembler", in python, for just one instruction, MOV. And not even 64, or 32-bit, (it was either 16-bit or 8-bit). After scratching my head with all the corner cases, and handling about 80% of them, my python code looked like a complete mess. There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. [0] https://www.google.com/search?q=MOV+is+turing+complete https://www.google.com/search?q=MOV+is+turing+complete
- nikeee 7y ago
  One simple way to show that MOV is turing complete is how this project does it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator This compiler compiles C to MOV instructions only.
- blattimwind 7y ago
  MOV+ is a mnemonic for at least something like two or three dozen different opcodes though.
- vidarh 7y ago
  But a compiler does not need to be able to generate every version in a generic way. You only need to generate the variations you're specifically intending to use.
- wolfgke 7y ago
  > There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only access to a finite amount of memory while a Turing machine needs an infinite tape to work. So the proof must be false. In other words: only a mathematically idealized version of MOV might be Turing complete - but this cannot be the MOV that x86 implements.
  - chrisseaton 7y ago
    Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.
    - wolfgke 7y ago
      The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
      - chrisseaton 7y ago
        If your program finishes without reaching the limit of tape then it doesn’t matter that the tape was limited. It’s not about classes of machines. A machine with a limited tape is a perfect approximation for the proper class of a machine with an unlimited tape if the limit is not reached for all programs you care about. Professors won’t be horrified - they also use the silent parenthetical constraint. Look for example at formal publications like Dolan’s and see how academics talk about it.
  - msla 7y ago
    If you want to be pedantic, let's get pedantic. Turing-completeness isn't a property of computational models, it's a property of problems. A problem is Turing-complete when it cannot be solved by any computational model less powerful than a Turing Machine, or other Turing-equivalent computational system, such as the Lambda Calculus. Moreover, a Turing machine does not have an infinite tape. It has an unbounded tape. Its tape is not limitless, it is extensible, such that a computation cannot fail due to running out of tape. Hey, you wanted to get pedantic. Finally, in practical land, the distinction between Turing-equivalent and non-Turing-equivalent is very relevant to real programming languages: Epigram is pointedly not Turing-equivalent, and therefore it's possible to prove programs in that language will halt. Moving away from Turing-equivalence frees you from the tyranny of the Halting Problem. https://scienceblogs.com/goodmath/2007/01/05/turing-equivalent-vs-turing-co https://scienceblogs.com/goodmath/2007/01/05/turing-equivale... https://en.wikipedia.org/wiki/Epigram_(programming_language) https://en.wikipedia.org/wiki/Epigram_(programming_language)
- userbinator 7y ago
  I'm not sure what you mean by "corner cases" with MOV, unless you mean things like segment registers (which are rarely if ever going to be emitted by a compiler.) There's reg<imm, m/r<imm, and m/r<>reg. That last one makes up the majority of MOV instructions a compiler will emit. Also, the opcodes (and especially the ModRM) make far more sense when written in Octal - see http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt http://www.dabo.de/ccc99/www.camp.ccc.de/radio/help.txt
- cpeterso 7y ago
  Like the one instruction set computer (OISC) architecture? https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer

nils-m-holm 7y ago

If 386 is sufficient: https://t3x.org/reload/index.html https://t3x.org/reload/index.html The later versions of the compiler even have an x86-64 backend. Or, if you want to skip assembly language entirely and compile directly to 386/ELF: https://t3x.org/t3x/book.html https://t3x.org/t3x/book.html

tyingq 7y ago

"a version that outputs AMD64 assembly" It's not based on the linked guide, but there's 8cc. Outputs x86-64 only. Diary of it being made: https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile... Github sources and history: https://github.com/rui314/8cc https://github.com/rui314/8cc The "gen.c" source file might be helpful for some of your questions about x86-64: https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff314820daf560cb987377/gen.c https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff31482...

userbinator 7y ago

There's an x86 version here: http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html 64-bit is almost entirely a superset of 32-bit, so that will at least get you started.