TECHNICAL REPORT 04-01

Partial Value Number Redundancy Elimination

Rei Odaira and Kei Hiraki

June 9, 2004

ÌDepartment of Information Science
Faculty of Science, University of Tokyo
7–3–1 Hongo, Bunkyo-Ku Tokyo, 113 JapanTECHNICAL REPORT 04-01
TITLE
Partial Value Number Redundancy Elimination

AUTHORSRei Odaira and Kei Hiraki

KEY WORDS AND PHRASES
partial redundancy elimination, global value numbering, optimizing compiler, just-in-time compiler, runtime compiler, Java virtual machine
ABSTRACT
When developing a redundancy elimination algorithm for a runtime optimizing compiler, not only its optimizing power but also its analysis speed must be considered. We propose a fast and eﬃcient algorithm
called Partial Value Number Redundancy Elimination (PVNRE), which completely fuses Partial Redundancy Elimination (PRE) and Global Value Numbering (GVN). Using value numbers in the data-ﬂow
analyses, PVNRE can deal with data-dependent redundancy, and can quickly remove path-dependent
partial redundancy by converting value numbers at join nodes on demand during the data-ﬂow analyses.
Compared with the naive combination of GVN, PRE, and copy propagation, PVNRE has a maximum
45% faster analyses speed, but the same optimizing power on SPECjvm98.

REPORT DATE
June 9, 2004

WRITTEN LANGUAGE
EnglishTOTAL NO. OF PAGES
24

NO. OF REFERENCES
19

ANY OTHER IDENTIFYING INFORMATION OF THIS REPORTDISTRIBUTION STATEMENTFirst issue 30 copies.

SUPPLEMENTARY NOTESDEPARTMENT OF INFORMATION SCIENCE
Faculty of Science, University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan

Partial Value Number Redundancy Elimination
Rei Odaira and Kei Hiraki,
Department of Computer Science,
Graduate School of Information Science and Technology,
University of Tokyo
7-3-1, Hongo, Bunkyo-ku, Tokyo, Japan{ray, hiraki}@is.s.u-tokyo.ac.jp

Abstract
When developing a redundancy elimination algorithm for a runtime optimizing compiler, not only
its optimizing power but also its analysis speed must be considered. We propose a fast and eﬃcientalgorithm called Partial Value Number Redundancy Elimination (PVNRE), which completely fusesPartial Redundancy Elimination (PRE) and Global Value Numbering (GVN). Using value numbersin the data-ﬂow analyses, PVNRE can deal with data-dependent redundancy, and can quickly remove
path-dependent partial redundancy by converting value numbers at join nodes on demand during
the data-ﬂow analyses.
Compared with the naive combination of GVN, PRE, and copy propagation, PVNRE has amaximum 45% faster analyses speed, but the same optimizing power on SPECjvm98.

1

Introduction

Runtime optimizing compilers have recently gained widespread use in Java and other execution environments. A runtime optimizing compiler needs to keep analysis time short, but at the same time, it
must reduce the execution time of generated code. Thus, the development of fast and eﬃcient advanced
optimizations has become increasingly important. In this paper, we aim to manage both optimizing
power and analysis speed of redundancy elimination, an optimization that is frequently used in modern
optimizing compilers [15].
Redundancy elimination is an optimizing technique that removes instructions that compute the samevalue as previously executed instructions. Partial Redundancy Elimination (PRE) [2, 3, 4, 12, 13, 14] andGlobal Value Numbering (GVN) [1, 5, 7, 8] are the most widely used redundancy elimination algorithms.
PRE can eliminate redundancy on at least one (but not necessarily all) execution path leading toan instruction (that is, partial redundancy). It deals with lexically identical instructions between which
there is no store for any of their operand variables. To remove the redundancy it has to solve three
data-ﬂow equations for availability (AVAIL) and anticipatability (ANTIC ) of instructions.
On the other hand, GVN can remove instructions that compute the same value on all paths evenwhen they are lexically diﬀerent. GVN uses value numbering, which is an algorithm to detect redundancy
by assigning the same value number to a group of instructions that can be proved to compute the samevalue by static analysis. One GVN variants called the bottom-up method uses a hash table to assign value
numbers to instructions [15]. It ﬁrst transforms the whole program into the Static Single Assignment(SSA) form [9] and then searches the hash table, using an operator for each instruction and the value
numbers of its operands as a key to the table. If the key has already been registered, a redundant
instruction is then found. If not, it generates a new value number and registers it to the table together
with the key. After value numbering, GVN performs dominator-based or availability-based redundancy
elimination, which removes instructions dominated by ones with the same value numbers, or instructions
whose value numbers are available.
Because of their complementary power, most modern optimizing compilers perform both GVN and
PRE [15]; that is, they ﬁrst perform GVN, then convert the program back into the non-SSA form, andﬁnally execute PRE.
1

Table 1: Eight types of redundancy

total
partialdata independent
path independent
path dependent(I): PRE, GVN(II): PRE
(III): PRE(IV): PREdata dependent
path independent
path dependent(V): GVN(VI)(VII)(VIII)

There are, however, three types of redundancy in ordinary programs that neither of these methods
can eliminate, as described in Section 2. Thus, we need to perform PRE and copy propagation (CP)iteratively after GVN[16]; we make as many instructions lexically identical as possible by propagating
copy instructions generated by the previous PRE, and remove the now-lexically-identical instructions
by the next PRE. In other words, from the upper stream of data dependency, we must perform both
PRE and CP for each depth level of the dependency, because PRE cannot deal with data dependency
in one pass. Therefore, this algorithm suﬀers from an overhead due to the iteration, which a runtime
optimizing compiler cannot ignore.
In this report, we propose Partial Value Number Redundancy Elimination (PVNRE), which fuses
GVN and PRE, and removes the need for the iteration of PRE and CP. PVNRE performs PRE-likedata-ﬂow analyses, in which it uses not the lexical appearances of instructions but rather their value
numbers as GVN does. In contrast to PRE, PVNRE can deal with data dependency between value
numbers during data-ﬂow analyses, and avoid the iteration of PRE and CP. Thus, it is as powerful as,
and faster than the combination of GVN and the iteration of PRE and CP.
The main contributions of our work are as follows.
• PVNRE is the ﬁrst redundancy elimination algorithm that tackles the iteration of PRE and CP,
and succeeds in managing both optimizing power and analysis speed.
• To allow PVNRE to include the powerful features of PRE, we developed a new algorithm to convert
value numbers through φ functions of the SSA form on demand during data-ﬂow analyses. Thus,
we need not construct any special representation of redundancy such as a Value Flow Graph [19]in advance of the analyses.
• We show that by assigning incremental value numbers to instructions the numbers can themselvesrepresent data dependency. PVNRE is the ﬁrst method that exploits this property in processing
the value numbers in the order of their data dependency during data-ﬂow analyses.
• We present the eﬀectiveness of PVNRE by implementing it in our just-in-time compiler and conducting experiments using real benchmarks.
The rest of the report is organized as follows. Section 2 presents the types of redundancy we deal
with in this report, and explains the ineﬃciencies of the existing algorithms to remove such redundancies.
Section 3 and 4 introduce the overview of PVNRE and basic notations. Section 5 describes the algorithmof PVNRE and Section 6 shows the experimental results. Section 7 reviews related work, and Section 8
sets out the conclusion.

2

BackgroundWe categorize the redundancy we deal with in this report into eight types (Type I – VIII) as shown in
Table 1. We also show in the table which types of redundancy PRE and GVN can detect and eliminate.
Figure 1 illustrates the four types of redundancy PRE can detect. PRE removes the computationsof Instructions (Insns.) 3, 7, 12, 15, and 19 by using a temporary variable “t” as exempliﬁed in TypeIV(b) of the ﬁgure.
In contrast, GVN can detect Types I and V. Precisely speaking, availability-based GVN can detectboth (1) and (2) of Type I in Fig. 1, while dominator-based GVN can detect only (1).
GVN cannot detect Type II because of the path-dependent redundancy; depending on the execution
path that leads to it, Insn. 12 computes diﬀerent values, since “a” refers to the diﬀerent deﬁnitions(Insns. 8 and 10). The path-dependency becomes clearer if we convert the program into the SSA form
2

Type I (1)12Type I (2)4a := read()x := a + 1
5

3

Type IIa := read()x := a + 1

68
9

a := read()x := a + 1

10 a := read()
11 y := a + 1

y := a + 1

z := a + 1
12 z := a + 1
7

Type III
13 a := read()z := a + 1

