src/hydrogen.h

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