{"id":324,"date":"2018-07-20T11:52:08","date_gmt":"2018-07-20T11:52:08","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=324"},"modified":"2018-07-20T11:56:55","modified_gmt":"2018-07-20T11:56:55","slug":"code-improving-transformations","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/code-improving-transformations\/","title":{"rendered":"Code Improving Transformations"},"content":{"raw":"

We will start this module by looking at use-define chains and define-use chains. We shall also discuss the algorithms for global common sub-expression, copy propagation and loop optimizations.<\/p>\r\n \r\n\r\n38.1 Define-Use and Use-Define (DU\/UD) Chains<\/strong>\r\n\r\n \r\n

After understanding the various algorithms to identify reaching definitions, available expressions and live- variable analysis in the previous module, we will discuss yet another procedure that is helpful for optimization in this module using define-use and use-define chains. The define-use (du) and use-define (ud) chains are convenient way to access\/use reaching definition information. Def-Use chains (DU chains) gives information of the possible consumers of the definition produced for a given a def.<\/strong> Use-Def chains (UD chains), accepts a use<\/strong>, and identifies all the possible producers of the definition consumed. Consider the example given in figure 38.1 having a control flow as depicted with variables r1 to r8.<\/p>\r\n \r\n\r\n\"\"\r\n

\r\n\r\nBased on this UD and DU chains, we can identify Next-use information, available expressions and reaching definitions information for carrying out function preserving transformations.\r\n\r\n \r\n\r\n38.2 Global Common Sub-expression elimination<\/strong>\r\n\r\n \r\n\r\nThe Available expression algorithm discussed in the previous module computes and informs whether an expression is common at point \u2018p\u2019. After identifying this, we need to get rid of the common sub-expression, both locally and globally. Algorithm 38.1 briefs on the procedure for global common sub-expression elimination.\r\n\r\n \r\n\r\nAlgorithm 38.1\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A flow graph with available expression information\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: A revised flow graph\r\n\r\n \r\n\r\nEliminate_Common_sub_expression()\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\nFor every statement\u2018s\u2019 of the form x:=y+z if y+z is available at the beginning of \u2018s\u2019 do the following\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Search backward from \u2018s\u2019 the expression \u2018y+z\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Create a new variable \u2018u\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace each statement w:=y+z found in the previous step by\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 u := y+z\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 w:= u\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace statement \u2018s\u2019 by x := u\r\n\r\n \r\n\r\n}\r\n\r\n<\/div>\r\n
\r\n\r\nObservations of the algorithm<\/strong>: Searching for \u2018y+z\u2019 can be done as a data-flow analysis problem. The replacement need not be optimized as it could result in copy statements. This algorithm does not handle the transitive nature of common sub-expressions. Consider the following two statements:\r\n\r\n<\/div>\r\n
\r\n\r\n\u2013\r\n\r\na := x+y\u00a0 \u00a0 \u00a0vs\u00a0 \u00a0 c := x+y\r\n\r\n<\/div>\r\n
\r\n\r\n\u2013\r\n\r\nb := a*z\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 d := c*z\r\n\r\n<\/div>\r\n \r\n\r\nIn the above set of statements, the value of \u2018b\u2019 and\u2018d\u2019 are also essentially same and the above algorithm does not handle this situation. Consider the example of figure 38.2, to apply the common sub-expression elimination algorithm.\r\n\r\n\"\"\r\n\r\n38.3 Copy Propagation<\/strong>\r\n\r\n \r\n\r\nAs we discussed in the previous module, copies gets generated due to elimination of common sub-expression. Consider the following statement \u2018S\u2019 that assigns the variable,\r\n
    \r\n \t
  • S: x:= y<\/li>\r\n<\/ul>\r\n

    \u00a0 After this assignment, the value of \u2018x\u2019 and \u2018y\u2019 will be exactly identical. So, we could get rid of variable \u2018x\u2019 and use \u2018y\u2019 in place of \u2018x\u2019. To carry out this, we initially determine where the value of \u2018x\u2019 is used and substitute \u2018y\u2019 in place of \u2018x\u2019 where \u2018u\u2019 is a statement that uses \u2018y\u2019. We need to ensure that statement \u2018s\u2019 must be the only definition of \u2018x\u2019 reaching \u2018u\u2019 and this could be checked using UD chains. We also need to ensure, that on every path from\u2018s\u2019 to \u2018u\u2019, there are no assignments to \u2018y\u2019 which could be looked upon as a new data-flow analysis problem.<\/p>\r\n \r\n

    The procedure that is discussed to eliminate copy p ropagation can be looked upon as forward copy propagation procedure which looks at the RHS of an assignment statement. However, this does not consider the chain of dependencies and hence create dead code. As an example for copy propagation, figure 38.4 is used.<\/p>\r\n \r\n\r\n\"\"\r\n

    As given in given in figure 38.4, r1 and r2 have the same values. So, we replace r2 in place of r1. After performing copy propagation, the statement r1 := r2 remains as a dead code.\u00a0 The following are some of the data flow equations that could be defined and used to identify copy propagation. Here, c_gen[] and c_kill[] indicates the copies generated and killed in a basic block. Thus<\/p>\r\n \r\n

      \r\n \t
    • out[B] = c_gen[B] U (in[B] \u2013 c_kill[B]) \u2013 Similar to reaching definitions<\/li>\r\n \t
    • in[B] = \u2229 out[P] where P is a predecessor block- Intersection of all the predecessor\u2019s output is computed as the in[] of all but the first block.<\/li>\r\n \t
    • in[B1] = \u03a6 where B1 is the initial block<\/li>\r\n<\/ul>\r\n

      The algorithm is similar to available expressions algorithm and the computation are also same. Consider the example given in figure 38.5 to identify copy propagation.<\/p>\r\n \r\n\r\n\"\"\r\n

      \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Determine whether for every use of \u2018x\u2019, \u2018s\u2019 is in c_in[B] where B is the block for this use and no definitions of \u2018x\u2019 or \u2018y\u2019 occur prior to this use\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If the statement meets this condition, remove \u2018s\u2019 and replace all uses of \u2018x\u2019 by \u2018y\u2019\r\n\r\n}\r\n\r\nThus eliminating copy propagation would result in dead code.\r\n\r\n \r\n\r\n38.4 Constant Propagation<\/strong>\r\n\r\n \r\n

      Another important optimization to be considered is constant propagation. Similar to copy propagation, if a variable is assigned a constant and if the variable is used in subsequent expression, it can be replaced by the constant thus making the assignment of the constant to the variable as dead code. Consider the forward propagation of assignment of the form<\/p>\r\n \r\n\r\nd:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 rx := L where L is literal and rx is a variable.\r\n\r\n \r\n

      Constant propagation involves replacement of \u201crx\u201d with \u201cL\u201d wherever possible, provided the definition\u2019s\u2019 is available at point of replacement.<\/p>\r\n \r\n\r\n38.5 Unreachable Code Elimination<\/strong>\r\n\r\n \r\n

      Copy propagation and constant folding could result in dead code. In addition, as discussed in peep hole optimization, some sections of code may be unreachable. This unreachable code need to be eliminated. To eliminate this, algorithm 38.3 is used.<\/p>\r\n \r\n\r\nAlgorithm 38.3 \u2013 Unreachable code elimination.\r\n\r\n \r\n\r\nInput: Flow graph\r\n\r\nOutput: Revised flow graph\r\n\r\n \r\n\r\nEliminate_Notreachable_code\r\n\r\n{\r\n\r\n \r\n\r\nMark initial BB visited\r\n\r\nto_visit = initial BB\r\n\r\nwhile (to_visit not empty)\r\n\r\ncurrent = to_visit.pop()\r\n\r\nfor each successor block of current\r\n\r\nMark successor as visited;\r\n\r\nto_visit += successor\r\n\r\nendfor\r\n\r\nendwhile\r\n\r\nEliminate all unvisited blocks\r\n\r\n}\r\n\r\n<\/div>\r\nThe algorithm carries out a depth- first search and tries to identify blocks that are useful. After identifying useful blocks, the other blocks available in the flow graph are identified as not useful\r\n\r\n\"\"\r\n

      \r\n

      Consider figure 38.6, which involves 5 basic blocks. As can be seen, a depth- first search from the entry point would include bb1, then bb4 followed by bb2 and then bb5. The block bb3 is never to be reached and hence could be eliminated.<\/p>\r\n \r\n\r\n38.6 Loop invariant computation<\/strong>\r\n\r\n \r\n

      The three major loop optimization techniques are strength reduction, code motion and induction variable elimination. Code motion involves eliminating loop invariant computation. UD-chains could be used to find out values that do not change as long as control stays within the loop. Loop has at least one way to get back to the header from any block in the loop. If x:= y+z is at a position in the loop and all possible definitions of \u2018y\u2019 and \u2018z\u2019 are outside the loop then y+z is loop invariant. Algorithm 38.4 discusses the loop invariant computation.<\/p>\r\n \r\n\r\nAlgorithm 38.4 \u2013 Loop invariant computation<\/strong>\r\n\r\n \r\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L consisting of a set of basic blocks having three address statements. The set of three-address statements that compute the same value each time executed, from the time control enters the loop L until control leaves L<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: Optimized loops.\r\n\r\n \r\n\r\nCompute_Loop_invariance()\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Mark the statements whose operands are all either constants or have all reaching definitions outside L as \u2018invariant\u2019\r\n\r\n<\/div>\r\n

      \r\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Repeat\u00a0 the\u00a0 following\u00a0 step\u00a0 until\u00a0 at\u00a0 some\u00a0 repetition\u00a0 no\u00a0 new\u00a0 statements\u00a0 are\u00a0 marked \u2018invariant\u2019<\/p>\r\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Mark \u2018invariant\u2019 all those statements not previously so marked all of whose operands are either constant or having definitions reaching outside \u2018L\u2019 or have only one reaching definition which is marked invariant.<\/p>\r\n \r\n\r\n}\r\n\r\n \r\n\r\n38.7 Performing Code motion<\/strong>\r\n\r\n \r\n\r\nAfter identifying the loop invariant statements, we have to eliminate repeated computation of the statements whose results are not going to change. The statements which are identified as loop invariant are moved to the pre-header of the loop. In order to apply code motion, certain conditions need to be checked and applied. Consider a statement, \u2018s\u2019 x: = y+z. The following are the conditions that need to be checked and applied.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Block containing a statement \u2018s\u2019 must dominate all exit nodes of the loop, which is essentially a successor node that is not in the loop\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No other statement in the loop assigns to \u2018x\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No use of \u2018x\u2019 in the loop is reached by any definition of \u2018x\u2019 other than \u2018s\u2019.\r\n\r\n \r\n\r\nAlgorithm 38.5 implements code motion.\r\n\r\n \r\n\r\nAlgorithm 38.5 \u2013 Code motion.<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: a loop L with ud-chain information and dominator information\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a revised loop with a pre-header and some statements moved to the pre-header (if any)\r\n\r\n \r\n\r\nIdentify_Eliminate_Codemotion\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Identify the loop invariant statements defining \u2018x\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 For each statement \u2018s\u2019 defining \u2018x\u2019 find\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 That it is in a block that dominates all exits of L\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 That \u2018x\u2019 is not defined elsewhere in L\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 All uses in L of x can only be reached using statement \u2018s\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Move, in the order found by loop invariant algorithm, each statement \u2018s\u2019 to a newly created pre-header\r\n\r\n}\r\n\r\n<\/div>\r\n \r\n\r\nCode motion sometime results in some illegal and incorrect situations. Consider the figure 38.7 where the available flow graph is optimized.\r\n\r\n\"\"\r\n

      In figure 38.7, there is a loop from B2 \u2013 B3 \u2013 B4 \u2013 B2. Thus there is an assignment to the variable \u2018i' to the value \u20182\u2019. As per the algorithm, this could be identified as loop invariant computation and could be moved to the pre-header and contributing to block B6. However, this is incorrect as the value of \u2018i' gets assigned to \u20182\u2019 if this path through B3 is followed. If an alternate path that does not go through B3 is followed the value of \u2018i' is \u20181\u2019 and hence we have performed an incorrect operation. So, for this flow graph there is no loop invariant computation.<\/p>\r\n \r\n

      Summary: <\/strong>In this module, we looked at the algorithms for eliminating common sub-expression and copy propagation. We also looked at algorithms to identify unreachable code and elimination of the same. Code motion and loop invariant computation algorithms are also discussed with an example. In the next module, we will discuss additional loop optimization techniques.<\/p>","rendered":"

      We will start this module by looking at use-define chains and define-use chains. We shall also discuss the algorithms for global common sub-expression, copy propagation and loop optimizations.<\/p>\n

       <\/p>\n

      38.1 Define-Use and Use-Define (DU\/UD) Chains<\/strong><\/p>\n

       <\/p>\n

      After understanding the various algorithms to identify reaching definitions, available expressions and live- variable analysis in the previous module, we will discuss yet another procedure that is helpful for optimization in this module using define-use and use-define chains. The define-use (du) and use-define (ud) chains are convenient way to access\/use reaching definition information. Def-Use chains (DU chains) gives information of the possible consumers of the definition produced for a given a def.<\/strong> Use-Def chains (UD chains), accepts a use<\/strong>, and identifies all the possible producers of the definition consumed. Consider the example given in figure 38.1 having a control flow as depicted with variables r1 to r8.<\/p>\n

       <\/p>\n

      \"\"<\/p>\n

      \n

      Based on this UD and DU chains, we can identify Next-use information, available expressions and reaching definitions information for carrying out function preserving transformations.<\/p>\n

       <\/p>\n

      38.2 Global Common Sub-expression elimination<\/strong><\/p>\n

       <\/p>\n

      The Available expression algorithm discussed in the previous module computes and informs whether an expression is common at point \u2018p\u2019. After identifying this, we need to get rid of the common sub-expression, both locally and globally. Algorithm 38.1 briefs on the procedure for global common sub-expression elimination.<\/p>\n

       <\/p>\n

      Algorithm 38.1<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A flow graph with available expression information<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: A revised flow graph<\/p>\n

       <\/p>\n

      Eliminate_Common_sub_expression()<\/p>\n

       <\/p>\n

      {<\/p>\n

       <\/p>\n

      For every statement\u2018s\u2019 of the form x:=y+z if y+z is available at the beginning of \u2018s\u2019 do the following<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Search backward from \u2018s\u2019 the expression \u2018y+z\u2019<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Create a new variable \u2018u\u2019<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace each statement w:=y+z found in the previous step by<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 u := y+z<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 w:= u<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace statement \u2018s\u2019 by x := u<\/p>\n

       <\/p>\n

      }<\/p>\n<\/div>\n

      \n

      Observations of the algorithm<\/strong>: Searching for \u2018y+z\u2019 can be done as a data-flow analysis problem. The replacement need not be optimized as it could result in copy statements. This algorithm does not handle the transitive nature of common sub-expressions. Consider the following two statements:<\/p>\n<\/div>\n

      \n

      \u2013<\/p>\n

      a := x+y\u00a0 \u00a0 \u00a0vs\u00a0 \u00a0 c := x+y<\/p>\n<\/div>\n

      \n

      \u2013<\/p>\n

      b := a*z\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 d := c*z<\/p>\n<\/div>\n

       <\/p>\n

      In the above set of statements, the value of \u2018b\u2019 and\u2018d\u2019 are also essentially same and the above algorithm does not handle this situation. Consider the example of figure 38.2, to apply the common sub-expression elimination algorithm.<\/p>\n

      \"\"<\/p>\n

      38.3 Copy Propagation<\/strong><\/p>\n

       <\/p>\n

      As we discussed in the previous module, copies gets generated due to elimination of common sub-expression. Consider the following statement \u2018S\u2019 that assigns the variable,<\/p>\n

        \n
      • S: x:= y<\/li>\n<\/ul>\n

        \u00a0 After this assignment, the value of \u2018x\u2019 and \u2018y\u2019 will be exactly identical. So, we could get rid of variable \u2018x\u2019 and use \u2018y\u2019 in place of \u2018x\u2019. To carry out this, we initially determine where the value of \u2018x\u2019 is used and substitute \u2018y\u2019 in place of \u2018x\u2019 where \u2018u\u2019 is a statement that uses \u2018y\u2019. We need to ensure that statement \u2018s\u2019 must be the only definition of \u2018x\u2019 reaching \u2018u\u2019 and this could be checked using UD chains. We also need to ensure, that on every path from\u2018s\u2019 to \u2018u\u2019, there are no assignments to \u2018y\u2019 which could be looked upon as a new data-flow analysis problem.<\/p>\n

         <\/p>\n

        The procedure that is discussed to eliminate copy p ropagation can be looked upon as forward copy propagation procedure which looks at the RHS of an assignment statement. However, this does not consider the chain of dependencies and hence create dead code. As an example for copy propagation, figure 38.4 is used.<\/p>\n

         <\/p>\n

        \"\"<\/p>\n

        As given in given in figure 38.4, r1 and r2 have the same values. So, we replace r2 in place of r1. After performing copy propagation, the statement r1 := r2 remains as a dead code.\u00a0 The following are some of the data flow equations that could be defined and used to identify copy propagation. Here, c_gen[] and c_kill[] indicates the copies generated and killed in a basic block. Thus<\/p>\n

         <\/p>\n

          \n
        • out[B] = c_gen[B] U (in[B] \u2013 c_kill[B]) \u2013 Similar to reaching definitions<\/li>\n
        • in[B] = \u2229 out[P] where P is a predecessor block- Intersection of all the predecessor\u2019s output is computed as the in[] of all but the first block.<\/li>\n
        • in[B1] = \u03a6 where B1 is the initial block<\/li>\n<\/ul>\n

          The algorithm is similar to available expressions algorithm and the computation are also same. Consider the example given in figure 38.5 to identify copy propagation.<\/p>\n

           <\/p>\n

          \"\"<\/p>\n

          \n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Determine whether for every use of \u2018x\u2019, \u2018s\u2019 is in c_in[B] where B is the block for this use and no definitions of \u2018x\u2019 or \u2018y\u2019 occur prior to this use<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If the statement meets this condition, remove \u2018s\u2019 and replace all uses of \u2018x\u2019 by \u2018y\u2019<\/p>\n

          }<\/p>\n

          Thus eliminating copy propagation would result in dead code.<\/p>\n

           <\/p>\n

          38.4 Constant Propagation<\/strong><\/p>\n

           <\/p>\n

          Another important optimization to be considered is constant propagation. Similar to copy propagation, if a variable is assigned a constant and if the variable is used in subsequent expression, it can be replaced by the constant thus making the assignment of the constant to the variable as dead code. Consider the forward propagation of assignment of the form<\/p>\n

           <\/p>\n

          d:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 rx := L where L is literal and rx is a variable.<\/p>\n

           <\/p>\n

          Constant propagation involves replacement of \u201crx\u201d with \u201cL\u201d wherever possible, provided the definition\u2019s\u2019 is available at point of replacement.<\/p>\n

           <\/p>\n

          38.5 Unreachable Code Elimination<\/strong><\/p>\n

           <\/p>\n

          Copy propagation and constant folding could result in dead code. In addition, as discussed in peep hole optimization, some sections of code may be unreachable. This unreachable code need to be eliminated. To eliminate this, algorithm 38.3 is used.<\/p>\n

           <\/p>\n

          Algorithm 38.3 \u2013 Unreachable code elimination.<\/p>\n

           <\/p>\n

          Input: Flow graph<\/p>\n

          Output: Revised flow graph<\/p>\n

           <\/p>\n

          Eliminate_Notreachable_code<\/p>\n

          {<\/p>\n

           <\/p>\n

          Mark initial BB visited<\/p>\n

          to_visit = initial BB<\/p>\n

          while (to_visit not empty)<\/p>\n

          current = to_visit.pop()<\/p>\n

          for each successor block of current<\/p>\n

          Mark successor as visited;<\/p>\n

          to_visit += successor<\/p>\n

          endfor<\/p>\n

          endwhile<\/p>\n

          Eliminate all unvisited blocks<\/p>\n

          }<\/p>\n<\/div>\n

          The algorithm carries out a depth- first search and tries to identify blocks that are useful. After identifying useful blocks, the other blocks available in the flow graph are identified as not useful<\/p>\n

          \"\"<\/p>\n

          \n

          Consider figure 38.6, which involves 5 basic blocks. As can be seen, a depth- first search from the entry point would include bb1, then bb4 followed by bb2 and then bb5. The block bb3 is never to be reached and hence could be eliminated.<\/p>\n

           <\/p>\n

          38.6 Loop invariant computation<\/strong><\/p>\n

           <\/p>\n

          The three major loop optimization techniques are strength reduction, code motion and induction variable elimination. Code motion involves eliminating loop invariant computation. UD-chains could be used to find out values that do not change as long as control stays within the loop. Loop has at least one way to get back to the header from any block in the loop. If x:= y+z is at a position in the loop and all possible definitions of \u2018y\u2019 and \u2018z\u2019 are outside the loop then y+z is loop invariant. Algorithm 38.4 discusses the loop invariant computation.<\/p>\n

           <\/p>\n

          Algorithm 38.4 \u2013 Loop invariant computation<\/strong><\/p>\n

           <\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L consisting of a set of basic blocks having three address statements. The set of three-address statements that compute the same value each time executed, from the time control enters the loop L until control leaves L<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: Optimized loops.<\/p>\n

           <\/p>\n

          Compute_Loop_invariance()<\/p>\n

           <\/p>\n

          {<\/p>\n

           <\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Mark the statements whose operands are all either constants or have all reaching definitions outside L as \u2018invariant\u2019<\/p>\n<\/div>\n

          \n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Repeat\u00a0 the\u00a0 following\u00a0 step\u00a0 until\u00a0 at\u00a0 some\u00a0 repetition\u00a0 no\u00a0 new\u00a0 statements\u00a0 are\u00a0 marked \u2018invariant\u2019<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Mark \u2018invariant\u2019 all those statements not previously so marked all of whose operands are either constant or having definitions reaching outside \u2018L\u2019 or have only one reaching definition which is marked invariant.<\/p>\n

           <\/p>\n

          }<\/p>\n

           <\/p>\n

          38.7 Performing Code motion<\/strong><\/p>\n

           <\/p>\n

          After identifying the loop invariant statements, we have to eliminate repeated computation of the statements whose results are not going to change. The statements which are identified as loop invariant are moved to the pre-header of the loop. In order to apply code motion, certain conditions need to be checked and applied. Consider a statement, \u2018s\u2019 x: = y+z. The following are the conditions that need to be checked and applied.<\/p>\n

           <\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Block containing a statement \u2018s\u2019 must dominate all exit nodes of the loop, which is essentially a successor node that is not in the loop<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No other statement in the loop assigns to \u2018x\u2019<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No use of \u2018x\u2019 in the loop is reached by any definition of \u2018x\u2019 other than \u2018s\u2019.<\/p>\n

           <\/p>\n

          Algorithm 38.5 implements code motion.<\/p>\n

           <\/p>\n

          Algorithm 38.5 \u2013 Code motion.<\/strong><\/p>\n

           <\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: a loop L with ud-chain information and dominator information<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a revised loop with a pre-header and some statements moved to the pre-header (if any)<\/p>\n

           <\/p>\n

          Identify_Eliminate_Codemotion<\/p>\n

           <\/p>\n

          {<\/p>\n

           <\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Identify the loop invariant statements defining \u2018x\u2019<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 For each statement \u2018s\u2019 defining \u2018x\u2019 find<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 That it is in a block that dominates all exits of L<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 That \u2018x\u2019 is not defined elsewhere in L<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 All uses in L of x can only be reached using statement \u2018s\u2019<\/p>\n

          \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Move, in the order found by loop invariant algorithm, each statement \u2018s\u2019 to a newly created pre-header<\/p>\n

          }<\/p>\n<\/div>\n

           <\/p>\n

          Code motion sometime results in some illegal and incorrect situations. Consider the figure 38.7 where the available flow graph is optimized.<\/p>\n

          \"\"<\/p>\n

          In figure 38.7, there is a loop from B2 \u2013 B3 \u2013 B4 \u2013 B2. Thus there is an assignment to the variable \u2018i’ to the value \u20182\u2019. As per the algorithm, this could be identified as loop invariant computation and could be moved to the pre-header and contributing to block B6. However, this is incorrect as the value of \u2018i’ gets assigned to \u20182\u2019 if this path through B3 is followed. If an alternate path that does not go through B3 is followed the value of \u2018i’ is \u20181\u2019 and hence we have performed an incorrect operation. So, for this flow graph there is no loop invariant computation.<\/p>\n

           <\/p>\n

          Summary: <\/strong>In this module, we looked at the algorithms for eliminating common sub-expression and copy propagation. We also looked at algorithms to identify unreachable code and elimination of the same. Code motion and loop invariant computation algorithms are also discussed with an example. In the next module, we will discuss additional loop optimization techniques.<\/p>\n","protected":false},"author":4,"menu_order":38,"template":"","meta":{"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-324","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\/324","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":3,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/324\/revisions"}],"predecessor-version":[{"id":333,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/324\/revisions\/333"}],"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\/324\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=324"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=324"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=324"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=324"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}