{"id":250,"date":"2018-07-20T09:31:34","date_gmt":"2018-07-20T09:31:34","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=250"},"modified":"2018-07-20T09:31:49","modified_gmt":"2018-07-20T09:31:49","slug":"basic-blocks-flow-graphs-and-next-use-information","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/basic-blocks-flow-graphs-and-next-use-information\/","title":{"rendered":"Basic Blocks, Flow graphs and Next-use information"},"content":{"raw":"
\r\n

After understanding the need for grouping the three-address intermediate code into basic blocks, this module will detail on the construction of basic blocks. A sequence of basic blocks represents a control flow of the program and is called as flow graphs and this module will discuss the construction of a flow graph. This module will conclude with the possible transformations in basic blocks to optimize the three-address code.<\/p>\r\n \r\n\r\n29.1 Basic Blocks and Flow graphs<\/strong>\r\n\r\n \r\n

A basic block is a sequence of consecutive instructions with exactly one entry point and one exit point. The exit points may be more than one if we consider branch instructions. A control flow graph (CFG) is a directed graph with basic blocks Bi as vertices and with edges Bi\u00aeBj if and only if Bj can be executed immediately after Bi. The algorithm for basic block construction was detailed in the previous module and is given below for a quick reference.<\/p>\r\n \r\n\r\nInput<\/em>:\u00a0 A sequence of three-address statements\r\n\r\n \r\n\r\nOutput<\/em>: A list of basic blocks with each three-address statement in exactly one block\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Determine the set of leaders<\/em>, the first statements of basic blocks\r\n\r\na)\u00a0\u00a0\u00a0\u00a0\u00a0 The first statement is the leader\r\n\r\nb)\u00a0\u00a0\u00a0\u00a0\u00a0 Any statement that is the target of a goto is a leader\r\n\r\nc)\u00a0\u00a0\u00a0\u00a0\u00a0 Any statement that immediately follows a goto is a leader\r\n\r\n<\/div>\r\n

\r\n

