{"id":340,"date":"2018-07-20T12:24:43","date_gmt":"2018-07-20T12:24:43","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=340"},"modified":"2018-07-20T12:30:23","modified_gmt":"2018-07-20T12:30:23","slug":"procedure-optimization","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/procedure-optimization\/","title":{"rendered":"Procedure Optimization"},"content":{"raw":"
\r\n\r\n \r\n

In this last module, we will try to understand the procedure optimization techniques. We shall discuss how a function could be optimized being recursive or non-recursive. We shall also discuss the concepts involved in Inter-procedural analysis.<\/p>\r\n \r\n\r\n40.1 Types of procedure optimizations<\/strong>\r\n\r\n \r\n

When it comes to procedure optimizations, we shall first indicate the definitions of the functions. A function could be recursive or non-recursive. Based on that, the following possibilities need to be considered while optimizing the functions.<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Tail-Call Optimization vs. Tail- Recursion Elimination \u2013 A call is said to be \u201ctail\u201d, if calling another function is the last statement of the current function . If the same is carried on in a recursive call, it is said to be tail- recursion\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Procedure Integration vs. In-line Expansion \u2013 Combining certain procedures to avoid the calling stack mechanism need to be studied as against in- line expansion of certain functions.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Leaf-routine Optimization vs. Shrink Wrapping \u2013 A function call is typically visualized as a call graph and if the leaf node is another function call we call this as a leaf-routine. This is done using a method called as shrink wrapping.<\/p>\r\n \r\n\r\nThis module discusses all of these types of procedures as part of optimization.\r\n\r\n \r\n\r\n40.2 Drawbacks of \u201cCall\u201d<\/strong>\r\n\r\n \r\n

Before we try to do optimization on procedures, let us first define the necessity to optimize these procedures. This can be well understood if we know the mechanism of a function call. In a calling convention, there are two players: a caller and a callee. A caller is one who calls another function and a callee is one who gets invoked by a function. The caller and callee need to handle the following:<\/p>\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Caller \u2013 need to take care of parameter passing, caller-saved register, return address branch after the callee returns\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Callee \u2013 This has two components: a prologue and epilogue that is to be done before and after executing the current function.\r\n\r\n\u2013\u00a0 prologue - save frame pointer, compute stack pointer, callee-saved register\r\n

\u2013\u00a0 epilogue : callee-saved register, return value, stack pointer, frame pointer, branch\u00a0\u00a0with this in the <\/span>caller \/ callee\u2019s domain, from an optimization <\/span>view point, there is very less chance to optimize between procedures. However, within a <\/span>procedure there is some space for optimization.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n40.3 Tail-call optimization vs Tail Recursion elimination<\/strong>\r\n\r\n \r\n

A tail-call is one where the last statement of a function call is a call to another function. If the same thing is applicable to a recursive function the situation is termed as tail recursion. Consider the following example:<\/p>\r\n \r\n\r\nvoid f(int x) {\r\n\r\n \r\n\r\n...\r\n\r\ng(x);\r\n\r\n(return;)\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

In the above example, function f() calls another function g(x) as the last step before return statement. Similarly, the following indicates tail-recursion, where f(x) is called as the last statement of the function f().<\/p>\r\n \r\n\r\nvoid f(int x) {\r\n\r\n...\r\n\r\n \r\n\r\nf(x);\r\n\r\n(return;)\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

Tail recursion results in procedure-call overhead. This can be eliminated by converting it to a loop and performing loop optimization. Consider the following function which has a tail-recursion:<\/p>\r\nvoid insert_node(int n, struct node *l)\r\n\r\n{\r\n\r\n \r\n\r\nif(n > l\u2192values)\r\n\r\nif(l\u2192next==null)\r\n\r\n \r\n\r\nmake_node(l,n);\r\n\r\nelse\r\n\r\ninsert_node(n,l\u2192next);\r\n\r\n}\r\n

The final call to insert_node could be eliminated by converting the recursive call to a loop as given below<\/p>\r\nvoid insert_node(int n, struct node *l)\r\n\r\n{\r\n\r\n \r\n\r\nLoop:\r\n\r\nif(n > l\u2192values)\r\n\r\n \r\n\r\nif(l\u2192next==null) make_node(p,n);\r\n\r\nelse { l = l\u2192next; goto Loop; }\r\n\r\n}\r\n\r\n \r\n

We introduced a label loop which is the point to continue and removed the recursive call and converted it to an iterative call.\u00a0Tail-call is termed as the routine performing the call does nothing after the call returns except return itself. During a tail call, the caller branches into the body of the other function and hence care should be taken care of <\/span>scope of variables and their return values. The following is an example of tail-call.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\nvoid make_node(struct node *p, int n)\r\n\r\n{\r\n\r\n \r\n\r\nL0: struct node *q = malloc(...);\r\n\r\np\u2192next = q;\r\n\r\n \r\n\r\n...\r\n\r\n}\r\n\r\nvoid insert_node(int n, struct node *l) {\r\n\r\nif(n > l\u2192value)\r\n\r\nif(l\u2192next==null) make_node(l, n);\r\n\r\n \r\n\r\n...\r\n\r\n}\r\n\r\nThe function insert_node() makes a tail-call to the function make_node.\r\n\r\n \r\n\r\nTail-call optimization is performed by following the steps given below:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Both procedure bodies should be visible to the compiler.\r\n\r\n\u2013\u00a0 It should be in the same compilation unit or should have their intermediate-code\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Need to know about callee.\r\n\r\n\u2013\u00a0 where it expects to find its parameters\r\n\r\n\u2013\u00a0 where to branch\r\n\r\n\u2013\u00a0 stack frame size.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the call by three things,\r\n\r\n\u2013 evaluation of the arguments and putting them where the callee expects to find them.\r\n\r\n\u2013\u00a0 if callee\u2019s stack frame is larger than caller\u2019s,\u00a0 an instruction that extends stack frame as difference.\r\n\r\n\u2013\u00a0 a branch to the beginning of the body of the callee\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Final step is to delete \u2018return\u2019 after a call. Consider the following example to perform tail-call optimization.\r\n\r\ninsert_node :\r\n\r\n{ ...\r\n\r\n \r\n\r\nr2 \u2190 r1\r\n\r\nr1 \u2190 r4\r\n\r\n \r\n\r\ncall make_node\r\n\r\nreturn;\r\n\r\n}\r\n\r\n \r\n\r\nThis will be converted to the following:\r\n\r\n \r\n\r\ninsert_node :\r\n\r\n<\/div>\r\n
\r\n\r\n{\r\n\r\n...\r\n\r\n \r\n\r\nr2 \u2190 r1\r\n\r\nr1 \u2190 r4\r\n\r\n \r\n\r\ngoto make_node\r\n\r\n}\r\n\r\n \r\n\r\nOn the other hand, the following sequence of steps is performed for removing tail-recursion.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the recursive call by\r\n\r\n\u2013\u00a0 assign proper values to the parameters, and\r\n\r\n\u2013\u00a0 branch to the beginning of the body of the procedure\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Delete \u2018return\u2019 after recursive call\r\n\r\nConsider one more example of tail-recursion elimination.\r\n\r\n \r\n\r\nvoid replace(int n) {\r\n\r\nif(n>=10) return;\r\n\r\n \r\n\r\nif(A[n]==0) A[n]=1;\r\n\r\nelse replace(n+1);\r\n\r\n}\r\n\r\n \r\n

In the above function replace(), the function gets called as the last step. The following is the optimized and tail-recursion eliminated function replace()<\/p>\r\nvoid replace(int n) {\r\n\r\nLoop:<\/strong>\r\n\r\nif(n>=10) return;\r\n\r\nif(A[n]==0) A[n]=1;\r\n\r\n \r\n\r\nelse {\r\n\r\nn = n+1;<\/strong>\r\n\r\n \r\n\r\ngoto Loop;<\/strong>\r\n\r\n}\r\n\r\n \r\n

We have introduced the label loop to go to the beginning of the function. The body of the else has multiple statements, which increments the variable \u2018n\u2019 and then a \u2018goto\u2019 to the beginning of the body of the function.<\/p>\r\n \r\n\r\n40. 4 Procedure Integration and Inlining<\/strong>\r\n\r\n \r\n

Procedure integration is also called as \u2018automatic inlining\u2019 where the body of the procedure is available in the caller\u2019s body itself. This replaces calls to the copy of the procedure body. A call can have unknown effect of the objects in the procedure on aliased variables and the local code gets expose and thus could enable more optimization. This is however better than \u2018inline\u2019 of C++ where it is optimized by user\u2019s intuition. The following are some of the issues with procedure integration:<\/p>\r\n\r\n<\/div>\r\n \r\n

\r\n
    \r\n \t
  • \u00a7\u00a0\u00a0 Range of inlined procedure \u2013 one has to save intermediate-code representations<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0\u00a0 Languages of caller and callee (cross compilation units)<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0 Need to handle the different languages and their various parameter passing conventions<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0 Need to handle the \u201cexternal language_name procedure_name<\/em>\u201d declaration to specify source languages<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0\u00a0 Saving intermediate-code of in- lined routines<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0\u00a0 Need to know the purpose of saving intermediate-code<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0 Need to compile a copy of the whole in- lined procedure<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0\u00a0 address of the procedure has been taken<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0\u00a0 calls from other compilation units, currently invisible and need to be addressed<\/li>\r\n \t
  • \u00a7\u00a0\u00a0\u00a0 Inlining on recursive procedures \u2013 To be avoided as running out of calls to them could be infinite process. It is valuable to inline once or twice<\/li>\r\n<\/ul>\r\nThe goal of inlining procedures should be to reduce e xecution time and avoid the calling stack mechanism. If every procedure is inlined then the following overhead need to be addressed:\r\n
      \r\n \t
    • \u00a7\u00a0\u00a0 decrease overhead costs of call<\/li>\r\n \t
    • \u00a7\u00a0\u00a0\u00a0 increase in object code size<\/li>\r\n \t
    • \u00a7\u00a0\u00a0\u00a0 more cache misses<\/li>\r\n \t
    • \u00a7\u00a0\u00a0\u00a0 compilation terminates only by exhaustion of resources<\/li>\r\n \t
    • \u00a7\u00a0\u00a0\u00a0\u00a0 We need heuristics or profiling feedback<\/li>\r\n<\/ul>\r\nThe following need to be considered while inlining procedures:\r\n
        \r\n \t
      • \u00a7\u00a0\u00a0\u00a0 The size of the procedure is small,<\/li>\r\n \t
      • \u00a7\u00a0\u00a0\u00a0 The procedure which is called less,<\/li>\r\n \t
      • \u00a7\u00a0\u00a0\u00a0\u00a0 The procedure that is called inside a loop<\/li>\r\n \t
      • \u00a7\u00a0\u00a0\u00a0\u00a0 The procedure whose call includes constant-valued parameter<\/li>\r\n<\/ul>\r\nTo perform inlining we need to handle the three major issues:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Different parameter passing conventions\r\n\r\n\u2013\u00a0 \u201cexternal language_name procedure_name<\/em>\u201d declaration\r\n\r\n\u2013\u00a0 call-by-reference vs. call-by-value\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Name conflicts\r\n\r\n\u2013\u00a0 conflicts between source symbol names need to be resolved\r\n\r\n\u2013\u00a0 detect conflicts and rename symbols of called procedure\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Static variables\r\n\r\n\u2013\u00a0 makes only one copy of static variable\r\n\r\n\u2013\u00a0 initialized once\r\n\r\n \r\n\r\n40.5 Leaf-Routine Optimization<\/strong>\r\n\r\n \r\n

        Leaf routine is similar to the statement that is appearing at the end of a function. Typically a call graph is constructed for a program to visualize the parameters that gets passed between the different functions. A leaf routine is one which is part of the leaf node in the call graph of a<\/p>\r\n\r\n<\/div>\r\n \r\n

        program. It is a routine that calls no procedures and hence many procedures are leaf routines. Leaf routine optimization, simplify the way parameters are passed, remove procedure prologue \/ epilogue and it is highly desirable with little effort. Leaf routine optimization is architecture-dependent. It depends on how many registers and stacks the procedure needs. It typically needs no more registers than caller-saved registers and thus requires no stack space with sufficient registers.<\/p>\r\n \r\n

        Shrink Wrapping is one of the leaf routine optimization methods. It involves, moving prologue and epilogue code to contain a smaller part of the procedure inside a loop and thus making many copies of codes. Figure 40.1 shows the prologue and epilogue in a flow graph and how that is typically brought closer using shrink wrapping.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

        \r\n\r\n40.6 Inte r-procedural optimization<\/strong>\r\n\r\n \r\n\r\nInter-procedural optimization could be attempted by performing inter-procedural analysis. This involves gathering information about the whole program instead of a single procedure. Inter-procedural Optimization is a program transformation method that involves more than one procedure in the program. Typically two Inter-procedural problems are solved: MOD Analysis and Alias Analysis. MOD analysis involves identification of modification to variables or side-effects that could be caused to the variables. Alias analysis is to verify whether the function or expressions are aliases to others.\r\n\r\n \r\n\r\n40.6.1 Modification and Reference Side-effect<\/strong>\r\n\r\n \r\n\r\nThis is one inter-procedural problem. Consider the following code:\r\n\r\n<\/div>\r\n
        \r\n\r\nS0:\r\n\r\n \r\n\r\nS1:\r\n\r\nCOMMON X,Y\r\n\r\n...\r\n\r\nDO I = 1, N\r\n\r\n \r\n\r\nCALL P\r\n\r\n \r\n\r\nX(I) = X(I) + Y(I)\r\n\r\n \r\n\r\nENDDO\r\n\r\n<\/div>\r\n
        \r\n\r\nIn this function the call to P can be vectorized if P\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 neither modifies nor uses X\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 does not modify Y\r\n\r\n \r\n\r\nMOD(S)<\/strong>: set of variables that may <\/strong>be modified as a side effect of call at S\r\n\r\n \r\n\r\nREF(S)<\/strong>: set of variables that may <\/strong>be referenced as a side effect of call at S DO I = 1, N\r\n\r\n<\/div>\r\n
        \r\n\r\nS0:\r\n\r\nS1:\r\n\r\nCALL P\r\n\r\n \r\n\r\nX(I) = X(I) + Y(I)\r\n\r\n<\/div>\r\n \r\n
        \r\n\r\nENDDO\r\n\r\n \r\n\r\nSince there is a call at P, it is not possible to vectorize S0 but can vectorize S1 as it is just some addition computation and doesn\u2019t have the modification or reference side effect.\r\n\r\n \r\n\r\n40.6.2 Alias Analysis<\/strong>\r\n\r\n \r\n\r\nALIAS(p,x)<\/strong>: set of variables that may <\/strong>refer to the same location as formal parameter \u2018x\u2019 on entry to \u2018p\u2019. This is similar to the aliases that were discussed in the context of pointers in the last module. Consider the following example:\r\n\r\n \r\n\r\nSUBROUTINE S(A,X,N)\r\n\r\nCOMMON Y\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* Y is global variable *\/\r\n\r\nDO I = 1, N\r\n\r\n \r\n\r\nS0:X = X + Y*A(I)\r\n\r\nENDDO\r\n\r\n \r\n\r\nEND\r\n\r\n<\/div>\r\nIn this subroutine, it would be efficient to keep X and Y in different registers and store in X outside the loop. When there is a call, CALL S(A,Y,N), then Y is aliased to X on entry to S. The procedure cannot delay update to X in the loop any more to avoid aliasing.\r\n\r\n \r\n\r\n40.7 Graph Construction in designing compiler<\/strong>\r\n\r\n \r\n\r\nTypically there are three types of major graphs that are constructed as part of the designing of a compiler.\r\n
          \r\n \t
        • Control-Flow graph G=(N,E) \u2013 Used to indicate the flow of control among the various\u00a0 instructions<\/li>\r\n<\/ul>\r\n\u2013\u00a0 N: the set of all instructions (or basic blocks)\r\n\r\n\u2013\u00a0 E: the set of control flow edges\r\n
            \r\n \t
          • Edge (p,q) is in E if instruction \u2018p\u2019 may be followed by instruction q<\/li>\r\n \t
          • Call Graph G=(N,E) \u2013 Used to indicate the data flow between procedure calls<\/li>\r\n<\/ul>\r\n\u2013\u00a0 N: one vertex for each procedure\r\n\r\n\u2013\u00a0 E: one edge for each possible call\r\n
              \r\n \t
            • Edge (p,q) is in E if procedure p calls procedure q<\/li>\r\n<\/ul>\r\n
                \r\n \t
              • Binding graph GB=(NB,EB) \u2013 used to indicate the parameter bindings<\/li>\r\n<\/ul>\r\n\u2013\u00a0 One vertex for each formal parameter of each procedure\r\n\r\n\u2013\u00a0 Directed edge from formal parameter, f1 of p to formal parameter, f2 of q if there\r\n\r\nexists a call site s=(p,q) in p such that f1 is bound to f2\r\n\r\n\u2013\u00a0\u00a0\u00a0\u00a0 |NB| <=\u00a0\u00a0 |E|, |EB| <=\u00a0\u00a0\u00a0\u00a0\u00a0 |E|, while G=(N,E) is a call graph\r\n\r\n \r\n\r\nOther graphs like Dependency graph to indicate the interaction between the non-terminals, the DAG, are part of the compiler design process.\r\n\r\n \r\n\r\nA Call Graph G=(N,E) is an important data structure where the nodes indicate the number of procedures and the edges E are defined one edge for each possible call. In addition, Edge (p,q) is in E if procedure p calls procedure q. It looks simple but construction is difficult in presence of procedure variables.\r\n\r\n \r\n\r\nAs these are advanced topics, it has been skipped in this version of the online material.\r\n\r\n \r\n\r\nSummary<\/strong>: In this module we discussed procedure optimization and inter-procedural analysis methods that could be adapted. As a thumb rule, the cost of optimization should not exceed the cost of computing without optimization.\r\n\r\n \r\n\r\nIn this course, we have discussed the following:\r\n
                  \r\n \t
                • Phases of the compiler<\/li>\r\n \t
                • Tools of the compiler \u2013 LEX, YACC<\/li>\r\n \t
                • Lexical Phase \u2013 Automata, Regular expression<\/li>\r\n \t
                • Syntax Phase \u2013 Top Down and Bottom up Parser<\/li>\r\n \t
                • Semantic Phase \u2013 Type Checking, Run-time storage management<\/li>\r\n \t
                • Intermediate Code Generation \u2013 3 address code, Backpatching<\/li>\r\n \t
                • Code generation \u2013 Simple, DAG, Dynamic Programming, Template Base<\/li>\r\n \t
                • Code Optimization \u2013 Transformation, Data- flow, Control flow analysis, Procedure optimization<\/li>\r\n<\/ul>\r\n \r\n\r\n ","rendered":"
                  \n

                   <\/p>\n

                  In this last module, we will try to understand the procedure optimization techniques. We shall discuss how a function could be optimized being recursive or non-recursive. We shall also discuss the concepts involved in Inter-procedural analysis.<\/p>\n

                   <\/p>\n

                  40.1 Types of procedure optimizations<\/strong><\/p>\n

                   <\/p>\n

                  When it comes to procedure optimizations, we shall first indicate the definitions of the functions. A function could be recursive or non-recursive. Based on that, the following possibilities need to be considered while optimizing the functions.<\/p>\n

                   <\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Tail-Call Optimization vs. Tail- Recursion Elimination \u2013 A call is said to be \u201ctail\u201d, if calling another function is the last statement of the current function . If the same is carried on in a recursive call, it is said to be tail- recursion<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Procedure Integration vs. In-line Expansion \u2013 Combining certain procedures to avoid the calling stack mechanism need to be studied as against in- line expansion of certain functions.<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Leaf-routine Optimization vs. Shrink Wrapping \u2013 A function call is typically visualized as a call graph and if the leaf node is another function call we call this as a leaf-routine. This is done using a method called as shrink wrapping.<\/p>\n

                   <\/p>\n

                  This module discusses all of these types of procedures as part of optimization.<\/p>\n

                   <\/p>\n

                  40.2 Drawbacks of \u201cCall\u201d<\/strong><\/p>\n

                   <\/p>\n

                  Before we try to do optimization on procedures, let us first define the necessity to optimize these procedures. This can be well understood if we know the mechanism of a function call. In a calling convention, there are two players: a caller and a callee. A caller is one who calls another function and a callee is one who gets invoked by a function. The caller and callee need to handle the following:<\/p>\n

                   <\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Caller \u2013 need to take care of parameter passing, caller-saved register, return address branch after the callee returns<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Callee \u2013 This has two components: a prologue and epilogue that is to be done before and after executing the current function.<\/p>\n

                  \u2013\u00a0 prologue – save frame pointer, compute stack pointer, callee-saved register<\/p>\n

                  \u2013\u00a0 epilogue : callee-saved register, return value, stack pointer, frame pointer, branch\u00a0\u00a0with this in the <\/span>caller \/ callee\u2019s domain, from an optimization <\/span>view point, there is very less chance to optimize between procedures. However, within a <\/span>procedure there is some space for optimization.<\/span><\/p>\n<\/div>\n

                  \n

                   <\/p>\n

                  40.3 Tail-call optimization vs Tail Recursion elimination<\/strong><\/p>\n

                   <\/p>\n

                  A tail-call is one where the last statement of a function call is a call to another function. If the same thing is applicable to a recursive function the situation is termed as tail recursion. Consider the following example:<\/p>\n

                   <\/p>\n

                  void f(int x) {<\/p>\n

                   <\/p>\n

                  …<\/p>\n

                  g(x);<\/p>\n

                  (return;)<\/p>\n

                   <\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  In the above example, function f() calls another function g(x) as the last step before return statement. Similarly, the following indicates tail-recursion, where f(x) is called as the last statement of the function f().<\/p>\n

                   <\/p>\n

                  void f(int x) {<\/p>\n

                  …<\/p>\n

                   <\/p>\n

                  f(x);<\/p>\n

                  (return;)<\/p>\n

                   <\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  Tail recursion results in procedure-call overhead. This can be eliminated by converting it to a loop and performing loop optimization. Consider the following function which has a tail-recursion:<\/p>\n

                  void insert_node(int n, struct node *l)<\/p>\n

                  {<\/p>\n

                   <\/p>\n

                  if(n > l\u2192values)<\/p>\n

                  if(l\u2192next==null)<\/p>\n

                   <\/p>\n

                  make_node(l,n);<\/p>\n

                  else<\/p>\n

                  insert_node(n,l\u2192next);<\/p>\n

                  }<\/p>\n

                  The final call to insert_node could be eliminated by converting the recursive call to a loop as given below<\/p>\n

                  void insert_node(int n, struct node *l)<\/p>\n

                  {<\/p>\n

                   <\/p>\n

                  Loop:<\/p>\n

                  if(n > l\u2192values)<\/p>\n

                   <\/p>\n

                  if(l\u2192next==null) make_node(p,n);<\/p>\n

                  else { l = l\u2192next; goto Loop; }<\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  We introduced a label loop which is the point to continue and removed the recursive call and converted it to an iterative call.\u00a0Tail-call is termed as the routine performing the call does nothing after the call returns except return itself. During a tail call, the caller branches into the body of the other function and hence care should be taken care of <\/span>scope of variables and their return values. The following is an example of tail-call.<\/span><\/p>\n<\/div>\n

                  \n

                  void make_node(struct node *p, int n)<\/p>\n

                  {<\/p>\n

                   <\/p>\n

                  L0: struct node *q = malloc(…);<\/p>\n

                  p\u2192next = q;<\/p>\n

                   <\/p>\n

                  …<\/p>\n

                  }<\/p>\n

                  void insert_node(int n, struct node *l) {<\/p>\n

                  if(n > l\u2192value)<\/p>\n

                  if(l\u2192next==null) make_node(l, n);<\/p>\n

                   <\/p>\n

                  …<\/p>\n

                  }<\/p>\n

                  The function insert_node() makes a tail-call to the function make_node.<\/p>\n

                   <\/p>\n

                  Tail-call optimization is performed by following the steps given below:<\/p>\n

                   <\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Both procedure bodies should be visible to the compiler.<\/p>\n

                  \u2013\u00a0 It should be in the same compilation unit or should have their intermediate-code<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Need to know about callee.<\/p>\n

                  \u2013\u00a0 where it expects to find its parameters<\/p>\n

                  \u2013\u00a0 where to branch<\/p>\n

                  \u2013\u00a0 stack frame size.<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the call by three things,<\/p>\n

                  \u2013 evaluation of the arguments and putting them where the callee expects to find them.<\/p>\n

                  \u2013\u00a0 if callee\u2019s stack frame is larger than caller\u2019s,\u00a0 an instruction that extends stack frame as difference.<\/p>\n

                  \u2013\u00a0 a branch to the beginning of the body of the callee<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Final step is to delete \u2018return\u2019 after a call. Consider the following example to perform tail-call optimization.<\/p>\n

                  insert_node :<\/p>\n

                  { …<\/p>\n

                   <\/p>\n

                  r2 \u2190 r1<\/p>\n

                  r1 \u2190 r4<\/p>\n

                   <\/p>\n

                  call make_node<\/p>\n

                  return;<\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  This will be converted to the following:<\/p>\n

                   <\/p>\n

                  insert_node :<\/p>\n<\/div>\n

                  \n

                  {<\/p>\n

                  …<\/p>\n

                   <\/p>\n

                  r2 \u2190 r1<\/p>\n

                  r1 \u2190 r4<\/p>\n

                   <\/p>\n

                  goto make_node<\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  On the other hand, the following sequence of steps is performed for removing tail-recursion.<\/p>\n

                   <\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Replace the recursive call by<\/p>\n

                  \u2013\u00a0 assign proper values to the parameters, and<\/p>\n

                  \u2013\u00a0 branch to the beginning of the body of the procedure<\/p>\n

                  \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Delete \u2018return\u2019 after recursive call<\/p>\n

                  Consider one more example of tail-recursion elimination.<\/p>\n

                   <\/p>\n

                  void replace(int n) {<\/p>\n

                  if(n>=10) return;<\/p>\n

                   <\/p>\n

                  if(A[n]==0) A[n]=1;<\/p>\n

                  else replace(n+1);<\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  In the above function replace(), the function gets called as the last step. The following is the optimized and tail-recursion eliminated function replace()<\/p>\n

                  void replace(int n) {<\/p>\n

                  Loop:<\/strong><\/p>\n

                  if(n>=10) return;<\/p>\n

                  if(A[n]==0) A[n]=1;<\/p>\n

                   <\/p>\n

                  else {<\/p>\n

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

                   <\/p>\n

                  goto Loop;<\/strong><\/p>\n

                  }<\/p>\n

                   <\/p>\n

                  We have introduced the label loop to go to the beginning of the function. The body of the else has multiple statements, which increments the variable \u2018n\u2019 and then a \u2018goto\u2019 to the beginning of the body of the function.<\/p>\n

                   <\/p>\n

                  40. 4 Procedure Integration and Inlining<\/strong><\/p>\n

                   <\/p>\n

                  Procedure integration is also called as \u2018automatic inlining\u2019 where the body of the procedure is available in the caller\u2019s body itself. This replaces calls to the copy of the procedure body. A call can have unknown effect of the objects in the procedure on aliased variables and the local code gets expose and thus could enable more optimization. This is however better than \u2018inline\u2019 of C++ where it is optimized by user\u2019s intuition. The following are some of the issues with procedure integration:<\/p>\n<\/div>\n

                   <\/p>\n

                  \n
                    \n
                  • \u00a7\u00a0\u00a0 Range of inlined procedure \u2013 one has to save intermediate-code representations<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0\u00a0 Languages of caller and callee (cross compilation units)<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0 Need to handle the different languages and their various parameter passing conventions<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0 Need to handle the \u201cexternal language_name procedure_name<\/em>\u201d declaration to specify source languages<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0\u00a0 Saving intermediate-code of in- lined routines<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0\u00a0 Need to know the purpose of saving intermediate-code<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0 Need to compile a copy of the whole in- lined procedure<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0\u00a0 address of the procedure has been taken<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0\u00a0 calls from other compilation units, currently invisible and need to be addressed<\/li>\n
                  • \u00a7\u00a0\u00a0\u00a0 Inlining on recursive procedures \u2013 To be avoided as running out of calls to them could be infinite process. It is valuable to inline once or twice<\/li>\n<\/ul>\n

                    The goal of inlining procedures should be to reduce e xecution time and avoid the calling stack mechanism. If every procedure is inlined then the following overhead need to be addressed:<\/p>\n

                      \n
                    • \u00a7\u00a0\u00a0 decrease overhead costs of call<\/li>\n
                    • \u00a7\u00a0\u00a0\u00a0 increase in object code size<\/li>\n
                    • \u00a7\u00a0\u00a0\u00a0 more cache misses<\/li>\n
                    • \u00a7\u00a0\u00a0\u00a0 compilation terminates only by exhaustion of resources<\/li>\n
                    • \u00a7\u00a0\u00a0\u00a0\u00a0 We need heuristics or profiling feedback<\/li>\n<\/ul>\n

                      The following need to be considered while inlining procedures:<\/p>\n

                        \n
                      • \u00a7\u00a0\u00a0\u00a0 The size of the procedure is small,<\/li>\n
                      • \u00a7\u00a0\u00a0\u00a0 The procedure which is called less,<\/li>\n
                      • \u00a7\u00a0\u00a0\u00a0\u00a0 The procedure that is called inside a loop<\/li>\n
                      • \u00a7\u00a0\u00a0\u00a0\u00a0 The procedure whose call includes constant-valued parameter<\/li>\n<\/ul>\n

                        To perform inlining we need to handle the three major issues:<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Different parameter passing conventions<\/p>\n

                        \u2013\u00a0 \u201cexternal language_name procedure_name<\/em>\u201d declaration<\/p>\n

                        \u2013\u00a0 call-by-reference vs. call-by-value<\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Name conflicts<\/p>\n

                        \u2013\u00a0 conflicts between source symbol names need to be resolved<\/p>\n

                        \u2013\u00a0 detect conflicts and rename symbols of called procedure<\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Static variables<\/p>\n

                        \u2013\u00a0 makes only one copy of static variable<\/p>\n

                        \u2013\u00a0 initialized once<\/p>\n

                         <\/p>\n

                        40.5 Leaf-Routine Optimization<\/strong><\/p>\n

                         <\/p>\n

                        Leaf routine is similar to the statement that is appearing at the end of a function. Typically a call graph is constructed for a program to visualize the parameters that gets passed between the different functions. A leaf routine is one which is part of the leaf node in the call graph of a<\/p>\n<\/div>\n

                         <\/p>\n

                        program. It is a routine that calls no procedures and hence many procedures are leaf routines. Leaf routine optimization, simplify the way parameters are passed, remove procedure prologue \/ epilogue and it is highly desirable with little effort. Leaf routine optimization is architecture-dependent. It depends on how many registers and stacks the procedure needs. It typically needs no more registers than caller-saved registers and thus requires no stack space with sufficient registers.<\/p>\n

                         <\/p>\n

                        Shrink Wrapping is one of the leaf routine optimization methods. It involves, moving prologue and epilogue code to contain a smaller part of the procedure inside a loop and thus making many copies of codes. Figure 40.1 shows the prologue and epilogue in a flow graph and how that is typically brought closer using shrink wrapping.<\/p>\n

                         <\/p>\n

                        \"\"<\/p>\n

                         <\/p>\n

                        \n

                        40.6 Inte r-procedural optimization<\/strong><\/p>\n

                         <\/p>\n

                        Inter-procedural optimization could be attempted by performing inter-procedural analysis. This involves gathering information about the whole program instead of a single procedure. Inter-procedural Optimization is a program transformation method that involves more than one procedure in the program. Typically two Inter-procedural problems are solved: MOD Analysis and Alias Analysis. MOD analysis involves identification of modification to variables or side-effects that could be caused to the variables. Alias analysis is to verify whether the function or expressions are aliases to others.<\/p>\n

                         <\/p>\n

                        40.6.1 Modification and Reference Side-effect<\/strong><\/p>\n

                         <\/p>\n

                        This is one inter-procedural problem. Consider the following code:<\/p>\n<\/div>\n

                        \n

                        S0:<\/p>\n

                         <\/p>\n

                        S1:<\/p>\n

                        COMMON X,Y<\/p>\n

                        …<\/p>\n

                        DO I = 1, N<\/p>\n

                         <\/p>\n

                        CALL P<\/p>\n

                         <\/p>\n

                        X(I) = X(I) + Y(I)<\/p>\n

                         <\/p>\n

                        ENDDO<\/p>\n<\/div>\n

                        \n

                        In this function the call to P can be vectorized if P<\/p>\n

                         <\/p>\n

                        1.\u00a0\u00a0\u00a0\u00a0\u00a0 neither modifies nor uses X<\/p>\n

                        2.\u00a0\u00a0\u00a0\u00a0\u00a0 does not modify Y<\/p>\n

                         <\/p>\n

                        MOD(S)<\/strong>: set of variables that may <\/strong>be modified as a side effect of call at S<\/p>\n

                         <\/p>\n

                        REF(S)<\/strong>: set of variables that may <\/strong>be referenced as a side effect of call at S DO I = 1, N<\/p>\n<\/div>\n

                        \n

                        S0:<\/p>\n

                        S1:<\/p>\n

                        CALL P<\/p>\n

                         <\/p>\n

                        X(I) = X(I) + Y(I)<\/p>\n<\/div>\n

                         <\/p>\n

                        \n

                        ENDDO<\/p>\n

                         <\/p>\n

                        Since there is a call at P, it is not possible to vectorize S0 but can vectorize S1 as it is just some addition computation and doesn\u2019t have the modification or reference side effect.<\/p>\n

                         <\/p>\n

                        40.6.2 Alias Analysis<\/strong><\/p>\n

                         <\/p>\n

                        ALIAS(p,x)<\/strong>: set of variables that may <\/strong>refer to the same location as formal parameter \u2018x\u2019 on entry to \u2018p\u2019. This is similar to the aliases that were discussed in the context of pointers in the last module. Consider the following example:<\/p>\n

                         <\/p>\n

                        SUBROUTINE S(A,X,N)<\/p>\n

                        COMMON Y\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \/* Y is global variable *\/<\/p>\n

                        DO I = 1, N<\/p>\n

                         <\/p>\n

                        S0:X = X + Y*A(I)<\/p>\n

                        ENDDO<\/p>\n

                         <\/p>\n

                        END<\/p>\n<\/div>\n

                        In this subroutine, it would be efficient to keep X and Y in different registers and store in X outside the loop. When there is a call, CALL S(A,Y,N), then Y is aliased to X on entry to S. The procedure cannot delay update to X in the loop any more to avoid aliasing.<\/p>\n

                         <\/p>\n

                        40.7 Graph Construction in designing compiler<\/strong><\/p>\n

                         <\/p>\n

                        Typically there are three types of major graphs that are constructed as part of the designing of a compiler.<\/p>\n

                          \n
                        • Control-Flow graph G=(N,E) \u2013 Used to indicate the flow of control among the various\u00a0 instructions<\/li>\n<\/ul>\n

                          \u2013\u00a0 N: the set of all instructions (or basic blocks)<\/p>\n

                          \u2013\u00a0 E: the set of control flow edges<\/p>\n

                            \n
                          • Edge (p,q) is in E if instruction \u2018p\u2019 may be followed by instruction q<\/li>\n
                          • Call Graph G=(N,E) \u2013 Used to indicate the data flow between procedure calls<\/li>\n<\/ul>\n

                            \u2013\u00a0 N: one vertex for each procedure<\/p>\n

                            \u2013\u00a0 E: one edge for each possible call<\/p>\n

                              \n
                            • Edge (p,q) is in E if procedure p calls procedure q<\/li>\n<\/ul>\n
                                \n
                              • Binding graph GB=(NB,EB) \u2013 used to indicate the parameter bindings<\/li>\n<\/ul>\n

                                \u2013\u00a0 One vertex for each formal parameter of each procedure<\/p>\n

                                \u2013\u00a0 Directed edge from formal parameter, f1 of p to formal parameter, f2 of q if there<\/p>\n

                                exists a call site s=(p,q) in p such that f1 is bound to f2<\/p>\n

                                \u2013\u00a0\u00a0\u00a0\u00a0 |NB| <=\u00a0\u00a0 |E|, |EB| <=\u00a0\u00a0\u00a0\u00a0\u00a0 |E|, while G=(N,E) is a call graph<\/p>\n

                                 <\/p>\n

                                Other graphs like Dependency graph to indicate the interaction between the non-terminals, the DAG, are part of the compiler design process.<\/p>\n

                                 <\/p>\n

                                A Call Graph G=(N,E) is an important data structure where the nodes indicate the number of procedures and the edges E are defined one edge for each possible call. In addition, Edge (p,q) is in E if procedure p calls procedure q. It looks simple but construction is difficult in presence of procedure variables.<\/p>\n

                                 <\/p>\n

                                As these are advanced topics, it has been skipped in this version of the online material.<\/p>\n

                                 <\/p>\n

                                Summary<\/strong>: In this module we discussed procedure optimization and inter-procedural analysis methods that could be adapted. As a thumb rule, the cost of optimization should not exceed the cost of computing without optimization.<\/p>\n

                                 <\/p>\n

                                In this course, we have discussed the following:<\/p>\n

                                  \n
                                • Phases of the compiler<\/li>\n
                                • Tools of the compiler \u2013 LEX, YACC<\/li>\n
                                • Lexical Phase \u2013 Automata, Regular expression<\/li>\n
                                • Syntax Phase \u2013 Top Down and Bottom up Parser<\/li>\n
                                • Semantic Phase \u2013 Type Checking, Run-time storage management<\/li>\n
                                • Intermediate Code Generation \u2013 3 address code, Backpatching<\/li>\n
                                • Code generation \u2013 Simple, DAG, Dynamic Programming, Template Base<\/li>\n
                                • Code Optimization \u2013 Transformation, Data- flow, Control flow analysis, Procedure optimization<\/li>\n<\/ul>\n

                                   <\/p>\n

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