Home | History | Annotate | Download | only in src 
      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         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_
    220