OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #ifndef VM_FLOW_GRAPH_OPTIMIZER_H_ | 5 #ifndef VM_FLOW_GRAPH_OPTIMIZER_H_ |
6 #define VM_FLOW_GRAPH_OPTIMIZER_H_ | 6 #define VM_FLOW_GRAPH_OPTIMIZER_H_ |
7 | 7 |
8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
9 #include "vm/flow_graph.h" | 9 #include "vm/flow_graph.h" |
10 | 10 |
(...skipping 298 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
309 static void Optimize(FlowGraph* graph); | 309 static void Optimize(FlowGraph* graph); |
310 }; | 310 }; |
311 | 311 |
312 | 312 |
313 class DeadCodeElimination : public AllStatic { | 313 class DeadCodeElimination : public AllStatic { |
314 public: | 314 public: |
315 static void EliminateDeadPhis(FlowGraph* graph); | 315 static void EliminateDeadPhis(FlowGraph* graph); |
316 }; | 316 }; |
317 | 317 |
318 | 318 |
319 // Sparse conditional constant propagation and unreachable code elimination. | |
320 // Assumes that use lists are computed and preserves them. | |
321 class ConstantPropagator : public FlowGraphVisitor { | |
322 public: | |
323 ConstantPropagator(FlowGraph* graph, | |
324 const GrowableArray<BlockEntryInstr*>& ignored); | |
325 | |
326 static void Optimize(FlowGraph* graph); | |
327 | |
328 // (1) Visit branches to optimize away unreachable blocks discovered by range | |
329 // analysis. | |
330 // (2) Eliminate branches that have the same true- and false-target: For | |
331 // example, this occurs after expressions like | |
332 // | |
333 // if (a == null || b == null) { | |
334 // ... | |
335 // } | |
336 // | |
337 // where b is known to be null. | |
338 static void OptimizeBranches(FlowGraph* graph); | |
339 | |
340 // Used to initialize the abstract value of definitions. | |
341 static RawObject* Unknown() { return Object::unknown_constant().raw(); } | |
342 | |
343 private: | |
344 void Analyze(); | |
345 void Transform(); | |
346 void EliminateRedundantBranches(); | |
347 | |
348 void SetReachable(BlockEntryInstr* block); | |
349 bool SetValue(Definition* definition, const Object& value); | |
350 | |
351 Definition* UnwrapPhi(Definition* defn); | |
352 void MarkPhi(Definition* defn); | |
353 | |
354 // Assign the join (least upper bound) of a pair of abstract values to the | |
355 // first one. | |
356 void Join(Object* left, const Object& right); | |
357 | |
358 bool IsUnknown(const Object& value) { | |
359 return value.raw() == unknown_.raw(); | |
360 } | |
361 bool IsNonConstant(const Object& value) { | |
362 return value.raw() == non_constant_.raw(); | |
363 } | |
364 bool IsConstant(const Object& value) { | |
365 return !IsNonConstant(value) && !IsUnknown(value); | |
366 } | |
367 | |
368 void VisitBinaryIntegerOp(BinaryIntegerOpInstr* binary_op); | |
369 | |
370 virtual void VisitBlocks() { UNREACHABLE(); } | |
371 | |
372 #define DECLARE_VISIT(type) virtual void Visit##type(type##Instr* instr); | |
373 FOR_EACH_INSTRUCTION(DECLARE_VISIT) | |
374 #undef DECLARE_VISIT | |
375 | |
376 Isolate* isolate() const { return graph_->isolate(); } | |
377 | |
378 FlowGraph* graph_; | |
379 | |
380 // Sentinels for unknown constant and non-constant values. | |
381 const Object& unknown_; | |
382 const Object& non_constant_; | |
383 | |
384 // Analysis results. For each block, a reachability bit. Indexed by | |
385 // preorder number. | |
386 BitVector* reachable_; | |
387 | |
388 BitVector* marked_phis_; | |
389 | |
390 // Worklists of blocks and definitions. | |
391 GrowableArray<BlockEntryInstr*> block_worklist_; | |
392 DefinitionWorklist definition_worklist_; | |
393 }; | |
394 | |
395 | |
396 // Rewrite branches to eliminate materialization of boolean values after | 319 // Rewrite branches to eliminate materialization of boolean values after |
397 // inlining, and to expose other optimizations (e.g., constant folding of | 320 // inlining, and to expose other optimizations (e.g., constant folding of |
398 // branches, unreachable code elimination). | 321 // branches, unreachable code elimination). |
399 class BranchSimplifier : public AllStatic { | 322 class BranchSimplifier : public AllStatic { |
400 public: | 323 public: |
401 static void Simplify(FlowGraph* flow_graph); | 324 static void Simplify(FlowGraph* flow_graph); |
402 | 325 |
403 // Replace a target entry instruction with a join entry instruction. Does | 326 // Replace a target entry instruction with a join entry instruction. Does |
404 // not update the original target's predecessors to point to the new block | 327 // not update the original target's predecessors to point to the new block |
405 // and does not replace the target in already computed block order lists. | 328 // and does not replace the target in already computed block order lists. |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
504 // Optimize spill stores inside try-blocks by identifying values that always | 427 // Optimize spill stores inside try-blocks by identifying values that always |
505 // contain a single known constant at catch block entry. | 428 // contain a single known constant at catch block entry. |
506 class TryCatchAnalyzer : public AllStatic { | 429 class TryCatchAnalyzer : public AllStatic { |
507 public: | 430 public: |
508 static void Optimize(FlowGraph* flow_graph); | 431 static void Optimize(FlowGraph* flow_graph); |
509 }; | 432 }; |
510 | 433 |
511 } // namespace dart | 434 } // namespace dart |
512 | 435 |
513 #endif // VM_FLOW_GRAPH_OPTIMIZER_H_ | 436 #endif // VM_FLOW_GRAPH_OPTIMIZER_H_ |
OLD | NEW |