| Program analysis techniques that automatically extract information from programs have been proposed to facilitate reasoning about and understanding program artifacts. However, existing techniques are either too inefficient or too imprecise in handling widely-used language constructs such as pointers in C programs. This dissertation presents research that develops efficient techniques for effective handling of pointers in program analyses.; Analyzing programs with pointers requires alias information that determines the memory locations that may be indirectly accessed through pointer dereferences. In the research, we implement and evaluate several existing alias-analysis algorithms that provide alias information. We compare the performance of these algorithms and evaluate the effects of using the alias information provided by these algorithms on program analyses for C programs. The empirical studies show that, because pointers are typically used in relatively simple ways by developers, simple and efficient algorithms may compute alias information close in precision to that computed by more sophisticated and more expensive algorithms. The empirical studies also show that the alias information provided by existing efficient algorithms does not effectively support program analyses: using such information, a program analysis may perform redundant computations, and may compute spurious information at callsites.; Motivated by these findings, we have developed two efficient techniques that improve the quality of alias information. Using the improved alias information, a program analysis can reduce redundant computations, and can also compute more precise information at callsites. We have also developed an efficient pointer analysis framework that can be tuned to utilize the simplicity of the common cases in which a program is written. The framework is extended to provide parameterized alias information that supports effective client program analyses. Empirical studies show that these techniques are effective: these techniques can improve the speed of a program slicer by a factor of up to 70, and can improve the precision of the slicer up to 40% on C programs. Therefore, these techniques will allow the program analysis techniques to analyze C programs effectively, and will enable and encourage the integration of these techniques with various tools to improve software quality and programming productivity. |
