Global Load Instruction Aggregation Based on Dimensions of Arrays
Yasunobu Sumikawaa,∗, Munehiro Takimotoa ,a2641, Yamazaki, Noda, Chiba, Japan, 278-8510, Tokyo University of Science

Abstract
Most modern processors have some cache memories that are much faster than main memory. These
cache memories function well if temporal or spatial localities in programs are enhanced; therefore, thecontinuous accesses to the same array that improves the localities can enhance eﬀective utilization of
the cache memories. In addition, because a multidimensional array can be regarded as an array oflower dimensional arrays, the continuous accesses to array references with the most similar indexes canenhance the utilization of them further. We propose a new code motion algorithm called MDGLIA
that improves utilization of cache memory. MDGLIA moves each array reference immediately after
the preceding references accessing the same array with the most similar indexes, and then delays it aslate as possible without changing the access order. These two-step code motions contribute to not only
improvement of the cache eﬃciency in the overall program but also suppression of register pressure.
We implemented MDGLIA in a real compiler and evaluated it for matrix multiplication and SPECbenchmarks. The experimental results show that our algorithm reduces the number of cache misses inmost cases.
Keywords: partial redundancy elimination, cache optimization, register pressure, and data-flow
analysis
1. Introduction
Most modern processors have some cache memories that are much faster than main memory.
Whenever a processor needs the data at address
x in main memory, the cache memory is checked
first to ascertain whether a copy of the data isstored in cache memory. At this time, it is calledcache hit if the data at x is found in the cachememory; otherwise, it is called cache miss. In
the case of a cache hit, because the data is obtained without any memory access, the programis executed without stalling. Conversely, when acache miss occurs, the processor fetches the data∗

Corresponding author
Email addresses: yas@cs.is.noda.tus.ac.jp(Yasunobu Sumikawa), mune@cs.is.noda.tus.ac.jp(Munehiro Takimoto)
URL: http://www.cs.is.noda.tus.ac.jp/~yas(Yasunobu Sumikawa)
Preprint submitted to Computers and Electrical Engineering

around x in the main memory, and then places it
into cache memory for subsequent cache hits. In
this case, the reference to x not only causes significant delay because of the fetching and placingof the data around x into cache memory but also
removes the old data in the same cache line. Thismeans that continuous access to addresses thatare at a distance from each other in main memory may result in cache misses, which can reduce
the execution eﬃciency of the program.
Let us look at how accessed data is copied into
cache memory. Consider the C program outlinedin Figure 1. In this paper, for ease of explanation, we assume that the cache memory is directly mapped without loss of generality. That is,when the data is transferred from main memory
to cache memory, the candidate location in which
it is placed is determined by the memory address
modulo and the number of lines in the cache memAugust 12, 2015

main(){
x=a[i]
y=b[i]
z=a[i+1]}
A C program・・・
b[i] 0011
b[i+1] 0100
・・・
a[i] 1011

00
01
10
11 a[i] a[i+1]Cache memory

main(){
x=a[i][j]y=a[k][l]z=a[i][j+1]}a[i+1] 1100
・・・
Main memory

A C program

00
01
10
11 a[i][j] a[i][j+1]Cache memory・・・
a[i][j] 0011
a[i][j+1] 0100
・・・
a[k][l] 1011
a[k][l+1] 1100
・・・
Main memory

Figure 2: Example of the kind of cache miss on which ouralgorithm is focused.

Figure 1: Example of the kind of cache miss on which ouralgorithm is focused.

to be expunged, resulting in a cache miss fora[i][j+1]. However, this cache miss can be prevented by moving the array reference immediately
before a[k][l].
We present a new cache optimization algorithm that continuously aggregates array references with the same indexes to higher dimensions. The proposed algorithm, called the multidimensional global load instruction aggregation(MDGLIA), is based on partial redundancy elimination (PRE) [3, 15, 18] that makes partiallyredundant expressions fully redundant by inserting some expressions, and then removing the redundant expressions. MDGLIA extends PRE
to aggregate array references, without sacrificing
the eﬀects of gained by removing redundant expressions. MDGLIA determines the number ofindexes of each array reference ar preceding a
moved candidate that are the same array as ar,and then moves ar to the program points closest
to the references with the same indexes most in
higher dimensions.
Consider the array references in Figure 3(a).
MDGLIA is applied to each array reference
traversing the control flow graph (CFG) in the
topological sort order. First, MDGLIA moves array reference a[k][l] immediately before arrayreference b[i] because the execution of b[i] between a[i][j] and a[k][l] may cause a[k][l]to be removed from the cache memory if the data
placed in the cache memory for b[i] share somecache lines for a[k][l]. Here, MDGLIA makes a
new Node 6’ for the moved array reference. Next,

ory. Following execution of array reference a[i],the data at a[i] and a[i+1] will be copied on
the cache line with index 11. Subsequently, because execution of array reference b[i] results ina cache miss, the data at b[i] and b[i+1] will
also be copied into cache memory. In this case,the data is copied on index 11 because the address
at b[i] is 0011; therefore, the data at a[i] anda[i+1] will be removed from the cache memory,which may result in a cache miss for subsequent
access to a[i+1].
As shown in the example, once the data at a
specific array index is loaded from main memory,
it is placed in the cache memory along with otherdata belonging to the same array. That is, continuously accessing the same array can get cachehits. Continuous access to the same array canbe promoted by moving references to an arrayaround other references to the same array. In Figure 1, moving a[i+1] immediately before b[i]can prevent a cache miss because a[i+1] could
then be executed immediately after a[i].
Furthermore, considering that a multidimensional array represents an array of lower dimensional arrays, preferentially aggregating referenceswith the same indexes more in higher dimensions
may further reduce cache misses. Consider thearray reference a[i][j+1] in Figure 2. The referenced data is copied to cache memory following
the execution of array reference a[i][j]. However, as was the case with the program in Figure 1, execution of a[k][l] may cause the data2

CPUs used in embedded systems in order to examine how our code motion reduces cache misses
in a real program. The results indicate that ouralgorithm is eﬀective in various types of computers.
The advantages of our algorithm are summarized as follows:

1
3
4 x=a[i][j]1

7’ t’=a[i][j+1]3
4 x=a[i][j]26’ t=a[k][l]2

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

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

7 w=t’

8• MDGLIA moves array references in order toremove redundancy and reduce the numberof cache misses while considering array dimensions.

8(a)• MDGLIA suppresses spills without reducing
the eﬀect of aggregation to prevent cache
misses.

(b)

Figure 3: Eﬀectiveness of MDGLIA: (a) Original code. (b)Result of applying MDGLIA.

• We implemented MDGLIA in a compiler andconducted experiments for two benchmarks
on two CPUs.

consider a[i][j+1] at Node 7. Although subarray a[i] is accessed at Nodes 4 and 7, anotherarray, b, and sub-array a[k] are accessed between
them. Because the data at a[i][j+1] may be removed from the cache memory after they havebeen executed, MDGLIA moves a[i][j+1] immediately ahead of a[k][l], as shown in Figure3(b).
Our goal in this paper is to provide algorithms
for aggregating array references and analyze eﬀective of our algorithm in detail. In our previous paper [24], we showed that our algorithm is eﬀective
for SPEC CPU 2000 benchmark on an Intel Corei5 processor, which is the processor used by popular desktop computers. In this paper, we demonstrate the eﬀects of our algorithm on other gradeCPUs, specifically, Xeon and Core2duo, whichhave larger and smaller cache memories, respectively, than Core i5. We implemented MDGLIA
and applied it to two kinds of benchmarks: matrix multiplication and SPEC CPU 2000. For thematrix multiplication, we conducted experiments
on an Intel Xeon processor possessing large cachememories in order to determine how our aggregation approach reduces cache misses. Conversely,
for the SPEC CPU 2000 benchmarks, we conducted experiments on an Intel Core2Duo processor possessing small cache memories similar to the

The rest of this paper is organized as follows:
Section 2 summarizes related works in this area.
Section 3 presents preliminary definitions needed
to explain our algorithm, and outlines laze code
motion (LCM)–a variant of PRE [15]. Section 4outlines our proposed MDGLIA algorithm that is
extended from LCM. Section 5 presents and analyzes experimental results that demonstrate theeﬀectiveness of MDGLIA. Section 6 concludes thispaper.
2. Related Work2.1. Cache Optimization
Data in memory that has been used once tends
to get used again in the near future, and the surrounding data also tends to be used in much of the
program. These two phenomena are called temporal locality and spatial locality, respectively, andare used to improve the execution eﬃciency of
programs via cache memories. Popular techniques
for enhancing the localities are due to transforming loop structures [1, 2]. Although these techniques often significantly improve the execution
eﬃciency of a program, their application tend tobe limited to specific control structures such as
simple loops. However, our algorithm is based on3

global code motion that does not change the control structure of a program, and therefore can beapplied to any program. Furthermore, our algorithm and the abovementioned loop transformation based techniques can both be applied to a
program at the same time to cooperatively improve the program.
Techniques that use prefetchers are also frequently used to improve the utilization of cachememories. The basic idea underlying these techniques is prefetching of data by transferring thatdata into a cache memory before it is used byprograms. There are two prefetch levels: software and hardware. Software prefetch can beachieved by explicitly inserting fetch instructions;
it is particularly eﬀective for loops with array accesses. Hardware prefetch implicitly achieves effective prefetch by exploiting spatial locality. According to Smith [22], there are three variants of
one block lookahead (OBL): The first prefetchesline l + 1 whenever line l is being accessed (always prefetch). The second prefetches line l + 1
whenever access to line l results in a cache miss(prefetch on miss). The third prefetches line l + 1
only for the first access to line l (tagged prefetch).
Hardware prefetch does not need a change in the
input program, but is eﬀective only for good spatial locality. Non-sequential memory access significantly decreases execution performance. Ouralgorithm not only removes redundant array references, but also improves spatial locality by moving array references. In other words, removing
redundancies and making array references continuous, reduces the number of memory accesses andimproves spatial locality. Consequently, our algorithm can enhance the eﬀect of prefetch, especially hardware prefetch.
Some algorithms improve cache eﬃciency basedon data-layout. Cache-conscious data placement(CCDP) reduces cache conflict misses by considering data-layout [4]. CCDP uses a temporal relationship graph (TRG), in which nodes represent
objects (e.g., functions, arrays, and global variables) to be placed in the data cache. The edges
between the objects represent the estimated number of cache misses that would occur if the two
objects were mapped to the same cache set. A

compiler assigns addresses to the objects basedon a conflict cost metric calculated for the TRG
in order to minimize cache conflict misses.
Although CCDP can reduce cache conflict
misses for a processor core with a single execution context, it loses much of its benefit in a multithreaded environment because inter-thread conflicts are not deterministic. Sarkar and Tullsen
proposed an algorithm that extends CCDP to
multithreaded architectures [21]. In their algorithm, the extra cost incurred from the sharing ofobjects by threads in cache blocks is added to each
TRG edge as weight. Like CCDP, the compiler
assigns addresses to the objects using a TRG inorder to minimize the cost of cache conflict misses.
Ishitobi et al. proposed an algorithm based on object layout that reduces the energy consumptionof on-chip memory by considering memory allocation on a processor that has cache memory andscratchpad memory [13]. Their algorithm partitions the memory into cacheable region, scratchpad region, and non-cacheable regions in order tominimize the total energy consumption and thenumber of cache misses. SwiftArray uses Hilbert
space-filling curve instead of row-major order as
the data-layout to improve the spatial locality ofmultidimensional arrays [9].
The above approaches focus on data allocationlayout in memory but not the reordering of theexecution code. The allocation layout information can be used synergistically to improve ouralgorithm by specifying eﬀective target array references. That is, Ishitobi et al.’s algorithm canbe combined with our algorithm by first applying their algorithm, and then using our algorithm
to move array references whose reference data isallocated in a cacheable region. This combination improves utilization of cache memory while
reducing the energy consumed. If our algorithm isutilized on a computer that uses SwiftArray, ouralgorithm may not be eﬀective because our algorithm assumes that array data is allocated in rowmajor order as mentioned in Section 3.1. Thus, inorder to integrate our algorithm with their datalayout, our aggregation targets should be modified to consider the layout of the data.
42.2. Removing Redundant Expressions
The original PRE algorithm that uses bidirectional data-flow analysis was proposed byMorel and Renvoise [18]. This algorithm can eliminate some redundancies and move loop-invariant
expressions out of loops, but some redundant expressions are not removed because the algorithm
does not insert expressions at nodes where downsafe are not satisfied. Dhamdhere extended thisalgorithm to insert expressions on edges [7], and
Dhamdhere and Patil also proposed another algorithm that removes redundancies based on unidirectional data-flow analysis [8]. Bodik et al.
proposed the removal of all redundant expressions by copying certain parts of the program [3].
Kawahito et al. proposed an algorithm that removes partially redundant load and store instructions based on extended PRE [14]. These algorithms remove redundant expressions, but they
are not capable of reducing the number of cache
misses.
Speculative code motion, another algorithm
based on code motion, moves load instructions outof loops, but the movement may introduce somenew computations [16]. This algorithm has to recognize loop structures whereas our algorithm canbe applied to an entire program without recognizing them, because our algorithm is based onPRE.

which we call a load statement. The right-handside of an assignment statement is called an expression. Further, a statement that stores thedata in a virtual register x to a memory locationa[i][j] is expressed as a[i][j] = x, which we call astore statement.
We assume that the memory access appears
solely in the assignment. That is, a procedure
call f (a[i][j]) is split into two statements; e.g., t =a[i][j] and f (t). Similarly, a store statement witha nested array reference a[i][j] = a[b[i]][k] is split
into three statements; e.g., t = b[i], t0 = a[t][k]and a[i][j] = t0 . Moreover, the load statement includes a temporary virtual register instead of an
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, whichmeans that the leftmost index corresponds to thehighest dimension of the array.
We assume that a CFG (control flow graph) has
been built for each program. A CFG is a graphstructure represented by a quadruple (N,E,s,e),
where N is a set of nodes with a single statement,
E (denoted by N × N) is a set of edges, s is a startnode with an empty statement, and e is an end
node with an empty statement. A given edge isexpressed as (m, n) ∈ E, where m is called a predecessor of n, and n is called a successor of m. In
general, there are several predecessors and successors for a node, because of the nondeterministic
branching structure of a CFG. Hence, the sets ofpredecessors and successors of node n are denotedby node sets pred (n) and succ(n), respectively.

3. BackgroundIn this section, we give the definitions of the
program representations assumed by our algorithm, and outline LCM (lazy code motion).
3.1. Preliminaries
We assume that MDGLIA is applied to the intermediate representation converted from a source
program, which is represented as a sequence ofstatements with at most one operator or function.
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 andindexes 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],A CFG assumes that any critical edge that leads
from a node with more than one successor to anode with more than one predecessor has been
removed and replaced with a synthesized node,
because critical edges can block eﬀective code motion. In fact, this assumption has been adopted
for the same reason in many traditional algorithms based on code motion [15].
53.2. Lazy Code Motion

the insertion node, as shown in Figure 4(b). Finally, LCM inserts the array references at Nodes
2 and 3, and then replaces the original a[i] witht, as shown in Figure 4(c).
These code motions have to satisfy two kinds ofsafeties: down-safety and up-safety. Down-safety
is used to ensure that LCM does not lengthen any
execution paths. It is represented by the predicate
DownSafe(n) that denotes that there are occurrences of the expression on all sub-paths following
the node n. Up-safety is used to ensure that there
are some paths where the number of expressions is
reduced by the insertions and removals. Up-safety
is represented by the predicate UpSafe(n) that denotes that there are some occurrences of the expression on all sub-paths leading to the node n.
These safeties are defined under the condition oftransparency that ensures that the value of an expression does not change at the program pointsof concern. LCM represents this condition using
the predicate Transp. Because up-safety is one of
the most important predicates in our algorithm,
we present its formal definition below.

PRE removes redundant expressions by inserting some expressions; however, the process of insertion and removal tends to lengthen the liveranges of variables carrying loaded values to theirutilization, leading to spills in the register allocation phase [6, 20]. To address this problem, LCM
consists of the first code motion hoisting expressions as early as possible and the second code motion delaying them as late as possible. The firstcode motion eliminates all removable expressions,and the second one minimizes the live-ranges ofvariables.
t=a[i]
1

Hoisting

2 x=a[i]34 y=a[i]

(a)

1

def

UpSafe(n) ⇔ (n ̸= s) ∧∏Comp(m) ∨Delaying

1

t=a[i]

t=a[i]

2 x=a[i]34 y=a[i](b)2’ t=a[i]3 t=a[i]m∈pred(n)2 x=t(Transp(m) ∧ UpSafe(m))(1)4 y=t

where the predicate Comp(n) denotes that noden includes the same expression.
For example, as shown in Figure 4(a), the
DownSafe of Nodes 1, 2, and 3 is true because
there is no modification for i nor a[i] in Nodes2, 3, and 4. In contrast, the UpSafe of all nodes
is false. Because no occurrence of the array reference on a path from Node 1 to Node 3, UpSafe(4)is false. The UpSafe of the other nodes is also
obviously false.
LCM determines two kinds of insertion nodes
based on the predicates Earliest and Latest,
which determine the insertion points in thetwo code motions mentioned above, respectively.
Earliest(n) denotes that node n is the closest
to s of the nodes m satisfying DownSafe(m).
Latest(n) denotes that node n, all paths to which
include some nodes satisfying Earliest, is the node(c)Figure 4: Code motions of LCM: (a) Hoisting expressions.
(b) Delaying expressions. (c) Result of translation of LCM.

For example, consider an array reference a[i]at Node 4 in Figure 4(a). This array reference ispartially redundant because it is redundant on apath through Node 2, whereas it is not on another
path through Node 3. To remove this redundancy,
LCM first determines the CFG nodes at which array references can be inserted. If an array reference is inserted at Node 1, the redundant arrayreference can be removed by replacing it with thetemporary t introduced. Note here that, the liverange of t is lengthened; therefore, LCM delays
6

closest to node c satisfying Comp(c), and any
node on the path from n to c does not satisfy
Comp. Latest(n) is defined on the basis of maximal fixed points of the data-flow equation for thepredicate Delayed (n) that denotes that the expression can be delayed until the exit of node n.
Consider a[i] in Figure 4 (a). At the beginning, LCM decides that Earliest(1) is true because DownSafe(1) is true, and this node is theclosest to the start node. LCM subsequently delays the insertion points through the decisionsof Delayed and Latest, which result in true forComp(2), false for Delayed (4), and true for Latest
at Nodes 2 and 3.
Here, because Delayed is also one of themost important predicates for our algorithm, we
present the formal definition as follows:

4.1. Local PropertiesMDGLIA defines the local properties
SameAddr , Transp e , Transp Addr , and isSame
to check addresses.
SameAddr and isSame
represent equalities of start addresses and entire
expressions, respectively. SameAddr (n) denotesthat n contains a load statement referring to
the same array reference as ar. isSame(n),corresponding to Comp of LCM, denotes that
SameAddr (n) is true and the indexes are thesame as ar. Transp e (n), which is defined astransparency, denotes that there is no modification to ar and no store statement to the arrayreferred to by ar in n. Transp Addr denotes that
there is neither modification to ar nor reference
to arrays diﬀerent from ar.
To determine these predicates, we use predicates rhs, Load , TopAddr , Store, Def , and Var .
rhs(n) returns the right-hand side of a statement
at node n. Load (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 that accesses the same array as
ar. Def (n) gives a variable defined at node n.
Var (ar) gives the set of variables used in ar. The
local properties are defined as follows:def

Delayed (n) ⇔ Earliest(n) ∨ (n ̸= s) ∧∏¬Comp(m) ∧ Delayed (m)m∈pred(n)LCM inserts expressions at the entry of nodes
n satisfying the predicate Insert(n) that denotesthat n is one of the nodes satisfying Latest.
Note that LCM does not insert any expression without reducing the number of expressions
on some paths, because such insertions are unnecessary. Therefore, Insert(n) is defined as
Latest(n) ∧ ¬Isolated (n) on the basis of the predicate Isolated (n) that denotes that the insertion
at n enables the removal of no expression otherthan the original one. After the insertion at
the entry points of nodes n satisfying Insert(n),each of the same expression at node n satisfying¬(Latest(n) ∧ Isolated (n)) is replaced by the temporary variable holding the value of the expression.

def

SameAddr (n) ⇔ Load (n) ∧(TopAddr (rhs(n)) = TopAddr (ar))
defTransp e (n) ⇔ Def (n) ̸∈ Var (ar) ∧ ¬Store(n)defTransp Addr (n) ⇔ Transp e (n) ∧(¬Load (n) ∨ SameAddr (n))
defisSame(n) ⇔ rhs(n) ̸= ⊥ ∧ rhs(n) = ar
4.2. Modified Global Properties

4. Aggregating Array References

MDGLIA modifies UpSafe and Delayed in
LCM.

Similar to LCM, MDGLIA checks DownSafe,
UpSafe, Earliest, Delayed , and Latest to determine the nodes to move an array reference ar.
In the delaying, MDGLIA checks start addresses
and the number of corresponding indexes of arrayreferences for aggregation while keeping the orderof accesses to arrays.

4.2.1. Extending UpSafe
UpSafe(n) is modified to denote that there aresome array references whose start addresses are
the same as ar on all sub-paths leading to noden. This predicate is formally defined as follows:7

def

UpSafe(n) ⇔ (n ̸= s) ∧∏SameAddr (m) ∨the exceptions [10, 17], but for architectures that
do not support it, speculative code motion should
be forbidden using equation (1).

m∈pred(n)(Transp e (m) ∧ UpSafe(m))(2)4.2.2. Extending Delayed
Delayed is modified to check whether the keeporder condition and keep-dimension condition aresatisfied. We describe the details of these conditions in this section.

By this modification, it is able to analyze theaccess order of arrays. However, it speculatively
moves array references although LCM does not
perform speculative movement.
Consider application of our algorithm toa[i][j+1] in Figure 5(a). Because an array reference a[i][j] is executed at Node 1, UpSafe(2)is true, and therefore, Earliest(2) is true. Consequently, it leads Delayed (2) is also true, but
Delayed (3) becomes false because TranspAddr (2)is false. As a result, Latest(2) becomes true, andtherefore, a[i][j+1] is moved immediately before Node 2 as shown in Figure 5(b). Note herethat a[i][j+1] does not originally exist on thepath through Node 3 in Figure 5(a). That is, thisinsertion is speculative. Speculative code motion
may increase the number of expressions on somepaths; however, if the speculatively inserted array references cause cache misses, the execution
eﬃciency would be significantly decreased.

Keep-order Condition
The keep-order condition guarantees that there
is no reference to the array diﬀerent from ar at
n after the preceding reference to the same arrayas ar. The keep-order condition is represented by
keepOrder , and is defined as follows:∑def
UpSafe(m)partialUpSafe(n) ⇔m∈pred(n)defkeepOrder (n) ⇔ ¬partialUpSafe(n) ∨Transp Addr (n)Figure 6(a) demonstrates the eﬀect of aggregation considering the keep-order condition. Consider moving a[k][l] at Node 6. Nodes 4 and
6 contain array references that reference array a,
but there is an array reference that references array b between them. To move a[k][l] immediately ahead of Node 5, MDGLIA determines
Earliest by first checking UpSafe and DownSafe.
Because there is no a[k][l] on the path throughNode 2, DownSafe(1) and UpSafe(1) are false.
These results cause Earliest(1) to be false. On theother hand, another path through Node 3 has thesame reference at Node 6. Hence, DownSafe(3)and Earliest(3) are true, which causes Delayed (3)to be true. At each node from Node 3, MDGLIA
checks whether the keep-order condition is satisfied. Node 4 has an array reference that references the same array as a[k][l], but Node 5
has another array reference that references a different array. Hence, SameAddr (4) is true, andthen UpSafe(5) is true, but SameAddr (5) is false.
These cause keepOrder (5) and Delayed (6) to befalse. Eventually, Latest(5) and Insert(5) aretrue; therefore, MDGLIA inserts an array reference immediately before Node 5 and removes theoriginal expression, as shown in Figure 6(b).

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

3
5

4 z=t

3
5

(a)

(b)

Figure 5: Speculative code motion: (a) Original code. (b)Moving array reference, not satisfying down-safety.

In general, speculatively moving load statements is unsafe; it may cause out-of-bounds exceptions. If the objective codes are executedon processors supporting the exception handler,
there is no problem. In fact, most modern architectures can resolve the problem by suppressing
8

1
DownSafe(1), UpSafe(1): false

1
3
4 x=a[i][j]5 y=b[i]2

3DownSafe(3): true
Earliest(3): true
Delayed(3): true

6 z=a[k][l]UpSafe(5): true
SameAddr(5): false
keepOrder(5): false

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

Delayed(6): false

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

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

8

8

(a)

(b)

Figure 6: Eﬀectiveness of extending UpSafe: (a) Result of computing data-flow equations to move a[k][l] at Node 6.
(b) Result of moving the array reference.

Keep-dimension Condition
The keep-dimension condition contributes tothe aggregation of references to closer addresses
in the same array by keeping the number of corresponding indexes from decreasing. This condition uses two kinds of predicates to preserve thenumber: nCI (number of corresponding indexes)
and pnCI (propagated nCI ).
To represent closeness on the main memory between references to an array, we define nCI as thenumber of higher indexes corresponding with ar.
nCI (n) checks whether each index of the arrayreference at n is same as corresponding index ofar, in succession from the left, whenever n contains a reference to the same array as ar. Thispredicate is formally defined as follows:

The pnCI of n denotes the number of indexes
to the reference that has the most indexes that are
the same as ar on all execution paths to the exitof n from the preceding node where SameAddr istrue. We represent the pnCI of n as pnCI (n),which can be defined by the data-flow equation
based on nCI as follows:0
if n = snCI (n)if SameAddr (n)defpnCI (n) ⇔Max({pnCI(m)|m ∈ pred (n)}) otherwise
The equation can be solved iteratively as wellas using typical data-flow analysis. If node n includes a reference to the same start address asar, then pnCI (n) is nCI (n). Otherwise, pnCI (n)is the maximal value of the pnCI of pred (n), excluding the start node. Thus, pnCI represents theadvantage of moving ar to n for cache-hits.
The keep-dimension condition is represented by
the predicate keepDimension, and is defined using
partialUpSafe and pnCI as follows:

Definition 1 (nCI ). Assume that ar isa[i1 ][i2 ]...[ik ]...[in ], and r is b[j1 ][j2 ]...[jk ]...[jm ].
Then,
if a = b ∧ il = jl ∧

 k


(k = n ∨ k = m∨defik+1 ̸= jk+1 )nCI (r) ⇔


where
∀l
∈ {1, ..., k}0otherwise

def

keepDimension(n) ⇔ ¬partialUpSafe(n) ∨∏pnCI (n) ≥ pnCI (m)m∈pred(n)The condition means that if their start addresses are the same, these indexes are checked
to determine whether the kth index is the same
until the last index.

This predicate denotes that n does not include
any reference with nCI that is less than the preceding references.
9Delaying Under Keep-order and Keep-dimension
Conditions
MDGLIA checks whether the keep-order andkeep-dimension conditions are satisfied in addition to Delayed of LCM. Once these conditions
are introduced, Delayed is simply changed as follows:

Finally, to aid understanding of the overall
algorithm, we present formal definitions of all
global predicates, apart from UpSafe, keepOrder ,keepDimension, and Delayed , in Figure 8.

4.3. Application to the Overall Program

def

Delayed (n) ⇔ Earliest(n) ∨ (n ̸= s) ∧∏¬isSame(m) ∧ keepOrder (m) ∧MDGLIA traverses CFG in topological sort order. When an array reference is found during thetraversal, MDGLIA determines local/global properties for it. This analysis style is called demanddriven analysis. Traditional PREs are designed
as an exhaustive analysis that determines the redundancy of all expressions using bit vectors andchecking lexical equality. In general, applicationof PRE based approaches exposes new redundant expressions. This eﬀect is called the second order-eﬀect. Reflecting as many of them as
possible results in the removal of more redundant
expressions. However the reflection of all second order-eﬀects requires iterative applications of
PRE that are costly because PRE is traditionallydesigned based on exhaustive data-flow analysis[19]. On the other hand, demand-driven application of MDGLIA to the entire program in topological sort order facilitates eﬃcient capture of thesecond order-eﬀects [23]. Further, the manner inwhich MDGLIA is applied eliminates unnecessarycode motion because array references are moved
one by one.
In Figure 9(a), Nodes 2 and 3 might expel datathat may be used later from cache memory. If
MDGLIA exhaustively moved all array referencesat the same time, both references a[i][j+1] anda[k][l+1] would be moved, as shown in Figure9(b). Although the code motion can address theabove problem, it enhances the register pressureof the temporary variable to hold the value ofa[k][l+1] because of the unnecessary code motion of a[k][l+1]. In contrast, MDGLIA traverses Nodes 1, 2, 3, and 4 in this order. Considering the case where Node 3 is visited, a[i][j+1]is moved to the entry of Node 2 based on the
demand-driven application manner as shown in
Figure 9(c).

m∈pred(n)keepDimension(m) ∧ Delayed (m)1Delayed(3): true3
4 x=a[i][j]6’ t=a[k][l]2
5 y=b[i]nCI(4): 1
pnCI(4): 1
nCI(6’): 0
pnCI(6’): 0
keepDimension(6’): false
Delayed(5): false

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

Figure 7: Computing the closeness of each address of
a[i][j+1] at Node 4 and Delayed .

Figure 7 shows the results of data-flow analysis
of MDGLIA when it is applied to a[i][j+1] at
Node 7 in Figure 6 (b). Nodes 4 and 7 contain array references that reference sub-array a[i], butthere is an array reference that references subarray a[k] between them. To move a[i][j+1]
immediately before Node 6’, MDGLIA determines
Earliest first. Because Earliest(3) is true as wellas the case of moving a[k][l] in Figure 6(a),Delayed (3) is also true. At each node from Node3, MDGLIA checks whether the keep-dimension
condition is satisfied. Although nCI and pnCIof Node 4 are one, nCI and pnCI of the successor Node 6’ are zero; therefore, keepDimension(6’)
and Delayed (5) are false. Eventually, Latest(6’)
and Insert(6’) are true, which results in MDGLIA
inserting an array reference immediately before
Node 6’ and removing the original expression, as
shown in Figure 3 (b).
10

∏

def

DownSafe(n) ⇔ (n ̸= e) ∧ (isSame(n) ∨ Transp e (n) ∧DownSafe(m))

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

m∈pred(n)∏defLatest(n) ⇔ Delayed (n) ∧ (isSame(n) ∨ ¬def

Isolated (n) ⇔∏Delayed (m))

m∈succ(n)(Latest(m) ∨ ¬isSame(m) ∧ Isolated (m))

m∈succ(n)defInsert(n) ⇔ Latest(n) ∧ ¬Isolated (n)defReplace(n) ⇔ isSame(n) ∧ ¬(Latest(n) ∧ Isolated (n))
Figure 8: Data-flow equations used in MDGLIA.

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

3 z=t

3 z=t

4 w=a[k][l+1]

4 w=t’

4 w=a[k][l+1]

(a)

(b)

(c)

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

aggregation on an Intel Xeon computer that haslarge cache memories. In the latter experiment,
we examined how well our speculative code motion reduces the number of cache misses on anIntel Core2Duo computer with a small amount ofcache memory, similar to the processors used inembedded systems.

5. Experimental Results
We implemented MDGLIA as a low-level intermediate representation converter in a COINS
compiler1 , which is a compiler infrastructure supported by the open-source community.
We conducted a matrix multiplication experiment (Section 5.1) and a SPEC CPU 2000 benchmark experiment (Section 5.2). In the former
experiment, we investigated the operation of our1

5.1. Eﬀectiveness of Aggregation
We used the matrix multiplication program
shown in Figure 10 in this experiment. We assumed that a scalar replacement was applied tohttp://coins-compiler.sourceforge.jp/

11Matrix Multiplying with Scalar Replacement
double A, double B, double C,
COL = ROW = 500
1: for (i = 0; i < COL; i++)2: for (j = 0; j < ROW ; j++)3:
tmp = 0.0
4:
for (k = 0; k < ROW ; k++)5:
tmp+ = A[i][k] ∗ B[k][j]6:
C[i][j] = tmp

Tiling
1: for (i0 = 0; i0 < COL; i0 +=8)
2: for (j0 = 0; j0 < ROW ; j0 +=8)3:mini = min(i0 + 7, COL)
4:for (i = i0 ; i < mini ; i++)5:minj = min(j0 + 7, ROW )6:
for (j = j0 ; j < minj ; j++)7:
tmp = 0.08:
for (k = 0; k < ROW ; k++)9:tmp+ = A[i][k] ∗ B[k][j]10:
C[i][j] = tmp

Figure 10: Matrix multiplication program following application of scalar replacement.

Figure 11: Result of Tiling.

the program [5].
We used an x64 machine with an Intel Xeon(R)CPU E5-1660 3.30GHz CPU and Debian OS. The
perf utility was employed to determine how eﬀectively misses of L1 data cache (L1D) and the lastlevel cache memory (LLC) can be reduced by ouraggregation. The cache memory parameters forthe x64 machine are shown in Table 1.

Applying these optimization settings result programs outlined in Figure 11 and Figure 12.
Loop tiling inserts two new loops (i0 - and j0 loops) based on the size of each cache line. Because the size of each cache line of the Xeon processor is 64, and the size of each element in matrices A and B is eight, we add i0 and j0 eight foreach iteration of the i0 - and j0 -loops.
The execution time and the number of cache
misses in the case where the optimizations areapplied without hardware prefetch are listed inTable 2.

Table 1: Cache memory parameters
Parameters
L1D
L2
L3
Total size (KB)32
256
15,360Line size (bytes)
64
64
64
Number of cache line 512 4,096 245,760
Associativity
8820

Table 2: Result of execution time and cache misses obtained by Tiling and MDGLIA-k-Unroll without hardware
prefetch
A.Tiling
B.MDGLIA-k-Unroll (A-B)/A
time
0.265
0.258
2.8%
L1D miss 576,314,189
768,844,837-33.4%
LLC miss 2,083,135
2,078,436
0.2%

To estimate eﬀect of our aggregation, we discuss four results: comparisons of 1) keep-ordercondition and 2) keep-dimension condition withloop tiling without hardware prefetch, 3) comparison of MDGLIA with LCM, and 4) comparison of MDGLIA with loop tiling using hardware
prefetch.

