{"id":334,"date":"2018-07-20T12:16:00","date_gmt":"2018-07-20T12:16:00","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=334"},"modified":"2018-07-20T12:16:44","modified_gmt":"2018-07-20T12:16:44","slug":"loop-transformation-and-aliases","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/loop-transformation-and-aliases\/","title":{"rendered":"Loop Transformation and Aliases"},"content":{"raw":"
\r\n

After discussing the various algorithms for function preserving transformations, we need to optimize the loops. In the previous module, we discussed to perform loop invariant computation and in this module we will continue to optimize the loops further. Another section that requires optimization is handling of aliases. Aliases could be defined with respect to pointers and in this module we will discuss algorithms to handle pointer aliases.<\/p>\r\n \r\n\r\n39.1 Induction variable identification and elimination<\/strong>\r\n\r\n \r\n

Induction variable elimination is carried out by first identifying the induction variable, followed by strength reduction of the induction variable and then induction variable elimination. During strength reduction, other state ments that require strength reduction are also carried out.<\/strong><\/p>\r\n \r\n

A <\/strong>loop is executed through an induction variable. Thus a variable \u2018x\u2019 is induction if every time the value of \u2018x\u2019 is changed by a constant \u2018c\u2019. So, to identify the induction variable, we first look for basic induction variable i := i \u00b1 c. Then we look for derived induction variable \u2018j\u2019 which are\u00a0 defined in terms of the basic \u2018i'.<\/p>\r\n \r\n\r\nAlgorithm 39.1 gives the procedure for induction variable identification.\r\n\r\n \r\n\r\nAlgorithm 39.1 - Induction variable identification algorithm<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definitions and loop-invariant computation\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a set of induction variables\r\n\r\n \r\n\r\nIdentify_Induction_Variable()\r\n\r\n{\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Find basic induction variable based on loop- invariant computation (i,I, 0)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Search for a variable k having the following forms\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 k := j * b, k := b * j, k := j \/ b, k:= j \u00b1b, k:= b \u00b1j\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 b \u2013 constant, j is an induction variable\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Triple for k is (j, b, 0)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Compute the triple and accumulate to the list of inductions variables\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

After identifying the induction variables, if these variables are not going to be used after the iteration then it could be replaced by some useful variable. If such a useful variable is not possible to be identified then the induction variable is retained. If an induction variable that could be eliminated is identified, then Algorithm 39.2 is used to eliminate this induction variable.<\/p>\r\n \r\n\r\nAlgorithm 39.2 \u2013 Eliminate induction variable<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definition information, loop-invariant computation and live variable information\r\n\r\n<\/div>\r\n

\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a revised loop Eliminate_Induction_Variable()\r\n\r\n{\r\n\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Take some induction variable \u2018j\u2019 in \u2018i\u2018s family with (i,c,d) and modify each test that \u2018i\u2018 appears in to use \u2018j\u2019 instead. Constant \u2018c\u2019 is positive.<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if \u2018i' relop \u2018x\u2019 goto B is replaced as\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 r := c*x, r := r+d, if j relop r goto B\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if i1 relop i2 is also replaced with new variable if j1 relop j2\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Delete all assignments to the eliminated induction variables from the loop L\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Consider every new statement j:= s\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Verify that no assignment to \u2018s\u2019 between the introduced statement and the use of \u2018j\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace all uses of \u2018j\u2019 by uses of \u2018s\u2019 and delete j := s\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

The output of induction variable elimination will be discussed after carrying out strength reduction as strength reduction will involve removal of the induction variable.<\/p>\r\n \r\n\r\n39.2 Strength Reduction<\/strong>\r\n\r\n \r\n

After identifying the induction variables, they are checked to see if we could mod ify them to use additions \/ subtractions against multiplication \/ division. If such a transformation exists we replace it in the loops for these induction variables and this procedure is termed as strength reduction. Algorithm 39.3 discusses strength reduction of induction variables where the input in a loop and output will be a revised loop which is strength reduced.<\/p>\r\n \r\n\r\nAlgorithm 39.3 \u2013 Stre ngth reduction<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definition information and induction variables computed\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: A revised loop\r\n\r\n \r\n\r\nReduce_Strength()\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 For each induction variable i in turn, for every induction variable j in the family of i with triple (i, c, d): (j := i *c +d)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Create a new variable \u2018s\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the assignment to j by j:=s\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Immediately after each assignment i := i+n, append\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := s + c* n\r\n\r\n<\/div>\r\n

\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Place \u2018s\u2019 in the family of \u2018i\u2018 with triple (i,c,d)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s is initialized to c*i+d\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := c * i\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := s+d\r\n\r\n \r\n\r\n}\r\n\r\n \r\n\r\n \r\n

The algorithm works on the triple that is created as part of the induction variable identification procedure. We create a new variable\u2018s\u2019 to store the initial computation of the higher strength computation. We then increment or decrement this variable\u2018s\u2019 to take care of the actual\u00a0 computation.<\/p>\r\n \r\n

Let us discuss the quick sort example flow graph which we had discussed earlier in the previous module. We had optimized two basic blocks B5 and B6 and that does not belong part of loops. So we have omitted those two blocks and the figure is represented in figure 39.1. In figure 39.1, the following are the modifications:<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 B2 and B3 are inner loops\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Induction variable in B2 is \u2018i\u2019 and t2 (i, 4, 0)\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 A new variable is constructed as s2\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := 4 * i is replaced with t2:= s2\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Inserts the assignment s2 := s2 + 4 after i:= i+1 Similarly:\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Induction variable in B3 is \u2018j\u2019 and t4 (j, 4, 0)\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 A new variable is constructed as s4\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := 4 * j is replaced with t4:= s4\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Inserts the assignment s4 := s4 \u2013 4 after j:= j-1\r\n\r\n \r\n\r\nThe revised flow graph is given in figure 39.2 with the variables s2 and s4 introduced and the higher strength computed expression moved to the pre-header.\r\n\r\n<\/div>\r\n\"\"\r\n

After carrying out strength reduction, the statements, \u201ci:=i+1\u201d and \u201cj:=j-1\u201d which involves induction variables are considered to be useless as their values are not going to be used after the iterations and hence they are removed from basic blocks B2 and B3. The result is shown in figure 39.3.<\/p>\r\n\"\"\r\n

\r\n

As given in algorithm 39.2 the induction variables and the temporary assignment t2:=s2 and t4:=s4 are eliminated from the basic blocks B2 and B3.<\/p>\r\n \r\n\r\n39.3 Dealing with aliases<\/strong>\r\n\r\n \r\n

Pointer assignments and accessing variables through pointers is a common situation in any programming language. When we talk about arrays, the name of the array indicates the address of the array. Thus when a variable is declared using an array, the content of the \u2018ith\u2019 element o f an array \u201cA\u201d is accessed through one of the following ways:<\/p>\r\n \r\n\r\nA[i], A:= A+i, *A, *(A+i)\r\n\r\n \r\n

Thus, the value at A[i] could be modified also using multiple means. This is what we term as alias. If two or more expressions denote the same memory address we say that the expressions are aliases of one another. Thus we can say that presence of pointers which causes aliases to occur makes data-flow analysis more complex. Pointer \u2018p\u2019 can point to some variable and is to assume that an indirect assignment through a pointer can potentially change any variable. Consider a language having preliminary data types. If pointer \u2018p\u2019 points to a primitive data element, then any arithmetic operation on \u2018p\u2019 produces a value that may be an integer. If \u2018p\u2019 points to an array, addition or subtraction leads to \u2018p\u2019 somewhere in the array. If \u2018p\u2019 points to other array, then the impact of this would have to be dealt by the optimizing compiler to ensure allowing only correct assignments.<\/p>\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n39.3.1 Effects of pointer assignments<\/strong>\r\n\r\n \r\n

Variables that could possibly be used as pointers are those declared to be pointers. In addition, pointers could also refer to temporary variables that receive a value is a pointer plus or minus a constant. Pointer can point to one of the following situations:<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment s: p := & a then immediately after s, \u2018p\u2019 points only to \u2018a\u2019. If a is an array, then p can point only to \u2018a\u2019 after assignment of the form p := &a \u00b1c, where &a refers to &a[0]<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment, s: p:= q \u00b1c , \u2018p\u2019 and \u2018q\u2019 are pointers, then immediately after \u2018s\u2019, \u2018p\u2019 can point to any array that \u2018q\u2019 could point to before \u2018s\u2019<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment, s: p := q, \u2018p\u2019 points to what \u2018q\u2019 points to\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Any other assignment to \u2018p\u2019, there is no object that \u2018p\u2019 could point to such an assignment is probably meaningless\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 After any assignment to a variable other than \u2018p\u2019, \u2018p\u2019 points to whatever it did before the assignment\r\n\r\n \r\n\r\n39.3.2 Alias computation<\/strong>\r\n\r\n \r\n

Thus as can be seen in the previous discussion, a pointer variable can be made to point to more than one location. We use data flow equations to compute aliases. Let \u2018p\u2019 be a pointer and let \u2018a\u2019 be a set of variables. The following components of the equation are defined:<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 in[B] \u2013 (p, a) \u2013 set of variables {a} to which \u2018p\u2019 could point at the beginning of B<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 transB\u00a0 \u2013 transfer function that defines the effect of block B. This function takes a set of\u00a0 pairs, S of the form (p,a) and produces another set T. transS is computed for every statement and transB is the union of trans S The following are the rules for computing transS for every statement S:<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if S: p:= & a or p:= &a \u00b1 c, where \u2018a\u2019 is array then \u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}) U (p,a) Then transfer function is computed by removing the previous definitions of \u2018p\u2019 forall the variables \u2018b\u2019 and the new definition of \u2018a\u2019 is added for variable \u2018p\u2019\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If s: p: = q \u00b1 c for pointer \u2018q\u2019 and \u2018c\u2019 is non-zero \u2013 transS (S) = (S \u2013 {(p,b) | any variable b}) U {(p,b) | (q,b) is in S and b is any variable}\u00a0Here the previous definitions of \u2018p\u2019 <\/span>is removed and new definitions for \u2018p\u2019 is added and\u00a0<\/span>it is added based on the definitions available for pointer \u2018q\u2019<\/span>\r\n\r\n<\/div>\r\n

    \r\n \t
  • If S: p:= q then\u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}) U {(p,b) | (q,b) is in S} This is similar to the previous case only where the definition of \u2018q\u2019 will be the definitions of \u2018p\u2019 only. To start with the previous definitions of \u2018p\u2019 are removed and the definitions of \u2018p\u2019 are added as the definitions of \u2018q\u2019.<\/li>\r\n \t
  • If \u2018S\u2019 assigns to pointer \u2018p\u2019 another expression the \u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}<\/li>\r\n \t
  • If s is not an assignment to a pointer the\u2013\u00a0 transS (S) = She following data-flow equations are used to compute the alias which is the output of out[B]<\/li>\r\n<\/ul>\r\n
      \r\n \t
    • out[B] = transB (in[B]) \u2013 this calls for computing the transfer function of all blocks<\/li>\r\n \t
    • in[B] = U out(P) where P is a predecessor block \u2013 the output of all predecessors blocks are computed as union to determine the in[] of every block.<\/li>\r\n \t
    • transB (S) = transsk (transsk-1 (transsk-2 \u2026 ))) - This is computed as a cumulative of all the transfer functions. Consider the following example shown in figure 39.4 and let us compute the aliases of all these blocks using the data flow equations.<\/li>\r\n<\/ul>\r\n\"\"\r\n\r\nAs in the previous case we assume the in[B1] = \u03a6\r\n\u2022 out[B1] = transB1 (\u03a6) - B1 has one statement and hence\r\nout[B1] = transB1 (\u03a6) = {(q,c)}\r\n\u2022 in[B2] = {(q,c)}\r\n\u2022 p:= & c replace all pairs of\u2019 \u2018p\u2019 with (p,c)\r\n\u2022 remove all definitions of \u2018q\u2019 and replace with (q,a)\r\n\u2022 out[B2] = transB2 ((q,c)) = {(p,c), (q,a)}\r\nThe remaining computations are shown in Table 39.1. This has to go through multiple passes as\r\nin the case of other data flow equations and the II pass is shown in Table 39.2\r\n\r\n\"\"\r\n

      Thus we have identified the aliases which indicates that the values of the variables \u2018a\u2019 and \u2018c\u2019 could be changed through pointers \u2018p\u2019 and \u2018q\u2019. Alias analysis are used for the following scenarios to perform code optimization<\/p>\r\n\r\n

        \r\n \t
      • For live variable analysis<\/li>\r\n \t
      • Dead variable analysis<\/li>\r\n \t
      • Reaching definitions<\/li>\r\n<\/ul>\r\n

        \u00a0Summary: <\/strong>In this module, we have understood the algorithms for performing loop optimizations like strength reduction and induction variable elimination. We also discussed the impact of aliases using pointers and the data flow equation to identify the same. In the next module we will discuss the optimizations that can be carried out in procedures.<\/p>","rendered":"

        \n

        After discussing the various algorithms for function preserving transformations, we need to optimize the loops. In the previous module, we discussed to perform loop invariant computation and in this module we will continue to optimize the loops further. Another section that requires optimization is handling of aliases. Aliases could be defined with respect to pointers and in this module we will discuss algorithms to handle pointer aliases.<\/p>\n

         <\/p>\n

        39.1 Induction variable identification and elimination<\/strong><\/p>\n

         <\/p>\n

        Induction variable elimination is carried out by first identifying the induction variable, followed by strength reduction of the induction variable and then induction variable elimination. During strength reduction, other state ments that require strength reduction are also carried out.<\/strong><\/p>\n

         <\/p>\n

        A <\/strong>loop is executed through an induction variable. Thus a variable \u2018x\u2019 is induction if every time the value of \u2018x\u2019 is changed by a constant \u2018c\u2019. So, to identify the induction variable, we first look for basic induction variable i := i \u00b1 c. Then we look for derived induction variable \u2018j\u2019 which are\u00a0 defined in terms of the basic \u2018i’.<\/p>\n

         <\/p>\n

        Algorithm 39.1 gives the procedure for induction variable identification.<\/p>\n

         <\/p>\n

        Algorithm 39.1 – Induction variable identification algorithm<\/strong><\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definitions and loop-invariant computation<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a set of induction variables<\/p>\n

         <\/p>\n

        Identify_Induction_Variable()<\/p>\n

        {<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Find basic induction variable based on loop- invariant computation (i,I, 0)<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Search for a variable k having the following forms<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 k := j * b, k := b * j, k := j \/ b, k:= j \u00b1b, k:= b \u00b1j<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 b \u2013 constant, j is an induction variable<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Triple for k is (j, b, 0)<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Compute the triple and accumulate to the list of inductions variables<\/p>\n

         <\/p>\n

        }<\/p>\n

         <\/p>\n

        After identifying the induction variables, if these variables are not going to be used after the iteration then it could be replaced by some useful variable. If such a useful variable is not possible to be identified then the induction variable is retained. If an induction variable that could be eliminated is identified, then Algorithm 39.2 is used to eliminate this induction variable.<\/p>\n

         <\/p>\n

        Algorithm 39.2 \u2013 Eliminate induction variable<\/strong><\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definition information, loop-invariant computation and live variable information<\/p>\n<\/div>\n

        \n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Output: a revised loop Eliminate_Induction_Variable()<\/p>\n

        {<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Take some induction variable \u2018j\u2019 in \u2018i\u2018s family with (i,c,d) and modify each test that \u2018i\u2018 appears in to use \u2018j\u2019 instead. Constant \u2018c\u2019 is positive.<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if \u2018i’ relop \u2018x\u2019 goto B is replaced as<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 r := c*x, r := r+d, if j relop r goto B<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if i1 relop i2 is also replaced with new variable if j1 relop j2<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Delete all assignments to the eliminated induction variables from the loop L<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Consider every new statement j:= s<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Verify that no assignment to \u2018s\u2019 between the introduced statement and the use of \u2018j\u2019<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace all uses of \u2018j\u2019 by uses of \u2018s\u2019 and delete j := s<\/p>\n

         <\/p>\n

        }<\/p>\n

         <\/p>\n

        The output of induction variable elimination will be discussed after carrying out strength reduction as strength reduction will involve removal of the induction variable.<\/p>\n

         <\/p>\n

        39.2 Strength Reduction<\/strong><\/p>\n

         <\/p>\n

        After identifying the induction variables, they are checked to see if we could mod ify them to use additions \/ subtractions against multiplication \/ division. If such a transformation exists we replace it in the loops for these induction variables and this procedure is termed as strength reduction. Algorithm 39.3 discusses strength reduction of induction variables where the input in a loop and output will be a revised loop which is strength reduced.<\/p>\n

         <\/p>\n

        Algorithm 39.3 \u2013 Stre ngth reduction<\/strong><\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input: A loop L with reaching definition information and induction variables computed<\/p>\n

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

         <\/p>\n

        Reduce_Strength()<\/p>\n

         <\/p>\n

        {<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 For each induction variable i in turn, for every induction variable j in the family of i with triple (i, c, d): (j := i *c +d)<\/p>\n

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

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the assignment to j by j:=s<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Immediately after each assignment i := i+n, append<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := s + c* n<\/p>\n<\/div>\n

        \n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Place \u2018s\u2019 in the family of \u2018i\u2018 with triple (i,c,d)<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s is initialized to c*i+d<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := c * i<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 s := s+d<\/p>\n

         <\/p>\n

        }<\/p>\n

         <\/p>\n

         <\/p>\n

        The algorithm works on the triple that is created as part of the induction variable identification procedure. We create a new variable\u2018s\u2019 to store the initial computation of the higher strength computation. We then increment or decrement this variable\u2018s\u2019 to take care of the actual\u00a0 computation.<\/p>\n

         <\/p>\n

        Let us discuss the quick sort example flow graph which we had discussed earlier in the previous module. We had optimized two basic blocks B5 and B6 and that does not belong part of loops. So we have omitted those two blocks and the figure is represented in figure 39.1. In figure 39.1, the following are the modifications:<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 B2 and B3 are inner loops<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Induction variable in B2 is \u2018i\u2019 and t2 (i, 4, 0)<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 A new variable is constructed as s2<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := 4 * i is replaced with t2:= s2<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Inserts the assignment s2 := s2 + 4 after i:= i+1 Similarly:<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Induction variable in B3 is \u2018j\u2019 and t4 (j, 4, 0)<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 A new variable is constructed as s4<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := 4 * j is replaced with t4:= s4<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Inserts the assignment s4 := s4 \u2013 4 after j:= j-1<\/p>\n

         <\/p>\n

        The revised flow graph is given in figure 39.2 with the variables s2 and s4 introduced and the higher strength computed expression moved to the pre-header.<\/p>\n<\/div>\n

        \"\"<\/p>\n

        After carrying out strength reduction, the statements, \u201ci:=i+1\u201d and \u201cj:=j-1\u201d which involves induction variables are considered to be useless as their values are not going to be used after the iterations and hence they are removed from basic blocks B2 and B3. The result is shown in figure 39.3.<\/p>\n

        \"\"<\/p>\n

        \n

        As given in algorithm 39.2 the induction variables and the temporary assignment t2:=s2 and t4:=s4 are eliminated from the basic blocks B2 and B3.<\/p>\n

         <\/p>\n

        39.3 Dealing with aliases<\/strong><\/p>\n

         <\/p>\n

        Pointer assignments and accessing variables through pointers is a common situation in any programming language. When we talk about arrays, the name of the array indicates the address of the array. Thus when a variable is declared using an array, the content of the \u2018ith\u2019 element o f an array \u201cA\u201d is accessed through one of the following ways:<\/p>\n

         <\/p>\n

        A[i], A:= A+i, *A, *(A+i)<\/p>\n

         <\/p>\n

        Thus, the value at A[i] could be modified also using multiple means. This is what we term as alias. If two or more expressions denote the same memory address we say that the expressions are aliases of one another. Thus we can say that presence of pointers which causes aliases to occur makes data-flow analysis more complex. Pointer \u2018p\u2019 can point to some variable and is to assume that an indirect assignment through a pointer can potentially change any variable. Consider a language having preliminary data types. If pointer \u2018p\u2019 points to a primitive data element, then any arithmetic operation on \u2018p\u2019 produces a value that may be an integer. If \u2018p\u2019 points to an array, addition or subtraction leads to \u2018p\u2019 somewhere in the array. If \u2018p\u2019 points to other array, then the impact of this would have to be dealt by the optimizing compiler to ensure allowing only correct assignments.<\/p>\n<\/div>\n

         <\/p>\n

        \n

        39.3.1 Effects of pointer assignments<\/strong><\/p>\n

         <\/p>\n

        Variables that could possibly be used as pointers are those declared to be pointers. In addition, pointers could also refer to temporary variables that receive a value is a pointer plus or minus a constant. Pointer can point to one of the following situations:<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment s: p := & a then immediately after s, \u2018p\u2019 points only to \u2018a\u2019. If a is an array, then p can point only to \u2018a\u2019 after assignment of the form p := &a \u00b1c, where &a refers to &a[0]<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment, s: p:= q \u00b1c , \u2018p\u2019 and \u2018q\u2019 are pointers, then immediately after \u2018s\u2019, \u2018p\u2019 can point to any array that \u2018q\u2019 could point to before \u2018s\u2019<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If there is an assignment, s: p := q, \u2018p\u2019 points to what \u2018q\u2019 points to<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Any other assignment to \u2018p\u2019, there is no object that \u2018p\u2019 could point to such an assignment is probably meaningless<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 After any assignment to a variable other than \u2018p\u2019, \u2018p\u2019 points to whatever it did before the assignment<\/p>\n

         <\/p>\n

        39.3.2 Alias computation<\/strong><\/p>\n

         <\/p>\n

        Thus as can be seen in the previous discussion, a pointer variable can be made to point to more than one location. We use data flow equations to compute aliases. Let \u2018p\u2019 be a pointer and let \u2018a\u2019 be a set of variables. The following components of the equation are defined:<\/p>\n

         <\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 in[B] \u2013 (p, a) \u2013 set of variables {a} to which \u2018p\u2019 could point at the beginning of B<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 transB\u00a0 \u2013 transfer function that defines the effect of block B. This function takes a set of\u00a0 pairs, S of the form (p,a) and produces another set T. transS is computed for every statement and transB is the union of trans S The following are the rules for computing transS for every statement S:<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 if S: p:= & a or p:= &a \u00b1 c, where \u2018a\u2019 is array then \u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}) U (p,a) Then transfer function is computed by removing the previous definitions of \u2018p\u2019 forall the variables \u2018b\u2019 and the new definition of \u2018a\u2019 is added for variable \u2018p\u2019<\/p>\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 If s: p: = q \u00b1 c for pointer \u2018q\u2019 and \u2018c\u2019 is non-zero \u2013 transS (S) = (S \u2013 {(p,b) | any variable b}) U {(p,b) | (q,b) is in S and b is any variable}\u00a0Here the previous definitions of \u2018p\u2019 <\/span>is removed and new definitions for \u2018p\u2019 is added and\u00a0<\/span>it is added based on the definitions available for pointer \u2018q\u2019<\/span><\/p>\n<\/div>\n

          \n
        • If S: p:= q then\u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}) U {(p,b) | (q,b) is in S} This is similar to the previous case only where the definition of \u2018q\u2019 will be the definitions of \u2018p\u2019 only. To start with the previous definitions of \u2018p\u2019 are removed and the definitions of \u2018p\u2019 are added as the definitions of \u2018q\u2019.<\/li>\n
        • If \u2018S\u2019 assigns to pointer \u2018p\u2019 another expression the \u2013\u00a0 transS (S) = (S \u2013 {(p,b) | any variable b}<\/li>\n
        • If s is not an assignment to a pointer the\u2013\u00a0 transS (S) = She following data-flow equations are used to compute the alias which is the output of out[B]<\/li>\n<\/ul>\n
            \n
          • out[B] = transB (in[B]) \u2013 this calls for computing the transfer function of all blocks<\/li>\n
          • in[B] = U out(P) where P is a predecessor block \u2013 the output of all predecessors blocks are computed as union to determine the in[] of every block.<\/li>\n
          • transB (S) = transsk (transsk-1 (transsk-2 \u2026 ))) – This is computed as a cumulative of all the transfer functions. Consider the following example shown in figure 39.4 and let us compute the aliases of all these blocks using the data flow equations.<\/li>\n<\/ul>\n

            \"\"<\/p>\n

            As in the previous case we assume the in[B1] = \u03a6
            \n\u2022 out[B1] = transB1 (\u03a6) – B1 has one statement and hence
            \nout[B1] = transB1 (\u03a6) = {(q,c)}
            \n\u2022 in[B2] = {(q,c)}
            \n\u2022 p:= & c replace all pairs of\u2019 \u2018p\u2019 with (p,c)
            \n\u2022 remove all definitions of \u2018q\u2019 and replace with (q,a)
            \n\u2022 out[B2] = transB2 ((q,c)) = {(p,c), (q,a)}
            \nThe remaining computations are shown in Table 39.1. This has to go through multiple passes as
            \nin the case of other data flow equations and the II pass is shown in Table 39.2<\/p>\n

            \"\"<\/p>\n

            Thus we have identified the aliases which indicates that the values of the variables \u2018a\u2019 and \u2018c\u2019 could be changed through pointers \u2018p\u2019 and \u2018q\u2019. Alias analysis are used for the following scenarios to perform code optimization<\/p>\n

              \n
            • For live variable analysis<\/li>\n
            • Dead variable analysis<\/li>\n
            • Reaching definitions<\/li>\n<\/ul>\n

              \u00a0Summary: <\/strong>In this module, we have understood the algorithms for performing loop optimizations like strength reduction and induction variable elimination. We also discussed the impact of aliases using pointers and the data flow equation to identify the same. In the next module we will discuss the optimizations that can be carried out in procedures.<\/p>\n","protected":false},"author":4,"menu_order":39,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-334","chapter","type-chapter","status-publish","hentry"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/334","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\/334\/revisions"}],"predecessor-version":[{"id":339,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/334\/revisions\/339"}],"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\/334\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=334"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=334"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=334"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}