Type IV (a)Type IV (b)16 a := read()
17 x := a + 1

14 x := a + 1

18 a := read()

16 a := read()
17 t := a + 1

18 a := read()t := a+ 1

x := t15 z := a + 1

19 z := a + 1

19 z := tFigure 1: Examples of optimization by PRE
Type II
8
9Type V (a)a0 := read()x := a0 + 1

10 a1 := read()
11 y := a1 + 1

a2 := φ(a0, a1)
12 z := a2 + 1

1
2
3
4
5

Type V (b)a := read()b := a + 1
c := b + 2

b := a + 1
y := b + 2

1
2
3
4
5

a := read()b := a + 1
c := b + 2

b := by := cFigure 2: Examples of optimization by GVN
as in Fig. 2 Type II. The newly inserted φ function is a pseudo function that merges more than one
deﬁnitions of a variable at a join node. Thus, Insns. 8, 10, and the φ function are assigned distinct value
numbers, and so are Insns. 9, 11, and 12, which makes it impossible to detect the redundancy amongthem.
The reason GVN cannot detect Type III is that Insn. 14 does not dominate Insn. 15, nor make thevalue number of “a + 1” available at Insn. 15 due to its partial redundancy. Type IV in Fig. 1 is acombination of Types II and III, so that it also cannot be detected by GVN.
Figure 2 Type V illustrates the type of redundancy GVN can remove but PRE cannot. Insns. 2 and4, and 3 and 5 are assigned the same value numbers; hence, we can eliminate the redundancy by using
the transformation shown in (b). In particular, although Insns. 3 and 5 are lexically identical, their
redundancy cannot be removed by PRE because there is a store for the operand between them (Insn. 4),
or in other words, because they are data-dependent on diﬀerent instructions (Insns. 2 and 4). Therefore,
we call this type of redundancy between Insns. 3 and 5 a data-dependent redundancy.
As described in Sect. 1, most modern optimizing compilers perform both GVN and PRE; but othertypes of redundancy (Fig. 3), which neither of them can eliminate, can also be encountered in real
programs. For example, a data-dependent chain of loop invariants, which can frequently be found in
address computations of loop-invariant array loads, is one of the variants of Type VII as shown in Fig.
3 Type VII (2).
Thus, after GVN, we have to perform PRE and copy propagation (CP) iteratively to completely
eliminate such redundancies 1 . For example, in Fig. 4, (a) is the same as Type VII (2) in Fig. 3. The
ﬁrst PRE moves Insn. 7 out of the loop (b). It cannot move Insn. 8 because this is data-dependent
on Insn. 7. The generated copy instruction is then propagated to Insn. 8 (c). Finally, since the data
dependency has been removed, the second PRE can move Insn. 8 out of the loop (d). The redundancies
of Types VI and VIII in Fig. 3 can be eliminated in the same manner.
The diagram of the resulting algorithm, which we call GVN+PRECP, is shown in the left-hand sideof Fig. 5. However, the ineﬃciencies in the algorithm are as follows.
• To collect the local information of instructions in PRE, a hash table is used to number each lexicalappearance of instructions. This operation is similar to value numbering in GVN.
1 In fact, if we iterate PRE and CP, we need not perform GVN from the point of view of optimizing ability. However,
we should perform GVN first because it can eliminate Type V much faster than the iteration of PRE and CP.

3

Type VI

Type VII (1)123a := read()

9 a := read()10 b := a + 1
11 c := b + 2

b := a + 1
c := b + 2

15
16
4
5

b := a + 1
c := b + 2

a := read()78

b := a + 1
c := b + 2

a := read()b := a + 1
c := b + 2

b := a + 1
c := b + 2

Type VIII

Type VII (2)
6

12
13
14

17
18
19

a := read()b := a + 1
c := b + 2

21
22

20

a := read()b := a + 1
c := b + 2

Figure 3: GVN+PRE cannot optimize these types of redundancy(a)
6 a := read()

7 b := a + 1
8 c := b + 2

(b)

(c)

6 a := read()
7 s := a + 1(d)

6 a := read()
7 s := a + 1

6 a := read()
7 s := a + 1
8 t := s + 2

b := sb := s8 c := b + 2

8 c := s + 2

b := sc := tFigure 4: Sequence of optimization by iteration of PRE and CP• In spite of the fact that copy propagation is trivial in the SSA form, we cannot perform it in thatform during PRECP because PRE is based on a non-SSA form.
• For each iteration of the loop, we must set up data structures and collect information for all
instructions in the program, although most of them might be unaﬀected by that iteration.
In the next section, we describe PVNRE, a redundancy elimination algorithm which overcomes these
ineﬃciencies of GVN+PRECP.

3

Overview of PVNRE Algorithm

PVNRE aims to provide equal or better optimizing power with faster analysis speed than GVN+PRECP.
The overview of the algorithm is shown on the right-hand side of Fig. 5. The main features of thisalgorithm are as follows.
• Using value numbers in the PRE-like data-ﬂow analyses, it can detect not only the redundancies
of Types I and V like GVN, but also partial redundancies, particularly Types III and VII. (Sect.
5.1, 5.3, and 5.8)
• Path-dependent redundancy is detected by converting value numbers through φ functions on demand during data-ﬂow analyses. It is worth noting that the reason GVN cannot detect the pathdependent redundancy is the existence of φ functions in the SSA form. (Sect. 5.4, 5.5, and 5.6)
• PVNRE assigns value numbers so that the numerical order can represent data dependency. This
constraint allows it to deal with data-dependent redundancy during data-ﬂow analyses and redundancy elimination. (Sect. 5.1, 5.4, 5.5, and 5.10)• Instead of iterating PRE and CP for all instructions, PVNRE uses iterations for only the essential
subset of the instructions; it iterates the value number conversion at the innermost loop of data-ﬂow
analyses to detect the redundancies of Types VI and VIII. Thus, it is faster than GVN+PRECP.
(Sect. 5.4 and 5.5)
4

GVN + PRECP

PVNRE

Set up data structures

Set up data structures

Assign value numbers

Assign value numbers

Eliminate redundancy
based on dominator oravailability

Solve four data flow
equation systems withvalue number conversion

Do global copy propagation
Convert the program
into a non-SSA form

Eliminate redundancy

Set up data structures

Recover the SSA property+ global copy propagation

Collect local information
Solve three data flow
equation systems
Eliminate redundancy
Do global copy propagation

Figure 5: GVN+PRECP and PVNRE algorithms• PVNRE performs copy propagation on the SSA form. (Sect. 5.4)
In fact, PVNRE can remove redundancies beyond the ones listed in Table 1, but such types of redundancy
are rarely found in real programs.

4

Preliminaries

Without loss of generality, we make the following assumptions about a program.
• The program has already been transformed into the SSA form.
• The control ﬂow graph is reducible.
• The nesting relationship of the loops has already been analyzed.
• The critical edges have already been removed.
• Each basic block has at most two preceding blocks, which implies that every φ function is binary.
A program is a directed graph G = Nodes, Edges, start, end  with the instruction set Nodes, theedge set Edges, the unique start instruction start, and the unique end instruction end . m→n denotes
an edge from m to n. BBNodes represents the basic block set. Pred (N ) denotes the preceding blocks ofN ∈ BBNodes, Succ(N ) the succeeding blocks, Head (N ) the ﬁrst instruction, and BB (n) the block towhich n ∈ Nodes belongs.
P [m, n] represents the set of all the paths from m to n. λ(p) is the length of a path p, and pi is its ith
instruction (1 ≤ i ≤ λ(p)). In addition, p[i, j] indicates the sub-path from the ith to the jth instruction.
Value(p, i) denotes the value computed by the ith instruction on p
The set of all operators Operators consists of arithmetic operators Normal , a copy operator Copy ,φ functions Phi , and the other operators Fixed . Fixed includes function calls and memory operators.
We deﬁne Op as a function from each instruction to its operator (Nodes → Operators), writing n.Op forn ∈ Nodes, and φN as an operator of a φ function in a block N .
As with Phi , we assume that Normal has exactly two operands and Copy has only the left operand.
We deﬁne Lt and Rt as functions from each instruction to its operands (Nodes → Nodes), writing n.Lt
and n.Rt. However, when there is no need to distinguish between them, we write one of them as n.X
and the other as n.Y .
5The value number set Nums is a subset of natural numbers N , and a value numbering Num can bedeﬁned as a function of Nodes → Nums. We make Op, Lt , and Rt also take the roles of functions fromeach value number to its operator and operand value numbers, respectively.

