Deep neural networks (DNN) are being used in a wide range of applications including safety-critical systems. Several DNN test generation approaches have been proposed to generate fault-revealing test inputs. However, the existing test generation approaches do not systematically cover the input data distribution to test DNNs with diverse inputs, and none of the approaches investigate the relationship between rare inputs and faults. We propose cit4dnn, an automated black-box approach to generate DNN test sets that are feature-diverse and that comprise rare inputs. cit4dnn constructs diverse test sets by applying combinatorial interaction testing to the latent space of generative models and formulates constraints over the geometry of the latent space to generate rare and fault-revealing test inputs. Evaluation on a range of datasets and models shows that cit4dnn generated tests are more feature diverse than the state-of-the-art, and can target rare fault-revealing testing inputs more effectively than existing methods.

Testingdeep neural networks (DNNs)has garnered great interest in the recent years due to their use in many applications. Black-box test adequacy measures are useful for guiding the testing process in covering the input domain. However, the absence of input specifications makes it challenging to apply black-box test adequacy measures in DNN testing. TheInput Distribution Coverage (IDC)framework addresses this challenge by using a variational autoencoder to learn a low dimensional latent representation of the input distribution, and then using that latent space as a coverage domain for testing. IDC applies combinatorial interaction testing on a partitioning of the latent space to measure test adequacy. Empirical evaluation demonstrates that IDC is cost-effective, capable of detecting feature diversity in test inputs, and more sensitive than prior work to test inputs generated using different DNN test generation methods. The findings demonstrate that IDC overcomes several limitations of white-box DNN coverage approaches by discounting coverage from unrealistic inputs and enabling the calculation of test adequacy metrics that capture the feature diversity present in the input space of DNNs.

We are pleased to welcome you to CGO 2021, the first virtual CGO Conference. In addition, the Program Committee was virtual due to the worldwide infection rate of the coronavirus. On behalf of the Program Committee, we are pleased to present an exciting and stimulating program for the 2021 International Symposium on Code Generation and Optimization Conference.

The reliability of software that has a Deep Neural Network (DNN) as a component is urgently important today given the increasing number of critical applications being deployed with DNNs. The need for reliability raises a need for rigorous testing of the safety and trustworthiness of these systems. In the last few years, there have been a number of research efforts focused on testing DNNs. However the test generation techniques proposed so far lack a check to determine whether the test inputs they are generating are valid, and thus invalid inputs are produced. To illustrate this situation, we explored three recent DNN testing techniques. Using deep generative model based input validation, we show that all the three techniques generate significant number of invalid test inputs. We further analyzed the test coverage achieved by the test inputs generated by the DNN testing techniques and showed how invalid test inputs can falsely inflate test coverage metrics. To overcome the inclusion of invalid inputs in testing, we propose a technique to incorporate the valid input space of the DNN model under test in the test generation process. Our technique uses a deep generative model-based algorithm to generate only valid inputs. Results of our empirical studies show that our technique is effective in eliminating invalid tests and boosting the number of valid test inputs generated.

Rust, an emerging programming language with explosive growth, provides a robust type system that enables programmers to write memory-safe and data-race free code. To allow access to a machine's hardware and to support low-level performance optimizations, a second language, Unsafe Rust, is embedded in Rust. It contains support for operations that are difficult to statically check, such as C-style pointers for access to arbitrary memory locations and mutable global variables. When a program uses these features, the compiler is unable to statically guarantee the safety properties Rust promotes. In this work, we perform a large-scale empirical study to explore how software developers are using Unsafe Rust in real-world Rust libraries and applications. Our results indicate that software engineers use the keyword unsafe in less than 30% of Rust libraries, but more than half cannot be entirely statically checked by the Rust compiler because of Unsafe Rust hidden somewhere in a library's call chain. We conclude that although the use of the keyword unsafe is limited, the propagation of unsafeness offers a challenge to the claim of Rust as a memory-safe language. Furthermore, we recommend changes to the Rust compiler and to the central Rust repository's interface to help Rust software developers be aware of when their Rust code is unsafe.

The low cost of resource ownership and flexibility have led users to increasingly port their applications to the clouds. To fully realize the cost benefits of cloud services, users usually need to reliably know the execution performance of their applications. However, due to the random performance fluctuations experienced by cloud applications, the black box nature of public clouds and the cloud usage costs, testing on clouds to acquire accurate performance results is extremely difficult. In this paper, we present a novel cloud performance testing methodology called PT4Cloud. By employing non-parametric statistical approaches of likelihood theory and the bootstrap method, PT4Cloud provides reliable stop conditions to obtain highly accurate performance distributions with confidence bands. These statistical approaches also allow users to specify intuitive accuracy goals and easily trade between accuracy and testing cost. We evaluated PT4Cloud with 33 benchmark configurations on Amazon Web Service and Chameleon clouds. When compared with performance data obtained from extensive performance tests, PT4Cloud provides testing results with 95.4% accuracy on average while reducing the number of test runs by 62%. We also propose two test execution reduction techniques for PT4Cloud, which can reduce the number of test runs by 90.1% while retaining an average accuracy of 91%. We compared our technique to three other techniques and found that our results are much more accurate.

The paradigm shift of deploying applications to the cloud has introduced both opportunities and challenges. Although clouds use elasticity to scale resource usage at runtime to help meet an application's performance requirements, developers are still challenged by unpredictable performance, little control of execution environment, and differences among cloud service providers, all while being charged for their cloud usages. Application performance stability is particularly affected by multi-tenancy in which the hardware is shared among varying applications and virtual machines. Developers porting their applications need to meet performance requirements, but testing on the cloud under the effects of performance uncertainty is difficult and expensive, due to high cloud usage costs. This paper presents a first approach to testing an application with typical inputs for how its performance will be affected by performance uncertainty, without incurring undue costs of brute force testing in the cloud. We specify cloud uncertainty testing criteria, design a test-based strategy to characterize the black box cloud's performance distributions using these testing criteria, and support execution of tests to characterize the resource usage and cloud baseline performance of the application to be deployed. Importantly, we developed a smart test oracle that estimates the application's performance with certain confidence levels using the above characterization test results and determines whether it will meet its performance requirements. We evaluated our testing approach on both the Chameleon cloud and Amazon web services; results indicate that this testing strategy shows promise as a cost-effective approach to test for performance effects of cloud uncertainty when porting an application to the cloud.

Modern NUMA platforms offer large numbers of cores to boost performance through parallelism and multi-threading. However, because performance scalability is limited by available memory bandwidth, the strategy of allocating all cores can result in degraded performance. Consequently, accurately predicting optimal (best performing) core allocations, and executing applications with these allocations are crucial for achieving the best performance. Previous research focused on the prediction of optimal numbers of cores. However, in this paper, we show that, because of the asymmetric NUMA memory configuration and the asymmetric application memory behavior, optimal core allocations are not merely optimal numbers of cores. Additionally, previous studies do not adequately consider NUMA memory resources, which further limits their ability to accurately predict optimal core allocations. In this paper, we present a model, NuCore, which predicts both memory bandwidth usage and optimal core allocations. NuCore considers various memory resources and NUMA asymmetry, and employs Integer Programming to achieve high accuracy and low overhead. Experimental results from real NUMA machines show that the core allocations predicted by NuCore provide 1.27x average speedup over using all cores with only 75.6% cores allocated. NuCore also provides 1.18x and 1.21x average speedups over two state-of-the-art techniques. Our results also show that NuCore faithfully models NUMA memory systems and predicts memory bandwidth usages with only 10% average error.

Memory bandwidth severely limits the scalability and performance of today's multi-core systems. Because of this limitation, many studies that focused on improving multi-core scalability rely on bandwidth usage predictions to achieve the best results. However, existing bandwidth prediction models have low accuracy, causing these studies to have inaccurate conclusions or perform sub-optimally. Most of these models make predictions based on the bandwidth usage samples of a few trial runs. Many factors that affect bandwidth usage and the complex DRAM operations are overlooked. This paper presents DraMon, a model that predicts bandwidth usages for multi-threaded programs with low overhead. It achieves high accuracy through highly accurate predictions of DRAM contention and DRAM concurrency, as well as by considering a wide range of hardware and software factors that impact bandwidth usage. We implemented two versions of DraMon: DraMon-T, a memory-trace based model, and DraMon-R, a run-time model which uses hardware performance counters. When evaluated on a real machine with memory-intensive benchmarks, DraMon-T has average accuracies of 99.17% and 94.70% for DRAM contention predictions and bandwidth predictions, respectively. DraMon-R has average accuracies of 98.55% and 93.37% for DRAM contention and bandwidth predictions respectively, with only 0.50% overhead on average.

As multicore processors with expanding core counts continue to dominate the server market, the overall utilization of the class of datacenters known as warehouse scale computers (WSCs) depends heavily on colocation of multiple workloads on each server to take advantage of the computational power provided by modern processors. However, many of the applications running in WSCs, such as websearch, are user-facing and have quality of service (QoS) requirements. When multiple applications are co-located on a multicore machine, contention for shared memory resources threatens application QoS as severe cross-core performance interference may occur. WSC operators are left with two options: either disregard QoS to maximize WSC utilization, or disallow the co-location of high-priority user-facing applications with other applications, resulting in low machine utilization and millions of dollars wasted.

To utilize the full potential of modern chip multiprocessors and obtain scalable performance improvements, it is critical to mitigate resource contention created by multithreaded workloads. In this article, we describe ReSense, the first runtime system that uses application characteristics to dynamically map multithreaded applications from dynamic workloads—workloads where multithreaded applications arrive, execute, and terminate continuously in unpredictable ways. ReSense mitigates contention for the shared resources in the memory hierarchy by applying a novel thread-mapping algorithm that dynamically adjusts the mapping of threads from dynamic workloads using a precalculated sensitivity score. The sensitivity score quantifies an application's sensitivity to sharing a particular memory resource and is calculated by an efficient characterization process that involves running the multithreaded application by itself on the target platform. To measure ReSense's effectiveness, sensitivity scores were determined for 21 benchmarks from PARSEC-2.1 and NPB-OMP-3.3 for the shared resources in the memory hierarchy on four different platforms. Using three different-sized dynamic workloads composed of randomly selected two, four, and eight corunning benchmarks with randomly selected start times, ReSense was able to improve the average response time of the three workloads by up to 27.03%, 20.89%, and 29.34% and throughput by up to 19.97%, 46.56%, and 29.86%, respectively, over the native OS on real hardware. By estimating and comparing ReSense's effectiveness with the optimal thread mapping for two different workloads, we found that the maximum average difference with the experimentally determined optimal performance was 1.49% for average response time and 2.08% for throughput.