Loop unrolling can reduce the number of conditional jumps; therefore, it improves execution
eﬃciency. However, the L1D misses for MDGLIAk-Unroll are greater than that for Tiling because
the number of spills is increased as shown in Table
3. Once a variable is spilled, additional load/store
statements are inserted around references of thevariable; therefore, L1D misses may also occur
for the inserted load/store statements. Note herethat the eﬀect of the spills on cache miss depends
on the locations where the load/store statements
are inserted. Although MDGLIA-k-Unroll increased only one spill, the extra load/store statements could be inserted into the innermost loop.

5.1.1. Aggregation Under Keep-order Condition
To investigate how our aggregation without
considering array dimensions reduces the number of cache misses, we adopted the following two
kinds of optimization settings:
Tiling, application of scalar replacement andloop tiling.
MDGLIA-k-Unroll, application of scalar replacement, loop tiling, unrolling the k-loop,
and MDGLIA.
12

Applying Tiling, unrolling the k - loop seven times, and MDGLIA
1: for (i0 = 0; i0 < COL; i0 +=8)
2: for (j0 = 0; j0 < ROW ; j0 +=8)3:mini = min(i0 + 7, COL)
4:for (i = i0 ; i < mini ; i++)5:minj = min(j0 + 7, ROW )6:
for (j = j0 ; j < minj ; j++)7:
tmp = 0.08:
for (k = 0; k < ROW ;)9:
if (k + 7 < ROW )10:
a1 = A[i][k]; a2 = A[i][k + 1]; a3 = A[i][k + 2]; a4 = A[i][k + 3];
11:
a5 = A[i][k + 4]; a6 = A[i][k + 5]; a7 = A[i][k + 6]; a8 = A[i][k + 7];
12:
b1 = B[k][j]; b2 = B[k + 1][j]; b3 = B[k + 2][j]; b4 = B[k + 3][j];13:b5 = B[k + 4][j]; b6 = B[k + 5][j]; b7 = B[k + 6][j]; b8 = B[k + 7][j]14:tmp+ = a1 ∗ b1 + a2 ∗ b2 + a3 ∗ b3 + a4 ∗ b4 + a5 ∗ b5 + a6 ∗ b6 + a7 ∗ b7 + a8 ∗ b8
15:
k+=8
16:
else
17:
tmp+ = A[i][k] ∗ B[k][j]
18:
k++
19:
C[i][j] = tmp
Figure 12: Result of MDGLIA-k-Unroll.

