login join help ad

May 17, 2020

Memoir 1 - Recursive functions in C and the only time I was brilliant

Some time around 1988 I wanted to port UNIX to ES-1011, a hungarian clone of Mitra-225. It was a 16-bit+ mini with an accumulator-based instruction set, and unlike its contemporary PDP-11, it had no hardware-supported stack.

Our ES-1011 ran OS MISS, written by late Vladimir Butenko, including a C compiler by Mark Venguerov. Mark found it somewhat annoying implementing a stack. His prologue routine had 22 instructions and epilogue had something like 9. The K&R C also had a non-trivial prologue function, called '.jsav' IIRC. But it wasn't as bad as having a word in memory work as a stack pointer on Mitra-225/ES-1011.

Because entering functions properly was so expensive, Mark made a decision not to make all functions recursive by default. Instead, those that needed to be recursive were marked with a reserved word "recursive". It was expected that not many needed it. The problem was how to find those that did and mark them. I didn't do that, but I think someone developed a program that searched for potential call loops (perhaps Ivan Bobrov or Sasha Ovsyankin did). Even so it was rather iffy to identify and tag recursion.

Before I started porting, I consulted with Vadim Antonov, who was basically King of Unix in USSR. His suggestion was to start with developing the ABI and calling convention. I don't remember if he pointed it out, or if I decided it myself, but Mark's explicit recursion was a non-starter. I began looking into the problem and had an idea.

Mitra-225 had an additional register, L, which was possible to read in userspace. I think it pointed at the word where the return address was saved. The instruction set featured a few rarely used addressing modes with L as an index register. Also, a procedure return instruction set L as a side effect, as I recall. Either way, I decided to use L as a frame pointer. I coded a somewhat unconventional prologue that recovered the return address and previous value of L, then re-set L so it continued to point into stack, and pushed return address there. It only took something like 9 instructions. The epilog was even smaller and it was basically RET. The code was compact and performant enough to allow all C functions to be recursive, as they should.

When I demonstrated the code to Mark, he looked at me for a long moment and said: "Where have you been before, Pete?"

By that time, he was busy with his 2nd C compiler, for 8086, and he never got back to retool the C for Mitra. And I burned out of porting UNIX for one reason or other. My diploma theses was porting MISS to PDP-11, ironically enough. So, nothing came out of my craftiness.

Next: Memoir 2.

Update: There's a manual for Mitra-15 floating on the Internet, so I used it to refresh my memory somewhat. The L register is loaded from a global "section table" upon a procedure call (CLS: Call Section). This hardware support and traditional use make a reason why nobody came upon the obvious. But the procedure return (RTS) is recursion-friendly: it loads the return address from L+0 and the L from L+2.

Posted by: Pete Zaitcev at 11:33 AM | No Comments | Add Comment
Post contains 547 words, total size 4 kb.

What colour is a green orange?

11kb generated in CPU 0.02, elapsed 0.0331 seconds.
25 queries taking 0.0227 seconds, 30 records returned.
Powered by Minx 1.1.6c-pink.