Optimizing Utilization of Memory Hierarchy
Based on Code Motion
コード移動に基づくメモリ階層利用最適化

byYasunobu Sumikawa

Submitted to the Graduate School of Science and Technology
in partial fulfillment of the requirements forthe degree of Doctor of Science

Tokyo University of Science
2015Abstract
Access speed to main memory is much slower than processor speed. In orderto reduce the number of accesses to memory, most modern processors havesome registers and cache memories that are much faster than main memory. To use such registers and cache memories eﬀectively, many researchers
have proposed several code optimization techniques that promote their utilization. However, because the gap between processor and main memory
access speed is growing, and such gap is likely to increase in the future, theimportance of solving this issue is also increasing. That is, we have to develop more sophisticated code optimization techniques for the eﬀective useof registers and cache memories.
In this thesis, we propose four new techniques for decreasing the numberof references from the processor to the cache memory, and from the cachememory to the main memory. One of these techniques is an extension of
the traditional partial redundancy elimination (PRE) that removes redundant expressions, and the other techniques are types of optimization techniques based on PRE. A brief description follows. First, we propose eﬀective
demand-driven PRE (EDDPRE) that improves analysis eﬃciency without
sacriﬁcing the eﬀectiveness of the traditional PRE. Second, we propose PREbased scalar replacement (PRESR) that removes array references that are
redundant over loop iterations. As EDDPRE and PRESR remove redundant array references by replacing them with temporary variables, thesetechniques increase the number of used registers, rather than cache/main
memory, because the data referred by arrays are stored on the main memory, whereas the data from temporary variables can be stored in registers.
Finally, we propose global load instruction aggregation (GLIA) that improves
the spatial locality of memory by making accesses to the same array continuous, so that suppressing cache misses. Furthermore, we extend GLIA
to manage multidimensional arrays that can be regarded as arrays of lower
dimensional arrays, and we call the extended GLIA multidimensional GLIA(MDGLIA). MDGLIA continuously aggregates the array references with themost similar indexes in the highest dimensions, even if they are not identical.
GLIA and MDGLIA decrease the number of cache misses, thus preventing
access to the main memory.
We implement our techniques in a COINS compiler and evaluate themiwith the standard performance evaluation corporation (SPEC) benchmark
programs. The experiment results show that EDDPRE improves analysis
eﬃciency by about 50% on average. PRESR improves execution eﬃciency
by about 2% on average. GLIA and MDGLIA decrease cache misses inmany programs.
The eﬀective utilization of registers and cache memories achieved bythese techniques result in the eﬃcient execution of object code.
Keywords: memory hierarchy, compiler, code optimization, data-ﬂow
analysis, code motion, partial redundancy elimination, scalar replacement,
cache optimizationii

Acknowledgements
To express my gratitude, I write acknowledgements in Japanese.
博士論文を執筆するにあたり，修士課程の 2 年間と博士後期課程の 3 年間の計 5 年間，多くの方々にお世話になりました．この 5 年間，思うように成果を出せずに苦しんだ時期もありましたが，とても多くの素晴らしい出会いに恵まれ，研究を行うための心構えや考え方について助言や励ましを多くの方にしていただきました．無事に博士論文を完成させることができたのは，皆様のお力添えのお蔭でございます．ここで深く感謝申し上げます．
まず修士課程からの 5 年間指導してくださった滝本宗宏先生に深く感謝致します．先生には，まだ私が数学科に所属していたときから自由に研究室やゼミに出入りして計算機科学の勉強と研究を行う環境を整えてくださり，研究での議論では毎回本質的なコメントをいただきました．また，研究を行う
ためには 1 つのことを追求するだけでなく幅広い知識を学ぶことが大事だか
らと，他大学で開催されている勉強会や研究会に私が参加できるようにご支援していただきました．その中で，非常勤講師や共同研究を行う機会にも恵まれ，専門外のことも学ぶことができ，自分に出来ることが着実に増えていることを実感することができました．院生として過ごした日々が本当に楽し
くて刺激的であったのも先生の暖かいご支援のおかげです．私も先生のように寛大で的確な助言をできる研究者になれるように，これからも励んでいきたいと思います．本当にありがとうございました．
次に，お忙しい中，博士論文の審査を引き受けていただきました，武田正之先生，太原育夫先生，明石重男先生，大和田勇人先生，西山裕之先生に御礼申し上げます．先生方には，博士論文を作成している時は励ましてくださり，審査が始まると，博士論文への有益なコメントと共に「勉強になった」というとても嬉しいお言葉をいただきました．これから本研究を更に発展させられるように研究を進めていきます．ありがとうございました．
また，計算機科学に関係する名著を読む輪講に，私が学部生のときから参加することを歓迎してくださった筑波大学の久野靖先生と，久野ゼミのメンバー皆様に深く感謝致します．先生のゼミに参加することで辞書のような分厚い本を読み，型理論やプログラミング言語の意味論といったコンパイラの研究を行うための基礎知識となる数々の重要な理論や概念を学ぶことができました．これも，皆様の非常にわかりやすい解説によって，難しい内容でも挫けることなく本を読み進めることができたおかげです．また，私が担当していた非常勤講師の授業で，どうすればよりわかりやすく，学生がプログラ
ミングを楽しいと思える授業をできるのかについて先生に相談させていただiii

きました．これからは，学生がプログラミングを学ぶ手助けをする機会が増えますが，試行錯誤を続け，プログラミングや計算機科学の楽しさを伝えられるように頑張ります．本当にありがとうございました．
私が数学科の学生のときに卒業研究のご指導をしていただき，修士課程か
ら情報科学専攻に進学するためのご支援をして下さった東京理科大学理工学
部数学科の牛島健夫先生に感謝致します．最後のゼミ発表では，学部 3 年の後期からの約 1 年半の間にゼミで学んだ内容を踏まえ，各自の興味のある事を数学と関係させた内容を発表する事になっていましたが，私の修士課程での研究内容を考慮していただき，コード最適化について発表する事を薦めてもらいました．この発表が分野外の人に研究紹介を行う初めての機会でしたが，先生に「とてもわかりやすかった．興味深いですね．
」と言ってもらえ，とても嬉しかったです．また，先生のゼミで学んだ微分方程式や不動点は，現在進めている研究と密に関係しており，これらの内容を扱う論文や本を読むときはいつも先生の指導を思い出しています．親切なご指導と暖かいご支援をしてくだり，ありがとうございました．
私を東京理科大学へ導いてくれた中学・高校時代の友人や先生方，歴代の滝本研究室のメンバーを含め，これまでに多くの素晴らしい友達に出会うことができました．大学院での生活は孤独であるとよく聞きますが，私がそのように感じることはありませんでした．これも皆様と一緒に遊んだり飲みに行く事でリフレッシュができたおかげです．どうもありがとうございました．
これからもどうぞよろしくお願い致します．
最後に，頑固で負けず嫌いであり，特に家族からの助言には耳を貸そうともしない私を，時には厳しく，時には優しく支え続けてくださった両親と，小さい頃から切磋琢磨していた兄妹に感謝致します．大学を卒業したら高校で数学の教師になるとずっと言っていたのに，学部 3 年生の秋に大学院への進学に進路変更を決めたとき，無理を言って承諾してもらいましたが，大学院での生活は本当に楽しくて，この道を進めることができて良かったです．博
士後期課程に進学してからはあまり顔を見せずにいましたが，これからは親孝行をしていきたいので，いつまでも元気に過ごしてください．

2015 年 1 月
澄川靖信

iv

Contents
List of Figuresvii

List of Tablesx

1 Introduction
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Removing Redundant Expressions . . . . . . . . . . . . . . .
1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . .

1
1
3
4
7
13

2 Background14
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Program Representation . . . . . . . . . . . . . . . . . 14
2.1.2 Control Flow Graph . . . . . . . . . . . . . . . . . . . 14
2.1.3 Data-ﬂow Analysis . . . . . . . . . . . . . . . . . . . . 16
2.1.4 Static Single Assignment Form . . . . . . . . . . . . . 19
2.2 Fundamental Code Optimization Techniques . . . . . . . . . 20
2.2.1 Global Value Numbering . . . . . . . . . . . . . . . . . 21
2.2.2 Common Sub-expression Elimination . . . . . . . . . . 23
2.2.3 Loop Invariant Code Motion . . . . . . . . . . . . . . 23
2.2.4 Partial Redundancy Elimination . . . . . . . . . . . . 24
3 Eﬀective Demand-driven PRE
31
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 PRE Based on Query Propagation . . . . . . . . . . . . . . . 32
3.3 Eﬀective Demand-driven PRE . . . . . . . . . . . . . . . . . . 37
3.3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . 37
3.3.2 Optimistic Global Value Numbering . . . . . . . . . . 38
3.3.3 Query Propagation . . . . . . . . . . . . . . . . . . . . 44
3.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52v

4 Demand-driven Scalar Replacement
53
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.1 Scalar Replacement . . . . . . . . . . . . . . . . . . . 56
4.2.2 Register Promotion . . . . . . . . . . . . . . . . . . . . 57
4.3 Array Reference Representation . . . . . . . . . . . . . . . . . 58
4.4 Demand-driven Scalar Replacement . . . . . . . . . . . . . . 59
4.4.1 Value Numbering for Array References . . . . . . . . . 60
4.4.2 Redundancy Removal over Iteration . . . . . . . . . . 60
4.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 64
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5 Global Load Instruction Aggregation
67
5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1 Cache Optimization . . . . . . . . . . . . . . . . . . . 69
5.2.2 Removing Redundant Expressions . . . . . . . . . . . 70
5.3 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.1 Program Representation . . . . . . . . . . . . . . . . . 71
5.3.2 Lazy Code Motion . . . . . . . . . . . . . . . . . . . . 71
5.4 Array Reference Aggregation . . . . . . . . . . . . . . . . . . 74
5.4.1 Local Properties . . . . . . . . . . . . . . . . . . . . . 74
5.4.2 Modiﬁed Global Properties . . . . . . . . . . . . . . . 75
5.4.3 Application to the Entire Program . . . . . . . . . . . 80
5.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 81
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6 Conclusion and Future Direction
88
6.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . . 88
6.2 Future Direction . . . . . . . . . . . . . . . . . . . . . . . . . 90vi

List of Figures
1.1
1.2
1.3

Memory hierarchy. . . . . . . . . . . . . . . . . . . . . . . . .
Jacobi’s stencil solver. . . . . . . . . . . . . . . . . . . . . . .
Example of removing redundant expressions over iteration.
(a) Original code. (b) A result of scalar replacement. . . . . .
1.4 Removing redundant expressions. (a) Original code. (b) Result of removing redundancy. . . . . . . . . . . . . . . . . . .
1.5 Using PRE to remove partially redundant expression. (a)Original code. (b) Result of PRE. . . . . . . . . . . . . . . .
1.6 Propagating a query for a[i] by EDDPRE. (a) Original program. (b) Query propagation. . . . . . . . . . . . . . . . . . .
1.7 (a) Result of query propagation shown in Fig. 1.6. (b) Translating the original program. . . . . . . . . . . . . . . . . . . .
1.8 Query propagation of PRESR. (a) Original program. (b)Query propagation. (c) Result of query propagation. (d)Result of translating the original program. . . . . . . . . . . .
1.9 Motivation example of GLIA. This ﬁgure represents that execution b[i] expels the reference data of a[i] and a[i+1]from the cache memory because the execution results in cachemiss. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.10 Moving the array reference a[i+1] by GLIA. . . . . . . . . .
2.1
2.2
2.3
2.4
2.5

2.6

(a) Original code. (b) An example CFG of the code. Eachnode corresponds to a basic block. . . . . . . . . . . . . . . .
Removing critical edge. (a) Original code. (b) After removing
the critical edge and applying PRE. . . . . . . . . . . . . . .
An example code for constant propagation. . . . . . . . . . .
An example of SSA form. (a) Normal form code. (b) SSA
form code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Assigning value numbers. (a) Original code. (b) After value
numbering. The numbers with ”[ ]” represent the value numbers of the corresponding expressions. . . . . . . . . . . . . .
Eﬀectiveness of GVN. (a) Original code represented in a CFG.
(b) Result of applying GVN on a dominance tree. The labelsof the tree correspond to the CFG. . . . . . . . . . . . . . . .
vii

3
5
5
6
7
8
9

10

12
12

15
16
17
20

21

22

2.7

Eﬀectiveness of CSE. (a) Original code. (b) Result of applying CSE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.8 Eﬀectiveness of LICM. (a) Original code. (b) Result of applying LICM. . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Eﬀectiveness of PRE. (a) Original code. (b) Result of applying PRE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.10 Motivation example of LCM. (a) Original code. (b) downsafety of a[i] . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.11 Insertion candidates. (a) Earliest. (b) Latest. . . . . . . . . .
2.12 Translated program. (a) Isolate. (b) Result of applying LCM.
3.1

3.2
3.3

3.4
3.5

4.1
4.2

4.3
4.4
4.5

5.1
5.2
5.3
5.4
5.5

23
24
25
28
29
30

Eﬀect of PREQP’s removing redundant expression and applying copy propagation. (a) Original program. (b) Afterremoving x1 +1 at Node 3. . . . . . . . . . . . . . . . . . . . . 33
Eﬀect of PREQP’s query propagation. (a) Example of propagating a query. (b) Result program of applying PREQP . . 34
Proof of equality between traversals of topological sorted dominance tree in depth-ﬁrst and left-ﬁrst search and a topologically sorted CFG. We assume 2 < k < r. . . . . . . . . . . . 39
Eﬀect of optimistic value numbering. (a) Original program.
(b) A result of GVN that is carried out on the dominator tree. 40
Eﬀect of EDDPRE’s query propagation. (a) Original program. (b) A result program. . . . . . . . . . . . . . . . . . . . 45
Eﬀect of PRESR. (a) Original program. (b) After applying
PRESR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
An example program after attaching versions for arrays. WhenPRESR propagates a query for a3 [i1 ], its attached version
is changed by using arrayVersion, as displayed in Table 4.1. .
Resulting program after applying PRESR to Fig. 4.2. . . . .
Eﬀect of PRESR. (a) Original program. (b) After applying
PRESR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ratio of analyzing costs, compared with exhaustive style ofPRE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
An example of a cache miss that is a target of MDGLIA. . .
Eﬀectiveness of MDGLIA. (a) Original code. (b) Result ofapplying MDGLIA. . . . . . . . . . . . . . . . . . . . . . . . .
Code motions of LCM. (a) Hoisting expressions. (b) Delaying.
Result of applying LCM to Fig. 5.3(a). . . . . . . . . . . . . .
Speculative code motion. (a) Original code. (b) Moving arrayreference, not satisfying down-safety. . . . . . . . . . . . . . .

viii

54

59
59
62
66
68
69
72
72
76

5.6

Eﬀectiveness of extending UpSafe. (a) Result of computing
data-ﬂow equations to move a[k][l] at Node 5. (b) Resultof moving the array reference. . . . . . . . . . . . . . . . . . .
5.7 Computing closeness of each addresses of a[i][l] at Node 4
and Delayed . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8 Preserving unnecessary code motion. (a) Original code. (b)Result of applying exhausive analysis version of MDGLIA toa[i+1]. (c) Result of applying demand-driven style MDGLIA
to a[i+1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9 Decrease rate of cache misses. . . . . . . . . . . . . . . . . . .
5.10 Diﬀerence of an insertion point for a[i][j+1]. (a) Originalcode. (b) Result of applying LCM-MEM. (c) Result of applying GLIA. (d) Result of applying MDGLIA. . . . . . . . .
5.11 The decrease ratio of L2 cache miss for GLIA, MDGLIA,USGLIA, and USMDGLIA to the cache miss for LCM-MEM.

ix

77
79

81
82

84
85

List of Tables
3.1
3.2
3.3
3.4

Execution time of objective code . . . . . . . . . . . . . . . .
Analysis time . . . . . . . . . . . . . . . . . . . . . . . . . . .
The time of query propagation . . . . . . . . . . . . . . . . .
The number of nodes which query propagated . . . . . . . . .

49
49
50
50

4.1
4.2
4.3

arrayVersions from Fig. 4.2 . . . . . . . . . . . . . . . . . . .
Results of execution time . . . . . . . . . . . . . . . . . . . .
Results of the dynamic number of load statement . . . . . . .

59
65
65

5.1
5.2
5.3
5.4
5.5

System parameters of cache memories . . . . . . . . . . . . . 82
The number of DCache Repl . . . . . . . . . . . . . . . . . . 83
The number of L2 Lines Out . . . . . . . . . . . . . . . . . . 83
The number of register spills . . . . . . . . . . . . . . . . . . 84
The number of L2 cache miss of USGLIA and USMDGLIA,
and the cache miss ratio of them to the cache miss for GLIA
and MDGLIA . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
The number of aggregated array references under keepOrderand keepDimension in speculative/not speculative code motion 86

5.6

xChapter 1

Introduction
1.1

Motivation

When we execute a program described in a high-level programming language, the program has to be processed by the own processor of the language, such as an interpreter or a compiler. If programmers’ main concern
is execution eﬃciency, for example, the program is expected for product use,the compiler should be used for applying code optimizations to the program
partially or totally to transform it into eﬃcient one. In particular, because
optimizing compilers apply several code optimizations to a program, theygenerate extremely eﬃcient code for the machine where the program is executed.
Initial compilers could only apply limited code optimizations to a program; therefore, in many cases, the code directly described in the machinecode by expert programmers was more eﬃcient than generated by compilers.
However, as the size of each program increases, it has been diﬃcult for programmers to manually create machine code considering the entire program,whereas improving a lot of code optimization techniques based on global
information has made compilers requisite items for programmers.
Since the 1960s, many researchers have proposed several optimization
techniques for optimizing compilers. These researchers’ eﬀorts primarily
focused on solving the issue of the main memory’s access speed functioning
much slower than the processor’s speed. In order to reduce the number ofaccesses to the main memory, modern processors have a set of registers thatwork as fast as processors. Modern processors also have cache memories
that are much faster than the main memory though they are slower than
the registers.
Most compilers apply two optimization techniques for the eﬀective use ofregisters, register promotion and register allocation. Register promotion replaces variables declared by users with virtual registers. On the other hand,register allocation tries to allocate the virtual registers to as many physi-

1Chapter 1. Introduction

cal registers as possible. Notice here that virtual registers have the same
properties as physical registers except that the number of virtual registers is
inﬁnite, corresponding to temporary variables generated inside a compiler.
In general, unlike virtual registers, user-declared variables may be modiﬁed
through side eﬀects; therefore, they should be allocated in the main memory. A simple way to replace variables with virtual registers is to pick up
variables with no side eﬀects, and then to replace them. This way enables
totally replacing the variables with the virtual register, but the number ofthem is restricted. In order to handle variables with side eﬀects, there is
the way to replace redundant load instructions with temporary variables
holding a result of preceding load instructions that access the same memory
locations and load the same value.
For the eﬀective use of cache memory, it is important to continuously
access memory locations whose copies exist in cache memory simultaneously.
Therefore, to continuously access contiguous memory locations, it is popular
to transform index of array references inside a loop.
Although many researchers have tried to solve the issue, the gap between
processor and main memory access speed is, unfortunately, growing. Thatis, the percentage of the time required to access the main memory in theexecution time of program become increasing year by year; therefore, solving
the issue is becoming more important.
This thesis presents new techniques that utilize code motion to more
eﬀectively handle the use of the registers and cache memory. Code motion
is a technique for program transformation that moves expressions or statements to suitable points in a program. Techniques based on code motion canbe categorized into heuristic approaches and data-ﬂow analysis approaches.
Heuristic approaches are used in cases where code motion simply leads tothe improvement of the performance of a program (for example, parallelizing instructions), whereas data-ﬂow analysis approaches are used in cases
in which code motion is utilized depending on the global conditions of aprogram such as removing redundant expressions. To remove partially redundant expressions that are redundant on some execution paths, manycode motion techniques based on the data-ﬂow analysis have been proposedsince 1980s. Our approach also uses a data-ﬂow analysis-based code motion
in order to remove redundant load instructions or aggregate array references to the same array or the same higher-dimensions of the same array.
These techniques contribute to promoting user declared variables to virtual
registers and decreasing cache misses.
In the remainder of this chapter, we summarize the memory hierarchy ofwhich we improve utilization and the approach adopted for the improvement.

2Chapter 1. Introduction

Smaller

FasterRegisterLevel 1 cache
Level 2 cache
Level 3 cache
Main memory
BiggerSlowerFigure 1.1: Memory hierarchy.

1.2

Memory Hierarchy

A computer needs memory to retain a program and the data for the execution of the program. In general, a computer uses three kinds of memory:
register, cache memory, and main memory. These three kinds of memories
are used hierarchically to make the memory system fast and scalable. This
structure of several memories is called the memory hierarchy. As shown in
Fig. 1.1, there is a trade-oﬀ between speed and size in the memory hierarchy.
The feature of each type of memory is summarized as follows:
Register is the fastest type of memory, but the bigger it is, the more expensive its production costs. Therefore, most CPUs have just a small
set of register.
Cache memory is used to store copies of data that are frequently accessedfrom the main memory. It works as fast as the register if accessed data
is included in it; otherwise, it is necessary to access main memory tocopy the data. In terms of eﬃciency and size, it is medium. The
middle layer for cache memory can consist of several caches as sublayers. The lower level caches are relatively slower, although they areallowed to be larger in size.
Main memory is the slowest kind of memory in the memory hierarchy
although it is the biggest. Once the memory is accesses, the CPU
stalls; therefore, memory access remarkably decreases the execution
eﬃciency of a program.

3

Chapter 1. Introduction

The memory hierarchy enhances the eﬃcient utilization of diﬀerent typesof memory based on the principle of locality [44]. Locality is categorized into
two basic varieties: temporal locality and spatial locality.
Temporal locality. If a memory location is accessed, it tends to be accessed again in the near future.
Spatial locality. If a memory location is accessed, other data around it
tends to be used in several parts of the program.
Whenever the processor needs data at a location x in the main memory,the cache memory is checked ﬁrst to determine whether it stores a copyof the data. If the data is found in the cache memory, it can be obtained
without any main memory access; otherwise, the processor fetches the dataaround x from the main memory and places them in the cache memory sothat it can be available for subsequent accesses. The former case is calleda cache hit; and in contrast, the latter case is called cache miss. If a cache
miss occurs, the access to x not only causes a signiﬁcant delay to fetch thedata around x in the main memory, but also to remove the old data fromthe cache memory. Thus, the key points for improving execution eﬃciency
are to 1) increase the use of registers, and 2) decrease the number of cache
misses.

1.3

Removing Redundant Expressions

Redundant expressions are executed in various kinds of practical programs,
such as computations of the oﬀsets of array references, calculating Fibonacci
numbers, multiplying matrices, and using the stencil solver. Further, about
half of the load instructions in SPEC’s Benchmark, which is one of themost popular benchmarks to conﬁrm improvement of techniques in the code
motion research ﬁeld, can be removed as they are redundant [7].
Example.
Figure 1.2 shows the pseudo code for Jacobi’s stencil solver. Consider
the two array references a[i][j-1] and a[i][j]. For the ﬁrst iteration of
the inner-loop (j=1), these array references execute a[i][0] and a[i][1],respectively. For the second iteration (j=2), they execute a[i][1] anda[i][2], respectively. That is, a[i][j-1] references the data that is referred to by a[i][j] in the previous iteration; therefore, a[i][j-1] is redundant. In addition, a[i][j] and a[i-1][j] are redundant because thesereferenced data are already referred in the previous iteration of the outer
loop by a[i+1][j] and a[i][j], respectively.
End of Example.

4

Chapter 1. Introduction

for(i=1;i<N;i++){for(j=1;j<N;j++){T[i][j] = 0.2*(a[i][j]+a[i-1][j]+a[i+1][j]+a[i][j-1]+a[i][j+1]);}}
Figure 1.2: Jacobi’s stencil solver.

while(i<N){
sum+=a[i]+a[i-1];i++;}t’=a[0];while(i<N){t=a[i];
sum+=t+t’;
i++;
t’=t;
}

(a)

(b)

Figure 1.3: Example of removing redundant expressions over iteration. (a)Original code. (b) A result of scalar replacement.

Removing array references that are redundant over iterations is called
scalar replacement. We show how traditional scalar replacement removes
the redundant array reference with a simple program shown in Fig. 1.3.
Example.
The array reference, a[i-1] in Fig. 1.3 (a), is redundant because thereference data is referred by a[i] in the previous iteration. To remove theredundant array reference, traditional scalar replacement introduces a new
temporary variable t for holding the value of a[i], and inserts t’=a[0]before the loop and t’=t at the exit of the loop body. Finally, a[i-1] canbe replaced with t’ because t’ has an initial value of a[i-1], otherwise, thetemporary variable holds the value of t for the next iteration. The result of
this translation is shown in Fig. 1.3 (b).
End of Example.

5Chapter 1. Introduction

x=a[i];
y=a[i];

x=a[i];
y=x;

(a)

(b)