Generally, a fault is a property violation at a program point along some execution path. To obtain the path where a fault occurs, we can either run the program or manually identify the execution paths through code inspection. In both of the cases, only a very limited number of execution paths can be examined for a program. This article presents a static framework, Marple, that automatically detects path segments where a fault occurs at a whole program scale. An important contribution of the work is the design of a demand-driven analysis that effectively addresses scalability challenges faced by traditional path-sensitive fault detection. The techniques are made general via a specification language and an algorithm that automatically generates path-based analyses from specifications. The generality is achieved in handling both data- and control-centric faults as well as both liveness and safety properties, enabling the exploitation of fault interactions for diagnosis and efficiency. Our experimental results demonstrate the effectiveness of our techniques in detecting path segments of buffer overflows, integer violations, null-pointer dereferences, and memory leaks. Because we applied an interprocedural, path-sensitive analysis, our static fault detectors generally report better precision than the tools available for comparison. Our demand-driven analyses are shown scalable to deployed applications such as apache , putty , and ffmpeg .

As the class of datacenters recently coined as warehouse scale computers (WSCs) continues to leverage commodity multicore processors with increasing core counts, there is a growing need to consolidate various workloads on these machines to fully utilize their computation power. However, it is well known that when multiple applications are co-located on a multicore machine, contention for shared memory resources can cause severe cross-core performance interference. To ensure that the quality of service (QoS) of user-facing applications does not suffer from performance interference, WSC operators resort to disallowing co-location of latency-sensitive applications with other applications. This policy translates to low machine utilization and millions of dollars wasted in WSCs.

With the shift to chip multiprocessors, managing shared resources has become a critical issue in realizing their full potential. Previous research has shown that thread mapping is a powerful tool for resource management. However, the difficulty of simultaneously managing multiple hardware resources and the varying nature of the workloads have impeded the efficiency of thread mapping algorithms. To overcome the difficulties of simultaneously managing multiple resources with thread mapping, the interaction between various microarchitectural resources and thread characteristics must be well understood. This paper presents an in-depth analysis of PARSEC benchmarks running under different thread mappings to investigate the interaction of various thread mappings with microarchitectural resources including, L1 I/D-caches, I/D TLBs, L2 caches, hardware prefetchers, off-chip memory interconnects, branch predictors, memory disambiguation units and the cores. For each resource, the analysis provides guidelines for how to improve its utilization when mapping threads with different characteristics. We also analyze how the relative importance of the resources varies depending on the workloads. Our experiments show that when only memory resources are considered, thread mapping improves an application's performance by as much as 14% over the default Linux scheduler. In contrast, when both memory and processor resources are considered the mapping algorithm achieves performance improvements by as much as 28%. Additionally, we demonstrate that thread mapping should consider L2 caches, prefetchers and off-chip memory interconnects as one resource, and we present a new metric called L2-misses-memory-latency-product (L2MP) for evaluating their aggregated performance impact.

The overhead of test coverage analysis is dominated by monitoring the application, which is traditionally performed using instrumentation. However, instrumentation can prohibitively increase the time and especially the memory overhead of an application. As an alternative to instrumentation, we explore how recent hardware advances can be leveraged to improve the overheads of test coverage analysis. These hardware advances include hardware performance monitors and multicore technology.

With the shift to many-core chip multiprocessors (CMPs), a critical issue is how to effectively coordinate and manage the execution of applications and hardware resources to overcome performance, power consumption, and reliability challenges stemming from hardware and application variations inherent in this new computing environment. Effective resource and application management on CMPs requires consideration of user/application/hardware-specific requirements and dynamic adaption of management decisions based on the actual run-time environment. However, designing an algorithm to manage resources and applications that can dynamically adapt based on the run-time environment is difficult because most resource and application management and monitoring facilities are only available at the operating system level. This paper presents REEact, an infrastructure that provides the capability to specify user-level management policies with dynamic adaptation. REEact is a virtual execution environment that provides a framework and core services to quickly enable the design of custom management policies for dynamically managing resources and applications. To demonstrate the capabilities and usefulness of REEact, this paper describes three case studies--each illustrating the use of REEact to apply a specific dynamic management policy on a real CMP. Through these case studies, we demonstrate that REEact can effectively and efficiently implement policies to dynamically manage resources and adapt application execution.

Dynamic binary translators (DBTs) are becoming increasingly important because of their power and flexibility. DBT-based services are valuable for all types of platforms. However, the high memory demands of DBTs present an obstacle for embedded systems. Most research on DBT design has a performance focus, which often drives up the DBT memory demand. In this article, we present a memory-oriented approach to DBT design. We consider the class of translation-based DBTs and their sources of memory demand; cached translated code, cached auxiliary code and DBT data structures. We explore aspects of DBT design that impact these memory demand sources and present strategies to mitigate memory demand. We also explore performance optimizations for DBTs that handle memory demand by placing a limit on it, and repeatedly flush translations to stay within the limit, thereby replacing the memory demand problem with a performance degradation problem. Our optimizations that mitigate memory demand improve performance.

An effective workshop has been developed for promoting a positive impact on high school teachers' recruitment of students, particularly women and minority students, into their CS classes. All past workshop attendees indicate they now are actively try to recruit girls and minority students into their computing classes and are successful in doing so.

In this paper, we present a direct methodology and framework for the measurement and characterization of an application's cross-core interference sensitivity on multicore microarchitectures. While prior works use indirect indicators, such as last level cache miss rate, to infer an application's cross-core interference sensitivity, our approach is direct, in that it characterizes the application's cross-core interference sensitivity using the performance impact due to actual contention. Our methodology and framework, the Cross-core interference Profiling Environment, or CiPE, is composed of a lightweight runtime environment on which a host application runs, along with a carefully designed contention synthesis engine that executes on a neighboring core. CiPE manipulates the co-running contention synthesis engine, while monitoring and analyzing the resulting dynamic impact on the host application.

Despite the emerging ubiquity of hardware monitoring mechanisms and prior research work in other fields, the applicability and usefulness of hardware monitoring mechanisms have not been fully scrutinized for software engineering.

In this paper we study the impact of sharing memory resources on five Google datacenter applications: a web search engine, bigtable, content analyzer, image stitching, and protocol buffer. While prior work has found neither positive nor negative effects from cache sharing across the PARSEC benchmark suite, we find that across these datacenter applications, there is both a sizable benefit and a potential degradation from improperly sharing resources. There are four main contributions of this paper. First, we present a study of the importance of thread-to-core mapping for applications in the datacenter as threads can be mapped to share or to not share caches and bus bandwidth. Second, we investigate the impact of co-locating threads from multiple applications with diverse memory behavior and discover that the best mapping for a given application changes de- pending on its co-runner. Third, we investigate the application characteristics that impact performance in the various thread-to-core mapping scenarios. Finally, we present both a heuristics-based and an adaptive approach to arrive at good thread-to-core decisions in the datacenter. We observe performance swings of up to 25% for web search, and 40% for other key applications, simply based on how application threads are mapped to cores. By employing our adaptive thread to core mapper the performance of the datacenter applications presented in this work improved by up to 22% over status quo thread-to-core mapping and performs within 3% of optimal.

For higher processing and computing power, chip multiprocessors (CMPs) have become the new mainstream architecture. This shift to CMPs has created many challenges for fully utilizing the power of multiple execution cores. One of these challenges is managing contention for shared resources. Most of the recent research address contention for shared resources by single-threaded applications. However, as CMPs scale up to many cores, the trend of application design has shifted towards multi-threaded programming and new parallel models to fully utilize the underlying hardware. There are differences between how single- and multi-threaded applications contend for shared resources. Therefore, to develop approaches to reduce shared resource contention for emerging multi-threaded applications, it is crucial to understand how their performances are affected by contention for a particular shared resource. In this research, we propose and evaluate a general methodology for characterizing multi-threaded applications by determining the effect of shared-resource contention on performance. To demonstrate the methodology, we characterize the applications in the widely used PARSEC benchmark suite for shared-memory resource contention. The characterization reveals several interesting aspects of the benchmark suite. Three of twelve PARSEC benchmarks exhibit no contention for cache resources. Nine of the benchmarks exhibit contention for the L2-cache. Of these nine, only three exhibit contention between their own threads-most contention is because of competition with a co-runner. Interestingly, contention for the Front Side Bus is a major factor with all but two of the benchmarks and degrades performance by more than 11%.

Although static bug detectors are extensively applied, there is a cost in using them. One challenge is that static analysis often reports a large number of false positives but little diagnostic information. Also, individual bug detectors need to be built in response to new types of faults, and tuning a static tool for precision and scalability is time-consuming. This paper presents a novel frame-work that automatically generates scalable, interprocedural, path-sensitive analyses to detect user-specified faults. The framework consists of a specification technique that expresses faults and information needed for their detection, a scalable, path-sensitive algorithm, and a generator that unifies the two. The analysis produced identifies not only faults but also the path segments where the root causes of a fault are located. The generality of the framework is accomplished for both data- and control-centric faults. We implemented our framework and generated fault detectors for identifying buffer overflows, integer violations, null-pointer dereferences and memory leaks. We experimentally demonstrate that the generated analyses scales to large deployed software, and its detection capability is comparable to tools that target a specific type of fault. In our experiments, we identify a total of 146 faults of the four types. While the length of path segments for the majority of faults is 1--4 procedures, we are able to detect faults deeply embedded in the code across 35 procedures.

As much of the world's computing continues to move into the cloud, the overprovisioning of computing resources to ensure the performance isolation of latency-sensitive tasks, such as web search, in modern datacenters is a major contributor to low machine utilization. Being unable to accurately predict performance degradation due to contention for shared resources on multicore systems has led to the heavy handed approach of simply disallowing the co-location of high-priority, latency-sensitive tasks with other tasks. Performing this precise prediction has been a challenging and unsolved problem.

