Posts

Compilers make heavy use of graph data structures as all the code being compiled is essentially stored as a graph. Most compilers also provide ways for visualizing these complex data structures which might come in handy while debugging, and help understanding certain optimizations. Let’s have a look at some of these data structures and how to visualize them using graphviz and LLVM passes. Note: All the graphs we’ll produce are generated in .dot format. If you want to visualize them make sure you have support for graphviz in your IDE or use an online tool. ...

Continuing on the loop optimizations covered in my last post here. Let’s look at one of the key loop optimization in detail today. Loop unroll as the name suggests tries to take the key aspect of a loop out of the loop i.e. looping xD. It achieves so by copying the instructions inside the loop and reducing the number of loop iterations or completely getting rid of them as we will see now. I’ll try to build up from basic examples to how it is implemented in the LLVM compiler. ...

Introduction Loops are “the” most compute intensive part of any software program making loop optimizations some of the most rewarding optimizations for a compiler. In this post, I’ll try to go over some of these optimizations which are covered by LLVM(I’m sure you’ll find them in other compilers too). This is not an extensive list you can always find more. Loop Invariant Code Motion (Code hoisting) It’s a known coding practice to always keep definitions and constant code outside the loop. What’s interesting is even if you don’t, the compiler will take care of it. The compiler determines if any instruction is “invariant” and moves it out of the loop. Either inside prehearder(every loop in LLVM has a preheader which has only 1 outgoing edge to the loop header) or loop exit (similarly every loop has an exit block with only 1 incoming edge). ...

As the first blog in the series let’s keep it short and informative. Introduction If you work on a large scale project like compilers you will always come across the need to have multiple versions as a part of your development arsenal. One might be the latest one(in sync with upstream), one might be for a brand new feature you are working on and the other might be some crash issue that you are investigating. ...