Home | History | Annotate | Download | only in src 
      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