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