54-line if condition in gcc's reload.c | Hacker News Reader

54-line if condition in gcc's reload.c

github.com

202 pointsmgdo90 comments

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.

Thanks everyone for watching another exciting episode of "Two Lawyers Explain Compiler Theory". :)

To be fair, I still manage the compiler team as well :)

Please note that:

1) The goals of Reload are very complex.

http://gcc.gnu.org/wiki/reload

"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).

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:

http://gcc.gnu.org/wiki/cauldron2012?action=AttachFile&do=ge...

Trivia: This code is older than many of the readers.

https://github.com/mirrors/gcc/blame/7057506456ba18f080679b2...

This code is one month younger than me.

Since it's trivia we're dealing with. This commit was made 18 days before I was born: https://github.com/mirrors/gcc/commit/cbbca02e2430b2dc1f5681... :)

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!

It was 16 lines in 1992. I guess that's not what it is today, but not exactly "so small". https://github.com/mirrors/gcc/blob/42c63e4d48cfac192be8c0cc...

The copyright notice goes back to '87. I wonder if '92 is just where the source control kicks in.

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.

I'm impressed that the blame log has survived intact. What SCM was originally used?

Probably Git? You know that's been around much longer than Github has, right.

Hasn't been around _that_ long. Wikipedia puts the release date in 2005.

Git was released in 2005. Git is only 3 years older than Github

Of course, but even without checking Wikipedia, I remember a time not too terribly long ago when git, and even svn, didn't exist.

And are pretty sure that GCC was around at that point!

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.

Probably RCS http://www.gnu.org/software/rcs/; It's a fact that it used CVS, then SVN at some point (see https://gcc.gnu.org/viewcvs/gcc/branches/CYGNUS/, a branch created by cvs2svn, a migration tool)

EDIT: Apparently all previous history was lost when they implemented CVS, circa 1997. We could always ask someone in the oldest maintainers file available (https://gcc.gnu.org/viewcvs/gcc/trunk/MAINTAINERS?revision=1...) and have the real answer.

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.

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.

SVN was a huge step forward compared to CVS.

> Originally? None.

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...]

1992.. older..

Now I feel old.

By 1992 I had already graduated...

Great. Now I feel a million years old...

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.

And that's why this will be here forever.

Actually reload has been replaced by LRA for x86/x86_64 in GCC 4.8 and work is ongoing to bring LRA to other targets. So it shouldn't be forever.

There's an off-by-one error in this thread's title. ;)

Why put logical operator at the start and not the end of each line?

I.e., this style (used in this case)

      && (CONSTANT_P (SUBREG_REG (in))
	  || GET_CODE (SUBREG_REG (in)) == PLUS
	  || strict_low
	  || (((REG_P (SUBREG_REG (in))

versus this style:

      (CONSTANT_P (SUBREG_REG (in)) ||
	  GET_CODE (SUBREG_REG (in)) == PLUS ||
	  strict_low ||
	  (((REG_P (SUBREG_REG (in)) &&

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).

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 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.

This, plus the stucture stays very readable even if for any specific reason a test clause has a very long line.

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

SELECT

    some_col

    , another_col

    --, and_another

    , and_more

FROM

    blah

EDIT: too bad formatting is screwed up :/

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.

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 :)

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.

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).

Javascripr lets you put the binary operators in the next line if you want. It won't insert a semicolon there:

http://blog.izs.me/post/2353458699/an-open-letter-to-javascr...

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.

Jshint still complains about it even though it's technically okay.

See how they're using #ifdefs? Those work much better with initial operators. Consider:

    ...
		  == NO_REGS))

#ifdef CANNOT_CHANGE_MODE_CLASS || (REG_P (SUBREG_REG (in)) && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER && REG_CANNOT_CHANGE_MODE_P (REGNO (SUBREG_REG (in)), GET_MODE (SUBREG_REG (in)), inmode)) #endif ))

That || needs to be inside the #ifdef, so it can't follow on the same line as the "== NO_REGS))".

And once you're doing that, might as well use them for the whole file.

much better readability due to proper alignment...

It’s from the GNU Coding Standards, section 5.1 Formatting Your Source Code¹:

When you split an expression into multiple lines, split it before an operator, not after one. Here is the right way:

    if (foo_this_is_long && bar > win (x, y, z)
        && remaining_condition)

1) https://www.gnu.org/prep/standards/html_node/Formatting.html

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

constant...

or get code...

or strict low

instead of

constant... or

get code... or

strict low

for copy&pasting around this is very practical, also with arrays:

$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).

I'm more concerned with the fact that the function is more than 700 lines long.

1996 lines to be precise.

But, to be fair it is well commented.

Or that the module is over 7000 lines...

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. :)

That makes it even worse.

You can count that as yet another condition. ;)

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:

http://pastebin.com/9zpr7Cd5

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.

I find "inmp > msrirp;" way more readable than "inmpgtmsrirp".

The same goes for "GET_MODE_PRECISION(msrirp)" which was replaced with "msrirp."

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.

[Edit] Time sequence correction.

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.

That's an argument from survivorship. Just because they've been successful doesn't mean this code shouldn't be improved.

You could say exactly the same about OpenSSL - it's not a good argument.

No. A bug in OpenSSL makes the thing meaningless while in GCC it affects some corner case. I want better vectorization.

> while in GCC it affects some corner case

If that corner case manifests as a bug in OpenSSL, it is by definition at least as bad as a bug in OpenSSL.

You're assuming and implying that this code is more bug-prone in its current state than it would be if it were rewritten.

I'm not convinced that's true.

> 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...)

Old code is better - it's got bug fixes.

> Old code is better - it's got bug fixes.

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.

To be fair, new code frequently has those attributes too.

If you've read some of the other posts, this whole file will hopefully be removed sometime in the future. For x86/x86_64 this file isn't of any use.

Edit: also reading the wiki, they are fully aware how bad this code is.

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)

>booleans

C doesn't support native booleans, C99 does-ish. And you can hack it in with

    #typedef enum {false, true} bool;

C uses ints, all the way down, for everything, until you hit turtles.

Needs more goto's.

At least it's not all the conditions in a single line :)

At least it's a proof that GCC is smart enough to understand and compile this condition :)

#ifdef should be shot

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.

There is no other mechanism to choose between <windows.h> and <linux.h>

Plan 9 manages to build the whole OS and userland for multiple architectures without using ifdefs, even cross compiling across CPUs with different endianness

No wonder llvm is getting popular (I realize that there are other reasons besides codebase quality).

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.

I'm sure a good optimizing compiler like GCC would optimize out repeated expressions in conditions ;) (perhaps not if they're declared volatile(?))

Definitely not if they're declared volatile

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.

`if` statements are for the 80s, we live in in the 90s and have objects, inheritance and C++. The conditions can be implicit in the objects.

I don't even.

A qualified defense of the grandparent post.

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.

Reply on news.ycombinator.com