About RTL and its origins

[Gabriel Ravier]

On 8/5/25 10:20 AM, Pierrick Philippe wrote:
> Hello everyone,
>
> I am currently in the end of my PhD, and I worked a lot with GCC.
> A chapter of my thesis is focusing on GCC and its internal representation.
> I mainly worked on GIMPLE-SSA, but I wanna write an overview of GCC's
> three main representations: GENERIC, GIMPLE (High, Low and SSA) and RTL.
>
> GENERIC is quite well documented regarding its data structures and
> logic, same goes for GIMPLE, alongside the mention of SIMPLE from the
> McCAT compiler as inspiration, which is an academic source (c.f.,
> https://link.springer.com/chapter/10.1007/3-540-57502-2_61).
> I found an academic paper designing an RTL system for the Typed
> Smalltalk (TS) compiler (c.f.,
> https://link.springer.com/chapter/10.1007/978-1-4471-3501-2_14), and I
> naively thought it was the base of the RTL IR for GCC.
> But then, going through the paper, I noticed, they are comparing their
> RTL system to GCC's one.
>
> I tried to go back to the commit introducing RTL IR, but it seems it was
> before the use of git as version control tool and I can't go back the
> initial commit from 33 years ago.
> I also tried to grep in the source code for references, but haven't find
> out anything so far.
> Also, no mention of inspiration are provided in the internals, as
> opposed to GIMPLE and its SIMPLE inspiration.
>
> Digging a bit more, I've found some academic work from Davidson and
> Fraser (c.f., https://dl.acm.org/doi/abs/10.1145/357094.357098) which
> seems to be the first basis of an RTL intermediate language.
> Hence, my question is about the origin of GCC's RTL IR itself, is the
> work from Davidson and Fraser the inspiration for the RTL IR? And are
> there any (other) academic or non-academic sources you can think of?
>
> I'll take any pointers you might have.
> Thank you for reading me,
> Cheers,
>
> Pierrick
>

Sorry for the extremely late response (hope this isn't necroing or 
something like that), but it does in fact appear that Davidson and 
Fraser are in fact the direct inspiration for the RTL IR, old versions 
of the GCC manual specifically state as such:

 > The idea of using RTL and some of the optimization ideas came from 
the program PO written at the University of Arizona by Jack Davidson and 
Christopher Fraser. See "Register Allocation and Exhaustive Peephole 
Optimization", Software Practice and Experience 14 (9), Sept. 1984, 
857-866.
- https://gcc.gnu.org/onlinedocs/gcc-2.95.3/gcc_23.html


Chris Fraser himself also stated that "GCC is based in part on PO" here: 
https://sites.cs.ucsb.edu/~ckrintz/papers/90-fraser-on-PO-and-gcc.html

Although, for precision on that last part, it should be noted that AIUI 
GCC is fully and entirely original code and doesn't have any code from 
PO itself at all - "based" here doesn't mean "uses code from", just "got 
the idea from".