{"id":272,"date":"2018-07-20T10:25:26","date_gmt":"2018-07-20T10:25:26","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=272"},"modified":"2018-07-20T10:26:13","modified_gmt":"2018-07-20T10:26:13","slug":"dag-based-code-generation-and-dynamic-programming","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/dag-based-code-generation-and-dynamic-programming\/","title":{"rendered":"DAG based Code Generation and Dynamic Programming"},"content":{"raw":"
\r\n

this module, we would try to understand the code generation algorithm from DAG after the DAG has been reordered and labeled. As another approach to code generation, we will discuss the Dynamic programming approach to code generation.<\/p>\r\n \r\n\r\n32.1 Code generation from DAG<\/strong>\r\n\r\n \r\n

As discussed in the previous module, one of the ideas behind the DAG construction is code generation. The steps involved include reordering of the instructions, labeling the nodes with the number of registers required and use this information to generate target assembly language code.<\/p>\r\n \r\n

The code generation algorithm uses a recursive procedure on a labeled DAG. Considers code generation based on the labels assigned to the nodes. It uses two stacks, one register stack \u201crstack\u201d and another memory stack, \u201cmstack\u201d. Stack \u201crstack\u201d is used to allocate registers. Initially rstack contains all available registers. The algorithm retains the registers on rstack in the same order it has found them. The typical functions of the stack, like push(), pop() is used to rearrange the rstack and in addition, the algorithm uses a swap(rstack) function to interchange the top two registers on rstack.<\/p>\r\n \r\n\r\nThe algorithm, considers five different cases to generate code. They are discussed as follows:\r\n\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 0: <\/strong>This is a simple and terminating case of the recursive procedure. If, \u2019n\u2019 is a leaf and the leftmost child of its parent, we generate just a load instruction.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 1: <\/strong>This is the situation when the right node is a leaf and the left node could be a sub-tree. In this case, we generate code to evaluate n1 into register R=top(rstack) followed by the instruction \u201cop name R\u201d.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 2: <\/strong>The right sub-tree requires more registers than the left sub-tree. A sub-tree of the form where n1 can be evaluated without stores but n2 is harder to evaluate than n1 as itrequires more registers. For this case, swap the top two registers on rsatck, then evaluate n2 into R=top(rstack).We remove R from rstack and evaluate n1 into S = top(rstack). Then we generate the instruction \u201cop R, S\u201d, which produce the value of \u201cn\u201d in register S. Another call to swap leaves rstack as it was, upon this call code generation begins.<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 3<\/strong>: It is similar to case 2 except that here the left sub-tree is harder and is evaluated first. There is no need to swap registers here.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 4: <\/strong>It occurs when both sub-trees require r or more registers to evaluate without stores. Since we must use a temporary memory location, we first evaluate the right sub-tree into the temporary T, then the left sub-tree, and finally the root. All these cases are discussed in Algorithm 32.1 to generate code from the DAG and the algorithm is named gencode(n) where \u2018n\u2019 is the root of the DAG which is passed as argument<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\nProcedure gencode(n);\r\n\r\nBegin\r\n\r\n \r\n\r\n\/* case 0 *\/\r\n\r\n \r\n\r\nif n is a left leaf representing operand name and n is the leftmost child of its parent then print \u2018MOV\u2019 || name || \u2018.\u2019 || top(rstack)\r\n\r\n \r\n

else if n is an interior node with operator op, left child n1, and right child n2 then \/* case 1 *\/<\/p>\r\nif label(n2) = 0 then begin\r\n\r\nlet name be the operand represented by n2;\r\n\r\ngencode(n1);\r\n\r\nprint op || name || \u2018.\u2019 || top(rstack)\r\n\r\nend\r\n\r\n \r\n\r\n\/* case 2 *\/\r\n\r\nelse if 1 \u2264 label (n1) < label(n2) and label(n1) < r then begin swap(rstack);\r\n\r\ngencode(n2 );\r\n\r\n \r\n\r\nR := pop(rstack); \/* n2 was evaluated into register R *\/ gencode(n1);\r\n\r\nprint op || R || \u2018.\u2019 || top(rstack);\r\n\r\n \r\n\r\npush(rstack,R);\r\n\r\nswap(rstack)\r\n\r\nend\r\n\r\n \r\n\r\n\/* case 3 *\/\r\n\r\nelse if 1 \u2264 label (n2) < label(n1) and label(n2) < r then begin gencode(n1);\r\n\r\nR := pop(rstack); \/* n1 was evaluated into register R *\/ gencode(n2);\r\n\r\nprint op || R || \u2018.\u2019 || top(rstack);\r\n\r\npush(rstack,R);\r\n\r\nend\r\n\r\n \r\n\r\n\/* case 4, both labels \u2265 r, the total number of registers *\/ else begin\r\n\r\ngencode(n2 );\r\n\r\nT := pop(tstack);\r\n\r\nPrint \u2018MOV\u2019 || top(rstack) || \u2018.\u2019 || T;\r\n\r\ngencode(n1);\r\n\r\npush(rstack,R);\r\n\r\nprint op || T || \u2018.\u2019 || top(rstack)\r\n\r\nend\r\n\r\nend\r\n\r\n \r\n

Case 1 checks if the right child of an interior node is a leaf node. If it is a leaf node, then we call the function recursively with the left child as the root node. To evaluate and finally conclude this case with generating an \u201cop\u201d instruction. Case 2 is evaluated if the right sub-tree is heavy. If it is heavy, we swap the register stack so that the right sub\u2014tree is evaluated into the register which<\/p>\r\n\r\n<\/div>\r\n \r\n

is beneath the top register. We then recursively call gencode() function with the right sub -tree\u2019s node as root and we remove this register from rstack. We then call gencode() to evaluate the left sub-tree and use the top of the stack register. After that we swap the rstack contents to ensure the initial rstack content is retained. Case 3 is just the opposite of Case 2 and since in this context, we evaluate first the left sub-tree, the rstack contents are used as it is and not swapped. Case 4 is the situation when there are no registers in the rstack. We use a memory based operation where the operands would be memory to compute.<\/p>\r\n \r\n\r\nConsider the DAG given in figure 32.1 as an example for code generation.\r\n\r\n \r\n\r\n\"\"\r\n

The nodes of the DAG are labeled with the number of registers that it requires for computation. Assume that there are two register R0 and R1 with R0 on the top of the stack. The algorithm gencode() is called with the root node t4. The children of this node are t1 and t3. Since the label of t3 is greater, case 2 is initiated. This calls recursively gencode() with t3 after swapping the register stack. This results in its left child being a leaf node and hence falls under case 0. Case 0 is a load instruction and the value \u2018e\u2019 is loaded into R1. After this call returns it goes to the next step of the previous call, which removes the register R1 from rstack using the pop() command and the gencode function is called with the right sub-tree node, which is t2. This falls under case 1 as the label of the right leaf node is 0 and thus gencode is again called with node \u2018c\u2019. This again falls under case 0 and initiates a load instruction into R0 and returns. The next instruction is the next step of Case1 where an operator instruction is issued followed by the next instruction of case 2 where a SUB instruction is issued and the register is pushed and then swapped. Proceeding in a similar fashion we get the following code.<\/p>\r\n \r\n\r\n \r\n\r\ngencode(t4) [R1 R0] \/\/ case 2\r\ngencode(t3) [R0 R1] \/\/ case 3\r\ngencode(e) [R0R1] \/\/ case 0\r\nprint MOV e, R1\r\ngencode(t2) [R0] \/\/ case 1\r\ngencode(c) [R0] \/\/ case 0\r\nprint MOV c, R0\r\nprint ADD d, R0\r\nprint SUB R0, R1\r\ngencode(t1) [R0] \/\/ case 1\r\ngencode(a) [R0] \/\/ case 0\r\nprint MOV a, R0\r\nprint ADD b, R0\r\nprint SUB R1, R0\r\n

\r\n\r\n32.2 Multi-register operation<\/strong>\r\n\r\n \r\n

The code generation algorithm gencode() discussed uses only one register by default. The algorithm could be made to use two registers for regular operations by changing the labeling algorithm as discussed in the previous module as follows:<\/p>\r\n \r\n

The algorithm could be used to exploit the algebraic properties where we could swap left and right nodes effectively to use the code generation algorithm. This will also avoid recomputation of common sub-expression.<\/p>\r\n \r\n\r\n32.3 Dynamic programming<\/strong>\r\n\r\n \r\n

Constructing a DAG for code generation creates one more approach to code generation. We can adopt a bottom- up approach to compute the cost of evaluating each node using a dynamic programming approach. Dynamic programming is an algorithmic design strategy where all possible directions are explored and the least cost is chosen for computing at every point of time. For code generation, in order to compute the code for each node, all possibilities in terms of instruction cost is evaluated and the least cost to compute each node is used. For each node \u2018n\u2019 of the expression tree T an array C<\/em> of costs, in which the ith component C[i] is the optimal cost of computing the sub-tree S rooted at \u2018n\u2019 into a register, assuming i registers are available for the computation<\/p>\r\n \r\n

After computing the cost vector, we traverse the tree T, and use the cost vectors to determine which sub-trees of T must be computed into memory or register. Traverse each tree using the cost vectors and associated instructions to generate the final target code. The code for the sub-trees computed into memory locations is generated first.<\/p>\r\n \r\n\r\nTo consider the dynamic programming approach to code generation the following assumptions are made:\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 There are only two registers available for computation\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Cost of computing a node which is in memory involves 0\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The following instructions are alone permitted where the LHS corresponds to target and\r\n\r\n \r\n\r\nthe RHS corresponds to the source.\r\n\r\n\u2013\u00a0 Ri := Mj - Loads the memory content Mj into register Ri\r\n\r\n\u2013\u00a0 Ri := Ri op Rj \u2013 operates Ri and Rj and the result is available in Ri\r\n\r\n<\/div>\r\n\u2013\u00a0 Ri := Ri op Mj - operates Ri and Mj and the result is available in Ri\r\n\r\n\u2013\u00a0 Ri := Rj \u2013 Loads the register content Rj into register Ri\r\n\r\n\u2013\u00a0 Mi := Ri \u2013 Loads the register content Ri into memory Mi\r\n\r\n \r\n\r\n\"\"\r\n\r\nFigure 32.2 Syntax tree for the example expression.<\/strong>\r\n\r\n \r\n\r\nEach node has a cost vector that has 3 values which indicate the cost of computing that node with 0, 1 and 2 registers. The computation for various cases is detailed below:\r\n\r\n \r\n

    \r\n \t
  • Leaf nodes \u2013 All leaf nodes have the same cost vector (0, 1, 1)<\/li>\r\n<\/ul>\r\n\u2013\u00a0 Cost of moving a variable with no registers is 0 \u2013 variable in register itself\r\n\r\n\u2013\u00a0 Cost of moving a variable with 1\/ 2 registers is 1 using the instruction Ri : = Mj\r\n\r\n\u2013\u00a0 Cost of leaf nodes are just (0, 1, 1) using no register, 1 register, 2 registers\r\n
      \r\n \t
    • Last but one node \u2013 find all possible and choose the least cost<\/li>\r\n<\/ul>\r\n\"\"\r\n
      \r\n\r\nCost vector of the last but one level node is (3, 2, 2) as this value is the minimum based on individual node computation\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Computing the * node.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Using 0 registers\r\n\r\n \r\n\r\nRi = Ri op Mj (costs 1)\r\n\r\n \r\n\r\nMj = Ri\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (costs 1)\r\n\r\n \r\n\r\nThe cost to compute the children nodes of * is 1 + 3. Thus resulting in 6.\r\n\r\n \r\n\r\n(or)\r\n\r\n \r\n\r\nRi = Ri op Rj (costs 1)\r\n\r\n \r\n\r\nMj = Ri\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (costs 1)\r\n\r\n \r\n\r\nThe cost to compute the children nodes of * is 1+2. Thus resulting in a total of 5 and between 5 and 6 we choose 5 as the cost of the first quantity.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Using 1 registers\r\n\r\n \r\n\r\nRi = Ri op Mj (costs 1)\r\n\r\n \r\n\r\nThe cost to compute the children nodes of * is 1 + 3. Thus resulting in 5 as the instruction Ri op Mj is supported which expects the RHS node to be in memory.\r\n\r\n<\/div>\r\n
        \r\n \t
      • Using 2 registers<\/li>\r\n<\/ul>\r\n \r\n\r\nRi = Ri op Rj (costs 1)\r\n\r\n \r\n

        The cost to compute the children nodes of * is 1+2. If the computation involves two registers it could be computed using one register also. Thus resulting in a total of 4 for two registers and between 5 and 4 we choose 4 as the cost of the third cost vector C.<\/p>\r\n \r\n\r\nThe following is the logic for the computation of the cost vector for the root.\r\n

          \r\n \t
        • Compute the left subtree with two registers available into register R0, compute the right subtree with one register available into register R1, and use the instruction ADD R0, R0, R1 to compute the root. This sequence has cost 2+5<\/em>+1=8.<\/li>\r\n \t
        • Compute the right subtree with two registers available into R l , compute the left subtree with one register available into R0, and use the instruction ADD R0, R0, R1. This sequence has cost 4+2+1=7.<\/li>\r\n \t
        • Compute the right subtree into memory location M, compute the left subtree with two registers available into register RO, and use the instruction ADD R0, R0, M. This sequence has cost 5+2+1=8<\/li>\r\n<\/ul>\r\nThis tree is traversed from bottom to top to generate code as follows:\r\n
            \r\n \t
          • R0 := c \u2013 the value is a memory based operation to move \u2018c\u2019 into R0<\/li>\r\n \t
          • R1 := d \u2013 same as \u2018c\u2019 and we use another register to move \u2018d\u2019 into R1<\/li>\r\n \t
          • R1 := R1\/e \u2013 Only one register is used to compute this node and the result is in R1<\/li>\r\n \t
          • R0 := R0 * R1 \u2013 Two registers resulted in a lower cost and we use that<\/li>\r\n \t
          • R1 := a \u2013 R1 is free and hence \u2018a\u2019 is loaded to R1<\/li>\r\n \t
          • R1 := R1 \u2013 b \u2013The last but one node computation involving only one register<\/li>\r\n \t
          • R1:= R1 + R0 - The root involving two registers.<\/li>\r\n<\/ul>\r\n \r\n\r\nWith a wide set of instructions we could use all combinations and arrive at the optimum cost of computing every node in a very effective manner.\r\n\r\n \r\n

            Summary<\/strong>: In this module we discussed the DAG based approach to code generation which involves calling recursively the gencode() algorithm using 5 cases. We also looked at the dynamic programming approach to code generation involving cost vector computation at every node and using a bottom- up strategy to accumulate the cost to compute the root node. In the next module, we would look at a template based approach to code generation.<\/p>","rendered":"

            \n

            this module, we would try to understand the code generation algorithm from DAG after the DAG has been reordered and labeled. As another approach to code generation, we will discuss the Dynamic programming approach to code generation.<\/p>\n

             <\/p>\n

            32.1 Code generation from DAG<\/strong><\/p>\n

             <\/p>\n

            As discussed in the previous module, one of the ideas behind the DAG construction is code generation. The steps involved include reordering of the instructions, labeling the nodes with the number of registers required and use this information to generate target assembly language code.<\/p>\n

             <\/p>\n

            The code generation algorithm uses a recursive procedure on a labeled DAG. Considers code generation based on the labels assigned to the nodes. It uses two stacks, one register stack \u201crstack\u201d and another memory stack, \u201cmstack\u201d. Stack \u201crstack\u201d is used to allocate registers. Initially rstack contains all available registers. The algorithm retains the registers on rstack in the same order it has found them. The typical functions of the stack, like push(), pop() is used to rearrange the rstack and in addition, the algorithm uses a swap(rstack) function to interchange the top two registers on rstack.<\/p>\n

             <\/p>\n

            The algorithm, considers five different cases to generate code. They are discussed as follows:<\/p>\n

             <\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 0: <\/strong>This is a simple and terminating case of the recursive procedure. If, \u2019n\u2019 is a leaf and the leftmost child of its parent, we generate just a load instruction.<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 1: <\/strong>This is the situation when the right node is a leaf and the left node could be a sub-tree. In this case, we generate code to evaluate n1 into register R=top(rstack) followed by the instruction \u201cop name R\u201d.<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 2: <\/strong>The right sub-tree requires more registers than the left sub-tree. A sub-tree of the form where n1 can be evaluated without stores but n2 is harder to evaluate than n1 as itrequires more registers. For this case, swap the top two registers on rsatck, then evaluate n2 into R=top(rstack).We remove R from rstack and evaluate n1 into S = top(rstack). Then we generate the instruction \u201cop R, S\u201d, which produce the value of \u201cn\u201d in register S. Another call to swap leaves rstack as it was, upon this call code generation begins.<\/p>\n

             <\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 3<\/strong>: It is similar to case 2 except that here the left sub-tree is harder and is evaluated first. There is no need to swap registers here.<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Case 4: <\/strong>It occurs when both sub-trees require r or more registers to evaluate without stores. Since we must use a temporary memory location, we first evaluate the right sub-tree into the temporary T, then the left sub-tree, and finally the root. All these cases are discussed in Algorithm 32.1 to generate code from the DAG and the algorithm is named gencode(n) where \u2018n\u2019 is the root of the DAG which is passed as argument<\/p>\n<\/div>\n

            \n

            Procedure gencode(n);<\/p>\n

            Begin<\/p>\n

             <\/p>\n

            \/* case 0 *\/<\/p>\n

             <\/p>\n

            if n is a left leaf representing operand name and n is the leftmost child of its parent then print \u2018MOV\u2019 || name || \u2018.\u2019 || top(rstack)<\/p>\n

             <\/p>\n

            else if n is an interior node with operator op, left child n1, and right child n2 then \/* case 1 *\/<\/p>\n

            if label(n2) = 0 then begin<\/p>\n

            let name be the operand represented by n2;<\/p>\n

            gencode(n1);<\/p>\n

            print op || name || \u2018.\u2019 || top(rstack)<\/p>\n

            end<\/p>\n

             <\/p>\n

            \/* case 2 *\/<\/p>\n

            else if 1 \u2264 label (n1) < label(n2) and label(n1) < r then begin swap(rstack);<\/p>\n

            gencode(n2 );<\/p>\n

             <\/p>\n

            R := pop(rstack); \/* n2 was evaluated into register R *\/ gencode(n1);<\/p>\n

            print op || R || \u2018.\u2019 || top(rstack);<\/p>\n

             <\/p>\n

            push(rstack,R);<\/p>\n

            swap(rstack)<\/p>\n

            end<\/p>\n

             <\/p>\n

            \/* case 3 *\/<\/p>\n

            else if 1 \u2264 label (n2) < label(n1) and label(n2) < r then begin gencode(n1);<\/p>\n

            R := pop(rstack); \/* n1 was evaluated into register R *\/ gencode(n2);<\/p>\n

            print op || R || \u2018.\u2019 || top(rstack);<\/p>\n

            push(rstack,R);<\/p>\n

            end<\/p>\n

             <\/p>\n

            \/* case 4, both labels \u2265 r, the total number of registers *\/ else begin<\/p>\n

            gencode(n2 );<\/p>\n

            T := pop(tstack);<\/p>\n

            Print \u2018MOV\u2019 || top(rstack) || \u2018.\u2019 || T;<\/p>\n

            gencode(n1);<\/p>\n

            push(rstack,R);<\/p>\n

            print op || T || \u2018.\u2019 || top(rstack)<\/p>\n

            end<\/p>\n

            end<\/p>\n

             <\/p>\n

            Case 1 checks if the right child of an interior node is a leaf node. If it is a leaf node, then we call the function recursively with the left child as the root node. To evaluate and finally conclude this case with generating an \u201cop\u201d instruction. Case 2 is evaluated if the right sub-tree is heavy. If it is heavy, we swap the register stack so that the right sub\u2014tree is evaluated into the register which<\/p>\n<\/div>\n

             <\/p>\n

            is beneath the top register. We then recursively call gencode() function with the right sub -tree\u2019s node as root and we remove this register from rstack. We then call gencode() to evaluate the left sub-tree and use the top of the stack register. After that we swap the rstack contents to ensure the initial rstack content is retained. Case 3 is just the opposite of Case 2 and since in this context, we evaluate first the left sub-tree, the rstack contents are used as it is and not swapped. Case 4 is the situation when there are no registers in the rstack. We use a memory based operation where the operands would be memory to compute.<\/p>\n

             <\/p>\n

            Consider the DAG given in figure 32.1 as an example for code generation.<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

            The nodes of the DAG are labeled with the number of registers that it requires for computation. Assume that there are two register R0 and R1 with R0 on the top of the stack. The algorithm gencode() is called with the root node t4. The children of this node are t1 and t3. Since the label of t3 is greater, case 2 is initiated. This calls recursively gencode() with t3 after swapping the register stack. This results in its left child being a leaf node and hence falls under case 0. Case 0 is a load instruction and the value \u2018e\u2019 is loaded into R1. After this call returns it goes to the next step of the previous call, which removes the register R1 from rstack using the pop() command and the gencode function is called with the right sub-tree node, which is t2. This falls under case 1 as the label of the right leaf node is 0 and thus gencode is again called with node \u2018c\u2019. This again falls under case 0 and initiates a load instruction into R0 and returns. The next instruction is the next step of Case1 where an operator instruction is issued followed by the next instruction of case 2 where a SUB instruction is issued and the register is pushed and then swapped. Proceeding in a similar fashion we get the following code.<\/p>\n

             <\/p>\n

             <\/p>\n

            gencode(t4) [R1 R0] \/\/ case 2
            \ngencode(t3) [R0 R1] \/\/ case 3
            \ngencode(e) [R0R1] \/\/ case 0
            \nprint MOV e, R1
            \ngencode(t2) [R0] \/\/ case 1
            \ngencode(c) [R0] \/\/ case 0
            \nprint MOV c, R0
            \nprint ADD d, R0
            \nprint SUB R0, R1
            \ngencode(t1) [R0] \/\/ case 1
            \ngencode(a) [R0] \/\/ case 0
            \nprint MOV a, R0
            \nprint ADD b, R0
            \nprint SUB R1, R0<\/p>\n

            \n

            32.2 Multi-register operation<\/strong><\/p>\n

             <\/p>\n

            The code generation algorithm gencode() discussed uses only one register by default. The algorithm could be made to use two registers for regular operations by changing the labeling algorithm as discussed in the previous module as follows:<\/p>\n

             <\/p>\n

            The algorithm could be used to exploit the algebraic properties where we could swap left and right nodes effectively to use the code generation algorithm. This will also avoid recomputation of common sub-expression.<\/p>\n

             <\/p>\n

            32.3 Dynamic programming<\/strong><\/p>\n

             <\/p>\n

            Constructing a DAG for code generation creates one more approach to code generation. We can adopt a bottom- up approach to compute the cost of evaluating each node using a dynamic programming approach. Dynamic programming is an algorithmic design strategy where all possible directions are explored and the least cost is chosen for computing at every point of time. For code generation, in order to compute the code for each node, all possibilities in terms of instruction cost is evaluated and the least cost to compute each node is used. For each node \u2018n\u2019 of the expression tree T an array C<\/em> of costs, in which the ith component C[i] is the optimal cost of computing the sub-tree S rooted at \u2018n\u2019 into a register, assuming i registers are available for the computation<\/p>\n

             <\/p>\n

            After computing the cost vector, we traverse the tree T, and use the cost vectors to determine which sub-trees of T must be computed into memory or register. Traverse each tree using the cost vectors and associated instructions to generate the final target code. The code for the sub-trees computed into memory locations is generated first.<\/p>\n

             <\/p>\n

            To consider the dynamic programming approach to code generation the following assumptions are made:<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 There are only two registers available for computation<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Cost of computing a node which is in memory involves 0<\/p>\n

            \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The following instructions are alone permitted where the LHS corresponds to target and<\/p>\n

             <\/p>\n

            the RHS corresponds to the source.<\/p>\n

            \u2013\u00a0 Ri := Mj – Loads the memory content Mj into register Ri<\/p>\n

            \u2013\u00a0 Ri := Ri op Rj \u2013 operates Ri and Rj and the result is available in Ri<\/p>\n<\/div>\n

            \u2013\u00a0 Ri := Ri op Mj – operates Ri and Mj and the result is available in Ri<\/p>\n

            \u2013\u00a0 Ri := Rj \u2013 Loads the register content Rj into register Ri<\/p>\n

            \u2013\u00a0 Mi := Ri \u2013 Loads the register content Ri into memory Mi<\/p>\n

             <\/p>\n

            \"\"<\/p>\n

            Figure 32.2 Syntax tree for the example expression.<\/strong><\/p>\n

             <\/p>\n

            Each node has a cost vector that has 3 values which indicate the cost of computing that node with 0, 1 and 2 registers. The computation for various cases is detailed below:<\/p>\n

             <\/p>\n

              \n
            • Leaf nodes \u2013 All leaf nodes have the same cost vector (0, 1, 1)<\/li>\n<\/ul>\n

              \u2013\u00a0 Cost of moving a variable with no registers is 0 \u2013 variable in register itself<\/p>\n

              \u2013\u00a0 Cost of moving a variable with 1\/ 2 registers is 1 using the instruction Ri : = Mj<\/p>\n

              \u2013\u00a0 Cost of leaf nodes are just (0, 1, 1) using no register, 1 register, 2 registers<\/p>\n

                \n
              • Last but one node \u2013 find all possible and choose the least cost<\/li>\n<\/ul>\n

                \"\"<\/p>\n

                \n

                Cost vector of the last but one level node is (3, 2, 2) as this value is the minimum based on individual node computation<\/p>\n

                 <\/p>\n

                \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Computing the * node.<\/p>\n

                \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Using 0 registers<\/p>\n

                 <\/p>\n

                Ri = Ri op Mj (costs 1)<\/p>\n

                 <\/p>\n

                Mj = Ri\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (costs 1)<\/p>\n

                 <\/p>\n

                The cost to compute the children nodes of * is 1 + 3. Thus resulting in 6.<\/p>\n

                 <\/p>\n

                (or)<\/p>\n

                 <\/p>\n

                Ri = Ri op Rj (costs 1)<\/p>\n

                 <\/p>\n

                Mj = Ri\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (costs 1)<\/p>\n

                 <\/p>\n

                The cost to compute the children nodes of * is 1+2. Thus resulting in a total of 5 and between 5 and 6 we choose 5 as the cost of the first quantity.<\/p>\n

                 <\/p>\n

                \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Using 1 registers<\/p>\n

                 <\/p>\n

                Ri = Ri op Mj (costs 1)<\/p>\n

                 <\/p>\n

                The cost to compute the children nodes of * is 1 + 3. Thus resulting in 5 as the instruction Ri op Mj is supported which expects the RHS node to be in memory.<\/p>\n<\/div>\n

                  \n
                • Using 2 registers<\/li>\n<\/ul>\n

                   <\/p>\n

                  Ri = Ri op Rj (costs 1)<\/p>\n

                   <\/p>\n

                  The cost to compute the children nodes of * is 1+2. If the computation involves two registers it could be computed using one register also. Thus resulting in a total of 4 for two registers and between 5 and 4 we choose 4 as the cost of the third cost vector C.<\/p>\n

                   <\/p>\n

                  The following is the logic for the computation of the cost vector for the root.<\/p>\n

                    \n
                  • Compute the left subtree with two registers available into register R0, compute the right subtree with one register available into register R1, and use the instruction ADD R0, R0, R1 to compute the root. This sequence has cost 2+5<\/em>+1=8.<\/li>\n
                  • Compute the right subtree with two registers available into R l , compute the left subtree with one register available into R0, and use the instruction ADD R0, R0, R1. This sequence has cost 4+2+1=7.<\/li>\n
                  • Compute the right subtree into memory location M, compute the left subtree with two registers available into register RO, and use the instruction ADD R0, R0, M. This sequence has cost 5+2+1=8<\/li>\n<\/ul>\n

                    This tree is traversed from bottom to top to generate code as follows:<\/p>\n

                      \n
                    • R0 := c \u2013 the value is a memory based operation to move \u2018c\u2019 into R0<\/li>\n
                    • R1 := d \u2013 same as \u2018c\u2019 and we use another register to move \u2018d\u2019 into R1<\/li>\n
                    • R1 := R1\/e \u2013 Only one register is used to compute this node and the result is in R1<\/li>\n
                    • R0 := R0 * R1 \u2013 Two registers resulted in a lower cost and we use that<\/li>\n
                    • R1 := a \u2013 R1 is free and hence \u2018a\u2019 is loaded to R1<\/li>\n
                    • R1 := R1 \u2013 b \u2013The last but one node computation involving only one register<\/li>\n
                    • R1:= R1 + R0 – The root involving two registers.<\/li>\n<\/ul>\n

                       <\/p>\n

                      With a wide set of instructions we could use all combinations and arrive at the optimum cost of computing every node in a very effective manner.<\/p>\n

                       <\/p>\n

                      Summary<\/strong>: In this module we discussed the DAG based approach to code generation which involves calling recursively the gencode() algorithm using 5 cases. We also looked at the dynamic programming approach to code generation involving cost vector computation at every node and using a bottom- up strategy to accumulate the cost to compute the root node. In the next module, we would look at a template based approach to code generation.<\/p>\n","protected":false},"author":4,"menu_order":32,"template":"","meta":{"_acf_changed":false,"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-rajeswari-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-272","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\/272","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\/272\/revisions"}],"predecessor-version":[{"id":277,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/272\/revisions\/277"}],"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\/272\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=272"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=272"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=272"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=272"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}