Program understanding can be assisted by tools that match patterns in the program source. Lexical pattern matchers provide excellent performance and ease of use, but have a limited vocabulary. Syntactic matchers provide more precision, but may sacrifice performance, robustness, or power. To achieve more of the benefits of both models, we extend the pattern syntax of AWK to support matching of abstract syntax trees, as demonstrated in a tool called TAWK. Its pattern syntax is language-independent, based on abstract tree patterns. As in AWK, patterns can have associated actions, which in TAWK are written in C for generality, familiarity, and performance. The use of C is simplified by high-level libraries and dynamic linking. To allow processing of program files containing non-syntactic constructs such as textual macros, mechanisms have been designed that allow matching of ‘language-like’ macros in a syntactic fashion. We survey and apply prototypical approaches to concretely demonstrate the tradeoffs in program processing. Our results indicate that TAWK can be used to quickly and easily perform a variety of common software engineering tasks, and the extensions to accommodate non-syntactic features significantly extend the generality of syntactic matchers. Copyright © 2005 John Wiley & Sons, Ltd.

Poorly structured code is hard to maintain and read. Program refactoring can improve code structure and thus make it easier to preserve and to discern the underlying design. However, refactoring is a difficult and time-consuming process making it unattractive for many developers. An automated tool that could identify poorly structured code and make suggestions would make the refactoring process easier. Although in general refactorings may be quite difficult to locate automatically, we show that many can be detected using low-cost, syntactic techniques. We have built a tool to locate refactorings in C# programs. Our experiments indicate that the tool has an excellent success rate in identifying refactorings.

Program slicing is a potentially useful analysis for aiding program understanding. However, in reality even slices of small programs are often too large to be useful. Imprecise pointer analyses have been suggested as one cause of this problem. In this paper, we use dynamic points-to data, which represents optimistic pointer information, to obtain a bound on the best case slice size improvement that can be achieved with improved pointer precision. Our experiments show that slice size can be reduced significantly for programs that make frequent use of calls through function pointers because for them the dynamic pointer data results in a considerably smaller call graph, which leads to fewer data dependences. Programs without or with only few calls through function pointers, however, show considerably less improvement. We discovered that C programs appear to have a significant fraction of direct and nonspurious pointer data dependences so that reducing spurious dependences via pointers is only of limited benefit. Consequently, to make slicing useful in general for such programs, improvements beyond better pointer analyses are necessary. On the other hand, since we show that collecting dynamic function pointer information can be performed with little overhead (average slowdown of 10 percent for our benchmarks), dynamic pointer information may be a practical approach to making slicing of programs with frequent function pointer use more successful in practice.

Software engineers need to understand programs in order to effectively maintain them. The call graph, which presents the calling relationships between functions, is a useful representation of a program that can aid understanding. For programs that do not use function pointers, the call graph can be extracted simply by parsing the program. However, for programs that use function pointers, call graph extraction is nontrivial. Many widely used C programs utilize function pointers for efficiency and ease of implementation. We present a technique called type signature filtering for improving call graph extraction in the presence of function pointers. Filtering can be accomplished in a single pass after pointer analysis is complete, making it reusable across different analyses. Our results show that for many programs our technique yields a call graph that is nearly identical to the true call graph, even if a naive pointer analysis is used.

To formalize a software process, its important aspects must be extracted as a model. Many processes are used repeatedly, and the ability to automate a process is also desired. One approach is to use a notation that already exists, such as a programming language, and extend it. However, the intricacies and restrictions the programming language places on the ability to succinctly and clearly describe a process can be problematic. An alternative approach is to develop a language specifically for describing processes. A significant disadvantage of this approach, however, is the lack of tool support for ensuring model correctness. We discuss a high-level language that encourages evolutionary model development and describe a tool for performing model verification. We have used our language and tool on the NetBeans model for distributed software development.

Program slicing is a potentially useful analysis for aiding program understanding. However, slices of even small programs are often too large to be generally useful. Imprecise pointer analyses have been suggested as one cause of this problem. In this paper, we use dynamic points-to data, which represents optimal or optimistic pointer information, to obtain a bound on the best case slice size improvement that can be achieved with improved pointer precision. Our experiments show that slice size can be reduced significantly for programs that make frequent use of calls through function pointers because for them the dynamic pointer data results in a considerably smaller call graph, which leads to fewer data dependences. Programs without or with only few calls through function pointers, however, show only insignificant improvement. We identified Amdahl's law as the reason for this behavior: C programs appear to have a large fraction of direct data dependences so that reducing spurious dependences via pointers is only of limited benefit. Consequently, to make slicing useful in general for such programs, improvements beyond better pointer analyses will be necessary. On the other hand, since we show that collecting dynamic function pointer information can be performed with little overhead (average slowdown of 10% for our benchmarks), dynamic pointer information may be a practical approach to making slicing of programs with frequent function pointer use more successful in reality.

Many software engineering tools such as program slicers must perform data-flow analysis in order to extract necessary information from the program source. These tools typically borrow much of their implementation from optimizing compilers. However, since these tools are expected to analyze programs in their entirety, rather than functions in isolation, the time and space performance of the dataflow analyses are of major concern. We present techniques that reduce the time and space required to perform dataflow analysis of large programs. We have used these techniques to implement an efficient program slicing tool for C programs and have computed slices of programs with more than 100,000 lines of code.

Understanding large software systems is difficult. Traditionally, automated tools are used to assist program understanding. However, the representations constructed by these tools often require prohibitive time and space. Demand-driven techniques can be used to reduce these requirements. However, the use of pointers in modern languages introduces additional problems that do not integrate well with these techniques. We present new techniques for effectively coping with pointers in large software systems written in the C programming language and use our techniques to implement a program slicing tool.First, we use a fast, flow-insensitive, points-to analysis before traditional data-flow analysis. Second, we allow the user to parameterize the points-to analysis so that the resulting program slices more closely match the actual program behavior. Such information cannot easily be obtained by the tool or might otherwise be deemed unsafe. Finally, we present data-flow equations for dealing with pointers to local variables in recursive programs. These equations allow the user to select an arbitrary amount of calling context in order to better trade performance for precision.To validate our techniques, we present empirical results using our program slicer on large programs. The results indicate that cost-effective analysis of large programs with pointers is feasible using our techniques.