{"id":241,"date":"2018-07-20T09:19:08","date_gmt":"2018-07-20T09:19:08","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=241"},"modified":"2018-07-20T09:19:41","modified_gmt":"2018-07-20T09:19:41","slug":"code-generator-introduction-and-basic-blocks","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/code-generator-introduction-and-basic-blocks\/","title":{"rendered":"Code Generator Introduction and Basic Blocks"},"content":{"raw":"

After discussing the various semantic rules necessary to convert every programming construct into three-address code, in this module, we will discuss the next phase of the compiler \u2013 Code generation. We will start this module by understanding the issues in generating code. As a first step in code generation, we will discuss the concept of basic blocks and flow graphs<\/p>\r\n \r\n\r\n28.1 Code Generation \u2013 Introduction<\/strong>\r\n\r\n \r\n

The position of the code generation module is shown in figure 28.1. As shown in figure 28.1, the front-end of the compiler delivers intermediate code as output after processing the lexical, syntactic and semantic phases. This intermediate code is used for code generation. The intermediate code could also be optimized and the optimized intermediate code could also be fed to the code generator.<\/p>\r\n\"\"\r\n

\r\n\r\nThe following are the expectations of the code generator:\r\n\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Code produced by compiler must be correct \u2013 The conversion from the source to the target language should preserve the semantics of the source program.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Code produced by compiler should be of high quality \u2013 The code generation algorithm should be aware of the instructions set of the target language. The code should be generated, by effectively using these target machine resources. Normally, heuristic techniques are used to generate good but suboptimal code, as optimal code generation is an undecidable problem.<\/p>\r\n \r\n

28.2 Issues in the Code Generator<\/strong><\/p>\r\n

<\/p>\r\n

The code generator needs to address so many issues before actually generating the code. The following are some of the issues and let us discuss each one of them in brief.<\/p>\r\n\r\n<\/div>\r\n

\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input to the code generator: The code generator gets the three-address code as input. The format in which this three-address code is fed as input need to be decided. The following are some of the ways of feeding input to the code generator.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Linear \u2013 The input could be a string of characters where we use postfix notation to express the input.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Tables \u2013 As discussed in the previous modules, the three-address code is typically represented using Quadruples, Triples or Indirect triples and this table could be served as input<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Non-linear \u2013 Abstract Syntax tree (AST) or Directed Acyclic Graph (DAG) could be used as input to the code generator after converting the input into AST or DAG representation\u00a0 In addition to the input, symbol table information need to be given to the code generator. The format in which symbol table needs to be available to the code generator needs to be decided.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Target Program Code: The back-end code generator of a compiler may generate different forms of code, depending on the requirements. The target program code needs to be specified as assembly language or machine language. The following are some of the forms<\/p>\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Absolute machine code \u2013 This code is directly executable\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Relocatable machine code \u2013 This is a relocatable machine language and is normally available as an object files\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Assembly language \u2013 This is available in any assembly language which depends on the target machine and later an assembler converts this to machine language.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Byte code forms for interpreters \u2013 Java virtual machine has the write once and run anywhere concept where the output should be in Byte code.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Target Machine: Implementing code generation requires thorough understanding of the target machine architecture and its instruction set. Consider a hypothetical machine with the following features:<\/p>\r\n \r\n\r\n\u2013\u00a0 The instructions are byte-addressable where a word is 4 bytes\r\n\r\n\u2013\u00a0 Has n<\/em> general purpose registers R0<\/strong>, R1<\/strong>, \u2026, R<\/strong>n-<\/em>1\r\n\r\n\u2013\u00a0 Instructions are of Two-address, ones of the form\r\n\r\nop source<\/em>, destination\u00a0<\/em>where op stands for op-codes.\r\n\r\n<\/div>\r\n \r\n\r\nFor example\r\n\r\n \r\n\r\nMOV <\/strong>(move content of source<\/em> to destination<\/em>)\r\n\r\nADD <\/strong>(add content of source<\/em> to destination<\/em>)\r\n\r\nSUB <\/strong>(subtract content of source<\/em> from destination<\/em>)\r\n\r\n\"\"\r\n\r\n\"\"\r\n

\r\n\r\nThe following would be the instructions with a total cost of 6 (2+2+2):\r\n\r\n \r\n\r\nMOV <\/strong>y,R0<\/strong>\r\n\r\nADD <\/strong>z,R0<\/strong>\r\n\r\nMOV R0,<\/strong>x\r\n\r\n \r\n\r\nConsider another instruction a:=a+1<\/strong> and if we adopt the same strategy to convert this instruction to target code, the following would be the result with a cost of 6 (2+2+2)\u201d\r\n\r\n \r\n\r\nMOV a,R0<\/strong>\r\n\r\nADD #1,R0<\/strong>\r\n\r\nMOV R0,a<\/strong>\r\n\r\n \r\n\r\nIf we replace this with the following instruction, the cost would be 3 (1 + 1 +1) which is \u201c1\u201d each for ADD, #1, a\r\n\r\n \r\n\r\nADD #1,a<\/strong>\r\n\r\n \r\n\r\nOn the other hand, if this is replaced by the following instruction the cost would be 2 (1 for INC and 1 for \u201ca\u201d)\r\n\r\n \r\n\r\nINC a<\/strong>\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Instruction Selection \u2013 The choice of instructions also could change based on the addressing Modes\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Suppose we translate a:=b+c<\/strong> into\r\n\r\n \r\n\r\nMOV b,R0 <\/strong>\r\n\r\nADD c,R0 <\/strong>\r\n\r\nMOV R0,a<\/strong>\r\n\r\n \r\n\r\nThe cost of this would be 6 (2 + 2 +2)\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 On the other hand, assuming addresses of a<\/strong>, b<\/strong>, and c<\/strong> are stored in R0<\/strong>, R1<\/strong>, and R2<\/strong>\r\n\r\n \r\n\r\nMOV *R1,*R0<\/strong>\r\n\r\n ADD *R2,*R0<\/strong>\r\n\r\n \r\n\r\nThe cost of this would be 2 (1 +1) which is just due to the MOV and ADD instructions\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Consider, R1<\/strong> and R2<\/strong> contain values of b<\/strong> and c<\/strong>\r\n\r\n \r\n\r\nADD R2,R1 <\/strong>\r\n\r\nMOV R1,a<\/strong>\r\n\r\n \r\n\r\nWould incur a cost of 3 (1 + 2) for ADD, MOV.\r\n\r\n<\/div>\r\n
    \r\n \t
  • Need for Global Code optimization<\/li>\r\n<\/ul>\r\nThis is the next issue in code generation. Consider the instruction and its corresponding three-address code as given in the table 28.3(a):\r\n\r\n \r\n\r\nTable 28.3 a \u2013 Instruction and code\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    Instruction<\/strong><\/td>\r\nCode<\/strong><\/td>\r\n<\/tr>\r\n
    x<\/em>:=<\/strong>y<\/em>+<\/strong>z<\/em><\/td>\r\nMOV<\/strong>y<\/em>,R0<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nADD <\/strong>z<\/em>,R0<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nMOV R0,<\/strong>x<\/em><\/td>\r\n<\/tr>\r\n
    <\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\nConsider the following sequence of instructions and supposing we use the same logic to translate, then we will end up in the table 28.3 (b).\r\n\r\n \r\n\r\nTable 28.3 (b) \u2013 Sequence of Instructions and code\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
    Instruction<\/strong><\/td>\r\nCode<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\n<\/td>\r\n<\/tr>\r\n
    a:=b+c<\/strong><\/td>\r\nMOVa,R0<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nADD b,R0<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nMOV R0,a<\/strong><\/td>\r\n<\/tr>\r\n
    d:=a+e<\/strong><\/td>\r\nMOV a,R0\u00a0 ------------ Redundant as R0 is used<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nADD e,R0<\/strong><\/td>\r\n<\/tr>\r\n
    <\/td>\r\nMOV R0,d<\/strong><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n

    As given in the Table 28.3 (b), register R0 already had the value of \u2018a\u2019 according to the previous computation and hence this MOV instruction as indicated is redundant and this calls for Global code optimization.<\/p>\r\n\r\n

      \r\n \t
    • Register allocation and Assignment<\/li>\r\n<\/ul>\r\n

      One of the important issues in code generation is register allocations. The number of registers in any architecture is limited to match the number of variable in a high- level program. Efficient utilization of the limited set of registers is important to generate good code. Registers are assigned by<\/p>\r\n \r\n\r\n\u2013 Register allocation<\/em> to select the set of variables that will reside in registers at a point in the code\r\n\r\n\u2013\u00a0 Register assignment<\/em> to pick the specific register that a variable will reside in\r\n\r\n \r\n

      However, finding an optimal register assignment in general is NP-complete. Consider the table 28.3 (c) that has the sequence of instructions and their corresponding three-address code.<\/p>\r\n\"\"\r\n\r\n28.3 Basic Blocks and Flowgraphs<\/strong>\r\n\r\n \r\n

      To handle all the issues in the code generation process, we need to construct basic blocks and flow graphs from the sequence of three-address code. Basic blocks are computation sequences and they form the node of a flow graph. Flow graph is a graphical representation of three-address code where nodes are the basic blocks and edges indicate the flow of control between basic blocks. The primary objective of flow graphs is code optimization include optimal register allocation.<\/p>\r\n \r\n

      A flow graph<\/em> is a graphical depiction of a sequence of instructions. A flow graph can be defined at the intermediate code level or target code level. Consider the following example at the final code level and the corresponding flow graph of Figure 28.2.<\/p>\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

      \r\n\r\nFigure 28.3 Flow graph with basic blocks highlighted\r\n\r\n \r\n\r\nIn a flow graph, suppose there is an edge from basic block B1 to B2 as B<\/em>1\u00aeB<\/em>2, then B<\/em>1 is a predecessor <\/em>of B<\/em>2 and B<\/em>2 is a successor <\/em>of B<\/em>1\r\n\r\n \r\n\r\nIn figure 28.3, we have grouped the statements into basic blocks 1, 2, 3 and the manner to do it is given algorithm 28.1\r\n\r\n \r\n\r\nAlgorithm 28.1 Basic block construction\r\n\r\n \r\n\r\nInput<\/em>:\u00a0 A sequence of three-address statements\r\n\r\n<\/div>\r\n
      \r\n\r\nOutput<\/em>:\u00a0 \u00a0A\u00a0 \u00a0 \u00a0list\u00a0 of\u00a0 basic\u00a0 blocks\u00a0 with each\r\n\r\nthree-address statementin\u00a0 exactly one block<\/span>\r\n\r\n<\/div>\r\n
      \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Determine the set of leaders<\/em>, the first statements if 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
      \r\n\r\n2.\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 of\u00a0 next\u00a0 the\u00a0 \u00a0leader leader\u00a0\u00a0\u00a0 or\u00a0 and\u00a0 the all end\u00a0\u00a0of the program<\/span>\r\n\r\n<\/div>\r\n
      \r\n\r\nFrom algorithm 28.1, it is evident that the first step is to identify the set of leaders and group the statements between a pair of leaders into a basic block. An example of this is given in the next module\r\n\r\n<\/div>\r\n \r\n\r\nSummary<\/strong>: In this module, we understood the need for code generation and the various issues that need to be handled in code generation. Basic block and algorithm for basic block creation from three address \/ final code was discussed.","rendered":"

      After discussing the various semantic rules necessary to convert every programming construct into three-address code, in this module, we will discuss the next phase of the compiler \u2013 Code generation. We will start this module by understanding the issues in generating code. As a first step in code generation, we will discuss the concept of basic blocks and flow graphs<\/p>\n

       <\/p>\n

      28.1 Code Generation \u2013 Introduction<\/strong><\/p>\n

       <\/p>\n

      The position of the code generation module is shown in figure 28.1. As shown in figure 28.1, the front-end of the compiler delivers intermediate code as output after processing the lexical, syntactic and semantic phases. This intermediate code is used for code generation. The intermediate code could also be optimized and the optimized intermediate code could also be fed to the code generator.<\/p>\n

      \"\"<\/p>\n

      \n

      The following are the expectations of the code generator:<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Code produced by compiler must be correct \u2013 The conversion from the source to the target language should preserve the semantics of the source program.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Code produced by compiler should be of high quality \u2013 The code generation algorithm should be aware of the instructions set of the target language. The code should be generated, by effectively using these target machine resources. Normally, heuristic techniques are used to generate good but suboptimal code, as optimal code generation is an undecidable problem.<\/p>\n

       <\/p>\n

      28.2 Issues in the Code Generator<\/strong><\/p>\n

      \n

      The code generator needs to address so many issues before actually generating the code. The following are some of the issues and let us discuss each one of them in brief.<\/p>\n<\/div>\n

      \n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Input to the code generator: The code generator gets the three-address code as input. The format in which this three-address code is fed as input need to be decided. The following are some of the ways of feeding input to the code generator.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Linear \u2013 The input could be a string of characters where we use postfix notation to express the input.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Tables \u2013 As discussed in the previous modules, the three-address code is typically represented using Quadruples, Triples or Indirect triples and this table could be served as input<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Non-linear \u2013 Abstract Syntax tree (AST) or Directed Acyclic Graph (DAG) could be used as input to the code generator after converting the input into AST or DAG representation\u00a0 In addition to the input, symbol table information need to be given to the code generator. The format in which symbol table needs to be available to the code generator needs to be decided.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Target Program Code: The back-end code generator of a compiler may generate different forms of code, depending on the requirements. The target program code needs to be specified as assembly language or machine language. The following are some of the forms<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Absolute machine code \u2013 This code is directly executable<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Relocatable machine code \u2013 This is a relocatable machine language and is normally available as an object files<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Assembly language \u2013 This is available in any assembly language which depends on the target machine and later an assembler converts this to machine language.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Byte code forms for interpreters \u2013 Java virtual machine has the write once and run anywhere concept where the output should be in Byte code.<\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Target Machine: Implementing code generation requires thorough understanding of the target machine architecture and its instruction set. Consider a hypothetical machine with the following features:<\/p>\n

       <\/p>\n

      \u2013\u00a0 The instructions are byte-addressable where a word is 4 bytes<\/p>\n

      \u2013\u00a0 Has n<\/em> general purpose registers R0<\/strong>, R1<\/strong>, \u2026, R<\/strong>n-<\/em>1<\/p>\n

      \u2013\u00a0 Instructions are of Two-address, ones of the form<\/p>\n

      op source<\/em>, destination\u00a0<\/em>where op stands for op-codes.<\/p>\n<\/div>\n

       <\/p>\n

      For example<\/p>\n

       <\/p>\n

      MOV <\/strong>(move content of source<\/em> to destination<\/em>)<\/p>\n

      ADD <\/strong>(add content of source<\/em> to destination<\/em>)<\/p>\n

      SUB <\/strong>(subtract content of source<\/em> from destination<\/em>)<\/p>\n

      \"\"<\/p>\n

      \"\"<\/p>\n

      \n

      The following would be the instructions with a total cost of 6 (2+2+2):<\/p>\n

       <\/p>\n

      MOV <\/strong>y,R0<\/strong><\/p>\n

      ADD <\/strong>z,R0<\/strong><\/p>\n

      MOV R0,<\/strong>x<\/p>\n

       <\/p>\n

      Consider another instruction a:=a+1<\/strong> and if we adopt the same strategy to convert this instruction to target code, the following would be the result with a cost of 6 (2+2+2)\u201d<\/p>\n

       <\/p>\n

      MOV a,R0<\/strong><\/p>\n

      ADD #1,R0<\/strong><\/p>\n

      MOV R0,a<\/strong><\/p>\n

       <\/p>\n

      If we replace this with the following instruction, the cost would be 3 (1 + 1 +1) which is \u201c1\u201d each for ADD, #1, a<\/p>\n

       <\/p>\n

      ADD #1,a<\/strong><\/p>\n

       <\/p>\n

      On the other hand, if this is replaced by the following instruction the cost would be 2 (1 for INC and 1 for \u201ca\u201d)<\/p>\n

       <\/p>\n

      INC a<\/strong><\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Instruction Selection \u2013 The choice of instructions also could change based on the addressing Modes<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Suppose we translate a:=b+c<\/strong> into<\/p>\n

       <\/p>\n

      MOV b,R0 <\/strong><\/p>\n

      ADD c,R0 <\/strong><\/p>\n

      MOV R0,a<\/strong><\/p>\n

       <\/p>\n

      The cost of this would be 6 (2 + 2 +2)<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 On the other hand, assuming addresses of a<\/strong>, b<\/strong>, and c<\/strong> are stored in R0<\/strong>, R1<\/strong>, and R2<\/strong><\/p>\n

       <\/p>\n

      MOV *R1,*R0<\/strong><\/p>\n

      ADD *R2,*R0<\/strong><\/p>\n

       <\/p>\n

      The cost of this would be 2 (1 +1) which is just due to the MOV and ADD instructions<\/p>\n

       <\/p>\n

      \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Consider, R1<\/strong> and R2<\/strong> contain values of b<\/strong> and c<\/strong><\/p>\n

       <\/p>\n

      ADD R2,R1 <\/strong><\/p>\n

      MOV R1,a<\/strong><\/p>\n

       <\/p>\n

      Would incur a cost of 3 (1 + 2) for ADD, MOV.<\/p>\n<\/div>\n

        \n
      • Need for Global Code optimization<\/li>\n<\/ul>\n

        This is the next issue in code generation. Consider the instruction and its corresponding three-address code as given in the table 28.3(a):<\/p>\n

         <\/p>\n

        Table 28.3 a \u2013 Instruction and code<\/p>\n

         <\/p>\n\n\n\n\n\n\n\n
        Instruction<\/strong><\/td>\nCode<\/strong><\/td>\n<\/tr>\n
        x<\/em>:=<\/strong>y<\/em>+<\/strong>z<\/em><\/td>\nMOV<\/strong>y<\/em>,R0<\/strong><\/td>\n<\/tr>\n
        <\/td>\nADD <\/strong>z<\/em>,R0<\/strong><\/td>\n<\/tr>\n
        <\/td>\nMOV R0,<\/strong>x<\/em><\/td>\n<\/tr>\n
        <\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

         <\/p>\n

        Consider the following sequence of instructions and supposing we use the same logic to translate, then we will end up in the table 28.3 (b).<\/p>\n

         <\/p>\n

        Table 28.3 (b) \u2013 Sequence of Instructions and code<\/p>\n

         <\/p>\n\n\n\n\n\n\n\n\n\n\n
        Instruction<\/strong><\/td>\nCode<\/strong><\/td>\n<\/tr>\n
        <\/td>\n<\/td>\n<\/tr>\n
        a:=b+c<\/strong><\/td>\nMOVa,R0<\/strong><\/td>\n<\/tr>\n
        <\/td>\nADD b,R0<\/strong><\/td>\n<\/tr>\n
        <\/td>\nMOV R0,a<\/strong><\/td>\n<\/tr>\n
        d:=a+e<\/strong><\/td>\nMOV a,R0\u00a0 ———— Redundant as R0 is used<\/strong><\/td>\n<\/tr>\n
        <\/td>\nADD e,R0<\/strong><\/td>\n<\/tr>\n
        <\/td>\nMOV R0,d<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

         <\/p>\n

        As given in the Table 28.3 (b), register R0 already had the value of \u2018a\u2019 according to the previous computation and hence this MOV instruction as indicated is redundant and this calls for Global code optimization.<\/p>\n

          \n
        • Register allocation and Assignment<\/li>\n<\/ul>\n

          One of the important issues in code generation is register allocations. The number of registers in any architecture is limited to match the number of variable in a high- level program. Efficient utilization of the limited set of registers is important to generate good code. Registers are assigned by<\/p>\n

           <\/p>\n

          \u2013 Register allocation<\/em> to select the set of variables that will reside in registers at a point in the code<\/p>\n

          \u2013\u00a0 Register assignment<\/em> to pick the specific register that a variable will reside in<\/p>\n

           <\/p>\n

          However, finding an optimal register assignment in general is NP-complete. Consider the table 28.3 (c) that has the sequence of instructions and their corresponding three-address code.<\/p>\n

          \"\"<\/p>\n

          28.3 Basic Blocks and Flowgraphs<\/strong><\/p>\n

           <\/p>\n

          To handle all the issues in the code generation process, we need to construct basic blocks and flow graphs from the sequence of three-address code. Basic blocks are computation sequences and they form the node of a flow graph. Flow graph is a graphical representation of three-address code where nodes are the basic blocks and edges indicate the flow of control between basic blocks. The primary objective of flow graphs is code optimization include optimal register allocation.<\/p>\n

           <\/p>\n

          A flow graph<\/em> is a graphical depiction of a sequence of instructions. A flow graph can be defined at the intermediate code level or target code level. Consider the following example at the final code level and the corresponding flow graph of Figure 28.2.<\/p>\n

          \"\"<\/p>\n

           <\/p>\n

          \"\"<\/p>\n

           <\/p>\n

          \n

          Figure 28.3 Flow graph with basic blocks highlighted<\/p>\n

           <\/p>\n

          In a flow graph, suppose there is an edge from basic block B1 to B2 as B<\/em>1\u00aeB<\/em>2, then B<\/em>1 is a predecessor <\/em>of B<\/em>2 and B<\/em>2 is a successor <\/em>of B<\/em>1<\/p>\n

           <\/p>\n

          In figure 28.3, we have grouped the statements into basic blocks 1, 2, 3 and the manner to do it is given algorithm 28.1<\/p>\n

           <\/p>\n

          Algorithm 28.1 Basic block construction<\/p>\n

           <\/p>\n

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

          \n

          Output<\/em>:\u00a0 \u00a0A\u00a0 \u00a0 \u00a0list\u00a0 of\u00a0 basic\u00a0 blocks\u00a0 with each<\/p>\n

          three-address statementin\u00a0 exactly one block<\/span><\/p>\n<\/div>\n

          \n

          1.\u00a0\u00a0\u00a0\u00a0\u00a0 Determine the set of leaders<\/em>, the first statements if 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

           <\/p>\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 of\u00a0 next\u00a0 the\u00a0 \u00a0leader leader\u00a0\u00a0\u00a0 or\u00a0 and\u00a0 the all end\u00a0\u00a0of the program<\/span><\/p>\n<\/div>\n

          \n

          From algorithm 28.1, it is evident that the first step is to identify the set of leaders and group the statements between a pair of leaders into a basic block. An example of this is given in the next module<\/p>\n<\/div>\n

           <\/p>\n

          Summary<\/strong>: In this module, we understood the need for code generation and the various issues that need to be handled in code generation. Basic block and algorithm for basic block creation from three address \/ final code was discussed.<\/p>\n","protected":false},"author":4,"menu_order":28,"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-241","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\/241","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\/241\/revisions"}],"predecessor-version":[{"id":249,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/241\/revisions\/249"}],"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\/241\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=241"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=241"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=241"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}