Граница доминирования

9.3.2 Границы доминирования

Основной недостаток максимальной SSA-формы – она содержит слишком много -функций. Чтобы уменьшить их количество, компилятор должен более тщательно определять места, где они необходимы. При размещении -функций основная проблема состоит в том, чтобы понять для каждой точки сбора, какие переменные требуют -функцию в этой точке. Чтобы эффективно и результативно решить эту проблему компилятор может поставить ее по-другому: для каждого базового блока B_i определить множество базовых блоков, в которых будет необходима -функция для любого определения переменной в блоке B_i. В таком расчете основную роль играет доминирование.

Рассмотрим определение в узле ГПУ n. Оно потенциально может достичь каждого узла m, для которого
n  Dom(m), не требуя -функций, так как каждый путь, достигающий m, проходит через n. Единственный вариант, при котором значение не достигает m, это когда есть еще одно определение с тем же именем в некотором узле p, расположенном между n и m. В этом случае определение в n не требует -функции, но ее требует определение в p.

Определение в узле n требует помещать -функции во все точки сбора, которые лежат непосредственно за границей области ГПУ, над которой доминирует n. Более формально определение в узле n требует помещать -функции в каждую точку сбора m, для которой:

(1) n доминирует над предшественниками m (q  Pred(m) & n  Dom(q));

(2) n не является строгим доминатором m (n  Dom(m) – {m}). (Использование строгого доминирования вместо доминирования позволяет помещать -функции в начало цикла, состоящего из одного блока: в этом случае m = n и
m  Dom(n) – {n}).

Множество узлов, удовлетворяющих условиям (1) и (2) называется границей доминирования узла n и обозначается DF(n).

Неформально, df(n) содержит ближайшие к n узлы, достижимые из n, над которыми n не доминирует. В примере, ГПУ которого приведен на рисунке, блок B5 доминирует над B6, B7, и B8, но не доминирует над B3, причем B3 – первый узел, на путях из B3

Informally, 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,

. 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 introDominator

tree duce one further notion, the dominator tree. Given a node n in a flow graph,

a tree that encodes the dominance information

for a flow graph

the set

STATIC ANALYSIS VERSUS DYNAMIC ANALYSIS

The notion of static analysis leads directly to the question, What about

dynamic analysis? By definition, static analysis tries to estimate, at compile

time, what will happen at runtime. In many situations, the compiler cannot

tell what will happen, even though the answer might be obvious with

knowledge of one or more runtime values.

Consider, for example, the C fragment

x = y * z + 12;

*p = 0;

q = y * z + 13;

It contains a redundant expression, y * z, if and only if p does not contain

the address of either y or z. At compile time, the value of p and the

address of y and z may be unknown. At runtime, they are known and

can be tested. Testing these values at runtime would allow the code to

avoid recomputing y * z, where compile-time analysis might be unable to

answer the question.

However, the cost of testing whether p == &y or p == &z or neither and

acting on the result is likely to exceed the cost of recomputing y * z. For

dynamic analysis to make sense, it must be a priori profitable—that is,

the savings must exceed the cost of the analysis. This happens in some

cases; in most cases, it does not. In contrast, the cost of static analysis

can be amortized over multiple runs of the executable code, so it is more

attractive, in general.