Scribd
Upload
11 views26 pages

CD Notes

Machine-independent optimization focuses on improving code efficiency without being tied to a specific target machine, relying instead on source language characteristics. Key techniques include local and global optimizations, constant propagation, dead code elimination, and loop optimizations, which enhance performance by reducing unnecessary computations and improving data flow analysis. The document outlines various optimization strategies and their implementations, emphasizing the importance of optimizing loops and eliminating redundancies in code.

Uploaded by

rupeshdharavath
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
11 views26 pages

CD Notes

Machine-independent optimization focuses on improving code efficiency without being tied to a specific target machine, relying instead on source language characteristics. Key techniques include local and global optimizations, constant propagation, dead code elimination, and loop optimizations, which enhance performance by reducing unnecessary computations and improving data flow analysis. The document outlines various optimization strategies and their implementations, emphasizing the importance of optimizing loops and eliminating redundancies in code.

Uploaded by

rupeshdharavath
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Machine-Independent Optimization _ Mochine-Independent Optimization: The Principal Sources Sf Optimization alta is Bhat 5 ata-Flow Constant Propagation, Partial-Redundaney Elimination, ‘Analysis, Foundations of Data-Flow Analysis, Loops in Flow Graphs. 1 : : LEARNING Osuectives > About Principle Sources of Optimization > > Introduction to Data Flow Analysis : > ‘Foundations to Data Flow Analysis > Concept of Constant Propagations >” Elimination’ of Partial Redundancy > Concept of Loops in Flow Graphs > INTRODUCTION ization is performed by the independent of target machine, but depends i i f target code gets improved by using sours | istics. In this optimization, efficiency of ; as imization and global optimization are ‘the two machine 81 appro} Local opti ‘ cod option i i basic block where as independent code optimizations. Local optiinizations are’ carried out with in a single Slobal optimizations are carried out across basic blocks. especially the inner loo} instruct the number of ins c gommon sub expression, Machine independent code op! ps, Most of the run time is spent ions in an inner loop. The various copy/variable . The «ration i © major source of code optimization is loops, ide the loops which cari be reduced by reducing tt ciple source ‘of optimization techniques, ore shee Propagation, elimination of dead code and loop optimiz tion of ration. ~ af. SS COMPILER DESIGN [UNTU-HYDERABAD) _PART-A, SHORT QUESTIONS WiTH ‘SOLUTIONS Dec.-17(R15), 49) Q1. What is machine independent code optimization? Answer : nthe source language characteristic, ‘Machine independent optimization is independent of target machine, but depends oF wget code, Various machine - ree f tangs ‘This optimization technique uses appropriate program structure in order io improve the efficiency © independent code optimization techniques are, i (a) Local optimization (©)_Global optimization, Discuss briefly about, - Local optimizations (ii) Global optimizations. Answer : : @ Local Optimizations Local optimizations are carried out within a single basic block. This techni the data and flow of control. Thus, implementation of this technique is simple. i) Global Optimizations * : A Global optimizations are caried outacross basic blocks, instead of single basic block. This analysis is also Known as dataflow analyzis. In this technique, addtional analysis is required across basic blocks. Thus, implementation ofthis technique is complex. Q3._ Distinguish between machine dependent and machine independent optimization. Answer : a2. que do not require the information regarding Mode! Paper, a1() “Machine Dependent Optimi Machine Independent Optimization ~~] 1. | lt is dependent on the instruction set and addressing modes to be used. roe 2. | The efficiency ofthe program is improved by allocating sufficient number of resources. Intermixed instructions with data increases the speed Tt is independent of the target machine, but depends| on the source language characteristics. The efficiency of the target code is improved by using| appropriate program structure. Elimination of dead code increases the speed of| of execution. execution, 4, | Intermediat structions are used wherever necessary. | 4. | Identical computations are moved to one place, thus avoiding the repeated computation of an expression. Q4. What is common sub-expression elimination? Explain. Answer : "The code can be improved by eliminating common subexpressions from the code. An expression whose value was previously computed and the values of variables in the expression are not changed, since its computation can be avoided to recompute it} using the earlier computed value, ip : May-19(R16), 210) Example 1 i + Consider the following sequence of code, *erd-c In the above code’the assignment to z have the common subexpression b* c. Since j i 3 . Since its value is rm it was computed, and its use in the expression z, we can avoid recomputing it by ais not changed after the Pot replacing the above code as follows: ‘ieee bs SISASSbE GES nN: | Machine-Independent Optimization ’ K uN Which graph Is used for identifying the common sub xpression in an expression? a5. i : Mareh-16(R12), Q4(0) est , . i flow graph is used for identifying the common subexpression in an expression. Itis a graphical representation of three- .¢ statements. 1 re ee Shree paki dtl is F basic block that performs some computations. An initial node a e . There is a directed i een blocks. There is an edge from block BI to block Ee ted edge from one node to another representing the flow of i Whats dead code elimination and reduction in strength? answer # : March-t7(R19), a4 pasa Code Elimination oe Apiece of code which is not reachable, that is the values it computes is never used an; is sai . is 1ywhere in the program then it is said» nh edd he abso Seer a safely. An assignment to a variable results in dead code, if the value of ‘arable i 1 . Also an assignment to a variable i ; e Set tthe same variable before ts vale is sed inthe set ease 8 Sead Code if here i lays another jedection in Strength the process of replacing expensive operations by equivalent cheaper operations onthe target machine. amany machines a multiplication operation takes more time than addition or subtraction. On such machines the speed of A ere \. ma the «ajectcode can be increased by replacing a multiplication by a subtraction, called reduction in strength. eePRere @. Briefly explain live variable analysis. AVS able (say a) is said to be alive at point p if, @ _Iscurrent value is used in the flow griph beginning at the point p. y @ , There exist a path (say p’) from start point p to end point (E) otherwise it is said to be in dead state. Example i . . ‘Consider the following figure, 3, aes a a be=10 Ci=5 2 3B, pe? Bs qnmatz By ss fanarehy : Figure: Flow Graph aie er and is killed at block 8, : Itcan be noticed from above figure, that a variable a is live from block B, to Block B, and Block B, and * What is a semilattice? , Wer: es meet operator *A’ such that for all. ing 4 Semilatice can be defined as algebraic structure (S, a) with set of values ‘S' and 2 : ) en *.y and z in ‘S°, It holds the following properties, pas dempotent : x ax Commutative sx Ay=y Ax 8 Ass ®) Asocitve LEA AREA AE” »- Asiilatice contains top element ‘T"V, #65, 91" ! and a bottom element 5.4 Q9. _Whatare the properties of transfer functions In ‘a data flow framework? Answer Ina data flow framework, the set of transfer functions F : S +S includes the following properties, (@)__Fincludes identity function I such that V x65, (2) =x. Gi) Fis closed under composition of functions. In other words, V fg € F there exists function h defined by Hx) = g(fRs) in F. Q10. Write a short note on monotone frameworks. Answer : Adata-flow framework (D, S, 6, F) is said to be monotone if the result generated from the first member is less than the second member after applying transfer function to, any two members of sét S. In other words, data-flow framework is said to be monotone XS y= fx) s/o) xy € Sandfe F Similarly, monotonicity can be described as, SEAS A) ASO) my © Sand fe F In the above equation, itis noticed that resultant value of function ‘f after calculating the meet of two members say ‘ and ‘y" can never be greater than the result achieved by applying meet between two individual members applied with function *. Q11. Define constant propagation. Answer = Constant Propagation Constant propagation can be defined as the process of providing the constant values to the variable during compile time. It is a forward data-flow problem. Example Consider the code given below, int a= 100; int b= 200; intx=a+(b-a); During compile time the values gets substituted as, int a= 100; init 6 = 200; 7 int.x = 100 + (200 ~ 109) COMPILER DESIGN [JNTU-HYDERABAD) | Q12. Whatare Induction variables? Whats induction variable elimination? Answer + May-19(R16), aig) ‘An induction variable is a loop control variable or any oiher variable that depelids on the induction variable in some fixed way. It can also be defined as a variable which is inereménted or decremented by a fixed number in a loop each time the loop is executed. Induction variables are of the form i814 c (where cis a constant). If there are two or more’ induction variables in a loop then’by'the induction variable elimination process all can be eliminated except one. Q13. Define loop unrolling. Give an example. Answer : (Model Paper, G10) | Mareh-17(R13), 4) Loop unrolling is the process of replicating the bodyof the loop to reduce the required number of tests or iterations. It can be applied if the number of iterations are constant, For ‘example, consider the following code, ’ j-0 while(j <= 50) { afi]=0; its } Inthe above example, the while loop is executed 50 times (.e., the test condition is checked 50 times). But, ifthe body of the loop is replicated then the number of times, the while loop is executed and test condition is checked is only 25 times. THe while loop after loop unrolling is shown below, jst . _MhileG <= 50) wt ail itt; alil-o; it Machine-Independent Optimization unit? ESSAY. QUESTIONS WITH So! LUTIONS. | THE PRINCIPAL SOURCES OF OPTIMIZATION : ! ee piscuss the following concepts, rahe “ ot () Machine independent optimization (i) Function-preserving transformation, Modal Paper, cote OR With an example explain common sub expres (Refer Orly Topics: Elimination of Globat Conipion, Sion and dead code eliminatic Sub-expresstong; OR ion methods in detail. Elimination of Déad Céite) Dec.-19(Ri6), a10 Explain in detail the procedure that eliminate: mene . Mareh-16(R13), a10 (Refer Only Topic: Eliminating’ Global Common sub-esp, ession) Answer {) Machine Independent Optimization . * Machin n is independent of target machine, but depends on the source language characteristics, : Pec cade ccnidue Uses appropriate program structure inom improve the efficiency of target code. Various marten ‘akpendent code optimization techniques are, 4 (@) Local optimization ‘ (©) . Global optimization, (“Local Optimization ©) Global Optimization é These are the optimizations carried out across basic blocks, instead of single basic block. This analysis: also-known & data-flow analysis: In this technique, additional analysis i “equired across basic blocks. Thus, implementation ofthis technique is complex. s @ Funetion-preserving ‘Transformations shia ap Semantic’ Preserving transformations helps in improving a program’code without peatying the function it computes Semantic preserving transformation (ot) function preserving transformations can be done by the following, @ ©) Elimination of déad code : ; r Elimination of global common sub-expressions. © Constant folding - @ () Copy/variable propagation ” Elimination of Global Common Sub-expressions . value was * le. An’ expression’ whose ‘TE code can be iniproved by eliminating common sub-cxptssions from the cod vided ic \ce its computation can be avoic ~ Previously computed and the values of variables in the expression are not changed, sin ‘ecompute it by using the earlier computed value. Example Consider the following sequence ofcode, =": ambte NSgitbe ~ COMPILER DESIGN [UNTU-HYDERABAD) —————$—_ @) Inthe above code the assignment to z have the common subexpression 5* ¢, Since its value is not changed afer the point it was computed, and its use in the expression 2, We can avoid recomputing it by replacing the above code as follows: te However, itis not possible to eliminate an expression if the value of one of its variable is changed. Example Consider the following code, tetd-c Here, the expression b* ¢ is not common because the value of variable c is changed after computing b* c. Therefore, we cannot eliminate this expression. Elimination of Dead Code piece of code which is not reachable, that is the values it computes is never used anywhere in the program then it is said to be dead code and can be removed from the program safely. An assignment to a variable results in dead code, ifthe value of this variable is not used in the subsequent program. Also an assignment to a variable is a dead code if there is always another assignment to the same variable before its value is used in the subsequent program. Copy propagation often makes the copy statements into dead code: Example Consider the following code, bee : Meopy statement a d e=b+d-3 ‘Suppose that the value of dis not used in the subsequent program, then using copy propagation followed by common subexpression elimination followed by dead code, elimination removes the assignment to dead variable d, Hence the above code becomes as: =abre ort, dst,-3). 4 © @ Constant Folding fexpressions involve constants, then these expression, can be evaluated at compile time itself. Statements like + xpexth 4 int maximum = 10; = Maxinum Copy/Variable Propagation If there are copy statements of the form x == y then in copy/variable propagation the use of variable x is replaced by the variable y in the subsequent expressions, ‘The copy propagation is possible if none of the variable is changed after this arrangement. * Example: Consider the following code, Heopy statement emb+d-3 We may notice that the code has common subexpressions b+ cand b + d, if we replace the variable d by the variable ¢ as both have the same value. Common subexpression treats these expressions as different. After applying copy propagation, the above code becomes: a=bte a embte-3 By copy propagation we can eliminate the assignnest to. Q15. Explain loop optimization technique with Answer : Loop Optimization example. May-19(R16), Q11(0) OR Mlustrate loop optimization with suitable example. March a7(R13),.09 The major source of code optimization is loops especially the inner loops, Most of the run time is spent inside the loops wi can be reduced by reducing the riumber of instructions in an inner loop: + There are three techniques namely, 1": Code motion 5 2. Elimination of induction variables 3 3.,,_ Strength reduction, , sh q Le ~ achine-Independent Optimization i ose motion teducts the numberof instructions ina loop ructions outside a loop. It moves loop-invariant meas ie. those instructions oF expressions that result ore value independent of the number of times a loop inde Si andplaces them at the beginning of the loop. The pore xpresions becomes entry for the loop. : mpl Consider the following while loop. while(x != n= 2) { owing ins +2; } Here the expression m ~ 2 is a loop-invariant mputation ie., the value evaluated by this expression is jpipendent of the number of times the while loop is executed, poder words the value of n remains unchanged. The code restion places the expressions ~ 2 before the while loop tepisas shown below : Which is equivalent to the above example. } Elimination of Induction Variables ‘An induction’ variable is a loop control variable or ®Y oer variable that depends on the induction variable in ‘ome fixed way. If can also be defined as a variable which is “cttented or decremented by a fixed number in a loop each “fat 00p i§ executed. Induction variables are of the form i © e(where c is a constant). isp there'are two or more induction variables in a loop fing? induction variable elimination process all can be tated except one, ple Consider the Part of a program. “int a{10}, b[10); Void fun(void) { inti, j, ky Ea for(i =0, ), k = 0; i< 10; i++) ali++] = bit} 1 5.7 ut ode Motion Inthe above example there are three induction variables /, Jand k which take on the values 1,2, 3,..,10 each time through the beginning of the loop. Suppose that the values of variables / and kare not used after the end of the laop then we can eliminate them from the function fun() by replacing them by variable i. After induction variable elimination, the above code becomes as, int a[10}, b[10]; void fun(void), ( inti for(i = 0; i < 10; i+) 3 } The use of induction variables elimination reduces code ‘space by reducing the number of additions or subtractions in a loop. It also improves the run time performance. 3. Strength Reduction Strength reduction is the process of replacing expensive operations by equivalent cheaper operations on the target machine. On many machines a multiplication operation takes more time than addition or subtraction. On such machines the speed of the object code can be increased by replacing a'multiplication by a subtraction. This is called reduction in strength a Example : 3 Consider the following code, forli= 1s8< 5:54) { } ‘The instruction x= 4 * in the loop can be replaced by equivalent addition instruction as x=. + 4, Another example of reduction in strength is the replacement of a fixed point multiplication by a power of two by the cheaper shift operatio Q16, Write the principal sources of optimization. May 19(R16), a10(0). OR ‘ f optimization in Explain the principe sources of optimization detail. wi * , OR é rincipal sources’ ‘ in in brief about different p! Ettoptimization techniques with sultable.., ¢ "examples. > a March-16(R13), 0810) Lee eset 2 OReg. 58 COMPILER DESIGN [JNTU-HYDERABAQy Explain different principle source of code In the above equations CGEN[B] is a set of all co jimization. statements generated in block B and CKILL{B] is set of statements in U that are killed in B. Where U being the univers aeeee Y NovsDec-201R18).28 | set containing all copy statements in the program. In relation tg “The various principal sources of optimization techniques | copy propagation we say that a statement s:x:~ y is killed inp are as follows, @ Gi) Copy/variable propagation Elimination of common subexpréssions (ii) Elimination of dead cde Gx)_Loop optimizations. Elimination of Common Subexpressions @ For answer refer Unit-V, QU, Topic: Global Common Subexpressions. Elimination of Copy Propagation For answer refer Unit-V, QI4, Topic: Copy / Variable Propagation. Gi) Elimination of Dead Code For answer refer Unit-V, QU4, Topic: Elimination of Dead Code. Gv) Loop Optimizatioas For answer refer Unit-V, QUS.. paar For sewer sefen UnW-, O15 SRee aaa Q17. Explain how copy propagation can be done using data flow equation. Answer : (Boe.-17(R1), Q9 | March-16(R13), Q9(b)) The intermediate code generator often creates the copy statements such as s : x >= y which involve temporary variables that are local to one block. Such copy statements can be eliminated by determining all places where x is used and replacing its use by y in all these places. This can be done if every 1 of x satisfy the following conditions, 1, The definition of x that reaches it use w must be only the statement s. This condition can be checked using uud-chaining information of x. 2. ° Thevalue of y is not changed along every path from the definition of x to its use i.e., from s to u. This condition can be checked by defining the sets BGN(B] and END([B]. The set BGN[B] is the set of copy statements. of the form s: x: = y, such that s is available along the pith from initial node to the beginning of B and along this path y is not redefined. The set END[B] is defined similarly but [Link] the end of block B. ‘The data flow equations for copy propagation are, END[B]_=CGEN[B] U(BGNIB]-CKILLB)) ‘ (2, ENDIPKGt Bis not the BGNIB] = tiger intial block) | BGN[B|] = 6 if B;is the inital block. if the defi Propagation Algorithm : ‘The algorithm takes as input a flow graph with ud-chain and du-chain information. It produces a revised flow graph as, an output. ‘The algorithm consists of the following steps, 1. Forthe copy statement s :a:= 6, determine all the uses ofa. 2! For every use of a found in step 1 determine whether s is in CBGN[B) and that a or b is not changed before the use of a within B(a block containing particular use of a). If CBGN{B] includes s then it is the only definition of a that reaches B. 3. If's satisfies the above conditions then remove s and substitute & for x in all of its uses found in step 1. tion of eory is changed and s isnot present in a | 4, Repeat these steps for each copy statement of the form Example Consider the flow graph shown in figure. ibaa: Block B, 2243 5 SS Block B, ci=a |] BlckB, Figire: Example Flow Graph In the above flow graph CGENB, CGEN[B,] = {a=} and * CGEN for remaining blocks is f CKILLIB,] = {a = 5} since 6 is‘changed inB2 CKILL[B,] = {a5} and CKILL [B,)= (4 a is changed in corresponding bloc CKILL for remaining blocks is f- From the data-flow equations, we get, BOND, - 5 Mechine-Independent Optimization pnt =, 5. eaitable expression for the low graph is given as, BI fa: Instruction Cost END[B,]=¢ . MOV a, R,{ 1+1+0=2 | |= BGN[B,] = END| - ; END[B,]= BGNIB,} (B ADD b, R, | 1+1+0=2 BGNIB,|= ENDIB,] 9 ENDIB,=9 Fi itis i Mov 4, R, 1+1+0=2 mthe above information it is not possible to replace all — afaby bor for definitions a ADD, R,| 1+1+0=2 leneither COPY’ ‘statement may be propagated. However we ; Ieee aby’c in B, but it is not an improvement inthe code. SUB eR, | i+i+o=2 a 18. Define loop optimization. Describe in brief about SUB__R,R,| 1+0+0=1 O18. he transformation on basic blocks, ~ = : Mov Rx | 1+0+1=2 ees Dee.7(R15), a10 - Ae eae Total Cost 13 Foranswer refer Unit-V, Q15, Topic: Loop Optimization. qansformation on Basic Blocks For answer refer Unit-IV, Q40. —— aia. Generate the code for the following expression x=(a+b)—((c + d)—e). Also compute its cost. Answer = March-17(R13), Qt Given expression is, (at b)-((e+d)-e) The three address code is, at The code generated is, MOV aR, ADD b,R, 4 MOV 4R, . ADD ¢R, sup gk, SUB R,R, MoV R,x boy, TH €0st for the above instructions is computed as fol- Consider, Mov See 5.2 INTRODUCTION TO DATA-FLOW ANALYSIS 20. Write about Data flow analysis of structural programs. Answer :* (Mode! Paper, Q10(b) | May-18(R15), 08) Data flow analysis of a structured program can be represented using a flow graph. As flow graphs are capable of exhibiting control flow constructs. Flow graphs are used to indicate the flow of control from ‘one point to another point. Few small circles called the dummy blocks (since they do not contain any stateménts) are used to indicate the entry and exit of control. A Set of nodes ‘nin the flow graph is called a region. ‘n’ also includes the dominating node in the region called the “header”. Consider a grammar with control flow constructs ic., do-while, if-else, assignment and sequential statements. - ‘tmnt —> identifier:= Expr | Stmt; Stmt] if Expr then Stmt else Stmt | do Stmt while Expr Expr — identifier + identifier | identifier Stmt represents a statement and Expr an ow the yields of ‘Stmt” can be iphs would replace the Where, expression. The flow graphs for drawn. However, cach of these flow gra general flow graph. ¢---> Dummy 5.10 . (Strat — identifier : = Expression ‘When stmnt takes the form, ‘Stmt —> identifier := Expression ‘The general flow graph is replaced by, Expression Example ¥ For the example assignment staternent, d:zetg ‘The flow graph is, DEF: ‘The data flow equations for the above flow graph are, GEN{stmt] = (DEF} KILL{stmt] = D,~ (DEF} OUT stmt] = GEN{stmt] U (INfstmt] - KILL [stmt)) ‘Where, . ‘D,Set of all definitions for variable‘ in the program GEN[Stmt] — Set of definitions generated by stmt KILL[Stmt] — Set of definitions killed by stmt. ‘The assignment statement d: = ¢ + g is the definition “DEF of ‘@’. Irrespective of whether definition ‘DEF’ reaches starting of the statement, it surely reaches the end of the statement, Morcover, by “DEF” all other prior definitions of ‘dare killed. : (i) Stmt > Stmty When Stmt takes the form tmt;; Stmt, stmt, ‘Stmt: “The general flow graph becomes, COMPILER DESIGN [JNTU-HYDERABAD) “The data low equations for the above flow graphs are, GEN[Stmt] = GEN{Stmt,] VGENIStmt, KILL {Sm KILL{Stmt] =KILL[Stmt,]U (KILL{Stmt,]-GEN[Stmt) IN{Stmt,] = IN[Stmt,] IN(Stmt,) = OUT(Stmt,) * ‘OUTIStmt] = OUTEStint,] ‘The cascade of statements Stmt = Stmt,; Stmt, has a ‘complicated rule for GEN, ic, DEF is generated by Stmt only it itis generated by Stmt,, Moreover, if DEF is generatedby Stmt, by not killing Stmt,-then itis guaranteed that DEF reaches the end of Stmt. Similarly, the rule for KILL is applied. (li) Stme— if Expr then Stmt, else Stmt, ‘When stmt takes the form, : Simt — if Expr then Stmt, else Stmt, “Then the general flow graph becomes, if Expr goto Stmt, ‘The data flow equations for the above flow graph are, GEN[Simt]= GEN[Stmt,] U GEN[Stmt,] KILL[Stmt]= KILL{Simt,] 4 KILL[Stmt,] IN{Stmt] OUT[Stmt,] LV OUT{Stmt,} ion is generated by cither branches of if-statement then surely that definition reaches the end of the statement. Moreover, the variable defined by DEF must be killed on either branches of “if” in order to kill definition DEF. Gv) Stmt— do Stmt, while Expr When Stmt takes the form, Stmt — do Stmt, while Expr ‘Then the general flow graph becomes, : Gad ‘The data flow equations for the above flow graph art GEN[Stmt] = GEN[stmt,] KILL[Stmt] = KILL{Stmt,] IN{Stmt]= IN[Stmi] U GEN{Simt,] nit-5 Machine-Independent Optimization opr. Briefly explain the following, () Reaching definitions (ii) | Live variable analysis, ‘ OR : Whatis liveness? Explain liveness with suitable example. (Refer Only Topic: Live Variable Anatysis) Answer = ‘March-17(R13), aa(a) @@ Reaching Definitions A definition d of variable Vis said to reach a point p, if there exist path (p') from dto p along which Vis not redefined, Example Consider the following figure, B, B, ed aiq=p +? Figure: Reaching Definition from Block B, to Black B, “The above definition is said to be reaching definition from block B, to block B,. (i) Live Variable Analysis variable (say a) is said to be alive at point p if, (Its current value is used in the flow graph beginning at the point p. ©) There exist a path (say p') from start point p to end point © otherwise it is said to be in dead state. Example . Consider the following figure, B, By Figure beat nt : Sees aby ‘oticed from above figure, thata variable ais PP°%B, 10 Block Band Block Bandi led at block By * : RARE ie ca1% eps, se “ei ‘Live variables ae used in dead code elimination. and ‘ee feptaten ai 5.11 Write an algorithm to comput fe reachil definition informatory for a flow graph. Q2:; Answer : A statement that assigns a value to a variable V is a definition of VA definition d of a variable is said to reach a P. if there exists a path from d to p along which V is not redefined. The reaching definition problem is to compute for cach block, all definitions of each variable which reach the beginning of the block. The data flow equations for reaching definitions are as follows, BGNIB]= U, Predecesoe one END[B] = GEN[B] v (BGN[B] - KILL[B}) END[P] The union operator (U) in equation for BGN{B] indicates that as definition reaches a block ifit reaches the end of any of its predecessors. Algorithm ‘The algorithm for computing reaching definitions takes a flow graph as input for which the sets GEN[B] and KILL{B] have been computed for each block B. The output of the algorithm is the sets BGN[B] and END[B] computed for each block B. The algorithm initially assumes that’ BGN[B] = ¢ for each block B. It propagates reaching definitions information as long as they are not killed the algorithm is as follows. 1. Initialize END[B] = GEN[B) for each block B on the assumption that initially BGN[B] = 6 for all B. Do following until there are no changes in any of the 2s END[B] sets. (i) For each block B calculate BGN[B] =| ,Y, ENDIP] reer PREV_END[B] := END[B] GEN[B] v (BGNIB}) - KILL[B)); eal xe any changes in ENDIL 'V_END{[B] and ENDIB). helps in terminating the END[B] : (ii) Check whether there a sets by'comparing PRE Record the result this alg 1g of the reaching def ition Q23. “Explain the workin; singe sultable, Informatory algorithm example. 5 i * : Corisider the graph -hown below, 5.12 7 COMPILER DESIGN [JNTU-HYDERABAD} BI dey =k aires | 8 doxmxel a yiey=1 Coreen axwe GENT = KILUBIY |B. (4,.d,.d4) {dedi dh) GENB2] = (d,.d,) RILLIBA =a 88,8) GENTBY = (4) KILLIBS] = (4) GENIBa)= (4) KILL(B4) = (4,.4,) Figure: Flow Graph ‘The above figure shows GEN and KILL sets computed for each block. In the above flow graph, there are seven definitions iy dyna d, defining the Variables x, y and =. We use bit vectors to represent the set of definitions. In a bit vector, the bit / contains 1 if and only if the definition d,is in sthe set. ; \ “The first step of the algorithm initializes END[B] = GEN[B] for each block B on the assumption that initially BGN[B] = 4 forall B. These initial values of END[B] are shown in the table given below. The algorithm enters into the while loop and starts first iteration. Suppose in the inner for loop B takes B1, B2, B3 and B4 in that order with B = BI. BGN[B1J= ¢ represented by 000 0000 since B1 is an initial node which have no predecessors and END[B1] = GEN[B!] Which also remains equal to GENIB 1] since PREV_END{B1] = ENDIB1] the variable any changes is not set to true. ‘Next for loop takes B = B2 for which BGN and END sets are computed as follows, BGN[B2]= END[B1] V END[B3] U END[B4] 0 110000 + 0000 010 + 0000 001 = 1110011 j END|[B2]= GEN(B2] U (BGN{B2] - KILL{B2)) = 0001 100 + (1110011 ~ 1100 001) = 0011 110 Similarly BGN and END sets for B3 and B4 are computed the table given below shows these computations. f [Block Thitial Values iteration 1 lence B ponte) [ eNpioy | senior [NDI | BGNIBI | ENDER “BI 000000 | 1110000 | 000000 1110000 | ~oo0e000 | axra00@ : 2. | 000000 | ovorr00 } 0011 | corto | titi | cong 3 | 0000000 | 000010 | oo1it10 | 00in10 | “oo11110 | coots10 a | 0000000 | oo00001 | ooisti0 | ovens | oorrito | coroin dy d, and d, reach [Link] being killed in B4. The second iteration of while Joop start In this iteration there are no 9 shag ony ot a ‘omputation of BGN and END Sots for Example Flow Graph + At the end ofthe first iteration the set END[B4] = 0910111 represents that the definition is eeneraé cate atti din and definitions Sets the) Figure: Reaching Definition answer t erative Algorithin for Reaching Definition For answer refer Unit-V, Q22, Topic: Algorithm. Problem Given that, Bi &j-n @:a-ul * a:j-j-1 wa daa ' i [wasn : Figure _Inthe figure of flow graph, there are seven definitions d,, d, ‘The GEN and KILL sets for each block are as follows, For BI: GEN[BI]= (d,,d,d,) , ? | , defining the variables i, and a. KILL[B1]= {d, d,,d, d,) For B2: GEN[B2] = {d, d,} KILL[B2]= {d,,d,,d,} For B3: GEN[B3}= {d,} | KILL[B3]= {d,} : ForB4; GEN[Ba)= (4) i f KILL{B4)= (4,4, agg, NE we bit ee i ee the set of definitions. Ina bit vector, the bit contains 1 ifand only ifthe defnon sim tion at initially BGNIB] = ihe first step ofthe algorithm initializes END[B] ~ GEN[B] foreach block B onthe assump $ for : is AILB. These initial Values of END[B] are shown in the table: "Iteration for loop B takes Bl, BRB nth tort emer into the while lop and start fet iteration. sero inthe inner for boop Ss iH tha order rd withB= BI, 9. : sree ug es fe . ~y 5.14 COMPILER DESIGN [JNTU-HYDERABAD) BGN[B1]= ¢ represented by 000 0000 since BI is an initial node which [Link] predecessors and ENDJB1} = GEN{B1] = 1110000 Which also remains equal to GEN{B1] since PREV_END[B1]=END[B1] the variable any changes is not set to true, ‘Next, for loop takes B = B2,for which BGN and END sets are computed as follows, BGN{[B2}= END[B1] U END[B3] U END[B4] = GENIB1] U 9000000 L 0000000 = 1110000 + 0000000 + 0000000 110000 JEN[B2] U (BGN(B2) - KILL[B2}) = 0001100 + (1110000 - 1100001) 0001100 + 0010000 : = 0011100 “Now, for loop takes B = B3 for which BGN and END sets are computed as follows, ‘ BGN[B3] = END[B2] " 3 = 0011100 © END[B3] = GEN([B3) U (BGN[B3] - KILL{B3)) (0000010 + (0011100 - 0010000) = 0000010 + 0001100 0001110 : Now, for loop takes B = B4 for which BGN and END sets are computed as follows, > BGN[B4]= END[B2] = 0011100 END[B4] = GEN[B4] U (BGN[B4] - KILL[B4)) = 0000001 + (0011100 ~ 1901000) 1000001 + 0010100 = 0010101 END[B2} ‘Second Iteration ‘The algorithm enters into the while loop again and starts second iteration. Here, we consider th a each block obtained in first iteration. : '¢ BGN and END sets of ForB=B1; BGN{BI}=¢ = 0000000 . END[B1]= GEN[B1] = 1110000 . ND[B1] U END{B3] U END[B4) L 110000 + 0001110 + 0010101 a7 END[B2]= GEN[B2] U (BGN [B2] — KILL{B2]) 001100 + (1111111 — 1100001) 2 001100 +.0011110 a real seo tr WITH ise sey c ae For = B3; BGN(B3}= ENDIB2) 3305 (0.7 OF Sat ee ah a yy ne ea ‘ = 0011110 S eel, Si ‘ ForB=B2; BGN(B2] tion N(B3] U (BGN(B3]— KILL[B3)) 0000010 + (001111 = 0000010 + 0001110 = 0001110 : p< B4 BGN[B4]= END[B2] fe = 0011110 ENDIB4]= GENIB4] v (BGNBS) - KILL (B4)) = 0000001 + (0011110 — 1001000) = 0000001 + (9010110) = 0010111 ‘ind Iteration i The algorithm enters into the while loop again and starts third iteration. Here, we consider the BGN and END Sets of each ‘phek obtained | in second iteration. ForB=Bl; BGN(BI]=4 = 0000000 END[B1]= GEN[B1]. = 1110000 : ForB=B2; - BGN(B2]= END[B1] V END[B3] U END[B4] = 1110000+'0001110 + 0010111 =H % END[B2]= GEN[B2]_ U (BGN[B2] — KILL[B2]) = 0001100 + (1111111 - 1100001) ‘= 0001100+ 0011110 ~ = 0011110 ForB=B3; * BGN[B3]= END[B2] * = 001110 * END[B3]= GEN[B3} U (BGN[B3] - KILL{B3)) = 0000010 + (0011110 — 0010000) = 0001110 BGN[B4]= END[B2] = 0011110 s : END[B4]= GEN[B4] (BGN[B4] —KILL[B4)) = 000001 + (0011110 ~ 1001000) ee = 000001 + 0010110 por 4 = 0010111 S Tathe thira iteration of while loop there are no changes to any of the END sets. So, the algorithm terminates. 73 * Bble shows all the BGN and END sets forthe given flow graph: Block Tnitial Values Tteration 1 7 Iteration 2 B BGN(B} END[B] | BGN[B]] END[B] | BGN[B] | ENDIB] BL 000000 | 1110000 | 0000000] 1110000 | 0000000 nio9 : B2 | 0000000 | : ooor10o | siio011 | oonttto | tnt iit i 3 0900000 “ 0000010 0011110 7 0001110 sort, sae . 24 0000000 | _oo00001_ | 011110 | _ooror11_| -oorsi10-|-obto1i } * ‘Table: Computation of BGN and END Sets for Given Flow Graph 5.16 Q25. Discuss briefly about available expresgjons. Answer : Available Expression ‘An expression a + bis said to be available at point P if, (@ All possible paths from initial node of flow graph reaching P computes a+b. . i) Thereexist no assignment ocither a orbreaching P, Gi) The operands gets modified before its use. Example ‘Consider the following figure, B, B, B, P=y+z[t) yeati | a=x [tb] as Figure Itcan be inferred from above figure that, the expression 1, = 4% in block B, is available in all the three blocks B., B, and By . Advantage It helps in eliminating common sub expression. 5.3 FOUNDATIONS OF DATA-FLOW ANALYSIS Q26. Write a short note on, Foundations of data-flow analysis framework (ii) Semilattice * (iii) Partial order. . Answer: Model Pay (Foundation of Data-flow Analysis Framework ‘A data-flow analysis framework (D, S, A, F) includes the following, : D:A data-flow direction which can be either a forward or backward S : Aset of values ‘S" ‘A:A binary operator ‘”” called meet operator, F-:A set of transfer functions F : SS. F should incorporate constant transfer functions for the nodes ‘|abelled with ENTRY and EXIT in data; flow graph, Bak as, tia) COMPILER DESIGN [JNTU-HYDERABAp) ‘Semilattice ‘Asemilattice can be defined as algebraic structures, ,) with set of values ‘S” and a meet operator *A” such that for aj, dz in ‘S*it holds the following properties, i) clements of x, »-an (a) Idempotent :xAx=* (b) Commutative 2x Ay = A (e) Associative: 0 WA 2)= 8 AYLAZ tT xeS,xAT Hx “Asemilattice contains top element and a bottom element “L’W xe5, 1 A*=* (ii) Partial Order ‘A relation < represents a partial order on set *S” Wx, y and z € S it satisfies the following properties (a) Reflexive :x Sx Ifx 3 and 9 > 1. As these fier removal of back edges) and hence reducible, ‘The back edges in a flow graph can be found and eliminated if ‘cross check whether the above flow graph is reducible or not, remove the'back edges 4— 3, | are the back edges and the remaining are forward edges, the graph is acyclic (a ‘Non-reducible Flow Graph 5 ‘There are some flow graphs which are not reducible, such a flow graph is as shown in figure (2). Figure (2 Non-reducible Flow Graph Here, there are no back edges as no head of an edge dominates its tail. As, the cycle 2 —> 3 can be entered at two different places, node 2 and node 3, the flow graph is non-reducible, However, it can be reducible if the complete flow graph is acyclic. Non-reducible flow graphs are very rare. Languages like Modula 2 and Bliss allow programs with reducible flow graphs only. : Q36. Explain natural loops and inner loops of a flow graph with an example. Answer + Natural Loops 3 Ina flow graph, if there exist a back edge n — 6, then the naturalsloop of the edge tat do not go through ‘b’ to reach ‘n’. In the edge m — &, b is the head and nis the tail, is given along with a set of nodes Algorithm for Constructing the Natural Loops Input ‘A low graph G, and a back edge n> d SE a . Output . euhctiad ene ee ners] ‘ _ Asset loop of all nodes in the natural loop of 2 4,7 oui gas) - . Procedure Insért(M) #092 5 vin ‘Mis not in loop then UNIT-5 Machine-Independent Optimization . vei Push(M4) : - end i j /* Main program */ Stack = Empty Loop = {a} Insert (n) \while(stack not empty) ( pop() . for(each predecessor P of M) = Insert(P) / } A useful property of natural loops is that, the two loops in a flow graph can be neithe? nested (one inside another) nor digjoint if they don’t have the same header. Moreover, when the header is same, but still the loops are not nested then they are treated as a single loop. Inner Loops Alloop that does contain any other loop is éalled an inner loop. For example, the flow graph given in figure (1), has an inner loop 4-9 2 ice., the path from 2 3 > 4. g Figure (1): Flow Graph with an Inner Loop 4 — 2 Determining an inner loop when to loops have the same header is abit difficult ask. One such situation is depicted in 8 figure (2). Block 2 Block 3 : E Figure (2: Two Loops with the Same H ‘At the end of Block 1, ifthere is atest o be made in order to branch to either Block 2 or Block 3,say. f __,_ ifi=15 goto B, Then Biogk 15 Block 3 is most likely to b ‘is deeply examined. GEN 1 the inner loop than Block 1 —> Block 2. However, it isnot sure {until the code’ 2 COMPILER DESIGN [JNTU-HYDERABAn, —— 1PORTANT QUESTIONS | FREQUENTLY ASKED QUESTIONS AND IM SHORT QUESTIONS (mnportant Question |Dee-17R18), a4 Q1. What is machine independent code optimization? Anst For answer refer Unit-V. QL : important Question | May 2. What ig common sub-oxpression elimination? Explain. (important Question | May-490246), tq) 4 Ans: For answer refer Unit Q3. What is dead code elimination and reduction in strength? (important Question | March-17(R13),ai(g) ‘Ans: For answer refer Unit-V, Q6. Q4. Write a short note on monotone frameworks. Ans: For answer refer Unit-V, Q10, Important Question ESSAY QUESTIONS Q5: Write the principal sources of optimization. 4 Ans: For answer refer Uni O16. ay-19R1), 107) | May-t8(R4), 9 | March-16(R12, 8/2) | NowDee-20¢R16), a8) FALE Q6. With an example explain ‘common subexpression and dead code elimin: ion methods in detail. Bl 9 (Dee.-19(R16), Q10 | March-18(R13), 10) | ‘Ans: For answer refer Unit-V, QI4. Q7. “Explain loop optimization technique with example. 2 : @8. Explain how copy propagation can be done using data flow equation. gl 2i° Ans: For answer refer Unit-V, QI7. (Bec-17(R15), 9 | Mareh-16(R13), a9(6)) FEMS Q9. Write about Data flow analysis of structural programs. Ans: For answer refer Unit-V: Q20. : _Ans: i g (Important Question | May-18(R15).08 Q10, Write a short note on, (i) Foundations of data-flow analysis framework Semilattice > (lil) Partial order. ‘Ans: For answer refer Unit-V, Q26. Important Questor Q11. Explain constant propagation with example. Ans: For answer refer Unit-V, Q30. (important Question | May-19(R16), 0110), @12, Explain redundancy elimination techniques. ‘Ans: For answer refer Unit-V, Q33.

You might also like