Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 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_HYDROGEN_FLOW_ENGINE_H_ |
| 6 | #define V8_HYDROGEN_FLOW_ENGINE_H_ |
| 7 | |
| 8 | #include "src/hydrogen.h" |
| 9 | #include "src/hydrogen-instructions.h" |
| 10 | #include "src/zone.h" |
| 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | |
| 15 | // An example implementation of effects that doesn't collect anything. |
| 16 | class 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. |
| 37 | class 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. |
| 67 | template <class State, class Effects> |
| 68 | class 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 v8::internal |
| 218 | |
| 219 | #endif // V8_HYDROGEN_FLOW_ENGINE_H_ |