1 // Copyright 2010 the V8 project authors. All rights reserved. 2 // Redistribution and use in source and binary forms, with or without 3 // modification, are permitted provided that the following conditions are 4 // met: 5 // 6 // * Redistributions of source code must retain the above copyright 7 // notice, this list of conditions and the following disclaimer. 8 // * Redistributions in binary form must reproduce the above 9 // copyright notice, this list of conditions and the following 10 // disclaimer in the documentation and/or other materials provided 11 // with the distribution. 12 // * Neither the name of Google Inc. nor the names of its 13 // contributors may be used to endorse or promote products derived 14 // from this software without specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 #include "v8.h" 29 30 #include "data-flow.h" 31 32 namespace v8 { 33 namespace internal { 34 35 36 void AstLabeler::Label(CompilationInfo* info) { 37 info_ = info; 38 VisitStatements(info_->function()->body()); 39 } 40 41 42 void AstLabeler::VisitStatements(ZoneList<Statement*>* stmts) { 43 for (int i = 0, len = stmts->length(); i < len; i++) { 44 Visit(stmts->at(i)); 45 } 46 } 47 48 49 void AstLabeler::VisitDeclarations(ZoneList<Declaration*>* decls) { 50 UNREACHABLE(); 51 } 52 53 54 void AstLabeler::VisitBlock(Block* stmt) { 55 VisitStatements(stmt->statements()); 56 } 57 58 59 void AstLabeler::VisitExpressionStatement( 60 ExpressionStatement* stmt) { 61 Visit(stmt->expression()); 62 } 63 64 65 void AstLabeler::VisitEmptyStatement(EmptyStatement* stmt) { 66 // Do nothing. 67 } 68 69 70 void AstLabeler::VisitIfStatement(IfStatement* stmt) { 71 UNREACHABLE(); 72 } 73 74 75 void AstLabeler::VisitContinueStatement(ContinueStatement* stmt) { 76 UNREACHABLE(); 77 } 78 79 80 void AstLabeler::VisitBreakStatement(BreakStatement* stmt) { 81 UNREACHABLE(); 82 } 83 84 85 void AstLabeler::VisitReturnStatement(ReturnStatement* stmt) { 86 UNREACHABLE(); 87 } 88 89 90 void AstLabeler::VisitWithEnterStatement( 91 WithEnterStatement* stmt) { 92 UNREACHABLE(); 93 } 94 95 96 void AstLabeler::VisitWithExitStatement(WithExitStatement* stmt) { 97 UNREACHABLE(); 98 } 99 100 101 void AstLabeler::VisitSwitchStatement(SwitchStatement* stmt) { 102 UNREACHABLE(); 103 } 104 105 106 void AstLabeler::VisitDoWhileStatement(DoWhileStatement* stmt) { 107 UNREACHABLE(); 108 } 109 110 111 void AstLabeler::VisitWhileStatement(WhileStatement* stmt) { 112 UNREACHABLE(); 113 } 114 115 116 void AstLabeler::VisitForStatement(ForStatement* stmt) { 117 UNREACHABLE(); 118 } 119 120 121 void AstLabeler::VisitForInStatement(ForInStatement* stmt) { 122 UNREACHABLE(); 123 } 124 125 126 void AstLabeler::VisitTryCatchStatement(TryCatchStatement* stmt) { 127 UNREACHABLE(); 128 } 129 130 131 void AstLabeler::VisitTryFinallyStatement( 132 TryFinallyStatement* stmt) { 133 UNREACHABLE(); 134 } 135 136 137 void AstLabeler::VisitDebuggerStatement( 138 DebuggerStatement* stmt) { 139 UNREACHABLE(); 140 } 141 142 143 void AstLabeler::VisitFunctionLiteral(FunctionLiteral* expr) { 144 UNREACHABLE(); 145 } 146 147 148 void AstLabeler::VisitFunctionBoilerplateLiteral( 149 FunctionBoilerplateLiteral* expr) { 150 UNREACHABLE(); 151 } 152 153 154 void AstLabeler::VisitConditional(Conditional* expr) { 155 UNREACHABLE(); 156 } 157 158 159 void AstLabeler::VisitSlot(Slot* expr) { 160 UNREACHABLE(); 161 } 162 163 164 void AstLabeler::VisitVariableProxy(VariableProxy* expr) { 165 expr->set_num(next_number_++); 166 Variable* var = expr->var(); 167 if (var->is_global() && !var->is_this()) { 168 info_->set_has_globals(true); 169 } 170 } 171 172 173 void AstLabeler::VisitLiteral(Literal* expr) { 174 UNREACHABLE(); 175 } 176 177 178 void AstLabeler::VisitRegExpLiteral(RegExpLiteral* expr) { 179 UNREACHABLE(); 180 } 181 182 183 void AstLabeler::VisitObjectLiteral(ObjectLiteral* expr) { 184 UNREACHABLE(); 185 } 186 187 188 void AstLabeler::VisitArrayLiteral(ArrayLiteral* expr) { 189 UNREACHABLE(); 190 } 191 192 193 void AstLabeler::VisitCatchExtensionObject( 194 CatchExtensionObject* expr) { 195 UNREACHABLE(); 196 } 197 198 199 void AstLabeler::VisitAssignment(Assignment* expr) { 200 Property* prop = expr->target()->AsProperty(); 201 ASSERT(prop != NULL); 202 ASSERT(prop->key()->IsPropertyName()); 203 VariableProxy* proxy = prop->obj()->AsVariableProxy(); 204 USE(proxy); 205 ASSERT(proxy != NULL && proxy->var()->is_this()); 206 info()->set_has_this_properties(true); 207 Visit(expr->value()); 208 expr->set_num(next_number_++); 209 } 210 211 212 void AstLabeler::VisitThrow(Throw* expr) { 213 UNREACHABLE(); 214 } 215 216 217 void AstLabeler::VisitProperty(Property* expr) { 218 ASSERT(expr->key()->IsPropertyName()); 219 VariableProxy* proxy = expr->obj()->AsVariableProxy(); 220 USE(proxy); 221 ASSERT(proxy != NULL && proxy->var()->is_this()); 222 info()->set_has_this_properties(true); 223 expr->set_num(next_number_++); 224 } 225 226 227 void AstLabeler::VisitCall(Call* expr) { 228 UNREACHABLE(); 229 } 230 231 232 void AstLabeler::VisitCallNew(CallNew* expr) { 233 UNREACHABLE(); 234 } 235 236 237 void AstLabeler::VisitCallRuntime(CallRuntime* expr) { 238 UNREACHABLE(); 239 } 240 241 242 void AstLabeler::VisitUnaryOperation(UnaryOperation* expr) { 243 UNREACHABLE(); 244 } 245 246 247 void AstLabeler::VisitCountOperation(CountOperation* expr) { 248 UNREACHABLE(); 249 } 250 251 252 void AstLabeler::VisitBinaryOperation(BinaryOperation* expr) { 253 Visit(expr->left()); 254 Visit(expr->right()); 255 expr->set_num(next_number_++); 256 } 257 258 259 void AstLabeler::VisitCompareOperation(CompareOperation* expr) { 260 UNREACHABLE(); 261 } 262 263 264 void AstLabeler::VisitThisFunction(ThisFunction* expr) { 265 UNREACHABLE(); 266 } 267 268 269 void AstLabeler::VisitDeclaration(Declaration* decl) { 270 UNREACHABLE(); 271 } 272 273 274 ZoneList<Expression*>* VarUseMap::Lookup(Variable* var) { 275 HashMap::Entry* entry = HashMap::Lookup(var, var->name()->Hash(), true); 276 if (entry->value == NULL) { 277 entry->value = new ZoneList<Expression*>(1); 278 } 279 return reinterpret_cast<ZoneList<Expression*>*>(entry->value); 280 } 281 282 283 void LivenessAnalyzer::Analyze(FunctionLiteral* fun) { 284 // Process the function body. 285 VisitStatements(fun->body()); 286 287 // All variables are implicitly defined at the function start. 288 // Record a definition of all variables live at function entry. 289 for (HashMap::Entry* p = live_vars_.Start(); 290 p != NULL; 291 p = live_vars_.Next(p)) { 292 Variable* var = reinterpret_cast<Variable*>(p->key); 293 RecordDef(var, fun); 294 } 295 } 296 297 298 void LivenessAnalyzer::VisitStatements(ZoneList<Statement*>* stmts) { 299 // Visit statements right-to-left. 300 for (int i = stmts->length() - 1; i >= 0; i--) { 301 Visit(stmts->at(i)); 302 } 303 } 304 305 306 void LivenessAnalyzer::RecordUse(Variable* var, Expression* expr) { 307 ASSERT(var->is_global() || var->is_this()); 308 ZoneList<Expression*>* uses = live_vars_.Lookup(var); 309 uses->Add(expr); 310 } 311 312 313 void LivenessAnalyzer::RecordDef(Variable* var, Expression* expr) { 314 ASSERT(var->is_global() || var->is_this()); 315 316 // We do not support other expressions that can define variables. 317 ASSERT(expr->AsFunctionLiteral() != NULL); 318 319 // Add the variable to the list of defined variables. 320 if (expr->defined_vars() == NULL) { 321 expr->set_defined_vars(new ZoneList<DefinitionInfo*>(1)); 322 } 323 DefinitionInfo* def = new DefinitionInfo(); 324 expr->AsFunctionLiteral()->defined_vars()->Add(def); 325 326 // Compute the last use of the definition. The variable uses are 327 // inserted in reversed evaluation order. The first element 328 // in the list of live uses is the last use. 329 ZoneList<Expression*>* uses = live_vars_.Lookup(var); 330 while (uses->length() > 0) { 331 Expression* use_site = uses->RemoveLast(); 332 use_site->set_var_def(def); 333 if (uses->length() == 0) { 334 def->set_last_use(use_site); 335 } 336 } 337 } 338 339 340 // Visitor functions for live variable analysis. 341 void LivenessAnalyzer::VisitDeclaration(Declaration* decl) { 342 UNREACHABLE(); 343 } 344 345 346 void LivenessAnalyzer::VisitBlock(Block* stmt) { 347 VisitStatements(stmt->statements()); 348 } 349 350 351 void LivenessAnalyzer::VisitExpressionStatement( 352 ExpressionStatement* stmt) { 353 Visit(stmt->expression()); 354 } 355 356 357 void LivenessAnalyzer::VisitEmptyStatement(EmptyStatement* stmt) { 358 // Do nothing. 359 } 360 361 362 void LivenessAnalyzer::VisitIfStatement(IfStatement* stmt) { 363 UNREACHABLE(); 364 } 365 366 367 void LivenessAnalyzer::VisitContinueStatement(ContinueStatement* stmt) { 368 UNREACHABLE(); 369 } 370 371 372 void LivenessAnalyzer::VisitBreakStatement(BreakStatement* stmt) { 373 UNREACHABLE(); 374 } 375 376 377 void LivenessAnalyzer::VisitReturnStatement(ReturnStatement* stmt) { 378 UNREACHABLE(); 379 } 380 381 382 void LivenessAnalyzer::VisitWithEnterStatement( 383 WithEnterStatement* stmt) { 384 UNREACHABLE(); 385 } 386 387 388 void LivenessAnalyzer::VisitWithExitStatement(WithExitStatement* stmt) { 389 UNREACHABLE(); 390 } 391 392 393 void LivenessAnalyzer::VisitSwitchStatement(SwitchStatement* stmt) { 394 UNREACHABLE(); 395 } 396 397 398 void LivenessAnalyzer::VisitDoWhileStatement(DoWhileStatement* stmt) { 399 UNREACHABLE(); 400 } 401 402 403 void LivenessAnalyzer::VisitWhileStatement(WhileStatement* stmt) { 404 UNREACHABLE(); 405 } 406 407 408 void LivenessAnalyzer::VisitForStatement(ForStatement* stmt) { 409 UNREACHABLE(); 410 } 411 412 413 void LivenessAnalyzer::VisitForInStatement(ForInStatement* stmt) { 414 UNREACHABLE(); 415 } 416 417 418 void LivenessAnalyzer::VisitTryCatchStatement(TryCatchStatement* stmt) { 419 UNREACHABLE(); 420 } 421 422 423 void LivenessAnalyzer::VisitTryFinallyStatement( 424 TryFinallyStatement* stmt) { 425 UNREACHABLE(); 426 } 427 428 429 void LivenessAnalyzer::VisitDebuggerStatement( 430 DebuggerStatement* stmt) { 431 UNREACHABLE(); 432 } 433 434 435 void LivenessAnalyzer::VisitFunctionLiteral(FunctionLiteral* expr) { 436 UNREACHABLE(); 437 } 438 439 440 void LivenessAnalyzer::VisitFunctionBoilerplateLiteral( 441 FunctionBoilerplateLiteral* expr) { 442 UNREACHABLE(); 443 } 444 445 446 void LivenessAnalyzer::VisitConditional(Conditional* expr) { 447 UNREACHABLE(); 448 } 449 450 451 void LivenessAnalyzer::VisitSlot(Slot* expr) { 452 UNREACHABLE(); 453 } 454 455 456 void LivenessAnalyzer::VisitVariableProxy(VariableProxy* expr) { 457 Variable* var = expr->var(); 458 ASSERT(var->is_global()); 459 ASSERT(!var->is_this()); 460 RecordUse(var, expr); 461 } 462 463 464 void LivenessAnalyzer::VisitLiteral(Literal* expr) { 465 UNREACHABLE(); 466 } 467 468 469 void LivenessAnalyzer::VisitRegExpLiteral(RegExpLiteral* expr) { 470 UNREACHABLE(); 471 } 472 473 474 void LivenessAnalyzer::VisitObjectLiteral(ObjectLiteral* expr) { 475 UNREACHABLE(); 476 } 477 478 479 void LivenessAnalyzer::VisitArrayLiteral(ArrayLiteral* expr) { 480 UNREACHABLE(); 481 } 482 483 484 void LivenessAnalyzer::VisitCatchExtensionObject( 485 CatchExtensionObject* expr) { 486 UNREACHABLE(); 487 } 488 489 490 void LivenessAnalyzer::VisitAssignment(Assignment* expr) { 491 Property* prop = expr->target()->AsProperty(); 492 ASSERT(prop != NULL); 493 ASSERT(prop->key()->IsPropertyName()); 494 VariableProxy* proxy = prop->obj()->AsVariableProxy(); 495 ASSERT(proxy != NULL && proxy->var()->is_this()); 496 497 // Record use of this at the assignment node. Assignments to 498 // this-properties are treated like unary operations. 499 RecordUse(proxy->var(), expr); 500 501 // Visit right-hand side. 502 Visit(expr->value()); 503 } 504 505 506 void LivenessAnalyzer::VisitThrow(Throw* expr) { 507 UNREACHABLE(); 508 } 509 510 511 void LivenessAnalyzer::VisitProperty(Property* expr) { 512 ASSERT(expr->key()->IsPropertyName()); 513 VariableProxy* proxy = expr->obj()->AsVariableProxy(); 514 ASSERT(proxy != NULL && proxy->var()->is_this()); 515 RecordUse(proxy->var(), expr); 516 } 517 518 519 void LivenessAnalyzer::VisitCall(Call* expr) { 520 UNREACHABLE(); 521 } 522 523 524 void LivenessAnalyzer::VisitCallNew(CallNew* expr) { 525 UNREACHABLE(); 526 } 527 528 529 void LivenessAnalyzer::VisitCallRuntime(CallRuntime* expr) { 530 UNREACHABLE(); 531 } 532 533 534 void LivenessAnalyzer::VisitUnaryOperation(UnaryOperation* expr) { 535 UNREACHABLE(); 536 } 537 538 539 void LivenessAnalyzer::VisitCountOperation(CountOperation* expr) { 540 UNREACHABLE(); 541 } 542 543 544 void LivenessAnalyzer::VisitBinaryOperation(BinaryOperation* expr) { 545 // Visit child nodes in reverse evaluation order. 546 Visit(expr->right()); 547 Visit(expr->left()); 548 } 549 550 551 void LivenessAnalyzer::VisitCompareOperation(CompareOperation* expr) { 552 UNREACHABLE(); 553 } 554 555 556 void LivenessAnalyzer::VisitThisFunction(ThisFunction* expr) { 557 UNREACHABLE(); 558 } 559 560 561 } } // namespace v8::internal 562