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