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