For the curious, reload was written by Richard Kenner, who, while a wonderful guy, was not generally familiar with modern compiler architecture (graph coloring register allocation goes back to 1982, reload was started in the late 80's).
It essentially took the place of spill placement/code/legalization. Over the years, it grew rematerialization, instruction combination, copy coalescing, stack slot sharing and all sorts of other interesting scope creep.
While i believe it has finally been replaced by LRA for some targets, there were many people who spent years of their life trying to replace reload with separate, smaller pieces of architecture. No one has yet completely succeeded.
It is essentially an interesting object lesson in what happens when you just incrementally improve architecture to achieve performance goals without a stop-loss point for requiring new design.
As someone moderately curious, I hope I'm not the only one when I say: I didn't understand a word after "the late 80's". And that's only because I searched for "graph coloring register allocation" first.
For simplicity, a compiler manipulates an internal representation in terms of virtual registers. A register allocator assigns physical registers to these virtual ones, under the principle that different virtual registers may be assigned to the same physical one if they are not live (I.e. hold a value that will be used in the future) at the same time.
Spill code generation is necessary because at a program point, there may not be enough physical registers for all the live values, and code must be generated to spill some of them to the stack and reload them when needed. Legalization performs code transformations to eliminate target independent operations in the IR that can't be represented on the target. Copy coalescing eliminates the need for copies between virtual registers by assigning both to the same physical register. Rematerialization takes advantage of values that can be recomputed cheaply, and instead of holding them in a register for a long time, recomputes them where needed.
What makes this all so complex is that 1) most of these don't have polynomial time algorithms that produce optimal solutions: 2) the individual problems are mostly coupled. E.g. spill code itself uses registers, and so the interference graph (which summaries whether virtual registers are simultaneously live) might need to be recomputed or modified.
If you're interested in this sort of thing, Kieth Cooper at Rice has posted the lecture notes for his graduate compilers class online: http://www.cs.rice.edu/~keith/512/Lectures. Register allocation is lectures 26-7.
"Reload does everything, and probably no one exactly knows how much that is. But to give you some idea:
Spill code generation
Instruction/register constraint validation
Constant pool building
Turning non-strict RTL (Register Transfer Language, a very low level intermediate representation used in the backends of GCC) into strict RTL (doing more of the above in evil ways).
Register elimination--changing frame pointer references to stack pointer references
Reload inheritance--essentially a builtin CSE (Common Subexpression Elimination) pass on spill code"
Reload achieved them for the last 25 years(!)
2) There are more modern approaches to reach such goals, but knowing 1) it is a lot of work before the goals can be achieved by some alternative code for all platforms (I don't know how far the developers got at the moment)
3) "Local Register Allocator
Project" presentation by Vladimir Makarov, working for RedHat:
That's beautiful. It may be a monster, but it started so small in 1992 - then was grown with loving care in 1993, 1994, 1995, 1998, 1999, 2001, 2002, 2004, 2005, 2008, and 2011!
I thinks that's just when the source control kicks in.
DannyBee claims that reload was started in the late 80s.
There are commits going back to 1988, but it looks like a lot of the early commits are out of order; the repository was (at least) converted from RCS to CVS to SVN to Git.
So, i converted the repository to SVN (which is what this is based on).
Originally?
None.
Then RCS
Then it forked into EGCS and GCC, and EGCS used CVS
On remerge, we used CVS.
Then we converted to SVN.
I basically rewrote large parts of cvs2svn to make this happen (before that it took weeks to convert and ran out of memory anyway :P)
During cvs2svn conversion, the old GCC RCS versions we had data for were inserted as branches and older revisions, as appropriate
Since the original per-file version numbers were not kept, this was done by inserting it and then incrementing existing version numbers on the RCS files that made up the CVS repository, and hacking up the cvs2svn parser slightly to allow for some idiosyncracies (because now you have a billion years worth of RCS bugs to parse)
So basically, history goes back as far as there were version control systems that were being used, which is roughly 1987
Before someone asks why it got moved to SVN, at the point at which we converted to SVN,
1. git was not popular yet (or all that usable yet for that matter)
2. GCC's biggest VC problem was needing single repository version numbers for tags, and atomic commits, which SVN solved.
Although note that a lot of earlyish GNU codebases kept tons of older versions of source files around in the form of Emacs versioned backup files, and there were RCS-conversion scripts that would commit all of those as RCS versions...
[There would be no log messages for those older versions, of course, but the writers and creation dates of the older files were potentially available... I don't really remember whether those conversion scripts actually used that info or not, although I think they did...]
When I started working on gcc 1.36 (company I was working for was designing Unix workstations and we were fixing the backend for MC680x0) we used RCS. But I'm not sure it was the original SCM, we didn't even have Internet access then :-) And we got gcc 1.35-36-37 "smuggled" to us on the 1/4" tape.
I was a MC680x0 maintainer back in those days. Also picked up i860 for the gcc 2.x stream. Fortunately I was at UMich in the gcc 1.x time, and we had NSFnet.
And yes, I used RCS when working on the gcc source.
Nice to meet you! :-) I still (barely) remember one bug which gave me a hard time - when compiling for 68030, I believe, under certain conditions gcc put floating point variables initialized with a constant into the constant segment. Which caused access violation when code tried to put something else into this variable. Or something along these lines, when was that, 25 years ago? Circa 87 or 88.
We used 860 (not sure) and 960 (definitely) too for other products.
Your last part is not correct. We had the "old-gcc" RCS files, it just was in a format not parseable by CVS. It was not entirely lost, just not easily accessible. Ian Taylor went to the trouble of rewriting the RCS files CVS had, and that we based the SVN repository on, to include the old data, so actually, SVN had more history than the CVS versions, dating back to 1987.
I was going to take a crack at breaking this apart into component functions, but I realized that I don't know where to draw the lines, or what to name the functions, without understanding the internals of this part (and probably other parts) of the compiler.
I don't have a personal preference here, just looking for any practical pros and cons I may not be aware of.
More on topic, I don't see why keep such a big conditional and not move it out to its own function(s) (but this has been asked already in this thread).
I used to use the latter, in both code and maths, but I have switched to the former. My main reason is that having the operators (logical and otherwise) at the start of the line means they're more likely to be in the same horizontal position, so it's easier to see which lines are continuations of the previous ones.
It is also easier to comment out lines of code if you need to test something.
This is especially useful in SQL, where you can quickly -- a condition or a column, without editing commas etc on other lines, eg
Isn't this behaviour exactly the same as with commas at the end? Here, to comment out the first line you would need to edit the second. With commas at the end, to comment out the last line you would need to edit the second last. Other than that, no editing of other lines is required.
In fact, in a language like Javascript where extra trailing commas are allowed, it seems that this argument makes even more sense for commas at the end than it does for commas at the beginning. Then, there would never be a situation where you would have to edit a line besides the one you were commenting out.
Trailing comma in SQL is a syntax error. It's also not allowed in JSON. And editing second last line can be a pain if you're testing something and are commenting/uncommenting the last line repeatedly.
Not if the line you're commenting out is the last item of a select or a join command or an AND within a where clause. Sorry Gould have made better example
But it was 4 am :)
One plus of the former is that you can add a new clause without needing to edit an existing line, makes for cleaner diffs during reviews and makes it such that you wouldn't show up as the last person who touched the existing line in git blame or any other source control equivalent.
I prefer the operators at the start because the start is less jagged, so the operators don't get spread out so much and stand out more.
Usually I only put them at the end of a line in languages that do implicit line endings, and will false-positive when you move the operator to the next line (i.e. javascript and visual basic).
I would say that the most common problem is having a semicolon not being inserted if you start a line with `(` or `[`. In practice, the only time when a semicolon gets inserted where it shouldn't is when returning an object literal.
Personally I find it easier to read the conditionals lined up in columns and with indentation on the left than at the end where they may or may not be lined up depending on the length of the expression.
I like the operator at the beginning because you can see the type of comparison at a glance, but most everyone I've talked to prefers them at the end. To each his own, I guess.
I like the former, since it's more readable. I mean as in written English, you should put conjunctions at the start of a new line instead of letting them "hang". So you get
for copy&pasting around this is very practical, also with arrays:
<pre><code>
$moo =
[
a
, b
, d
];
// insert c
</pre></code>
better than having the delimiter at the end, where you a) have to take care where you relocate the last element and b) could forget to remove it at the last element (most language parsers tolerate that though).
To be fair, the length is not strictly 54 lines, since blocks of it depend on evaluation of the preprocessor (the #ifdef stuff). Still, that's pretty long. :)
The rest of that file also has a ton of redundancies and verboseness its in logic that could be simplified considerably; e.g. I see this pattern a lot (428 ~ 435):
x && y || !x && z
In this absence of side-effects, this basically implements a 2-input multiplexer and is identical to
x ? y : z
In the 54-line condition the first obvious thing I'd factor out is SUBREG_REG(in) and GET_MODE(SUBREG_REG(in)), and then work out what else is duplicated from there. Here's my attempt at making this a little more readable. It's only 2 lines less, but this gets rid of all the repeated uppercase:
The way it was for me was that I only "got" the hang of the ternary operator once I learned what a multiplexer is and how it's implemented. Before that, it was something I used now and then (certainly didn't have any trouble understanding it or anything like that), but I never thought about it as some way to channel data through based on a condition. I just always thought of it as some handy form of conditional evaluation. Things "clicked" a lot when I learned about how digital hardware and muxes works.
This reminds me of a comment in a particularly hairy section of code in the MWC 8086 compiler written by dgc (among other things, author of MicroEmacs). I don't have the exact wording but it was something to the effect of
I am frankly embarrassed by the number of bugs that have been tracked to this function.
This was in the day before register coloring.
Earlier, I had the chance to write a code generator for an implementation language targeting the 8085 (!) and even that was sufficiently hairy that the team that took it over complained about the difficulty of improving the code.
Why not break it up into variables or functions so that the logic can be followed while reducing the likelihood that a bug creeps in? What is the excuse for horrible code like this?
It's been getting the job done for decades, in perhaps the most popular compiler of all time. I'm willing to trust the maintainers' judgement on this one.
If they'd spent all their time needlessly fixing what ain't broke, gcc would've gone the way of GNU/Hurd.
> It's been getting the job done for decades, in perhaps the most popular compiler of all time. I'm willing to trust the maintainers' judgement on this one.
I don't trust anyone - myself included - writing code 1/10th as convoluted, age-of-product be damned. Code is not wine, old doesn't mean good. Neither do the maintainers, methinks: Looking at blame shows some refactoring.
> If they'd spent all their time needlessly refactoring, gcc would've gone the way of GNU/Hurd.
And the lack of needful refactoring may very well send it the way of COBOL - with everyone merely wishing it had gone the way of GNU/Hurd. I've seen clang and LLVM replace gcc in both of my vendor toolchains that used gcc - suggesting they've already wished and then done something about that wish.
(Either that or licensing, but code like this stomps on the scales a bit...)
It's also got prototypes that made it into production, ball of mud designs that encourage usage bugs, and C++ thrown together by that short lived intern who took a few Java classes, wrote everything assuming there was a garbage collector around, and took great care to avoid class trees with less than 3 layers of inheritance lest he be shamed for lack of 1337ness... then topped it off with a few __try/__catch blocks to deal with that one rare crash that nobody could find a repro case for.
Re-implementing bug fixes is a toll... sometimes a very worthwhile one, though.
The problem of course, is that although reload very typically would work pretty well for the existing supported architectures (and optimizations etc), porting to a new architecture or changing other algorithms in the compiler would often expose problems that required extremely painful tweaking of the mess of unstated assumptions in the giant code hairball that is (was) reload... ><
LRA is by all appearances infinitely more maintainable.
Because the choice is never, "Should I refactor this code or not?" The choice is, "Should I refactor this code, or work on this feature/bug/refactoring/etc. instead?" Sure it could be refactored to be cleaner, but thus far, presumably there has always been something more important to do.
Any time this if statement has been edited, it was clearly faster to simply add to the existing one than to refactor the whole thing. Sometimes it makes sense to take that extra time to refactor code when you happen to be working on it anyway... and sometimes there's something else more pressing to do.
I will never have the skills to maintain let alone write a compiler. However, in a situation like this, I would break up the condition into a set of sub-conditions, set intermediate booleans, and progressively build upon the condition tests so as to make the code more intelligible and maintainable. No need for additional functions.
(Amusing incongruity: "boolean" fails the spellchecker in an IT forum :o)
There are definitely times when it's overused, and times when it could be factored out. However, when you're dealing with the low level stuff a compiler that targets multiple architectures has to, using preprocessor defines can make things less maddening. GCC targets architectures that have all sorts of weird quirks regarding register locations and visibility, memory models, etc, that need to be accounted for. Without those #ifdefs, the code could very well be uglier with redundant checks, even uglier if statements, etc.
Plan 9 manages to build the whole OS and userland for multiple architectures without using ifdefs, even cross compiling across CPUs with different endianness
Compilers are complex, and these conditionals had to be evaluated in some way. Sure the author could have split it up into multiple if statements, but would have that really helped?
Yes, yes it would have, there is literally no question about that. It also appears that some of the parts of the conditions are repeated, so those could have been refactored.
You could pull out boolean subexpressions and give them descriptive names and still use one if statement. It's even in the Google C++ style guide I believe.
In a lot of software in the industry I've seen, I'd say he's right -- instead of an "if X condition, do X code, if U condition, do Y, otherwise do Z" you can make an object, subclass the object's base class into a default type doing Z and two other types that do X and Y instead. (If you need to share more behaviors in a more complicated setup, you make the strategies into classes as well, then have the X1 and X2 classes invoke the X strategy.) Happiness ensues! (unless you're stuck with too much ugly-looking Java boilerplate or insane C++ templatization angle-brackets)
That said...
any good advice like that should be taken with a MASSIVE grain of salt because of the exigencies of real software development, especially software like gcc. Moreover the approach is not a panacea against code complexity because sometimes the relationships between different types of conditions are just plain complicated, as appears to be the case here.
So I can totally understand where this code is coming from, and while I can imagine it being far more elegant, it's not really the prime candidate for a rant. Grandparent post should chill out.
It essentially took the place of spill placement/code/legalization. Over the years, it grew rematerialization, instruction combination, copy coalescing, stack slot sharing and all sorts of other interesting scope creep.
While i believe it has finally been replaced by LRA for some targets, there were many people who spent years of their life trying to replace reload with separate, smaller pieces of architecture. No one has yet completely succeeded.
It is essentially an interesting object lesson in what happens when you just incrementally improve architecture to achieve performance goals without a stop-loss point for requiring new design.