Dynamic binary translators (DBTs) are becoming increasingly important because of their power and flexibility. However, the high memory demands of DBTs present an obstacle for all platforms, and especially embedded systems. The memory demand is typically controlled by placing a limit on cached translations and forcing the DBT to flush all translations upon reaching the limit. This solution manifests as a performance inefficiency because many flushed translations require retranslation. Ideally, translations should be selectively flushed to minimize retranslations for a given memory limit. However, three obstacles exist:(1) it is difficult to predict which selections will minimize retranslation,(2) selective flushing results in greater book-keeping overheads than full flushing, and(3) the emergence of multicore processors and multi-threaded programming complicates most flushing algorithms. These issues have led to the widespread adoption of full flushing as a standard protocol. In this paper, we present a partial flushing approach aimed at reducing retranslation overhead and improving overall performance, given a fixed memory budget. Our technique applies uniformly to single-threaded and multi-threaded guest applications

Cross-core application interference due to contention for shared on-chip and off-chip resources pose a significant challenge to providing application level quality of service (QoS) guarantees on commodity multicore micro-architectures. Unexpected cross-core interference is especially problematic when considering latency-sensitive applications that are present in the web service data center application domains, such as web-search. The commonly used solution is to simply disallow the co-location of latency-sensitive applications and throughput-oriented batch applications on a single chip, leaving much of the processing capabilities of multicore micro-architectures underutilized. In this work we present a Contention Aware Execution Runtime (CAER) environment that provides a lightweight runtime solution that minimizes cross-core interference due to contention, while maximizing utilization. CAER leverages the ubiquitous performance monitoring capabilities present in current multicore processors to infer and respond to contention and requires no added hardware support. We present the design and implementation of the CAER environment, two separate contention detection heuristics, and approaches to respond to contention online. We evaluate our solution using the SPEC2006 benchmark suite. Our experiments show that when allowing co-location with CAER, as opposed to disallowing co-location, we are able to increase the utilization of the multicore CPU by 58% on average. Meanwhile CAER brings the overhead due to allowing co-location from 17% down to just 4% on average.

Although a number of automatic tools have been developed to detect faults, much of the diagnosis is still being done manually. To help with the diagnostic tasks, we formally introduce fault correlation, a causal relationship between faults. We statically determine correlations based on the expected dynamic behavior of a fault. If the occurrence of one fault causes another fault to occur, we say they are correlated. With the identification of the correlated faults, we can better understand fault behaviors and the risks of faults. If one fault is uniquely correlated with another, we know fixing the first fault will fix the other. Correlated faults can be grouped, enabling prioritization of diagnoses of the fault groups. In this paper, we develop an interprocedural, path-sensitive, and scalable algorithm to automatically compute correlated faults in a program. In our approach, we first statically detect faults and determine their error states. By propagating the effects of the error state along a path, we detect the correlation of pairs of faults. We automatically construct a correlation graph which shows how correlations occur among multiple faults and along different paths. Guided by a correlation graph, we can reduce the number of faults required for diagnosis to find root causes. We implemented our correlation algorithm and found through experimentation that faults involved in the correlations can be of different types and located in different procedures. Using correlation information, we are able to automate diagnostic tasks that previously had to be done manually.

Dynamic binary translators(DBTs) provide powerful platforms for building dynamic program monitoring and adaptation tools. DBTs, however, have high memory demands because they cache translated code and auxiliary code to a software code cache and must also maintain data structures to support the code cache. The high memory demands make it difficult for memory-constrained embedded systems to take advantage of DBT-based tools. Previous research on DBT memory management focused on the translated code and auxiliary code only. However, we found that data structures are comparable to the code cache in size. We show that the translated code size, auxiliary code size and the data structure size interact in a complex manner, depending on the path selection (trace selection and link formation) strategy. Therefore, holistic memory efficiency (comprising translated code, auxiliary code and data structures) cannot be improved by focusing on the code cache only. In this paper, we use path selection for improving holistic memory efficiency which in turn impacts performance in memory-constrained environments. Although there has been previous research on path selection, such research only considered performance in memory-unconstrained environments.

Although register allocation is critical for performance, the implementation of register allocation algorithms is difficult, due to the complexity of the algorithms and target machine architectures. It is particularly difficult to detect register allocation errors if the output code runs to completion, as bugs in the register allocator can cause the compiler to produce incorrect output code. The output code may even execute properly on some test data, but errors can remain. In this article, we propose novel data flow analyses to statically check that the value flow of the output code from the register allocator is the same as the value flow of its input code. The approach is accurate, fast, and can identify and report error locations and types. It is independent of the register allocator and uses only the input and output code of the register allocator. It can be used with different register allocators, including those that perform coalescing and rematerialization. The article describes our approach, called SARAC, and a tool that statically checks a register allocation and reports the errors and their types that it finds. The tool has an average compile-time overhead of only 8% and a modest average memory overhead of 85KB. Our techniques can be used by compiler developers during regression testing and as a command-line-enabled debugging pass for mysterious compiler behavior.

Debugging programs at the source level is essential in the software development cycle. With the growing importance of dynamic optimization, there is a clear need for debugging support in the presence of runtime code transformation. This paper presents a framework, called DeDoc, and lightweight techniques that allow debugging at the source level for programs that have been transformed by a trace-based binary dynamic optimizer. Our techniques provide full transparency and hide from the user the effect of dynamic optimizations on code statements and data values. We describe and evaluate an implementation of DeDoc and its techniques that interface a dynamic optimizer with a native debugger. Our experimental results indicate that DeDoc is able to report over 96% of values, that are otherwise not reportable due to code transformations, and incurs less than 1% performance overhead.

Despite increasing efforts in detecting and managing software security vulnerabilities, the number of security attacks is still rising every year. As software becomes more complex, security vulnerabilities are more easily introduced into a system and more difficult to eliminate. Even though buffer overflow detection has been studied for more than 20 years, it is still the most commonly exploited vulnerability. In this paper, we develop a static analyzer for detecting and helping diagnose buffer overflows with the key idea of categorizing program paths as they relate to vulnerability. We combine path-sensitivity with a demand-driven analysis for precision and scalability. We first develop a vulnerability model for buffer overflow and then use the model in the development of the demand-driven path-sensitive analyzer. We detect and identify categories of paths including infeasible, safe, vulnerable, overflow-input-independent and don't-know. The categorization enables priorities to be set when searching for root causes of vulnerable paths. We implemented our analyzer, Marple, and compared its performance with existing tools. Our experiments show that Marple is able to detect buffer overflows that other tools cannot, and being path-sensitive with prioritization, Marple produces only 1 false positive out of 72 reported overflows. We also show that Marple scales to 570,000 lines of code, the largest benchmark we had.

In today's dynamic computing environments, the available resources and even underlying computation engine can change during the execution of a program. Additionally, current trends in software development favor the flexibility and cost-effectiveness of dynamically loaded components and libraries. Because of these trends, there has been increased research interest in virtual execution environments (VEEs) for delivering adaptable software suitable for today's rapidly changing, heterogeneous computing environments. In this project, we have been investigating tools and techniques to support implementation of VEEs using software dynamic translation (SDT). This paper highlights some of our recent results. One significant result is that we have developed novel translation techniques that reduce the memory and runtime overhead of SDT to negligible levels. We have also developed innovative debugging and instrumentation tools for SDT-based software environments. Together, these results make SDT-based systems viable for solving a wide range of pressing problems. The paper concludes with a discussion of how SDT may offer a solution to one such problem-inherent process variation in emerging chip multiprocessors.

This paper presents a tool that (i) constructs tree-based models of a program's behavior during testing and (ii) employs these trees while reordering and reducing a test suite. Using either a dynamic call tree or a calling context tree, the test reduction component identifies a subset of the original tests that covers the same call tree paths. The prioritization technique reorders a test suite so that it covers the call tree paths more rapidly than the initial test ordering. In support of program and test suite understanding, the tool also visualizes the call trees and the coverage relationships. For a chosen case study application, the experimental results show that call tree construction only increases testing time by 13%. In comparison to the original test suite, the experiments show that (i) a prioritized suite achieves coverage much faster and (ii) a reduced test suite contains 45% fewer tests and consumes 82% less time

Although static analysis is an important technique for detecting buffer overflow before software deployment, current static tools rely on considerable human effort for annotating code to help analysis, or for diagnosing warnings, many of which are false positives. This paper presents an analysis technique that refines information about the paths that involve a potential buffer overflow to help in the diagnosis and debugging of vulnerabilities. Instead of only reporting a vulnerable buffer or statement in the program, which most tools do, our analysis categorizes paths of a possibly vulnerable statement into five types: Vulnerable, Overflow-User-Independent, Safe, Infeasible and Don't-Know. Thus, safe and infeasible paths can be excluded from being inspected, providing focus on problematic paths. For scalability, we designed and implemented our analysis as an interprocedural, demand-driven path-sensitive analysis. Our experiments demonstrate that various path types do go through a possibly vulnerable buffer statement. The results also indicate that our technique is efficient and practical.

Wireless sensor network (WSN) applications are notoriously difficult to develop and debug. This paper describes Clairvoyant which is a comprehensive source-level debugger for wireless, embedded networks. With Clairvoyant, a developer can wirelessly connect to a sensor network and execute standard debugging commands including break, step, watch, and backtrace, as well as new commands that are specially designed for debugging WSNs. Clairvoyant attempts to minimize its effect on the program being debugged in terms of network load, memory footprint, execution speed, clock consistency, and flash lifetime.

Sensor network debugging is notoriously difficult because many bugs manifest themselves only when they encounter the real world -- exactly when most powerful debugging tools can no longer be applied. There are currectly two common approaches to source level debugging in wireless sensor networks (WSNs), (i) simulation-based debugging [3], and (ii) wire-based debugging via logic analyzers or in-circuit emulators [1]. The former do not capture the true dynamics of a real deployment while the latter do not scale with the number of nodes and geographic size of the network. Thus, existing source-level debugging approaches for WSNs cannot be used in many real deployment environments.

Traditional code optimizers have produced significant performance improvements over the past forty years. While promising avenues of research still exist, traditional static and profiling techniques have reached the point of diminishing returns. The main problem is that these approaches have only a limited view of the program and have difficulty taking advantage of the actual run-time behavior of a program. We are addressing this problem through the development of a dynamic optimization system suited for aggressive optimization - using the full power of the most beneficial optimizations. We have designed our optimizer to operate using a software dynamic translation (SDT) execution system. Difficult challenges in this research include reducing SDT overhead and determining what optimizations to apply and where in the code to apply them. Another challenge is having the necessary tools to ensure the reliability of software that is dynamically optimized. In this paper, we describe our efforts in reducing overhead in SDT and efficient techniques for instrumenting the application code. We also describe our approach to determine what and where an optimization should be applied. We discuss other fundamental issues in developing a dynamic optimizer and finally present a basic debugger for SDT systems

