LiveTraverser.h

Go to the documentation of this file.

//
// Copyright (C) 2016 LunarG, Inc.
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following
// disclaimer in the documentation and/or other materials provided
// with the distribution.
//
// Neither the name of 3Dlabs Inc. Ltd. nor the names of its
// contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//

#ifndef _MACHINE_INDEPENDENT_LIVE_TRAVERSER_H
#define _MACHINE_INDEPENDENT_LIVE_TRAVERSER_H

#pragma once

#include "../Include/Common.h"
#include "reflection.h"
#include "localintermediate.h"

#include "gl_types.h"

#include <list>
#include <unordered_set>

namespace glslang {

//
// The traverser: mostly pass through, except
// - processing function-call nodes to push live functions onto the stack of functions to process
// - processing selection nodes to trim semantically dead code
//
// This is in the glslang namespace directly so it can be a friend of TReflection.
// This can be derived from to implement reflection database traversers or
// binding mappers: anything that wants to traverse the live subset of the tree.
//

class TLiveTraverser : public TIntermTraverser {
public:
 TLiveTraverser(const TIntermediate& i, bool traverseAll = false,
 bool preVisit = true, bool inVisit = false, bool postVisit = false) :
 TIntermTraverser(preVisit, inVisit, postVisit),
 intermediate(i), traverseAll(traverseAll)
 { }

 //
 // Given a function name, find its subroot in the tree, and push it onto the stack of
 // functions left to process.
 //
 void pushFunction(const TString& name)
 {
 TIntermSequence& globals = intermediate.getTreeRoot()->getAsAggregate()->getSequence();
 for (unsigned int f = 0; f < globals.size(); ++f) {
 TIntermAggregate* candidate = globals[f]->getAsAggregate();
 if (candidate && candidate->getOp() == EOpFunction && candidate->getName() == name) {
 functions.push_back(candidate);
 break;
 }
 }
 }

 typedef std::list<TIntermAggregate*> TFunctionStack;
 TFunctionStack functions;

protected:
 // To catch which function calls are not dead, and hence which functions must be visited.
 virtual bool visitAggregate(TVisit, TIntermAggregate* node)
 {
 if (!traverseAll)
 if (node->getOp() == EOpFunctionCall)
 addFunctionCall(node);

 return true; // traverse this subtree
 }

 // To prune semantically dead paths.
 virtual bool visitSelection(TVisit /* visit */, TIntermSelection* node)
 {
 if (traverseAll)
 return true; // traverse all code

 TIntermConstantUnion* constant = node->getCondition()->getAsConstantUnion();
 if (constant) {
 // cull the path that is dead
 if (constant->getConstArray()[0].getBConst() == true && node->getTrueBlock())
 node->getTrueBlock()->traverse(this);
 if (constant->getConstArray()[0].getBConst() == false && node->getFalseBlock())
 node->getFalseBlock()->traverse(this);

 return false; // don't traverse any more, we did it all above
 } else
 return true; // traverse the whole subtree
 }

 // Track live functions as well as uniforms, so that we don't visit dead functions
 // and only visit each function once.
 void addFunctionCall(TIntermAggregate* call)
 {
 // // just use the map to ensure we process each function at most once
 if (liveFunctions.find(call->getName()) == liveFunctions.end()) {
 liveFunctions.insert(call->getName());
 pushFunction(call->getName());
 }
 }

 const TIntermediate& intermediate;
 typedef std::unordered_set<TString> TLiveFunctions;
 TLiveFunctions liveFunctions;
 bool traverseAll;

private:
 // prevent copy & copy construct
 TLiveTraverser(TLiveTraverser&);
 TLiveTraverser& operator=(TLiveTraverser&);
};

} // namespace glslang

#endif