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
9namespace v8 {
10namespace internal {
11
12class 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    DCHECK(!(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      DCHECK(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    DCHECK(!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    DCHECK(!pred_state->HasRememberedSimulates());
147    DCHECK(!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.
164class 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
174void 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