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