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 : // Analysis of the AST needed for HLSL generation
8 :
9 : #include "compiler/translator/ASTMetadataHLSL.h"
10 :
11 : #include "compiler/translator/CallDAG.h"
12 : #include "compiler/translator/SymbolTable.h"
13 :
14 : namespace sh
15 : {
16 :
17 : namespace
18 : {
19 :
20 : // Class used to traverse the AST of a function definition, checking if the
21 : // function uses a gradient, and writing the set of control flow using gradients.
22 : // It assumes that the analysis has already been made for the function's
23 : // callees.
24 0 : class PullGradient : public TIntermTraverser
25 : {
26 : public:
27 0 : PullGradient(MetadataList *metadataList, size_t index, const CallDAG &dag)
28 0 : : TIntermTraverser(true, false, true),
29 : mMetadataList(metadataList),
30 0 : mMetadata(&(*metadataList)[index]),
31 : mIndex(index),
32 0 : mDag(dag)
33 : {
34 0 : ASSERT(index < metadataList->size());
35 0 : }
36 :
37 0 : void traverse(TIntermFunctionDefinition *node)
38 : {
39 0 : node->traverse(this);
40 0 : ASSERT(mParents.empty());
41 0 : }
42 :
43 : // Called when a gradient operation or a call to a function using a gradient is found.
44 0 : void onGradient()
45 : {
46 0 : mMetadata->mUsesGradient = true;
47 : // Mark the latest control flow as using a gradient.
48 0 : if (!mParents.empty())
49 : {
50 0 : mMetadata->mControlFlowsContainingGradient.insert(mParents.back());
51 : }
52 0 : }
53 :
54 0 : void visitControlFlow(Visit visit, TIntermNode *node)
55 : {
56 0 : if (visit == PreVisit)
57 : {
58 0 : mParents.push_back(node);
59 : }
60 0 : else if (visit == PostVisit)
61 : {
62 0 : ASSERT(mParents.back() == node);
63 0 : mParents.pop_back();
64 : // A control flow's using a gradient means its parents are too.
65 0 : if (mMetadata->mControlFlowsContainingGradient.count(node)> 0 && !mParents.empty())
66 : {
67 0 : mMetadata->mControlFlowsContainingGradient.insert(mParents.back());
68 : }
69 : }
70 0 : }
71 :
72 0 : bool visitLoop(Visit visit, TIntermLoop *loop) override
73 : {
74 0 : visitControlFlow(visit, loop);
75 0 : return true;
76 : }
77 :
78 0 : bool visitIfElse(Visit visit, TIntermIfElse *ifElse) override
79 : {
80 0 : visitControlFlow(visit, ifElse);
81 0 : return true;
82 : }
83 :
84 0 : bool visitUnary(Visit visit, TIntermUnary *node) override
85 : {
86 0 : if (visit == PreVisit)
87 : {
88 0 : switch (node->getOp())
89 : {
90 : case EOpDFdx:
91 : case EOpDFdy:
92 0 : onGradient();
93 : default:
94 0 : break;
95 : }
96 : }
97 :
98 0 : return true;
99 : }
100 :
101 0 : bool visitAggregate(Visit visit, TIntermAggregate *node) override
102 : {
103 0 : if (visit == PreVisit)
104 : {
105 0 : if (node->getOp() == EOpFunctionCall)
106 : {
107 0 : if (node->isUserDefined())
108 : {
109 0 : size_t calleeIndex = mDag.findIndex(node->getFunctionSymbolInfo());
110 0 : ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
111 :
112 0 : if ((*mMetadataList)[calleeIndex].mUsesGradient) {
113 0 : onGradient();
114 : }
115 : }
116 : else
117 : {
118 : TString name =
119 0 : TFunction::unmangleName(node->getFunctionSymbolInfo()->getName());
120 :
121 0 : if (name == "texture2D" ||
122 0 : name == "texture2DProj" ||
123 0 : name == "textureCube")
124 : {
125 0 : onGradient();
126 : }
127 : }
128 : }
129 : }
130 :
131 0 : return true;
132 : }
133 :
134 : private:
135 : MetadataList *mMetadataList;
136 : ASTMetadataHLSL *mMetadata;
137 : size_t mIndex;
138 : const CallDAG &mDag;
139 :
140 : // Contains a stack of the control flow nodes that are parents of the node being
141 : // currently visited. It is used to mark control flows using a gradient.
142 : std::vector<TIntermNode*> mParents;
143 : };
144 :
145 : // Traverses the AST of a function definition to compute the the discontinuous loops
146 : // and the if statements containing gradient loops. It assumes that the gradient loops
147 : // (loops that contain a gradient) have already been computed and that it has already
148 : // traversed the current function's callees.
149 0 : class PullComputeDiscontinuousAndGradientLoops : public TIntermTraverser
150 : {
151 : public:
152 0 : PullComputeDiscontinuousAndGradientLoops(MetadataList *metadataList,
153 : size_t index,
154 : const CallDAG &dag)
155 0 : : TIntermTraverser(true, false, true),
156 : mMetadataList(metadataList),
157 0 : mMetadata(&(*metadataList)[index]),
158 : mIndex(index),
159 0 : mDag(dag)
160 : {
161 0 : }
162 :
163 0 : void traverse(TIntermFunctionDefinition *node)
164 : {
165 0 : node->traverse(this);
166 0 : ASSERT(mLoopsAndSwitches.empty());
167 0 : ASSERT(mIfs.empty());
168 0 : }
169 :
170 : // Called when traversing a gradient loop or a call to a function with a
171 : // gradient loop in its call graph.
172 0 : void onGradientLoop()
173 : {
174 0 : mMetadata->mHasGradientLoopInCallGraph = true;
175 : // Mark the latest if as using a discontinuous loop.
176 0 : if (!mIfs.empty())
177 : {
178 0 : mMetadata->mIfsContainingGradientLoop.insert(mIfs.back());
179 : }
180 0 : }
181 :
182 0 : bool visitLoop(Visit visit, TIntermLoop *loop) override
183 : {
184 0 : if (visit == PreVisit)
185 : {
186 0 : mLoopsAndSwitches.push_back(loop);
187 :
188 0 : if (mMetadata->hasGradientInCallGraph(loop))
189 : {
190 0 : onGradientLoop();
191 : }
192 : }
193 0 : else if (visit == PostVisit)
194 : {
195 0 : ASSERT(mLoopsAndSwitches.back() == loop);
196 0 : mLoopsAndSwitches.pop_back();
197 : }
198 :
199 0 : return true;
200 : }
201 :
202 0 : bool visitIfElse(Visit visit, TIntermIfElse *node) override
203 : {
204 0 : if (visit == PreVisit)
205 : {
206 0 : mIfs.push_back(node);
207 : }
208 0 : else if (visit == PostVisit)
209 : {
210 0 : ASSERT(mIfs.back() == node);
211 0 : mIfs.pop_back();
212 : // An if using a discontinuous loop means its parents ifs are also discontinuous.
213 0 : if (mMetadata->mIfsContainingGradientLoop.count(node) > 0 && !mIfs.empty())
214 : {
215 0 : mMetadata->mIfsContainingGradientLoop.insert(mIfs.back());
216 : }
217 : }
218 :
219 0 : return true;
220 : }
221 :
222 0 : bool visitBranch(Visit visit, TIntermBranch *node) override
223 : {
224 0 : if (visit == PreVisit)
225 : {
226 0 : switch (node->getFlowOp())
227 : {
228 : case EOpBreak:
229 : {
230 0 : ASSERT(!mLoopsAndSwitches.empty());
231 0 : TIntermLoop *loop = mLoopsAndSwitches.back()->getAsLoopNode();
232 0 : if (loop != nullptr)
233 : {
234 0 : mMetadata->mDiscontinuousLoops.insert(loop);
235 : }
236 : }
237 0 : break;
238 : case EOpContinue:
239 : {
240 0 : ASSERT(!mLoopsAndSwitches.empty());
241 0 : TIntermLoop *loop = nullptr;
242 0 : size_t i = mLoopsAndSwitches.size();
243 0 : while (loop == nullptr && i > 0)
244 : {
245 0 : --i;
246 0 : loop = mLoopsAndSwitches.at(i)->getAsLoopNode();
247 : }
248 0 : ASSERT(loop != nullptr);
249 0 : mMetadata->mDiscontinuousLoops.insert(loop);
250 : }
251 0 : break;
252 : case EOpKill:
253 : case EOpReturn:
254 : // A return or discard jumps out of all the enclosing loops
255 0 : if (!mLoopsAndSwitches.empty())
256 : {
257 0 : for (TIntermNode *intermNode : mLoopsAndSwitches)
258 : {
259 0 : TIntermLoop *loop = intermNode->getAsLoopNode();
260 0 : if (loop)
261 : {
262 0 : mMetadata->mDiscontinuousLoops.insert(loop);
263 : }
264 : }
265 : }
266 0 : break;
267 : default:
268 0 : UNREACHABLE();
269 : }
270 : }
271 :
272 0 : return true;
273 : }
274 :
275 0 : bool visitAggregate(Visit visit, TIntermAggregate *node) override
276 : {
277 0 : if (visit == PreVisit && node->getOp() == EOpFunctionCall)
278 : {
279 0 : if (node->isUserDefined())
280 : {
281 0 : size_t calleeIndex = mDag.findIndex(node->getFunctionSymbolInfo());
282 0 : ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
283 :
284 0 : if ((*mMetadataList)[calleeIndex].mHasGradientLoopInCallGraph)
285 : {
286 0 : onGradientLoop();
287 : }
288 : }
289 : }
290 :
291 0 : return true;
292 : }
293 :
294 0 : bool visitSwitch(Visit visit, TIntermSwitch *node) override
295 : {
296 0 : if (visit == PreVisit)
297 : {
298 0 : mLoopsAndSwitches.push_back(node);
299 : }
300 0 : else if (visit == PostVisit)
301 : {
302 0 : ASSERT(mLoopsAndSwitches.back() == node);
303 0 : mLoopsAndSwitches.pop_back();
304 : }
305 0 : return true;
306 : }
307 :
308 : private:
309 : MetadataList *mMetadataList;
310 : ASTMetadataHLSL *mMetadata;
311 : size_t mIndex;
312 : const CallDAG &mDag;
313 :
314 : std::vector<TIntermNode*> mLoopsAndSwitches;
315 : std::vector<TIntermIfElse *> mIfs;
316 : };
317 :
318 : // Tags all the functions called in a discontinuous loop
319 0 : class PushDiscontinuousLoops : public TIntermTraverser
320 : {
321 : public:
322 0 : PushDiscontinuousLoops(MetadataList *metadataList, size_t index, const CallDAG &dag)
323 0 : : TIntermTraverser(true, true, true),
324 : mMetadataList(metadataList),
325 0 : mMetadata(&(*metadataList)[index]),
326 : mIndex(index),
327 : mDag(dag),
328 0 : mNestedDiscont(mMetadata->mCalledInDiscontinuousLoop ? 1 : 0)
329 : {
330 0 : }
331 :
332 0 : void traverse(TIntermFunctionDefinition *node)
333 : {
334 0 : node->traverse(this);
335 0 : ASSERT(mNestedDiscont == (mMetadata->mCalledInDiscontinuousLoop ? 1 : 0));
336 0 : }
337 :
338 0 : bool visitLoop(Visit visit, TIntermLoop *loop) override
339 : {
340 0 : bool isDiscontinuous = mMetadata->mDiscontinuousLoops.count(loop) > 0;
341 :
342 0 : if (visit == PreVisit && isDiscontinuous)
343 : {
344 0 : mNestedDiscont++;
345 : }
346 0 : else if (visit == PostVisit && isDiscontinuous)
347 : {
348 0 : mNestedDiscont--;
349 : }
350 :
351 0 : return true;
352 : }
353 :
354 0 : bool visitAggregate(Visit visit, TIntermAggregate *node) override
355 : {
356 0 : switch (node->getOp())
357 : {
358 : case EOpFunctionCall:
359 0 : if (visit == PreVisit && node->isUserDefined() && mNestedDiscont > 0)
360 : {
361 0 : size_t calleeIndex = mDag.findIndex(node->getFunctionSymbolInfo());
362 0 : ASSERT(calleeIndex != CallDAG::InvalidIndex && calleeIndex < mIndex);
363 :
364 0 : (*mMetadataList)[calleeIndex].mCalledInDiscontinuousLoop = true;
365 : }
366 0 : break;
367 : default:
368 0 : break;
369 : }
370 0 : return true;
371 : }
372 :
373 : private:
374 : MetadataList *mMetadataList;
375 : ASTMetadataHLSL *mMetadata;
376 : size_t mIndex;
377 : const CallDAG &mDag;
378 :
379 : int mNestedDiscont;
380 : };
381 :
382 : }
383 :
384 0 : bool ASTMetadataHLSL::hasGradientInCallGraph(TIntermLoop *node)
385 : {
386 0 : return mControlFlowsContainingGradient.count(node) > 0;
387 : }
388 :
389 0 : bool ASTMetadataHLSL::hasGradientLoop(TIntermIfElse *node)
390 : {
391 0 : return mIfsContainingGradientLoop.count(node) > 0;
392 : }
393 :
394 0 : MetadataList CreateASTMetadataHLSL(TIntermNode *root, const CallDAG &callDag)
395 : {
396 0 : MetadataList metadataList(callDag.size());
397 :
398 : // Compute all the information related to when gradient operations are used.
399 : // We want to know for each function and control flow operation if they have
400 : // a gradient operation in their call graph (shortened to "using a gradient"
401 : // in the rest of the file).
402 : //
403 : // This computation is logically split in three steps:
404 : // 1 - For each function compute if it uses a gradient in its body, ignoring
405 : // calls to other user-defined functions.
406 : // 2 - For each function determine if it uses a gradient in its call graph,
407 : // using the result of step 1 and the CallDAG to know its callees.
408 : // 3 - For each control flow statement of each function, check if it uses a
409 : // gradient in the function's body, or if it calls a user-defined function that
410 : // uses a gradient.
411 : //
412 : // We take advantage of the call graph being a DAG and instead compute 1, 2 and 3
413 : // for leaves first, then going down the tree. This is correct because 1 doesn't
414 : // depend on other functions, and 2 and 3 depend only on callees.
415 0 : for (size_t i = 0; i < callDag.size(); i++)
416 : {
417 0 : PullGradient pull(&metadataList, i, callDag);
418 0 : pull.traverse(callDag.getRecordFromIndex(i).node);
419 : }
420 :
421 : // Compute which loops are discontinuous and which function are called in
422 : // these loops. The same way computing gradient usage is a "pull" process,
423 : // computing "bing used in a discont. loop" is a push process. However we also
424 : // need to know what ifs have a discontinuous loop inside so we do the same type
425 : // of callgraph analysis as for the gradient.
426 :
427 : // First compute which loops are discontinuous (no specific order) and pull
428 : // the ifs and functions using a gradient loop.
429 0 : for (size_t i = 0; i < callDag.size(); i++)
430 : {
431 0 : PullComputeDiscontinuousAndGradientLoops pull(&metadataList, i, callDag);
432 0 : pull.traverse(callDag.getRecordFromIndex(i).node);
433 : }
434 :
435 : // Then push the information to callees, either from the a local discontinuous
436 : // loop or from the caller being called in a discontinuous loop already
437 0 : for (size_t i = callDag.size(); i-- > 0;)
438 : {
439 0 : PushDiscontinuousLoops push(&metadataList, i, callDag);
440 0 : push.traverse(callDag.getRecordFromIndex(i).node);
441 : }
442 :
443 : // We create "Lod0" version of functions with the gradient operations replaced
444 : // by non-gradient operations so that the D3D compiler is happier with discont
445 : // loops.
446 0 : for (auto &metadata : metadataList)
447 : {
448 0 : metadata.mNeedsLod0 = metadata.mCalledInDiscontinuousLoop && metadata.mUsesGradient;
449 : }
450 :
451 0 : return metadataList;
452 : }
453 :
454 : } // namespace sh
|
