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