Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/hydrogen-flow-engine.h"
      6 #include "src/hydrogen-instructions.h"
      7 #include "src/hydrogen-removable-simulates.h"
      8 
      9 namespace v8 {
     10 namespace internal {
     11 
     12 class State : public ZoneObject {
     13  public:
     14   explicit State(Zone* zone)
     15       : zone_(zone), mergelist_(2, zone), first_(true), mode_(NORMAL) { }
     16 
     17   State* Process(HInstruction* instr, Zone* zone) {
     18     if (FLAG_trace_removable_simulates) {
     19       PrintF("[%s with state %p in B%d: #%d %s]\n",
     20              mode_ == NORMAL ? "processing" : "collecting",
     21              reinterpret_cast<void*>(this), instr->block()->block_id(),
     22              instr->id(), instr->Mnemonic());
     23     }
     24     // Forward-merge "trains" of simulates after an instruction with observable
     25     // side effects to keep live ranges short.
     26     if (mode_ == COLLECT_CONSECUTIVE_SIMULATES) {
     27       if (instr->IsSimulate()) {
     28         HSimulate* current_simulate = HSimulate::cast(instr);
     29         if (current_simulate->is_candidate_for_removal() &&
     30             !current_simulate->ast_id().IsNone()) {
     31           Remember(current_simulate);
     32           return this;
     33         }
     34       }
     35       FlushSimulates();
     36       mode_ = NORMAL;
     37     }
     38     // Ensure there's a non-foldable HSimulate before an HEnterInlined to avoid
     39     // folding across HEnterInlined.
     40     ASSERT(!(instr->IsEnterInlined() &&
     41              HSimulate::cast(instr->previous())->is_candidate_for_removal()));
     42     if (instr->IsLeaveInlined() || instr->IsReturn()) {
     43       // Never fold simulates from inlined environments into simulates in the
     44       // outer environment. Simply remove all accumulated simulates without
     45       // merging. This is safe because simulates after instructions with side
     46       // effects are never added to the merge list. The same reasoning holds for
     47       // return instructions.
     48       RemoveSimulates();
     49       return this;
     50     }
     51     if (instr->IsControlInstruction()) {
     52       // Merge the accumulated simulates at the end of the block.
     53       FlushSimulates();
     54       return this;
     55     }
     56     // Skip the non-simulates and the first simulate.
     57     if (!instr->IsSimulate()) return this;
     58     if (first_) {
     59       first_ = false;
     60       return this;
     61     }
     62     HSimulate* current_simulate = HSimulate::cast(instr);
     63     if (!current_simulate->is_candidate_for_removal()) {
     64       Remember(current_simulate);
     65       FlushSimulates();
     66     } else if (current_simulate->ast_id().IsNone()) {
     67       ASSERT(current_simulate->next()->IsEnterInlined());
     68       FlushSimulates();
     69     } else if (current_simulate->previous()->HasObservableSideEffects()) {
     70       Remember(current_simulate);
     71       mode_ = COLLECT_CONSECUTIVE_SIMULATES;
     72     } else {
     73       Remember(current_simulate);
     74     }
     75 
     76     return this;
     77   }
     78 
     79   static State* Merge(State* succ_state,
     80                       HBasicBlock* succ_block,
     81                       State* pred_state,
     82                       HBasicBlock* pred_block,
     83                       Zone* zone) {
     84     return (succ_state == NULL)
     85         ? pred_state->Copy(succ_block, pred_block, zone)
     86         : succ_state->Merge(succ_block, pred_state, pred_block, zone);
     87   }
     88 
     89   static State* Finish(State* state, HBasicBlock* block, Zone* zone) {
     90     if (FLAG_trace_removable_simulates) {
     91       PrintF("[preparing state %p for B%d]\n", reinterpret_cast<void*>(state),
     92              block->block_id());
     93     }
     94     // For our current local analysis, we should not remember simulates across
     95     // block boundaries.
     96     ASSERT(!state->HasRememberedSimulates());
     97     // Nasty heuristic: Never remove the first simulate in a block. This
     98     // just so happens to have a beneficial effect on register allocation.
     99     state->first_ = true;
    100     return state;
    101   }
    102 
    103  private:
    104   explicit State(const State& other)
    105       : zone_(other.zone_),
    106         mergelist_(other.mergelist_, other.zone_),
    107         first_(other.first_),
    108         mode_(other.mode_) { }
    109 
    110   enum Mode { NORMAL, COLLECT_CONSECUTIVE_SIMULATES };
    111 
    112   bool HasRememberedSimulates() const { return !mergelist_.is_empty(); }
    113 
    114   void Remember(HSimulate* sim) {
    115     mergelist_.Add(sim, zone_);
    116   }
    117 
    118   void FlushSimulates() {
    119     if (HasRememberedSimulates()) {
    120       mergelist_.RemoveLast()->MergeWith(&mergelist_);
    121     }
    122   }
    123 
    124   void RemoveSimulates() {
    125     while (HasRememberedSimulates()) {
    126       mergelist_.RemoveLast()->DeleteAndReplaceWith(NULL);
    127     }
    128   }
    129 
    130   State* Copy(HBasicBlock* succ_block, HBasicBlock* pred_block, Zone* zone) {
    131     State* copy = new(zone) State(*this);
    132     if (FLAG_trace_removable_simulates) {
    133       PrintF("[copy state %p from B%d to new state %p for B%d]\n",
    134              reinterpret_cast<void*>(this), pred_block->block_id(),
    135              reinterpret_cast<void*>(copy), succ_block->block_id());
    136     }
    137     return copy;
    138   }
    139 
    140   State* Merge(HBasicBlock* succ_block,
    141                State* pred_state,
    142                HBasicBlock* pred_block,
    143                Zone* zone) {
    144     // For our current local analysis, we should not remember simulates across
    145     // block boundaries.
    146     ASSERT(!pred_state->HasRememberedSimulates());
    147     ASSERT(!HasRememberedSimulates());
    148     if (FLAG_trace_removable_simulates) {
    149       PrintF("[merge state %p from B%d into %p for B%d]\n",
    150              reinterpret_cast<void*>(pred_state), pred_block->block_id(),
    151              reinterpret_cast<void*>(this), succ_block->block_id());
    152     }
    153     return this;
    154   }
    155 
    156   Zone* zone_;
    157   ZoneList<HSimulate*> mergelist_;
    158   bool first_;
    159   Mode mode_;
    160 };
    161 
    162 
    163 // We don't use effects here.
    164 class Effects : public ZoneObject {
    165  public:
    166   explicit Effects(Zone* zone) { }
    167   bool Disabled() { return true; }
    168   void Process(HInstruction* instr, Zone* zone) { }
    169   void Apply(State* state) { }
    170   void Union(Effects* that, Zone* zone) { }
    171 };
    172 
    173 
    174 void HMergeRemovableSimulatesPhase::Run() {
    175   HFlowEngine<State, Effects> engine(graph(), zone());
    176   State* state = new(zone()) State(zone());
    177   engine.AnalyzeDominatedBlocks(graph()->blocks()->at(0), state);
    178 }
    179 
    180 } }  // namespace v8::internal
    181