1 // 2 // Copyright 2002 The ANGLE Project Authors. All rights reserved. 3 // Use of this source code is governed by a BSD-style license that can be 4 // found in the LICENSE file. 5 // 6 7 // CallDAG.h: Defines a call graph DAG of functions to be re-used accross 8 // analyses, allows to efficiently traverse the functions in topological 9 // order. 10 11 #ifndef COMPILER_TRANSLATOR_CALLDAG_H_ 12 #define COMPILER_TRANSLATOR_CALLDAG_H_ 13 14 #include <map> 15 16 #include "compiler/translator/IntermNode.h" 17 18 namespace sh 19 { 20 21 // The translator needs to analyze the the graph of the function calls 22 // to run checks and analyses; since in GLSL recursion is not allowed 23 // that graph is a DAG. 24 // This class is used to precompute that function call DAG so that it 25 // can be reused by multiple analyses. 26 // 27 // It stores a vector of function records, with one record per defined function. 28 // Records are accessed by index but a function symbol id can be converted 29 // to the index of the corresponding record. The records contain the AST node 30 // of the function definition and the indices of the function's callees. 31 // 32 // In addition, records are in reverse topological order: a function F being 33 // called by a function G will have index index(F) < index(G), that way 34 // depth-first analysis becomes analysis in the order of indices. 35 36 class CallDAG : angle::NonCopyable 37 { 38 public: 39 CallDAG(); 40 ~CallDAG(); 41 42 struct Record 43 { 44 TIntermFunctionDefinition *node; // Guaranteed to be non-null. 45 std::vector<int> callees; 46 }; 47 48 enum InitResult 49 { 50 INITDAG_SUCCESS, 51 INITDAG_RECURSION, 52 INITDAG_UNDEFINED, 53 }; 54 55 // Returns INITDAG_SUCCESS if it was able to create the DAG, otherwise prints 56 // the initialization error in diagnostics, if present. 57 InitResult init(TIntermNode *root, TDiagnostics *diagnostics); 58 59 // Returns InvalidIndex if the function wasn't found 60 size_t findIndex(const TSymbolUniqueId &id) const; 61 62 const Record &getRecordFromIndex(size_t index) const; 63 size_t size() const; 64 void clear(); 65 66 const static size_t InvalidIndex; 67 68 private: 69 std::vector<Record> mRecords; 70 std::map<int, int> mFunctionIdToIndex; 71 72 class CallDAGCreator; 73 }; 74 75 } // namespace sh 76 77 #endif // COMPILER_TRANSLATOR_CALLDAG_H_ 78