Figure 1.4: Removing redundant expressions. (a) Original code. (b) Resultof removing redundancy.

Removing redundant expressions is an important technique for improving execution eﬃciency because it can shorten the critical path or reduce
the necessity of using hardware. Furthermore, removing redundant memoryreferences is a critical technique because it reduces the number of references for cache and main memory. This thesis presents a demand-driven
scalar replacement based on partial redundancy elimination (PRE) that is
one technique for removing redundancy. In addition, we extend PRE to
decrease the number of cache misses. In the remainder of this section, weshow how redundant expressions are removed by PRE.
Example.
Consider the two statements that contain a[i] in Fig. 1.4 (a). The
values of the operand variable i and a[i] are the same because there is novariable deﬁnition or store statement between the statements; therefore, theright-hand side of the statement y=a[i] is redundant. This expression canbe removed by substituting the value referred to by the preceding expression;that is, the redundant expression can be removed by substituting x in theleft-hand side of the preceding statement as shown in Fig. 1.4 (b).
End of Example.
If a program contains some branch instructions, the preceding instructions are not always executed. In this case, even if some expressions are
redundant on speciﬁc execution paths, they may not be removed as in thecase of previous example.
Example.
Consider an expression a[i] in line 6 in Fig. 1.5 (a). If the conditionof the if statement is true, the expression is redundant; otherwise, it is not.
An expression that is redundant on some, but not all, execution paths iscalled partially redundant.
End of Example.
PRE makes partially redundant expression fully redundant by inserting
expressions.

6

Chapter 1. Introduction

1: if(...){
2: x=a[i];3: }else{
4: ...
5: }6: y=a[i];if(...){
t=a[i];
x=t;}else{...
t=a[i];
}
y=t;

(a)

(b)

Figure 1.5: Using PRE to remove partially redundant expression. (a) Original code. (b) Result of PRE.

Example.
In Fig. 1.5 (a), PRE inserts statement t=a[i] into then and else parts
as shown in Fig. 1.5 (b); therefore, the partially redundant a[i] becomesfully redundant. Finally, all the fully redundant expressions can be removed
by replacing them with t, which results in a program as shown in Fig. 1.5(b).
End of Example.

1.4

Contribution

To improve the eﬃcient utilization of the memory hierarchy, we propose
three new optimization techniques based on PRE, PRE-based scalar replacement (PRESR) [76], global load instruction aggregation (GLIA) [77],and multidimensional GLIA (MDGLIA) [79]. Furthermore, in order to enhance eﬀectiveness of these PRE based techniques, we propose a new PRE
technique eﬀective demand-driven PRE (EDDPRE) [78] that is based on
demand-driven data-ﬂow analysis.
The contribution details of this thesis are as follows:• Development of eﬀective query propagation for removing redundant array references.
Traditional PRE and scalar replacement require the iterative applications of their entire algorithm for removing all redundant expressions.
Regarding PRE, because it detects redundant expressions based on
their lexical equality, removing lexically diﬀerent expressions with the7Chapter 1. Introduction

i=a[k];j=i;
x=a[j];
if(...){
y=b[i];}else{i++;}z=a[i];Is the value ofa[i] redundant?

(a)i=a[k];j=i;
x=a[j];
if(...){
y=b[i];}else{i++;}z=a[i]; Is the value ofa[i] redundant?

(b)Figure 1.6: Propagating a query for a[i] by EDDPRE. (a) Original program. (b) Query propagation.

same value requires the iterative applications of PRE and copy propagation, as explained detail in Chapter 3. Regarding scalar replacement, traditional techniques are applied to each nest-level in a nested
loop; therefore, if an array reference can be found to be redundantby analyzing some nest-level at a time, traditional techniques need
to be applied iteratively. In contrast, EDDPRE and PRESR can remove redundant array references by only once application. For eacharray reference, these techniques backwardly propagate a query thatcan detect redundant array references by checking whether the valueof the array reference is redundant or not even if they are lexicallydiﬀerent. This is achieved by applying global value numbering (GVN)
that assigns value numbers to all array reference. If some array references generate the same value, GVN assigns the same value number tothe array references; therefore, GVN ﬁnds redundant array references,leading to the disuse of copy propagation. Our GVN creates two kindsof occurred value numbers table at each control ﬂow graph (CFG) nodein order to suppress unnecessary query propagation. EDDPRE andPRESR propagate queries that check occurrence of the value numberof inquired array references on CFG of the program independent of its
structure.
Example.
Consider the array reference a[i] in Fig. 1.6 (a). Because the values ofi and j are same on a path through the then part, the array reference
is redundant on the path. On the other hand, these values are diﬀerent
from each other on another path through the else part; therefore, the8Chapter 1. Introduction

true

i=a[k];j=i;
x=a[j];
if(...){
y=b[i];}else{i++;false}
z=a[i];(a)i=a[k];j=i;
x=a[j];
if(...){
y=b[i];
t=x;}else{i++;t=a[i];}
z=t;(b)

Figure 1.7: (a) Result of query propagation shown in Fig. 1.6. (b) Translating the original program.

array reference is not redundant on the path. That is, a[i] is partiallyredundant. EDDPRE backwardly propagates a query ”Is the value ofa[i] redundant?”, as shown in Fig. 1.6 (b). Considering a querythat is propagated to the then part, it is further propagated before
the if statement, and then, it gets an answer true because it canﬁnd that the value of a[j] is same as the inquired array reference’s
value. Considering a query propagated to the else part, the query can
get an answer false without propagating it before the if statement
because there is no occurrence of value until before the a[i]. These
results are returned backed to the a[i], as shown in Fig. 1.7 (a).
Using these results, EDDPRE ﬁnds that a[i] is partially redundant;
therefore, it inserts a[i] into the else part. Finally, EDDPRE replaces
the inquired a[i] with newly introduced an introduced temporary
variable, as shown in Fig. 1.7 (b).
End of Example.
• Decreasing the number of references from processor to cachememory based on eﬀective demand-driven analysis.
Removing redundant array references promotes memory references toregister references, which means that it promotes even cache references
to register references. This is achieved by EDDPRE and PRESR.
These techniques remove redundant array references included in an iteration of a loop. In addition, PRESR can also remove array referencesthat are redundant over iterations.
9Chapter 1. Introduction

Is the value ofa[i-1] redundant?

while(i<N){t=a[i];
j=i;
while(j<M){
sum+=j+a[i-1];}b[i]=sum;Is the value of
i=i+1;}
a[i] redundant?

while(i<N){t=a[i];
j=i;
while(j<M){
sum+=j+a[i-1];}b[i]=sum;i=i+1;
}
(a)

(b)

false

while(i<N){
true
t=a[i];
j=i;
while(j<M){
sum+=j+a[i-1];}b[i]=sum;i=i+1;
true}(c)t’=a[i-1];
while(i<N){t=a[i];
j=i;
while(j<M){
sum+=j+t’;}b[i]=sum;i=i+1;t’=t;}(d)Figure 1.8: Query propagation of PRESR. (a) Original program. (b) Query
propagation. (c) Result of query propagation. (d) Result of translating theoriginal program.

Example.
Consider the array reference a[i-1] in Fig. 1.8 (a). This array reference is redundant because the referenced data is already loaded to by
a[i] in the previous iteration. To remove this redundancy, PRESR
backwardly propagates a query ”Is the value of a[i-1] redundant?”
as shown in Fig. 1.8 (b). Consider a query that is propagated throughthe back edge to the exit of the loop body. This query is propagated tothe deﬁnition i=i+1 of an induction variable included in the inquired

10Chapter 1. Introduction

array reference. To check redundant array references in the previous
iteration, the query is changed to check the value of a[i] by replacing i with the right-hand side of the statement deﬁning the i, andthen, the query is propagated further. This query will be propagatedto a[i] below the while statement; therefore, it gets true. Because aquery propagated to outside of the loop gets false, this array referenceis partially redundant. Similar to EDDPRE, PRESR inserts a[i-1]at the entry of the loop, and then it returns true, as shown in Fig. 1.8(c). Finally, PRESR replaces the inquired a[i-1] with t’, as shownin Fig. 1.8 (d).
End of Example.
• Decreasing the number of references from cache memory to
main memory based on PRE framework.
GLIA makes references to the same array continuous by moving thereferences immediately after preceding other references to the samearray. This movement is achieved based on PRE framework. By thismovement, some cache misses can be suppressed because data in anarray are continuously stored in the main memory. To explain the
motivation for GLIA, we show how accessed data are copied into cachememory with an example program in Fig. 1.9. In this thesis, forease of explanation, we assume that cache memory is directly mapped
without loss of generality. That is, when the data are transferred fromthe main memory to the cache memory, the cache line is determinedby the memory address modulo of the number of lines in the cachememory.
Example.
Consider the array reference a[i+1] in the C program in Fig. 1.9.
After execution of the array reference a[i], the data from a[i] anda[i+1] are copied to a cache line whose index is 10. Then, because
execution of the array reference b[i] results in a cache miss, the datacontained in b[i] and b[i+1] are also copied into cache memory.
In this case, these data are copied to the cache line at the index 10
because the address of b[i] is 1010; therefore, the data from a[i]and a[i+1] are removed from cache memory, which may result in acache miss for the subsequent access of a[i+1].
As shown in the example, once data at a speciﬁc array index is loaded
from main memory, it is stored in cache memory along with otherdata belonging to the same array. That is, continuously accessing thesame array may result in cache hits. Continuously accessing the samearray can be promoted by moving references to an array around other11

Chapter 1. Introduction

‫؞‬
‫؞‬
‫؞‬

void main(){x=a[i];
y=b[i];
z=a[i+1];}a[i] 0010
a[i+1] 0011

00
01
10

a[i] a[i+1]11Cache memory

‫؞‬
‫؞‬
‫؞‬

b[i] 1010
b[i+1] 1011
‫؞‬
‫؞‬
‫؞‬
Main memory

Figure 1.9: Motivation example of GLIA. This ﬁgure represents that execution b[i] expels the reference data of a[i] and a[i+1] from the cachememory because the execution results in cache miss.

void main(){x=a[i];
z=a[i+1];y=b[i];}
Figure 1.10: Moving the array reference a[i+1] by GLIA.

reference to the same array. GLIA moves a[i+1] immediately beforeb[i] so as to follow a[i], as shown in Fig. 1.10.
End of Example.
In addition, a multidimensional array can be regarded as an array oflower dimensional arrays, which means that it is more eﬀective to continuously aggregate the array references with the most similar indexes
in higher dimensions. We extend GLIA to handle multidimensional
arrays for moving a reference immediately after the preceding references to the same array with the largest number of similar indexes.
We call this extended GLIA MDGLIA. MDGLIA computes the number of indexes of each array reference, preceding a candidate that was
moved, which are the same as the indexes of the candidate; then,12Chapter 1. Introduction

MDGLIA moves the candidate to the points in the program close to
the references holding the number of the same indexes.
• Demonstrating the eﬀectiveness of our techniques throughexperiments employing popular benchmarks.
We have implemented EDDPRE, PRESR, GLIA, and MDGLIA as
low-level intermediate representation converters in a COINS compiler[24]. We evaluated the eﬀects of our techniques using programs from
CFP2000 and CINT2000 in SPEC’s Benchmarks. On average, theanalyzing cost of EDDPRE was about half of the demand-driven PRE.
PRESR improved the performance of all the programs about 2% on
average. GLIA and MDGLIA decreased the number of cache missesof many programs.

1.5

Thesis Organization

Chapter 2 presents preliminaries and details the algorithms of two basic optimization techniques, GVN and PRE. Chapter 3 describes the algorithm for
EDDPRE, and demonstrates the analytical improvement and eﬃciency of
execution of objective code. Chapter 4 explains the algorithm for PRESR
where EDDPRE is extended to remove redundant array references acrossloop iterations and shows the experimental result. Chapter 5 outlines thealgorithm for GLIA and MDGLIA and the experimental results from suppressing the number of cache misses. Chapter 6 concludes this thesis andindicates future directions of this thesis.

13

Chapter 2

BackgroundIn this chapter, we deﬁne the program representation and control ﬂow graph,and then provide the details of the data-ﬂow analysis. Finally, we describe
the algorithms of GVN and PRE that are the basis of our technique.

2.1

Preliminaries

2.1.1

Program Representation

Many modern compilers consist of ﬁve stages: lexical analysis, syntax analysis, semantic analysis, code optimization, and code generation. Lexical
analysis creates a sequence of tokens from a source program, and then syntax analysis builds abstract syntax trees (ASTs) from those tokens. The
ASTs are checked for their consistency with declarations by semantic analysis such as type checking. After that, the ASTs are transformed into anintermediate representation (IR). The IR code is used as both input andoutput for optimizations that are independent of programming languages
and machines.
We assume that the IR code is a sequence of statements, that have at
most one operator, known as three-address code [2], as the following:x ← y op z

2.1.2

Control Flow Graph

We assume that a control ﬂow graph (CFG) has been built for each program.
The CFG is a graph structure, which is represented as a quadruple (N, E,
start, end), where N is a set of node, E denotes a set of edges N × N,
start is a start node with an empty statement, and end is an end node with

14

Chapter 2. Background

0

x=1;
y=1;
z=x+y;
if(z<0){w=z;}else{
w=-z;
}

2

1

x=1
y=1
z=x+y

w=z

3

w=-z

4
5

(a)

(b)

Figure 2.1: (a) Original code. (b) An example CFG of the code. Each nodecorresponds to a basic block.

an empty statement. 1
Example.
Figure 2.1 (b) shows a CFG of Fig. 2.1 (a). As the left side code has one
if -else statement, it has four basic blocks. These basic blocks correspondto Nodes 1, 2, 3, and 4 in the CFG. In particular, Nodes 0 and 5 are called
the start and end node, respectively.
End of Example.
A given edge is expressed as (m, n) ∈ E, where m is referred to as apredecessor of n and n is known as a successor of m. In general, a node has
several predecessors and successors because of the nondeterministic branching structure of a CFG. Here, the sets of predecessors and successors of noden are denoted as pred (n) and succ(n), respectively.
When all the paths from start to node n include node m, it is said thatm dominates n [4]. If m dominates n and m is not n, it is said that mstrictly dominates n. An edge a → b where the destination b dominates thesource a is called a back edge [2].
In the CFG, it is assumed that the critical edges, which are edges leadingfrom a node with more than one successor to a node with more than one
predecessor, have been removed by inserting synthesized nodes, because the1

In this thesis, we sometime omit the start node and the end node to simplify explanation.
15

Chapter 2. Background1
1

2 x=a[i]42t=a[i]
x=t

4
7 t=a[i]3 y=a[i]

5

3 y=t

6

5

6
(a)

(b)

Figure 2.2: Removing critical edge. (a) Original code. (b) After removing
the critical edge and applying PRE.

critical edges can block eﬀective code motion.
Example.
In Fig. 2.2 (a), there is a critical edge from Node 4 to Node 3. As a[i]at Node 3 is partially redundant, it can be removed by inserting the same
expression at Node 4, but PRE does not allow such an insertion because theinsertion introduces a new computation at the path through Nodes 1, 4, 5,
and 6. To remove the partially redundant expressions, a new node, Node 7,
is inserted on the critical edge as shown in Fig. 2.2 (b).
End of Example.

2.1.3

Data-ﬂow Analysis

Data-ﬂow analysis is performed to collect information for code optimizations, such as constant propagation, copy propagation, common sub-expression
elimination, GVN, dead code elimination [6, 53], register promotion, and soon. To present formal deﬁnitions, we use Fig. 2.3 to show how the data-ﬂow
analysis for a constant propagation collects information.
Example.
Consider applying constant propagation to the code in Fig. 2.3. A
variable a is initialized to 1 at Node 1, and then it is used at Node 2.
To propagate the value of a from Node 1 to Node 2, the initial value 1 is
16

Chapter 2. Background

1 a=1
2 b=a+2
3 c=0
4 d=a+5
5 a=3
6

Figure 2.3: An example code for constant propagation.

recorded at the exit of Node 1.
End of Example.
The information collected at the exit of a node n, OUT[n], can be formally deﬁned by a transfer function f , and information collected at the entryof n, IN[n], as follows:
OUT[n] = f (IN[n])(2.1)

Example.
Consider the statement a=3 in Fig. 2.3. Once the statement has been
executed, the value of a is modiﬁed to 3. In other words, the statement
generates a deﬁnition of a, 3, and kills all deﬁnitions of the variable, 1,reaching to the node.
End of Example.
The transfer function of a program point x can be formally deﬁned asfollows:f (x) = gen ∨ (x − kill )(2.2)

Consider the statement a=3 in Fig. 2.3, in which gen and kill correspondto 3 and 1, respectively. Here, if a transfer function uses information at theentry point of a node to determine information about the exit point as wellas constant propagation, its direction is forwards. In contrast, if the functionuses information at the exit point of a node to determine information about
the entry point, its direction is backwards.
17

Chapter 2. BackgroundTo present the formal deﬁnition of IN[n], we continue to explain theexample of constant propagation in Fig. 2.3.
Example.
We consider the value of a that can reach the expression a+5 at Node
4 in Fig. 2.3. a is deﬁned at 1 at Node 1, whereas it is deﬁned to as 3 at
Node 5. These values can reach the a+5 through Node 3 because the former
value propagates on a path that consists of Nodes 1, 2, 3, and 4 while thelatter value propagates through a back edge and Nodes 3 and 4. This result
indicates that it is impossible to statically determine which value is usedat the a+5. This observation shows that the analysis has to calculate theintersection of values propagated on all paths from start to Node 3 that isa join point.
End of Example.
IN[n] is formally deﬁned as follows:
IN[n] =∏Fi (IN[start])

(2.3)

∀i

where Fi is the functional composition of the transfer function overthe execution path Pi from the start node to ni .
To collect accurate information, the optimizer should calculate equation(2.3); however, in general, it is impossible to do so because of existing loops.
Example.
Consider the number of execution paths from start to Node 4 in Fig.
2.3. Let P41 be an execution path that consists of Nodes 1, 2, 3, and 4. Let
P42 be an execution path that consists of Nodes 1, 2, 3, 4, 5, 3, and 4. Let
P43 be an execution path that consists of Nodes 1, 2, 3, 4, 5, 3, 4, 5, 3, and4. Furthermore, we can deﬁne P44 , P45 , ..., P4n as well as the aforementioned
paths. Thus, an inﬁnite number of execution paths can be assumed for a
program including the paths within loops.
End of Example.
Therefore, to calculate the data-ﬂow information for any program, equation (2.4) presents an approximate solution as follows:
IN[n] =∏

OUT[p](2.4)

p∈pred(n)The result of solving equation (2.3) is called the meet-over-path (MOP)
solution. On the other hand, the approximate solution is called the maximum ﬁxed point (MFP), which is determined by repeatedly solving equations(2.1) and (2.4) until the values of IN and OUT are ﬁxed [2]. Notice that,18Chapter 2. Background

if the transfer function f of equation (2.2) satisﬁes distributivity, the MFP
solution is the same as the MOP solution [50].
To deﬁne formal equations, we used constant propagation whose thetransfer function’s direction is forwards. In contrast, for an optimizer whose
the transfer function’s direction is backwards, IN[n] and OUT[n] are formallydeﬁned as follows:

OUT[n] =∏IN[s]s∈succ(n)IN[n] = f (OUT[n])2.1.4

Static Single Assignment Form

Many programming languages support mutable variables. Such variables areuseful for writing programs along control ﬂows in imperative programming
languages, but at times, this result in complex data-ﬂow analyses because
these variables can be modiﬁed at any point. If each variable can have only
one value without modiﬁcation, it is possible to simplify data-ﬂow analysis
by deﬁning the transfer function without any kill term.
Static single assignment (SSA) form is one variety of program representation that allows every variable to be deﬁned only once [4, 9]. In SSA
form, the representation with only one deﬁnition for each variable is achieved
through attaching a unique version number to an original variable name pera deﬁnition. Furthermore, in SSA form, a special function ϕ that alternatively returns one of the arguments depending on a control ﬂow is inserted
to merge several deﬁnitions that reach the same uses. The ϕ function gives
the property where each deﬁnition dominates all of its uses, so that code
optimizers can be more simply described for programs in SSA form. Transformation into SSA form is achieved by the following two steps: 1) inserting
ϕ functions, and 2) renaming variables. The ϕ functions can be eﬃciently
inserted at the dominance frontiers of all the deﬁnitions of each variable.
The dominance frontier of a node n is a set of nodes that n cannot dominate. Notice that the insertions of ϕ functions result in the insertions of new
assignments, that have to be considered for additional dominance frontiers.
Thus, dominance frontiers can be recursively deﬁned; these are referred toas iterated dominance frontiers. The ϕ functions have to be inserted at all
the iterated dominance frontiers.
Once ϕ functions are inserted, the variables can be renamed. Rememberthat each deﬁnition dominates all uses. That is, the new version of a variablename that is generated at each deﬁnition is only used at nodes dominated by
the deﬁnition. On the other hand, there are ϕ functions using the deﬁnition
at immediate successors of nodes dominated by the deﬁnition. Therefore,
19Chapter 2. Background

1
1

i₁=0

i=0
2

2

3
3

i=1

i₂=1

4

4

5 i₃=φ(i₂,i₁)

56

6 x=i+1(a)i₄=φ(i₃,i₁)
x₁=i₄+1(b)

Figure 2.4: An example of SSA form. (a) Normal form code. (b) SSA form
code.

renaming the deﬁnitions and uses can be eﬃciently achieved by traversing
a dominator relation.
Example.
Consider a variable i in Fig. 2.4 (a). The variable is deﬁned twice atNodes 1 and 3. In normal form, they are shared through a common variable
i which is used at Node 6. In contrast, in SSA form, variable i2 does not
dominate Node 6, but its value may be used at that node. To carry thevalue to its use, SSA form inserts ϕ functions at the entry of Nodes 5 and 6,
and then variable i4 is deﬁned by Node 6 where it is used as i4 +1, as shownin Fig. 2.4 (b).
End of Example.
Three algorithms are known for eﬃciently transforming code from normal form into SSA form [11, 18, 27]. As the ϕ function is not a real statementthat some processors can execute, it is necessary to transform its SSA form
into normal form [8, 11, 64, 74].

2.2

Fundamental Code Optimization Techniques

In this section, we explain four compiler optimizations that are the basis of
our technique.

20

Chapter 2. Backgrounda=read()
b=a+1
c=a+1
x=b+5
y=c+5
z=x*5
w=y*5

a=read() [1]
b=a+1
[3]
c=a+1
[3]
x=b+5
[5]
y=c+5
[5]
z=x*5
[6]
w=y*5
[6]

(a)

(b)

Figure 2.5: Assigning value numbers. (a) Original code. (b) After value
numbering. The numbers with ”[ ]” represent the value numbers of thecorresponding expressions.

2.2.1

Global Value Numbering

Value numbering is a technique that removes redundant computations thatgenerate the same value without depending on their lexical forms in a basic
block. Cocke and Schwarts described a local technique that assigns a unique
number, called a value number, to expressions with the same value numbers
for operands and the same operator [23]. In addition, the variables withthe value generated by the expressions are assigned the value number. The
process of assigning value numbers to expressions and variables is calledvalue numbering. Value numbering is often implemented by recording eachvalue number in a hash-table where it has a tuple of the value numbers of theoperands and the operator as the key. If expressions with a value number
equal to e are found through their tuple in the hash-table for a basic block,they are congruent with e.
Example.
In Fig. 2.5 (a), two variables b and c have the same value, a+1; therefore,both b+5 and c+5 must compute to the same value. The congruence of these
expressions results in the same value number for variables x and y. Similarly,
two variables z and w also have the same value number. Notice here that thevalue numbers are assigned to not only variables but also constant values.
In this example, the constant values 1 and 5 are assigned to value numbers[2] and [4], respectively. As a result, the expressions are assigned to value
numbers as shown in Fig. 2.5 (b).
End of Example.

21

Chapter 2. Backgroundx₁=a[i₁]
1 y₁=a[i₁]z₁=x₁+12

x₁=a[i₁]
1 y₁=x₁
z₁=x₁+1

3

4 w₁=y₁+1

2

4 w₁=y₁+1

3

(a)

(b)

Figure 2.6: Eﬀectiveness of GVN. (a) Original code represented in a CFG.
(b) Result of applying GVN on a dominance tree. The labels of the treecorrespond to the CFG.

To replace the redundant expression with the variable to which the preceding congruent expression is assigned, each expression in a basic block isprocessed from top to bottom.
Value numbering locally detects congruent expressions within a basic
block, whereas a technique globally detecting congruent expressions in an
entire program is called global value numbering (GVN) [3, 21, 35, 37, 59,
65, 67, 69], which is based on a program converted into SSA form. Typical
GVN techniques traverse a dominator tree using a depth-ﬁrst and left-ﬁrst
search, in the process of which once an expression is visited, GVN assigns avalue number to the expression. At this time, it records the assigned value
number to a hash-table. After value numbering all expressions in a node,
GVN propagates the hash-table to the children in the dominance tree.
Example.
Consider two variables x1 and y1 at Node 1 in Fig. 2.6 (a). They are eachassigned the expression a[i1 ], that is, the same value number is assigned tothem, which means that the expression assigned to y1 is redundant; therefore, the expression can be replaced with x1 . Then, the value numbers of
the three variables are propagated to Nodes 2, 3, and 4, which are childrenof Node 1 on a dominator tree that is shown in Fig. 2.6 (b). As result of
this propagation, y1 +1 can be replaced with z1 because z1 is assigned x1 +1
that has the same value number as y1 +1. The propagation way of the value
numbers on the dominator tree guarantees that the value numbers eﬃciently
reach their uses, based on the dominance property of SSA.
End of Example.

