Blog

Consider the following Tiger code that gets converted to its…

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?

Compilers, like programmers, can introduce inefficiencies wh…

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)

Consider the following algorithm to perform liveness analysi…

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)

Consider the language of strings accepted by the regular exp…

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)

For each of the following scenarios, give an IR example of a…

For each of the following scenarios, give an IR example of a basic block where local value numbering and associated optimizations enable the specified improvement to code performance. Show both the original (unoptimized) and final (optimized) versions of the IR.  Local value numbering and associated optimizations allow CISC instruction(s) to be selected. Local value numbering and associated optimizations reduce the live range of a variable. (10 pts)