src/v8/src/hydrogen-flow-engine.h

   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 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->IsReachable()) {
 128         if (block->IsLoopHeader()) {
 129           // Apply loop effects before analyzing loop body.
 130           ComputeLoopEffects(block)->Apply(state);
 131         } else {
 132           // Must have visited all predecessors before this block.
 133           CheckPredecessorCount(block);
 134         }
 135
 136         // Go through all instructions of the current block, updating the state.
 137         for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
 138           state = state->Process(it.Current(), zone_);
 139         }
 140       }
 141
 142       // Propagate the block state forward to all successor blocks.
 143       int max = block->end()->SuccessorCount();
 144       for (int i = 0; i < max; i++) {
 145         HBasicBlock* succ = block->end()->SuccessorAt(i);
 146         IncrementPredecessorCount(succ);
 147         if (StateAt(succ) == NULL) {
 148           // This is the first state to reach the successor.
 149           if (max == 1 && succ->predecessors()->length() == 1) {
 150             // Optimization: successor can inherit this state.
 151             SetStateAt(succ, state);
 152           } else {
 153             // Successor needs a copy of the state.
 154             SetStateAt(succ, state->Copy(succ, block, zone_));
 155           }
 156         } else {
 157           // Merge the current state with the state already at the successor.
 158           SetStateAt(succ, StateAt(succ)->Merge(succ, state, block, zone_));
 159         }
 160       }
 161     }
 162   }
 163
 164  private:
 165   // Computes and caches the loop effects for the loop which has the given
 166   // block as its loop header.
 167   Effects* ComputeLoopEffects(HBasicBlock* block) {
 168     ASSERT(block->IsLoopHeader());
 169     Effects* effects = loop_effects_[block->block_id()];
 170     if (effects != NULL) return effects;  // Already analyzed this loop.
 171
 172     effects = new(zone_) Effects(zone_);
 173     loop_effects_[block->block_id()] = effects;
 174     if (effects->Disabled()) return effects;  // No effects for this analysis.
 175
 176     HLoopInformation* loop = block->loop_information();
 177     int end = loop->GetLastBackEdge()->block_id();
 178     // Process the blocks between the header and the end.
 179     for (int i = block->block_id(); i <= end; i++) {
 180       HBasicBlock* member = graph_->blocks()->at(i);
 181       if (i != block->block_id() && member->IsLoopHeader()) {
 182         // Recursively compute and cache the effects of the nested loop.
 183         ASSERT(member->loop_information()->parent_loop() == loop);
 184         Effects* nested = ComputeLoopEffects(member);
 185         effects->Union(nested, zone_);
 186         // Skip the nested loop's blocks.
 187         i = member->loop_information()->GetLastBackEdge()->block_id();
 188       } else {
 189         // Process all the effects of the block.
 190         if (member->IsUnreachable()) continue;
 191         ASSERT(member->current_loop() == loop);
 192         for (HInstructionIterator it(member); !it.Done(); it.Advance()) {
 193           effects->Process(it.Current(), zone_);
 194         }
 195       }
 196     }
 197     return effects;
 198   }
 199
 200   inline bool SkipNonDominatedBlock(HBasicBlock* root, HBasicBlock* other) {
 201     if (root->block_id() == 0) return false;  // Visit the whole graph.
 202     if (root == other) return false;          // Always visit the root.
 203     return !root->Dominates(other);           // Only visit dominated blocks.
 204   }
 205
 206   inline State* StateAt(HBasicBlock* block) {
 207     return block_states_.at(block->block_id());
 208   }
 209
 210   inline void SetStateAt(HBasicBlock* block, State* state) {
 211     block_states_.Set(block->block_id(), state);
 212   }
 213
 214   inline void InitializeStates() {
 215 #if DEBUG
 216     pred_counts_.Rewind(0);
 217     pred_counts_.AddBlock(0, graph_->blocks()->length(), zone_);
 218 #endif
 219     block_states_.Rewind(0);
 220     block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_);
 221   }
 222
 223   inline void CheckPredecessorCount(HBasicBlock* block) {
 224     ASSERT(block->predecessors()->length() == pred_counts_[block->block_id()]);
 225   }
 226
 227   inline void IncrementPredecessorCount(HBasicBlock* block) {
 228 #if DEBUG
 229     pred_counts_[block->block_id()]++;
 230 #endif
 231   }
 232
 233   HGraph* graph_;                    // The hydrogen graph.
 234   Zone* zone_;                       // Temporary zone.
 235 #if DEBUG
 236   ZoneList<int> pred_counts_;        // Finished predecessors (by block id).
 237 #endif
 238   ZoneList<State*> block_states_;    // Block states (by block id).
 239   ZoneList<Effects*> loop_effects_;  // Loop effects (by block id).
 240 };
 241
 242
 243 } }  // namespace v8::internal
 244
 245 #endif  // V8_HYDROGEN_FLOW_ENGINE_H_