deps/v8/src/hydrogen.h

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