《高级后端代码优化》——前沿编译技术解析

需积分: 10 151 浏览量更新于2024-07-21 收藏 5.28MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

Introduction xv

The practice is not very attractive. It is not rare to have a code transformation

implemented at frontend optimizing for a backend objective: for instance, cache

optimization at a loop nest can be done at frontend because the high-level program

structure (loops) has yet to be destroyed. Inversely, it is possible to have a high-level

analysis implemented at assembly or as binary code, such as data dependence and

interprocedural analysis. Compilers are very complex pieces of software that are

maintained for a long period of time, and the frontiers between high and low levels

can sometimes be difﬁcult to deﬁne formally. Nevertheless, the notion of frontend

and backend optimization is not fundamental. It is a technical decomposition of

compilation mainly for easing the development of the compiler software.

We are interested in backend code optimization mainly due to a personal

inclination towards hardware/software frontiers. Even this barrier starts to leak with

the development of reconﬁgurable and programmable architectures, where compilers

are asked to generate a part of the instruction set. In this book, we have tried to be as

abstract as possible in order to have general results applicable to wide processor

families (superscalar, VLIW, Explicitly Parallel Instruction Computing (EPIC), etc.).

When the micro-architectural features are too complex to model, we provide

technical solutions for practical situations.

I.1. Inside this book

This book is the outcome of a long period of research activity in academia and

industry. We write fundamental results in terms of lemmas, deﬁnitions, theorems and

corollaries, and in terms of algorithms and heuristics. We also provide an appendix

that contains some experimental results. For future reproducibility, we have released

most of our experimental results in terms of documented software and numerical data.

Although we did not include all of our mature research results in this book, we

think that we have succeeded in summarizing most of our efforts on backend code

optimization. In the following, we brieﬂy describe the organization of this book.

Section I.3, on basic recalls on instruction-level parallelism (ILP) in processor

architectures, starts with explaining the difference between superscalar and VLIW

architectures. ILP processor architectures are widely covered in other books, so this

section will be a brief summary.

Part 1: introduction to optimizing compilation

Chapter 1 is entitled “On the Decidability of Phase Ordering in Optimizing

Compilation”: we have had long and sometimes painful experiences with code

optimization of large and complex applications. The obtained speedups, in practice,

www.it-ebooks.info

xvi Advanced Backend Code Optimization

are not always satisfactory when using usual compilation ﬂags. When iterative

compilation started to become a new trend in our ﬁeld, we asked ourselves whether

such methodologies may outperform static compilation: static compilation is

designed for all possible data inputs, while iterative compilation chooses a data input

and therefore, it seems to simplify the problem. We studied the decidability of phase

ordering from the theoretical point of view in the context of iterative

compilation.

Part 2: instruction scheduling

This part of the book covers instruction scheduling in ILP. The chapters of this part

(Chapters 2–6) use the same notations, which are different from the notations used

in the following part. The reason why the formal notations in this part are slightly

different from the notations of Part 3 is that the instruction scheduling problems are

strongly related to the theory of machine scheduling. In this area of research, there are

some common and usual notations that we use in this part but not in Part 3.

Chapter 2, entitled “Instruction Scheduling Problems and Overview”, is a

reminder of scheduling problems for ILP, and their relationship with register

optimization. Special attention is given to cyclic scheduling problems because they

are of importance for optimizing the performance of loops.

Chapter 3, entitled “Applications of Machine Scheduling to Instruction

Scheduling”, is an interesting chapter that discusses the relationship between

theoretical scheduling problems and practical instruction scheduling problems.

Indeed, although instruction scheduling is a mature discipline, its relationship with

the ﬁeld of machine scheduling is often ignored. In this chapter, we show how the

theory of machine scheduling can be applied to instruction scheduling.

Chapter 4, entitled “Instruction Scheduling before Register Allocation”, provides

a formal method and a practical implementation for cyclic instruction scheduling

under resource constraints. The presented scheduling method is still sensitive to

Chapter 5, entitled “Instruction Scheduling after Register Allocation”, presents a

postpass register allocation method. After an instruction scheduling, register allocation

may introduce spill code and may require making some instruction rescheduling. This

chapter presents a faster technique suitable for just-in-time compilation.

Chapter 6, entitled “Dealing in Practice with Memory Hierarchy Effects and

Instruction-Level Parallelism”, studies the complex micro-architectural features from

www.it-ebooks.info

Introduction xvii

a practical point of view. First, we highlight the problem with memory

disambiguation mechanisms in out-of-order processors. This problem exists in most

of the micro-architectures and creates false dependences between independent

instructions during execution, limiting ILP. Second, we show how to use insert

instructions for data preloading and prefetching in the context of embedded VLIW.

Part 3: register optimization

This part of the book discusses register pressure in ILP, which can be read

independently from Part 2. In order to understand all the formal information and

notations of this part, we advise the readers not to neglect the formal model and

notations presented in section 7.1.

Chapter 7, entitled “The Register Need of a Fixed Instruction Schedule”, deals with

coexist, some notions are similarly named but do not have the same mathematical

deﬁnition. Typically, the notion of the register need may have distinct signiﬁcations.

We formally deﬁne this quantity in two contexts: the context of acyclic scheduling

(basic block and superblock) and the context of cyclic scheduling (software pipelining

of a loop). While the acyclic register need is a well-understood notion, we provide new

formal knowledge on the register need in cyclic scheduling.

Chapter 8 is entitled “The Register Saturation”: our approach here for tackling

allocation. Indeed, we study the problem of register need maximization, not

minimization. We explain the differences between the two problems and provide an

efﬁcient greedy heuristic. Register maximization allows us to decouple register

constraints from instruction scheduling: if we detect that the maximal register need is

below the processor capacity, we can neglect register constraints.

Chapter 9, entitled “Spill Code Reduction”, mainly discusses schedule

independent register allocation (SIRA) framework: this approach handles register

constraints before instruction scheduling by adding edges to the data dependence

graph (DDG). It guarantees the absence of spilling for all valid instruction schedules.

This approach takes care not to alter the ILP if possible. We present the theoretical

graph approach, called SIRA, and we show its applications in multiple contexts:

multiple register ﬁle architectures, rotating register ﬁles and buffers. We present

SIRALINA, an efﬁcient and effective heuristic that allows satisfactory spill code

reduction in practice while saving the ILP.

Chapter 10, entitled “Exploiting the Register Access Delays before Instruction

Scheduling”, discusses a certain problem and provides a solution: until now, the

www.it-ebooks.info

xviii Advanced Backend Code Optimization

literature has not formally tackled one of the real problems that arises when register

optimization is handled before instruction scheduling. Indeed, when the processor

has explicit register access delays (such as in VLIW, explicitly parallel instruction

computing (EPIC) and digital signal processing (DSP)), bounding or minimizing the

theory when resource constraints are considered afterward. The nature of this

problem and a solution in the context of SIRA are the main subject of this chapter.

Chapter 11 is entitled “Loop Unrolling Degree Minimization for Periodic

between the number of allocated registers in a loop, the critical circuit of the DDG

and the loop unrolling factor. For the purpose of code size compaction, we show how

can we minimize the unrolling degree with the guarantee of neither generating spill

code nor altering the ILP. The problem is based on the minimization of a least

common multiple, using the set of remaining registers.

Part 4: Epilog

Chapter 12, entitled “Statistical Performance Analysis: The Speedup-Test

Protocol”, tends to improve the reproducibility of the experimental results in our

community. We tackle the problem of code performance variation in practical

observations. We describe the protocol called the Speedup-Test; it uses well-known

statistical tests to declare, with a proved risk level, whether an average or a median

execution time has been improved or not. We clearly explain what the hypotheses

