1//
2// Copyright (c) 2002-2015 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
18namespace 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
36class 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