Communications - January 2011

tually canceled [in 1969] by Armonk, by headquarters, which we should have known would happen, because it was not 360. But we developed things that subsequently influenced the company a lot. We did a lot with branch prediction, both hardware and software, and caching, and machine-independent, language-independent optimizers. John, after being very disappointed about not being able to build the fastest machine in the world, decided he would build the best cost-performance machine. That was where the PowerPC came from—the 801 project.

After ACS, I took an unhappy digression from my work on compilers. I was assigned to work on FS, the famous “Future System” of IBM. It was so bad on performance, I wrote a letter. FS took two round trips to memory to fetch any item of data, because it had a very high-level intermediate form as the architected form for the machine.

Should I be reminded of the Intel 432, the processor designed for ada? It had a very high-level architecture that turned out to be memory-bound, because it was constantly fetching descriptors from memory.

Yes. We aren’t very good about passing on the lessons we’ve learned, and we don’t write our failures up very well.

It’s harder to get a failure published
than a success.

But there are a lot of lessons in them. After fuming about FS for a few months, I wrote a letter to somebody higher up and said, “This isn’t going to work,” and why, and that was the wrong thing to say. So I was kind of put on the shelf for a while. But then I did a lot of work with a PL/I compiler that IBM had subcontracted to Intermetrics.

the compilers you worked on—such as
the aCS compiler and the PL/I compil-
er in the 1970s—what languages were
those implemented in?

Some of them were implemented in FORTRAN, some in PL/I, and some were in assembly language.

how about alpha?

That was in the assembly language for Stretch.

Your 1976 Communications paper with

any single harvest
instruction could
run for days, and
be self-modifying.

John Cocke contains some actual PL/I code that represents sets as bit vectors, and propagates sets around the program control flow graph. the intersections and unions of the sets were just PL/I & and | operators, which makes the code concise and easy to read. You have said that PL/I was a complicated language to compile, but it seems to have expressive power.

Yes, it was really very useful for writing optimizers and compilers. The data flow work came from early FORTRAN and their use of control flow graphs. On Project Y we built control flow graphs and developed a language about the articulation points on the graph, abstracting away from DO loops into something more general, then optimizing based on a hierarchy of these graphs, making the assumption that they represented parts of the program that were most frequently executed.

when did you first start using that bit-
vector representation?

Right at the beginning of the ACS project. “Graph intervals” was a term that John had come up with, but then I wrote the paper and carried the idea further. Then Mike Harrison came, and we were struggling with the problem that we had no way of bounding the computation of the flow of information in such a graph.

In some of your papers, you talked
about earlier monotonic relaxation
techniques, but they had very large the-
oretical bounds.

Yes, but I wasn’t much concerned, because I knew that real programs don’t have those, and Mike agreed. Jeff Ullman did some analysis on programs. That did get a better bound, but that analysis didn’t produce a structure against which one could actually make transformations.

the graph interval decomposition improved the theoretical cost bounds of the algorithm by guiding the order— but if I hear you correctly, the interval structure is just as important, perhaps more important, for guiding the transformations than for doing the analysis?

Yes. People who were focusing on the theoretical bounds missed, I think, the importance of leaving a framework in which one could make the transformations. But then something really exciting happened. A student of Knuth’s, [Robert] Tarjan, developed a way to map this problem into a spanning tree.

Nodal graphs could be decomposed
into spanning trees plus back edges.

Yes! It was startling. Great things sometimes look simple in retrospect, but that solved that part of structuring the bounds of subsequent algorithms’ analysis and transformation.

So tarjan’s work played a role in this?

Yes, I don’t think he knew it, but as soon as he published that, it was just obvious that we should abandon graph intervals and go there.

Could you talk about Jack Schwartz?

Jack spent a summer at ACS and had a huge influence. He wrote a number of wonderful papers on optimizing transformations, one being “Strength reduction, or Babbage’s differencing engine in modern dress.” Jack had a list of applications for strength reduction, which we in compilers never took advantage of. He and John wrote a big book, never published but widely circulated, on a lot of this work. I spent a year in the Courant Institute—I taught graduate compilers. And Jack and I were married for a number of years. So it was a good relationship all around.