1// Copyright 2012 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_HYDROGEN_H_
6#define V8_HYDROGEN_H_
7
8#include "src/v8.h"
9
10#include "src/accessors.h"
11#include "src/allocation.h"
12#include "src/ast.h"
13#include "src/bailout-reason.h"
14#include "src/compiler.h"
15#include "src/hydrogen-instructions.h"
16#include "src/scopes.h"
17#include "src/zone.h"
18
19namespace v8 {
20namespace internal {
21
22// Forward declarations.
23class BitVector;
24class FunctionState;
25class HEnvironment;
26class HGraph;
27class HLoopInformation;
28class HOsrBuilder;
29class HTracer;
30class LAllocator;
31class LChunk;
32class LiveRange;
33
34
35class HBasicBlock FINAL : public ZoneObject {
36 public:
37  explicit HBasicBlock(HGraph* graph);
38  ~HBasicBlock() { }
39
40  // Simple accessors.
41  int block_id() const { return block_id_; }
42  void set_block_id(int id) { block_id_ = id; }
43  HGraph* graph() const { return graph_; }
44  Isolate* isolate() const;
45  const ZoneList<HPhi*>* phis() const { return &phis_; }
46  HInstruction* first() const { return first_; }
47  HInstruction* last() const { return last_; }
48  void set_last(HInstruction* instr) { last_ = instr; }
49  HControlInstruction* end() const { return end_; }
50  HLoopInformation* loop_information() const { return loop_information_; }
51  HLoopInformation* current_loop() const {
52    return IsLoopHeader() ? loop_information()
53                          : (parent_loop_header() != NULL
54                            ? parent_loop_header()->loop_information() : NULL);
55  }
56  const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
57  bool HasPredecessor() const { return predecessors_.length() > 0; }
58  const ZoneList<HBasicBlock*>* dominated_blocks() const {
59    return &dominated_blocks_;
60  }
61  const ZoneList<int>* deleted_phis() const {
62    return &deleted_phis_;
63  }
64  void RecordDeletedPhi(int merge_index) {
65    deleted_phis_.Add(merge_index, zone());
66  }
67  HBasicBlock* dominator() const { return dominator_; }
68  HEnvironment* last_environment() const { return last_environment_; }
69  int argument_count() const { return argument_count_; }
70  void set_argument_count(int count) { argument_count_ = count; }
71  int first_instruction_index() const { return first_instruction_index_; }
72  void set_first_instruction_index(int index) {
73    first_instruction_index_ = index;
74  }
75  int last_instruction_index() const { return last_instruction_index_; }
76  void set_last_instruction_index(int index) {
77    last_instruction_index_ = index;
78  }
79  bool is_osr_entry() { return is_osr_entry_; }
80  void set_osr_entry() { is_osr_entry_ = true; }
81
82  void AttachLoopInformation();
83  void DetachLoopInformation();
84  bool IsLoopHeader() const { return loop_information() != NULL; }
85  bool IsStartBlock() const { return block_id() == 0; }
86  void PostProcessLoopHeader(IterationStatement* stmt);
87
88  bool IsFinished() const { return end_ != NULL; }
89  void AddPhi(HPhi* phi);
90  void RemovePhi(HPhi* phi);
91  void AddInstruction(HInstruction* instr, HSourcePosition position);
92  bool Dominates(HBasicBlock* other) const;
93  bool EqualToOrDominates(HBasicBlock* other) const;
94  int LoopNestingDepth() const;
95
96  void SetInitialEnvironment(HEnvironment* env);
97  void ClearEnvironment() {
98    DCHECK(IsFinished());
99    DCHECK(end()->SuccessorCount() == 0);
100    last_environment_ = NULL;
101  }
102  bool HasEnvironment() const { return last_environment_ != NULL; }
103  void UpdateEnvironment(HEnvironment* env);
104  HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
105
106  void set_parent_loop_header(HBasicBlock* block) {
107    DCHECK(parent_loop_header_ == NULL);
108    parent_loop_header_ = block;
109  }
110
111  bool HasParentLoopHeader() const { return parent_loop_header_ != NULL; }
112
113  void SetJoinId(BailoutId ast_id);
114
115  int PredecessorIndexOf(HBasicBlock* predecessor) const;
116  HPhi* AddNewPhi(int merged_index);
117  HSimulate* AddNewSimulate(BailoutId ast_id,
118                            HSourcePosition position,
119                            RemovableSimulate removable = FIXED_SIMULATE) {
120    HSimulate* instr = CreateSimulate(ast_id, removable);
121    AddInstruction(instr, position);
122    return instr;
123  }
124  void AssignCommonDominator(HBasicBlock* other);
125  void AssignLoopSuccessorDominators();
126
127  // If a target block is tagged as an inline function return, all
128  // predecessors should contain the inlined exit sequence:
129  //
130  // LeaveInlined
131  // Simulate (caller's environment)
132  // Goto (target block)
133  bool IsInlineReturnTarget() const { return is_inline_return_target_; }
134  void MarkAsInlineReturnTarget(HBasicBlock* inlined_entry_block) {
135    is_inline_return_target_ = true;
136    inlined_entry_block_ = inlined_entry_block;
137  }
138  HBasicBlock* inlined_entry_block() { return inlined_entry_block_; }
139
140  bool IsDeoptimizing() const {
141    return end() != NULL && end()->IsDeoptimize();
142  }
143
144  void MarkUnreachable();
145  bool IsUnreachable() const { return !is_reachable_; }
146  bool IsReachable() const { return is_reachable_; }
147
148  bool IsLoopSuccessorDominator() const {
149    return dominates_loop_successors_;
150  }
151  void MarkAsLoopSuccessorDominator() {
152    dominates_loop_successors_ = true;
153  }
154
155  bool IsOrdered() const { return is_ordered_; }
156  void MarkAsOrdered() { is_ordered_ = true; }
157
158  void MarkSuccEdgeUnreachable(int succ);
159
160  inline Zone* zone() const;
161
162#ifdef DEBUG
163  void Verify();
164#endif
165
166 protected:
167  friend class HGraphBuilder;
168
169  HSimulate* CreateSimulate(BailoutId ast_id, RemovableSimulate removable);
170  void Finish(HControlInstruction* last, HSourcePosition position);
171  void FinishExit(HControlInstruction* instruction, HSourcePosition position);
172  void Goto(HBasicBlock* block,
173            HSourcePosition position,
174            FunctionState* state = NULL,
175            bool add_simulate = true);
176  void GotoNoSimulate(HBasicBlock* block, HSourcePosition position) {
177    Goto(block, position, NULL, false);
178  }
179
180  // Add the inlined function exit sequence, adding an HLeaveInlined
181  // instruction and updating the bailout environment.
182  void AddLeaveInlined(HValue* return_value,
183                       FunctionState* state,
184                       HSourcePosition position);
185
186 private:
187  void RegisterPredecessor(HBasicBlock* pred);
188  void AddDominatedBlock(HBasicBlock* block);
189
190  int block_id_;
191  HGraph* graph_;
192  ZoneList<HPhi*> phis_;
193  HInstruction* first_;
194  HInstruction* last_;
195  HControlInstruction* end_;
196  HLoopInformation* loop_information_;
197  ZoneList<HBasicBlock*> predecessors_;
198  HBasicBlock* dominator_;
199  ZoneList<HBasicBlock*> dominated_blocks_;
200  HEnvironment* last_environment_;
201  // Outgoing parameter count at block exit, set during lithium translation.
202  int argument_count_;
203  // Instruction indices into the lithium code stream.
204  int first_instruction_index_;
205  int last_instruction_index_;
206  ZoneList<int> deleted_phis_;
207  HBasicBlock* parent_loop_header_;
208  // For blocks marked as inline return target: the block with HEnterInlined.
209  HBasicBlock* inlined_entry_block_;
210  bool is_inline_return_target_ : 1;
211  bool is_reachable_ : 1;
212  bool dominates_loop_successors_ : 1;
213  bool is_osr_entry_ : 1;
214  bool is_ordered_ : 1;
215};
216
217
218OStream& operator<<(OStream& os, const HBasicBlock& b);
219
220
221class HPredecessorIterator FINAL BASE_EMBEDDED {
222 public:
223  explicit HPredecessorIterator(HBasicBlock* block)
224      : predecessor_list_(block->predecessors()), current_(0) { }
225
226  bool Done() { return current_ >= predecessor_list_->length(); }
227  HBasicBlock* Current() { return predecessor_list_->at(current_); }
228  void Advance() { current_++; }
229
230 private:
231  const ZoneList<HBasicBlock*>* predecessor_list_;
232  int current_;
233};
234
235
236class HInstructionIterator FINAL BASE_EMBEDDED {
237 public:
238  explicit HInstructionIterator(HBasicBlock* block)
239      : instr_(block->first()) {
240    next_ = Done() ? NULL : instr_->next();
241  }
242
243  inline bool Done() const { return instr_ == NULL; }
244  inline HInstruction* Current() { return instr_; }
245  inline void Advance() {
246    instr_ = next_;
247    next_ = Done() ? NULL : instr_->next();
248  }
249
250 private:
251  HInstruction* instr_;
252  HInstruction* next_;
253};
254
255
256class HLoopInformation FINAL : public ZoneObject {
257 public:
258  HLoopInformation(HBasicBlock* loop_header, Zone* zone)
259      : back_edges_(4, zone),
260        loop_header_(loop_header),
261        blocks_(8, zone),
262        stack_check_(NULL) {
263    blocks_.Add(loop_header, zone);
264  }
265  ~HLoopInformation() {}
266
267  const ZoneList<HBasicBlock*>* back_edges() const { return &back_edges_; }
268  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
269  HBasicBlock* loop_header() const { return loop_header_; }
270  HBasicBlock* GetLastBackEdge() const;
271  void RegisterBackEdge(HBasicBlock* block);
272
273  HStackCheck* stack_check() const { return stack_check_; }
274  void set_stack_check(HStackCheck* stack_check) {
275    stack_check_ = stack_check;
276  }
277
278  bool IsNestedInThisLoop(HLoopInformation* other) {
279    while (other != NULL) {
280      if (other == this) {
281        return true;
282      }
283      other = other->parent_loop();
284    }
285    return false;
286  }
287  HLoopInformation* parent_loop() {
288    HBasicBlock* parent_header = loop_header()->parent_loop_header();
289    return parent_header != NULL ? parent_header->loop_information() : NULL;
290  }
291
292 private:
293  void AddBlock(HBasicBlock* block);
294
295  ZoneList<HBasicBlock*> back_edges_;
296  HBasicBlock* loop_header_;
297  ZoneList<HBasicBlock*> blocks_;
298  HStackCheck* stack_check_;
299};
300
301
302class BoundsCheckTable;
303class InductionVariableBlocksTable;
304class HGraph FINAL : public ZoneObject {
305 public:
306  explicit HGraph(CompilationInfo* info);
307
308  Isolate* isolate() const { return isolate_; }
309  Zone* zone() const { return zone_; }
310  CompilationInfo* info() const { return info_; }
311
312  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
313  const ZoneList<HPhi*>* phi_list() const { return phi_list_; }
314  HBasicBlock* entry_block() const { return entry_block_; }
315  HEnvironment* start_environment() const { return start_environment_; }
316
317  void FinalizeUniqueness();
318  bool ProcessArgumentsObject();
319  void OrderBlocks();
320  void AssignDominators();
321  void RestoreActualValues();
322
323  // Returns false if there are phi-uses of the arguments-object
324  // which are not supported by the optimizing compiler.
325  bool CheckArgumentsPhiUses();
326
327  // Returns false if there are phi-uses of an uninitialized const
328  // which are not supported by the optimizing compiler.
329  bool CheckConstPhiUses();
330
331  void CollectPhis();
332
333  HConstant* GetConstantUndefined();
334  HConstant* GetConstant0();
335  HConstant* GetConstant1();
336  HConstant* GetConstantMinus1();
337  HConstant* GetConstantTrue();
338  HConstant* GetConstantFalse();
339  HConstant* GetConstantHole();
340  HConstant* GetConstantNull();
341  HConstant* GetInvalidContext();
342
343  bool IsConstantUndefined(HConstant* constant);
344  bool IsConstant0(HConstant* constant);
345  bool IsConstant1(HConstant* constant);
346  bool IsConstantMinus1(HConstant* constant);
347  bool IsConstantTrue(HConstant* constant);
348  bool IsConstantFalse(HConstant* constant);
349  bool IsConstantHole(HConstant* constant);
350  bool IsConstantNull(HConstant* constant);
351  bool IsStandardConstant(HConstant* constant);
352
353  HBasicBlock* CreateBasicBlock();
354  HArgumentsObject* GetArgumentsObject() const {
355    return arguments_object_.get();
356  }
357
358  void SetArgumentsObject(HArgumentsObject* object) {
359    arguments_object_.set(object);
360  }
361
362  int GetMaximumValueID() const { return values_.length(); }
363  int GetNextBlockID() { return next_block_id_++; }
364  int GetNextValueID(HValue* value) {
365    DCHECK(!disallow_adding_new_values_);
366    values_.Add(value, zone());
367    return values_.length() - 1;
368  }
369  HValue* LookupValue(int id) const {
370    if (id >= 0 && id < values_.length()) return values_[id];
371    return NULL;
372  }
373  void DisallowAddingNewValues() {
374    disallow_adding_new_values_ = true;
375  }
376
377  bool Optimize(BailoutReason* bailout_reason);
378
379#ifdef DEBUG
380  void Verify(bool do_full_verify) const;
381#endif
382
383  bool has_osr() {
384    return osr_ != NULL;
385  }
386
387  void set_osr(HOsrBuilder* osr) {
388    osr_ = osr;
389  }
390
391  HOsrBuilder* osr() {
392    return osr_;
393  }
394
395  int update_type_change_checksum(int delta) {
396    type_change_checksum_ += delta;
397    return type_change_checksum_;
398  }
399
400  void update_maximum_environment_size(int environment_size) {
401    if (environment_size > maximum_environment_size_) {
402      maximum_environment_size_ = environment_size;
403    }
404  }
405  int maximum_environment_size() { return maximum_environment_size_; }
406
407  bool use_optimistic_licm() {
408    return use_optimistic_licm_;
409  }
410
411  void set_use_optimistic_licm(bool value) {
412    use_optimistic_licm_ = value;
413  }
414
415  void MarkRecursive() {
416    is_recursive_ = true;
417  }
418
419  bool is_recursive() const {
420    return is_recursive_;
421  }
422
423  void MarkDependsOnEmptyArrayProtoElements() {
424    // Add map dependency if not already added.
425    if (depends_on_empty_array_proto_elements_) return;
426    Map::AddDependentCompilationInfo(
427        handle(isolate()->initial_object_prototype()->map()),
428        DependentCode::kElementsCantBeAddedGroup, info());
429    Map::AddDependentCompilationInfo(
430        handle(isolate()->initial_array_prototype()->map()),
431        DependentCode::kElementsCantBeAddedGroup, info());
432    depends_on_empty_array_proto_elements_ = true;
433  }
434
435  bool depends_on_empty_array_proto_elements() {
436    return depends_on_empty_array_proto_elements_;
437  }
438
439  bool has_uint32_instructions() {
440    DCHECK(uint32_instructions_ == NULL || !uint32_instructions_->is_empty());
441    return uint32_instructions_ != NULL;
442  }
443
444  ZoneList<HInstruction*>* uint32_instructions() {
445    DCHECK(uint32_instructions_ == NULL || !uint32_instructions_->is_empty());
446    return uint32_instructions_;
447  }
448
449  void RecordUint32Instruction(HInstruction* instr) {
450    DCHECK(uint32_instructions_ == NULL || !uint32_instructions_->is_empty());
451    if (uint32_instructions_ == NULL) {
452      uint32_instructions_ = new(zone()) ZoneList<HInstruction*>(4, zone());
453    }
454    uint32_instructions_->Add(instr, zone());
455  }
456
457  void IncrementInNoSideEffectsScope() { no_side_effects_scope_count_++; }
458  void DecrementInNoSideEffectsScope() { no_side_effects_scope_count_--; }
459  bool IsInsideNoSideEffectsScope() { return no_side_effects_scope_count_ > 0; }
460
461  // If we are tracking source positions then this function assigns a unique
462  // identifier to each inlining and dumps function source if it was inlined
463  // for the first time during the current optimization.
464  int TraceInlinedFunction(Handle<SharedFunctionInfo> shared,
465                           HSourcePosition position);
466
467  // Converts given HSourcePosition to the absolute offset from the start of
468  // the corresponding script.
469  int SourcePositionToScriptPosition(HSourcePosition position);
470
471 private:
472  HConstant* ReinsertConstantIfNecessary(HConstant* constant);
473  HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
474                         int32_t integer_value);
475
476  template<class Phase>
477  void Run() {
478    Phase phase(this);
479    phase.Run();
480  }
481
482  void EliminateRedundantBoundsChecksUsingInductionVariables();
483
484  Isolate* isolate_;
485  int next_block_id_;
486  HBasicBlock* entry_block_;
487  HEnvironment* start_environment_;
488  ZoneList<HBasicBlock*> blocks_;
489  ZoneList<HValue*> values_;
490  ZoneList<HPhi*>* phi_list_;
491  ZoneList<HInstruction*>* uint32_instructions_;
492  SetOncePointer<HConstant> constant_undefined_;
493  SetOncePointer<HConstant> constant_0_;
494  SetOncePointer<HConstant> constant_1_;
495  SetOncePointer<HConstant> constant_minus1_;
496  SetOncePointer<HConstant> constant_true_;
497  SetOncePointer<HConstant> constant_false_;
498  SetOncePointer<HConstant> constant_the_hole_;
499  SetOncePointer<HConstant> constant_null_;
500  SetOncePointer<HConstant> constant_invalid_context_;
501  SetOncePointer<HArgumentsObject> arguments_object_;
502
503  HOsrBuilder* osr_;
504
505  CompilationInfo* info_;
506  Zone* zone_;
507
508  bool is_recursive_;
509  bool use_optimistic_licm_;
510  bool depends_on_empty_array_proto_elements_;
511  int type_change_checksum_;
512  int maximum_environment_size_;
513  int no_side_effects_scope_count_;
514  bool disallow_adding_new_values_;
515
516  class InlinedFunctionInfo {
517   public:
518    explicit InlinedFunctionInfo(Handle<SharedFunctionInfo> shared)
519      : shared_(shared), start_position_(shared->start_position()) {
520    }
521
522    Handle<SharedFunctionInfo> shared() const { return shared_; }
523    int start_position() const { return start_position_; }
524
525   private:
526    Handle<SharedFunctionInfo> shared_;
527    int start_position_;
528  };
529
530  int next_inline_id_;
531  ZoneList<InlinedFunctionInfo> inlined_functions_;
532
533  DISALLOW_COPY_AND_ASSIGN(HGraph);
534};
535
536
537Zone* HBasicBlock::zone() const { return graph_->zone(); }
538
539
540// Type of stack frame an environment might refer to.
541enum FrameType {
542  JS_FUNCTION,
543  JS_CONSTRUCT,
544  JS_GETTER,
545  JS_SETTER,
546  ARGUMENTS_ADAPTOR,
547  STUB
548};
549
550
551class HEnvironment FINAL : public ZoneObject {
552 public:
553  HEnvironment(HEnvironment* outer,
554               Scope* scope,
555               Handle<JSFunction> closure,
556               Zone* zone);
557
558  HEnvironment(Zone* zone, int parameter_count);
559
560  HEnvironment* arguments_environment() {
561    return outer()->frame_type() == ARGUMENTS_ADAPTOR ? outer() : this;
562  }
563
564  // Simple accessors.
565  Handle<JSFunction> closure() const { return closure_; }
566  const ZoneList<HValue*>* values() const { return &values_; }
567  const GrowableBitVector* assigned_variables() const {
568    return &assigned_variables_;
569  }
570  FrameType frame_type() const { return frame_type_; }
571  int parameter_count() const { return parameter_count_; }
572  int specials_count() const { return specials_count_; }
573  int local_count() const { return local_count_; }
574  HEnvironment* outer() const { return outer_; }
575  int pop_count() const { return pop_count_; }
576  int push_count() const { return push_count_; }
577
578  BailoutId ast_id() const { return ast_id_; }
579  void set_ast_id(BailoutId id) { ast_id_ = id; }
580
581  HEnterInlined* entry() const { return entry_; }
582  void set_entry(HEnterInlined* entry) { entry_ = entry; }
583
584  int length() const { return values_.length(); }
585
586  int first_expression_index() const {
587    return parameter_count() + specials_count() + local_count();
588  }
589
590  int first_local_index() const {
591    return parameter_count() + specials_count();
592  }
593
594  void Bind(Variable* variable, HValue* value) {
595    Bind(IndexFor(variable), value);
596  }
597
598  void Bind(int index, HValue* value);
599
600  void BindContext(HValue* value) {
601    Bind(parameter_count(), value);
602  }
603
604  HValue* Lookup(Variable* variable) const {
605    return Lookup(IndexFor(variable));
606  }
607
608  HValue* Lookup(int index) const {
609    HValue* result = values_[index];
610    DCHECK(result != NULL);
611    return result;
612  }
613
614  HValue* context() const {
615    // Return first special.
616    return Lookup(parameter_count());
617  }
618
619  void Push(HValue* value) {
620    DCHECK(value != NULL);
621    ++push_count_;
622    values_.Add(value, zone());
623  }
624
625  HValue* Pop() {
626    DCHECK(!ExpressionStackIsEmpty());
627    if (push_count_ > 0) {
628      --push_count_;
629    } else {
630      ++pop_count_;
631    }
632    return values_.RemoveLast();
633  }
634
635  void Drop(int count);
636
637  HValue* Top() const { return ExpressionStackAt(0); }
638
639  bool ExpressionStackIsEmpty() const;
640
641  HValue* ExpressionStackAt(int index_from_top) const {
642    int index = length() - index_from_top - 1;
643    DCHECK(HasExpressionAt(index));
644    return values_[index];
645  }
646
647  void SetExpressionStackAt(int index_from_top, HValue* value);
648
649  HEnvironment* Copy() const;
650  HEnvironment* CopyWithoutHistory() const;
651  HEnvironment* CopyAsLoopHeader(HBasicBlock* block) const;
652
653  // Create an "inlined version" of this environment, where the original
654  // environment is the outer environment but the top expression stack
655  // elements are moved to an inner environment as parameters.
656  HEnvironment* CopyForInlining(Handle<JSFunction> target,
657                                int arguments,
658                                FunctionLiteral* function,
659                                HConstant* undefined,
660                                InliningKind inlining_kind) const;
661
662  HEnvironment* DiscardInlined(bool drop_extra) {
663    HEnvironment* outer = outer_;
664    while (outer->frame_type() != JS_FUNCTION) outer = outer->outer_;
665    if (drop_extra) outer->Drop(1);
666    return outer;
667  }
668
669  void AddIncomingEdge(HBasicBlock* block, HEnvironment* other);
670
671  void ClearHistory() {
672    pop_count_ = 0;
673    push_count_ = 0;
674    assigned_variables_.Clear();
675  }
676
677  void SetValueAt(int index, HValue* value) {
678    DCHECK(index < length());
679    values_[index] = value;
680  }
681
682  // Map a variable to an environment index.  Parameter indices are shifted
683  // by 1 (receiver is parameter index -1 but environment index 0).
684  // Stack-allocated local indices are shifted by the number of parameters.
685  int IndexFor(Variable* variable) const {
686    DCHECK(variable->IsStackAllocated());
687    int shift = variable->IsParameter()
688        ? 1
689        : parameter_count_ + specials_count_;
690    return variable->index() + shift;
691  }
692
693  bool is_local_index(int i) const {
694    return i >= first_local_index() && i < first_expression_index();
695  }
696
697  bool is_parameter_index(int i) const {
698    return i >= 0 && i < parameter_count();
699  }
700
701  bool is_special_index(int i) const {
702    return i >= parameter_count() && i < parameter_count() + specials_count();
703  }
704
705  Zone* zone() const { return zone_; }
706
707 private:
708  HEnvironment(const HEnvironment* other, Zone* zone);
709
710  HEnvironment(HEnvironment* outer,
711               Handle<JSFunction> closure,
712               FrameType frame_type,
713               int arguments,
714               Zone* zone);
715
716  // Create an artificial stub environment (e.g. for argument adaptor or
717  // constructor stub).
718  HEnvironment* CreateStubEnvironment(HEnvironment* outer,
719                                      Handle<JSFunction> target,
720                                      FrameType frame_type,
721                                      int arguments) const;
722
723  // True if index is included in the expression stack part of the environment.
724  bool HasExpressionAt(int index) const;
725
726  void Initialize(int parameter_count, int local_count, int stack_height);
727  void Initialize(const HEnvironment* other);
728
729  Handle<JSFunction> closure_;
730  // Value array [parameters] [specials] [locals] [temporaries].
731  ZoneList<HValue*> values_;
732  GrowableBitVector assigned_variables_;
733  FrameType frame_type_;
734  int parameter_count_;
735  int specials_count_;
736  int local_count_;
737  HEnvironment* outer_;
738  HEnterInlined* entry_;
739  int pop_count_;
740  int push_count_;
741  BailoutId ast_id_;
742  Zone* zone_;
743};
744
745
746OStream& operator<<(OStream& os, const HEnvironment& env);
747
748
749class HOptimizedGraphBuilder;
750
751enum ArgumentsAllowedFlag {
752  ARGUMENTS_NOT_ALLOWED,
753  ARGUMENTS_ALLOWED
754};
755
756
757class HIfContinuation;
758
759// This class is not BASE_EMBEDDED because our inlining implementation uses
760// new and delete.
761class AstContext {
762 public:
763  bool IsEffect() const { return kind_ == Expression::kEffect; }
764  bool IsValue() const { return kind_ == Expression::kValue; }
765  bool IsTest() const { return kind_ == Expression::kTest; }
766
767  // 'Fill' this context with a hydrogen value.  The value is assumed to
768  // have already been inserted in the instruction stream (or not need to
769  // be, e.g., HPhi).  Call this function in tail position in the Visit
770  // functions for expressions.
771  virtual void ReturnValue(HValue* value) = 0;
772
773  // Add a hydrogen instruction to the instruction stream (recording an
774  // environment simulation if necessary) and then fill this context with
775  // the instruction as value.
776  virtual void ReturnInstruction(HInstruction* instr, BailoutId ast_id) = 0;
777
778  // Finishes the current basic block and materialize a boolean for
779  // value context, nothing for effect, generate a branch for test context.
780  // Call this function in tail position in the Visit functions for
781  // expressions.
782  virtual void ReturnControl(HControlInstruction* instr, BailoutId ast_id) = 0;
783
784  // Finishes the current basic block and materialize a boolean for
785  // value context, nothing for effect, generate a branch for test context.
786  // Call this function in tail position in the Visit functions for
787  // expressions that use an IfBuilder.
788  virtual void ReturnContinuation(HIfContinuation* continuation,
789                                  BailoutId ast_id) = 0;
790
791  void set_for_typeof(bool for_typeof) { for_typeof_ = for_typeof; }
792  bool is_for_typeof() { return for_typeof_; }
793
794 protected:
795  AstContext(HOptimizedGraphBuilder* owner, Expression::Context kind);
796  virtual ~AstContext();
797
798  HOptimizedGraphBuilder* owner() const { return owner_; }
799
800  inline Zone* zone() const;
801
802  // We want to be able to assert, in a context-specific way, that the stack
803  // height makes sense when the context is filled.
804#ifdef DEBUG
805  int original_length_;
806#endif
807
808 private:
809  HOptimizedGraphBuilder* owner_;
810  Expression::Context kind_;
811  AstContext* outer_;
812  bool for_typeof_;
813};
814
815
816class EffectContext FINAL : public AstContext {
817 public:
818  explicit EffectContext(HOptimizedGraphBuilder* owner)
819      : AstContext(owner, Expression::kEffect) {
820  }
821  virtual ~EffectContext();
822
823  virtual void ReturnValue(HValue* value) OVERRIDE;
824  virtual void ReturnInstruction(HInstruction* instr,
825                                 BailoutId ast_id) OVERRIDE;
826  virtual void ReturnControl(HControlInstruction* instr,
827                             BailoutId ast_id) OVERRIDE;
828  virtual void ReturnContinuation(HIfContinuation* continuation,
829                                  BailoutId ast_id) OVERRIDE;
830};
831
832
833class ValueContext FINAL : public AstContext {
834 public:
835  ValueContext(HOptimizedGraphBuilder* owner, ArgumentsAllowedFlag flag)
836      : AstContext(owner, Expression::kValue), flag_(flag) {
837  }
838  virtual ~ValueContext();
839
840  virtual void ReturnValue(HValue* value) OVERRIDE;
841  virtual void ReturnInstruction(HInstruction* instr,
842                                 BailoutId ast_id) OVERRIDE;
843  virtual void ReturnControl(HControlInstruction* instr,
844                             BailoutId ast_id) OVERRIDE;
845  virtual void ReturnContinuation(HIfContinuation* continuation,
846                                  BailoutId ast_id) OVERRIDE;
847
848  bool arguments_allowed() { return flag_ == ARGUMENTS_ALLOWED; }
849
850 private:
851  ArgumentsAllowedFlag flag_;
852};
853
854
855class TestContext FINAL : public AstContext {
856 public:
857  TestContext(HOptimizedGraphBuilder* owner,
858              Expression* condition,
859              HBasicBlock* if_true,
860              HBasicBlock* if_false)
861      : AstContext(owner, Expression::kTest),
862        condition_(condition),
863        if_true_(if_true),
864        if_false_(if_false) {
865  }
866
867  virtual void ReturnValue(HValue* value) OVERRIDE;
868  virtual void ReturnInstruction(HInstruction* instr,
869                                 BailoutId ast_id) OVERRIDE;
870  virtual void ReturnControl(HControlInstruction* instr,
871                             BailoutId ast_id) OVERRIDE;
872  virtual void ReturnContinuation(HIfContinuation* continuation,
873                                  BailoutId ast_id) OVERRIDE;
874
875  static TestContext* cast(AstContext* context) {
876    DCHECK(context->IsTest());
877    return reinterpret_cast<TestContext*>(context);
878  }
879
880  Expression* condition() const { return condition_; }
881  HBasicBlock* if_true() const { return if_true_; }
882  HBasicBlock* if_false() const { return if_false_; }
883
884 private:
885  // Build the shared core part of the translation unpacking a value into
886  // control flow.
887  void BuildBranch(HValue* value);
888
889  Expression* condition_;
890  HBasicBlock* if_true_;
891  HBasicBlock* if_false_;
892};
893
894
895class FunctionState FINAL {
896 public:
897  FunctionState(HOptimizedGraphBuilder* owner,
898                CompilationInfo* info,
899                InliningKind inlining_kind,
900                int inlining_id);
901  ~FunctionState();
902
903  CompilationInfo* compilation_info() { return compilation_info_; }
904  AstContext* call_context() { return call_context_; }
905  InliningKind inlining_kind() const { return inlining_kind_; }
906  HBasicBlock* function_return() { return function_return_; }
907  TestContext* test_context() { return test_context_; }
908  void ClearInlinedTestContext() {
909    delete test_context_;
910    test_context_ = NULL;
911  }
912
913  FunctionState* outer() { return outer_; }
914
915  HEnterInlined* entry() { return entry_; }
916  void set_entry(HEnterInlined* entry) { entry_ = entry; }
917
918  HArgumentsObject* arguments_object() { return arguments_object_; }
919  void set_arguments_object(HArgumentsObject* arguments_object) {
920    arguments_object_ = arguments_object;
921  }
922
923  HArgumentsElements* arguments_elements() { return arguments_elements_; }
924  void set_arguments_elements(HArgumentsElements* arguments_elements) {
925    arguments_elements_ = arguments_elements;
926  }
927
928  bool arguments_pushed() { return arguments_elements() != NULL; }
929
930  int inlining_id() const { return inlining_id_; }
931
932 private:
933  HOptimizedGraphBuilder* owner_;
934
935  CompilationInfo* compilation_info_;
936
937  // During function inlining, expression context of the call being
938  // inlined. NULL when not inlining.
939  AstContext* call_context_;
940
941  // The kind of call which is currently being inlined.
942  InliningKind inlining_kind_;
943
944  // When inlining in an effect or value context, this is the return block.
945  // It is NULL otherwise.  When inlining in a test context, there are a
946  // pair of return blocks in the context.  When not inlining, there is no
947  // local return point.
948  HBasicBlock* function_return_;
949
950  // When inlining a call in a test context, a context containing a pair of
951  // return blocks.  NULL in all other cases.
952  TestContext* test_context_;
953
954  // When inlining HEnterInlined instruction corresponding to the function
955  // entry.
956  HEnterInlined* entry_;
957
958  HArgumentsObject* arguments_object_;
959  HArgumentsElements* arguments_elements_;
960
961  int inlining_id_;
962  HSourcePosition outer_source_position_;
963
964  FunctionState* outer_;
965};
966
967
968class HIfContinuation FINAL {
969 public:
970  HIfContinuation()
971    : continuation_captured_(false),
972      true_branch_(NULL),
973      false_branch_(NULL) {}
974  HIfContinuation(HBasicBlock* true_branch,
975                  HBasicBlock* false_branch)
976      : continuation_captured_(true), true_branch_(true_branch),
977        false_branch_(false_branch) {}
978  ~HIfContinuation() { DCHECK(!continuation_captured_); }
979
980  void Capture(HBasicBlock* true_branch,
981               HBasicBlock* false_branch) {
982    DCHECK(!continuation_captured_);
983    true_branch_ = true_branch;
984    false_branch_ = false_branch;
985    continuation_captured_ = true;
986  }
987
988  void Continue(HBasicBlock** true_branch,
989                HBasicBlock** false_branch) {
990    DCHECK(continuation_captured_);
991    *true_branch = true_branch_;
992    *false_branch = false_branch_;
993    continuation_captured_ = false;
994  }
995
996  bool IsTrueReachable() { return true_branch_ != NULL; }
997  bool IsFalseReachable() { return false_branch_ != NULL; }
998  bool TrueAndFalseReachable() {
999    return IsTrueReachable() || IsFalseReachable();
1000  }
1001
1002  HBasicBlock* true_branch() const { return true_branch_; }
1003  HBasicBlock* false_branch() const { return false_branch_; }
1004
1005 private:
1006  bool continuation_captured_;
1007  HBasicBlock* true_branch_;
1008  HBasicBlock* false_branch_;
1009};
1010
1011
1012class HAllocationMode FINAL BASE_EMBEDDED {
1013 public:
1014  explicit HAllocationMode(Handle<AllocationSite> feedback_site)
1015      : current_site_(NULL), feedback_site_(feedback_site),
1016        pretenure_flag_(NOT_TENURED) {}
1017  explicit HAllocationMode(HValue* current_site)
1018      : current_site_(current_site), pretenure_flag_(NOT_TENURED) {}
1019  explicit HAllocationMode(PretenureFlag pretenure_flag)
1020      : current_site_(NULL), pretenure_flag_(pretenure_flag) {}
1021  HAllocationMode()
1022      : current_site_(NULL), pretenure_flag_(NOT_TENURED) {}
1023
1024  HValue* current_site() const { return current_site_; }
1025  Handle<AllocationSite> feedback_site() const { return feedback_site_; }
1026
1027  bool CreateAllocationMementos() const WARN_UNUSED_RESULT {
1028    return current_site() != NULL;
1029  }
1030
1031  PretenureFlag GetPretenureMode() const WARN_UNUSED_RESULT {
1032    if (!feedback_site().is_null()) return feedback_site()->GetPretenureMode();
1033    return pretenure_flag_;
1034  }
1035
1036 private:
1037  HValue* current_site_;
1038  Handle<AllocationSite> feedback_site_;
1039  PretenureFlag pretenure_flag_;
1040};
1041
1042
1043class HGraphBuilder {
1044 public:
1045  explicit HGraphBuilder(CompilationInfo* info)
1046      : info_(info),
1047        graph_(NULL),
1048        current_block_(NULL),
1049        scope_(info->scope()),
1050        position_(HSourcePosition::Unknown()),
1051        start_position_(0) {}
1052  virtual ~HGraphBuilder() {}
1053
1054  Scope* scope() const { return scope_; }
1055  void set_scope(Scope* scope) { scope_ = scope; }
1056
1057  HBasicBlock* current_block() const { return current_block_; }
1058  void set_current_block(HBasicBlock* block) { current_block_ = block; }
1059  HEnvironment* environment() const {
1060    return current_block()->last_environment();
1061  }
1062  Zone* zone() const { return info_->zone(); }
1063  HGraph* graph() const { return graph_; }
1064  Isolate* isolate() const { return graph_->isolate(); }
1065  CompilationInfo* top_info() { return info_; }
1066
1067  HGraph* CreateGraph();
1068
1069  // Bailout environment manipulation.
1070  void Push(HValue* value) { environment()->Push(value); }
1071  HValue* Pop() { return environment()->Pop(); }
1072
1073  virtual HValue* context() = 0;
1074
1075  // Adding instructions.
1076  HInstruction* AddInstruction(HInstruction* instr);
1077  void FinishCurrentBlock(HControlInstruction* last);
1078  void FinishExitCurrentBlock(HControlInstruction* instruction);
1079
1080  void Goto(HBasicBlock* from,
1081            HBasicBlock* target,
1082            FunctionState* state = NULL,
1083            bool add_simulate = true) {
1084    from->Goto(target, source_position(), state, add_simulate);
1085  }
1086  void Goto(HBasicBlock* target,
1087            FunctionState* state = NULL,
1088            bool add_simulate = true) {
1089    Goto(current_block(), target, state, add_simulate);
1090  }
1091  void GotoNoSimulate(HBasicBlock* from, HBasicBlock* target) {
1092    Goto(from, target, NULL, false);
1093  }
1094  void GotoNoSimulate(HBasicBlock* target) {
1095    Goto(target, NULL, false);
1096  }
1097  void AddLeaveInlined(HBasicBlock* block,
1098                       HValue* return_value,
1099                       FunctionState* state) {
1100    block->AddLeaveInlined(return_value, state, source_position());
1101  }
1102  void AddLeaveInlined(HValue* return_value, FunctionState* state) {
1103    return AddLeaveInlined(current_block(), return_value, state);
1104  }
1105
1106  template<class I>
1107  HInstruction* NewUncasted() { return I::New(zone(), context()); }
1108
1109  template<class I>
1110  I* New() { return I::New(zone(), context()); }
1111
1112  template<class I>
1113  HInstruction* AddUncasted() { return AddInstruction(NewUncasted<I>());}
1114
1115  template<class I>
1116  I* Add() { return AddInstructionTyped(New<I>());}
1117
1118  template<class I, class P1>
1119  HInstruction* NewUncasted(P1 p1) {
1120    return I::New(zone(), context(), p1);
1121  }
1122
1123  template<class I, class P1>
1124  I* New(P1 p1) { return I::New(zone(), context(), p1); }
1125
1126  template<class I, class P1>
1127  HInstruction* AddUncasted(P1 p1) {
1128    HInstruction* result = AddInstruction(NewUncasted<I>(p1));
1129    // Specializations must have their parameters properly casted
1130    // to avoid landing here.
1131    DCHECK(!result->IsReturn() && !result->IsSimulate() &&
1132           !result->IsDeoptimize());
1133    return result;
1134  }
1135
1136  template<class I, class P1>
1137  I* Add(P1 p1) {
1138    I* result = AddInstructionTyped(New<I>(p1));
1139    // Specializations must have their parameters properly casted
1140    // to avoid landing here.
1141    DCHECK(!result->IsReturn() && !result->IsSimulate() &&
1142           !result->IsDeoptimize());
1143    return result;
1144  }
1145
1146  template<class I, class P1, class P2>
1147  HInstruction* NewUncasted(P1 p1, P2 p2) {
1148    return I::New(zone(), context(), p1, p2);
1149  }
1150
1151  template<class I, class P1, class P2>
1152  I* New(P1 p1, P2 p2) {
1153    return I::New(zone(), context(), p1, p2);
1154  }
1155
1156  template<class I, class P1, class P2>
1157  HInstruction* AddUncasted(P1 p1, P2 p2) {
1158    HInstruction* result = AddInstruction(NewUncasted<I>(p1, p2));
1159    // Specializations must have their parameters properly casted
1160    // to avoid landing here.
1161    DCHECK(!result->IsSimulate());
1162    return result;
1163  }
1164
1165  template<class I, class P1, class P2>
1166  I* Add(P1 p1, P2 p2) {
1167    I* result = AddInstructionTyped(New<I>(p1, p2));
1168    // Specializations must have their parameters properly casted
1169    // to avoid landing here.
1170    DCHECK(!result->IsSimulate());
1171    return result;
1172  }
1173
1174  template<class I, class P1, class P2, class P3>
1175  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3) {
1176    return I::New(zone(), context(), p1, p2, p3);
1177  }
1178
1179  template<class I, class P1, class P2, class P3>
1180  I* New(P1 p1, P2 p2, P3 p3) {
1181    return I::New(zone(), context(), p1, p2, p3);
1182  }
1183
1184  template<class I, class P1, class P2, class P3>
1185  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3) {
1186    return AddInstruction(NewUncasted<I>(p1, p2, p3));
1187  }
1188
1189  template<class I, class P1, class P2, class P3>
1190  I* Add(P1 p1, P2 p2, P3 p3) {
1191    return AddInstructionTyped(New<I>(p1, p2, p3));
1192  }
1193
1194  template<class I, class P1, class P2, class P3, class P4>
1195  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4) {
1196    return I::New(zone(), context(), p1, p2, p3, p4);
1197  }
1198
1199  template<class I, class P1, class P2, class P3, class P4>
1200  I* New(P1 p1, P2 p2, P3 p3, P4 p4) {
1201    return I::New(zone(), context(), p1, p2, p3, p4);
1202  }
1203
1204  template<class I, class P1, class P2, class P3, class P4>
1205  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4) {
1206    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4));
1207  }
1208
1209  template<class I, class P1, class P2, class P3, class P4>
1210  I* Add(P1 p1, P2 p2, P3 p3, P4 p4) {
1211    return AddInstructionTyped(New<I>(p1, p2, p3, p4));
1212  }
1213
1214  template<class I, class P1, class P2, class P3, class P4, class P5>
1215  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1216    return I::New(zone(), context(), p1, p2, p3, p4, p5);
1217  }
1218
1219  template<class I, class P1, class P2, class P3, class P4, class P5>
1220  I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1221    return I::New(zone(), context(), p1, p2, p3, p4, p5);
1222  }
1223
1224  template<class I, class P1, class P2, class P3, class P4, class P5>
1225  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1226    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5));
1227  }
1228
1229  template<class I, class P1, class P2, class P3, class P4, class P5>
1230  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1231    return AddInstructionTyped(New<I>(p1, p2, p3, p4, p5));
1232  }
1233
1234  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1235  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1236    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6);
1237  }
1238
1239  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1240  I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1241    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6);
1242  }
1243
1244  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1245  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1246    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6));
1247  }
1248
1249  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1250  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1251    return AddInstructionTyped(New<I>(p1, p2, p3, p4, p5, p6));
1252  }
1253
1254  template<class I, class P1, class P2, class P3, class P4,
1255      class P5, class P6, class P7>
1256  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1257    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7);
1258  }
1259
1260  template<class I, class P1, class P2, class P3, class P4,
1261      class P5, class P6, class P7>
1262      I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1263    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7);
1264  }
1265
1266  template<class I, class P1, class P2, class P3,
1267           class P4, class P5, class P6, class P7>
1268  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1269    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7));
1270  }
1271
1272  template<class I, class P1, class P2, class P3,
1273           class P4, class P5, class P6, class P7>
1274  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1275    return AddInstructionTyped(New<I>(p1, p2, p3, p4, p5, p6, p7));
1276  }
1277
1278  template<class I, class P1, class P2, class P3, class P4,
1279      class P5, class P6, class P7, class P8>
1280  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4,
1281                            P5 p5, P6 p6, P7 p7, P8 p8) {
1282    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7, p8);
1283  }
1284
1285  template<class I, class P1, class P2, class P3, class P4,
1286      class P5, class P6, class P7, class P8>
1287      I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7, P8 p8) {
1288    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7, p8);
1289  }
1290
1291  template<class I, class P1, class P2, class P3, class P4,
1292           class P5, class P6, class P7, class P8>
1293  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4,
1294                            P5 p5, P6 p6, P7 p7, P8 p8) {
1295    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7, p8));
1296  }
1297
1298  template<class I, class P1, class P2, class P3, class P4,
1299           class P5, class P6, class P7, class P8>
1300  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7, P8 p8) {
1301    return AddInstructionTyped(New<I>(p1, p2, p3, p4, p5, p6, p7, p8));
1302  }
1303
1304  void AddSimulate(BailoutId id, RemovableSimulate removable = FIXED_SIMULATE);
1305
1306  // When initializing arrays, we'll unfold the loop if the number of elements
1307  // is known at compile time and is <= kElementLoopUnrollThreshold.
1308  static const int kElementLoopUnrollThreshold = 8;
1309
1310 protected:
1311  virtual bool BuildGraph() = 0;
1312
1313  HBasicBlock* CreateBasicBlock(HEnvironment* env);
1314  HBasicBlock* CreateLoopHeaderBlock();
1315
1316  template <class BitFieldClass>
1317  HValue* BuildDecodeField(HValue* encoded_field) {
1318    HValue* mask_value = Add<HConstant>(static_cast<int>(BitFieldClass::kMask));
1319    HValue* masked_field =
1320        AddUncasted<HBitwise>(Token::BIT_AND, encoded_field, mask_value);
1321    return AddUncasted<HShr>(masked_field,
1322        Add<HConstant>(static_cast<int>(BitFieldClass::kShift)));
1323  }
1324
1325  HValue* BuildGetElementsKind(HValue* object);
1326
1327  HValue* BuildCheckHeapObject(HValue* object);
1328  HValue* BuildCheckString(HValue* string);
1329  HValue* BuildWrapReceiver(HValue* object, HValue* function);
1330
1331  // Building common constructs
1332  HValue* BuildCheckForCapacityGrow(HValue* object,
1333                                    HValue* elements,
1334                                    ElementsKind kind,
1335                                    HValue* length,
1336                                    HValue* key,
1337                                    bool is_js_array,
1338                                    PropertyAccessType access_type);
1339
1340  HValue* BuildCopyElementsOnWrite(HValue* object,
1341                                   HValue* elements,
1342                                   ElementsKind kind,
1343                                   HValue* length);
1344
1345  void BuildTransitionElementsKind(HValue* object,
1346                                   HValue* map,
1347                                   ElementsKind from_kind,
1348                                   ElementsKind to_kind,
1349                                   bool is_jsarray);
1350
1351  HValue* BuildNumberToString(HValue* object, Type* type);
1352
1353  void BuildJSObjectCheck(HValue* receiver,
1354                          int bit_field_mask);
1355
1356  // Checks a key value that's being used for a keyed element access context. If
1357  // the key is a index, i.e. a smi or a number in a unique string with a cached
1358  // numeric value, the "true" of the continuation is joined. Otherwise,
1359  // if the key is a name or a unique string, the "false" of the continuation is
1360  // joined. Otherwise, a deoptimization is triggered. In both paths of the
1361  // continuation, the key is pushed on the top of the environment.
1362  void BuildKeyedIndexCheck(HValue* key,
1363                            HIfContinuation* join_continuation);
1364
1365  // Checks the properties of an object if they are in dictionary case, in which
1366  // case "true" of continuation is taken, otherwise the "false"
1367  void BuildTestForDictionaryProperties(HValue* object,
1368                                        HIfContinuation* continuation);
1369
1370  void BuildNonGlobalObjectCheck(HValue* receiver);
1371
1372  HValue* BuildKeyedLookupCacheHash(HValue* object,
1373                                    HValue* key);
1374
1375  HValue* BuildUncheckedDictionaryElementLoad(HValue* receiver,
1376                                              HValue* elements,
1377                                              HValue* key,
1378                                              HValue* hash);
1379
1380  HValue* BuildRegExpConstructResult(HValue* length,
1381                                     HValue* index,
1382                                     HValue* input);
1383
1384  // Allocates a new object according with the given allocation properties.
1385  HAllocate* BuildAllocate(HValue* object_size,
1386                           HType type,
1387                           InstanceType instance_type,
1388                           HAllocationMode allocation_mode);
1389  // Computes the sum of two string lengths, taking care of overflow handling.
1390  HValue* BuildAddStringLengths(HValue* left_length, HValue* right_length);
1391  // Creates a cons string using the two input strings.
1392  HValue* BuildCreateConsString(HValue* length,
1393                                HValue* left,
1394                                HValue* right,
1395                                HAllocationMode allocation_mode);
1396  // Copies characters from one sequential string to another.
1397  void BuildCopySeqStringChars(HValue* src,
1398                               HValue* src_offset,
1399                               String::Encoding src_encoding,
1400                               HValue* dst,
1401                               HValue* dst_offset,
1402                               String::Encoding dst_encoding,
1403                               HValue* length);
1404
1405  // Align an object size to object alignment boundary
1406  HValue* BuildObjectSizeAlignment(HValue* unaligned_size, int header_size);
1407
1408  // Both operands are non-empty strings.
1409  HValue* BuildUncheckedStringAdd(HValue* left,
1410                                  HValue* right,
1411                                  HAllocationMode allocation_mode);
1412  // Add two strings using allocation mode, validating type feedback.
1413  HValue* BuildStringAdd(HValue* left,
1414                         HValue* right,
1415                         HAllocationMode allocation_mode);
1416
1417  HInstruction* BuildUncheckedMonomorphicElementAccess(
1418      HValue* checked_object,
1419      HValue* key,
1420      HValue* val,
1421      bool is_js_array,
1422      ElementsKind elements_kind,
1423      PropertyAccessType access_type,
1424      LoadKeyedHoleMode load_mode,
1425      KeyedAccessStoreMode store_mode);
1426
1427  HInstruction* AddElementAccess(
1428      HValue* elements,
1429      HValue* checked_key,
1430      HValue* val,
1431      HValue* dependency,
1432      ElementsKind elements_kind,
1433      PropertyAccessType access_type,
1434      LoadKeyedHoleMode load_mode = NEVER_RETURN_HOLE);
1435
1436  HInstruction* AddLoadStringInstanceType(HValue* string);
1437  HInstruction* AddLoadStringLength(HValue* string);
1438  HStoreNamedField* AddStoreMapConstant(HValue* object, Handle<Map> map) {
1439    return Add<HStoreNamedField>(object, HObjectAccess::ForMap(),
1440                                 Add<HConstant>(map));
1441  }
1442  HLoadNamedField* AddLoadMap(HValue* object,
1443                              HValue* dependency = NULL);
1444  HLoadNamedField* AddLoadElements(HValue* object,
1445                                   HValue* dependency = NULL);
1446
1447  bool MatchRotateRight(HValue* left,
1448                        HValue* right,
1449                        HValue** operand,
1450                        HValue** shift_amount);
1451
1452  HValue* BuildBinaryOperation(Token::Value op,
1453                               HValue* left,
1454                               HValue* right,
1455                               Type* left_type,
1456                               Type* right_type,
1457                               Type* result_type,
1458                               Maybe<int> fixed_right_arg,
1459                               HAllocationMode allocation_mode);
1460
1461  HLoadNamedField* AddLoadFixedArrayLength(HValue *object,
1462                                           HValue *dependency = NULL);
1463
1464  HLoadNamedField* AddLoadArrayLength(HValue *object,
1465                                      ElementsKind kind,
1466                                      HValue *dependency = NULL);
1467
1468  HValue* AddLoadJSBuiltin(Builtins::JavaScript builtin);
1469
1470  HValue* EnforceNumberType(HValue* number, Type* expected);
1471  HValue* TruncateToNumber(HValue* value, Type** expected);
1472
1473  void FinishExitWithHardDeoptimization(const char* reason);
1474
1475  void AddIncrementCounter(StatsCounter* counter);
1476
1477  class IfBuilder FINAL {
1478   public:
1479    // If using this constructor, Initialize() must be called explicitly!
1480    IfBuilder();
1481
1482    explicit IfBuilder(HGraphBuilder* builder);
1483    IfBuilder(HGraphBuilder* builder,
1484              HIfContinuation* continuation);
1485
1486    ~IfBuilder() {
1487      if (!finished_) End();
1488    }
1489
1490    void Initialize(HGraphBuilder* builder);
1491
1492    template<class Condition>
1493    Condition* If(HValue *p) {
1494      Condition* compare = builder()->New<Condition>(p);
1495      AddCompare(compare);
1496      return compare;
1497    }
1498
1499    template<class Condition, class P2>
1500    Condition* If(HValue* p1, P2 p2) {
1501      Condition* compare = builder()->New<Condition>(p1, p2);
1502      AddCompare(compare);
1503      return compare;
1504    }
1505
1506    template<class Condition, class P2, class P3>
1507    Condition* If(HValue* p1, P2 p2, P3 p3) {
1508      Condition* compare = builder()->New<Condition>(p1, p2, p3);
1509      AddCompare(compare);
1510      return compare;
1511    }
1512
1513    template<class Condition>
1514    Condition* IfNot(HValue* p) {
1515      Condition* compare = If<Condition>(p);
1516      compare->Not();
1517      return compare;
1518    }
1519
1520    template<class Condition, class P2>
1521    Condition* IfNot(HValue* p1, P2 p2) {
1522      Condition* compare = If<Condition>(p1, p2);
1523      compare->Not();
1524      return compare;
1525    }
1526
1527    template<class Condition, class P2, class P3>
1528    Condition* IfNot(HValue* p1, P2 p2, P3 p3) {
1529      Condition* compare = If<Condition>(p1, p2, p3);
1530      compare->Not();
1531      return compare;
1532    }
1533
1534    template<class Condition>
1535    Condition* OrIf(HValue *p) {
1536      Or();
1537      return If<Condition>(p);
1538    }
1539
1540    template<class Condition, class P2>
1541    Condition* OrIf(HValue* p1, P2 p2) {
1542      Or();
1543      return If<Condition>(p1, p2);
1544    }
1545
1546    template<class Condition, class P2, class P3>
1547    Condition* OrIf(HValue* p1, P2 p2, P3 p3) {
1548      Or();
1549      return If<Condition>(p1, p2, p3);
1550    }
1551
1552    template<class Condition>
1553    Condition* AndIf(HValue *p) {
1554      And();
1555      return If<Condition>(p);
1556    }
1557
1558    template<class Condition, class P2>
1559    Condition* AndIf(HValue* p1, P2 p2) {
1560      And();
1561      return If<Condition>(p1, p2);
1562    }
1563
1564    template<class Condition, class P2, class P3>
1565    Condition* AndIf(HValue* p1, P2 p2, P3 p3) {
1566      And();
1567      return If<Condition>(p1, p2, p3);
1568    }
1569
1570    void Or();
1571    void And();
1572
1573    // Captures the current state of this IfBuilder in the specified
1574    // continuation and ends this IfBuilder.
1575    void CaptureContinuation(HIfContinuation* continuation);
1576
1577    // Joins the specified continuation from this IfBuilder and ends this
1578    // IfBuilder. This appends a Goto instruction from the true branch of
1579    // this IfBuilder to the true branch of the continuation unless the
1580    // true branch of this IfBuilder is already finished. And vice versa
1581    // for the false branch.
1582    //
1583    // The basic idea is as follows: You have several nested IfBuilder's
1584    // that you want to join based on two possible outcomes (i.e. success
1585    // and failure, or whatever). You can do this easily using this method
1586    // now, for example:
1587    //
1588    //   HIfContinuation cont(graph()->CreateBasicBlock(),
1589    //                        graph()->CreateBasicBlock());
1590    //   ...
1591    //     IfBuilder if_whatever(this);
1592    //     if_whatever.If<Condition>(arg);
1593    //     if_whatever.Then();
1594    //     ...
1595    //     if_whatever.Else();
1596    //     ...
1597    //     if_whatever.JoinContinuation(&cont);
1598    //   ...
1599    //     IfBuilder if_something(this);
1600    //     if_something.If<Condition>(arg1, arg2);
1601    //     if_something.Then();
1602    //     ...
1603    //     if_something.Else();
1604    //     ...
1605    //     if_something.JoinContinuation(&cont);
1606    //   ...
1607    //   IfBuilder if_finally(this, &cont);
1608    //   if_finally.Then();
1609    //   // continues after then code of if_whatever or if_something.
1610    //   ...
1611    //   if_finally.Else();
1612    //   // continues after else code of if_whatever or if_something.
1613    //   ...
1614    //   if_finally.End();
1615    void JoinContinuation(HIfContinuation* continuation);
1616
1617    void Then();
1618    void Else();
1619    void End();
1620
1621    void Deopt(const char* reason);
1622    void ThenDeopt(const char* reason) {
1623      Then();
1624      Deopt(reason);
1625    }
1626    void ElseDeopt(const char* reason) {
1627      Else();
1628      Deopt(reason);
1629    }
1630
1631    void Return(HValue* value);
1632
1633   private:
1634    void InitializeDontCreateBlocks(HGraphBuilder* builder);
1635
1636    HControlInstruction* AddCompare(HControlInstruction* compare);
1637
1638    HGraphBuilder* builder() const {
1639      DCHECK(builder_ != NULL);  // Have you called "Initialize"?
1640      return builder_;
1641    }
1642
1643    void AddMergeAtJoinBlock(bool deopt);
1644
1645    void Finish();
1646    void Finish(HBasicBlock** then_continuation,
1647                HBasicBlock** else_continuation);
1648
1649    class MergeAtJoinBlock : public ZoneObject {
1650     public:
1651      MergeAtJoinBlock(HBasicBlock* block,
1652                       bool deopt,
1653                       MergeAtJoinBlock* next)
1654        : block_(block),
1655          deopt_(deopt),
1656          next_(next) {}
1657      HBasicBlock* block_;
1658      bool deopt_;
1659      MergeAtJoinBlock* next_;
1660    };
1661
1662    HGraphBuilder* builder_;
1663    bool finished_ : 1;
1664    bool did_then_ : 1;
1665    bool did_else_ : 1;
1666    bool did_else_if_ : 1;
1667    bool did_and_ : 1;
1668    bool did_or_ : 1;
1669    bool captured_ : 1;
1670    bool needs_compare_ : 1;
1671    bool pending_merge_block_ : 1;
1672    HBasicBlock* first_true_block_;
1673    HBasicBlock* first_false_block_;
1674    HBasicBlock* split_edge_merge_block_;
1675    MergeAtJoinBlock* merge_at_join_blocks_;
1676    int normal_merge_at_join_block_count_;
1677    int deopt_merge_at_join_block_count_;
1678  };
1679
1680  class LoopBuilder FINAL {
1681   public:
1682    enum Direction {
1683      kPreIncrement,
1684      kPostIncrement,
1685      kPreDecrement,
1686      kPostDecrement,
1687      kWhileTrue
1688    };
1689
1690    explicit LoopBuilder(HGraphBuilder* builder);  // while (true) {...}
1691    LoopBuilder(HGraphBuilder* builder,
1692                HValue* context,
1693                Direction direction);
1694    LoopBuilder(HGraphBuilder* builder,
1695                HValue* context,
1696                Direction direction,
1697                HValue* increment_amount);
1698
1699    ~LoopBuilder() {
1700      DCHECK(finished_);
1701    }
1702
1703    HValue* BeginBody(
1704        HValue* initial,
1705        HValue* terminating,
1706        Token::Value token);
1707
1708    void BeginBody(int drop_count);
1709
1710    void Break();
1711
1712    void EndBody();
1713
1714   private:
1715    void Initialize(HGraphBuilder* builder, HValue* context,
1716                    Direction direction, HValue* increment_amount);
1717    Zone* zone() { return builder_->zone(); }
1718
1719    HGraphBuilder* builder_;
1720    HValue* context_;
1721    HValue* increment_amount_;
1722    HInstruction* increment_;
1723    HPhi* phi_;
1724    HBasicBlock* header_block_;
1725    HBasicBlock* body_block_;
1726    HBasicBlock* exit_block_;
1727    HBasicBlock* exit_trampoline_block_;
1728    Direction direction_;
1729    bool finished_;
1730  };
1731
1732  HValue* BuildNewElementsCapacity(HValue* old_capacity);
1733
1734  class JSArrayBuilder FINAL {
1735   public:
1736    JSArrayBuilder(HGraphBuilder* builder,
1737                   ElementsKind kind,
1738                   HValue* allocation_site_payload,
1739                   HValue* constructor_function,
1740                   AllocationSiteOverrideMode override_mode);
1741
1742    JSArrayBuilder(HGraphBuilder* builder,
1743                   ElementsKind kind,
1744                   HValue* constructor_function = NULL);
1745
1746    enum FillMode {
1747      DONT_FILL_WITH_HOLE,
1748      FILL_WITH_HOLE
1749    };
1750
1751    ElementsKind kind() { return kind_; }
1752    HAllocate* elements_location() { return elements_location_; }
1753
1754    HAllocate* AllocateEmptyArray();
1755    HAllocate* AllocateArray(HValue* capacity,
1756                             HValue* length_field,
1757                             FillMode fill_mode = FILL_WITH_HOLE);
1758    // Use these allocators when capacity could be unknown at compile time
1759    // but its limit is known. For constant |capacity| the value of
1760    // |capacity_upper_bound| is ignored and the actual |capacity|
1761    // value is used as an upper bound.
1762    HAllocate* AllocateArray(HValue* capacity,
1763                             int capacity_upper_bound,
1764                             HValue* length_field,
1765                             FillMode fill_mode = FILL_WITH_HOLE);
1766    HAllocate* AllocateArray(HValue* capacity,
1767                             HConstant* capacity_upper_bound,
1768                             HValue* length_field,
1769                             FillMode fill_mode = FILL_WITH_HOLE);
1770    HValue* GetElementsLocation() { return elements_location_; }
1771    HValue* EmitMapCode();
1772
1773   private:
1774    Zone* zone() const { return builder_->zone(); }
1775    int elements_size() const {
1776      return IsFastDoubleElementsKind(kind_) ? kDoubleSize : kPointerSize;
1777    }
1778    HGraphBuilder* builder() { return builder_; }
1779    HGraph* graph() { return builder_->graph(); }
1780    int initial_capacity() {
1781      STATIC_ASSERT(JSArray::kPreallocatedArrayElements > 0);
1782      return JSArray::kPreallocatedArrayElements;
1783    }
1784
1785    HValue* EmitInternalMapCode();
1786
1787    HGraphBuilder* builder_;
1788    ElementsKind kind_;
1789    AllocationSiteMode mode_;
1790    HValue* allocation_site_payload_;
1791    HValue* constructor_function_;
1792    HAllocate* elements_location_;
1793  };
1794
1795  HValue* BuildAllocateArrayFromLength(JSArrayBuilder* array_builder,
1796                                       HValue* length_argument);
1797  HValue* BuildCalculateElementsSize(ElementsKind kind,
1798                                     HValue* capacity);
1799  HAllocate* AllocateJSArrayObject(AllocationSiteMode mode);
1800  HConstant* EstablishElementsAllocationSize(ElementsKind kind, int capacity);
1801
1802  HAllocate* BuildAllocateElements(ElementsKind kind, HValue* size_in_bytes);
1803
1804  void BuildInitializeElementsHeader(HValue* elements,
1805                                     ElementsKind kind,
1806                                     HValue* capacity);
1807
1808  HValue* BuildAllocateElementsAndInitializeElementsHeader(ElementsKind kind,
1809                                                           HValue* capacity);
1810
1811  // |array| must have been allocated with enough room for
1812  // 1) the JSArray and 2) an AllocationMemento if mode requires it.
1813  // If the |elements| value provided is NULL then the array elements storage
1814  // is initialized with empty array.
1815  void BuildJSArrayHeader(HValue* array,
1816                          HValue* array_map,
1817                          HValue* elements,
1818                          AllocationSiteMode mode,
1819                          ElementsKind elements_kind,
1820                          HValue* allocation_site_payload,
1821                          HValue* length_field);
1822
1823  HValue* BuildGrowElementsCapacity(HValue* object,
1824                                    HValue* elements,
1825                                    ElementsKind kind,
1826                                    ElementsKind new_kind,
1827                                    HValue* length,
1828                                    HValue* new_capacity);
1829
1830  void BuildFillElementsWithValue(HValue* elements,
1831                                  ElementsKind elements_kind,
1832                                  HValue* from,
1833                                  HValue* to,
1834                                  HValue* value);
1835
1836  void BuildFillElementsWithHole(HValue* elements,
1837                                 ElementsKind elements_kind,
1838                                 HValue* from,
1839                                 HValue* to);
1840
1841  void BuildCopyElements(HValue* from_elements,
1842                         ElementsKind from_elements_kind,
1843                         HValue* to_elements,
1844                         ElementsKind to_elements_kind,
1845                         HValue* length,
1846                         HValue* capacity);
1847
1848  HValue* BuildCloneShallowArrayCow(HValue* boilerplate,
1849                                    HValue* allocation_site,
1850                                    AllocationSiteMode mode,
1851                                    ElementsKind kind);
1852
1853  HValue* BuildCloneShallowArrayEmpty(HValue* boilerplate,
1854                                      HValue* allocation_site,
1855                                      AllocationSiteMode mode);
1856
1857  HValue* BuildCloneShallowArrayNonEmpty(HValue* boilerplate,
1858                                         HValue* allocation_site,
1859                                         AllocationSiteMode mode,
1860                                         ElementsKind kind);
1861
1862  HValue* BuildElementIndexHash(HValue* index);
1863
1864  void BuildCompareNil(
1865      HValue* value,
1866      Type* type,
1867      HIfContinuation* continuation);
1868
1869  void BuildCreateAllocationMemento(HValue* previous_object,
1870                                    HValue* previous_object_size,
1871                                    HValue* payload);
1872
1873  HInstruction* BuildConstantMapCheck(Handle<JSObject> constant);
1874  HInstruction* BuildCheckPrototypeMaps(Handle<JSObject> prototype,
1875                                        Handle<JSObject> holder);
1876
1877  HInstruction* BuildGetNativeContext(HValue* closure);
1878  HInstruction* BuildGetNativeContext();
1879  HInstruction* BuildGetArrayFunction();
1880
1881 protected:
1882  void SetSourcePosition(int position) {
1883    DCHECK(position != RelocInfo::kNoPosition);
1884    position_.set_position(position - start_position_);
1885  }
1886
1887  void EnterInlinedSource(int start_position, int id) {
1888    if (FLAG_hydrogen_track_positions) {
1889      start_position_ = start_position;
1890      position_.set_inlining_id(id);
1891    }
1892  }
1893
1894  // Convert the given absolute offset from the start of the script to
1895  // the HSourcePosition assuming that this position corresponds to the
1896  // same function as current position_.
1897  HSourcePosition ScriptPositionToSourcePosition(int position) {
1898    HSourcePosition pos = position_;
1899    pos.set_position(position - start_position_);
1900    return pos;
1901  }
1902
1903  HSourcePosition source_position() { return position_; }
1904  void set_source_position(HSourcePosition position) {
1905    position_ = position;
1906  }
1907
1908  template <typename ViewClass>
1909  void BuildArrayBufferViewInitialization(HValue* obj,
1910                                          HValue* buffer,
1911                                          HValue* byte_offset,
1912                                          HValue* byte_length);
1913
1914 private:
1915  HGraphBuilder();
1916
1917  template <class I>
1918  I* AddInstructionTyped(I* instr) {
1919    return I::cast(AddInstruction(instr));
1920  }
1921
1922  CompilationInfo* info_;
1923  HGraph* graph_;
1924  HBasicBlock* current_block_;
1925  Scope* scope_;
1926  HSourcePosition position_;
1927  int start_position_;
1928};
1929
1930
1931template<>
1932inline HDeoptimize* HGraphBuilder::Add<HDeoptimize>(
1933    const char* reason, Deoptimizer::BailoutType type) {
1934  if (type == Deoptimizer::SOFT) {
1935    isolate()->counters()->soft_deopts_requested()->Increment();
1936    if (FLAG_always_opt) return NULL;
1937  }
1938  if (current_block()->IsDeoptimizing()) return NULL;
1939  HBasicBlock* after_deopt_block = CreateBasicBlock(
1940      current_block()->last_environment());
1941  HDeoptimize* instr = New<HDeoptimize>(reason, type, after_deopt_block);
1942  if (type == Deoptimizer::SOFT) {
1943    isolate()->counters()->soft_deopts_inserted()->Increment();
1944  }
1945  FinishCurrentBlock(instr);
1946  set_current_block(after_deopt_block);
1947  return instr;
1948}
1949
1950
1951template<>
1952inline HInstruction* HGraphBuilder::AddUncasted<HDeoptimize>(
1953    const char* reason, Deoptimizer::BailoutType type) {
1954  return Add<HDeoptimize>(reason, type);
1955}
1956
1957
1958template<>
1959inline HSimulate* HGraphBuilder::Add<HSimulate>(
1960    BailoutId id,
1961    RemovableSimulate removable) {
1962  HSimulate* instr = current_block()->CreateSimulate(id, removable);
1963  AddInstruction(instr);
1964  return instr;
1965}
1966
1967
1968template<>
1969inline HSimulate* HGraphBuilder::Add<HSimulate>(
1970    BailoutId id) {
1971  return Add<HSimulate>(id, FIXED_SIMULATE);
1972}
1973
1974
1975template<>
1976inline HInstruction* HGraphBuilder::AddUncasted<HSimulate>(BailoutId id) {
1977  return Add<HSimulate>(id, FIXED_SIMULATE);
1978}
1979
1980
1981template<>
1982inline HReturn* HGraphBuilder::Add<HReturn>(HValue* value) {
1983  int num_parameters = graph()->info()->num_parameters();
1984  HValue* params = AddUncasted<HConstant>(num_parameters);
1985  HReturn* return_instruction = New<HReturn>(value, params);
1986  FinishExitCurrentBlock(return_instruction);
1987  return return_instruction;
1988}
1989
1990
1991template<>
1992inline HReturn* HGraphBuilder::Add<HReturn>(HConstant* value) {
1993  return Add<HReturn>(static_cast<HValue*>(value));
1994}
1995
1996template<>
1997inline HInstruction* HGraphBuilder::AddUncasted<HReturn>(HValue* value) {
1998  return Add<HReturn>(value);
1999}
2000
2001
2002template<>
2003inline HInstruction* HGraphBuilder::AddUncasted<HReturn>(HConstant* value) {
2004  return Add<HReturn>(value);
2005}
2006
2007
2008template<>
2009inline HCallRuntime* HGraphBuilder::Add<HCallRuntime>(
2010    Handle<String> name,
2011    const Runtime::Function* c_function,
2012    int argument_count) {
2013  HCallRuntime* instr = New<HCallRuntime>(name, c_function, argument_count);
2014  if (graph()->info()->IsStub()) {
2015    // When compiling code stubs, we don't want to save all double registers
2016    // upon entry to the stub, but instead have the call runtime instruction
2017    // save the double registers only on-demand (in the fallback case).
2018    instr->set_save_doubles(kSaveFPRegs);
2019  }
2020  AddInstruction(instr);
2021  return instr;
2022}
2023
2024
2025template<>
2026inline HInstruction* HGraphBuilder::AddUncasted<HCallRuntime>(
2027    Handle<String> name,
2028    const Runtime::Function* c_function,
2029    int argument_count) {
2030  return Add<HCallRuntime>(name, c_function, argument_count);
2031}
2032
2033
2034template<>
2035inline HContext* HGraphBuilder::New<HContext>() {
2036  return HContext::New(zone());
2037}
2038
2039
2040template<>
2041inline HInstruction* HGraphBuilder::NewUncasted<HContext>() {
2042  return New<HContext>();
2043}
2044
2045class HOptimizedGraphBuilder : public HGraphBuilder, public AstVisitor {
2046 public:
2047  // A class encapsulating (lazily-allocated) break and continue blocks for
2048  // a breakable statement.  Separated from BreakAndContinueScope so that it
2049  // can have a separate lifetime.
2050  class BreakAndContinueInfo FINAL BASE_EMBEDDED {
2051   public:
2052    explicit BreakAndContinueInfo(BreakableStatement* target,
2053                                  Scope* scope,
2054                                  int drop_extra = 0)
2055        : target_(target),
2056          break_block_(NULL),
2057          continue_block_(NULL),
2058          scope_(scope),
2059          drop_extra_(drop_extra) {
2060    }
2061
2062    BreakableStatement* target() { return target_; }
2063    HBasicBlock* break_block() { return break_block_; }
2064    void set_break_block(HBasicBlock* block) { break_block_ = block; }
2065    HBasicBlock* continue_block() { return continue_block_; }
2066    void set_continue_block(HBasicBlock* block) { continue_block_ = block; }
2067    Scope* scope() { return scope_; }
2068    int drop_extra() { return drop_extra_; }
2069
2070   private:
2071    BreakableStatement* target_;
2072    HBasicBlock* break_block_;
2073    HBasicBlock* continue_block_;
2074    Scope* scope_;
2075    int drop_extra_;
2076  };
2077
2078  // A helper class to maintain a stack of current BreakAndContinueInfo
2079  // structures mirroring BreakableStatement nesting.
2080  class BreakAndContinueScope FINAL BASE_EMBEDDED {
2081   public:
2082    BreakAndContinueScope(BreakAndContinueInfo* info,
2083                          HOptimizedGraphBuilder* owner)
2084        : info_(info), owner_(owner), next_(owner->break_scope()) {
2085      owner->set_break_scope(this);
2086    }
2087
2088    ~BreakAndContinueScope() { owner_->set_break_scope(next_); }
2089
2090    BreakAndContinueInfo* info() { return info_; }
2091    HOptimizedGraphBuilder* owner() { return owner_; }
2092    BreakAndContinueScope* next() { return next_; }
2093
2094    // Search the break stack for a break or continue target.
2095    enum BreakType { BREAK, CONTINUE };
2096    HBasicBlock* Get(BreakableStatement* stmt, BreakType type,
2097                     Scope** scope, int* drop_extra);
2098
2099   private:
2100    BreakAndContinueInfo* info_;
2101    HOptimizedGraphBuilder* owner_;
2102    BreakAndContinueScope* next_;
2103  };
2104
2105  explicit HOptimizedGraphBuilder(CompilationInfo* info);
2106
2107  virtual bool BuildGraph() OVERRIDE;
2108
2109  // Simple accessors.
2110  BreakAndContinueScope* break_scope() const { return break_scope_; }
2111  void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; }
2112
2113  HValue* context() { return environment()->context(); }
2114
2115  HOsrBuilder* osr() const { return osr_; }
2116
2117  void Bailout(BailoutReason reason);
2118
2119  HBasicBlock* CreateJoin(HBasicBlock* first,
2120                          HBasicBlock* second,
2121                          BailoutId join_id);
2122
2123  FunctionState* function_state() const { return function_state_; }
2124
2125  void VisitDeclarations(ZoneList<Declaration*>* declarations);
2126
2127  void* operator new(size_t size, Zone* zone) {
2128    return zone->New(static_cast<int>(size));
2129  }
2130  void operator delete(void* pointer, Zone* zone) { }
2131  void operator delete(void* pointer) { }
2132
2133  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
2134
2135 protected:
2136  // Type of a member function that generates inline code for a native function.
2137  typedef void (HOptimizedGraphBuilder::*InlineFunctionGenerator)
2138      (CallRuntime* call);
2139
2140  // Forward declarations for inner scope classes.
2141  class SubgraphScope;
2142
2143  static const InlineFunctionGenerator kInlineFunctionGenerators[];
2144
2145  static const int kMaxCallPolymorphism = 4;
2146  static const int kMaxLoadPolymorphism = 4;
2147  static const int kMaxStorePolymorphism = 4;
2148
2149  // Even in the 'unlimited' case we have to have some limit in order not to
2150  // overflow the stack.
2151  static const int kUnlimitedMaxInlinedSourceSize = 100000;
2152  static const int kUnlimitedMaxInlinedNodes = 10000;
2153  static const int kUnlimitedMaxInlinedNodesCumulative = 10000;
2154
2155  // Maximum depth and total number of elements and properties for literal
2156  // graphs to be considered for fast deep-copying.
2157  static const int kMaxFastLiteralDepth = 3;
2158  static const int kMaxFastLiteralProperties = 8;
2159
2160  // Simple accessors.
2161  void set_function_state(FunctionState* state) { function_state_ = state; }
2162
2163  AstContext* ast_context() const { return ast_context_; }
2164  void set_ast_context(AstContext* context) { ast_context_ = context; }
2165
2166  // Accessors forwarded to the function state.
2167  CompilationInfo* current_info() const {
2168    return function_state()->compilation_info();
2169  }
2170  AstContext* call_context() const {
2171    return function_state()->call_context();
2172  }
2173  HBasicBlock* function_return() const {
2174    return function_state()->function_return();
2175  }
2176  TestContext* inlined_test_context() const {
2177    return function_state()->test_context();
2178  }
2179  void ClearInlinedTestContext() {
2180    function_state()->ClearInlinedTestContext();
2181  }
2182  StrictMode function_strict_mode() {
2183    return function_state()->compilation_info()->strict_mode();
2184  }
2185
2186  // Generators for inline runtime functions.
2187#define INLINE_FUNCTION_GENERATOR_DECLARATION(Name, argc, ressize)      \
2188  void Generate##Name(CallRuntime* call);
2189
2190  INLINE_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
2191  INLINE_OPTIMIZED_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
2192#undef INLINE_FUNCTION_GENERATOR_DECLARATION
2193
2194  void VisitDelete(UnaryOperation* expr);
2195  void VisitVoid(UnaryOperation* expr);
2196  void VisitTypeof(UnaryOperation* expr);
2197  void VisitNot(UnaryOperation* expr);
2198
2199  void VisitComma(BinaryOperation* expr);
2200  void VisitLogicalExpression(BinaryOperation* expr);
2201  void VisitArithmeticExpression(BinaryOperation* expr);
2202
2203  bool PreProcessOsrEntry(IterationStatement* statement);
2204  void VisitLoopBody(IterationStatement* stmt,
2205                     HBasicBlock* loop_entry);
2206
2207  // Create a back edge in the flow graph.  body_exit is the predecessor
2208  // block and loop_entry is the successor block.  loop_successor is the
2209  // block where control flow exits the loop normally (e.g., via failure of
2210  // the condition) and break_block is the block where control flow breaks
2211  // from the loop.  All blocks except loop_entry can be NULL.  The return
2212  // value is the new successor block which is the join of loop_successor
2213  // and break_block, or NULL.
2214  HBasicBlock* CreateLoop(IterationStatement* statement,
2215                          HBasicBlock* loop_entry,
2216                          HBasicBlock* body_exit,
2217                          HBasicBlock* loop_successor,
2218                          HBasicBlock* break_block);
2219
2220  // Build a loop entry
2221  HBasicBlock* BuildLoopEntry();
2222
2223  // Builds a loop entry respectful of OSR requirements
2224  HBasicBlock* BuildLoopEntry(IterationStatement* statement);
2225
2226  HBasicBlock* JoinContinue(IterationStatement* statement,
2227                            HBasicBlock* exit_block,
2228                            HBasicBlock* continue_block);
2229
2230  HValue* Top() const { return environment()->Top(); }
2231  void Drop(int n) { environment()->Drop(n); }
2232  void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
2233  bool IsEligibleForEnvironmentLivenessAnalysis(Variable* var,
2234                                                int index,
2235                                                HValue* value,
2236                                                HEnvironment* env) {
2237    if (!FLAG_analyze_environment_liveness) return false;
2238    // |this| and |arguments| are always live; zapping parameters isn't
2239    // safe because function.arguments can inspect them at any time.
2240    return !var->is_this() &&
2241           !var->is_arguments() &&
2242           !value->IsArgumentsObject() &&
2243           env->is_local_index(index);
2244  }
2245  void BindIfLive(Variable* var, HValue* value) {
2246    HEnvironment* env = environment();
2247    int index = env->IndexFor(var);
2248    env->Bind(index, value);
2249    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) {
2250      HEnvironmentMarker* bind =
2251          Add<HEnvironmentMarker>(HEnvironmentMarker::BIND, index);
2252      USE(bind);
2253#ifdef DEBUG
2254      bind->set_closure(env->closure());
2255#endif
2256    }
2257  }
2258
2259  HValue* LookupAndMakeLive(Variable* var) {
2260    HEnvironment* env = environment();
2261    int index = env->IndexFor(var);
2262    HValue* value = env->Lookup(index);
2263    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) {
2264      HEnvironmentMarker* lookup =
2265          Add<HEnvironmentMarker>(HEnvironmentMarker::LOOKUP, index);
2266      USE(lookup);
2267#ifdef DEBUG
2268      lookup->set_closure(env->closure());
2269#endif
2270    }
2271    return value;
2272  }
2273
2274  // The value of the arguments object is allowed in some but not most value
2275  // contexts.  (It's allowed in all effect contexts and disallowed in all
2276  // test contexts.)
2277  void VisitForValue(Expression* expr,
2278                     ArgumentsAllowedFlag flag = ARGUMENTS_NOT_ALLOWED);
2279  void VisitForTypeOf(Expression* expr);
2280  void VisitForEffect(Expression* expr);
2281  void VisitForControl(Expression* expr,
2282                       HBasicBlock* true_block,
2283                       HBasicBlock* false_block);
2284
2285  // Visit a list of expressions from left to right, each in a value context.
2286  void VisitExpressions(ZoneList<Expression*>* exprs);
2287
2288  // Remove the arguments from the bailout environment and emit instructions
2289  // to push them as outgoing parameters.
2290  template <class Instruction> HInstruction* PreProcessCall(Instruction* call);
2291  void PushArgumentsFromEnvironment(int count);
2292
2293  void SetUpScope(Scope* scope);
2294  virtual void VisitStatements(ZoneList<Statement*>* statements) OVERRIDE;
2295
2296#define DECLARE_VISIT(type) virtual void Visit##type(type* node) OVERRIDE;
2297  AST_NODE_LIST(DECLARE_VISIT)
2298#undef DECLARE_VISIT
2299
2300  Type* ToType(Handle<Map> map);
2301
2302 private:
2303  // Helpers for flow graph construction.
2304  enum GlobalPropertyAccess {
2305    kUseCell,
2306    kUseGeneric
2307  };
2308  GlobalPropertyAccess LookupGlobalProperty(Variable* var, LookupIterator* it,
2309                                            PropertyAccessType access_type);
2310
2311  void EnsureArgumentsArePushedForAccess();
2312  bool TryArgumentsAccess(Property* expr);
2313
2314  // Try to optimize fun.apply(receiver, arguments) pattern.
2315  bool TryCallApply(Call* expr);
2316
2317  bool TryHandleArrayCall(Call* expr, HValue* function);
2318  bool TryHandleArrayCallNew(CallNew* expr, HValue* function);
2319  void BuildArrayCall(Expression* expr, int arguments_count, HValue* function,
2320                      Handle<AllocationSite> cell);
2321
2322  enum ArrayIndexOfMode { kFirstIndexOf, kLastIndexOf };
2323  HValue* BuildArrayIndexOf(HValue* receiver,
2324                            HValue* search_element,
2325                            ElementsKind kind,
2326                            ArrayIndexOfMode mode);
2327
2328  HValue* ImplicitReceiverFor(HValue* function,
2329                              Handle<JSFunction> target);
2330
2331  int InliningAstSize(Handle<JSFunction> target);
2332  bool TryInline(Handle<JSFunction> target,
2333                 int arguments_count,
2334                 HValue* implicit_return_value,
2335                 BailoutId ast_id,
2336                 BailoutId return_id,
2337                 InliningKind inlining_kind,
2338                 HSourcePosition position);
2339
2340  bool TryInlineCall(Call* expr);
2341  bool TryInlineConstruct(CallNew* expr, HValue* implicit_return_value);
2342  bool TryInlineGetter(Handle<JSFunction> getter,
2343                       Handle<Map> receiver_map,
2344                       BailoutId ast_id,
2345                       BailoutId return_id);
2346  bool TryInlineSetter(Handle<JSFunction> setter,
2347                       Handle<Map> receiver_map,
2348                       BailoutId id,
2349                       BailoutId assignment_id,
2350                       HValue* implicit_return_value);
2351  bool TryInlineApply(Handle<JSFunction> function,
2352                      Call* expr,
2353                      int arguments_count);
2354  bool TryInlineBuiltinMethodCall(Call* expr,
2355                                  HValue* receiver,
2356                                  Handle<Map> receiver_map);
2357  bool TryInlineBuiltinFunctionCall(Call* expr);
2358  enum ApiCallType {
2359    kCallApiFunction,
2360    kCallApiMethod,
2361    kCallApiGetter,
2362    kCallApiSetter
2363  };
2364  bool TryInlineApiMethodCall(Call* expr,
2365                              HValue* receiver,
2366                              SmallMapList* receiver_types);
2367  bool TryInlineApiFunctionCall(Call* expr, HValue* receiver);
2368  bool TryInlineApiGetter(Handle<JSFunction> function,
2369                          Handle<Map> receiver_map,
2370                          BailoutId ast_id);
2371  bool TryInlineApiSetter(Handle<JSFunction> function,
2372                          Handle<Map> receiver_map,
2373                          BailoutId ast_id);
2374  bool TryInlineApiCall(Handle<JSFunction> function,
2375                         HValue* receiver,
2376                         SmallMapList* receiver_maps,
2377                         int argc,
2378                         BailoutId ast_id,
2379                         ApiCallType call_type);
2380
2381  // If --trace-inlining, print a line of the inlining trace.  Inlining
2382  // succeeded if the reason string is NULL and failed if there is a
2383  // non-NULL reason string.
2384  void TraceInline(Handle<JSFunction> target,
2385                   Handle<JSFunction> caller,
2386                   const char* failure_reason);
2387
2388  void HandleGlobalVariableAssignment(Variable* var,
2389                                      HValue* value,
2390                                      BailoutId ast_id);
2391
2392  void HandlePropertyAssignment(Assignment* expr);
2393  void HandleCompoundAssignment(Assignment* expr);
2394  void HandlePolymorphicNamedFieldAccess(PropertyAccessType access_type,
2395                                         Expression* expr,
2396                                         BailoutId ast_id,
2397                                         BailoutId return_id,
2398                                         HValue* object,
2399                                         HValue* value,
2400                                         SmallMapList* types,
2401                                         Handle<String> name);
2402
2403  HValue* BuildAllocateExternalElements(
2404      ExternalArrayType array_type,
2405      bool is_zero_byte_offset,
2406      HValue* buffer, HValue* byte_offset, HValue* length);
2407  HValue* BuildAllocateFixedTypedArray(
2408      ExternalArrayType array_type, size_t element_size,
2409      ElementsKind fixed_elements_kind,
2410      HValue* byte_length, HValue* length);
2411
2412  Handle<JSFunction> array_function() {
2413    return handle(isolate()->native_context()->array_function());
2414  }
2415
2416  bool IsCallArrayInlineable(int argument_count, Handle<AllocationSite> site);
2417  void BuildInlinedCallArray(Expression* expression, int argument_count,
2418                             Handle<AllocationSite> site);
2419
2420  class PropertyAccessInfo {
2421   public:
2422    PropertyAccessInfo(HOptimizedGraphBuilder* builder,
2423                       PropertyAccessType access_type,
2424                       Type* type,
2425                       Handle<String> name)
2426        : lookup_(builder->isolate()),
2427          builder_(builder),
2428          access_type_(access_type),
2429          type_(type),
2430          name_(name),
2431          field_type_(HType::Tagged()),
2432          access_(HObjectAccess::ForMap()) { }
2433
2434    // Checkes whether this PropertyAccessInfo can be handled as a monomorphic
2435    // load named. It additionally fills in the fields necessary to generate the
2436    // lookup code.
2437    bool CanAccessMonomorphic();
2438
2439    // Checks whether all types behave uniform when loading name. If all maps
2440    // behave the same, a single monomorphic load instruction can be emitted,
2441    // guarded by a single map-checks instruction that whether the receiver is
2442    // an instance of any of the types.
2443    // This method skips the first type in types, assuming that this
2444    // PropertyAccessInfo is built for types->first().
2445    bool CanAccessAsMonomorphic(SmallMapList* types);
2446
2447    Handle<Map> map();
2448    Type* type() const { return type_; }
2449    Handle<String> name() const { return name_; }
2450
2451    bool IsJSObjectFieldAccessor() {
2452      int offset;  // unused
2453      return Accessors::IsJSObjectFieldAccessor<Type>(type_, name_, &offset);
2454    }
2455
2456    bool GetJSObjectFieldAccess(HObjectAccess* access) {
2457      int offset;
2458      if (Accessors::IsJSObjectFieldAccessor<Type>(type_, name_, &offset)) {
2459        if (type_->Is(Type::String())) {
2460          DCHECK(String::Equals(isolate()->factory()->length_string(), name_));
2461          *access = HObjectAccess::ForStringLength();
2462        } else if (type_->Is(Type::Array())) {
2463          DCHECK(String::Equals(isolate()->factory()->length_string(), name_));
2464          *access = HObjectAccess::ForArrayLength(map()->elements_kind());
2465        } else {
2466          *access = HObjectAccess::ForMapAndOffset(map(), offset);
2467        }
2468        return true;
2469      }
2470      return false;
2471    }
2472
2473    bool has_holder() { return !holder_.is_null(); }
2474    bool IsLoad() const { return access_type_ == LOAD; }
2475
2476    Handle<JSObject> holder() { return holder_; }
2477    Handle<JSFunction> accessor() { return accessor_; }
2478    Handle<Object> constant() { return constant_; }
2479    Handle<Map> transition() { return handle(lookup_.GetTransitionTarget()); }
2480    SmallMapList* field_maps() { return &field_maps_; }
2481    HType field_type() const { return field_type_; }
2482    HObjectAccess access() { return access_; }
2483
2484    bool IsFound() const { return lookup_.IsFound(); }
2485    bool IsProperty() const { return lookup_.IsProperty(); }
2486    bool IsField() const { return lookup_.IsField(); }
2487    bool IsConstant() const { return lookup_.IsConstant(); }
2488    bool IsAccessor() const { return lookup_.IsPropertyCallbacks(); }
2489    bool IsTransition() const { return lookup_.IsTransition(); }
2490
2491    bool IsConfigurable() const { return lookup_.IsConfigurable(); }
2492    bool IsReadOnly() const { return lookup_.IsReadOnly(); }
2493
2494   private:
2495    Handle<Object> GetAccessorsFromMap(Handle<Map> map) const {
2496      return handle(lookup_.GetValueFromMap(*map), isolate());
2497    }
2498    Handle<Object> GetConstantFromMap(Handle<Map> map) const {
2499      return handle(lookup_.GetConstantFromMap(*map), isolate());
2500    }
2501    Handle<HeapType> GetFieldTypeFromMap(Handle<Map> map) const {
2502      return handle(lookup_.GetFieldTypeFromMap(*map), isolate());
2503    }
2504    Handle<Map> GetFieldOwnerFromMap(Handle<Map> map) const {
2505      return handle(lookup_.GetFieldOwnerFromMap(*map));
2506    }
2507    int GetLocalFieldIndexFromMap(Handle<Map> map) const {
2508      return lookup_.GetLocalFieldIndexFromMap(*map);
2509    }
2510    Representation representation() const { return lookup_.representation(); }
2511
2512    Type* ToType(Handle<Map> map) { return builder_->ToType(map); }
2513    Zone* zone() { return builder_->zone(); }
2514    Isolate* isolate() const { return lookup_.isolate(); }
2515    CompilationInfo* top_info() { return builder_->top_info(); }
2516    CompilationInfo* current_info() { return builder_->current_info(); }
2517
2518    bool LoadResult(Handle<Map> map);
2519    void LoadFieldMaps(Handle<Map> map);
2520    bool LookupDescriptor();
2521    bool LookupInPrototypes();
2522    bool IsCompatible(PropertyAccessInfo* other);
2523
2524    void GeneralizeRepresentation(Representation r) {
2525      access_ = access_.WithRepresentation(
2526          access_.representation().generalize(r));
2527    }
2528
2529    LookupResult lookup_;
2530    HOptimizedGraphBuilder* builder_;
2531    PropertyAccessType access_type_;
2532    Type* type_;
2533    Handle<String> name_;
2534    Handle<JSObject> holder_;
2535    Handle<JSFunction> accessor_;
2536    Handle<JSObject> api_holder_;
2537    Handle<Object> constant_;
2538    SmallMapList field_maps_;
2539    HType field_type_;
2540    HObjectAccess access_;
2541  };
2542
2543  HInstruction* BuildMonomorphicAccess(PropertyAccessInfo* info,
2544                                       HValue* object,
2545                                       HValue* checked_object,
2546                                       HValue* value,
2547                                       BailoutId ast_id,
2548                                       BailoutId return_id,
2549                                       bool can_inline_accessor = true);
2550
2551  HInstruction* BuildNamedAccess(PropertyAccessType access,
2552                                 BailoutId ast_id,
2553                                 BailoutId reutrn_id,
2554                                 Expression* expr,
2555                                 HValue* object,
2556                                 Handle<String> name,
2557                                 HValue* value,
2558                                 bool is_uninitialized = false);
2559
2560  void HandlePolymorphicCallNamed(Call* expr,
2561                                  HValue* receiver,
2562                                  SmallMapList* types,
2563                                  Handle<String> name);
2564  void HandleLiteralCompareTypeof(CompareOperation* expr,
2565                                  Expression* sub_expr,
2566                                  Handle<String> check);
2567  void HandleLiteralCompareNil(CompareOperation* expr,
2568                               Expression* sub_expr,
2569                               NilValue nil);
2570
2571  enum PushBeforeSimulateBehavior {
2572    PUSH_BEFORE_SIMULATE,
2573    NO_PUSH_BEFORE_SIMULATE
2574  };
2575
2576  HControlInstruction* BuildCompareInstruction(
2577      Token::Value op,
2578      HValue* left,
2579      HValue* right,
2580      Type* left_type,
2581      Type* right_type,
2582      Type* combined_type,
2583      HSourcePosition left_position,
2584      HSourcePosition right_position,
2585      PushBeforeSimulateBehavior push_sim_result,
2586      BailoutId bailout_id);
2587
2588  HInstruction* BuildStringCharCodeAt(HValue* string,
2589                                      HValue* index);
2590
2591  HValue* BuildBinaryOperation(
2592      BinaryOperation* expr,
2593      HValue* left,
2594      HValue* right,
2595      PushBeforeSimulateBehavior push_sim_result);
2596  HInstruction* BuildIncrement(bool returns_original_input,
2597                               CountOperation* expr);
2598  HInstruction* BuildKeyedGeneric(PropertyAccessType access_type,
2599                                  Expression* expr,
2600                                  HValue* object,
2601                                  HValue* key,
2602                                  HValue* value);
2603
2604  HInstruction* TryBuildConsolidatedElementLoad(HValue* object,
2605                                                HValue* key,
2606                                                HValue* val,
2607                                                SmallMapList* maps);
2608
2609  LoadKeyedHoleMode BuildKeyedHoleMode(Handle<Map> map);
2610
2611  HInstruction* BuildMonomorphicElementAccess(HValue* object,
2612                                              HValue* key,
2613                                              HValue* val,
2614                                              HValue* dependency,
2615                                              Handle<Map> map,
2616                                              PropertyAccessType access_type,
2617                                              KeyedAccessStoreMode store_mode);
2618
2619  HValue* HandlePolymorphicElementAccess(Expression* expr,
2620                                         HValue* object,
2621                                         HValue* key,
2622                                         HValue* val,
2623                                         SmallMapList* maps,
2624                                         PropertyAccessType access_type,
2625                                         KeyedAccessStoreMode store_mode,
2626                                         bool* has_side_effects);
2627
2628  HValue* HandleKeyedElementAccess(HValue* obj, HValue* key, HValue* val,
2629                                   Expression* expr, BailoutId ast_id,
2630                                   BailoutId return_id,
2631                                   PropertyAccessType access_type,
2632                                   bool* has_side_effects);
2633
2634  HInstruction* BuildNamedGeneric(PropertyAccessType access,
2635                                  Expression* expr,
2636                                  HValue* object,
2637                                  Handle<String> name,
2638                                  HValue* value,
2639                                  bool is_uninitialized = false);
2640
2641  HCheckMaps* AddCheckMap(HValue* object, Handle<Map> map);
2642
2643  void BuildLoad(Property* property,
2644                 BailoutId ast_id);
2645  void PushLoad(Property* property,
2646                HValue* object,
2647                HValue* key);
2648
2649  void BuildStoreForEffect(Expression* expression,
2650                           Property* prop,
2651                           BailoutId ast_id,
2652                           BailoutId return_id,
2653                           HValue* object,
2654                           HValue* key,
2655                           HValue* value);
2656
2657  void BuildStore(Expression* expression,
2658                  Property* prop,
2659                  BailoutId ast_id,
2660                  BailoutId return_id,
2661                  bool is_uninitialized = false);
2662
2663  HInstruction* BuildLoadNamedField(PropertyAccessInfo* info,
2664                                    HValue* checked_object);
2665  HInstruction* BuildStoreNamedField(PropertyAccessInfo* info,
2666                                     HValue* checked_object,
2667                                     HValue* value);
2668
2669  HValue* BuildContextChainWalk(Variable* var);
2670
2671  HInstruction* BuildThisFunction();
2672
2673  HInstruction* BuildFastLiteral(Handle<JSObject> boilerplate_object,
2674                                 AllocationSiteUsageContext* site_context);
2675
2676  void BuildEmitObjectHeader(Handle<JSObject> boilerplate_object,
2677                             HInstruction* object);
2678
2679  void BuildInitElementsInObjectHeader(Handle<JSObject> boilerplate_object,
2680                                       HInstruction* object,
2681                                       HInstruction* object_elements);
2682
2683  void BuildEmitInObjectProperties(Handle<JSObject> boilerplate_object,
2684                                   HInstruction* object,
2685                                   AllocationSiteUsageContext* site_context,
2686                                   PretenureFlag pretenure_flag);
2687
2688  void BuildEmitElements(Handle<JSObject> boilerplate_object,
2689                         Handle<FixedArrayBase> elements,
2690                         HValue* object_elements,
2691                         AllocationSiteUsageContext* site_context);
2692
2693  void BuildEmitFixedDoubleArray(Handle<FixedArrayBase> elements,
2694                                 ElementsKind kind,
2695                                 HValue* object_elements);
2696
2697  void BuildEmitFixedArray(Handle<FixedArrayBase> elements,
2698                           ElementsKind kind,
2699                           HValue* object_elements,
2700                           AllocationSiteUsageContext* site_context);
2701
2702  void AddCheckPrototypeMaps(Handle<JSObject> holder,
2703                             Handle<Map> receiver_map);
2704
2705  HInstruction* NewPlainFunctionCall(HValue* fun,
2706                                     int argument_count,
2707                                     bool pass_argument_count);
2708
2709  HInstruction* NewArgumentAdaptorCall(HValue* fun, HValue* context,
2710                                       int argument_count,
2711                                       HValue* expected_param_count);
2712
2713  HInstruction* BuildCallConstantFunction(Handle<JSFunction> target,
2714                                          int argument_count);
2715
2716  // The translation state of the currently-being-translated function.
2717  FunctionState* function_state_;
2718
2719  // The base of the function state stack.
2720  FunctionState initial_function_state_;
2721
2722  // Expression context of the currently visited subexpression. NULL when
2723  // visiting statements.
2724  AstContext* ast_context_;
2725
2726  // A stack of breakable statements entered.
2727  BreakAndContinueScope* break_scope_;
2728
2729  int inlined_count_;
2730  ZoneList<Handle<Object> > globals_;
2731
2732  bool inline_bailout_;
2733
2734  HOsrBuilder* osr_;
2735
2736  friend class FunctionState;  // Pushes and pops the state stack.
2737  friend class AstContext;  // Pushes and pops the AST context stack.
2738  friend class KeyedLoadFastElementStub;
2739  friend class HOsrBuilder;
2740
2741  DISALLOW_COPY_AND_ASSIGN(HOptimizedGraphBuilder);
2742};
2743
2744
2745Zone* AstContext::zone() const { return owner_->zone(); }
2746
2747
2748class HStatistics FINAL: public Malloced {
2749 public:
2750  HStatistics()
2751      : times_(5),
2752        names_(5),
2753        sizes_(5),
2754        total_size_(0),
2755        source_size_(0) { }
2756
2757  void Initialize(CompilationInfo* info);
2758  void Print(const char* stats_name);
2759  void SaveTiming(const char* name, base::TimeDelta time, unsigned size);
2760
2761  void IncrementFullCodeGen(base::TimeDelta full_code_gen) {
2762    full_code_gen_ += full_code_gen;
2763  }
2764
2765  void IncrementCreateGraph(base::TimeDelta delta) { create_graph_ += delta; }
2766
2767  void IncrementOptimizeGraph(base::TimeDelta delta) {
2768    optimize_graph_ += delta;
2769  }
2770
2771  void IncrementGenerateCode(base::TimeDelta delta) { generate_code_ += delta; }
2772
2773  void IncrementSubtotals(base::TimeDelta create_graph,
2774                          base::TimeDelta optimize_graph,
2775                          base::TimeDelta generate_code) {
2776    IncrementCreateGraph(create_graph);
2777    IncrementOptimizeGraph(optimize_graph);
2778    IncrementGenerateCode(generate_code);
2779  }
2780
2781 private:
2782  List<base::TimeDelta> times_;
2783  List<const char*> names_;
2784  List<unsigned> sizes_;
2785  base::TimeDelta create_graph_;
2786  base::TimeDelta optimize_graph_;
2787  base::TimeDelta generate_code_;
2788  unsigned total_size_;
2789  base::TimeDelta full_code_gen_;
2790  double source_size_;
2791};
2792
2793
2794class HPhase : public CompilationPhase {
2795 public:
2796  HPhase(const char* name, HGraph* graph)
2797      : CompilationPhase(name, graph->info()),
2798        graph_(graph) { }
2799  ~HPhase();
2800
2801 protected:
2802  HGraph* graph() const { return graph_; }
2803
2804 private:
2805  HGraph* graph_;
2806
2807  DISALLOW_COPY_AND_ASSIGN(HPhase);
2808};
2809
2810
2811class HTracer FINAL : public Malloced {
2812 public:
2813  explicit HTracer(int isolate_id)
2814      : trace_(&string_allocator_), indent_(0) {
2815    if (FLAG_trace_hydrogen_file == NULL) {
2816      SNPrintF(filename_,
2817               "hydrogen-%d-%d.cfg",
2818               base::OS::GetCurrentProcessId(),
2819               isolate_id);
2820    } else {
2821      StrNCpy(filename_, FLAG_trace_hydrogen_file, filename_.length());
2822    }
2823    WriteChars(filename_.start(), "", 0, false);
2824  }
2825
2826  void TraceCompilation(CompilationInfo* info);
2827  void TraceHydrogen(const char* name, HGraph* graph);
2828  void TraceLithium(const char* name, LChunk* chunk);
2829  void TraceLiveRanges(const char* name, LAllocator* allocator);
2830
2831 private:
2832  class Tag FINAL BASE_EMBEDDED {
2833   public:
2834    Tag(HTracer* tracer, const char* name) {
2835      name_ = name;
2836      tracer_ = tracer;
2837      tracer->PrintIndent();
2838      tracer->trace_.Add("begin_%s\n", name);
2839      tracer->indent_++;
2840    }
2841
2842    ~Tag() {
2843      tracer_->indent_--;
2844      tracer_->PrintIndent();
2845      tracer_->trace_.Add("end_%s\n", name_);
2846      DCHECK(tracer_->indent_ >= 0);
2847      tracer_->FlushToFile();
2848    }
2849
2850   private:
2851    HTracer* tracer_;
2852    const char* name_;
2853  };
2854
2855  void TraceLiveRange(LiveRange* range, const char* type, Zone* zone);
2856  void Trace(const char* name, HGraph* graph, LChunk* chunk);
2857  void FlushToFile();
2858
2859  void PrintEmptyProperty(const char* name) {
2860    PrintIndent();
2861    trace_.Add("%s\n", name);
2862  }
2863
2864  void PrintStringProperty(const char* name, const char* value) {
2865    PrintIndent();
2866    trace_.Add("%s \"%s\"\n", name, value);
2867  }
2868
2869  void PrintLongProperty(const char* name, int64_t value) {
2870    PrintIndent();
2871    trace_.Add("%s %d000\n", name, static_cast<int>(value / 1000));
2872  }
2873
2874  void PrintBlockProperty(const char* name, int block_id) {
2875    PrintIndent();
2876    trace_.Add("%s \"B%d\"\n", name, block_id);
2877  }
2878
2879  void PrintIntProperty(const char* name, int value) {
2880    PrintIndent();
2881    trace_.Add("%s %d\n", name, value);
2882  }
2883
2884  void PrintIndent() {
2885    for (int i = 0; i < indent_; i++) {
2886      trace_.Add("  ");
2887    }
2888  }
2889
2890  EmbeddedVector<char, 64> filename_;
2891  HeapStringAllocator string_allocator_;
2892  StringStream trace_;
2893  int indent_;
2894};
2895
2896
2897class NoObservableSideEffectsScope FINAL {
2898 public:
2899  explicit NoObservableSideEffectsScope(HGraphBuilder* builder) :
2900      builder_(builder) {
2901    builder_->graph()->IncrementInNoSideEffectsScope();
2902  }
2903  ~NoObservableSideEffectsScope() {
2904    builder_->graph()->DecrementInNoSideEffectsScope();
2905  }
2906
2907 private:
2908  HGraphBuilder* builder_;
2909};
2910
2911
2912} }  // namespace v8::internal
2913
2914#endif  // V8_HYDROGEN_H_
2915