| 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_BUILDER_H_ | 5 #ifndef VM_FLOW_GRAPH_BUILDER_H_ |
| 6 #define VM_FLOW_GRAPH_BUILDER_H_ | 6 #define VM_FLOW_GRAPH_BUILDER_H_ |
| 7 | 7 |
| 8 #include "vm/allocation.h" | 8 #include "vm/allocation.h" |
| 9 #include "vm/ast.h" | 9 #include "vm/ast.h" |
| 10 #include "vm/growable_array.h" | 10 #include "vm/growable_array.h" |
| (...skipping 20 matching lines...) Expand all Loading... |
| 31 const ParsedFunction& parsed_function() const { return parsed_function_; } | 31 const ParsedFunction& parsed_function() const { return parsed_function_; } |
| 32 | 32 |
| 33 void Bailout(const char* reason); | 33 void Bailout(const char* reason); |
| 34 | 34 |
| 35 private: | 35 private: |
| 36 const ParsedFunction& parsed_function_; | 36 const ParsedFunction& parsed_function_; |
| 37 GrowableArray<BlockEntryInstr*> postorder_block_entries_; | 37 GrowableArray<BlockEntryInstr*> postorder_block_entries_; |
| 38 }; | 38 }; |
| 39 | 39 |
| 40 | 40 |
| 41 #define DEFINE_VISIT(type, name) virtual void Visit##type(type* node); | |
| 42 | |
| 43 class TestGraphVisitor; | 41 class TestGraphVisitor; |
| 44 | 42 |
| 45 // Translate an AstNode to a control-flow graph fragment for its effects | 43 // Translate an AstNode to a control-flow graph fragment for its effects |
| 46 // (e.g., a statement or an expression in an effect context). Implements a | 44 // (e.g., a statement or an expression in an effect context). Implements a |
| 47 // function from an AstNode and next temporary index to a graph fragment | 45 // function from an AstNode and next temporary index to a graph fragment |
| 48 // with a single entry and at most one exit. The fragment is represented by | 46 // with a single entry and at most one exit. The fragment is represented by |
| 49 // an (entry, exit) pair of Instruction pointers: | 47 // an (entry, exit) pair of Instruction pointers: |
| 50 // | 48 // |
| 51 // - (NULL, NULL): an empty and open graph fragment | 49 // - (NULL, NULL): an empty and open graph fragment |
| 52 // - (i0, NULL): a closed graph fragment which has only non-local exits | 50 // - (i0, NULL): a closed graph fragment which has only non-local exits |
| 53 // - (i0, i1): an open graph fragment | 51 // - (i0, i1): an open graph fragment |
| 54 class EffectGraphVisitor : public AstNodeVisitor { | 52 class EffectGraphVisitor : public AstNodeVisitor { |
| 55 public: | 53 public: |
| 56 EffectGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) | 54 EffectGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) |
| 57 : owner_(owner), | 55 : owner_(owner), |
| 58 temp_index_(temp_index), | 56 temp_index_(temp_index), |
| 59 entry_(NULL), | 57 entry_(NULL), |
| 60 exit_(NULL) { } | 58 exit_(NULL) { } |
| 61 | 59 |
| 60 #define DEFINE_VISIT(type, name) virtual void Visit##type(type* node); |
| 62 NODE_LIST(DEFINE_VISIT) | 61 NODE_LIST(DEFINE_VISIT) |
| 62 #undef DEFINE_VISIT |
| 63 | 63 |
| 64 FlowGraphBuilder* owner() const { return owner_; } | 64 FlowGraphBuilder* owner() const { return owner_; } |
| 65 intptr_t temp_index() const { return temp_index_; } | 65 intptr_t temp_index() const { return temp_index_; } |
| 66 Instruction* entry() const { return entry_; } | 66 Instruction* entry() const { return entry_; } |
| 67 Instruction* exit() const { return exit_; } | 67 Instruction* exit() const { return exit_; } |
| 68 | 68 |
| 69 bool is_empty() const { return entry_ == NULL; } | 69 bool is_empty() const { return entry_ == NULL; } |
| 70 bool is_open() const { return is_empty() || exit_ != NULL; } | 70 bool is_open() const { return is_empty() || exit_ != NULL; } |
| 71 | 71 |
| 72 void Bailout(const char* reason); | 72 void Bailout(const char* reason); |
| 73 | 73 |
| 74 // Append a graph fragment to this graph. Assumes this graph is open. | 74 // Append a graph fragment to this graph. Assumes this graph is open. |
| 75 void Append(const EffectGraphVisitor& other_fragment); | 75 void Append(const EffectGraphVisitor& other_fragment); |
| 76 // Append a single instruction. Assumes this graph is open. | 76 // Append a single instruction. Assumes this graph is open. |
| 77 void AddInstruction(Instruction* instruction); | 77 void AddInstruction(Instruction* instruction); |
| 78 | 78 |
| 79 // Append a 'diamond' branch and join to this graph, depending on which | 79 // Append a 'diamond' branch and join to this graph, depending on which |
| 80 // parts are reachable. Assumes this graph is open. | 80 // parts are reachable. Assumes this graph is open. |
| 81 void Join(const TestGraphVisitor& test_fragment, | 81 void Join(const TestGraphVisitor& test_fragment, |
| 82 const EffectGraphVisitor& true_fragment, | 82 const EffectGraphVisitor& true_fragment, |
| 83 const EffectGraphVisitor& false_fragment); | 83 const EffectGraphVisitor& false_fragment); |
| 84 | 84 |
| 85 // Append a 'while loop' test and back edge to this graph, depending on | 85 // Append a 'while loop' test and back edge to this graph, depending on |
| 86 // which parts are reachable. Afterward, the graph exit is the false | 86 // which parts are reachable. Afterward, the graph exit is the false |
| 87 // successor of the loop condition. | 87 // successor of the loop condition. |
| 88 void TieLoop(const TestGraphVisitor& test_fragment, | 88 void TieLoop(const TestGraphVisitor& test_fragment, |
| 89 const EffectGraphVisitor& body_fragment); | 89 const EffectGraphVisitor& body_fragment); |
| 90 | 90 |
| 91 protected: | 91 protected: |
| 92 // Implement the core part of the translation of expression node types. | 92 // Helpers for translating parts of the AST. |
| 93 AssertAssignableComp* TranslateAssignable(const AssignableNode& node); | |
| 94 InstanceCallComp* TranslateBinaryOp(const BinaryOpNode& node); | |
| 95 InstanceCallComp* TranslateUnaryOp(const UnaryOpNode& node); | |
| 96 Computation* TranslateComparison(const ComparisonNode& node); | |
| 97 StoreLocalComp* TranslateStoreLocal(const StoreLocalNode& node); | |
| 98 StaticCallComp* TranslateStaticCall(const StaticCallNode& node); | |
| 99 InstanceCallComp* TranslateInstanceCall(const InstanceCallNode& node); | |
| 100 void TranslateArgumentList(const ArgumentListNode& node, | 93 void TranslateArgumentList(const ArgumentListNode& node, |
| 101 ZoneGrowableArray<Value*>* values); | 94 ZoneGrowableArray<Value*>* values); |
| 102 | 95 |
| 103 void CloseFragment() { exit_ = NULL; } | 96 void CloseFragment() { exit_ = NULL; } |
| 104 intptr_t AllocateTempIndex() { return temp_index_++; } | 97 intptr_t AllocateTempIndex() { return temp_index_++; } |
| 105 | 98 |
| 106 private: | 99 private: |
| 107 // Helper to append a Do instruction to the graph. | 100 // Specify a computation as the final result. Adds a Do instruction to |
| 108 void DoComputation(Computation* computation) { | 101 // the graph, but normally overridden in subclasses. |
| 102 virtual void ReturnComputation(Computation* computation) { |
| 109 AddInstruction(new DoInstr(computation)); | 103 AddInstruction(new DoInstr(computation)); |
| 110 } | 104 } |
| 111 | 105 |
| 112 // Shared global state. | 106 // Shared global state. |
| 113 FlowGraphBuilder* owner_; | 107 FlowGraphBuilder* owner_; |
| 114 | 108 |
| 115 // Input parameters. | 109 // Input parameters. |
| 116 intptr_t temp_index_; | 110 intptr_t temp_index_; |
| 117 | 111 |
| 118 // Output parameters. | 112 // Output parameters. |
| 119 Instruction* entry_; | 113 Instruction* entry_; |
| 120 Instruction* exit_; | 114 Instruction* exit_; |
| 121 }; | 115 }; |
| 122 | 116 |
| 123 | 117 |
| 124 // Translate an AstNode to a control-flow graph fragment for both its effects | 118 // Translate an AstNode to a control-flow graph fragment for both its effects |
| 125 // and value (e.g., for an expression in a value context). Implements a | 119 // and value (e.g., for an expression in a value context). Implements a |
| 126 // function from an AstNode and next temporary index to a graph fragment (as | 120 // function from an AstNode and next temporary index to a graph fragment (as |
| 127 // in the EffectGraphVisitor), a next temporary index, and an intermediate | 121 // in the EffectGraphVisitor), a next temporary index, and an intermediate |
| 128 // language Value. | 122 // language Value. |
| 129 class ValueGraphVisitor : public EffectGraphVisitor { | 123 class ValueGraphVisitor : public EffectGraphVisitor { |
| 130 public: | 124 public: |
| 131 ValueGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) | 125 ValueGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) |
| 132 : EffectGraphVisitor(owner, temp_index), value_(NULL) { } | 126 : EffectGraphVisitor(owner, temp_index), value_(NULL) { } |
| 133 | 127 |
| 134 NODE_LIST(DEFINE_VISIT) | 128 // Visit functions overridden by this class. |
| 129 virtual void VisitLiteralNode(LiteralNode* node); |
| 130 virtual void VisitLoadLocalNode(LoadLocalNode* node); |
| 135 | 131 |
| 136 Value* value() const { return value_; } | 132 Value* value() const { return value_; } |
| 137 | 133 |
| 138 private: | 134 private: |
| 139 // Helper to set the output state to return a Value. | 135 // Helper to set the output state to return a Value. |
| 140 void ReturnValue(Value* value) { value_ = value; } | 136 void ReturnValue(Value* value) { value_ = value; } |
| 141 | 137 |
| 142 // Helper to append a Bind instruction to the graph and return its | 138 // Specify a computation as the final result. Adds a Bind instruction to |
| 143 // temporary value (i.e., set the output parameters). | 139 // the graph and returns its temporary value (i.e., set the output |
| 144 void ReturnValueOf(Computation* computation) { | 140 // parameters). |
| 141 virtual void ReturnComputation(Computation* computation) { |
| 145 AddInstruction(new BindInstr(temp_index(), computation)); | 142 AddInstruction(new BindInstr(temp_index(), computation)); |
| 146 value_ = new TempVal(AllocateTempIndex()); | 143 value_ = new TempVal(AllocateTempIndex()); |
| 147 } | 144 } |
| 148 | 145 |
| 149 // Output parameters. | 146 // Output parameters. |
| 150 Value* value_; | 147 Value* value_; |
| 151 }; | 148 }; |
| 152 | 149 |
| 153 | 150 |
| 154 // Translate an AstNode to a control-flow graph fragment for both its | 151 // Translate an AstNode to a control-flow graph fragment for both its |
| (...skipping 11 matching lines...) Expand all Loading... |
| 166 // We expect that AstNode in test contexts either have only nonlocal exits | 163 // We expect that AstNode in test contexts either have only nonlocal exits |
| 167 // or else control flow has both true and false successors. | 164 // or else control flow has both true and false successors. |
| 168 class TestGraphVisitor : public EffectGraphVisitor { | 165 class TestGraphVisitor : public EffectGraphVisitor { |
| 169 public: | 166 public: |
| 170 TestGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) | 167 TestGraphVisitor(FlowGraphBuilder* owner, intptr_t temp_index) |
| 171 : EffectGraphVisitor(owner, temp_index), | 168 : EffectGraphVisitor(owner, temp_index), |
| 172 true_successor_address_(NULL), | 169 true_successor_address_(NULL), |
| 173 false_successor_address_(NULL) { | 170 false_successor_address_(NULL) { |
| 174 } | 171 } |
| 175 | 172 |
| 176 NODE_LIST(DEFINE_VISIT) | 173 // Visit functions overridden by this class. |
| 174 virtual void VisitLiteralNode(LiteralNode* node); |
| 175 virtual void VisitLoadLocalNode(LoadLocalNode* node); |
| 177 | 176 |
| 178 bool can_be_true() const { | 177 bool can_be_true() const { |
| 179 // Either both successors are set or neither is set. | 178 // Either both successors are set or neither is set. |
| 180 ASSERT((true_successor_address_ == NULL) == | 179 ASSERT((true_successor_address_ == NULL) == |
| 181 (false_successor_address_ == NULL)); | 180 (false_successor_address_ == NULL)); |
| 182 return true_successor_address_ != NULL; | 181 return true_successor_address_ != NULL; |
| 183 } | 182 } |
| 184 bool can_be_false() const { | 183 bool can_be_false() const { |
| 185 // Either both successors are set or neither is set. | 184 // Either both successors are set or neither is set. |
| 186 ASSERT((true_successor_address_ == NULL) == | 185 ASSERT((true_successor_address_ == NULL) == |
| 187 (false_successor_address_ == NULL)); | 186 (false_successor_address_ == NULL)); |
| 188 return false_successor_address_ != NULL; | 187 return false_successor_address_ != NULL; |
| 189 } | 188 } |
| 190 | 189 |
| 191 TargetEntryInstr** true_successor_address() const { | 190 TargetEntryInstr** true_successor_address() const { |
| 192 ASSERT(can_be_true()); | 191 ASSERT(can_be_true()); |
| 193 return true_successor_address_; | 192 return true_successor_address_; |
| 194 } | 193 } |
| 195 TargetEntryInstr** false_successor_address() const { | 194 TargetEntryInstr** false_successor_address() const { |
| 196 ASSERT(can_be_false()); | 195 ASSERT(can_be_false()); |
| 197 return false_successor_address_; | 196 return false_successor_address_; |
| 198 } | 197 } |
| 199 | 198 |
| 200 private: | 199 private: |
| 201 // Construct and concatenate a Branch instruction to this graph fragment. | 200 // Construct and concatenate a Branch instruction to this graph fragment. |
| 202 // Closes the fragment and sets the output parameters. | 201 // Closes the fragment and sets the output parameters. |
| 203 void BranchOnValue(Value* value); | 202 void BranchOnValue(Value* value); |
| 204 | 203 |
| 205 // Helper to bind a computation and branch on its value. | 204 // Specify a computation as the final result. Adds a Bind instruction to |
| 206 void BranchOnValueOf(Computation* computation) { | 205 // the graph and branches on its value. |
| 206 virtual void ReturnComputation(Computation* computation) { |
| 207 AddInstruction(new BindInstr(temp_index(), computation)); | 207 AddInstruction(new BindInstr(temp_index(), computation)); |
| 208 BranchOnValue(new TempVal(temp_index())); | 208 BranchOnValue(new TempVal(temp_index())); |
| 209 } | 209 } |
| 210 | 210 |
| 211 // Output parameters. | 211 // Output parameters. |
| 212 TargetEntryInstr** true_successor_address_; | 212 TargetEntryInstr** true_successor_address_; |
| 213 TargetEntryInstr** false_successor_address_; | 213 TargetEntryInstr** false_successor_address_; |
| 214 }; | 214 }; |
| 215 | 215 |
| 216 #undef DEFINE_VISIT | |
| 217 | |
| 218 | |
| 219 } // namespace dart | 216 } // namespace dart |
| 220 | 217 |
| 221 #endif // VM_FLOW_GRAPH_BUILDER_H_ | 218 #endif // VM_FLOW_GRAPH_BUILDER_H_ |
| OLD | NEW |