glslang/MachineIndependent/LiveTraverser.h

   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) :
  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     //
  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
  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.
 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.
 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.
 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
 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