Next: Related Work Up: Interprocedural Algorithm Previous: Applying a PTF

Recursive Calls

We use an iterative approach to handling recursive calls. Because of calls through pointers, we must identify the recursive cycles as the analysis proceeds. Since we already keep a stack to record the calling contexts, we can detect recursive calls by searching back to see if the call target is already on the stack. Instead of creating a new PTF for a recursive call, we just use the summary from the PTF that is already on the call stack. On the first iteration the summary may be empty, and we may need to defer evaluation of the recursive call. As long as there is some path that terminates the recursion, however, an approximate summary will eventually be provided. The iteration then continues until it reaches a fixpoint.

The PTF at the entry to a recursive cycle is an approximation for multiple calling contexts. We combine the aliases and function pointer values from each recursive call site with those recorded in the PTF. That may change the input domain for the PTF so that it no longer matches the original non-recursive calling context. To avoid that problem, we record two separate input domains for these recursive PTFs. One specifies the original input domain for the call from outside the recursive cycle, and the other combines the inputs from all the recursive calls.



Next: Related Work Up: Interprocedural Algorithm Previous: Applying a PTF


Bob Wilson