OLD | NEW |
1 // Copyright 2009 the V8 project authors. All rights reserved. | 1 // Copyright 2009 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 16 matching lines...) Expand all Loading... |
27 | 27 |
28 #ifndef V8_CFG_H_ | 28 #ifndef V8_CFG_H_ |
29 #define V8_CFG_H_ | 29 #define V8_CFG_H_ |
30 | 30 |
31 #include "ast.h" | 31 #include "ast.h" |
32 | 32 |
33 namespace v8 { | 33 namespace v8 { |
34 namespace internal { | 34 namespace internal { |
35 | 35 |
36 class ExitNode; | 36 class ExitNode; |
| 37 class Location; |
| 38 |
| 39 // Translate a source AST into a control-flow graph (CFG). The CFG contains |
| 40 // single-entry, single-exit blocks of straight-line instructions and |
| 41 // administrative nodes. |
| 42 // |
| 43 // Instructions are described by the following grammar. |
| 44 // |
| 45 // <Instruction> ::= |
| 46 // BinaryOpInstr <Location> Token::Value <Value> <Value> |
| 47 // | ReturnInstr Effect <Value> |
| 48 // |
| 49 // Values are trivial expressions: |
| 50 // |
| 51 // <Value> ::= Constant | <Location> |
| 52 // |
| 53 // Locations are storable values ('lvalues'). They can be slots, |
| 54 // compiler-generated temporaries, or the special location 'Effect' |
| 55 // indicating that no value is needed. |
| 56 // |
| 57 // <Location> ::= |
| 58 // SlotLocation Slot::Type <Index> |
| 59 // | TempLocation |
| 60 // | Effect |
| 61 |
| 62 |
| 63 // Administrative nodes: There are several types of 'administrative' nodes |
| 64 // that do not contain instructions and do not necessarily have a single |
| 65 // predecessor and a single successor. |
| 66 // |
| 67 // EntryNode: there is a distinguished entry node that has no predecessors |
| 68 // and a single successor. |
| 69 // |
| 70 // ExitNode: there is a distinguished exit node that has arbitrarily many |
| 71 // predecessors and no successor. |
| 72 // |
| 73 // JoinNode: join nodes have multiple predecessors and a single successor. |
| 74 // |
| 75 // BranchNode: branch nodes have a single predecessor and multiple |
| 76 // successors. |
| 77 |
37 | 78 |
38 // A convenient class to keep 'global' values when building a CFG. Since | 79 // A convenient class to keep 'global' values when building a CFG. Since |
39 // CFG construction can be invoked recursively, CFG globals are stacked. | 80 // CFG construction can be invoked recursively, CFG globals are stacked. |
40 class CfgGlobals BASE_EMBEDDED { | 81 class CfgGlobals BASE_EMBEDDED { |
41 public: | 82 public: |
42 explicit CfgGlobals(FunctionLiteral* fun); | 83 explicit CfgGlobals(FunctionLiteral* fun); |
43 | 84 |
44 ~CfgGlobals() { top_ = previous_; } | 85 ~CfgGlobals() { top_ = previous_; } |
45 | 86 |
46 static CfgGlobals* current() { | 87 static CfgGlobals* current() { |
47 ASSERT(top_ != NULL); | 88 ASSERT(top_ != NULL); |
48 return top_; | 89 return top_; |
49 } | 90 } |
50 | 91 |
| 92 // The function currently being compiled. |
51 FunctionLiteral* fun() { return global_fun_; } | 93 FunctionLiteral* fun() { return global_fun_; } |
52 | 94 |
| 95 // The shared global exit node for all exits from the function. |
53 ExitNode* exit() { return global_exit_; } | 96 ExitNode* exit() { return global_exit_; } |
54 | 97 |
| 98 // A singleton effect location. |
| 99 Location* effect_location() { return effect_; } |
| 100 |
55 #ifdef DEBUG | 101 #ifdef DEBUG |
56 int next_number() { return node_counter_++; } | 102 int next_node_number() { return node_counter_++; } |
| 103 int next_temp_number() { return temp_counter_++; } |
57 #endif | 104 #endif |
58 | 105 |
59 private: | 106 private: |
60 static CfgGlobals* top_; | 107 static CfgGlobals* top_; |
61 | |
62 // Function literal currently compiling. | |
63 FunctionLiteral* global_fun_; | 108 FunctionLiteral* global_fun_; |
64 | |
65 // Shared global exit node for all returns from the same function. | |
66 ExitNode* global_exit_; | 109 ExitNode* global_exit_; |
| 110 Location* effect_; |
67 | 111 |
68 #ifdef DEBUG | 112 #ifdef DEBUG |
69 // Used to number nodes when printing. | 113 // Used to number nodes and temporaries when printing. |
70 int node_counter_; | 114 int node_counter_; |
| 115 int temp_counter_; |
71 #endif | 116 #endif |
72 | 117 |
73 CfgGlobals* previous_; | 118 CfgGlobals* previous_; |
74 }; | 119 }; |
75 | 120 |
76 | 121 |
77 // Values appear in instructions. They represent trivial source | 122 // Values represent trivial source expressions: ones with no side effects |
78 // expressions: ones with no side effects and that do not require code to be | 123 // and that do not require code to be generated. |
79 // generated. | |
80 class Value : public ZoneObject { | 124 class Value : public ZoneObject { |
81 public: | 125 public: |
82 virtual ~Value() {} | 126 virtual ~Value() {} |
83 | 127 |
84 virtual void ToRegister(MacroAssembler* masm, Register reg) = 0; | 128 // Predicates: |
| 129 |
| 130 // True if the value is a temporary allocated to the stack in |
| 131 // fast-compilation mode. |
| 132 virtual bool is_on_stack() { return false; } |
| 133 |
| 134 // True if the value is a compiler-generated temporary location. |
| 135 virtual bool is_temporary() { return false; } |
| 136 |
| 137 // Support for fast-compilation mode: |
| 138 |
| 139 // Move the value into a register. |
| 140 virtual void Get(MacroAssembler* masm, Register reg) = 0; |
| 141 |
| 142 // Push the value on the stack. |
| 143 virtual void Push(MacroAssembler* masm) = 0; |
85 | 144 |
86 #ifdef DEBUG | 145 #ifdef DEBUG |
87 virtual void Print() = 0; | 146 virtual void Print() = 0; |
88 #endif | 147 #endif |
89 }; | 148 }; |
90 | 149 |
91 | 150 |
92 // A compile-time constant that appeared as a literal in the source AST. | 151 // A compile-time constant that appeared as a literal in the source AST. |
93 class Constant : public Value { | 152 class Constant : public Value { |
94 public: | 153 public: |
95 explicit Constant(Handle<Object> handle) : handle_(handle) {} | 154 explicit Constant(Handle<Object> handle) : handle_(handle) {} |
96 | 155 |
97 virtual ~Constant() {} | 156 virtual ~Constant() {} |
98 | 157 |
99 void ToRegister(MacroAssembler* masm, Register reg); | 158 // Support for fast-compilation mode. |
| 159 void Get(MacroAssembler* masm, Register reg); |
| 160 void Push(MacroAssembler* masm); |
100 | 161 |
101 #ifdef DEBUG | 162 #ifdef DEBUG |
102 void Print(); | 163 void Print(); |
103 #endif | 164 #endif |
104 | 165 |
105 private: | 166 private: |
106 Handle<Object> handle_; | 167 Handle<Object> handle_; |
107 }; | 168 }; |
108 | 169 |
109 | 170 |
110 // Locations are values that can be stored into ('lvalues'). | 171 // Locations are values that can be stored into ('lvalues'). |
111 class Location : public Value { | 172 class Location : public Value { |
112 public: | 173 public: |
113 virtual ~Location() {} | 174 virtual ~Location() {} |
114 | 175 |
115 virtual void ToRegister(MacroAssembler* masm, Register reg) = 0; | 176 // Static factory function returning the singleton effect location. |
| 177 static Location* Effect() { |
| 178 return CfgGlobals::current()->effect_location(); |
| 179 } |
| 180 |
| 181 // Support for fast-compilation mode: |
| 182 |
| 183 // Assumes temporaries have been allocated. |
| 184 virtual void Get(MacroAssembler* masm, Register reg) = 0; |
| 185 |
| 186 // Store the value in a register to the location. Assumes temporaries |
| 187 // have been allocated. |
| 188 virtual void Set(MacroAssembler* masm, Register reg) = 0; |
| 189 |
| 190 // Assumes temporaries have been allocated, and if the value is a |
| 191 // temporary it was not allocated to the stack. |
| 192 virtual void Push(MacroAssembler* masm) = 0; |
116 | 193 |
117 #ifdef DEBUG | 194 #ifdef DEBUG |
118 virtual void Print() = 0; | 195 virtual void Print() = 0; |
119 #endif | 196 #endif |
120 }; | 197 }; |
121 | 198 |
122 | 199 |
| 200 // Effect is a special (singleton) location that indicates the value of a |
| 201 // computation is not needed (though its side effects are). |
| 202 class Effect : public Location { |
| 203 public: |
| 204 // We should not try to emit code to read or write to Effect. |
| 205 void Get(MacroAssembler* masm, Register reg) { UNREACHABLE(); } |
| 206 void Set(MacroAssembler* masm, Register reg) { UNREACHABLE(); } |
| 207 void Push(MacroAssembler* masm) { UNREACHABLE(); } |
| 208 |
| 209 #ifdef DEBUG |
| 210 void Print(); |
| 211 #endif |
| 212 |
| 213 private: |
| 214 Effect() {} |
| 215 |
| 216 friend class CfgGlobals; |
| 217 }; |
| 218 |
| 219 |
123 // SlotLocations represent parameters and stack-allocated (i.e., | 220 // SlotLocations represent parameters and stack-allocated (i.e., |
124 // non-context) local variables. | 221 // non-context) local variables. |
125 class SlotLocation : public Location { | 222 class SlotLocation : public Location { |
126 public: | 223 public: |
127 SlotLocation(Slot::Type type, int index) : type_(type), index_(index) {} | 224 SlotLocation(Slot::Type type, int index) : type_(type), index_(index) {} |
128 | 225 |
129 void ToRegister(MacroAssembler* masm, Register reg); | 226 // Accessors. |
| 227 Slot::Type type() { return type_; } |
| 228 int index() { return index_; } |
| 229 |
| 230 // Support for fast-compilation mode. |
| 231 void Get(MacroAssembler* masm, Register reg); |
| 232 void Set(MacroAssembler* masm, Register reg); |
| 233 void Push(MacroAssembler* masm); |
130 | 234 |
131 #ifdef DEBUG | 235 #ifdef DEBUG |
132 void Print(); | 236 void Print(); |
133 #endif | 237 #endif |
134 | 238 |
135 private: | 239 private: |
136 Slot::Type type_; | 240 Slot::Type type_; |
137 int index_; | 241 int index_; |
138 }; | 242 }; |
139 | 243 |
140 | 244 |
| 245 // TempLocations represent compiler generated temporaries. They are |
| 246 // allocated to registers or memory either before code generation (in the |
| 247 // optimized-for-speed compiler) or on the fly during code generation (in |
| 248 // the optimized-for-space compiler). |
| 249 class TempLocation : public Location { |
| 250 public: |
| 251 // Fast-compilation mode allocation decisions. |
| 252 enum Where { |
| 253 NOWHERE, // Not yet allocated. |
| 254 ACCUMULATOR, // Allocated to the dedicated accumulator register. |
| 255 STACK // " " " " stack. |
| 256 }; |
| 257 |
| 258 TempLocation() : where_(NOWHERE) { |
| 259 #ifdef DEBUG |
| 260 number_ = -1; |
| 261 #endif |
| 262 } |
| 263 |
| 264 // Cast accessor. |
| 265 static TempLocation* cast(Location* loc) { |
| 266 ASSERT(loc->is_temporary()); |
| 267 return reinterpret_cast<TempLocation*>(loc); |
| 268 } |
| 269 |
| 270 // Accessors. |
| 271 Where where() { return where_; } |
| 272 void set_where(Where where) { where_ = where; } |
| 273 |
| 274 // Predicates. |
| 275 bool is_on_stack() { return where_ == STACK; } |
| 276 bool is_temporary() { return true; } |
| 277 |
| 278 // Support for fast-compilation mode. Assume the temp has been allocated. |
| 279 void Get(MacroAssembler* masm, Register reg); |
| 280 void Set(MacroAssembler* masm, Register reg); |
| 281 void Push(MacroAssembler* masm); |
| 282 |
| 283 #ifdef DEBUG |
| 284 int number() { |
| 285 if (number_ == -1) number_ = CfgGlobals::current()->next_temp_number(); |
| 286 return number_; |
| 287 } |
| 288 |
| 289 void Print(); |
| 290 #endif |
| 291 |
| 292 private: |
| 293 Where where_; |
| 294 |
| 295 #ifdef DEBUG |
| 296 int number_; |
| 297 #endif |
| 298 }; |
| 299 |
| 300 |
141 // Instructions are computations. The represent non-trivial source | 301 // Instructions are computations. The represent non-trivial source |
142 // expressions: typically ones that have side effects and require code to | 302 // expressions: typically ones that have side effects and require code to |
143 // be generated. | 303 // be generated. |
144 class Instruction : public ZoneObject { | 304 class Instruction : public ZoneObject { |
145 public: | 305 public: |
| 306 // Every instruction has a location where its result is stored (which may |
| 307 // be Effect). |
| 308 Instruction(Location* loc) : loc_(loc) {} |
| 309 |
146 virtual ~Instruction() {} | 310 virtual ~Instruction() {} |
147 | 311 |
| 312 // Accessors. |
| 313 Location* location() { return loc_; } |
| 314 |
| 315 // Support for fast-compilation mode: |
| 316 |
| 317 // Emit code to perform the instruction. |
148 virtual void Compile(MacroAssembler* masm) = 0; | 318 virtual void Compile(MacroAssembler* masm) = 0; |
149 | 319 |
| 320 // Allocate a temporary which is the result of the immediate predecessor |
| 321 // instruction. It is allocated to the accumulator register if it is used |
| 322 // as an operand to this instruction, otherwise to the stack. |
| 323 virtual void FastAllocate(TempLocation* temp) = 0; |
| 324 |
150 #ifdef DEBUG | 325 #ifdef DEBUG |
151 virtual void Print() = 0; | 326 virtual void Print() = 0; |
152 #endif | 327 #endif |
| 328 |
| 329 protected: |
| 330 Location* loc_; |
153 }; | 331 }; |
154 | 332 |
155 | 333 |
156 // Return a value. | 334 // Perform a (non-short-circuited) binary operation on a pair of values, |
| 335 // leaving the result in a location. |
| 336 class BinaryOpInstr : public Instruction { |
| 337 public: |
| 338 BinaryOpInstr(Location* loc, Token::Value op, Value* val0, Value* val1) |
| 339 : Instruction(loc), op_(op), val0_(val0), val1_(val1) { |
| 340 } |
| 341 |
| 342 // Support for fast-compilation mode. |
| 343 void Compile(MacroAssembler* masm); |
| 344 void FastAllocate(TempLocation* temp); |
| 345 |
| 346 #ifdef DEBUG |
| 347 void Print(); |
| 348 #endif |
| 349 |
| 350 private: |
| 351 Token::Value op_; |
| 352 Value* val0_; |
| 353 Value* val1_; |
| 354 }; |
| 355 |
| 356 |
| 357 // Return a value. Has the side effect of moving its value into the return |
| 358 // value register. Can only occur as the last instruction in an instruction |
| 359 // block, and implies that the block is closed (cannot have instructions |
| 360 // appended or graph fragments concatenated to the end) and that the block's |
| 361 // successor is the global exit node for the current function. |
157 class ReturnInstr : public Instruction { | 362 class ReturnInstr : public Instruction { |
158 public: | 363 public: |
159 explicit ReturnInstr(Value* value) : value_(value) {} | 364 // Location is always Effect. |
| 365 explicit ReturnInstr(Value* value) |
| 366 : Instruction(CfgGlobals::current()->effect_location()), |
| 367 value_(value) { |
| 368 } |
160 | 369 |
161 virtual ~ReturnInstr() {} | 370 virtual ~ReturnInstr() {} |
162 | 371 |
| 372 // Support for fast-compilation mode. |
163 void Compile(MacroAssembler* masm); | 373 void Compile(MacroAssembler* masm); |
| 374 void FastAllocate(TempLocation* temp); |
164 | 375 |
165 #ifdef DEBUG | 376 #ifdef DEBUG |
166 void Print(); | 377 void Print(); |
167 #endif | 378 #endif |
168 | 379 |
169 private: | 380 private: |
170 Value* value_; | 381 Value* value_; |
171 }; | 382 }; |
172 | 383 |
173 | 384 |
174 // Nodes make up control-flow graphs. They contain single-entry, | 385 // Nodes make up control-flow graphs. |
175 // single-exit blocks of instructions and administrative nodes making up the | |
176 // graph structure. | |
177 class CfgNode : public ZoneObject { | 386 class CfgNode : public ZoneObject { |
178 public: | 387 public: |
179 CfgNode() : is_marked_(false) { | 388 CfgNode() : is_marked_(false) { |
180 #ifdef DEBUG | 389 #ifdef DEBUG |
181 number_ = -1; | 390 number_ = -1; |
182 #endif | 391 #endif |
183 } | 392 } |
184 | 393 |
185 virtual ~CfgNode() {} | 394 virtual ~CfgNode() {} |
186 | 395 |
| 396 // Because CFGs contain cycles, nodes support marking during traversal |
| 397 // (e.g., for printing or compilation). The traversal functions mark |
| 398 // unmarked nodes and bailout if they encounter a marked one. After a |
| 399 // traversal, the graph should be explicitly unmarked (by calling Unmark |
| 400 // on the entry node). |
187 bool is_marked() { return is_marked_; } | 401 bool is_marked() { return is_marked_; } |
| 402 virtual void Unmark() = 0; |
188 | 403 |
| 404 // Predicates: |
| 405 |
| 406 // True if the node is an instruction block. |
189 virtual bool is_block() { return false; } | 407 virtual bool is_block() { return false; } |
190 | 408 |
191 virtual void Unmark() = 0; | 409 // Support for fast-compilation mode. Emit the instructions or control |
192 | 410 // flow represented by the node. |
193 virtual void Compile(MacroAssembler* masm) = 0; | 411 virtual void Compile(MacroAssembler* masm) = 0; |
194 | 412 |
195 #ifdef DEBUG | 413 #ifdef DEBUG |
196 int number() { | 414 int number() { |
197 if (number_ == -1) number_ = CfgGlobals::current()->next_number(); | 415 if (number_ == -1) number_ = CfgGlobals::current()->next_node_number(); |
198 return number_; | 416 return number_; |
199 } | 417 } |
200 | 418 |
201 virtual void Print() = 0; | 419 virtual void Print() = 0; |
202 #endif | 420 #endif |
203 | 421 |
204 protected: | 422 protected: |
205 bool is_marked_; | 423 bool is_marked_; |
206 | 424 |
207 #ifdef DEBUG | 425 #ifdef DEBUG |
208 int number_; | 426 int number_; |
209 #endif | 427 #endif |
210 }; | 428 }; |
211 | 429 |
212 | 430 |
213 // A block is a single-entry, single-exit block of instructions. | 431 // A block is a single-entry, single-exit block of instructions. |
214 class InstructionBlock : public CfgNode { | 432 class InstructionBlock : public CfgNode { |
215 public: | 433 public: |
216 InstructionBlock() : successor_(NULL), instructions_(4) {} | 434 InstructionBlock() : successor_(NULL), instructions_(4) {} |
217 | 435 |
218 virtual ~InstructionBlock() {} | 436 virtual ~InstructionBlock() {} |
219 | 437 |
| 438 void Unmark(); |
| 439 |
| 440 // Cast accessor. |
220 static InstructionBlock* cast(CfgNode* node) { | 441 static InstructionBlock* cast(CfgNode* node) { |
221 ASSERT(node->is_block()); | 442 ASSERT(node->is_block()); |
222 return reinterpret_cast<InstructionBlock*>(node); | 443 return reinterpret_cast<InstructionBlock*>(node); |
223 } | 444 } |
224 | 445 |
| 446 bool is_block() { return true; } |
| 447 |
| 448 // Accessors. |
| 449 CfgNode* successor() { return successor_; } |
| 450 |
225 void set_successor(CfgNode* succ) { | 451 void set_successor(CfgNode* succ) { |
226 ASSERT(successor_ == NULL); | 452 ASSERT(successor_ == NULL); |
227 successor_ = succ; | 453 successor_ = succ; |
228 } | 454 } |
229 | 455 |
230 bool is_block() { return true; } | 456 ZoneList<Instruction*>* instructions() { return &instructions_; } |
231 | 457 |
232 void Unmark(); | 458 // Support for fast-compilation mode. |
233 | |
234 void Compile(MacroAssembler* masm); | 459 void Compile(MacroAssembler* masm); |
235 | 460 |
| 461 // Add an instruction to the end of the block. |
236 void Append(Instruction* instr) { instructions_.Add(instr); } | 462 void Append(Instruction* instr) { instructions_.Add(instr); } |
237 | 463 |
238 #ifdef DEBUG | 464 #ifdef DEBUG |
239 void Print(); | 465 void Print(); |
240 #endif | 466 #endif |
241 | 467 |
242 private: | 468 private: |
243 CfgNode* successor_; | 469 CfgNode* successor_; |
244 ZoneList<Instruction*> instructions_; | 470 ZoneList<Instruction*> instructions_; |
245 }; | 471 }; |
246 | 472 |
247 | 473 |
248 // The CFG for a function has a distinguished entry node. It has no | 474 // An entry node (one per function). |
249 // predecessors and a single successor. The successor is the block | |
250 // containing the function's first instruction. | |
251 class EntryNode : public CfgNode { | 475 class EntryNode : public CfgNode { |
252 public: | 476 public: |
253 explicit EntryNode(InstructionBlock* succ) : successor_(succ) {} | 477 explicit EntryNode(InstructionBlock* succ) : successor_(succ) {} |
254 | 478 |
255 virtual ~EntryNode() {} | 479 virtual ~EntryNode() {} |
256 | 480 |
257 void Unmark(); | 481 void Unmark(); |
258 | 482 |
| 483 // Support for fast-compilation mode. |
259 void Compile(MacroAssembler* masm); | 484 void Compile(MacroAssembler* masm); |
260 | 485 |
261 #ifdef DEBUG | 486 #ifdef DEBUG |
262 void Print(); | 487 void Print(); |
263 #endif | 488 #endif |
264 | 489 |
265 private: | 490 private: |
266 InstructionBlock* successor_; | 491 InstructionBlock* successor_; |
267 }; | 492 }; |
268 | 493 |
269 | 494 |
270 // The CFG for a function has a distinguished exit node. It has no | 495 // An exit node (one per function). |
271 // successor and arbitrarily many predecessors. The predecessors are all | |
272 // the blocks returning from the function. | |
273 class ExitNode : public CfgNode { | 496 class ExitNode : public CfgNode { |
274 public: | 497 public: |
275 ExitNode() {} | 498 ExitNode() {} |
276 | 499 |
277 virtual ~ExitNode() {} | 500 virtual ~ExitNode() {} |
278 | 501 |
279 void Unmark(); | 502 void Unmark(); |
280 | 503 |
| 504 // Support for fast-compilation mode. |
281 void Compile(MacroAssembler* masm); | 505 void Compile(MacroAssembler* masm); |
282 | 506 |
283 #ifdef DEBUG | 507 #ifdef DEBUG |
284 void Print(); | 508 void Print(); |
285 #endif | 509 #endif |
286 }; | 510 }; |
287 | 511 |
288 | 512 |
289 // A CFG consists of a linked structure of nodes. It has a single entry | 513 // A CFG consists of a linked structure of nodes. Nodes are linked by |
290 // node and optionally an exit node. There is a distinguished global exit | 514 // pointing to their successors, always beginning with a (single) entry node |
291 // node that is used as the successor of all blocks that return from the | 515 // (not necessarily of type EntryNode). If it is still possible to add |
292 // function. | 516 // nodes to the end of the graph (i.e., there is a (single) path that does |
| 517 // not end with the global exit node), then the CFG has an exit node as |
| 518 // well. |
293 // | 519 // |
294 // Fragments of control-flow graphs, produced when traversing the statements | 520 // The empty CFG is represented by a NULL entry and a NULL exit. |
295 // and expressions in the source AST, are represented by the same class. | |
296 // They have instruction blocks as both their entry and exit (if there is | |
297 // one). Instructions can always be prepended or appended to fragments, and | |
298 // fragments can always be concatenated. | |
299 // | 521 // |
300 // A singleton CFG fragment (i.e., with only one node) has the same node as | 522 // We use the term 'open fragment' to mean a CFG whose entry and exits are |
301 // both entry and exit (if the exit is available). | 523 // both instruction blocks. It is always possible to add instructions and |
| 524 // nodes to the beginning or end of an open fragment. |
| 525 // |
| 526 // We use the term 'closed fragment' to mean a CFG whose entry is an |
| 527 // instruction block and whose exit is NULL (all paths go to the global |
| 528 // exit). |
| 529 // |
| 530 // We use the term 'fragment' to refer to a CFG that is known to be an open |
| 531 // or closed fragment. |
302 class Cfg : public ZoneObject { | 532 class Cfg : public ZoneObject { |
303 public: | 533 public: |
304 // Create a singleton CFG fragment. | 534 // Create an empty CFG fragment. |
305 explicit Cfg(InstructionBlock* block) : entry_(block), exit_(block) {} | 535 Cfg() : entry_(NULL), exit_(NULL) {} |
306 | 536 |
307 // Build the CFG for a function. | 537 // Build the CFG for a function. The returned CFG begins with an |
| 538 // EntryNode and all paths end with the ExitNode. |
308 static Cfg* Build(); | 539 static Cfg* Build(); |
309 | 540 |
310 // The entry and exit nodes. | 541 // The entry and exit nodes of the CFG (not necessarily EntryNode and |
| 542 // ExitNode). |
311 CfgNode* entry() { return entry_; } | 543 CfgNode* entry() { return entry_; } |
312 CfgNode* exit() { return exit_; } | 544 CfgNode* exit() { return exit_; } |
313 | 545 |
314 // True if the CFG has no nodes. | 546 // True if the CFG has no nodes. |
315 bool is_empty() { return entry_ == NULL; } | 547 bool is_empty() { return entry_ == NULL; } |
316 | 548 |
317 // True if the CFG has an available exit node (i.e., it can be appended or | 549 // True if the CFG has an available exit node (i.e., it can be appended or |
318 // concatenated to). | 550 // concatenated to). |
319 bool has_exit() { return exit_ != NULL; } | 551 bool has_exit() { return exit_ != NULL; } |
320 | 552 |
321 // Add an entry node to a CFG fragment. It is no longer a fragment | 553 // Add an EntryNode to a CFG fragment. It is no longer a fragment |
322 // (instructions cannot be prepended). | 554 // (instructions can no longer be prepended). |
323 void PrependEntryNode(); | 555 void PrependEntryNode(); |
324 | 556 |
325 // Append an instruction to the end of a CFG fragment. Assumes it has an | 557 // Append an instruction to the end of an open fragment. |
326 // available exit. | |
327 void Append(Instruction* instr); | 558 void Append(Instruction* instr); |
328 | 559 |
329 // Appends a return instruction to the end of a CFG fragment. It no | 560 // Appends a return instruction to the end of an open fragment and make |
330 // longer has an available exit node. | 561 // it a closed fragment (the exit's successor becomes global exit node). |
331 void AppendReturnInstruction(Value* value); | 562 void AppendReturnInstruction(Value* value); |
332 | 563 |
| 564 // Glue an other CFG fragment to the end of this (open) fragment. |
| 565 void Concatenate(Cfg* other); |
| 566 |
| 567 // Support for compilation. Compile the entire CFG. |
333 Handle<Code> Compile(Handle<Script> script); | 568 Handle<Code> Compile(Handle<Script> script); |
334 | 569 |
335 #ifdef DEBUG | 570 #ifdef DEBUG |
336 // Support for printing. | 571 // Support for printing. |
337 void Print(); | 572 void Print(); |
338 #endif | 573 #endif |
339 | 574 |
340 private: | 575 private: |
341 // Entry and exit nodes. | 576 // Entry and exit nodes. |
342 CfgNode* entry_; | 577 CfgNode* entry_; |
343 CfgNode* exit_; | 578 CfgNode* exit_; |
344 }; | 579 }; |
345 | 580 |
346 | 581 |
347 // An Expression Builder traverses a trivial expression and returns a value. | 582 // An ExpressionBuilder traverses an expression and returns an open CFG |
| 583 // fragment (currently a possibly empty list of instructions represented by |
| 584 // a singleton instruction block) and the expression's value. |
| 585 // |
| 586 // Failure is to build the CFG is indicated by a NULL CFG. |
348 class ExpressionBuilder : public AstVisitor { | 587 class ExpressionBuilder : public AstVisitor { |
349 public: | 588 public: |
350 ExpressionBuilder() : value_(new Constant(Handle<Object>::null())) {} | 589 ExpressionBuilder() : value_(NULL), cfg_(NULL) {} |
351 | 590 |
| 591 // Result accessors. |
352 Value* value() { return value_; } | 592 Value* value() { return value_; } |
| 593 Cfg* cfg() { return cfg_; } |
| 594 |
| 595 void Build(Expression* expr) { |
| 596 value_ = NULL; |
| 597 cfg_ = new Cfg(); |
| 598 Visit(expr); |
| 599 } |
353 | 600 |
354 // AST node visitors. | 601 // AST node visitors. |
355 #define DECLARE_VISIT(type) void Visit##type(type* node); | 602 #define DECLARE_VISIT(type) void Visit##type(type* node); |
356 AST_NODE_LIST(DECLARE_VISIT) | 603 AST_NODE_LIST(DECLARE_VISIT) |
357 #undef DECLARE_VISIT | 604 #undef DECLARE_VISIT |
358 | 605 |
359 private: | 606 private: |
360 Value* value_; | 607 Value* value_; |
| 608 Cfg* cfg_; |
361 }; | 609 }; |
362 | 610 |
363 | 611 |
364 // A StatementBuilder traverses a statement and returns a CFG. | 612 // A StatementBuilder maintains a CFG fragment accumulator. When it visits |
| 613 // a statement, it concatenates the CFG for the statement to the end of the |
| 614 // accumulator. |
365 class StatementBuilder : public AstVisitor { | 615 class StatementBuilder : public AstVisitor { |
366 public: | 616 public: |
367 StatementBuilder() : cfg_(new Cfg(new InstructionBlock())) {} | 617 StatementBuilder() : cfg_(new Cfg()) {} |
368 | 618 |
369 Cfg* cfg() { return cfg_; } | 619 Cfg* cfg() { return cfg_; } |
370 | 620 |
371 void VisitStatements(ZoneList<Statement*>* stmts); | 621 void VisitStatements(ZoneList<Statement*>* stmts); |
372 | 622 |
373 // AST node visitors. | 623 // AST node visitors. |
374 #define DECLARE_VISIT(type) void Visit##type(type* node); | 624 #define DECLARE_VISIT(type) void Visit##type(type* node); |
375 AST_NODE_LIST(DECLARE_VISIT) | 625 AST_NODE_LIST(DECLARE_VISIT) |
376 #undef DECLARE_VISIT | 626 #undef DECLARE_VISIT |
377 | 627 |
378 private: | 628 private: |
379 Cfg* cfg_; | 629 Cfg* cfg_; |
380 }; | 630 }; |
381 | 631 |
382 | 632 |
383 } } // namespace v8::internal | 633 } } // namespace v8::internal |
384 | 634 |
385 #endif // V8_CFG_H_ | 635 #endif // V8_CFG_H_ |
OLD | NEW |