1 //
2 // Copyright (c) 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 // RewriteDoWhile.cpp: rewrites do-while loops using another equivalent
8 // construct.
9
10 #include "compiler/translator/RewriteDoWhile.h"
11
12 #include "compiler/translator/IntermNode_util.h"
13 #include "compiler/translator/IntermTraverse.h"
14 #include "compiler/translator/StaticType.h"
15
16 namespace sh
17 {
18
19 namespace
20 {
21
22 // An AST traverser that rewrites loops of the form
23 // do {
24 // CODE;
25 // } while (CONDITION)
26 //
27 // to loops of the form
28 // bool temp = false;
29 // while (true) {
30 // if (temp) {
31 // if (!CONDITION) {
32 // break;
33 // }
34 // }
35 // temp = true;
36 // CODE;
37 // }
38 //
39 // The reason we don't use a simpler form, with for example just (temp && !CONDITION) in the
40 // while condition, is that short-circuit is often badly supported by driver shader compiler.
41 // The double if has the same effect, but forces shader compilers to behave.
42 //
43 // TODO(cwallez) when UnfoldShortCircuitIntoIf handles loops correctly, revisit this as we might
44 // be able to use while (temp || CONDITION) with temp initially set to true then run
45 // UnfoldShortCircuitIntoIf
46 class DoWhileRewriter : public TIntermTraverser
47 {
48 public:
DoWhileRewriter(TSymbolTable * symbolTable)49 DoWhileRewriter(TSymbolTable *symbolTable) : TIntermTraverser(true, false, false, symbolTable)
50 {
51 }
52
visitBlock(Visit,TIntermBlock * node)53 bool visitBlock(Visit, TIntermBlock *node) override
54 {
55 // A well-formed AST can only have do-while inside TIntermBlock. By doing a prefix traversal
56 // we are able to replace the do-while in the sequence directly as the content of the
57 // do-while will be traversed later.
58
59 TIntermSequence *statements = node->getSequence();
60
61 // The statements vector will have new statements inserted when we encounter a do-while,
62 // which prevents us from using a range-based for loop. Using the usual i++ works, as
63 // the (two) new statements inserted replace the statement at the current position.
64 for (size_t i = 0; i < statements->size(); i++)
65 {
66 TIntermNode *statement = (*statements)[i];
67 TIntermLoop *loop = statement->getAsLoopNode();
68
69 if (loop == nullptr || loop->getType() != ELoopDoWhile)
70 {
71 continue;
72 }
73
74 // Found a loop to change.
75 const TType *boolType = StaticType::Get<EbtBool, EbpUndefined, EvqTemporary, 1, 1>();
76 TVariable *conditionVariable = CreateTempVariable(mSymbolTable, boolType);
77
78 // bool temp = false;
79 TIntermDeclaration *tempDeclaration =
80 CreateTempInitDeclarationNode(conditionVariable, CreateBoolNode(false));
81
82 // temp = true;
83 TIntermBinary *assignTrue =
84 CreateTempAssignmentNode(conditionVariable, CreateBoolNode(true));
85
86 // if (temp) {
87 // if (!CONDITION) {
88 // break;
89 // }
90 // }
91 TIntermIfElse *breakIf = nullptr;
92 {
93 TIntermBranch *breakStatement = new TIntermBranch(EOpBreak, nullptr);
94
95 TIntermBlock *breakBlock = new TIntermBlock();
96 breakBlock->getSequence()->push_back(breakStatement);
97
98 TIntermUnary *negatedCondition =
99 new TIntermUnary(EOpLogicalNot, loop->getCondition());
100
101 TIntermIfElse *innerIf = new TIntermIfElse(negatedCondition, breakBlock, nullptr);
102
103 TIntermBlock *innerIfBlock = new TIntermBlock();
104 innerIfBlock->getSequence()->push_back(innerIf);
105
106 breakIf = new TIntermIfElse(CreateTempSymbolNode(conditionVariable), innerIfBlock,
107 nullptr);
108 }
109
110 // Assemble the replacement loops, reusing the do-while loop's body and inserting our
111 // statements at the front.
112 TIntermLoop *newLoop = nullptr;
113 {
114 TIntermBlock *body = loop->getBody();
115 if (body == nullptr)
116 {
117 body = new TIntermBlock();
118 }
119 auto sequence = body->getSequence();
120 sequence->insert(sequence->begin(), assignTrue);
121 sequence->insert(sequence->begin(), breakIf);
122
123 newLoop = new TIntermLoop(ELoopWhile, nullptr, CreateBoolNode(true), nullptr, body);
124 }
125
126 TIntermSequence replacement;
127 replacement.push_back(tempDeclaration);
128 replacement.push_back(newLoop);
129
130 node->replaceChildNodeWithMultiple(loop, replacement);
131 }
132 return true;
133 }
134 };
135
136 } // anonymous namespace
137
RewriteDoWhile(TIntermNode * root,TSymbolTable * symbolTable)138 void RewriteDoWhile(TIntermNode *root, TSymbolTable *symbolTable)
139 {
140 DoWhileRewriter rewriter(symbolTable);
141
142 root->traverse(&rewriter);
143 }
144
145 } // namespace sh
146