Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Explaining my fast 6502 code generator

pubby.games

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Explaining my fast 6502 code generator

#41

Post by pubby »

coldacid wrote: post #31
pubby wrote: post #21

Earlier quoted context omitted.

Since it combines register allocation with instruction spilling is innate - there isn't a special spilling phase. Spilled variables are assigned ram addresses after code generation occurs at link time, with the most frequently used going to zeropage.

Does it avoid ZP addresses with special purpose for the system when doing this?

Yeah it can reserve specific ZP addresses. I do this to implement the runtime. It can also be used to reserve hardware registers, but since my only target is the NES, I don't have to worry about that.

Re: Explaining my fast 6502 code generator

#42

Post by quag »

nstbayless wrote: post #34

I may have misunderstood, but I believe step 1 (eliding loads) is simply a cache scheduling problem. The optimal solution is the greedy "furthest in the future" eviction policy.

Is [1] a good way to learn about furthest in the future eviction?

[1]: https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-fart...

Re: Explaining my fast 6502 code generator

#43

Post by ajross »

tom_ wrote: post #32
ajross wrote: post #17

Earlier quoted context omitted.

> 6502 assembly remains a really good intro to assembly It... really is not, though. It doesn't teach you macro assemblers as they exist in the modern world. It doesn't teach you interaction with the linker except in the simplest ways. And while the instruction set is "simple" in the sense that it can be understood on a page of paper, lots of critically important ideas don't exist in a meaningful way. Modern techniqu…

I was almost with you, because much as I love the 6502, it is kind of weird by modern "standards". But then: the Apple II? Like, wtf man. C'mon. The Apple II is shit . Is it just because you like that sweet double density disk throughput? Well, fair enough, but then why not go for the BBC Micro. 2 MHz, plus 80 columns. OK, so it only has 32 KB RAM... meanwhile, you are still American. In summary, please tell us how m…

> Well, fair enough, but then why not go for the BBC Micro

Because the Apple shipped four years earlier? The question isn't what machine is better. Obviously later hardware builds on the advances of its ancestors. The idea behind valuing history is understanding where the changes happened.

Acorn (and Commodore) shipped an excellent machine given the constraints of the time. Both devices were worth purchasing.

Apple shipped an absolutely groundbreaking work of genius that no one had forseen and that no one would duplicate for years. AAA games were shipping in 1988 (c.f. Ultima V and Prince of Persia) designed directly to a framebuffer design architected in the spring of 1977.

If you can't see the difference there and perceive which device is more important to understand and study, I don't know what to say.

Re: Explaining my fast 6502 code generator

#44

Post by matt_d »

pubby wrote: post #12
billyjobob wrote: post #10

All the other compilers in the comparison are C compilers, right? Whereas this compiler is compiling its own home made language? So not sure how the comparison can be valid.

FWIW the custom language is very close to C, and the examples are pretty much a 1-1 transposition. I agree with you though on a different note. It's dubious to compare compilers by benchmarking them, because tests are highly arbitrary and are won/lost based on single weak links. It's not really an exact science, but rather something you can start with to figure out how things are behaving. I mostly base my opinions b…

It could be fun to compare with Action!--it's been known to compile a reasonably good 6502 assembly (considerably better than other compiled languages for that platform), https://en.wikipedia.org/wiki/Action!_(programming_language),

It has been released as open-source together with the binaries, https://atariwiki.org/wiki/Wiki.jsp?page=Action

You should be able to run these using an Atari 8-bit (XL/XE model) emulator, like Atari800, https://github.com/atari800/atari800/releases or Altirra, https://www.virtualdub.org/altirra.html

Re: Explaining my fast 6502 code generator

#45

Post by nstbayless »

quag wrote: post #42
nstbayless wrote: post #34

I may have misunderstood, but I believe step 1 (eliding loads) is simply a cache scheduling problem. The optimal solution is the greedy "furthest in the future" eviction policy.

