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
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_BACKEND_CONSTANT_PROPAGATOR_H_
6#define RUNTIME_VM_COMPILER_BACKEND_CONSTANT_PROPAGATOR_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include "vm/compiler/backend/flow_graph.h"
13#include "vm/compiler/backend/il.h"
14
15namespace dart {
16
17// Sparse conditional constant propagation and unreachable code elimination.
18// Assumes that use lists are computed and preserves them.
19class ConstantPropagator : public FlowGraphVisitor {
20 public:
21 ConstantPropagator(FlowGraph* graph,
22 const GrowableArray<BlockEntryInstr*>& ignored);
23
24 static void Optimize(FlowGraph* graph);
25
26 // (1) Visit branches to optimize away unreachable blocks discovered by range
27 // analysis.
28 // (2) Eliminate branches that have the same true- and false-target: For
29 // example, this occurs after expressions like
30 //
31 // if (a == null || b == null) {
32 // ...
33 // }
34 //
35 // where b is known to be null.
36 static void OptimizeBranches(FlowGraph* graph);
37
38 // Used to initialize the abstract value of definitions.
39 static ObjectPtr Unknown() { return Object::unknown_constant().raw(); }
40
41 private:
42 void Analyze();
43 void Transform();
44 // Tries to replace uses of [defn] with a constant, returns true if
45 // successfull. The [value] is used as a temporary handle.
46 bool TransformDefinition(Definition* defn);
47 void EliminateRedundantBranches();
48
49 void SetReachable(BlockEntryInstr* block);
50 bool SetValue(Definition* definition, const Object& value);
51
52 // Phi might be viewed as redundant based on current reachability of
53 // predecessor blocks (i.e. the same definition is flowing from all
54 // reachable predecessors). We can use this information to constant
55 // fold phi(x) == x and phi(x) != x comparisons.
56 Definition* UnwrapPhi(Definition* defn);
57 void MarkUnwrappedPhi(Definition* defn);
58
59 // Assign the join (least upper bound) of a pair of abstract values to the
60 // first one.
61 void Join(Object* left, const Object& right);
62
63 bool IsUnknown(const Object& value) { return value.raw() == unknown_.raw(); }
64 bool IsNonConstant(const Object& value) {
65 return value.raw() == non_constant_.raw();
66 }
67 bool IsConstant(const Object& value) {
68 return !IsNonConstant(value) && !IsUnknown(value);
69 }
70
71 void VisitBinaryIntegerOp(BinaryIntegerOpInstr* binary_op);
72 void VisitUnaryIntegerOp(UnaryIntegerOpInstr* unary_op);
73
74 virtual void VisitBlocks() { UNREACHABLE(); }
75
76#define DECLARE_VISIT(type, attrs) virtual void Visit##type(type##Instr* instr);
77 FOR_EACH_INSTRUCTION(DECLARE_VISIT)
78
79#undef DECLARE_VISIT
80 // Structure tracking visit counts for phis. Used to detect infinite loops.
81 struct PhiInfo {
82 PhiInstr* phi;
83 intptr_t visit_count;
84 };
85
86 // Returns PhiInfo associated with the given phi. Note that this
87 // pointer can be invalidated by subsequent call to GetPhiInfo and
88 // thus should not be stored anywhere.
89 PhiInfo* GetPhiInfo(PhiInstr* phi);
90
91 Isolate* isolate() const { return graph_->isolate(); }
92
93 FlowGraph* graph_;
94
95 // Sentinels for unknown constant and non-constant values.
96 const Object& unknown_;
97 const Object& non_constant_;
98
99 // Temporary handle used in [TransformDefinition].
100 Object& constant_value_;
101
102 // Analysis results. For each block, a reachability bit. Indexed by
103 // preorder number.
104 BitVector* reachable_;
105
106 // Bitvector of phis that were "unwrapped" into one of their inputs
107 // when visiting one of their uses. These uses of these phis
108 // should be revisited if reachability of the predecessor blocks
109 // changes even if that does not change constant value of the phi.
110 BitVector* unwrapped_phis_;
111
112 // List of visited phis indexed by their id (stored as pass specific id on
113 // a phi instruction).
114 GrowableArray<PhiInfo> phis_;
115
116 // Worklists of blocks and definitions.
117 GrowableArray<BlockEntryInstr*> block_worklist_;
118 DefinitionWorklist definition_worklist_;
119};
120
121} // namespace dart
122
123#endif // RUNTIME_VM_COMPILER_BACKEND_CONSTANT_PROPAGATOR_H_
124