Line data Source code
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_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_
6 : #define V8_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_
7 :
8 : #include "src/crankshaft/hydrogen-instructions.h"
9 : #include "src/crankshaft/hydrogen.h"
10 : #include "src/zone/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 851189 : 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 851189 : loop_effects_(graph->blocks()->length(), zone) {
78 851189 : loop_effects_.AddBlock(NULL, graph_->blocks()->length(), zone);
79 851189 : }
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 1702365 : void AnalyzeDominatedBlocks(HBasicBlock* root, State* initial) {
93 851184 : InitializeStates();
94 : SetStateAt(root, initial);
95 :
96 : // Iterate all dominated blocks starting from the given start block.
97 14386118 : for (int i = root->block_id(); i < graph_->blocks()->length(); i++) {
98 42401560 : HBasicBlock* block = graph_->blocks()->at(i);
99 :
100 : // Skip blocks not dominated by the root node.
101 13534933 : if (SkipNonDominatedBlock(root, block)) continue;
102 4511633 : State* state = State::Finish(StateAt(block), block, zone_);
103 :
104 13534955 : if (block->IsReachable()) {
105 : DCHECK(state != NULL);
106 10403702 : if (block->IsLoopHeader()) {
107 : // Apply loop effects before analyzing loop body.
108 154590 : 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 79300827 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
116 68897134 : state = state->Process(it.Current(), zone_);
117 : }
118 : }
119 :
120 : // Propagate the block state forward to all successor blocks.
121 13534946 : int max = block->end()->SuccessorCount();
122 28866602 : for (int i = 0; i < max; i++) {
123 15331681 : HBasicBlock* succ = block->end()->SuccessorAt(i);
124 : IncrementPredecessorCount(succ);
125 :
126 15331669 : 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 19735244 : State::Merge(StateAt(succ), succ, state, block, zone_));
133 : }
134 : }
135 : }
136 851185 : }
137 :
138 : private:
139 : // Computes and caches the loop effects for the loop which has the given
140 : // block as its loop header.
141 2236745 : Effects* ComputeLoopEffects(HBasicBlock* block) {
142 : DCHECK(block->IsLoopHeader());
143 497397 : Effects* effects = loop_effects_[block->block_id()];
144 169642 : if (effects != NULL) return effects; // Already analyzed this loop.
145 :
146 264320 : effects = new(zone_) Effects(zone_);
147 158113 : loop_effects_[block->block_id()] = effects;
148 51906 : if (effects->Disabled()) return effects; // No effects for this analysis.
149 :
150 : HLoopInformation* loop = block->loop_information();
151 106207 : int end = loop->GetLastBackEdge()->block_id();
152 : // Process the blocks between the header and the end.
153 1802783 : for (int i = block->block_id(); i <= end; i++) {
154 3408204 : HBasicBlock* member = graph_->blocks()->at(i);
155 3286945 : 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 15052 : Effects* nested = ComputeLoopEffects(member);
159 15052 : effects->Union(nested, zone_);
160 : // Skip the nested loop's blocks.
161 15052 : i = member->loop_information()->GetLastBackEdge()->block_id();
162 : } else {
163 : // Process all the effects of the block.
164 1681524 : if (member->IsUnreachable()) continue;
165 : DCHECK(member->current_loop() == loop);
166 8387119 : for (HInstructionIterator it(member); !it.Done(); it.Advance()) {
167 7103054 : effects->Process(it.Current(), zone_);
168 : }
169 : }
170 : }
171 : return effects;
172 : }
173 :
174 13534931 : inline bool SkipNonDominatedBlock(HBasicBlock* root, HBasicBlock* other) {
175 13534931 : if (root->block_id() == 0) return false; // Visit the whole graph.
176 0 : if (root == other) return false; // Always visit the root.
177 0 : return !root->Dominates(other); // Only visit dominated blocks.
178 : }
179 :
180 23402552 : inline State* StateAt(HBasicBlock* block) {
181 23402552 : return block_states_.at(block->block_id());
182 : }
183 :
184 16182871 : inline void SetStateAt(HBasicBlock* block, State* state) {
185 16182871 : block_states_.Set(block->block_id(), state);
186 : }
187 :
188 851184 : 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 851184 : block_states_.AddBlock(NULL, graph_->blocks()->length(), zone_);
195 851184 : }
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_CRANKSHAFT_HYDROGEN_FLOW_ENGINE_H_
|
