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