5

Algorithm Details

5.1

Value Numbering

The value numbering in PVNRE shown in Fig. 6 is the same as that for GVN, except that (1) it
computes backedges (Bedges ) and transparency (UnTransp), and (2) it must assign incremental value
numbers (Line 9 and 26). GEN is used as local information in the following data-ﬂow analyses. Backedges
and transparency is described in Sect. 5.3.
Incremental value numbers ensures the following constraint (Deﬁnition 5.1), which means that Insn.
x is assigned a greater number than Insn. y if x is data-dependent on y. This is because in value
numbering we must number instructions in the data dependency order (the reverse post order in Line 5
and the pre-order in Line 7), so that we can use the value numbers of the left and right operands as a
key to the hash table.
Definition 5.1 (Numerical Order Constraint). For α ∈ Nums,
α.Op ∈ Normal ⇒ α.X < α .
PVNRE utilizes this numerical order in the following data-ﬂow analyses to process value numbers indata dependency order.

5.2

Data-Flow Analyses

After value numbering, PVNRE solves four data-ﬂow equation systems for AVAILall , AVAILsome ,ANTIC all , and AVAILMsome . These are the framework for PRE proposed by Bodik et al. [3]. AVAILall
and AVAILsome represent the availability on all paths and some paths respectively, while ANTIC all
denotes the anticipatability on all paths. AVAILMsome is akin to AVAILsome , but a condition is added
to prevent speculative insertion of instructions. We refer readers to the paper by Bodik et al. [3] formore details about these predicates. Here, we focus on the diﬀerences between their work and PVNRE,
namely, transparency and value number conversion.

5.3

Transparency

Transparency is a condition that determines whether or not data-ﬂow information is valid beyond a
block or an edge in data-ﬂow analysis. In traditional PRE, the propagated information (AVAIL or
ANTIC ) of an instruction is invalidated if a block contains a store for an operand variable of the
instruction. PVNRE, on the other hand, does not need such kind of condition because it can deal with
data-dependent redundancy as illustrated in Fig. 2 Type V.
In PVNRE, however, we need special treatment for backedges. For example, in Fig. 7(1), if weallowed the AVAIL of the value numbers of Insn. 6 to ﬂow through the backedge, the information would
reache Insn. 6 again; hence, we would consider it to be a loop invariant However, since Insn. 6 is aninduction variable, this does not happen and it returns diﬀerent values for each iteration of the loop.
To solve the problem, we deﬁne transparency for value numbers and backedges: the value numbersof instructions that may compute diﬀerent values for each iteration of a loop are invalidated at thebackedge of the loop. The reason an instruction computes diﬀerent values for each iteration is that it isdata-dependent on a φ function or a function call inside the loop. Thus, we ﬁrst deﬁne DefBBNodes for
Fixed and Phi value numbers, which is a set of the basic blocks containing instructions that generate avalue number.

6

1 for each e ∈ Edges do
2 UnTransp(e) := ∅3 end
4 VN := 0
5 for each N ∈ BBNodes in reverse post order do
6 GEN (N ) = ∅7 for each n ∈ N in pre-order do
8
if n.Op ∈ Fixed , Phi then9
VN := VN + 1
10
VN .Op := n.Op
11
Bedges(VN ) := the set of the enclosing backedges of N
12
Num(n) := VN
13else if n.Op ∈ Copy then14
Num(n) := Num(n.Lt)
15
else
16
α := call Hash(n.Op, Num(n.Lt ), Num(n.Rt ))17
Num(n) := α18
GEN (N ) := GEN (N ) ∪ {α}19end
20 end21 end22
23 Hash(op, l, r) {24 If op, l, r is registered, returns the corresponding VN .
25 If not,26 VN := VN + 1
27 Register VN with op, l, r.
28 VN .Op := op; VN .Lt := l ; VN .Rt := r
29 Bedges(VN ) := Bedges(l ) ∪ Bedges(r )30 for each b ∈ Bedges(VN ) do
31
UnTransp(b) := UnTransp(b) ∪ {VN }32 end33 return VN
34 }Figure 6: Algorithm for value numbering

BB1
1

1

i0 := read()
Value No. Transp Description

BB2
2
3
4
5
6

2
3
4
5
6

i1 := φBB2(i0, i2)
a := i0 + 1
b := read()c := i0 + bi2 := i1 + 1

BB3
2
4
7

7
8
9

x := i1y := bz := x + y

bedge

1
2
3

4
5
6
7

true DefBBNodes(1) is outside the loop.
false DefBBNodes(2) is inside the loop.
true It is inside the loop, but its operand refers to
the value number of the instrucion outside
the loop, so it is loop-invariant.
false DefBBNodes(4) is inside the loop.
false One of its operand refers to the value numberof the instruction inside the loop.
false The same as 5.
false It is outside the loop, but its operands refer tothe value numbers of the instructions inside
the loop.

Figure 7: Example of backedge and transparency

7

Definition 5.2 (DefBBNodes for Fixed ). For α ∈ Nums s.t. α.Op ∈ Fixed ,DefNodes(α)
DefBBNodes(α)

def

=

def

=

{n ∈ Nodes | Num(n) = α ∧ n.Op = α.Op}BB (n) s.t. n ∈ DefNodes(α) .
∀nDefinition 5.3 (DefBBNodes for Phi ).
def

For α ∈ Nums s.t. α.Op = φN ∈ Phi , DefBBNodes (α) = {N } .
In Fig. 7, DefBBNodes (2 ) = {BB2} and DefBBNodes (4 ) = {BB2}. Since Insn. 7 and 8 are copy
instructions, they are not considered to generate their own value numbers.
5.3.1

Backedges
defBackedges can be deﬁned as Bedges = {m→n | n dom m}, where dom denotes domination relationship.
Here, we deﬁne backedges for each instruction and block as follows.
Definition 5.4 (Backedges for an instruction and a basic block).
For u ∈ Nodes and N ∈ BBNodes,
Bedges(u)Bedges(N )def={e = m→n | e ∈ Bedges ∧ ∃p ∈ P [u, m] ∀1 ≤ i ≤ λ(p) . pi = n}defBedges(Head (N )) .

=That is, they represent all the backedges of the loops enclosing the instruction or the block. In Fig. 7,
Bedges for Insn. 2–6 and BB2 is {bedge}, and Bedges for the other instructions is ∅.
5.3.2

Transparency

We deﬁne the transparency in PVNRE as follows.
Definition 5.5 (Transp). For α ∈ Nums and e ∈ Edges,(1) if α.Op ∈ Fixed ∨ α.Op ∈ Phi , then
def/Bedges(N ) s.t. N ∈ DefBBNodes(α),
Transp(α, e) ⇔ e ∈∀N(2) otherwise
defTransp(α, e) ⇔ Transp(α.Lt , e) ∧ Transp(α.Rt, e) .
A Fixed value number is not allowed to propagate through the enclosing back-edges because we assume
that a memory load or a function call returns diﬀerent values each time it is executed. Propagation is notallowed for Phi in the same way because we cannot determine statically which of the merged deﬁnitions
is actually referred to for each execution. For Normal , its value is considered to be invalid beyond abackedge of a loop iﬀ. one of its operands’ values is invalid beyond the backedge. Figure 7 shows Transp
for bedge for each value number.
We also naturally extend the deﬁnition of Transp to any path.
Definition 5.6 (Transp ∀ ).
For α ∈ Nums, p ∈ P [start , end ], 1 ≤ i < j ≤ λ(p),Transp ∀ (α, p[i, j ]) ⇔defTransp(α, pk →pk +1 ) .

∀i≤k <jDuring value numbering, PVNRE computes the enclosing backedges for a φ function and a function
call (Fig. 6 Line 11). Other instructions inherit backedges from the data-dependent instructions (Line29), and register themselves to UnTransp (the complementary set of the transparency) for the backedges(Line 30 – 32).
Alternatively, we could invalidate value numbers not at the backedges but at the φ functions or thefunction calls on which they are data-dependent. However, if we did so we would need to compute
UnTransp for all the basic blocks, and set up upward and downward GEN separately, which would
result in longer analysis time. To the best of our knowledge, PVNRE is the ﬁrst redundancy elimination
algorithm to use backedge-based transparency.
8

BB1
1 1 a0 := read()
2 2 b := a0 + 1
3 3 c := b + 2

BB2
4 4 a1 := read()
5 5 m := a1 + 1
6 6 n := m + 2

AVAIL 2, 3

