oPtIMizaTiOn

// Without recursion, wrong
void GraphInfo::dfs(UtilNode &startNode) {
    /* Second element in pair is false -- if current node is a target to visit
     * and false -- if it is a mark from already visited node, means that
     * all subrees of this node are already visited
     */
    std::stack<std::pair<UtilNode*, bool>> stack;
    stack.push({ &startNode, false });
    std::set<int> visited;

    while (!stack.empty()) {
        UtilNode &node = *stack.top().first;
        bool isCompletion = stack.top().second;
        stack.pop();

        if (isCompletion) {
            node.timeOut = globalTime++;
            continue;
        }

        if (visited.contains(node.id))
            continue;
        visited.insert(node.id);

        funBlocksIds.push_back(node.id);
        node.timeIn = globalTime++;
        stack.push({ &node, true });

        IR_Block &block = cfg->block(node.id);
        for (int nextId : block.next) {
            auto it = utilNodes.lower_bound(nextId);
            if (it == utilNodes.end() || it->first != nextId) {
                arcsClasses.emplace(std::make_pair(node.id, nextId), GraphInfo::TREE);

                auto &domNode = domData.emplace(nextId, DomNode()).first->second;
                auto &newNode = utilNodes.emplace_hint(it, nextId, UtilNode(nextId, &domNode))->second;

                newNode.parent = &node;
                stack.push({ &newNode, false });
            }
            else {
                unprocArcs.push_back(std::make_pair(&node, &it->second));

                if (!visited.contains(it->second.parent->id)) {
                    it->second.parent = &node;
                    // TODO: Relink TREE arc...
                    stack.push({ &it->second, false });
                }
            }
        }
    }
}


// With recursion, correct
void GraphInfo::dfs(UtilNode &node) {
    funBlocksIds.push_back(node.id);
    node.timeIn = globalTime++;

    IR_Block &block = cfg->block(node.id);
    for (int nextId : block.next) {
        auto it = utilNodes.lower_bound(nextId);
        if (it == utilNodes.end() || it->first != nextId) {
            arcsClasses.emplace(std::make_pair(node.id, nextId), GraphInfo::TREE);

            auto &domNode = domData.emplace(nextId, DomNode()).first->second;
            auto &newNode = utilNodes.emplace_hint(it, nextId, UtilNode(nextId, &domNode))->second;

            newNode.parent = &node;
            dfs(newNode);
        }
        else {
            unprocArcs.push_back(std::make_pair(&node, &it->second));
        }
    }
    node.timeOut = globalTime++;
}