{"id":286,"date":"2018-07-20T11:15:46","date_gmt":"2018-07-20T11:15:46","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=286"},"modified":"2018-07-20T11:15:46","modified_gmt":"2018-07-20T11:15:46","slug":"code-optimization","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/code-optimization\/","title":{"rendered":"Code Optimization"},"content":{"raw":"<p style=\"text-align: justify\">In this module, we will understand the function preserving transformations and loop optimization techniques that would be carried out as a means of code optimization<\/p>\r\n&nbsp;\r\n\r\n<strong>34.1 Optimization<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Function preserving transformations and loop optimization are the major optimizations that are carried out in every basic block. We considered the code for quick sort as an example to explain the optimizations that can be carried out in the previous module. The high level code is converted to three-address code and this will later represent as a control flow graph. For convenience, the control flow graph of quick sort program is given in figure 34.1.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-287 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169.png\" alt=\"\" width=\"677\" height=\"627\" \/>\r\n\r\n<img class=\"size-full wp-image-288 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170.png\" alt=\"\" width=\"654\" height=\"222\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">From figure 34.1, blocks B5 and B6 alone are given in the above table for convenience as our focus will be these two blocks for applying function preserving transformation. We will discuss in detail the function preserving transformations and how this could be applied to our example in subsequent sections.<\/p>\r\n&nbsp;\r\n\r\n<strong>34.2 Function Preserving Transformation<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe following are some of the function preserving transformation.\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Common Sub-expression Elimination\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Copy Propagation\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Dead-code elimination\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Constant Folding\r\n\r\nThe order in which one applies these transformations is also important for any particular block as an incorrect order may result in redundant code.\r\n\r\n&nbsp;\r\n\r\n<strong>34.2.1 Common Sub-expression Elimination (CSE)<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Common sub-expressions are so very frequently occurring in any scenario of code. E is called a common sub-expression if E was previously computed and the values of variables in E have not changed since the previous computation and this E is occurring at a particular point of time. Identifying E is easier with DAG as a basic block and this is identified as the node that have multiple tags associated<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Consider the quick sort example and let us consider the basic block B5. The temporary variables t6 and t7 computes the expression 4 * i. Similarly, the temporary variables t8 and t10 computes the expression 4 * j between the computation of t6 and t7 and the value of the variable \u2018i' has not<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n<p style=\"text-align: justify\">changed. So is the case between the expressions t8 and t10 for the variable \u2018j\u2019. Thus we can say, t7 has a common expression with t6 and t10 have common sub-expression with t8. We will see how to eliminate this.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">To eliminate common sub-expression, in the second occurrence of the common sub-expression, replace the expression with the first computed expression\u2019s variable. So, in this example for the block B5, t6 has the result of the expression 4 * i and hence, wherever 4*i occurs within a basic block, we replace it with t6. So, is the case for 4 * j where we replace with t8. This common sub-expression is referred to as local common sub-expression as we are analyzing within a basic block. On the other hand, if this is carried out across basic blocks, the optimization is referred to global common sub-expression. A particular value of \u2018i' and \u2018j\u2019 both enters the basics 5 and 6 respectively. Thus the same value of \u2018i' and \u2018j\u2019 is being used by both these blocks and hence common sub-expression could be incorporated across these blocks also. If we try to trace back, 4 * i computed in block B2 and 4 * j computed in B3 hasn\u2019t changed till B5 or B6. Hence, their values could be reused. So is the value of a[t2] and a[t4]. Table 34.1 explains the local and global common sub-expression elimination of the basic blocks B5 and B6<\/p>\r\n&nbsp;\r\n\r\n<img class=\" wp-image-289 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171.png\" alt=\"\" width=\"663\" height=\"714\" \/>\r\n\r\n<strong>34.2.2 Copy Propagation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Assignments of the form f:= g denotes a copy statement. Copy statements, could be available in the code itself. In addition elimination of common sub-expression leads to creation of copy. Elimination of copy statements is called copy propagation as the assignments f:= g, can be transformed by using \u201cg\u201d for \u201cf\u201d. After that, we remove the assignment statement f := g. In the table 34.1, we had removed the assignments statements which are copies, like t7:= t6, t10:= t8, etc and have used t6 in place of t7 and t8 in place of t10. Copy propagation could be carried out only if the values of these variables haven\u2019t changed during the sequence of statements.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Consider the following example flow graph, where copy propagation could be carefully carried out. Copies are also introduced due to CSE and this also needs to be eliminated. Consider the following figure 34.2 (a)<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-290 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172.png\" alt=\"\" width=\"738\" height=\"388\" \/>\r\n<p style=\"text-align: justify\">We could use a temporary variable and now the CSE is independent of the variables\u2018d\u2019 and \u2018e\u2019. Applying copy propagation to the basic blocks 5 and 6 will result in the following optimized code.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-291 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173.png\" alt=\"\" width=\"687\" height=\"250\" \/>\r\n<div>\r\n\r\n<strong>34.2.3 Dead-code elimination<\/strong>\r\n\r\n&nbsp;\r\n\r\nA variable is live at a point where its value can be used subsequently, else dead at that point. Due to analyzing the copy statements, the statement\r\n\r\n&nbsp;\r\n\r\nx := t3\r\n\r\n&nbsp;\r\n\r\nis dead, because \u2018x\u2019 is not going to be used as it would be replaced by t3. These statements are removed from the three-address code.\r\n\r\n&nbsp;\r\n\r\n<strong>34.2.4 Constant Folding<\/strong>\r\n\r\n&nbsp;\r\n\r\nDuring compile time deducing that a value is constant and using the constant instead of the variable is known as constant folding. Identification of constant folding would also lead to dead code. Consider the following example involving two statements:\r\n\r\n&nbsp;\r\n\r\na := 1\r\n\r\nc := a+ b\r\n\r\n&nbsp;\r\n\r\nHere, \u2018a\u2019 has the value \u20181\u2019 and hence therefore a constant and the expressions that uses \u2018a\u2019 could be replaced with \u20181\u2019. Thus the instructions get changed as follows:\r\n\r\n&nbsp;\r\n\r\na:= 1\r\n\r\n&nbsp;\r\n\r\nc := 1 + b\r\n\r\nAfter applying constant folding there is no use for the statement a: = 1 and hence need to be eliminated as dead code and the final code corresponds to the one statement \u201cc : = 1 + b\u201d\r\n\r\n&nbsp;\r\n\r\n<strong>34.3 DAG for optimization <\/strong>The directed acyclic graph (DAG) as discussed in the previous modules could be used for optimization. One simp le optimization is identification of common sub-expressions. Consider the following sequence of statements\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\na := b+c\r\n<ul>\r\n \t<li>b := a-d<\/li>\r\n \t<li>c := b+c<\/li>\r\n \t<li>d := a - d<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nThe DAG for the same is given in figure 34.3.\r\n\r\n<img class=\"size-full wp-image-292 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174.png\" alt=\"\" width=\"556\" height=\"275\" \/>\r\n<div>\r\n\r\n<strong>common sub-expression<\/strong>.\r\n\r\n&nbsp;\r\n\r\nAlgebraic simplifications are typically applied using DAG as a means of optimization. Algebraic identities are used to convert multiplication to addition, exponentiation to multiplication, etc. Multiplicative identity and additive identity are also applied to generate optimized code. For example, the following identities are used:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x + 0 = 0 + x = x\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x \u2013 0 = x\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x * 1 = 1 * x = x\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x \/ 1 = x\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x ** 2 = x * x\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x * 2 = x + x\r\n\r\n&nbsp;\r\n\r\nThese optimizations are applied either in the basic block or DAG before applying other optimizations.\r\n\r\n&nbsp;\r\n\r\n<strong>34.4 Loop Optimization<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Running time of a program may be improved if the number of instructions in the inner loop is reduced. Outer loops could have more instructions which we are fine with it. There are three\u00a0\u00a0<span style=\"font-size: 1em;text-align: initial\">types of optimizations that are possible with loops: Code motion, induction variable elimination and reduction in strength.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>34.4.1 Code motion<\/strong>\r\n\r\n&nbsp;\r\n\r\nIf a particular code is not in motion, then we may not have to re-compute this code repeatedly.\u00a0 For example, consider the following piece of code:\r\n\r\n&nbsp;\r\n\r\nwhile (i &lt;=\u00a0 limit - 2)\r\n\r\n{\r\n\r\n&nbsp;\r\n\r\n}\r\n\r\nL1:\r\n\r\nt1 = limit \u2013 2\r\n\r\nif (i &gt; t1) goto L2\r\n\r\nbody of loop\r\n\r\n&nbsp;\r\n\r\ngoto L1\r\n\r\nL2:\r\n<p style=\"text-align: justify\">The outside while() loop compares, whether the variab le \u2018i' is less than \u201climit-2\u201d and enters or exits the loop. After the exit of the loop, the value of the variable \u2018i' which is altered inside the<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">while() loop will be compared and correspondingly two branches are taken. The expression \u201climit-2\u201d will evaluate to the same value as the body of the while loop does not alter the variable \u201climit\u201d and hence this variable is non- motion variable. This expression is computed every time the while() loop is entered and hence could be avoided. The details after implementing code motion are given below:<\/p>\r\n&nbsp;\r\n\r\nt := limit - 2\r\n\r\nwhile (i &lt;= t)\r\n\r\nt1 = limit \u2013 2\r\n\r\nL1:\r\n\r\nif (i &gt; t1) goto L2\r\n\r\nbody of loop\r\n\r\ngoto L1\r\n\r\nL2:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before entering the while() loop, the expression \u201climit-2\u201d is computed and stored in a temporary variable, and the while() continues or exits by comparing this variable \u201ct\u201d with the value of \u201ci\"<\/p>\r\n&nbsp;\r\n\r\n<strong>34.4.2 Strength Reduction<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Typically induction Variables control loop iterations. Strength reduction involves replacing costlier computation with cheaper ones. Consider the figure 34.4 which are the parts of the basic blocks B2 \/ B3 of the CFG of figure 34.1. The computation 4*j gets executed every time the loop is entered. We could replace this computation of multiplication with just subtraction as the index<\/p>\r\n&nbsp;\r\n\r\nvariable \u2018j\u2019 gets decremented by \u201c1\u201d for all iterations. The procedure involves creating a new\u00a0 block above this basic block and declares the multiplication once. Subsequently, for the next\r\n\r\n<\/div>\r\n<img class=\"size-full wp-image-293 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175.png\" alt=\"\" width=\"702\" height=\"841\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Summary: <\/strong>In this module we discussed, basic function preserving transformations for implementing code optimizations. Algebraic transformations are also discussed to generate optimized code. Loop Optimization is very important to generate optimized code as loops increase or decrease the computational complexity of any program and the various loop optimizations are also discussed. In the next module, we will discuss more on loops to try out other possible optimizations that could be carried out.<\/p>","rendered":"<p style=\"text-align: justify\">In this module, we will understand the function preserving transformations and loop optimization techniques that would be carried out as a means of code optimization<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.1 Optimization<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Function preserving transformations and loop optimization are the major optimizations that are carried out in every basic block. We considered the code for quick sort as an example to explain the optimizations that can be carried out in the previous module. The high level code is converted to three-address code and this will later represent as a control flow graph. For convenience, the control flow graph of quick sort program is given in figure 34.1.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-287 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169.png\" alt=\"\" width=\"677\" height=\"627\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169.png 677w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169-300x278.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169-65x60.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169-225x208.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-169-350x324.png 350w\" sizes=\"auto, (max-width: 677px) 100vw, 677px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-288 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170.png\" alt=\"\" width=\"654\" height=\"222\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170.png 654w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170-300x102.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170-65x22.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170-225x76.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-170-350x119.png 350w\" sizes=\"auto, (max-width: 654px) 100vw, 654px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\">From figure 34.1, blocks B5 and B6 alone are given in the above table for convenience as our focus will be these two blocks for applying function preserving transformation. We will discuss in detail the function preserving transformations and how this could be applied to our example in subsequent sections.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.2 Function Preserving Transformation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The following are some of the function preserving transformation.<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Common Sub-expression Elimination<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Copy Propagation<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Dead-code elimination<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Constant Folding<\/p>\n<p>The order in which one applies these transformations is also important for any particular block as an incorrect order may result in redundant code.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.2.1 Common Sub-expression Elimination (CSE)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Common sub-expressions are so very frequently occurring in any scenario of code. E is called a common sub-expression if E was previously computed and the values of variables in E have not changed since the previous computation and this E is occurring at a particular point of time. Identifying E is easier with DAG as a basic block and this is identified as the node that have multiple tags associated<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Consider the quick sort example and let us consider the basic block B5. The temporary variables t6 and t7 computes the expression 4 * i. Similarly, the temporary variables t8 and t10 computes the expression 4 * j between the computation of t6 and t7 and the value of the variable \u2018i&#8217; has not<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">changed. So is the case between the expressions t8 and t10 for the variable \u2018j\u2019. Thus we can say, t7 has a common expression with t6 and t10 have common sub-expression with t8. We will see how to eliminate this.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To eliminate common sub-expression, in the second occurrence of the common sub-expression, replace the expression with the first computed expression\u2019s variable. So, in this example for the block B5, t6 has the result of the expression 4 * i and hence, wherever 4*i occurs within a basic block, we replace it with t6. So, is the case for 4 * j where we replace with t8. This common sub-expression is referred to as local common sub-expression as we are analyzing within a basic block. On the other hand, if this is carried out across basic blocks, the optimization is referred to global common sub-expression. A particular value of \u2018i&#8217; and \u2018j\u2019 both enters the basics 5 and 6 respectively. Thus the same value of \u2018i&#8217; and \u2018j\u2019 is being used by both these blocks and hence common sub-expression could be incorporated across these blocks also. If we try to trace back, 4 * i computed in block B2 and 4 * j computed in B3 hasn\u2019t changed till B5 or B6. Hence, their values could be reused. So is the value of a[t2] and a[t4]. Table 34.1 explains the local and global common sub-expression elimination of the basic blocks B5 and B6<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-289 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171.png\" alt=\"\" width=\"663\" height=\"714\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171.png 663w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171-279x300.png 279w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171-65x70.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171-225x242.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-171-350x377.png 350w\" sizes=\"auto, (max-width: 663px) 100vw, 663px\" \/><\/p>\n<p><strong>34.2.2 Copy Propagation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Assignments of the form f:= g denotes a copy statement. Copy statements, could be available in the code itself. In addition elimination of common sub-expression leads to creation of copy. Elimination of copy statements is called copy propagation as the assignments f:= g, can be transformed by using \u201cg\u201d for \u201cf\u201d. After that, we remove the assignment statement f := g. In the table 34.1, we had removed the assignments statements which are copies, like t7:= t6, t10:= t8, etc and have used t6 in place of t7 and t8 in place of t10. Copy propagation could be carried out only if the values of these variables haven\u2019t changed during the sequence of statements.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Consider the following example flow graph, where copy propagation could be carefully carried out. Copies are also introduced due to CSE and this also needs to be eliminated. Consider the following figure 34.2 (a)<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-290 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172.png\" alt=\"\" width=\"738\" height=\"388\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172.png 738w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172-300x158.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172-65x34.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172-225x118.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-172-350x184.png 350w\" sizes=\"auto, (max-width: 738px) 100vw, 738px\" \/><\/p>\n<p style=\"text-align: justify\">We could use a temporary variable and now the CSE is independent of the variables\u2018d\u2019 and \u2018e\u2019. Applying copy propagation to the basic blocks 5 and 6 will result in the following optimized code.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-291 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173.png\" alt=\"\" width=\"687\" height=\"250\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173.png 687w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173-300x109.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173-65x24.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173-225x82.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-173-350x127.png 350w\" sizes=\"auto, (max-width: 687px) 100vw, 687px\" \/><\/p>\n<div>\n<p><strong>34.2.3 Dead-code elimination<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>A variable is live at a point where its value can be used subsequently, else dead at that point. Due to analyzing the copy statements, the statement<\/p>\n<p>&nbsp;<\/p>\n<p>x := t3<\/p>\n<p>&nbsp;<\/p>\n<p>is dead, because \u2018x\u2019 is not going to be used as it would be replaced by t3. These statements are removed from the three-address code.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.2.4 Constant Folding<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>During compile time deducing that a value is constant and using the constant instead of the variable is known as constant folding. Identification of constant folding would also lead to dead code. Consider the following example involving two statements:<\/p>\n<p>&nbsp;<\/p>\n<p>a := 1<\/p>\n<p>c := a+ b<\/p>\n<p>&nbsp;<\/p>\n<p>Here, \u2018a\u2019 has the value \u20181\u2019 and hence therefore a constant and the expressions that uses \u2018a\u2019 could be replaced with \u20181\u2019. Thus the instructions get changed as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>a:= 1<\/p>\n<p>&nbsp;<\/p>\n<p>c := 1 + b<\/p>\n<p>After applying constant folding there is no use for the statement a: = 1 and hence need to be eliminated as dead code and the final code corresponds to the one statement \u201cc : = 1 + b\u201d<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.3 DAG for optimization <\/strong>The directed acyclic graph (DAG) as discussed in the previous modules could be used for optimization. One simp le optimization is identification of common sub-expressions. Consider the following sequence of statements<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>a := b+c<\/p>\n<ul>\n<li>b := a-d<\/li>\n<li>c := b+c<\/li>\n<li>d := a &#8211; d<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>The DAG for the same is given in figure 34.3.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-292 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174.png\" alt=\"\" width=\"556\" height=\"275\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174.png 556w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174-300x148.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174-225x111.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-174-350x173.png 350w\" sizes=\"auto, (max-width: 556px) 100vw, 556px\" \/><\/p>\n<div>\n<p><strong>common sub-expression<\/strong>.<\/p>\n<p>&nbsp;<\/p>\n<p>Algebraic simplifications are typically applied using DAG as a means of optimization. Algebraic identities are used to convert multiplication to addition, exponentiation to multiplication, etc. Multiplicative identity and additive identity are also applied to generate optimized code. For example, the following identities are used:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x + 0 = 0 + x = x<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x \u2013 0 = x<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x * 1 = 1 * x = x<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x \/ 1 = x<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x ** 2 = x * x<\/p>\n<p>\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 x * 2 = x + x<\/p>\n<p>&nbsp;<\/p>\n<p>These optimizations are applied either in the basic block or DAG before applying other optimizations.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.4 Loop Optimization<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Running time of a program may be improved if the number of instructions in the inner loop is reduced. Outer loops could have more instructions which we are fine with it. There are three\u00a0\u00a0<span style=\"font-size: 1em;text-align: initial\">types of optimizations that are possible with loops: Code motion, induction variable elimination and reduction in strength.<\/span><\/p>\n<\/div>\n<div>\n<p><strong>34.4.1 Code motion<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>If a particular code is not in motion, then we may not have to re-compute this code repeatedly.\u00a0 For example, consider the following piece of code:<\/p>\n<p>&nbsp;<\/p>\n<p>while (i &lt;=\u00a0 limit &#8211; 2)<\/p>\n<p>{<\/p>\n<p>&nbsp;<\/p>\n<p>}<\/p>\n<p>L1:<\/p>\n<p>t1 = limit \u2013 2<\/p>\n<p>if (i &gt; t1) goto L2<\/p>\n<p>body of loop<\/p>\n<p>&nbsp;<\/p>\n<p>goto L1<\/p>\n<p>L2:<\/p>\n<p style=\"text-align: justify\">The outside while() loop compares, whether the variab le \u2018i&#8217; is less than \u201climit-2\u201d and enters or exits the loop. After the exit of the loop, the value of the variable \u2018i&#8217; which is altered inside the<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">while() loop will be compared and correspondingly two branches are taken. The expression \u201climit-2\u201d will evaluate to the same value as the body of the while loop does not alter the variable \u201climit\u201d and hence this variable is non- motion variable. This expression is computed every time the while() loop is entered and hence could be avoided. The details after implementing code motion are given below:<\/p>\n<p>&nbsp;<\/p>\n<p>t := limit &#8211; 2<\/p>\n<p>while (i &lt;= t)<\/p>\n<p>t1 = limit \u2013 2<\/p>\n<p>L1:<\/p>\n<p>if (i &gt; t1) goto L2<\/p>\n<p>body of loop<\/p>\n<p>goto L1<\/p>\n<p>L2:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before entering the while() loop, the expression \u201climit-2\u201d is computed and stored in a temporary variable, and the while() continues or exits by comparing this variable \u201ct\u201d with the value of \u201ci&#8221;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>34.4.2 Strength Reduction<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Typically induction Variables control loop iterations. Strength reduction involves replacing costlier computation with cheaper ones. Consider the figure 34.4 which are the parts of the basic blocks B2 \/ B3 of the CFG of figure 34.1. The computation 4*j gets executed every time the loop is entered. We could replace this computation of multiplication with just subtraction as the index<\/p>\n<p>&nbsp;<\/p>\n<p>variable \u2018j\u2019 gets decremented by \u201c1\u201d for all iterations. The procedure involves creating a new\u00a0 block above this basic block and declares the multiplication once. Subsequently, for the next<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-293 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175.png\" alt=\"\" width=\"702\" height=\"841\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175.png 702w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175-250x300.png 250w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175-65x78.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175-225x270.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-175-350x419.png 350w\" sizes=\"auto, (max-width: 702px) 100vw, 702px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Summary: <\/strong>In this module we discussed, basic function preserving transformations for implementing code optimizations. Algebraic transformations are also discussed to generate optimized code. Loop Optimization is very important to generate optimized code as loops increase or decrease the computational complexity of any program and the various loop optimizations are also discussed. In the next module, we will discuss more on loops to try out other possible optimizations that could be carried out.<\/p>\n","protected":false},"author":4,"menu_order":34,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-rajeswari-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-286","chapter","type-chapter","status-publish","hentry","contributor-dr-rajeswari-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/286","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":1,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/286\/revisions"}],"predecessor-version":[{"id":294,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/286\/revisions\/294"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/286\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=286"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=286"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=286"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=286"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}