Algorithms for Compiler Design:

7/24/2010 8:05:08 PM

Global common subexpressions are expressions that compute the same value but in different basic blocks. To detect such expressions, we need to compute available expressions.

Available Expressions

An expression x op y is available at a point p if every path from the initial node of the flow graph reaching to p evaluates x op y, and if after the last such evaluation and prior to reaching p there are no subsequent assignments to x or y. To eliminate global common subexpressions, we need to compute the set of all the expressions available at the point just before the start of every block. This requires computing the set all the expressions available at a point just after the end of every block. We call these sets IN(b) and OUT(b), respectively. The computation of IN(b) and OUT(b) requires computing the set of all expressions generated by the basic block and the set of all expressions killed by the basic block, respectively:

  • A block kills an expression x op y if it assigns to x or y and if does not subsequently recompute as op y.

  • A block generates an expression x op y if it evaluates x op y and subsequently does not redefine x or y.

To compute the available expressions, we solve the following equations:

Here, also, we obtain the smallest solution.

The algorithm for computing the smallest IN(b) and OUT(b) is given below, where b1 is the initial block, and U is a "universal" set of all expressions appearing on the right of one or more statements of the program.

  1. IN(b1) = φ
    OUT(b1) = GEN(b1);

  2. for (i=2; i <= n; i++)

    IN(b) = U OUT(b) = U - GEN(b)
  3. flag = true

  4. while (flag) do

    flag = false
    for (i=2; i <= n; i++)
    { INnew(bi) = Φ for each predecessor p of bi INnew(bi) = INnew(bi) OUT(p)
    if INnew(bi) IN(bi) then

    flag = true
    IN(bi) = INnew(bi)
    OUT(bi) = IN(bi) - KILL(bi) GEN(bi)

After computing IN(b) and OUT(b), eliminating the global common subexpressions is done as follows. For every statement s of the form x = y op z such that y op z is available at the beginning of the block containing s, and neither y nor z is defined prior to the statement x = y op z in that block, do:

  1. Find all definitions reaching up to the s statement block that have y op z on the right.

  2. Create a new temp.

  3. Replace each statement U = y op z found in step 1 by:

  4. Replace the statement x = y op z in block by x = temp.

Most View
Windows Vista : Build Your Network (part 7) - Troubleshoot Network Connections, Test an IP Address
Android Application Development : Rolling Your Own Widgets (part 3) - Canvas Drawing - Drawing text, Matrix transformations
Compact Liquid Cooling System Roundup – Front Runners (Part 2)
Smart, But Not Pricey : LG Optimus L7, Nokia Lumia 610, Sony Xperia U, Micromax A90S, BlackBerry Curve 9320, Nokia Lumia 710
AMD A10-6800 - AMD Accelerated Processors for Desktop PCs
Microsoft Lync Server 2010 : Microsoft Communicator Client for Macintosh - Audio/Video Calls and Conferencing
The Best Deals On Cool-Running Components And Passive Cooling Solutions
Are Your Passwords Safe? (Part 1)
Take Encoding Up A Level (Part 1)
Toshiba Satellite Pro L830 10J – An Affordable 13.3in Laptop
Top 10
Olympus Stylus 1 - The Pied Piper (Part 3)
Olympus Stylus 1 - The Pied Piper (Part 2)
Olympus Stylus 1 - The Pied Piper (Part 1)
Olympus Pen E-PL5 - April 2014
Nikon 1 J3 – April 2014
New Camera For You – Nikon 1 AW1
Phase One IQ250, Hasselblad H5D-50c - Medium-format Media Systems: Bigger Gets Better
Kaveri APU - AMD A10-7700K
Fujifilm X-M1 – Review April 2014
Fujifilm X-T1 : Good To Go