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/compiler.h" 7 #include "src/parsing/parser.h" 8 9 namespace v8 { 10 namespace internal { 11 namespace compiler { 12 13 typedef class AstLoopAssignmentAnalyzer ALAA; // for code shortitude. 14 15 ALAA::AstLoopAssignmentAnalyzer(Zone* zone, CompilationInfo* info) 16 : info_(info), zone_(zone), loop_stack_(zone) { 17 InitializeAstVisitor(info->isolate()); 18 } 19 20 21 LoopAssignmentAnalysis* 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 30 void 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 40 void 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 56 void ALAA::VisitVariableDeclaration(VariableDeclaration* leaf) {} 57 void ALAA::VisitFunctionDeclaration(FunctionDeclaration* leaf) {} 58 void ALAA::VisitImportDeclaration(ImportDeclaration* leaf) {} 59 void ALAA::VisitExportDeclaration(ExportDeclaration* leaf) {} 60 void ALAA::VisitEmptyStatement(EmptyStatement* leaf) {} 61 void ALAA::VisitContinueStatement(ContinueStatement* leaf) {} 62 void ALAA::VisitBreakStatement(BreakStatement* leaf) {} 63 void ALAA::VisitDebuggerStatement(DebuggerStatement* leaf) {} 64 void ALAA::VisitFunctionLiteral(FunctionLiteral* leaf) {} 65 void ALAA::VisitNativeFunctionLiteral(NativeFunctionLiteral* leaf) {} 66 void ALAA::VisitVariableProxy(VariableProxy* leaf) {} 67 void ALAA::VisitLiteral(Literal* leaf) {} 68 void ALAA::VisitRegExpLiteral(RegExpLiteral* leaf) {} 69 void ALAA::VisitThisFunction(ThisFunction* leaf) {} 70 void ALAA::VisitSuperPropertyReference(SuperPropertyReference* leaf) {} 71 void ALAA::VisitSuperCallReference(SuperCallReference* leaf) {} 72 73 74 // --------------------------------------------------------------------------- 75 // -- Pass-through nodes------------------------------------------------------ 76 // --------------------------------------------------------------------------- 77 void ALAA::VisitBlock(Block* stmt) { VisitStatements(stmt->statements()); } 78 79 80 void ALAA::VisitDoExpression(DoExpression* expr) { 81 Visit(expr->block()); 82 Visit(expr->result()); 83 } 84 85 86 void ALAA::VisitExpressionStatement(ExpressionStatement* stmt) { 87 Visit(stmt->expression()); 88 } 89 90 91 void ALAA::VisitIfStatement(IfStatement* stmt) { 92 Visit(stmt->condition()); 93 Visit(stmt->then_statement()); 94 Visit(stmt->else_statement()); 95 } 96 97 98 void ALAA::VisitReturnStatement(ReturnStatement* stmt) { 99 Visit(stmt->expression()); 100 } 101 102 103 void ALAA::VisitWithStatement(WithStatement* stmt) { 104 Visit(stmt->expression()); 105 Visit(stmt->statement()); 106 } 107 108 109 void ALAA::VisitSwitchStatement(SwitchStatement* stmt) { 110 Visit(stmt->tag()); 111 ZoneList<CaseClause*>* clauses = stmt->cases(); 112 for (int i = 0; i < clauses->length(); i++) { 113 Visit(clauses->at(i)); 114 } 115 } 116 117 118 void ALAA::VisitTryFinallyStatement(TryFinallyStatement* stmt) { 119 Visit(stmt->try_block()); 120 Visit(stmt->finally_block()); 121 } 122 123 124 void ALAA::VisitClassLiteral(ClassLiteral* e) { 125 VisitIfNotNull(e->extends()); 126 VisitIfNotNull(e->constructor()); 127 ZoneList<ObjectLiteralProperty*>* properties = e->properties(); 128 for (int i = 0; i < properties->length(); i++) { 129 Visit(properties->at(i)->key()); 130 Visit(properties->at(i)->value()); 131 } 132 } 133 134 135 void ALAA::VisitConditional(Conditional* e) { 136 Visit(e->condition()); 137 Visit(e->then_expression()); 138 Visit(e->else_expression()); 139 } 140 141 142 void ALAA::VisitObjectLiteral(ObjectLiteral* e) { 143 ZoneList<ObjectLiteralProperty*>* properties = e->properties(); 144 for (int i = 0; i < properties->length(); i++) { 145 Visit(properties->at(i)->key()); 146 Visit(properties->at(i)->value()); 147 } 148 } 149 150 151 void ALAA::VisitArrayLiteral(ArrayLiteral* e) { VisitExpressions(e->values()); } 152 153 154 void ALAA::VisitYield(Yield* stmt) { 155 Visit(stmt->generator_object()); 156 Visit(stmt->expression()); 157 } 158 159 160 void ALAA::VisitThrow(Throw* stmt) { Visit(stmt->exception()); } 161 162 163 void ALAA::VisitProperty(Property* e) { 164 Visit(e->obj()); 165 Visit(e->key()); 166 } 167 168 169 void ALAA::VisitCall(Call* e) { 170 Visit(e->expression()); 171 VisitExpressions(e->arguments()); 172 } 173 174 175 void ALAA::VisitCallNew(CallNew* e) { 176 Visit(e->expression()); 177 VisitExpressions(e->arguments()); 178 } 179 180 181 void ALAA::VisitCallRuntime(CallRuntime* e) { 182 VisitExpressions(e->arguments()); 183 } 184 185 186 void ALAA::VisitUnaryOperation(UnaryOperation* e) { Visit(e->expression()); } 187 188 189 void ALAA::VisitBinaryOperation(BinaryOperation* e) { 190 Visit(e->left()); 191 Visit(e->right()); 192 } 193 194 195 void ALAA::VisitCompareOperation(CompareOperation* e) { 196 Visit(e->left()); 197 Visit(e->right()); 198 } 199 200 201 void ALAA::VisitSpread(Spread* e) { UNREACHABLE(); } 202 203 204 void ALAA::VisitEmptyParentheses(EmptyParentheses* e) { UNREACHABLE(); } 205 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 Enter(loop); 258 Visit(loop->each()); 259 Visit(loop->subject()); 260 Visit(loop->body()); 261 Exit(loop); 262 } 263 264 265 void 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 276 void 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 284 void ALAA::VisitCountOperation(CountOperation* e) { 285 Expression* l = e->expression(); 286 Visit(l); 287 if (l->IsVariableProxy()) AnalyzeAssignment(l->AsVariableProxy()->var()); 288 } 289 290 291 void ALAA::VisitRewritableExpression(RewritableExpression* expr) { 292 Visit(expr->expression()); 293 } 294 295 296 void ALAA::AnalyzeAssignment(Variable* var) { 297 if (!loop_stack_.empty() && var->IsStackAllocated()) { 298 loop_stack_.back()->Add(GetVariableIndex(info()->scope(), var)); 299 } 300 } 301 302 303 int ALAA::GetVariableIndex(Scope* scope, Variable* var) { 304 CHECK(var->IsStackAllocated()); 305 if (var->is_this()) return 0; 306 if (var->IsParameter()) return 1 + var->index(); 307 return 1 + scope->num_parameters() + var->index(); 308 } 309 310 311 int LoopAssignmentAnalysis::GetAssignmentCountForTesting(Scope* scope, 312 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