src/compiler/depgraph/DependencyGraphBuilder.cpp

//
// Copyright (c) 2012 The ANGLE Project Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//

#include "compiler/depgraph/DependencyGraphBuilder.h"

TDependencyGraphBuilder::TLeftmostSymbolMaintainer::TSubtreePlaceholder
    TDependencyGraphBuilder::TLeftmostSymbolMaintainer::kLeftSubtree;

TDependencyGraphBuilder::TLeftmostSymbolMaintainer::TSubtreePlaceholder
    TDependencyGraphBuilder::TLeftmostSymbolMaintainer::kRightSubtree;

void TDependencyGraphBuilder::build(TIntermNode* node, TDependencyGraph* graph)
{
    TDependencyGraphBuilder builder(graph);
    builder.build(node);
}

bool TDependencyGraphBuilder::visitAggregate(Visit visit, TIntermAggregate* intermAggregate)
{
    switch (intermAggregate->getOp()) {
        case EOpFunction: visitFunctionDefinition(intermAggregate); break;
        case EOpFunctionCall: visitFunctionCall(intermAggregate); break;
        default: visitAggregateChildren(intermAggregate); break;
    }

    return false;
}

void TDependencyGraphBuilder::visitFunctionDefinition(TIntermAggregate* intermAggregate)
{
    // Function defintions should only exist in the global scope.
    ASSERT(mIsGlobalScope);

    // Currently, we do not support user defined functions.
    if (intermAggregate->getName() != "main(")
        return;

    mIsGlobalScope = false;

    visitAggregateChildren(intermAggregate);

    mIsGlobalScope = true;
}

// Takes an expression like "f(x)" and creates a dependency graph like
// "x -> argument 0 -> function call".
void TDependencyGraphBuilder::visitFunctionCall(TIntermAggregate* intermFunctionCall)
{
    TGraphFunctionCall* functionCall = mGraph->createFunctionCall(intermFunctionCall);

    // Run through the function call arguments.
    int argumentNumber = 0;
    TIntermSequence& intermArguments = intermFunctionCall->getSequence();
    for (TIntermSequence::const_iterator iter = intermArguments.begin();
         iter != intermArguments.end();
         ++iter, ++argumentNumber)
    {
        TNodeSetMaintainer nodeSetMaintainer(this);

        TIntermNode* intermArgument = *iter;
        intermArgument->traverse(this);

        if (TParentNodeSet* argumentNodes = mNodeSets.getTopSet()) {
            TGraphArgument* argument = mGraph->createArgument(intermFunctionCall, argumentNumber);
            connectMultipleNodesToSingleNode(argumentNodes, argument);
            argument->addDependentNode(functionCall);
        }
    }

    // Push the leftmost symbol of this function call into the current set of dependent symbols to
    // represent the result of this function call.
    // Thus, an expression like "y = f(x)" will yield a dependency graph like
    // "x -> argument 0 -> function call -> y".
    // This line essentially passes the function call node back up to an earlier visitAssignment
    // call, which will create the connection "function call -> y".
    mNodeSets.insertIntoTopSet(functionCall);
}

void TDependencyGraphBuilder::visitAggregateChildren(TIntermAggregate* intermAggregate)
{
    TIntermSequence& sequence = intermAggregate->getSequence();
    for(TIntermSequence::const_iterator iter = sequence.begin(); iter != sequence.end(); ++iter)
    {
        TIntermNode* intermChild = *iter;
        intermChild->traverse(this);
    }
}

void TDependencyGraphBuilder::visitSymbol(TIntermSymbol* intermSymbol)
{
    // Push this symbol into the set of dependent symbols for the current assignment or condition
    // that we are traversing.
    TGraphSymbol* symbol = mGraph->getOrCreateSymbol(intermSymbol, mIsGlobalScope);
    mNodeSets.insertIntoTopSet(symbol);

    // If this symbol is the current leftmost symbol under an assignment, replace the previous
    // leftmost symbol with this symbol.
    if (!mLeftmostSymbols.empty() && mLeftmostSymbols.top() !=
        &TLeftmostSymbolMaintainer::kRightSubtree) {
        mLeftmostSymbols.pop();
        mLeftmostSymbols.push(symbol);
    }
}

bool TDependencyGraphBuilder::visitBinary(Visit visit, TIntermBinary* intermBinary)
{
    TOperator op = intermBinary->getOp();
    if (op == EOpInitialize || intermBinary->modifiesState())
        visitAssignment(intermBinary);
    else if (op == EOpLogicalAnd || op == EOpLogicalOr)
        visitLogicalOp(intermBinary);
    else
        visitBinaryChildren(intermBinary);

    return false;
}

