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