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 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 // Move <Location> <Value> | |
47 // | PropLoad <Location> <Value> <Value> | |
48 // | BinaryOp <Location> Token::Value <Value> <Value> | |
49 // | Return Nowhere <Value> | |
50 // | Position <Int> | |
51 // | |
52 // Values are trivial expressions: | |
53 // | |
54 // <Value> ::= Constant | <Location> | |
55 // | |
56 // Locations are storable values ('lvalues'). They can be slots, | |
57 // compiler-generated temporaries, or the special location 'Nowhere' | |
58 // indicating that no value is needed. | |
59 // | |
60 // <Location> ::= | |
61 // SlotLocation Slot::Type <Index> | |
62 // | TempLocation | |
63 // | Nowhere | |
64 | |
65 | |
66 // Administrative nodes: There are several types of 'administrative' nodes | |
67 // that do not contain instructions and do not necessarily have a single | |
68 // predecessor and a single successor. | |
69 // | |
70 // EntryNode: there is a distinguished entry node that has no predecessors | |
71 // and a single successor. | |
72 // | |
73 // ExitNode: there is a distinguished exit node that has arbitrarily many | |
74 // predecessors and no successor. | |
75 // | |
76 // JoinNode: join nodes have multiple predecessors and a single successor. | |
77 // | |
78 // BranchNode: branch nodes have a single predecessor and multiple | |
79 // successors. | |
80 | |
81 | |
82 // A convenient class to keep 'global' values when building a CFG. Since | |
83 // CFG construction can be invoked recursively, CFG globals are stacked. | |
84 class CfgGlobals BASE_EMBEDDED { | |
85 public: | |
86 explicit CfgGlobals(FunctionLiteral* fun); | |
87 | |
88 ~CfgGlobals() { top_ = previous_; } | |
89 | |
90 static CfgGlobals* current() { | |
91 ASSERT(top_ != NULL); | |
92 return top_; | |
93 } | |
94 | |
95 // The function currently being compiled. | |
96 FunctionLiteral* fun() { return global_fun_; } | |
97 | |
98 // The shared global exit node for all exits from the function. | |
99 ExitNode* exit() { return global_exit_; } | |
100 | |
101 // A singleton. | |
102 Location* nowhere() { return nowhere_; } | |
103 | |
104 #ifdef DEBUG | |
105 int next_node_number() { return node_counter_++; } | |
106 int next_temp_number() { return temp_counter_++; } | |
107 #endif | |
108 | |
109 private: | |
110 static CfgGlobals* top_; | |
111 FunctionLiteral* global_fun_; | |
112 ExitNode* global_exit_; | |
113 Location* nowhere_; | |
114 | |
115 #ifdef DEBUG | |
116 // Used to number nodes and temporaries when printing. | |
117 int node_counter_; | |
118 int temp_counter_; | |
119 #endif | |
120 | |
121 CfgGlobals* previous_; | |
122 }; | |
123 | |
124 | |
125 class SlotLocation; | |
126 | |
127 // Values represent trivial source expressions: ones with no side effects | |
128 // and that do not require code to be generated. | |
129 class Value : public ZoneObject { | |
130 public: | |
131 virtual ~Value() {} | |
132 | |
133 // Predicates: | |
134 | |
135 virtual bool is_temporary() { return false; } | |
136 virtual bool is_slot() { return false; } | |
137 virtual bool is_constant() { return false; } | |
138 | |
139 // True if the value is a temporary allocated to the stack in | |
140 // fast-compilation mode. | |
141 virtual bool is_on_stack() { return false; } | |
142 | |
143 // Support for fast-compilation mode: | |
144 | |
145 // Move the value into a register. | |
146 virtual void Get(MacroAssembler* masm, Register reg) = 0; | |
147 | |
148 // Push the value on the stack. | |
149 virtual void Push(MacroAssembler* masm) = 0; | |
150 | |
151 // Move the value into a slot location. | |
152 virtual void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) = 0; | |
153 | |
154 #ifdef DEBUG | |
155 virtual void Print() = 0; | |
156 #endif | |
157 }; | |
158 | |
159 | |
160 // A compile-time constant that appeared as a literal in the source AST. | |
161 class Constant : public Value { | |
162 public: | |
163 explicit Constant(Handle<Object> handle) : handle_(handle) {} | |
164 | |
165 // Cast accessor. | |
166 static Constant* cast(Value* value) { | |
167 ASSERT(value->is_constant()); | |
168 return reinterpret_cast<Constant*>(value); | |
169 } | |
170 | |
171 // Accessors. | |
172 Handle<Object> handle() { return handle_; } | |
173 | |
174 // Predicates. | |
175 bool is_constant() { return true; } | |
176 | |
177 // Support for fast-compilation mode. | |
178 void Get(MacroAssembler* masm, Register reg); | |
179 void Push(MacroAssembler* masm); | |
180 void MoveToSlot(MacroAssembler* masm, SlotLocation* loc); | |
181 | |
182 #ifdef DEBUG | |
183 void Print(); | |
184 #endif | |
185 | |
186 private: | |
187 Handle<Object> handle_; | |
188 }; | |
189 | |
190 | |
191 // Locations are values that can be stored into ('lvalues'). | |
192 class Location : public Value { | |
193 public: | |
194 virtual ~Location() {} | |
195 | |
196 // Static factory function returning the singleton nowhere location. | |
197 static Location* Nowhere() { | |
198 return CfgGlobals::current()->nowhere(); | |
199 } | |
200 | |
201 // Support for fast-compilation mode: | |
202 | |
203 // Assumes temporaries have been allocated. | |
204 virtual void Get(MacroAssembler* masm, Register reg) = 0; | |
205 | |
206 // Store the value in a register to the location. Assumes temporaries | |
207 // have been allocated. | |
208 virtual void Set(MacroAssembler* masm, Register reg) = 0; | |
209 | |
210 // Assumes temporaries have been allocated, and if the value is a | |
211 // temporary it was not allocated to the stack. | |
212 virtual void Push(MacroAssembler* masm) = 0; | |
213 | |
214 // Emit code to move a value into this location. | |
215 virtual void Move(MacroAssembler* masm, Value* value) = 0; | |
216 | |
217 #ifdef DEBUG | |
218 virtual void Print() = 0; | |
219 #endif | |
220 }; | |
221 | |
222 | |
223 // Nowhere is a special (singleton) location that indicates the value of a | |
224 // computation is not needed (though its side effects are). | |
225 class Nowhere : public Location { | |
226 public: | |
227 // We should not try to emit code to read Nowhere. | |
228 void Get(MacroAssembler* masm, Register reg) { UNREACHABLE(); } | |
229 void Push(MacroAssembler* masm) { UNREACHABLE(); } | |
230 void MoveToSlot(MacroAssembler* masm, SlotLocation* loc) { UNREACHABLE(); } | |
231 | |
232 // Setting Nowhere is ignored. | |
233 void Set(MacroAssembler* masm, Register reg) {} | |
234 void Move(MacroAssembler* masm, Value* value) {} | |
235 | |
236 #ifdef DEBUG | |
237 void Print(); | |
238 #endif | |
239 | |
240 private: | |
241 Nowhere() {} | |
242 | |
243 friend class CfgGlobals; | |
244 }; | |
245 | |
246 | |
247 // SlotLocations represent parameters and stack-allocated (i.e., | |
248 // non-context) local variables. | |
249 class SlotLocation : public Location { | |
250 public: | |
251 SlotLocation(Slot::Type type, int index) : type_(type), index_(index) {} | |
252 | |
253 // Cast accessor. | |
254 static SlotLocation* cast(Value* value) { | |
255 ASSERT(value->is_slot()); | |
256 return reinterpret_cast<SlotLocation*>(value); | |
257 } | |
258 | |
259 // Accessors. | |
260 Slot::Type type() { return type_; } | |
261 int index() { return index_; } | |
262 | |
263 // Predicates. | |
264 bool is_slot() { return true; } | |
265 | |
266 // Support for fast-compilation mode. | |
267 void Get(MacroAssembler* masm, Register reg); | |
268 void Set(MacroAssembler* masm, Register reg); | |
269 void Push(MacroAssembler* masm); | |
270 void Move(MacroAssembler* masm, Value* value); | |
271 void MoveToSlot(MacroAssembler* masm, SlotLocation* loc); | |
272 | |
273 #ifdef DEBUG | |
274 void Print(); | |
275 #endif | |
276 | |
277 private: | |
278 Slot::Type type_; | |
279 int index_; | |
280 }; | |
281 | |
282 | |
283 // TempLocations represent compiler generated temporaries. They are | |
284 // allocated to registers or memory either before code generation (in the | |
285 // optimized-for-speed compiler) or on the fly during code generation (in | |
286 // the optimized-for-space compiler). | |
287 class TempLocation : public Location { | |
288 public: | |
289 // Fast-compilation mode allocation decisions. | |
290 enum Where { | |
291 NOT_ALLOCATED, // Not yet allocated. | |
292 ACCUMULATOR, // Allocated to the dedicated accumulator register. | |
293 STACK // " " " " stack. | |
294 }; | |
295 | |
296 TempLocation() : where_(NOT_ALLOCATED) { | |
297 #ifdef DEBUG | |
298 number_ = -1; | |
299 #endif | |
300 } | |
301 | |
302 // Cast accessor. | |
303 static TempLocation* cast(Value* value) { | |
304 ASSERT(value->is_temporary()); | |
305 return reinterpret_cast<TempLocation*>(value); | |
306 } | |
307 | |
308 // Accessors. | |
309 Where where() { return where_; } | |
310 void set_where(Where where) { | |
311 ASSERT(where_ == TempLocation::NOT_ALLOCATED); | |
312 where_ = where; | |
313 } | |
314 | |
315 // Predicates. | |
316 bool is_on_stack() { return where_ == STACK; } | |
317 bool is_temporary() { return true; } | |
318 | |
319 // Support for fast-compilation mode. Assume the temp has been allocated. | |
320 void Get(MacroAssembler* masm, Register reg); | |
321 void Set(MacroAssembler* masm, Register reg); | |
322 void Push(MacroAssembler* masm); | |
323 void Move(MacroAssembler* masm, Value* value); | |
324 void MoveToSlot(MacroAssembler* masm, SlotLocation* loc); | |
325 | |
326 #ifdef DEBUG | |
327 int number() { | |
328 if (number_ == -1) number_ = CfgGlobals::current()->next_temp_number(); | |
329 return number_; | |
330 } | |
331 | |
332 void Print(); | |
333 #endif | |
334 | |
335 private: | |
336 Where where_; | |
337 | |
338 #ifdef DEBUG | |
339 int number_; | |
340 #endif | |
341 }; | |
342 | |
343 | |
344 // Instructions are computations. The represent non-trivial source | |
345 // expressions: typically ones that have side effects and require code to | |
346 // be generated. | |
347 class Instruction : public ZoneObject { | |
348 public: | |
349 // Accessors. | |
350 Location* location() { return location_; } | |
351 void set_location(Location* location) { location_ = location; } | |
352 | |
353 // Support for fast-compilation mode: | |
354 | |
355 // Emit code to perform the instruction. | |
356 virtual void Compile(MacroAssembler* masm) = 0; | |
357 | |
358 // Allocate a temporary which is the result of the immediate predecessor | |
359 // instruction. It is allocated to the accumulator register if it is used | |
360 // as an operand to this instruction, otherwise to the stack. | |
361 virtual void FastAllocate(TempLocation* temp) = 0; | |
362 | |
363 #ifdef DEBUG | |
364 virtual void Print() = 0; | |
365 #endif | |
366 | |
367 protected: | |
368 // Every instruction has a location where its result is stored (which may | |
369 // be Nowhere). | |
370 explicit Instruction(Location* location) : location_(location) {} | |
371 | |
372 virtual ~Instruction() {} | |
373 | |
374 Location* location_; | |
375 }; | |
376 | |
377 | |
378 // Base class of instructions that have no input operands. | |
379 class ZeroOperandInstruction : public Instruction { | |
380 public: | |
381 // Support for fast-compilation mode: | |
382 virtual void Compile(MacroAssembler* masm) = 0; | |
383 void FastAllocate(TempLocation* temp); | |
384 | |
385 #ifdef DEBUG | |
386 // Printing support: print the operands (nothing). | |
387 virtual void Print() {} | |
388 #endif | |
389 | |
390 protected: | |
391 explicit ZeroOperandInstruction(Location* loc) : Instruction(loc) {} | |
392 }; | |
393 | |
394 | |
395 // Base class of instructions that have a single input operand. | |
396 class OneOperandInstruction : public Instruction { | |
397 public: | |
398 // Support for fast-compilation mode: | |
399 virtual void Compile(MacroAssembler* masm) = 0; | |
400 void FastAllocate(TempLocation* temp); | |
401 | |
402 #ifdef DEBUG | |
403 // Printing support: print the operands. | |
404 virtual void Print(); | |
405 #endif | |
406 | |
407 protected: | |
408 OneOperandInstruction(Location* loc, Value* value) | |
409 : Instruction(loc), value_(value) { | |
410 } | |
411 | |
412 Value* value_; | |
413 }; | |
414 | |
415 | |
416 // Base class of instructions that have two input operands. | |
417 class TwoOperandInstruction : public Instruction { | |
418 public: | |
419 // Support for fast-compilation mode: | |
420 virtual void Compile(MacroAssembler* masm) = 0; | |
421 void FastAllocate(TempLocation* temp); | |
422 | |
423 #ifdef DEBUG | |
424 // Printing support: print the operands. | |
425 virtual void Print(); | |
426 #endif | |
427 | |
428 protected: | |
429 TwoOperandInstruction(Location* loc, Value* value0, Value* value1) | |
430 : Instruction(loc), value0_(value0), value1_(value1) { | |
431 } | |
432 | |
433 Value* value0_; | |
434 Value* value1_; | |
435 }; | |
436 | |
437 | |
438 // A phantom instruction that indicates the start of a statement. It | |
439 // causes the statement position to be recorded in the relocation | |
440 // information but generates no code. | |
441 class PositionInstr : public ZeroOperandInstruction { | |
442 public: | |
443 explicit PositionInstr(int pos) | |
444 : ZeroOperandInstruction(CfgGlobals::current()->nowhere()), pos_(pos) { | |
445 } | |
446 | |
447 // Support for fast-compilation mode. | |
448 void Compile(MacroAssembler* masm); | |
449 | |
450 // This should not be called. The last instruction of the previous | |
451 // statement should not have a temporary as its location. | |
452 void FastAllocate(TempLocation* temp) { UNREACHABLE(); } | |
453 | |
454 #ifdef DEBUG | |
455 // Printing support. Print nothing. | |
456 void Print() {} | |
457 #endif | |
458 | |
459 private: | |
460 int pos_; | |
461 }; | |
462 | |
463 | |
464 // Move a value to a location. | |
465 class MoveInstr : public OneOperandInstruction { | |
466 public: | |
467 MoveInstr(Location* loc, Value* value) | |
468 : OneOperandInstruction(loc, value) { | |
469 } | |
470 | |
471 // Accessors. | |
472 Value* value() { return value_; } | |
473 | |
474 // Support for fast-compilation mode. | |
475 void Compile(MacroAssembler* masm); | |
476 | |
477 #ifdef DEBUG | |
478 // Printing support. | |
479 void Print(); | |
480 #endif | |
481 }; | |
482 | |
483 | |
484 // Load a property from a receiver, leaving the result in a location. | |
485 class PropLoadInstr : public TwoOperandInstruction { | |
486 public: | |
487 PropLoadInstr(Location* loc, Value* object, Value* key) | |
488 : TwoOperandInstruction(loc, object, key) { | |
489 } | |
490 | |
491 // Accessors. | |
492 Value* object() { return value0_; } | |
493 Value* key() { return value1_; } | |
494 | |
495 // Support for fast-compilation mode. | |
496 void Compile(MacroAssembler* masm); | |
497 | |
498 #ifdef DEBUG | |
499 void Print(); | |
500 #endif | |
501 }; | |
502 | |
503 | |
504 // Perform a (non-short-circuited) binary operation on a pair of values, | |
505 // leaving the result in a location. | |
506 class BinaryOpInstr : public TwoOperandInstruction { | |
507 public: | |
508 BinaryOpInstr(Location* loc, Token::Value op, Value* left, Value* right) | |
509 : TwoOperandInstruction(loc, left, right), op_(op) { | |
510 } | |
511 | |
512 // Accessors. | |
513 Value* left() { return value0_; } | |
514 Value* right() { return value1_; } | |
515 Token::Value op() { return op_; } | |
516 | |
517 // Support for fast-compilation mode. | |
518 void Compile(MacroAssembler* masm); | |
519 | |
520 #ifdef DEBUG | |
521 void Print(); | |
522 #endif | |
523 | |
524 private: | |
525 Token::Value op_; | |
526 }; | |
527 | |
528 | |
529 // Return a value. Has the side effect of moving its value into the return | |
530 // value register. Can only occur as the last instruction in an instruction | |
531 // block, and implies that the block is closed (cannot have instructions | |
532 // appended or graph fragments concatenated to the end) and that the block's | |
533 // successor is the global exit node for the current function. | |
534 class ReturnInstr : public OneOperandInstruction { | |
535 public: | |
536 explicit ReturnInstr(Value* value) | |
537 : OneOperandInstruction(CfgGlobals::current()->nowhere(), value) { | |
538 } | |
539 | |
540 virtual ~ReturnInstr() {} | |
541 | |
542 // Accessors. | |
543 Value* value() { return value_; } | |
544 | |
545 // Support for fast-compilation mode. | |
546 void Compile(MacroAssembler* masm); | |
547 | |
548 #ifdef DEBUG | |
549 void Print(); | |
550 #endif | |
551 }; | |
552 | |
553 | |
554 // Nodes make up control-flow graphs. | |
555 class CfgNode : public ZoneObject { | |
556 public: | |
557 CfgNode() : is_marked_(false) { | |
558 #ifdef DEBUG | |
559 number_ = -1; | |
560 #endif | |
561 } | |
562 | |
563 virtual ~CfgNode() {} | |
564 | |
565 // Because CFGs contain cycles, nodes support marking during traversal | |
566 // (e.g., for printing or compilation). The traversal functions will mark | |
567 // unmarked nodes and backtrack if they encounter a marked one. After a | |
568 // traversal, the graph should be explicitly unmarked by calling Unmark on | |
569 // the entry node. | |
570 bool is_marked() { return is_marked_; } | |
571 virtual void Unmark() = 0; | |
572 | |
573 // Predicates: | |
574 | |
575 // True if the node is an instruction block. | |
576 virtual bool is_block() { return false; } | |
577 | |
578 // Support for fast-compilation mode. Emit the instructions or control | |
579 // flow represented by the node. | |
580 virtual void Compile(MacroAssembler* masm) = 0; | |
581 | |
582 #ifdef DEBUG | |
583 int number() { | |
584 if (number_ == -1) number_ = CfgGlobals::current()->next_node_number(); | |
585 return number_; | |
586 } | |
587 | |
588 virtual void Print() = 0; | |
589 #endif | |
590 | |
591 protected: | |
592 bool is_marked_; | |
593 | |
594 #ifdef DEBUG | |
595 int number_; | |
596 #endif | |
597 }; | |
598 | |
599 | |
600 // A block is a single-entry, single-exit block of instructions. | |
601 class InstructionBlock : public CfgNode { | |
602 public: | |
603 InstructionBlock() : successor_(NULL), instructions_(4) {} | |
604 | |
605 virtual ~InstructionBlock() {} | |
606 | |
607 void Unmark(); | |
608 | |
609 // Cast accessor. | |
610 static InstructionBlock* cast(CfgNode* node) { | |
611 ASSERT(node->is_block()); | |
612 return reinterpret_cast<InstructionBlock*>(node); | |
613 } | |
614 | |
615 bool is_block() { return true; } | |
616 | |
617 // Accessors. | |
618 CfgNode* successor() { return successor_; } | |
619 | |
620 void set_successor(CfgNode* succ) { | |
621 ASSERT(successor_ == NULL); | |
622 successor_ = succ; | |
623 } | |
624 | |
625 ZoneList<Instruction*>* instructions() { return &instructions_; } | |
626 | |
627 // Support for fast-compilation mode. | |
628 void Compile(MacroAssembler* masm); | |
629 | |
630 // Add an instruction to the end of the block. | |
631 void Append(Instruction* instr) { instructions_.Add(instr); } | |
632 | |
633 #ifdef DEBUG | |
634 void Print(); | |
635 #endif | |
636 | |
637 private: | |
638 CfgNode* successor_; | |
639 ZoneList<Instruction*> instructions_; | |
640 }; | |
641 | |
642 | |
643 // An entry node (one per function). | |
644 class EntryNode : public CfgNode { | |
645 public: | |
646 explicit EntryNode(InstructionBlock* succ) : successor_(succ) {} | |
647 | |
648 virtual ~EntryNode() {} | |
649 | |
650 void Unmark(); | |
651 | |
652 // Support for fast-compilation mode. | |
653 void Compile(MacroAssembler* masm); | |
654 | |
655 #ifdef DEBUG | |
656 void Print(); | |
657 #endif | |
658 | |
659 private: | |
660 InstructionBlock* successor_; | |
661 }; | |
662 | |
663 | |
664 // An exit node (one per function). | |
665 class ExitNode : public CfgNode { | |
666 public: | |
667 ExitNode() {} | |
668 | |
669 virtual ~ExitNode() {} | |
670 | |
671 void Unmark(); | |
672 | |
673 // Support for fast-compilation mode. | |
674 void Compile(MacroAssembler* masm); | |
675 | |
676 #ifdef DEBUG | |
677 void Print(); | |
678 #endif | |
679 }; | |
680 | |
681 | |
682 // A CFG consists of a linked structure of nodes. Nodes are linked by | |
683 // pointing to their successors, always beginning with a (single) entry node | |
684 // (not necessarily of type EntryNode). If it is still possible to add | |
685 // nodes to the end of the graph (i.e., there is a (single) path that does | |
686 // not end with the global exit node), then the CFG has an exit node as | |
687 // well. | |
688 // | |
689 // The empty CFG is represented by a NULL entry and a NULL exit. | |
690 // | |
691 // We use the term 'open fragment' to mean a CFG whose entry and exits are | |
692 // both instruction blocks. It is always possible to add instructions and | |
693 // nodes to the beginning or end of an open fragment. | |
694 // | |
695 // We use the term 'closed fragment' to mean a CFG whose entry is an | |
696 // instruction block and whose exit is NULL (all paths go to the global | |
697 // exit). | |
698 // | |
699 // We use the term 'fragment' to refer to a CFG that is known to be an open | |
700 // or closed fragment. | |
701 class Cfg : public ZoneObject { | |
702 public: | |
703 // Create an empty CFG fragment. | |
704 Cfg() : entry_(NULL), exit_(NULL) {} | |
705 | |
706 // Build the CFG for a function. The returned CFG begins with an | |
707 // EntryNode and all paths end with the ExitNode. | |
708 static Cfg* Build(); | |
709 | |
710 // The entry and exit nodes of the CFG (not necessarily EntryNode and | |
711 // ExitNode). | |
712 CfgNode* entry() { return entry_; } | |
713 CfgNode* exit() { return exit_; } | |
714 | |
715 // True if the CFG has no nodes. | |
716 bool is_empty() { return entry_ == NULL; } | |
717 | |
718 // True if the CFG has an available exit node (i.e., it can be appended or | |
719 // concatenated to). | |
720 bool has_exit() { return exit_ != NULL; } | |
721 | |
722 // Add an EntryNode to a CFG fragment. It is no longer a fragment | |
723 // (instructions can no longer be prepended). | |
724 void PrependEntryNode(); | |
725 | |
726 // Append an instruction to the end of an open fragment. | |
727 void Append(Instruction* instr); | |
728 | |
729 // Appends a return instruction to the end of an open fragment and make | |
730 // it a closed fragment (the exit's successor becomes global exit node). | |
731 void AppendReturnInstruction(Value* value); | |
732 | |
733 // Glue an other CFG fragment to the end of this (open) fragment. | |
734 void Concatenate(Cfg* other); | |
735 | |
736 // Support for compilation. Compile the entire CFG. | |
737 Handle<Code> Compile(Handle<Script> script); | |
738 | |
739 #ifdef DEBUG | |
740 // Support for printing. | |
741 void Print(); | |
742 #endif | |
743 | |
744 private: | |
745 // Entry and exit nodes. | |
746 CfgNode* entry_; | |
747 CfgNode* exit_; | |
748 }; | |
749 | |
750 | |
751 // An implementation of a set of locations (currently slot locations), most | |
752 // of the operations are destructive. | |
753 class LocationSet BASE_EMBEDDED { | |
754 public: | |
755 // Construct an empty location set. | |
756 LocationSet() : parameters_(0), locals_(0) {} | |
757 | |
758 // Raw accessors. | |
759 uintptr_t parameters() { return parameters_; } | |
760 uintptr_t locals() { return locals_; } | |
761 | |
762 // Make this the empty set. | |
763 void Empty() { | |
764 parameters_ = locals_ = 0; | |
765 } | |
766 | |
767 // Insert an element. | |
768 void AddElement(SlotLocation* location) { | |
769 if (location->type() == Slot::PARAMETER) { | |
770 // Parameter indexes begin with -1 ('this'). | |
771 ASSERT(location->index() < kBitsPerPointer - 1); | |
772 parameters_ |= (1 << (location->index() + 1)); | |
773 } else { | |
774 ASSERT(location->type() == Slot::LOCAL); | |
775 ASSERT(location->index() < kBitsPerPointer); | |
776 locals_ |= (1 << location->index()); | |
777 } | |
778 } | |
779 | |
780 // (Destructively) compute the union with another set. | |
781 void Union(LocationSet* other) { | |
782 parameters_ |= other->parameters(); | |
783 locals_ |= other->locals(); | |
784 } | |
785 | |
786 bool Contains(SlotLocation* location) { | |
787 if (location->type() == Slot::PARAMETER) { | |
788 ASSERT(location->index() < kBitsPerPointer - 1); | |
789 return (parameters_ & (1 << (location->index() + 1))); | |
790 } else { | |
791 ASSERT(location->type() == Slot::LOCAL); | |
792 ASSERT(location->index() < kBitsPerPointer); | |
793 return (locals_ & (1 << location->index())); | |
794 } | |
795 } | |
796 | |
797 private: | |
798 uintptr_t parameters_; | |
799 uintptr_t locals_; | |
800 }; | |
801 | |
802 | |
803 // An ExpressionCfgBuilder traverses an expression and returns an open CFG | |
804 // fragment (currently a possibly empty list of instructions represented by | |
805 // a singleton instruction block) and the expression's value. | |
806 // | |
807 // Failure to build the CFG is indicated by a NULL CFG. | |
808 class ExpressionCfgBuilder : public AstVisitor { | |
809 public: | |
810 ExpressionCfgBuilder() : destination_(NULL), value_(NULL), graph_(NULL) {} | |
811 | |
812 // Result accessors. | |
813 Value* value() { return value_; } | |
814 Cfg* graph() { return graph_; } | |
815 LocationSet* assigned_vars() { return &assigned_vars_; } | |
816 | |
817 // Build the cfg for an expression and remember its value. The | |
818 // destination is a 'hint' where the value should go which may be ignored. | |
819 // NULL is used to indicate no preference. | |
820 // | |
821 // Concretely, if the expression needs to generate a temporary for its | |
822 // value, it should use the passed destination or generate one if NULL. | |
823 void Build(Expression* expr, Location* destination) { | |
824 value_ = NULL; | |
825 graph_ = new Cfg(); | |
826 assigned_vars_.Empty(); | |
827 destination_ = destination; | |
828 Visit(expr); | |
829 } | |
830 | |
831 // AST node visitors. | |
832 #define DECLARE_VISIT(type) void Visit##type(type* node); | |
833 AST_NODE_LIST(DECLARE_VISIT) | |
834 #undef DECLARE_VISIT | |
835 | |
836 private: | |
837 // State for the visitor. Input parameter: | |
838 Location* destination_; | |
839 | |
840 // Output parameters: | |
841 Value* value_; | |
842 Cfg* graph_; | |
843 LocationSet assigned_vars_; | |
844 }; | |
845 | |
846 | |
847 // A StatementCfgBuilder maintains a CFG fragment accumulator. When it | |
848 // visits a statement, it concatenates the CFG for the statement to the end | |
849 // of the accumulator. | |
850 class StatementCfgBuilder : public AstVisitor { | |
851 public: | |
852 StatementCfgBuilder() : graph_(new Cfg()) {} | |
853 | |
854 Cfg* graph() { return graph_; } | |
855 | |
856 void VisitStatements(ZoneList<Statement*>* stmts); | |
857 | |
858 // AST node visitors. | |
859 #define DECLARE_VISIT(type) void Visit##type(type* node); | |
860 AST_NODE_LIST(DECLARE_VISIT) | |
861 #undef DECLARE_VISIT | |
862 | |
863 private: | |
864 // State for the visitor. Input/output parameter: | |
865 Cfg* graph_; | |
866 }; | |
867 | |
868 | |
869 } } // namespace v8::internal | |
870 | |
871 #endif // V8_CFG_H_ | |
OLD | NEW |