Conditional Elimination through Code Duplication

My Advanced Compilers course at IIT Bombay under Prof. D. M. Dhamdhere also involved a group project. Our group had the task to pick an existing compiler optimization which works by restructuring the control flow graph of the code, and implement that in LLVM. As we did not quickly find a suitable optimization, I came up with a simple idea by myself. At first, our professor was not really pleased by this move, but after the second presentation or so, when the ideas were more streamlined and we noticed how simple yet possibly widely applicable the transformation is, he allowed us to carry on with it. I concentrated on the theoretical part, writing a paper describing it, while the others in the team implemented parts of it as a pass for the LLVM compiler.

The idea is simple: If within one execution of a program the same conditional expression (e.g. a variable debug_enabled) is evaluated several times, then it might be faster to copy the code in between the conditional jumps and thus “remember” the result without further conditional jumps. Of course this increases the code size, and there is a trade-off, but in some instances the benefits could well be the worth the effort, especially inside tight inner loops. You can read more about it in my paper about CECD, and I’m considering uploading it to arxiv.org as well.

Update: I have put it on arXiv.org as publication 1106.3478


Given branch prediction & the significance of small code size (think caching) it might conceivably not improve things.
#1 Anonymous am 2011-05-27T21:33:55+00:00
I recommend Craig Chambers' thesis.
#2 Derek Elkins am 2011-05-27T22:34:27+00:00

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.