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