• PDF / 237,754 Bytes
• 17 Pages / 439.363 x 666.131 pts Page_size
• 110 Downloads / 197 Views

DOWNLOAD

REPORT

---

Abstract. In high-end compilers such as Open64, GCC or LLVM, the Static Single Assignment (SSA) form is a structural part of the targetindependent program representation that supports most of the code optimizations. However, aggressive compilation also requires that optimizations that are more effective with the SSA form be applied to the target-specific program representations operated by the code generator, that is, the set of compiler phases after and including instruction selection. While using the SSA form in the code generator has definite advantages, the SSA form does not apply to all the code generator program representations, and is not suited for all optimizations. We discuss some of the issues of inserting the SSA form in a code generator, specifically: what are the challenges of maintaining the SSA form on a program representation based on machine instructions; how the SSA form may be used in the if-conversion optimizations; why the SSA form does not seem to benefit instruction scheduling; and what is the state-of-the-art in SSA form destruction on machine code. Keywords: SSA Form, Code Generation, If-Conversion, Instruction Scheduling.

1

Introduction

In a compiler for imperative languages such as C, C++, or FORTRAN, the code generator covers the set of code transformations and optimizations that operate on a program representation close to the target machine ISA, and produce an assembly source or relocatable file with debugging information as result. The main duties of code generation are: lowering the program intermediate representation to the target machine instructions and calling conventions; laying out data objects in sections and composing the stack frames; allocating variable live ranges to architectural registers; scheduling instructions to exploit microarchitecture; and producing assembly source or object code. Historically, the 1986 edition of the “Compilers Principles, Techniques, and Tools” Dragon Book by Aho et al. lists the tasks of code generation as: – – – –

Instruction selection and lowering of calling conventions. Control-flow (dominators, loops) and data-flow (variable liveness) analyses. Register allocation and stack frame building. Peephole optimizations.

A. Cohen (Ed.): CC 2014, LNCS 8409, pp. 1–17, 2014. c Springer-Verlag Berlin Heidelberg 2014 

2

B.D. de Dinechin

Ten years later, the 1997 textbook “Advanced Compiler Design & Implementation” by Muchnich extends code generation with the following tasks: – Loop unrolling and basic block replication. – Instruction scheduling and software pipelining. – Branch optimizations and basic block alignment. In current releases of high-end compilers such as Open64 or GCC, code generation techniques have significantly evolved, as they are mainly responsible for exploiting the performance-oriented features of architectures and microarchitectures. In these compilers, code generator optimizations include: – – – – – –

If-conversion using SELECT, conditional move, or predicated, instructions. Use of specialized addressing modes such as auto-modified