SAPFOR

Table of Contents

Введение
Алгоритм обхода графа.
Анализ отдельной вершины (doStep)
Пример

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

Так очень часто задачи, связанные с IR, являются в том или ином виде задачей анализа потока данных (Wikipedia), было принято решение выделить код обхода ГПУ (CFG) таким образом, чтобы его можно было переиспользовать. Эта станица посвящена тому, как его использовать.

Введение

Исходные файлы находятся в папке CFGraph/DataFlow. На вершине иерархии находится абстрактный класс DataFlowAnalysis<NodeType>. Предполагается, что для каждого анализа будет создаваться наследник (не обязательно непосредственный) и из него будет создаваться (чаще всего один) объект, назовём его объектом анализа. После этого в объект будет загружаться ГПУ, представленный массивом из SAPFOR::BasicBlock* вызовом функции fit и запускаться анализ вызовом функции analyze.

Теперь подробнее о NodeType. Предполагается, что для каждого анализа также будет создаваться наследник класса DataFlowAnalysisNode<DataType>, который будет представлять собой обёртку над SAPFOR::BasicBlock*. DataType - это тип тех самых данных, которые предполагается распространять по графу. Единственное ограничение - должна быть итерируемая коллекция. Чаще всего этот тип должен совпадать с типом множеств IN и OUT поставленной задачи потока данных. Этот класс должен реализовывать 5 функций:

DataType getIn() (пока что это неиспользуемая функция)
DataType getOut()
bool addIn(const DataType& data)
bool addOut(const DataType& data) (пока что это неиспользуемая функция)
bool forwardData(const DataType& data)

Первые две функции должны возвращать для данной вершины множества IN и OUT соответственно (чаще всего это просто геттеры).

Вторые две функции должны добавлять в множества IN и OUT соотвественно текущей вершины переданные данные и возвращать true, если новый элемент был добавлен. Предполагается, что это "добавление" эквивалентно dest := data U dest, где dest - IN и OUT соотвественно, U - оператор сбора.

Последняя функция должна выполнять обновление множества OUT по подмножеству множества IN. Предполагается, что реализация этой функции совпадает с передаточной функцией (transfer function, см статью из вики в заголовке).

Алгоритм обхода графа.

Выполнение требуемого анализа начинается с вызова функции DataFlowAnalysis<NodeType>::analyze(). В ней выполняется последовательный проход по вектору nodes (то есть от первого его элемента к последнему). Для очередного элемента вектора (назовём его node = nodes[i]) вызывается функция DataFlowAnalysisNode<DataType>::doStep() (о ней будет рассказано далее). Потом для node выбирается случайная дуга R из Rollback \ IgnoreRollback (Rollback - множество обратных дуг для данной задачи, то есть дуга, переход по которой повлечёт переход в вершину, которая в массиве вершин имеет меньший индекс (на самом деле меньший или равный), чем текущая; IgnoreRollback - подмножество множества Rollback, изначально пусто). После этого R помещается в node->IgnoreRollback и производится переход по R (в этом случае производится переход в какую-то предыдущую вершину) (На самом деле этот откат производится только если данные текущего блога строго более "свежие", иначе R попадает в IgnoreRollback и выбирается другое R). Если Rollback \ IgnoreRollback пусто, то выполняется переход к следующей за node в nodes вершиной (к nodes[i+1]). Алгоритм завершается, когда весь массив пройден.

Анализ отдельной вершины (doStep)

Начинается всё с того, что каждой вершине приписывается два счётчика: cnt_in = cnt_out = 0. Данные блока A более свежие чем данные блока B, если A->cnt_out > B->cnt_in. A->doStep() перебирает все блоки B такие, что блок B имеет более свежие данные чем A, то есть B->cnt_out > A->cnt_in. Для каждого такого блока B он обновляет множество A->IN данными из B->OUT через A->addIn(B->getOut()). И для тех данных, которые действительно обновили A->IN он вызывает A->forwardData(). (На самом деле берётся не вся коллекция B->getOut() сразу целиком, а каждый её элемент сначала попадает в addIn, а затем, если addIn возвращает true, попадает в forwardData). При этом в cnt_in (cnt_out) попадает максимальное значение счётчика cnt_out среди блоков, которые добавили в множество IN (при помощи addIn) хоть один новый элемент (соответственно добавили в OUT при помощи forwardData хоть один новый элемент). Если данная вершина вызывает doStep впервые, то в конце [к cnt_in и cnt_out прибавляем по 1][TODO: это не правильно, нужно потом исправить в коде и здесь] чтобы обозначить, что в OUT этой вершины есть данные, которые появляются изначально при создании вершины и которые нужно распространить в остальные вершины.

