Transforming flow information during code optimization for timing analysis

The steadily growing embedded-systems market comprises many application domains in which real-time constraints must be satisfied. To guarantee that these constraints are met, the analysis of the worst-case execution time (WCET) of software components is mandatory. In general WCET analysis needs additional control-flow information, which may be provided manually by the user or calculated automatically by program analysis. For flexibility and simplicity reasons it is desirable to specify the flow information at the same level at which the program is developed, i.e., at the source level. In contrast, to obtain precise WCET bounds the WCET analysis has to be performed at machine-code level. Mapping and transforming the flow information from the source-level down to the machine code, where flow information is used in the WCET analysis, is challenging, even more so if the compiler generates highly optimized code. In this article we present a method for transforming flow information from source code to machine code. To obtain a mapping that is safe and accurate, flow information is transformed in parallel to code transformations performed by an optimizing compiler. This mapping is not only useful for transforming manual code annotations but also if platform-independent flow information is automatically calculated at the source level. We show that our method can be applied to every type of semantics-preserving code transformation. The precision of this flow-information transformation allows its users to calculate tight WCET bounds.     

Designing a source-level debugger for cognitive agent programs

When an agent program exhibits unexpected behaviour, a developer needs to locate the fault by debugging the agent’s source code. The process of fault localisation requires an understanding of how code relates to the observed agent behaviour. The main aim of this paper is to design a source-level debugger that supports single-step execution of a cognitive agent program. Cognitive agents execute a decision cycle in which they process events and derive a choice of action from their beliefs and goals. Current state-of-the-art debuggers for agent programs provide insight in how agent behaviour originates from this cycle but less so in how it relates to the program code. As relating source code to generated behaviour is an important part of the debugging task, arguably, a developer also needs to be able to suspend an agent program on code locations. We propose a design approach for single-step execution of agent programs that supports both code-based as well as cycle-based suspension of an agent program. This approach results in a concrete stepping diagram ready for implementation and is illustrated by a diagram for both the Goal and Jason agent programming languages, and a corresponding full implementation of a source-level debugger for Goal in the Eclipse development environment. The evaluation that was performed based on this implementation shows that agent programmers prefer a source-level debugger over a purely cycle-based debugger.     

Timing constraint specification and analysis

Real‐time programmers have to deal with the problem of relating timing constraints associated with source code to sequences of machine instructions. This paper describes an environment to assist users in the specification and analysis of timing constraints. A timing analyzer predicts the best and worst case bounds for these constrained portions of code. A user interface for this timing analyzer was developed to depict whether these constraints were violated or met. A user is allowed to specify timing constraints within the source code of a C program. The user interface also provides three different methods for interactively selecting portions of programs. After each selection the corresponding bounded times, source code lines, and machine instructions are automatically displayed. Users are prevented from only selecting portions of the program for which timing bounds cannot be obtained. In addition, a technique is presented that allows the timing analysis to scale efficiently with complex functions and loops. The result is a user‐friendly environment that supports the user specification and analysis of timing constraints at a high (source code) level and retains the accuracy of low (machine code) level analysis. Copyright © 1999 John Wiley & Sons, Ltd.     

Performance debugging of Esterel specifications

Synchronous languages like Esterel have been widely adopted for designing reactive systems in safety-critical domains such as avionics. Specifications written in Esterel are based on the underlying ??synchrony hypothesis??, which needs to be validated when Esterel specifications get compiled to real implementations (such as C code). In this work, we present a model-driven and architecture-aware timing analysis framework for C code generated from Esterel and executed on general-purpose processors. By integrating model-level information into the traditional timing analysis, we can efficiently compute accurate time estimates via systematically eliminating a large number of infeasible paths in the generated code. Experimental results show that with our proposed intermediate representation level infeasible path analysis in the model compilation, we obtain up to 16.1?% tighter WCET estimates compared to the traditional assembly code level infeasible path detection with substantially less analysis time. Furthermore, by maintaining the traceability links between Esterel specifications and the generated C code, we are able to map the time-critical computations at the C-level back to the Esterel-level.     

CCodeExtractor:一种针对C程序自动化的函数提取方法