Regression test prioritization is often performed in a time constrained execution environment in which testing only occurs for a fixed time period. For example, many organizations rely upon nightly building and regression testing of their applications every time source code changes are committed to a version control repository. This paper presents a regression test prioritization technique that uses a genetic algorithm to reorder test suites in light of testing time constraints. Experiment results indicate that our prioritization approach frequently yields higher average percentage of faults detected (APFD) values, for two case study applications, when basic block level coverage is used instead of method level coverage. The experiments also reveal fundamental trade offs in the performance of time-aware prioritization. This paper shows that our prioritization technique is appropriate for many regression testing environments and explains how the baseline approach can be extended to operate in additional time constrained testing circumstances.

Although optimizations have been applied for a number of years to improve the performance of software, problems with respect to the application of optimizations have not been adequately addressed. For example, in certain circumstances, optimizations may degrade performance. However, there is no efficient way to know when a degradation will occur. In this research, we investigate the profitability of optimizations, which is useful for determining the benefit of applying optimizations. We develop a framework that enables us to predict profitability using analytic models. The profitability of an optimization depends on code context, the particular optimization, and machine resources. Thus, our framework has analytic models for each of these components. As part of the framework, there is also a profitability engine that uses models to predict the profit. In this paper, we target scalar optimizations and, in particular, describe the models for partial redundancy elimination (PRE), loop invariant code motion (LICM), and value numbering (VN). We implemented the framework for predicting the profitability of these optimizations. Based on the predictions, we can selectively apply profitable optimizations. We compared the profit-driven approach with an approach that uses a heuristic in deciding when optimizations should be applied. Our experiments demonstrate that the profitability of scalar optimizations can be accurately predicted by using models. That is, without actually applying a scalar optimization, we can determine if an optimization is beneficial and should be applied.

Although optimizations have been applied for a number of years to improve the performance of software, problems that have been long-standing remain, which include knowing what optimizations to apply and how to apply them. To systematically tackle these problems, we need to understand the properties of optimizations. In our current research, we are investigating the profitability property, which is useful for determining the benefit of applying an optimization. Due to the high cost of applying optimizations and then experimentally evaluating their profitability, we use an analytic model framework for predicting the profitability of optimizations. In this paper, we target scalar optimizations, and in particular, describe framework instances for partial redundancy elimination (PRE) and loop invariant code motion (LICM). We implemented the framework for both optimizations and compare profit-driven PRE and LICM with a heuristic-driven approach. Our experiments demonstrate that a model-based approach is effective and efficient in that it can accurately predict the profitability of optimizations with low overhead. By predicting the profitability using models, we can selectively apply optimizations. The model-based approach does not require tuning of parameters used in heuristic approaches and works well across different code contexts and optimizations.

Producing reliable and robust software has become one of the most important software development concerns in recent years. Testing is a process by which software quality can be assured through the collection of information. While testing can improve software reliability, current tools typically are inflexible and have high over-heads, making it challenging to test large software projects. In this paper, we describe a new scalable and flexible framework for testing programs with a novel demand-driven approach based on execution paths to implement test coverage. This technique uses dynamic instrumentation on the binary code that can be inserted and removed on-the-fly to keep performance and memory overheads low. We describe and evaluate implementations of the framework for branch, node and defuse testing of Java programs. Experimental results for branch testing show that our approach has, on average, a 1.6 speed up over static instrumentation and also uses less memory.

Software for resource constrained embedded devices is often implemented in the Java programming language because the Java compiler and virtual machine provide enhanced safety, portability, and the potential for run-time optimization. It is important to verify that a software application executes correctly in the environment in which it will normally execute, even if this environment is an embedded one that severely constrains memory resources. Testing can be used to isolate defects within and establish a confidence in the correctness of a Java application that executes in a resource constrained environment. However, executing test suites with a Java virtual machine (JVM) that uses dynamic compilation to create native code bodies can introduce significant testing time overheads if memory resources are highly constrained. This paper describes an approach that uses adaptive code unloading to ensure that it is feasible to perform testing in the actual memory constrained execution environment. The experiments demonstrate that code unloading can reduce both the test suite execution time by 34% and the code size of the test suite and application under test by 78% while maintaining the overall size of the JVM.

Program instrumentation, inserted either before or during execution, is rapidly becoming a necessary component of many systems. Instrumentation is commonly used to collect information for many diverse analysis applications, such as detecting program invariants, dynamic slicing and alias analysis, software security checking, and computer architecture modeling. Because instrumentation typically has a high run-time overhead, techniques are needed to mitigate the overheads. This paper describes "instrumentation optimizations" that reduce the overhead of profiling for program analysis. Our approach applies transformations to the instrumentation code that reduce the (1) number of instrumentation points executed, (2) cost of instrumentation probes, and (3) cost of instrumentation payload, while maintaining the semantics of the original instrumentation. We present the transformations and apply them for program profiling and computer architecture modeling. We evaluate the optimizations and show that the optimizations improve profiling performance by 1.26-2.63x and architecture modeling performance by 2-3.3x.

Virtual execution environments have become increasingly useful in system implementation, with dynamic translation techniques being an important component for performance-critical systems. Many devices have exceptionally tight performance and memory constraints (e.g., smart cards and sensors in distributed systems), which require effective resource management. One approach to manage code memory is to download code partitions on-demand from a server and to cache the partitions in the resource-constrained device (client). However, due to the high cost of downloading code and re-translation, it is critical to intelligently manage the code buffer to minimize the overhead of code buffer misses. Yet, intelligent buffer management on the tightly constrained client can be too expensive. In this paper, we propose to move code buffer management to the server, where sophisticated schemes can be employed. We describe two schemes that use profiling information to direct the client in caching code partitions. One scheme is designed for workloads with stable run-time behavior, while the other scheme adapts its decisions for workloads with unstable behaviors. We evaluate and compare our schemes and show they perform well, compared to other approaches, with the adaptive scheme having the best performance overall.

Software engineering research and programming language design have enjoyed asymbioticrelationship, with traceable impacts since the 1970s, when these areas were first distinguished from one another. This report documents this relationship by focusing on several major features of current programming languages: data and procedural abstraction, types, concurrency, exceptions, and visual programming mechanisms. The influences are determined by tracing references in publications in both fields, obtaining oral histories from language designers delineating influences on them, and tracking cotemporal research trends and ideas as demonstrated by workshop topics, special issue publications, and invited talks in the two fields. In some cases there is conclusive data supporting influence. In other cases, there are circumstantial arguments (i.e., cotemporal ideas) that indicate influence. Using this approach, this study provides evidence of the impact of software engineering research on modern programming language design and documents the close relationship between these two fields.

Software dynamic translation (SDT) is a technology that permits the modification of an executing program's instructions. In recent years, SDT has received increased attention, from both industry and academia, as a feasible and effective approach to solving a variety of significant problems. Despite this increased attention, the task of initiating a new project in software dynamic translation remains a difficult one. To address this concern, and in particular, to promote the adoption of SDT technology into an even wider range of applications, we have implemented Strata, a cross-platform infrastructure for building software dynamic translators. This paper describes Strata's architecture, our experience retargeting it to three different processors, and our use of Strata to build two novel SDT systems - one for safe execution of untrusted binaries and one for fast prototyping of architectural simulators.

The ICSE Doctoral Symposium is a forum for Ph.D. students to publicly discuss their research goals, methods, and results prior to completion of their doctorates. The Symposium aims to provide useful guidance for completion of the dissertation research and initiation of a research career. The Symposium and ICSE also provide an opportunity for student participants to interact with established researchers and others in the wider software engineering community.

When applying optimizations, a number of decisions are made using fixed strategies, such as always applying an optimization if it is applicable, applying optimizations in a fixed order and assuming a fixed configuration for optimizations such as tile size and loop unrolling factor. While it is widely recognized that these fixed strategies may not be the most appropriate for producing high quality code, especially for embedded systems, there are no general and automatic strategies that do otherwise. In this paper, we present a framework that enables these decisions to be made based on predicting the impact of an optimization, taking into account resources and code context. The framework consists of optimization models, code models and resource models, which are integrated for predicting the impact of applying optimizations. Because data cache performance is important to embedded codes, we focus on cache performance and present an instance of the framework for cache performance in this paper. Since most opportunities for cache improvement come from loop optimizations, we describe code, optimization and cache models tailored to predict the impact of applying loop optimizations for data locality. Experimentally we demonstrate the need to selectively apply optimizations and show the performance benefit of our framework in predicting when to apply an optimization. We also show that our framework can be used to choose the most beneficial optimization when a number of optimizations can be applied to a loop nest. And lastly, we show that we can use the framework to combine optimizations on a loop nest.

Trace reuse improves the performance of processors by skipping the execution of sequences of redundant instructions. However, many reusable traces do not have all of their inputs ready by the time the reuse test is done. For these cases, we developed a new technique called reuse through speculation on traces (RST), where trace inputs may be predicted. We study the limits of RST for modern processors with deep pipelines, as well as the effects of constraining resources on performance. We show that our approach reuses more traces than the nonspeculative trace reuse technique, with speedups of 43% over a nonspeculative trace reuse and 57% when memory accesses are reused.

Although a software application always executes within a particular environment, current testing methods have largely ignored these environmental factors. Many applications execute in an environment that contains a database. In this paper, we propose a family of test adequacy criteria that can be used to assess the quality of test suites for database-driven applications. Our test adequacy criteria use dataflow information that is associated with the entities in a relational database. Furthermore, we develop a unique representation of a database-driven application that facilitates the enumeration of database interaction associations. These associations can reflect an application's definition and use of database entities at multiple levels of granularity. The usage of a tool to calculate intraprocedural database interaction associations for two case study applications indicates that our adequacy criteria can be computed with an acceptable time and space overhead.

