Exam Paper in Compilers IV 
23rd January 2004 
Answer 2 questions 
1. 
(a) Analyse the reasons why, in a programming language, it can become desirable for the language implementor to provide a heap storage allocation and deallocation mechanism. Yom answer should compare the advantages and disadvantages of heap allocation with an alternative dynamic store allocation approach. (6 marks) 
(b) Describe two distinct approaches to the provision of automatic mechanisms for the recovery of unused heap storage buffers. Your answer should give outline algorithms and give some cost-benefit assessment of the two approaches. (14 marks) 
2.	Assuming that you have a compiled vector language, compare and contrast two different approaches to generating code for statements of the form a +- b * c - d where a,b,c,d are all vectors whose lengths and type are known at compile time. (20 marks) 
3.	Describe, justify and give diagrams for minimally adequate function call mechanisms for languages with the following characteristics. 
(a) A language that provides only non-recursive function calls and allows no nesting of functions, but does allow the passing of function parameters to other functions and the returning of function results. Assume the language is strongly typed but that types are not recursive. (8 marks) 
(b) A language that provides recursive functions within the scope of which other functions can be declared but which does not allow the returning of function results or the passing of function parameters. (6 marks) 
(c) A language which is the same as that in case (a) except that it allows function nesting. (6 marks) 
1 

I 
Compilers IV answers 
1 Storage allocation question 1.1 Part a 
This question is designed to get the students to compare heap and stack allocation mechanisms and identify when heap allocation techiques become required. The students have to recognises stacks as an alternative mechanism for dynamic allocation. Reasons why heaps may be prefered that would be accepted are 
•	the presence of dynamically sized arrays. This would be a possible reason why heaps might be needed but a point would be allocated if the student recognised that it was still possible to handle these on a stack. 
•	the presence of records and pointers to records, these make some form of heap necessary. 
•	the presence of dynamically created objects which can reference other objects makes heaps necessary 
•	the presence of retained environments such as when functions return nested functions makes heaps necessary 
A point would be given for each of these that are identified. A point would be given for arguing that heaps are slower than stack allocation and thus should not be used when not required. An additional point for saying that heap allocation is costly to implement and thus should only be used when required. 
Maximum of 6 points awarded. 
1.2 Partb 
This basically is asking students to describe two garbage collection schemes. One point is awarded for mentioning garbage collection at all. One point is awared for each of two methods that they identify with a max of 2 points from the list of methods 
• Mark sweep. 
• Semi-space 
• Reference counting 
For mark sweep and semi-space algorithms the students should mention the problem of determining where pointers are in the stack and in heap objects ( 1 point for each mentioned) and points will be given for solutions to these problems such as : tagging every word to indicate if it is a pointer, having 2 stacks one for pointers one for non pointers, having a pointer in each activation record 
1 

to a frame descriptor: partitioojng objects into pointer and non-pointer fields, putting class pointers into the start of objects refering to a format descriptor. (point for each method giwn) 
For the algorithms 
•	~Iark sweep: must identify each phase, must be capbable of performing transitive closure of reacbability in mark phase. Point for mentioning disMvantage of fragmentation. 
•	Ref counting must mention circumstances in which deallocation occurs ( count =0 ). circumstances in which mum decremented ( leaving scope, deleting another object: assigning over a used pointer), circumstances in which count incremented (parameter passing: assignment). Can mention constant costs as advantage, should mention non collection of loop structures. 
•	Semi space, identify two phases; copy over stack referenced objects, passing through the new space copying over the objects stiU pointed to in old space, ~Iention non-fragmentation as advantage, mention doubling of size as disadvantage. Mention use of indirect pointers. 
2 Vector expressions 
The question is designed to get the students to compare the simplicity of an implementation based upon using a Map functional with the efficiency that can be achieved by decomposing the expression into equivaJent while loops. 
For the approach that uses the Map funtionaJ the students will be expected to give at least a C prototype of the functional showing the parameters that would have to be passed; 
1.	The address of an operator function 
2.	The addresses of the source vectors 
3. The ranks sizes of the vectors if these are not encoded in the vector headers 
Note that since the question does not ask for an array language but for a vector language, the full complexity of handling expressions of mixed rank can be avoided. 
Within the functional the students should indicate that a loop is executed and that the functional will typically allocate a buffer to return the result. 
For the optimal version the students would have to present the rewrite of the original expression as 
for i=O to min(len(b),min(len(c),len(d))) -1 do a [i] =b [i] *c [i] -d [i] ; 
2 

The students should discuss the advantages of this approach mentioning: 
The fact that register allocation can be used for all intermediate vectors. 
The avoidance of cache poUution. The avoidance of unnecessary function calls. 
Disadvantages mentioned should be the greater complexity of analysis . 
..\. point should be awarded if the problem of data flow hazards are mentioned though this only occurs if transpose or shift operators are allowed in the language), and the reasons why this may favour the Map functional approach. 
3 Call mechanisms 
a r This like FORTRAN IV with higher order functions. Since there is no recursion. no stack is needed, (1) both parameters (1) and local variables (1) can be allocated in static memory. The caU and return mechanism can use a branch an link mode1like so that w call foo(99) for a fimction declared as 
function foo(int bar) 
we can generate the sequence 
mov [faa_bar]. 99 mov [foo_ret}, next jump foo 
next: 
(2marks) 
For foo we generate 
section .data foo_ret dw 0 ; faa_bar dwO section .text foo: 
; body of foo jump [foo_ret] (2 marks) 
holds return address parameter bar 
return code 
Functions passed as parameters are simply passed as labels, similarly for function results (1) 
b) This can be implemented using a display (1) the display has a pointer to each lexical level. Since there is recursion a stack must be used (I), parameters are addressed with +ve offsets from a base register (1), locals allocated on stack and addressed using a negative offset (1 ). On entering a new procedure the ctlrent frame pointer register is added to the display on stack(l) or in registers(l). 
c) Since functions can be nested and since function results can be returned this means that a returned function can now access parameters of a previously called activation(I). We thus modify the previous model (a) in cases where a function is returned. Consider 
3 

foo(int bar-> fn(->int» begin 
return zot(->real) sqrt(bar); end 
a= foo(4) 
b = foo(9) print(aO ,bO) -> 2 3 
(1 mark for an example) 
To do this we modify those functions that return a result so that they copy their parameters to a newly created heap block when caHed(I). They also store locaJs in this heap blockJ.(I) 
Returned functions come back as [Iabel,heap pntrj(l). All functions have hidden parameter - their heap context.(l) 
4