Ehren's Blog

Popping my GIMPLES (a plan)

Posted in Seneca by ehren on September 30, 2009

This week marks the deadline for our initial project plan in DPS909 and I must admit that if left to my own devices I would be putting this post off even more than I already have. However, especially after a conversation with humph and mhoye last Friday on IRC, I must admit that working on open technology means working in the open, even if you don’t have all the pieces together quite yet.

In a previous post I offered a brief overview of my project which involves adding support for an alwayszero function attribute to gcc. The description provided by Taras in the bug gives a general outline:

nsresult rv = call();
if (NS_FAILED(rv)....) <-- gcc should be able to optimize this away if it knows that value of call() is always zero

Previously, I had been tackling this project solely by code reading, including grepping the sources and going file by file through the code base (my kingdom for a good multiline grep). Although I believe this approach will bear fruit in the coming week, I would like to mention and dispense with one whopping illusion I had upon beginning the project:

* That it can be completed without knowledge of compiler design and formal grammar.

My solution has been to find the best textbook I can (and I think I’ve done it). On Thursday I finally got my hands on a copy of Compiler Construction – Principles and Practice by Kenneth Louden, and I’ve since been burning through it. I’ve already got through the first 4 chapters which so far have given a fairly rigorous overview of Scanning (including LEX), Parsing and CFGs, and (various kinds of) Top Down Parsing (next on the docket: Bottom Up Parsing and Semantic Analysis).

At this point you may be thinking I’ve gone totally off the rails. However, this book has helped me to better grasp another important text I had overlooked: The GCC Internals Manual. Admittedly, my problem has nothing to do with Scanning (Converting lexemes into tokens). It also has nothing to do with Parsing Algorithms, which build an (abstract) syntax tree out of the tokens. But, as far as I can tell at this point, the problem will require me to traverse this parse or syntax tree in order to locate the start of the next statement sequence after the unnecessary test of the function’s return value. I would expect that the calling function of a function can be accessed as a parent node of the function. I’ll return to this question of where exactly my modifications should take place shortly.

I should mention that another step–Semantic Analysis–is undertaken by the compiler which involves, for example, recognizing context sensitive aspects of the language. For example, in C you must declare an identifier (variable name, etc) before using it ie in an undeclared context an identifier is illegal but if declared it is legal (I haven’t got to the chapter on this subject yet but apparently this (static) semantic analysis is undertaken using a lookup table).

Now that I’ve given a broad overlay, let’s consider actual GCC specifics. The book I’m reading explains an important dichotomy in compiler design between the front end (those operations which depend entirely upon the source language) and the back end (those operations which depend totally on the target language). Apparently for C and C++ the front end builds its internal language representation using this tree structure. The docs also mention a similar structure known as GENERIC which, although bypassed by C and C++, is used by a number of different languages (FORTRAN is parsed to its own unique representation which is then converted to GENERIC).

Likely, most of the reading I’ve done is unnecessary in that it doesn’t matter how the parsing is actually completed. All I’m concerned about is taking that tree, once constructed, and bypassing one or more statement sequences that depend on the return value of an alwayszero function. I should be able to access the calling function of an alwayszero function as a parent node of that function. Functions, for example, are represented using a FUNCTION_DECL node. This page also lists the relevant control structure nodes which I may have to consider one by one in order to remove unnecessary branches. Unfortunately the docs don’t mention accessing a calling function from a child node so this may have to be gleamed by viewing the definition of the FUNCTION_DECL node. It is mentioned here that a call to a function is represented by a CALL_EXPR node, but I’m really after the callee and not the caller. My guess is that a calling function can be accessed by a more generic (not GENERIC) tree macro.

At this point I am tantalizingly close to the first stage of my problem: creating and recognizing a function attribute. GCC defines a macro DECL_ATTRIBUTES (tree decl) which returns a TREE_LIST representing the attribute. My first step is to add and recognize a new attribute which I hope can be completed shortly. See this page for the documentation of function and variable attributes.

At this stage I need to specify my initial release plan for the project which is as follows:

