Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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" |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 6 | #include "src/compiler.h" |
| 7 | #include "src/parsing/parser.h" |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 16 | : info_(info), zone_(zone), loop_stack_(zone) { |
| 17 | InitializeAstVisitor(info->isolate()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 18 | } |
| 19 | |
| 20 | |
| 21 | LoopAssignmentAnalysis* ALAA::Analyze() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 22 | LoopAssignmentAnalysis* a = new (zone_) LoopAssignmentAnalysis(zone_); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 23 | result_ = a; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 24 | VisitStatements(info()->literal()->body()); |
| 25 | result_ = nullptr; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 33 | BitVector* bits = new (zone_) BitVector(num_variables, zone_); |
| 34 | if (info()->is_osr() && info()->osr_ast_id() == loop->OsrEntryId()) |
| 35 | bits->AddAll(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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) {} |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 58 | void ALAA::VisitImportDeclaration(ImportDeclaration* leaf) {} |
| 59 | void ALAA::VisitExportDeclaration(ExportDeclaration* leaf) {} |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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) {} |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 70 | void ALAA::VisitSuperPropertyReference(SuperPropertyReference* leaf) {} |
| 71 | void ALAA::VisitSuperCallReference(SuperCallReference* leaf) {} |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 72 | |
| 73 | |
| 74 | // --------------------------------------------------------------------------- |
| 75 | // -- Pass-through nodes------------------------------------------------------ |
| 76 | // --------------------------------------------------------------------------- |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 77 | void ALAA::VisitBlock(Block* stmt) { VisitStatements(stmt->statements()); } |
| 78 | |
| 79 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 80 | void ALAA::VisitDoExpression(DoExpression* expr) { |
| 81 | Visit(expr->block()); |
| 82 | Visit(expr->result()); |
| 83 | } |
| 84 | |
| 85 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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++) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 129 | Visit(properties->at(i)->key()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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++) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 145 | Visit(properties->at(i)->key()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 201 | void ALAA::VisitSpread(Spread* e) { UNREACHABLE(); } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 202 | |
| 203 | |
| 204 | void ALAA::VisitEmptyParentheses(EmptyParentheses* e) { UNREACHABLE(); } |
| 205 | |
| 206 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 207 | void ALAA::VisitCaseClause(CaseClause* cc) { |
| 208 | if (!cc->is_default()) Visit(cc->label()); |
| 209 | VisitStatements(cc->statements()); |
| 210 | } |
| 211 | |
| 212 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 213 | void ALAA::VisitSloppyBlockFunctionStatement( |
| 214 | SloppyBlockFunctionStatement* stmt) { |
| 215 | Visit(stmt->statement()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 216 | } |
| 217 | |
| 218 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 219 | // --------------------------------------------------------------------------- |
| 220 | // -- Interesting nodes------------------------------------------------------- |
| 221 | // --------------------------------------------------------------------------- |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 266 | Visit(loop->assign_iterator()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 267 | Enter(loop); |
Ben Murdoch | c561043 | 2016-08-08 18:44:38 +0100 | [diff] [blame^] | 268 | Visit(loop->next_result()); |
| 269 | Visit(loop->result_done()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 270 | Visit(loop->assign_each()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 291 | void ALAA::VisitRewritableExpression(RewritableExpression* expr) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 292 | Visit(expr->expression()); |
| 293 | } |
| 294 | |
| 295 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 320 | } // namespace compiler |
| 321 | } // namespace internal |
| 322 | } // namespace v8 |