1 // Copyright 2021 The Tint Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "src/transform/loop_to_for_loop.h"
16
17 #include "src/ast/break_statement.h"
18 #include "src/ast/for_loop_statement.h"
19 #include "src/program_builder.h"
20 #include "src/sem/block_statement.h"
21 #include "src/sem/function.h"
22 #include "src/sem/statement.h"
23 #include "src/sem/variable.h"
24 #include "src/utils/scoped_assignment.h"
25
26 TINT_INSTANTIATE_TYPEINFO(tint::transform::LoopToForLoop);
27
28 namespace tint {
29 namespace transform {
30 namespace {
31
IsBlockWithSingleBreak(const ast::BlockStatement * block)32 bool IsBlockWithSingleBreak(const ast::BlockStatement* block) {
33 if (block->statements.size() != 1) {
34 return false;
35 }
36 return block->statements[0]->Is<ast::BreakStatement>();
37 }
38
IsVarUsedByStmt(const sem::Info & sem,const ast::Variable * var,const ast::Statement * stmt)39 bool IsVarUsedByStmt(const sem::Info& sem,
40 const ast::Variable* var,
41 const ast::Statement* stmt) {
42 auto* var_sem = sem.Get(var);
43 for (auto* user : var_sem->Users()) {
44 if (auto* s = user->Stmt()) {
45 if (s->Declaration() == stmt) {
46 return true;
47 }
48 }
49 }
50 return false;
51 }
52
53 } // namespace
54
55 LoopToForLoop::LoopToForLoop() = default;
56
57 LoopToForLoop::~LoopToForLoop() = default;
58
Run(CloneContext & ctx,const DataMap &,DataMap &)59 void LoopToForLoop::Run(CloneContext& ctx, const DataMap&, DataMap&) {
60 ctx.ReplaceAll([&](const ast::LoopStatement* loop) -> const ast::Statement* {
61 // For loop condition is taken from the first statement in the loop.
62 // This requires an if-statement with either:
63 // * A true block with no else statements, and the true block contains a
64 // single 'break' statement.
65 // * An empty true block with a single, no-condition else statement
66 // containing a single 'break' statement.
67 // Examples:
68 // loop { if (condition) { break; } ... }
69 // loop { if (condition) {} else { break; } ... }
70 auto& stmts = loop->body->statements;
71 if (stmts.empty()) {
72 return nullptr;
73 }
74 auto* if_stmt = stmts[0]->As<ast::IfStatement>();
75 if (!if_stmt) {
76 return nullptr;
77 }
78
79 bool negate_condition = false;
80 if (IsBlockWithSingleBreak(if_stmt->body) &&
81 if_stmt->else_statements.empty()) {
82 negate_condition = true;
83 } else if (if_stmt->body->Empty() && if_stmt->else_statements.size() == 1 &&
84 if_stmt->else_statements[0]->condition == nullptr &&
85 IsBlockWithSingleBreak(if_stmt->else_statements[0]->body)) {
86 negate_condition = false;
87 } else {
88 return nullptr;
89 }
90
91 // The continuing block must be empty or contain a single, assignment or
92 // function call statement.
93 const ast::Statement* continuing = nullptr;
94 if (auto* loop_cont = loop->continuing) {
95 if (loop_cont->statements.size() != 1) {
96 return nullptr;
97 }
98
99 continuing = loop_cont->statements[0];
100 if (!continuing
101 ->IsAnyOf<ast::AssignmentStatement, ast::CallStatement>()) {
102 return nullptr;
103 }
104
105 // And the continuing statement must not use any of the variables declared
106 // in the loop body.
107 for (auto* stmt : loop->body->statements) {
108 if (auto* var_decl = stmt->As<ast::VariableDeclStatement>()) {
109 if (IsVarUsedByStmt(ctx.src->Sem(), var_decl->variable, continuing)) {
110 return nullptr;
111 }
112 }
113 }
114
115 continuing = ctx.Clone(continuing);
116 }
117
118 auto* condition = ctx.Clone(if_stmt->condition);
119 if (negate_condition) {
120 condition = ctx.dst->create<ast::UnaryOpExpression>(ast::UnaryOp::kNot,
121 condition);
122 }
123
124 ast::Statement* initializer = nullptr;
125
126 ctx.Remove(loop->body->statements, if_stmt);
127 auto* body = ctx.Clone(loop->body);
128 return ctx.dst->create<ast::ForLoopStatement>(initializer, condition,
129 continuing, body);
130 });
131
132 ctx.Clone();
133 }
134
135 } // namespace transform
136 } // namespace tint
137