News for hackers. Stuff that matters.
Re:Slim Binaries (1997) by EdwardCoffin on Wednesday July 31, 2019 @12:35PM (#20575823)
This reminds me of a technique used by another language I read about in the early nineties, used by a language called (I think) 'C@T' (don't bother Googling that: I found nothing relevant, and the results seem to be mostly NSFW).

The technique was instruction interleaving. They supported several very different architectures from one platform-independent binary. I think they were x86, 68k, MIPS and SPARC. Each executable started with a boilerplate header: a bit of black magic which worked on all of the platforms (more on that below). When execution emerged at the end of the header, the instruction pointer was pointed at the entry point appropriate for the architecture it was executing on. Each entry point (one for each architecture) made sure that the instruction pointer would always jump over parts with the other architectures, to the next applicable instruction in the correct architecture.

The boilerplate header worked something like this: the first few bytes, when interpreted on one particular architecture, would jump to the address immediately following the header, which was the starting point for that architecture's thread-of-control. All other architectures interpreted that instruction as something that was effectively a no-op for the purpose of flow control (like maybe added two registers into another register). Consequently, the next instruction would only be seen by one of the remaining architectures, and a similar process would peel off the remaining architectures, one-by-one, directing each to the appropriate real entry point for that architecture. As I recall they did not do something simple like have monolithic blocks of code separated by architecture: if there was a loop, the body of the loop had interleaved instructions for all architectures. I'm sure this was in the days before instruction caches were a thing.

I think they were able to get some space savings with this, at least by sharing constant data segments (maybe). At the time I read it I did not appreciate some of what they did, and now I could but I can't find the article I read nor any papers about it. I probably read it in Computer Language or Dr. Dobbs or something like that, probably in the early nineties. If anyone else remembers this and can point me to a source, I'd love to revisit it. I think it might have been a project out of AT&T labs.

Re:Slim Binaries (1997) by EdwardCoffin on Thursday August 01, 2019 @09:17AM (#20583430)
I had the name wrong. The language is C+@ [1]. I dug up an article about it in Dr. Dobbs Journal, the October 1993 issue. This does not seem to be the article I am remembering, since it does not go into the instruction interleaving technique anywhere near as much as I remember, but they do mention it and say it was called "beading":

The binaries produced by the C+@ compiler are independent of the underlying machine architecture. Without recompiling, applications can be moved from SPARC to 68000 to Intel x86, and so on. C+@ is not interpretive--the binaries are encoded using a sophisticated 'beading' technique developed at Bell Labs. Because of the streamlined language design, the C+@ compiler produces these portable binaries with extraordinary speed, without the need for preprocessing or front ends.

This is from the article's introduction:

The C+@ programming language, an object-oriented language derived from AT&T Bell Lab's Calico programming language, was developed to provide programmers with a true object-based language and development environment. C+@ (pronounced "cat") has the syntax of C and the power of Smalltalk. Unlike C++, C+@ includes a mature class library with more than 350 classes used throughout the system. The C+@ compiler itself is written in C+@, and all of the source for the class libraries is included with development systems. The Calico project was started at AT&T Bell Labs in the early '80s, after the introduction of Smalltalk and at the same time as C++. Calico was originally used for rapid prototyping of telecommunication services; hence, its heavy emphasis on keeping the language syntax simple and showcasing the power of the graphical development environment.

[1] https://encyclopedia2.thefreedictionary.com/C%2b%40

Re:Slim Binaries (1997) by jandrese on Wednesday July 31, 2019 @04:14PM (#20577996)
> As I recall they did not do something simple like have monolithic blocks of code separated by architecture: if there was a loop, the body of the loop had interleaved instructions for all architectures. I'm sure this was in the days before instruction caches were a thing.

The first part of your post sounded pretty clever and workable, but this part sounds completely insane. Managing all of the side effects for all of those other architectures constantly would have been an never ending nightmare. Keeping separate blocks and only sharing data segments seems like the only way to keep your sanity.

Re:Slim Binaries (1997) by kazinator on Wednesday July 31, 2019 @05:12PM (#20578597)
Well, there are never going to be side effects for the other architectures, because those parts simply can't be touched. Code for the i386 only jumps to other i386 code. Anything that is not i386 code might as well be donkey droppings. If we think about how sequences of NOP instructions are routinely added to machine code for cache-aligning the start of a block, or how non-code data such a string literals is weaved into the middle of code, it doesn't seem far-fetched at all.
Re:Slim Binaries (1997) by jandrese on Wednesday July 31, 2019 @08:20PM (#20580071)
That makes even less sense. Was the code flow like:

  x86_instruction
  jump +6
  mips instruction
  jump +6
  sparc instruction
  jump +6
  68k instruction
  jump +6
Not separating the code out by blocks seems unworkable to me.
Re:Slim Binaries (1997) by kazinator on Wednesday July 31, 2019 @08:50PM (#20580241)
Sounds like it was like:

     block
     of
     x86
     code
     je L43
     more
     x86
     code
     jmp L57

   L33:
     sparc
     code
     never
     mind

   L43:
     x86
     code
 
   L37:
     sparc
     never
     mind

   L57:
     x86
     code
     again

That kind of thing: blocks of code mashed together, but everything is correctly generated to jumps to its own kind.

In regular compiler-generated machine code, we already have "foreign" blocks of stuff in the middle of the instructions, such as string (and other) literals, and computed branch tables. The generated code doesn't accidentally jump into these things. This is kind of the same: all the other architecture stuff is just a literal (that is not referenced). From the x86 POV, the stuff at L33 and L37 above is just data.

Re:Slim Binaries (1997) by EdwardCoffin on Wednesday July 31, 2019 @09:02PM (#20580301)
No, that's not the way I remember they did it. I think you'd have a run of instructions for one architecture, and the only thing that interrupted a run of them would be a branch or a jump. So for example, if you had something like:

    for (i=0; i<10; i++) {
      // body of loop
    }
Then you'd have all of the x86 instructions for the loop in contiguous bytes, after that block you'd have the MIPS instructions, then the SPARC instructions and so on.

I could be wrong about this, which is why I am now really adamant that I find the article I remember, so I can figure out what they really did. But I think there are three levels of granularity they could have done:

1. They could have had what was essentially a monolithic code block for each architecture, concatenated those blocks and had the little bit of magic at the beginning of the executable figure out which block to dispatch to, then execution would stay in that block. I don't think they did this. 2. At the other extreme, they could interleave individual instructions, like you just described. I don't think they did this either. 3. They could have runs of architecture specific instructions corresponding to basic blocks [1], which is what I tried to describe above. I think that's what they did, but I could easily be misremembering.

[1] https://en.wikipedia.org/wiki/Basic_block

Re:Slim Binaries (1997) by EdwardCoffin on Wednesday July 31, 2019 @06:56PM (#20579463)
As I recall, there were no jumps or branches that there would not have been anyway in a single-architecture binary. Every time there was a jump or branch, it simply had to go further, since it would be skipping over unreachable binary code for the other architectures. The real complexity was all resolved up front, in that blob of magic at the entry point.
Re:Slim Binaries (1997) by kazinator on Wednesday July 31, 2019 @05:12PM (#20578596)
> I'm sure this was in the days before instruction caches were a thing.

This would have to be before paged virtual memory was a thing, too.