Home | History | Annotate | Download | only in src 
      1 // Copyright 2011 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 "ast.h"
     34 #include "compiler.h"
     35 #include "data-flow.h"
     36 #include "hydrogen-instructions.h"
     37 #include "zone.h"
     38 
     39 namespace v8 {
     40 namespace internal {
     41 
     42 // Forward declarations.
     43 class HEnvironment;
     44 class HGraph;
     45 class HLoopInformation;
     46 class HTracer;
     47 class LAllocator;
     48 class LChunk;
     49 class LiveRange;
     50 
     51 
     52 class HBasicBlock: public ZoneObject {
     53  public:
     54   explicit HBasicBlock(HGraph* graph);
     55   virtual ~HBasicBlock() { }
     56 
     57   // Simple accessors.
     58   int block_id() const { return block_id_; }
     59   void set_block_id(int id) { block_id_ = id; }
     60   HGraph* graph() const { return graph_; }
     61   const ZoneList<HPhi*>* phis() const { return &phis_; }
     62   HInstruction* first() const { return first_; }
     63   HInstruction* last() const { return last_; }
     64   void set_last(HInstruction* instr) { last_ = instr; }
     65   HInstruction* GetLastInstruction();
     66   HControlInstruction* end() const { return end_; }
     67   HLoopInformation* loop_information() const { return loop_information_; }
     68   const ZoneList<HBasicBlock*>* predecessors() const { return &predecessors_; }
     69   bool HasPredecessor() const { return predecessors_.length() > 0; }
     70   const ZoneList<HBasicBlock*>* dominated_blocks() const {
     71     return &dominated_blocks_;
     72   }
     73   const ZoneList<int>* deleted_phis() const {
     74     return &deleted_phis_;
     75   }
     76   void RecordDeletedPhi(int merge_index) {
     77     deleted_phis_.Add(merge_index);
     78   }
     79   HBasicBlock* dominator() const { return dominator_; }
     80   HEnvironment* last_environment() const { return last_environment_; }
     81   int argument_count() const { return argument_count_; }
     82   void set_argument_count(int count) { argument_count_ = count; }
     83   int first_instruction_index() const { return first_instruction_index_; }
     84   void set_first_instruction_index(int index) {
     85     first_instruction_index_ = index;
     86   }
     87   int last_instruction_index() const { return last_instruction_index_; }
     88   void set_last_instruction_index(int index) {
     89     last_instruction_index_ = index;
     90   }
     91 
     92   void AttachLoopInformation();
     93   void DetachLoopInformation();
     94   bool IsLoopHeader() const { return loop_information() != NULL; }
     95   bool IsStartBlock() const { return block_id() == 0; }
     96   void PostProcessLoopHeader(IterationStatement* stmt);
     97 
     98   bool IsFinished() const { return end_ != NULL; }
     99   void AddPhi(HPhi* phi);
    100   void RemovePhi(HPhi* phi);
    101   void AddInstruction(HInstruction* instr);
    102   bool Dominates(HBasicBlock* other) const;
    103 
    104   void SetInitialEnvironment(HEnvironment* env);
    105   void ClearEnvironment() { last_environment_ = NULL; }
    106   bool HasEnvironment() const { return last_environment_ != NULL; }
    107   void UpdateEnvironment(HEnvironment* env) { last_environment_ = env; }
    108   HBasicBlock* parent_loop_header() const { return parent_loop_header_; }
    109 
    110   void set_parent_loop_header(HBasicBlock* block) {
    111     ASSERT(parent_loop_header_ == NULL);
    112     parent_loop_header_ = block;
    113   }
    114 
    115   bool HasParentLoopHeader() const { return parent_loop_header_ != NULL; }
    116 
    117   void SetJoinId(int id);
    118 
    119   void Finish(HControlInstruction* last);
    120   void FinishExit(HControlInstruction* instruction);
    121   void Goto(HBasicBlock* block, bool include_stack_check = false);
    122 
    123   int PredecessorIndexOf(HBasicBlock* predecessor) const;
    124   void AddSimulate(int id) { AddInstruction(CreateSimulate(id)); }
    125   void AssignCommonDominator(HBasicBlock* other);
    126 
    127   void FinishExitWithDeoptimization() {
    128     FinishExit(CreateDeoptimize());
    129   }
    130 
    131   // Add the inlined function exit sequence, adding an HLeaveInlined
    132   // instruction and updating the bailout environment.
    133   void AddLeaveInlined(HValue* return_value, HBasicBlock* target);
    134 
    135   // If a target block is tagged as an inline function return, all
    136   // predecessors should contain the inlined exit sequence:
    137   //
    138   // LeaveInlined
    139   // Simulate (caller's environment)
    140   // Goto (target block)
    141   bool IsInlineReturnTarget() const { return is_inline_return_target_; }
    142   void MarkAsInlineReturnTarget() { is_inline_return_target_ = true; }
    143 
    144   inline Zone* zone();
    145 
    146 #ifdef DEBUG
    147   void Verify();
    148 #endif
    149 
    150  private:
    151   void RegisterPredecessor(HBasicBlock* pred);
    152   void AddDominatedBlock(HBasicBlock* block);
    153 
    154   HSimulate* CreateSimulate(int id);
    155   HDeoptimize* CreateDeoptimize();
    156 
    157   int block_id_;
    158   HGraph* graph_;
    159   ZoneList<HPhi*> phis_;
    160   HInstruction* first_;
    161   HInstruction* last_;
    162   HControlInstruction* end_;
    163   HLoopInformation* loop_information_;
    164   ZoneList<HBasicBlock*> predecessors_;
    165   HBasicBlock* dominator_;
    166   ZoneList<HBasicBlock*> dominated_blocks_;
    167   HEnvironment* last_environment_;
    168   // Outgoing parameter count at block exit, set during lithium translation.
    169   int argument_count_;
    170   // Instruction indices into the lithium code stream.
    171   int first_instruction_index_;
    172   int last_instruction_index_;
    173   ZoneList<int> deleted_phis_;
    174   HBasicBlock* parent_loop_header_;
    175   bool is_inline_return_target_;
    176 };
    177 
    178 
    179 class HLoopInformation: public ZoneObject {
    180  public:
    181   explicit HLoopInformation(HBasicBlock* loop_header)
    182       : back_edges_(4), loop_header_(loop_header), blocks_(8) {
    183     blocks_.Add(loop_header);
    184   }
    185   virtual ~HLoopInformation() {}
    186 
    187   const ZoneList<HBasicBlock*>* back_edges() const { return &back_edges_; }
    188   const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
    189   HBasicBlock* loop_header() const { return loop_header_; }
    190   HBasicBlock* GetLastBackEdge() const;
    191   void RegisterBackEdge(HBasicBlock* block);
    192 
    193  private:
    194   void AddBlock(HBasicBlock* block);
    195 
    196   ZoneList<HBasicBlock*> back_edges_;
    197   HBasicBlock* loop_header_;
    198   ZoneList<HBasicBlock*> blocks_;
    199 };
    200 
    201 
    202 class HGraph: public ZoneObject {
    203  public:
    204   explicit HGraph(CompilationInfo* info);
    205 
    206   Isolate* isolate() { return isolate_; }
    207   Zone* zone() { return isolate_->zone(); }
    208 
    209   const ZoneList<HBasicBlock*>* blocks() const { return &blocks_; }
    210   const ZoneList<HPhi*>* phi_list() const { return phi_list_; }
    211   HBasicBlock* entry_block() const { return entry_block_; }
    212   HEnvironment* start_environment() const { return start_environment_; }
    213 
    214   void InitializeInferredTypes();
    215   void InsertTypeConversions();
    216   void InsertRepresentationChanges();
    217   void MarkDeoptimizeOnUndefined();
    218   void ComputeMinusZeroChecks();
    219   bool ProcessArgumentsObject();
    220   void EliminateRedundantPhis();
    221   void EliminateUnreachablePhis();
    222   void Canonicalize();
    223   void OrderBlocks();
    224   void AssignDominators();
    225   void ReplaceCheckedValues();
    226 
    227   // Returns false if there are phi-uses of the arguments-object
    228   // which are not supported by the optimizing compiler.
    229   bool CollectPhis();
    230 
    231   Handle<Code> Compile(CompilationInfo* info);
    232 
    233   void set_undefined_constant(HConstant* constant) {
    234     undefined_constant_.set(constant);
    235   }
    236   HConstant* GetConstantUndefined() const { return undefined_constant_.get(); }
    237   HConstant* GetConstant1();
    238   HConstant* GetConstantMinus1();
    239   HConstant* GetConstantTrue();
    240   HConstant* GetConstantFalse();
    241 
    242   HBasicBlock* CreateBasicBlock();
    243   HArgumentsObject* GetArgumentsObject() const {
    244     return arguments_object_.get();
    245   }
    246   bool HasArgumentsObject() const { return arguments_object_.is_set(); }
    247 
    248   void SetArgumentsObject(HArgumentsObject* object) {
    249     arguments_object_.set(object);
    250   }
    251 
    252   int GetMaximumValueID() const { return values_.length(); }
    253   int GetNextBlockID() { return next_block_id_++; }
    254   int GetNextValueID(HValue* value) {
    255     values_.Add(value);
    256     return values_.length() - 1;
    257   }
    258   HValue* LookupValue(int id) const {
    259     if (id >= 0 && id < values_.length()) return values_[id];
    260     return NULL;
    261   }
    262 
    263 #ifdef DEBUG
    264   void Verify() const;
    265 #endif
    266 
    267  private:
    268   void Postorder(HBasicBlock* block,
    269                  BitVector* visited,
    270                  ZoneList<HBasicBlock*>* order,
    271                  HBasicBlock* loop_header);
    272   void PostorderLoopBlocks(HLoopInformation* loop,
    273                            BitVector* visited,
    274                            ZoneList<HBasicBlock*>* order,
    275                            HBasicBlock* loop_header);
    276   HConstant* GetConstant(SetOncePointer<HConstant>* pointer,
    277                          Object* value);
    278 
    279   void InsertTypeConversions(HInstruction* instr);
    280   void PropagateMinusZeroChecks(HValue* value, BitVector* visited);
    281   void RecursivelyMarkPhiDeoptimizeOnUndefined(HPhi* phi);
    282   void InsertRepresentationChangeForUse(HValue* value,
    283                                         HValue* use,
    284                                         Representation to);
    285   void InsertRepresentationChangesForValue(HValue* current,
    286                                            ZoneList<HValue*>* value_list,
    287                                            ZoneList<Representation>* rep_list);
    288   void InferTypes(ZoneList<HValue*>* worklist);
    289   void InitializeInferredTypes(int from_inclusive, int to_inclusive);
    290   void CheckForBackEdge(HBasicBlock* block, HBasicBlock* successor);
    291 
    292   Isolate* isolate_;
    293   int next_block_id_;
    294   HBasicBlock* entry_block_;
    295   HEnvironment* start_environment_;
    296   ZoneList<HBasicBlock*> blocks_;
    297   ZoneList<HValue*> values_;
    298   ZoneList<HPhi*>* phi_list_;
    299   SetOncePointer<HConstant> undefined_constant_;
    300   SetOncePointer<HConstant> constant_1_;
    301   SetOncePointer<HConstant> constant_minus1_;
    302   SetOncePointer<HConstant> constant_true_;
    303   SetOncePointer<HConstant> constant_false_;
    304   SetOncePointer<HArgumentsObject> arguments_object_;
    305 
    306   DISALLOW_COPY_AND_ASSIGN(HGraph);
    307 };
    308 
    309 
    310 Zone* HBasicBlock::zone() { return graph_->zone(); }
    311 
    312 
    313 class HEnvironment: public ZoneObject {
    314  public:
    315   HEnvironment(HEnvironment* outer,
    316                Scope* scope,
    317                Handle<JSFunction> closure);
    318 
    319   // Simple accessors.
    320   Handle<JSFunction> closure() const { return closure_; }
    321   const ZoneList<HValue*>* values() const { return &values_; }
    322   const ZoneList<int>* assigned_variables() const {
    323     return &assigned_variables_;
    324   }
    325   int parameter_count() const { return parameter_count_; }
    326   int local_count() const { return local_count_; }
    327   HEnvironment* outer() const { return outer_; }
    328   int pop_count() const { return pop_count_; }
    329   int push_count() const { return push_count_; }
    330 
    331   int ast_id() const { return ast_id_; }
    332   void set_ast_id(int id) { ast_id_ = id; }
    333 
    334   int length() const { return values_.length(); }
    335 
    336   void Bind(Variable* variable, HValue* value) {
    337     Bind(IndexFor(variable), value);
    338   }
    339 
    340   void Bind(int index, HValue* value);
    341 
    342   HValue* Lookup(Variable* variable) const {
    343     return Lookup(IndexFor(variable));
    344   }
    345 
    346   HValue* Lookup(int index) const {
    347     HValue* result = values_[index];
    348     ASSERT(result != NULL);
    349     return result;
    350   }
    351 
    352   void Push(HValue* value) {
    353     ASSERT(value != NULL);
    354     ++push_count_;
    355     values_.Add(value);
    356   }
    357 
    358   HValue* Pop() {
    359     ASSERT(!ExpressionStackIsEmpty());
    360     if (push_count_ > 0) {
    361       --push_count_;
    362     } else {
    363       ++pop_count_;
    364     }
    365     return values_.RemoveLast();
    366   }
    367 
    368   void Drop(int count);
    369 
    370   HValue* Top() const { return ExpressionStackAt(0); }
    371 
    372   HValue* ExpressionStackAt(int index_from_top) const {
    373     int index = length() - index_from_top - 1;
    374     ASSERT(HasExpressionAt(index));
    375     return values_[index];
    376   }
    377 
    378   void SetExpressionStackAt(int index_from_top, HValue* value);
    379 
    380   HEnvironment* Copy() const;
    381   HEnvironment* CopyWithoutHistory() const;
    382   HEnvironment* CopyAsLoopHeader(HBasicBlock* block) const;
    383 
    384   // Create an "inlined version" of this environment, where the original
    385   // environment is the outer environment but the top expression stack
    386   // elements are moved to an inner environment as parameters. If
    387   // is_speculative, the argument values are expected to be PushArgument
    388   // instructions, otherwise they are the actual values.
    389   HEnvironment* CopyForInlining(Handle<JSFunction> target,
    390                                 FunctionLiteral* function,
    391                                 bool is_speculative,
    392                                 HConstant* undefined) const;
    393 
    394   void AddIncomingEdge(HBasicBlock* block, HEnvironment* other);
    395 
    396   void ClearHistory() {
    397     pop_count_ = 0;
    398     push_count_ = 0;
    399     assigned_variables_.Rewind(0);
    400   }
    401 
    402   void SetValueAt(int index, HValue* value) {
    403     ASSERT(index < length());
    404     values_[index] = value;
    405   }
    406 
    407   void PrintTo(StringStream* stream);
    408   void PrintToStd();
    409 
    410  private:
    411   explicit HEnvironment(const HEnvironment* other);
    412 
    413   // True if index is included in the expression stack part of the environment.
    414   bool HasExpressionAt(int index) const;
    415 
    416   bool ExpressionStackIsEmpty() const;
    417 
    418   void Initialize(int parameter_count, int local_count, int stack_height);
    419   void Initialize(const HEnvironment* other);
    420 
    421   // Map a variable to an environment index.  Parameter indices are shifted
    422   // by 1 (receiver is parameter index -1 but environment index 0).
    423   // Stack-allocated local indices are shifted by the number of parameters.
    424   int IndexFor(Variable* variable) const {
    425     Slot* slot = variable->AsSlot();
    426     ASSERT(slot != NULL && slot->IsStackAllocated());
    427     int shift = (slot->type() == Slot::PARAMETER) ? 1 : parameter_count_;
    428     return slot->index() + shift;
    429   }
    430 
    431   Handle<JSFunction> closure_;
    432   // Value array [parameters] [locals] [temporaries].
    433   ZoneList<HValue*> values_;
    434   ZoneList<int> assigned_variables_;
    435   int parameter_count_;
    436   int local_count_;
    437   HEnvironment* outer_;
    438   int pop_count_;
    439   int push_count_;
    440   int ast_id_;
    441 };
    442 
    443 
    444 class HGraphBuilder;
    445 
    446 // This class is not BASE_EMBEDDED because our inlining implementation uses
    447 // new and delete.
    448 class AstContext {
    449  public:
    450   bool IsEffect() const { return kind_ == Expression::kEffect; }
    451   bool IsValue() const { return kind_ == Expression::kValue; }
    452   bool IsTest() const { return kind_ == Expression::kTest; }
    453 
    454   // 'Fill' this context with a hydrogen value.  The value is assumed to
    455   // have already been inserted in the instruction stream (or not need to
    456   // be, e.g., HPhi).  Call this function in tail position in the Visit
    457   // functions for expressions.
    458   virtual void ReturnValue(HValue* value) = 0;
    459 
    460   // Add a hydrogen instruction to the instruction stream (recording an
    461   // environment simulation if necessary) and then fill this context with
    462   // the instruction as value.
    463   virtual void ReturnInstruction(HInstruction* instr, int ast_id) = 0;
    464 
    465   void set_for_typeof(bool for_typeof) { for_typeof_ = for_typeof; }
    466   bool is_for_typeof() { return for_typeof_; }
    467 
    468  protected:
    469   AstContext(HGraphBuilder* owner, Expression::Context kind);
    470   virtual ~AstContext();
    471 
    472   HGraphBuilder* owner() const { return owner_; }
    473 
    474   inline Zone* zone();
    475 
    476   // We want to be able to assert, in a context-specific way, that the stack
    477   // height makes sense when the context is filled.
    478 #ifdef DEBUG
    479   int original_length_;
    480 #endif
    481 
    482  private:
    483   HGraphBuilder* owner_;
    484   Expression::Context kind_;
    485   AstContext* outer_;
    486   bool for_typeof_;
    487 };
    488 
    489 
    490 class EffectContext: public AstContext {
    491  public:
    492   explicit EffectContext(HGraphBuilder* owner)
    493       : AstContext(owner, Expression::kEffect) {
    494   }
    495   virtual ~EffectContext();
    496 
    497   virtual void ReturnValue(HValue* value);
    498   virtual void ReturnInstruction(HInstruction* instr, int ast_id);
    499 };
    500 
    501 
    502 class ValueContext: public AstContext {
    503  public:
    504   explicit ValueContext(HGraphBuilder* owner)
    505       : AstContext(owner, Expression::kValue) {
    506   }
    507   virtual ~ValueContext();
    508 
    509   virtual void ReturnValue(HValue* value);
    510   virtual void ReturnInstruction(HInstruction* instr, int ast_id);
    511 };
    512 
    513 
    514 class TestContext: public AstContext {
    515  public:
    516   TestContext(HGraphBuilder* owner,
    517               HBasicBlock* if_true,
    518               HBasicBlock* if_false)
    519       : AstContext(owner, Expression::kTest),
    520         if_true_(if_true),
    521         if_false_(if_false) {
    522   }
    523 
    524   virtual void ReturnValue(HValue* value);
    525   virtual void ReturnInstruction(HInstruction* instr, int ast_id);
    526 
    527   static TestContext* cast(AstContext* context) {
    528     ASSERT(context->IsTest());
    529     return reinterpret_cast<TestContext*>(context);
    530   }
    531 
    532   HBasicBlock* if_true() const { return if_true_; }
    533   HBasicBlock* if_false() const { return if_false_; }
    534 
    535  private:
    536   // Build the shared core part of the translation unpacking a value into
    537   // control flow.
    538   void BuildBranch(HValue* value);
    539 
    540   HBasicBlock* if_true_;
    541   HBasicBlock* if_false_;
    542 };
    543 
    544 
    545 class FunctionState BASE_EMBEDDED {
    546  public:
    547   FunctionState(HGraphBuilder* owner,
    548                 CompilationInfo* info,
    549                 TypeFeedbackOracle* oracle);
    550   ~FunctionState();
    551 
    552   CompilationInfo* compilation_info() { return compilation_info_; }
    553   TypeFeedbackOracle* oracle() { return oracle_; }
    554   AstContext* call_context() { return call_context_; }
    555   HBasicBlock* function_return() { return function_return_; }
    556   TestContext* test_context() { return test_context_; }
    557   void ClearInlinedTestContext() {
    558     delete test_context_;
    559     test_context_ = NULL;
    560   }
    561 
    562   FunctionState* outer() { return outer_; }
    563 
    564  private:
    565   HGraphBuilder* owner_;
    566 
    567   CompilationInfo* compilation_info_;
    568   TypeFeedbackOracle* oracle_;
    569 
    570   // During function inlining, expression context of the call being
    571   // inlined. NULL when not inlining.
    572   AstContext* call_context_;
    573 
    574   // When inlining in an effect of value context, this is the return block.
    575   // It is NULL otherwise.  When inlining in a test context, there are a
    576   // pair of return blocks in the context.  When not inlining, there is no
    577   // local return point.
    578   HBasicBlock* function_return_;
    579 
    580   // When inlining a call in a test context, a context containing a pair of
    581   // return blocks.  NULL in all other cases.
    582   TestContext* test_context_;
    583 
    584   FunctionState* outer_;
    585 };
    586 
    587 
    588 class HGraphBuilder: public AstVisitor {
    589  public:
    590   enum BreakType { BREAK, CONTINUE };
    591 
    592   // A class encapsulating (lazily-allocated) break and continue blocks for
    593   // a breakable statement.  Separated from BreakAndContinueScope so that it
    594   // can have a separate lifetime.
    595   class BreakAndContinueInfo BASE_EMBEDDED {
    596    public:
    597     explicit BreakAndContinueInfo(BreakableStatement* target)
    598       : target_(target), break_block_(NULL), continue_block_(NULL) {
    599     }
    600 
    601     BreakableStatement* target() { return target_; }
    602     HBasicBlock* break_block() { return break_block_; }
    603     void set_break_block(HBasicBlock* block) { break_block_ = block; }
    604     HBasicBlock* continue_block() { return continue_block_; }
    605     void set_continue_block(HBasicBlock* block) { continue_block_ = block; }
    606 
    607    private:
    608     BreakableStatement* target_;
    609     HBasicBlock* break_block_;
    610     HBasicBlock* continue_block_;
    611   };
    612 
    613   // A helper class to maintain a stack of current BreakAndContinueInfo
    614   // structures mirroring BreakableStatement nesting.
    615   class BreakAndContinueScope BASE_EMBEDDED {
    616    public:
    617     BreakAndContinueScope(BreakAndContinueInfo* info, HGraphBuilder* owner)
    618         : info_(info), owner_(owner), next_(owner->break_scope()) {
    619       owner->set_break_scope(this);
    620     }
    621 
    622     ~BreakAndContinueScope() { owner_->set_break_scope(next_); }
    623 
    624     BreakAndContinueInfo* info() { return info_; }
    625     HGraphBuilder* owner() { return owner_; }
    626     BreakAndContinueScope* next() { return next_; }
    627 
    628     // Search the break stack for a break or continue target.
    629     HBasicBlock* Get(BreakableStatement* stmt, BreakType type);
    630 
    631    private:
    632     BreakAndContinueInfo* info_;
    633     HGraphBuilder* owner_;
    634     BreakAndContinueScope* next_;
    635   };
    636 
    637   HGraphBuilder(CompilationInfo* info, TypeFeedbackOracle* oracle)
    638       : function_state_(NULL),
    639         initial_function_state_(this, info, oracle),
    640         ast_context_(NULL),
    641         break_scope_(NULL),
    642         graph_(NULL),
    643         current_block_(NULL),
    644         inlined_count_(0),
    645         zone_(info->isolate()->zone()) {
    646     // This is not initialized in the initializer list because the
    647     // constructor for the initial state relies on function_state_ == NULL
    648     // to know it's the initial state.
    649     function_state_= &initial_function_state_;
    650   }
    651 
    652   HGraph* CreateGraph();
    653 
    654   // Simple accessors.
    655   HGraph* graph() const { return graph_; }
    656   BreakAndContinueScope* break_scope() const { return break_scope_; }
    657   void set_break_scope(BreakAndContinueScope* head) { break_scope_ = head; }
    658 
    659   HBasicBlock* current_block() const { return current_block_; }
    660   void set_current_block(HBasicBlock* block) { current_block_ = block; }
    661   HEnvironment* environment() const {
    662     return current_block()->last_environment();
    663   }
    664 
    665   // Adding instructions.
    666   HInstruction* AddInstruction(HInstruction* instr);
    667   void AddSimulate(int id);
    668 
    669   // Bailout environment manipulation.
    670   void Push(HValue* value) { environment()->Push(value); }
    671   HValue* Pop() { return environment()->Pop(); }
    672 
    673  private:
    674   // Type of a member function that generates inline code for a native function.
    675   typedef void (HGraphBuilder::*InlineFunctionGenerator)(CallRuntime* call);
    676 
    677   // Forward declarations for inner scope classes.
    678   class SubgraphScope;
    679 
    680   static const InlineFunctionGenerator kInlineFunctionGenerators[];
    681 
    682   static const int kMaxCallPolymorphism = 4;
    683   static const int kMaxLoadPolymorphism = 4;
    684   static const int kMaxStorePolymorphism = 4;
    685 
    686   static const int kMaxInlinedNodes = 196;
    687   static const int kMaxInlinedSize = 196;
    688   static const int kMaxSourceSize = 600;
    689 
    690   // Simple accessors.
    691   FunctionState* function_state() const { return function_state_; }
    692   void set_function_state(FunctionState* state) { function_state_ = state; }
    693 
    694   AstContext* ast_context() const { return ast_context_; }
    695   void set_ast_context(AstContext* context) { ast_context_ = context; }
    696 
    697   // Accessors forwarded to the function state.
    698   CompilationInfo* info() const {
    699     return function_state()->compilation_info();
    700   }
    701   TypeFeedbackOracle* oracle() const { return function_state()->oracle(); }
    702 
    703   AstContext* call_context() const {
    704     return function_state()->call_context();
    705   }
    706   HBasicBlock* function_return() const {
    707     return function_state()->function_return();
    708   }
    709   TestContext* inlined_test_context() const {
    710     return function_state()->test_context();
    711   }
    712   void ClearInlinedTestContext() {
    713     function_state()->ClearInlinedTestContext();
    714   }
    715   bool function_strict_mode() {
    716     return function_state()->compilation_info()->is_strict_mode();
    717   }
    718 
    719   // Generators for inline runtime functions.
    720 #define INLINE_FUNCTION_GENERATOR_DECLARATION(Name, argc, ressize)      \
    721   void Generate##Name(CallRuntime* call);
    722 
    723   INLINE_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
    724   INLINE_RUNTIME_FUNCTION_LIST(INLINE_FUNCTION_GENERATOR_DECLARATION)
    725 #undef INLINE_FUNCTION_GENERATOR_DECLARATION
    726 
    727   void Bailout(const char* reason);
    728 
    729   void PreProcessOsrEntry(IterationStatement* statement);
    730   // True iff. we are compiling for OSR and the statement is the entry.
    731   bool HasOsrEntryAt(IterationStatement* statement);
    732 
    733   HBasicBlock* CreateJoin(HBasicBlock* first,
    734                           HBasicBlock* second,
    735                           int join_id);
    736 
    737   // Create a back edge in the flow graph.  body_exit is the predecessor
    738   // block and loop_entry is the successor block.  loop_successor is the
    739   // block where control flow exits the loop normally (e.g., via failure of
    740   // the condition) and break_block is the block where control flow breaks
    741   // from the loop.  All blocks except loop_entry can be NULL.  The return
    742   // value is the new successor block which is the join of loop_successor
    743   // and break_block, or NULL.
    744   HBasicBlock* CreateLoop(IterationStatement* statement,
    745                           HBasicBlock* loop_entry,
    746                           HBasicBlock* body_exit,
    747                           HBasicBlock* loop_successor,
    748                           HBasicBlock* break_block);
    749 
    750   HBasicBlock* JoinContinue(IterationStatement* statement,
    751                             HBasicBlock* exit_block,
    752                             HBasicBlock* continue_block);
    753 
    754   HValue* Top() const { return environment()->Top(); }
    755   void Drop(int n) { environment()->Drop(n); }
    756   void Bind(Variable* var, HValue* value) { environment()->Bind(var, value); }
    757 
    758   void VisitForValue(Expression* expr);
    759   void VisitForTypeOf(Expression* expr);
    760   void VisitForEffect(Expression* expr);
    761   void VisitForControl(Expression* expr,
    762                        HBasicBlock* true_block,
    763                        HBasicBlock* false_block);
    764 
    765   // Visit an argument subexpression and emit a push to the outgoing
    766   // arguments.
    767   void VisitArgument(Expression* expr);
    768   void VisitArgumentList(ZoneList<Expression*>* arguments);
    769 
    770   // Visit a list of expressions from left to right, each in a value context.
    771   void VisitExpressions(ZoneList<Expression*>* exprs);
    772 
    773   void AddPhi(HPhi* phi);
    774 
    775   void PushAndAdd(HInstruction* instr);
    776 
    777   // Remove the arguments from the bailout environment and emit instructions
    778   // to push them as outgoing parameters.
    779   template <int V> HInstruction* PreProcessCall(HCall<V>* call);
    780 
    781   void AssumeRepresentation(HValue* value, Representation r);
    782   static Representation ToRepresentation(TypeInfo info);
    783 
    784   void SetupScope(Scope* scope);
    785   virtual void VisitStatements(ZoneList<Statement*>* statements);
    786 
    787 #define DECLARE_VISIT(type) virtual void Visit##type(type* node);
    788   AST_NODE_LIST(DECLARE_VISIT)
    789 #undef DECLARE_VISIT
    790 
    791   HBasicBlock* CreateBasicBlock(HEnvironment* env);
    792   HBasicBlock* CreateLoopHeaderBlock();
    793 
    794   // Helpers for flow graph construction.
    795   enum GlobalPropertyAccess {
    796     kUseCell,
    797     kUseGeneric
    798   };
    799   GlobalPropertyAccess LookupGlobalProperty(Variable* var,
    800                                             LookupResult* lookup,
    801                                             bool is_store);
    802 
    803   bool TryArgumentsAccess(Property* expr);
    804 
    805   // Try to optimize fun.apply(receiver, arguments) pattern.
    806   bool TryCallApply(Call* expr);
    807 
    808   bool TryInline(Call* expr);
    809   bool TryInlineBuiltinFunction(Call* expr,
    810                                 HValue* receiver,
    811                                 Handle<Map> receiver_map,
    812                                 CheckType check_type);
    813 
    814   // If --trace-inlining, print a line of the inlining trace.  Inlining
    815   // succeeded if the reason string is NULL and failed if there is a
    816   // non-NULL reason string.
    817   void TraceInline(Handle<JSFunction> target, const char* failure_reason);
    818 
    819   void HandleGlobalVariableAssignment(Variable* var,
    820                                       HValue* value,
    821                                       int position,
    822                                       int ast_id);
    823 
    824   void HandlePropertyAssignment(Assignment* expr);
    825   void HandleCompoundAssignment(Assignment* expr);
    826   void HandlePolymorphicStoreNamedField(Assignment* expr,
    827                                         HValue* object,
    828                                         HValue* value,
    829                                         ZoneMapList* types,
    830                                         Handle<String> name);
    831   void HandlePolymorphicCallNamed(Call* expr,
    832                                   HValue* receiver,
    833                                   ZoneMapList* types,
    834                                   Handle<String> name);
    835 
    836   HStringCharCodeAt* BuildStringCharCodeAt(HValue* string,
    837                                            HValue* index);
    838   HInstruction* BuildBinaryOperation(BinaryOperation* expr,
    839                                      HValue* left,
    840                                      HValue* right);
    841   HInstruction* BuildIncrement(HValue* value, bool increment);
    842   HLoadNamedField* BuildLoadNamedField(HValue* object,
    843                                        Property* expr,
    844                                        Handle<Map> type,
    845                                        LookupResult* result,
    846                                        bool smi_and_map_check);
    847   HInstruction* BuildLoadNamedGeneric(HValue* object, Property* expr);
    848   HInstruction* BuildLoadKeyedFastElement(HValue* object,
    849                                           HValue* key,
    850                                           Property* expr);
    851   HInstruction* BuildLoadKeyedSpecializedArrayElement(HValue* object,
    852                                                       HValue* key,
    853                                                       Property* expr);
    854   HInstruction* BuildLoadKeyedGeneric(HValue* object,
    855                                       HValue* key);
    856 
    857   HInstruction* BuildLoadKeyed(HValue* obj,
    858                                HValue* key,
    859                                Property* prop);
    860 
    861   HInstruction* BuildLoadNamed(HValue* object,
    862                                Property* prop,
    863                                Handle<Map> map,
    864                                Handle<String> name);
    865   HInstruction* BuildStoreNamed(HValue* object,
    866                                 HValue* value,
    867                                 Expression* expr);
    868   HInstruction* BuildStoreNamedField(HValue* object,
    869                                      Handle<String> name,
    870                                      HValue* value,
    871                                      Handle<Map> type,
    872                                      LookupResult* lookup,
    873                                      bool smi_and_map_check);
    874   HInstruction* BuildStoreNamedGeneric(HValue* object,
    875                                        Handle<String> name,
    876                                        HValue* value);
    877   HInstruction* BuildStoreKeyedGeneric(HValue* object,
    878                                        HValue* key,
    879                                        HValue* value);
    880 
    881   HInstruction* BuildStoreKeyedFastElement(HValue* object,
    882                                            HValue* key,
    883                                            HValue* val,
    884                                            Expression* expr);
    885 
    886   HInstruction* BuildStoreKeyedSpecializedArrayElement(
    887       HValue* object,
    888       HValue* key,
    889       HValue* val,
    890       Expression* expr);
    891 
    892   HInstruction* BuildStoreKeyed(HValue* object,
    893                                 HValue* key,
    894                                 HValue* value,
    895                                 Expression* assignment);
    896 
    897   HValue* BuildContextChainWalk(Variable* var);
    898 
    899   void AddCheckConstantFunction(Call* expr,
    900                                 HValue* receiver,
    901                                 Handle<Map> receiver_map,
    902                                 bool smi_and_map_check);
    903 
    904   Zone* zone() { return zone_; }
    905 
    906   // The translation state of the currently-being-translated function.
    907   FunctionState* function_state_;
    908 
    909   // The base of the function state stack.
    910   FunctionState initial_function_state_;
    911 
    912   // Expression context of the currently visited subexpression. NULL when
    913   // visiting statements.
    914   AstContext* ast_context_;
    915 
    916   // A stack of breakable statements entered.
    917   BreakAndContinueScope* break_scope_;
    918 
    919   HGraph* graph_;
    920   HBasicBlock* current_block_;
    921 
    922   int inlined_count_;
    923 
    924   Zone* zone_;
    925 
    926   friend class FunctionState;  // Pushes and pops the state stack.
    927   friend class AstContext;  // Pushes and pops the AST context stack.
    928 
    929   DISALLOW_COPY_AND_ASSIGN(HGraphBuilder);
    930 };
    931 
    932 
    933 Zone* AstContext::zone() { return owner_->zone(); }
    934 
    935 
    936 class HValueMap: public ZoneObject {
    937  public:
    938   HValueMap()
    939       : array_size_(0),
    940         lists_size_(0),
    941         count_(0),
    942         present_flags_(0),
    943         array_(NULL),
    944         lists_(NULL),
    945         free_list_head_(kNil) {
    946     ResizeLists(kInitialSize);
    947     Resize(kInitialSize);
    948   }
    949 
    950   void Kill(int flags);
    951 
    952   void Add(HValue* value) {
    953     present_flags_ |= value->flags();
    954     Insert(value);
    955   }
    956 
    957   HValue* Lookup(HValue* value) const;
    958 
    959   HValueMap* Copy(Zone* zone) const {
    960     return new(zone) HValueMap(this);
    961   }
    962 
    963  private:
    964   // A linked list of HValue* values.  Stored in arrays.
    965   struct HValueMapListElement {
    966     HValue* value;
    967     int next;  // Index in the array of the next list element.
    968   };
    969   static const int kNil = -1;  // The end of a linked list
    970 
    971   // Must be a power of 2.
    972   static const int kInitialSize = 16;
    973 
    974   explicit HValueMap(const HValueMap* other);
    975 
    976   void Resize(int new_size);
    977   void ResizeLists(int new_size);
    978   void Insert(HValue* value);
    979   uint32_t Bound(uint32_t value) const { return value & (array_size_ - 1); }
    980 
    981   int array_size_;
    982   int lists_size_;
    983   int count_;  // The number of values stored in the HValueMap.
    984   int present_flags_;  // All flags that are in any value in the HValueMap.
    985   HValueMapListElement* array_;  // Primary store - contains the first value
    986   // with a given hash.  Colliding elements are stored in linked lists.
    987   HValueMapListElement* lists_;  // The linked lists containing hash collisions.
    988   int free_list_head_;  // Unused elements in lists_ are on the free list.
    989 };
    990 
    991 
    992 class HStatistics: public Malloced {
    993  public:
    994   void Initialize(CompilationInfo* info);
    995   void Print();
    996   void SaveTiming(const char* name, int64_t ticks, unsigned size);
    997   static HStatistics* Instance() {
    998     static SetOncePointer<HStatistics> instance;
    999     if (!instance.is_set()) {
   1000       instance.set(new HStatistics());
   1001     }
   1002     return instance.get();
   1003   }
   1004 
   1005  private:
   1006 
   1007   HStatistics()
   1008       : timing_(5),
   1009         names_(5),
   1010         sizes_(5),
   1011         total_(0),
   1012         total_size_(0),
   1013         full_code_gen_(0),
   1014         source_size_(0) { }
   1015 
   1016   List<int64_t> timing_;
   1017   List<const char*> names_;
   1018   List<unsigned> sizes_;
   1019   int64_t total_;
   1020   unsigned total_size_;
   1021   int64_t full_code_gen_;
   1022   double source_size_;
   1023 };
   1024 
   1025 
   1026 class HPhase BASE_EMBEDDED {
   1027  public:
   1028   static const char* const kFullCodeGen;
   1029   static const char* const kTotal;
   1030 
   1031   explicit HPhase(const char* name) { Begin(name, NULL, NULL, NULL); }
   1032   HPhase(const char* name, HGraph* graph) {
   1033     Begin(name, graph, NULL, NULL);
   1034   }
   1035   HPhase(const char* name, LChunk* chunk) {
   1036     Begin(name, NULL, chunk, NULL);
   1037   }
   1038   HPhase(const char* name, LAllocator* allocator) {
   1039     Begin(name, NULL, NULL, allocator);
   1040   }
   1041 
   1042   ~HPhase() {
   1043     End();
   1044   }
   1045 
   1046  private:
   1047   void Begin(const char* name,
   1048              HGraph* graph,
   1049              LChunk* chunk,
   1050              LAllocator* allocator);
   1051   void End() const;
   1052 
   1053   int64_t start_;
   1054   const char* name_;
   1055   HGraph* graph_;
   1056   LChunk* chunk_;
   1057   LAllocator* allocator_;
   1058   unsigned start_allocation_size_;
   1059 };
   1060 
   1061 
   1062 class HTracer: public Malloced {
   1063  public:
   1064   void TraceCompilation(FunctionLiteral* function);
   1065   void TraceHydrogen(const char* name, HGraph* graph);
   1066   void TraceLithium(const char* name, LChunk* chunk);
   1067   void TraceLiveRanges(const char* name, LAllocator* allocator);
   1068 
   1069   static HTracer* Instance() {
   1070     static SetOncePointer<HTracer> instance;
   1071     if (!instance.is_set()) {
   1072       instance.set(new HTracer("hydrogen.cfg"));
   1073     }
   1074     return instance.get();
   1075   }
   1076 
   1077  private:
   1078   class Tag BASE_EMBEDDED {
   1079    public:
   1080     Tag(HTracer* tracer, const char* name) {
   1081       name_ = name;
   1082       tracer_ = tracer;
   1083       tracer->PrintIndent();
   1084       tracer->trace_.Add("begin_%s\n", name);
   1085       tracer->indent_++;
   1086     }
   1087 
   1088     ~Tag() {
   1089       tracer_->indent_--;
   1090       tracer_->PrintIndent();
   1091       tracer_->trace_.Add("end_%s\n", name_);
   1092       ASSERT(tracer_->indent_ >= 0);
   1093       tracer_->FlushToFile();
   1094     }
   1095 
   1096    private:
   1097     HTracer* tracer_;
   1098     const char* name_;
   1099   };
   1100 
   1101   explicit HTracer(const char* filename)
   1102       : filename_(filename), trace_(&string_allocator_), indent_(0) {
   1103     WriteChars(filename, "", 0, false);
   1104   }
   1105 
   1106   void TraceLiveRange(LiveRange* range, const char* type);
   1107   void Trace(const char* name, HGraph* graph, LChunk* chunk);
   1108   void FlushToFile();
   1109 
   1110   void PrintEmptyProperty(const char* name) {
   1111     PrintIndent();
   1112     trace_.Add("%s\n", name);
   1113   }
   1114 
   1115   void PrintStringProperty(const char* name, const char* value) {
   1116     PrintIndent();
   1117     trace_.Add("%s \"%s\"\n", name, value);
   1118   }
   1119 
   1120   void PrintLongProperty(const char* name, int64_t value) {
   1121     PrintIndent();
   1122     trace_.Add("%s %d000\n", name, static_cast<int>(value / 1000));
   1123   }
   1124 
   1125   void PrintBlockProperty(const char* name, int block_id) {
   1126     PrintIndent();
   1127     trace_.Add("%s \"B%d\"\n", name, block_id);
   1128   }
   1129 
   1130   void PrintBlockProperty(const char* name, int block_id1, int block_id2) {
   1131     PrintIndent();
   1132     trace_.Add("%s \"B%d\" \"B%d\"\n", name, block_id1, block_id2);
   1133   }
   1134 
   1135   void PrintIntProperty(const char* name, int value) {
   1136     PrintIndent();
   1137     trace_.Add("%s %d\n", name, value);
   1138   }
   1139 
   1140   void PrintIndent() {
   1141     for (int i = 0; i < indent_; i++) {
   1142       trace_.Add("  ");
   1143     }
   1144   }
   1145 
   1146   const char* filename_;
   1147   HeapStringAllocator string_allocator_;
   1148   StringStream trace_;
   1149   int indent_;
   1150 };
   1151 
   1152 
   1153 } }  // namespace v8::internal
   1154 
   1155 #endif  // V8_HYDROGEN_H_
   1156