Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » High Performance Computing » Optimizing Compiler Tour

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • HPC Open Edu Cup

    This collection is included inLens: High Performance Computing Open Education Cup 2008-2009
    By: Ken Kennedy Institute for Information Technology

    Click the "HPC Open Edu Cup" link to see all content they endorse.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • NSF Partnership display tagshide tags

    This collection is included inLens: NSF Partnership in Signal Processing
    By: Sidney Burrus

    Click the "NSF Partnership" link to see all content affiliated with them.

    Click the tag icon tag icon to display tags associated with this content.

  • Featured Content

    This collection is included inLens: Connexions Featured Content
    By: Connexions

    Comments:

    "The purpose of Chuck Severence's book, High Performance Computing has always been to teach new programmers and scientists about the basics of High Performance Computing. This book is for learners […]"

    Click the "Featured Content" link to see all content affiliated with them.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

  • eScience, eResearch and Computational Problem Solving

    This collection is included inLens: eScience, eResearch and Computational Problem Solving
    By: Jan E. Odegard

    Click the "eScience, eResearch and Computational Problem Solving" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Optimizing Compiler Tour

Module by: Charles Severance, Kevin Dowd. E-mail the authors

We will start by taking a walk through an optimizing compiler to see one at work. We think it’s interesting, and if you can empathize with the compiler, you will be a better programmer; you will know what the compiler wants from you, and what it can do on its own.

Compilation Process

Figure 1
Basic compiler processes
This figure is a flowchart showing movement from numerous lines of code to numerous boxes. From the beginning is a group of code, the first line showing A=B*C+5, and the second line D=B*C. From the bottom of this group of code is a line pointing to a box labeled Lexical Analysis. Below this is a line pointing to a line of code, A=B*C+5. The A is labeled variable, the * is labeled Operator, and the 5 is labeled constant. Below this line of code is an arrow pointing down at a box labeled Parse. Below this box is a grouping of code. The first line reads, T1:=B*C, the second line reads, A:=T1+5, and the third line reads D:=B*C. Pointing towards the upper-right is an arrow that points at a box labeled Optimization.

The compilation process is typically broken down into a number of identifiable steps, as shown in Figure 1. While not all compilers are implemented in exactly this way, it helps to understand the different functions a compiler must perform:

  1. A precompiler or preprocessor phase is where some simple textual manipulation of the source code is performed. The preprocessing step can be processing of include files and making simple string substitutions throughout the code.
  2. The lexical analysis phase is where the incoming source statements are decomposed into tokens such as variables, constants, comments, or language elements.
  3. The parsing phase is where the input is checked for syntax, and the compiler translates the incoming program into an intermediate language that is ready for optimization.
  4. One or more optimization passes are performed on the intermediate language.
  5. An object code generator translates the intermediate language into assembly code, taking into consideration the particular architectural details of the processor in question.

As compilers become more and more sophisticated in order to wring the last bit of performance from the processor, some of these steps (especially the optimization and code-generation steps) become more and more blurred. In this chapter, we focus on the traditional optimizing compiler, and in later chapters we will look more closely at how modern compilers do more sophisticated optimizations.

Intermediate Language Representation

Because we are most interested in the optimization of our program, we start our discussion at the output of the parse phase of the compiler. The parse phase output is in the form of an an intermediate language (IL) that is somewhere between a high-level language and assembly language. The intermediate language expresses the same calculations that were in the original program, in a form the compiler can manipulate more easily. Furthermore, instructions that aren’t present in the source, such as address expressions for array references, become visible along with the rest of the program, making them subject to optimizations too.

How would an intermediate language look? In terms of complexity, it’s similar to assembly code but not so simple that the definitions1 and uses of variables are lost. We’ll need definition and use information to analyze the flow of data through the program. Typically, calculations are expressed as a stream of quadruples — statements with exactly one operator, (up to) two operands, and a result.2 Presuming that anything in the original source program can be recast in terms of quadruples, we have a usable intermediate language. To give you an idea of how this works, We’re going to rewrite the statement below as a series of four quadruples:

A = -B + C * D / E 
    

Taken all at once, this statement has four operators and four operands: /, *, +, and - (negate), and B, C, D, and E. This is clearly too much to fit into one quadruple. We need a form with exactly one operator and, at most, two operands per statement. The recast version that follows manages to do this, employing temporary variables to hold the intermediate results:


T1 = D / E T2 = C * T1 T3 = -B A = T3 + T2

A workable intermediate language would, of course, need some other features, like pointers. We’re going to suggest that we create our own intermediate language to investigate how optimizations work. To begin, we need to establish a few rules:

  • Instructions consist of one opcode, two operands, and a result. Depending on the instruction, the operands may be empty.
  • Assignments are of the form X := Y op Z, meaning X gets the result of op applied to Y and Z.
  • All memory references are explicit load from or store to “temporaries” tn.
  • Logical values used in branches are calculated separately from the actual branch.
  • Jumps go to absolute addresses.

If we were building a compiler, we’d need to be a little more specific. For our purposes, this will do. Consider the following bit of C code:


while (j < n) { k = k + j * 2; m = j * 2; j++; }

This loop translates into the intermediate language representation shown here:


A:: t1 := j t2 := n t3 := t1 < t2 jmp (B) t3 jmp (C) TRUE B:: t4 := k t5 := j t6 := t5 * 2 t7 := t4 + t6 k := t7 t8 := j t9 := t8 * 2 m := t9 t10 := j t11 := t10 + 1 j := t11 jmp (A) TRUE C::

Each C source line is represented by several IL statements. On many RISC processors, our IL code is so close to machine language that we could turn it directly into object code.3 Often the lowest optimization level does a literal translation from the intermediate language to machine code. When this is done, the code generally is very large and performs very poorly. Looking at it, you can see places to save a few instructions. For instance, j gets loaded into temporaries in four places; surely we can reduce that. We have to do some analysis and make some optimizations.

Basic Blocks

After generating our intermediate language, we want to cut it into basic blocks. These are code sequences that start with an instruction that either follows a branch or is itself a target for a branch. Put another way, each basic block has one entrance (at the top) and one exit (at the bottom). Figure 2 represents our IL code as a group of three basic blocks. Basic blocks make code easier to analyze. By restricting flow of control within a basic block from top to bottom and eliminating all the branches, we can be sure that if the first statement gets executed, the second one does too, and so on. Of course, the branches haven’t disappeared, but we have forced them outside the blocks in the form of the connecting arrows — the flow graph.

Figure 2
Intermediate language divided into basic blocks
This figure is comprised of three blocks containing lines of code. The first reads A : : as a title, then the first column reads t1, t2, t3, jmp. The second column reads := j, := n, := t1 less than t2, (B) t3. The second block contains two items that fit the same columns as in the first block. In the first column is jmp, and in the second, (C) TRUE. In the third block are the same columns, this time headed as B : :. The first column reads, t4, t5, t6, t7, k, t8, t9, m, t10, t11, j, jmp. The second column reads := k, := j, := t5 * 2, := t4 +t6, := t7, := j, := t8 * 2, := t9, := j, := t10 + 1, := t11, (A) TRUE. There is an arrow pointing from the first block to the second block, and another arrow pointing from the first block to the third block. There is an arrow pointing from the end of the third block to the beginning of the first block. And there is a dashed arrow pointing out from the right of the second block straight down away from the blocks.

We are now free to extract information from the blocks themselves. For instance, we can say with certainty which variables a given block uses and which variables it defines (sets the value of ). We might not be able to do that if the block contained a branch. We can also gather the same kind of information about the calculations it performs. After we have analyzed the blocks so that we know what goes in and what comes out, we can modify them to improve performance and just worry about the interaction between blocks.

Footnotes

  1. By “definitions,” we mean the assignment of values: not declarations.
  2. More generally, code can be cast as n-tuples. It depends on the level of the intermediate language.
  3. See (Reference) for some examples of machine code translated directly from intermediate language.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks