src/v8/src/hydrogen.h

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