随着程序规模和复杂性的增加,代码重构在改善软件质量、性能以及提高软件的扩展性和维护性等方面至关重要。目前的Eclipse中,C源代码重构工具的函数提取只能处理一些简单的代码,且处理过程需要人工参与,不能自动化处理。为此,提出一种C源代码级别自动化的函数提取方法(CCodeExtractor),它通过指定提取条件,在保证语义一致的前提下,将符合条件的代码片段自动分离成一个单独的函数,并将其放到新文件中,而原代码片段替换成了一个函数调用。为了验证CCodeExtractor的有效性,结合循环分析和优化在实际应用中的广泛应用,在LLVM上实现了一个提取循环的工具,将程序中满足条件的for循环封装成单独的函数。在实验中,使用该工具对6个不同规模的程序进行了测试并且对比了变换前后程序运行的结果。实验结果表明,CCodeExtractor代码提取方法在保证程序语义不变的前提下,适用于不同规模的程序。     

Complete worst-case execution time analysis of straight-line hard real-time programs

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a hard real-time program is addressed. The analysis is focused on straight-line code (without loops and recursive function calls) which is quite commonly found in synthesised code for embedded systems. A comprehensive timing analysis system covering both low-level (assembler instruction level) as well as high-level aspects (programming language level) is presented. The low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. The high-level analysis uses the results from the low-level to compute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, based on the functional dependencies between various program parts.     

Code compaction for parallel architectures

There are two principal methods used to exploit the parallelism available on a parallel machine: the program to be executed can be optimized by hand, or the program can be automatically converted to parallel machine code by a compiler. The first method usually derives parallelism at the procedure level; a parallel program is written in a high-level language and typically has various modules executing in parallel. By contrast, the compiler methodically transforms the program into parallel code using various transformations, such as code movement. The automatic conversion of a program to parallel code is called compaction or parallelization. This paper describes the evolution of a new compaction program and presents a new algorithm for determining legal code movements. A simulator of the target architecture was used to estimate the execution times of a sample suite of programs before and after compaction. The results verify that substantial advantages arise from applying this compaction technique.     

Predicting program execution times by analyzing static and dynamic program paths

This paper describes a method to predict guaranteed and tight deterministic execution time bounds of a sequential program. The basic prediction technique is a static analysis based on simple timing schema for source-level language constructs, which gives accurate predictions in many cases. Using powerful user-provided information, dynamic path analysis refines looser predictions by eliminating infeasible paths and decomposing the possible execution behaviors in a pathwise manner. Overall prediction cost is scalable with respect to desired precision, controlling the amount of information provided. We introduce a formal path model for dynamic path analysis, where user execution information is represented by a set of program paths. With a well-defined practical high-level interface language, user information can be used in an easy and efficient way. We also introduce a method to verify given user information with known program verification techniques. Initial experiments with a timing tool show that safe and tight predictions are possible for a wide range of programs. The tool can also provide predictions for interesting subsets of program executions.This research was supported in part by the Office of Naval Research under grant number N00014-89-J-1040.     

用嵌入式数据库实现轻量的序列化模块

数据的存储和传输序列化是软件编制中必不可少的过程,将该过程整合为独立通用的模块,可以降低软件开发的复杂度,提高开发效率。本文介绍了使用嵌入式数据库Berkely DB实现轻量的通用序列化模块的方法。该方法通过在现有代码上植入序列化模块的形式,使得对原有代码的改造减少到最小,而源代码级的集成也易于进行程序调试和除错,因此具备简便易用的特点。文中给出了一个应用实例。     

一种基于动态插桩的JavaScript反事实执行方法

目前,静态分析技术已被广泛用于JavaScript程序的安全性分析。但是由于JavaScript支持通过eval等方法在运行时动态生成代码,仅靠静态分析难以取得动态生成代码。一种可行的解决方法是通过动态运行目标程序取得动态生成代码,再对其进行静态分析。然而,动态运行目标程序只能覆盖有限的执行路径,会遗漏其他执行路径中的动态生成代码。针对这一问题,基于动态插桩实现了一个反事实执行方法。该方法通过修改JavaScript引擎,在其语法解析阶段动态插入反事实执行体,使条件不成立的分支路径和当前执行路径均能够得到执行。通过该插桩方式,即使嵌套调用eval等方法,也能在其动态生成代码中完成插桩。同时,还实现了一种按需undo方法,以消除反事实执行体中赋值操作带来的影响,且能够避免冗余操作。实验结果表明,实现的方法能够有效地扩大动态分析中执行路径的覆盖面。     

A dynamic block-level execution profiler

Most performance enhancing mechanisms in current processors, such as branch predictors or prefetchers, rely on program characteristics monitored at the granularity of single instructions. However, many of these characteristics can be obtained at the basic block-level instead. The coarser granularity allows a larger portion of the code to be examined, enabling a more accurate profiling and a detailed analysis of the different types of instructions executed within a block. Therefore, block-level analysis can be advantageous for performance enhancing mechanisms, as it allows us to look at how the instructions influence each other, and thus detect complex behavior patterns.In this paper, we present the Dynamic Block-Level Execution Profiler (DBLEP), a basic block level online mechanism that profiles micro-architectural bottlenecks, such as delinquent memory loads, hard-to-predict branches and contention for functional units. DBLEP operates at the basic block level and provides information that can be used to reduce the impact of these bottlenecks. A prefetch dropping scheme and a memory controller policy were developed to use the code profiling information provided by DBLEP. By taking advantage of the high profiling accuracy, these mechanisms are able to improve the processor’s performance by up to 18.6% (5.3% on average). We show that our mechanism’s performance is comparable to mechanisms that work on single instruction granularity, using less hardware.     

Predictive Mitigation of Timing Channels - Threat Defense for Machine Codes

The security of software systems can be threatened by many internal and external threats, including data leakages due to timing channels. Even if developers manage to avoid security threats in the source code or bytecode during development and testing, new threats can arise as the compiler generates machine codes from representations at the binary code level during execution on the processor or due to operating system specifics. Current approaches either do not allow the neutralization of timing channels to be achieved comprehensively with a sufficient degree of security or require an unjustifiable amount of time and/or resources. Herein, a method is demonstrated for the protected execution of software based on a secure virtual execution environment (VEE) that combines the results from dynamic and static analyses to find timing channels through the application of code transformations. This solution complements other available techniques to prevent timing channels from being exploited. This approach helps control the appearance and neutralization of timing channels via just-in-time code modifications during all stages of program development and usage. This work demonstrates the identification of threats using timing channels as an example. The approach presented herein can be expanded to the neutralization of other types of threats.     

Mining Association Rules from Code (MARC) to support legacy software management

This paper presents a methodology for Mining Association Rules from Code (MARC), aiming at capturing program structure, facilitating system understanding and supporting software management. MARC groups program entities (paragraphs or statements) based on similarities, such as variable use, data types and procedure calls. It comprises three stages: code parsing/analysis, association rule mining and rule grouping. Code is parsed to populate a database with records and respective attributes. Association rules are then extracted from this database and subsequently processed to abstract programs into groups containing interrelated entities. Entities are then grouped together if their attributes participate to common rules. This abstraction is performed at the program level or even the paragraph level, in contrast to other approaches that work at the system level. Groups can then be visualised as collections of interrelated entities. The methodology was evaluated using real-life COBOL programs. Results showed that the methodology facilitates program comprehension by using source code only, where domain knowledge and documentation are either unavailable or unreliable.     

Combining static worst-case timing analysis and program proof

This paper describes SPATS—a new toolset for the development of safety-critical and hard real-time systems. SPATS integrates the analysis traditionally offered by program proof and static timing analysis tools through analysis of program basic-path graphs. This paper concentrates on SPATS' facilities for high-level static timing analysis and analysis of worst-case stack usage. The integration of timing analysis and program proof allows timing analysis to be performed where worst-case execution time (WCET) depends on a program's input data, and allows timing annotations to be formally verified. The approach is developed and illustrated with a worked example. The implementation and experimental application of SPATS to realistic industrial case-studies are also described. We conclude that SPATS offers a novel new approach to static timing analysis, offers several new analyses not seen in previous systems, and can be implemented in a useful and efficient toolset.This work was completed while Rod Chapman was with the Dependable Computing Systems Centre at the University of York.     