Each statement in the innermost loop will be executed 500 × 500 × 500 times; thus, the increased
spills can worsen the results. The LLC miss results are virtually similar. This is because of thelarge sizes of the L2 cache memory and the LLC; we suppose these cache memories record data
missed in L1D. In addition, loop tiling can also
address the same problem as MDGLIA-k-Unroll.

subsequent application of MDGLIA results in the
program shown in Figure 14.
tmp11 +=A[i][k] ∗ B[k][j]tmp12 +=A[i][k + 1] ∗ B[k + 1][j]tmp13 +=A[i][k + 2] ∗ B[k + 2][j]tmp14 +=A[i][k + 3] ∗ B[k + 3][j]tmp15 +=A[i][k + 4] ∗ B[k + 4][j]tmp16 +=A[i][k + 5] ∗ B[k + 5][j]tmp17 +=A[i][k + 6] ∗ B[k + 6][j]tmp18 +=A[i][k + 7] ∗ B[k + 7][j]tmp11 +=A[i][k + 8] ∗ B[k + 8][j]tmp21 +=A[i][k] ∗ B[k][j + 1]
tmp22 +=A[i][k + 1] ∗ B[k + 1][j + 1]
tmp23 +=A[i][k + 2] ∗ B[k + 2][j + 1]
tmp24 +=A[i][k + 3] ∗ B[k + 3][j + 1]
tmp25 +=A[i][k + 4] ∗ B[k + 4][j + 1]
tmp26 +=A[i][k + 5] ∗ B[k + 5][j + 1]
tmp27 +=A[i][k + 6] ∗ B[k + 6][j + 1]
tmp28 +=A[i][k + 7] ∗ B[k + 7][j + 1]
tmp21 +=A[i][k + 8] ∗ B[k + 8][j + 1]

Table 3: Number of spills occurred by Tiling and
MDGLIA-k-Unroll

spillsA.Tiling B.MDGLIA-k-Unroll
34

5.1.2. Aggregation Under Keep-dimension Condition
To examine how aggregation considering array
dimensions reduces the number of cache misses,
we used the following optimization setting:Figure 13: Revealing redundant array references loading
data of array A by unroll-and-jam.

MDGLIA-j-Unroll, application of scalar replacement, loop tiling, unroll-and-jam to thej-loop, unrolling the k-loop, and MDGLIA.

The execution time and cache misses of Tilingand MDGLIA-j-Unroll are listed in Table 4. The
execution time of MDGLIA-j-Unroll is better
than that of Tiling about 40% because MDGLIA

Unrolling the j-loop reveals redundant arrayreferences to array A, as shown in Figure 13;13

Invoking unroll - and - jam to j - loop , Unrolling k - loop , and applying MDGLIA
1: for (i0 = 0; i0 < COL; i0 +=8)
2: for (j0 = 0; j0 < ROW ; j0 +=8)3:mini = min(i0 + 7, COL)
4:for (i = i0 ; i < mini ; i++)5:minj = min(j0 + 7, ROW )6:
for (j = j0 ; j < minj ;)7:
if (j + 1 < ROW )8:
tmp1 = 0.0
9:tmp2 = 0.0
10:
for (k = 0; k < ROW ;)11:
if (k + 7 < ROW )12:
a1 = A[i][k]; a2 = A[i][k + 1]; a3 = A[i][k + 2]; a4 = A[i][k + 3]; a5 = A[i][k + 4];
13:
a6 = A[i][k + 5]; a7 = A[i][k + 6]; a8 = A[i][k + 7];
14:
b11 = B[k][j]; b21 = B[k][j + 1]; b12 = B[k + 1][j]; b22 = B[k + 1][j + 1]
15:
b13 = B[k + 2][j]; b23 = B[k + 2][j + 1]; b14 = B[k + 3][j]; b24 = B[k + 3][j + 1];
16:
b15 = B[k + 4][j]; b25 = B[k + 4][j + 1]; b16 = B[k + 5][j]; b26 = B[k + 5][j + 1];17:
b17 = B[k + 6][j]; b27 = B[k + 6][j + 1]; b18 = B[k + 7][j]; b28 = B[k + 7][j + 1];
18:
tmp1 + = a1 ∗b11 +a2 ∗b12 +a3 ∗b13 +a4 ∗b14 +a5 ∗b15 +a6 ∗b16 +a7 ∗b17 +a8 ∗b18
19:
tmp2 + = a1 ∗b21 +a2 ∗b22 +a3 ∗b23 +a4 ∗b24 +a5 ∗b25 +a6 ∗b26 +a7 ∗b27 +a8 ∗b28
20:
k+=8
21:
else
22:
tmp1 + = A[i][k] ∗ B[k][j]23:
tmp2 + = A[i][k] ∗ B[k][j + 1]
24:
k++
25:
C[i][j] = tmp1
26:
C[i][j + 1] = tmp2
27:
j+=2
28:
else
29:
// following code is same as lines 7–19 of Figure 12
Figure 14: Result of MDGLIA-j-Unroll.

to stop delaying earlier than LCM. For example, consider a[i][j+1] in Figure 15(a). The
array reference is redundant; thus, it can be removed by LCM, as shown in Figure 15(b). On
the other hand, this array reference is relevant for
MDGLIA, which result in it moving, as shownin Figure 15(c). These observations show thatMDGLIA may enhance register pressure morethan LCM. If some store and load statements that
occur as a result of spills are inserted between thearray references to the same array, they may decrease the eﬀects of MDGLIA.

Table 4: Result of execution time and cache misses obtained by each optimization without hardware prefetch
A.Tiling
B.MDGLIA-j-Unroll (A-C)/A
time
0.265
0.159
40.2%
L1D miss 576,314,189
729,992,458-26.7%
LLC miss 2,083,135
2,338,954-12.3%

can remove redundant array references revealed
by loop unrolling. On the other hand, MDGLIAj-Unroll increases the number of L1D and LLC
misses. This is because some load/store statements that are inserted by spills can increase themisses as discussed in the previous section. Although LCM (lazy code motion) tries to reduce
the number of spills by delaying insertion points
as mentioned in Section 3.2, it can increase thenumber of spills [11]. In addition, MDGLIA tends

The number of spills caused by Tiling and
MDGLIA-j-Unroll are shown in Table 5. As
shown, the number of spills caused by MDGLIAj-Unroll is five times that of Tiling.
14

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

4 w=t

4 w=t

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

6 p=t

6 p=t

(a)

(b)

array references to array B are aggregated or
not; MDGLIA-j-Unroll aggregates them, whereas
LCM-j-Unroll does not.
The execution time and LLC misses for Tiling,
MDGLIA-j-Unroll, and LCM-j-Unroll are shownin Table 6. Comparing MDGLIA-j-Unroll with
LCM-j-Unroll, both the execution time and thenumber of LLC misses for MDGLIA-j-Unroll are
better than those of LCM-j-Unroll. Further, comparing LCM-j-Unroll with Tiling, the execution
time of LCM-j-Unroll is better than that of Tilingbut the number of misses for LLC have increased.
These results show that removing redundant loadstatements and aggregating array references significantly improve execution eﬃciency. In particular, aggregation considering array dimensions iseﬀective for reducing LLC misses.

(c)Figure 15: Diﬀerence in insertion point for a[i][j+1]:(a) Original code. (b) Result of applying LCM-MEM. (c)Result of applying MDGLIA.

Table 5: Number of spills occurred by Tiling and
MDGLIA-j-Unroll

spillsA.Tiling B.MDGLIA-j-Unroll
3
15

5.1.4. Eﬀectiveness of the combination of Aggregation and Hardware Prefetch
As mentioned in Section 2, hardware prefetch
is eﬀective for good spatial locality. Because
MDGLIA improves the locality, we examined
how the combination of MDGLIA and hardware
prefetch reduces the number of cache misses.
The results for Tiling, MDGLIA-j-Unroll, andMDGLIA-j-7-Unroll (in which the j-loop is unrolled seven times) with hardware prefetch are
shown in Table 7. Although the number of LLC
missed for MDGLIA-j-Unroll is greater than thatfor Tiling, the rate of increase is about 4.3%.
As shown in Table 4, the rate of increase for
MDGLIA-j-Unroll without hardware prefetch isabout 12.3%; therefore, MDGLIA with hardware
prefetch is more eﬀective than only MDGLIA.
Comparing MDGLIA-j-7-Unroll with MDGLIAj-Unroll, MDGLIA-j-7-Unroll reduces the number of LLC misses, but the execution time isincreased. This is because unrolling the j-loop
seven times can eﬀectively utilize cache memory
for loading data from array B, but it increases thenumber of spills, as shown in Table 8. Comparing MDGLIA-j-7-Unroll with Tiling, both the execution eﬃciency and the number of LLC misses
are similar, but MDGLIA-j-7-Unroll increases thenumber of spills by a factor of 23 over loop tiling.

