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