22

Chapter 2. Background

1 t=a[i]1 x=a[i]

2

x=t

3

2

4 y=a[i]

3

4

(a)

y=t
(b)

Figure 2.7: Eﬀectiveness of CSE. (a) Original code. (b) Result of applying
CSE.

2.2.2

Common Sub-expression Elimination

If more than one expression is executed on a path, and the value would not
be changed between them; these expressions, excluding the ﬁrst one, aresaid to be redundant on the path. If an expression is redundant on all thepaths from start to the expression, the expression, which is called a common sub-expression, can be removed by replacing it with a variable with thesame value. The optimization is called a common sub-expression elimination (CSE) [22], which contributes to decreasing the number of expressions
to be executed in run time. In order to replace a redundant expression
with a variable, a temporary variable assigned the preceding expression is
introduced as a variable.
Example.
Consider a[i] at Node 4 in Fig. 2.7 (a). As the same expression has
already been computed at Node 1, the expression is redundant at Node
4. CSE inserts a statement t=a[i] before the ﬁrst occurrence, and thenreplaces all redundant a[i] with t as shown in Fig. 2.7 (b).
End of Example.

2.2.3

Loop Invariant Code Motion

If an expression is computed in a loop without any change in its value,
it is called a loop invariant expression. In general, executing loop invariant
expressions outside the loop remarkably decreases the execution cost because
the code inside the loop can be repeatedly executed a lot of times. Loopinvariant code motion (LICM) moves the loop invariant expressions out ofloops.
23

Chapter 2. Backgroundi=1;
while(i<1000){x=a[0];
i+=1;}
print(x);i=1;
x=a[0];
while(i<1000){
i+=1;}
print(x);

(a)

(b)

Figure 2.8: Eﬀectiveness of LICM. (a) Original code. (b) Result of applying
LICM.

Example.
Consider the a[0] in the while loop in Fig. 2.8 (a). As the expression
is an array reference with a constant as the index, and without any modiﬁcation within the loop, the expression is loop invariant. If the expression is
moved outside the loop, as shown in Fig. 2.8 (b), the number of executionsof the expression is reduced from 1,000 to 1.
End of Example.

2.2.4

Partial Redundancy Elimination

If an expression e is redundant at n on all paths from start to n, it can beremoved by CSE. Such an expression is said to be fully redundant. That
is, CSE removes only fully redundant expressions. On the other hand, CSE
cannot remove an expression that is redundant at n on some (but not all)paths from start to n. Such an expression is said to be partially redundant.
PRE makes a partially redundant expression fully redundant by inserting some expressions at preceding points and then removing the original
expression. In PRE, a loop invariant expression can also be regarded as apartially redundant expression because it is not redundant on a path fromthe entry of loop, but it is redundant on a path from the exit of loop bodyto the entry. Once PRE is applied to the loop invariant expression, some
expressions are inserted outside the loop, and the original expression inside
the loop is removed. This process corresponds to LICM. Thus, PRE includes
the eﬀectiveness of CSE and LICM.
Example.
Consider a[i] at Node 4 in Fig. 2.9 (a). The expression is redundant
on a path through Node 2 whereas it is not redundant on another path. To
remove the redundant expression, PRE inserts statements t=a[i] at Nodes
24

Chapter 2. Background

1

1

3

2 t=a[i] 3 t=a[i]4 y=a[i]4 y=t

2 x=a[i]

x=t

(a)

(b)

Figure 2.9: Eﬀectiveness of PRE. (a) Original code. (b) Result of applyingPRE.

2 and 3. As the insertions make the original expression fully redundant, it
can be removed as shown in Fig. 2.9 (b).
End of Example.
The ﬁrst PRE algorithm was proposed by Morel and Renvoise in 1979[57] as a bi-directional data-ﬂow analysis. Although Morel and Renvoise’salgorithm is a powerful technique, it has two issues: 1) some redundant expressions cannot be removed, and 2) some insertions are ineﬀective, where
ineﬀective insertions lengthen the lifetime of temporary variables, leading toan increase of register pressure. To improve the eﬀect of PRE, many techniques have been proposed to achieve optimal completeness, computation,
lifetime, or cost [5, 40, 51, 52, 68, 70], SSA-based sparse analysis algorithm[19, 49, 60, 81], speculative inserting based on proﬁle [13, 38, 46, 72, 84, 87],
removing redundant memory reference instructions [32, 48, 54, 55], and soon [10, 28, 29, 30].
In the rest of this section, we deﬁne the basic properties of PRE, availability and anticipability, and then we explain lazy code motion (LCM) [51, 52]
that is one of the most popular technique of PRE and the basis of ourtechnique.
Basic Properties
Expression e is available at node n iﬀ e is computed on any path p fromstart to n, and there is no deﬁnition of e’s operands since the most recent
occurrence of e on p [5]. When e is available at n, n is up-safe with respect
to e, and e is partially available at node n iﬀ there is at least one pathfrom start to n in which e is computed without subsequent redeﬁnition of
its operands. When e is available at n, e is fully redundant and can be
replaced with the variable that has the preceding execution result. When e25

Chapter 2. Backgroundis partially available at n, e is partially redundant. The partially redundant
expression can be eliminated after inserting expressions to make the original
expression fully redundant.
Expression e is anticipable at node n iﬀ e is computed along any path r
from n to end, and the operands of e are undeﬁned before the ﬁrst computation of e on r [5]. When e is anticipable at n, n is down-safe with respect
to e. PRE inserts expressions at the down-safe nodes without extending
the lengths of any path. If some expressions are inserted at non down-safe
nodes, the insertions are speculative. The speculative insertions allow loop
invariant expressions inside a zero-trip loop such as a while loop to be moved
out of the loop.
Lazy Code Motion
PRE removes redundant expressions by inserting some expressions. However, the insertions and removals process tends to lengthen the live-ranges ofvariables carrying preceding expression values to their uses, so that the variables may be spilled in the register allocation phase [12, 17, 20, 36, 61, 63, 83].
To address the problem, LCM consists of the ﬁrst code motion hoisting expressions as early as possible and the second code motion delaying themas late as possible. The ﬁrst code motion contributes to eliminating all
removable expressions, and the second one contributes to minimizing the
live-ranges of variables. These code motions have to satisfy down-safety andup-safety.
Down-safety is used to ensure that LCM does not introduce a new occurrence of the inserted expression on any execution path. Down-safety is represented by predicate DownSafe. In addition, up-safety is used to ensure that
there are some paths where the number of expressions is decreased by the insertions and removals. Up-safety is represented by predicate UpSafe. These
safeties are deﬁned based on the local properties Comp(n) and Transp(n).
These predicates denote that n contains an occurrence of e, and no operands
are deﬁned or modiﬁed in n, respectively. In particular, the property represented by Transp(n) is called the transparency at node n. To explain thealgorithm, in the rest of section, we assume that each node has only one
statement, and e represents the concerned expression to help understandthe algorithm. The local properties are deﬁned as follows:
Deﬁnition 2.2.1 (Local properties of LCM).
Comp(n)Transp(n)def⇔rhs(n) = e

def

Def (n) ̸∈ Var (e)⇔In the equations, functions rhs(n), Def (n), and Var (ar) return the righthand side of statement at n, a variable deﬁned at node n, and a set of26

Chapter 2. Backgroundvariables which are used in ar, respectively. Using these local properties,
predicates DownSafe and UpSafe are deﬁned as follows:
Deﬁnition 2.2.2 (Safety).
DownSafe(n)def⇔(n ̸= end) ∧(Comp(n) ∨ Transp(n) ∧∏DownSafe(s))

s∈succ(n)UpSafe(n)def⇔(n ̸= start) ∧∏Comp(p) ∨ (Transp(p) ∧ UpSafe(p))
p∈pred(n)Safe(n)def⇔

DownSafe(n) ∨ UpSafe(n)Example.
Consider partially redundant expression a[i] in Fig. 2.10 (a). Once astatement t=a[i] is inserted at Node 1, the original expressions at Nodes
4 and 6 can be removed by replacing them with t. However, this insertion
introduces a new computation on a path through Node 2. If the control
ﬂows along the path, the execution time may be increased. To prevent
such insertions, LCM checks down-safety at each node. As a result, LCM
determines that Nodes 3, 4, 5, and 6 satisfy the down-safety as shown in
Fig. 2.10 (b).
End of Example.
After determining the down-safe nodes, LCM determines optimal node
where expressions can be inserted. The optimal nodes are determined by
the predicates Earliest and Latest. The predicate Earliest(n) denotes that
node n is the closest to start of the nodes m satisfying DownSafe(m) or
UpSafe(m). The predicate Latest(n) denotes that node n is the closest to thenode c that satisﬁes Comp(c) on each path from Earliest to end, and there
is no node that satisﬁes the Comp on the path from Earliest to c. Earliest
is determined as a maximal ﬁxed point of its data-ﬂow equation. Latest
is determined based on a maximal ﬁxed point of the data-ﬂow equation ofpredicate Delayed (n), which denotes that the expression can be delayed until
the exit of node n. Notice that Delayed is based on the result of Earliest;
therefore, they have to be computed in proper sequence. These predicatesare deﬁned as follows:27

Chapter 2. Background: DownSafe

11

3
4 x=a[i]235

4 x=a[i]26 y=a[i]56 y=a[i]

7

7

(a)

(b)

Figure 2.10: Motivation example of LCM. (a) Original code. (b) down-safetyof a[i]Deﬁnition 2.2.3 (Determine insertion candidate nodes).
Earliest(n)def⇔

Safe(n) ∧∑((n = start) ∨¬ Transp(p) ∨ ¬ Safe(p))

p∈pred(n)Delayed (n)def⇔Earliest(n) ∨∏(n ̸= start) ∧¬ Comp(p) ∧ Delayed (p)p∈pred(n)Latest(n)def⇔Delayed (n) ∧ (Comp(n) ∨∑¬ Delayed (s))

s∈succ(n)Example.
Consider the four nodes with dotted borders that satisfy down-safety in
Fig. 2.10 (b). Only Node 3 has a predecessor that does not satisfy the downsafety or up-safety of them. As a result, Earliest(3) is true whereas others
are false, as shown in Fig. 2.11 (a). From Node 3, LCM checks whether
each node satisﬁes Delayed . As Node 4 satisﬁes Comp, Node 6 does notsatisfy Delayed . As a result, Delayed (3), Delayed (4), and Delayed (5) aretrue. Finally, the nodes satisfying Latest are Nodes 4 and 5, as shown in
Fig. 2.11 (b).
End of Example.
28

Chapter 2. Background: Earliest: Latest

1

1

3
4 x=a[i]235

4 x=a[i]26 y=a[i]56 y=a[i]

7

7

(a)

(b)

Figure 2.11: Insertion candidates. (a) Earliest. (b) Latest.

LCM inserts expressions at the entry of nodes n satisfying the predicate Insert(n), where node n also satisﬁes Latest(n). Notice that LCM
does not insert expressions without decreasing the number of executed expressions on some paths because such insertions are unnecessary. In order
to exclude the unnecessary insertions, LCM speciﬁes them based on thepredicate Isolated (n) that denotes that the insertion at n does not result
in removing any expression other than original one; therefore, Insert(n) is
deﬁned as Latest(n) ∧ ¬Isolated (n). After insertions at the entry points ofnodes n satisfying Insert(n) are performed, the original expressions at nodes
n satisfying the predicate Replace(n) that denotes that n contains an e are
replaced with the temporary variable holding the value of the expression.
These predicates are deﬁned as follows:
Deﬁnition 2.2.4 (Translation of the Program).
Isolated (n)

def

⇔

∏

Latest(s) ∨ ¬Comp(s) ∧ Isolated (s)s∈succ(n)Insert(n)Replace(n)def⇔Latest(n) ∧ ¬Isolated (n)defComp(n) ∧ ¬(Latest(n) ∧ Isolated (n))⇔

Example.
As shown Fig. 2.12 (a), Isolated (4) and Isolated (5) are false. This result
indicates that insertions to these nodes are useful for removing redundancy.
29

Chapter 2. Background: Isolate

1

1

3

3

4’ t=a[i]4 x=a[i]

2

6

5

2

4 x=t

y=a[i]

5 t=a[i]

6 y=t

7

7

(a)

(b)

Figure 2.12: Translated program. (a) Isolate. (b) Result of applying LCM.

Finally, LCM inserts a statement t=a[i] with the temporary variable t thatis unique for the expression at Nodes 4 and 5, and then replaces the original
a[i] with t, as shown in Fig. 2.12 (b). Here, LCM assumes that each CFG
node has only one instruction, and LCM makes a new CFG node 4’ for theinserted t=a[i] at Node 4.
End of Example.

30

Chapter 3

Eﬀective Demand-driven
PRE
In this chapter, we describe the algorithm of eﬀective demand-driven PRE(EDDPRE). Section 3.1 explains the motivation of EDDPRE. Section 3.2
describes a previous demand-driven PRE. Section 3.3 gives the detail of
EDDPRE. Section 3.4 shows experimental results to demonstrate the eﬀectiveness of EDDPRE. Section 3.5 and Section 3.6 summarize, respectively,
the related works and EDDPRE.

3.1

Motivation

Traditional PRE exhaustively analyzes the entire program based on dataﬂow equations, before transforming the program to remove all of the redundant expressions found during the analysis. The removal of the expressions
leads to some copy assignments; therefore, the application of copy propagation has the eﬀect of exposing new redundancies, which are known assecond-order eﬀects. To remove more redundant expressions by capturing
these eﬀects, it is necessary to repeatedly apply PRE and copy propagation.
To address the issue, a demand-driven PRE, PRE based on query propagation (PREQP) [80], is proposed. For each expression e, PREQP backwardly propagates a query to determine if e is available. An answer truemeans that e is available on the path on which the query was propagated
whereas false means that it is not. The query generated at the origin of e isduplicated at a join point that is a program point with several predecessors.
Consequently, in case where the answers at the join point are both trueand false, PREQP inserts expressions at nodes where false were obtainedin order to make e available. After the insertion, PREQP replaces e withan introduced temporary variable, and then PREQP applies demand-driven
copy propagation. Although this copy propagation can reveal some new redundant expressions, applying it for all expressions sometimes incur greater
31

Chapter 3. Effective Demand-driven PRE

costs than exhaustive PRE. In addition, the query may sometimes be propagated unnecessarily in order to check the redundancy of an expression, even
if the expression is not redundant on some execution paths, as explained in
the next section.
In this chapter, we propose EDDPRE to suppress unnecessary copy
propagation and query propagation. First, EDDPRE applies global value
numbering (GVN) in order to statically detect redundant expressions thatare lexically diﬀerent expressions for disuse of copy propagation. During
GVN, EDDPRE records occurrences of the value numbers into tables at
each CFG node. For each expression, EDDPRE propagates a query thatchecks whether the value number of the inquired expressions is available ornot. This query is propagated to each node while a value number of theinquired expression is recorded in the value number occurrence table.
The advantages of EDDPRE are summarized as follows:• EDDPRE can capture many second-order eﬀects without copy propagation and iterative applications of whole algorithm.
• EDDPRE suppresses unnecessary query propagations by recording theoccurrence of value numbers on paths from the start node to the exitof each node.

3.2

PRE Based on Query Propagation

PREQP is applied to programs translated into SSA form. PREQP visitseach CFG node that represents a basic block in topological sort order, andperforms query propagation [67] to check whether each expression e can beeliminated at the node. Before explaining the detail, we present an example
how PREQP removes the redundant expressions.
Example.
Consider the statement z1 =x1 +1 at Node 3 in Fig. 3.1 (a). The x1 +1
is redundant because there is the statement y1 =x1 +1 that has the same expression in the right-hand side immediately before it. PREQP replaces itwith y1 , and then PREQP applies copy propagation in order to capture thesecond-order eﬀect through replacing z1 with y1 . The copy propagation traverses Nodes 3, 4, 5, and 6 dominated by Node 3 while replacing z1 with y1 .
Remember here that the uses of each variable are dominated by the deﬁnition of it in SSA form. The copy propagation results in the program shownin Fig. 3.1 (b), where it is found that the right-hand side of a statement
j1 =y1 +1 is redundant. Then, PREQP is applied to the expression, so that
it is replaced it with i1 . After that, the copy propagation is applied again.
Consider the loop invariant expression x1 +2 at Node 5 shown in Fig.
3.2 (a). PREQP propagates a query ”is x1 +2 available?” to the predecessor

32

Chapter 3. Effective Demand-driven PRE

1 x₁=read()

1 x₁=read()

2

2

3

4

y₁=x₁+1z₁=x₁+1
i₁=y₁+1
j₁=z₁+13i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,j₁)

4

y₁=x₁+1z₁=y₁
i₁=y₁+1
j₁=y₁+1i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,j₁)

5

a₁=x₁+2i₃=i₂+1
j₃=j₂+15

a₁=x₁+2i₃=i₂+1
j₃=j₂+16

b₁=x₁+36

b₁=x₁+3(a)(b)

Figure 3.1: Eﬀect of PREQP’s removing redundant expression and applying
copy propagation. (a) Original program. (b) After removing x1 +1 at Node3.

4. There is no expression in Node 4; therefore, the query is further propagated to two predecessors 3 and 5. Following this, the query propagatedto Node 3 is further propagated to Nodes 2 and 1 in this order. However,
the expression is not found, so that the answer false is returned to Node
4. By contrast, the query propagated to Node 5 obtains the answer true
because x1 +2 itself is found at Node 5. The two answers true and false meanthat x1 +2 is partially available at Node 4. In this case, PREQP makes it
available by inserting a statement t1 =x1 +2 into Node 3, where traditionalPREs check down-safety. However, PREQP ignores the down-safety in thecase where the query is propagated to the inquired expression itself, so thatloop invariant expressions are speculatively moved out of the loop, even if
the down-safety is not satisﬁed. Consequently, the answer true is returned
to Node 5; therefore, x1 +2 is determined to be redundant. Finally, x1 +2 isreplaced with t1 , as shown in Fig. 3.2 (b).
When a query is propagated over a ϕ function that deﬁnes some operandsof the inquired expression, the operands are replaced with arguments corresponding to predecessors where the query is propagated. For example,
33

Chapter 3. Effective Demand-driven PRE

1 x₁=read()
1 x₁=read()
2
2

3

4

y₁=x₁+1z₁=y₁
i₁=y₁+1j₁=i₁

3

i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,i₁)
5

a₁=x₁+2i₃=i₂+1
j₃=j₂+16

b₁=x₁+3

4
Is x₁+2 redundant?

(a)y₁=x₁+1z₁=y₁
i₁=y₁+1
j₁=i₁
t₁=x₁+2i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,i₁)
5a₁=t₁
i₃=i₂+1
j₃=j₂+16

b₁=x₁+3(b)

Figure 3.2: Eﬀect of PREQP’s query propagation. (a) Example of propagating a query. (b) Result program of applying PREQP

consider a query regarding i2 +1 at Node 5. The query is propagated to
Nodes 3 and 5 over a ϕ function i2 =ϕ4 (i3 ,i1 ) after Node 4. In this situation, two new queries ”Is i1 +1/i3 +1 available?” are generated for Nodes 3
and 5, respectively. We call this replacement ϕ function replacement.
If a query is propagated twice to a node without ϕ function replacement
in a loop, the answer true should be returned for the maximum ﬁxed pointof the data-ﬂow equations. However, this rule may lead to unnecessary code
motion passing some empty loops. For example, in Fig. 3.2 (a), consider thata query regarding x1 +2 is propagated from Node 2 to Node 2 through theback edge. If it is simply assumed that the second visit to Node 2 returns
an answer true, an expression would be inserted into Node 1 because ananswer false is returned from Node 1. However, as mentioned above, theexpression should be inserted into Node 3; therefore, inserting it into Node1 unnecessarily extends the live-range of an introduced temporary variable.
To suppress the unnecessary insertion, PREQP deﬁnes a predicate isReal
to indicate that the answer true is derived from the fact that the query has

34

Chapter 3. Effective Demand-driven PRE

reached a real expression. Insertions are allowed only if isReal is true. Thus,
the insertion into Node 1 is suppressed because isReal s at Nodes 1 and 2
are false, so that, false is returned from Node 2.
End of Example.
These observations lead to formal deﬁnitions of the answer of a query in
PREQP. In this deﬁnition, e represents an inquired expression. Once a queryis propagated to a node, PREQP determines the answer at the entry of anode under the predicate NAnswer . As mentioned above, NAnswer is true
if one of the following two conditions is satisﬁed: 1) all answers are obtained
as true from predecessors, or 2) expressions are inserted into predecessors,
where the second condition is denoted by Insertable. In addition, PREQP
represents the answer at the exit of a node as XAnswer , which is deﬁned
using Local that denotes some occurrences the expression in the node. The
N /XAnswer and Local are formally described as follows:
Deﬁnition 3.2.1. When a query is propagated to a node n, the answer isdeﬁned as follows:def

XAnswer (e, n) ⇔ (n ̸= start) ∧(Local (e, n) ∨ Transp(e, n) ∧ NAnswer (e, n))(3.1)
defNAnswer (e, n) ⇔ Insertable(e, n) ∨∏XAnswer (transPhi (e, p, n), p)(3.2)
p∈pred(n)where Transp(e, n) indicates transparency that means no operands of e isdeﬁned at n, and transPhi performs ϕ function replacement. transPhi (e, p, n)
replaces each operand of e with a ϕ function’s relevant argument that corresponds to predecessor p if n contains the ϕ function.
Deﬁnition 3.2.2 (Rules of the local answer for a query). Local (e, n) is
deﬁned by the following rules, which are checked when a query is propagatedto node n:(1) If n is a node where the query has already been propagated, and thecurrent query is same as the previous one, the answer is true.
(2) If n is a node where the query has already been propagated, and thecurrent query is diﬀerent from the previous one, the answer is false.
(3) If n is the original node of the query, and the original query is also thesame as the current query, both the answer and isSelf (e, n) are true
where isSelf indicates that the query has been propagated back to theoriginal location of inquired expression.
(4) If n is a node where e occurs in n, both the answer and isReal (e, n) are
true.
35

Chapter 3. Effective Demand-driven PRE

Rule (2) takes account of the situation where some operands of the expression are changed, so that the current value is diﬀerent from inquired
expression. In this situation, the answer false should be returned. Other
rules correspond with the above explanation.
Insertable gives the details of the condition for insertions. As mentioned
above, if answers true and false are returned to a node where isReal anddown-safety are true, expressions are inserted into predecessors that had
returned false. Note here that, the down-safety condition is ignored for aloop invariant expression in order to promote speculative code motion outof a loop. The loop invariant expressions are identiﬁed through a predicate
isSelf . These conditions are formally described as follows:
Deﬁnition 3.2.3 (Insertion condition).
∑def

isReal (e, n) ⇔ e occurs in n ∨isReal (e, p)(3.3)

p∈pred(n)∑defisSelf (e, n) ⇔ the original expression of e is in n ∨defInsertable(e, n) ⇔∑isSelf (e, p)p∈pred(n)isReal (e, p)p∈pred(n)∧ (DownSafe(e, n) ∨∑isSelf (e, p)) (3.4)

p∈pred(n)PREQP also checks down-safety through query propagation. The answer
depends on transPhi and Local . However, Local ignores rule (3) in the query
propagation. This deﬁnition is presented in that of DownSafe.
Deﬁnition 3.2.4 (Down-safety based on query propagation). Down-safety
is deﬁned with performing the replacement of a variable deﬁned by a ϕ function with a suitable argument.
∏

def

DownSafe(e, n) ⇔ (n ̸= end) ∧Local (e′ , s) ∨s∈succ(n)Transp(e′ , s) ∧ DownSafe(e′ , s) (3.5)
where e′ = transPhi (e, n, s)
After inserting expressions, PREQP inserts a ϕ function if NAnswer istrue and the size of the node’s pred is more than 1.
Example.
As mentioned above, the application of PREQP to the program in Fig.
3.2 (a) causes copy propagation twice. Because the copy propagation basedon SSA form checks all of the nodes dominated by a node containing the36

Chapter 3. Effective Demand-driven PRE

