CSCE [45]655 Midterm Exam
Due 10/22/15 at 5:30pm CDT
To complete this exam, you are free to use written or online material. Of course if/when you do use such material you should provide proper citation(s). You are NOT to discuss this exam with any human other than myself --- and I won’t be much help. (And you’re NOT to use online material written by other members of this class or any online material you solicit, e.g. “Hey Ron Cytron, how about telling me about SSA.”)
1. Consider the following control flow graph:
B1
B2
B3
B4
B5 B6
B7 B8
B9
B10
In the above control-flow graph, X is a global variable. All other variables listed should be considered local variables. (In this context, local means within the function represented by the control flow graph. Global means the variable has program scope.)
Complete the following:
1. Show the Dominator Tree.
2. Show the Post-Dominator Tree.
3. List the dominator frontier for each basic block of the CFG.
4. Insert the (non-minimal) phi-nodes (I suggest that you use Morgan’s simple algorithm).
2. Welcome to Compilers-R-Us. We see on your resume that you’ve taken a course from that renowned teacher of compiler optimization, Herr Docktor Professor Sweany. Because of that we’re putting you in charge of our optimizer team for the company’s single piece of software, our Phonetic Compiler. As you no doubt well know the Phonetic Compiler (PC) will generate excellent code for a wide range of cell phone manufacturers’ targets. Of course, the project will use the LLVM compiler as a front end and will map all languages, including C, C++, Java, Haskell, …, to the Common Instruction Architecture (CIA) that is becoming the standard instruction set for all hand-held devices. Since Compilers-R-Us has only enough venture capital to last 7 months, our first product release will be 6 months from now. Your first job is to outline what optimization(s) we should include in that first release. And to help us plan for future projects, including hiring enough compiler engineers to complete the work we’d also like your thoughts on what we should include in the 2nd release of PC, which will follow release one by 18 months. In both cases (the 6 month deadline and the following 2 year deadline) you should indicate why you chose the optimizations that you have and those you’ve left out (i.e. your reasons for those choices).