Context Sensitivity
Introduction: Interprocedural analysis is challenging because the behavior of each procedure is dependent upon the context in which it is called. Example 12.2 uses the problem of interprocedural constant propagation on a small program to illustrate the significance of contexts.
Example: Consider the program fragment in Fig. 12.3. Function / is invoked at three call sites: c1, c2 and c3. Constant 0 is passed in as the actual parameter at c1, and constant 243 is passed in at c2 and c3 in each iteration; the constants 1 and 244 are returned, respectively. Thus, function / is invoked with a constant in each of the contexts, but the value of the constant is context-dependent.
As we shall see, it is not possible to tell that t1, t2, and t3 each are assigned constant values (and thus so is X[i)), unless we recognize that when called in context c l , / returns 1, and when called in the other two contexts, / returns 244. A naive analysis would conclude that / can return either 1 or 244 from any call.
One simplistic but extremely inaccurate approach to interprocedural analysis, known as context-insensitive analysis, is to treat each call and return statement as "goto" operations. We create a super control-flow graph where, besides the normal intraprocedural control flow edges, additional edges are created connecting
1. Each call site to the beginning of the procedure it calls, and
2. The return statements back to the call sites.1
Assignment statements are added to assign each actual parameter to its corresponding formal parameter and to assign the returned value to the variable receiving the result. We can then apply a standard analysis intended to be used within a procedure to the super control-flow graph to find context-insensitive interprocedural results. While simple, this model abstracts out the important relationship between input and output values in procedure invocations, causing the analysis to be imprecise.
Example: The super control-flow graph for the program in Fig. 12.3 is shown in Figure 12.4. Block BQ is the function /. Block B3 contains the call site c l ; it sets the formal parameter v to 0 and then jumps to the beginning of /, at BQ. Similarly, B4 and £5 represent the call sites c2 and c3, respectively. In £4, which is reached from the end of / (block BQ), we take the return value from / and assign it to t1. We then set formal parameter v to 243 and call / again, by jumping to B6. Note that there is no edge from B3 to B4. Control must flow through / on the way from B3 to B4. B5 is similar to B4. It receives the return from /, assigns the return value to t2, and initiates the third call to /. Block B7 represents the return from the third call and the assignment to X[i],
If we treat Fig. 12.4 as if it were the flow graph of a single procedure, then we would conclude that coming into BQ, V can have the value 0 or 243. Thus, the most we can conclude about r e t v a l is that it is assigned 1 or 244, but no other value. Similarly, we can only conclude about t1, t2 , and t3 that they can each be either 1 or 244. Thus, X[i] appears to be either 3, 246, 489, or 732. In contrast, a context-sensitive analysis would separate the results for each of the calling contexts and produces the intuitive answer described in Example: t1 is always 1, t2 and t3 are always 244, and X[i] is 489.
Call Strings: In Example 12.2, we can distinguish among the contexts by just knowing the call site that calls the procedure /. In general, a calling context is defined by the contents of the entire call stack. We refer to the string of call sites on the stack as the call string.
Example: Figure 12.5 is a slight modification of Fig. 12.3. Here we have replaced the calls to / by calls to g, which then calls / with the same argument. There is an additional call site, c4, where g calls /. There are three call strings to /: (cl, c4), (c2, c4), and (c3, c4). As we see in this example, the value of v in functions / depends not on the immediate or last site c4 on the call string. Rather, the constants are determined by the first element in each of the call strings.