8 ms·
54-line if condition in gcc's reload.c
- AYBABTME 12y agoTrivia: This code is older than many of the readers. https://github.com/mirrors/gcc/blame/7057506456ba18f080679b2fe55ec56ee90fd81c/gcc/reload.c#L1056-L1110 https://github.com/mirrors/gcc/blame/7057506456ba18f080679b2...
- mrdmnd 12y agoThis code is one month younger than me.
- dufferzafar 12y agoSince it's trivia we're dealing with. This commit was made 18 days before I was born: https://github.com/mirrors/gcc/commit/cbbca02e2430b2dc1f5681e15b620524bb4da6db https://github.com/mirrors/gcc/commit/cbbca02e2430b2dc1f5681... :)
- mrspeaker 12y agoThat'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 12y agoIt 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/42c63e4d48cfac192be8c0ccf36ee82193a03000/gcc/reload.c#L468-L484 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.
- LukeShu 12y agoI 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.
- deleted 12y ago[deleted]
- bdcravens 12y agoI'm impressed that the blame log has survived intact. What SCM was originally used?
- b0z0 12y agoProbably Git? You know that's been around much longer than Github has, right.
- kehrlann 12y agoHasn't been around _that_ long. Wikipedia puts the release date in 2005.
- nemothekid 12y agoGit was released in 2005. Git is only 3 years older than Github
- deleted 12y ago[deleted]
- bdcravens 12y agoOf course, but even without checking Wikipedia, I remember a time not too terribly long ago when git, and even svn, didn't exist.
- misnome 12y agoAnd are pretty sure that GCC was around at that point!
- kika 12y agoWhen 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.
- 12y ago
- rplnt 12y ago1992.. older.. Now I feel old.
- rbanffy 12y agoBy 1992 I had already graduated... Great. Now I feel a million years old...
- _davidchambers 12y agoThere's an off-by-one error in this thread's title. ;)
- dokem 12y agoWhy 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?
- raldi 12y agoIt'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 12y agoThat's an argument from survivorship. Just because they've been successful doesn't mean this code shouldn't be improved.
- matthewmacleod 12y agoYou could say exactly the same about OpenSSL - it's not a good argument.
- frozenport 12y agoNo. A bug in OpenSSL makes the thing meaningless while in GCC it affects some corner case. I want better vectorization.
- MaulingMonkey 12y ago> 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.
- raldi 12y agoYou'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.
- adamnemecek 12y agoNo wonder llvm is getting popular (I realize that there are other reasons besides codebase quality).
- webkike 12y agoCompilers 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?
- adamnemecek 12y agoYes, 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.
- laichzeit0 12y agoI'm sure a good optimizing compiler like GCC would optimize out repeated expressions in conditions ;) (perhaps not if they're declared volatile(?))
- smcl 12y agoDefinitely not if they're declared volatile
- VMG 12y agoYou 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.
- frozenport 12y 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 12y agoTo 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. :)
- adamnemecek 12y agoThat makes it even worse.
- Argorak 12y agoYou can count that as yet another condition. ;)
- goblin89 12y agoWhy 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 12y agoPersonally 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 12y agoI 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 12y agoI 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 12y agoThis, plus the stucture stays very readable even if for any specific reason a test clause has a very long line.
- deleted 12y ago[deleted]
- 12y ago
- nardi 12y agoI 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 12y agoActually 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 12y agoI'm more concerned with the fact that the function is more than 700 lines long.
- DannyBee 12y agoFor 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 12y agoAs 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 12y agoFor 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 http://www.cs.rice.edu/~keith/512/Lectures. Register allocation is lectures 26-7.
- SixSigma 12y ago#ifdef should be shot
- Sanddancer 12y agoThere 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.
- frozenport 12y agoThere is no other mechanism to choose between <windows.h> and <linux.h>
- SixSigma 12y agoPlan 9 manages to build the whole OS and userland for multiple architectures without using ifdefs, even cross compiling across CPUs with different endianness
- shadykiller 12y agoAt least it's not all the conditions in a single line :)
- acqq 12y agoPlease note that: 1) The goals of Reload are very complex. http://gcc.gnu.org/wiki/reload 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). 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: http://gcc.gnu.org/wiki/cauldron2012?action=AttachFile&do=get&target=Local_Register_Allocator_Project_Detail.pdf http://gcc.gnu.org/wiki/cauldron2012?action=AttachFile&do=ge...
- userbinator 12y agoThe 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 http://pastebin.com/9zpr7Cd5
- wfunction 12y agoThe 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 12y agoI find "inmp > msrirp;" way more readable than "inmpgtmsrirp". The same goes for "GET_MODE_PRECISION(msrirp)" which was replaced with "msrirp."
- zoner 12y agoAt least it's a proof that GCC is smart enough to understand and compile this condition :)
- __boomslang 12y agoNeeds more goto's.
- GnarfGnarf 12y agoI 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 12y 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 12y agoThis 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.