Although graphical user interfaces (GUIs) constitute a large part of the software being developed today and are typically created using rapid prototyping, there are no effective regression testing techniques for GUIs. The needs of GUI regression testing differ from those of traditional software. When the structure of a GUI is modified, test cases from the original GUI are either reusable or unusable on the modified GUI. Since GUI test case generation is expensive, our goal is to make the unusable test cases usable. The idea of reusing these unusable (a.k.a. obsolete) test cases has not been explored before. In this paper, we show that for GUIs, the unusability of a large number of test cases is a serious problem. We present a novel GUI regression testing technique that first automatically determines the usable and unusable test cases from a test suite after a GUI modification. It then determines which of the unusable test cases can be repaired so they can execute on the modified GUI. The last step is to repair the test cases. Our technique is integrated into a GUI testing framework that, given a test case, automatically executes it on the GUI. We implemented our regression testing technique and demonstrate for two case studies that our approach is effective in that many of the test cases can be repaired, and is practical in terms of its time performance.

No abstract available.

Component based software technologies are viewed as essential for creating the software systems of the future. However, the use of externally-provided components has serious drawbacks for a wide range of software engineering activities, often because of a lack of information about the components. Previously (A. Orso et al., 2000), we proposed the use of component metacontents: additional data and methods provided with a component, to support software engineering tasks. The authors present two new metacontent based techniques that address the problem of regression test selection for component based applications: a code based approach and a specification based approach. First, we illustrate the two techniques. Then, we present a case study that applies the code based technique to a real component based system. On the system studied, on average, 26% of the overall testing effort was saved over seven releases, with a maximum savings of 99% for one version.

A widespread recognition of the usefulness of graphical user interfaces (GUIs) has established their importance as critical components of today's software. GUIs have characteristics different from traditional software, and conventional testing techniques do not directly apply to GUIs. This paper's focus is on coverage critieria for GUIs, important rules that provide an objective measure of test quality. We present new coverage criteria to help determine whether a GUI has been adequately tested. These coverage criteria use events and event sequences to specify a measure of test adequacy. Since the total number of permutations of event sequences in any non-trivial GUI is extremely large, the GUI's hierarchical structure is exploited to identify the important event sequences to be tested. A GUI is decomposed into GUI components, each of which is used as a basic unit of testing. A representation of a GUI component, called an event-flow graph, identifies the interaction of events within a component and intra-component criteria are used to evaluate the adequacy of tests on these events. The hierarchical relationship among components is represented by an integration tree, and inter-component coverage criteria are used to evaluate the adequacy of test sequences that cross components. Algorithms are given to construct event-flow graphs and an integration tree for a given GUI, and to evaluate the coverage of a given test suite with respect to the new coverage criteria. A case study illustrates the usefulness of the coverage report to guide further testing and an important correlation between event-based coverage of a GUI and statement coverage of its software's underlying code.

The widespread use of GUIs for interacting with software is leading to the construction of more and more complex GUIs. With the growing complexity come challenges in testing the correctness of a GUI and its underlying software. We present a new technique to automatically generate test cases for GUIs that exploits planning, a well-developed and used technique in artificial intelligence. Given a set of operators, an initial state, and a goal state, a planner produces a sequence of the operators that will transform the initial state to the goal state. Our test case generation technique enables efficient application of planning by first creating a hierarchical model of a GUI based on its structure. The GUI model consists of hierarchical planning operators representing the possible events in the GUI. The test designer defines the preconditions and effects of the hierarchical operators, which are input into a plan-generation system. The test designer also creates scenarios that represent typical initial and goal states for a GUI user. The planner then generates plans representing sequences of GUI interactions that a user might employ to reach the goal state from the initial state. We implemented our test case generation system, called Planning Assisted Tester for Graphical User Interface Systems (PATHS) and experimentally evaluated its practicality and effectiveness. We describe a prototype implementation of PATHS and report on the results of controlled experiments to generate test cases for Microsoft's WordPad.

Branch coverage is an important criteria used during the structural testing of programs. We present a new program execution based approach to generate input data that exercises a selected branch in a program. The test data generation is initiated with an arbitrarily chosen input from the input domain of the program. A new input is derived from the initial input in an attempt to force execution through any of the paths through the selected branch. The method dynamically switches among the paths that reach the branch by refining the input. Using a numerical iterative technique that attempts to generate an input to exercise the branch, it dynamically selects a path that offers less resistance. We have implemented the technique and present experimental results of its performance for some programs. Our results show that our method is feasible and practical.

Graphical User Interfaces (GUIs) are critical components of today's software. Because GUIs have different characteristics than traditional software, conventional testing techniques do not apply to GUI software. In previous work, we presented an approach to generate GUI test cases, which take the form of sequences of actions. In this paper we develop a test oracle technique to determine if a GUI behaves as expected for a given test case. Our oracle uses a formal model of a GUI, expressed as sets of objects, object properties, and actions. Given the formal model and a test case, our oracle automatically derives the expected state for every action in the test case. We represent the actual state of an executing GUI in terms of objects and their properties derived from the GUI's execution. Using the actual state acquired from an execution monitor, our oracle automatically compares the expected and actual states after each action to verify the correctness of the GUI for the test case. We implemented the oracle as a component in our GUI testing system, called Planning Assisted Tester for grapHical user interface Systems (PATHS), which is based on AI planning. We experimentally evaluated the practicality and effectiveness of our oracle technique and report on the results of experiments to test and verify the behavior of our version of the Microsoft WordPad's GUI.

Various methods for value prediction have been proposed to overcome the limits imposed by data dependencies within programs. Using a value prediction scheme, an instruction's computed value is predicted during the fetch stage and forwarded to all dependent instructions to speed up execution. Value prediction schemes have been based on a local context by predicting values using the values generated by the same instruction. This paper presents techniques that predict values of an instruction based on a global context where the behavior of other instructions is used in prediction. The global context includes the path along which an instruction is executed and the values computed by other previously completed instructions. We present techniques that augment conventional last value and stride predictors with global context information. Experiments performed using path-based techniques with realistic table sizes resulted in an increase in prediction of 6.4-8.4% over the current prediction schemes. Prediction using values computed by other instructions resulted in a further improvement of 7.2% prediction accuracy over the best path-based predictor.

The widespread use of GUIs for interacting with soft-ware is leading to the construction of more and more complex GUIs. With the growing complexity comes challenges in testing the correctness of a GUI and the underlying software. We present a new technique to au-tomatically generate test cases for GUIs that exploits planning, a well developed and used technique in ar-tificial intelligence. Given a set of operators, an initial state and a goal state, a planner produces a sequence of the operators that will change the initial state to the goal state. Our test case generation technique first ana-lyzes a GUI and derives hierarchical planning operators from the actions in the GUI. The test designer deter-mines the preconditions and effects of the hierarchical operators, which are then input into a planning system. With the knowledge of the GUI and the way in which the user will interact with the GUI, the test designer creates sets of initial and goal states. Given these ini-tial and final states of the GUI, a hierarchical planner produces plans, or a set of test cases, that enable the goal state to be reached. Our technique has the ad-ditional benefit of putting verification commands into the test cases automatically. We implemented our tech-nique by developing the GUI analyzer and extending a planner. We generated test cases for Microsoft’s Word-Pad to demonstrate the viability and practicality of the approach.

The performance of VLIW architectures is dependent on the capability of the compiler to detect and exploit instruction-level parallelism during instruction scheduling. To exploit the detected parallelism, instructions are reordered to reduce the length of the code schedule and minimize the cycle count for execution. Code reordering is limited by the dependencies among instructions arising from both control flow and data flow. In this paper, we present the design of a VLIW architecture that uses value prediction to remove data dependencies and improve the instruction schedule. Our architecture consists of two execution engines, one for executing the original VLIW code, and the other for executing compensation code after a misprediction. Any code executed due to mispredictions is executed in parallel with the VLIW instructions. The instruction set and hardware of a traditional VLIW machine are modified accordingly to support this type of concurrent execution. The efficacy of the proposed architecture is demonstrated by implementing the prediction model in the Trimaran compiler infrastructure and studying the speedups that result due to the parallel execution of compensation code.

A number of approaches have been proposed to automatically generate test data to traverse a given path in a program. We present a program execution based approach to generate test data for a given path. The technique derives a desired input for a test path by iteratively refining an arbitrarily chosen input. A set of linear constraints on the increments to the input are derived to refine the input. We solve this constraint set using a Unified Numerical Approach (UNA) developed in this paper. Our technique can generate both integer and floating point inputs as well as handle arrays and loops. We determine a basis set of paths for a program and use our technique to generate test data for this set. We implemented and experimentally evaluated our technique. We present results of generating input for scientific programs. The experimental results show that the technique is effective in that it generates input for most of the paths in the basis sets and also efficiently detects linear infeasible paths. Our experiments also show that our technique is efficient in the number of iterations required to generate test data. The time performance shows that it provides a practical method to automatically generate test data for scientific programs.

Load-reuse analysis finds instructions that repeatedly access the same memory location. This location can be promoted to a register, eliminating redundant loads by reusing the results of prior memory accesses. This paper develops a load-reuse analysis and designs a method for evaluating its precision.In designing the analysis, we aspire for completeness---the goal of exposing all reuse that can be harvested by a subsequent program transformation. For register promotion, a suitable transformation is partial redundancy elimination (PRE). To approach the ideal goal of PRE-completeness, the load-reuse analysis is phrased as a data-flow problem on a program representation that is path-sensitive, as it detects reuse even when it originates in a different instruction along each control flow path. Furthermore, the analysis is comprehensive, as it treats scalar, array and pointer-based loads uniformly.In evaluating the analysis, we compare it with an ideal analysis. By observing the run-time stream of memory references, we collect all PRE-exploitable reuse and treat it as the ideal analysis performance. To compare the (static) load-reuse analysis with the (dynamic) ideal reuse, we use an estimator algorithm that computes, given a data-flow solution and a program profile, the dynamic amount of reuse detected by the analysis. We developed a family of estimators that differ in how well they bound the profiling error inherent in the edge profile. By bounding the error, the estimators offer a precise and practical method for determining the run-time optimization benefit.Our experiments show that about 55% of loads executed in Spec95 exhibit reuse. Of those, our analysis exposes about 80%.

