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.
5 #ifndef V8_HYDROGEN_FLOW_ENGINE_H_
6 #define V8_HYDROGEN_FLOW_ENGINE_H_
8 #include "src/hydrogen.h"
9 #include "src/hydrogen-instructions.h"
15 // An example implementation of effects that doesn't collect anything.
16 class NoEffects : public ZoneObject {
18 explicit NoEffects(Zone* zone) { }
20 inline bool Disabled() {
21 return true; // Nothing to do.
23 template <class State>
24 inline void Apply(State* state) {
27 inline void Process(HInstruction* value, Zone* zone) {
30 inline void Union(NoEffects* other, Zone* zone) {
36 // An example implementation of state that doesn't track anything.
39 inline NoState* Copy(HBasicBlock* succ, Zone* zone) {
42 inline NoState* Process(HInstruction* value, Zone* zone) {
45 inline NoState* Merge(HBasicBlock* succ, NoState* other, Zone* zone) {
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
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.
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.
67 template <class State, class Effects>
70 HFlowEngine(HGraph* graph, Zone* zone)
74 pred_counts_(graph->blocks()->length(), zone),
76 block_states_(graph->blocks()->length(), zone),
77 loop_effects_(graph->blocks()->length(), zone) {
78 loop_effects_.AddBlock(NULL, graph_->blocks()->length(), zone);
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_);
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) {
94 SetStateAt(root, initial);
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);
100 // Skip blocks not dominated by the root node.
101 if (SkipNonDominatedBlock(root, block)) continue;
102 State* state = State::Finish(StateAt(block), block, zone_);
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);
110 // Must have visited all predecessors before this block.
111 CheckPredecessorCount(block);
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_);
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);
126 if (max == 1 && succ->predecessors()->length() == 1) {
127 // Optimization: successor can inherit this state.
128 SetStateAt(succ, state);
130 // Merge the current state with the state already at the successor.
132 State::Merge(StateAt(succ), succ, state, block, zone_));
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.
146 effects = new(zone_) Effects(zone_);
147 loop_effects_[block->block_id()] = effects;
148 if (effects->Disabled()) return effects; // No effects for this analysis.
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();
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_);
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.
180 inline State* StateAt(HBasicBlock* block) {
181 return block_states_.at(block->block_id());
184 inline void SetStateAt(HBasicBlock* block, State* state) {
185 block_states_.Set(block->block_id(), state);
188 inline void InitializeStates() {
190 pred_counts_.Rewind(0);
191 pred_counts_.AddBlock(0, graph_->blocks()->length(), zone_);
193 block_states_.Rewind(0);
194 block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_);
197 inline void CheckPredecessorCount(HBasicBlock* block) {
198 DCHECK(block->predecessors()->length() == pred_counts_[block->block_id()]);
201 inline void IncrementPredecessorCount(HBasicBlock* block) {
203 pred_counts_[block->block_id()]++;
207 HGraph* graph_; // The hydrogen graph.
208 Zone* zone_; // Temporary zone.
210 ZoneList<int> pred_counts_; // Finished predecessors (by block id).
212 ZoneList<State*> block_states_; // Block states (by block id).
213 ZoneList<Effects*> loop_effects_; // Loop effects (by block id).
217 } } // namespace v8::internal
219 #endif // V8_HYDROGEN_FLOW_ENGINE_H_