Inter-variable Out-of-SSA Coalescing in GCC

It was little more than a decade ago that GCC was dragged, kicking and screaming (as Richard T. Henderson put it), into adopting the SSA form for part of the compilation process. RTL remains in use for the later compilation passes, and the conversion out of SSA takes place exactly at the translation from the GIMPLE SSA form to RTL.

As usual, during this translation, we partition and coalesce SSA versions so as to reduce the number of allocated registers and stack slots and of copy instructions.

We used to regard, as candidates for coalescing into the same partition, only different versions of the same variable, and anonymous SSA versions (created for some compiler-generated temporaries) with the same type.

That was not as bad as it sounded:  the copyrename pass, executed several times per compiled function, identified copies between versions of different variables and changed the variable of one of them, so as to
enable them to coalesce into the same partition. Unfortunately changing variables was often confusing when tracking down gcc bugs by analyzing intermediate representations.

Before we introduced variable tracking at assignments (VTA), such changes also severely impacted
debug information generation. Copyrename passes used to refrain from renaming SSA versions of non-inlined user-visible variables, to reduce the debug information impact, but after VTA was introduced, we could lift this restriction, since copyrename no longer affected debug information. Although the debug information issue had already been addressed, copyrename still affected GCC dumps.

Most of all, the copyrename passes were wasteful, because the out-of-SSA pass also examined all SSA copy statements. It just rejected, as candidates for coalescing, those that didn’t copy between versions of
the same variable. There was room for improvement.

Furthermore, copyrename would not rename for coalescing versions of different function parameters, nor would it operate on versions of the function result. There was a good reason for that: unlike normal
variables, parameters and results are handled in a special way by the out-of-SSA conversion, because RTL for them had to be allocated and initialized with the incoming arguments by the code that dealt with
various calling convention details, as opposed to just being assigned pretty much any uninitialized (pseudo-)register or stack slot. These special requirements only applied to the actual incoming values; other versions did not have to be so limited, so there was room for improvement there too.

Finally, out-of-SSA created declarations to serve as the variable for each set of coalesced anonymous SSA versions. Avoiding this small waste of compile time and memory was desirable.

GCC PR64164 provided us with the excuse we needed to tackle these long-standing wishes for improvement.

Ideally, we’d be able to deal with parameters and results within a function just as if they were like any other variable, and we’d separate the code that dealt with extracting incoming parameter values from
their incoming locations from the code that stored them in their function-internal initial locations.

Given the number of different targets with different calling conventions idiosyncrasies, making significant changes to the calling-convention code was found to be too risky, and it wouldn’t get us better generated code or a more maintainable compiler.

So, we avoided excess complexity by leaving that code mostly alone, and using the RTL assigned by it for partitions holding the initial versions of parameters.

We could thus successfully remove the copyrename passes without harming generated code by integrating similar functionality into the out-of-SSA expander. It’s not equivalent because we can now also coalesce versions of function arguments and return values with user-defined variables and
compiler-introduced temporaries, which tends to generate slightly better code and to save compile time.

We no longer create declarations for the temporaries: after some adjustments we made, GCC can now deal with the anonymous SSA names directly in the coalescer and in the expander, without an underlying
declaration, completing the project that introduced anonymous SSA names years ago. This saves a bit of compile-time memory.

We also added assertions to check that RTL assignments met the expectations with regards to register/memory placement and access modes. That revealed a number of cases in which results and parameters that we expected to hold in registers were assigned to memory, and of parameters and results in registers of unexpected modes. All of these cases were fixed, and the assertions remain active in development releases of GCC. This made the compiler more maintainable.

The primary goal of this change was to make GCC more maintainable:  plenty of unnecessary or complex code was removed, and simpler code replaced it. Compile-time and even run-time benefits exist, but they
were just desirable side effects.

This improved out-of-SSA coalescer is expected to be present in the upcoming GCC release 6.


Join the Red Hat Developer Program (it’s free) and get access to related cheat sheets, books, and product downloads.

Share