Source code
Revision control
Copy as Markdown
Other Tools
//
// Copyright 2002 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.
//
// Analysis of the AST needed for HLSL generation
#include "compiler/translator/ASTMetadataHLSL.h"
#include "compiler/translator/CallDAG.h"
#include "compiler/translator/SymbolTable.h"
#include "compiler/translator/tree_util/IntermTraverse.h"
namespace sh
{
namespace
{
// Class used to traverse the AST of a function definition, checking if the
// function uses a gradient, and writing the set of control flow using gradients.
// It assumes that the analysis has already been made for the function's
// callees.
class PullGradient : public TIntermTraverser
{
public:
PullGradient(MetadataList *metadataList, size_t index, const CallDAG &dag)
: TIntermTraverser(true, false, true),
mMetadataList(metadataList),
mMetadata(&(*metadataList)[index]),
mIndex(index),
mDag(dag)
{
ASSERT(index < metadataList->size());
// ESSL 100 builtin gradient functions
mGradientBuiltinFunctions.insert(ImmutableString("texture2D"));
mGradientBuiltinFunctions.insert(ImmutableString("texture2DProj"));
mGradientBuiltinFunctions.insert(ImmutableString("textureCube"));
// ESSL 300 builtin gradient functions
mGradientBuiltinFunctions.insert(ImmutableString("dFdx"));
mGradientBuiltinFunctions.insert(ImmutableString("dFdy"));
mGradientBuiltinFunctions.insert(ImmutableString("fwidth"));
mGradientBuiltinFunctions.insert(ImmutableString("texture"));
mGradientBuiltinFunctions.insert(ImmutableString("textureProj"));
mGradientBuiltinFunctions.insert(ImmutableString("textureOffset"));
mGradientBuiltinFunctions.insert(ImmutableString("textureProjOffset"));
// ESSL 310 doesn't add builtin gradient functions
}
void traverse(TIntermFunctionDefinition *node)
{
node->traverse(this);
ASSERT(mParents.empty());
}
// Called when a gradient operation or a call to a function using a gradient is found.
void onGradient()
{
mMetadata->mUsesGradient = true;
// Mark the latest control flow as using a gradient.
if (!mParents.empty())
{
mMetadata->mControlFlowsContainingGradient.insert(mParents.back());
}
}
void visitControlFlow(Visit visit, TIntermNode *node)
{
if (visit == PreVisit)
{
mParents.push_back(node);
}
else if (visit == PostVisit)
{
ASSERT(mParents.back() == node);
mParents.pop_back();
// A control flow's using a gradient means its parents are too.
if (mMetadata->mControlFlowsContainingGradient.count(node) > 0 && !mParents.empty())
{
mMetadata->mControlFlowsContainingGradient.insert(mParents.back());
}
}
}
bool visitLoop(Visit visit, TIntermLoop *loop) override
{
visitControlFlow(visit, loop);
return true;
}
bool visitIfElse(Visit visit, TIntermIfElse *ifElse) override
{
visitControlFlow(visit, ifElse);
return true;
}
bool visitAggregate(Visit visit, TIntermAggregate *node) override
{
if (visit == PreVisit)
{
if (node->getOp() == EOpCallFunctionInAST)
{
size_t calleeIndex = mDag.findIndex(node->getFunction()->uniqueId());
ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
if ((*mMetadataList)[calleeIndex].mUsesGradient)
{
onGradient();
}
}
else if (BuiltInGroup::IsBuiltIn(node->getOp()) && !BuiltInGroup::IsMath(node->getOp()))
{
if (mGradientBuiltinFunctions.find(node->getFunction()->name()) !=
mGradientBuiltinFunctions.end())
{
onGradient();
}
}
}
return true;
}
private:
MetadataList *mMetadataList;
ASTMetadataHLSL *mMetadata;
size_t mIndex;
const CallDAG &mDag;
// Contains a stack of the control flow nodes that are parents of the node being
// currently visited. It is used to mark control flows using a gradient.
std::vector<TIntermNode *> mParents;
// A list of builtin functions that use gradients
std::set<ImmutableString> mGradientBuiltinFunctions;
};
// Traverses the AST of a function definition to compute the the discontinuous loops
// and the if statements containing gradient loops. It assumes that the gradient loops
// (loops that contain a gradient) have already been computed and that it has already
// traversed the current function's callees.
class PullComputeDiscontinuousAndGradientLoops : public TIntermTraverser
{
public:
PullComputeDiscontinuousAndGradientLoops(MetadataList *metadataList,
size_t index,
const CallDAG &dag)
: TIntermTraverser(true, false, true),
mMetadataList(metadataList),
mMetadata(&(*metadataList)[index]),
mIndex(index),
mDag(dag)
{}
void traverse(TIntermFunctionDefinition *node)
{
node->traverse(this);
ASSERT(mLoopsAndSwitches.empty());
ASSERT(mIfs.empty());
}
// Called when traversing a gradient loop or a call to a function with a
// gradient loop in its call graph.
void onGradientLoop()
{
mMetadata->mHasGradientLoopInCallGraph = true;
// Mark the latest if as using a discontinuous loop.
if (!mIfs.empty())
{
mMetadata->mIfsContainingGradientLoop.insert(mIfs.back());
}
}
bool visitLoop(Visit visit, TIntermLoop *loop) override
{
if (visit == PreVisit)
{
mLoopsAndSwitches.push_back(loop);
if (mMetadata->hasGradientInCallGraph(loop))
{
onGradientLoop();
}
}
else if (visit == PostVisit)
{
ASSERT(mLoopsAndSwitches.back() == loop);
mLoopsAndSwitches.pop_back();
}
return true;
}
bool visitIfElse(Visit visit, TIntermIfElse *node) override
{
if (visit == PreVisit)
{
mIfs.push_back(node);
}
else if (visit == PostVisit)
{
ASSERT(mIfs.back() == node);
mIfs.pop_back();
// An if using a discontinuous loop means its parents ifs are also discontinuous.
if (mMetadata->mIfsContainingGradientLoop.count(node) > 0 && !mIfs.empty())
{
mMetadata->mIfsContainingGradientLoop.insert(mIfs.back());
}
}
return true;
}
bool visitBranch(Visit visit, TIntermBranch *node) override
{
if (visit == PreVisit)
{
switch (node->getFlowOp())
{
case EOpBreak:
{
ASSERT(!mLoopsAndSwitches.empty());
TIntermLoop *loop = mLoopsAndSwitches.back()->getAsLoopNode();
if (loop != nullptr)
{
mMetadata->mDiscontinuousLoops.insert(loop);
}
}
break;
case EOpContinue:
{
ASSERT(!mLoopsAndSwitches.empty());
TIntermLoop *loop = nullptr;
size_t i = mLoopsAndSwitches.size();
while (loop == nullptr && i > 0)
{
--i;
loop = mLoopsAndSwitches.at(i)->getAsLoopNode();
}
ASSERT(loop != nullptr);
mMetadata->mDiscontinuousLoops.insert(loop);
}
break;
case EOpKill:
case EOpReturn:
// A return or discard jumps out of all the enclosing loops
if (!mLoopsAndSwitches.empty())
{
for (TIntermNode *intermNode : mLoopsAndSwitches)
{
TIntermLoop *loop = intermNode->getAsLoopNode();
if (loop)
{
mMetadata->mDiscontinuousLoops.insert(loop);
}
}
}
break;
default:
UNREACHABLE();
}
}
return true;
}
bool visitAggregate(Visit visit, TIntermAggregate *node) override
{
if (visit == PreVisit && node->getOp() == EOpCallFunctionInAST)
{
size_t calleeIndex = mDag.findIndex(node->getFunction()->uniqueId());
ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
if ((*mMetadataList)[calleeIndex].mHasGradientLoopInCallGraph)
{
onGradientLoop();
}
}
return true;
}
bool visitSwitch(Visit visit, TIntermSwitch *node) override
{
if (visit == PreVisit)
{
mLoopsAndSwitches.push_back(node);
}
else if (visit == PostVisit)
{
ASSERT(mLoopsAndSwitches.back() == node);
mLoopsAndSwitches.pop_back();
}
return true;
}
private:
MetadataList *mMetadataList;
ASTMetadataHLSL *mMetadata;
size_t mIndex;
const CallDAG &mDag;
std::vector<TIntermNode *> mLoopsAndSwitches;
std::vector<TIntermIfElse *> mIfs;
};
// Tags all the functions called in a discontinuous loop
class PushDiscontinuousLoops : public TIntermTraverser
{
public:
PushDiscontinuousLoops(MetadataList *metadataList, size_t index, const CallDAG &dag)
: TIntermTraverser(true, true, true),
mMetadataList(metadataList),
mMetadata(&(*metadataList)[index]),
mIndex(index),
mDag(dag),
mNestedDiscont(mMetadata->mCalledInDiscontinuousLoop ? 1 : 0)
{}
void traverse(TIntermFunctionDefinition *node)
{
node->traverse(this);
ASSERT(mNestedDiscont == (mMetadata->mCalledInDiscontinuousLoop ? 1 : 0));
}
bool visitLoop(Visit visit, TIntermLoop *loop) override
{
bool isDiscontinuous = mMetadata->mDiscontinuousLoops.count(loop) > 0;
if (visit == PreVisit && isDiscontinuous)
{
mNestedDiscont++;
}
else if (visit == PostVisit && isDiscontinuous)
{
mNestedDiscont--;
}
return true;
}
bool visitAggregate(Visit visit, TIntermAggregate *node) override
{
switch (node->getOp())
{
case EOpCallFunctionInAST:
if (visit == PreVisit && mNestedDiscont > 0)
{
size_t calleeIndex = mDag.findIndex(node->getFunction()->uniqueId());
ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
(*mMetadataList)[calleeIndex].mCalledInDiscontinuousLoop = true;
}
break;
default:
break;
}
return true;
}
private:
MetadataList *mMetadataList;
ASTMetadataHLSL *mMetadata;
size_t mIndex;
const CallDAG &mDag;
int mNestedDiscont;
};
} // namespace
bool ASTMetadataHLSL::hasGradientInCallGraph(TIntermLoop *node)
{
return mControlFlowsContainingGradient.count(node) > 0;
}
bool ASTMetadataHLSL::hasGradientLoop(TIntermIfElse *node)
{
return mIfsContainingGradientLoop.count(node) > 0;
}
MetadataList CreateASTMetadataHLSL(TIntermNode *root, const CallDAG &callDag)
{
MetadataList metadataList(callDag.size());
// Compute all the information related to when gradient operations are used.
// We want to know for each function and control flow operation if they have
// a gradient operation in their call graph (shortened to "using a gradient"
// in the rest of the file).
//
// This computation is logically split in three steps:
// 1 - For each function compute if it uses a gradient in its body, ignoring
// calls to other user-defined functions.
// 2 - For each function determine if it uses a gradient in its call graph,
// using the result of step 1 and the CallDAG to know its callees.
// 3 - For each control flow statement of each function, check if it uses a
// gradient in the function's body, or if it calls a user-defined function that
// uses a gradient.
//
// We take advantage of the call graph being a DAG and instead compute 1, 2 and 3
// for leaves first, then going down the tree. This is correct because 1 doesn't
// depend on other functions, and 2 and 3 depend only on callees.
for (size_t i = 0; i < callDag.size(); i++)
{
PullGradient pull(&metadataList, i, callDag);
pull.traverse(callDag.getRecordFromIndex(i).node);
}
// Compute which loops are discontinuous and which function are called in
// these loops. The same way computing gradient usage is a "pull" process,
// computing "bing used in a discont. loop" is a push process. However we also
// need to know what ifs have a discontinuous loop inside so we do the same type
// of callgraph analysis as for the gradient.
// First compute which loops are discontinuous (no specific order) and pull
// the ifs and functions using a gradient loop.
for (size_t i = 0; i < callDag.size(); i++)
{
PullComputeDiscontinuousAndGradientLoops pull(&metadataList, i, callDag);
pull.traverse(callDag.getRecordFromIndex(i).node);
}
// Then push the information to callees, either from the a local discontinuous
// loop or from the caller being called in a discontinuous loop already
for (size_t i = callDag.size(); i-- > 0;)
{
PushDiscontinuousLoops push(&metadataList, i, callDag);
push.traverse(callDag.getRecordFromIndex(i).node);
}
// We create "Lod0" version of functions with the gradient operations replaced
// by non-gradient operations so that the D3D compiler is happier with discont
// loops.
for (auto &metadata : metadataList)
{
metadata.mNeedsLod0 = metadata.mCalledInDiscontinuousLoop && metadata.mUsesGradient;
}
return metadataList;
}
} // namespace sh