1 // Copyright 2006-2008 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 "ast.h" 31 #include "scopes.h" 32 #include "usage-analyzer.h" 33 34 namespace v8 { 35 namespace internal { 36 37 // Weight boundaries 38 static const int MinWeight = 1; 39 static const int MaxWeight = 1000000; 40 static const int InitialWeight = 100; 41 42 43 class UsageComputer: public AstVisitor { 44 public: 45 static bool Traverse(AstNode* node); 46 47 // AST node visit functions. 48 #define DECLARE_VISIT(type) void Visit##type(type* node); 49 AST_NODE_LIST(DECLARE_VISIT) 50 #undef DECLARE_VISIT 51 52 void VisitVariable(Variable* var); 53 54 private: 55 int weight_; 56 bool is_write_; 57 58 UsageComputer(int weight, bool is_write); 59 virtual ~UsageComputer(); 60 61 // Helper functions 62 void RecordUses(UseCount* uses); 63 void Read(Expression* x); 64 void Write(Expression* x); 65 void ReadList(ZoneList<Expression*>* list); 66 void ReadList(ZoneList<ObjectLiteral::Property*>* list); 67 68 friend class WeightScaler; 69 }; 70 71 72 class WeightScaler BASE_EMBEDDED { 73 public: 74 WeightScaler(UsageComputer* uc, float scale); 75 ~WeightScaler(); 76 77 private: 78 UsageComputer* uc_; 79 int old_weight_; 80 }; 81 82 83 // ---------------------------------------------------------------------------- 84 // Implementation of UsageComputer 85 86 bool UsageComputer::Traverse(AstNode* node) { 87 UsageComputer uc(InitialWeight, false); 88 uc.Visit(node); 89 return !uc.HasStackOverflow(); 90 } 91 92 93 void UsageComputer::VisitBlock(Block* node) { 94 VisitStatements(node->statements()); 95 } 96 97 98 void UsageComputer::VisitDeclaration(Declaration* node) { 99 Write(node->proxy()); 100 if (node->fun() != NULL) 101 VisitFunctionLiteral(node->fun()); 102 } 103 104 105 void UsageComputer::VisitExpressionStatement(ExpressionStatement* node) { 106 Visit(node->expression()); 107 } 108 109 110 void UsageComputer::VisitEmptyStatement(EmptyStatement* node) { 111 // nothing to do 112 } 113 114 115 void UsageComputer::VisitIfStatement(IfStatement* node) { 116 Read(node->condition()); 117 { WeightScaler ws(this, 0.5); // executed 50% of the time 118 Visit(node->then_statement()); 119 Visit(node->else_statement()); 120 } 121 } 122 123 124 void UsageComputer::VisitContinueStatement(ContinueStatement* node) { 125 // nothing to do 126 } 127 128 129 void UsageComputer::VisitBreakStatement(BreakStatement* node) { 130 // nothing to do 131 } 132 133 134 void UsageComputer::VisitReturnStatement(ReturnStatement* node) { 135 Read(node->expression()); 136 } 137 138 139 void UsageComputer::VisitWithEnterStatement(WithEnterStatement* node) { 140 Read(node->expression()); 141 } 142 143 144 void UsageComputer::VisitWithExitStatement(WithExitStatement* node) { 145 // nothing to do 146 } 147 148 149 void UsageComputer::VisitSwitchStatement(SwitchStatement* node) { 150 Read(node->tag()); 151 ZoneList<CaseClause*>* cases = node->cases(); 152 for (int i = cases->length(); i-- > 0;) { 153 WeightScaler ws(this, static_cast<float>(1.0 / cases->length())); 154 CaseClause* clause = cases->at(i); 155 if (!clause->is_default()) 156 Read(clause->label()); 157 VisitStatements(clause->statements()); 158 } 159 } 160 161 162 void UsageComputer::VisitDoWhileStatement(DoWhileStatement* node) { 163 WeightScaler ws(this, 10.0); 164 Read(node->cond()); 165 Visit(node->body()); 166 } 167 168 169 void UsageComputer::VisitWhileStatement(WhileStatement* node) { 170 WeightScaler ws(this, 10.0); 171 Read(node->cond()); 172 Visit(node->body()); 173 } 174 175 176 void UsageComputer::VisitForStatement(ForStatement* node) { 177 if (node->init() != NULL) Visit(node->init()); 178 { WeightScaler ws(this, 10.0); // executed in each iteration 179 if (node->cond() != NULL) Read(node->cond()); 180 if (node->next() != NULL) Visit(node->next()); 181 Visit(node->body()); 182 } 183 } 184 185 186 void UsageComputer::VisitForInStatement(ForInStatement* node) { 187 WeightScaler ws(this, 10.0); 188 Write(node->each()); 189 Read(node->enumerable()); 190 Visit(node->body()); 191 } 192 193 194 void UsageComputer::VisitTryCatchStatement(TryCatchStatement* node) { 195 Visit(node->try_block()); 196 { WeightScaler ws(this, 0.25); 197 Write(node->catch_var()); 198 Visit(node->catch_block()); 199 } 200 } 201 202 203 void UsageComputer::VisitTryFinallyStatement(TryFinallyStatement* node) { 204 Visit(node->try_block()); 205 Visit(node->finally_block()); 206 } 207 208 209 void UsageComputer::VisitDebuggerStatement(DebuggerStatement* node) { 210 } 211 212 213 void UsageComputer::VisitFunctionLiteral(FunctionLiteral* node) { 214 ZoneList<Declaration*>* decls = node->scope()->declarations(); 215 for (int i = 0; i < decls->length(); i++) VisitDeclaration(decls->at(i)); 216 VisitStatements(node->body()); 217 } 218 219 220 void UsageComputer::VisitFunctionBoilerplateLiteral( 221 FunctionBoilerplateLiteral* node) { 222 // Do nothing. 223 } 224 225 226 void UsageComputer::VisitConditional(Conditional* node) { 227 Read(node->condition()); 228 { WeightScaler ws(this, 0.5); 229 Read(node->then_expression()); 230 Read(node->else_expression()); 231 } 232 } 233 234 235 void UsageComputer::VisitSlot(Slot* node) { 236 UNREACHABLE(); 237 } 238 239 240 void UsageComputer::VisitVariable(Variable* node) { 241 RecordUses(node->var_uses()); 242 } 243 244 245 void UsageComputer::VisitVariableProxy(VariableProxy* node) { 246 // The proxy may refer to a variable in which case it was bound via 247 // VariableProxy::BindTo. 248 RecordUses(node->var_uses()); 249 } 250 251 252 void UsageComputer::VisitLiteral(Literal* node) { 253 // nothing to do 254 } 255 256 void UsageComputer::VisitRegExpLiteral(RegExpLiteral* node) { 257 // nothing to do 258 } 259 260 261 void UsageComputer::VisitObjectLiteral(ObjectLiteral* node) { 262 ReadList(node->properties()); 263 } 264 265 266 void UsageComputer::VisitArrayLiteral(ArrayLiteral* node) { 267 ReadList(node->values()); 268 } 269 270 271 void UsageComputer::VisitCatchExtensionObject(CatchExtensionObject* node) { 272 Read(node->value()); 273 } 274 275 276 void UsageComputer::VisitAssignment(Assignment* node) { 277 if (node->op() != Token::ASSIGN) 278 Read(node->target()); 279 Write(node->target()); 280 Read(node->value()); 281 } 282 283 284 void UsageComputer::VisitThrow(Throw* node) { 285 Read(node->exception()); 286 } 287 288 289 void UsageComputer::VisitProperty(Property* node) { 290 // In any case (read or write) we read both the 291 // node's object and the key. 292 Read(node->obj()); 293 Read(node->key()); 294 // If the node's object is a variable proxy, 295 // we have a 'simple' object property access. We count 296 // the access via the variable or proxy's object uses. 297 VariableProxy* proxy = node->obj()->AsVariableProxy(); 298 if (proxy != NULL) { 299 RecordUses(proxy->obj_uses()); 300 } 301 } 302 303 304 void UsageComputer::VisitCall(Call* node) { 305 Read(node->expression()); 306 ReadList(node->arguments()); 307 } 308 309 310 void UsageComputer::VisitCallNew(CallNew* node) { 311 Read(node->expression()); 312 ReadList(node->arguments()); 313 } 314 315 316 void UsageComputer::VisitCallRuntime(CallRuntime* node) { 317 ReadList(node->arguments()); 318 } 319 320 321 void UsageComputer::VisitUnaryOperation(UnaryOperation* node) { 322 Read(node->expression()); 323 } 324 325 326 void UsageComputer::VisitCountOperation(CountOperation* node) { 327 Read(node->expression()); 328 Write(node->expression()); 329 } 330 331 332 void UsageComputer::VisitBinaryOperation(BinaryOperation* node) { 333 Read(node->left()); 334 Read(node->right()); 335 } 336 337 338 void UsageComputer::VisitCompareOperation(CompareOperation* node) { 339 Read(node->left()); 340 Read(node->right()); 341 } 342 343 344 void UsageComputer::VisitThisFunction(ThisFunction* node) { 345 } 346 347 348 UsageComputer::UsageComputer(int weight, bool is_write) { 349 weight_ = weight; 350 is_write_ = is_write; 351 } 352 353 354 UsageComputer::~UsageComputer() { 355 // nothing to do 356 } 357 358 359 void UsageComputer::RecordUses(UseCount* uses) { 360 if (is_write_) 361 uses->RecordWrite(weight_); 362 else 363 uses->RecordRead(weight_); 364 } 365 366 367 void UsageComputer::Read(Expression* x) { 368 if (is_write_) { 369 UsageComputer uc(weight_, false); 370 uc.Visit(x); 371 } else { 372 Visit(x); 373 } 374 } 375 376 377 void UsageComputer::Write(Expression* x) { 378 if (!is_write_) { 379 UsageComputer uc(weight_, true); 380 uc.Visit(x); 381 } else { 382 Visit(x); 383 } 384 } 385 386 387 void UsageComputer::ReadList(ZoneList<Expression*>* list) { 388 for (int i = list->length(); i-- > 0; ) 389 Read(list->at(i)); 390 } 391 392 393 void UsageComputer::ReadList(ZoneList<ObjectLiteral::Property*>* list) { 394 for (int i = list->length(); i-- > 0; ) 395 Read(list->at(i)->value()); 396 } 397 398 399 // ---------------------------------------------------------------------------- 400 // Implementation of WeightScaler 401 402 WeightScaler::WeightScaler(UsageComputer* uc, float scale) { 403 uc_ = uc; 404 old_weight_ = uc->weight_; 405 int new_weight = static_cast<int>(uc->weight_ * scale); 406 if (new_weight <= 0) new_weight = MinWeight; 407 else if (new_weight > MaxWeight) new_weight = MaxWeight; 408 uc->weight_ = new_weight; 409 } 410 411 412 WeightScaler::~WeightScaler() { 413 uc_->weight_ = old_weight_; 414 } 415 416 417 // ---------------------------------------------------------------------------- 418 // Interface to variable usage analysis 419 420 bool AnalyzeVariableUsage(FunctionLiteral* lit) { 421 if (!FLAG_usage_computation) return true; 422 HistogramTimerScope timer(&Counters::usage_analysis); 423 return UsageComputer::Traverse(lit); 424 } 425 426 } } // namespace v8::internal 427