1 //
2 // Copyright (c) 2002-2013 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 // UnfoldShortCircuitToIf is an AST traverser to convert short-circuiting operators to if-else
7 // statements.
8 // The results are assigned to s# temporaries, which are used by the main translator instead of
9 // the original expression.
10 //
11
12 #include "compiler/translator/UnfoldShortCircuitToIf.h"
13
14 #include "compiler/translator/IntermNodePatternMatcher.h"
15 #include "compiler/translator/IntermTraverse.h"
16
17 namespace sh
18 {
19
20 namespace
21 {
22
23 // Traverser that unfolds one short-circuiting operation at a time.
24 class UnfoldShortCircuitTraverser : public TIntermTraverser
25 {
26 public:
27 UnfoldShortCircuitTraverser(TSymbolTable *symbolTable);
28
29 bool visitBinary(Visit visit, TIntermBinary *node) override;
30 bool visitTernary(Visit visit, TIntermTernary *node) override;
31
32 void nextIteration();
foundShortCircuit() const33 bool foundShortCircuit() const { return mFoundShortCircuit; }
34
35 protected:
36 // Marked to true once an operation that needs to be unfolded has been found.
37 // After that, no more unfolding is performed on that traversal.
38 bool mFoundShortCircuit;
39
40 IntermNodePatternMatcher mPatternToUnfoldMatcher;
41 };
42
UnfoldShortCircuitTraverser(TSymbolTable * symbolTable)43 UnfoldShortCircuitTraverser::UnfoldShortCircuitTraverser(TSymbolTable *symbolTable)
44 : TIntermTraverser(true, false, true, symbolTable),
45 mFoundShortCircuit(false),
46 mPatternToUnfoldMatcher(IntermNodePatternMatcher::kUnfoldedShortCircuitExpression)
47 {
48 }
49
visitBinary(Visit visit,TIntermBinary * node)50 bool UnfoldShortCircuitTraverser::visitBinary(Visit visit, TIntermBinary *node)
51 {
52 if (mFoundShortCircuit)
53 return false;
54
55 if (visit != PreVisit)
56 return true;
57
58 if (!mPatternToUnfoldMatcher.match(node, getParentNode()))
59 return true;
60
61 // If our right node doesn't have side effects, we know we don't need to unfold this
62 // expression: there will be no short-circuiting side effects to avoid
63 // (note: unfolding doesn't depend on the left node -- it will always be evaluated)
64 ASSERT(node->getRight()->hasSideEffects());
65
66 mFoundShortCircuit = true;
67
68 switch (node->getOp())
69 {
70 case EOpLogicalOr:
71 {
72 // "x || y" is equivalent to "x ? true : y", which unfolds to "bool s; if(x) s = true;
73 // else s = y;",
74 // and then further simplifies down to "bool s = x; if(!s) s = y;".
75
76 TIntermSequence insertions;
77 TType boolType(EbtBool, EbpUndefined, EvqTemporary);
78
79 ASSERT(node->getLeft()->getType() == boolType);
80 insertions.push_back(createTempInitDeclaration(node->getLeft()));
81
82 TIntermBlock *assignRightBlock = new TIntermBlock();
83 ASSERT(node->getRight()->getType() == boolType);
84 assignRightBlock->getSequence()->push_back(createTempAssignment(node->getRight()));
85
86 TIntermUnary *notTempSymbol =
87 new TIntermUnary(EOpLogicalNot, createTempSymbol(boolType));
88 TIntermIfElse *ifNode = new TIntermIfElse(notTempSymbol, assignRightBlock, nullptr);
89 insertions.push_back(ifNode);
90
91 insertStatementsInParentBlock(insertions);
92
93 queueReplacement(createTempSymbol(boolType), OriginalNode::IS_DROPPED);
94 return false;
95 }
96 case EOpLogicalAnd:
97 {
98 // "x && y" is equivalent to "x ? y : false", which unfolds to "bool s; if(x) s = y;
99 // else s = false;",
100 // and then further simplifies down to "bool s = x; if(s) s = y;".
101 TIntermSequence insertions;
102 TType boolType(EbtBool, EbpUndefined, EvqTemporary);
103
104 ASSERT(node->getLeft()->getType() == boolType);
105 insertions.push_back(createTempInitDeclaration(node->getLeft()));
106
107 TIntermBlock *assignRightBlock = new TIntermBlock();
108 ASSERT(node->getRight()->getType() == boolType);
109 assignRightBlock->getSequence()->push_back(createTempAssignment(node->getRight()));
110
111 TIntermIfElse *ifNode =
112 new TIntermIfElse(createTempSymbol(boolType), assignRightBlock, nullptr);
113 insertions.push_back(ifNode);
114
115 insertStatementsInParentBlock(insertions);
116
117 queueReplacement(createTempSymbol(boolType), OriginalNode::IS_DROPPED);
118 return false;
119 }
120 default:
121 UNREACHABLE();
122 return true;
123 }
124 }
125
visitTernary(Visit visit,TIntermTernary * node)126 bool UnfoldShortCircuitTraverser::visitTernary(Visit visit, TIntermTernary *node)
127 {
128 if (mFoundShortCircuit)
129 return false;
130
131 if (visit != PreVisit)
132 return true;
133
134 if (!mPatternToUnfoldMatcher.match(node))
135 return true;
136
137 mFoundShortCircuit = true;
138
139 // Unfold "b ? x : y" into "type s; if(b) s = x; else s = y;"
140 TIntermSequence insertions;
141
142 TIntermDeclaration *tempDeclaration = createTempDeclaration(node->getType());
143 insertions.push_back(tempDeclaration);
144
145 TIntermBlock *trueBlock = new TIntermBlock();
146 TIntermBinary *trueAssignment = createTempAssignment(node->getTrueExpression());
147 trueBlock->getSequence()->push_back(trueAssignment);
148
149 TIntermBlock *falseBlock = new TIntermBlock();
150 TIntermBinary *falseAssignment = createTempAssignment(node->getFalseExpression());
151 falseBlock->getSequence()->push_back(falseAssignment);
152
153 TIntermIfElse *ifNode =
154 new TIntermIfElse(node->getCondition()->getAsTyped(), trueBlock, falseBlock);
155 insertions.push_back(ifNode);
156
157 insertStatementsInParentBlock(insertions);
158
159 TIntermSymbol *ternaryResult = createTempSymbol(node->getType());
160 queueReplacement(ternaryResult, OriginalNode::IS_DROPPED);
161
162 return false;
163 }
164
nextIteration()165 void UnfoldShortCircuitTraverser::nextIteration()
166 {
167 mFoundShortCircuit = false;
168 nextTemporaryId();
169 }
170
171 } // namespace
172
UnfoldShortCircuitToIf(TIntermNode * root,TSymbolTable * symbolTable)173 void UnfoldShortCircuitToIf(TIntermNode *root, TSymbolTable *symbolTable)
174 {
175 UnfoldShortCircuitTraverser traverser(symbolTable);
176 // Unfold one operator at a time, and reset the traverser between iterations.
177 do
178 {
179 traverser.nextIteration();
180 root->traverse(&traverser);
181 if (traverser.foundShortCircuit())
182 traverser.updateTree();
183 } while (traverser.foundShortCircuit());
184 }
185
186 } // namespace sh
187