that must be checked for each statistical test are.

Finally, the Conclusion describes some open problems in optimizing compilation

in general. These open problems are known but do not yet have satisfactory solutions

in the literature. Here, we conclude with a general summary.

I.2. Other contributors

This book is the outcome of long-term fundamental, experimental and technical

research using graph theory, scheduling theory, linear programming, complexity

theory, compilation, etc. We had great pleasure and honor collaborating with many

talented people with high-quality backgrounds in computer science, computer

engineering and mathematics. Table I.1 provides a list of collaborators for each

chapter, whom we would like to thank very much.

www.it-ebooks.info

Introduction xix

Chapter Contributor Nature of the contribution

Chapter 1 Pr Denis BARTHOU Formal proofs and modeling of phase ordering

problems

Chapter 6 Dr Christophe LEMIET PhD work, implementation, experiments,

performance analysis of memory disambiguation

mechanisms.

Dr Samir AMMENOUCHE PhD work, implementation, experiments,

performance analysis of instruction scheduling

under cache effects on VLIW processors.

Pr William JALBY PhD direction

Chapter 9 Dr Christine EISENBEIS Initial intuition and formal description of the

SIRA framework, PhD direction

Dr Karine DESCHINKEL SIRALINA heuristic proposal, software

implementation

Dr Sébastien BRIAIS Software implementation of SIRALINA,

experiments

Mr Frederic BRAULT Integration of SIRA framework inside an

industrial compiler for VLIW processors,

experiments and performance analysis

Chapter 10 Dr Karine DESCHINKEL Iterative method for eliminating non-positive

circuits in data dependence graphs

Dr Sébastien BRIAIS Formal proofs and algorithms, implementation

and experiments

Chapter 11 Dr Mounira BACHIR PhD work, formal proofs, implementation and

experiments

Dr Albert COHEN PhD direction

Dr David GREGG Contribution on algorithms

Mr Frederic BRAULT Experimental study with an industrial compiler for

VLIW processors

Chapter 12 Dr Julien WORMS Parametric statistics, statistical testing

Dr Sébastien BRIAIS Speedup-Test implementation

Dr Abdelhaﬁd MAZOUZ Experimental study of program performance

variability

Table I.1. Other contributors to the results presented in this book

I.3. Basics on instruction-level parallelism processor architectures

Today’s microprocessors are the powerful descendants of the Von Neumann

computer [SIL 99]. Although various computer architectures have been considerably

changed and rapidly developed over the last 20 years, the basic principles in Von

Neumann computational model are still the foundation of today’s most widely used

computer architectures as well as high-level programming languages. The Von

Neumann computational model was proposed by Von Neumann and his colleagues in

www.it-ebooks.info

剩余384页未读，继续阅读

vanridin

粉丝: 108
资源: 1188

《高级后端代码优化》——前沿编译技术解析

optimization Code

ImportError: cannot import name 'tensorflow_backend' from 'keras.backend'

postgresql pg_cancel_backend和pg_terminate_backend的区别

Backend API是什么

Backend TkAgg is interactive backend. Turning interactive mode on.

matplotlib库的backend在哪设置

from keras.backend.tensorflow_backend import set_session ModuleNotFoundError: No module named 'keras.backend.tensorflow_backend'; 'keras.backend' is not a package

nvidia backend安装失败

AttributeError: module 'keras.backend' has no attribute 'tensorflow_backend'

import _ext as _backend

matplotlib的backend是做什么用的

nginx配置后端服务高可用 backend

ModuleNotFoundError: No module named 'keras.backend.tensorflow_backend'; 'keras.backend' is not a package

osrm-backend

No module named 'lstm_backend'

Python Scientific没有"Matplotlib backend"选项

bprophet中的stan_backend怎样设置参数

no module named 'keras.backend.tensorflow_backend'; 'keras.backend' is not a package

最新资源