deﬁnition and the dominance frontiers of them; therefore, Nodes 3, 4, 5, and6 are checked twice.
Consider the expression j2 +1, which is redundant because the expression computes the same value as i2 +1. However, PREQP cannot eliminate
the expression because the query of PREQP pessimistically ﬁnds equality
between expressions. When a query regarding j2 +1 is propagated to Nodes
3 and 5 from Node 4, the new queries j1 +1 and j3 +1 are generated. These
expressions cannot reach any same expression through the further propagation. Finally, considering the expression x1 +3 that is not redundant, thefact cannot be found without propagating a query to Node 1 through all thenodes.
End of Example.
Compared with the traditional PRE technique based on data-ﬂow analysis, PREQP can improve the analysis eﬃciency for many programs because
it eﬃciently captures many second-order eﬀects by repeating the redundancy
elimination and copy propagation processes within limited program regions
without analyzing the entire program. In some programs, however, the analysis eﬃciency of PREQP can be worse than the traditional PRE because
the nodes traversed during the copy propagation and query propagation in
PREQP still include many nodes not contributing to the ﬁnal result.

3.3

Eﬀective Demand-driven PRE

In this section, we provide the details of EDDPRE. At the beginning, we
describe an overview of EDDPRE’s algorithm, and then, we present thedetails of each steps with pseudo code.

3.3.1

Algorithm Overview

EDDPRE consists of the following two steps:
1. Optimistic GVN
This step identiﬁes the same expressions by assigning value numbers for them. The value numbers can be managed by a hash-tablevalueTable where expressions with the same value number can be assumed to be expressions generating the same value, even if their lexical
forms are diﬀerent. In addition to the hash-table, for each CFG node,
GVN creates two tables: a local value occurrence table and a path value
occurrence table. The local value occurrence table of node n records
value numbers occurred in n. The path value occurrence table of anode n manages the occurred value numbers on all paths from thestart node to the exit of n. This path value occurrence table is used toquickly know the preceding occurrence of inquired expression without
37

Chapter 3. Effective Demand-driven PRE

query propagation. In addition, EDDPRE can optimistically assigns
value numbers to ϕ functions with cyclic dependence inside a loop,
which contributes to detecting the same expressions with induction
variable.
2. Redundancy Removal
In this step, redundant expressions are removed through query propagation and transformation. Query propagation is carried out for each
expression in topological sort order. Once the query propagation for
expression e results in true, insertion points are determined. During
the transformation, suitable expressions and ϕ functions carrying theirvalues are inserted. Finally, if e is fully redundant, it is replaced withthe variable containing the value of the available expressions. Notethat EDDPRE speculatively inserts expressions only if e is a loop invariant expression as well as PREQP.

3.3.2

Optimistic Global Value Numbering

GVN traverses the dominator tree in depth-ﬁrst and left-ﬁrst search. Oncean expression has been visited, GVN assigns a value number to it. The value
number of the expression can be obtained through the hash-table valueTable
by using a variable name or a tuple of an operator and value numbers ofoperands as a key. The value number of an operand can also be obtained
from valueTable by using the operand’s variable name as a key. If the same
tuple has already existed in valueTable, the expression is assigned to thevalue number; otherwise, the expression is assigned to a new value numberthat is recorded in the hash-table, using the tuple as a key. If the expression
is on the right-hand side of an assignment, the variable on the left-hand side
is assigned to the same value number. GVN assumes that every function
call returns a diﬀerent value; therefore, each variable deﬁned by a function
call is assigned a diﬀerent value number.
EDDPRE assumes that the child nodes of each node in the dominator tree are sorted in topological sort order. To assign value numbers toarguments of ϕ functions as many as possible before assigning value numbers to the ϕ functions, GVN should traverse in topological sort order in
CFG. Traversing the dominance tree in depth-ﬁrst and left-ﬁrst search canbe proven to correspond with the topological sort order in the CFG throughlemmas 1 and 2, where we assume that ni and nj are two arbitrary childrenof node n in the dominance tree, and that Ni and Nj are the subtree nodesets that include the ni and nj as roots in the dominance tree, respectively.
Fig. 3.3 depicts the relation between the subtrees of node n.
Lemma 1. njd is nj if there is an edge (nis , njd ) in the CFG where nodes
nis and njd are included in Ni and Nj , respectively.
38

Chapter 3. Effective Demand-driven PRE

dominator tree edge
CFG edge
1

2

n

ni

r

nj njd

k nis
Ni

Nj

Figure 3.3: Proof of equality between traversals of topological sorted dominance tree in depth-ﬁrst and left-ﬁrst search and a topologically sorted CFG.
We assume 2 < k < r.

Proof . If we assume that njd is not nj , njd is included in the subtree
that has one of the children of nj as a root. nis is not dominated by nj ;therefore, some paths do not include nj from the start node to njd throughedge (nis , njd ) in the CFG. This contradicts the fact that njd is dominatedby nj .
Lemma 2. ∀ nia ∈ Ni precedes ∀ nja ∈ Nj in the topological sort order in
the CFG if ni precedes nj in the topological sort order in the CFG.
Proof . Assume that Nj includes a node njs preceding nid ∈ Ni whenni precedes nj . At this time, there is an edge from njs to nid in the CFG;
therefore, njs precedes ni according to the lemma 1. In addition, consideringthat ns dominates njs , nj precedes njs in the CFG. As a result, because ni
precedes nj , This contradicts the assumption.
Lemma 2 suggests that the depth-ﬁrst and left-ﬁrst search order in thedominator tree corresponds to one of the topological sort orders of CFG if
children of each node in the dominator tree has been sorted in the topologicalsort order of CFG.
For an acyclic CFG, the traversal can determine value numbers of all
expressions. By contrast, for a general CFG with some cycles, the value
numbers of several ϕ functions may not be determined in case where theirarguments are deﬁned in the bodies of loops. Assume a ϕ function pn witharguments nvargs, the value numbers of which have not yet been determined, is found at node n. In such cases, in general, the nvargs should beconservatively assumed to have diﬀerent value numbers. However, if all the39

Chapter 3. Effective Demand-driven PRE

1 x₁=read()

1 x₁=read() [1]

2

2

3

4

y₁=x₁+1z₁=x₁+1
i₁=y₁+1
j₁=z₁+13i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,j₁)

4

y₁=x₁+1z₁=x₁+1
i₁=y₁+1
j₁=z₁+1

[3]
[3]
[4]
[4]

i₂=φ₄(i₃,i₁) [11]j₂=φ₄(j₃,j₁) [11]5a₁=x₁+2i₃=i₂+1
j₃=j₂+15

a₁=x₁+2i₃=i₂+1
j₃=j₂+1

[7]
[12]
[12]

6

b₁=x₁+36

b₁=x₁+3

[10]

(a)

(b)

Figure 3.4: Eﬀect of optimistic value numbering. (a) Original program. (b)A result of GVN that is carried out on the dominator tree.

predecessors corresponding to nvargs are dominated by n, GVN optimistically assigns the same temporary value number 0 to all nvargs, and thencontinues value numbering for the sub-dominator tree of n. Once GVN has
been completed for the subtree, the value numbers of the nvargs have been
determined; therefore, the value number of pn can be also determined. At
this time, the ϕ functions to which the same value number has been optimistically assigned may be partitioned into diﬀerent value numbers. In thiscase, GVN is once again applied to the subtree of n. The optimistic GVN
guarantees the assignment of correct value numbers in at most two traversals a ϕ function. Notice there that the repeated traversals are limited to
the nodes dominated by the ϕ function.
Example.
Given a dominator tree for the CFG in Fig. 3.4 (a), GVN traverses thedominator tree, shown in Fig. 3.4 (b), using the depth-ﬁrst and left-ﬁrst
search. Node 1 is visited ﬁrst, and the expressions in the node are assigned
value numbers. After that, Nodes 2, 3, and 4 are processed as well in thisorder. In Node 3, variables i1 and j1 are assigned the same value numbers,
and then the ϕ functions are assigned value numbers in Node 4. In this case,although arguments i3 and j3 have not yet been assigned value numbers,

40

Chapter 3. Effective Demand-driven PRE

optimistic GVN can be applied to the ϕ functions through assigning thesearguments the temporary value number 0 because the unprocessed Node 5of the predecessors corresponding to the arguments is dominated by Node
4. Once value numbers are assigned to statements of Nodes 4, 5, and 6,
the ϕ functions are assigned value numbers once again. Finally, expressions
are assigned value numbers as shown in Fig. 3.4 (b). In the ﬁgures of thisthesis, we present each value number as a bracketed number. Note thatthe constant values 1 and 2 are also assigned value numbers [2] and [6],respectively.
End of Example.
For each node n, after assigning value numbers to all expressions includedin n, these value numbers are recorded in a local value occurrence table ofn. Moreover, for each CFG node n, GVN creates a path value occurrencetable that is deﬁned as the union of the local value occurrence table of n
and the path value occurrence table of predecessors of n.

Pseudo Codes
The GVN algorithm is shown in Programs 3.1, 3.2, 3.3, and 3.4. Program
3.1 deﬁnes functions for the traversal of a dominator tree and the value
numbering of statements. Program 3.2 deﬁnes functions for assigning a value
number to each statement with hash-table valueTable. Program 3.3 deﬁnes
two functions for checking whether optimistic value numbering should be
performed and checking whether the result is correct. Program 3.4 shows afunction for making a path value occurrence table for each CFG node.
At the beginning, the function globalValueNumbering is called to perform GVN. This function initializes a global variable value to generate a
new value number when a new entry is added into valueTable. After the
initialization, to traverse each node, it calls the function traverseDomTree.
Finally, it calls function makePathValueTable to make path value occurrencetables. traverseDomTree(n, optimistic) calls the function numbering to assign a value number to each expression included in n ﬁrst. If optimisticof the arguments is true, value numbers are optimistically assigned to theexpressions. After the value numbering for the visiting node n, this function checks whether value numbers are optimistically assigned to ϕ functionsin the n’s children nodes by function checkPhiArg deﬁned in Program 3.3.
When the optimistic value numbering is performed, checkPhiVal is called
for checking correctness of optimistic value numbering.
numbering assigns a value number to each ϕ function, each variableassigned the return value of a function call, and each expression. These
expressions are identiﬁed by functions isPhi , isFunc, and isExp. If theargument optimistic is true, for checking the correctness of optimistic value
numbering, ϕ functions are recoded into table samePhis.

41

Chapter 3. Effective Demand-driven PRE

Program 3.1 (Traversing of GVN)
Function: globalValueNumbering()
1: Initialize a global value value.
2: Call traverseDomTree(root, false) to visit the dominator tree.
3: Call makePathValueTable() to make path value occurrence tables.
Function: traverseDomTree(n, optimistic)// Arguments: n is a node of dominator tree. optimistic represents//
whether the optimistic GVN is performed.
4: Perform value numbering to n by numbering(n, optimistic).
5: for each child kid of n in depth-ﬁrst and left-ﬁrst search.
6: if (checkPhiArg(kid))
7:
Perform optimistic GVN by traverseDomTree(kid, true).
8:
Check correctness of the optimistic GVN by checkPhiVal (kid).
9: else10:
Call traverseDomTree(kid, optimistic).
Function: numbering(n, optimistic)// Arguments: n is a node of dominator tree. optimistic represents//
whether the optimistic GVN is performed.
11: for each statement st of n.
12: if (isPhi (st) ∨ isFunc(st) ∨ isExp(rhs(st)))13:
Get a value number val of st by value(st).
14:
if (optimistic ∧ isPhi (st) ∧ val is assigned to another ϕ function)
15:
Record lhs(st) in table samePhis for using in function checkPhiVal .
16:
Record (val, lhs(st)) in the local value occurrence table.
Assigning a value number to a statement st is performed in function
value(st) deﬁned in Program 3.2. If st is a trivial assignment, this function returns a value number of the right-hand side of st. Notice that theright-hand and left-hand sides of a statement are represented by rhs(st)and lhs(st), respectively. If st is a function call, value generates a newvalue number for st and returns the value number. Otherwise, the function translates each operand of expression or argument of ϕ function in thestatement into its value number at line 5, which is used to determine thevalue number of the statement. When a new value number is assigned to st,
newValue increments the global variable value, and adds the value number
with the expression as a key to valueTable before returning the value number. valueTable is used for getting the value number of an expression if it
includes an entry for the expression, as shown in function getValue.
Program 3.3 shows functions checkPhiArg and checkPhiVal that determine whether the optimistic value numbering is performed, and checks correctness of the optimistic value numbering, respectively. checkPhiArg checks
whether each argument of the ϕ function has already been assigned a value

42Chapter 3. Effective Demand-driven PRE

Program 3.2 (Assigning value numbers)
Function: value(st)// Arguments: st is a statement.
// Return value: a value number of st.
1: if (st is a trivial assignment) return getValue(rhs(st))
2: if (isFunc(st)) return newValue(lhs(st))
3: if (isPhi (st) ∧ all value numbers of the arguments are same)
4: return the value number
5: Make ve by changing each operand of rhs(st) to its value numbers.
6: return getValue(ve)Function: newValue(exp)// Arguments: exp is an expression.
// Return value: a value number of st.
7: Increment value.
8: Record (exp, value), exp is a key of value, in hash-table valueTable.
9: return value
Function: getValue(ve)// Arguments: ve is an expression whose operands are changed to//corresponding value numbers.
// Return value: a value number of ve.
10: if (ve is recorded in valueTable as a key) return valueTable.get(ve)11: else return newValue(ve) // Assign a new value number to ve.
number. If some arguments have no corresponding value number, and ndominates the predecessors corresponding to the arguments, the arguments
are assigned the temporary value number 0. If n does not dominate thepredecessor, checkPhiArg returns false and assigns a new value number tothe ϕ function in a conservative manner.
The function checkPhiVal returns true if some ϕ functions are assigned
the same value number as some entries recorded in samePhis that is deﬁned
in function numbering of Program 3.1. Otherwise, it returns false after
deleting the ϕ function in samePhis because the ϕ function needs to be
assigned to a diﬀerent value number.
After completing value numbering, EDDPRE creates a path value occurrence table for each node by calling makePathValueTable shown in Program
3.4. Remember that this function uses CFG nodes rather than dominatortree. This function uses a stack worklist to manage nodes. If there are somenodes in the worklist, a node n is popped, and then n’s path value occurrence table is made. Whenever a value number is added into the path value
occurrence table, the successors of n are pushed to worklist. The process isrepeated until there is no node in the worklist.

43

Chapter 3. Effective Demand-driven PRE

Program 3.3 (Determine whether optimistic value number is performed and test its correctness)
Function: checkPhiArg(n)// Arguments: n is a node of dominator tree.
// Return value: Decision of whether the optimistic GVN is performed.
1: let ans := false
2: for each ϕ function phi included in n
3: for each argument arg of phi
4:
if (valueTable records the value number of arg as a key) continue
5:
if (n dominates the corresponding predecessor)
6:
Record (arg, 0) in hash-table valueTable.
7:
ans := true
8:
else
9:
for each argument zarg that is assigned a value number 0 of phi
10:
if (valueTable.get(zarg) = 0)
11:
Remove the tuple of zarg from valueTable
12:
return false
13: return ans
Function: checkPhiVal (n)// Arguments: n is a node of dominator tree.
14: for each ϕ function phi included in n
15: Get a value number v of phi by value(phi).
16: Record (v, lhs(st)) in the local value occurrence table.
17: Get a ϕ function p included in samePhis corresponding to lhs(st).
18: if (v is diﬀerent from a value number of p)
19:
traverseDomTree(n, true)
Program 3.4 (Make path value occurrence table)
Function: makePathValueTable()// Note: this function is performed on CFG.
1: let worklist := {succ(start)}
2: while worklist ̸= ∅3: Get a node n by pop from worklist.
4: Let size be a size of n’s path value occurrence table pvot.
5: Add value numbers of n’s local value occurrence table into pvot.
6: for all p ∈ pred (n)7:Add value numbers of p’s path value occurrence table into pvot.
8: if (size ̸= the size of pvot)
9:
worklist.push(succ(n))

3.3.3Query Propagation

In this section, we explain how query propagation of PREQP is extended
to EDDPRE. EDDPRE propagates a query that checks if some expressions
44

Chapter 3. Effective Demand-driven PRE

1 x₁=read()
1 x₁=read() [1]

2
2

3

4

y₁=x₁+1z₁=y₁
i₁=y₁+1
j₁=i₁

[3]
[3]
[4]
[4]

3

i₂=φ₄(i₃,i₁) [11]j₂=φ₄(j₃,j₁) [11]5a₁=x₁+2i₃=i₂+1
j₃=j₂+1

[7]
[12]
[12]

6

b₁=x₁+3[10]4i₂=φ₄(i₃,i₁)
j₂=φ₄(j₃,j₁)

Is [7] redundant?

(a)y₁=x₁+1z₁=y₁
i₁=y₁+1
j₁=i₁
t₁=x₁+25a₁=t₁
i₃=i₂+1
j₃=i₃

6

b₁=x₁+3(b)

Figure 3.5: Eﬀect of EDDPRE’s query propagation. (a) Original program.
(b) A result program.

have the same value number as e at each node. Before explain the detail ofextension, we show how query propagation of EDDPRE is carried out.
Example.
Consider the loop invariant expression x1 +2 with value number is [7] at
Node 5 in Fig. 3.5 (a). EDDPRE propagates a query ”is [7] available?” to apredecessor Node 4. There is no expression in Node 4 with value number [7];therefore, the query is further propagated to two predecessors Nodes 3 and5. Following this, the query propagated to Node 3 is further propagated to
Nodes 2 and 1 in this order, and then the answer false is returned to Node
4 as well as PREQP. By contrast, the query propagated to Node 5 obtains
the answer true because x1 +2 itself is found at Node 5. The two answers
true and false mean that x1 +2 is partially available at Node 4. Similar to
PREQP, EDDPRE makes it available by inserting the statement t1 =x1 +2
into Node 3 without checking its down-safety. Finally, EDDPRE replacesx1 +2 with t1 , as shown in Fig. 3.5 (b).
Although PREQP performs a copy propagation for the replaced expression in order to change lexical representation of some expression, EDDPRE
disuses copy propagation because of checking value numbering. Further-45

Chapter 3. Effective Demand-driven PRE

more, for the expression x1 +3 at Node 6, the ﬁrst occurrence of the value
number is Node 6; therefore, Node 5’s path value occurrence table does notcontain the value number. That is, EDDPRE results in false as soon as
propagating a query to only the predecessor Node 5 whereas PREQP has topropagate a query to all the nodes.
End of Example.
To achieve this extension, EDDPRE redeﬁnes predicts, XAnswer , isReal ,DownSafe, and Local , as follows:
Deﬁnition 3.3.1. XAnswer of equation (3.1) and isReal of equation (3.3)
are extended for checking value numbers and ignoring transparency as follows:def

XAnswer (e, n) ⇔ (n ̸= start) ∧ (Local (e, n) ∨ NAnswer (e, n))
(3.6)
∑
def
isReal (e, n) ⇔ a value number of e occurs in n ∨isReal (e, p)p∈pred(n)Because EDDPRE checks occurrences with the same value as inquired
expression, the answer XAnswer is changed to ignore transparency that isused in checking the lexical equality.
Deﬁnition 3.3.2 (Down-safety of EDDPRE). DownSafe of equation (3.5)
is also extended to check value numbers as follows:∏
def
DownSafe(e, n) ⇔ (n ̸= end) ∧Local (e′ , s) ∨ DownSafe(e′ , s)s∈succ(n)where e′ = transPhi (e, n, s)Deﬁnition 3.3.3 (Rules for the local answer to a query). Local (e, n) is
redeﬁned for checking occurrence of e’s value number by the following rules,
which are checked when a query is propagated to node n:(1) If n is a node where the query has already been propagated, and thevalue number of the current e is same as the previous one, the answer
is true.
(2) If n is a node where the query has already been propagated, and thevalue number of the current e is diﬀerent from the previous one, theanswer is false.
(2’) If n is a node where no value number of the query occurred on any pathfrom the start to the exit of n, and the value number is not dependent
on the ϕ function, the answer is false.
(3) If n is the original node of the query, and the original query is also thesame as the current query, both the answer and isSelf (e, n) are true.
46

Chapter 3. Effective Demand-driven PRE(4) If n is a node where the value number of e has been recorded in its local
value occurrence table, both the answer and isReal (e, n) are true.

Pseudo Codes
To perform query propagation of EDDPRE, EDDPRE calls the function
eliminate shown in Program 3.5. For each expression, the function analyzes
local redundancies by localMap recording value numbers for occurrences atthe current node ﬁrst. If the expression is locally redundant, it is replacedwith a variable holding the same value. Otherwise, it calls function propagate
to propagate a query after calling the function initialize for initializing the
global tables that are used to record expressions and value numbers in query
propagation. If the expression is redundant, it is replaced with the suitablevariable.
We describe the pseudo code of propagate in Program 3.6. propagate
determines an answer at the entry of node n after propagating queries topredecessors. Lines 2–4 perform the preparation for propagating a new queryto the predecessors. transPhi of equation (3.2) is applied at line 2, and nep
is then introduced to hold the return value. After obtaining the new query
nep , a new value number of nep is determined at line 3, and the query isthen recorded in order to insert an expression into some predecessors at line
4. At line 5, function local is called to obtain an answer that corresponds
to XAnswer . Following propagations to all predecessors, the answer for n
is determined by the answers obtained from its predecessors under equation(3.2). If the answer of this node is true, PRESR inserts expressions into thepredecessors where the answers are false, and then inserts the ϕ function.
Function local corresponds to equation (3.6).
Program 3.5 (Analysis redundancy)
Function: eliminate()
1: for each CFG node n in toporogical sort order
2: Make a local occurrence map localMap
3: for each statement st of n4:
if (¬isExp(rhs(st))∨ st is a trivial assignment) continue
5:
Get a value number val of st by value(st).
8:
if (localMap.containsKey(val))
9:
let predVar := localMap.get(val)10:
Replace rhs(st) with predVar .
11:
else
12:
Put (val, lhs(st)) into localMap.
12:
Initialize global tables used during propagating a query.
13:
Let originalN be n.
15:
if (propagate(rhs(st), n))16:
Replace rhs(st) with the introduced temporal variable.

47

Chapter 3. Effective Demand-driven PRE

Program 3.6 (Query propagation)
Function: propagate(e, n)// Arguments: The inquired expression e, and visiting CFG node n.
// Return value: A tuple of isAvail , isReal , and isSelf that denote the//answer of query at n, occurrence of e, and visited itself, respectively.
1: for each p ∈ pred (n)2: Make a new array reference nep by transPhi (e, p, n).
3: Determine a value number valp of nep .
4: Record nep in order to insert it at the exit of p later if it is necessary.
5: (isAvailp , isRealp , isSelf∏ p ) = local (valp , nep , p)
6: if (Insertable(e, n) ∨ p∈pred(n) isAvailp ) // equation (3.2)
7: Insert nep made at line 4 into predecessors whose isAvailp is false.
8: Insert a ϕ functionof n.
∑ into the entry∑
9: return (true, p∈pred(n) isRealp , p∈pred(n) isSelfp )10: else
11: return (false, false, false)
Function: local (val, e, n)// Arguments: The inquired expression e, and visiting CFG node n.
// Return value: A tuple of isAvail , isReal , and isSelf that denote the//answer of query at n, occurrence of e, and visited itself, respectively.
12: if (n is the start node) return (false, false, false)
13: if (condition of Rule (1) is satisﬁed) return (true, false, false)
14: if (condition of extended Rule (2) is satisﬁed) return (false, false, false)
15: Record val in order to check Rules (1) and (2)16: if (val is recorded in local value occurrence table of n)
17: if (n equals to originalN and e is same as the original expression)
18:
return (true, true, true) // Corresponding to Rule (3)19: else
20:
return (true, true, false) // Corresponding to Rule (4)21: else if (n’s path value occurrence table does not record val ∧¬dependPhi (e))// Corresponding to Rule (2’)
22: return (false, false, false)
23: else
24: return propagate(e, n)

3.4

Experimental Results

We implemented EDDPRE as a low-level intermediate representation converter using a COINS compiler [24]. To evaluate the beneﬁts of EDDPRE as
accurately as possible, we compared EDDPRE with PREQP and PRE*2,
which applies PRE twice and copy propagation once between them. We
used the machine with Intel Core i5-2320 3.00GHz as a CPU and Ubuntu
12.04 LTS as an OS.

48

Chapter 3. Effective Demand-driven PRE

Table 3.1: Execution time of objective code
Programs

A.PRE*2

B.PREQP

C.EDDPRE(A-C)/A(B-C)/B

equake69.1 sec

65.2 sec

65.5 sec

5.2%

-0.5%

art

35.7 sec

36.1 sec

33.6 sec

5.9%

6.9%

mcf

34.3 sec

33.7 sec

33.7 sec

1.7%

0.0%

bzip2

73.3 sec

77.3 sec

75.4 sec

-2.9%

2.5%

gzip

103 sec

100 sec

99 sec

3.9%

1.0%

ammp

119 sec

118 sec

120 sec

-0.8%

-1.7%

vpr

68.4 sec

72.2 sec

65.9 sec

3.7%

8.7%

parser102 sec

105 sec

104 sec

-2.0%

1.0%

twolf

110 sec

110 sec

108 sec

1.8%

1.8%

Table 3.2: Analysis time
Programs

