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,
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
Your 1976 Communications paper with
any single harvest
run for days, and
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-
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-
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
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
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.
what did you think about SetL [a
programming language developed by
It wasn’t the right thing for that
time, but it may be an interesting language to go back and look at now that
we’re mired in over-specifying.
Gregory Chaitin’s classic PLDI paper
on “Register allocation and Spilling via
Graph Coloring” contains a substan-