Partial redundancy elimination (PRE), the most important component of global optimizers, generalizes the removal of common subexpressions and loop-invariant computations. Because existing PRE implementations are based on code motion, they fail to completely remove the redundancies. In fact, we observed that 73% of loop-invariant statements cannot be eliminated from loops by code motion alone. In dynamic terms, traditional PRE eliminates only half of redundancies that are strictly partial. To achieve a complete PRE, control flow restructuring must be applied. However, the resulting code duplication may cause code size explosion.This paper focuses on achieving a complete PRE while incurring an acceptable code growth. First, we present an algorithm for complete removal of partial redundancies, based on the integration of code motion and control flow restructuring. In contrast to existing complete techniques, we resort to restructuring merely to remove obstacles to code motion, rather than to carry out the actual optimization.Guiding the optimization with a profile enables additional code growth reduction through selecting those duplications whose cost is justified by sufficient execution-time gains. The paper develops two methods for determining the optimization benefit of restructuring a program region, one based on path-profiles and the other on data-flow frequency analysis. Furthermore, the abstraction underlying the new PRE algorithm enables a simple formulation of speculative code motion guaranteed to have positive dynamic improvements. Finally, we show how to balance the three transformations (code motion, restructuring, and speculation) to achieve a near-complete PRE with very little code growth.We also present algorithms for efficiently computing dynamic benefits. In particular, using an elimination-style data-flow framework, we derive a demand-driven frequency analyzer whose cost can be controlled by permitting a bounded degree of conservative imprecision in the solution.

An important problem that arises in path oriented testing is the generation of test data that causes a program to follow a given path. In this paper, we present a novel program execution based approach using an iterative relaxation method to address the above problem. In this method, test data generation is initiated with an arbitrarily chosen input from a given domain. This input is then iteratively refined to obtain an input on which all the branch predicates on the given path evaluate to the desired outcome. In each iteration the program statements relevant to the evaluation of each branch predicate on the path are executed, and a set of linear constraints is derived. The constraints are then solved to obtain the increments for the input. These increments are added to the current input to obtain the input for the next iteration. The relaxation technique used in deriving the constraints provides feedback on the amount by which each input variable should be adjusted for the branches on the path to evaluate to the desired outcome.When the branch conditions on a path are linear functions of input variables, our technique either finds a solution for such paths in one iteration or it guarantees that the path is infeasible. In contrast, existing execution based approaches may require an unacceptably large number of iterations for relatively long paths because they consider only one input variable and one branch predicate at a time and use backtracking. When the branch conditions on a path are nonlinear functions of input variables, though it may take more then one iteration to derive a desired input, the set of constraints to be solved in each iteration is linear and is solved using Gaussian elimination. This makes our technique practical and suitable for automation.

The existence of statically detectable correlation among conditional branches enables their elimination, an optimization that has a number of benefits. This paper presents techniques to determine whether an interprocedural execution path leading to a conditional branch exists along which the branch outcome is known at compile time, and then to eliminate the branch along this path through code restructuring. The technique consists of a demand driven interprocedural analysis that determines whether a specific branch outcome is correlated with prior statements or branch outcomes. The optimization is performed using a code restructuring algorithm that replicates code to separate out the paths with correlation. When the correlated path is affected by a procedure call, the restructuring is based on procedure entry splitting and exit splitting. The entry splitting transformation creates multiple entries to a procedure, and the exit splitting transformation allows a procedure to return control to one of several return points in the caller. Our technique is efficient in that the correlation detection is demand driven, thus avoiding exhaustive analysis of the entire program, and the restructuring never increases the number of operations along a path through an interprocedural control flow graph. We describe the benefits of our interprocedural branch elimination optimization (ICBE). Our experimental results show that, for the same amount of code growth, the estimated reduction in executed conditional branches is about 2.5 times higher with the ICBE optimization than when only intraprocedural conditional branch elimination is applied.

The high cost and growing importance of interprocedural data flow analysis have led to an increased interest in demand-driven algorithms. In this article, we present a general framework for developing demand-driven interprocedural data flow analyzers and report our experience in evaluating the performance of this approach. A demand for data flow information is modeled as a set of queries. The framework includes a generic demand-driven algorithm that determines the response to query by iteratively applying a system of query propagation rules. The propagation rules yield precise responses for the class of distributive finite data flow problems. We also describe a two-phase framework variation to accurately handle nondistributive problems. A performance evaluation of our demand-driven approach is presented for two data flow problems, namely, reaching-definitions and copy constant propagation. Our experiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhaustive analysis.

Although code transformations are routinely applied to improve the performance of programs for both scalar and parallel machines, the properties of code-improving transformations are not well understood. In this article we present a framework that enables the exploration, both analytically and experimentally, of properties of code-improving transformations. The major component of the framework is a specification language, Gospel, for expressing the conditions needed to safely apply a transformation and the actions required to change the code to implement the transformation. The framework includes a technique that facilitates an analytical investigation of code-improving transformations using the Gospel specifications. It also contains a tool, Genesis, that automatically produces a transformer that implements the transformations specified in Gospel. We demonstrate the usefulness of the framework by exploring the enabling and disabling properties of transformations. We first present analytical results on the enabling and disabling properties of a set of code transformations, including both traditional and parallelizing transformations, and then describe experimental results showing the types of transformations and the enabling and disabling interactions actually found in a set of programs.

Program slicing is an effective techniqe for narrowing the focus of attention to the relevant parts of a program during the debugging process. However, imprecision is a problem in static slices, since they are based on all possible executions that reach a given program point rather than the specific execution under which the program is being debugged. Dynamic slices, based on the specific execution being debugged, are precise but incur high run-time overhead due to the tracing information that is collected during the program's execution. We present a hybrid slicing technique that integrates dynamic information from a specific execution into a static slice analysis. The hybrid slice produced is more precise that the static slice and less costly that the dynamic slice. The technique exploits dynamic information that is readily available during debugging—namely, breakpoint information and the dynamic call graph. This information is integrated into a static slicing analysis to more accurately estimate the potential paths taken by the program. The breakpoints and call/return points, used as reference points, divide the execution path into intervals. By associating each statement in the slice with an execution interval, hybrid slicing provides information as to when a statement was encountered during execution. Another attractive feature of our approach is that it allows the user to control the cost of hybrid slicing by limiting the amount of dynamic information used in computing the slice. We implemented the hybrid slicing technique to demonstrate the feasibility of our approach.

After changes are made to a previously tested program, a goal of regression testing is to perform retesting based on the modifications while maintaining the same testing coverage as completely retesting the program. This paper presents a novel approach to data flow based regression testing that uses slicing algorithms for the explicit detection of definition-use associations that are affected by a program change. An important benefit of this slicing technique is that, unlike previous techniques, neither data flow history nor recomputation of data flow for the entire program is required to detect affected definition-use associations. The program changes drive the recomputation of the required partial data flow through slicing. Another advantage is that the technique achieves the same testing coverage with respect to the affected definition-use associations as a complete retest of the program, without maintaining a test suite. Thus, the overhead of maintaining and updating a test suite is eliminated.

Software testing is an expensive component of software development and maintenance. For data flow testing, test cases must be found to test the def-use pairs in a program. Since some of the def-use pairs identified through static analysis may be infeasible, no amount of testing effort may result in exhaustive testing of a program. Therefore in practice a fixed amount of effort is spent in testing a program. We develop an approach for assigning priorities to def-use pairs, such that the def-use pairs with higher priorities can be expected to require less effort for test case generation and therefore testing. Thus, by using the priorities as a guide for ordering the def-use pairs for testing, we can maximize the number of def-use pairs tested using a fixed amount of testing effort. We apply the technique to regression testing during the software maintenance phase, in which case the priorities are assigned to capture not only the difficulty in test case generation but also the likelihood that an error introduced by a program change is uncovered by the test case.

This paper presents a general framework for deriving demand-driven algorithms for interprocedural data flow analysis of imperative programs. The goal of demand-driven analysis is to reduce the time and/or space overhead of conventional exhaustive analysis by avoiding the collection of information that is not needed. In our framework, a demand for data flow information is modeled as a set of date flow queries. The derived demand-driven algorithms find responses to these queries through a partial reversal of the respective data flow analysis. Depending on whether minimizing time or space is of primary concern, result caching may be incorporated in the derived algorithm. Our framework is applicable to interprocedural data flow problems with a finite domain set. If the problem's flow functions are distributive, the derived demand algorithms provide as precise information as the corresponding exhaustive analysis. For problems with monotone but non-distributive flow functions the provided data flow solutions are only approximate. We demonstrate our approach using the example of interprocedural copy constant propagation.

Article Free Access Share on Hybrid slicing: an approach for refining static slices using dynamic information Authors: Rajiv Gupta Dept. of Computer Science, University of Pittsburgh, Pittsburgh, PA Dept. of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile , Mary Lou Soffa Dept. of Computer Science, University of Pittsburgh, Pittsburgh, PA Dept. of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile Authors Info & Claims SIGSOFT '95: Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineeringOctober 1995 Pages 29–40https://doi.org/10.1145/222124.222137Published:01 October 1995Publication History 43citation417DownloadsMetricsTotal Citations43Total Downloads417Last 12 Months16Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Although the application of code transformations is critical to exploit parallelism in program code, few guidelines or tools are provided to determine what transformations should be applied and where they should be applied. In this paper, we approach this problem by first providing a taxonomy of code transformations to assist the user in parallelizing programs. We then present an efficient technique to remove transformations from the code when it is determined that they are ineffective or prevent more beneficial transformations from being applied. The technique to remove transformations employs inverse primitive actions, making it transformation independent. The technique uses the program dependence graph as the intermediate representation, making it language independent.

A transformation applied to optimize or parallelize a program may be found to be ineffective, or may be made invalid by code changes. In this paper, we present a technique to remove such transformations. The order of undoing the transformations is independent of the application order. The technique uses post conditions of a transformation to determine whether the transformation can be immediately removed. Transformations that affect the immediate removal of a transformation must be identified and removed. Other transformations made invalid by the removal of a transformation must also be undone. The technique employs inverse primitive actions, making the technique transformation independent. The enabling and disabling interactions of transformations are used to drive the process, thereby reducing redundant analysis when undoing transformations.

Although data flow analysis was first developed for use in compilers, its usefulness is now recognized in many software tools. Because of its compiler origins, the computation of data flow for software tools is based on the traditional exhaustive data flow framework. However, although this framework is useful for computing data flow for compilers, it is not the most appropriate for software tools, particularly those used in the maintenance stage. In maintenance, testing and debugging is typically performed in response to program changes. As such, the data flow required is demand driven from the changed program points. Rather than compute the data flow exhaustively using the traditional data flow frame work, we present a framework for partial analysis. The framework includes a specification language enabling the specification of the demand driven data flow desired by a user. From the specification, a partial analysis algorithm is automatically generated using an L-attributed definition for the grammar of the specification language. A specification of a demand driven data flow problem expresses characteristics that define the kind of traversal needed in the partial analysis and the type of dependencies to be captured. The partial analyses algorithms are efficient in that only as much of the program is analyzed as actually needed, thus reducing the time and space requirements over exhaustively computing the data flow information. The algorithms are shown to be useful when debugging and testing programs during maintenance.>

