CS 553 Compiler Construction — Fall 2005 Homework #3Interprocedural Ptr Analysis, Reg Alloc, Instr Sched, Data Dep Analysis, etc.Due December 9, 2005Write your answers on another sheet of paper. Homework assignments are to be completedindividually. Hand written submissions are fine, but they must be readable. Due at the beginningof class. Total points: 150, 5% of course grade1. [10 Points] True or False. If a statement is false, explain how so.(a) It is possible to do full-path, context-sensitive analysis for recursive functions.(b) Trace scheduling requires memory dependence profiles.(c) The second Futamura projection compiles a program.(d) The value dependences within a program are a subset of all the memory dependences ina program.(e) Unimodular transformation frameworks subsume the unifying transformation frameworkbuilt on presburger arithmetic.2. [20 Points] Interprocedural pointer analysis. Do flow-sensitive, points-to analysis with threedifferent levels of context sensitivity: none, one-level, and full path.int g;void main () {int a,b,c;foo(&g, &a); // call site 1 (CS1)foo(&a, &c); // CS2}void foo(int *p, int *s) {bar(p,s); // CS3}void bar(int *i, int *j) {...}Partial answer:At the Context Sensitivitybeginning of ... NONE One Level Pathmain ∅ ∅ ∅foo {p → g, p → a, s → c, s → a} ?? ??bar ?? ?? {([CS1, CS3], {i → a, j → c, }), ??}13. [50 Points] Register Allocation. Here is an example program. (Hint: for this problem youwill need to rewrite the program five time s).y = ...t = ...a = 3 + tb = ac = ax = 40if (y<x) goto L1z = y + cx = b + 30goto L2L1:z = y + 30L2:t = z + x(a) Find and show the webs within the example. Provide a version of the program whereeach web has been assigned a symbolic register.(b) Construct an interference graph and perform as many iterations of coalescing and in-terference graph construction as is possible. Show all your steps. Coalesce the copystatements in the order they appear in the example.(c) Use the Briggs register allo c ation algorithm to color the graph assuming there are tworegisters available. Visit the nodes in the graph in alphabetic order if a number of nodeshave the same number of interferences edges. Show the code and any new interferencegraph if spilling occurs.(d) What is the final code once the variables have been assigned to registers R1 and R2?Partial answer:Here are the interference graphs you will be generating.abt0t1zyxc2abt0t1zyxcabt0t1zyxct0t1zyxabct0t1zyxabc34. [30 Points] Instruction Scheduling. The loop shown belowfor (i=1000; i>0; i--) {x[i] = x[i] + s;}can be converted to MIPS asse mbly as follows:// body of the loopLoop:L.D F0, 0(R1) // F0 = &R1ADD.D F4, F0, F2 // F4 = F0 + F2S.D F4, 0(R1)DADDI R3, R3, #-1 // R3 = R3-1DADDI R1, R1, #-8 // R1 = R1-8BNE R3, R2, LoopUse the following set of interlocks/latencies between different instructions when the secondinstruction depends on the first instruction. For example, the architecture will interlock for 3cycles between two DADDI instructions if the instructions are scheduled one after the other. Ifonly one instruction is scheduled in between the two, there will still be two cycles of interlock.second instructionfirst instruction ADD.D S.DADD.D 3 2L.D 1 0The body of the loop given above requires 9 cycles to execute. Use list scheduling with thefollowing priorities to find a schedule that only requires 7 cycles:(a) Avoid stalls with previously scheduled instructions.(b) Does the instruction interlock w ith any immediate successors?(c) How many successors does the instruction have?(d) Is the instruction on the critical path?Show the DAG that you use to perform the scheduling. Assume that the BNE instructionmust occur last.44. [40 Points] Data dependence analysis with Omega.integer i,j,Nreal a(0:99)for i=0,(N-1) dofor j=0,(N-1) doa(j) = a(i-2)endforendfor(a) What is the anti-dependence relation between the read to a(i-2) and the write to a(j)?(b) Write a Tiny program that results in the following data-dependence relation. There willbe other data-dependence relations. The one provided will be one of many.[i,j] -> [i+3,j-2] : 0 <= i <= N-4 && 2 <= j < N(c) Focusing only on the flow dependence from c(i) to c(i+1), use omega to show that loopfusion is illegal on the following two loops:for i=0,(n-1)c(i) = a(i) / 2endforfor j=0,(n-1)d(j) = 1 /
View Full Document
Unlocking...