1 // Copyright 2014 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/compiler/ast-loop-assignment-analyzer.h"
6 #include "src/ast/scopes.h"
7 #include "src/compilation-info.h"
8 #include "src/objects-inl.h"
9
10 namespace v8 {
11 namespace internal {
12 namespace compiler {
13
14 typedef class AstLoopAssignmentAnalyzer ALAA; // for code shortitude.
15
AstLoopAssignmentAnalyzer(Zone * zone,CompilationInfo * info)16 ALAA::AstLoopAssignmentAnalyzer(Zone* zone, CompilationInfo* info)
17 : info_(info), zone_(zone), loop_stack_(zone) {
18 InitializeAstVisitor(info->isolate());
19 }
20
21
Analyze()22 LoopAssignmentAnalysis* ALAA::Analyze() {
23 LoopAssignmentAnalysis* a = new (zone_) LoopAssignmentAnalysis(zone_);
24 result_ = a;
25 VisitStatements(info()->literal()->body());
26 result_ = nullptr;
27 return a;
28 }
29
30
Enter(IterationStatement * loop)31 void ALAA::Enter(IterationStatement* loop) {
32 int num_variables = 1 + info()->scope()->num_parameters() +
33 info()->scope()->num_stack_slots();
34 BitVector* bits = new (zone_) BitVector(num_variables, zone_);
35 if (info()->is_osr() && info()->osr_ast_id() == loop->OsrEntryId())
36 bits->AddAll();
37 loop_stack_.push_back(bits);
38 }
39
40
Exit(IterationStatement * loop)41 void ALAA::Exit(IterationStatement* loop) {
42 DCHECK(loop_stack_.size() > 0);
43 BitVector* bits = loop_stack_.back();
44 loop_stack_.pop_back();
45 if (!loop_stack_.empty()) {
46 loop_stack_.back()->Union(*bits);
47 }
48 result_->list_.push_back(
49 std::pair<IterationStatement*, BitVector*>(loop, bits));
50 }
51
52
53 // ---------------------------------------------------------------------------
54 // -- Leaf nodes -------------------------------------------------------------
55 // ---------------------------------------------------------------------------
56
VisitVariableDeclaration(VariableDeclaration * leaf)57 void ALAA::VisitVariableDeclaration(VariableDeclaration* leaf) {}
VisitFunctionDeclaration(FunctionDeclaration * leaf)58 void ALAA::VisitFunctionDeclaration(FunctionDeclaration* leaf) {}
VisitEmptyStatement(EmptyStatement * leaf)59 void ALAA::VisitEmptyStatement(EmptyStatement* leaf) {}
VisitContinueStatement(ContinueStatement * leaf)60 void ALAA::VisitContinueStatement(ContinueStatement* leaf) {}
VisitBreakStatement(BreakStatement * leaf)61 void ALAA::VisitBreakStatement(BreakStatement* leaf) {}
VisitDebuggerStatement(DebuggerStatement * leaf)62 void ALAA::VisitDebuggerStatement(DebuggerStatement* leaf) {}
VisitFunctionLiteral(FunctionLiteral * leaf)63 void ALAA::VisitFunctionLiteral(FunctionLiteral* leaf) {}
VisitNativeFunctionLiteral(NativeFunctionLiteral * leaf)64 void ALAA::VisitNativeFunctionLiteral(NativeFunctionLiteral* leaf) {}
VisitVariableProxy(VariableProxy * leaf)65 void ALAA::VisitVariableProxy(VariableProxy* leaf) {}
VisitLiteral(Literal * leaf)66 void ALAA::VisitLiteral(Literal* leaf) {}
VisitRegExpLiteral(RegExpLiteral * leaf)67 void ALAA::VisitRegExpLiteral(RegExpLiteral* leaf) {}
VisitThisFunction(ThisFunction * leaf)68 void ALAA::VisitThisFunction(ThisFunction* leaf) {}
VisitSuperPropertyReference(SuperPropertyReference * leaf)69 void ALAA::VisitSuperPropertyReference(SuperPropertyReference* leaf) {}
VisitSuperCallReference(SuperCallReference * leaf)70 void ALAA::VisitSuperCallReference(SuperCallReference* leaf) {}
71
72
73 // ---------------------------------------------------------------------------
74 // -- Pass-through nodes------------------------------------------------------
75 // ---------------------------------------------------------------------------
VisitBlock(Block * stmt)76 void ALAA::VisitBlock(Block* stmt) { VisitStatements(stmt->statements()); }
77
78
VisitDoExpression(DoExpression * expr)79 void ALAA::VisitDoExpression(DoExpression* expr) {
80 Visit(expr->block());
81 Visit(expr->result());
82 }
83
84
VisitExpressionStatement(ExpressionStatement * stmt)85 void ALAA::VisitExpressionStatement(ExpressionStatement* stmt) {
86 Visit(stmt->expression());
87 }
88
89
VisitIfStatement(IfStatement * stmt)90 void ALAA::VisitIfStatement(IfStatement* stmt) {
91 Visit(stmt->condition());
92 Visit(stmt->then_statement());
93 Visit(stmt->else_statement());
94 }
95
96
VisitReturnStatement(ReturnStatement * stmt)97 void ALAA::VisitReturnStatement(ReturnStatement* stmt) {
98 Visit(stmt->expression());
99 }
100
101
VisitWithStatement(WithStatement * stmt)102 void ALAA::VisitWithStatement(WithStatement* stmt) {
103 Visit(stmt->expression());
104 Visit(stmt->statement());
105 }
106
107
VisitSwitchStatement(SwitchStatement * stmt)108 void ALAA::VisitSwitchStatement(SwitchStatement* stmt) {
109 Visit(stmt->tag());
110 ZoneList<CaseClause*>* clauses = stmt->cases();
111 for (int i = 0; i < clauses->length(); i++) {
112 Visit(clauses->at(i));
113 }
114 }
115
116
VisitTryFinallyStatement(TryFinallyStatement * stmt)117 void ALAA::VisitTryFinallyStatement(TryFinallyStatement* stmt) {
118 Visit(stmt->try_block());
119 Visit(stmt->finally_block());
120 }
121
122
VisitClassLiteral(ClassLiteral * e)123 void ALAA::VisitClassLiteral(ClassLiteral* e) {
124 VisitIfNotNull(e->extends());
125 VisitIfNotNull(e->constructor());
126 ZoneList<ClassLiteralProperty*>* properties = e->properties();
127 for (int i = 0; i < properties->length(); i++) {
128 Visit(properties->at(i)->key());
129 Visit(properties->at(i)->value());
130 }
131 }
132
133
VisitConditional(Conditional * e)134 void ALAA::VisitConditional(Conditional* e) {
135 Visit(e->condition());
136 Visit(e->then_expression());
137 Visit(e->else_expression());
138 }
139
140
VisitObjectLiteral(ObjectLiteral * e)141 void ALAA::VisitObjectLiteral(ObjectLiteral* e) {
142 ZoneList<ObjectLiteralProperty*>* properties = e->properties();
143 for (int i = 0; i < properties->length(); i++) {
144 Visit(properties->at(i)->key());
145 Visit(properties->at(i)->value());
146 }
147 }
148
149
VisitArrayLiteral(ArrayLiteral * e)150 void ALAA::VisitArrayLiteral(ArrayLiteral* e) { VisitExpressions(e->values()); }
151
152
VisitYield(Yield * stmt)153 void ALAA::VisitYield(Yield* stmt) {
154 Visit(stmt->generator_object());
155 Visit(stmt->expression());
156 }
157
158
VisitThrow(Throw * stmt)159 void ALAA::VisitThrow(Throw* stmt) { Visit(stmt->exception()); }
160
161
VisitProperty(Property * e)162 void ALAA::VisitProperty(Property* e) {
163 Visit(e->obj());
164 Visit(e->key());
165 }
166
167
VisitCall(Call * e)168 void ALAA::VisitCall(Call* e) {
169 Visit(e->expression());
170 VisitExpressions(e->arguments());
171 }
172
173
VisitCallNew(CallNew * e)174 void ALAA::VisitCallNew(CallNew* e) {
175 Visit(e->expression());
176 VisitExpressions(e->arguments());
177 }
178
179
VisitCallRuntime(CallRuntime * e)180 void ALAA::VisitCallRuntime(CallRuntime* e) {
181 VisitExpressions(e->arguments());
182 }
183
184
VisitUnaryOperation(UnaryOperation * e)185 void ALAA::VisitUnaryOperation(UnaryOperation* e) { Visit(e->expression()); }
186
187
VisitBinaryOperation(BinaryOperation * e)188 void ALAA::VisitBinaryOperation(BinaryOperation* e) {
189 Visit(e->left());
190 Visit(e->right());
191 }
192
193
VisitCompareOperation(CompareOperation * e)194 void ALAA::VisitCompareOperation(CompareOperation* e) {
195 Visit(e->left());
196 Visit(e->right());
197 }
198
199
VisitSpread(Spread * e)200 void ALAA::VisitSpread(Spread* e) { UNREACHABLE(); }
201
202
VisitEmptyParentheses(EmptyParentheses * e)203 void ALAA::VisitEmptyParentheses(EmptyParentheses* e) { UNREACHABLE(); }
204
VisitGetIterator(GetIterator * e)205 void ALAA::VisitGetIterator(GetIterator* e) { UNREACHABLE(); }
206
VisitCaseClause(CaseClause * cc)207 void ALAA::VisitCaseClause(CaseClause* cc) {
208 if (!cc->is_default()) Visit(cc->label());
209 VisitStatements(cc->statements());
210 }
211
212
VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement * stmt)213 void ALAA::VisitSloppyBlockFunctionStatement(
214 SloppyBlockFunctionStatement* stmt) {
215 Visit(stmt->statement());
216 }
217
218
219 // ---------------------------------------------------------------------------
220 // -- Interesting nodes-------------------------------------------------------
221 // ---------------------------------------------------------------------------
VisitTryCatchStatement(TryCatchStatement * stmt)222 void ALAA::VisitTryCatchStatement(TryCatchStatement* stmt) {
223 Visit(stmt->try_block());
224 Visit(stmt->catch_block());
225 // TODO(turbofan): are catch variables well-scoped?
226 AnalyzeAssignment(stmt->variable());
227 }
228
229
VisitDoWhileStatement(DoWhileStatement * loop)230 void ALAA::VisitDoWhileStatement(DoWhileStatement* loop) {
231 Enter(loop);
232 Visit(loop->body());
233 Visit(loop->cond());
234 Exit(loop);
235 }
236
237
VisitWhileStatement(WhileStatement * loop)238 void ALAA::VisitWhileStatement(WhileStatement* loop) {
239 Enter(loop);
240 Visit(loop->cond());
241 Visit(loop->body());
242 Exit(loop);
243 }
244
245
VisitForStatement(ForStatement * loop)246 void ALAA::VisitForStatement(ForStatement* loop) {
247 VisitIfNotNull(loop->init());
248 Enter(loop);
249 VisitIfNotNull(loop->cond());
250 Visit(loop->body());
251 VisitIfNotNull(loop->next());
252 Exit(loop);
253 }
254
255
VisitForInStatement(ForInStatement * loop)256 void ALAA::VisitForInStatement(ForInStatement* loop) {
257 Expression* l = loop->each();
258 Enter(loop);
259 Visit(l);
260 Visit(loop->subject());
261 Visit(loop->body());
262 if (l->IsVariableProxy()) AnalyzeAssignment(l->AsVariableProxy()->var());
263 Exit(loop);
264 }
265
266
VisitForOfStatement(ForOfStatement * loop)267 void ALAA::VisitForOfStatement(ForOfStatement* loop) {
268 Visit(loop->assign_iterator());
269 Enter(loop);
270 Visit(loop->next_result());
271 Visit(loop->result_done());
272 Visit(loop->assign_each());
273 Visit(loop->body());
274 Exit(loop);
275 }
276
277
VisitAssignment(Assignment * stmt)278 void ALAA::VisitAssignment(Assignment* stmt) {
279 Expression* l = stmt->target();
280 Visit(l);
281 Visit(stmt->value());
282 if (l->IsVariableProxy()) AnalyzeAssignment(l->AsVariableProxy()->var());
283 }
284
285
VisitCountOperation(CountOperation * e)286 void ALAA::VisitCountOperation(CountOperation* e) {
287 Expression* l = e->expression();
288 Visit(l);
289 if (l->IsVariableProxy()) AnalyzeAssignment(l->AsVariableProxy()->var());
290 }
291
292
VisitRewritableExpression(RewritableExpression * expr)293 void ALAA::VisitRewritableExpression(RewritableExpression* expr) {
294 Visit(expr->expression());
295 }
296
297
AnalyzeAssignment(Variable * var)298 void ALAA::AnalyzeAssignment(Variable* var) {
299 if (!loop_stack_.empty() && var->IsStackAllocated()) {
300 loop_stack_.back()->Add(GetVariableIndex(info()->scope(), var));
301 }
302 }
303
GetVariableIndex(DeclarationScope * scope,Variable * var)304 int ALAA::GetVariableIndex(DeclarationScope* scope, Variable* var) {
305 CHECK(var->IsStackAllocated());
306 if (var->is_this()) return 0;
307 if (var->IsParameter()) return 1 + var->index();
308 return 1 + scope->num_parameters() + var->index();
309 }
310
GetAssignmentCountForTesting(DeclarationScope * scope,Variable * var)311 int LoopAssignmentAnalysis::GetAssignmentCountForTesting(
312 DeclarationScope* scope, Variable* var) {
313 int count = 0;
314 int var_index = AstLoopAssignmentAnalyzer::GetVariableIndex(scope, var);
315 for (size_t i = 0; i < list_.size(); i++) {
316 if (list_[i].second->Contains(var_index)) count++;
317 }
318 return count;
319 }
320 } // namespace compiler
321 } // namespace internal
322 } // namespace v8
323