A.PRE*2

B.PREQP

C.EDDPRE(A-C)/A(B-C)/B

equake1,949 msec

879 msec

677 msec

65.3%

23.0%

384 msec

423 msec

271 msec

29.4%

35.9%

art
mcf

998 msec

866 msec

374 msec

62.5%

56.8%

bzip2

1,018 msec

1,104 msec

745 msec

26.8%

32.5%

gzip

2,669 msec

1,952 msec

1,087 msec

59.3%

44.3%

ammp

10,959 msec

6,035 msec

3,532 msec

67.8%

41.5%

vpr

5,047 msec

4,574 msec

2,498 msec

50.5%

45.4%

parser

3,744 msec

3,945 msec

2,265 msec

39.5%

42.6%

twolf

36,012 msec

14,484 msec

10,546 msec

70.7%

27.2%

We evaluated the eﬀects of EDDPRE using three programs (equake, art,
and ammp) from CFP2000 and six programs (mcf, bzip2, gzip, vpr, parser,
and twolf) from CINT2000 in the SPEC benchmarks.
Table 3.1 shows the execution time results for PRE*2, PREQP, and
EDDPRE. Regarding PREQP and EDDPRE, most of the programs were
improved or matched when using EDDPRE. In particular, the eﬃciency ofart and vpr were improved by about 6.9% and 8.7%, respectively. EDDPRE
can eliminate more redundancies than PREQP because EDDPRE uses optimistic value numbering. However, compared with PRE*2, moving loop
invariant expression speculatively may decrease the execution eﬃciency aswell as PREQP.
Table 3.2 shows the analyzing time results for PRE*2, PREQP, and EDDPRE, all of which were improved by applying EDDPRE. In particular, theeﬃciency of twolf was improved by about 70.7% compared with PRE*2. The

49

Chapter 3. Effective Demand-driven PRE

Table 3.3: The time of query propagation
Programs

A.PREQP

B.EDDPRE(A-B)/Aequake661 msec

265 msec

59.9%

art

311 msec

74 msec

76.2%

mcf

667 msec

79 msec

88.2%

bzip2

837 msec

279 msec

66.7%

gzip

1,447 msec

260 msec

82.0%

ammp

4,516 msec

1,102 msec

75.6%

vpr

3,369 msec

773 msec

77.1%

parser

2,964 msec

753 msec

74.6%

twolf

10,662 msec

2,635 msec

75.3%

Table 3.4: The number of nodes which query propagatedPrograms

A.PREQP

B.EDDPREA-B

equake31,88437,328-5,444art

10,149

5,949

4,200

mcf

10,271

3,503

6,768

bzip2

37,71921,626

16,093gzip

43,167

18,84424,323

ammp

169,749

90,81578,934vpr

108,91764,48344,434parser

96,05653,48442,572

twolf

497,177

343,105

154,072

eﬃciency of mcf was also remarkably improved by about 56.8% comparedwith PREQP.
Furthermore, Table 3.3 shows the query propagation time results for
PREQP and EDDPRE, all of which were improved by applying EDDPRE.
In particular, the eﬃciency of mcf was remarkably improved by about 88.2%.
The number of nodes propagated by the queries using the two techniques
is shown in Table 3.4, where EDDPRE visited fewer nodes than PREQP
other than equake. PREQP does not generate queries for the expressions
with operands that are deﬁned in the node, whereas EDDPRE generates
queries for the expressions because EDDPRE does not consider the deﬁnition. Thus, it is possible to that EDDPRE generates more queries than
PREQP. However, the analytical eﬃciency of EDDPRE was better than
PREQP, as shown in Table 3.3, because the answers to queries are obtained
immediately for non-redundant expressions and EDDPRE does not need to50

Chapter 3. Effective Demand-driven PRE

apply copy propagation.

3.5

Related Work

The original PRE technique was proposed by Morel and Renvoise [57], whichuses bi-directional data-ﬂow analysis. This technique can eliminate someredundant expressions and move loop invariant expressions out of loops, butsome redundant expressions are not removed because the technique does notinsert expressions at not down-safe nodes.
In general, most PRE techniques increase the register pressure because
the live-range of variables are extended by inserting expressions. To suppress
the register pressure, a variant of PRE, LCM, was proposed [51, 52]. LCM
moves expressions as early as possible as the ﬁrst code motion, and thendelays the expressions as late as possible as the second code motion. The ﬁrst
code motion enables eliminating all of the removable expressions, and thesecond one enables minimizing the live-ranges of the variables. Bodik et al.
proposed another variant of PRE that eliminates all redundant expressions
by copying certain parts of the program [5]. However, the copying process
can change the reducible loops into irreducible loops. It is not possible
for this technique to be used with other optimization techniques that are
assumed to be applied to reducible program. For such a technique, thetranslation from an irreducible program into a reducible program may be
eﬀective, but tends to increase the program size. These PRE techniques need
to apply copy propagation repeatedly to catch second-order eﬀects. Kennedy
et al. proposed PRE on SSA, SSAPRE, which exploits the properties of the
SSA form [49]. SSAPRE produces a factored redundancy graph (FRG) for
each expression, and then applies PRE to the FRG, which decreases theanalyzing cost because of the sparse structure of the FRG. However, someredundancies are not eliminated because SSAPRE is based on the lexical
equality of expressions.
GVN was extended from the local approach by Rosen et al. [67]. The
GVN utilizes a hash-table to record the value numbers of each node. Expressions are moved up nodes to check whether the expression is recorded in thehash-table of the node, and then redundant expressions are eliminated. This
technique uses query propagation and the loop information to analyze fully
redundancy; therefore, it depends on the control ﬂow structure. Furthermore, the technique requires the iterative applications of copy propagation
repeatedly as well as PREQP. EDDPRE does not depend on any program
structure, and performs the analysis eﬃciently because it does not need touse the loop information and copy propagation. Alpern et al. proposed another GVN technique that uses partitioning on a dependence graph of SSA,
which is called value graph, to detect congruent expressions as candidates ofredundant expressions. Because their technique calculates congruent parti-

51

Chapter 3. Effective Demand-driven PRE

tions as maximal ﬂow points, it can detect congruent expressions with someinduction variables [3]. However, redundancy elimination techniques basedon their congruence cannot handle some redundant expressions eliminatedby traditional techniques because of the value graph structure including ϕfunctions. Ruthing et al. proposed a technique that canonicalizes the value
graph with regard to the ϕ functions to remove the structure constraint [69],but its analysis is costly. Nie and Cheng proposed a technique based on the
SSA form for sparse analysis, which eliminates as many redundant expressions as Ruthing’s technique [59]. Click proposed a technique that extended
Alpern et al.’s technique by moving loop invariant expressions out of theloops [21]. This technique requires the loop structure information because
it moves expressions downward without moving into the loop, after moving
upward speculatively.
Cooper and Xu proposed a technique that eliminates all of the fully redundant load instructions, which combined GVN with common sub-expression
elimination [26]. This technique handles the redundancies by assigning avalue number to a tuple with the operator of the store/load instruction
and the value number of the address. VanDrunen and Hosking proposeda technique that eliminates partially redundant expressions based on thevalue number based method [81]. This technique deﬁnes the availability
and anticipability based on value number, but needs to be repeatedly applied to eliminate all of the redundant expressions because it is not based on
the data-ﬂow equation of pure PRE. Odaira and Hiraki proposed the partial value number redundancy elimination (PVNRE) that combines GVN
and PRE [60]. PVNRE maps the value numbers of the ϕ function and its
arguments to another value number to eliminate lexically diﬀerent partial
redundancy. PVNRE deﬁnes that back edges are not transparent to prevent the movement of expressions with induction variables outside of theloop. The transparency of back edge means PVNRE is only applicable toprograms without any irreducible loop. By contrast, EDDPRE does notdepend on any control ﬂow structure, and enables moving loop invariant
expressions outside the loop speculatively.

3.6

Summary

In this chapter, we proposed a new eﬀective demand-driven PRE (EDDPRE)
that eliminates more redundant expressions than previous techniques by using optimistic value numbering and eﬀective query propagation and recording occurrences of the value numbers. To demonstrate its eﬀectiveness, weapplied EDDPRE to several benchmark programs, which showed that EDDPRE improved eﬃciency of the analysis in all cases and the execution
eﬃciency of generated object code in most cases.

52

Chapter 4

Demand-driven Scalar
Replacement
In this chapter, we describe the algorithm of PRE-based scalar replacement(PRESR). Section 4.1 explains the motivation for PRESR. Section 4.2 summarizes the related works. Section 4.3 deﬁnes array reference representation.
Section 4.4 gives the details of PRESR. Section 4.5 shows experimental results to demonstrate the eﬀectiveness of PRESR, and Section 4.6 summarizes
PRESR.

4.1

Motivation

PRE removes redundant expressions, and moves loop invariant expressions
out of loops. Traditional PRE lexically detects partially redundant expressions based on data-ﬂow equations, and then inserts expressions at suitable
points to make them fully redundant, thereby removing them. PRE is a
powerful code optimization technique; however, it poses two issues. First,
each application of PRE has the potential for exposing other redundant expressions; therefore, copy propagation must be performed to reveal theirlexical redundancy. The process tends to increase analysis costs. Second,
PRE cannot be applied across several loop iterations. This restriction does
not permit PRE to manage redundant expressions over some iterations, suchas array references with various induction variables as their indices.
To address the ﬁrst issue, we have proposed EDDPRE that is deﬁned in
Chapter 3. For each program represented in SSA form, EDDPRE applies
GVN, and then for each expression e, backwardly propagates a query to
determine if e is available in terms of its value number. An answer truemeans that e is available on the path on which the query was propagated
whereas false means that it is not. The query generated at the origin of e isduplicated every time it is propagated to a join point. Consequently, in casewhere the answers are both true and false, EDDPRE inserts expressions
53

Chapter 4. Demand-driven Scalar Replacementi₁=1
1 t₁=a[i₁]t₃=a[i₁-1]

i₂=φ₂(i₁,i₃)x₁=a[i₂-1]+12
a[i₂+1]=x₁
i₃=i₂+1t₄=φ₂(t₃,t₂)t₂=φ₂(t₁,x₁)i₂=φ₂(i₁,i₃)
2
x₁=t₄+1a[i₂+1]=x₁
i₃=i₂+1

3

3

1 i₁=1(a)(b)

Figure 4.1: Eﬀect of PRESR. (a) Original program. (b) After applying
PRESR.

with the value numbers derived from e at each node where a false wasobtained in order to make e fully redundant.
In this chapter, we address the second PRE issue by extending EDDPRE
in order to remove redundant array references across several iterations of aloop in a manner similar to scalar replacement [15, 16, 66]. We call thisextended EDDPRE PRESR. Compared to traditional scalar replacement
techniques, PRESR can remove redundant array references over iterations
with the following two features: 1) PRESR can be applied to any type of control ﬂow structure without altering any loop structure, including irreducibleloops, and 2) PRESR determines the most appropriate insertion points ina program through a single application. The ﬁrst feature is useful becausechanging program structures may increase its size and number of instructions, such as goto instructions. The second feature contributes to reducing
the number of instructions, such as trivial assignments and initializations.
PRESR propagates a query for each array reference. If the inquired arrayreference has some induction variables in its index, and the related query is
propagated to the deﬁnition of the variable, then the query is modiﬁed byreplacing the induction variables with the right-hand side of the deﬁnition.
This modiﬁcation enables a query to check previous iterations.
Example.
Consider the array reference a[i2 -1] at Node 2 in Fig. 4.1 (a). PRESR
backwardly propagates a query ”Is the value number of a[i2 -1] available?”
54

Chapter 4. Demand-driven Scalar Replacement

for the array reference from Node 2 to its predecessors, Node 1 and Node 2.
At this time, since there is a ϕ function that deﬁnes i2 and uses i1 and i3
as arguments at Node 2, queries regarding a[i1 -1] and a[i3 -1] are propagated to Nodes 1 and 2 as well as EDDPRE. Once the query is propagated to
Node 1, false is obtained as an answer. On the other hand, for the query regarding a[i3 -1] propagated to Node 2, the deﬁnition i3 =i2 +1 of i3 is foundat Node 2. Once a deﬁnition of an induction variable such as i3 has beenfound, the variable is replaced with the right-hand side of its deﬁnition– inthis case i2 +1 –to check availability in the previous iteration. Hence, a newquery regarding a[i2 ] is generated and continuously propagated. Furthermore, applying the same process to the a[i2 ] results in a query regarding
a[i2 +1] at Node 2. Because an array reference, a[i2 +1], identical to theinquired expression is found on the left-hand side of a statement at Node 2;
therefore, the query gets the answer true. Consequently, as both true andfalse are obtained at the predecessors of Node 2, a[i2 ] is found to be partially available at Node 2. In this case, to make it available, PRESR inserts
a statement t1 =a[i1 ] into Node 1, where the answer false was obtained.
Furthermore, to carry the value of x1 or t1 to the point where the query was
initiated, PRESR inserts a ϕ function t2 =ϕ2 (t1 ,x1 ) at the entry of Node 2.
Following the insertion, the answer of query a[i2 ] at Node 2 is found to betrue. Thus, once a query obtains an answer at a node, the answer is returnedto the successor node. Hence, true is returned through the back edge to thesuccessor 2. As a result, as well as the preceding process, true is obtainedat Node 2 for the initial query regarding a[i2 -1] following the insertion ofstatement t3 =a[i1 -1] into Node 1 and a ϕ function t4 =ϕ2 (t3 ,t2 ) into Node
2. The ϕ function contributes to carrying the value of a[i1 -1] or a[i2 +1].
Finally, PRESR replaces a[i2 -1] with t4 as a redundant array reference,as shown in Fig. 4.1 (b). Throughout this process, PRESR inserts compensation code, such as t1 =a[i1 ] and t3 =a[i1 -1], at the most suitable points
without checking the loop-nest level. Thus, PRESR can remove redundant
array references at any level in a nested loop, such as a2 [i2 -1] at Node 5
in Fig. 4.4.
End of Example.
The contributions of PRESR are summarized as follows:• PRESR uses only pure SSA form for removing array references to be
redundant in some iterations.
PRESR can be easily implemented and combined with other SSA
based optimization techniques in any compiler.
• PRESR can be applied to irreducible as well as reducible loops, andremoves redundant array references at any nest-level in a nested loop.

55

Chapter 4. Demand-driven Scalar Replacement

Because query propagation does not depend on control ﬂow structures, PRESR can be applied to programs that include some irreducible loops, which may be generated by aggressive optimizations[25], such as instruction aggregation [34] and removing redundant/dead expression[5, 6], apart from the single application of traditional
scalar replacements.
• PRESR detects redundant array references, simultaneously inserting
initializations for scalar temporaries, the insertion points suitable forwhich are globally determined as compensation code.
Traditional scalar replacement techniques ﬁrst detect redundant arrayreferences and then determine where to insert the compensation code.
PRESR inserts array references and ϕ functions as compensation code,
based on the answers returned from each query.
• PRESR removes redundant array references on demand.
It is known that demand-driven analysis of PRE is more eﬃcient than
exhaustive analysis techniques [78].

4.2

Related WorkIn this section, we compare PRESR with traditional scalar replacement andregister promotion studies, revealing the diﬀerences between them.

4.2.1

Scalar Replacement

Scalar replacement is a code optimization technique that removes reusesof array references beyond loop iterations, to improve the eﬀect of register
allocation. The ﬁrst technique was proposed by Callahan et al. [15]. Theirtechnique detects redundancy by using a dependence graph; therefore, it isable to remove redundant array references included only in the innermost
loops that consist of only one basic block.
Carr and Kennedy extended the original technique to manage control
ﬂow by incorporating PRE [16]. This is one of the most general techniques
for scalar replacement; however, it includes an assumption regarding control
ﬂow that may limit its usefulness. The assumption is that this technique
can be applied only to the innermost loops which have to be reducible.
Rishi et al. proposed a scalar replacement based on array SSA form thatcan manage control ﬂow within and across loop iterations [66]. Their technique extended array SSA form, which is proposed in [33], to capture theavailability of previous iterations by inserting header ϕ nodes at loop headers. To insert the nodes, it is necessary to assume that every loop has only56

Chapter 4. Demand-driven Scalar Replacement

one incoming edge. Thus, their technique cannot remove array referencesthat are included in irreducible loops. Although irreducible loops can beconverted to reducible ones, the conversion process increases program size
and analyzing costs. In addition, their technique introduces scalar temporaries that contain the values of redundant array references and removes thearray references by replacing them with the temporaries. These processes
are performed on the original input program. The code to initialize thescalar temporaries is inserted in the loop preheader. After transforming the
program, the array SSA form must be reconstructed before any subsequent
phase that eliminates redundant memory instructions, because the array
SSA form depends on the occurrence of memory operations. These analyzing and transforming processes must be applied iteratively in each nestinglevel of the loop-nest tree beginning with the innermost loop, to remove all
redundant array references.
In contrast, the process of analysis and transformation programs used in
PRESR is comparatively simpler. If array references are determined to bepartially available at certain nodes, modiﬁed array references are inserted
in nodes that return false as a query answer. Because the propagation is
independent of the control ﬂow structure, array references can be inserted
in the most appropriate nodes over the entire program, e.g. moving loop
invariant array references out of loops over the several nesting levels of them.
In addition, PRESR inserts ϕ functions to capture diﬀerent values as well as
EDDPRE, because PRESR is performed on pure SSA form. The ϕ functions
can also enable reusing values across iterations. That is, PRESR does not
require inserting copy assignments in loop bodies, unlike traditional scalarreplacement techniques. This process can also be applied to irreducible loops
as well as reducible loops without transforming loop structures, including
zero-trip loops.

4.2.2

Register Promotion

Lu and Cooper proposed a register promotion that moves explicit memoryreferences outside loops by using point-to analysis with data-ﬂow analysis[56]. Lo et al. proposed a technique based on sparse PRE [55]. Theirtechnique constructs a loop-nest tree, and then it speculatively moves memory references outside loops. These techniques replace memory referenceswith register references, similarly to scalar replacement; however, these techniques do not remove redundancies across several iterations.
Bodik et al. proposed a path-sensitive register promotion that detects
numerous redundant references across several iterations [7]. Their technique
is based on a value name graph (VNG), which consists of address value slices.
First, symbolic slices of the address operand are created by backwardly propagating addresses on the CFG. Then, the equality among the slices, which
are initially separated, is exposed by GVN, so that address value slices are
57

Chapter 4. Demand-driven Scalar Replacement

obtained. Their technique assumes that the redundancies are removed on
the VNG. The VNG creation process is similar to the analysis in PRESR, because these processes use GVN and backwardly propagate addresses or arrayreferences on the CFG. However, PRESR removes them immediately after
detecting the redundancy, by speculative movement. PRESR can remove
redundant array references more rapidly than the Bodik et al.’s approach.

4.3

Array Reference Representation

We assume that every array reference appears only in either the left-handside or the right-hand side of a statement. That is, a procedure call f (a[i])is split into two statements such as t = a[i] and f (t), and a store statementwith nested array references a[i] = a[a[i − 1]] is split to three statements
such as t = a[i − 1], t0 = a[t] and a[i] = t0 .
Similar to EDDPRE, each CFG node represents a basic block in PRESR.
In case where store statements can be executed between load statements thataccess the same address, the results of the load operations may be diﬀerent.
To distinguish these load statements, the diﬀerent versions are attached to
the name of the arrays in the same way as scalar SSA form, such as a1 [i1 ].
We assume that the assignment to an array element deﬁnes the array
itself; therefore, the name of the array is distinguished for each deﬁnitionof the element. In addition, our SSA form increments the version number
for arrays where a ϕ function is inserted in scalar SSA form. These version
numbers for the arrays are managed in hash-table arrayVersion[n]. Thishash-table is used to determine which version number was the largest at theexit of each node whenever a query has been propagated to predecessors.
Example.
Consider the array reference a3 [i1 ] at Node 4 in Fig. 4.2. Because there
is a store statement at Node 3, the version number is incremented. If it was
the deﬁnition of a scalar variable, a ϕ function would be inserted at the entryof Node 4. However, it is an array reference; therefore, as mentioned above,
PRESR implicitly increments the version number at nodes where ϕ functions
should be inserted in scalar SSA form, instead of inserting the ϕ function.
Thus, in our SSA form, the left-hand side of the store statement, a2 [i1 ], is
lexically diﬀerent from a3 [i1 ] in Fig. 4.2, although they contain the samevalue. To detect the redundancy, PRESR changes the version number when
propagating a query to each predecessor by using arrayVersion shown in
Table 4.1. For example, in Fig. 4.3, PRESR identiﬁes that the a3 [i1 ] ispartially redundant by propagating a1 [i1 ] and a2 [i1 ] to predecessors 2 and3, respectively. Finally, the result shown in Fig. 4.3 can be obtained.
End of Example.

58

Chapter 4. Demand-driven Scalar Replacement

1

2

3

Is the value numberof a₁[i₁] available?

x₁=a₁[i₁]a₂[i₁]=i₁
Is the value numberof a₂[i₁] available?

4 z₁=a₃[i₁]Figure 4.2: An example program after attaching versions for arrays. WhenPRESR propagates a query for a3 [i1 ], its attached version is changed byusing arrayVersion, as displayed in Table 4.1.

Table 4.1: arrayVersions from Fig. 4.2
node number

array version

1

1

2

1

3

2

4

3

1

2 t₁=a₁[i₁] 34x₁=a₁[i₁]a₂[i₁]=i₁t₂=φ₄(i₁,t₁)
z₁=t₂

Figure 4.3: Resulting program after applying PRESR to Fig. 4.2.

4.4

Demand-driven Scalar Replacement

PRESR extends optimistic GVN and query propagation of EDDPRE to
manage array references. In particular, in the query propagation, some
operands of inquired expression have to be replaced with the right-handside of their deﬁnitions when the query is propagated to their deﬁnitions inorder to achieve the query propagation across several iterations.

59

Chapter 4. Demand-driven Scalar Replacement

4.4.1

Value Numbering for Array References

In addition to assigning a value number to each scalar expression, as deﬁned
in Section 3.3.2, PRESR also assigns value numbers to array references.
The value number of an array reference a1 [i1 ] is deﬁned by the tuple of an
operator [ ] and the value numbers of the start address a1 and index i1 . If
the same tuple is found in the hash-table, its value number is assigned tothe array reference; otherwise, a new value number is assigned to the arrayreference. Subsequently, the value number is recorded, rending the tuple a
key in the hash-table. Similar to scalar expressions, these value numbers arerecorded in the local value occurrence table and the path value occurrencetable at each CFG node.

4.4.2

Redundancy Removal over Iteration

PRESR propagates a query for each array reference. The query propagation
is basically same as EDDPRE, except for three extensions. First, Local is
modiﬁed to allow a query to iteratively visit the same node, considering
aliases. Second, XAnswer is modiﬁed for replacement of variables. Third,
PRESR weakens the condition for speculative insertion in order to increase
opportunities for removing redundant array references.
Extension of Local .
As shown how PRESR removes redundant array reference beyond the loop
iterations with the motivation example in Section 4.1, a query should be
iteratively propagated to a node. Moreover, for safe code motion, the aliases
of memory references must be checked. The modiﬁed rules of Local are as
follows:
Deﬁnition 4.4.1 (Rules for a local answer to a query). Local (e, n) is redeﬁned for iteratively propagating queries to a node by the following rules,
which are checked when a query is propagated to node n:(1) If n is a node where the query has already been propagated, and thevalue number of the current e is same as the previous one, the answer
is true.
(2) If n is a node where the query has already been iteratively propagatedbeyond a certain number of times, according to the number of boundaries, and the value number of the current e is diﬀerent from theprevious one, the answer is false.
(2’) If n is a node where no value number of the query occurred on any pathfrom the start to the exit of n and the value number is not dependent
on the ϕ function, the answer is false.

60

Chapter 4. Demand-driven Scalar Replacement(3) If n is the original node of the query, and the original query is also sameas the current query, both the answer and isSelf (e, n) are true.
(4) If n is a node where the value number of e has been recorded in its local
value occurrence table, both the answer and isReal (e, n) are true.
(4’) If n contains any aliases of store statements, the answer is false.
Rule (2) of EDDPRE returns false if a query has already propagatedtwice to the same node. PRESR increases the number until it is the sameas a threshold that is initially given as a parameter visitLimNum.
Extension of XAnswer .
To check redundancy in a previous iteration, PRESR extends equation (3.6)
to replace each variable with the right-hand side of its deﬁnition, and thenchecks redundancy for the new query. Let replaceOp(e, n) be a functionthat performs the replacement of the variable of e if n is a node where theoperands are deﬁned.
Deﬁnition 4.4.2 (XAnswer of PRESR). Let e′ be the result of replaceOp.
To replace variables, XAnswer is redeﬁned as follows:def

