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