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