AVAIL 5, 6
BB3
1 4
AVAIL 8, 9
7 7 a2 := φ(a0, a1)
8 8 x := a2 + 1
9 9 y := x + 2

JT(BB3) JT’(BB3) Hash Table
t l r
7 1 4

t

7 1 4
8 2 5

8 2 5

7 1 4
8 2 5
9 3 6

8 2 5
9 3 6

l

r

op l
2 + 1
3 + 2
5 + 4
6 + 5
8 + 7
9 + 8

r
const1const2const1const2const1const2

Figure 8: Example of value number conversion for Type II and VI

5.4

Examples of Value Number Conversion

If we only propagate value numbers on PRE-like data-ﬂow analyses, we cannot detect path-dependent
redundancies (Types II, IV, VI, and VIII) as we described in Sect. 2. To solve the problem, we convert
value numbers at join nodes on demand during data-ﬂow analyses, using φ functions.
PVNRE uses two sets, JT (N ) and JT  (N ), which are deﬁned for each join node N . Their elements
are of the form t, l, r, which means “value number l and r join at N , and are converted into t.”
JT (N ) is initialized by the φ functions in N in the original program, and JT  (N ) is set to ∅. PVNRE
uses and adds elements to JT and JT  while solving AVAILall and AVAILsome . To solve ANTIC all and
AVAILMsome , it just uses JT  , adding no more elements.
5.4.1

Types II and VI (Path-Dependent Total Redundancy).

We use the example in Fig. 8. Value numbers (italic numbers 1 – 9 ) are already assigned as the hashtable shows. Assume that we are now processing basic block 3 (BB3) for the ﬁrst time while we arecomputing the maximum ﬁxed points for AVAILall and AVAILsome . JT is initialized as {7 , 1 , 4 } by
the φ function (Insn. 7).
some(BB3). 2 and 3 are available from the left,
Now we have to compute AVAILallin (BB3) and AVAILin
so that we process 2 ﬁrst, utilizing the constraints between the numerical order and the data dependency
described in Sect. 5.1. We search the “l ” column of JT for 1 (the left operand of 2 ). We need not search
for the right operand, because it is constant 1, and is not subject to conversion. We ﬁnd an element in
JT 2 , which indicates that 1 merges with 4 and is converted into 7. Now we search the hash table for“4 + const1” and “7 + const1,” ﬁnding 5 and 8. Thus we add a new element 8 , 2 , 5  to JT andJT  . In the same manner, we process 3 and add another element 9 , 3 , 6 . Note that if we process 3
ﬁrst, we cannot convert either 2 or 3. Then we process 5 and 6 from the right, but we need not add any
some= {2 , 3 , 5 , 6 , 8 , 9 }. We propagate themmore elements. Consequently, AVAILall
in = {8 , 9 }, AVAILin
into BB3, and ﬁnally detect the redundancy of Insn. 8 (Type II) and Insn. 9 (Type VI), because theirvalue numbers are available. When we process BB3 again during the computation of the maximum ﬁxed
points, we need not repeat the process again for 2, 3, 5, and 6, but just use JT  . In the same way, we
also use JT  to compute ANTIC all and AVAILMsome .
Indeed, it is not mandatory to compute AVAILsome , but we do so in order to speed up the analyses
that follow; if not, we would have to update JT  , even during the computation of ANTIC all . This isbecause the number of propagated value numbers in AVAILall is so small that the resulting JT  would
not have enough elements to convert value numbers backward for ANTIC all .
5.4.2

Types IV and VIII (Path-Dependent Partial Redundancy).

For the path-dependent partial redundancy, we must generate new value numbers during the conversion.
For example, in Fig. 9, when we process 2, we cannot ﬁnd “4 + const1” in the hash table. Then we
generate a new value number 8, and register it to the hash table3 . The same goes for 3, and 9 is
2 If we could not found any, then 2 would not be converted at BB3.

3 If we cannot find a conversion target (in this case, “5 + const1”), we generate another value number, and let itpropagate down.

9

BB1
BB2
JT(BB3)
1 1 a0 := read() 4 4 a1 := read() t l r
2 2 b := a0 + 1
5 1 4
3 3 c := b + 2
AVAIL 2, 3
BB3
AVAIL 8, 9

1 4
5 5 a2 := φ(a0, a1)
6 6 x := a2 + 1
7 7 y := x + 2

5 1 4
6 2 8
5 1 4
6 2 8
7 3 9

JT’(BB3) Hash Table
t

l

r

6 2 8

op l
2 + 1
3 + 2
6 + 5
7 + 6

r
const1const2const1const2

6 2 8
7 3 9

8 + 4 const1
9 + 8 const2+

BB1
1 r1 := read()a0 := r1
2 r2 := a0 + 1
b := r2
3 r3 := b + 2
c := r3

BB2
4 r4 := read()
a1 := r4
r8 := r4 + 1
r9 := r8 + 2

BB3 5 r5 := φ(a0, a1)
r6 := φ(r2, r8)
r7 := φ(r3, r9)a2 := r5
6 x := r6
7 y := r7

Figure 9: Example of value number conversion for Type IV and VIII, and the result of redundancy
eliminationsome
generated. Consequently, AVAILall= {2 , 3 , 6 , 7 }, so that we can detect the partial
in = ∅, AVAILin
redundancy of Insn. 6 (Type IV) and Insn. 7 (Type VIII).

5.4.3

Redundancy Elimination

After the computation of AVAILall , AVAILsome , ANTIC all , and AVAILMsome , we insert new instructions
into edges and remove all redundancies as in [3]. We show an example of redundancy elimination in theright-hand side of Fig. 9. We use a new variable “rn” for a value number n. For a non-redundant
instruction, the value is stored into “rn,” For a redundant instruction, the expression is replaced with“rn.” For each element in JT  , a new φ function is inserted. To make partially redundant instructions
totally redundant, new instructions are inserted at certain edges to join nodes [3]. For example, we must
insert instructions to compute 8 and 9 at the tail of BB2. Thus, consulting the hash table, “r8 := r4+ 1” and “r9 := r8 + 1” are inserted in the data dependency order, or the numerical order of the value
numbers.
After redundancy elimination, we must recover the SSA property because “rn” can be assigned atmore than one place. We use the algorithm proposed by Cytron et al. [9], and at the same time perform
copy propagation.

5.5

Value Number Conversion Algorithm

The program code to compute AVAILall and AVAILsome is shown in Fig. 10 and 11. Let lnk be l, rs.t. trgt , l , r  ∈ JT (N ), and el , er the incoming edges of N , we denote lnk (el ) = l and lnk (er ) = r .
We deﬁne AVAILsome not only for blocks but also for edges to record AVAILsomeof their source blocks
out(Fig. 11 Line 23).
JT (N ) is initialized by the φ functions in N in the original program (Fig. 10 Line 3), and JT  (N ) is
set to ∅ (Line 5). We compute maximum ﬁxed points for AVAILall and AVAILsome at Fig. 10 Line 12– 24. We ﬁrst update JT  (N ) in ConvThroughPhi (Line 16), and use it to compute new AVAILallin (N )and AVAILsome(N)
in
CompAVin
(Line
18).
in
To update JT  (and JT ), we convert the value numbers that have reached N for the ﬁrst time (Fig.
11 Line 3). The ascending order (Line 4) ensures that we process them from the upper stream of data
dependency. We search JT (N ) for the left and right operands of α at Line 5 and 6. Line 10 corresponds
to the situation where both of the operands are converted, while Line 14 and 19 to the situation where
either left or right operand is converted respectively. DoConv updates JT (N ) and JT  (N ) at Line 44
and 45. The newly-added element can be used at Line 5 and 6 of the following iterations of the same
loop (Line 4–22) to convert data-dependent value numbers.
The computation of ANTIC all and AVAILMsome is done in a similar manner except that we need
not update JT any more.

10

