27 Switch-case statements and Run-time storage manage ment
Rajeswari Sridhar
In this module we will discuss the pending constructs in generating three-address code namely switch-case statements. We will also discuss the procedure involved in generating three-address code for expressions involving mixed operands. Run-time memory management is essential in knowing how the function calls are handled by the compiler and in this module we will discuss that as well. Finally, we will conclude this module with the various parameter passing techniques
27.1Mixed Operands
Boolean expressions can have arithmetic sub-expressions. A Boolean can be considered as arithmetic in languages where true is “1’ and false is “0”. We could incorporate short-circuit information to handle this as well. Consider the following grammar:
• E à E+E | E and E | E relop E | id
In this scenario, the variable E could refer to an arithmetic expression or could be a boolean. If one of the ‘E’ in E à E+E is arithmetic and other is Boolean, how can the compiler allow computation of addition of the two expressions is the cause of concern. The semantic rules should handle this situation and generate appropriate three-address code. Another example is the expression “E+E” could produce arithmetic result and could be “and” with another boolean expression’s result.
The following is the set of semantic rules which are added along with the other semantic rules which are part of the arithmetic expression grammar for the production E àE1 + E2. As the LHS variable is to store an arithmetic result, we assign the type of this variable E as arithmetic. We use two types of values for the variable E. If the value of the expression is ‘0’ or ‘1’ it is said to be of type “bool” meaning Boolean, else it is said to be of type “arith” meaning arithmetic.
E.Type := arith;
if E1.type = arith and E2.type = arith
E.place := newtemp
E.code := E1.code || E2.code ||
gen(E.place ‘:=‘ E1.place ‘+’ E2.place)
else if E1.type = arith and E2.type = bool
E.place := newtemp
E2.true := newlabel
E2.false := newlabel
E.code := E1.code || E2.code ||
gen(E2.true ‘:’ E.place ‘:=‘ E1.place +1)
gen(‘goto’ nextstat +1)
gen(E2.false ‘:’ E.place ‘:=‘ E1.place)
else if E2.type = arith and E1.type = bool
E.place := newtemp
E1.true := newlabel
E1.false := newlabel
E.code := E1.code || E2.code ||
gen(E1.true ‘:’ E.place ‘:=‘ E2.place +1)
gen(‘goto’ nextstat +1)
gen(E1.false ‘:’ E.place ‘:=‘ E2.place)
else …
The logic behind the semantic rules is that if the expressions are arithmetic, we proceed in a similar manner as the expression grammar. If the expressions are mixed, then we increment or decrement depending on one of the expressions being true or false. In the first set, we verify if both the expressions are of type arithmetic and simply proceed like arithmetic expression grammar. In the second and third cases, we will check which expression is Boolean and assign two labels as true and false for this Boolean expression. At the corresponding label we compute the LHS variable’s value as the RHS’s arithmetic variable’s value +1 or arithmetic variable alone depending on whether the Boolean RHS variable is true or false respectively. The “goto” in between the two “gen” ensures that we don’t compute both and skip the computation of “false” label.
27.2 Switch-case statements
A switch-case statement is a shorter representation of nested if-else statements. The switch case statement’s general construct is given below. There is an expression which is evaluated and the various case statements are the different values that the expression would get. After every case statement, there is a break which will come out of the switch – case construct. The presence of a default statement is optional.
Switch expression
begin
case value: statement
case value: statement
…
default: statement
end
The semantic rules necessary to generate three-address code for the switch-case statement involves the following steps:
• Evaluate the expression
• Find which value in the list of cases is the same as the value of the expression
• Execute the statement associated with the value found and come out of the switch-case construct The following is the translation scheme of the switch case which by itself represent the three-address code.
• Code to evaluate E into t
• goto test
• L1:code for S1 goto next
• L2:code for S2
goto next
…
• Ln:code for Sn goto next
• test: if t = V1 goto L1
if t = V2 goto L2
…
if t = Vn-1 goto Ln goto Ln
• next:
In the above sequence, the first step is to compute the expression E and store it in a temporary variable‘t’. We generate a ‘goto’ to compare the value of the variable with known cases of the switch case. The various cases of the switch-case is available in variable V1, V2, .. and the default case does not have a value V. The block of “test” compares and generates a goto to the appropriate body of the case statements. If the value does not match with any of the Vi, then this case corresponds to the default case and that is handled by the goto Ln statement. After every case body S1, S2,..Sn, there is a “goto next” to come out of the switch-case construct.
27.3 Run-time Memory management
To compile and execute the program, we need to use memory to store:
• Code
• Static data (global variables)
• Dynamic data objects – data that are used when executing a certain procedure as well as dynamically allocated objects where user requests memory using malloc, new, etc., depending on the programming language.
Figure 27.1 shows the memory layout where the code, static data are stored. Stack data occupies the top portion while heap memory occup ies from bottom to top. Static allocation is typically known during compile time and it is typically occupied by static variables and
global variables of a function. Stack allocation is the result of memory required during function calls and Heap allocation results during dynamic memory allocation.
Static allocation lays out storage for all data objects at compile time. The advantage of this approach is memory management becomes simple. However, the constraints of this approach of memory allocation is ,
• size of object must be known and alignment requirements must be known at compile time.
• Recursion is not supported
• Dynamic data structure is not supported
A balance of the pros and cons of this approach need to be managed and we need some static allocation as part of the program.
27.3.3 Stack allocation
Stack allocation manages the run time storage as a stack. Stack allocation is managed by creating a new activation record for every function call. When a function call happens, t he activation record is pushed on when a function is entered. The same activation record is popped off as the function exits. The constraints of this approach are
· Values of locals cannot be retained when activation ends. So local variables need to be properly returned to the caller.
· A called activation cannot outlive a caller.
The constraints of the stack memory are unavoidable as we modularize our programs and hence there will be function calls. We need to take care of handling the constraints to achieve correct result.
The stack memory management is done by the compiler. The procedure is implemented by defining a function calling sequence and a matching return sequence. A calling sequence allocates an activation record and enters information into its fields (push the activation record). On the opposite of the calling sequence is the return sequence. Return sequence restores the state of the machine so that the calling procedure can continue execution. A Calling Sequence typically does the following sequence of actions after creating an activation record.
• The caller evaluates actual parameters and push these actual parameters on the stack
• The caller saves return address(program counter) and the old value of stack pointer (sp) into the stack
• The caller increments the sp
• The callee saves registers and other status information
• The callee initializes local variables and begins execution. After executing a function the called function returns control to the caller and this is defined using the return sequence and the following are the typical sequence of actions:
• The callee places a return value next to the activation record of the caller.
• The callee restores other registers and sp and return (jump to pc).
• The caller copies the return value to its activation record.
27.3.4 Heap allocation
Memory is allocated and freed dynamically as needed at runtime from a data area called as heap. The memory architecture of figure 27.1 indicates that this memory grows from bottom to top. Heap allocation is essential as we cannot predetermine all memory requirements and have then as static variable. The requirements for heap memory are that the procedures to be activated in the LIFO manner and the compiler should support true dynamic memory management.
27.3.5 Access to non-local variables
Nonlocal variables in programming languages like C (without nested procedures) would still have nested scopes (blocks). The problem is whether to consider them as static, stack or heap variable? The simple proposed solution is as follows:
• All data declared outside procedures are static.
• Other names must be in the activation record at the top of the stack, can be accessed from sp.
– Treat a block as a parameter- less procedure
– Allocates space for all blocks in a procedure.
• If p is nested immediately within q in the source text, then the access link in an activation record for p points to the access link in the record for the most recent activation of q.
• A procedure p at nesting depth n_p accesses a nonlocal ‘a’ at nesting depth n_a: (1) following n_p – n_a links and (2) using the relative offset in the activation record.
27.4 Parameter Passing
Parameter passing is the method to associate actual parameters with formal parameters. The parameter passing method will affect the code generated. The four major types of parameter passing techniques are Call by value, Call by reference, Call by copy-restore, and Call by name. Let us discuss each one of them in detail in the following sub-sections
27.4.1 Call by value
In this method of parameter passing, the actual parameters are evaluated and their r-values are passed to the called procedure. A formal parameter is treated like a local name, so the storage for the formals is in the activation record of the called procedure. The caller evaluates the actual parameters and places their r-values in the storage for the formals. Consider the following example that has a function swap( ) and the main ( ) function in the C programming language. The function swap, tries to exchange the values in the variables ‘a’ and ‘b’.
Swap(int a, int b)
{int temp;
temp = a; a = b; b = temp;
}
Void main()
{int a = 1, b = 2;
Swap(a, b); printf(“%d \t %d”, a, b);
}
When this function is called from main() the actual arguments “1” and “2” are passed as values in the activation record. The function swap() considers these values and swaps them in the activation record. Once, the swap function returns, the activation record is removed and thus the swapping of the variables does not take place. This is the drawback of call by value. This is restored in the Call by reference method of parameter passing.
27.4.2 Call by Reference
This method of parameter passing is also referred to as call-by address or call-by- location. The caller passes to the called procedure a pointer to the storage address of each actual parameter. Actual parameter must have an address and hence only variables make sense while expressions do not make much sense. Thus the location of the temporary variable that holds the result of the expression will be passed as parameter.
Consider the same example as discussed in Call by value. But, here we pass reference, that is the address of the parameters and hence in the activation record, address of the variables gets passed. As the swap function tries to change the values of the variable in the addresses that has been passed, call by reference ensures swap function is computed correctly. Call by reference is implemented by C++, Java etc.,
Swap(int * a, int * b)
{int temp;
temp = *a; *a = *b; *b = temp;
}
Void main()
{int a = 1, b = 2;
Swap(&a, &b); printf(“%d \t %d”, a, b);
}
27.4.3 Call by Copy-Restore
This technique is a hybrid between call-by- value and call-by-reference. The actual parameters are evaluated and its r-values are passed to the called procedure as in call-by- value. When the control returns, the r-value of the formal parameters are copied back into the l- value of the actuals.
Considering the same example of swap function, if the function is called as “swap(i,a[i])” it works correctly using copy-restore. Location of a[i] is computed and preserved by the calling program before initiating the call. This parameter passing technique is used by Fortran.
27.4.4 Call by name
This technique of parameter passing is defined by the copy-rule of Algol. Every procedure is considered as if it were a macro. The actual parameters are literally substituted with the formal as a macro-expansion. Local names of called procedures are kept distinct and it may be renamed. Actual parameters are surrounded by parentheses to preserve integrity The following are permitted and yields correct results in call by name technique:
- x : = f(A) + f(B)
- Here A , B are expressions
- Substitution of expressions A and B in the formal parameter leads to call by name parameter passing technique being implemented.
Summary: In this module, control flow statements involving switch – case are studied. We also discussed run-time storage management in the context of Static, Stack, and Heap memory allocation. We also discussed the various parameter passing techniques.