DESKTOP

# Algorithms for Compiler Design:

7/24/2010 8:05:08 PM
##### 10.6 ELIMINATING GLOBAL COMMON SUBEXPRESSIONS 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. IN(b1) = φ OUT(b1) = GEN(b1); for (i=2; i <= n; i++) ```{ IN(b) = U OUT(b) = U - GEN(b)}``` flag = true while (flag) do ```{flag = falsefor (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: Find all definitions reaching up to the s statement block that have y op z on the right. Create a new temp. Replace each statement U = y op z found in step 1 by: Replace the statement x = y op z in block by x = temp. var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>");
 Other

 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
 -  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