Optimising Compilers Supervision 4

Exercises

Bolded items are taken from the worksheet.

1. Section 1
2. Section 2
3. Exam question: 2008 Paper 9 Question 16
4. Section 4
5. Exam question: 2002 Paper 9 Question 7
6. Consider the x86x64 GNU Assembler output below.
   1. Construct the flow graph corresponding to this program, where each flow graph node is a basic block. You may consider the sequence leave; ret as corresponding to the distinguished EXIT block. (4 marks)
   2. Label the basic blocks and show the dominance tree. (3 marks)
   3. Indicate any back-edges in the flow graph. (1 mark)
   4. Write down a decompiled version of this function in a C-like language, without making use of the goto statement. Comment on the features of the graph that compelled you to use particular constructs of the language (if statements, loops etc.) to represent this program. (8 marks)
   5. What function does this assembly code implement? (2 marks)

   
   _ENTRY:
         pushl   %ebp
         xorl    %eax, %eax
         movl    %esp, %ebp
         pushl   %edi
         pushl   %esi
         movl    8(%ebp), %esi
         testl   %esi, %esi
         je      L11
         cmpl    $1, %esi
         je      L4
         cmpl    $2, %esi
         je      L4
         movl    $1, %edi
         movl    $1, %edx
         movl    $2, %ecx
         jmp     L8
   L16:
         movl    %eax, %edx
   L8:
         incl    %ecx
         cmpl    %ecx, %esi
         leal    (%edi,%edx), %eax
         movl    %edx, %edi
         jne     L16
   L11:
         popl    %esi
         popl    %edi
         leave
         ret
   L4:
         popl    %esi
         movl    $1, %eax
         popl    %edi
         leave
         ret
   

   Bear in mind that:
   1. In GNU Assembler the source operand is the one on the left, and the destination the operand on the right.
   2. leal (%r1, %r2), %r3 puts the sum of the values of r1 and r2 into r3.
   3. The argument to this function arrives in memory at location 8(%ebp) (which you might be more familiar with seeing as [ebp+8]).
   4. cmpl subtracts one argument from another, discarding the result but changing the flags.
   5. testl ANDs one argument with another, discarding the result but changing the flags.
   6. je jumps if the flags indicate the last result computed was 0, jne is the obvious complement.
   More information on x86 assembler is available here and here.