Проверка доминирования

Определение SSA, взятое за основу при разработке дерева операций, позволяет говорить о свойстве доминирования. По отношению к языку программирования свойство означает, что каждое использование переменной не предшествует точке ее определения. По существу, это значит, что каждая переменная объявлена до использования, а также не используется вне ее области видимости.

В теории графов доминированием называется бинарное отношение на узлах ориентированного графа с определенным входным узлом, показывающее преимущество при прохождении пути от входного узла r. Говорят, что узел графа p доминирует узел графа q (или p является доминатором для q), если любой путь от r до q проходит через p. Каждый узел графа доминирует сам себя. Кроме того, можно ввести определение строгого доминирования, совпадающее с приведенным определением за исключением того, что каждый узел графа не будет являться строгим доминатором для самого себя.

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

Дерево доминаторов представлено соответствующим классом с методами, позволяющими выполнять описанные проверки.

struct DominanceTree {
    DominanceTree() = delete;
    explicit DominanceTree(const Operation::Ptr &rootOp);

    bool dominates(const Operation::Ptr &dominator, const Operation::Ptr &dominated) const;
    bool properlyDominates(const Operation::Ptr &dominator, const Operation::Ptr &dominated) const;

  private:
    struct Node {
        Node *parent = nullptr;
    };
    Node *root;
    std::unordered_map<const Operation *, const Node *> traversedOps;

    // ...
};

Для построения дерева доминаторов выполняется рекурсивный обход дерева операций, начиная от корня. Первая вложенная операция становится потомком операции, ее объемлющей, а каждая последующая операция становится потомком предыдущей. Исключение составляют операции ModuleOp (вложенные в нее операции FunctionOp равноправны, и она становится их общим предком), IfOp (аналогично, операции ThenOp и ElseOp не доминируют друг друга) и ConditionOp (эта операция не доминирует следующую за ней). При обходе также сохраняется соответствие узлов дерева операций узлам дерева доминаторов.

В дальнейшем, во время семантического анализа дерева операций, проверка свойства доминирования выполняется следующим образом:

  1. Для указанного дерева операций строится дерево доминаторов.

  2. Для каждой операции Def проверяется следующее утверждение: верно ли, что каждая из операций Use, имеющая результат операции Def в качестве операнда, строго доминирует Def.

  3. Аналогичное утверждение проверяется для внутренних регистров каждой операции в дереве.

Если во всех случаях утверждение верно, то дерево операций считается корректным с точки зрения свойства доминирования. В противном случае дерево не может быть использовано для дальнейших трансформаций.

Назад