Compilation techniques for parallel systems

Over the past two decades tremendous progress has been made in both the design of parallel architectures and the compilers needed for exploiting parallelism on such architectures. In this paper we summarize the advances in compilation techniques for uncovering and effectively exploiting parallelism at various levels of granularity. We begin by describing the program analysis techniques through which parallelism is detected and expressed in form of a program representation. Next compilation techniques for scheduling instruction level parallelism (ILP) are discussed along with the relationship between the nature of compiler support and type of processor architecture. Compilation techniques for exploiting loop and task level parallelism on shared-memory multiprocessors (SMPs) are summarized. Locality optimizations that must be used in conjunction with parallelization techniques for achieving high performance on machines with complex memory hierarchies are also discussed. Finally we provide an overview of compilation techniques for distributed memory machines that must perform partitioning of both code and data for parallel execution. Communication optimization and code generation issues that are unique to such compilers are also briefly discussed.     

Static scheduling for barrier MIMD architectures

In a SIMD or VLIW machine, conceptual synchronizations are accomplished by using a static code schedule that does not require run-time synchronization. The lack of run-time synchronization overhead makes these machines very effective for fine-grain parallelism, but they cannot execute parallel code structures as general as those executed by MIMD architectures, and this limits their utility.In this paper we present a timing analysis that allows a compiler for a MIMD machine to eliminate a large fraction of the run-time synchronization by making efficient use of static code scheduling. Although these techniques can be adapted to be applied to most MIMD machines, this paper centers on the analysis and scheduling for barrier MIMD machines. Barrier MIMDs are asynchronous multiple instruction stream/multiple data stream architectures capable of parallel execution of variable execution-time instructions and arbitrary control flow (e.g., while loops and calls). However, they also incorporate a special hardware barrier synchronization mechanism that facilitates static scheduling by providing a mechanism which the compiler can use to enforce precise timing constraints. In other words, the compiler tracks relative timing between processors and uses static code scheduling until the timing imprecision becomes too large, at which point the compiler simply inserts a barrier to reduce that timing imprecision to zero (or a small constant).This paper describes new scheduling and barrier placement algorithms for barrier MIMDs that are based loosely on the list scheduling approach employed for VLIWs [Ellis 1985]. In addition, the experimental results from scheduling thousands of synthetic benchmark programs for a parameterized barrier MIMD machine are presented.     

Software model checking without source code

We present a framework, called air, for verifying safety properties of assembly language programs via software model checking. air extends the applicability of predicate abstraction and counterexample guided abstraction refinement to the automated verification of low-level software. By working at the assembly level, air allows verification of programs for which source code is unavailable—such as legacy and COTS software—and programs that use features—such as pointers, structures, and object-orientation—that are problematic for source-level software verification tools. In addition, air makes no assumptions about the underlying compiler technology. We have implemented a prototype of air and present encouraging results on several non-trivial examples.     

A DSL for modeling application-specific functionalities of business applications

Models have been widely used in the information system development process. Models are not just means for system analysis and documentation. They may be also transformed into system implementation, primarily program code. Generated program code of screen forms and transaction programs mainly implements generic functionalities that can be expressed by simple retrieval, insertion, update, or deletion operations over database records. Besides the program code of generic functionalities, each application usually includes program code for specific business logic that represents application-specific functionalities, which may include complex calculations, as well as a series of database operations. There is a lack of domain-specific and tool-supported techniques for specification of such application-specific functionalities at the level of platform-independent models (PIMs). In this paper, we propose an approach and a domain-specific language (DSL), named IIS^⁎CFuncLang, aimed at enabling a complete specification of application-specific functionalities at the PIM level. We have developed algorithms for transformation of IIS^⁎CFuncLang specifications into executable program code, such as PL/SQL program code. In order to support specification of application-specific functionalities using IIS^⁎CFuncLang, we have also developed appropriate tree-based and textual editors. The language, editors, and the transformations are embedded into a Model-Driven Software Development tool, named Integrated Information Systems CASE (IIS^⁎Case). IIS^⁎Case supports platform-independent design and automated prototyping of information systems, which allows us to verify and test our approach in practice.