OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_ | 5 #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_ |
6 #define V8_COMPILER_CONTROL_EQUIVALENCE_H_ | 6 #define V8_COMPILER_CONTROL_EQUIVALENCE_H_ |
7 | 7 |
8 #include "src/compiler/graph.h" | 8 #include "src/compiler/graph.h" |
9 #include "src/compiler/node.h" | 9 #include "src/compiler/node.h" |
10 #include "src/zone-containers.h" | 10 #include "src/zone-containers.h" |
(...skipping 10 matching lines...) Expand all Loading... |
21 // | 21 // |
22 // Note that this implementation actually uses cycle equivalence to establish | 22 // Note that this implementation actually uses cycle equivalence to establish |
23 // class numbers. Any two nodes are cycle equivalent if they occur in the same | 23 // class numbers. Any two nodes are cycle equivalent if they occur in the same |
24 // set of cycles. It can be shown that control dependence equivalence reduces | 24 // set of cycles. It can be shown that control dependence equivalence reduces |
25 // to undirected cycle equivalence for strongly connected control flow graphs. | 25 // to undirected cycle equivalence for strongly connected control flow graphs. |
26 // | 26 // |
27 // The algorithm is based on the paper, "The program structure tree: computing | 27 // The algorithm is based on the paper, "The program structure tree: computing |
28 // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which | 28 // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which |
29 // also contains proofs for the aforementioned equivalence. References to line | 29 // also contains proofs for the aforementioned equivalence. References to line |
30 // numbers in the algorithm from figure 4 have been added [line:x]. | 30 // numbers in the algorithm from figure 4 have been added [line:x]. |
31 class ControlEquivalence FINAL : public ZoneObject { | 31 class ControlEquivalence final : public ZoneObject { |
32 public: | 32 public: |
33 ControlEquivalence(Zone* zone, Graph* graph) | 33 ControlEquivalence(Zone* zone, Graph* graph) |
34 : zone_(zone), | 34 : zone_(zone), |
35 graph_(graph), | 35 graph_(graph), |
36 dfs_number_(0), | 36 dfs_number_(0), |
37 class_number_(1), | 37 class_number_(1), |
38 node_data_(graph->NodeCount(), EmptyData(), zone) {} | 38 node_data_(graph->NodeCount(), EmptyData(), zone) {} |
39 | 39 |
40 // Run the main algorithm starting from the {exit} control node. This causes | 40 // Run the main algorithm starting from the {exit} control node. This causes |
41 // the following iterations over control edges of the graph: | 41 // the following iterations over control edges of the graph: |
(...skipping 120 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
162 int dfs_number_; // Generates new DFS pre-order numbers on demand. | 162 int dfs_number_; // Generates new DFS pre-order numbers on demand. |
163 int class_number_; // Generates new equivalence class numbers on demand. | 163 int class_number_; // Generates new equivalence class numbers on demand. |
164 Data node_data_; // Per-node data stored as a side-table. | 164 Data node_data_; // Per-node data stored as a side-table. |
165 }; | 165 }; |
166 | 166 |
167 } // namespace compiler | 167 } // namespace compiler |
168 } // namespace internal | 168 } // namespace internal |
169 } // namespace v8 | 169 } // namespace v8 |
170 | 170 |
171 #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ | 171 #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ |
OLD | NEW |