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