No abstract available.

Abstract Although code optimizations are necessary to parallelize code, few guidelines exist for determining when and where to apply optimizations to produce the most efficient code. The order of applying optimizations can also have an impact on the efficiency of the final target code. However, determining the appropriate optimizations is difficult due to the complex interactions among the optimizations, scheduler and architecture. To aid in selecting appropriate optimizations, an optimizer generator (Genesis) is presented that produces an optimizer from specifications of optimizations. This paper describes the design and implementation of Genesis and demonstrates how such a generator could be used by optimizer designers. Some experiences with the generator are also described.

Although graph coloring is widely recognized as an effective technique for register allocation, memory demands can become quite high for large interference graphs that are needed in coloring. In this paper we present an algorithm that uses the notion of clique separators to improve the space overhead of coloring. The algorithm, based on a result by R. Tarjan regarding the colorability of graphs, partitions program code into code segments using clique separators. The interference graphs for the code partitions are constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the entire program. This approach can be used to perform register allocation in a space-efficient manner. For straight-line code (e.g., local register allocation), an optimal allocation can be obtained from optimal allocations for individual code partitions. Experimental results are presented demonstrating memory demand reductions for interference graphs when allocating registers using clique separators.

The dependencies that exist among definitions and uses of variables in a program are required by many language-processing tools. This paper considers the computation of definition-use and use-definition chains that extend across procedure boundaries at call and return sites. Intraprocedural definition and use information is abstracted for each procedure and is used to construct an interprocedural flow graph. This intraprocedural data-flow information is then propagated throughout the program via the interprocedural flow graph to obtain sets of reaching definitions and/or reachable uses for reach interprocedural control point, including procedure entry, exit, call, and return. Interprocedural definition-use and/or use-definition chains are computed from this reaching information. The technique handles the interprocedural effects of the data flow caused by both reference parameters and global variables, while preserving the calling context of called procedures. Additionally, recursion, aliasing, and separate compilation are handled. The technique has been implemented using a Sun-4 Workstation and incorporated into an interprocedural data-flow tester. Results from experiments indicate the practicality of the technique, both in terms of the size of the interprocedural flow graph and the size of the data-flow sets.

As the number of available multiprocessors increases, so does the importance of providing software support for these systems, including parallel compilers. Data flow analysis, an important component of software tools, may be computed many times during the compilation of a program, especially when compiling for a multiprocessor. Although converting a sequential data flow algorithm to a parallel algorithm can present some opportunities for computing data flow in parallel, more parallelism can be exposed by the development of new parallel data flow algorithms. We present a technique that computes rapid data flow problems in parallel and thus is applicable for commonly used classical data flow problems, including reaching definitions, reachable uses, available expressions, and very busy expressions. Unlike previous techniques, our technique exploits the inherent parallelism in the data flow computation that occurs across independent paths, within linear paths, and in paths through loops of a control flow graph. The technique first changes cyclic structures in a control flow graph to acyclic structures and then builds a combining directed acyclic graph (DAG) that represents the paths through the control flow graph needed to compute data flow. Data flow is then computed using two passes over the DAG by computing the data flow for the nodes on each level of the DAG in parallel. We also present experimental results comparing the performance of our algorithm with a sequential algorithm and a parallelized sequential algorithm.>

A new approach is given for scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors. The key idea in our approach is to exploit the fine grained parallelism present in the instruction stream. In this context, schedules are constructed by a careful balancing of execution and communication costs at the level of individual instructions, and their data dependencies. Three methods are used to evaluate our approach. First, several existing methods are extended to the fine grained situation. Our approach is then compared to these methods using both static schedule length analyses, and simulated executions of the scheduled code. In each instance, our method is found to provide significantly shorter schedules. Second, by varying parameters such as the speed of the instruction set, and the speed/parallelism in the interconnection structure, simulation techniques are used to examine the effects of various architectural considerations on the executions of the schedules. These results show that our approach provides significant speedups in a wide-range of situations. Third, schedules produced by our approach are executed on a two-processor Data General shared memory multiprocessor system. These experiments show that there is a strong correlation between our simulation results, and these actual executions, and thereby serve to validate the simulation studies. Together, our results establish that fine grained parallelism can be exploited in a substantial manner when scheduling a sequential instruction stream for execution "in parallel" on asynchronous multiprocessors.>

Creating highly optimized code for parallel machines is a difficult task, as the efficiency of the transformed the code depends of the types of tranformations applied.

Data flow analysis techniques have traditionally been restricted to the analysis of scalar variables. This retriction, however, imposes a limitation on the kinds of optimizations that can be performed in loops containing array references. We present a data flow framework for array reference analysis that provides the information needed in various optimizations targeted at sequential or fine-grained parallel architectures. The framework extends the traditional scalar framework by incorporating iteration distance values into the analysis to qualify the computed data flow solution during the fixed point iteration. Analyses phrased in this framework are capable of discovering recurrent access patterns among array references that evolve during the execution of a loop. Applications of our framework are discussed for register allocation, load/store optimizations, and controlled loop unrolling.

Abstract A commonly used approach for detecting defects in a program is to generate a suite of test inputs which exercises the entire program under a given testing criterion. Current techniques to generate test cases automatically that satisfy a testing criterion choose test input data by considering the testing requirements in an arbitrary order. In this paper, a technique is presented that groups the requirements and orders the generation of the test cases to reduce the number of test cases generated. The grouping is based on the statically determined property of post‐dominance. Test cases for each group are generated taking into account requirements for other groups. The use of this technique to generate test cases can be expected to produce fewer test cases that have to be retained with the software. A smaller number of test cases will require less effort and resources to test the software. The technique is especially useful in the maintenance environment, whether retesting of a changed program is done exhaustively or incrementally. The technique not only attempts to minimize the number of test cases generated but also reduces the effort to generate the test cases using the concept of a program slice.

This paper presents a technique to select a representative set of test cases from a test suite that provides the same coverage as the entire test suite. This selection is performed by identifying, and then eliminating, the redundant and obsolete test cases in the test suite. The representative set replaces the original test suite and thus, potentially produces a smaller test suite. The representative set can also be used to identify those test cases that should be rerun to test the program after it has been changed. Our technique is independent of the testing methodology and only requires an association between a testing requirement and the test cases that satisfy the requirement. We illustrate the technique using the data flow testing methodology. The reduction that is possible with our technique is illustrated by experimental results.

The authors present a novel approach to data-flow-based regression testing that uses slicing type algorithms to explicitly detect definition-use pairs that are affected by a program change. An important benefit of the slicing technique is that, unlike previous techniques, no data flow history is needed nor is the recomputation of data flow for the entire program required to detect affected definition-use pairs. The program changes drive the recomputation of the required partial data flow through slicing. Another advantage is that the proposed technique achieves the same testing coverage as a complete retest of the program without the need for maintaining and updating a test suite.>

A software environment for visualization when parallelizing programs is described. The system supports multiparadigm program visualization, automatic generation of optimizers from specifications, interactive and undo facilities for code transformations, and a multilevel browser. Textual and graphical forms of optimization specification languages are utilized in the specification of both traditional and parallelizing transformations. An undo facility is provided for the user to remove ineffective or inappropriate transformations. An extended form of the program dependence graph is developed that not only enables the exploitation of parallelism in sequential programs by applying transformations but also facilitates mappings for code visualization. The conceptual framework that allows multiparadigm program visualization is presented. A multilevel browser can be used to browse any block of statements in one program view, and the corresponding code of another program view is highlighted.>

Although the tasks of applying transformations and scheduling instructions are typically implemented in separate phases of a parallelizing compiler, interactions between these phases occur. The authors discuss these interdependencies and demonstrate that the separate phase approach can result in the application of a sequence of transformations that is not effective. The techniques presented for integrating these tasks utilize an iterative approach to applying program transformations and scheduling instructions for execution on a multiprocessor. These integrated techniques employ a demand driven approach to applying transformations; by iterating between the scheduling and transforming tasks, transformations are applied to the program only if and where they are needed. The authors also introduce an automatic transformation application and selection algorithm that provides further control over the application of transformations.>

Although optimizing compilers have been quite successful in producing excellent code, two factors that limit their usefulness are the accompanying long compilation times and the lack of good symbolic debuggers for optimized code. One approach to attaining faster recompilations is to reduce the redundant analysis that is performed for optimization in response to edits, and in particulars, small maintenance changes, without affecting the quality of the generated code. Although modular programming with separate compilation aids in eliminating unnecessary recompilation and reoptimization, recent studies have discovered that more efficient code can be generated by collapsing a modular program through procedure inlining. To avoid having to reoptimize the resultant large procedures, this paper presents techniques for incrementally incorporating changes into globally optimized code. An algorithm is given for determining which optimizations are no longer safe after a program change, and for discovering which new optimizations can be performed in order to maintain a high level of optimization. An intermediate representation is incrementally updated to reflect the current optimizations in the program. Analysis is performed in response to changes rather than in preparation for possible changes, so analysis is not wasted if an edit has no far-reaching effects. The techniques developed in this paper have also been exploited to improve on the current techniques for symbolic debugging of optimized code.

article Free Access Share on Automatic generation of global optimizers Authors: Deborah Whitfield Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile , Mary Lou Soffa Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 26Issue 6June 1991 pp 120–129https://doi.org/10.1145/113446.113456Published:01 May 1991Publication History 22citation315DownloadsMetricsTotal Citations22Total Downloads315Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Compile-time techniques for storage allocation of scalar values into memory modules that limit run-time memory-access conflicts are presented. The allocation approach is applicable to those operands in instructions that can be predicted at compile-time, where an instruction is composed of the multiple operations and corresponding operands that execute in parallel. Algorithms to schedule data transfers among memory modules to avoid conflicts that cannot be eliminated by the distribution of values alone are developed. The techniques have been implemented as part of a compiler for a reconfigurable long instruction word architecture. Results of experiments are presented demonstrating that a very high percentage of memory access conflicts can be avoided by scheduling a very low number of data transfers.>

