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

   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 "hydrogen.h"
   9 #include "hydrogen-instructions.h"
  10 #include "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         ASSERT(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     ASSERT(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         ASSERT(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         ASSERT(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     ASSERT(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_