{"id":278,"date":"2018-07-20T10:54:10","date_gmt":"2018-07-20T10:54:10","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=278"},"modified":"2018-07-20T10:54:25","modified_gmt":"2018-07-20T10:54:25","slug":"code-generation-tree-rewriting-and-introduction-to-code-optimization","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/code-generation-tree-rewriting-and-introduction-to-code-optimization\/","title":{"rendered":"Code Generation Tree Rewriting and Introduction to Code Optimization"},"content":{"raw":"

In this module, we learn to generate code using a template based approach. The template based approach to code generation is preceded by tree rewriting. We will also learn to understand the need for a code optimizer<\/p>\r\n \r\n\r\n33.1 Code-Gene rator generators<\/strong>\r\n\r\n \r\n

We have already seen three approaches to code generation namely, simple code generator, DAG based approach and dynamic programming strategy for code generation. All these approaches start from the scratch to generate code. Instead of this approach, we could use a black box based approach, where the black box would generate code if the input is given in a particular format using a template based approach. We need to however, convert o ur input to the input format of the code generator. The flow of the data is shown below:<\/p>\r\n \r\n\r\nInput instruction \u00e0 Standard format \u00e0 Template based code generator \u00e0 code\r\n\r\n \r\n

The steps involved in any code generation approach would include p icking an evaluation order, assigning registers and selecting appropriate target- language instructions and these steps are done in this method also with an addition of converting the input to a standardized representation.<\/p>\r\n \r\n\r\n33.2Code-generation by tree rewriting<\/strong>\r\n\r\n \r\n\r\nLet us assume that the evaluation order and registers allocation are completed, then the intermediate language could be converted to a representation as a tree. The tree should correspond to one of the pre-defined template. After matching with the template, there is a predefined code for every tree and code is generated. The sequence of flow for the code-generator is given in Figure 33.1.\r\n\r\n\"\"\r\n\r\n \r\n

\r\n\r\nInput tree is reduced into a single node by applying a sequence of tree-rewriting rules. The tree-writing rules is a translation scheme. The rewriting translation scheme has the following format:\r\n\r\n<\/div>\r\n \r\n\r\nReplacement \u2190 template {action}\r\n\r\n \r\n\r\nThe LHS which is a Replacement is the reduction of the template and the RHS will have a tree representation of the input. Replacement is a single node of the tree and template is a tree. The action will be the code fragment that is to be generated. Table 33.1 discusses few tree-writing rules and their corresponding target code\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\nThe RHS is the expression \u201cb+1\u201d and hence the right sub-tree corresponds to Mb which is added to constant 1. The root of the tree is the assignment operator. The LHS corresponds to a[i]. To compute a[i] we first index the variable \u2018i' using the stack pointer register and using the base address of \u2018a\u2019 using the constant Ca we use the \u201cind\u201d to indicate it is indexed operation and this forms the left sub-tree. The corresponding code for the above expression is given below which is generated by applying the rules as given in Table 33.1\r\n\r\n \r\n
    \r\n \t
  • Apply rule 1: MOV #a, R0<\/li>\r\n \t
  • Apply rule 6: ADD SP, R0<\/li>\r\n \t
  • Apply rule 7: ADD i(SP), R0<\/li>\r\n \t
  • Apply rule 2: MOV b, R1<\/li>\r\n \t
  • Apply rule 8: INC R1<\/li>\r\n \t
  • Apply rule 4: MOV R1, *R0<\/li>\r\n<\/ul>\r\nThe same tree rewriting rules can be implemented using syntax directed translation. The SDT for scheme construction and their corresponding target code is given below:\r\n\r\n \r\n
      \r\n \t
    • \u2022 regi \uf0e0 constc {MOV #c, Ri }\r\n\u2022 regi \uf0e0 mema {MOV a, Ri }\r\n\u2022 mem \uf0e0 := mem a regi {MOV Ri , a}<\/li>\r\n \t
    • \u00a0mem \uf0e0 := ind regi regj {MOV Rj , *Ri }\r\n\u2022 regi \uf0e0 ind + constc regj {MOV c(Rj ), Ri }\r\n\u2022 regi \uf0e0 + regi ind + constc regj {ADD c(Rj ), Ri }\r\n\u2022 regi \uf0e0 + regi regj {ADD Rj , Ri }\r\n\u2022 regi \uf0e0 + regi const1 {INC Ri }<\/li>\r\n<\/ul>\r\nAll the methods of code generations have its own advantages and disadvantages. Depending on the application we could use the corresponding algorithm for code generation.\r\n\r\n \r\n\r\n33.3Code Optimization<\/strong>\r\n\r\n \r\n

      The code that is being generated by the code generator using any one of the approaches discussed above need not be efficient. In addition the intermediate code that is generated also may not be efficient. DAG and instruction selection algorithms are used for getting efficient code. There is still some more means of improving the code generation. The following criteria are used for generating optimized code:<\/p>\r\n \r\n

        \r\n \t
      • The optimized code should have the most benefit for the least effort that is being put in optimizing<\/li>\r\n \t
      • Transformation should preserve the meaning of the program. This essentially emphasizes the fact that optimization should not change the output of the program\u00a0 After incorporating the code optimization, the code that is generated is transformed to an optimized one. The following are some of the properties of transformation that a code optimization algorithm should ensure:<\/span><\/li>\r\n \t
      • Transformation must on an average speed up the programs by a measurable amount. Optimization sometimes would slow down the program. Prevention should be taken for this.<\/li>\r\n \t
      • Transformation must be worth the effort. Time should not be spent in writing optimization code rather than the actual code of the problem\"\"<\/li>\r\n<\/ul>\r\n33.4 Position of the Code optimizer<\/strong>\r\n\r\n \r\n

        The code optimization algorithm needs to achieve a better performance. The code optimization could be implemented either at the intermediate code level or at the final code generation level. The position of the code optimizer is shown in figure 33.3.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n\"\"","rendered":"

        In this module, we learn to generate code using a template based approach. The template based approach to code generation is preceded by tree rewriting. We will also learn to understand the need for a code optimizer<\/p>\n

         <\/p>\n

        33.1 Code-Gene rator generators<\/strong><\/p>\n

         <\/p>\n

        We have already seen three approaches to code generation namely, simple code generator, DAG based approach and dynamic programming strategy for code generation. All these approaches start from the scratch to generate code. Instead of this approach, we could use a black box based approach, where the black box would generate code if the input is given in a particular format using a template based approach. We need to however, convert o ur input to the input format of the code generator. The flow of the data is shown below:<\/p>\n

         <\/p>\n

        Input instruction \u00e0 Standard format \u00e0 Template based code generator \u00e0 code<\/p>\n

         <\/p>\n

        The steps involved in any code generation approach would include p icking an evaluation order, assigning registers and selecting appropriate target- language instructions and these steps are done in this method also with an addition of converting the input to a standardized representation.<\/p>\n

         <\/p>\n

        33.2Code-generation by tree rewriting<\/strong><\/p>\n

         <\/p>\n

        Let us assume that the evaluation order and registers allocation are completed, then the intermediate language could be converted to a representation as a tree. The tree should correspond to one of the pre-defined template. After matching with the template, there is a predefined code for every tree and code is generated. The sequence of flow for the code-generator is given in Figure 33.1.<\/p>\n

        \"\"<\/p>\n

         <\/p>\n

        \n

        Input tree is reduced into a single node by applying a sequence of tree-rewriting rules. The tree-writing rules is a translation scheme. The rewriting translation scheme has the following format:<\/p>\n<\/div>\n

         <\/p>\n

        Replacement \u2190 template {action}<\/p>\n

         <\/p>\n

        The LHS which is a Replacement is the reduction of the template and the RHS will have a tree representation of the input. Replacement is a single node of the tree and template is a tree. The action will be the code fragment that is to be generated. Table 33.1 discusses few tree-writing rules and their corresponding target code<\/p>\n

        \"\"<\/p>\n

        \"\"<\/p>\n

        The RHS is the expression \u201cb+1\u201d and hence the right sub-tree corresponds to Mb which is added to constant 1. The root of the tree is the assignment operator. The LHS corresponds to a[i]. To compute a[i] we first index the variable \u2018i’ using the stack pointer register and using the base address of \u2018a\u2019 using the constant Ca we use the \u201cind\u201d to indicate it is indexed operation and this forms the left sub-tree. The corresponding code for the above expression is given below which is generated by applying the rules as given in Table 33.1<\/p>\n

         <\/p>\n

          \n
        • Apply rule 1: MOV #a, R0<\/li>\n
        • Apply rule 6: ADD SP, R0<\/li>\n
        • Apply rule 7: ADD i(SP), R0<\/li>\n
        • Apply rule 2: MOV b, R1<\/li>\n
        • Apply rule 8: INC R1<\/li>\n
        • Apply rule 4: MOV R1, *R0<\/li>\n<\/ul>\n

          The same tree rewriting rules can be implemented using syntax directed translation. The SDT for scheme construction and their corresponding target code is given below:<\/p>\n

           <\/p>\n

            \n
          • \u2022 regi \uf0e0 constc {MOV #c, Ri }
            \n\u2022 regi \uf0e0 mema {MOV a, Ri }
            \n\u2022 mem \uf0e0 := mem a regi {MOV Ri , a}<\/li>\n
          • \u00a0mem \uf0e0 := ind regi regj {MOV Rj , *Ri }
            \n\u2022 regi \uf0e0 ind + constc regj {MOV c(Rj ), Ri }
            \n\u2022 regi \uf0e0 + regi ind + constc regj {ADD c(Rj ), Ri }
            \n\u2022 regi \uf0e0 + regi regj {ADD Rj , Ri }
            \n\u2022 regi \uf0e0 + regi const1 {INC Ri }<\/li>\n<\/ul>\n

            All the methods of code generations have its own advantages and disadvantages. Depending on the application we could use the corresponding algorithm for code generation.<\/p>\n

             <\/p>\n

            33.3Code Optimization<\/strong><\/p>\n

             <\/p>\n

            The code that is being generated by the code generator using any one of the approaches discussed above need not be efficient. In addition the intermediate code that is generated also may not be efficient. DAG and instruction selection algorithms are used for getting efficient code. There is still some more means of improving the code generation. The following criteria are used for generating optimized code:<\/p>\n

             <\/p>\n

              \n
            • The optimized code should have the most benefit for the least effort that is being put in optimizing<\/li>\n
            • Transformation should preserve the meaning of the program. This essentially emphasizes the fact that optimization should not change the output of the program\u00a0 After incorporating the code optimization, the code that is generated is transformed to an optimized one. The following are some of the properties of transformation that a code optimization algorithm should ensure:<\/span><\/li>\n
            • Transformation must on an average speed up the programs by a measurable amount. Optimization sometimes would slow down the program. Prevention should be taken for this.<\/li>\n
            • Transformation must be worth the effort. Time should not be spent in writing optimization code rather than the actual code of the problem\"\"<\/li>\n<\/ul>\n

              33.4 Position of the Code optimizer<\/strong><\/p>\n

               <\/p>\n

              The code optimization algorithm needs to achieve a better performance. The code optimization could be implemented either at the intermediate code level or at the final code generation level. The position of the code optimizer is shown in figure 33.3.<\/p>\n

               <\/p>\n

              \"\"<\/p>\n

              \"\"<\/p>\n","protected":false},"author":4,"menu_order":33,"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-278","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\/278","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\/278\/revisions"}],"predecessor-version":[{"id":285,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/278\/revisions\/285"}],"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\/278\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=278"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=278"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=278"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=278"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}