OLD | NEW |
(Empty) | |
| 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 |
| 35 namespace v8 { |
| 36 namespace internal { |
| 37 |
| 38 // An example implementation of effects that doesn't collect anything. |
| 39 class 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. |
| 60 class 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. |
| 90 template <class State, class Effects> |
| 91 class 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 StateAt(block); |
| 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 for (int i = 0; i < block->end()->SuccessorCount(); i++) { |
| 142 HBasicBlock* succ = block->end()->SuccessorAt(i); |
| 143 IncrementPredecessorCount(succ); |
| 144 if (StateAt(succ) == NULL) { |
| 145 // This is the first state to reach the successor. |
| 146 SetStateAt(succ, state->Copy(succ, zone_)); |
| 147 } else { |
| 148 // Merge the current state with the state already at the successor. |
| 149 SetStateAt(succ, state->Merge(succ, StateAt(succ), zone_)); |
| 150 } |
| 151 } |
| 152 } |
| 153 } |
| 154 |
| 155 private: |
| 156 // Computes and caches the loop effects for the loop which has the given |
| 157 // block as its loop header. |
| 158 Effects* ComputeLoopEffects(HBasicBlock* block) { |
| 159 ASSERT(block->IsLoopHeader()); |
| 160 Effects* effects = loop_effects_[block->block_id()]; |
| 161 if (effects != NULL) return effects; // Already analyzed this loop. |
| 162 |
| 163 effects = new(zone_) Effects(zone_); |
| 164 loop_effects_[block->block_id()] = effects; |
| 165 if (effects->Disabled()) return effects; // No effects for this analysis. |
| 166 |
| 167 HLoopInformation* loop = block->loop_information(); |
| 168 int end = loop->GetLastBackEdge()->block_id(); |
| 169 // Process the blocks between the header and the end. |
| 170 for (int i = block->block_id(); i <= end; i++) { |
| 171 HBasicBlock* member = graph_->blocks()->at(i); |
| 172 if (i != block->block_id() && member->IsLoopHeader()) { |
| 173 // Recursively compute and cache the effects of the nested loop. |
| 174 ASSERT(member->loop_information()->parent_loop() == loop); |
| 175 Effects* nested = ComputeLoopEffects(member); |
| 176 effects->Union(nested, zone_); |
| 177 // Skip the nested loop's blocks. |
| 178 i = member->loop_information()->GetLastBackEdge()->block_id(); |
| 179 } else { |
| 180 // Process all the effects of the block. |
| 181 ASSERT(member->current_loop() == loop); |
| 182 for (HInstructionIterator it(member); !it.Done(); it.Advance()) { |
| 183 effects->Process(it.Current(), zone_); |
| 184 } |
| 185 } |
| 186 } |
| 187 return effects; |
| 188 } |
| 189 |
| 190 inline bool SkipNonDominatedBlock(HBasicBlock* root, HBasicBlock* other) { |
| 191 if (root->block_id() == 0) return false; // Visit the whole graph. |
| 192 if (root == other) return false; // Always visit the root. |
| 193 return !root->Dominates(other); // Only visit dominated blocks. |
| 194 } |
| 195 |
| 196 inline State* StateAt(HBasicBlock* block) { |
| 197 return block_states_.at(block->block_id()); |
| 198 } |
| 199 |
| 200 inline void SetStateAt(HBasicBlock* block, State* state) { |
| 201 block_states_.Set(block->block_id(), state); |
| 202 } |
| 203 |
| 204 inline void InitializeStates() { |
| 205 #if DEBUG |
| 206 pred_counts_.Rewind(0); |
| 207 pred_counts_.AddBlock(0, graph_->blocks()->length(), zone_); |
| 208 #endif |
| 209 block_states_.Rewind(0); |
| 210 block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_); |
| 211 } |
| 212 |
| 213 inline void CheckPredecessorCount(HBasicBlock* block) { |
| 214 ASSERT(block->predecessors()->length() == pred_counts_[block->block_id()]); |
| 215 } |
| 216 |
| 217 inline void IncrementPredecessorCount(HBasicBlock* block) { |
| 218 #if DEBUG |
| 219 pred_counts_[block->block_id()]++; |
| 220 #endif |
| 221 } |
| 222 |
| 223 HGraph* graph_; // The hydrogen graph. |
| 224 Zone* zone_; // Temporary zone. |
| 225 #if DEBUG |
| 226 ZoneList<int> pred_counts_; // Finished predecessors (by block id). |
| 227 #endif |
| 228 ZoneList<State*> block_states_; // Block states (by block id). |
| 229 ZoneList<Effects*> loop_effects_; // Loop effects (by block id). |
| 230 }; |
| 231 |
| 232 |
| 233 } } // namespace v8::internal |
| 234 |
| 235 #endif // V8_HYDROGEN_FLOW_ENGINE_H_ |
OLD | NEW |