blob: 149c99bec5e417b1c0affbef2464d6b2cab00b0b [file] [log] [blame]
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_
#define V8_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_
#include "src/crankshaft/hydrogen-instructions.h"
#include "src/crankshaft/hydrogen.h"
#include "src/zone/zone.h"
namespace v8 {
namespace internal {
// An example implementation of effects that doesn't collect anything.
class NoEffects : public ZoneObject {
public:
explicit NoEffects(Zone* zone) { }
inline bool Disabled() {
return true; // Nothing to do.
}
template <class State>
inline void Apply(State* state) {
// do nothing.
}
inline void Process(HInstruction* value, Zone* zone) {
// do nothing.
}
inline void Union(NoEffects* other, Zone* zone) {
// do nothing.
}
};
// An example implementation of state that doesn't track anything.
class NoState {
public:
inline NoState* Copy(HBasicBlock* succ, Zone* zone) {
return this;
}
inline NoState* Process(HInstruction* value, Zone* zone) {
return this;
}
inline NoState* Merge(HBasicBlock* succ, NoState* other, Zone* zone) {
return this;
}
};
// This class implements an engine that can drive flow-sensitive analyses
// over a graph of basic blocks, either one block at a time (local analysis)
// or over the entire graph (global analysis). The flow engine is parameterized
// by the type of the state and the effects collected while walking over the
// graph.
//
// The "State" collects which facts are known while passing over instructions
// in control flow order, and the "Effects" collect summary information about
// which facts could be invalidated on other control flow paths. The effects
// are necessary to correctly handle loops in the control flow graph without
// doing a fixed-point iteration. Thus the flow engine is guaranteed to visit
// each block at most twice; once for state, and optionally once for effects.
//
// The flow engine requires the State and Effects classes to implement methods
// like the example NoState and NoEffects above. It's not necessary to provide
// an effects implementation for local analysis.
template <class State, class Effects>
class HFlowEngine {
public:
HFlowEngine(HGraph* graph, Zone* zone)
: graph_(graph),
zone_(zone),
#if DEBUG
pred_counts_(graph->blocks()->length(), zone),
#endif
block_states_(graph->blocks()->length(), zone),
loop_effects_(graph->blocks()->length(), zone) {
loop_effects_.AddBlock(NULL, graph_->blocks()->length(), zone);
}
// Local analysis. Iterates over the instructions in the given block.
State* AnalyzeOneBlock(HBasicBlock* block, State* state) {
// Go through all instructions of the current block, updating the state.
for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
state = state->Process(it.Current(), zone_);
}
return state;
}
// Global analysis. Iterates over all blocks that are dominated by the given
// block, starting with the initial state. Computes effects for nested loops.
void AnalyzeDominatedBlocks(HBasicBlock* root, State* initial) {
InitializeStates();
SetStateAt(root, initial);
// Iterate all dominated blocks starting from the given start block.
for (int i = root->block_id(); i < graph_->blocks()->length(); i++) {
HBasicBlock* block = graph_->blocks()->at(i);
// Skip blocks not dominated by the root node.
if (SkipNonDominatedBlock(root, block)) continue;
State* state = State::Finish(StateAt(block), block, zone_);
if (block->IsReachable()) {
DCHECK(state != NULL);
if (block->IsLoopHeader()) {
// Apply loop effects before analyzing loop body.
ComputeLoopEffects(block)->Apply(state);
} else {
// Must have visited all predecessors before this block.
CheckPredecessorCount(block);
}
// Go through all instructions of the current block, updating the state.
for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
state = state->Process(it.Current(), zone_);
}
}
// Propagate the block state forward to all successor blocks.
int max = block->end()->SuccessorCount();
for (int i = 0; i < max; i++) {
HBasicBlock* succ = block->end()->SuccessorAt(i);
IncrementPredecessorCount(succ);
if (max == 1 && succ->predecessors()->length() == 1) {
// Optimization: successor can inherit this state.
SetStateAt(succ, state);
} else {
// Merge the current state with the state already at the successor.
SetStateAt(succ,
State::Merge(StateAt(succ), succ, state, block, zone_));
}
}
}
}
private:
// Computes and caches the loop effects for the loop which has the given
// block as its loop header.
Effects* ComputeLoopEffects(HBasicBlock* block) {
DCHECK(block->IsLoopHeader());
Effects* effects = loop_effects_[block->block_id()];
if (effects != NULL) return effects; // Already analyzed this loop.
effects = new(zone_) Effects(zone_);
loop_effects_[block->block_id()] = effects;
if (effects->Disabled()) return effects; // No effects for this analysis.
HLoopInformation* loop = block->loop_information();
int end = loop->GetLastBackEdge()->block_id();
// Process the blocks between the header and the end.
for (int i = block->block_id(); i <= end; i++) {
HBasicBlock* member = graph_->blocks()->at(i);
if (i != block->block_id() && member->IsLoopHeader()) {
// Recursively compute and cache the effects of the nested loop.
DCHECK(member->loop_information()->parent_loop() == loop);
Effects* nested = ComputeLoopEffects(member);
effects->Union(nested, zone_);
// Skip the nested loop's blocks.
i = member->loop_information()->GetLastBackEdge()->block_id();
} else {
// Process all the effects of the block.
if (member->IsUnreachable()) continue;
DCHECK(member->current_loop() == loop);
for (HInstructionIterator it(member); !it.Done(); it.Advance()) {
effects->Process(it.Current(), zone_);
}
}
}
return effects;
}
inline bool SkipNonDominatedBlock(HBasicBlock* root, HBasicBlock* other) {
if (root->block_id() == 0) return false; // Visit the whole graph.
if (root == other) return false; // Always visit the root.
return !root->Dominates(other); // Only visit dominated blocks.
}
inline State* StateAt(HBasicBlock* block) {
return block_states_.at(block->block_id());
}
inline void SetStateAt(HBasicBlock* block, State* state) {
block_states_.Set(block->block_id(), state);
}
inline void InitializeStates() {
#if DEBUG
pred_counts_.Rewind(0);
pred_counts_.AddBlock(0, graph_->blocks()->length(), zone_);
#endif
block_states_.Rewind(0);
block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_);
}
inline void CheckPredecessorCount(HBasicBlock* block) {
DCHECK(block->predecessors()->length() == pred_counts_[block->block_id()]);
}
inline void IncrementPredecessorCount(HBasicBlock* block) {
#if DEBUG
pred_counts_[block->block_id()]++;
#endif
}
HGraph* graph_; // The hydrogen graph.
Zone* zone_; // Temporary zone.
#if DEBUG
ZoneList<int> pred_counts_; // Finished predecessors (by block id).
#endif
ZoneList<State*> block_states_; // Block states (by block id).
ZoneList<Effects*> loop_effects_; // Loop effects (by block id).
};
} // namespace internal
} // namespace v8
#endif // V8_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_