As a result of modifications to a program during the maintenance phase, the size of a test suite used for regression testing can become unmanageable. The authors present a technique that selects from a test suite a representative set of test cases that provides the same measure of coverage as the test suite. This selection is performed by the identification of the redundant and obsolete test cases in the test suite. The representative set can be used to reduce the size of the test suite by substituting for the test suite. The representative set can also be used to determine those test cases that should be rerun to test the program after it has been changed. The technique is independent of the testing methodology and only requires an association between each testing requirement and the test cases that satisfy the requirement. The technique is illustrated by means of the data flow testing methodology. Experimental studies are being performed that demonstrate the effectiveness of the technique.>

As an approach to deriving an application order of optimizing transformations, a framework is developed for examining the interactions of the transformations. The framework is based on an axiomatic specification technique and includes both pre-conditions and post conditions that must exist before and after applying optimizations. For a selected set of optimizations, the framework is used to determine those interactions among the optimizations that can create conditions and those that can destroy conditions for applying other optimizations. From these interactions, an application order is derived to obtain the potential benefits of the optimizations that can be applied to a program. In some cases, the ordering of a pair of optimizations is unambiguous in that one optimization can either create or destroy the conditions for the other. In the few cases where there is a cyclic interaction, the ordering is resolved based on the perceived importance of the two optimizations.

A hardware support mechanism is presented that permits all classes of data objects, including dynamically allocated objects and array elements, to be held in registers without consideration of possible aliases and without requiring that the generated code maintain consistency between register and memory copies of variables. Use of this approach permits programs to benefit from the speed advantages and reduced memory traffic associated with register storage, obviates the need to collect aliasing information for use in register allocation, and reduces instruction traffic by eliminating code used solely to maintain register-memory consistency. The support hardware can be implemented using known hardware technology and without increasing the cycle time of the processor.>

Abstract Current compiler technology performs extensive code transformations either to parallelize code or to perform optimizations that reduce space or time. The cost of the analyses for these transformations is high and is further magnified when edits are made, forcing complete recompilation. By extending the concept of incremental compilation to include fine‐grained, high‐quality target code generation, we develop techniques that reuse the information created by an optimizing compiler to incorporate program edits efficiently into optimized target code. Our techniques include developing models of register usage for both local and global register allocation schemes and algorithms for incrementally updating these structures in response to an editing change. Based on these changes, the target code is updated. As graph colouring is a widely accepted register allocation scheme, we present techniques to rebuild and recolour interference graphs incrementally. Results from experiments that compare the performance of the incremental target code generator with its non‐incremental counterpart are reported, showing a saving when incorporating changes incrementally.

Abstract Although the expressive power of retentive control is widely accepted, languages possessing such control forms are not always available. In this paper, we present an implementation technique to extend a recursive language to one containing simulation processes. In particular, we report on the design of a preprocessor that translates SimCal, a language that combines Pascal and the process abstraction of Simula, into Pascal. The translation is done automatically by the preprocessor without additional information from the user. The preprocessor has been implemented for a microcomputer using Turbo Pascal, which is also used as the target language. SimCal has been found to be useful for teaching simulation and for programming simulation applications.

Region scheduling, a technique applicable to both fine-grain and coarse-grain parallelism, uses a program representation that divides a program into regions consisting of source and intermediate level statements and permits the expression of both data and control dependencies. Guided by estimates of the parallelism present in regions, the region scheduler redistributes code, thus providing opportunities for parallelism in those regions containing insufficient parallelism compared to the capabilities of the executing architecture. The program representation and the transformations are applicable to both structured and unstructured programs, making region scheduling useful for a wide range of applications. The results of experiments conducted using the technique in the generation of code for a reconfigurable long instruction word architecture are presented. The advantages of region scheduling over trace scheduling are discussed.>

Although graph coloring is widely recognized as an effective technique for global register allocation, the overhead can be quite high, not only in execution time but also in memory, as the size of the interference graph needed in coloring can become quite large. In this paper, we present an algorithm based upon a result by R. Tarjan regarding the colorability of graphs which are decomposable using clique separators, that improves on the overhead of coloring. The algorithm first partitions program code into code segments using the notion of clique separators. The interference graphs for the code partitions are next constructed one at a time and colored independently. The colorings for the partitions are combined to obtain a register allocation for the program code. The technique presented is both efficient in space and time because the graph for only a single code segment needs to be constructed and colored at any given point in time. The partitioning of a graph using clique separators increases the likelihood of obtaining a coloring without spilling and hence an efficient allocation of registers for the program. For straight line code an optimal allocation for the entire program code can be obtained from optimal allocations for individual code segments. In the presence of branches, optimal allocation along one execution path and a near optimal allocation along alternative paths can be potentially obtained. Since the algorithm is highly efficient, it eliminates the need for a local register allocation phase.

A technique is presented for incrementally updating solutions to both union and intersection data-flow problems in response to program edits and transformations. For generality, the technique is based on the iterative approach to computing data-flow information. The authors show that for both union and intersection problems, some changes can be incrementally incorporated immediately into the data-flow sets while others are handled by a two-phase approach. The first phase updates the data-flow sets to overestimate the effect of the program change, enabling the second phase to incrementally update the affected data-flow sets to reflect the actual program change. An important problem that is addressed is the computation of the data-flow changes that need to be propagated throughout a program, based on different local code changes. The technique is compared to other approaches to incremental data-flow analysis.>

An incremental testing system to aid in unit testing during the maintenance stage is described. Based on data-flow testing, the system is designed for use in a programming environment; it shares common information and techniques with tools typically found in programming environments. In response to a change in a module, the incremental tester reuses the analysis and test cases from the previous testing session. The analysis is incrementally updated to determine areas of the program that must be retested. From the updates, the tester determines which test cases must be rerun, which may be eliminated, and whether the test cases are sufficient for the changed program.>

Although optimizing compilers have successfully been used to reduce the size and running times of compiled programs, present incremental compilers only support the incremental update of unoptimized code. In this work, we extend the notion of incremental compilation to include optimized code. Techniques to incrementally compile locally optimized code, given intermediate code modifications are developed using a program representation based on flow graphs and dags. A model is designed to represent both unoptimized and optimized code and to maintain an optimizing history. Changes to the optimized code which either destroy optimizations or create conditions for further optimizations are incorporated into the model and the optimized code without recompiling unaffected optimizations.

The problem of finding a minimum cardinality feedback vertex set of a directed graph is considered. Of the classic NP-complete problems, this is one of the least understood. Although Karp showed the general problem to be NP-complete, a linear algorithm for its solution on reducible flow graphs was given by Shamir. The class of reducible flow graphs is the only nontrivial class of graphs for which a polynomial-time algorithm to solve this problem is known. The main result of this paper is to present a new class of graphs—the cyclically reducible graphs —for which minimum feedback vertex sets can be found in polynomial time. This class is not restricted to flow graphs, and most small graphs (10 or fewer nodes) fall into this class. The identification of this class is particularly important since there do not exist approximation algorithms for this problem having a provably good worst case performance. Along with the class and a simple polynomial-time algorithm for finding minimum feedback vertex sets of graphs in the class, several related results are presented. It is shown that there is no “forbidden subgraph” characterization of the class and that there is no particular inclusion relationship between this class and the reducible flow graphs. In addition, it is shown that a class of (general) graphs, which are related to the reducible flow graphs, are contained in the cyclically reducible class.

An evaluation stack, used exclusively to store temporary values in expression evaluation, is known to be an effective mechanism in the implementation of high level languages. This work considers the efficient management of evaluation stacks for concurrent programming languages. Techniques for sharing a single evaluation stack among many processes, without copying on process switches, are developed. The best strategy for managing the evaluation stack is shown to depend strongly upon the scheduling paradigm adopted by the run-time support of the language. Simulation studies, driven by synthetic workloads, show that the techniques described in this paper exhibit substantial performance improvements over traditional temporary storage management schemes for concurrent languages.

Reclamation policies are presented which permit the reuse of storage for procedure instances before the procedures terminate. These eager reclamation policies are applicable under certain conditions and can reduce the total amount of memory needed for the execution of a program. The policies essentially differ in the amount of run-time checks needed and the reclamation opportunities. This eager reclamation strategy would be particularly useful when instances are implemented using register banks or in a microprocessor environment.

A methodology for the experimental investigation of the implementation of control in programming languages is presented. The methodology specifies a data-collection technique, the environment for driving simulations of control implementations, and a meaningful metric for performance evaluation. The key in the methodology is the separation of activity which is affected by the control implementation from that which is not.

The combination of coroutines with recursive procedures is characteristic of many modern higher level languages offering advanced control structures (e.g., SIMULA-67, SL5, or INTERLISP). We say a language has block-structured coroutines (BSCRs) when static nesting considerations govern the usage of this control combination. Starting with the BSCR control description work of Wang and Dahl, this paper pursues further the implications of static program structure on BSCR programs in a particular compilation-oriented setting. Disciplines on BSCR reference assignment and individual control actions are defined, offering enhanced implementability and program comprehensibility. Of particular interest is a scope-based discipline on "detach " operations, which avoids the formation of idle chain subheads, an implementationally undesirable condition. The retention requirements of BSCRs are analyzed under a range of possible remote accessibility conditions, and two deletion strategies are then defined, keyed to these requirements. The first uses a special form of scope-sensitive reference counting, and the second does mark-sweep garbage collection, again exploiting static program structure. Space and time estimates for both methods are given, along with avenues for continuing research.

Analyzing and grading programs in an introductory computer science course can require a great deal of time and effort from the course instructor. This paper investigates the development of a system called Instructional Tool for Program ADvising (ITPAD) that assumes some of the instructor's duties by keeping student profiles and assignment profiles, by detecting possible plagiarism, and by providing suggestions directly to the students for improving their programs.

Abstract Algorithms using retentive control are currently being developed in operating systems, simulation, artificial intelligence and language implementation. This paper investigates two aspects of a form of retentive control, namely coroutines. The behaviour of coroutines and language primitives that express the operations on coroutines are explored by surveying the literature for coroutine usage. Secondly, the area of control implementation of coroutines is investigated by considering the Bobrow and Wegbreit spaghetti stack as a viable data structure for managing run‐time storage. Changes in the basic model of the spaghetti stack, tailoring its use in a strictly coroutine environment with subsequent implementation alternatives, are explored. An investigation through experimentation is made of the effect control‐related aspects of coroutines have on the revised spaghetti stack models. An analysis of the empirical results obtained provides a useful barometer for selecting appropriate storage management schemes based on coroutine design and usage.