Revision: 17159
Author: [email protected]
Date: Fri Oct 11 13:00:42 2013 UTC
Log: Implement first version of HFlowEngine, a framework for
performing global flow-sensitive analyses.
BUG=
[email protected]
Review URL: https://codereview.chromium.org/25254002
http://code.google.com/p/v8/source/detail?r=17159
Added:
/branches/bleeding_edge/src/hydrogen-flow-engine.h
Modified:
/branches/bleeding_edge/tools/gyp/v8.gyp
=======================================
--- /dev/null
+++ /branches/bleeding_edge/src/hydrogen-flow-engine.h Fri Oct 11 13:00:42
2013 UTC
@@ -0,0 +1,235 @@
+// Copyright 2013 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_HYDROGEN_FLOW_ENGINE_H_
+#define V8_HYDROGEN_FLOW_ENGINE_H_
+
+#include "hydrogen.h"
+#include "hydrogen-instructions.h"
+#include "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 StateAt(block);
+ }
+
+ // 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 = StateAt(block);
+
+ 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.
+ for (int i = 0; i < block->end()->SuccessorCount(); i++) {
+ HBasicBlock* succ = block->end()->SuccessorAt(i);
+ IncrementPredecessorCount(succ);
+ if (StateAt(succ) == NULL) {
+ // This is the first state to reach the successor.
+ SetStateAt(succ, state->Copy(succ, zone_));
+ } else {
+ // Merge the current state with the state already at the
successor.
+ SetStateAt(succ, state->Merge(succ, StateAt(succ), zone_));
+ }
+ }
+ }
+ }
+
+ private:
+ // Computes and caches the loop effects for the loop which has the given
+ // block as its loop header.
+ Effects* ComputeLoopEffects(HBasicBlock* block) {
+ ASSERT(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.
+ ASSERT(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.
+ ASSERT(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) {
+ ASSERT(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 v8::internal
+
+#endif // V8_HYDROGEN_FLOW_ENGINE_H_
=======================================
--- /branches/bleeding_edge/tools/gyp/v8.gyp Fri Oct 4 14:53:16 2013 UTC
+++ /branches/bleeding_edge/tools/gyp/v8.gyp Fri Oct 11 13:00:42 2013 UTC
@@ -344,6 +344,7 @@
'../../src/hydrogen-environment-liveness.h',
'../../src/hydrogen-escape-analysis.cc',
'../../src/hydrogen-escape-analysis.h',
+ '../../src/hydrogen-flow-engine.h',
'../../src/hydrogen-instructions.cc',
'../../src/hydrogen-instructions.h',
'../../src/hydrogen.cc',
--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