1 for each N ∈ BBNodes do
2 for each n ∈ N . n.Op ∈ Phi do
3
JT (N ) ∪ :={Num(n), Num (n.Lt), Num(n.Rt)}4 end
5 JT  (N ) := ∅some
6 AVAILallout (N ) := , AVAILout (N ) := ∅7 end
8 for each e ∈ Edges do
9 AVAILsome (e) := ∅10 end11
12 AVAILallout (start) := ∅, W := Succ(start )13 while W = ∅ do
14 N ∈ W, W := W \ N
15 for each M ∈ Pred (N ) do
16
call ConvThroughPhi(M, N )17 end18 call CompAVin(N )all
19 AVAILallout (N ) := AVAILin (N ) ∪ GEN (N )some(N ) ∪ GEN (N )20 AVAILout (N ) := AVAILsome
insome
21 if AVAILallout (N ) or AVAILout (N ) changed then22
W ∪ :=Succ(N )23 end24 end25
26 CompAVin(N ) {some(N ) := ∅27 AVAILallin (N ) := , AVAILin
28 for each M ∈ Pred (N ) doall
29
AVAILallin (N ) ∩ :=(AVAILout (M ) − UnTransp(M→N ))
some
(N
)
∪
:=(AVAIL30
AVAILsomeout (M ) − UnTransp(M→N ))in
31 end32 for each trgt, lnk  ∈ JT  (N ) do
33
if ∀M ∈ Pred (N ) . lnk (M→N ) ∈ AVAILallout (M ) then
34
AVAILallin (N ) ∪ :={trgt}
35
end
36
if ∃M ∈ Pred (N ) . lnk (M→N ) ∈ AVAILsome
out (M ) then(N)∪:={trgt}
37
AVAILsomein
38
end
39 end40 }Figure 10: Algorithm for AVAILall and AVAILsome (the ﬁrst half)11

1 ConvThroughPhi(M, N ) {2 e := M→Nsome (e))
3 diﬀ := (AVAILsome
out (M ) − AVAIL
4 for each α ∈ diﬀ in ascending order do
5ljs := {trgt , lnk  ∈ JT (N ) | lnk (e) = α.Lt}
6
rjs := {trgt, lnk  ∈ JT (N ) | lnk (e) = α.Rt}
7
if ljs = ∅ then8
if rjs = ∅ then9for each l, llnk  ∈ ljs, r , rlnk  ∈ rjs do
10call DoConv (N, α, l, llnk , r , rlnk )
11
end
12
else if α.Rt ∈ Transp(e) then13
for each l, llnk  ∈ ljs do
14call DoConv (N, α, l, llnk , α.Rt, nil)
15
end
16
end
17
else if rjs = ∅ ∧ α.Lt ∈ Transp(e) then18
for each r, rlnk  ∈ rjs do
19call DoConv (N, α, α.Lt, nil, r , rlnk )
20
end
21
end
22 end23 AVAILsome (e) := AVAILsome
out (M )24 }25
26 DoConv (N, α, l, llnk , r , rlnk ) {27 trgt := call Hash(α.Op, l , r )28 if ∃x . trgt , x  ∈ JT (N ) then29
return end
30 for each M ∈ Pred (N ) do
31
if llnk = nil then32
lt := l33
else
34
lt := llnk (M→N )
35
end
36
if rlnk = nil then37
rt := r38
else
39
rt := rlnk (M→N )
40
end
41
β := call Hash(α.Op, lt, rt)42lnk (M→N ) := β43 end44 JT (N ) ∪ :=trgt, lnk 
45 JT  (N ) ∪ :=trgt , lnk 
46 }Figure 11: Algorithm for AVAILall and AVAILsome (the second half)

12

5.6

Formalization of Value Number Conversion

As shown in the previous section, PVNRE joins two value numbers together which satisfy certain conditions at a join node. It then converts them into a new value number, and transfers it to the following
nodes. The joinability is deﬁned as follows.
Definition 5.7 (Jtarget and Jtarget  ). For M, N ∈ BBNodes s.t. M ∈ Pred (N ) and α0 , α1 ∈ Nums,
Jtarget(N, α0 , α1 ) = (1) ∪ (2) ∪ (3), and Jtarget  (N, α0 , α1 ) = (2) ∪ (3), where
def

def

(1) {α ∈ Nums | ∃n ∈ Nodes s.t. α = Num(n)∧ n.Op = φN ∧ Num(n).Op = φN ∧ α0 = Num(n.Lt) ∧ α1 = Num(n.Rt)}(2) {α2 ∈ Nums | α2 .Op = α0 .Op = α1 .Op ∈ Normal∧ α2 .X ∈ Jtarget(N , α0 .X , α1 .X )∧ α2 .Y = α0 .Y = α1 .Y ∧ Transp(α2 .Y , M →N )}(3) {α2 ∈ Nums | α2 .Op = α0 .Op = α1 .Op ∈ Normal∧ α2 .Lt ∈ Jtarget (N , α0 .Lt , α1 .Lt) ∧ α2 .Rt ∈ Jtarget(N , α0 .Rt, α1 .Rt)} .
Set (1) denotes that a φ function is the basis of joinability; it is Jtarget  that represents the actual
recursive joinability of value numbers. Set (2) is the case where one of the operands of α0 joins with thecorresponding operand of α1 . Set (3) describes the case where both of the operands join.
In Fig. 8, it can be proved that
Jtarget(BB3, 1 , 4 ) = {7 },Jtarget(BB3, 2 , 5 ) = Jtarget  (BB3, 2 , 5 ) = {8 },Jtarget(BB3, 3 , 6 ) = Jtarget  (BB3, 3 , 6 ) = {9 } .
In Fig. 9,
Jtarget(BB3, 1 , 4 ) = {5 },Jtarget(BB3, 2 , 8 ) = Jtarget  (BB3, 2 , 8 ) = {6 },Jtarget(BB3, 3 , 9 ) = Jtarget  (BB3, 3 , 9 ) = {7 } .
We also deﬁne Jlink (and Jlink  ) as a set of the value numbers to which a value number is converted.
Definition 5.8 (Jlink and Jlink  ). For M, N ∈ BBNodes s.t. M ∈ Pred (N )defand α ∈ Nums, Jlink (N , α, M →N ) =(1) if M is the left preceding block of N , then ∀β Jtarget (N, α, β)(2) if M is the right preceding block of N , then ∀β Jtarget(N, β, α) .
Jlink  is defined in the same way using Jtarget  .
In Fig. 8,
Jlink (BB3, 1 , BB1→BB3) = {7 }, Jlink (BB3, 4 , BB2→BB3) = {7 },Jlink (BB3, 2 , BB1→BB3) = Jlink  (BB3, 2 , BB1→BB3) = {8 },Jlink (BB3, 5 , BB2→BB3) = Jlink  (BB3, 5 , BB2→BB3) = {8 },Jlink (BB3, 3 , BB1→BB3) = Jlink  (BB3, 3 , BB1→BB3) = {9 },Jlink (BB3, 6 , BB2→BB3) = Jlink  (BB3, 6 , BB2→BB3) = {9 } .
We omit Jlink and Jlink  for Fig. 9.

5.7Soundness

In order to have PVNRE work correctly, we must assign value numbers so that Op, Lt , Rt, and Numsatisfy the soundness deﬁned later in this section. We ﬁrst deﬁne DefNodes for Normal , Phi , and Copy .
DefNodes for Fixed has already been deﬁned in Deﬁnition 5.2.
13

BB1
1
2

1
2

BB2
a0:=read()x0:=a0+1

3
4

3
4

a1:=read()x1:=a1+1

BB3
Op
Lt
Rt
DefNodes1 read() --1
2+
1 const1
2
3 read() --3
4+
2 const1
4
5 φBB3 1
35
6+
5 const1
6,7

a2:=φΒΒ3(a0, a1)x2:=φBB3(x0, x1)
7 y:=a2+1
5

5
6
6

6

Figure 12: Example of sound value numbering
Definition 5.9 (DefNodes). For α ∈ Nums,(1) if α.Op ∈ Normal
DefNormalNodes(α)
DefPhiNodes(α)

def={n ∈ Nodes | Num(n) = α ∧ n.Op = α.Op}def{n ∈ Nodes | Num(n) = α ∧ n.Op ∈ Phi∧Jtarget  (BB (n), Num(n.Lt ), Num(n.Rt)) = ∅=∧Num(n.X ).Op = α.Op}
DefNodes(α)

def=DefNormalNodes(α) ∪ DefPhiNodes (α)(2) if α.Op ∈ Phi
DefNodes(α)

def={n ∈ Nodes | Num(n) = α ∧ n.Op = α.Op
∧Num(n.X ) = α∧Jtarget  (N, Num(n.Lt ), Num(n.Rt)) = ∅}(3) if α.Op ∈ Copy
DefNodes(α)

def={n ∈ Nodes | Num(n) = α ∧ n.Op = α.Op
∧Num(n.Lt) = α} .

