High-level feature specification and delivery about llvm-mos

[mysterymath]

Largely agree with the items and bucketing present.

Additions to Necessary:

• Compiler runtime library

  • This encompasses integer/floating-point division and multiplication routines, basically anything you can write in pure C that takes more than 2/3 instructions, with the notable exception of memmove, memcpy, memcmp, and memset. This corresponds to libgcc or libcompiler-rt in GCC and clang, respectively. It's somewhat unlikely that we could use either, since both are written in largely "branch-free" style, which is not appropriate for an architecture where large arithmetic operations are vastly more expensive than branches.

• Bare-minimum libc

  • GCC and GCC-compatible C compilers emit calls to memmove, memcpy, memcmp, and memset to handle struct operations, even though those routines are not provided in the compiler support library (libgcc). This is true even if -nolibc or -nostdlib is given to the compiler. (See https://gcc.gnu.org/onlinedocs/gcc/Link-Options.html) To allow compilation of C code out-of-the-box, we'll need to provide a minimal implementation that can be used in lieu of a full libc. Such a library would conflict with a full libc, so it should probably be either-or, unless we make our own libc depend on the little library.

Additions to Important:

• LTO
  • Allowing users to increase or decrease the number of imaginary registers (e.g., depending on which set of OS routines are used, or the size of sprite DMA regions reserved for the NES, etc) would either require recompiling libc for each possible imaginary register configuration, or else compiling the libc to use a bare minimum of imaginary registers. The runtime-performance of the latter will likely be unacceptable, and the compile-time performance and flexibility of the former unacceptable. Instead, if the libc is shipped with the SDK as archives of LLVM bitcode, the lowest level of assembly code generation can be done on the fly during the link, allowing it to respond to user changes in imaginary register profile.
  • This basically works now, but it seems like it might be easy to break, so this is more one of those "keep it in mind" things.

Additions to Nice-To-Have:

• Binary Packing
  • While bin packing is NP-complete, it's one of the "easiest" such problems, since it admits a linear-time constant approximation algorithm. Our problem isn't exactly bin-packing, but it's similar enough to suspect a similar approximation guarantee exists. I played around with the standard heuristics for the problem (e.g., First Fit Decreasing), and they prima facie produced fairly good results.
  • LD scripting already has a mechanism for specifying discontiguous memory, so an extension to the syntax could be designed to allow requesting this.
  • This would be a huge value-add for both ASM and C development. Packing problems in operations research are essentially never solved by hand, since heuristic solvers routinely generate vastly super-human results, and this would likely be the case here as well.

[johnwbyrd]

Agreed on added items and prioritization.

Re binary packing: it MAY be possible that such a tool could be done as a custom linker step. However, a potential user has informed us that "they are used to assigning code to sections themselves."

[mysterymath]

A variant of this feature already exists in GCC: see -enable-non-contiguous-regions https://sourceware.org/binutils/docs/ld/Options.html This definitely isn't as fancy as a proper bin packing, since it doesn't allow sections to be reordered: a single large section could cause a memory region to say deallocated, even if later sections were small enough to fit.

…

On Thu, Mar 18, 2021, 7:35 PM John Byrd ***@***.***> wrote: Agreed on added items and prioritization. Re binary packing: it MAY be possible that such a tool could be done as a custom linker step. However, a potential user has informed us that "they are used to assigning code to sections themselves." — You are receiving this because you were assigned. Reply to this email directly, view it on GitHub <#21 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABD6W4PFFLET4GUWEQMH3HTTEK2AXANCNFSM4ZMESNMQ> .

[mysterymath]

At the very least this feature would probably interact poorly with the other available features of the linker script, and all that would have to be untangled before it approached a good idea. We can keep it off the issue list; that way maybe someone will file it against us if they really care. On Thu, Mar 18, 2021, 7:49 PM Daniel Thornburgh ***@***.***> wrote:

…

A variant of this feature already exists in GCC: see -enable-non-contiguous-regions https://sourceware.org/binutils/docs/ld/Options.html This definitely isn't as fancy as a proper bin packing, since it doesn't allow sections to be reordered: a single large section could cause a memory region to say deallocated, even if later sections were small enough to fit. On Thu, Mar 18, 2021, 7:35 PM John Byrd ***@***.***> wrote: > Agreed on added items and prioritization. > > Re binary packing: it MAY be possible that such a tool could be done as a > custom linker step. However, a potential user has informed us that "they > are used to assigning code to sections themselves." > > — > You are receiving this because you were assigned. > Reply to this email directly, view it on GitHub > <#21 (comment)>, > or unsubscribe > <https://github.com/notifications/unsubscribe-auth/ABD6W4PFFLET4GUWEQMH3HTTEK2AXANCNFSM4ZMESNMQ> > . >

[johnwbyrd]

I would like to reorganize this project into milestones, so that critical path tasks can be front loaded, and less critical things can be blown off until later.

I propose that milestones should be created, and ordered, by number of project participants. And technical features in turn need to be chosen around that goal. Features for each milestone should be chosen on that basis.

The first milestone(s) should involve relatively few people touching the code, either as users or developers -- "stealth mode" if you will.

The next should be "friends and family" milestones, with a small handful of key users and/or developers, proposing fixes or trying to use the compiler and SDK as we intend. I envision six or seven -- no more than ten or so.

Progressive milestones should seek to push llvm-mos out to a wider and wider audience. "Public presentations" could be considered a milestone. "Upstream" could be considered a milestone.

Following this structure for milestones, permits us to make sure we're doing the important stuff first. Unless someone stops me, I'll start ordering tasks in the project according to this methodology.

Assignments of issues to milestones will be tentative, and can be moved around as the project scope changes.

[mysterymath]

Can you clarify how expected number of project participants will inform the issues selected for milestones?
What will the objective criteria be for determining whether or not a milestone has been accomplished?

[johnwbyrd]

The fewer the number of participants, the more radical the changes can be made to the code base.

Early on is a good time for radical rethinks of architectures, rebases, or adding or deleting major new features on which other features depend. This will get harder to do, the more eyeballs are looking at the code, or using the products of it.

However, given enough eyeballs, all bugs are shallow, and it will be useful to have more help once we are shaking out bugs in the "production" compiler.

I'm going to roughly sort the issues that we have into milestones, but sorting will be up for debate and discussion. Once issues are thusly sorted, we can just declare a milestone complete once all its component issues have been addressed. There's your objective criteria. Also, this is why we are trying to reduce abstract issues ("cc65 compatibility") to more concrete ones.

Once any milestone has been completed, is a good time to gather whatever participants to comment on the next, and make adjustments to that milestone based on popular feedback.

It's also reasonable to expect that the later the milestone, the lower the barrier to entry to using llvm-mos. Later milestones will have packaging, good documentation, better test suites, better examples and so forth. Early adopters tend to be tolerant of bugs, can build llvm tools themselves, fix bugs, etc.

[johnwbyrd]

The milestones should also correspond roughly to the prioritized list discussed at the top of this thread. Conveniently, I think there's a correspondence between the ordered list and number of expected participants.

[mysterymath]

I'm not too keen to add too much process here; it's likely that our product development ideologies differ somewhat, and this is a hobby project.

I'm not going to try to stop you from creating such organization if you find it helpful, but at present I'm only working to:

• Decrease known systemic risk for the long-term viability of the project, and then
• Define, design, implement, and release the minimum viable C compiler.

I'm very interested in discussion on what properties our first releasable artifact should have, or if we can identify specific decisions that we're making that may have long-term consequences. But otherwise, I do value the flexibility of selecting whatever tasks are appropriate at the time to further that first-release goal. Once we actually have a compiler, and some folks have used it, we'll have more information than we do now, and be in a better place to make decisions.

[mysterymath]

Closing this; now that we have a healthier issue tracker, we should probably track tasks required for initial release via issues and milestone labels. I've populated a v0.1.0 label (semver); it's not intended to be exhaustive, but feel free to add anything that I've missed.