Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(16)

Side by Side Diff: src/hydrogen-flow-engine.h

Issue 1405363003: Move Hydrogen and Lithium to src/crankshaft/ (Closed) Base URL: https://chromium.googlesource.com/v8/v8.git@master
Patch Set: rebased Created 5 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/hydrogen-escape-analysis.cc ('k') | src/hydrogen-gvn.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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 DCHECK(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 DCHECK(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 DCHECK(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 DCHECK(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 DCHECK(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 internal
218 } // namespace v8
219
220 #endif // V8_HYDROGEN_FLOW_ENGINE_H_
OLDNEW
« no previous file with comments | « src/hydrogen-escape-analysis.cc ('k') | src/hydrogen-gvn.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698