OLD | NEW |
---|---|
(Empty) | |
1 // Copyright 2009 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 #ifndef V8_CFG_H_ | |
29 #define V8_CFG_H_ | |
30 | |
31 #include "ast.h" | |
32 | |
33 namespace v8 { | |
34 namespace internal { | |
35 | |
36 // Values appear in instructions. They represent trivial source | |
37 // expressions: ones with no side effects and that do not require code to be | |
38 // generated. | |
39 class Value : public ZoneObject { | |
40 public: | |
41 virtual void ToRegister(MacroAssembler* masm, Register reg) = 0; | |
42 | |
43 #ifdef DEBUG | |
44 virtual void Print() = 0; | |
45 #endif | |
46 }; | |
47 | |
48 | |
49 // A compile-time constant that appeared as a literal in the source AST. | |
50 class Constant : public Value { | |
51 public: | |
52 explicit Constant(Handle<Object> handle) : handle_(handle) {} | |
53 | |
54 virtual void ToRegister(MacroAssembler* masm, Register reg); | |
55 | |
56 #ifdef DEBUG | |
57 void Print(); | |
58 #endif | |
59 | |
60 private: | |
61 Handle<Object> handle_; | |
62 }; | |
63 | |
64 | |
65 // Instructions are computations. The represent non-trivial source | |
66 // expressions: typically ones that have side effects and require code to | |
67 // be generated. | |
68 class Instruction : public ZoneObject { | |
69 public: | |
70 virtual void Compile(MacroAssembler* masm) = 0; | |
71 | |
72 #ifdef DEBUG | |
73 virtual void Print() = 0; | |
74 #endif | |
75 }; | |
76 | |
77 | |
78 // Return a value. | |
79 class ReturnInstr : public Instruction { | |
80 public: | |
81 explicit ReturnInstr(Value* value) : value_(value) {} | |
82 | |
83 void Compile(MacroAssembler* masm); | |
84 | |
85 #ifdef DEBUG | |
86 void Print(); | |
87 #endif | |
88 | |
89 private: | |
90 Value* value_; | |
91 }; | |
92 | |
93 | |
94 // Nodes make up control-flow graphs. They contain single-entry, | |
95 // single-exit blocks of instructions and administrative nodes making up the | |
96 // graph structure. | |
97 class CfgNode : public ZoneObject { | |
98 public: | |
99 CfgNode() : is_marked_(false) { | |
100 #ifdef DEBUG | |
101 number_ = -1; | |
102 #endif | |
103 } | |
104 | |
105 bool is_marked() { return is_marked_; } | |
106 | |
107 static void Reset(); | |
108 | |
109 virtual bool is_block() { return false; } | |
110 | |
111 virtual void Unmark() = 0; | |
112 | |
113 virtual void Compile(MacroAssembler* masm) = 0; | |
114 | |
115 #ifdef DEBUG | |
116 int number() { | |
117 if (number_ == -1) number_ = node_counter_++; | |
118 return number_; | |
119 } | |
120 | |
121 virtual void Print() = 0; | |
122 #endif | |
123 | |
124 protected: | |
125 bool is_marked_; | |
126 | |
127 #ifdef DEBUG | |
128 int number_; | |
129 | |
130 static int node_counter_; | |
131 #endif | |
132 }; | |
133 | |
134 | |
135 // A block is a single-entry, single-exit block of instructions. | |
136 class InstructionBlock : public CfgNode { | |
137 public: | |
138 InstructionBlock() : successor_(NULL), instructions_(4) {} | |
139 | |
140 static InstructionBlock* cast(CfgNode* node) { | |
141 ASSERT(node->is_block()); | |
142 return reinterpret_cast<InstructionBlock*>(node); | |
143 } | |
144 | |
145 void set_successor(CfgNode* succ) { | |
146 ASSERT(successor_ == NULL); | |
147 successor_ = succ; | |
148 } | |
149 | |
150 bool is_block() { return true; } | |
151 | |
152 void Unmark(); | |
153 | |
154 void Compile(MacroAssembler* masm); | |
155 | |
156 void Append(Instruction* instr) { instructions_.Add(instr); } | |
157 | |
158 #ifdef DEBUG | |
159 void Print(); | |
160 #endif | |
161 | |
162 private: | |
163 CfgNode* successor_; | |
164 ZoneList<Instruction*> instructions_; | |
165 }; | |
166 | |
167 | |
168 // The CFG for a function has a distinguished entry node. It has no | |
169 // predecessors and a single successor. The successor is the block | |
170 // containing the function's first instruction. | |
171 class EntryNode : public CfgNode { | |
172 public: | |
173 EntryNode(FunctionLiteral* fun, InstructionBlock* succ); | |
174 | |
175 void Unmark(); | |
176 | |
177 void Compile(MacroAssembler* masm); | |
178 | |
179 #ifdef DEBUG | |
180 void Print(); | |
181 #endif | |
182 | |
183 private: | |
184 InstructionBlock* successor_; | |
185 int local_count_; | |
186 }; | |
187 | |
188 | |
189 // The CFG for a function has a distinguished exit node. It has no | |
190 // successor and arbitrarily many predecessors. The predecessors are all | |
191 // the blocks returning from the function. | |
192 class ExitNode : public CfgNode { | |
193 public: | |
194 explicit ExitNode(FunctionLiteral* fun); | |
195 | |
196 void Unmark(); | |
197 | |
198 void Compile(MacroAssembler* masm); | |
199 | |
200 #ifdef DEBUG | |
201 void Print(); | |
202 #endif | |
203 | |
204 private: | |
205 int parameter_count_; | |
206 }; | |
207 | |
208 | |
209 // A CFG is a consists of a linked structure of nodes. It has a single | |
antonm
2009/07/31 13:30:47
looks like you forgot to remove abandoned phrase.
| |
210 // entry node and optionally an exit node. There is a distinguished global | |
211 // exit node that is used as the successor of all blocks that return from | |
212 // the function. | |
213 // | |
214 // Fragments of control-flow graphs, produced when traversing the statements | |
215 // and expressions in the source AST, are represented by the same class. | |
216 // They have instruction blocks as both their entry and exit (if there is | |
217 // one). Instructions can always be prepended or appended to fragments, and | |
218 // fragments can always be concatenated. | |
219 // | |
220 // A singleton CFG fragment (i.e., with only one node) has the same node as | |
221 // both entry and exit (if the exit is available). | |
222 class Cfg : public ZoneObject { | |
223 public: | |
224 // Create a singleton CFG fragment. | |
225 explicit Cfg(InstructionBlock* block) : entry_(block), exit_(block) {} | |
226 | |
227 // Build the CFG for a function. | |
228 static Cfg* Build(FunctionLiteral* fun); | |
229 | |
230 // The entry and exit nodes. | |
231 CfgNode* entry() { return entry_; } | |
232 CfgNode* exit() { return exit_; } | |
233 | |
234 // True if the CFG has no nodes. | |
235 bool is_empty() { return entry_ == NULL; } | |
236 | |
237 // True if the CFG has an available exit node (i.e., it can be appended or | |
238 // concatenated to). | |
239 bool has_exit() { return exit_ != NULL; } | |
240 | |
241 // Add an entry node to a CFG fragment. It is no longer a fragment | |
242 // (instructions cannot be prepended). | |
243 void PrependEntryNode(FunctionLiteral* fun); | |
244 | |
245 // Append an instruction to the end of a CFG fragment. Assumes it has an | |
246 // available exit. | |
247 void Append(Instruction* instr); | |
248 | |
249 // Appends a return instruction to the end of a CFG fragment. It no | |
250 // longer has an available exit node. | |
251 void AppendReturnInstruction(Value* value); | |
252 | |
253 Handle<Code> Compile(FunctionLiteral* fun, Handle<Script> script); | |
254 | |
255 #ifdef DEBUG | |
256 // Support for printing. | |
257 void Print(); | |
258 #endif | |
259 | |
260 private: | |
261 // Reset static variables before building the CFG for a function. | |
262 static void Reset(FunctionLiteral* fun); | |
263 | |
264 // Shared global exit nodes for all returns from the same function. | |
265 static ExitNode* global_exit_; | |
266 | |
267 // Entry and exit nodes. | |
268 CfgNode* entry_; | |
269 CfgNode* exit_; | |
270 }; | |
271 | |
272 | |
273 // An Expression Builder traverses a trivial expression and returns a value. | |
274 class ExpressionBuilder : public AstVisitor { | |
275 public: | |
276 ExpressionBuilder() : value_(new Constant(Handle<Object>::null())) {} | |
277 | |
278 Value* value() { return value_; } | |
279 | |
280 // AST node visitors. | |
281 #define DECLARE_VISIT(type) void Visit##type(type* node); | |
282 AST_NODE_LIST(DECLARE_VISIT) | |
283 #undef DECLARE_VISIT | |
284 | |
285 private: | |
286 Value* value_; | |
287 }; | |
288 | |
289 | |
290 // A StatementBuilder traverses a statement and returns a CFG. | |
291 class StatementBuilder : public AstVisitor { | |
292 public: | |
293 StatementBuilder() : cfg_(new Cfg(new InstructionBlock())) {} | |
294 | |
295 Cfg* cfg() { return cfg_; } | |
296 | |
297 void VisitStatements(ZoneList<Statement*>* stmts); | |
298 | |
299 // AST node visitors. | |
300 #define DECLARE_VISIT(type) void Visit##type(type* node); | |
301 AST_NODE_LIST(DECLARE_VISIT) | |
302 #undef DECLARE_VISIT | |
303 | |
304 private: | |
305 Cfg* cfg_; | |
306 }; | |
307 | |
308 | |
309 } } // namespace v8::internal | |
310 | |
311 #endif // V8_CFG_H_ | |
OLD | NEW |