December 2005 - Posts

• Another Math Puzzler

  I'll pose an easy one this time. Everyone should be familiar with the Fibonacci sequence defined recursively as F(n) = F(n-1) + F(n-2). Fibonacci is often one of the first examples of recursion one learns, and also one of the first examples of how recursion Read More... Posted Wednesday, December 21, 2005 12:54 PM by ReuvenLax | 0 Comments Filed under: Mathematics

• Finding Global Expressions: 2

  In the last post, we discussed a method to find common subexpression on the entire control-flow graph using partitioning. Today, we're going to talk about another classic way of accomplishing this goal using data-flow analysis. Then I think I'm going Read More... Posted Tuesday, December 20, 2005 7:25 PM by ReuvenLax | 0 Comments Filed under: Algorithms, Programming, Computer Science

• Finding Expressions Globally

  In the last few posts, we examined ways of eliminating redundant expressions in basic blocks and in tree-structures of basic blocks. We examined the tree of extended basic blocks and then enhanced this algorithm to run over the immediate-dominator tree Read More... Posted Monday, December 19, 2005 1:23 PM by ReuvenLax | 0 Comments Filed under: Algorithms, Programming, Computer Science

• Extending Value Numbering 2

  In the last post we extended the value-numbering algorithm to extended basic blocks. This is generally a win, but still leaves us wanting a bit more. Consider the following contrived program: x = y + z B1 if x == 0 a = y + z B2 else b = y + z B3 c = y Read More... Posted Thursday, December 15, 2005 7:28 PM by ReuvenLax | 1 Comments Filed under: Algorithms, Programming, Computer Science

• Extending Value Numbering

  Yesterday's post dealt with optimizing a single basic block. Most useful progams contain some control flow however, so in the next few posts we'll explore extending the algorithm to larger regions. The set of all basic block in a procedure form a graph, Read More... Posted Thursday, December 15, 2005 9:27 AM by ReuvenLax | 0 Comments Filed under: Algorithms, Programming, Computer Science

• Some Nifty Compiler Tricks

  Despite my having worked on Windows Storage for the past four years, one of my main interests has always been compilers. I had the good fortune to go to school at Rice University, a school that had one of the strongest compiler programs in the country. Read More... Posted Wednesday, December 14, 2005 5:23 PM by ReuvenLax | 2 Comments Filed under: Algorithms, Programming, Computer Science

• Tricks of The Trade: How to use old tricks in new ways

  At some point in your programming career, you've probably written a growable list. It might've been to implement a dynamic array or it might've been for a hash table, but I bet you've written one. After all, while you can usually find a library that has Read More... Posted Wednesday, December 14, 2005 12:30 PM by ReuvenLax | 1 Comments Filed under: Algorithms, Programming, Computer Science