Do problem 2.16.
Perform context-sensitive flow analysis for Example 2.36 (signs analysis for fibonacci) using a program that takes the maximum call-string length as a parameter. The instructor will provide skeleton code. Turn in a printout of the main program (which has all the code you will write). What improvements do you see with increasing call string length? Explain your results.
We get much better results for our analysis if we can split apart the information at a call-site into the part relevant to the call and the irrelevant part. The irrelevant part is then recombined with the results of the call to get the information after the call. For instance, we save the evaluation stack below the call, and the state of local variables as irrelevant to the callee. The evaluation stack is stuck back under the return value information, and the state of local variables is restored to complete the call.
Now, this means we are transmitting information not along the control flow, but rather around the entire call. Is this sound? Discuss what can go wrong, and what conditions are required for this ``splitting'' to be correct.
(The issues raised in the previous question do not apply, because although temporally separated, the call and return at the callee-side are syntactically conjoined.)
As with all homeworks, please turn in your homework on paper at the beginning of lecture.