XAnswer (e, n) ⇔ (n ̸= start) ∧ (Local (e, n) ∨{NAnswer (e, n)if e = e′) (4.1)′′
Local (e , n) ∨ NAnswer (e , n) otherwise
XAnswer (e, n) ﬁrst checks the occurrence of the value number of e if
n is diﬀerent from the start node. If the value number does not occur inn, replaceOp is called. The result of the replacement is represented as e′ .
Following the replacement, XAnswer checks the occurrence of the new value
number of e′ . If there is no occurrence of the new value number in n, a queryfor e′ is propagated to predecessors by NAnswer .
Extension of speculative insertion.
PRESR weakens the condition for the speculative insertion. This insertion is
performed when some variables in an expression are replaced with the righthand side of their deﬁnitions. This extension increases the opportunity forremoving redundant array references.
Example.
Consider the a2 [i2 -1] at Node 6 in Fig. 4.4 (a). a2 [i2 -1] has the samevalue as the a2 [i2 +1], which is deﬁned two iterations prior, and a2 [i2 +1] isoutside the innermost loop. The redundant array reference can be removed61

Chapter 4. Demand-driven Scalar Replacement

1 i₁=12

1

t₂=a₁[1]t₄=a₁[0]t₅=φ₃(t₄,t₃)
3 t₃=φ₃(t₂,t₀)i₂=φ₃(i₁,i₃)

i₁=1

4

2
3 i₂=φ₃(i₁,i₃)

j₁=i₂
5 t₆=b₂[j₁]t₈=b₂[j₁-1]

4 a₂[i₂+1]=c₁[i₂]5t₉=φ₆(t₈,t₇)
t₇=φ₆(t₆,t₁)
j₂=φ₆(j₁,j₃)6
t₁=t₅+t₉b₃[j₂+1]=t₁
j₃=j₂+1

j₁=i₂

j₂=φ₆(j₁,j₃)
6 b₃[j₂+1]=a₂[i₂-1]+b₂[j₂-1]
j₃=j₂+1
7

t₀=c₁[i₂]a₂[i₂+1]=t₀

i₃=i₂+17(a)i₃=i₂+1(b)

Figure 4.4: Eﬀect of PRESR. (a) Original program. (b) After applying
PRESR.

by inserting two statements, t2 =a1 [1] and t4 =a1 [0], into Node 2, and two
ϕ functions, t3 =ϕ3 (t2 ,t0 ) and t5 =ϕ3 (t4 ,t3 ), into Node 3 as shown in Fig.
4.4 (b). However, Node 2 is not down-safe for these two statements. Thatis, in order to remove the array reference, the array references should bespeculatively inserted. Note that although b2 [j2 -1] can be removed bytraditional scalar replacement techniques, they cannot remove a2 [i2 -1] bysingle application.
End of Example.

62

Chapter 4. Demand-driven Scalar Replacement

Deﬁnition 4.4.3 (Insertion of PRESR). To speculatively insert array references, Insertable (equation (3.4)) is redeﬁned as follows:def

AlgRepl (e, n) ⇔ e ̸= replaceOp(e, n) ∨def

Insertable(e, n) ⇔∑∑AlgRepl (e, p)(4.2)

p∈pred(n)isReal (e, p) ∧p∈pred(n)(DownSafe(e, n) ∨∑isSelf (e, p) ∨ AlgRepl (e, p))p∈pred(n)AlgRepl (e, n) indicates that some variables of e are replaced with theright-hand side of the deﬁnition at n, or there are predecessors of n thatsatisfy this predicate.

Pseudo Codes
We show pseudo codes of PRESR’s query propagation in Program 4.1 andProgram 4.2 that deﬁne functions propagate and local . PRESR extends
function propagate to check whether some operands are replaced with theright-hand side of their deﬁnition for calculating AlgRepl of equation (4.2)
at line 6. Further, PRESR extends function local to check the extended
Local property at lines 11–17.
Program 4.1 (Query propagation)
Function: propagate(e, n)// Arguments: The inquired expression e, and visiting CFG node n.
// Return value: A tuple of isAvail , isReal , and isSelf that denote the//answer of query at n, occurrence of e, and visited itself, respectively.
1: for each p ∈ pred (n)2: Make a new array reference nep by transPhi (e, p, n).
3: Determine a value number valp of nep .
4: Record nep in order to insert it at the exit of p later if it is necessary.
5: (isAvailp , isReal∑ p , isSelfp ) = local (valp , nep , p)
6: algRepl [n] := p∈pred(n) algRepl [p]∏7: if (Insertable(e, n) ∨ p∈pred(n) isAvailp ) // equation (3.2)
8: Insert nep made at line 4 into predecessors whose isAvailp is false.
9: Insert a ϕ functionof n.
∑ into the entry∑
10: return (true, p∈pred(n) isRealp , p∈pred(n) isSelfp )11: else
12: return (false, false, false)

63Chapter 4. Demand-driven Scalar Replacement

Program 4.2 (Analysis occurrence of value number)
Function: local (val, e, n)// Arguments: A value number val, the inquired array reference e, and visiting//
CFG node n.
// Return value: A tuple of isAvail , isReal , and isSelf .
1: if (n is the start node) return (false, false, false)
2: if (the condition of Rule (1) is satisﬁed) return (true, false, false)
3: if (the condition of extended Rule (2) is satisﬁed) return (false, false, false)
4: Record val in order to check Rules (1) and (2)5: Increment the visited number of n
6: if (val is recorded in local value occurrence table of n)
7: if (n equals to originalN and e is same as the original expression)
8:
return (true, true, true) // Corresponding to Rule (3)9: else10:
return (true, true, false) // Corresponding to Rule (4)11: else if (some operands of e are deﬁned in n)
12: Make new array reference ne by replaceOp.
13: Let nval be a value number of ne.
14: algRepl [n] := (ne ̸= e)
15: return local (nval, ne, n, true)
16: else if (the condition of Rule (4’) is satisﬁed)
17: return (false, false, false)
18: else
19: return propagate(e, n)

4.5

Experimental Results

We implemented PRESR as a low-level intermediate representation converter using a COINS compiler. We evaluated the eﬀects of PRESR using
loops from four programs (gzip, parser, bzip2, and twolf) from CINT2000,
and two programs (art and equake) from CFP2000 in the SPEC benchmarks. We conducted various experiments on a machine equipped with a
Xeon E5-1660 3.3GHz CPU and Debian 64bit OS. We set 3 to visitLimNumin this experiment, because this number is suﬃcient to detect redundancy
for SPEC2000 benchmark programs.
To evaluate the beneﬁts derived from PRESR, we compared it with TSR,
as follows:
TSR applies traditional scalar replacement that is proposed in [16].
PRESR converts normal form to SSA form, applies PRESR, and converts
SSA form back to normal form.
Table 4.2 and Table 4.3 list the execution time and dynamic load instruction count that was measured by PAPI [62] interface when TSR and PRESR
were applied to the loops of the programs listed above. The performances
64Chapter 4. Demand-driven Scalar Replacement

Table 4.2: Results of execution time
Program

TSR Time (sec)

PRESR Time(sec)

Improvement

gzip

77.1

76.0

1.4%

parser

85.0

83.7

1.5%

bzip2

64.6

63.4

1.9%

twolf

100

97.9

2.1%

art

32.6

31.5

3.4%

equake

27.7

27.0

2.5%

Table 4.3: Results of the dynamic number of load statement
Program

TSR Loads

PRESR Loads

Decreasegzip

9.17E+10

8.58E+10

6.4%

parser

1.41E+11

1.34E+11

4.4%

bzip2

1.06E+11

9.71E+10

8.1%

twolf

1.04E+11

9.93E+10

4.8%

art

7.13E+10

5.12E+10

28.2%

equake7.83E+10

7.15E+10

8.7%

of all the programs were improved when PRESR was applied. In particular,
the execution eﬃciency of art was improved by about 3.4%. The dynamic
number of executed load instructions for art decreased about 28.2%.
Next, we evaluated the analysis costs of PRESR, to demonstrate thatPRESR’s analysis is more eﬃcient than the iterative application of the exhaustive technique. In this evaluation, we compared PRESR with PRE*2and EDDPRE MEM, as follows:
PRE*2 applies PRE twice, and also applies copy propagation between the
two applications of PRE.
EDDPRE MEM applies EDDPRE only to array references.
Figure 4.5 shows the ratio of analysis time of EDDPRE MEM and PRESR
to PRE*2. As demonstrated by the results, comparing PRESR with PRE*2,
all programs were improved by applying PRESR. In particular, the improvement was about 67.9% in twolf. In contrast, comparing PRESR with EDDPRE MEM, the analysis cost increased twice in all programs, though thenumber of iterative visits was less than visitLimNum.
In general, scalar replacement uses register spill moderation to suppress
spills. In the evaluation, we applied only PRESR or traditional scalar replacement without the register spill moderation. It is straightforward tocombine PRESR with the register spill moderation, because PRESR cansimply decide not to be redundant without query propagation if the register
65

Chapter 4. Demand-driven Scalar Replacement

EDDPRE_MEM

PRESR

100.0%
80.0%
60.0%
40.0%
20.0%
0.0%

gzip

parser

bzip2

twolf

art

equakeFigure 4.5: Ratio of analyzing costs, compared with exhaustive style of PRE.

spill moderator determines that registers are full. In addition, it would be
eﬀective to preferentially remove more costly array references such as [66].
If PRESR could had a list of array references sorted according to their cost,
it could stop removing them in the case of no register available for removing
them.

4.6

Summary

In this chapter, we proposed a demand-driven scalar replacement techniquecalled PRESR that can remove all redundant array references from any
level of loop in a single application without restriction to input control ﬂow
structures. PRESR removes redundant array references by applying query
propagation. To detect redundancies across several iterations, the operandof the query is replaced with the right-hand side of the deﬁnition statement,
if the query is propagated to a node that includes the statement. To show
its eﬀectiveness, we applied PRESR to several benchmark programs. The
result showed that PRESR improved the execution eﬃciency of objectivecode in all cases. In future work, we intend to devise an additional technique to removes unnecessary store instructions based on query propagation
techniques such as PRESR.

66

Chapter 5

Global Load Instruction
Aggregation
In this chapter, we describe the algorithm of multidimensional global load instruction aggregation (MDGLIA). Section 5.1 explains the motivation of thistechnique. Section 5.2 summarizes the related works. Section 5.3 gives preliminary deﬁnitions needed for the purpose of explaining MDGLIA, and summarizes lazy code motion (LCM). Section 5.4 gives the details of the extension of LCM to MDGLIA. Section 5.5 shows experimental results to demonstrate the eﬀectiveness of MDGLIA. Section 5.6 summarizes MDGLIA.

5.1

Motivation

Most modern processors have some cache memories that are much fasterthan a main memory. Whenever the processor needs the data at address
x in main memory, cache memory is checked whether a copy of the data isstored in the cache memory ﬁrst. At this time, it is called cache hit if thedata at x is found in cache memory; otherwise, it is called cache miss. In
the case of the cache hit, because the data is obtained without any accessing
main memory, the program is executed without stalling. Conversely, oncethe cache miss occurs, the processor fetches the data around x in the main
memory and places them in the cache memory for cache hits later. In thiscase, the reference to x not only causes signiﬁcant delay because of thefetching but also removes the old data in the same cache line. This meansthat continuous accesses to addresses that are distant each other in themain memory may result in cache misses, which can decrease the execution
eﬃciency of the program.
Once a data at a speciﬁc array index is loaded from main memory, itis placed in cache memory along with other data belonging to the samearray. Therefore, if the accesses to the same array are executed continuously, they may contribute to the cache hits. Furthermore, considering
67

Chapter 5. Global Load Instruction Aggregation

void main(){x=a[i][j]y=a[k][l]z=a[i][j+1]}㻭㻌㻯㻌㼜㼞㼛㼓㼞㼍㼙

00
01
10
11

・
・
・
a[k][l] 0011
㼑㼤㼜㼑㼘
a[k][l+1] 0100
・・・
a[i][j] 1011
a[i][j+1] 1100
・
a[i][j] a[i][j+1]・・㻹㼍㼕㼚㻌㼙㼑㼙㼛㼞㼥㻯㼍㼏㼔㼑㻌㼙㼑㼙㼛㼞㼥

Figure 5.1: An example of a cache miss that is a target of MDGLIA.

that a multidimensional array represents an array of lower dimensional arrays, preferentially aggregating references with same indexes more in higher
dimensions may further decrease cache misses.
Example.
Consider the array reference a[i][j+1] in Fig. 5.1. In this chapter,for ease of explanation, we assume that cache memory is directly mapped
without loss of generality. That is, when the data are transferred fromthe main memory to the cache memory, the cache line is determined by
the memory address modulo of the number of lines in the cache memory.
The referenced data of a[i][j+1] is copied on the cache memory after the
execution of array reference a[i][j], but the execution of a[k][l] may
expel it. Therefore, a[i][j+1] will get a cache miss. However, this cache
miss can be prevented by moving a[i][j+1] immediately before a[k][l].
End of Example.
We present a new cache optimization technique, MDGLIA, that continuously aggregates the array references with the same indexes more in higher
dimensions. MDGLIA extended LCM to aggregate array references, without
sacriﬁcing the removal eﬀects of redundant expressions. MDGLIA computes
how many indexes of each array reference preceding a moved candidate aresame as ones of the candidate, and then MDGLIA moves the candidate to
the program points close to the references with the same indexes most in
higher dimensions.
Example.
Consider array references in Fig. 5.2 (a). Aggregation is applied to eacharray reference traversing CFG in the topological sort order. First, MDGLIA
moves the array reference a[k][l] immediately before the array referenceb[i] because the execution of b[i] between a[i][j] and a[k][l] may
68

Chapter 5. Global Load Instruction Aggregation

1
3 x=a[i][j]6’ t’=a[i][j+1]15’ t=a[k][l]3 x=a[i][j]22

4 y=b[i]4 y=b[i]5 z=a[k][l]5 z=t

6 w=a[i][j+1]

6 w=t’

7

7

(a)

(b)

Figure 5.2: Eﬀectiveness of MDGLIA. (a) Original code. (b) Result ofapplying MDGLIA.

cause the data of a[k][l] to be removed from the cache memory if thedata of b[i] shares some cache lines for a[k][l]. Here, MDGLIA makesa new Node 5’ for the moved array reference. Next, consider a[i][j+1] at
Node 6. Although a sub-array a[i] is accessed at Nodes 3 and 6, anotherarray b and sub-array a[k] are accessed between them. Hence, the data ofa[i][j+1] may be removed from the cache memory after the execution ofthem. MDGLIA moves a[i][j+1] immediately before a[k][l] as shownin Fig. 5.2 (b).
End of Example.
The advantages of MDGLIA are summarized as follows:• MDGLIA not only removes redundant array references but also decreases the number of cache misses, considering array dimensions.
• MDGLIA suppresses spills without decreasing the eﬀect of preventing
cache miss.

5.2

Related Work

5.2.1

Cache Optimization

Once a data in the memory is used, it tends to be used again in the near
future, and the data stored around it tends to be used in much of the
program. These two phenomena are called temporal locality and spatial
69

Chapter 5. Global Load Instruction Aggregation

locality, respectively, which are utilized in order to improve the execution
eﬃciency of the programs through cache memories. Popular techniques forenhancing the localities are due to transforming loop structures [1, 4, 44].
Although these techniques often greatly improve the execution eﬃciency ofa program, its application tends to be limited to speciﬁc control structures
such as a simple loop. However, MDGLIA is based on global code motion,
which does not have to change the control structure of a program; therefore,MDGLIA can be applied to any programs.
There are some techniques that improve cache eﬃciency based on datalayout. Cache-conscious data placement (CCDP) [14] reduces the cache
conﬂict misses by considering the data layout. CCDP uses the temporal
relationship graph (TRG). In the TRG, the nodes represent objects (e.g.,functions, arrays, and global variables) to be placed into the data cache.
The edges between the objects represent the estimated number of cache
misses that would occur if the two objects mapped to the same cache set. A
compiler assigns addresses to the objects based on the conﬂict cost metriccalculated for the TRG so as to minimize the cache conﬂict misses. Although
CCDP can reduce the cache conﬂict misses for a processor core with a single
execution context, it loses much of its beneﬁt in a multithreaded environment
because inter-thread conﬂicts are not deterministic. Sarkar and Tullsen
proposed a technique that extends CCDP to multithreaded architectures[71]. In their technique, the extra cost is generated so that threads shareobjects in cache blocks is added to each TRG edge as weight. Similar to
CCDP, the compiler assigns addresses to the objects using a TRG so as
to minimize the cache conﬂict misses cost. As another technique based on
the object layout, Ishitobi et al. proposed a technique for suppressing theenergy consumption of on-chip memory by considering memory allocation
on a processor that has cache memory and scratchpad memory [47]. Theirtechnique considers a cacheable region, a scratchpad region, and a noncacheable regions so as to minimize the total energy consumption and thenumber of cache misses. These approaches deal with memory allocation
methods for data but not the ordering method of the execution code.

5.2.2

Removing Redundant Expressions

The original PRE technique was proposed by Morel and Renvoise [57], whichuses bi-directional data-ﬂow analysis. This technique can eliminate someredundancies and move loop invariant expressions out of loops, but some redundant expressions are not removed because the technique does not insert
expressions at non down-safe nodes. Dhamdhere extended this technique
to insert expressions on edges [28], and Dhamdhere and Patil proposed another technique that removes redundancies based on uni-directional dataﬂow analysis [30]. Bodik et al. proposed the removal of all redundant expressions by copying certain parts of the program [5]. Kawahito et al. proposed70

Chapter 5. Global Load Instruction Aggregationa technique that removes partially redundant load and store instructions byextended PRE [48]. These techniques remove redundant expressions, but
decreasing the number of cache misses is out of their target.
As another technique based on code motion, there is a speculative code
motion technique [55], which speculatively moves load instructions out ofloops. This technique needs to recognize loop structures, whereas MDGLIA
can be applied to an entire program without recognizing them, because
MDGLIA is based on PRE.

5.3

Background

5.3.1

Program Representation

We assume that MDGLIA is applied to the intermediate representation converted from a source program, which is represented as a sequence of statements with at most an operator or a function, and to CFG each node ofwhich represents a single statement rather than a basic block. The righthand side of an assignment is called an expression. Some statements include
load and store instructions with memory access, which is described as an array reference, e.g., a[i][j] with address a and indexes i and j. The statement
loading the data at memory location a[i][j] into a virtual register x is expressed as assignment statement x = a[i][j], which we call a load statement.
Similarly, a statement storing the data in a virtual register x to a memory
location a[i][j] is expressed as a[i][j] = x, which we call a store statement.
We assume that the memory access solely appears in assignment. Thatis, a procedure call f (a[i][j]) is split into two statements such as t = a[i][j]and f (t). In addition, a store statement with a nested array referencea[i][j] = a[b[i]][k] is split to three statements such as t = b[i], t0 = a[t][k] anda[i][j] = t0 . Moreover, the load statement includes a temporary virtual register instead of original virtual register in the left-hand side. For example,
the load statement i = a[i][j] is split into two statements such as t = a[i][j]and i = t by introducing a temporary virtual register t. We assume that any
arrays are laid out in row-major order on the memory such as arrays in C,
which means that the leftmost index corresponds to the highest dimensionof the array.

5.3.2

Lazy Code Motion

PRE tends to lengthen the live-ranges of variables carrying loaded values totheir uses because it removes redundant expressions by inserting some expressions. LCM tries to address the problem by hoisting expressions as earlyas possible and delaying them as late as possible. The hoisting contributes
to eliminating all removable expressions, and the delaying contributes tominimizing the live-ranges of variables.

71

Chapter 5. Global Load Instruction Aggregationt=a[i]
hoisting

1
2 x=a[i]delaying

1

t=a[i]

t=a[i]
2 x=a[i]34 y=a[i]34 y=a[i](a)(b)

Figure 5.3: Code motions of LCM. (a) Hoisting expressions. (b) Delaying.

12’ t=a[i]3 t=a[i]
2 x=t
4 y=t

Figure 5.4: Result of applying LCM to Fig. 5.3 (a).

Example.
Consider an array reference a[i] at Node 4 in Fig. 5.3 (a). This arrayreference is partially redundant because it is redundant on a path throughNode 2 whereas it is not on another path through Node 3. To remove thisarray reference, LCM determines CFG nodes at which array references canbe inserted ﬁrst. If it is inserted at Node 1, it is able to remove the redundant
array reference by replacing the reference with the introduced temporary t.
Notice here that, the live-range of t is lengthened; therefore, LCM delays
the insertion node, as shown in Fig. 5.3 (b). Finally, LCM inserts the arrayreferences at Nodes 2 and 3, and then it replaces the original a[i] with t,
as shown in Fig. 5.4.
End of Example.
These code motions have to satisfy two kinds of safeties: down-safety andup-safety. Down-safety is used to ensure that LCM does not introduce a new
occurrence of the inserted expression on any execution path. Down-safety isrepresented by predicate DownSafe. In addition, up-safety is used to ensure

72Chapter 5. Global Load Instruction Aggregationthat there are some paths where the number of expressions is decreased by
the insertions and removals. Up-safety is represented by predicate UpSafe.
These safeties are deﬁned under the condition of transparency that ensuresthat the value of an expression does not change at the program points ofconcern. LCM represents it by predicate Transp. Because the up-safety
is one of the most important predicates of MDGLIA, we show the formal
deﬁnition.
def

UpSafe(n) ⇔ (n ̸= start) ∧∏Comp(p) ∨ (Transp(p) ∧ UpSafe(p)) (5.1)
p∈pred(n)where the predicate Comp(n) denotes that node n includes a same expression.
Example.
As shown in Fig. 5.3 (a), DownSafe of Nodes 1, 2, and 3 are true becauseof no modiﬁcation for i nor a[i] at Nodes 2, 3, and 4. In contrast, UpSafeof all nodes are false. Because no occurrence of the array reference on apath from Node 1 to Node 3, UpSafe(4) is false. Others nodes’ UpSafe isobviously false.
End of Example.
LCM determines two kinds of insertion nodes based on the predicates
Earliest and Latest, which determine insertion points in two code motions mentioned above, respectively. The predicate Earliest(n) denotes that
node n is the closest to start of the nodes m satisfying DownSafe(m) or
UpSafe(m). The predicate Latest(n) denotes that node n is the closest to
the node c that satisﬁes Comp(c) on each path from Earliest to end, andthere is no node that satisﬁes the Comp on the path from Earliest to c.
Latest(n) is deﬁned on the basis of maximal ﬁxed points of the data-ﬂow
equation for the predicate Delayed (n), which denotes that the expression
can be delayed until the exit of node n.
Example.
Consider the a[i] in Fig. 5.3 (a). First, LCM decides that Earliest(1)is true because DownSafe(1) is true, and this node is the closest to thestart node. Then, LCM delays the insertion points through the decisions ofDelayed and Latest, which result in true for Comp(2), false for Delayed (4),and true for Latest at Nodes 2 and 3.
End of Example.
Here, as Delayed is also one of the most important predicates for MDGLIA,
we present the formal deﬁnition.

73

Chapter 5. Global Load Instruction Aggregation

def

Delayed (n) ⇔ Earliest(n) ∨∏(n ̸= start) ∧¬Comp(p) ∧ Delayed (p) (5.2)

p∈pred(n)LCM inserts expressions at the entry of nodes n satisfying the predicate
Insert(n), which denotes that n is one of nodes satisfying Latest. Note thatLCM does not insert any expression without decreasing the number of expressions on some paths, because such insertions are unnecessary. Therefore,
Insert(n) is deﬁned as Latest(n) ∧ ¬Isolated (n) on the basis of the predicate Isolated (n) which denotes that the insertion at n enables removing no
expression other than original one.

5.4

Array Reference Aggregation

MDGLIA aggregates each array reference ar traversing CFG in the topological sort order. Similar to LCM, MDGLIA calculates DownSafe, UpSafe,
Earliest, Delayed , and Latest to determine nodes to move ar. In the delaying
process, MDGLIA checks start addresses and the number of corresponding
indexes of array references to aggregate them while considering the order ofaccesses to arrays.

5.4.1

Local Properties

For the checking addresses, MDGLIA deﬁnes local properties SameAddr ,Transp e , Transp Addr , and isSame. SameAddr and isSame represent equalities of start addresses and whole expressions, respectively. SameAddr (n)denotes that n contains a load statement referring to the same array reference as ar. isSame, corresponding to Comp of LCM, denotes that SameAddr
is true and the indexes are same as ar. Transp e (n), corresponding to Transp
of LCM, denotes that there is no modiﬁcation to ar and no store operation
to the array referred by ar in n. Transp Addr denotes that there is neither
modiﬁcation to ar nor reference to arrays diﬀerent from ar.
To determine these predicates, we use predicates rhs, isLoad , TopAddr ,Store, Def , and Var . rhs(n) returns the right-hand side of a statement
at the node n. isLoad (n) denotes that node n includes a load statement.
TopAddr (ar) returns the start address of ar if ar is an array; otherwise, it
returns ⊥. Store(n) denotes that node n includes a store statement thataccesses the same array as ar. Def (n) gives a variable deﬁned at node n.
Var (ar) gives a set of variables which are used in ar. The local properties
are formally deﬁned as follows:74

Chapter 5. Global Load Instruction Aggregation

def

SameAddr (n) ⇔ isLoad (n) ∧ (TopAddr (rhs(n)) = TopAddr (ar))
defTransp e (n) ⇔ Def (n) ̸∈ Var (ar) ∧ ¬Store(n)defTransp Addr (n) ⇔ Transp e (n) ∧ (¬isLoad (n) ∨ SameAddr (n))
defisSame(n) ⇔ rhs(n) ̸= ⊥ ∧ rhs(n) = ar

5.4.2

Modiﬁed Global PropertiesMDGLIA uses modiﬁed UpSafe and Delayed of LCM.
Extending UpSafe
UpSafe(n) of equation (5.1) is modiﬁed to denote that there are some arrayreferences whose start addresses are same as ar on all sub-paths leading to
the node n. This predicate is formally deﬁned as follows:def

UpSafe(n) ⇔ (n ̸= start) ∧∏SameAddr (p) ∨ (Transp e (p) ∧ UpSafe(p))
p∈pred(n)The modiﬁcation not only contributes to detecting the access order toarrays, but also gives the criterion for speculatively moving array references.
Example.
In Fig. 5.5 (a), consider applying MDGLIA to the a[i+1]. Because thearray reference a[i] is executed at Node 1, UpSafe(2) is true; therefore,
Earliest(2) is true. It leads Delayed (2) to be true, but Delayed (3) becomes
false because TranspAddr (2) is false. As a result, Latest(2) becomes true;
therefore, a[i+1] is inserted before Node 2 as shown in 5.5 (b). Noticehere that a[i+1] does not originally exist on the path through Node 3 inFig. 5.5 (a). That is, this insertion is speculative. Speculative code motion
may increase the number of the expression on some paths. However, if
the speculatively inserted array references cause cache misses, the execution
eﬃciency would be signiﬁcantly decreased.
End of Example.

Extending Delayed
Delayed of equation (5.2) is modiﬁed to check whether keep-order condition
and keep-dimension condition are satisﬁed.

75

Chapter 5. Global Load Instruction Aggregation

1 x=a[i]1 x=a[i]4’ t=a[i+1]2 y=b[i]2 y=b[i]4 z=a[i+1]

3

4 z=t

3

5

5
(a)

(b)

Figure 5.5: Speculative code motion. (a) Original code. (b) Moving arrayreference, not satisfying down-safety.

Keep-order Condition
The keep-order condition guarantees that there is no any reference to thearray diﬀerent from ar at n after preceding reference to the same array as
ar. The keep-order condition is represented by keepOrder (n), and deﬁned
as follows:defpartialUpSafe(n) ⇔∑UpSafe(p)p∈pred(n)defkeepOrder (n) ⇔ ¬partialUpSafe(n) ∨ Transp Addr (n)Example.
We show an example of the eﬀect of aggregation considering keep-ordercondition in Fig. 5.6 (a). Consider moving the a[k][l] at Node 5. Nodes
3 and 5 contain array references that reference to array a; however there
is an array reference that reference to array b between them. To move thea[k][l] immediately before Node 4, MDGLIA determines Earliest throughchecking UpSafe and DownSafe ﬁrst. As there is no a[k][l] on the paththrough Node 2, DownSafe(1) and UpSafe(1) are false. These results cause
Earliest(1) to be false. On the other hand, another path through Node 3
has the same reference at Node 5. Hence, DownSafe(3) and Earliest(3) aretrue, which causes Delayed (3) to be true. At each node from the Node 3,
MDGLIA checks whether the keep-order condition is satisﬁed. Node 3 hasan array reference that reference to the same array as a[k][l]; however,76

Chapter 5. Global Load Instruction Aggregation

1

2

1

DownSafe(1), UpSafe(1): false
DownSafe(3): true
Earliest(3): true
Delayed(3): true
3 x=a[i][j]UpSafe(4): true
SameAddr(4): false
4 y=b[i]keepOrder(4): false

3 x=a[i][j]5’ t=a[k][l]4 y=b[i]25 z=a[k][l]5 z=t

Delayed(5): false

6 w=a[i][j+1]

6 w=a[i][j+1]

7

7
(a)

(b)

Figure 5.6: Eﬀectiveness of extending UpSafe. (a) Result of computing
data-ﬂow equations to move a[k][l] at Node 5. (b) Result of moving thearray reference.

Node 4 has another array reference that references to diﬀerent array. Hence,
SameAddr (3) is true, and then UpSafe(4) is true; however SameAddr (4) isfalse. These results cause keepOrder (4) and Delayed (5) to be false. Eventually, Latest(4) and Insert(4) are true, so that MDGLIA inserts an arrayreference immediately before the Node 4 and removes the original expression, as shown in Fig. 5.6 (b).
End of Example.

Keep-dimension Condition
The keep-dimension condition contributes to the aggregation of references
to closer addresses in the same array through keeping the number of corresponding indexes from decreasing. To keep the number, this condition
uses two kinds of predicates: number of corresponding indexes (nCI ) andpropagated nCI (pnCI ).
nCI is the number of higher indexes corresponding with ar for representing closeness on the main memory between references to an array. nCI (n)checks whether each index of the array reference at n is same as corresponding index of ar, one by one in left-ﬁrst, whenever n contains a reference tothe same array as ar. This predicate is formally deﬁned as follows:77

Chapter 5. Global Load Instruction Aggregation

Deﬁnition 5.4.1. We assume that ar is a[i1 ][i2 ]...[ik ]...[in ], and r isb[j1 ][j2 ]...[jk ]...[jm ]. Then,kif a = b ∧ il = jl ∧(k = n ∨ k = m ∨ ik+1 ̸= jk+1 )def
nCI (r) ⇔where ∀l ∈ {1, ..., k}0otherwise
The condition means that if their start addresses are same, these indexes
are checked about whether the kth index is same or not until it is the lastindex.
pnCI (n) denotes the number of indexes of the reference which has themost same indexes as ar on all execution paths to the exit of n from preceding node where SameAddr is true. pnCI can be deﬁned by the data-ﬂow
equation based on nCI as follows:
if n = start 0
defnCI (n)if SameAddr (n)pnCI (n) ⇔Max ({pnCI (m) | m ∈ pred (n)}) otherwise
The equation can be iteratively solved as well as typical data-ﬂow analysis. If node n includes a reference to the same start address as ar, thenpnCI (n) equals to nCI (n). Otherwise, pnCI (n) is the maximal value of the
pnCI of all predecessors, except the start node.
The keep-dimension condition is represented by predicate keepDimensionthat is deﬁned using partialUpSafe and pnCI as follows:def

keepDimension(n) ⇔ ¬partialUpSafe(n) ∨∏pnCI (n) ≥ pnCI (p)p∈pred(n)This predicate denotes n does not include any reference with nCI lessthan the preceding references.
Delaying Considering Keep-order and Keep-dimension Conditions
MDGLIA checks whether the keep-order and keep-dimension conditions are
satisﬁed in addition to Delayed of LCM. Once these conditions are introduced, Delayed is simply changed as follows:def

Delayed (n) ⇔ Earliest(n) ∨ (n ̸= start) ∧∏¬isSame(p) ∧ keepOrder (p) ∧p∈pred(n)keepDimension(p) ∧ Delayed (p)78Chapter 5. Global Load Instruction Aggregation

1
3 x=a[i][j]5’ t=a[k][l]4 y=b[i]Delayed(3): truenCI(3): 1
pnCI(3): 1
nCI(5’): 0
pnCI(5’): 0
keepDimension(5’): false
Delayed(4): false

2
5 z=t
6 w=a[i][j+1]7

Figure 5.7: Computing closeness of each addresses of a[i][l] at Node 4
and Delayed .

Example.
In Fig. 5.7, we show results of data-ﬂow analysis of MDGLIA when it
moves the a[i][j+1] at Node 6 in Fig. 5.6 (b). Nodes 3 and 6 containarray references that reference to sub-array a[i], but there is an array reference that reference to sub-array a[k] between them. To move a[i][j+1]
immediately before Node 5’, MDGLIA determines Earliest ﬁrst. Because
Earliest(3) is true as well as in the case where moving the a[k][l] in Fig.
5.6 (a), Delayed (3) is true. At each node following the Node 3, MDGLIA
checks whether the keep-dimension condition is satisﬁed. Although nCI
and pnCI of Node 3 are 1, nCI and pnCI of the successor 5’ are 0; therefore, keepDimension(5′ ) and Delayed (4) are false. Eventually, Latest(5′ )and Insert(5′ ) are true; therefore, MDGLIA inserts an array reference immediately before the Node 5′ and removes the original expression, as shownin Fig. 5.2 (b).
End of Example.
Finally, to help understanding of whole algorithm, we present formal deﬁnitions of all global predicates other than UpSafe, keepOrder , keepDimension,and Delayed as follows:79

Chapter 5. Global Load Instruction Aggregation

def

DownSafe(n) ⇔ (n ̸= end) ∧(isSame(n) ∨ Transp e (n) ∧∏DownSafe(s))

s∈succ(n)defSafe(n) ⇔ UpSafe(n) ∨ DownSafe(n)defEarliest(n) ⇔ Safe(n) ∧∑((n = start) ∨¬ Transp e (p) ∨ ¬ Safe(p))

p∈pred(n)defLatest(n) ⇔ Delayed (n) ∧ (isSame(n) ∨defIsolated (n) ⇔∏∑¬ Delayed (s))

s∈succ(n)Latest(s) ∨ ¬isSame(s) ∧ Isolated (s)s∈succ(n)defInsert(n) ⇔ Latest(n) ∧ ¬Isolated (n)defReplace(n) ⇔ isSame(n) ∧ ¬(Latest(n) ∧ Isolated (n))

5.4.3

Application to the Entire Program

We design MDGLIA as a demand-driven analysis, which is applied to eacharray reference one by one, rather than exhaustive one. In general, PRE
based approaches are known that an application of it exposes new redundant expressions. The eﬀect is called second-order eﬀects. Capturing themas many as possible results in removing more redundant expressions. However, capturing all the second-order eﬀects requires iterative applications ofPRE, which are costly because PRE is traditionally designed based on an
exhaustive data-ﬂow analysis [60, 78, 80]. On the other hand, the demanddriven applications of PRE to the entire program in the topological sortorder enables eﬃciently capturing a lot of the second-order eﬀects, as shownin Chapter 3. Furthermore, for the aggregating array references, demanddriven application contributes to suppressing unnecessary code motion.
Example.
In Fig. 5.8 (a), Nodes 2 and 3 might expel data that may be used laterfrom a cache memory. At this time, if MDGLIA would move all array references in the exhaustive application such as the traditional PRE, referencesa[i+1] and b[i+1] would be moved as shown in Fig. 5.8 (b). As a result,even if the problems of cache misses are resolved, it would enhance registerpressure of the temporary variable which had the value of b[i+1] because
the unnecessary code motion of b[i+1] lengthened the live-range of it. By
contrast, in demand-driven application, only the a[i+1] is moved to the80Chapter 5. Global Load Instruction Aggregation

1 x=a[i]3’ t=a[i+1]1 x=a[i]1 x=a[i]2 y=b[i]3’ t=a[i+1]2 y=b[i]4’ t’=b[i+1]2 y=b[i]3 z=a[i+1]

3 z=t

3 z=t

4 w=b[i+1]

4 w=t’

4 w=b[i+1]

(a)

(b)

(c)

Figure 5.8: Preserving unnecessary code motion. (a) Original code. (b)Result of applying exhausive analysis version of MDGLIA to a[i+1]. (c)Result of applying demand-driven style MDGLIA to a[i+1].

entry of Node 2 based on the demand-driven application manner as shown
Fig. 5.8 (c).
End of Example.

5.5

Experimental Results

We have implemented MDGLIA as a low-level intermediate representation
converter in a COINS compiler. To emphasize the beneﬁts of MDGLIA, we
compared MDGLIA with the following two optimizations.
LCM-MEM only removes redundant array references based on LCM.
GLIA aggregates references to the same array without considering theirdimensions.
We evaluated the eﬀects of these optimizations for two programs (equake
and art) of CFP2000 and three programs (mcf, gzip, and twolf) of CINT2000
in the SPEC benchmarks on x86 machine whose CPU and OS are, respectively, Intel Core2Duo U9600 1.6GHz and CentOS. The system parametersof the machine are shown in Table 5.1.
To show how many cache misses can be decreased by GLIA and MDGLIA,
we measured the following two hardware counters.
DCache Repl:

the number of replacement at L1 data cache.

L2 Lines Out:the number of cache out from L2 cache.
81Chapter 5. Global Load Instruction Aggregation

Table 5.1: System parameters of cache memories
Parameters
L1D
L2
Total size (KB)32
3,072Line size (bytes)
64
64
The number of cache line 512 49,152
Associativity
8
12
We simply call these numbers L1D cache miss and L2 cache miss, respectively.
The result of comparison among the cache misses for the three optimizations is shown in Fig. 5.9, and the results of the number of L1D and L2 cache
misses, respectively, are shown in Tables 5.2 and 5.3. Comparing GLIA andMDGLIA with LCM-MEM, L1D cache misses occur to the same degree
for four programs (art, mcf, gzip, and twolf), though they increased about
7% for a program (ammp). Comparing GLIA with LCM-MEM, L2 cache
misses decreased for three programs (art, mcf, and gzip). In particular, thecache misses remarkably decreased about 19.9% for art. In contrast, they
increased for two programs (ammp and twolf). Comparing MDGLIA with
LCM-MEM, L2 cache misses decreased for four programs (art, mcf, gzip, andammp). In particular, the cache misses remarkably decreased about 30.3%
in art. On the other hand, they increased for a program (twolf). Comparing MDGLIA with GLIA, L2 cache misses decreased for four programs(art, gzip, ammp, and twolf). In particular, the cache miss remarkably decreased about 15.6% in ammp. For ammp, comparing these techniques with

L1D_cache_miss-GLIA

L2_cache_miss-GLIA

L1D_cache_miss-MDGLIA

L2_cache_miss-MDGLIA

40.00%
30.00%
20.00%
10.00%
0.00%-10.00%-20.00%-30.00%

art

gzip

mcf

ammp

Figure 5.9: Decrease rate of cache misses.

82

twolf

Chapter 5. Global Load Instruction Aggregation

Program
art
mcf
gzip
ammp
twolf

Table 5.2: The number of DCache Repl
LCM-MEMGLIAMDGLIA
11,439,104,576 11,453,555,362 11,444,685,513
7,567,419,160
7,531,488,486
7,544,975,464
7,725,469,653
7,707,389,218
7,818,871,317
21,792,733,488 23,216,563,772 23,413,676,395
9,056,125,547
9,029,509,531
8,986,903,509

Table 5.3: The number of L2 Lines Out
Program LCM-MEM
GLIA
MDGLIAart
366,823,834 293,702,375 329,018,854
mcf
727,422,092 720,133,268 724,349,339
gzip
25,856,048
25,177,224
24,706,624
408,120,338 419,706,166 354,268,633
ammp
twolf
1,518,718
1,812,932
1,678,713
LCM-MEM, although L2 cache misses increased for GLIA, they decreasedfor MDGLIA. This is because MDGLIA can aggregate more array references
than GLIA, showing that the aggregation of the array references with themost similar indexes in higher dimensions is important.
In some programs, GLIA and MDGLIA caused cache misses to increase.
The increase is considered to be derived from the following reasons: 1) the
number of spills of temporary variables increased, and 2) speculative code
motion lengthened execution paths without contributing to decrease of cache
misses, as mentioned in Section 5.4.2.
The ﬁrst reason can be considered to be for the use of LCM framework of these techniques, which is known to increase the number of spills[39] although LCM tries to decrease them by delaying insertion points. In
addition, GLIA and MDGLIA tend to stop the delaying earlier than LCM.
Example.
Consider an array reference a[i][j+1] in Fig. 5.10 (a). The arrayreference is redundant at Node 6; therefore, it can be removed by LCMMEM, as shown in Fig. 5.10 (b). On the other hand, this array reference isjust moved in GLIA and MDGLIA, as shown in Fig. 5.10 (c) and Fig. 5.10(d). This observations show that GLIA and MDGLIA may enhance moreregister pressure than LCM-MEM. If some spills occur, they may decrease
the eﬀects of GLIA and MDGLIA by the insertions of some store and load
instructions between the array references to the same array. In other words,
the spills may increase not only the length of some execution path but also
the number of cache misses.
End of Example.

