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