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