|
Abstract : |
The first interprocedural modification side-e#ects analysis for C (MODC) that obtains better than worst-case precision on programs with general-purpose pointer usage is presented with empirical results. 1 The analysis consists of an algorithm schema corresponding to a family of MODC algorithms with two independent phases: one for determining pointer-induced aliases and a subsequent one for propagating interprocedural side e#ects. These MODC algorithms are parameterized by the aliasing method used. The empirical results compare the performance of two dissimilar MODC algorithms: MODC (FSAlias) uses a flow-sensitive, calling-contextsensitive interprocedural alias analysis [LR92]; MODC (F IAlias) uses a flow-insensitive, callingcontext-insensitive alias analysis which is much faster, but less accurate. These two algorithms were profiled on 45 programs ranging in size from 250 to 30,000 lines of C code, and the results demonstrate dramatically the possible cost-precision tradeo#s. This first comparative implementation of MODC analyses o#ers insight into the di#erences between flow-/contextsensitive and flow-/context-insensitive analyses. The analysis cost versus precision tradeo#s in side-e#ect information obtained is reported. The results show surprisingly that the precision of flow-sensitive side-e#ect analysis is not always prohibitive in cost, and that the precision of flow-insensitive analysis is substantially better than worst-case estimates and seems su#cient for certain applications. On average MODC (FSAlias) for procedures and calls is in the range of 20 % more precise than MODC (F IAlias); however, the performance was found to be at least an order of magnitude slower than MODC (F IAlias)., |