void TDependencyGraphBuilder::visitAssignment(TIntermBinary* intermAssignment)
{
    TIntermTyped* intermLeft = intermAssignment->getLeft();
    if (!intermLeft)
        return;

    TGraphSymbol* leftmostSymbol = NULL;

    {
        TNodeSetMaintainer nodeSetMaintainer(this);

        {
            TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kLeftSubtree);
            intermLeft->traverse(this);
            leftmostSymbol = mLeftmostSymbols.top();

            // After traversing the left subtree of this assignment, we should have found a real
            // leftmost symbol, and the leftmost symbol should not be a placeholder.
            ASSERT(leftmostSymbol != &TLeftmostSymbolMaintainer::kLeftSubtree);
            ASSERT(leftmostSymbol != &TLeftmostSymbolMaintainer::kRightSubtree);
        }

        if (TIntermTyped* intermRight = intermAssignment->getRight()) {
            TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
            intermRight->traverse(this);
        }

        if (TParentNodeSet* assignmentNodes = mNodeSets.getTopSet())
            connectMultipleNodesToSingleNode(assignmentNodes, leftmostSymbol);
    }

    // Push the leftmost symbol of this assignment into the current set of dependent symbols to
    // represent the result of this assignment.
    // An expression like "a = (b = c)" will yield a dependency graph like "c -> b -> a".
    // This line essentially passes the leftmost symbol of the nested assignment ("b" in this
    // example) back up to the earlier visitAssignment call for the outer assignment, which will
    // create the connection "b -> a".
    mNodeSets.insertIntoTopSet(leftmostSymbol);
}

void TDependencyGraphBuilder::visitLogicalOp(TIntermBinary* intermLogicalOp)
{
    if (TIntermTyped* intermLeft = intermLogicalOp->getLeft()) {
        TNodeSetPropagatingMaintainer nodeSetMaintainer(this);

        intermLeft->traverse(this);
        if (TParentNodeSet* leftNodes = mNodeSets.getTopSet()) {
            TGraphLogicalOp* logicalOp = mGraph->createLogicalOp(intermLogicalOp);
            connectMultipleNodesToSingleNode(leftNodes, logicalOp);
        }
    }

    if (TIntermTyped* intermRight = intermLogicalOp->getRight()) {
        TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
        intermRight->traverse(this);
    }
}

void TDependencyGraphBuilder::visitBinaryChildren(TIntermBinary* intermBinary)
{
    if (TIntermTyped* intermLeft = intermBinary->getLeft())
        intermLeft->traverse(this);

    if (TIntermTyped* intermRight = intermBinary->getRight()) {
        TLeftmostSymbolMaintainer leftmostSymbolMaintainer(this, TLeftmostSymbolMaintainer::kRightSubtree);
        intermRight->traverse(this);
    }
}

bool TDependencyGraphBuilder::visitSelection(Visit visit, TIntermSelection* intermSelection)
{
    if (TIntermNode* intermCondition = intermSelection->getCondition()) {
        TNodeSetMaintainer nodeSetMaintainer(this);

        intermCondition->traverse(this);
        if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
            TGraphSelection* selection = mGraph->createSelection(intermSelection);
            connectMultipleNodesToSingleNode(conditionNodes, selection);
        }
    }

    if (TIntermNode* intermTrueBlock = intermSelection->getTrueBlock())
        intermTrueBlock->traverse(this);

    if (TIntermNode* intermFalseBlock = intermSelection->getFalseBlock())
        intermFalseBlock->traverse(this);

    return false;
}

bool TDependencyGraphBuilder::visitLoop(Visit visit, TIntermLoop* intermLoop)
{
    if (TIntermTyped* intermCondition = intermLoop->getCondition()) {
        TNodeSetMaintainer nodeSetMaintainer(this);

        intermCondition->traverse(this);
        if (TParentNodeSet* conditionNodes = mNodeSets.getTopSet()) {
            TGraphLoop* loop = mGraph->createLoop(intermLoop);
            connectMultipleNodesToSingleNode(conditionNodes, loop);
        }
    }

    if (TIntermNode* intermBody = intermLoop->getBody())
        intermBody->traverse(this);

    if (TIntermTyped* intermExpression = intermLoop->getExpression())
        intermExpression->traverse(this);

    return false;
}


void TDependencyGraphBuilder::connectMultipleNodesToSingleNode(TParentNodeSet* nodes,
                                                               TGraphNode* node) const
{
    for (TParentNodeSet::const_iterator iter = nodes->begin(); iter != nodes->end(); ++iter)
    {
        TGraphParentNode* currentNode = *iter;
        currentNode->addDependentNode(node);
    }
}