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

https://github.com/mirrors/gcc/blob/7057506456ba18f080679b2fe55ec56ee90fd81c/gcc/reload.c#L1056-L1110

by mgdo • 12 years ago

202 90 12 years ago

github.com

AYBABTME• 12 years ago

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

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

mrdmnd• 12 years ago

This code is one month younger than me.

dufferzafar• 12 years ago

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

mrspeaker• 12 years ago

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!

asveikau• 12 years ago

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.

bdcravens2• 12 years ago

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

b0z0• 12 years ago

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

kika2• 12 years ago

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.

iajrz• 12 years ago

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.

DannyBee4• 12 years ago

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.

rplnt• 12 years ago

1992.. older..

Now I feel old.

rbanffy• 12 years ago

By 1992 I had already graduated...

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

_davidchambers• 12 years ago

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

dokem• 12 years ago

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?

raldi2• 12 years ago

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.

rdwallis• 12 years ago

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

matthewmacleod• 12 years ago

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

MaulingMonkey3• 12 years ago

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

snogglethorpe2• 12 years ago

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.

tempestn• 12 years ago

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.

adamnemecek3• 12 years ago

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

webkike• 12 years ago

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?

adamnemecek3• 12 years ago

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.

VMG• 12 years ago

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.

frozenport3• 12 years ago

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

chatmasta• 12 years ago

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

adamnemecek3• 12 years ago

That makes it even worse.

Argorak• 12 years ago

You can count that as yet another condition. ;)

goblin89• 12 years ago

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

sbilstein• 12 years ago

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.

RussianCow• 12 years ago

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.

mkl• 12 years ago

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.

hrktb• 12 years ago

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

drglitch2• 12 years ago

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

jzukoff• 12 years ago

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.

Strilanc• 12 years ago

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

ufo• 12 years ago

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.

cbr• 12 years ago

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.

signa11• 12 years ago

much better readability due to proper alignment...

teddyh• 12 years ago

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

ryujo• 12 years ago

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

frevd• 12 years ago

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

nardi• 12 years ago

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.

ajenner• 12 years ago

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.

resist_futility• 12 years ago

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

weavie• 12 years ago

1996 lines to be precise.

But, to be fair it is well commented.

kabouseng• 12 years ago

Or that the module is over 7000 lines...

DannyBee4• 12 years ago

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.

probably_wrong• 12 years ago

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.

rayiner• 12 years ago

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.

SixSigma2• 12 years ago

#ifdef should be shot

Sanddancer• 12 years ago

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.

frozenport3• 12 years ago

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

SixSigma2• 12 years ago

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

shadykiller• 12 years ago

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

acqq• 12 years ago

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

userbinator• 12 years ago

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

wfunction• 12 years ago

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.

chillingeffect• 12 years ago

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

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

zoner• 12 years ago

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

__boomslang• 12 years ago

Needs more goto's.

GnarfGnarf• 12 years ago

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)

valarauca1• 12 years ago

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.

wglb• 12 years ago

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.

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

Related Stories