B/A
5.0

In this section, we have discussed how our algorithm aﬀects the execution times and L1D and
LLC misses. In the following discussion, we will
especially concentrate on the execution times and
LLC misses because reducing the cache misses directly aﬀects the execution time.
5.1.3. Comparison of Aggregation with Redundancy Elimination
Although loop unrolling and redundancy elimination improve execution eﬃciency, combining
them results in an increase in the number of spills
and cache misses. In order to simply check how
our aggregation under keep-dimension condition
reduces the number of cache misses, we used thefollowing optimization setting:
LCM-j-Unroll, application of scalar replacement, loop tiling, unroll-and-jam to the jloop, unrolling the k-loop, and LCM.
The resulting program for the LCM-j-Unroll isshown in Figure 16. The diﬀerence between LCMj-Unroll and MDGLIA-j-Unroll lies in whether
15

Invoking unroll - and - jam to j - loop , Unrolling k - loop , and applying LCM
1: for (i0 = 0; i0 < COL; i0 +=8)
2: for (j0 = 0; j0 < ROW ; j0 +=8)3:mini = min(i0 + 7, COL)
4:for (i = i0 ; i < mini ; i++)5:minj = min(j0 + 7, ROW )6:
for (j = j0 ; j < minj ;)7:
if (j + 1 < ROW )8:
tmp1 = 0.0
9:tmp2 = 0.0
10:
for (k = 0; k < ROW ;)11:
if (k + 7 < ROW )12:
a1 = A[i][k]; a2 = A[i][k + 1]; a3 = A[i][k + 2]; a4 = A[i][k + 3]; a5 = A[i][k + 4];
13:
a6 = A[i][k + 5]; a7 = A[i][k + 6]; a8 = A[i][k + 7];
14:
b11 = B[k][j]; b12 = B[k + 1][j]; b13 = B[k + 2][j]; b14 = B[k + 3][j];15:b15 = B[k + 4][j]; b16 = B[k + 5][j]; b17 = B[k + 6][j]; b18 = B[k + 7][j];16:b21 = B[k][j +1]; b22 = B[k+1][j +1]; b23 = B[k+2][j +1]; b24 = B[k+3][j +1];17:
b25 = B[k + 4][j + 1]; b26 = B[k + 5][j + 1]; b27 = B[k + 6][j + 1];
18:
b28 = B[k + 7][j + 1];
19:
tmp1 + = a1 ∗b11 +a2 ∗b12 +a3 ∗b13 +a4 ∗b14 +a5 ∗b15 +a6 ∗b16 +a7 ∗b17 +a8 ∗b18
20:
tmp2 + = a1 ∗b21 +a2 ∗b22 +a3 ∗b23 +a4 ∗b24 +a5 ∗b25 +a6 ∗b26 +a7 ∗b27 +a8 ∗b28
21:
k+=8
22:
else
23:
tmp1 + = A[i][k] ∗ B[k][j]24:tmp2 + = A[i][k] ∗ B[k][j + 1]
25:
k++
26:
C[i][j] = tmp1
27:
C[i][j + 1] = tmp2
28:
j+=2
29:
else
30:
// following code is same as lines 7–19 of Figure 12
Figure 16: Resulting program for unrolling the j- and k-loops and removing redundant load statements.
Table 6: Result of execution time and cache misses obtained by Tiling, MDGLIA-j-Unroll, and LCM-j-Unrolltime
LLC miss

A.Tiling B.MDGLIA-j-Unroll
0.265
0.159
2,083,135
2,338,954

C.LCM-j-Unroll
0.203
4,079,427(A-C)/A
23.6%-95.8%(B-C)/B-27.7%-74.4%

Table 7: Results of execution time and cache misses obtained by each optimization technique with hardware prefetch

time
LLC miss

A.Tiling B.MDGLIA-j-Unroll
0.255
0.157
2,006,466
2,091,877

C.MDGLIA-j-7-Unroll
0.253
2,028,946(A-B)/A
38.5%
-4.3%

(A-C)/A
0.8%-1.1%

Table 8: Number of spills occurring for Tiling, MDGLIA-j-Unroll, and MDGLIA-j-7-Unroll

spillsA.Tiling B.MDGLIA-j-Unroll
3
15

16

C.MDGLIA-j-7-Unroll
69

B/A C/A
5.0
23

5.1.5. Discussions
In this evaluation, we used a program that multiplied two matrices, A and B, with sizes 500×500
on a Xeon computer with large cache memories(the associativity of L3 is 20).
In Section 5.1.1, we showed that unrolling theinnermost (k-) loop gives us a real situation inwhich accesses to array A alternate with accesses
to array B. Comparing the aggregation with loop
tiling, there is no diﬀerence between them in theview of LLC misses.
In Section 5.1.2, we showed that unroll-and-jam
reveals not only redundant array references, butalso references to the higher dimension of array
B alternating with references to the lower dimension of the array. Although removing the redundant array references remarkably improves execution eﬃciency, it increases the number of spills
and LLC misses.
In order to perform a simple check of the eﬀectiveness of our aggregation considering array dimension, we compared MDGLIA with LCM, andobtained results that showed that the aggregation
significantly reduces the number of LLC misses in
Section 5.1.3. This is because matrix multiplication has three loops: i-, j-, and k-loop, and unrolland-jam to the j-loop gives MDGLIA a chance toaggregate the data for B[k][j] and B[k][j + 1]. In
this program, we used 500 × 500 matrices; therefore, it is diﬃcult to store a datum of B[k][j +1] incache memory before use without our aggregation
because the associativity is 20.
These results show that removing redundancy
and aggregating array references improve the execution eﬃciency of objective codes. However, removing redundancy typically increases the number of spills, leading to reduced gain in decreasing
the cache misses by our aggregation. Therefore,
developing a new register allocation that performs
spills while considering cache misses may provide
powerful support for MDGLIA. In addition, as
shown in Section 5.1.4, using MDGLIA with hardware prefetch is good for decreasing cache misses.
In the view of execution eﬃciency, comparing
MDGLIA with hardware prefetch with loop tiling,
MDGLIA is better than loop tiling. However,in the view of cache misses, MDGLIA with un-

rolling the j-loop seven times increased the LLC
misses about 1.1% although MDGLIA increased
the number of spills by a factor of 23 over loop
tiling. This result implies that it is able to reduce
the LLC miss of MDGLIA to less than that ofloop tiling if the new register allocation has beendeveloped.
5.2. Examining the Eﬀect of Speculative Code
MotionIn this evaluation, we used the SPEC CPU 2000
benchmark to examine how our speculative code
motion contributes to reducing cache misses. We
used two CFP2000 programs (equake and art) andthree CINT2000 programs (mcf, gzip, and twolf)in the SPEC benchmarks on an x86 machine withan Intel Core2Duo U9600 1.6GHz CPU and CentOS. The cache memory parameters for the x86
machine are shown in Table 9. We kept the default hardware prefetch status because it was notpossible to change the status in the BIOS of thecomputer.
Table 9: Cache memories parameters

Parameters
Total size (KB)
Line size (bytes)
Number of cache line
Associativity

L1D
L2
32
3,072
64
64
512 49,152
8
12

To emphasize the benefits of our algorithm, we
compared MDGLIA with the following two optimizations.
LCM-MEM, which only removes redundant array references based on LCM.
GLIA, which aggregates references to the samearray without considering their dimensions.
To determine the level of reduction in cache
misses occasioned by GLIA and MDGLIA, wemeasured the following two hardware counters.
DCache Repl: the number of replacements of
L1 data cache.
L2 Lines Out: the number of removals fromthe L2 cache.
17

We simply call these numbers L1D cache miss andL2 cache miss, respectively.
The result of these cache misses for comparison
among the three optimizations is shown in Figure 17, and the results for the number of L1D
cache misses and L2 cache misses are shown, respectively, in Tables 10 and 11.

In addition, the execution times of objective
codes resulting from each optimization are shownin Figure 18 and Table 12.
GLIA

MDGLIA

16.0%
14.0%
12.0%

40.0%

L1D_cache_miss-GLIA

L2_cache_miss-GLIA

L1D_cache_miss-MDGLIA

L2_cache_miss-MDGLIA

10.0%
8.0%
6.0%
4.0%
2.0%
0.0%

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

-2.0%

art

mcf

-4.0%

gzip

art

mcf

gzip
ammp

twolf

ammp

Figure 18: Execution time of objective codes (second).

twolf

Figure 17: Ratio by which L1D and L2 cache misses are
reduced for GLIA and MDGLIA to the cache misses for
LCM-MEM.