2.\u00a0\u00a0 For\u00a0\u00a0\u00a0 each\u00a0\u00a0\u00a0 leader, statements\u00a0\u00a0\u00a0 up\u00a0\u00a0\u00a0 to\u00a0 its\u00a0 but\u00a0 basic not\u00a0 block including\u00a0 consist the\u00a0 ofnextthe\u00a0\u00a0leader leader\u00a0 \u00a0or\u00a0\u00a0andtheall\u00a0 end\u00a0\u00a0of the <\/span>programUsing the algorithm for basic block construction let us try an example.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\nConsider the following high level program in Pascal language. Let us try constructing the basic blocks and flow graph of the same.\r\n\r\n \r\n\r\nBegin\r\n\r\nprod := 0\r\n\r\ni := 1;\r\n\r\ndo begin\r\n\r\nprod : = prod + a[i] * b[i];\r\n\r\ni = i +1;\r\n\r\nend\r\n\r\nwhile i< = 20\r\n\r\nend\r\n\r\n<\/div>\r\n \r\n\r\nThe following is the three-address code generated for the above sequence of instructions using the semantic rules discussed in the previous modules.\r\n
    \r\n \t
  1. prod := 0<\/li>\r\n \t
  2. i := 1<\/li>\r\n \t
  3. t1 := 4 * i<\/li>\r\n \t
  4. t2 := a[t1]<\/li>\r\n \t
  5. t3 := 4 * i<\/li>\r\n \t
  6. t4 := b [t3]<\/li>\r\n \t
  7. t5 := t2 *t4<\/li>\r\n \t
  8. t6 := prod + t5<\/li>\r\n \t
  9. prod := t6<\/li>\r\n \t
  10. t7 := i+1<\/li>\r\n \t
  11. i := t7<\/li>\r\n \t
  12. If i<= 20 goto (3)<\/li>\r\n<\/ol>\r\n \r\n

    The code is a do-while loop. The first two statements in the high- level program initializes two variables and the same is retained in the three-address code as well. The first statement in the body of the do-while loop, multiplies two array values and adds it with another variable. This is done in lines 3 to 9 of the three-address code based on the semantic rules for array access. The second statement of the do-while block increments the index variable \u2018i\u2019 and this is done in lines 10 to 11. Finally line 12 is the three-address code corresponding to the high- level while statement, which checks for end of iteration and branch accordingly.<\/p>\r\n \r\n\r\nNow, to construct the basic block and flow graph the following are the observations:\r\n

      \r\n \t
    • Line (1) is the beginning of the three-address code and hence is declared as a leader<\/li>\r\n \t
    • Line (3) is the target of a jump from line (12) and hence is also declared a leader<\/li>\r\n \t
    • Statement following (12), say line number (13) is a leader<\/li>\r\n \t
    • Hence, Lines (1) and (2) will form a basic block<\/li>\r\n \t
    • Lines (3) to (12) will form another basic block.<\/li>\r\n<\/ul>\r\n \r\n\r\nThis is depicted in figure 29.1\r\n\r\n\"\"\r\n\r\nThe first one is called basic block B1 and the second one as B2. B1 is the predecessor of B2 and so B2 is the successor of B1. The instructions that are part of B1 need to be executed before B2\u2019s instructions and hence control flows from B1 to B2.\r\n\r\n \r\n\r\n29.2 Loops<\/strong>\r\n\r\n \r\n

      Basic blocks that include a direction of control flow are called as a flow graph. This flow graph can sometimes form a loop that goes in a circular fashion amongst the basic blocks. A loop is a collection of basic blocks, such that<\/p>\r\n\r\n

        \r\n \t
      • All blocks in the collection are strongly connected. A strongly connected loop is one in which from any node to any other node, there is a path of length one or more within the loop.<\/li>\r\n \t
      • The collection of blocks has a unique entry, and the only way to reach a block in the loop is through this entry<\/li>\r\n<\/ul>\r\nLoops not containing any other loop is called as Inner loop. Loop that has one or more inner loops is referred to as outer loop.\r\n

        Consider the basic block and flow graph of figure 29.2. There are 4 blocks B1, B2, B3 and B4.<\/p>\r\n\"\"\r\n\r\nIn figure 29.2, B2 is connected to all other blocks with a path length of more than 1and hence is a strongly connected component. So, is the case with B3 and B4.\r\n\r\n \r\n\r\n29.3 Transformations on Basic Blocks<\/strong>\r\n\r\n \r\n

        In the previous module, we questioned on the need for basic blocks. Typically, any basic block, computes a set of expression. Values of the variables outside the block is decided by the computation inside the block. Two basic blocks are equivalent if they compute the same set of expressions. Consider the following basic block, which computes the addition of \u2018a\u2019 and \u2018b\u2019 and multiply with \u2018c\u2019 and assigns it to \u2018a\u2019. Though this block adds \u2018a\u2019 and \u2018b\u2019, since \u2018b\u2019 is initialized to \u20180\u2019 to start with, the addition of \u2018a\u2019 and \u2018b\u2019 does not have any effect. Hence, this block can be thought of as simply multiplying \u2018a\u2019 and \u2018c\u2019 and assigning it to \u2018a\u2019 and the value of \u2018b\u2019 which is set to \u20180\u2019 and the value of \u2018c\u2019 is unaltered.<\/p>\r\n\"\"\r\n

        \r\n

        As can be observed from this discussion, basic blocks could be analyzed on a simpler note to verify the validity of some instructions. A code- improving transformation is a code optimization to improve speed or reduce code size. Global transformations are performed across basic blocks. Local transformations are only performed on single basic blocks. The transformations that are carried out must be safe and preserve the meaning of the code. We can say, that a local transformation is safe if the transformed basic block is guaranteed to be equivalent to its original form.<\/p>\r\n \r\n\r\nThe transformations that are possible with basic block can be grouped into the following:\r\n\r\n \r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Structure-Preserving Transformation \u2013 In this transformation, the syntactic structure of the statements in the basic blocks are not altered.<\/p>\r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Algebraic Transformation\u2013In this type of transformation, mathematical identity are applied on the statements to perform the transformation and thus altering the syntactic structure<\/p>\r\n \r\n\r\nLet us look into these two types of transformations in detail in the next sections\r\n\r\n \r\n\r\n29.3.1 Structure-Preserving Transformation<\/strong>\r\n\r\n \r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Common Sub-expression Elimination \u2013 Within a block, if a particular expression is repeated the expression is said to be common. This could be eliminated to avoid unnecessary computation.<\/p>\r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Dead-code elimination \u2013 In a basic block, if a particular variable or assignment is not going to be used, then the instruction is said to be dead.<\/p>\r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Renaming of temporary variables \u2013 As we know, to convert instructions to three-address code, temporary variables are defined. These variables are renamed to effectively optimize the final code.<\/p>\r\n

        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Interchange of two independent adjacent statements \u2013 As we have already discussed in the previous module, reordering of instructions will result in an optimized code and this transformation allows swapping of two independent adjacent statements.<\/p>\r\n\r\n<\/div>\r\n

        \r\n\r\n \r\n\r\n29.3.1.1 Common Sub-expression Elimination.<\/strong>\r\n\r\n \r\n

        If an expression is computed repeatedly and in between the repeated computations, if the values of the variables of the expression is unaltered then the expression is said to be common.<\/p>\r\n \r\n\r\nConsider the following sequence of instructions:\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 a := b+c\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 b := a\u2013d\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 c := b+c\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := a-d\r\n\r\n \r\n\r\n \r\n

        In the above set of instruction, the RHS of the expression in line number (1) and (3) has \u201cb+c\u201d and so is \u201ca-d\u201d in line number (2) and (4). But, between line numbers (1) and (3) the value of the variable \u2018b\u2019 changes and hence \u201cb+c\u201d is not a common expression. However, the value of \u2018a\u2019 or\u2018d\u2019 doesn\u2019t change between line numbers (2) and (4) and hence \u201ca-d\u201d is considered as a common sub-expression. The value of \u2018d\u2019 changes after line number (4) and hence the above instructions could be replaced as follows:<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 a := b+c\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 b := a \u2013 d\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 c := b + c\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := b\r\n\r\n \r\n

        Thus common sub-expression elimination involves, identifying the common-expression and replacing the RHS with the computed LHS variable at the previous line number.\u00a0 Consider one more example:<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b * c\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a - t1\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 t3 := b * c\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t3\r\n\r\n \r\n

        Here, the common expression is \u201cb*c\u201d and hence this could be replaced as follows:<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>t1 := b * c<\/strong>\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a - t1<\/strong>\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 t3 := t1<\/strong>\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t3<\/strong>\r\n\r\n \r\n\r\n \r\n

        Here, the instruction at line number (3) is not used and hence, we could also eliminate that and replace t3 with t1. This is referred to as copy propagation. Thus removing common sub-expressions <\/span>results in copy code propagation, where the same value is available at multiple variables. This can be removed by replacing the LHS variable with the RHS <\/span>till the LHS \/ RHS values change. In this example, we could replace t3 with t1, as both will have the same value and thereby the instruction at line number (3) could be eliminated. Hence the code could be reduced to the following:<\/span><\/p>\r\n\r\n<\/div>\r\n

        \r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b * c<\/strong>\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a - t1<\/strong>\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t1<\/strong>\r\n\r\n \r\n\r\n29.3.1.2 Dead code elimination<\/strong>\r\n\r\n \r\n

        Any code that is not used is said to be dead. In the previous example, t3 is dead and hence we eliminated the instruction t3:= t1. In a similar fashion, if a particular variable is not going to be used later, then the instruction involving that variable could be eliminated. Consider the following sequence of instructions:<\/p>\r\n \r\n\r\nb := a + 1<\/strong>\r\n\r\na := b + c<\/strong>\r\n\r\n \r\n

        If the variable \u2018a\u2019 is not going to be used in any part of the later set of instructions, then \u2018a\u2019 is said to be dead and hence the above sequence of instructions can be reduced to just the single statement:<\/p>\r\n \r\n\r\nb := a + 1<\/strong>\r\n\r\n \r\n\r\nUnreachable code will also account for dead code and hence they could also be eliminated. Consider a branch instruction in which a particular path is never going to be taken. Then the instructions belonging to this branch could be completely eliminated as they are never going to be computed.\r\n\r\n \r\n\r\n29.3.1.3 Renaming Temporary variables<\/strong>\r\n\r\n \r\n

        Temporary variables that are dead at the end of a block can be safely renamed and can be eliminated if necessary. Consider the following sequence of instructions:<\/p>\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b + c<\/strong>\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a - t1<\/strong>\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := t1 * d<\/strong>\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := t2 + t1<\/strong>\r\n\r\n \r\n

        In this scenario, t1 is being reused at line numbers (1) and (3) and this could be conveniently renamed to another variable as shown in the instruction sequence below:<\/p>\r\n\r\n<\/div>\r\n

          \r\n \t
        1. t1 := b + c<\/strong><\/li>\r\n \t
        2. t2 := a - t1<\/strong><\/li>\r\n \t
        3. t3 := t1 * d<\/strong><\/li>\r\n \t
        4. d := t2 + t3<\/strong><\/li>\r\n<\/ol>\r\nHere, t1 in the LHS of line (3) is renamed as t3 and this value is used at line number (4).\r\n\r\n \r\n\r\n29.3.1.4 Independent state ments can be reorde red<\/strong>\r\n\r\n \r\n

          For improving on the register usage, certain statements could be reordered. The algorithm to do this will be seen in later modules. However, consider the following example involving 4 instructions.<\/p>\r\n\r\n

            \r\n \t
          1. t1 := b + c<\/strong><\/li>\r\n \t
          2. t2 := a - t1<\/strong><\/li>\r\n \t
          3. t3 := t1 * d<\/strong><\/li>\r\n \t
          4. d := t2 + t3<\/strong><\/li>\r\n<\/ol>\r\n \r\n\r\nThe above instructions could be changed as follows which doesn\u2019t alter the syntactic and semantic structure of the computation.\r\n
              \r\n \t
            1. t1 := b + c<\/strong><\/li>\r\n \t
            2. t3 := t1 * d<\/strong><\/li>\r\n \t
            3. t2 := a - t1<\/strong><\/li>\r\n \t
            4. d := t2 + t3<\/strong><\/li>\r\n<\/ol>\r\n \r\n\r\nHere, we have swapped line number (2) and (3) so that the computed value of t1 could be used effectively.\r\n\r\n \r\n\r\n29.3.2 Algebraic transformations<\/strong>\r\n\r\n \r\n

              In this transformation, the syntactic structure is altered to apply the mathematical identities. Instructions involving addition by \u20180\u2019 or multiplication by \u20181\u2019 could be eliminated. Similarly, multiplying by \u20182\u2019 could be considered as a left-shift or addition of a variable with itself. Exponentiation by \u20182\u2019 could be considered as multiplying a variable with itself. Following is the sequence of instructions and their corresponding algebraic transformed instructions.<\/p>\r\n\"\"\r\n

              The first computation results in \u20180\u2019 and hence t1 is assigned \u20180\u2019. As t1 is \u20180\u2019 the addition operation in the next instruction is removed. The third instruction of multiplying by 2 is changed to left-shift by 1. The fourth instruction of computing y2 is replaced with multiplying \u2018y\u2019 with itself.<\/p>\r\n \r\n\r\n29.4 Next-Use Information.<\/strong>\r\n\r\n \r\n

              Next-use information is needed for dead-code elimination and register allocation. Next-use is computed by a backward scan of a basic block. The next-use information will indicate the statement number at which a particular variable that is defined in the current position will be reused. The following are the steps involved in generating next-use information Consider a statement number \u2018i' with the following instruction.<\/p>\r\n\r\n

                \r\n \t
              • i<\/em>: x <\/em>:= y <\/em>op z<\/em><\/li>\r\n<\/ul>\r\nWe need to add liveness\/next-use information for the variables x<\/em>, y<\/em>, and z<\/em> to statement i<\/em> using the following rules:\r\n\r\n \r\n\r\n\u2013\u00a0 Set x<\/em> to \u201cnot live\u201d and \u201cno next use\u201d \u2013 As \u2018x\u2019 is defined here it\u2019s set to not live.\r\n\r\n\u2013 Set y<\/em> and z<\/em> to \u201clive\u201d and the next uses of y<\/em> and z<\/em> to i.<\/em> The variables \u2018y\u2019 and \u2018z\u2019 are being used in this statement and hence has their next use at \u2018i' and as they are used here these variables are set to live.\r\n\r\n \r\n\r\nTable 29.1 gives an example sequence of instructions and their nextuse and liveness computation. Consider statement \u2018i' precedes statement \u2018j\u2019. We start computing the information from statement \u2018j\u2019\r\n\r\n\"\"\r\n\r\nThe usage of nextuse and live information will be discussed in the subsequent modules along with the code generation algorithm.\r\n\r\n \r\n

                Summary<\/strong>: In this module we discussed the conversion from three-address code into basic blocks. The structure preserving and algebraic transformations that are possible in basic blocks also discussed. The module was completed with the computation of next-use and live information.<\/p>","rendered":"

                \n

                After understanding the need for grouping the three-address intermediate code into basic blocks, this module will detail on the construction of basic blocks. A sequence of basic blocks represents a control flow of the program and is called as flow graphs and this module will discuss the construction of a flow graph. This module will conclude with the possible transformations in basic blocks to optimize the three-address code.<\/p>\n

                 <\/p>\n

                29.1 Basic Blocks and Flow graphs<\/strong><\/p>\n

                 <\/p>\n

                A basic block is a sequence of consecutive instructions with exactly one entry point and one exit point. The exit points may be more than one if we consider branch instructions. A control flow graph (CFG) is a directed graph with basic blocks Bi as vertices and with edges Bi\u00aeBj if and only if Bj can be executed immediately after Bi. The algorithm for basic block construction was detailed in the previous module and is given below for a quick reference.<\/p>\n

                 <\/p>\n

                Input<\/em>:\u00a0 A sequence of three-address statements<\/p>\n

                 <\/p>\n

                Output<\/em>: A list of basic blocks with each three-address statement in exactly one block<\/p>\n

                 <\/p>\n

                1.\u00a0\u00a0\u00a0\u00a0\u00a0 Determine the set of leaders<\/em>, the first statements of basic blocks<\/p>\n

                a)\u00a0\u00a0\u00a0\u00a0\u00a0 The first statement is the leader<\/p>\n

                b)\u00a0\u00a0\u00a0\u00a0\u00a0 Any statement that is the target of a goto is a leader<\/p>\n

                c)\u00a0\u00a0\u00a0\u00a0\u00a0 Any statement that immediately follows a goto is a leader<\/p>\n<\/div>\n

                \n

                2.\u00a0\u00a0 For\u00a0\u00a0\u00a0 each\u00a0\u00a0\u00a0 leader, statements\u00a0\u00a0\u00a0 up\u00a0\u00a0\u00a0 to\u00a0 its\u00a0 but\u00a0 basic not\u00a0 block including\u00a0 consist the\u00a0 ofnextthe\u00a0\u00a0leader leader\u00a0 \u00a0or\u00a0\u00a0andtheall\u00a0 end\u00a0\u00a0of the <\/span>programUsing the algorithm for basic block construction let us try an example.<\/span><\/p>\n<\/div>\n

                \n

                Consider the following high level program in Pascal language. Let us try constructing the basic blocks and flow graph of the same.<\/p>\n

                 <\/p>\n

                Begin<\/p>\n

                prod := 0<\/p>\n

                i := 1;<\/p>\n

                do begin<\/p>\n

                prod : = prod + a[i] * b[i];<\/p>\n

                i = i +1;<\/p>\n

                end<\/p>\n

                while i< = 20<\/p>\n

                end<\/p>\n<\/div>\n

                 <\/p>\n

                The following is the three-address code generated for the above sequence of instructions using the semantic rules discussed in the previous modules.<\/p>\n

                  \n
                1. prod := 0<\/li>\n
                2. i := 1<\/li>\n
                3. t1 := 4 * i<\/li>\n
                4. t2 := a[t1]<\/li>\n
                5. t3 := 4 * i<\/li>\n
                6. t4 := b [t3]<\/li>\n
                7. t5 := t2 *t4<\/li>\n
                8. t6 := prod + t5<\/li>\n
                9. prod := t6<\/li>\n
                10. t7 := i+1<\/li>\n
                11. i := t7<\/li>\n
                12. If i<= 20 goto (3)<\/li>\n<\/ol>\n

                   <\/p>\n

                  The code is a do-while loop. The first two statements in the high- level program initializes two variables and the same is retained in the three-address code as well. The first statement in the body of the do-while loop, multiplies two array values and adds it with another variable. This is done in lines 3 to 9 of the three-address code based on the semantic rules for array access. The second statement of the do-while block increments the index variable \u2018i\u2019 and this is done in lines 10 to 11. Finally line 12 is the three-address code corresponding to the high- level while statement, which checks for end of iteration and branch accordingly.<\/p>\n

                   <\/p>\n

                  Now, to construct the basic block and flow graph the following are the observations:<\/p>\n

                    \n
                  • Line (1) is the beginning of the three-address code and hence is declared as a leader<\/li>\n
                  • Line (3) is the target of a jump from line (12) and hence is also declared a leader<\/li>\n
                  • Statement following (12), say line number (13) is a leader<\/li>\n
                  • Hence, Lines (1) and (2) will form a basic block<\/li>\n
                  • Lines (3) to (12) will form another basic block.<\/li>\n<\/ul>\n

                     <\/p>\n

                    This is depicted in figure 29.1<\/p>\n

                    \"\"<\/p>\n

                    The first one is called basic block B1 and the second one as B2. B1 is the predecessor of B2 and so B2 is the successor of B1. The instructions that are part of B1 need to be executed before B2\u2019s instructions and hence control flows from B1 to B2.<\/p>\n

                     <\/p>\n

                    29.2 Loops<\/strong><\/p>\n

                     <\/p>\n

                    Basic blocks that include a direction of control flow are called as a flow graph. This flow graph can sometimes form a loop that goes in a circular fashion amongst the basic blocks. A loop is a collection of basic blocks, such that<\/p>\n

                      \n
                    • All blocks in the collection are strongly connected. A strongly connected loop is one in which from any node to any other node, there is a path of length one or more within the loop.<\/li>\n
                    • The collection of blocks has a unique entry, and the only way to reach a block in the loop is through this entry<\/li>\n<\/ul>\n

                      Loops not containing any other loop is called as Inner loop. Loop that has one or more inner loops is referred to as outer loop.<\/p>\n

                      Consider the basic block and flow graph of figure 29.2. There are 4 blocks B1, B2, B3 and B4.<\/p>\n

                      \"\"<\/p>\n

                      In figure 29.2, B2 is connected to all other blocks with a path length of more than 1and hence is a strongly connected component. So, is the case with B3 and B4.<\/p>\n

                       <\/p>\n

                      29.3 Transformations on Basic Blocks<\/strong><\/p>\n

                       <\/p>\n

                      In the previous module, we questioned on the need for basic blocks. Typically, any basic block, computes a set of expression. Values of the variables outside the block is decided by the computation inside the block. Two basic blocks are equivalent if they compute the same set of expressions. Consider the following basic block, which computes the addition of \u2018a\u2019 and \u2018b\u2019 and multiply with \u2018c\u2019 and assigns it to \u2018a\u2019. Though this block adds \u2018a\u2019 and \u2018b\u2019, since \u2018b\u2019 is initialized to \u20180\u2019 to start with, the addition of \u2018a\u2019 and \u2018b\u2019 does not have any effect. Hence, this block can be thought of as simply multiplying \u2018a\u2019 and \u2018c\u2019 and assigning it to \u2018a\u2019 and the value of \u2018b\u2019 which is set to \u20180\u2019 and the value of \u2018c\u2019 is unaltered.<\/p>\n

                      \"\"<\/p>\n

                      \n

                      As can be observed from this discussion, basic blocks could be analyzed on a simpler note to verify the validity of some instructions. A code- improving transformation is a code optimization to improve speed or reduce code size. Global transformations are performed across basic blocks. Local transformations are only performed on single basic blocks. The transformations that are carried out must be safe and preserve the meaning of the code. We can say, that a local transformation is safe if the transformed basic block is guaranteed to be equivalent to its original form.<\/p>\n

                       <\/p>\n

                      The transformations that are possible with basic block can be grouped into the following:<\/p>\n

                       <\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Structure-Preserving Transformation \u2013 In this transformation, the syntactic structure of the statements in the basic blocks are not altered.<\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Algebraic Transformation\u2013In this type of transformation, mathematical identity are applied on the statements to perform the transformation and thus altering the syntactic structure<\/p>\n

                       <\/p>\n

                      Let us look into these two types of transformations in detail in the next sections<\/p>\n

                       <\/p>\n

                      29.3.1 Structure-Preserving Transformation<\/strong><\/p>\n

                       <\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Common Sub-expression Elimination \u2013 Within a block, if a particular expression is repeated the expression is said to be common. This could be eliminated to avoid unnecessary computation.<\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Dead-code elimination \u2013 In a basic block, if a particular variable or assignment is not going to be used, then the instruction is said to be dead.<\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Renaming of temporary variables \u2013 As we know, to convert instructions to three-address code, temporary variables are defined. These variables are renamed to effectively optimize the final code.<\/p>\n

                      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Interchange of two independent adjacent statements \u2013 As we have already discussed in the previous module, reordering of instructions will result in an optimized code and this transformation allows swapping of two independent adjacent statements.<\/p>\n<\/div>\n

                      \n

                       <\/p>\n

                      29.3.1.1 Common Sub-expression Elimination.<\/strong><\/p>\n

                       <\/p>\n

                      If an expression is computed repeatedly and in between the repeated computations, if the values of the variables of the expression is unaltered then the expression is said to be common.<\/p>\n

                       <\/p>\n

                      Consider the following sequence of instructions:<\/p>\n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 a := b+c<\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 b := a\u2013d<\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 c := b+c<\/p>\n

                      4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := a-d<\/p>\n

                       <\/p>\n

                       <\/p>\n

                      In the above set of instruction, the RHS of the expression in line number (1) and (3) has \u201cb+c\u201d and so is \u201ca-d\u201d in line number (2) and (4). But, between line numbers (1) and (3) the value of the variable \u2018b\u2019 changes and hence \u201cb+c\u201d is not a common expression. However, the value of \u2018a\u2019 or\u2018d\u2019 doesn\u2019t change between line numbers (2) and (4) and hence \u201ca-d\u201d is considered as a common sub-expression. The value of \u2018d\u2019 changes after line number (4) and hence the above instructions could be replaced as follows:<\/p>\n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 a := b+c<\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 b := a \u2013 d<\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 c := b + c<\/p>\n

                      4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := b<\/p>\n

                       <\/p>\n

                      Thus common sub-expression elimination involves, identifying the common-expression and replacing the RHS with the computed LHS variable at the previous line number.\u00a0 Consider one more example:<\/p>\n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b * c<\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a – t1<\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 t3 := b * c<\/p>\n

                      4.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t3<\/p>\n

                       <\/p>\n

                      Here, the common expression is \u201cb*c\u201d and hence this could be replaced as follows:<\/p>\n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 <\/strong>t1 := b * c<\/strong><\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a – t1<\/strong><\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 t3 := t1<\/strong><\/p>\n

                      4.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t3<\/strong><\/p>\n

                       <\/p>\n

                       <\/p>\n

                      Here, the instruction at line number (3) is not used and hence, we could also eliminate that and replace t3 with t1. This is referred to as copy propagation. Thus removing common sub-expressions <\/span>results in copy code propagation, where the same value is available at multiple variables. This can be removed by replacing the LHS variable with the RHS <\/span>till the LHS \/ RHS values change. In this example, we could replace t3 with t1, as both will have the same value and thereby the instruction at line number (3) could be eliminated. Hence the code could be reduced to the following:<\/span><\/p>\n<\/div>\n

                      \n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b * c<\/strong><\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a – t1<\/strong><\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 t4 := t2 + t1<\/strong><\/p>\n

                       <\/p>\n

                      29.3.1.2 Dead code elimination<\/strong><\/p>\n

                       <\/p>\n

                      Any code that is not used is said to be dead. In the previous example, t3 is dead and hence we eliminated the instruction t3:= t1. In a similar fashion, if a particular variable is not going to be used later, then the instruction involving that variable could be eliminated. Consider the following sequence of instructions:<\/p>\n

                       <\/p>\n

                      b := a + 1<\/strong><\/p>\n

                      a := b + c<\/strong><\/p>\n

                       <\/p>\n

                      If the variable \u2018a\u2019 is not going to be used in any part of the later set of instructions, then \u2018a\u2019 is said to be dead and hence the above sequence of instructions can be reduced to just the single statement:<\/p>\n

                       <\/p>\n

                      b := a + 1<\/strong><\/p>\n

                       <\/p>\n

                      Unreachable code will also account for dead code and hence they could also be eliminated. Consider a branch instruction in which a particular path is never going to be taken. Then the instructions belonging to this branch could be completely eliminated as they are never going to be computed.<\/p>\n

                       <\/p>\n

                      29.3.1.3 Renaming Temporary variables<\/strong><\/p>\n

                       <\/p>\n

                      Temporary variables that are dead at the end of a block can be safely renamed and can be eliminated if necessary. Consider the following sequence of instructions:<\/p>\n

                       <\/p>\n

                      1.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := b + c<\/strong><\/p>\n

                      2.\u00a0\u00a0\u00a0\u00a0\u00a0 t2 := a – t1<\/strong><\/p>\n

                      3.\u00a0\u00a0\u00a0\u00a0\u00a0 t1 := t1 * d<\/strong><\/p>\n

                      4.\u00a0\u00a0\u00a0\u00a0\u00a0 d := t2 + t1<\/strong><\/p>\n

                       <\/p>\n

                      In this scenario, t1 is being reused at line numbers (1) and (3) and this could be conveniently renamed to another variable as shown in the instruction sequence below:<\/p>\n<\/div>\n

                        \n
                      1. t1 := b + c<\/strong><\/li>\n
                      2. t2 := a – t1<\/strong><\/li>\n
                      3. t3 := t1 * d<\/strong><\/li>\n
                      4. d := t2 + t3<\/strong><\/li>\n<\/ol>\n

                        Here, t1 in the LHS of line (3) is renamed as t3 and this value is used at line number (4).<\/p>\n

                         <\/p>\n

                        29.3.1.4 Independent state ments can be reorde red<\/strong><\/p>\n

                         <\/p>\n

                        For improving on the register usage, certain statements could be reordered. The algorithm to do this will be seen in later modules. However, consider the following example involving 4 instructions.<\/p>\n

                          \n
                        1. t1 := b + c<\/strong><\/li>\n
                        2. t2 := a – t1<\/strong><\/li>\n
                        3. t3 := t1 * d<\/strong><\/li>\n
                        4. d := t2 + t3<\/strong><\/li>\n<\/ol>\n

                           <\/p>\n

                          The above instructions could be changed as follows which doesn\u2019t alter the syntactic and semantic structure of the computation.<\/p>\n

                            \n
                          1. t1 := b + c<\/strong><\/li>\n
                          2. t3 := t1 * d<\/strong><\/li>\n
                          3. t2 := a – t1<\/strong><\/li>\n
                          4. d := t2 + t3<\/strong><\/li>\n<\/ol>\n

                             <\/p>\n

                            Here, we have swapped line number (2) and (3) so that the computed value of t1 could be used effectively.<\/p>\n

                             <\/p>\n

                            29.3.2 Algebraic transformations<\/strong><\/p>\n

                             <\/p>\n

                            In this transformation, the syntactic structure is altered to apply the mathematical identities. Instructions involving addition by \u20180\u2019 or multiplication by \u20181\u2019 could be eliminated. Similarly, multiplying by \u20182\u2019 could be considered as a left-shift or addition of a variable with itself. Exponentiation by \u20182\u2019 could be considered as multiplying a variable with itself. Following is the sequence of instructions and their corresponding algebraic transformed instructions.<\/p>\n

                            \"\"<\/p>\n

                            The first computation results in \u20180\u2019 and hence t1 is assigned \u20180\u2019. As t1 is \u20180\u2019 the addition operation in the next instruction is removed. The third instruction of multiplying by 2 is changed to left-shift by 1. The fourth instruction of computing y2 is replaced with multiplying \u2018y\u2019 with itself.<\/p>\n

                             <\/p>\n

                            29.4 Next-Use Information.<\/strong><\/p>\n

                             <\/p>\n

                            Next-use information is needed for dead-code elimination and register allocation. Next-use is computed by a backward scan of a basic block. The next-use information will indicate the statement number at which a particular variable that is defined in the current position will be reused. The following are the steps involved in generating next-use information Consider a statement number \u2018i’ with the following instruction.<\/p>\n

                              \n
                            • i<\/em>: x <\/em>:= y <\/em>op z<\/em><\/li>\n<\/ul>\n

                              We need to add liveness\/next-use information for the variables x<\/em>, y<\/em>, and z<\/em> to statement i<\/em> using the following rules:<\/p>\n

                               <\/p>\n

                              \u2013\u00a0 Set x<\/em> to \u201cnot live\u201d and \u201cno next use\u201d \u2013 As \u2018x\u2019 is defined here it\u2019s set to not live.<\/p>\n

                              \u2013 Set y<\/em> and z<\/em> to \u201clive\u201d and the next uses of y<\/em> and z<\/em> to i.<\/em> The variables \u2018y\u2019 and \u2018z\u2019 are being used in this statement and hence has their next use at \u2018i’ and as they are used here these variables are set to live.<\/p>\n

                               <\/p>\n

                              Table 29.1 gives an example sequence of instructions and their nextuse and liveness computation. Consider statement \u2018i’ precedes statement \u2018j\u2019. We start computing the information from statement \u2018j\u2019<\/p>\n

                              \"\"<\/p>\n

                              The usage of nextuse and live information will be discussed in the subsequent modules along with the code generation algorithm.<\/p>\n

                               <\/p>\n

                              Summary<\/strong>: In this module we discussed the conversion from three-address code into basic blocks. The structure preserving and algebraic transformations that are possible in basic blocks also discussed. The module was completed with the computation of next-use and live information.<\/p>\n","protected":false},"author":4,"menu_order":29,"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-250","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\/250","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":2,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/250\/revisions"}],"predecessor-version":[{"id":257,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/250\/revisions\/257"}],"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\/250\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=250"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=250"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=250"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}