DefPhiNodes implies that φ functions whose operands satisfy joinability can be DefNodes for a value
number whose operator is Normal . For exmaple, in Fig. 12, the operator of Insn. 6 is φ, but the operator
of its value number 6 is + ∈ Normal because its operands 2 and 4 merge at BB3.
Using DefNodes, we deﬁne the soundness for Op, Lt, and Rt.
def

Definition 5.10 (Soundness of Op.) Op for value numbers satisfies soundness ⇔ for α ∈ Nums,∃n ∈ Nodes . Num(n) = α ⇒ DefNodes(α) = ∅ .
For example, if we deﬁne α.Op = read() ∈ Fixed for a value number α and there exists an instruction
with value number α in the program, there must be at least one instruction whose operator is read()
and whose value number is α.
def

Definition 5.11 (Soundness of Lt and Rt.) Lt for value numbers satisfies soundness ⇔ for α, β ∈Nums, α.Lt = β ∧ ∃n ∈ Nodes . Num(n) = α ⇒(1) if α.Op ∈ Normal∃n ∈ DefNormalNodes(α) . Num(n.Lt ) = β∨∃n ∈ DefPhiNodes(α) .
(Jtarget  (BB (n), Num(n.Lt ).Lt, Num(n.Rt).Lt )  β∨Num(n.Lt ).Lt = Num(n.Rt).Lt = β)14(2) if α.Op ∈ Phi , Copy∃n ∈ DefNodes(α) . Num(n.Lt ) = β .
Soundness of Rt is defined in the same manner.
Definition 5.12 (Soundness of Value Numbering). A value numbering Num satisfies soundnessdef⇔ for m, n ∈ Nodes, if m = n ∧ Num(m) = Num(n), then one of (1)–(5) holds, where(1) m.Op ∈ Copy ∧ Num(m.Lt ) = Num(n)(2) m.Op ∈ Phi ∧ Num(m.Lt ) = Num(m.Rt ) = Num(n)(3) m.Op = n.Op ∈ Normal ∪ Phi ∧ Num(m.X ) = Num(n.X )(4) m.Op ∈ Phi ∧ n.Op ∈ Normal ∧Num(n) ∈ Jtarget  (BB (m), Num(m.Lt ), Num(m.Rt ))(5) (1)–(4) with m and n interchanged .
Following are the explainations for each condition.
(1) A copy instruction is allowed to have the same value number as its operand, because it always returns
the same value as its operand.
(2) A φ function whose operands have the same value number is allowed to be assigned that value
number. This is because if two deﬁnitions of a variable are the same value, their merging also
generates that value.
(3) For Normal and Phi , two instructions are allowed to have the same value number if their operator
and operands are the same. This condition corresponds to searching the hash table in GVN.
(4) It is Condition (4) that distinguishes PVNRE from GVN, as it can detect redundancy beyond φfunctions.
Conditions (1) – (5) imply that two diﬀerent Fixed instructions with the same value number do notsatisfy the soundness. In addition, it is worth noting that the opposite direction is not required to besatisﬁed for soundness. In this case, the soundness of the algorithm is satisﬁed, but its completeness iscompromised.
Theorem 5.13 (Redundancy Theorem). If Op, Lt, Rt, and Num satisfies soundness, then forp ∈ P [start, end ] and 1 ≤ i < j ≤ λ(p),Num(pi ) = Num(pj ) ∧ Transp ∀ (Num(pi ), p[i, j ]) ⇒ Value(p, i) = Value(p, j ) .
Intuitively, if two instructions have the same value number, and the execution between them is along a
Transp ∀ path, they compute the same value. We can prove the theorem by induction on the depth ofdata dependency with Fixed as a basis as we show in the Appendix A.
Note that the algorithms shown in Fig. 6, 10, and 11 satisfy the soundness of Op, Lt , Rt, and Num.
Based on the theorem, PVNRE solves data ﬂow equations in order to ﬁnd instructions with the samevalue number between which there exists a Transp ∀ path.

5.8

Data-Flow Equation System

Equations for AVAILall and AVAILsome are as follows.

AVAILall(AVAILallin (α, n) =out (α, m) ∧ Transp(α, m→n))(1)∀m∈Pred(n)