83

Chapter 5. Global Load Instruction Aggregation

1 x=a[i][j]1 x=a[i][j]1 x=a[i][j]1 x=a[i][j]2 y=a[k][l]2 y=a[k][l]4’ t=a[i][j+1]2 y=a[k][l]3 z=b[i]4’ t=a[i][j+1]2 y=a[k][l]3 z=b[i]4’ t=a[i][j+1]3 z=b[i]3 z=b[i]4 w=a[i][j+1]

4 w=t

4 w=t

4 w=t

5 o=c[i][j]5 o=c[i][j]5 o=c[i][j]5 o=c[i][j]6 p=a[i][j+1]

6 p=t

6 p=t

6 p=t

(a)

(b)

(c)

(d)

Figure 5.10: Diﬀerence of an insertion point for a[i][j+1]. (a) Originalcode. (b) Result of applying LCM-MEM. (c) Result of applying GLIA. (d)Result of applying MDGLIA.

We conducted experiments to conﬁrm how the problems increased thenumber of cache misses.

Impact of Spill
We show the number of spills for the applications of three optimizations inTable 5.4. Comparing GLIA and MDGLIA with LCM-MEM, they caused
more spills for four programs (mcf, gzip, ammp, and twolf). In particular,
the number of the spills increased about 20% for twolf. However, in spiteof the increase of the spills, L1D cache misses were held to the same degree
as LCM-MEM for mcf and gzip. These additional results show that, theincrease of the spills does not always increase the number of cache misses.
Actually, applying MDGLIA to ammp decreased L2 cache misses although
it increases the number of spills. In contrast, for twolf, the number of bothspills and cache misses increased. It is considered that load/store for spills

Table 5.4: The number of register spills
Program
art
mcf
gzip
ammp
twolf

A.LCM-MEM
28
61
107
317
804

B.GLIA
28
71
114
334
962

C.MDGLIA
28
71
114
335
979

84

(A-B)/A
0.0 %-16.4 %
-6.5 %-5.4 %-19.7 %(A-C)/A
0.0 %-16.4 %
-6.5 %-5.7 %-21.8 %(B-C)/B
0.0 %
0.0 %
0.0 %
-0.3 %-1.8 %

Chapter 5. Global Load Instruction AggregationGLIAMDGLIAUSGLIAUSMDGLIA

40.0%
30.0%
20.0%
10.0%
0.0%
-10.0%-20.0%-30.0%

art

mcf

gzip

ammp

twolf

Figure 5.11: The decrease ratio of L2 cache miss for GLIA, MDGLIA, USGLIA, and USMDGLIA to the cache miss for LCM-MEM.

were inserted between references continuously moved by MDGLIA. Thus, a
new register allocation technique for suppressing more cache misses is oneof our future works.

Speculative Code Motion vs. Unspeculative Code Motion
In order to comparatively conﬁrm how many number of cache misses the
speculative code motion decreases, we implemented the following two optimizations that do not speculatively aggregate array references:
USGLIA aggregates array references with the keep-order condition basedon UpSafe of equation (5.1).
USMDGLIA aggregates array references with the keep-order and keepdimension conditions based on UpSafe of equation (5.1).
First, we show the result of L2 cache misses for USGLIA and USMDGLIA in addition to GLIA and MDGLIA in Fig. 5.11 and Table 5.5.
Comparing GLIA with USGLIA, GLIA increased the number of cache misses
for three programs (art, ammp, and twolf). In contrast, comparing MDGLIA
with USGLIA, MDGLIA decreased the number of the cache misses for two
programs (art and gzip). Comparing MDGLIA with USMDGLIA, MDGLIA
decreased the number of the cache misses for four programs (art, mcf, gzip,
and ammp). Thus, MDGLIA was better than these unspeculative versions
on average. This is because speculative code motion can aggregate morearray references than unspeculative ones. Table 5.6 shows the number ofstopped delaying by checking keep-order or keep-dimension conditions inthe speculative and unspeculative code motions. As shown in the table, the85

Chapter 5. Global Load Instruction Aggregation

Table 5.5: The number of L2 cache miss of USGLIA and USMDGLIA, andthe cache miss ratio of them to the cache miss for GLIA and MDGLIA
Program
art
mcf
gzip
ammp
twolf

USGLIA
282,855,332
721,268,586
25,449,483
345,935,455
1,689,141

vs. GLIA3.7 %-0.2 %-1.1 %
17.6 %
6.8 %vs. MDGLIA-10.6 %
0.4 %-3.0 %
2.4 %-0.6 %USMDGLIA
297,012,498
732,708,340
26,351,879
359,701,112
1,667,434

vs. MDGLIA-16.1 %
-1.2 %-6.7 %-1.5 %
0.7 %Table 5.6: The number of aggregated array references under keepOrder andkeepDimension in speculative/not speculative code motion
Program
art
mcf
gzip
ammp
twolf

Speculative
keepOrder keepDimension
438
22
750
298
829
134
8,043
2,015
30,3997,313

Not Speculative
keepOrder keepDimension
145
22
104
71
182
77
719
512
8,855
811

speculative code motion was able to aggregate move more array references
than unspeculative one.
Considering L2 cache miss when GLIA, MDGLIA, USGLIA, or USMDGLIA was applied to twolf, they increased L2 cache misses for the program. Although the increase for GLIA was about 20%, the other increases
were about 10%. Furthermore, comparing USGLIA and USMDGLIA, theresults of L2 cache misses are held to the same degree. These results indicate that GLIA speculatively inserts array references, which cause thenumber of spills to increase, leading to cache misses. On the other hand,
speculative aggregation of array references with the most similar indexes inhigher dimensions decreases the cache misses although MDGLIA increases
more number of spills than GLIA. That is, the speculative aggregation underkeep-dimension condition decreased the L2 cache misses.
Finally, these results shows that the aggregation of array references ismore useful technique for decreasing cache misses than simply removing
redundant array references. However, unspeculative code motion is better than speculative ones for some programs. Because the speculative code
motion can move array references further than unspeculative one has potential, we believe that MDGLIA can be improved by proﬁling whether theaggregated array references get cache hit.

86

Chapter 5. Global Load Instruction Aggregation

5.6

Summary

In this chapter, we have proposed a new global code motion technique foraggregating array references with the most similar indexes in higher dimensions of the same array in order to suppress cache misses. MDGLIA not
only suppresses the cache misses but also suppresses spills through delaying
the load instructions without changing their access order.
In order to show the eﬀectiveness of MDGLIA, we applied it to somebenchmark programs. As a result, we have shown that there are some
programs in which it decreases the number of cache misses. As future work,
we can consider 1) making a new register allocation that preferentially spills
variables that will get cache hits, and 2) aggregating array references basedon sophisticated informations of cache memory and their addresses on main
memory.

87

Chapter 6

Conclusion and Future
Direction
The optimization of memory hierarchy utilization is one of the most important techniques of code optimizations because accesses to the main memory
remarkably decreases the eﬃciency of execution of objective code. To solve
this issue, many researchers have proposed a lot of kinds of hardware structures and various code optimization techniques, such as register promotion,
register allocation, and loop transformation. However, the penalty of accessto the main memory tends to increase; therefore, the importance of the issue
will increase further.

6.1

Summary of Contributions

This thesis presents a new code motion-based memory hierarchy utilization optimization framework. In particular, partial redundancy elimination(PRE) plays a fundamental role in the framework. PRE removes redundant
array references by inserting expressions to suitable points in a program andreplacing them with the introduced temporary variables. The framework extends the potential of PRE to remove array references that are redundant
over iterations and suppress cache misses from occurring.
The main contributions of the framework are summarized as follows:• Removing redundant array references by eﬃcient demanddriven analysis without sacriﬁcing traditional PRE’s power
The contribution is derived from the eﬀective demand-driven PRE(EDDPRE). EDDPRE removes redundant array reference in about
half cost of the traditional PRE in combination with global value
numbering (GVN) and query propagation. When removing all redundant array references including second-order eﬀects with the traditional PRE, because it detects redundant expressions based on their88Chapter 6. Conclusion and Future Direction

