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 16 ALAA::AstLoopAssignmentAnalyzer(Zone* zone, CompilationInfo* info) 17 : info_(info), zone_(zone), loop_stack_(zone) { 18 InitializeAstVisitor(info->isolate()); 19 } 20 21 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 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 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 57 void ALAA::VisitVariableDeclaration(VariableDeclaration* leaf) {} 58 void ALAA::VisitFunctionDeclaration(FunctionDeclaration* leaf) {} 59 void ALAA::VisitEmptyStatement(EmptyStatement* leaf) {} 60 void ALAA::VisitContinueStatement(ContinueStatement* leaf) {} 61 void ALAA::VisitBreakStatement(BreakStatement* leaf) {} 62 void ALAA::VisitDebuggerStatement(DebuggerStatement* leaf) {} 63 void ALAA::VisitFunctionLiteral(FunctionLiteral* leaf) {} 64 void ALAA::VisitNativeFunctionLiteral(NativeFunctionLiteral* leaf) {} 65 void ALAA::VisitVariableProxy(VariableProxy* leaf) {} 66 void ALAA::VisitLiteral(Literal* leaf) {} 67 void ALAA::VisitRegExpLiteral(RegExpLiteral* leaf) {} 68 void ALAA::VisitThisFunction(ThisFunction* leaf) {} 69 void ALAA::VisitSuperPropertyReference(SuperPropertyReference* leaf) {} 70 void ALAA::VisitSuperCallReference(SuperCallReference* leaf) {} 71 72 73 // --------------------------------------------------------------------------- 74 // -- Pass-through nodes------------------------------------------------------ 75 // --------------------------------------------------------------------------- 76 void ALAA::VisitBlock(Block* stmt) { VisitStatements(stmt->statements()); } 77 78 79 void ALAA::VisitDoExpression(DoExpression* expr) { 80 Visit(expr->block()); 81 Visit(expr->result()); 82 } 83 84 85 void ALAA::VisitExpressionStatement(ExpressionStatement* stmt) { 86 Visit(stmt->expression()); 87 } 88 89 90 void ALAA::VisitIfStatement(IfStatement* stmt) { 91 Visit(stmt->condition()); 92 Visit(stmt->then_statement()); 93 Visit(stmt->else_statement()); 94 } 95 96 97 void ALAA::VisitReturnStatement(ReturnStatement* stmt) { 98 Visit(stmt->expression()); 99 } 100 101 102 void ALAA::VisitWithStatement(WithStatement* stmt) { 103 Visit(stmt->expression()); 104 Visit(stmt->statement()); 105 } 106 107 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 117 void ALAA::VisitTryFinallyStatement(TryFinallyStatement* stmt) { 118 Visit(stmt->try_block()); 119 Visit(stmt->finally_block()); 120 } 121 122 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 134 void ALAA::VisitConditional(Conditional* e) { 135 Visit(e->condition()); 136 Visit(e->then_expression()); 137 Visit(e->else_expression()); 138 } 139 140 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 150 void ALAA::VisitArrayLiteral(ArrayLiteral* e) { VisitExpressions(e->values()); } 151 152 153 void ALAA::VisitYield(Yield* stmt) { 154 Visit(stmt->generator_object()); 155 Visit(stmt->expression()); 156 } 157 158 159 void ALAA::VisitThrow(Throw* stmt) { Visit(stmt->exception()); } 160 161 162 void ALAA::VisitProperty(Property* e) { 163 Visit(e->obj()); 164 Visit(e->key()); 165 } 166 167 168 void ALAA::VisitCall(Call* e) { 169 Visit(e->expression()); 170 VisitExpressions(e->arguments()); 171 } 172 173 174 void ALAA::VisitCallNew(CallNew* e) { 175 Visit(e->expression()); 176 VisitExpressions(e->arguments()); 177 } 178 179 180 void ALAA::VisitCallRuntime(CallRuntime* e) { 181 VisitExpressions(e->arguments()); 182 } 183 184 185 void ALAA::VisitUnaryOperation(UnaryOperation* e) { Visit(e->expression()); } 186 187 188 void ALAA::VisitBinaryOperation(BinaryOperation* e) { 189 Visit(e->left()); 190 Visit(e->right()); 191 } 192 193 194 void ALAA::VisitCompareOperation(CompareOperation* e) { 195 Visit(e->left()); 196 Visit(e->right()); 197 } 198 199 200 void ALAA::VisitSpread(Spread* e) { UNREACHABLE(); } 201 202 203 void ALAA::VisitEmptyParentheses(EmptyParentheses* e) { UNREACHABLE(); } 204 205 void ALAA::VisitGetIterator(GetIterator* e) { UNREACHABLE(); } 206 207 void ALAA::VisitCaseClause(CaseClause* cc) { 208 if (!cc->is_default()) Visit(cc->label()); 209 VisitStatements(cc->statements()); 210 } 211 212 213 void ALAA::VisitSloppyBlockFunctionStatement( 214 SloppyBlockFunctionStatement* stmt) { 215 Visit(stmt->statement()); 216 } 217 218 219 // --------------------------------------------------------------------------- 220 // -- Interesting nodes------------------------------------------------------- 221 // --------------------------------------------------------------------------- 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 230 void ALAA::VisitDoWhileStatement(DoWhileStatement* loop) { 231 Enter(loop); 232 Visit(loop->body()); 233 Visit(loop->cond()); 234 Exit(loop); 235 } 236 237 238 void ALAA::VisitWhileStatement(WhileStatement* loop) { 239 Enter(loop); 240 Visit(loop->cond()); 241 Visit(loop->body()); 242 Exit(loop); 243 } 244 245 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 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 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 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 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 293 void ALAA::VisitRewritableExpression(RewritableExpression* expr) { 294 Visit(expr->expression()); 295 } 296 297 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 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 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