1 // 2 // Copyright (C) 2016 LunarG, Inc. 3 // 4 // All rights reserved. 5 // 6 // Redistribution and use in source and binary forms, with or without 7 // modification, are permitted provided that the following conditions 8 // are met: 9 // 10 // Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // 13 // Redistributions in binary form must reproduce the above 14 // copyright notice, this list of conditions and the following 15 // disclaimer in the documentation and/or other materials provided 16 // with the distribution. 17 // 18 // Neither the name of 3Dlabs Inc. Ltd. nor the names of its 19 // contributors may be used to endorse or promote products derived 20 // from this software without specific prior written permission. 21 // 22 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 30 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 32 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 // POSSIBILITY OF SUCH DAMAGE. 34 // 35 36 #pragma once 37 38 #include "../Include/Common.h" 39 #include "reflection.h" 40 #include "localintermediate.h" 41 42 #include "gl_types.h" 43 44 #include <list> 45 #include <unordered_set> 46 47 namespace glslang { 48 49 // 50 // The traverser: mostly pass through, except 51 // - processing function-call nodes to push live functions onto the stack of functions to process 52 // - processing selection nodes to trim semantically dead code 53 // 54 // This is in the glslang namespace directly so it can be a friend of TReflection. 55 // This can be derived from to implement reflection database traversers or 56 // binding mappers: anything that wants to traverse the live subset of the tree. 57 // 58 59 class TLiveTraverser : public TIntermTraverser { 60 public: 61 TLiveTraverser(const TIntermediate& i, bool traverseAll = false, 62 bool preVisit = true, bool inVisit = false, bool postVisit = false) : TIntermTraverser(preVisit,inVisit,postVisit)63 TIntermTraverser(preVisit, inVisit, postVisit), 64 intermediate(i), traverseAll(traverseAll) 65 { } 66 67 // 68 // Given a function name, find its subroot in the tree, and push it onto the stack of 69 // functions left to process. 70 // pushFunction(const TString & name)71 void pushFunction(const TString& name) 72 { 73 TIntermSequence& globals = intermediate.getTreeRoot()->getAsAggregate()->getSequence(); 74 for (unsigned int f = 0; f < globals.size(); ++f) { 75 TIntermAggregate* candidate = globals[f]->getAsAggregate(); 76 if (candidate && candidate->getOp() == EOpFunction && candidate->getName() == name) { 77 destinations.push_back(candidate); 78 break; 79 } 80 } 81 } 82 pushGlobalReference(const TString & name)83 void pushGlobalReference(const TString& name) 84 { 85 TIntermSequence& globals = intermediate.getTreeRoot()->getAsAggregate()->getSequence(); 86 for (unsigned int f = 0; f < globals.size(); ++f) { 87 TIntermAggregate* candidate = globals[f]->getAsAggregate(); 88 if (candidate && candidate->getOp() == EOpSequence && 89 candidate->getSequence().size() == 1 && 90 candidate->getSequence()[0]->getAsBinaryNode()) { 91 TIntermBinary* binary = candidate->getSequence()[0]->getAsBinaryNode(); 92 TIntermSymbol* symbol = binary->getLeft()->getAsSymbolNode(); 93 if (symbol && symbol->getQualifier().storage == EvqGlobal && 94 symbol->getName() == name) { 95 destinations.push_back(candidate); 96 break; 97 } 98 } 99 } 100 } 101 102 typedef std::list<TIntermAggregate*> TDestinationStack; 103 TDestinationStack destinations; 104 105 protected: 106 // To catch which function calls are not dead, and hence which functions must be visited. visitAggregate(TVisit,TIntermAggregate * node)107 virtual bool visitAggregate(TVisit, TIntermAggregate* node) 108 { 109 if (!traverseAll) 110 if (node->getOp() == EOpFunctionCall) 111 addFunctionCall(node); 112 113 return true; // traverse this subtree 114 } 115 116 // To prune semantically dead paths. visitSelection(TVisit,TIntermSelection * node)117 virtual bool visitSelection(TVisit /* visit */, TIntermSelection* node) 118 { 119 if (traverseAll) 120 return true; // traverse all code 121 122 TIntermConstantUnion* constant = node->getCondition()->getAsConstantUnion(); 123 if (constant) { 124 // cull the path that is dead 125 if (constant->getConstArray()[0].getBConst() == true && node->getTrueBlock()) 126 node->getTrueBlock()->traverse(this); 127 if (constant->getConstArray()[0].getBConst() == false && node->getFalseBlock()) 128 node->getFalseBlock()->traverse(this); 129 130 return false; // don't traverse any more, we did it all above 131 } else 132 return true; // traverse the whole subtree 133 } 134 135 // Track live functions as well as uniforms, so that we don't visit dead functions 136 // and only visit each function once. addFunctionCall(TIntermAggregate * call)137 void addFunctionCall(TIntermAggregate* call) 138 { 139 // just use the map to ensure we process each function at most once 140 if (liveFunctions.find(call->getName()) == liveFunctions.end()) { 141 liveFunctions.insert(call->getName()); 142 pushFunction(call->getName()); 143 } 144 } 145 addGlobalReference(const TString & name)146 void addGlobalReference(const TString& name) 147 { 148 // just use the map to ensure we process each global at most once 149 if (liveGlobals.find(name) == liveGlobals.end()) { 150 liveGlobals.insert(name); 151 pushGlobalReference(name); 152 } 153 } 154 155 const TIntermediate& intermediate; 156 typedef std::unordered_set<TString> TLiveFunctions; 157 TLiveFunctions liveFunctions; 158 typedef std::unordered_set<TString> TLiveGlobals; 159 TLiveGlobals liveGlobals; 160 bool traverseAll; 161 162 private: 163 // prevent copy & copy construct 164 TLiveTraverser(TLiveTraverser&); 165 TLiveTraverser& operator=(TLiveTraverser&); 166 }; 167 168 } // namespace glslang 169