Dominance Frontier (1157471)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

The next three subsections present, in detail, an algorithm to build semipruned SSA form—a version with fewer _-functions. Section 9.3.2 shows how dominance information introduced in Section 9.2.1 can be used to compute dominance frontiers to guide insertion of _-functions. Section 9.3.3 gives an algorithm to insert _-functions, and Section 9.3.4 shows how to rewrite variable names to complete the construction of SSA form. Section 9.3.5 discusses the difficulties that can arise in converting the code back into an executable form.

9.3.2 Dominance Frontiers

The primary problem with maximal SSA form is that it contains too many -functions. To reduce their number, the compiler must determine more carefully where they are required. The key to placing -functions lies in understanding which variables need a -function at each join point. To solve this problem efficiently and effectively, the compiler can turn the question around. It can determine, for each block i, the set of blocks that will need a -function for any definition in block i. Dominance plays a critical role in this computation.

Consider a definition in node n of the CFG. That value could potentially reach every node m where n  Dom(m) without need for a -function, since every path that reaches m passes through n. The only way that the value does not reach m is if another definition of the same name intervenes—that is, it occurs in some node p between n and m. In this case, the definition in n does not force the presence of a -function; instead, the redefinition in p does.

A definition in node n forces a -function at join points that lie just outside the region of the CFG that n dominates. More formally, a definition in node n forces a corresponding -function at any join point m where (1) n dominates a predecessor of m (q 2 preds(m) and n 2 Dom(q)), and (2) n does not strictly dominate m. (Using strict dominance rather than dominance allows a _-function at the start of a single-block loop. In that case, nDm, and m =2 Dom(n)fng.)We call the collection of nodes m that have this property with respect to n the dominance frontier of n, denoted DF(n).

Informally, DF(n) contains the first nodes reachable from n that n does not dominate, on each CFG path leaving n. In the CFG of our continuing example, B5 dominates B6, B7, and B8, but does not dominate B3. On every path leaving B5, B3 is the first node that B5 does not dominate. Thus, DF(B5) D fB3g.

Dominator Trees

Before giving an algorithm to compute dominance frontiers, we must introduce one further notion, the dominator tree. Given a node n in a flow graph the set of nodes that strictly dominate n is given by (Dom(n) n). The node in that set that is closest to n is called n’s immediate dominator, denoted IDom(n). The entry node of the flow graph has no immediate dominator.

The dominator tree of a flow graph contains every node of the flow graph. Its edges encode the IDom sets in a simple way. If m is IDom(n), then the dominator tree has an edge from m to n. The dominator tree for our example CFG appears in the margin. Notice that B6, B7, and B8 are all children of B5, even though B7 is not an immediate successor of B5 in the CFG.

The dominator tree compactly encodes both the IDom information and the complete Dom sets for each node. Given a node n in the dominator tree, IDom(n) is just its parent in the tree. The nodes in Dom(n) are exactly the nodes that lie on the path from the root of the dominator tree to n,

for all n  CFG

DF(n) ;

for all n  CFG

if |Pred(n)| 2 then

for each p  Pred(n)

runner p

while runner  IDom(n)

DF(runner) DF(runner)  {fn}

runner IDom(runner)

FIGURE 9.8 Algorithm for Computing Dominance Frontiers.

inclusive of both the root and n. From the tree, we can read the following

sets:

Computing Dominance Frontiers

To make _-insertion efficient, we need to calculate the dominance frontier

for each node in the flow graph. We could formulate a data-flow problem to

compute df(n) for each n in the graph. Using both the dominator tree and the

cfg, we can formulate a simple and direct algorithm, shown in Figure 9.8.

Since only nodes that are join points in the cfg can be members of a dominance

frontier, we first identify all of the join points in the graph. For a join

point j, we examine each of its cfg predecessors.

The algorithm is based on three observations. First, nodes in a df set must

be join points in the graph. Second, for a join point j, each predecessor k

of j must have j 2 df(k), since k cannot dominate j if j has more than one

predecessor. Finally, if j 2 df(k) for some predecessor k, then j must also be

in df(l) for each l 2 Dom(k), unless l 2 Dom( j).

The algorithm follows these observations. It locates nodes j that are join

points in the cfg. Then, for each predecessor p of j, it walks up the dominator

tree from p until it finds a node that dominates j. From the second and third

observations in the preceding paragraph, j belongs in df(l) for each node l

that the algorithm traverses in this dominator-tree walk, except for the final

node in the walk, since that node dominates j. A small amount of bookkeeping

is needed to ensure that any n is added to a node’s dominance frontier

only once.

To see how this works, consider again the example cfg and its dominance

tree. The analyzer examines the nodes in some order, looking for nodes with

multiple predecessors. Assuming that it takes the nodes in name order, it

finds the join points as B1, then B3, then B7.

1. B1 For cfg-predecessor B0, the algorithm finds that B0 is IDom(B1), so

it never enters the while loop. For cfg-predecessor B3, it adds B1

to df(B3) and advances to B1. It adds B1 to df(B1) and advances to B0,

where it halts.

2. B3 For cfg-predecessor B2, it adds B3 to df(B2), advances to B1 which

is IDom(B3), and halts. For cfg-predecessor B7, it adds B3 to df(B7)

and advances to B5. It adds B3 to df(B5) and advances to B1, where it

halts.

3. B7 For cfg-predecessor B6, it adds B7 to df(B6), advances to B5 which

is IDom(B7), and halts. For cfg-predecessor B8, it adds B7 to df(B8)

and advances to B5, where it halts.

Accumulating these results, we obtain the following dominance frontiers:

B0 B1 B2 B3 B4 B5 B6 B7 B8

DF ; fB1g fB3g fB1g ; fB3g fB7g fB3g fB7g

9.3.3 Placing _-Functions

The naive

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций