hydrogen.h revision 8b112d2025046f85ef7f6be087c6129c872ebad2 
1// Copyright 2011 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_HYDROGEN_H_
29#define V8_HYDROGEN_H_
30
31#include "v8.h"
32
33#include "ast.h"
34#include "compiler.h"
35#include "data-flow.h"
36#include "hydrogen-instructions.h"
37#include "zone.h"
38
39namespace v8 {
40namespace internal {
41
42// Forward declarations.
43class HEnvironment;
44class HGraph;
45class HLoopInformation;
46class HTracer;
47class LAllocator;
48class LChunk;
49class LiveRange;
50
51
52class HBasicBlock: public ZoneObject {
53 public:
54  explicit HBasicBlock(HGraph* graph);
55  virtual ~HBasicBlock() { }
56
57  // Simple accessors.
58  int block_id() const { return block_id_; }
59  void set_block_id(int id) { block_id_ = id; }
60  HGraph* graph() const { return graph_; }
61  const ZoneList<HPhi*>* phis() const { return &phis_; }
62  HInstruction* first() const { return first_; }
63  HInstruction* last() const { return last_; }
64  void set_last(HInstruction* instr) { last_ = instr; }
65  HInstruction* GetLastInstruction();
66  HControlInstruction* end() const { return end_; }
67  HLoopInformation* loop_information() const { return loop_information_; }
68  const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
69  bool HasPredecessor() const { return predecessors_.length() > 0; }
70  const ZoneList<HBasicBlock*>* dominated_blocks() const {
71    return &dominated_blocks_;
72  }
73  const ZoneList<int>* deleted_phis() const {
74    return &deleted_phis_;
75  }
76  void RecordDeletedPhi(int merge_index) {
77    deleted_phis_.Add(merge_index);
78  }
79  HBasicBlock* dominator() const { return dominator_; }
80  HEnvironment* last_environment() const { return last_environment_; }
81  int argument_count() const { return argument_count_; }
82  void set_argument_count(int count) { argument_count_ = count; }
83  int first_instruction_index() const { return first_instruction_index_; }
84  void set_first_instruction_index(int index) {
85    first_instruction_index_ = index;
86  }
87  int last_instruction_index() const { return last_instruction_index_; }
88  void set_last_instruction_index(int index) {
89    last_instruction_index_ = index;
90  }
91
92  void AttachLoopInformation();
93  void DetachLoopInformation();
94  bool IsLoopHeader() const { return loop_information() != NULL; }
95  bool IsStartBlock() const { return block_id() == 0; }
96  void PostProcessLoopHeader(IterationStatement* stmt);
97
98  bool IsFinished() const { return end_ != NULL; }
99  void AddPhi(HPhi* phi);
100  void RemovePhi(HPhi* phi);
101  void AddInstruction(HInstruction* instr);
102  bool Dominates(HBasicBlock* other) const;
103
104  void SetInitialEnvironment(HEnvironment* env);
105  void ClearEnvironment() { last_environment_ = NULL; }
106  bool HasEnvironment() const { return last_environment_ != NULL; }
107  void UpdateEnvironment(HEnvironment* env) { last_environment_ = env; }
108  HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
109
110  void set_parent_loop_header(HBasicBlock* block) {
111    ASSERT(parent_loop_header_ == NULL);
112    parent_loop_header_ = block;
113  }
114
115  bool HasParentLoopHeader() const { return parent_loop_header_ != NULL; }
116
117  void SetJoinId(int id);
118
119  void Finish(HControlInstruction* last);
120  void FinishExit(HControlInstruction* instruction);
121  void Goto(HBasicBlock* block, bool include_stack_check = false);
122
123  int PredecessorIndexOf(HBasicBlock* predecessor) const;
124  void AddSimulate(int id) { AddInstruction(CreateSimulate(id)); }
125  void AssignCommonDominator(HBasicBlock* other);
126
127  void FinishExitWithDeoptimization() {
128    FinishExit(CreateDeoptimize());
129  }
130
131  // Add the inlined function exit sequence, adding an HLeaveInlined
132  // instruction and updating the bailout environment.
133  void AddLeaveInlined(HValue* return_value, HBasicBlock* target);
134
135  // If a target block is tagged as an inline function return, all
136  // predecessors should contain the inlined exit sequence:
137  //
138  // LeaveInlined
139  // Simulate (caller's environment)
140  // Goto (target block)
141  bool IsInlineReturnTarget() const { return is_inline_return_target_; }
142  void MarkAsInlineReturnTarget() { is_inline_return_target_ = true; }
143
144  inline Zone* zone();
145
146#ifdef DEBUG
147  void Verify();
148#endif
149
150 private:
151  void RegisterPredecessor(HBasicBlock* pred);
152  void AddDominatedBlock(HBasicBlock* block);
153
154  HSimulate* CreateSimulate(int id);
155  HDeoptimize* CreateDeoptimize();
156
157  int block_id_;
158  HGraph* graph_;
159  ZoneList<HPhi*> phis_;
160  HInstruction* first_;
161  HInstruction* last_;
162  HControlInstruction* end_;
163  HLoopInformation* loop_information_;
164  ZoneList<HBasicBlock*> predecessors_;
165  HBasicBlock* dominator_;
166  ZoneList<HBasicBlock*> dominated_blocks_;
167  HEnvironment* last_environment_;
168  // Outgoing parameter count at block exit, set during lithium translation.
169  int argument_count_;
170  // Instruction indices into the lithium code stream.
171  int first_instruction_index_;
172  int last_instruction_index_;
173  ZoneList<int> deleted_phis_;
174  HBasicBlock* parent_loop_header_;
175  bool is_inline_return_target_;
176};
177
178
179class HLoopInformation: public ZoneObject {
180 public:
181  explicit HLoopInformation(HBasicBlock* loop_header)
182      : back_edges_(4), loop_header_(loop_header), blocks_(8) {
183    blocks_.Add(loop_header);
184  }
185  virtual ~HLoopInformation() {}
186
187  const ZoneList<HBasicBlock*>* back_edges() const { return &back_edges_; }
188  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
189  HBasicBlock* loop_header() const { return loop_header_; }
190  HBasicBlock* GetLastBackEdge() const;
191  void RegisterBackEdge(HBasicBlock* block);
192
193 private:
194  void AddBlock(HBasicBlock* block);
195
196  ZoneList<HBasicBlock*> back_edges_;
197  HBasicBlock* loop_header_;
198  ZoneList<HBasicBlock*> blocks_;
199};
200
201
202class HGraph: public ZoneObject {
203 public:
204  explicit HGraph(CompilationInfo* info);
205
206  Isolate* isolate() { return isolate_; }
207  Zone* zone() { return isolate_->zone(); }
208
209  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
210  const ZoneList<HPhi*>* phi_list() const { return phi_list_; }
211  HBasicBlock* entry_block() const { return entry_block_; }
212  HEnvironment* start_environment() const { return start_environment_; }
213
214  void InitializeInferredTypes();
215  void InsertTypeConversions();
216  void InsertRepresentationChanges();
217  void ComputeMinusZeroChecks();
218  bool ProcessArgumentsObject();
219  void EliminateRedundantPhis();
220  void EliminateUnreachablePhis();
221  void Canonicalize();
222  void OrderBlocks();
223  void AssignDominators();
224
225  // Returns false if there are phi-uses of the arguments-object
226  // which are not supported by the optimizing compiler.
227  bool CollectPhis();
228
229  Handle<Code> Compile(CompilationInfo* info);
230
231  void set_undefined_constant(HConstant* constant) {
232    undefined_constant_.set(constant);
233  }
234  HConstant* GetConstantUndefined() const { return undefined_constant_.get(); }
235  HConstant* GetConstant1();
236  HConstant* GetConstantMinus1();
237  HConstant* GetConstantTrue();
238  HConstant* GetConstantFalse();
239
240  HBasicBlock* CreateBasicBlock();
241  HArgumentsObject* GetArgumentsObject() const {
242    return arguments_object_.get();
243  }
244  bool HasArgumentsObject() const { return arguments_object_.is_set(); }
245
246  void SetArgumentsObject(HArgumentsObject* object) {
247    arguments_object_.set(object);
248  }
249
250  int GetMaximumValueID() const { return values_.length(); }
251  int GetNextBlockID() { return next_block_id_++; }
252  int GetNextValueID(HValue* value) {
253    values_.Add(value);
254    return values_.length() - 1;
255  }
256  HValue* LookupValue(int id) const {
257    if (id >= 0 && id < values_.length()) return values_[id];
258    return NULL;
259  }
260
261#ifdef DEBUG
262  void Verify() const;
263#endif
264
265 private:
266  void Postorder(HBasicBlock* block,
267                 BitVector* visited,
268                 ZoneList<HBasicBlock*>* order,
269                 HBasicBlock* loop_header);
270  void PostorderLoopBlocks(HLoopInformation* loop,
271                           BitVector* visited,
272                           ZoneList<HBasicBlock*>* order,
273                           HBasicBlock* loop_header);
274  HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
275                         Object* value);
276
277  void InsertTypeConversions(HInstruction* instr);
278  void PropagateMinusZeroChecks(HValue* value, BitVector* visited);
279  void InsertRepresentationChangeForUse(HValue* value,
280                                        HValue* use,
281                                        Representation to);
282  void InsertRepresentationChangesForValue(HValue* current,
283                                           ZoneList<HValue*>* value_list,
284                                           ZoneList<Representation>* rep_list);
285  void InferTypes(ZoneList<HValue*>* worklist);
286  void InitializeInferredTypes(int from_inclusive, int to_inclusive);
287  void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
288
289  Isolate* isolate_;
290  int next_block_id_;
291  HBasicBlock* entry_block_;
292  HEnvironment* start_environment_;
293  ZoneList<HBasicBlock*> blocks_;
294  ZoneList<HValue*> values_;
295  ZoneList<HPhi*>* phi_list_;
296  SetOncePointer<HConstant> undefined_constant_;
297  SetOncePointer<HConstant> constant_1_;
298  SetOncePointer<HConstant> constant_minus1_;
299  SetOncePointer<HConstant> constant_true_;
300  SetOncePointer<HConstant> constant_false_;
301  SetOncePointer<HArgumentsObject> arguments_object_;
302
303  DISALLOW_COPY_AND_ASSIGN(HGraph);
304};
305
306
307Zone* HBasicBlock::zone() { return graph_->zone(); }
308
309
310class HEnvironment: public ZoneObject {
311 public:
312  HEnvironment(HEnvironment* outer,
313               Scope* scope,
314               Handle<JSFunction> closure);
315
316  // Simple accessors.
317  Handle<JSFunction> closure() const { return closure_; }
318  const ZoneList<HValue*>* values() const { return &values_; }
319  const ZoneList<int>* assigned_variables() const {
320    return &assigned_variables_;
321  }
322  int parameter_count() const { return parameter_count_; }
323  int local_count() const { return local_count_; }
324  HEnvironment* outer() const { return outer_; }
325  int pop_count() const { return pop_count_; }
326  int push_count() const { return push_count_; }
327
328  int ast_id() const { return ast_id_; }
329  void set_ast_id(int id) { ast_id_ = id; }
330
331  int length() const { return values_.length(); }
332
333  void Bind(Variable* variable, HValue* value) {
334    Bind(IndexFor(variable), value);
335  }
336
337  void Bind(int index, HValue* value);
338
339  HValue* Lookup(Variable* variable) const {
340    return Lookup(IndexFor(variable));
341  }
342
343  HValue* Lookup(int index) const {
344    HValue* result = values_[index];
345    ASSERT(result != NULL);
346    return result;
347  }
348
349  void Push(HValue* value) {
350    ASSERT(value != NULL);
351    ++push_count_;
352    values_.Add(value);
353  }
354
355  HValue* Pop() {
356    ASSERT(!ExpressionStackIsEmpty());
357    if (push_count_ > 0) {
358      --push_count_;
359    } else {
360      ++pop_count_;
361    }
362    return values_.RemoveLast();
363  }
364
365  void Drop(int count);
366
367  HValue* Top() const { return ExpressionStackAt(0); }
368
369  HValue* ExpressionStackAt(int index_from_top) const {
370    int index = length() - index_from_top - 1;
371    ASSERT(HasExpressionAt(index));
372    return values_[index];
373  }
374
375  void SetExpressionStackAt(int index_from_top, HValue* value);
376
377  HEnvironment* Copy() const;
378  HEnvironment* CopyWithoutHistory() const;
379  HEnvironment* CopyAsLoopHeader(HBasicBlock* block) const;
380
381  // Create an "inlined version" of this environment, where the original
382  // environment is the outer environment but the top expression stack
383  // elements are moved to an inner environment as parameters. If
384  // is_speculative, the argument values are expected to be PushArgument
385  // instructions, otherwise they are the actual values.
386  HEnvironment* CopyForInlining(Handle<JSFunction> target,
387                                FunctionLiteral* function,
388                                bool is_speculative,
389                                HConstant* undefined) const;
390
391  void AddIncomingEdge(HBasicBlock* block, HEnvironment* other);
392
393  void ClearHistory() {
394    pop_count_ = 0;
395    push_count_ = 0;
396    assigned_variables_.Rewind(0);
397  }
398
399  void SetValueAt(int index, HValue* value) {
400    ASSERT(index < length());
401    values_[index] = value;
402  }
403
404  void PrintTo(StringStream* stream);
405  void PrintToStd();
406
407 private:
408  explicit HEnvironment(const HEnvironment* other);
409
410  // True if index is included in the expression stack part of the environment.
411  bool HasExpressionAt(int index) const;
412
413  bool ExpressionStackIsEmpty() const;
414
415  void Initialize(int parameter_count, int local_count, int stack_height);
416  void Initialize(const HEnvironment* other);
417
418  // Map a variable to an environment index.  Parameter indices are shifted
419  // by 1 (receiver is parameter index -1 but environment index 0).
420  // Stack-allocated local indices are shifted by the number of parameters.
421  int IndexFor(Variable* variable) const {
422    Slot* slot = variable->AsSlot();
423    ASSERT(slot != NULL && slot->IsStackAllocated());
424    int shift = (slot->type() == Slot::PARAMETER) ? 1 : parameter_count_;
425    return slot->index() + shift;
426  }
427
428  Handle<JSFunction> closure_;
429  // Value array [parameters] [locals] [temporaries].
430  ZoneList<HValue*> values_;
431  ZoneList<int> assigned_variables_;
432  int parameter_count_;
433  int local_count_;
434  HEnvironment* outer_;
435  int pop_count_;
436  int push_count_;
437  int ast_id_;
438};
439
440
441class HGraphBuilder;
442
443// This class is not BASE_EMBEDDED because our inlining implementation uses
444// new and delete.
445class AstContext {
446 public:
447  bool IsEffect() const { return kind_ == Expression::kEffect; }
448  bool IsValue() const { return kind_ == Expression::kValue; }
449  bool IsTest() const { return kind_ == Expression::kTest; }
450
451  // 'Fill' this context with a hydrogen value.  The value is assumed to
452  // have already been inserted in the instruction stream (or not need to
453  // be, e.g., HPhi).  Call this function in tail position in the Visit
454  // functions for expressions.
455  virtual void ReturnValue(HValue* value) = 0;
456
457  // Add a hydrogen instruction to the instruction stream (recording an
458  // environment simulation if necessary) and then fill this context with
459  // the instruction as value.
460  virtual void ReturnInstruction(HInstruction* instr, int ast_id) = 0;
461
462  void set_for_typeof(bool for_typeof) { for_typeof_ = for_typeof; }
463  bool is_for_typeof() { return for_typeof_; }
464
465 protected:
466  AstContext(HGraphBuilder* owner, Expression::Context kind);
467  virtual ~AstContext();
468
469  HGraphBuilder* owner() const { return owner_; }
470
471  inline Zone* zone();
472
473  // We want to be able to assert, in a context-specific way, that the stack
474  // height makes sense when the context is filled.
475#ifdef DEBUG
476  int original_length_;
477#endif
478
479 private:
480  HGraphBuilder* owner_;
481  Expression::Context kind_;
482  AstContext* outer_;
483  bool for_typeof_;
484};
485
486
487class EffectContext: public AstContext {
488 public:
489  explicit EffectContext(HGraphBuilder* owner)
490      : AstContext(owner, Expression::kEffect) {
491  }
492  virtual ~EffectContext();
493
494  virtual void ReturnValue(HValue* value);
495  virtual void ReturnInstruction(HInstruction* instr, int ast_id);
496};
497
498
499class ValueContext: public AstContext {
500 public:
501  explicit ValueContext(HGraphBuilder* owner)
502      : AstContext(owner, Expression::kValue) {
503  }
504  virtual ~ValueContext();
505
506  virtual void ReturnValue(HValue* value);
507  virtual void ReturnInstruction(HInstruction* instr, int ast_id);
508};
509
510
511class TestContext: public AstContext {
512 public:
513  TestContext(HGraphBuilder* owner,
514              HBasicBlock* if_true,
515              HBasicBlock* if_false)
516      : AstContext(owner, Expression::kTest),
517        if_true_(if_true),
518        if_false_(if_false) {
519  }
520
521  virtual void ReturnValue(HValue* value);
522  virtual void ReturnInstruction(HInstruction* instr, int ast_id);
523
524  static TestContext* cast(AstContext* context) {
525    ASSERT(context->IsTest());
526    return reinterpret_cast<TestContext*>(context);
527  }
528
529  HBasicBlock* if_true() const { return if_true_; }
530  HBasicBlock* if_false() const { return if_false_; }
531
532 private:
533  // Build the shared core part of the translation unpacking a value into
534  // control flow.
535  void BuildBranch(HValue* value);
536
537  HBasicBlock* if_true_;
538  HBasicBlock* if_false_;
539};
540
541
542class FunctionState BASE_EMBEDDED {
543 public:
544  FunctionState(HGraphBuilder* owner,
545                CompilationInfo* info,
546                TypeFeedbackOracle* oracle);
547  ~FunctionState();
548
549  CompilationInfo* compilation_info() { return compilation_info_; }
550  TypeFeedbackOracle* oracle() { return oracle_; }
551  AstContext* call_context() { return call_context_; }
552  HBasicBlock* function_return() { return function_return_; }
553  TestContext* test_context() { return test_context_; }
554  void ClearInlinedTestContext() {
555    delete test_context_;
556    test_context_ = NULL;
557  }
558
559  FunctionState* outer() { return outer_; }
560
561 private:
562  HGraphBuilder* owner_;
563
564  CompilationInfo* compilation_info_;
565  TypeFeedbackOracle* oracle_;
566
567  // During function inlining, expression context of the call being
568  // inlined. NULL when not inlining.
569  AstContext* call_context_;
570
571  // When inlining in an effect of value context, this is the return block.
572  // It is NULL otherwise.  When inlining in a test context, there are a
573  // pair of return blocks in the context.  When not inlining, there is no
574  // local return point.
575  HBasicBlock* function_return_;
576
577  // When inlining a call in a test context, a context containing a pair of
578  // return blocks.  NULL in all other cases.
579  TestContext* test_context_;
580
581  FunctionState* outer_;
582};
583
584
585class HGraphBuilder: public AstVisitor {
586 public:
587  enum BreakType { BREAK, CONTINUE };
588
589  // A class encapsulating (lazily-allocated) break and continue blocks for
590  // a breakable statement.  Separated from BreakAndContinueScope so that it
591  // can have a separate lifetime.
592  class BreakAndContinueInfo BASE_EMBEDDED {
593   public:
594    explicit BreakAndContinueInfo(BreakableStatement* target)
595      : target_(target), break_block_(NULL), continue_block_(NULL) {
596    }
597
598    BreakableStatement* target() { return target_; }
599    HBasicBlock* break_block() { return break_block_; }
600    void set_break_block(HBasicBlock* block) { break_block_ = block; }
601    HBasicBlock* continue_block() { return continue_block_; }
602    void set_continue_block(HBasicBlock* block) { continue_block_ = block; }
603
604   private:
605    BreakableStatement* target_;
606    HBasicBlock* break_block_;
607    HBasicBlock* continue_block_;
608  };
609
610  // A helper class to maintain a stack of current BreakAndContinueInfo
611  // structures mirroring BreakableStatement nesting.
612  class BreakAndContinueScope BASE_EMBEDDED {
613   public:
614    BreakAndContinueScope(BreakAndContinueInfo* info, HGraphBuilder* owner)
615        : info_(info), owner_(owner), next_(owner->break_scope()) {
616      owner->set_break_scope(this);
617    }
618
619    ~BreakAndContinueScope() { owner_->set_break_scope(next_); }
620
621    BreakAndContinueInfo* info() { return info_; }
622    HGraphBuilder* owner() { return owner_; }
623    BreakAndContinueScope* next() { return next_; }
624
625    // Search the break stack for a break or continue target.
626    HBasicBlock* Get(BreakableStatement* stmt, BreakType type);
627
628   private:
629    BreakAndContinueInfo* info_;
630    HGraphBuilder* owner_;
631    BreakAndContinueScope* next_;
632  };
633
634  HGraphBuilder(CompilationInfo* info, TypeFeedbackOracle* oracle)
635      : function_state_(NULL),
636        initial_function_state_(this, info, oracle),
637        ast_context_(NULL),
638        break_scope_(NULL),
639        graph_(NULL),
640        current_block_(NULL),
641        inlined_count_(0),
642        zone_(info->isolate()->zone()) {
643    // This is not initialized in the initializer list because the
644    // constructor for the initial state relies on function_state_ == NULL
645    // to know it's the initial state.
646    function_state_= &initial_function_state_;
647  }
648
649  HGraph* CreateGraph();
650
651  // Simple accessors.
652  HGraph* graph() const { return graph_; }
653  BreakAndContinueScope* break_scope() const { return break_scope_; }
654  void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; }
655
656  HBasicBlock* current_block() const { return current_block_; }
657  void set_current_block(HBasicBlock* block) { current_block_ = block; }
658  HEnvironment* environment() const {
659    return current_block()->last_environment();
660  }
661
662  // Adding instructions.
663  HInstruction* AddInstruction(HInstruction* instr);
664  void AddSimulate(int id);
665
666  // Bailout environment manipulation.
667  void Push(HValue* value) { environment()->Push(value); }
668  HValue* Pop() { return environment()->Pop(); }
669
670 private:
671  // Type of a member function that generates inline code for a native function.
672  typedef void (HGraphBuilder::*InlineFunctionGenerator)(CallRuntime* call);
673
674  // Forward declarations for inner scope classes.
675  class SubgraphScope;
676
677  static const InlineFunctionGenerator kInlineFunctionGenerators[];
678
679  static const int kMaxCallPolymorphism = 4;
680  static const int kMaxLoadPolymorphism = 4;
681  static const int kMaxStorePolymorphism = 4;
682
683  static const int kMaxInlinedNodes = 196;
684  static const int kMaxInlinedSize = 196;
685  static const int kMaxSourceSize = 600;
686
687  // Simple accessors.
688  FunctionState* function_state() const { return function_state_; }
689  void set_function_state(FunctionState* state) { function_state_ = state; }
690
691  AstContext* ast_context() const { return ast_context_; }
692  void set_ast_context(AstContext* context) { ast_context_ = context; }
693
694  // Accessors forwarded to the function state.
695  CompilationInfo* info() const {
696    return function_state()->compilation_info();
697  }
698  TypeFeedbackOracle* oracle() const { return function_state()->oracle(); }
699
700  AstContext* call_context() const {
701    return function_state()->call_context();
702  }
703  HBasicBlock* function_return() const {
704    return function_state()->function_return();
705  }
706  TestContext* inlined_test_context() const {
707    return function_state()->test_context();
708  }
709  void ClearInlinedTestContext() {
710    function_state()->ClearInlinedTestContext();
711  }
712  bool function_strict_mode() {
713    return function_state()->compilation_info()->is_strict_mode();
714  }
715
716  // Generators for inline runtime functions.
717#define INLINE_FUNCTION_GENERATOR_DECLARATION(Name, argc, ressize)      \
718  void Generate##Name(CallRuntime* call);
719
720  INLINE_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
721  INLINE_RUNTIME_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
722#undef INLINE_FUNCTION_GENERATOR_DECLARATION
723
724  void Bailout(const char* reason);
725
726  void PreProcessOsrEntry(IterationStatement* statement);
727  // True iff. we are compiling for OSR and the statement is the entry.
728  bool HasOsrEntryAt(IterationStatement* statement);
729
730  HBasicBlock* CreateJoin(HBasicBlock* first,
731                          HBasicBlock* second,
732                          int join_id);
733
734  // Create a back edge in the flow graph.  body_exit is the predecessor
735  // block and loop_entry is the successor block.  loop_successor is the
736  // block where control flow exits the loop normally (e.g., via failure of
737  // the condition) and break_block is the block where control flow breaks
738  // from the loop.  All blocks except loop_entry can be NULL.  The return
739  // value is the new successor block which is the join of loop_successor
740  // and break_block, or NULL.
741  HBasicBlock* CreateLoop(IterationStatement* statement,
742                          HBasicBlock* loop_entry,
743                          HBasicBlock* body_exit,
744                          HBasicBlock* loop_successor,
745                          HBasicBlock* break_block);
746
747  HBasicBlock* JoinContinue(IterationStatement* statement,
748                            HBasicBlock* exit_block,
749                            HBasicBlock* continue_block);
750
751  HValue* Top() const { return environment()->Top(); }
752  void Drop(int n) { environment()->Drop(n); }
753  void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
754
755  void VisitForValue(Expression* expr);
756  void VisitForTypeOf(Expression* expr);
757  void VisitForEffect(Expression* expr);
758  void VisitForControl(Expression* expr,
759                       HBasicBlock* true_block,
760                       HBasicBlock* false_block);
761
762  // Visit an argument subexpression and emit a push to the outgoing
763  // arguments.
764  void VisitArgument(Expression* expr);
765  void VisitArgumentList(ZoneList<Expression*>* arguments);
766
767  // Visit a list of expressions from left to right, each in a value context.
768  void VisitExpressions(ZoneList<Expression*>* exprs);
769
770  void AddPhi(HPhi* phi);
771
772  void PushAndAdd(HInstruction* instr);
773
774  // Remove the arguments from the bailout environment and emit instructions
775  // to push them as outgoing parameters.
776  template <int V> HInstruction* PreProcessCall(HCall<V>* call);
777
778  void AssumeRepresentation(HValue* value, Representation r);
779  static Representation ToRepresentation(TypeInfo info);
780
781  void SetupScope(Scope* scope);
782  virtual void VisitStatements(ZoneList<Statement*>* statements);
783
784#define DECLARE_VISIT(type) virtual void Visit##type(type* node);
785  AST_NODE_LIST(DECLARE_VISIT)
786#undef DECLARE_VISIT
787
788  HBasicBlock* CreateBasicBlock(HEnvironment* env);
789  HBasicBlock* CreateLoopHeaderBlock();
790
791  // Helpers for flow graph construction.
792  enum GlobalPropertyAccess {
793    kUseCell,
794    kUseGeneric
795  };
796  GlobalPropertyAccess LookupGlobalProperty(Variable* var,
797                                            LookupResult* lookup,
798                                            bool is_store);
799
800  bool TryArgumentsAccess(Property* expr);
801  bool TryCallApply(Call* expr);
802  bool TryInline(Call* expr);
803  bool TryInlineBuiltinFunction(Call* expr,
804                                HValue* receiver,
805                                Handle<Map> receiver_map,
806                                CheckType check_type);
807
808  // If --trace-inlining, print a line of the inlining trace.  Inlining
809  // succeeded if the reason string is NULL and failed if there is a
810  // non-NULL reason string.
811  void TraceInline(Handle<JSFunction> target, const char* failure_reason);
812
813  void HandleGlobalVariableAssignment(Variable* var,
814                                      HValue* value,
815                                      int position,
816                                      int ast_id);
817
818  void HandlePropertyAssignment(Assignment* expr);
819  void HandleCompoundAssignment(Assignment* expr);
820  void HandlePolymorphicStoreNamedField(Assignment* expr,
821                                        HValue* object,
822                                        HValue* value,
823                                        ZoneMapList* types,
824                                        Handle<String> name);
825  void HandlePolymorphicCallNamed(Call* expr,
826                                  HValue* receiver,
827                                  ZoneMapList* types,
828                                  Handle<String> name);
829
830  HStringCharCodeAt* BuildStringCharCodeAt(HValue* string,
831                                           HValue* index);
832  HInstruction* BuildBinaryOperation(BinaryOperation* expr,
833                                     HValue* left,
834                                     HValue* right);
835  HInstruction* BuildIncrement(HValue* value, bool increment);
836  HLoadNamedField* BuildLoadNamedField(HValue* object,
837                                       Property* expr,
838                                       Handle<Map> type,
839                                       LookupResult* result,
840                                       bool smi_and_map_check);
841  HInstruction* BuildLoadNamedGeneric(HValue* object, Property* expr);
842  HInstruction* BuildLoadKeyedFastElement(HValue* object,
843                                          HValue* key,
844                                          Property* expr);
845  HInstruction* BuildLoadKeyedSpecializedArrayElement(HValue* object,
846                                                      HValue* key,
847                                                      Property* expr);
848  HInstruction* BuildLoadKeyedGeneric(HValue* object,
849                                      HValue* key);
850
851  HInstruction* BuildLoadKeyed(HValue* obj,
852                               HValue* key,
853                               Property* prop);
854
855  HInstruction* BuildLoadNamed(HValue* object,
856                               Property* prop,
857                               Handle<Map> map,
858                               Handle<String> name);
859  HInstruction* BuildStoreNamed(HValue* object,
860                                HValue* value,
861                                Expression* expr);
862  HInstruction* BuildStoreNamedField(HValue* object,
863                                     Handle<String> name,
864                                     HValue* value,
865                                     Handle<Map> type,
866                                     LookupResult* lookup,
867                                     bool smi_and_map_check);
868  HInstruction* BuildStoreNamedGeneric(HValue* object,
869                                       Handle<String> name,
870                                       HValue* value);
871  HInstruction* BuildStoreKeyedGeneric(HValue* object,
872                                       HValue* key,
873                                       HValue* value);
874
875  HInstruction* BuildStoreKeyedFastElement(HValue* object,
876                                           HValue* key,
877                                           HValue* val,
878                                           Expression* expr);
879
880  HInstruction* BuildStoreKeyedSpecializedArrayElement(
881      HValue* object,
882      HValue* key,
883      HValue* val,
884      Expression* expr);
885
886  HInstruction* BuildStoreKeyed(HValue* object,
887                                HValue* key,
888                                HValue* value,
889                                Expression* assignment);
890
891  HValue* BuildContextChainWalk(Variable* var);
892
893  void AddCheckConstantFunction(Call* expr,
894                                HValue* receiver,
895                                Handle<Map> receiver_map,
896                                bool smi_and_map_check);
897
898  Zone* zone() { return zone_; }
899
900  // The translation state of the currently-being-translated function.
901  FunctionState* function_state_;
902
903  // The base of the function state stack.
904  FunctionState initial_function_state_;
905
906  // Expression context of the currently visited subexpression. NULL when
907  // visiting statements.
908  AstContext* ast_context_;
909
910  // A stack of breakable statements entered.
911  BreakAndContinueScope* break_scope_;
912
913  HGraph* graph_;
914  HBasicBlock* current_block_;
915
916  int inlined_count_;
917
918  Zone* zone_;
919
920  friend class FunctionState;  // Pushes and pops the state stack.
921  friend class AstContext;  // Pushes and pops the AST context stack.
922
923  DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
924};
925
926
927Zone* AstContext::zone() { return owner_->zone(); }
928
929
930class HValueMap: public ZoneObject {
931 public:
932  HValueMap()
933      : array_size_(0),
934        lists_size_(0),
935        count_(0),
936        present_flags_(0),
937        array_(NULL),
938        lists_(NULL),
939        free_list_head_(kNil) {
940    ResizeLists(kInitialSize);
941    Resize(kInitialSize);
942  }
943
944  void Kill(int flags);
945
946  void Add(HValue* value) {
947    present_flags_ |= value->flags();
948    Insert(value);
949  }
950
951  HValue* Lookup(HValue* value) const;
952
953  HValueMap* Copy(Zone* zone) const {
954    return new(zone) HValueMap(this);
955  }
956
957 private:
958  // A linked list of HValue* values.  Stored in arrays.
959  struct HValueMapListElement {
960    HValue* value;
961    int next;  // Index in the array of the next list element.
962  };
963  static const int kNil = -1;  // The end of a linked list
964
965  // Must be a power of 2.
966  static const int kInitialSize = 16;
967
968  explicit HValueMap(const HValueMap* other);
969
970  void Resize(int new_size);
971  void ResizeLists(int new_size);
972  void Insert(HValue* value);
973  uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); }
974
975  int array_size_;
976  int lists_size_;
977  int count_;  // The number of values stored in the HValueMap.
978  int present_flags_;  // All flags that are in any value in the HValueMap.
979  HValueMapListElement* array_;  // Primary store - contains the first value
980  // with a given hash.  Colliding elements are stored in linked lists.
981  HValueMapListElement* lists_;  // The linked lists containing hash collisions.
982  int free_list_head_;  // Unused elements in lists_ are on the free list.
983};
984
985
986class HStatistics: public Malloced {
987 public:
988  void Initialize(CompilationInfo* info);
989  void Print();
990  void SaveTiming(const char* name, int64_t ticks, unsigned size);
991  static HStatistics* Instance() {
992    static SetOncePointer<HStatistics> instance;
993    if (!instance.is_set()) {
994      instance.set(new HStatistics());
995    }
996    return instance.get();
997  }
998
999 private:
1000
1001  HStatistics()
1002      : timing_(5),
1003        names_(5),
1004        sizes_(5),
1005        total_(0),
1006        total_size_(0),
1007        full_code_gen_(0),
1008        source_size_(0) { }
1009
1010  List<int64_t> timing_;
1011  List<const char*> names_;
1012  List<unsigned> sizes_;
1013  int64_t total_;
1014  unsigned total_size_;
1015  int64_t full_code_gen_;
1016  double source_size_;
1017};
1018
1019
1020class HPhase BASE_EMBEDDED {
1021 public:
1022  static const char* const kFullCodeGen;
1023  static const char* const kTotal;
1024
1025  explicit HPhase(const char* name) { Begin(name, NULL, NULL, NULL); }
1026  HPhase(const char* name, HGraph* graph) {
1027    Begin(name, graph, NULL, NULL);
1028  }
1029  HPhase(const char* name, LChunk* chunk) {
1030    Begin(name, NULL, chunk, NULL);
1031  }
1032  HPhase(const char* name, LAllocator* allocator) {
1033    Begin(name, NULL, NULL, allocator);
1034  }
1035
1036  ~HPhase() {
1037    End();
1038  }
1039
1040 private:
1041  void Begin(const char* name,
1042             HGraph* graph,
1043             LChunk* chunk,
1044             LAllocator* allocator);
1045  void End() const;
1046
1047  int64_t start_;
1048  const char* name_;
1049  HGraph* graph_;
1050  LChunk* chunk_;
1051  LAllocator* allocator_;
1052  unsigned start_allocation_size_;
1053};
1054
1055
1056class HTracer: public Malloced {
1057 public:
1058  void TraceCompilation(FunctionLiteral* function);
1059  void TraceHydrogen(const char* name, HGraph* graph);
1060  void TraceLithium(const char* name, LChunk* chunk);
1061  void TraceLiveRanges(const char* name, LAllocator* allocator);
1062
1063  static HTracer* Instance() {
1064    static SetOncePointer<HTracer> instance;
1065    if (!instance.is_set()) {
1066      instance.set(new HTracer("hydrogen.cfg"));
1067    }
1068    return instance.get();
1069  }
1070
1071 private:
1072  class Tag BASE_EMBEDDED {
1073   public:
1074    Tag(HTracer* tracer, const char* name) {
1075      name_ = name;
1076      tracer_ = tracer;
1077      tracer->PrintIndent();
1078      tracer->trace_.Add("begin_%s\n", name);
1079      tracer->indent_++;
1080    }
1081
1082    ~Tag() {
1083      tracer_->indent_--;
1084      tracer_->PrintIndent();
1085      tracer_->trace_.Add("end_%s\n", name_);
1086      ASSERT(tracer_->indent_ >= 0);
1087      tracer_->FlushToFile();
1088    }
1089
1090   private:
1091    HTracer* tracer_;
1092    const char* name_;
1093  };
1094
1095  explicit HTracer(const char* filename)
1096      : filename_(filename), trace_(&string_allocator_), indent_(0) {
1097    WriteChars(filename, "", 0, false);
1098  }
1099
1100  void TraceLiveRange(LiveRange* range, const char* type);
1101  void Trace(const char* name, HGraph* graph, LChunk* chunk);
1102  void FlushToFile();
1103
1104  void PrintEmptyProperty(const char* name) {
1105    PrintIndent();
1106    trace_.Add("%s\n", name);
1107  }
1108
1109  void PrintStringProperty(const char* name, const char* value) {
1110    PrintIndent();
1111    trace_.Add("%s \"%s\"\n", name, value);
1112  }
1113
1114  void PrintLongProperty(const char* name, int64_t value) {
1115    PrintIndent();
1116    trace_.Add("%s %d000\n", name, static_cast<int>(value / 1000));
1117  }
1118
1119  void PrintBlockProperty(const char* name, int block_id) {
1120    PrintIndent();
1121    trace_.Add("%s \"B%d\"\n", name, block_id);
1122  }
1123
1124  void PrintBlockProperty(const char* name, int block_id1, int block_id2) {
1125    PrintIndent();
1126    trace_.Add("%s \"B%d\" \"B%d\"\n", name, block_id1, block_id2);
1127  }
1128
1129  void PrintIntProperty(const char* name, int value) {
1130    PrintIndent();
1131    trace_.Add("%s %d\n", name, value);
1132  }
1133
1134  void PrintIndent() {
1135    for (int i = 0; i < indent_; i++) {
1136      trace_.Add("  ");
1137    }
1138  }
1139
1140  const char* filename_;
1141  HeapStringAllocator string_allocator_;
1142  StringStream trace_;
1143  int indent_;
1144};
1145
1146
1147} }  // namespace v8::internal
1148
1149#endif  // V8_HYDROGEN_H_
1150