(β,
m)
s.t.
α
∈
Jlink
(BB
(n),
β,
m→n))
∨(AVAILall
out
15

(2)

AVAILallout (α, n)(α, n)AVAILsomein= AVAILallin (α, n) ∨ (n ∈ DefNodes(α))
(AVAILsome=
out (α, m) ∧ Transp(α, m→n))

(3)
(4)

∀m∈Pred(n)∨(AVAILsome
(β,
m)
s.t.
α
∈
Jlink
(BB
(n),
β,
m→n))
out
AVAILsomeout (α, n)=

AVAILsome(α, n) ∨ (n ∈ DefNodes(α)) .
in

(5)
(6)

Predicate (1) and (4) are the cases where α propagates unchanged, while (2) and (5) cover the situations
where α is converted into β.
Equations for ANTIC all and AVAILMsome are as follows.
(ANTIC all(7)
ANTIC allout (α, m) =in (α, n) ∧ Transp(α, m→n))∨∀n∈Succ(m)(ANTIC allin (β, n) s.t. β ∈ Jlink (BB (n), α, m→n))

(8)

∀β

ANTIC allin (α, n)
AVAILMsome(α, n)
in= ANTIC allout (α, n) ∨ (n ∈ DefNodes(α))
 (AVAILMsome=(α, m) ∧ Transp(α, m→n))
out

(9)
(10)

∀m∈Pred(n)(β, m) s.t. α ∈ Jlink  (BB (n), β, m→n))∨(AVAILMsome
out
KILL(α, n)all= AVAILallin (α, n) ∨ ANTIC in (α, n)

AVAILMsome(α, n)
out(AVAILMsome(α, n) ∧ KILL(α, n))in=∨(n ∈ DefNodes(α))

(11)
(12)
(13)

Predicate (8) denotes the case where β is converted into α when the control ﬂow is traced backward.
AVAILMsome is akin to AVAILsome , but the condition KILL is added to prevent speculative insertion of
instructions.
PVNRE solves the above equations by computing maximum ﬁxed points.
Theorem 5.14 Maximum fixed point (MFP) solutions to AVAILall , AVAILsome , and AVAILMsome are
equal to their meet-over-all-paths (MOP) solutions. An MFP solution to ANTIC all does not match its
MOP solution, but is a correct one.
The proof of the theorem can be seen in the Appendix B.
The correctness of the MFP solution to ANTIC all ensures soundness of PVNRE, but the incompleteness of the solution implies that there might exist some redundancy that PVNRE cannot eliminate. In
fact, however, programs encountered in real life rarely contain such redundancies.

5.9

Formalization of Insertion Points

In order to make partially redundant instructions totally redundant, PVNRE inserts arithmetic instructions and φ functions into the original program. In this section, we use the following notations.
AVAIL = Must

def⇔

AVAILall ∧ AVAILMsome

AVAIL = May

def⇔¬AVAILall ∧ AVAILMsome

AVAIL = No

def

¬AVAILall ∧ ¬AVAILMsome .

⇔Definition 5.15 (InsertNormal ). For α ∈ Nums, m, n ∈ Nodes,
defInsertNormal (α, m→n) ⇔(AVAILin (α, n) = No ∧ (n ∈ DefNormalNodes(α)))∨(¬ ∃β . α ∈ Jlink  (BB (n), β, m→n)

(14)

∧AVAILout (α, m) = No ∧ AVAILin (α, n) = May ∧ ANTIC allin (α, n))∨(∃γ . γ ∈ Jlink (BB (n), α, m→n)

(15)

∧AVAILout (α, m) = No ∧ AVAILin (γ, n) = May ∧ ANTIC allin (γ, n)) .

(16)

16

Predicate (14) represents the points immediately before the non-redundant instructions. PVNRE(and also PRE) stores the value of a non-redundant instruction to a temporary variable, and modiﬁes
the following instructions which compute the same value, so that they refer to this variable insteadof computing the value. (15) and (16) are the conditions to insert instructions at the edges whereavailability turns from No to May. They denote the cases where a value number is converted or notconverted, respectively, at a join node.
Definition 5.16 (InsertPhi ). For α0 , α1 , α2 ∈ Nums, N ∈ BBNodes,
defInsertPhi (α2 , N , α0 , α1 ) ⇔α2 ∈ Jtarget  (N, α0 , α1 )(17)∧(AVAILin (α2 , Head (N )) = Must∨(AVAILin (α2 , Head (N )) = May ∧ ANTIC allin (α2 , Head (N ))))

(18)∧¬ ∃n ∈ Nodes . (n.Op = φN ∧ Num(n) = α2∧Num(n.Lt ) = α0 ∧ Num(n.Rt) = α1 ) .

(19)

φ functions are inserted to explicitly represent the conversion of value numbers in a program. Condition(18) is necessary because there must exist instructions referred to by the operands of φ functions. In
addition, (19) implies that it is not necessary to insert φ functions whose equivalents already exist in theoriginal program.

5.10

Instruction Insertion and Redundancy Elimination

PVNRE assigns a unique variable to each value number. These new variables must not be the same as
the variables in the original program. Var(α) denotes a variable assigned to value number α.
Let InsertionNums(m→n) be a set of value numbers of arithmetic instructions that is to be inserted at
m→n. PVNRE inserts instructions according to the ascending order of value numbers in InsertionNums.
The inserted instruction for α is Var(α) := Var (α.Lt ) α.Op Var (α.Rt). The reason for the ascendingorder insertion is that if there is true data dependency between value numbers in InsertionNums, weneed to insert the dependent one below. Here, we utilize the numerical order constraint (Deﬁnition 5.1).
As for φ functions, given InsertPhi (α2 , N , α0 , α1 ), the instruction to be inserted at the head of block
N is Var(α2 ) := φN (Var (α0 ), Var (α1 )).
Furthermore, for n ∈ Nodes s.t. n.Op ∈/ Normal ∧n ∈ DefNodes(Num(n)), x := Var (Num(n)), where
x is a destination variable of n, is inserted immediately after n. The destination of n is then altered into
Var(Num(n)).
Since the above insertion and transformation make all the arithmetic instructions in the original program totally redundant, we can replace the right-hand side of all those instructions with Var(Num(n)),
thus, eliminating all the redundancy.
A brief proof of the soundness of PVNRE and its complexity can be seen in the Appendix C.

5.11

Complexity

Let p and n be the number of φ functions and the other instructions, respectively, in the original program.
If we consider and analyze each instruction separately, one instruction generates O(x2 ) new φ functions in
the worst case, where x denotes the number of φ functions before the data ﬂow analysis of the instruction.
nThus the ﬁnal number of φ functions will be O(p2 ), which means that the maximum value number cannnbe O(n + p2 ). This results in the complexity of O(n2 + np2 ) in the data ﬂow analyses. In practice,
however, one instruction generates at most p new φ functions, so that we can expect the complexity ofO((1 + p)n2 ).

6Experimental Results

We implemented PVNRE in a Java just-in-time (JIT) compiler that we are now developing, called RJJ.
RJJ is invoked from kaﬀe-1.0.7 [10], a free implementation of a Java virtual machine. This time, we used
17

GVN

GVN+PRECP5

GVN+PRECP1

GVN+PRECP2

GVN+PRECP3
Type I ~ VIII

Eliminated redundancy

100%
80%
60%
40%
20%
0%

compressjess

raytrace

db

javac

mpegaudio

jackgeom. mean

Figure 13: Dynamic counts of eliminated redundancies (PVNRE = 100%)
GVN+PRECP5

GVN

GVN+PRECP1

GVN+PRECP2

GVN+PRECP3

Analysis time

150%

100%

50%

0%

compressjess

raytrace

db

javac

mpegaudio

jackgeom. mean

Figure 14: Analysis time (PVNRE = 100%)
RJJ only for counting the dynamic number of redundancies eliminated and measuring analysis time; wedelegated the generation of execution code to a JIT compiler in kaﬀe.
We also implemented dominator-based GVN and GVN+PRECP. We refer to algorithms that execute both PRE and CP exactly once, at most twice, and at most three times as GVN+PRECP1,
GVN+PRECP2, and GVN+PRECP3, respectively. GVN+PRECP2 and GVN+PRECP3 stop iteration when further improvement cannot be achieved.
We eliminated redundancy not only in arithmetic but also in load instructions. We assumed a newmemory model for Java (JSR-000133), so that we aggressively eliminated redundant loads. To measure
the intrinsic power of PVNRE, we did not preserve the exception order before and after optimization.
As benchmarks, we used SPECjvm98 [18]. All measurements were collected on Linux 2.4.18 with a
2.20 GHz Xeon and 512 MB main memory.

6.1

Eﬀectiveness of Redundancy Elimination

We calculated the dynamic counts of reduced instructions for all the executed methods. Figure 13
shows the results. Each bar corresponds to PVNRE, GVN, GVN+PRECP1, GVN+PRECP2, and
GVN+PRECP3 from left to right, except that we also show the result of GVN+PRECP5 for “compress.”
Further iteration of PRE and CP made no improvement. The bars are normalized to PVNRE = 100%,and the breakdown of PVNRE represents Types I – VIII from bottom to top. Note that GVN = Type I+ V, and GVN+PRECP1 = Type I + II + III + IV + V. It is also worth noting that Types I and V in
the results represent only the redundancies dominator-based GVN can detect. Thus, for example, TypeI(2) in Fig. 1 is included in Type II in the graph. We can observe that Types II and VI do not appear
in the graph except in “compress,” while Type V accounts for over 50% on an average.
The result indicates that we need to iterate PRE and CP three times (or ﬁve times for “compress”)
to completely remove redundancies of Types VI, VII, and VIII, or in other words, to match the abilityof GVN+PRECP to that of PVNRE. Those redundancy types account for 19% in dynamic counts, thus
it is not suﬃcient to perform only GVN, or GVN and PRE with no iteration.

18

6.2

Analysis Time

Figure 14 shows the total analysis time of GVN and GVN+PRECPs for all the executed methods incomparison with that of PVNRE. We did not include the time to convert the program into a non-SSA
form in GVN+PRECPs. Note that the analysis time of GVN+PRECPs does not increase proportionallyto the number of iterations because iteration is stopped when further improvement cannot be achieved.
GVN+PRECP3, which has almost the same ability to eliminate redundancy as PVNRE, is 82% slower
than PVNRE for “jess,” and 42% slower on an average. That means PVNRE achieves a 45% maximum
speedup over GVN+PRECP3, and a 30% speedup on an average.

7

Related Work

Several approaches [16, 19] that are as powerful as PVNRE have been proposed, but actual data havenever been presented concerning their analysis speed compared with traditional algorithms. In contrast, we measured the analysis time of PVNRE on real benchmarks and showed that it is faster than
GVN+PRECP. Moreover, we estimate that the existing approaches are slower than PVNRE as follows.
Rosen et al.[16] proposed an algorithm that converts the lexical appearance of instructions through φfunctions. It ﬁrst assigns an integer called rank to each instruction that represents the depth of data
dependency. It then performs copy propagation, code motion and redundancy elimination separately
for each class of instructions with the same rank. Therefore it is essentially as slow as PRECP. Steﬀen
et al.[19] proposed a two-phased algorithm that ﬁrst computes Herbrand equivalences of instructions
represented by a Value Flow Graph. It then performs PRE on that graph. In comparison, our value
numbering is much faster than its equivalence computation. In addition, our work relies solely on the
traditional SSA form and on-demand value number conversion at join nodes, while their algorithm suﬀers
from an overhead due to a necessary conversion of the whole-program graph representation.
Bodik et al.[2] proposed “Path-Sensitive Value-Flow Analysis,” which extends the optimizing powerof GVN and PRE by using symbolic back-substitution at the cost of analysis time. Actually, PVNRE
also includes part of the extended ability, but we did not encounter such a situation in SPECjvm98
where this kind of ability is of use. Rather, the emphasis of our work is on providing the power of
GVN+PRECP in a shorter analysis time.
Bodik et al.[3] also proposed the framework for PRE that we utilize in PVNRE. Its optimizing poweris the same as that of the existing frameworks for PRE, hence, is weaker than that of PVNRE. Chowet al.[6] proposed PRE on the SSA form. The goal of their work was to speed up analysis by exploiting
sparse data structures. Thus, its optimizing ability is just the same as that of the traditional PRE
algorithms.
Alpern et al.[1] proposed GVN using a partitioning algorithm, and Rüthing et al.[17] extended it todetect Herbrand equivalences. PVNRE cannot use partitioning because it has to assign value numbers
even while it is solving data-ﬂow equations. Click [7] proposed an algorithm combining GVN andaggressive code motion. It ﬁrst performs hash-table-based GVN, and then moves instructions out of loops
using dominator relationship. It can eliminate partial redundancy, but cannot detect path-dependent
redundancy. Cooper et al.[8] proposed an algorithm that ﬁrst performs GVN using a hash table and thenperforms PRE on value numbers. It is similar to PVNRE in that it propagates value numbers in dataﬂow analyses, but it does not convert them using φ functions. Thus, it cannot remove path-dependent
redundancy.

8

Conclusion

We proposed PVNRE, a redundancy elimination algorithm that manages both optimizing power andanalysis time. Using value numbers in data-ﬂow analyses, PVNRE can deal with data-dependent redundancy. It can also detect path-dependent partial redundancy by converting value numbers throughφ functions on demand. It represents data dependency by the numerical order between value numbers;
therefore it can quickly process data-dependent redundancy during data-ﬂow analyses, and avoid theoverhead due to the iteration of PRE and CP.

19

We implemented PVNRE in a Java JIT compiler and conducted experiments using SPECjvm98. The
results showed that PVNRE has the same optimizing power but has a maximum 45% faster analysis speed
than algorithms that iterate PRE and CP. These results show that PVNRE is an outstanding algorithm
for a runtime optimizing compiler, where both optimizing power and analysis time are important.
We are currently integrating PVNRE with redundant exception elimination in Java. We expect that
all redundancy eliminations that preserve exception orders can be performed in one pass.

References[1] Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables inprograms. In Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pages 1–11, San Diego, California, 1988.
[2] Rastislav Bodik and Sadun Anik. Path-sensitive value-ﬂow analysis. In Symposium on Principles
of Programming Languages, pages 237–251, 1998.
[3] Rastislav Bodik, Rajiv Gupta, and Mary Lou Soﬀa. Complete removal of redundant computations.
In SIGPLAN Conference on Programming Language Design and Implementation, pages 1–14, 1998.
[4] Preston Briggs and Keith D. Cooper. Eﬀective partial redundancy elimination. ACM SIGPLAN
Notices, 29(6):159–170, 1994.
[5] Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value numbering. Software Practice andExperience, 27(6):701–724, 1997.
[6] Fred Chow, Sun Chan, Robert Kennedy, Shin-Ming Liu, Raymond Lo, and Peng Tu. A new
algorithm for partial redundancy elimination based on ssa form. In Proceedings of the 1997 ACM
SIGPLAN conference on Programming language design and implementation, pages 273–286. ACM
Press, 1997.
[7] Cliﬀ Click. Global code motion: global value numbering. ACM SIGPLAN Notices, 30(6):246–257,
1995.
[8] Keith Cooper and Taylor Simpson. Value-driven code motion. Technical report,
CRPC-TR95637-S, Rice University, 1995.
[9] Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Eﬃciently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451–490, October 1991.
[10] Kaﬀe.org. Kaﬀe Open VM. http://www.kaﬀe.org/.
[11] Gary A. Kildall. A uniﬁed approach to global program optimization. In Proceedings of the 1stannual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 194–206. ACM Press, 1973.
[12] Jens Knoop, Oliver Rüthing, and Bernhard Steﬀen. Lazy code motion. ACM SIGPLAN Notices,27(7):224–234, 1992.
[13] Jens Knoop, Oliver Rüthing, and Bernhard Steﬀen. Optimal code motion: theory and practice.
ACM Transactions on Programming Languages and Systems (TOPLAS), 16(4):1117–1155, 1994.
[14] E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM, 22(2):96–103, 1979.
[15] Steven S. Muchnick. Advanced Compiler Design & Implementation. Morgan Kaufmann Publishers,
1997.
[16] B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming
languages, pages 12–27. ACM Press, 1988.
20

[17] Oliver Rüthing, Jens Knoop, and Bernhard Steﬀen. Detecting equalities of variables: Combining
eﬃciency with precision. In Static Analysis Symposium, pages 232–247, 1999.
[18] Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks.
http://www.spec.org/osg/jvm98/.
[19] Bernhard Steﬀen, Jens Knoop, and Oliver Rüthing. The value ﬂow graph: A program representationfor optimal program transformations. In European Symposium on Programming, pages 389–405,
1990.

Appendix
A

Theorem 5.13 (Redundancy Theorem)

Definition A.1 (DomBedges .) For u ∈ Nodes,
def

DomBedges(u) = {e = m → n | e ∈ Bedges ∧ n dom u} .
Using the reducibility of the control-ﬂow graph, we can prove the following two lemmas.
Lemma A.2 For p ∈ P [start , end] and 1 ≤ j < i ≤ λ(p),pi .Op ∈ Normal ∪ Copy ∧ pj = pi .X/ DomBedges(Node(pi .X )) .
⇒ ∀j ≤ k < i . pk→pk+1 ∈Lemma A.3 For e ∈ Edges and n ∈ Nodes,e∈/ DomBedges(n) ⇒ Transp(Num(n), e) .
The following Theorem A.4 indicates that the value numbers of the operands of an instruction istransparent along the paths between the operand instructions and the instruction.
Theorem A.4 (Transparency of Operands.)
For p ∈ P [start, end ] and 1 ≤ j < i ≤ λ(p),pi .Op ∈ Normal ∪ Copy ∧ pj = pi .X ⇒ Transp ∀ (Num(pj ), p[i, j ])Proof: This theorem follows from Lemma A.2, A.3, and Definition 5.5(2).

We cannot propagate Jtarget to the original point along the backedges of the enclosing loops asfollows.
Lemma A.5 For α0 , α1 , α2 ∈ Nums, N ∈ BBNodes, p ∈ P [start , end], and 1 ≤ i < j ≤ λ(p),α2 ∈ Jtarget (N, α0 , α1 ) ∧ Node(pi ) = Node(pj ) = Head (N )⇒ ¬Transp ∀ (α2 , p[i, j ])From Theorem A.4 and Lemma A.5, we can prove Theorem 5.13.
Proof: Our proof will proceed by induction on the depth of data dependency with Fixed as a basis.
From the fact that Num(pi ) = Num(pj ), we can rely on the soundness of value numbering (Definition
5.12). Induction hypothesis is satisfied by Theorem A.4. For the case of Definition 5.12(4), we appeal toLemma A.5.



21

B

Theorem 5.14 (MFP and MOP solution)

The MFP solution to a problem matches its MOP solution if all of its ﬂow functions are monotone anddistributive [11]. Transp, (n ∈ DefNodes(α)), and KILL, which appear in the data-ﬂow equations for
AVAILall , AVAILsome , ANTIC all , and AVAILMsome , are monotone and distributive. Jlink  is monotone,
but is not distributive for ∧. The ﬂow function of Jlink  can be generalized into the form of f (xα ) =xα ∨ xβ , where 1 ≤ α, β ≤ max (Nums).
Lemma B.1 Jlink  is monotone.
Proof: xα  ≤ yα  ⇒ xα ≤ yα ⇒ xα ∨ xβ ≤ yα ∨ yβ ⇒ xα ∨ xβ  ≤ yα ∨ yβ  ⇒ f (xα ) ≤ f (yα )Lemma B.2 Jlink  is distributive for ∨, but not for ∧.
Proof: For ∧, f (xα  ∧ yα ) = (xα ∧ yα ) ∨ (xβ ∧ yβ ) = (xα ∨ xβ ) ∧ (yα ∨ yβ ) = f (xα ) ∧ f (yα ).
We can prove the distributivity for ∨ in the same manner.

We can prove Theorem 5.14 as follows.
Proof: From Lemma B.1 and B.2, it is clear that MFP solutions to AVAILsome and AVAILMsome are
equal to their MOP solutions. The proof by Kildall [11] implies that an MFP solution to ANTIC all is acorrect solution, but does not match its MOP solution.
Jlink  for AVAILall is distributive because Lemma A.5 means that∀α∃β . α ∈ Jlink  (BB (n), β, m→n) ⇒ ¬AVAILallout (α, m),and the flow function is essentially f (xα ) = xβ . Consequently, an MFP solution to AVAILall matches
its MOP solution.
CSoundness of PVNRE

Theorem C.1 (Soundness of PVNRE). The value of any instruction on any execution path after
optimization by PVNRE is the same as that of the corresponding instruction (if any) before the optimization.
Proof: We can prove the syntactic soundness; for example, the operands of a newly-inserted Normal
instruction whose value number is α refer to instructions whose value numbers are α.X. Thus the value
numbers of the newly-inserted instructions satisfy Definition 5.12. It follows that Theorem 5.13 holds true
even after the optimization. From Theorem 5.14, Definition 5.15, and 5.16, all the Normal instructions
become totally redundant in terms of Theorem 5.13. Therefore we can replace the right-hand side of all
those instructions n with Var (Num(n)).
22