编译器优化：图算法在编译后端的应用

编译原理

需积分: 10 99 浏览量更新于2024-07-18 1 收藏 713KB PDF 举报

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

领优惠券(最高得80元）

"该资源是一份关于编译器优化中使用的图算法的PDF文档，作者是Carl D. Oﬀner，来自University of Massachusetts Boston。文档主要涵盖了深度优先搜索、流图、可约流图以及测试可约性等相关图论算法，并讨论了它们在编译器优化中的应用。" 在编译器优化中，图算法扮演着至关重要的角色，特别是在编译器的后端阶段。以下是这些算法的一些核心概念和应用： 1. **深度优先搜索(DFS)** - 深度优先遍历是一种探索图的方法，从一个顶点开始，尽可能深地沿着边向下搜索，直到到达叶子节点或回溯。 - DFS可用于识别有向无环图(DAGs)、确定顶点的后代关系，并在寻找强连通分量时发挥作用。 2. **有向无环图(DAGs)的特性** - DAGs在编译器优化中特别重要，因为它们可以表示程序的控制流，如函数调用和循环结构。 - 通过DFS，可以明确地描述DAGs的结构，例如，确定是否存在从一个顶点到另一个顶点的路径。 3. **支配者** - 在流图中，一个顶点A支配另一个顶点B，如果从B出发的所有路径都必须经过A。 - 掌握支配理论对于计算前驱节点和后继节点，以及在数据流分析中找到局部最优解至关重要。 4. **可约流图** - 可约流图是具有特定结构的图，使得编译器可以更有效地进行优化。 - 可约流图的概念与间隔(intervals)紧密相关，它们有助于简化图的表示，从而简化分析和优化过程。 5. **间隔算法** - 间隔是用于构建可约流图的工具，它们定义了顶点的相对顺序，并帮助识别不可约子图。 - 算法如T1和T2被用来构造和操作间隔，以实现图的可约性测试和转换。 6. **数据流分析的应用** - 数据流分析是编译器优化的关键部分，它利用图算法来理解程序的静态信息流，如变量的使用和定义。 - 分析结果可以帮助识别冗余计算，消除死代码，以及插入优化如常量折叠和公共子表达式消除。这份PDF文档详细介绍了这些概念，并提供了Tarjan等人的算法实现，这些都是编译器设计和优化领域的基础。通过深入理解和应用这些算法，开发者能够构建更高效、更优化的编译器，从而提高程序的性能。

资源详情

资源推荐

12 CHAPTER 1. DEPTH-FIRST WALKS

The reverse graph G

of G is the graph with the same nodes as G but with each edge reversed (i.e. “pointing

in the opposite direction”). It is immediate that the strongly connected components of G are the same as

those of G

1.14 Lemma If {T

} is the spanning forest of trees produced by a depth-ﬁrst traversal of G, then (the set of nodes

of) each strongly connected component of G is contained in (the set of nodes of) one of the T

Remark Intuitively, once a depth-ﬁr s t walk reaches one node of a strongly connected component, it will

reach all other nodes in that component in the same depth-ﬁrst tree of the walk. The path lemma en ables

us to give a qu ick proof of this fact:

Proof. If x and y are contained in the same strongly connected component of G, let us suppose without

loss of generality that pre[x] < pre[y]. Since we know there is a path from x to y, some element u of that

path is an ancestor of x and y. That is, x, y, and u must all belong to the s ame tree in the forest. Since x

and y are arbitrary, each element in the strongly connected component must belong to th at same tree.

procedure SCC(G: graph)

begin

Perform a d ep th -ﬁ r s t traversal of G, assigning to each node x its reverse-post-order number rpost[x].

Perform a de pt h- ﬁr s t traversal of G

. Each time a choice is necessary in the while loop of the driving

procedure DFWalk, choose the node x which has not yet been visited and for which rpost[x] is

least.

Return the family of trees produ ce d by this second walk. Each tree is a strongly conn ec te d component

of G.

end

Figure 1.7: Algorith m for computing strongly-connected components.

1.15 Theorem The algor it hm in Figure 1.7 computes the strongly connect ed components of G.

Proof. By the lemma, each strongly connected component lies entirely within some tree T in the forest

produced by the second de pt h- ﬁr s t traversal (i.e., the traversal of G

). So we only have to prove that each

tree in the forest is strongly connected. To do this, it is enough to prove that if r is the root of a tree T in

the forest and x is an element of T diﬀerent from r, then x and r are in the same component; i.e. that there

exist paths in G (or in G

, for that matter) from x to r and from r to x. We may assume that x 6= r.

Since x is an element of the tree T rooted at r, there is a path in G

from r to x (namely the path of tree

arcs from r to x). The reverse path is therefore a path in G from x to r. We note that this path lies entirely

in T

Note that what we are denoting here by T

is not a tree. It is just the tree T with all the edges reversed.

These reversed edges are all edges in the original graph G.

Thus there is a path in G from x to r. It remains to show that the r e is a path i n G from r to x.

1.6. TARJAN’S ORIGINAL ALGORITHM 13

To show this, we will show that in fact r is an ancestor of x in the original dept h- ﬁr s t walk (the one over G

in the algorithm).

Now f or r to be an ancestor of x, it is nece s sar y and suﬃcient that both

pre[r] < pre[x]

rpost[r] < rpost[x]

Further , by the cons t r uc tion , we know that rpost[r] < rpost[x]. (This is true because of the choice made in

the second step of the algorit hm.)

Therefore r is an ancestor of x iﬀ pre[r] < pre[x].

Suppose then this is not tru e. Then (since x 6= r) pre[x] < pre[r], and so by the Path Lemma, there is an

element u on the path in T

from x to r which is an ancestor of both r and x. Hence rpost[u] ≤ rpost[r], and

since u is an ancestor of x ( b ut by assumpt ion r is not), u 6= r, so in fact rpost[u] < rpost[r], contradicting

the choice of r made in the second step of the algorithm.

This algorithm was published in Aho, Hopcroft, and Ullman[1], and is originally due to R. Kosaraju (un-

published) and Sharir[17].

Figure 1.8 gives an example of the workings of th is algorithm.

1.6 Tarjan’s Original Algorithm

Tarjan was the ﬁrst person to give an algorithm for ﬁnding strongly connected components in time pro-

portional to the size of G. Although this algorithm is more intricate than the algorithm presented in the

previous section , it is quite easy to program, and is possibly somewhat more eﬃcient.

We begin with a strengthening of Lemma 1.14:

1.16 Lemma If T is any one of the trees generated by a depth-ﬁrst search of G, then the intersection of the nodes

and edges of T with t hose of a strongly connected component of G is again a tree.

Proof. Let R be a str ongly connected component of G. By Lemma 1.14, either R is disjoint from T or its

set of nodes is completely contained in T . Further, from the proof of Lemma 1.14, we know that given any

two elements x and y of R, they have a common ancestor in R. By iterating the process of ﬁnding common

ancestors, we can thus ﬁnd an element r of R which is a common ancestor of e very other element in R.

If y is any node in the component, and if r →

∗

x →

∗

y is a path (x being any node in G) in T , then since

there must be a path in G fr om y to r, x must also be in the component. Thus, the intersection of T with

the component is itself a tree rooted at r.

We r ef er to the node r as t he root of the strongly connected component. r can be characterized as the node

in the component whose pre-order number is least. Since it is an ancestor of every node in the component,

its reverse post-order numb er is also least.

Note that r is not a unique entry node of R: a strongly connected component could have more than one entry

node; and diﬀerent depth-ﬁrst searches of G could yield diﬀerent roots of a strongly connected component.

1.6. TARJAN’S ORIGINAL ALGORITHM 15

Now for any node x in a strongly connected component R, consider the set of paths P(x) of the form

x = x

→ x

→ . . . → x

→ y where

1. all the nodes in the path ar e in R,

2. all the arcs in the path except the last one are tr ee arcs (and so in particular, each arc is an arc from

a node to a descendant of that node),

3. the arc x

→ y is either a back arc or a cross arc.

Let L(x) denote the lesser of pre[x] and t he minimum value of pre[y] where y is reachable from x by such

an arc. So in particular, L(x) ≤ pre[x].

Note that L(x) would have the same value if the arcs up to the last arc could also be forward arcs. Such

a forward arc could always be replaced by a sequence of tree arcs. For our purposes, it is simpler to ignor e

the forward arcs.

1.17 Lemma A node x is the root r of a strongly connected region ⇐⇒ L(x) = pre[x].

Proof. =⇒ : This is immediate from the fact that pre[y] ≥ pre[r] for any node y in R.

⇐= : Say x 6= r. Again, denote the depth-ﬁrst spanning tree by T . By t he previous lemma, T ∩ R is a tree

rooted at r. Since x 6= r, the subtree of T

rooted at x (call it T

R,x

) does not contain r. There is a p ath

from x to r (and certainly every element of this path is in R). Let y be the ﬁrst element of this path not in

R,x

. Then the predecessor p of y on this path can be reached by a series of arcs in T

R,x

, and so that series

of arcs followed by the arc p → y constitutes a path P in P(x).

Now if pre[y] > pre[x], then by the Path Lemma, x would be an ancestor of y, which is impossible because

y /∈ T

R,x

. Hence pre[y] < pre[x], and so L(x) < x.

The problem with this Lemma is that without knowing R to begin with, condition 1 is impossible to evaluate.

Therefore, we shall show below how to replace this cond it ion with one that is easily det er i mine d. This is

Tarjan’s key point.

1.18 Lemma If R is a strongly connected component of G with root r, and if r → x

→ x

→ . . . → x

→ y

is a path with all arcs except the la s t being either tree arcs or forward arcs, and if pre[y] < pre[r] (so in

par ticu l ar , y does not lie in R), then if s is the root of the strongly connected com ponent containing y, we

have rpost[s] > rpost[r].

Proof. An equivalent statement is this: if R and S are d is tin c t strongly conn ec te d components with roots

r and s respectively, and if x ∈ R and y ∈ S and there is an arc x → y, and if pre[y] < pre[r], then

rpost[s] > rpost[r].

We know in any case that pre[s] ≤ pre[y] < pr e[r]. If als o rpost[s] < rpost[r] then r would be a descendant

of s. Since there is a path from r to s (containing the arc x → y), this would mean that R and S are really

the same strongly connected component, a contradiction.

So here is how the algorithm works: We perform a depth-ﬁrst search of the graph. We maintain an auxiliary

stack σ of nodes of G. σ will be managed just like the implicit stack of the depth-ﬁrst search, except that

nodes are not automatically popped oﬀ it when their processing is ﬁnished.

16 CHAPTER 1. DEPTH-FIRST WALKS

To be pr ec is e , σ is managed as follows: As each node is ﬁrst reached, it is pushed on σ. (That is, the

nodes of G are pushed on σ in pre-order .) Thus the desc en dants of each node lie above the node on σ.

In particular, the roots of the strongly connected components of G will eventually be on σ with the other

elements of their c omponent above them. When the processing (i.e. in the d ep th -ﬁ r s t walk) for a root r is

ﬁnished, we pop every element in th e stack down to and including r. (For this to happen, of course, we have

to be able to identify the nodes which are roots of strongly connected regions. We deal with this below.)

No other elements of other strongly connected regions can be among the elements popped. This is because

if y were such an element, it would have been placed on the stack after r was ﬁrst reached and before the

processing of r was ﬁnished, and so would be a descendant of r. So by the preceding lemma, the root s of

the component of y would also be a descendant of r, and so would have been placed above r on the stack.

Since its pr ocessing would have been ﬁnished before r’s proces s in g, s and all nodes higher than it on the

stack, including y, would already have been popped oﬀ the stack before we pop r.

As noted above, for this algorithm to work, we have to b e able to identify the roots of the strongly connected

regions. Using the stack σ, we can do this as follows: for each node x being processed, compute the attribute

L[x] (L is the replacement for L above), whose value is deﬁned to be th e lesser of pre[x] and the minimum

of pre[y] taken over all y such that there is a path x = x

→ x

→ . . . → x

→ y where

1. Each arc up to x

is a tree arc.

2. The arc x

→ y is a back arc or a cross arc.

3. y is on σ at some point durin g the processing of x.

Here condition 3 substitutes for the pr ev ious condition 1.

The same argument as in Lemma 1.17 shows that if x is not a root, then L[x] < pre[x].

On the other hand, l et r be a root, and let y be th at node for which pre[y] = L(r). Now the only way

we could have L[r] < pre[r] is if the y belonged to a strongly connected component with root s such that

rpost[s] > rpost[r]. S in ce we also have pre[s] ≤ pre[y] = L(r) < pre[r], we have

start[s] < start[r]

ﬁnish[s] < ﬁnish[r]

and so by the parenthesis nesting property, ﬁnish[s] < start[r]; i.e., the processing of s is ﬁnished before the

processing of r starts, which means that s (and hence y) is not on the stack at any time during the processing

of r. Hence L[r] = pre[r].

Thus in the algorithm, we compute L[x] for each node as it is processed. When the processing of the no de is

ﬁnished, if L[x] = pre[x], it is known to be a root, and it and all elements above it on the stack are popped

and constitute a strongly connected component.

The complete algorithm is shown in Figure 1.9. Figure 1.10 shows the order in which the str ongly connected

components of the graph in Figure 1.8 ar e discovered, with the same depth-ﬁrst walk as in that ﬁgure.

剩余99页未读，继续阅读

xwjbs

粉丝: 45
资源: 5

编译器优化：图算法在编译后端的应用

编译原理 代码优化 基本块

c语言实现语法分析器.doc 设计

图优化资料

编译原理与编译过程简介

编译原理基础概念解析

有限自动机与编译原理

编译原理：扩展巴科斯范式和语法图技术

编译原理：探究语言的构成要素

编译系统透视:图解编译原理 pdf

编译系统透视图解编译原理 pdf

山东大学编译原理实验java

android apk编译原理

编译原理期末试题 csdn

Altium Designer设计电路原理图面试考点

编译原理算法有线分析器代码

编译原理 分析python的语言环境结构图

编译原理词法分析程序c语言

编译原理如何判断是否活跃信息

厦门理工学院编译原理实验二nfa赚dfa

编译原理 LR分析法实验内容

最新资源

编译原理代码优化基本块

编译原理分析python的语言环境结构图