src/v8/src/hydrogen.h

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