The results are similar to the result for L2
cache misses. Comparing GLIA with LCM-MEM,
the execution time improved for three programs(art, mcf, and gzip), and worsened for two programs (ammp and twolf). Comparing MDGLIA
with LCM-MEM, the execution time improved for
four programs (art, mcf, gzip, and ammp), andworsened for twolf. Interestingly, in twolf, GLIA
and MDGLIA increased the number of L2 cache
misses about 10% and 20%, but the execution
time worsened about only 0.4% and 0.9%, respectively. In addition, in mcf, comparing MDGLIA
with LCM-MEM, the number of L2 cache misses
decreased about only 0.4%, but the execution
time improved about 1.6%. Comparing MDGLIA
with GLIA, the number of L2 cache misses for
MDGLIA is greater than that of GLIA, but theexecution time of MDGLIA better than GLIA.
This is because aggregation moves array references to points that are closer to the start node
than the original points; in other words, the rangeof the hide penalty of cache miss can be lengthened.
In some programs, GLIA and MDGLIA increased cache misses. The increase is considered
to be as a result of the following: 1) the number of spills of the temporary variables increased,
and 2) speculative code motion lengthened execu-

Comparing GLIA and MDGLIA with LCMMEM, the number of L1D cache misses is thesame degree as LCM-MEM for four programs(art, mcf, gzip, and twolf); however, for one program (ammp) the number increased about 7%.
Comparing GLIA with LCM-MEM, the numberof L2 cache misses decreased for three programs(art, mcf, and gzip). In particular, the cache misssignificantly decreased about 19.9% in art; however, the number of misses increased for two programs (ammp and twolf). Comparing MDGLIA
with LCM-MEM, L2 cache miss decreased for
four programs (art, mcf, gzip, and ammp). In
particular, the cache miss significantly decreased
about 30.3% in art; however, the number of misses
increased for twolf. Comparing MDGLIA with
GLIA, L2 cache miss decreased for four programs(art, gzip, ammp, and twolf). In particular, thecache miss significantly decreased about 15.6% in
ammp. In ammp, the algorithms were comparedwith LCM-MEM, although GLIA increased thenumber of L2 cache misses in ammp, MDGLIA
reduced it. This is because MDGLIA can aggregate more array references than GLIA.
18

Table 10: Number of L1D cache misses

Program A.LCM-MEM
B.GLIA
C.MDGLIA (A-B)/A (A-C)/A (B-C)/B
art 11,439,104,576 11,453,555,362 11,444,685,513
-0.1%
-0.1%
0.1%
mcf 7,567,419,160 7,531,488,486 7,544,975,464
0.5%
0.3%
-0.2%
gzip 7,725,469,653 7,707,389,218 7,818,871,317
0.2%
-1.2%
-1.4%
-6.5%
-7.4%
-0.8%
ammp 21,792,733,488 23,216,563,772 23,413,676,395
twolf 9,056,125,547 9,029,509,531 8,986,903,509
0.3%
0.8%
0.5%
Table 11: Number of L2 cache misses

Program A.LCM-MEM
B.GLIA C.MDGLIA (A-B)/A (A-C)/A (B-C)/B
art
366,823,834 293,702,375 255,801,603
19.9%
30.3%
12.9%
mcf
727,422,092 720,133,268 724,349,339
1.0%
0.4%
-0.6%
gzip
25,856,048 25,177,224
24,706,624
2.6%
4.5%
1.9%
ammp
408,120,338 419,706,166 354,268,633
-2.8%
13.2%
15.6%
twolf
1,518,718
1,812,932
1,678,713-19.4%-10.5%
7.4%
Table 12: Execution time of objective codes (second)

Program
art
mcf
gzip
ammp
twolf

A.LCM-MEM B.GLIA
97.2
89.2
97.6
96.3
211
209
475
488
228
229

C.MDGLIA
87.4
96.0
209
449
230

tion paths without reducing the number of cache
misses, as mentioned in Section 4.2.1.
We confirm how the problems increase the number of cache misses below.

(A-B)/A
8.2%
1.3%
0.9%
-2.7%
-0.4%

(A-C)/A
10.1%
1.6%
0.9%
5.5%
-0.9%

(B-C)/B
2.0%
0.3%
0.0%
8.0%
-0.4%

ber of spills. Note here that, in the previous experiment, matrix multiplication experiment, spills
may insert load/store statements in loops because
our algorithm increases register pressures in loop.
In contrast, in this experiment, SPEC CPU 2000,
we applied our algorithm the overall program, including outside of loops. That is, Table 13 includes the number of spills occurred in outside ofloops. Conversely, in twolf, the number of spills
and cache misses increased. We believe that theload/store statements for spills were inserted between references that were continuously moved by
MDGLIA.

5.2.1. Impact of Spill
The number of spills that occur for applications of the three optimizations is shown in Table
13. Comparing GLIA and MDGLIA with LCMMEM, they caused more spills for four programs(mcf, gzip, ammp, and twolf). In particular, thenumber of spills increased about 20% in twolf.
However, in spite of the increase in the numberof spills, the L1D cache misses were held at thesame degree with LCM-MEM in mcf and gzip.
These additional results show that the increase in
the spills does not always equate to an increase in
the number of cache misses; in particular, the sizeof a program is large, such as SPEC CPU benchmark. In fact, in ammp, application of MDGLIA
reduced L2 cache misses but increased the num-

5.2.2. Speculative Code Motion vs. Unspeculative
Code Motion
In order to determine the number of cache
misses that the speculative code motion decreased, we implemented the following two optimizations that do not speculatively aggregate
array references:19

Table 13: Number of spills

Program
art
mcf
gzip
ammp
twolf

A.LCM-MEM B.GLIA
28
28
61
71
107
114
317
334
804
962

C.MDGLIA
28
71
114
335
979

USGLIA, which aggregates array referenceswith the keep-order condition by using
UpSafe, defined in equation (1) rather thanequation (2).

MDGLIAart

mcf

USGLIAUSMDGLIA

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

gzip

