Applications of Compiler
Technology
Compiler design is not only about compilers, and many people use the
technology learned by studying compilers in school, yet have never, strictly
speaking, written (even part of) a compiler for a major programming language.
Compiler technology has other important uses as well. Additionally, compiler
design impacts several other areas of computer science. In this section, we
review the most important interactions and applications of the technology.
1 Implementation
of High-Level Programming
Languages
A high-level programming language defines a programming abstraction: the
programmer expresses an algorithm using the language, and the compiler must
translate that program to the target language. Generally, higher-level
programming languages are easier to program in, but are less efficient, that
is, the target programs run more slowly. Programmers using a low-level language
have more control over a computation and can, in principle, produce more
efficient code. Unfortunately, lower-level programs are harder to write and —
worse still — less portable, more prone to errors, and harder to maintain.
Optimizing compilers include techniques to improve the performance of
generated code, thus offsetting the inefficiency introduced by high-level
abstractions.
Example 1.2: The register keyword in the C programming language is an
early example of the interaction between compiler technology and language
evo-lution. When the C language was created in the mid 1970s, it was considered
necessary to let a programmer control which program variables reside in
regis-ters. This control became unnecessary as effective register-allocation
techniques were developed, and most modern programs no longer use this language
feature.
In fact, programs that use the register
keyword may lose efficiency, because programmers often are not the best judge
of very low-level matters like register allocation. The optimal choice of
register allocation depends greatly on the specifics of a machine architecture.
Hardwiring low-level resource-management decisions like register allocation may
in fact hurt performance, especially if the program is run on machines other
than the one for which it was written. •
The many shifts in the popular choice of programming languages have been
in the direction of increased levels of abstraction. C was the predominant
systems programming language of the 80's; many of the new projects started in
the 90's chose C + + ; Java, introduced in 1995, gained popularity quickly in
the late 90's. The new programming-language features introduced in each round
spurred new research in compiler optimization. In the following, we give an
overview on the main language features that have stimulated significant
advances in compiler technology.
Practically all common programming languages, including C, Fortran and
Cobol, support user-defined aggregate data types, such as arrays and
structures, and high-level control flow, such as loops and procedure
invocations. If we just take each high-level construct or data-access operation
and translate it directly to machine code, the result would be very
inefficient. A body of compiler optimizations, known as data-flow optimizations, has been developed to analyze the flow of
data through the program and removes redundancies across these constructs. They
are effective in generating code that resembles code written by a skilled
programmer at a lower level.
Object orientation was first introduced in Simula in 1967, and has been
incorporated in languages such as Smalltalk, C + + , C # , and Java. The key
ideas behind object orientation are
Data abstraction and
Inheritance of properties,
both of which have been found to make programs more modular and easier
to maintain. Object-oriented programs are different from those written in many
other languages, in that they consist of many more, but smaller, procedures
(called methods in object-oriented
terms). Thus, compiler optimizations must be able to perform well across the
procedural boundaries of the source program. Procedure inlining, which is the
replacement of a procedure call by the body of the procedure, is particularly
useful here. Optimizations to speed up virtual method dispatches have also been
developed.
Java has many features that make programming easier, many of which have
been introduced previously in other languages. The Java language is type-safe;
that is, an object cannot be used as an object of an unrelated type. All array
accesses are checked to ensure that they lie within the bounds of the array.
Java has no pointers and does not allow pointer arithmetic. It has a built-in
garbage-collection facility that automatically frees the memory of variables
that are no longer in use. While all these features make programming easier,
they incur a run-time overhead. Compiler optimizations have been developed to
reduce the overhead, for example, by eliminating unnecessary range checks and
by allocating objects that are not accessible beyond a procedure on the stack
instead of the heap. Effective algorithms also have been developed to minimize
the overhead of garbage collection.
In addition, Java is designed to support portable and mobile code.
Programs are distributed as Java bytecode, which must either be interpreted or
compiled into native code dynamically, that is, at run time. Dynamic
compilation has also been studied in other contexts, where information is
extracted dynamically at run time and used to produce better-optimized code. In
dynamic optimization, it is important to minimize the compilation time as it is
part of the execution overhead. A common technique used is to only compile and
optimize those parts of the program that will be frequently executed.
2. Optimizations for Computer
Architectures
The rapid evolution of computer architectures has also led to an
insatiable demand for new compiler technology. Almost all high-performance
systems take advantage of the same two basic techniques: parallelism and memory
hierarchies. Parallelism can be found at several levels: at the instruction level, where multiple
operations are executed simultaneously and at the processor level, where
different threads of the same application are run on different processors.
Memory hierarchies are a response to the basic limitation that we can build
very fast storage or very large storage, but not storage that is both fast and
large.
Parallelism
All modern microprocessors exploit instruction-level parallelism.
However, this parallelism can be hidden from the programmer. Programs are
written as if all instructions were executed in sequence; the hardware
dynamically checks for dependencies in the sequential instruction stream and
issues them in parallel when possible. In some cases, the machine includes a
hardware scheduler that can change the instruction ordering to increase the
parallelism in the program. Whether the hardware reorders the instructions or
not, compilers can rearrange the instructions to make instruction-level
parallelism more effective.
Instruction-level parallelism can also appear explicitly in the
instruction set. VLIW (Very Long Instruction Word) machines have instructions
that can issue multiple operations in parallel. The Intel IA64 is a well-known
example of such an architecture. All high-performance, general-purpose
microprocessors also include instructions that can operate on a vector of data
at the same time. Compiler techniques have been developed to generate code
automatically for such machines from sequential programs.
Multiprocessors have also become prevalent; even personal computers
of-ten have multiple processors. Programmers can write multithreaded code for
multiprocessors, or parallel code can be automatically generated by a com-piler
from conventional sequential programs. Such a compiler hides from the
programmers the details of finding parallelism in a program, distributing the
computation across the machine, and minimizing synchronization and
com-munication among the processors. Many scientific-computing and engineering
applications are computation-intensive and can benefit greatly from parallel
processing. Parallelization techniques have been developed to translate
auto-matically sequential scientific programs into multiprocessor code.
M e m o r y Hierarchies
A memory hierarchy consists of several levels of storage with different
speeds and sizes, with the level closest to the processor being the fastest but
small-est. The average memory-access time of a program is reduced if most of
its accesses are satisfied by the faster levels of the hierarchy. Both
parallelism and the existence of a memory hierarchy improve the potential
performance of a machine, but they must be harnessed effectively by the
compiler to deliver real performance on an application.
Memory hierarchies are found in all machines. A processor usually has a
small number of registers consisting of hundreds of bytes, several levels of
caches containing kilobytes to megabytes, physical memory containing mega-bytes
to gigabytes, and finally secondary storage that contains gigabytes and beyond.
Correspondingly, the speed of accesses between adjacent levels of the hierarchy
can differ by two or three orders of magnitude. The performance of a system is
often limited not by the speed of the processor but by the performance of the
memory subsystem. While compilers traditionally focus on optimizing the
processor execution, more emphasis is now placed on making the memory hierarchy
more effective.
Using registers effectively is probably the single most important
problem in optimizing a program. Unlike registers that have to be managed
explicitly in software, caches and physical memories are hidden from the
instruction set and are managed by hardware. It has been found that
cache-management policies implemented by hardware are not effective in some
cases, especially in scientific code that has large data structures (arrays,
typically). It is possible to improve the effectiveness of the memory hierarchy
by changing the layout of the data, or changing the order of instructions accessing
the data. We can also change the layout of code to improve the effectiveness of
instruction caches.
3. Design of New Computer
Architectures
In the early days of computer architecture design, compilers were
developed after the machines were built. That has changed. Since programming in
high-level languages is the norm, the performance of a computer system is
determined not by its raw speed but also by how well compilers can exploit its
features. Thus, in modern computer architecture development, compilers are
developed in the processor-design stage, and compiled code, running on
simulators, is used to evaluate the proposed architectural features.
R I S C
One of the best known examples of how compilers influenced the design of
computer architecture was the invention of the RISC (Reduced Instruction-Set
Computer) architecture. Prior to this invention, the trend was to develop
progressively complex instruction sets intended to make assembly programming
easier; these architectures were known as CISC (Complex Instruction-Set
Computer). For example, CISC instruction sets include complex
memory-addressing modes to support data-structure accesses and
procedure-invocation instructions that save registers and pass parameters on
the stack.
Compiler optimizations often can reduce these instructions to a small
number of simpler operations by eliminating the redundancies across complex
instructions. Thus, it is desirable to build simple instruction sets;
compilers can use them effectively and the hardware is much easier to optimize.
Most general-purpose processor architectures, including PowerPC, SPARC,
MIPS, Alpha, and PA-RISC, are based on the RISC concept. Although the x86
architecture—the most popular microprocessor—has a CISC instruction set, many
of the ideas developed for RISC machines are used in the implementation of the
processor itself. Moreover, the most effective way to use a high-performance
x86 machine is to use just its simple instructions.
Specialized Architectures
Over the last three decades, many architectural concepts have been
proposed. They include data flow machines, vector machines, VLIW (Very Long
Instruction Word) machines, SIMD (Single Instruction, Multiple Data) arrays of
processors, systolic arrays, multiprocessors with shared memory, and
multiprocessors with distributed memory. The development of each of these
architectural concepts was accompanied by the research and development of
corresponding compiler technology.
Some of these ideas have made their way into the designs of embedded
machines. Since entire systems can fit on a single chip, processors need no
longer be prepackaged commodity units, but can be tailored to achieve better
cost-effectiveness for a particular application. Thus, in contrast to
general-purpose processors, where economies of scale have led computer
architectures to converge, application-specific processors exhibit a diversity
of computer architectures. Compiler technology is needed not only to support
programming for these architectures, but also to evaluate proposed architectural
designs.
4. Program Translations
While we normally think of compiling as a translation from a high-level
language to the machine level, the same technology can be applied to translate
between different kinds of languages. The following are some of the important
applications of program-translation techniques.
Binary Translation
Compiler technology can be used to translate the binary code for one
machine to that of another, allowing a machine to run programs originally
compiled for another instruction set. Binary translation technology has been
used by various computer companies to increase the availability of software for
their machines. In particular, because of the domination of the x86
personal-computer mar-ket, most software titles are available as x86 code.
Binary translators have been developed to convert x86 code into both Alpha and
Sparc code. Binary translation was also used by Transmeta Inc. in their
implementation of the x86 instruction set. Instead of executing the complex x86
instruction set directly in hardware, the Transmeta Crusoe processor is a VLIW
processor that relies on binary translation to convert x86 code into native
VLIW code.
Binary translation can also be used to provide backward compatibility.
When the processor in the Apple Macintosh was changed from the Motorola MC
68040 to the PowerPC in 1994, binary translation was used to allow PowerPC
processors run legacy MC 68040 code.
Hardware Synthesis
Not only is most software written in high-level languages; even hardware
de-signs are mostly described in high-level hardware description languages like
Verilog and VHDL (Very high-speed integrated circuit Hardware Description
Language). Hardware designs are typically described at the register trans-fer
level (RTL), where variables represent registers and expressions represent
combinational logic. Hardware-synthesis tools translate RTL descriptions
auto-matically into gates, which are then mapped to transistors and eventually
to a physical layout. Unlike compilers for programming languages, these tools
often take hours optimizing the circuit. Techniques to translate designs at
higher levels, such as the behavior or functional level, also exist.
Database Query
Interpreters
Besides specifying software and hardware, languages are useful in many
other applications. For example, query languages, especially SQL (Structured
Query Language), are used to search databases. Database queries consist of
predicates containing relational and boolean operators. They can be interpreted
or com-piled into commands to search a database for records satisfying that
predicate.
Compiled Simulation
Simulation is a general technique used in many scientific and
engineering disci-plines to understand a phenomenon or to validate a design.
Inputs to a simula-tor usually include the description of the design and
specific input parameters for that particular simulation run. Simulations can
be very expensive. We typi-cally need to simulate many possible design
alternatives on many different input sets, and each experiment may take days to
complete on a high-performance machine. Instead of writing a simulator that
interprets the design, it is faster to compile the design to produce machine
code that simulates that particular design natively. Compiled simulation can
run orders of magnitude faster than an interpreter-based approach. Compiled
simulation is used in many state-of-the-art tools that simulate designs written
in Verilog or VHDL.
5. Software Productivity Tools
Programs are arguably the most complicated engineering artifacts ever
pro-duced; they consist of many many details, every one of which must be
correct before the program will work completely. As a result, errors are
rampant in programs; errors may crash a system, produce wrong results, render a
system vulnerable to security attacks, or even lead to catastrophic failures in
critical systems. Testing is the primary technique for locating errors in
programs.
An interesting and promising complementary approach is to use data-flow
analysis to locate errors statically (that is, before the program is run).
Data-flow analysis can find errors along all the possible execution paths, and
not just those exercised by the input data sets, as in the case of program
testing. Many of the data-flow-analysis techniques, originally developed for
compiler optimizations, can be used to create tools that assist programmers in
their software engineering tasks.
The problem of finding all program errors is undecidable. A data-flow
analy-sis may be designed to warn the programmers of all possible statements
violating a particular category of errors. But if most of these warnings are
false alarms, users will not use the tool. Thus, practical error detectors are
often neither sound nor complete. That is, they may not find all the errors in
the program, and not all errors reported are guaranteed to be real errors.
Nonetheless, var-ious static analyses have been developed and shown to be
effective in finding errors, such as dereferencing null or freed pointers, in
real programs. The fact that error detectors may be unsound makes them
significantly different from compiler optimizations. Optimizers must be
conservative and cannot alter the semantics of the program under any
circumstances.
In the balance of this section, we shall mention several ways in which
pro-gram analysis, building upon techniques originally developed to optimize
code in compilers, have improved software productivity. Of special importance
are techniques that detect statically when a program might have a security
vulner-ability.
Type Checking
Type checking is an effective and well-established technique to catch
inconsis-tencies in programs. It can be used to catch errors, for example,
where an operation is applied to the wrong type of object, or if parameters
passed to a procedure do not match the signature of the procedure. Program
analysis can go beyond finding type errors by analyzing the flow of data
through a program. For example, if a pointer is assigned n u l l and then
immediately dereferenced, the program is clearly in error.
The same technology can be used to catch a variety of security holes, in
which an attacker supplies a string or other data that is used carelessly by
the program. A user-supplied string can be labeled with a type
"dangerous." If this string is not checked for proper format, then it
remains "dangerous," and if a string of this type is able to influence
the control-flow of the code at some point in the program, then there is a
potential security flaw.
Bounds Checking
It is easier to make mistakes when programming in a lower-level language
than a higher-level one. For example, many security breaches in systems are
caused by buffer overflows in programs written in C. Because C does not have
array-bounds checks, it is up to the user to ensure that the arrays are not
accessed out of bounds. Failing to check that the data supplied by the user can
overflow a buffer, the program may be tricked into storing user data outside of
the buffer. An attacker can manipulate the input data that causes the program
to misbehave and compromise the security of the system. Techniques have been
developed to find buffer overflows in programs, but with limited success.
Had the program been written in a safe language that includes automatic
range checking, this problem would not have occurred. The same data-flow
analysis that is used to eliminate redundant range checks can also be used to
locate buffer overflows. The major difference, however, is that failing to
eliminate a range check would only result in a small run-time cost, while
failing to identify a potential buffer overflow may compromise the security of
the system. Thus, while it is adequate to use simple techniques to optimize
range checks, so-phisticated analyses, such as tracking the values of pointers
across procedures, are needed to get high-quality results in error detection
tools.
Memory – Management Tools
Garbage collection is another excellent example of the tradeoff between
efficiency and a combination of ease of programming and software reliability.
Au-tomatic memory management obliterates all memorymanagement errors (e.g.,
"memory leaks"), which are a major source of problems in C and C + +
pro-grams. Various tools have been developed to help programmers find memory
management errors. For example, Purify is a widely used tool that dynamically
catches memory management errors as they occur. Tools that help identify some
of these problems statically have also been developed.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.