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: Implements 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#include "compiler/translator/CallDAG.h"
12
13#include "compiler/translator/Diagnostics.h"
14#include "compiler/translator/SymbolTable.h"
15#include "compiler/translator/tree_util/IntermTraverse.h"
16
17namespace sh
18{
19
20// The CallDAGCreator does all the processing required to create the CallDAG
21// structure so that the latter contains only the necessary variables.
22class CallDAG::CallDAGCreator : public TIntermTraverser
23{
24 public:
25 CallDAGCreator(TDiagnostics *diagnostics)
26 : TIntermTraverser(true, false, false),
27 mDiagnostics(diagnostics),
28 mCurrentFunction(nullptr),
29 mCurrentIndex(0)
30 {}
31
32 InitResult assignIndices()
33 {
34 int skipped = 0;
35 for (auto &it : mFunctions)
36 {
37 // Skip unimplemented functions
38 if (it.second.definitionNode)
39 {
40 InitResult result = assignIndicesInternal(&it.second);
41 if (result != INITDAG_SUCCESS)
42 {
43 return result;
44 }
45 }
46 else
47 {
48 skipped++;
49 }
50 }
51
52 ASSERT(mFunctions.size() == mCurrentIndex + skipped);
53 return INITDAG_SUCCESS;
54 }
55
56 void fillDataStructures(std::vector<Record> *records, std::map<int, int> *idToIndex)
57 {
58 ASSERT(records->empty());
59 ASSERT(idToIndex->empty());
60
61 records->resize(mCurrentIndex);
62
63 for (auto &it : mFunctions)
64 {
65 CreatorFunctionData &data = it.second;
66 // Skip unimplemented functions
67 if (!data.definitionNode)
68 {
69 continue;
70 }
71 ASSERT(data.index < records->size());
72 Record &record = (*records)[data.index];
73
74 record.node = data.definitionNode;
75
76 record.callees.reserve(data.callees.size());
77 for (auto &callee : data.callees)
78 {
79 record.callees.push_back(static_cast<int>(callee->index));
80 }
81
82 (*idToIndex)[it.first] = static_cast<int>(data.index);
83 }
84 }
85
86 private:
87 struct CreatorFunctionData
88 {
89 CreatorFunctionData()
90 : definitionNode(nullptr), name(""), index(0), indexAssigned(false), visiting(false)
91 {}
92
93 std::set<CreatorFunctionData *> callees;
94 TIntermFunctionDefinition *definitionNode;
95 ImmutableString name;
96 size_t index;
97 bool indexAssigned;
98 bool visiting;
99 };
100
101 bool visitFunctionDefinition(Visit visit, TIntermFunctionDefinition *node) override
102 {
103 // Create the record if need be and remember the definition node.
104 mCurrentFunction = &mFunctions[node->getFunction()->uniqueId().get()];
105 // Name will be overwritten here. If we've already traversed the prototype of this function,
106 // it should have had the same name.
107 ASSERT(mCurrentFunction->name == "" ||
108 mCurrentFunction->name == node->getFunction()->name());
109 mCurrentFunction->name = node->getFunction()->name();
110 mCurrentFunction->definitionNode = node;
111
112 node->getBody()->traverse(this);
113 mCurrentFunction = nullptr;
114 return false;
115 }
116
117 void visitFunctionPrototype(TIntermFunctionPrototype *node) override
118 {
119 ASSERT(mCurrentFunction == nullptr);
120
121 // Function declaration, create an empty record.
122 auto &record = mFunctions[node->getFunction()->uniqueId().get()];
123 record.name = node->getFunction()->name();
124 }
125
126 // Track functions called from another function.
127 bool visitAggregate(Visit visit, TIntermAggregate *node) override
128 {
129 if (node->getOp() == EOpCallFunctionInAST)
130 {
131 // Function call, add the callees
132 auto it = mFunctions.find(node->getFunction()->uniqueId().get());
133 ASSERT(it != mFunctions.end());
134
135 // We might be traversing the initializer of a global variable. Even though function
136 // calls in global scope are forbidden by the parser, some subsequent AST
137 // transformations can add them to emulate particular features.
138 if (mCurrentFunction)
139 {
140 mCurrentFunction->callees.insert(&it->second);
141 }
142 }
143 return true;
144 }
145
146 // Recursively assigns indices to a sub DAG
147 InitResult assignIndicesInternal(CreatorFunctionData *root)
148 {
149 // Iterative implementation of the index assignment algorithm. A recursive version
150 // would be prettier but since the CallDAG creation runs before the limiting of the
151 // call depth, we might get stack overflows (computation of the call depth uses the
152 // CallDAG).
153
154 ASSERT(root);
155
156 if (root->indexAssigned)
157 {
158 return INITDAG_SUCCESS;
159 }
160
161 // If we didn't have to detect recursion, functionsToProcess could be a simple queue
162 // in which we add the function being processed's callees. However in order to detect
163 // recursion we need to know which functions we are currently visiting. For that reason
164 // functionsToProcess will look like a concatenation of segments of the form
165 // [F visiting = true, subset of F callees with visiting = false] and the following
166 // segment (if any) will be start with a callee of F.
167 // This way we can remember when we started visiting a function, to put visiting back
168 // to false.
169 TVector<CreatorFunctionData *> functionsToProcess;
170 functionsToProcess.push_back(root);
171
172 InitResult result = INITDAG_SUCCESS;
173
174 std::stringstream errorStream = sh::InitializeStream<std::stringstream>();
175
176 while (!functionsToProcess.empty())
177 {
178 CreatorFunctionData *function = functionsToProcess.back();
179
180 if (function->visiting)
181 {
182 function->visiting = false;
183 function->index = mCurrentIndex++;
184 function->indexAssigned = true;
185
186 functionsToProcess.pop_back();
187 continue;
188 }
189
190 if (!function->definitionNode)
191 {
192 errorStream << "Undefined function '" << function->name
193 << ")' used in the following call chain:";
194 result = INITDAG_UNDEFINED;
195 break;
196 }
197
198 if (function->indexAssigned)
199 {
200 functionsToProcess.pop_back();
201 continue;
202 }
203
204 function->visiting = true;
205
206 for (auto callee : function->callees)
207 {
208 functionsToProcess.push_back(callee);
209
210 // Check if the callee is already being visited after pushing it so that it appears
211 // in the chain printed in the info log.
212 if (callee->visiting)
213 {
214 errorStream << "Recursive function call in the following call chain:";
215 result = INITDAG_RECURSION;
216 break;
217 }
218 }
219
220 if (result != INITDAG_SUCCESS)
221 {
222 break;
223 }
224 }
225
226 // The call chain is made of the function we were visiting when the error was detected.
227 if (result != INITDAG_SUCCESS)
228 {
229 bool first = true;
230 for (auto function : functionsToProcess)
231 {
232 if (function->visiting)
233 {
234 if (!first)
235 {
236 errorStream << " -> ";
237 }
238 errorStream << function->name << ")";
239 first = false;
240 }
241 }
242 if (mDiagnostics)
243 {
244 std::string errorStr = errorStream.str();
245 mDiagnostics->globalError(errorStr.c_str());
246 }
247 }
248
249 return result;
250 }
251
252 TDiagnostics *mDiagnostics;
253
254 std::map<int, CreatorFunctionData> mFunctions;
255 CreatorFunctionData *mCurrentFunction;
256 size_t mCurrentIndex;
257};
258
259// CallDAG
260
261CallDAG::CallDAG() {}
262
263CallDAG::~CallDAG() {}
264
265const size_t CallDAG::InvalidIndex = std::numeric_limits<size_t>::max();
266
267size_t CallDAG::findIndex(const TSymbolUniqueId &id) const
268{
269 auto it = mFunctionIdToIndex.find(id.get());
270
271 if (it == mFunctionIdToIndex.end())
272 {
273 return InvalidIndex;
274 }
275 else
276 {
277 return it->second;
278 }
279}
280
281const CallDAG::Record &CallDAG::getRecordFromIndex(size_t index) const
282{
283 ASSERT(index != InvalidIndex && index < mRecords.size());
284 return mRecords[index];
285}
286
287size_t CallDAG::size() const
288{
289 return mRecords.size();
290}
291
292void CallDAG::clear()
293{
294 mRecords.clear();
295 mFunctionIdToIndex.clear();
296}
297
298CallDAG::InitResult CallDAG::init(TIntermNode *root, TDiagnostics *diagnostics)
299{
300 CallDAGCreator creator(diagnostics);
301
302 // Creates the mapping of functions to callees
303 root->traverse(&creator);
304
305 // Does the topological sort and detects recursions
306 InitResult result = creator.assignIndices();
307 if (result != INITDAG_SUCCESS)
308 {
309 return result;
310 }
311
312 creator.fillDataStructures(&mRecords, &mFunctionIdToIndex);
313 return INITDAG_SUCCESS;
314}
315
316} // namespace sh
317