1// Copyright 2012 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifndef V8_HYDROGEN_H_
29#define V8_HYDROGEN_H_
30
31#include "v8.h"
32
33#include "allocation.h"
34#include "ast.h"
35#include "compiler.h"
36#include "hydrogen-instructions.h"
37#include "zone.h"
38#include "scopes.h"
39
40namespace v8 {
41namespace internal {
42
43// Forward declarations.
44class BitVector;
45class FunctionState;
46class HEnvironment;
47class HGraph;
48class HLoopInformation;
49class HOsrBuilder;
50class HTracer;
51class LAllocator;
52class LChunk;
53class LiveRange;
54
55
56class HBasicBlock: public ZoneObject {
57 public:
58  explicit HBasicBlock(HGraph* graph);
59  virtual ~HBasicBlock() { }
60
61  // Simple accessors.
62  int block_id() const { return block_id_; }
63  void set_block_id(int id) { block_id_ = id; }
64  HGraph* graph() const { return graph_; }
65  Isolate* isolate() const;
66  const ZoneList<HPhi*>* phis() const { return &phis_; }
67  HInstruction* first() const { return first_; }
68  HInstruction* last() const { return last_; }
69  void set_last(HInstruction* instr) { last_ = instr; }
70  HControlInstruction* end() const { return end_; }
71  HLoopInformation* loop_information() const { return loop_information_; }
72  HLoopInformation* current_loop() const {
73    return IsLoopHeader() ? loop_information()
74                          : (parent_loop_header() != NULL
75                            ? parent_loop_header()->loop_information() : NULL);
76  }
77  const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
78  bool HasPredecessor() const { return predecessors_.length() > 0; }
79  const ZoneList<HBasicBlock*>* dominated_blocks() const {
80    return &dominated_blocks_;
81  }
82  const ZoneList<int>* deleted_phis() const {
83    return &deleted_phis_;
84  }
85  void RecordDeletedPhi(int merge_index) {
86    deleted_phis_.Add(merge_index, zone());
87  }
88  HBasicBlock* dominator() const { return dominator_; }
89  HEnvironment* last_environment() const { return last_environment_; }
90  int argument_count() const { return argument_count_; }
91  void set_argument_count(int count) { argument_count_ = count; }
92  int first_instruction_index() const { return first_instruction_index_; }
93  void set_first_instruction_index(int index) {
94    first_instruction_index_ = index;
95  }
96  int last_instruction_index() const { return last_instruction_index_; }
97  void set_last_instruction_index(int index) {
98    last_instruction_index_ = index;
99  }
100  bool is_osr_entry() { return is_osr_entry_; }
101  void set_osr_entry() { is_osr_entry_ = true; }
102
103  void AttachLoopInformation();
104  void DetachLoopInformation();
105  bool IsLoopHeader() const { return loop_information() != NULL; }
106  bool IsStartBlock() const { return block_id() == 0; }
107  void PostProcessLoopHeader(IterationStatement* stmt);
108
109  bool IsFinished() const { return end_ != NULL; }
110  void AddPhi(HPhi* phi);
111  void RemovePhi(HPhi* phi);
112  void AddInstruction(HInstruction* instr);
113  bool Dominates(HBasicBlock* other) const;
114  int LoopNestingDepth() const;
115
116  void SetInitialEnvironment(HEnvironment* env);
117  void ClearEnvironment() {
118    ASSERT(IsFinished());
119    ASSERT(end()->SuccessorCount() == 0);
120    last_environment_ = NULL;
121  }
122  bool HasEnvironment() const { return last_environment_ != NULL; }
123  void UpdateEnvironment(HEnvironment* env);
124  HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
125
126  void set_parent_loop_header(HBasicBlock* block) {
127    ASSERT(parent_loop_header_ == NULL);
128    parent_loop_header_ = block;
129  }
130
131  bool HasParentLoopHeader() const { return parent_loop_header_ != NULL; }
132
133  void SetJoinId(BailoutId ast_id);
134
135  void Finish(HControlInstruction* last);
136  void FinishExit(HControlInstruction* instruction);
137  void Goto(HBasicBlock* block,
138            FunctionState* state = NULL,
139            bool add_simulate = true);
140  void GotoNoSimulate(HBasicBlock* block) {
141    Goto(block, NULL, false);
142  }
143
144  int PredecessorIndexOf(HBasicBlock* predecessor) const;
145  HPhi* AddNewPhi(int merged_index);
146  HSimulate* AddNewSimulate(BailoutId ast_id,
147                            RemovableSimulate removable = FIXED_SIMULATE) {
148    HSimulate* instr = CreateSimulate(ast_id, removable);
149    AddInstruction(instr);
150    return instr;
151  }
152  void AssignCommonDominator(HBasicBlock* other);
153  void AssignLoopSuccessorDominators();
154
155  // Add the inlined function exit sequence, adding an HLeaveInlined
156  // instruction and updating the bailout environment.
157  void AddLeaveInlined(HValue* return_value, FunctionState* state);
158
159  // If a target block is tagged as an inline function return, all
160  // predecessors should contain the inlined exit sequence:
161  //
162  // LeaveInlined
163  // Simulate (caller's environment)
164  // Goto (target block)
165  bool IsInlineReturnTarget() const { return is_inline_return_target_; }
166  void MarkAsInlineReturnTarget(HBasicBlock* inlined_entry_block) {
167    is_inline_return_target_ = true;
168    inlined_entry_block_ = inlined_entry_block;
169  }
170  HBasicBlock* inlined_entry_block() { return inlined_entry_block_; }
171
172  bool IsDeoptimizing() const { return is_deoptimizing_; }
173  void MarkAsDeoptimizing() { is_deoptimizing_ = true; }
174
175  bool IsLoopSuccessorDominator() const {
176    return dominates_loop_successors_;
177  }
178  void MarkAsLoopSuccessorDominator() {
179    dominates_loop_successors_ = true;
180  }
181
182  inline Zone* zone() const;
183
184#ifdef DEBUG
185  void Verify();
186#endif
187
188 private:
189  friend class HGraphBuilder;
190
191  void RegisterPredecessor(HBasicBlock* pred);
192  void AddDominatedBlock(HBasicBlock* block);
193
194  HSimulate* CreateSimulate(BailoutId ast_id, RemovableSimulate removable);
195
196  int block_id_;
197  HGraph* graph_;
198  ZoneList<HPhi*> phis_;
199  HInstruction* first_;
200  HInstruction* last_;
201  HControlInstruction* end_;
202  HLoopInformation* loop_information_;
203  ZoneList<HBasicBlock*> predecessors_;
204  HBasicBlock* dominator_;
205  ZoneList<HBasicBlock*> dominated_blocks_;
206  HEnvironment* last_environment_;
207  // Outgoing parameter count at block exit, set during lithium translation.
208  int argument_count_;
209  // Instruction indices into the lithium code stream.
210  int first_instruction_index_;
211  int last_instruction_index_;
212  ZoneList<int> deleted_phis_;
213  HBasicBlock* parent_loop_header_;
214  // For blocks marked as inline return target: the block with HEnterInlined.
215  HBasicBlock* inlined_entry_block_;
216  bool is_inline_return_target_ : 1;
217  bool is_deoptimizing_ : 1;
218  bool dominates_loop_successors_ : 1;
219  bool is_osr_entry_ : 1;
220};
221
222
223class HPredecessorIterator BASE_EMBEDDED {
224 public:
225  explicit HPredecessorIterator(HBasicBlock* block)
226      : predecessor_list_(block->predecessors()), current_(0) { }
227
228  bool Done() { return current_ >= predecessor_list_->length(); }
229  HBasicBlock* Current() { return predecessor_list_->at(current_); }
230  void Advance() { current_++; }
231
232 private:
233  const ZoneList<HBasicBlock*>* predecessor_list_;
234  int current_;
235};
236
237
238class HInstructionIterator BASE_EMBEDDED {
239 public:
240  explicit HInstructionIterator(HBasicBlock* block)
241      : instr_(block->first()) {
242    next_ = Done() ? NULL : instr_->next();
243  }
244
245  inline bool Done() const { return instr_ == NULL; }
246  inline HInstruction* Current() { return instr_; }
247  inline void Advance() {
248    instr_ = next_;
249    next_ = Done() ? NULL : instr_->next();
250  }
251
252 private:
253  HInstruction* instr_;
254  HInstruction* next_;
255};
256
257
258class HLoopInformation: public ZoneObject {
259 public:
260  HLoopInformation(HBasicBlock* loop_header, Zone* zone)
261      : back_edges_(4, zone),
262        loop_header_(loop_header),
263        blocks_(8, zone),
264        stack_check_(NULL) {
265    blocks_.Add(loop_header, zone);
266  }
267  virtual ~HLoopInformation() {}
268
269  const ZoneList<HBasicBlock*>* back_edges() const { return &back_edges_; }
270  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
271  HBasicBlock* loop_header() const { return loop_header_; }
272  HBasicBlock* GetLastBackEdge() const;
273  void RegisterBackEdge(HBasicBlock* block);
274
275  HStackCheck* stack_check() const { return stack_check_; }
276  void set_stack_check(HStackCheck* stack_check) {
277    stack_check_ = stack_check;
278  }
279
280  bool IsNestedInThisLoop(HLoopInformation* other) {
281    while (other != NULL) {
282      if (other == this) {
283        return true;
284      }
285      other = other->parent_loop();
286    }
287    return false;
288  }
289  HLoopInformation* parent_loop() {
290    HBasicBlock* parent_header = loop_header()->parent_loop_header();
291    return parent_header != NULL ? parent_header->loop_information() : NULL;
292  }
293
294 private:
295  void AddBlock(HBasicBlock* block);
296
297  ZoneList<HBasicBlock*> back_edges_;
298  HBasicBlock* loop_header_;
299  ZoneList<HBasicBlock*> blocks_;
300  HStackCheck* stack_check_;
301};
302
303
304class BoundsCheckTable;
305class InductionVariableBlocksTable;
306class HGraph: public ZoneObject {
307 public:
308  explicit HGraph(CompilationInfo* info);
309
310  Isolate* isolate() const { return isolate_; }
311  Zone* zone() const { return zone_; }
312  CompilationInfo* info() const { return info_; }
313
314  const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
315  const ZoneList<HPhi*>* phi_list() const { return phi_list_; }
316  HBasicBlock* entry_block() const { return entry_block_; }
317  HEnvironment* start_environment() const { return start_environment_; }
318
319  void FinalizeUniqueValueIds();
320  bool ProcessArgumentsObject();
321  void OrderBlocks();
322  void AssignDominators();
323  void SetupInformativeDefinitions();
324  void RestoreActualValues();
325
326  // Returns false if there are phi-uses of the arguments-object
327  // which are not supported by the optimizing compiler.
328  bool CheckArgumentsPhiUses();
329
330  // Returns false if there are phi-uses of an uninitialized const
331  // which are not supported by the optimizing compiler.
332  bool CheckConstPhiUses();
333
334  void CollectPhis();
335
336  void set_undefined_constant(HConstant* constant) {
337    undefined_constant_.set(constant);
338  }
339  HConstant* GetConstantUndefined() const { return undefined_constant_.get(); }
340  HConstant* GetConstant0();
341  HConstant* GetConstant1();
342  HConstant* GetConstantMinus1();
343  HConstant* GetConstantTrue();
344  HConstant* GetConstantFalse();
345  HConstant* GetConstantHole();
346  HConstant* GetConstantNull();
347  HConstant* GetInvalidContext();
348
349  bool IsStandardConstant(HConstant* constant);
350
351  HBasicBlock* CreateBasicBlock();
352  HArgumentsObject* GetArgumentsObject() const {
353    return arguments_object_.get();
354  }
355
356  void SetArgumentsObject(HArgumentsObject* object) {
357    arguments_object_.set(object);
358  }
359
360  int GetMaximumValueID() const { return values_.length(); }
361  int GetNextBlockID() { return next_block_id_++; }
362  int GetNextValueID(HValue* value) {
363    values_.Add(value, zone());
364    return values_.length() - 1;
365  }
366  HValue* LookupValue(int id) const {
367    if (id >= 0 && id < values_.length()) return values_[id];
368    return NULL;
369  }
370
371  bool Optimize(BailoutReason* bailout_reason);
372
373#ifdef DEBUG
374  void Verify(bool do_full_verify) const;
375#endif
376
377  bool has_osr() {
378    return osr_ != NULL;
379  }
380
381  void set_osr(HOsrBuilder* osr) {
382    osr_ = osr;
383  }
384
385  HOsrBuilder* osr() {
386    return osr_;
387  }
388
389  int update_type_change_checksum(int delta) {
390    type_change_checksum_ += delta;
391    return type_change_checksum_;
392  }
393
394  void update_maximum_environment_size(int environment_size) {
395    if (environment_size > maximum_environment_size_) {
396      maximum_environment_size_ = environment_size;
397    }
398  }
399  int maximum_environment_size() { return maximum_environment_size_; }
400
401  bool use_optimistic_licm() {
402    return use_optimistic_licm_;
403  }
404
405  void set_use_optimistic_licm(bool value) {
406    use_optimistic_licm_ = value;
407  }
408
409  bool has_soft_deoptimize() {
410    return has_soft_deoptimize_;
411  }
412
413  void set_has_soft_deoptimize(bool value) {
414    has_soft_deoptimize_ = value;
415  }
416
417  void MarkRecursive() {
418    is_recursive_ = true;
419  }
420
421  bool is_recursive() const {
422    return is_recursive_;
423  }
424
425  void MarkDependsOnEmptyArrayProtoElements() {
426    // Add map dependency if not already added.
427    if (depends_on_empty_array_proto_elements_) return;
428    isolate()->initial_object_prototype()->map()->AddDependentCompilationInfo(
429        DependentCode::kElementsCantBeAddedGroup, info());
430    isolate()->initial_array_prototype()->map()->AddDependentCompilationInfo(
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    ASSERT(uint32_instructions_ == NULL || !uint32_instructions_->is_empty());
441    return uint32_instructions_ != NULL;
442  }
443
444  ZoneList<HInstruction*>* uint32_instructions() {
445    ASSERT(uint32_instructions_ == NULL || !uint32_instructions_->is_empty());
446    return uint32_instructions_;
447  }
448
449  void RecordUint32Instruction(HInstruction* instr) {
450    ASSERT(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 private:
462  HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
463                         int32_t integer_value);
464
465  template<class Phase>
466  void Run() {
467    Phase phase(this);
468    phase.Run();
469  }
470
471  void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
472  void SetupInformativeDefinitionsInBlock(HBasicBlock* block);
473  void SetupInformativeDefinitionsRecursively(HBasicBlock* block);
474  void EliminateRedundantBoundsChecksUsingInductionVariables();
475
476  Isolate* isolate_;
477  int next_block_id_;
478  HBasicBlock* entry_block_;
479  HEnvironment* start_environment_;
480  ZoneList<HBasicBlock*> blocks_;
481  ZoneList<HValue*> values_;
482  ZoneList<HPhi*>* phi_list_;
483  ZoneList<HInstruction*>* uint32_instructions_;
484  SetOncePointer<HConstant> undefined_constant_;
485  SetOncePointer<HConstant> constant_0_;
486  SetOncePointer<HConstant> constant_1_;
487  SetOncePointer<HConstant> constant_minus1_;
488  SetOncePointer<HConstant> constant_true_;
489  SetOncePointer<HConstant> constant_false_;
490  SetOncePointer<HConstant> constant_the_hole_;
491  SetOncePointer<HConstant> constant_null_;
492  SetOncePointer<HConstant> constant_invalid_context_;
493  SetOncePointer<HArgumentsObject> arguments_object_;
494
495  HOsrBuilder* osr_;
496
497  CompilationInfo* info_;
498  Zone* zone_;
499
500  bool is_recursive_;
501  bool use_optimistic_licm_;
502  bool has_soft_deoptimize_;
503  bool depends_on_empty_array_proto_elements_;
504  int type_change_checksum_;
505  int maximum_environment_size_;
506  int no_side_effects_scope_count_;
507
508  DISALLOW_COPY_AND_ASSIGN(HGraph);
509};
510
511
512Zone* HBasicBlock::zone() const { return graph_->zone(); }
513
514
515// Type of stack frame an environment might refer to.
516enum FrameType {
517  JS_FUNCTION,
518  JS_CONSTRUCT,
519  JS_GETTER,
520  JS_SETTER,
521  ARGUMENTS_ADAPTOR,
522  STUB
523};
524
525
526class HEnvironment: public ZoneObject {
527 public:
528  HEnvironment(HEnvironment* outer,
529               Scope* scope,
530               Handle<JSFunction> closure,
531               Zone* zone);
532
533  HEnvironment(Zone* zone, int parameter_count);
534
535  HEnvironment* arguments_environment() {
536    return outer()->frame_type() == ARGUMENTS_ADAPTOR ? outer() : this;
537  }
538
539  // Simple accessors.
540  Handle<JSFunction> closure() const { return closure_; }
541  const ZoneList<HValue*>* values() const { return &values_; }
542  const GrowableBitVector* assigned_variables() const {
543    return &assigned_variables_;
544  }
545  FrameType frame_type() const { return frame_type_; }
546  int parameter_count() const { return parameter_count_; }
547  int specials_count() const { return specials_count_; }
548  int local_count() const { return local_count_; }
549  HEnvironment* outer() const { return outer_; }
550  int pop_count() const { return pop_count_; }
551  int push_count() const { return push_count_; }
552
553  BailoutId ast_id() const { return ast_id_; }
554  void set_ast_id(BailoutId id) { ast_id_ = id; }
555
556  HEnterInlined* entry() const { return entry_; }
557  void set_entry(HEnterInlined* entry) { entry_ = entry; }
558
559  int length() const { return values_.length(); }
560  bool is_special_index(int i) const {
561    return i >= parameter_count() && i < parameter_count() + specials_count();
562  }
563
564  int first_expression_index() const {
565    return parameter_count() + specials_count() + local_count();
566  }
567
568  int first_local_index() const {
569    return parameter_count() + specials_count();
570  }
571
572  void Bind(Variable* variable, HValue* value) {
573    Bind(IndexFor(variable), value);
574  }
575
576  void Bind(int index, HValue* value);
577
578  void BindContext(HValue* value) {
579    Bind(parameter_count(), value);
580  }
581
582  HValue* Lookup(Variable* variable) const {
583    return Lookup(IndexFor(variable));
584  }
585
586  HValue* Lookup(int index) const {
587    HValue* result = values_[index];
588    ASSERT(result != NULL);
589    return result;
590  }
591
592  HValue* context() const {
593    // Return first special.
594    return Lookup(parameter_count());
595  }
596
597  void Push(HValue* value) {
598    ASSERT(value != NULL);
599    ++push_count_;
600    values_.Add(value, zone());
601  }
602
603  HValue* Pop() {
604    ASSERT(!ExpressionStackIsEmpty());
605    if (push_count_ > 0) {
606      --push_count_;
607    } else {
608      ++pop_count_;
609    }
610    return values_.RemoveLast();
611  }
612
613  void Drop(int count);
614
615  HValue* Top() const { return ExpressionStackAt(0); }
616
617  bool ExpressionStackIsEmpty() const;
618
619  HValue* ExpressionStackAt(int index_from_top) const {
620    int index = length() - index_from_top - 1;
621    ASSERT(HasExpressionAt(index));
622    return values_[index];
623  }
624
625  void SetExpressionStackAt(int index_from_top, HValue* value);
626
627  HEnvironment* Copy() const;
628  HEnvironment* CopyWithoutHistory() const;
629  HEnvironment* CopyAsLoopHeader(HBasicBlock* block) const;
630
631  // Create an "inlined version" of this environment, where the original
632  // environment is the outer environment but the top expression stack
633  // elements are moved to an inner environment as parameters.
634  HEnvironment* CopyForInlining(Handle<JSFunction> target,
635                                int arguments,
636                                FunctionLiteral* function,
637                                HConstant* undefined,
638                                InliningKind inlining_kind,
639                                bool undefined_receiver) const;
640
641  static bool UseUndefinedReceiver(Handle<JSFunction> closure,
642                                   FunctionLiteral* function,
643                                   CallKind call_kind,
644                                   InliningKind inlining_kind) {
645    return (closure->shared()->native() || !function->is_classic_mode()) &&
646        call_kind == CALL_AS_FUNCTION && inlining_kind != CONSTRUCT_CALL_RETURN;
647  }
648
649  HEnvironment* DiscardInlined(bool drop_extra) {
650    HEnvironment* outer = outer_;
651    while (outer->frame_type() != JS_FUNCTION) outer = outer->outer_;
652    if (drop_extra) outer->Drop(1);
653    return outer;
654  }
655
656  void AddIncomingEdge(HBasicBlock* block, HEnvironment* other);
657
658  void ClearHistory() {
659    pop_count_ = 0;
660    push_count_ = 0;
661    assigned_variables_.Clear();
662  }
663
664  void SetValueAt(int index, HValue* value) {
665    ASSERT(index < length());
666    values_[index] = value;
667  }
668
669  // Map a variable to an environment index.  Parameter indices are shifted
670  // by 1 (receiver is parameter index -1 but environment index 0).
671  // Stack-allocated local indices are shifted by the number of parameters.
672  int IndexFor(Variable* variable) const {
673    ASSERT(variable->IsStackAllocated());
674    int shift = variable->IsParameter()
675        ? 1
676        : parameter_count_ + specials_count_;
677    return variable->index() + shift;
678  }
679
680  bool is_local_index(int i) const {
681    return i >= first_local_index() &&
682           i < first_expression_index();
683  }
684
685  void PrintTo(StringStream* stream);
686  void PrintToStd();
687
688  Zone* zone() const { return zone_; }
689
690 private:
691  HEnvironment(const HEnvironment* other, Zone* zone);
692
693  HEnvironment(HEnvironment* outer,
694               Handle<JSFunction> closure,
695               FrameType frame_type,
696               int arguments,
697               Zone* zone);
698
699  // Create an artificial stub environment (e.g. for argument adaptor or
700  // constructor stub).
701  HEnvironment* CreateStubEnvironment(HEnvironment* outer,
702                                      Handle<JSFunction> target,
703                                      FrameType frame_type,
704                                      int arguments) const;
705
706  // True if index is included in the expression stack part of the environment.
707  bool HasExpressionAt(int index) const;
708
709  void Initialize(int parameter_count, int local_count, int stack_height);
710  void Initialize(const HEnvironment* other);
711
712  Handle<JSFunction> closure_;
713  // Value array [parameters] [specials] [locals] [temporaries].
714  ZoneList<HValue*> values_;
715  GrowableBitVector assigned_variables_;
716  FrameType frame_type_;
717  int parameter_count_;
718  int specials_count_;
719  int local_count_;
720  HEnvironment* outer_;
721  HEnterInlined* entry_;
722  int pop_count_;
723  int push_count_;
724  BailoutId ast_id_;
725  Zone* zone_;
726};
727
728
729class HOptimizedGraphBuilder;
730
731enum ArgumentsAllowedFlag {
732  ARGUMENTS_NOT_ALLOWED,
733  ARGUMENTS_ALLOWED
734};
735
736
737class HIfContinuation;
738
739// This class is not BASE_EMBEDDED because our inlining implementation uses
740// new and delete.
741class AstContext {
742 public:
743  bool IsEffect() const { return kind_ == Expression::kEffect; }
744  bool IsValue() const { return kind_ == Expression::kValue; }
745  bool IsTest() const { return kind_ == Expression::kTest; }
746
747  // 'Fill' this context with a hydrogen value.  The value is assumed to
748  // have already been inserted in the instruction stream (or not need to
749  // be, e.g., HPhi).  Call this function in tail position in the Visit
750  // functions for expressions.
751  virtual void ReturnValue(HValue* value) = 0;
752
753  // Add a hydrogen instruction to the instruction stream (recording an
754  // environment simulation if necessary) and then fill this context with
755  // the instruction as value.
756  virtual void ReturnInstruction(HInstruction* instr, BailoutId ast_id) = 0;
757
758  // Finishes the current basic block and materialize a boolean for
759  // value context, nothing for effect, generate a branch for test context.
760  // Call this function in tail position in the Visit functions for
761  // expressions.
762  virtual void ReturnControl(HControlInstruction* instr, BailoutId ast_id) = 0;
763
764  // Finishes the current basic block and materialize a boolean for
765  // value context, nothing for effect, generate a branch for test context.
766  // Call this function in tail position in the Visit functions for
767  // expressions that use an IfBuilder.
768  virtual void ReturnContinuation(HIfContinuation* continuation,
769                                  BailoutId ast_id) = 0;
770
771  void set_for_typeof(bool for_typeof) { for_typeof_ = for_typeof; }
772  bool is_for_typeof() { return for_typeof_; }
773
774 protected:
775  AstContext(HOptimizedGraphBuilder* owner, Expression::Context kind);
776  virtual ~AstContext();
777
778  HOptimizedGraphBuilder* owner() const { return owner_; }
779
780  inline Zone* zone() const;
781
782  // We want to be able to assert, in a context-specific way, that the stack
783  // height makes sense when the context is filled.
784#ifdef DEBUG
785  int original_length_;
786#endif
787
788 private:
789  HOptimizedGraphBuilder* owner_;
790  Expression::Context kind_;
791  AstContext* outer_;
792  bool for_typeof_;
793};
794
795
796class EffectContext: public AstContext {
797 public:
798  explicit EffectContext(HOptimizedGraphBuilder* owner)
799      : AstContext(owner, Expression::kEffect) {
800  }
801  virtual ~EffectContext();
802
803  virtual void ReturnValue(HValue* value);
804  virtual void ReturnInstruction(HInstruction* instr, BailoutId ast_id);
805  virtual void ReturnControl(HControlInstruction* instr, BailoutId ast_id);
806  virtual void ReturnContinuation(HIfContinuation* continuation,
807                                  BailoutId ast_id);
808};
809
810
811class ValueContext: public AstContext {
812 public:
813  ValueContext(HOptimizedGraphBuilder* owner, ArgumentsAllowedFlag flag)
814      : AstContext(owner, Expression::kValue), flag_(flag) {
815  }
816  virtual ~ValueContext();
817
818  virtual void ReturnValue(HValue* value);
819  virtual void ReturnInstruction(HInstruction* instr, BailoutId ast_id);
820  virtual void ReturnControl(HControlInstruction* instr, BailoutId ast_id);
821  virtual void ReturnContinuation(HIfContinuation* continuation,
822                                  BailoutId ast_id);
823
824  bool arguments_allowed() { return flag_ == ARGUMENTS_ALLOWED; }
825
826 private:
827  ArgumentsAllowedFlag flag_;
828};
829
830
831class TestContext: public AstContext {
832 public:
833  TestContext(HOptimizedGraphBuilder* owner,
834              Expression* condition,
835              HBasicBlock* if_true,
836              HBasicBlock* if_false)
837      : AstContext(owner, Expression::kTest),
838        condition_(condition),
839        if_true_(if_true),
840        if_false_(if_false) {
841  }
842
843  virtual void ReturnValue(HValue* value);
844  virtual void ReturnInstruction(HInstruction* instr, BailoutId ast_id);
845  virtual void ReturnControl(HControlInstruction* instr, BailoutId ast_id);
846  virtual void ReturnContinuation(HIfContinuation* continuation,
847                                  BailoutId ast_id);
848
849  static TestContext* cast(AstContext* context) {
850    ASSERT(context->IsTest());
851    return reinterpret_cast<TestContext*>(context);
852  }
853
854  Expression* condition() const { return condition_; }
855  HBasicBlock* if_true() const { return if_true_; }
856  HBasicBlock* if_false() const { return if_false_; }
857
858 private:
859  // Build the shared core part of the translation unpacking a value into
860  // control flow.
861  void BuildBranch(HValue* value);
862
863  Expression* condition_;
864  HBasicBlock* if_true_;
865  HBasicBlock* if_false_;
866};
867
868
869class FunctionState {
870 public:
871  FunctionState(HOptimizedGraphBuilder* owner,
872                CompilationInfo* info,
873                InliningKind inlining_kind);
874  ~FunctionState();
875
876  CompilationInfo* compilation_info() { return compilation_info_; }
877  AstContext* call_context() { return call_context_; }
878  InliningKind inlining_kind() const { return inlining_kind_; }
879  HBasicBlock* function_return() { return function_return_; }
880  TestContext* test_context() { return test_context_; }
881  void ClearInlinedTestContext() {
882    delete test_context_;
883    test_context_ = NULL;
884  }
885
886  FunctionState* outer() { return outer_; }
887
888  HEnterInlined* entry() { return entry_; }
889  void set_entry(HEnterInlined* entry) { entry_ = entry; }
890
891  HArgumentsObject* arguments_object() { return arguments_object_; }
892  void set_arguments_object(HArgumentsObject* arguments_object) {
893    arguments_object_ = arguments_object;
894  }
895
896  HArgumentsElements* arguments_elements() { return arguments_elements_; }
897  void set_arguments_elements(HArgumentsElements* arguments_elements) {
898    arguments_elements_ = arguments_elements;
899  }
900
901  bool arguments_pushed() { return arguments_elements() != NULL; }
902
903 private:
904  HOptimizedGraphBuilder* owner_;
905
906  CompilationInfo* compilation_info_;
907
908  // During function inlining, expression context of the call being
909  // inlined. NULL when not inlining.
910  AstContext* call_context_;
911
912  // The kind of call which is currently being inlined.
913  InliningKind inlining_kind_;
914
915  // When inlining in an effect or value context, this is the return block.
916  // It is NULL otherwise.  When inlining in a test context, there are a
917  // pair of return blocks in the context.  When not inlining, there is no
918  // local return point.
919  HBasicBlock* function_return_;
920
921  // When inlining a call in a test context, a context containing a pair of
922  // return blocks.  NULL in all other cases.
923  TestContext* test_context_;
924
925  // When inlining HEnterInlined instruction corresponding to the function
926  // entry.
927  HEnterInlined* entry_;
928
929  HArgumentsObject* arguments_object_;
930  HArgumentsElements* arguments_elements_;
931
932  FunctionState* outer_;
933};
934
935
936class HIfContinuation {
937 public:
938  HIfContinuation() { continuation_captured_ = false; }
939  ~HIfContinuation() { ASSERT(!continuation_captured_); }
940
941  void Capture(HBasicBlock* true_branch,
942               HBasicBlock* false_branch,
943               int position) {
944    ASSERT(!continuation_captured_);
945    true_branch_ = true_branch;
946    false_branch_ = false_branch;
947    position_ = position;
948    continuation_captured_ = true;
949  }
950
951  void Continue(HBasicBlock** true_branch,
952                HBasicBlock** false_branch,
953                int* position) {
954    ASSERT(continuation_captured_);
955    *true_branch = true_branch_;
956    *false_branch = false_branch_;
957    if (position != NULL) *position = position_;
958    continuation_captured_ = false;
959  }
960
961  bool IsTrueReachable() { return true_branch_ != NULL; }
962  bool IsFalseReachable() { return false_branch_ != NULL; }
963  bool TrueAndFalseReachable() {
964    return IsTrueReachable() || IsFalseReachable();
965  }
966
967  bool continuation_captured_;
968  HBasicBlock* true_branch_;
969  HBasicBlock* false_branch_;
970  int position_;
971};
972
973
974class HGraphBuilder {
975 public:
976  explicit HGraphBuilder(CompilationInfo* info)
977      : info_(info),
978        graph_(NULL),
979        current_block_(NULL) {}
980  virtual ~HGraphBuilder() {}
981
982  HBasicBlock* current_block() const { return current_block_; }
983  void set_current_block(HBasicBlock* block) { current_block_ = block; }
984  HEnvironment* environment() const {
985    return current_block()->last_environment();
986  }
987  Zone* zone() const { return info_->zone(); }
988  HGraph* graph() const { return graph_; }
989  Isolate* isolate() const { return graph_->isolate(); }
990  CompilationInfo* top_info() { return info_; }
991
992  HGraph* CreateGraph();
993
994  // Bailout environment manipulation.
995  void Push(HValue* value) { environment()->Push(value); }
996  HValue* Pop() { return environment()->Pop(); }
997
998  virtual HValue* context() = 0;
999
1000  // Adding instructions.
1001  HInstruction* AddInstruction(HInstruction* instr);
1002
1003  template<class I>
1004  HInstruction* NewUncasted() { return I::New(zone(), context()); }
1005
1006  template<class I>
1007  I* New() { return I::cast(NewUncasted<I>()); }
1008
1009  template<class I>
1010  HInstruction* AddUncasted() { return AddInstruction(NewUncasted<I>());}
1011
1012  template<class I>
1013  I* Add() { return I::cast(AddUncasted<I>());}
1014
1015  template<class I, class P1>
1016  HInstruction* NewUncasted(P1 p1) {
1017    return I::New(zone(), context(), p1);
1018  }
1019
1020  template<class I, class P1>
1021  I* New(P1 p1) { return I::cast(NewUncasted<I>(p1)); }
1022
1023  template<class I, class P1>
1024  HInstruction* AddUncasted(P1 p1) {
1025    HInstruction* result = AddInstruction(NewUncasted<I>(p1));
1026    // Specializations must have their parameters properly casted
1027    // to avoid landing here.
1028    ASSERT(!result->IsReturn() && !result->IsSimulate() &&
1029           !result->IsDeoptimize());
1030    return result;
1031  }
1032
1033  template<class I, class P1>
1034  I* Add(P1 p1) {
1035    return I::cast(AddUncasted<I>(p1));
1036  }
1037
1038  template<class I, class P1, class P2>
1039  HInstruction* NewUncasted(P1 p1, P2 p2) {
1040    return I::New(zone(), context(), p1, p2);
1041  }
1042
1043  template<class I, class P1, class P2>
1044  I* New(P1 p1, P2 p2) {
1045    return I::cast(NewUncasted<I>(p1, p2));
1046  }
1047
1048  template<class I, class P1, class P2>
1049  HInstruction* AddUncasted(P1 p1, P2 p2) {
1050    HInstruction* result = AddInstruction(NewUncasted<I>(p1, p2));
1051    // Specializations must have their parameters properly casted
1052    // to avoid landing here.
1053    ASSERT(!result->IsSimulate());
1054    return result;
1055  }
1056
1057  template<class I, class P1, class P2>
1058  I* Add(P1 p1, P2 p2) {
1059    return static_cast<I*>(AddUncasted<I>(p1, p2));
1060  }
1061
1062  template<class I, class P1, class P2, class P3>
1063  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3) {
1064    return I::New(zone(), context(), p1, p2, p3);
1065  }
1066
1067  template<class I, class P1, class P2, class P3>
1068  I* New(P1 p1, P2 p2, P3 p3) {
1069    return I::cast(NewUncasted<I>(p1, p2, p3));
1070  }
1071
1072  template<class I, class P1, class P2, class P3>
1073  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3) {
1074    return AddInstruction(NewUncasted<I>(p1, p2, p3));
1075  }
1076
1077  template<class I, class P1, class P2, class P3>
1078  I* Add(P1 p1, P2 p2, P3 p3) {
1079    return I::cast(AddUncasted<I>(p1, p2, p3));
1080  }
1081
1082  template<class I, class P1, class P2, class P3, class P4>
1083  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4) {
1084    return I::New(zone(), context(), p1, p2, p3, p4);
1085  }
1086
1087  template<class I, class P1, class P2, class P3, class P4>
1088  I* New(P1 p1, P2 p2, P3 p3, P4 p4) {
1089    return I::cast(NewUncasted<I>(p1, p2, p3, p4));
1090  }
1091
1092  template<class I, class P1, class P2, class P3, class P4>
1093  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4) {
1094    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4));
1095  }
1096
1097  template<class I, class P1, class P2, class P3, class P4>
1098  I* Add(P1 p1, P2 p2, P3 p3, P4 p4) {
1099    return I::cast(AddUncasted<I>(p1, p2, p3, p4));
1100  }
1101
1102  template<class I, class P1, class P2, class P3, class P4, class P5>
1103  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1104    return I::New(zone(), context(), p1, p2, p3, p4, p5);
1105  }
1106
1107  template<class I, class P1, class P2, class P3, class P4, class P5>
1108  I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1109    return I::cast(NewUncasted<I>(p1, p2, p3, p4, p5));
1110  }
1111
1112  template<class I, class P1, class P2, class P3, class P4, class P5>
1113  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1114    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5));
1115  }
1116
1117  template<class I, class P1, class P2, class P3, class P4, class P5>
1118  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5) {
1119    return I::cast(AddUncasted<I>(p1, p2, p3, p4, p5));
1120  }
1121
1122  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1123  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1124    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6);
1125  }
1126
1127  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1128  I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1129    return I::cast(NewUncasted<I>(p1, p2, p3, p4, p5, p6));
1130  }
1131
1132  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1133  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1134    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6));
1135  }
1136
1137  template<class I, class P1, class P2, class P3, class P4, class P5, class P6>
1138  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6) {
1139    return I::cast(AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6)));
1140  }
1141
1142  template<class I, class P1, class P2, class P3, class P4,
1143      class P5, class P6, class P7>
1144  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1145    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7);
1146  }
1147
1148  template<class I, class P1, class P2, class P3, class P4,
1149      class P5, class P6, class P7>
1150      I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1151    return I::cast(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7));
1152  }
1153
1154  template<class I, class P1, class P2, class P3,
1155           class P4, class P5, class P6, class P7>
1156  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1157    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7));
1158  }
1159
1160  template<class I, class P1, class P2, class P3,
1161           class P4, class P5, class P6, class P7>
1162  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7) {
1163    return I::cast(AddInstruction(NewUncasted<I>(p1, p2, p3, p4,
1164                                                 p5, p6, p7)));
1165  }
1166
1167  template<class I, class P1, class P2, class P3, class P4,
1168      class P5, class P6, class P7, class P8>
1169  HInstruction* NewUncasted(P1 p1, P2 p2, P3 p3, P4 p4,
1170                            P5 p5, P6 p6, P7 p7, P8 p8) {
1171    return I::New(zone(), context(), p1, p2, p3, p4, p5, p6, p7, p8);
1172  }
1173
1174  template<class I, class P1, class P2, class P3, class P4,
1175      class P5, class P6, class P7, class P8>
1176      I* New(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7, P8 p8) {
1177    return I::cast(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7, p8));
1178  }
1179
1180  template<class I, class P1, class P2, class P3, class P4,
1181           class P5, class P6, class P7, class P8>
1182  HInstruction* AddUncasted(P1 p1, P2 p2, P3 p3, P4 p4,
1183                            P5 p5, P6 p6, P7 p7, P8 p8) {
1184    return AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7, p8));
1185  }
1186
1187  template<class I, class P1, class P2, class P3, class P4,
1188           class P5, class P6, class P7, class P8>
1189  I* Add(P1 p1, P2 p2, P3 p3, P4 p4, P5 p5, P6 p6, P7 p7, P8 p8) {
1190    return I::cast(
1191        AddInstruction(NewUncasted<I>(p1, p2, p3, p4, p5, p6, p7, p8)));
1192  }
1193
1194  void AddSimulate(BailoutId id, RemovableSimulate removable = FIXED_SIMULATE);
1195
1196 protected:
1197  virtual bool BuildGraph() = 0;
1198
1199  HBasicBlock* CreateBasicBlock(HEnvironment* env);
1200  HBasicBlock* CreateLoopHeaderBlock();
1201
1202  HValue* BuildCheckHeapObject(HValue* object);
1203  HValue* BuildCheckMap(HValue* obj, Handle<Map> map);
1204  HValue* BuildWrapReceiver(HValue* object, HValue* function);
1205
1206  // Building common constructs
1207  HValue* BuildCheckForCapacityGrow(HValue* object,
1208                                    HValue* elements,
1209                                    ElementsKind kind,
1210                                    HValue* length,
1211                                    HValue* key,
1212                                    bool is_js_array);
1213
1214  HValue* BuildCopyElementsOnWrite(HValue* object,
1215                                   HValue* elements,
1216                                   ElementsKind kind,
1217                                   HValue* length);
1218
1219  void BuildTransitionElementsKind(HValue* object,
1220                                   HValue* map,
1221                                   ElementsKind from_kind,
1222                                   ElementsKind to_kind,
1223                                   bool is_jsarray);
1224
1225  HInstruction* BuildUncheckedMonomorphicElementAccess(
1226      HValue* object,
1227      HValue* key,
1228      HValue* val,
1229      HCheckMaps* mapcheck,
1230      bool is_js_array,
1231      ElementsKind elements_kind,
1232      bool is_store,
1233      LoadKeyedHoleMode load_mode,
1234      KeyedAccessStoreMode store_mode);
1235
1236  HInstruction* AddExternalArrayElementAccess(
1237      HValue* external_elements,
1238      HValue* checked_key,
1239      HValue* val,
1240      HValue* dependency,
1241      ElementsKind elements_kind,
1242      bool is_store);
1243
1244  HInstruction* AddFastElementAccess(
1245      HValue* elements,
1246      HValue* checked_key,
1247      HValue* val,
1248      HValue* dependency,
1249      ElementsKind elements_kind,
1250      bool is_store,
1251      LoadKeyedHoleMode load_mode,
1252      KeyedAccessStoreMode store_mode);
1253
1254  HLoadNamedField* BuildLoadNamedField(
1255      HValue* object,
1256      HObjectAccess access,
1257      HValue* typecheck);
1258  HInstruction* BuildLoadStringLength(HValue* object, HValue* typecheck);
1259  HStoreNamedField* AddStoreMapConstant(HValue *object, Handle<Map>);
1260  HLoadNamedField* AddLoadElements(HValue *object, HValue *typecheck);
1261  HLoadNamedField* AddLoadFixedArrayLength(HValue *object);
1262
1263  HValue* AddLoadJSBuiltin(Builtins::JavaScript builtin);
1264
1265  HValue* TruncateToNumber(HValue* value, Handle<Type>* expected);
1266
1267  void PushAndAdd(HInstruction* instr);
1268
1269  void FinishExitWithHardDeoptimization(const char* reason,
1270                                        HBasicBlock* continuation);
1271
1272  void AddIncrementCounter(StatsCounter* counter,
1273                           HValue* context);
1274
1275  class IfBuilder {
1276   public:
1277    explicit IfBuilder(HGraphBuilder* builder,
1278                       int position = RelocInfo::kNoPosition);
1279    IfBuilder(HGraphBuilder* builder,
1280              HIfContinuation* continuation);
1281
1282    ~IfBuilder() {
1283      if (!finished_) End();
1284    }
1285
1286    template<class Condition>
1287    HInstruction* If(HValue *p) {
1288      HControlInstruction* compare = new(zone()) Condition(p);
1289      AddCompare(compare);
1290      return compare;
1291    }
1292
1293    template<class Condition, class P2>
1294    HInstruction* If(HValue* p1, P2 p2) {
1295      HControlInstruction* compare = new(zone()) Condition(p1, p2);
1296      AddCompare(compare);
1297      return compare;
1298    }
1299
1300    template<class Condition, class P2, class P3>
1301    HInstruction* If(HValue* p1, P2 p2, P3 p3) {
1302      HControlInstruction* compare = new(zone()) Condition(p1, p2, p3);
1303      AddCompare(compare);
1304      return compare;
1305    }
1306
1307    template<class Condition, class P2>
1308    HInstruction* IfNot(HValue* p1, P2 p2) {
1309      HControlInstruction* compare = new(zone()) Condition(p1, p2);
1310      AddCompare(compare);
1311      HBasicBlock* block0 = compare->SuccessorAt(0);
1312      HBasicBlock* block1 = compare->SuccessorAt(1);
1313      compare->SetSuccessorAt(0, block1);
1314      compare->SetSuccessorAt(1, block0);
1315      return compare;
1316    }
1317
1318    template<class Condition, class P2, class P3>
1319    HInstruction* IfNot(HValue* p1, P2 p2, P3 p3) {
1320      HControlInstruction* compare = new(zone()) Condition(p1, p2, p3);
1321      AddCompare(compare);
1322      HBasicBlock* block0 = compare->SuccessorAt(0);
1323      HBasicBlock* block1 = compare->SuccessorAt(1);
1324      compare->SetSuccessorAt(0, block1);
1325      compare->SetSuccessorAt(1, block0);
1326      return compare;
1327    }
1328
1329    template<class Condition>
1330    HInstruction* OrIf(HValue *p) {
1331      Or();
1332      return If<Condition>(p);
1333    }
1334
1335    template<class Condition, class P2>
1336    HInstruction* OrIf(HValue* p1, P2 p2) {
1337      Or();
1338      return If<Condition>(p1, p2);
1339    }
1340
1341    template<class Condition, class P2, class P3>
1342    HInstruction* OrIf(HValue* p1, P2 p2, P3 p3) {
1343      Or();
1344      return If<Condition>(p1, p2, p3);
1345    }
1346
1347    template<class Condition>
1348    HInstruction* AndIf(HValue *p) {
1349      And();
1350      return If<Condition>(p);
1351    }
1352
1353    template<class Condition, class P2>
1354    HInstruction* AndIf(HValue* p1, P2 p2) {
1355      And();
1356      return If<Condition>(p1, p2);
1357    }
1358
1359    template<class Condition, class P2, class P3>
1360    HInstruction* AndIf(HValue* p1, P2 p2, P3 p3) {
1361      And();
1362      return If<Condition>(p1, p2, p3);
1363    }
1364
1365    void Or();
1366    void And();
1367
1368    void CaptureContinuation(HIfContinuation* continuation);
1369
1370    void Then();
1371    void Else();
1372    void End();
1373
1374    void Deopt(const char* reason);
1375    void ElseDeopt(const char* reason) {
1376      Else();
1377      Deopt(reason);
1378    }
1379
1380    void Return(HValue* value);
1381
1382   private:
1383    void AddCompare(HControlInstruction* compare);
1384
1385    Zone* zone() { return builder_->zone(); }
1386
1387    HGraphBuilder* builder_;
1388    int position_;
1389    bool finished_ : 1;
1390    bool deopt_then_ : 1;
1391    bool deopt_else_ : 1;
1392    bool did_then_ : 1;
1393    bool did_else_ : 1;
1394    bool did_and_ : 1;
1395    bool did_or_ : 1;
1396    bool captured_ : 1;
1397    bool needs_compare_ : 1;
1398    HBasicBlock* first_true_block_;
1399    HBasicBlock* last_true_block_;
1400    HBasicBlock* first_false_block_;
1401    HBasicBlock* split_edge_merge_block_;
1402    HBasicBlock* merge_block_;
1403  };
1404
1405  class LoopBuilder {
1406   public:
1407    enum Direction {
1408      kPreIncrement,
1409      kPostIncrement,
1410      kPreDecrement,
1411      kPostDecrement
1412    };
1413
1414    LoopBuilder(HGraphBuilder* builder,
1415                HValue* context,
1416                Direction direction);
1417    ~LoopBuilder() {
1418      ASSERT(finished_);
1419    }
1420
1421    HValue* BeginBody(
1422        HValue* initial,
1423        HValue* terminating,
1424        Token::Value token);
1425    void EndBody();
1426
1427   private:
1428    Zone* zone() { return builder_->zone(); }
1429
1430    HGraphBuilder* builder_;
1431    HValue* context_;
1432    HInstruction* increment_;
1433    HPhi* phi_;
1434    HBasicBlock* header_block_;
1435    HBasicBlock* body_block_;
1436    HBasicBlock* exit_block_;
1437    Direction direction_;
1438    bool finished_;
1439  };
1440
1441  HValue* BuildNewElementsCapacity(HValue* old_capacity);
1442
1443  void BuildNewSpaceArrayCheck(HValue* length,
1444                               ElementsKind kind);
1445
1446  class JSArrayBuilder {
1447   public:
1448    JSArrayBuilder(HGraphBuilder* builder,
1449                   ElementsKind kind,
1450                   HValue* allocation_site_payload,
1451                   HValue* constructor_function,
1452                   AllocationSiteOverrideMode override_mode);
1453
1454    JSArrayBuilder(HGraphBuilder* builder,
1455                   ElementsKind kind,
1456                   HValue* constructor_function);
1457
1458    HValue* AllocateEmptyArray();
1459    HValue* AllocateArray(HValue* capacity, HValue* length_field,
1460                          bool fill_with_hole);
1461    HValue* GetElementsLocation() { return elements_location_; }
1462
1463   private:
1464    Zone* zone() const { return builder_->zone(); }
1465    int elements_size() const {
1466      return IsFastDoubleElementsKind(kind_) ? kDoubleSize : kPointerSize;
1467    }
1468    HGraphBuilder* builder() { return builder_; }
1469    HGraph* graph() { return builder_->graph(); }
1470    int initial_capacity() {
1471      STATIC_ASSERT(JSArray::kPreallocatedArrayElements > 0);
1472      return JSArray::kPreallocatedArrayElements;
1473    }
1474
1475    HValue* EmitMapCode();
1476    HValue* EmitInternalMapCode();
1477    HValue* EstablishEmptyArrayAllocationSize();
1478    HValue* EstablishAllocationSize(HValue* length_node);
1479    HValue* AllocateArray(HValue* size_in_bytes, HValue* capacity,
1480                          HValue* length_field,  bool fill_with_hole);
1481
1482    HGraphBuilder* builder_;
1483    ElementsKind kind_;
1484    AllocationSiteMode mode_;
1485    HValue* allocation_site_payload_;
1486    HValue* constructor_function_;
1487    HInnerAllocatedObject* elements_location_;
1488  };
1489
1490  HValue* BuildAllocateElements(ElementsKind kind,
1491                                HValue* capacity);
1492
1493  void BuildInitializeElementsHeader(HValue* elements,
1494                                     ElementsKind kind,
1495                                     HValue* capacity);
1496
1497  HValue* BuildAllocateElementsAndInitializeElementsHeader(ElementsKind kind,
1498                                                           HValue* capacity);
1499
1500  // array must have been allocated with enough room for
1501  // 1) the JSArray, 2) a AllocationMemento if mode requires it,
1502  // 3) a FixedArray or FixedDoubleArray.
1503  // A pointer to the Fixed(Double)Array is returned.
1504  HInnerAllocatedObject* BuildJSArrayHeader(HValue* array,
1505                                            HValue* array_map,
1506                                            AllocationSiteMode mode,
1507                                            ElementsKind elements_kind,
1508                                            HValue* allocation_site_payload,
1509                                            HValue* length_field);
1510
1511  HValue* BuildGrowElementsCapacity(HValue* object,
1512                                    HValue* elements,
1513                                    ElementsKind kind,
1514                                    ElementsKind new_kind,
1515                                    HValue* length,
1516                                    HValue* new_capacity);
1517
1518  void BuildFillElementsWithHole(HValue* elements,
1519                                 ElementsKind elements_kind,
1520                                 HValue* from,
1521                                 HValue* to);
1522
1523  void BuildCopyElements(HValue* from_elements,
1524                         ElementsKind from_elements_kind,
1525                         HValue* to_elements,
1526                         ElementsKind to_elements_kind,
1527                         HValue* length,
1528                         HValue* capacity);
1529
1530  HValue* BuildCloneShallowArray(HValue* boilerplate,
1531                                 HValue* allocation_site,
1532                                 AllocationSiteMode mode,
1533                                 ElementsKind kind,
1534                                 int length);
1535
1536  void BuildCompareNil(
1537      HValue* value,
1538      Handle<Type> type,
1539      int position,
1540      HIfContinuation* continuation);
1541
1542  HValue* BuildCreateAllocationMemento(HValue* previous_object,
1543                                       int previous_object_size,
1544                                       HValue* payload);
1545
1546  void BuildConstantMapCheck(Handle<JSObject> constant, CompilationInfo* info);
1547  void BuildCheckPrototypeMaps(Handle<JSObject> prototype,
1548                               Handle<JSObject> holder);
1549
1550  HInstruction* BuildGetNativeContext();
1551  HInstruction* BuildGetArrayFunction();
1552
1553 private:
1554  HGraphBuilder();
1555
1556  void PadEnvironmentForContinuation(HBasicBlock* from,
1557                                     HBasicBlock* continuation);
1558
1559  CompilationInfo* info_;
1560  HGraph* graph_;
1561  HBasicBlock* current_block_;
1562};
1563
1564
1565template<>
1566inline HInstruction* HGraphBuilder::AddUncasted<HDeoptimize>(
1567    const char* reason, Deoptimizer::BailoutType type) {
1568  if (type == Deoptimizer::SOFT) {
1569    isolate()->counters()->soft_deopts_requested()->Increment();
1570    if (FLAG_always_opt) return NULL;
1571  }
1572  if (current_block()->IsDeoptimizing()) return NULL;
1573  HDeoptimize* instr = New<HDeoptimize>(reason, type);
1574  AddInstruction(instr);
1575  if (type == Deoptimizer::SOFT) {
1576    isolate()->counters()->soft_deopts_inserted()->Increment();
1577    graph()->set_has_soft_deoptimize(true);
1578  }
1579  current_block()->MarkAsDeoptimizing();
1580  return instr;
1581}
1582
1583
1584template<>
1585inline HDeoptimize* HGraphBuilder::Add<HDeoptimize>(
1586    const char* reason, Deoptimizer::BailoutType type) {
1587  return static_cast<HDeoptimize*>(AddUncasted<HDeoptimize>(reason, type));
1588}
1589
1590
1591template<>
1592inline HInstruction* HGraphBuilder::AddUncasted<HSimulate>(
1593    BailoutId id,
1594    RemovableSimulate removable) {
1595  HSimulate* instr = current_block()->CreateSimulate(id, removable);
1596  AddInstruction(instr);
1597  return instr;
1598}
1599
1600
1601template<>
1602inline HInstruction* HGraphBuilder::NewUncasted<HLoadNamedField>(
1603    HValue* object, HObjectAccess access) {
1604  return NewUncasted<HLoadNamedField>(object, access,
1605                                      static_cast<HValue*>(NULL));
1606}
1607
1608
1609template<>
1610inline HInstruction* HGraphBuilder::AddUncasted<HLoadNamedField>(
1611    HValue* object, HObjectAccess access) {
1612  return AddUncasted<HLoadNamedField>(object, access,
1613                                      static_cast<HValue*>(NULL));
1614}
1615
1616
1617template<>
1618inline HInstruction* HGraphBuilder::AddUncasted<HSimulate>(BailoutId id) {
1619  return AddUncasted<HSimulate>(id, FIXED_SIMULATE);
1620}
1621
1622
1623template<>
1624inline HInstruction* HGraphBuilder::AddUncasted<HReturn>(HValue* value) {
1625  int num_parameters = graph()->info()->num_parameters();
1626  HValue* params = AddUncasted<HConstant>(num_parameters);
1627  HReturn* return_instruction = New<HReturn>(value, params);
1628  current_block()->FinishExit(return_instruction);
1629  return return_instruction;
1630}
1631
1632
1633template<>
1634inline HInstruction* HGraphBuilder::AddUncasted<HReturn>(HConstant* value) {
1635  return AddUncasted<HReturn>(static_cast<HValue*>(value));
1636}
1637
1638
1639template<>
1640inline HInstruction* HGraphBuilder::NewUncasted<HContext>() {
1641  return HContext::New(zone());
1642}
1643
1644
1645class HOptimizedGraphBuilder: public HGraphBuilder, public AstVisitor {
1646 public:
1647  // A class encapsulating (lazily-allocated) break and continue blocks for
1648  // a breakable statement.  Separated from BreakAndContinueScope so that it
1649  // can have a separate lifetime.
1650  class BreakAndContinueInfo BASE_EMBEDDED {
1651   public:
1652    explicit BreakAndContinueInfo(BreakableStatement* target,
1653                                  int drop_extra = 0)
1654        : target_(target),
1655          break_block_(NULL),
1656          continue_block_(NULL),
1657          drop_extra_(drop_extra) {
1658    }
1659
1660    BreakableStatement* target() { return target_; }
1661    HBasicBlock* break_block() { return break_block_; }
1662    void set_break_block(HBasicBlock* block) { break_block_ = block; }
1663    HBasicBlock* continue_block() { return continue_block_; }
1664    void set_continue_block(HBasicBlock* block) { continue_block_ = block; }
1665    int drop_extra() { return drop_extra_; }
1666
1667   private:
1668    BreakableStatement* target_;
1669    HBasicBlock* break_block_;
1670    HBasicBlock* continue_block_;
1671    int drop_extra_;
1672  };
1673
1674  // A helper class to maintain a stack of current BreakAndContinueInfo
1675  // structures mirroring BreakableStatement nesting.
1676  class BreakAndContinueScope BASE_EMBEDDED {
1677   public:
1678    BreakAndContinueScope(BreakAndContinueInfo* info,
1679                          HOptimizedGraphBuilder* owner)
1680        : info_(info), owner_(owner), next_(owner->break_scope()) {
1681      owner->set_break_scope(this);
1682    }
1683
1684    ~BreakAndContinueScope() { owner_->set_break_scope(next_); }
1685
1686    BreakAndContinueInfo* info() { return info_; }
1687    HOptimizedGraphBuilder* owner() { return owner_; }
1688    BreakAndContinueScope* next() { return next_; }
1689
1690    // Search the break stack for a break or continue target.
1691    enum BreakType { BREAK, CONTINUE };
1692    HBasicBlock* Get(BreakableStatement* stmt, BreakType type, int* drop_extra);
1693
1694   private:
1695    BreakAndContinueInfo* info_;
1696    HOptimizedGraphBuilder* owner_;
1697    BreakAndContinueScope* next_;
1698  };
1699
1700  explicit HOptimizedGraphBuilder(CompilationInfo* info);
1701
1702  virtual bool BuildGraph();
1703
1704  // Simple accessors.
1705  BreakAndContinueScope* break_scope() const { return break_scope_; }
1706  void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; }
1707
1708  bool inline_bailout() { return inline_bailout_; }
1709
1710  HValue* context() { return environment()->context(); }
1711
1712  void Bailout(BailoutReason reason);
1713
1714  HBasicBlock* CreateJoin(HBasicBlock* first,
1715                          HBasicBlock* second,
1716                          BailoutId join_id);
1717
1718  FunctionState* function_state() const { return function_state_; }
1719
1720  void VisitDeclarations(ZoneList<Declaration*>* declarations);
1721
1722  void* operator new(size_t size, Zone* zone) {
1723    return zone->New(static_cast<int>(size));
1724  }
1725  void operator delete(void* pointer, Zone* zone) { }
1726  void operator delete(void* pointer) { }
1727
1728  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
1729
1730 private:
1731  // Type of a member function that generates inline code for a native function.
1732  typedef void (HOptimizedGraphBuilder::*InlineFunctionGenerator)
1733      (CallRuntime* call);
1734
1735  // Forward declarations for inner scope classes.
1736  class SubgraphScope;
1737
1738  static const InlineFunctionGenerator kInlineFunctionGenerators[];
1739
1740  static const int kMaxCallPolymorphism = 4;
1741  static const int kMaxLoadPolymorphism = 4;
1742  static const int kMaxStorePolymorphism = 4;
1743
1744  // Even in the 'unlimited' case we have to have some limit in order not to
1745  // overflow the stack.
1746  static const int kUnlimitedMaxInlinedSourceSize = 100000;
1747  static const int kUnlimitedMaxInlinedNodes = 10000;
1748  static const int kUnlimitedMaxInlinedNodesCumulative = 10000;
1749
1750  // Maximum depth and total number of elements and properties for literal
1751  // graphs to be considered for fast deep-copying.
1752  static const int kMaxFastLiteralDepth = 3;
1753  static const int kMaxFastLiteralProperties = 8;
1754
1755  // Simple accessors.
1756  void set_function_state(FunctionState* state) { function_state_ = state; }
1757
1758  AstContext* ast_context() const { return ast_context_; }
1759  void set_ast_context(AstContext* context) { ast_context_ = context; }
1760
1761  // Accessors forwarded to the function state.
1762  CompilationInfo* current_info() const {
1763    return function_state()->compilation_info();
1764  }
1765  AstContext* call_context() const {
1766    return function_state()->call_context();
1767  }
1768  HBasicBlock* function_return() const {
1769    return function_state()->function_return();
1770  }
1771  TestContext* inlined_test_context() const {
1772    return function_state()->test_context();
1773  }
1774  void ClearInlinedTestContext() {
1775    function_state()->ClearInlinedTestContext();
1776  }
1777  StrictModeFlag function_strict_mode_flag() {
1778    return function_state()->compilation_info()->is_classic_mode()
1779        ? kNonStrictMode : kStrictMode;
1780  }
1781
1782  // Generators for inline runtime functions.
1783#define INLINE_FUNCTION_GENERATOR_DECLARATION(Name, argc, ressize)      \
1784  void Generate##Name(CallRuntime* call);
1785
1786  INLINE_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
1787  INLINE_RUNTIME_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
1788#undef INLINE_FUNCTION_GENERATOR_DECLARATION
1789
1790  void VisitDelete(UnaryOperation* expr);
1791  void VisitVoid(UnaryOperation* expr);
1792  void VisitTypeof(UnaryOperation* expr);
1793  void VisitNot(UnaryOperation* expr);
1794
1795  void VisitComma(BinaryOperation* expr);
1796  void VisitLogicalExpression(BinaryOperation* expr);
1797  void VisitArithmeticExpression(BinaryOperation* expr);
1798
1799  bool PreProcessOsrEntry(IterationStatement* statement);
1800  void VisitLoopBody(IterationStatement* stmt,
1801                     HBasicBlock* loop_entry,
1802                     BreakAndContinueInfo* break_info);
1803
1804  // Create a back edge in the flow graph.  body_exit is the predecessor
1805  // block and loop_entry is the successor block.  loop_successor is the
1806  // block where control flow exits the loop normally (e.g., via failure of
1807  // the condition) and break_block is the block where control flow breaks
1808  // from the loop.  All blocks except loop_entry can be NULL.  The return
1809  // value is the new successor block which is the join of loop_successor
1810  // and break_block, or NULL.
1811  HBasicBlock* CreateLoop(IterationStatement* statement,
1812                          HBasicBlock* loop_entry,
1813                          HBasicBlock* body_exit,
1814                          HBasicBlock* loop_successor,
1815                          HBasicBlock* break_block);
1816
1817  HBasicBlock* JoinContinue(IterationStatement* statement,
1818                            HBasicBlock* exit_block,
1819                            HBasicBlock* continue_block);
1820
1821  HValue* Top() const { return environment()->Top(); }
1822  void Drop(int n) { environment()->Drop(n); }
1823  void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
1824  bool IsEligibleForEnvironmentLivenessAnalysis(Variable* var,
1825                                                int index,
1826                                                HValue* value,
1827                                                HEnvironment* env) {
1828    if (!FLAG_analyze_environment_liveness) return false;
1829    // |this| and |arguments| are always live; zapping parameters isn't
1830    // safe because function.arguments can inspect them at any time.
1831    return !var->is_this() &&
1832           !var->is_arguments() &&
1833           !value->IsArgumentsObject() &&
1834           env->is_local_index(index);
1835  }
1836  void BindIfLive(Variable* var, HValue* value) {
1837    HEnvironment* env = environment();
1838    int index = env->IndexFor(var);
1839    env->Bind(index, value);
1840    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) {
1841      HEnvironmentMarker* bind =
1842          new(zone()) HEnvironmentMarker(HEnvironmentMarker::BIND, index);
1843      AddInstruction(bind);
1844#ifdef DEBUG
1845      bind->set_closure(env->closure());
1846#endif
1847    }
1848  }
1849  HValue* LookupAndMakeLive(Variable* var) {
1850    HEnvironment* env = environment();
1851    int index = env->IndexFor(var);
1852    HValue* value = env->Lookup(index);
1853    if (IsEligibleForEnvironmentLivenessAnalysis(var, index, value, env)) {
1854      HEnvironmentMarker* lookup =
1855          new(zone()) HEnvironmentMarker(HEnvironmentMarker::LOOKUP, index);
1856      AddInstruction(lookup);
1857#ifdef DEBUG
1858      lookup->set_closure(env->closure());
1859#endif
1860    }
1861    return value;
1862  }
1863
1864  // The value of the arguments object is allowed in some but not most value
1865  // contexts.  (It's allowed in all effect contexts and disallowed in all
1866  // test contexts.)
1867  void VisitForValue(Expression* expr,
1868                     ArgumentsAllowedFlag flag = ARGUMENTS_NOT_ALLOWED);
1869  void VisitForTypeOf(Expression* expr);
1870  void VisitForEffect(Expression* expr);
1871  void VisitForControl(Expression* expr,
1872                       HBasicBlock* true_block,
1873                       HBasicBlock* false_block);
1874
1875  // Visit an argument subexpression and emit a push to the outgoing arguments.
1876  void VisitArgument(Expression* expr);
1877
1878  void VisitArgumentList(ZoneList<Expression*>* arguments);
1879
1880  // Visit a list of expressions from left to right, each in a value context.
1881  void VisitExpressions(ZoneList<Expression*>* exprs);
1882
1883  // Remove the arguments from the bailout environment and emit instructions
1884  // to push them as outgoing parameters.
1885  template <class Instruction> HInstruction* PreProcessCall(Instruction* call);
1886
1887  void SetUpScope(Scope* scope);
1888  virtual void VisitStatements(ZoneList<Statement*>* statements);
1889
1890#define DECLARE_VISIT(type) virtual void Visit##type(type* node);
1891  AST_NODE_LIST(DECLARE_VISIT)
1892#undef DECLARE_VISIT
1893
1894  // Helpers for flow graph construction.
1895  enum GlobalPropertyAccess {
1896    kUseCell,
1897    kUseGeneric
1898  };
1899  GlobalPropertyAccess LookupGlobalProperty(Variable* var,
1900                                            LookupResult* lookup,
1901                                            bool is_store);
1902
1903  void EnsureArgumentsArePushedForAccess();
1904  bool TryArgumentsAccess(Property* expr);
1905
1906  // Try to optimize fun.apply(receiver, arguments) pattern.
1907  bool TryCallApply(Call* expr);
1908
1909  int InliningAstSize(Handle<JSFunction> target);
1910  bool TryInline(CallKind call_kind,
1911                 Handle<JSFunction> target,
1912                 int arguments_count,
1913                 HValue* implicit_return_value,
1914                 BailoutId ast_id,
1915                 BailoutId return_id,
1916                 InliningKind inlining_kind);
1917
1918  bool TryInlineCall(Call* expr, bool drop_extra = false);
1919  bool TryInlineConstruct(CallNew* expr, HValue* implicit_return_value);
1920  bool TryInlineGetter(Handle<JSFunction> getter, Property* prop);
1921  bool TryInlineSetter(Handle<JSFunction> setter,
1922                       BailoutId id,
1923                       BailoutId assignment_id,
1924                       HValue* implicit_return_value);
1925  bool TryInlineApply(Handle<JSFunction> function,
1926                      Call* expr,
1927                      int arguments_count);
1928  bool TryInlineBuiltinMethodCall(Call* expr,
1929                                  HValue* receiver,
1930                                  Handle<Map> receiver_map,
1931                                  CheckType check_type);
1932  bool TryInlineBuiltinFunctionCall(Call* expr, bool drop_extra);
1933
1934  // If --trace-inlining, print a line of the inlining trace.  Inlining
1935  // succeeded if the reason string is NULL and failed if there is a
1936  // non-NULL reason string.
1937  void TraceInline(Handle<JSFunction> target,
1938                   Handle<JSFunction> caller,
1939                   const char* failure_reason);
1940
1941  void HandleGlobalVariableAssignment(Variable* var,
1942                                      HValue* value,
1943                                      int position,
1944                                      BailoutId ast_id);
1945
1946  void HandlePropertyAssignment(Assignment* expr);
1947  void HandleCompoundAssignment(Assignment* expr);
1948  void HandlePolymorphicLoadNamedField(Property* expr,
1949                                       HValue* object,
1950                                       SmallMapList* types,
1951                                       Handle<String> name);
1952  HInstruction* TryLoadPolymorphicAsMonomorphic(Property* expr,
1953                                                HValue* object,
1954                                                SmallMapList* types,
1955                                                Handle<String> name);
1956  void HandlePolymorphicStoreNamedField(int position,
1957                                        BailoutId assignment_id,
1958                                        HValue* object,
1959                                        HValue* value,
1960                                        HValue* result,
1961                                        SmallMapList* types,
1962                                        Handle<String> name);
1963  bool TryStorePolymorphicAsMonomorphic(int position,
1964                                        BailoutId assignment_id,
1965                                        HValue* object,
1966                                        HValue* value,
1967                                        HValue* result,
1968                                        SmallMapList* types,
1969                                        Handle<String> name);
1970  void HandlePolymorphicCallNamed(Call* expr,
1971                                  HValue* receiver,
1972                                  SmallMapList* types,
1973                                  Handle<String> name);
1974  bool TryCallPolymorphicAsMonomorphic(Call* expr,
1975                                       HValue* receiver,
1976                                       SmallMapList* types,
1977                                       Handle<String> name);
1978  void HandleLiteralCompareTypeof(CompareOperation* expr,
1979                                  Expression* sub_expr,
1980                                  Handle<String> check);
1981  void HandleLiteralCompareNil(CompareOperation* expr,
1982                               Expression* sub_expr,
1983                               NilValue nil);
1984
1985  HInstruction* BuildStringCharCodeAt(HValue* string,
1986                                      HValue* index);
1987  HInstruction* BuildBinaryOperation(BinaryOperation* expr,
1988                                     HValue* left,
1989                                     HValue* right);
1990  HInstruction* BuildIncrement(bool returns_original_input,
1991                               CountOperation* expr);
1992  HInstruction* BuildLoadKeyedGeneric(HValue* object,
1993                                      HValue* key);
1994
1995  HInstruction* TryBuildConsolidatedElementLoad(HValue* object,
1996                                                HValue* key,
1997                                                HValue* val,
1998                                                SmallMapList* maps);
1999
2000  HInstruction* BuildMonomorphicElementAccess(HValue* object,
2001                                              HValue* key,
2002                                              HValue* val,
2003                                              HValue* dependency,
2004                                              Handle<Map> map,
2005                                              bool is_store,
2006                                              KeyedAccessStoreMode store_mode);
2007
2008  HValue* HandlePolymorphicElementAccess(HValue* object,
2009                                         HValue* key,
2010                                         HValue* val,
2011                                         Expression* prop,
2012                                         BailoutId ast_id,
2013                                         int position,
2014                                         bool is_store,
2015                                         KeyedAccessStoreMode store_mode,
2016                                         bool* has_side_effects);
2017
2018  HValue* HandleKeyedElementAccess(HValue* obj,
2019                                   HValue* key,
2020                                   HValue* val,
2021                                   Expression* expr,
2022                                   BailoutId ast_id,
2023                                   int position,
2024                                   bool is_store,
2025                                   bool* has_side_effects);
2026
2027  HInstruction* BuildLoadNamedGeneric(HValue* object,
2028                                      Handle<String> name,
2029                                      Property* expr);
2030  HInstruction* BuildCallGetter(HValue* object,
2031                                Handle<Map> map,
2032                                Handle<JSFunction> getter,
2033                                Handle<JSObject> holder);
2034  HInstruction* BuildLoadNamedMonomorphic(HValue* object,
2035                                          Handle<String> name,
2036                                          Property* expr,
2037                                          Handle<Map> map);
2038
2039  HCheckMaps* AddCheckMap(HValue* object, Handle<Map> map);
2040
2041  void BuildStoreNamed(Expression* expression,
2042                       BailoutId id,
2043                       int position,
2044                       BailoutId assignment_id,
2045                       Property* prop,
2046                       HValue* object,
2047                       HValue* store_value,
2048                       HValue* result_value);
2049
2050  HInstruction* BuildStoreNamedField(HValue* object,
2051                                     Handle<String> name,
2052                                     HValue* value,
2053                                     Handle<Map> map,
2054                                     LookupResult* lookup);
2055  HInstruction* BuildStoreNamedGeneric(HValue* object,
2056                                       Handle<String> name,
2057                                       HValue* value);
2058  HInstruction* BuildStoreNamedMonomorphic(HValue* object,
2059                                           Handle<String> name,
2060                                           HValue* value,
2061                                           Handle<Map> map);
2062  HInstruction* BuildStoreKeyedGeneric(HValue* object,
2063                                       HValue* key,
2064                                       HValue* value);
2065
2066  HValue* BuildContextChainWalk(Variable* var);
2067
2068  HInstruction* BuildThisFunction();
2069
2070  HInstruction* BuildFastLiteral(HValue* context,
2071                                 Handle<JSObject> boilerplate_object,
2072                                 Handle<JSObject> original_boilerplate_object,
2073                                 Handle<Object> allocation_site,
2074                                 int data_size,
2075                                 int pointer_size,
2076                                 AllocationSiteMode mode);
2077
2078  void BuildEmitDeepCopy(Handle<JSObject> boilerplat_object,
2079                         Handle<JSObject> object,
2080                         Handle<Object> allocation_site,
2081                         HInstruction* target,
2082                         int* offset,
2083                         HInstruction* data_target,
2084                         int* data_offset,
2085                         AllocationSiteMode mode);
2086
2087  MUST_USE_RESULT HValue* BuildEmitObjectHeader(
2088      Handle<JSObject> boilerplat_object,
2089      HInstruction* target,
2090      HInstruction* data_target,
2091      int object_offset,
2092      int elements_offset,
2093      int elements_size);
2094
2095  void BuildEmitInObjectProperties(Handle<JSObject> boilerplate_object,
2096                                   Handle<JSObject> original_boilerplate_object,
2097                                   HValue* object_properties,
2098                                   HInstruction* target,
2099                                   int* offset,
2100                                   HInstruction* data_target,
2101                                   int* data_offset);
2102
2103  void BuildEmitElements(Handle<FixedArrayBase> elements,
2104                         Handle<FixedArrayBase> original_elements,
2105                         ElementsKind kind,
2106                         HValue* object_elements,
2107                         HInstruction* target,
2108                         int* offset,
2109                         HInstruction* data_target,
2110                         int* data_offset);
2111
2112  void BuildEmitFixedDoubleArray(Handle<FixedArrayBase> elements,
2113                                 ElementsKind kind,
2114                                 HValue* object_elements);
2115
2116  void BuildEmitFixedArray(Handle<FixedArrayBase> elements,
2117                           Handle<FixedArrayBase> original_elements,
2118                           ElementsKind kind,
2119                           HValue* object_elements,
2120                           HInstruction* target,
2121                           int* offset,
2122                           HInstruction* data_target,
2123                           int* data_offset);
2124
2125  void AddCheckPrototypeMaps(Handle<JSObject> holder,
2126                             Handle<Map> receiver_map);
2127
2128  void AddCheckConstantFunction(Handle<JSObject> holder,
2129                                HValue* receiver,
2130                                Handle<Map> receiver_map);
2131
2132  bool MatchRotateRight(HValue* left,
2133                        HValue* right,
2134                        HValue** operand,
2135                        HValue** shift_amount);
2136
2137  // The translation state of the currently-being-translated function.
2138  FunctionState* function_state_;
2139
2140  // The base of the function state stack.
2141  FunctionState initial_function_state_;
2142
2143  // Expression context of the currently visited subexpression. NULL when
2144  // visiting statements.
2145  AstContext* ast_context_;
2146
2147  // A stack of breakable statements entered.
2148  BreakAndContinueScope* break_scope_;
2149
2150  int inlined_count_;
2151  ZoneList<Handle<Object> > globals_;
2152
2153  bool inline_bailout_;
2154
2155  HOsrBuilder* osr_;
2156
2157  friend class FunctionState;  // Pushes and pops the state stack.
2158  friend class AstContext;  // Pushes and pops the AST context stack.
2159  friend class KeyedLoadFastElementStub;
2160  friend class HOsrBuilder;
2161
2162  DISALLOW_COPY_AND_ASSIGN(HOptimizedGraphBuilder);
2163};
2164
2165
2166Zone* AstContext::zone() const { return owner_->zone(); }
2167
2168
2169class HStatistics: public Malloced {
2170 public:
2171  HStatistics()
2172      : timing_(5),
2173        names_(5),
2174        sizes_(5),
2175        create_graph_(0),
2176        optimize_graph_(0),
2177        generate_code_(0),
2178        total_size_(0),
2179        full_code_gen_(0),
2180        source_size_(0) { }
2181
2182  void Initialize(CompilationInfo* info);
2183  void Print();
2184  void SaveTiming(const char* name, int64_t ticks, unsigned size);
2185
2186  void IncrementFullCodeGen(int64_t full_code_gen) {
2187    full_code_gen_ += full_code_gen;
2188  }
2189
2190  void IncrementSubtotals(int64_t create_graph,
2191                          int64_t optimize_graph,
2192                          int64_t generate_code) {
2193    create_graph_ += create_graph;
2194    optimize_graph_ += optimize_graph;
2195    generate_code_ += generate_code;
2196  }
2197
2198 private:
2199  List<int64_t> timing_;
2200  List<const char*> names_;
2201  List<unsigned> sizes_;
2202  int64_t create_graph_;
2203  int64_t optimize_graph_;
2204  int64_t generate_code_;
2205  unsigned total_size_;
2206  int64_t full_code_gen_;
2207  double source_size_;
2208};
2209
2210
2211class HPhase : public CompilationPhase {
2212 public:
2213  HPhase(const char* name, HGraph* graph)
2214      : CompilationPhase(name, graph->info()),
2215        graph_(graph) { }
2216  ~HPhase();
2217
2218 protected:
2219  HGraph* graph() const { return graph_; }
2220
2221 private:
2222  HGraph* graph_;
2223
2224  DISALLOW_COPY_AND_ASSIGN(HPhase);
2225};
2226
2227
2228class HTracer: public Malloced {
2229 public:
2230  explicit HTracer(int isolate_id)
2231      : trace_(&string_allocator_), indent_(0) {
2232    if (FLAG_trace_hydrogen_file == NULL) {
2233      OS::SNPrintF(filename_,
2234                   "hydrogen-%d-%d.cfg",
2235                   OS::GetCurrentProcessId(),
2236                   isolate_id);
2237    } else {
2238      OS::StrNCpy(filename_, FLAG_trace_hydrogen_file, filename_.length());
2239    }
2240    WriteChars(filename_.start(), "", 0, false);
2241  }
2242
2243  void TraceCompilation(CompilationInfo* info);
2244  void TraceHydrogen(const char* name, HGraph* graph);
2245  void TraceLithium(const char* name, LChunk* chunk);
2246  void TraceLiveRanges(const char* name, LAllocator* allocator);
2247
2248 private:
2249  class Tag BASE_EMBEDDED {
2250   public:
2251    Tag(HTracer* tracer, const char* name) {
2252      name_ = name;
2253      tracer_ = tracer;
2254      tracer->PrintIndent();
2255      tracer->trace_.Add("begin_%s\n", name);
2256      tracer->indent_++;
2257    }
2258
2259    ~Tag() {
2260      tracer_->indent_--;
2261      tracer_->PrintIndent();
2262      tracer_->trace_.Add("end_%s\n", name_);
2263      ASSERT(tracer_->indent_ >= 0);
2264      tracer_->FlushToFile();
2265    }
2266
2267   private:
2268    HTracer* tracer_;
2269    const char* name_;
2270  };
2271
2272  void TraceLiveRange(LiveRange* range, const char* type, Zone* zone);
2273  void Trace(const char* name, HGraph* graph, LChunk* chunk);
2274  void FlushToFile();
2275
2276  void PrintEmptyProperty(const char* name) {
2277    PrintIndent();
2278    trace_.Add("%s\n", name);
2279  }
2280
2281  void PrintStringProperty(const char* name, const char* value) {
2282    PrintIndent();
2283    trace_.Add("%s \"%s\"\n", name, value);
2284  }
2285
2286  void PrintLongProperty(const char* name, int64_t value) {
2287    PrintIndent();
2288    trace_.Add("%s %d000\n", name, static_cast<int>(value / 1000));
2289  }
2290
2291  void PrintBlockProperty(const char* name, int block_id) {
2292    PrintIndent();
2293    trace_.Add("%s \"B%d\"\n", name, block_id);
2294  }
2295
2296  void PrintIntProperty(const char* name, int value) {
2297    PrintIndent();
2298    trace_.Add("%s %d\n", name, value);
2299  }
2300
2301  void PrintIndent() {
2302    for (int i = 0; i < indent_; i++) {
2303      trace_.Add("  ");
2304    }
2305  }
2306
2307  EmbeddedVector<char, 64> filename_;
2308  HeapStringAllocator string_allocator_;
2309  StringStream trace_;
2310  int indent_;
2311};
2312
2313
2314class NoObservableSideEffectsScope {
2315 public:
2316  explicit NoObservableSideEffectsScope(HGraphBuilder* builder) :
2317      builder_(builder) {
2318    builder_->graph()->IncrementInNoSideEffectsScope();
2319  }
2320  ~NoObservableSideEffectsScope() {
2321    builder_->graph()->DecrementInNoSideEffectsScope();
2322  }
2323
2324 private:
2325  HGraphBuilder* builder_;
2326};
2327
2328
2329} }  // namespace v8::internal
2330
2331#endif  // V8_HYDROGEN_H_
2332