ammp-20.0%-30.0%(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 %

was better than these unspeculative versions insome programs. This is because speculative code
motion can move array references more than unspeculative ones. Table 15 shows the number ofstopped delaying by checking keep-order or keepdimension conditions in the speculative and unspeculative code motions. As shown by the table,
the speculative code motion could move more array references than unspeculative one.
Considering L2 cache misses when GLIA,MDGLIA, USGLIA, and USMDGLIA were applied to twolf, they increased L2 cache misses in
the program. Although the increase for GLIA wasabout 20%, the increase for the others increasing was about 10%. Furthermore, comparing USGLIA and USMDGLIA, the results of L2 cache
misses are held at the same degree between the
two algorithms. This result indicates that speculative insertion under keep-order condition increases the number of cache misses for twolf. On
the other hand, speculative insertion under keepdimension condition decreases the cache misses.
That is, the speculative aggregation consideringkeep-dimension condition reduced the number of
L2 cache misses.

USMDGLIA, which aggregates array references with the keep-order and keepdimension conditions by using UpSafe
defined in equation (1) rather than equation
(2).

GLIA

(A-B)/A
0.0 %-16.4 %
-6.5 %-5.4 %-19.7 %

twolf

Figure 19: Ratio of reduction in L2 cache misses for GLIA,MDGLIA, USGLIA, and USMDGLIA to the cache missfor LCM-MEM.

5.2.3. Discussion
These results show that speculative code motion is useful for reducing cache misses, comparedwith simply removing redundant array references.
Because the speculative code motion can move array references further than unspeculative one, but
unspeculative code motion is sometimes better
than speculative ones. We believe that extensionof MDGLIA for analyzing whether the aggregatedarray references will get a cache hit using profile
information has the potential to significantly reduce cache misses.

The resulting L2 cache misses after applying
USGLIA and USMDGLIA are shown in Figure 19 and Table 14. Comparing GLIA withUSGLIA, GLIA increased the number of cache
misses for three programs (art, ammp, and twolf).
In contrast, comparing MDGLIA with USGLIA,MDGLIA reduced the number of cache misses
for two programs (art and gzip). Comparing
MDGLIA with USMDGLIA, MDGLIA reduced
the number of cache misses for four programs(art, mcf, gzip, and ammp). Thus, MDGLIA
20

Table 14: Number of L2 cache misses of USGLIA and USMDGLIA, and the ratio of their cache misses to the cache missfor GLIA and MDGLIA

Program
art
mcf
gzip
ammp
twolf

USGLIA vs. GLIA vs. MDGLIA
282,855,332
3.7 %-10.6 %
721,268,586-0.2 %
0.4 %
25,449,483-1.1 %-3.0 %
345,935,455
17.6 %
2.4 %
1,689,141
6.8 %-0.6 %USMDGLIA vs. MDGLIA
297,012,498-16.1 %
732,708,340-1.2 %
26,351,879-6.7 %
359,701,112-1.5 %
1,667,434
0.7 %Table 15: Number of aggregated array references by working keepOrder and keepDimension in speculative/unspeculativecode motion

Program
art
mcf
gzip
ammp
twolf

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

As stated in Section 3.1, MDGLIA assumes
that array data is placed in row-major order.
However, recently, Hilbert space-filling curve wasused rather than row-major order. This trendmeans that it is eﬀective for aggregating arrayreferences to use profile information for switchingdata-layouts. In addition, the usage of profile information may enhance aggregation by estimating
speculation penalties and heavy uses of pointers.
Because the current algorithm of MDGLIA does
not handle pointer operations sophisticatedly, theextension with the-state-of-art alias or points-to
analysis techniques [12, 25] may improve some
practical programs such as SPEC benchmarks.

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

SPEC CPU 2000 benchmark programs. Consequently, we showed that our aggregation significantly reduces the number of cache misses. The
results of evaluation of matrix multiplication indicate that removing redundant array references
sometimes reduces the gain of the aggregation because of increasing spills; therefore, developing a
new register allocation is one of the most important future works. From the evaluation of SPECCPU 2000, we found that speculative code motion can reduce the number of cache misses, butsometimes increases it. We believe that extending MDGLIA to use profile information in orderto analyze the aggregated array references has thepotential to further reduce cache misses.

6. Conclusions
Acknowledgements
In this paper, we proposed a new global code
motion algorithm that aggregates array referenceswith the same indexes for the same array in order to reduce the number of cache misses. Ouralgorithm not only reduces the number of cache
misses but also suppresses spills by delaying thearray references without changing their access order.
To demonstrate the eﬀectiveness of our algorithm, we applied it to matrix multiplication andWe would like to thank the reviewers for theirvaluable and insightful comments and suggestions that helped improve the paper. This research is partially supported by Scientific Research (25330089).
References[1] Aho, A.V., Sethi, R., Ullman, J.D., 1986. Compilers:principles, techniques, and tools. Addison-Wesley21Longman Publishing Co., Inc., Boston, MA, USA.
Verlag, London, UK, UK. pp. 107–121.
URL:[2] Appel, A.W., 1997. Modern Compiler Implementahttp://dl.acm.org/citation.cfm?id=647475.727623.
tion in ML: Basic Techniques. Cambridge University[12] Hardekopf, B., Lin, C., 2009. Semi-sparse flowsensitive pointer analysis, in: Proceedings of thePress, New York, NY, USA.
[3] Bodik, R., Gupta, R., Soﬀa, M.L., 1998. Complete
36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages,
removal of redundant expressions, in: Proceedings
ACM, New York, NY, USA. pp. 226–238. URL:of the ACM SIGPLAN 1998 conference on Programming language design and implementation,
http://doi.acm.org/10.1145/1480881.1480911,
doi:10.1145/1480881.1480911.
ACM, New York, NY, USA. pp. 1–14.
URL:[13] Ishitobi, Y., Ishihara, T., Yasuura, H., 2010.
http://doi.acm.org/10.1145/277650.277653,
Code and data placement for embedded prodoi:10.1145/277650.277653.
cessors with scratchpad and cache memories.
[4] Calder, B., Krintz, C., John, S., Austin, T.,
J. Signal Process. Syst. 60, 211–224.
URL:
1998.
Cache-conscious data placement, in:
http://dx.doi.org/10.1007/s11265-008-0306-3,
Proceedings of the eighth international condoi:10.1007/s11265-008-0306-3.
ference on Architectural support for programming languages and operating systems, ACM,
[14] Kawahito, M., Komatsu, H., Nakatani, T.,
New York, NY, USA. pp. 139–149.
URL:
2004.
Partial redundancy elimination for
http://doi.acm.org/10.1145/291069.291036,
access expressions by speculative code modoi:10.1145/291069.291036.
tion.
Softw. Pract. Exper. 34, 1065–1090.
[5] Carr, S., Kennedy, K., 1994.
URL:
http://dx.doi.org/10.1002/spe.604,
Scalar replacedoi:10.1002/spe.604.
ment in the presence of conditional control[15] Knoop, J., Ruthing, O., Steﬀen, B., 1992. Lazyflow.
Softw. Pract. Exper. 24, 51–77.
URL:
code motion, in:Proceedings of the ACM
http://dx.doi.org/10.1002/spe.4380240104,
SIGPLAN 1992 conference on Programmingdoi:10.1002/spe.4380240104.
language design and implementation, ACM,
[6] Chaitin, G.J., 1982. Register allocation & spilling
New York, NY, USA. pp. 224–234.
URL:
via graph coloring, in: Proceedings of the 1982
http://doi.acm.org/10.1145/143095.143136,
SIGPLAN symposium on Compiler construction,
doi:10.1145/143095.143136.
ACM, New York, NY, USA. pp. 98–105. URL:
[16] Lo, R., Chow, F., Kennedy, R., Liu, S.M., Tu,
http://doi.acm.org/10.1145/800230.806984,
doi:10.1145/800230.806984.
P., 1998. Register promotion by sparse partial[7] Dhamdhere, D.M., 1988. A fast algorithm for code
redundancy elimination of loads and stores, in:Proceedings of the ACM SIGPLAN 1998 conference
movement optimisation. SIGPLAN Not. 23, 172–180.
on Programming language design and implementaURL: http://doi.acm.org/10.1145/51607.51621,
tion, ACM, New York, NY, USA. pp. 26–37. URL:
doi:10.1145/51607.51621.
http://doi.acm.org/10.1145/277650.277659,[8] Dhamdhere, D.M., Patil, H., 1993.
An elimdoi:10.1145/277650.277659.
ination algorithm for bidirectional data flow[17] Mahlke, S.A., Chen, W.Y., Bringmann, R.A., Hank,
problems using edge placement.
ACM Trans.
Program. Lang. Syst. 15, 312–336.
URL:
R.E., Hwu, W.M.W., Rau, B.R., Schlansker,
http://doi.acm.org/10.1145/169701.169684,
M.S., 1993.
Sentinel scheduling:
A modeldoi:10.1145/169701.169684.
for compiler-controlled speculative execution.
[9] Geng, Y., Huang, X., Yang, G., 2014. SwiftarACM Trans. Comput. Syst. 11, 376–408. URL:
ray: Accelerating queries on multidimensional arhttp://doi.acm.org/10.1145/161541.159765,
rays. Tsinghua Science and Technology 19, 521–530.
doi:10.1145/161541.159765.
doi:10.1109/TST.2014.6919829.
[18] Morel, E., Renvoise, C., 1979.
Global op[10] Gupta, R., Berson, D.A., Fang, J.Z., 1998. Pathtimization by suppression of partial redunprofile guided partial redundancy elimination using
dancies.
Commun. ACM 22, 96–103.
URL:
speculation, in: Proceedings of the 1998 International
http://doi.acm.org/10.1145/359060.359069,
Conference on Computer Languages, IEEE Comdoi:10.1145/359060.359069.
puter Society, Washington, DC, USA. pp. 230–. URL:
[19] Odaira, R., Hiraki, K., 2004. Partial value number
redundancy elimination. Information Processing Sohttp://dl.acm.org/citation.cfm?id=857172.857261.
ciety of Japan Transactions on Programming 45, 59–[11] Gupta, R., Bodik, R., 1999. Register pressure
sensitive redundancy elimination, in: Proceed79. (in Japanese).
Linearings of the 8th International Conference on[20] Poletto, M., Sarkar, V., 1999.
scan register allocation.
ACM Trans. ProCompiler Construction, Held as Part of thegram. Lang. Syst. 21, 895–913.
URL:
European Joint Conferences on the Theory
http://doi.acm.org/10.1145/330249.330250,
and Practice of Software, ETAPS’99, Springer-

22

sium on Principles of programming languages,
ACM, New York, NY, USA. pp. 197–208. URL:
http://doi.acm.org/10.1145/1328438.1328464,
doi:10.1145/1328438.1328464.

doi:10.1145/330249.330250.
[21] Sarkar, S., Tullsen, D.M., 2008. Compiler techniques
for reducing data cache miss rate on a multithreaded
architecture, in: Proceedings of the 3rd international
conference on High performance embedded architectures and compilers, Springer-Verlag, Berlin, Heidelberg. pp. 353–368.
[22] Smith,
A.J.,
1982.
Cache memories.
ACM Comput. Surv. 14, 473–530.
URL:
http://doi.acm.org/10.1145/356887.356892,
doi:10.1145/356887.356892.
[23] Sumikawa, Y., Takimoto, M., 2013.
Eﬀectivedemand-driven partial redundancy elimination. Information Processing Society of Japan Transactions
on Programming 6, 33–44.
[24] Sumikawa, Y., Takimoto, M., 2014. Global load
instruction aggregation based on array dimensions,in: Proceedings of the 2014 Sixh International Symposium on Parallel Architectures, Algorithms andProgramming, IEEE Computer Society, Washington,
DC, USA. pp. 123–129. doi:10.1109/PAAP.2014.43.
[25] Zheng, X., Rugina, R., 2008.
Demand-driven
alias analysis for c, in:Proceedings of the35th annual ACM SIGPLAN-SIGACT sympo-

Yasunobu Sumikawa received his B.S. degreein Mathematics from Tokyo University of Sciencein 2010, and his M.S. and Ph.D. degrees in Information Science from Tokyo University of Sciencein 2012 and 2015, respectively. He is currently
an assistant professor at Tokyo University of Science. His research interests lie in compiler anddata mining.
Munihiro Takimoto is a professor in the Department of Information Sciences at Tokyo University of Science. His research interests include
the design and implementation of programming
languages. He received his undergraduate, postgraduate, and doctoral degrees in engineeringfrom Keio University.

23