lexical equality, iterative applications of copy propagation and PRE
is required for removing lexically diﬀerent expressions with the samevalue. On the other hand, GVN can reveal the redundant expressions
even if they are lexically diﬀerent. In addition, the query propagation
can shorten range to be analyzed.
• Decreasing the number of memory references by increasing the number of register references through eﬃcient query
propagation.
EDDPRE replaces redundant array references with a temporary variable holding value of inserted expressions. In addition, we extended
EDDPRE to handle array references that are redundant across several
iterations, such as scalar replacement. We named this extended EDDPRE PRE-based scalar replacement (PRESR). PRESR inserts compensation code for maintaining the behavior of a program at a lessfrequently executed point, and then it removes the redundant arrayreference. Array references accesses to cache memory whereas using
temporary variables gets the data from register; therefore, EDDPRE
and PRESR reduce the number of memory references. We showedthat PRESR can improve the eﬃciency of execution of some benchmark programs. PRESR improved the execution eﬃciency of SPEC
2000 benchmark programs about 2% on average.
• Decreasing the number of cache misses based on PRE framework.
We proposed two new cache optimization techniques, global load instruction aggregation (GLIA) and multidimensional GLIA (MDGLIA).
GLIA aggregates array references for making accesses to the same array continuous because loading data at a speciﬁc array index frommain memory places it in the cache memory along with other data
belonging to the same array. Therefore, some array references can be
executed before the reference data are removed from cache memory by
the aggregation. To achieve aggregation, we extended PRE to movethe references immediately after other preceding references to the samearray and then delaying it immediately before another reference to adiﬀerent array.
We showed that GLIA basically works well. Comparing removal ofredundant array references, the last level (L2) cache misses decreased
remarkably about 19.9% in the best case. However, the number of thecache misses increased for some programs.
In order to enhance eﬀect of aggregation, MDGLIA extended GLIA to
manage the array dimensions because a multidimensional array represents an array of lower dimensional arrays, preferentially aggregating
89

Chapter 6. Conclusion and Future Directionreferences with same indexes in higher dimensions may further decrease cache misses. MDGLIA computes the number of same indexes
as a moved candidate each preceding array reference has, and thenMDGLIA moves the candidate to the program points that are theclosest to the reference with the most similar indexes in higher dimensions.
As a result, MDGLIA could decrease L2 cache misses greater than
GLIA. Comparing MDGLIA with GLIA, L2 cache misses decreased forseveral programs. In particular, the cache misses remarkably decreased
about 15.6% in the best case.

6.2

Future Direction

This section proposes the future directions of the framework. We proposed
only code motion-based techniques; however, using others optimization may
enhance our techniques. We believe following new techniques will obtainremarkable gains from this framework, and will be demanded.

Using Sophisticated Alias Analysis
As our framework moves load statements, these techniques must consider
an alias that points to a memory location referred by another pointers forsafe movement. Pointer analysis reveals a memory location for each pointerreference [45]; therefore, whether two pointer references refer to a same
memory location or not becomes obvious [86].
To improve the precision of pointer analysis, many researchers haveproposed several algorithms. These techniques can be roughly classiﬁed
into ﬂow-sensitivity [31, 42, 43, 58, 75, 85] or ﬂow-insensitivity [41]. Flowsensitive pointer analysis calculates the pointer information at each program point along control ﬂows, whereas ﬂow-insensitive pointer analysis
ignores execution order. Furthermore, pointer analysis techniques can be divided into two classes context-sensitivity [73, 82, 88] or context-insensitivity.
Context-sensitivity considers the values of the arguments of function calls.
In this thesis, we used a very simple alias analysis. Using the state of
the art alias analysis or pointer analysis may reveal the potential of ourframework.

Proﬁle Guided MDGLIA
Although MDGLIA suppressed cache misses, it could perform more eﬀectivecode motion if it can use detailed information such as the memory addressesof array data. The reason is that main memory data are generally placed ona cache memory based on the number of cache line and associativity. This90

Chapter 6. Conclusion and Future Direction

information will enable predicting whether each array reference will resultin cache misses.

Cache Miss Sensitive Register Allocation
Although PRE is a powerful code optimization technique, the insertion andremoval processes move some expression to nodes of the CFG closer to thestart node; therefore, the register pressure tends to increase [17, 63, 83]. If a
spill occurs, some store and load instructions are inserted at some program
points. The extra execution cost derived from these additional instructions
may be greater than the improvement due to the redundancy elimination.
Because our framework is extended from PRE, our framework also tends toincrease register pressure. To suppress this cost, register allocation should
preferentially spill variables for which load/store instructions inserted byspilling result in cache hits. This cache miss sensitive register allocation
may increase the impact of PRE and our framework.

91

Bibliography[1] Aho, A. V., Sethi, R. and Ullman, J. D.: Compilers: principles,
techniques, and tools, Addison-Wesley Longman Publishing Co., Inc.,
Boston, MA, USA (1986).
[2] Aho, A. V., Lam, M. S., Sethi, R. and Ullman, J. D.: Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman
Publishing Co., Inc., Boston, MA, USA (2006).
[3] Alpern, B., Wegman, M. N. and Zadeck, F. K.: Detecting equalityof variables in programs, Proceedings of the 15th ACM SIGPLANSIGACT symposium on Principles of programming languages, POPL
’88, New York, NY, USA, ACM, pp. 1–11 (1988).
[4] Appel, A. W.: Modern Compiler Implementation in ML: Basic Techniques, Cambridge University Press, New York, NY, USA (1997).
[5] Bodik, R., Gupta, R. and Soﬀa, M. L.: Complete removal of redundant expressions, Proceedings of the ACM SIGPLAN 1998 conference
on Programming language design and implementation, PLDI ’98, New
York, NY, USA, ACM, pp. 1–14 (1998).
[6] Bodik, R. and Gupta, R.: Partial Dead Code Elimination Using Slicing
Transformations, Proceedings of the ACM SIGPLAN 1997 Conference
on Programming Language Design and Implementation, PLDI ’97, New
York, NY, USA, ACM, pp. 159–170 (1997).
[7] Bodik, R., Gupta, R. and Soﬀa, M. L.: Load-reuse analysis: designand evaluation, Proceedings of the ACM SIGPLAN 1999 conference
on Programming language design and implementation, PLDI ’99, New
York, NY, USA, ACM, pp. 64–76 (1999).
[8] Boissinot, B., Darte, A., Rastello, F., de Dinechin, B. D. and Guillon,
C.: Revisiting Out-of-SSA Translation for Correctness, Code Quality
and Eﬃciency, Proceedings of the 7th Annual IEEE/ACM International
Symposium on Code Generation and Optimization, CGO ’09, Washington, DC, USA, IEEE Computer Society, pp. 114–125 (2009).

92

Bibliography[9] Braun, M., Buchwald, S., Hack, S., Leiba, R., Mallon, C. and Zwinkau,
A.: Simple and eﬃcient construction of static single assignment form,
Proceedings of the 22nd international conference on Compiler Construction, CC’13, Berlin, Heidelberg, Springer-Verlag, pp. 102–122 (2013).
[10] Briggs, P. and Cooper, K. D.: Eﬀective Partial Redundancy Elimination, Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, PLDI ’94, New York, NY,
USA, ACM, pp. 159–170 (1994).
[11] Briggs, P., Cooper, K. D., Harvey, T. J. and Simpson, L. T.: Practical Improvements to the Construction and Destruction of Static Single
Assignment Form, Softw. Pract. Exper., Vol. 28, No. 8, pp. 859–881(1998).
[12] Briggs, P., Cooper, K. D. and Torczon, L.: Improvements to graphcoloring register allocation, ACM Trans. Program. Lang. Syst., Vol. 16,
No. 3, pp. 428–455 (1994).
[13] Cai, Q. and Xue, J.: Optimal and eﬃcient speculation-based partial redundancy elimination, Proceedings of the international symposium on
Code generation and optimization: feedback-directed and runtime optimization, CGO ’03, Washington, DC, USA, IEEE Computer Society,pp. 91–102 (2003).
[14] Calder, B., Krintz, C., John, S. and Austin, T.: Cache-conscious data
placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems,
ASPLOS-VIII, New York, NY, USA, ACM, pp. 139–149 (1998).
[15] Callahan, D., Carr, S. and Kennedy, K.: Improving register allocation
for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, PLDI
’90, New York, NY, USA, ACM, pp. 53–65 (1990).
[16] Carr, S. and Kennedy, K.: Scalar replacement in the presence of conditional control ﬂow, Softw. Pract. Exper., Vol. 24, No. 1, pp. 51–77(1994).
[17] Chaitin, G. J.: Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction,
SIGPLAN ’82, New York, NY, USA, ACM, pp. 98–105 (1982).
[18] Choi, J.-D., Cytron, R. and Ferrante, J.: Automatic Construction of
Sparse Data Flow Evaluation Graphs, Proceedings of the 18th ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’91, New York, NY, USA, ACM, pp. 55–66 (1991).
93

Bibliography[19] Chow, F., Chan, S., Kennedy, R., Liu, S.-M., Lo, R. and Tu, P.: A New
Algorithm for Partial Redundancy Elimination Based on SSA Form,
Proceedings of the ACM SIGPLAN 1997 Conference on Programming
Language Design and Implementation, PLDI ’97, New York, NY, USA,ACM, pp. 273–286 (1997).
[20] Chow, F. and Hennessy, J.: Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, SIGPLAN ’84, New York, NY, USA, ACM, pp. 222–232(1984).
[21] Click, C.: Global code motion/global value numbering, Proceedings of
the ACM SIGPLAN 1995 conference on Programming language design
and implementation, PLDI ’95, New York, NY, USA, ACM, pp. 246–
257 (1995).
[22] Cocke, J.: Global Common Subexpression Elimination, Proceedings ofa Symposium on Compiler Optimization, New York, NY, USA, ACM,
pp. 20–24 (1970).
[23] Cocke, J. and Schwarts, J. T.: Programming Languages and Their Compilers: Preliminary Notes, Courant Institute of Mathematical Sciences,
New York University (1970).
[24] COINS: http://coins-compiler.sourceforge.jp/.
[25] Cooper D., K., Harvey, T. J. and Kennedy, K.: Iterative data-ﬂow
analysis, revisited, Technical report (2004).
[26] Cooper D., K. and Xu, L.: An eﬃcient static analysis algorithm todetect redundant memory operations, Proceedings of the 2002 workshop
on Memory system performance, MSP ’02, New York, NY, USA, ACM,
pp. 97–107 (2002).
[27] Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N. and Zadeck,
F. K.: Eﬃciently Computing Static Single Assignment Form and theControl Dependence Graph, Technical report, Providence, RI, USA(1991).
[28] Dhamdhere, D. M.: A fast algorithm for code movement optimisation,
SIGPLAN Not., Vol. 23, No. 10, pp. 172–180 (1988).
[29] Dhamdhere, D. M.: E-path PRE:partial redundancy elimination madeeasy, SIGPLAN Not., Vol. 37, No. 8, pp. 53–65 (2002).
[30] Dhamdhere, D. M. and Patil, H.: An elimination algorithm for bidirectional data ﬂow problems using edge placement, ACM Trans. Program.
Lang. Syst., Vol. 15, No. 2, pp. 312–336 (1993).
94

Bibliography[31] Dillig, I., Dillig, T. and Aiken, A.: Sound, Complete and Scalable Pathsensitive Analysis, Proceedings of the 2008 ACM SIGPLAN Conference
on Programming Language Design and Implementation, PLDI ’08, New
York, NY, USA, ACM, pp. 270–280 (2008).
[32] Fernandez, M. and Espasa, R.: Link-Time Path-Sensitive Memory Redundancy Elimination, Proceedings of the 10th International Symposium on High Performance Computer Architecture, HPCA ’04, Washington, DC, USA, IEEE Computer Society, pp. 300– (2004).
[33] Fink, S. J., Knobe, K. and Sarkar, V.: Uniﬁed Analysis of Array andObject References in Strongly Typed Languages, Proceedings of the 7thInternational Symposium on Static Analysis, SAS ’00, London, UK,
UK, Springer-Verlag, pp. 155–174 (2000).
[34] Gal, A., Probst, C. W. and Franz, M.: HotpathVM: An Eﬀective JIT
Compiler for Resource-constrained Devices, Proceedings of the 2Nd International Conference on Virtual Execution Environments, VEE ’06,
New York, NY, USA, ACM, pp. 144–153 (2006).
[35] Gargi, K.: A Sparse Algorithm for Predicated Global Value Numbering,
Proceedings of the ACM SIGPLAN 2002 Conference on Programming
Language Design and Implementation, PLDI ’02, New York, NY, USA,ACM, pp. 45–56 (2002).
[36] George, L. and Appel, A. W.: Iterated register coalescing, ACM Trans.
Program. Lang. Syst., Vol. 18, No. 3, pp. 300–324 (1996).
[37] Gulwani, S. and Necula, G. C.: Global Value Numbering Using Random Interpretation, Proceedings of the 31st ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages, POPL ’04, New
York, NY, USA, ACM, pp. 342–352 (2004).
[38] Gupta, R., Berson, D. A. and Fang, J. Z.: Path Proﬁle Guided Partial
Redundancy Elimination Using Speculation, Proceedings of the 1998
International Conference on Computer Languages, ICCL ’98, Washington, DC, USA, IEEE Computer Society, pp. 230–239 (1998).
[39] Gupta, R. and Bodik, R.: Register Pressure Sensitive Redundancy
Elimination, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on
the Theory and Practice of Software, ETAPS’99, CC ’99, London, UK,
UK, Springer-Verlag, pp. 107–121 (1999).
[40] Hailperin, M.: Cost-optimal Code Motion, ACM Trans. Program. Lang.
Syst., Vol. 20, No. 6, pp. 1297–1322 (1998).

95

Bibliography[41] Hardekopf, B. and Lin, C.: The Ant and the Grasshopper: Fast andAccurate Pointer Analysis for Millions of Lines of Code, Proceedingsof the 2007 ACM SIGPLAN Conference on Programming Language
Design and Implementation, PLDI ’07, New York, NY, USA, ACM,
pp. 290–299 (2007).
[42] Hardekopf, B. and Lin, C.: Semi-sparse ﬂow-sensitive pointer analysis,
Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposiumon Principles of programming languages, POPL ’09, New York, NY,
USA, ACM, pp. 226–238 (2009).
[43] Hardekopf, B. and Lin, C.: Flow-sensitive Pointer Analysis for Millionsof Lines of Code, Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’11,
Washington, DC, USA, IEEE Computer Society, pp. 289–298 (2011).
[44] Hennessy, J. L. and Patterson, D. A.: Computer Architecture, Fifth
Edition: A Quantitative Approach, Morgan Kaufmann Publishers Inc.,San Francisco, CA, USA (2011).
[45] Hind, M. and Pioli, A.: Which Pointer Analysis Should I Use?, Proceedings of the 2000 ACM SIGSOFT International Symposium on Software
Testing and Analysis, ISSTA ’00, New York, NY, USA, ACM, pp. 113–
123 (2000).
[46] Horspool, R. N. and Ho, H. C.: Partial Redundancy Elimination Driven
by a Cost-Beneﬁt Analysis, Proceedings of the 8th Israeli Conference
on Computer-Based Systems and Software Engineering, ICCSSE ’97,
Washington, DC, USA, IEEE Computer Society, pp. 111– (1997).
[47] Ishitobi, Y., Ishihara, T. and Yasuura, H.: Code and Data Placement
for Embedded Processors with Scratchpad and Cache Memories, J. Signal Process. Syst., Vol. 60, No. 2, pp. 211–224 (2010).
[48] Kawahito, M., Komatsu, H. and Nakatani, T.: Partial redundancy elimination for access expressions by speculative code motion, Softw. Pract.
Exper., Vol. 34, No. 11, pp. 1065–1090 (2004).
[49] Kennedy, R., Chan, S., Liu, S.-M., Lo, R., Tu, P. and Chow, F.: Partial redundancy elimination in SSA form, ACM Trans. Program. Lang.
Syst., Vol. 21, No. 3, pp. 627–676 (1999).
[50] Kildall, G. A.: A Uniﬁed Approach to Global Program Optimization,
Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposiumon Principles of Programming Languages, POPL ’73, New York, NY,
USA, ACM, pp. 194–206 (1973).

96

Bibliography[51] Knoop, J., Ruthing, O. and Steﬀen, B.: Lazy code motion, Proceedingsof the ACM SIGPLAN 1992 conference on Programming language design and implementation, PLDI ’92, New York, NY, USA, ACM, pp.
224–234 (1992).
[52] Knoop, J., Ruthing, O. and Steﬀen, B.: Optimal code motion: theory
and practice, ACM Trans. Program. Lang. Syst., Vol. 16, No. 4, pp.
1117–1155 (1994).
[53] Knoop, J., Ruthing, O. and Steﬀen, B.: Partial dead code elimination,
Proceedings of the ACM SIGPLAN 1994 conference on Programming
language design and implementation, PLDI ’94, New York, NY, USA,ACM, pp. 147–158 (1994).
[54] Lin, J., Chen, T., Hsu, W.-C., Yew, P.-C., Ju, R. D.-C., Ngai, T.-F.
and Chan, S.: A Compiler Framework for Speculative Analysis andOptimizations, Proceedings of the ACM SIGPLAN 2003 Conference on
Programming Language Design and Implementation, PLDI ’03, New
York, NY, USA, ACM, pp. 289–299 (2003).
[55] Lo, R., Chow, F., Kennedy, R., Liu, S.-M. and Tu, P.: Register promotion by sparse partial redundancy elimination of loads and stores,
Proceedings of the ACM SIGPLAN 1998 conference on Programming
language design and implementation, PLDI ’98, New York, NY, USA,ACM, pp. 26–37 (1998).
[56] Lu, J. and Cooper, K. D.: Register promotion in C programs, Proceedings of the ACM SIGPLAN 1997 conference on Programming language
design and implementation, PLDI ’97, New York, NY, USA, ACM, pp.
308–319 (1997).
[57] Morel, E. and Renvoise, C.: Global optimization by suppression ofpartial redundancies, Commun. ACM, Vol. 22, No. 2, pp. 96–103 (1979).
[58] Nasre, R.: Time- and Space-eﬃcient Flow-sensitive Points-to Analysis,
ACM Trans. Archit. Code Optim., Vol. 10, No. 4, pp. 39:1–39:27 (2013).
[59] Nie, J. T. and Cheng, X.: An eﬃcient SSA-based algorithm for complete
global value numbering, Proceedings of the 5th Asian conference on
Programming languages and systems, APLAS’07, Berlin, Heidelberg,
Springer-Verlag, pp. 319–334 (2007).
[60] Odaira, R. and Hiraki, K.: Partial Value Number Redundancy Elimination, Information Processing Society of Japan Transactions on
Programming, Vol. 45, No. SIG09(PRO22), pp. 59–79 (2004). (inJapanese).

97

Bibliography[61] Odaira, R., Nakaike, T., Inagaki, T., Komatsu, H. and Nakatani, T.:
Coloring-based coalescing for graph coloring register allocation, Proceedings of the 8th annual IEEE/ACM international symposium on
Code generation and optimization, CGO ’10, New York, NY, USA,ACM, pp. 160–169 (2010).
[62] PAPI: http://icl.cs.utk.edu/papi/.
[63] Poletto, M. and Sarkar, V.: Linear scan register allocation, ACM Trans.
Program. Lang. Syst., Vol. 21, No. 5, pp. 895–913 (1999).
[64] Rastello, F., Ferriere, F. d. and Guillon, C.: Optimizing Translation
Out of SSA Using Renaming Constraints, Proceedings of the International Symposium on Code Generation and Optimization: Feedbackdirected and Runtime Optimization, CGO ’04, Washington, DC, USA,IEEE Computer Society, pp. 265– (2004).
[65] Reif, J. H. and Lewis, H. R.: Symbolic Evaluation and the Global Value
Graph, Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on
Principles of Programming Languages, POPL ’77, New York, NY, USA,ACM, pp. 104–118 (1977).
[66] Rishi, S., Rajkishore, B., Jisheng, Z. and Vivek, S.: Inter-iteration
Scalar Replacement Using Array SSA Form, Proceedings of the 23rd
international conference on Compiler Construction, CC’14, Berlin, Heidelberg, Springer-Verlag, pp. 40–60 (2014).
[67] Rosen, B. K., Wegman, M. N. and Zadeck, F. K.: Global value numbers
and redundant computations, Proceedings of the 15th ACM SIGPLANSIGACT symposium on Principles of programming languages, POPL
’88, New York, NY, USA, ACM, pp. 12–27 (1988).
[68] Ruthing, O.: Optimal Code Motion in the Presence of Large Expressions, Proceedings of the 1998 International Conference on Computer
Languages, ICCL ’98, Washington, DC, USA, IEEE Computer Society,pp. 216–225 (1998).
[69] Ruthing, O., Knoop, J. and Steﬀen, B.: Detecting Equalities of Variables: Combining Eﬃciency with Precision, Proceedings of the 6th International Symposium on Static Analysis, SAS ’99, London, UK, UK,
Springer-Verlag, pp. 232–247 (1999).
[70] Ruthing, O., Knoop, J. and Steﬀen, B.: Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles ofprogramming languages, POPL ’00, New York, NY, USA, ACM, pp.
170–183 (2000).

98

Bibliography[71] Sarkar, S. and Tullsen, D. M.: Compiler techniques for reducing data
cache miss rate on a multithreaded architecture, Proceedings of the 3rdinternational conference on High performance embedded architecturesand compilers, HiPEAC’08, Berlin, Heidelberg, Springer-Verlag, pp.
353–368 (2008).
[72] Scholz, B., Horspool, N. and Knoop, J.: Optimizing for Space and Time
Usage with Speculative Partial Redundancy Elimination, Proceedingsof the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES ’04, New York, NY,
USA, ACM, pp. 221–230 (2004).
[73] Shang, L., Xie, X. and Xue, J.: On-demand Dynamic Summary-based
Points-to Analysis, Proceedings of the Tenth International Symposiumon Code Generation and Optimization, CGO ’12, New York, NY, USA,ACM, pp. 264–274 (2012).
[74] Sreedhar, V. C., Ju, R. D.-C., Gillies, D. M. and Santhanam, V.: Translating Out of Static Single Assignment Form, Proceedings of the 6th International Symposium on Static Analysis, SAS ’99, London, UK, UK,
Springer-Verlag, pp. 194–210 (1999).
[75] Sui, Y., Ye, S., Xue, J. and Yew, P.-C.: SPAS: Scalable Path-sensitive
Pointer Analysis on Full-sparse SSA, Proceedings of the 9th Asian Conference on Programming Languages and Systems, APLAS’11, Berlin,
Heidelberg, Springer-Verlag, pp. 155–171 (2011).
[76] Sumikawa, Y., Ojima, R. and Takimoto, M.: Demand-driven Scalar
Replacement, Computer Software (2014). (in Japanese), to appear.
[77] Sumikawa, Y. and Takimoto, M.: Global Load Instruction Aggregation
Based on Code Motion, Proceedings of the 2012 Fifth International
Symposium on Parallel Architectures, Algorithms and Programming,
PAAP ’12, Taipei, IEEE Computer Society, pp. 149–156 (2012).
[78] Sumikawa, Y. and Takimoto, M.: Eﬀective Demand-driven Partial Redundancy Elimination, Information Processing Society of Japan Transactions on Programming, Vol. 6, No. 2, pp. 33–44 (2013).
[79] Sumikawa, Y. and Takimoto, M.: Global Load Instruction Aggregation
Based on Array Dimensions, Proceedings of the 2014 Sixh International
Symposium on Parallel Architectures, Algorithms and Programming,
PAAP ’14, Washington, DC, USA, IEEE Computer Society, pp. 123–129 (2014).
[80] Takimoto, M.: Speculative Partial Redundancy Elimination Based on
Question Propagation, Information Processing Society of Japan Transactions on Programming, Vol. 2, No. 5, pp. 15–27 (2009). (in Japanese).
99

Bibliography[81] VanDrunen, T. and Hosking, A. L.: Value-based partial redundancy
elimination, In CC, pp. 167–184 (2004).
[82] Whaley, J. and Lam, M. S.: Cloning-based Context-sensitive PointerAlias Analysis Using Binary Decision Diagrams, Proceedings of the
ACM SIGPLAN 2004 Conference on Programming Language Design
and Implementation, PLDI ’04, New York, NY, USA, ACM, pp. 131–
144 (2004).
[83] Wimmer, C. and Franz, M.: Linear scan register allocation on SSA
form, Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, CGO ’10, New York, NY,
USA, ACM, pp. 170–179 (2010).
[84] Xue, J. and Cai, Q.: A Lifetime Optimal Algorithm for Speculative
PRE, ACM Trans. Archit. Code Optim., Vol. 3, No. 2, pp. 115–155(2006).
[85] Yu, H., Xue, J., Huo, W., Feng, X. and Zhang, Z.: Level by Level: Making Flow- and Context-sensitive Pointer Analysis Scalable for Millionsof Lines of Code, Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO ’10,
New York, NY, USA, ACM, pp. 218–229 (2010).
[86] Zheng, X. and Rugina, R.: Demand-driven alias analysis for C, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on
Principles of programming languages, POPL ’08, New York, NY, USA,ACM, pp. 197–208 (2008).
[87] Zhou, H., Chen, W. and Chow, F.: An SSA-based algorithm for optimal
speculative code motion under an execution proﬁle, Proceedings of the
32nd ACM SIGPLAN conference on Programming language design andimplementation, PLDI ’11, New York, NY, USA, ACM, pp. 98–108(2011).
[88] Zhu, J. and Calman, S.: Symbolic Pointer Analysis Revisited, Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI ’04, New York, NY, USA,ACM, pp. 145–157 (2004).

100