1.Three Address Code Three Address Code-4 Translate the following program fragment to 3 address code using T1, T2, ... for temporaries and L1, L2, for labels, and upper case letters for variables /* this computes x^n in log_2(n) steps using the following identities */ q^(2n) = (q^2)^n q^(2n+1)= q (q^2)^n p = 1; q = x; while (n> 0) { // invariant p*q^n is constant at this point in the program if (n%2==0){ n = n/2; q = q*q; } else { n = (n-1)/2; q=q+q; } Translation: P=1 Q=X if false (N>0) goto (L1) L1:/nFlow Graphs -4 Consider the following program in 3 address code. 1) find and label the Basic Blocks 2) draw the Flow graph for this program (ideally using graphviz) and 3) find the loops in this program (as sets of basic blocks) Cut/paste your basic block decomposition below and list of loops below and include a link to a movie where you explain how you decomposed the code into basic blocks and how you created the flow graph, and found the loops, and also show the flow graph. i-m-1 j-n t1=4*n v=a[11] L1: L2: i=i+1 t2=4*1 t3=a[12] if t3<v goto (L1) j-j-1 t4=4*j t5=a[t4] if t5>v goto(L2) if ij goto (L3) +6=4*1 x= a[6] t7=4*1 t8=4*j +9=a[18] a[17]=t9 a[t11]=x goto(L1)/n3. Register Allocation LOAD V R STORE RV Consider the machine language with the following instructions which copies the value in stack location V to register R which copies the value in register R to stack location V which is D D+S where S and D are registers ADD 5 D MUL S D SUB SD which is D = D+S which is DD-S DIV S D which is D = D/S and assume that values V1, V2, V3... are in the stack. You can introduce as many new variables V4, VS,.... Compile the following program into this assembly language using A) 4 registers B) 3 registers C) 2 registers and estimate the time required where an arithmetic operation counts as 1 time step but a LOAD or STORE counts as 18 time steps. V1 = (V1-V2)*(V1+V2) + (V1-V3)+(V1+V3) For example, it could start with LOAD V1 R1 LOAD V2 R2 SUB R2 R1 and end by storing some register value into V1 STORE R1 V Cut/paste your answers below (including the assembly code) and record a short movie explaining how you compiled these expression using only two, three, four registers. Don't give all the details, just explain enough so we know your strategy for each of the three cases and we could follow your strategy for a new problem.

Fig: 1

Fig: 2

Fig: 3