Consider the following Tiger code that gets converted to its MIPS assembly: function main()    begin        let            var a, i : int := 0;            var b : int := 1;        begin            a := a + b;            while (i < 10) do                a := a + b;                if (i < 5) then                    a := a + b;                else                    a := a - b;                endif;                a := a + b;                i := i + 1;            enddo;            printi(a);        end    end main:   addi $sp, $sp, __    li $t1, 0    li $s2, 0   li $t0, __    add $s2, $s2, $t0_L0:   li $t8, __   bge $t1, $t8, __    add $s2, $s2, $t0    li $t8, 5   bge $t1, $t8, _L2    add $s2, $s2, $t0   j ___L2:    sub $s2, $s2, $t0_L3:    add $s2, $s2, $t0   addi __, __, 1   j ___L1:    move $a0, $s2    li $v0, 1    syscall    li $a0, 10    li $v0, 11    syscall   addiu $sp, $sp, 40    jr $ra The MIPS assembly for the above code has some parts replaced with underline blanks. What values, temporary variables or labels need to be in these blanks?

Given L1 and L2  is a regular language, which of the following are regular languages?

Compilers, like programmers, can introduce inefficiencies while translating source language into IR. As a result, the compiler’s optimizer is very important in removing these inefficiencies. Give two examples of inefficiencies you would expect an optimizer to improve. Give two examples of inefficiencies you would expect an optimizer to miss, even though they can be improved. Explain why an optimizer would have difficulty improving them. (8 pts)

Which of the following situations can NOT always be guaranteed to be reported at compile time?  (Select all that apply) (4 pts)

Minimize the following DFA using Brzozowski’s algorithm.  Show the resulting DFA after the first (backward) pass. Show the final resulting DFA after the second (forward) pass.  You may choose the names for states in each DFA. Write each DFA in the following format, illustrated with the original DFA:  States: 0, 1, 2, 3 Start state 0  Accepting states: 1, 3 Transitions: (0, a) = 1, (0, b) = 2, (1, a) = 1, (2, a) = 3, (3, a) = 3 (12 pts)

Consider the optimization of inlining: replacing a function call by expanding the called function’s body into the caller. Here is a simple example in Tiger IR to illustrate its behavior. Without inlining start_function square int square(int x) int-list: x float-list:square: ret = x * x; return ret;end_function square// somewhere else in the program: b = a * 2; r = call square(b); if a < r goto label1; With inlining, the code at the end becomes b = a * 2; r = b * b; // this line changed if a < r goto label1; Assuming no other optimizations occur, what is the performance benefit of inlining a function call? If other optimizations occur, can inlining provide further benefits? If so, describe how. Describe a way in which inlining may worsen performance. Based on parts (1) – (3), give a heuristic that an optimizer could use to decide if an individual function call should be inlined – i.e., the benefit of inlining it is likely to exceed the drawback. Are there cases where a function call cannot be inlined because doing so would cause incorrect or erroneous behavior? Briefly explain why or why not. (15 pts)

Consider the language of strings accepted by the regular expression (ac)+ | (ad)+.  Write an LL(1) grammar for this language.   {a, c, d} are terminal symbols.   State the start symbol.  Write grammar rules in BNF format, e.g.  ->  c | Compute First and Follow sets for each non-terminal symbol.  Write the sets as e.g. First(non-terminal) = { a, b, c }  Compute the parse table for the grammar.  Write parse table entries as e.g. P[non-terminal, a] = -> c  Briefly explain why the grammar is LL(1).  (16 pts)

Consider the following algorithm to perform liveness analysis: Perform a postorder traversal of the control flow graph When visiting each basic block B: Iterate backward through the instructions of B Calculate LiveOut and LiveIn using the data-flow equations (Def and Use) for each instruction Is this algorithm correct? Briefly explain why or why not. (5 pts)

identify structure #17 [BLANK-1] identify structure #18 [BLANK-2]

Briefly describe these two forms of divergent thinking:  brainstorming and group mind mapping.