Is [1] a good way to learn about furthest in the future eviction? [1]: https://blog.henrypoon.com/blog/2014/02/02/proof-of-the-fart...

I found that article quite confusing. I think these slides are clearer: https://courses.cs.washington.edu/courses/cse421/18au/lectur...

(provided you know about induction already.)

Re: Explaining my fast 6502 code generator

#46

Post by peterfirefly »

pubby wrote: post #6
thechao wrote: post #4

This is a Massalin superoptimizer.

From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a sym…

I think you'll be (very!) interested in e-graphs:

https://en.wikipedia.org/wiki/E-graph

Google fodder:

"Equality Saturation: A New Approach to Optimization"

"Denali: A Goal-directed Superoptimizer"

"Z3: An Efficient SMT Solver"

"Efficient E-matching for SMT Solvers"

"egg: Fast and Extensible Equality Saturation"

"Rewrite Rule Inference Using Equality Saturation"

Re: Explaining my fast 6502 code generator

#47

Post by ant6n »

pubby wrote: post #6
thechao wrote: post #4

This is a Massalin superoptimizer.

From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a sym…

It also only uses one possible ordering for the IR instructions?

Still a nice result. It looks like a dynamic programming solution to code generation.

Next to the game boy. ;-)

Re: Explaining my fast 6502 code generator

#48

Post by heisenbit »

ajross wrote: post #17
troad wrote: post #14

Earlier quoted context omitted.

I don't think of retro-computing as an activity limited solely to the hardware and software that existed at a given time, that's far too restrictive for me. 6502 is an architecture, not a specific machine, nor even the set of machines that supported that architecture in the past. The architecture is and remains interesting on its own! (6502 assembly remains a really good intro to assembly, for instance, even for peop…

> 6502 assembly remains a really good intro to assembly It... really is not, though. It doesn't teach you macro assemblers as they exist in the modern world. It doesn't teach you interaction with the linker except in the simplest ways. And while the instruction set is "simple" in the sense that it can be understood on a page of paper, lots of critically important ideas don't exist in a meaningful way. Modern techniqu…

Yes! I learned 6502 assembly from the Apple ][ system manual. You got the op code tables, the schematics and Woz‘s monitor incl. listing and a disassembler. It motivated me to learn English, forced me to carefully calculate relative jumps and taught me to think first then code. Two of the three still useful skills.

Re: Explaining my fast 6502 code generator

#49

Post by ant6n »

ant6n wrote: post #47
pubby wrote: post #6

Earlier quoted context omitted.

From a quick skim of Massalin's paper, they seem similar in how they generate combinations of instructions and prune, but different in other areas. Superoptimizer spews out every combination of instruction (even invalid ones) in a search for true optimality, and uses boolean logic + emulation to determine equivalent code sequences to prune. 6502 algorithm only generates combinations it knows will work, and uses a sym…

It also only uses one possible ordering for the IR instructions? Still a nice result. It looks like a dynamic programming solution to code generation. Next to the game boy. ;-)

It’s probably possible to incorporate all possible orderings of instructions, if the set of already computed instructions is part of the state of the dynamic programming algorithm.

Re: Explaining my fast 6502 code generator

#50

Post by exDM69 »

billyjobob wrote: post #10

All the other compilers in the comparison are C compilers, right? Whereas this compiler is compiling its own home made language? So not sure how the comparison can be valid.

No, not really. LLVM is not a C compiler, it consumes an intermediate representation. Clang is the C compiler which produces LLVM IR.

Likewise, GCC contains a C compiler but the machine specific parts like the codegen take an intermediate representation (GCC has several) as input.

Almost no compilers out there compile directly from C to machine code, there is one or more intermediate forms in between. C is not a good input language for an optimizing compiler.

It's a good and entirely valid comparison. It's the backend codegen that is being compared, the language frontend does not really play a part in it.

Post reply on HN