Теперь осталось только решить задачу с заполнением nodes. Эту задачу берёт на себя метод fit(). Реализация этого метода отличается в случаях, когда рассматривается задача прямого и обратного анализа потока данных. До этого повествование шло так, будто мы рассматриваем задачу прямого обхода. Поэтому в случае прямого обхода nodes заполняется естественно в топологическом порядке, то есть так, чтобы выполнялось соотношение, что для любых i < j дуги из nodes[i] в nodes[j] либо нет, либо это обратная дуга графа потока управления (см функцию sortCfgNodes). Для каждой созданной вершины node нужно заполнить:

rollback - множество i таких что есть обратная дуга node -> nodes[i]
prev_blocks - множество всех вершин, из которых в node могут попасть данные (для задачи прямого обхода - это nodes[i] такие что есть дуга nodes[i] -> nodes; для задачи обратного прохода - это nodes[i]: есть дуга node -> nodes[i]).
bb - соответствующий базовый блок.

На самом деле реализация fit для задач прямого и обратного обхода почти одинаковая, потому что обратная задача отличается только тем, что массив nodes развёрнут и prev_blocks другой. При этом IN DataFlowAnalysisNode соответствует OUT для базового блока и наоборот OUT DataFlowAnalysisNode соответствует IN базового блока. Поэтому для DataFlowAnalysis определены классы BackwardDataFlowAnalysis и ForwardDataFlowAnalysis (TODO: ForwardDataFlowAnalysis ещё не определён).

На практике требуется при создании экземпляра наследника DataFlowAnalysisNode передавать в конструктор какие-то аргументы кроме базового блока, поэтому в fit при создании объекта наследника DataFlowAnalysisNode используется виртуальная функция createNode, которая должна быть реализована в конечном наследнике и выполнять создание объекта типа NodeType. Чаще всего это просто вызов конструктора NodeType с аргументами BasicBlock* и аргументами-полями класса.

Итак, если подвести итог, то для создания анализа достаточно:

Унаследоваться от DataFlowAnalysisNode и реализовать в нём необходимые функции (+ скорее всего понадобится конструктор) (назовём этот класс NodeImpl)
Унаследоваться от BackwardDataFlowAnalysis<NodeImpl> или ForwardDataFlowAnalysis<NodeImpl> и реализовать в нём createNode (+ скорее всего понадобится конструктор) (назовём этот класс DataFlowImpl)
создать объект DataFlowImpl analysis_object
загрузить в него ГПУ: analysis_object.fit(CFG)
запустить анализ: analysis_object.analyze()
опционально результаты анализа можно помещать в NodeImpl и потом проитерировать по всем вершинам с помощью analysis_object.getNodes()

Пример

Анализ живых переменных (задача обратного обхода) (см файл CFGraph/live_variable_analysis.cpp)

class LiveVarAnalysisNode : public DataFlowAnalysisNode<map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>>> {
private:
    set<SAPFOR::Argument*> live, dead;
public:
    map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>> getIn() { return getBlock()->getLiveOut(); };

    map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>> getOut() { return getBlock()->getLiveIn(); };

    bool addIn(const map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>>& data) { return getBlock()->addLiveOut(data); };

    bool addOut(const map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>>& data) { return getBlock()->addLiveIn(data); };

    bool forwardData(const map<SAPFOR::Argument*, vector<SAPFOR::BasicBlock*>>& data)
    {
        bool inserted = false;

        for (const auto& byArg : data)
            if (live.find(byArg.first) == live.end() && dead.find(byArg.first) == dead.end())
                inserted |= getBlock()->addLiveIn({ byArg });

        return inserted;
    };

    LiveVarAnalysisNode(SAPFOR::BasicBlock* block, vector<SAPFOR::Argument*>& formal_parameters,
                        vector<LiveDeadVarsForCall>& fcalls, const map<string, FuncInfo*>& funcByName)
    {
        setBlock(block);

        buildUseDef(getBlock(), live, dead, formal_parameters, fcalls, funcByName, true);

        for (SAPFOR::Argument* arg : live)
            getBlock()->addLiveIn({ { arg, { getBlock() } } });
    }
};

class LiveVarAnalysis : public BackwardDataFlowAnalysis<LiveVarAnalysisNode> {
protected:
    vector<SAPFOR::Argument*>& formal_parameters;
    vector<LiveDeadVarsForCall>& fcalls;
    const map<string, FuncInfo*>& funcByName;

    LiveVarAnalysisNode* createNode(SAPFOR::BasicBlock* block) override {
        return new LiveVarAnalysisNode(block, formal_parameters, fcalls, funcByName);
    };
public:
    LiveVarAnalysis(vector<SAPFOR::Argument*>& formal_parameters, vector<LiveDeadVarsForCall>& fcalls,
        const map<string, FuncInfo*>& funcByName) : formal_parameters(formal_parameters), fcalls(fcalls), funcByName(funcByName)
    { };
};

LiveVarAnalysis* analysis_object = new LiveVarAnalysis(params, curr_fcalls, funcByName);
analysis_object->fit(itCFG->second);
analysis_object->analyze();

Надеюсь, это кому-нибудь поможет, c вопросами и предложениями можно обращаться к @xnpster.