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