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 an 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/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 were needed. 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 had 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 found a less than obvious way to extract the return address and save it at L, by tricking the return instruction so it jumped into the body of the function instead of out of it, and that set L. The epilog was even smaller and I think 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 549 words, total size 3 kb.

What colour is a green orange?

11kb generated in CPU 0.01, elapsed 0.0243 seconds.
25 queries taking 0.0169 seconds, 30 records returned.
Powered by Minx 1.1.6c-pink.