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