| 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/base/compiler-specific.h" |
| 8 #include "src/compiler/graph.h" | 9 #include "src/compiler/graph.h" |
| 9 #include "src/compiler/node.h" | 10 #include "src/compiler/node.h" |
| 11 #include "src/globals.h" |
| 10 #include "src/zone/zone-containers.h" | 12 #include "src/zone/zone-containers.h" |
| 11 | 13 |
| 12 namespace v8 { | 14 namespace v8 { |
| 13 namespace internal { | 15 namespace internal { |
| 14 namespace compiler { | 16 namespace compiler { |
| 15 | 17 |
| 16 // Determines control dependence equivalence classes for control nodes. Any two | 18 // Determines control dependence equivalence classes for control nodes. Any two |
| 17 // nodes having the same set of control dependences land in one class. These | 19 // nodes having the same set of control dependences land in one class. These |
| 18 // classes can in turn be used to: | 20 // classes can in turn be used to: |
| 19 // - Build a program structure tree (PST) for controls in the graph. | 21 // - Build a program structure tree (PST) for controls in the graph. |
| 20 // - Determine single-entry single-exit (SESE) regions within the graph. | 22 // - Determine single-entry single-exit (SESE) regions within the graph. |
| 21 // | 23 // |
| 22 // Note that this implementation actually uses cycle equivalence to establish | 24 // 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 | 25 // 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 | 26 // set of cycles. It can be shown that control dependence equivalence reduces |
| 25 // to undirected cycle equivalence for strongly connected control flow graphs. | 27 // to undirected cycle equivalence for strongly connected control flow graphs. |
| 26 // | 28 // |
| 27 // The algorithm is based on the paper, "The program structure tree: computing | 29 // The algorithm is based on the paper, "The program structure tree: computing |
| 28 // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which | 30 // control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which |
| 29 // also contains proofs for the aforementioned equivalence. References to line | 31 // also contains proofs for the aforementioned equivalence. References to line |
| 30 // numbers in the algorithm from figure 4 have been added [line:x]. | 32 // numbers in the algorithm from figure 4 have been added [line:x]. |
| 31 class ControlEquivalence final : public ZoneObject { | 33 class V8_EXPORT_PRIVATE ControlEquivalence final |
| 34 : public NON_EXPORTED_BASE(ZoneObject) { |
| 32 public: | 35 public: |
| 33 ControlEquivalence(Zone* zone, Graph* graph) | 36 ControlEquivalence(Zone* zone, Graph* graph) |
| 34 : zone_(zone), | 37 : zone_(zone), |
| 35 graph_(graph), | 38 graph_(graph), |
| 36 dfs_number_(0), | 39 dfs_number_(0), |
| 37 class_number_(1), | 40 class_number_(1), |
| 38 node_data_(graph->NodeCount(), EmptyData(), zone) {} | 41 node_data_(graph->NodeCount(), EmptyData(), zone) {} |
| 39 | 42 |
| 40 // Run the main algorithm starting from the {exit} control node. This causes | 43 // Run the main algorithm starting from the {exit} control node. This causes |
| 41 // the following iterations over control edges of the graph: | 44 // 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. | 165 int dfs_number_; // Generates new DFS pre-order numbers on demand. |
| 163 int class_number_; // Generates new equivalence class numbers on demand. | 166 int class_number_; // Generates new equivalence class numbers on demand. |
| 164 Data node_data_; // Per-node data stored as a side-table. | 167 Data node_data_; // Per-node data stored as a side-table. |
| 165 }; | 168 }; |
| 166 | 169 |
| 167 } // namespace compiler | 170 } // namespace compiler |
| 168 } // namespace internal | 171 } // namespace internal |
| 169 } // namespace v8 | 172 } // namespace v8 |
| 170 | 173 |
| 171 #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ | 174 #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ |
| OLD | NEW |