OLD | NEW |
| (Empty) |
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 | |
OLD | NEW |