1// Copyright 2013 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_FLOW_ENGINE_H_
29#define V8_HYDROGEN_FLOW_ENGINE_H_
30
31#include "hydrogen.h"
32#include "hydrogen-instructions.h"
33#include "zone.h"
34
35namespace v8 {
36namespace internal {
37
38// An example implementation of effects that doesn't collect anything.
39class NoEffects : public ZoneObject {
40 public:
41  explicit NoEffects(Zone* zone) { }
42
43  inline bool Disabled() {
44    return true;  // Nothing to do.
45  }
46  template <class State>
47  inline void Apply(State* state) {
48    // do nothing.
49  }
50  inline void Process(HInstruction* value, Zone* zone) {
51    // do nothing.
52  }
53  inline void Union(NoEffects* other, Zone* zone) {
54    // do nothing.
55  }
56};
57
58
59// An example implementation of state that doesn't track anything.
60class NoState {
61 public:
62  inline NoState* Copy(HBasicBlock* succ, Zone* zone) {
63    return this;
64  }
65  inline NoState* Process(HInstruction* value, Zone* zone) {
66    return this;
67  }
68  inline NoState* Merge(HBasicBlock* succ, NoState* other, Zone* zone) {
69    return this;
70  }
71};
72
73
74// This class implements an engine that can drive flow-sensitive analyses
75// over a graph of basic blocks, either one block at a time (local analysis)
76// or over the entire graph (global analysis). The flow engine is parameterized
77// by the type of the state and the effects collected while walking over the
78// graph.
79//
80// The "State" collects which facts are known while passing over instructions
81// in control flow order, and the "Effects" collect summary information about
82// which facts could be invalidated on other control flow paths. The effects
83// are necessary to correctly handle loops in the control flow graph without
84// doing a fixed-point iteration. Thus the flow engine is guaranteed to visit
85// each block at most twice; once for state, and optionally once for effects.
86//
87// The flow engine requires the State and Effects classes to implement methods
88// like the example NoState and NoEffects above. It's not necessary to provide
89// an effects implementation for local analysis.
90template <class State, class Effects>
91class HFlowEngine {
92 public:
93  HFlowEngine(HGraph* graph, Zone* zone)
94    : graph_(graph),
95      zone_(zone),
96#if DEBUG
97      pred_counts_(graph->blocks()->length(), zone),
98#endif
99      block_states_(graph->blocks()->length(), zone),
100      loop_effects_(graph->blocks()->length(), zone) {
101    loop_effects_.AddBlock(NULL, graph_->blocks()->length(), zone);
102  }
103
104  // Local analysis. Iterates over the instructions in the given block.
105  State* AnalyzeOneBlock(HBasicBlock* block, State* state) {
106    // Go through all instructions of the current block, updating the state.
107    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
108      state = state->Process(it.Current(), zone_);
109    }
110    return state;
111  }
112
113  // Global analysis. Iterates over all blocks that are dominated by the given
114  // block, starting with the initial state. Computes effects for nested loops.
115  void AnalyzeDominatedBlocks(HBasicBlock* root, State* initial) {
116    InitializeStates();
117    SetStateAt(root, initial);
118
119    // Iterate all dominated blocks starting from the given start block.
120    for (int i = root->block_id(); i < graph_->blocks()->length(); i++) {
121      HBasicBlock* block = graph_->blocks()->at(i);
122
123      // Skip blocks not dominated by the root node.
124      if (SkipNonDominatedBlock(root, block)) continue;
125      State* state = StateAt(block);
126
127      if (block->IsLoopHeader()) {
128        // Apply loop effects before analyzing loop body.
129        ComputeLoopEffects(block)->Apply(state);
130      } else {
131        // Must have visited all predecessors before this block.
132        CheckPredecessorCount(block);
133      }
134
135      // Go through all instructions of the current block, updating the state.
136      for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
137        state = state->Process(it.Current(), zone_);
138      }
139
140      // Propagate the block state forward to all successor blocks.
141      int max = block->end()->SuccessorCount();
142      for (int i = 0; i < max; i++) {
143        HBasicBlock* succ = block->end()->SuccessorAt(i);
144        IncrementPredecessorCount(succ);
145        if (StateAt(succ) == NULL) {
146          // This is the first state to reach the successor.
147          if (max == 1 && succ->predecessors()->length() == 1) {
148            // Optimization: successor can inherit this state.
149            SetStateAt(succ, state);
150          } else {
151            // Successor needs a copy of the state.
152            SetStateAt(succ, state->Copy(succ, zone_));
153          }
154        } else {
155          // Merge the current state with the state already at the successor.
156          SetStateAt(succ, state->Merge(succ, StateAt(succ), zone_));
157        }
158      }
159    }
160  }
161
162 private:
163  // Computes and caches the loop effects for the loop which has the given
164  // block as its loop header.
165  Effects* ComputeLoopEffects(HBasicBlock* block) {
166    ASSERT(block->IsLoopHeader());
167    Effects* effects = loop_effects_[block->block_id()];
168    if (effects != NULL) return effects;  // Already analyzed this loop.
169
170    effects = new(zone_) Effects(zone_);
171    loop_effects_[block->block_id()] = effects;
172    if (effects->Disabled()) return effects;  // No effects for this analysis.
173
174    HLoopInformation* loop = block->loop_information();
175    int end = loop->GetLastBackEdge()->block_id();
176    // Process the blocks between the header and the end.
177    for (int i = block->block_id(); i <= end; i++) {
178      HBasicBlock* member = graph_->blocks()->at(i);
179      if (i != block->block_id() && member->IsLoopHeader()) {
180        // Recursively compute and cache the effects of the nested loop.
181        ASSERT(member->loop_information()->parent_loop() == loop);
182        Effects* nested = ComputeLoopEffects(member);
183        effects->Union(nested, zone_);
184        // Skip the nested loop's blocks.
185        i = member->loop_information()->GetLastBackEdge()->block_id();
186      } else {
187        // Process all the effects of the block.
188        ASSERT(member->current_loop() == loop);
189        for (HInstructionIterator it(member); !it.Done(); it.Advance()) {
190          effects->Process(it.Current(), zone_);
191        }
192      }
193    }
194    return effects;
195  }
196
197  inline bool SkipNonDominatedBlock(HBasicBlock* root, HBasicBlock* other) {
198    if (root->block_id() == 0) return false;  // Visit the whole graph.
199    if (root == other) return false;          // Always visit the root.
200    return !root->Dominates(other);           // Only visit dominated blocks.
201  }
202
203  inline State* StateAt(HBasicBlock* block) {
204    return block_states_.at(block->block_id());
205  }
206
207  inline void SetStateAt(HBasicBlock* block, State* state) {
208    block_states_.Set(block->block_id(), state);
209  }
210
211  inline void InitializeStates() {
212#if DEBUG
213    pred_counts_.Rewind(0);
214    pred_counts_.AddBlock(0, graph_->blocks()->length(), zone_);
215#endif
216    block_states_.Rewind(0);
217    block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_);
218  }
219
220  inline void CheckPredecessorCount(HBasicBlock* block) {
221    ASSERT(block->predecessors()->length() == pred_counts_[block->block_id()]);
222  }
223
224  inline void IncrementPredecessorCount(HBasicBlock* block) {
225#if DEBUG
226    pred_counts_[block->block_id()]++;
227#endif
228  }
229
230  HGraph* graph_;                    // The hydrogen graph.
231  Zone* zone_;                       // Temporary zone.
232#if DEBUG
233  ZoneList<int> pred_counts_;        // Finished predecessors (by block id).
234#endif
235  ZoneList<State*> block_states_;    // Block states (by block id).
236  ZoneList<Effects*> loop_effects_;  // Loop effects (by block id).
237};
238
239
240} }  // namespace v8::internal
241
242#endif  // V8_HYDROGEN_FLOW_ENGINE_H_
243