0.1 – Oct 19, 2009: Create and Recognize a function attribute. Also hopefully gain access to the caller of a function, given the FUNCTION_DECL node of that function.

0.2 – Nov 16, 2009: Perform some amount of branch optimization. Taras’ code example in the bug outline illustrates some of the complexity in this optimization, in that the actual call to the function is not within the test expression of the if statement. Conceivably I’ll be ably to iterate through all of the statements of the caller to determine what’s unnecessary.

0.3 – Dec 7, 2009: If not a release worthy patch, hopefully I’ll at least have some functional code that meets the specs.

One particular concern I have is that necessary optimizations might not take place at the tree level. After the parse, gcc converts the tree structure into a kind of three address code called GIMPLE (part of the middle end). After this GIMPLE is translated into an assembly like language called RTL, which combined with knowledge of the target architecture, allows for the object code output. Naturally, it’s probably much easier to write segmented model x86 assembly code than to dig into these representations.

One other thing is that Taras did mention the possibility of using static analysis (perhaps with Dehydra) to confirm correct behavior of the attribute. David Humphrey pointed out an interesting blog post by Taras where he describes the addition by Zack Weinberg of an NS_MUST_OVERRIDE static annotation, combined with a script to ensure that NS_MUST_OVERRIDE methods are always overridden. I could imagine that using a similar Dehydra annotation would suffice to ensure that a function annotated as alwayszero never has it’s return value checked, but I would think that this introduces the danger of not checking the return value of a function that is mistakenly assumed to be alwayszero. Perhaps two different annotations could be defined both for the caller and the callee (and a match could be made between the two), but I’d rather attempt the gcc modification just for the cool factor (I realize this a very dangerous standard in deciding how to tackle a bug).

Please see the project wiki for updates, especially as more concrete developments take place.


7 Responses

Subscribe to comments with RSS.

  1. Benjamin Smedberg said, on September 30, 2009 at 3:56 pm

    Are you planning on writing an analysis pass, to warn the coder that their code is dead, or a GCC optimization pass which actually removes the dead code for them? If the latter, I don’t think you want to be traversing the C++ syntax tree. Rather, I think you’d be better off doing the analysis on the GIMPLE tree after it has been converted to SSA form. Once you’re in SSA form, it’s a lot simpler to follow the value from function call to use, and see where the dead branch occurs.

    To start out, you might want to just write an analysis pass using dehydra: there’s a fair bit of prior art in the analysis.js and ESP.js frameworks which already does the basic block traversal and value tagging.

  2. Taras said, on September 30, 2009 at 4:32 pm

    I’m impressed by your progress so far. Actually the problem is simpler than you think. Flip through your compiler books to “value analysis”. I’m 99% sure that gcc already can eliminate statements like
    rv = 0
    if (rv) {// always false, therefore nuke this

    So the hard part of your problem can be restated in terms of ensuring that gcc knows that rv == 0. After that just make sure that gcc is ineed eliminating those if statements and be happy.

    btw, that is a gross blog title 🙂

  3. […] hold. Luckily, one of David Humphrey’s students decided to take on the first task, see his blog post here. I’m really psyched about this, few things that are cooler than cross-project open […]

  4. jmdesp said, on October 1, 2009 at 6:06 am

    I’m 100% behind tara here.
    Find a way so that for always zero functions, gcc instead of
    “rv = function;” ends up seeing this “function; rv=0;” and you’re done,
    existing dead code elimination will do the job for you.

    Now there should be in addition to this, a static analysis script taht makes
    sure always zero function really don’t return a value.
    It’s more complex than making sure their return value isn’t checked but it can bendone also, there has been some similar work already.

  5. […] I’m not a gcc hacker.  Instead, I’ve taught him how to be lost productively, how to manage fear and turn it into forward momentum measured in inches.  And more than this, I’ve gotten him connected to some amazing new […]

  6. […] I ended up implementing almost exactly what was suggested in this comment by jmdesp except it was necessary to make sure that the gimple call remained a value returning […]

  7. […] C’est quoi les CFG ? Context-free grammar en fait. La documentation lĂ  dessus dans GCC : Et un peu de rĂ©flexion sur le sujet. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: