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 3 // found in the LICENSE file. 4 5 #ifndef V8_COMPILER_CONTROL_EQUIVALENCE_H_ 6 #define V8_COMPILER_CONTROL_EQUIVALENCE_H_ 7 8 #include "src/compiler/graph.h" 9 #include "src/compiler/node.h" 10 #include "src/zone-containers.h" 11 12 namespace v8 { 13 namespace internal { 14 namespace compiler { 15 16 // Determines control dependence equivalence classes for control nodes. Any two 17 // nodes having the same set of control dependences land in one class. These 18 // classes can in turn be used to: 19 // - Build a program structure tree (PST) for controls in the graph. 20 // - Determine single-entry single-exit (SESE) regions within the graph. 21 // 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 24 // set of cycles. It can be shown that control dependence equivalence reduces 25 // to undirected cycle equivalence for strongly connected control flow graphs. 26 // 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 29 // also contains proofs for the aforementioned equivalence. References to line 30 // numbers in the algorithm from figure 4 have been added [line:x]. 31 class ControlEquivalence final : public ZoneObject { 32 public: ControlEquivalence(Zone * zone,Graph * graph)33 ControlEquivalence(Zone* zone, Graph* graph) 34 : zone_(zone), 35 graph_(graph), 36 dfs_number_(0), 37 class_number_(1), 38 node_data_(graph->NodeCount(), EmptyData(), zone) {} 39 40 // Run the main algorithm starting from the {exit} control node. This causes 41 // the following iterations over control edges of the graph: 42 // 1) A breadth-first backwards traversal to determine the set of nodes that 43 // participate in the next step. Takes O(E) time and O(N) space. 44 // 2) An undirected depth-first backwards traversal that determines class 45 // numbers for all participating nodes. Takes O(E) time and O(N) space. 46 void Run(Node* exit); 47 48 // Retrieves a previously computed class number. ClassOf(Node * node)49 size_t ClassOf(Node* node) { 50 DCHECK_NE(kInvalidClass, GetClass(node)); 51 return GetClass(node); 52 } 53 54 private: 55 static const size_t kInvalidClass = static_cast<size_t>(-1); 56 typedef enum { kInputDirection, kUseDirection } DFSDirection; 57 58 struct Bracket { 59 DFSDirection direction; // Direction in which this bracket was added. 60 size_t recent_class; // Cached class when bracket was topmost. 61 size_t recent_size; // Cached set-size when bracket was topmost. 62 Node* from; // Node that this bracket originates from. 63 Node* to; // Node that this bracket points to. 64 }; 65 66 // The set of brackets for each node during the DFS walk. 67 typedef ZoneLinkedList<Bracket> BracketList; 68 69 struct DFSStackEntry { 70 DFSDirection direction; // Direction currently used in DFS walk. 71 Node::InputEdges::iterator input; // Iterator used for "input" direction. 72 Node::UseEdges::iterator use; // Iterator used for "use" direction. 73 Node* parent_node; // Parent node of entry during DFS walk. 74 Node* node; // Node that this stack entry belongs to. 75 }; 76 77 // The stack is used during the undirected DFS walk. 78 typedef ZoneStack<DFSStackEntry> DFSStack; 79 80 struct NodeData { 81 size_t class_number; // Equivalence class number assigned to node. 82 size_t dfs_number; // Pre-order DFS number assigned to node. 83 bool visited; // Indicates node has already been visited. 84 bool on_stack; // Indicates node is on DFS stack during walk. 85 bool participates; // Indicates node participates in DFS walk. 86 BracketList blist; // List of brackets per node. 87 }; 88 89 // The per-node data computed during the DFS walk. 90 typedef ZoneVector<NodeData> Data; 91 92 // Called at pre-visit during DFS walk. 93 void VisitPre(Node* node); 94 95 // Called at mid-visit during DFS walk. 96 void VisitMid(Node* node, DFSDirection direction); 97 98 // Called at post-visit during DFS walk. 99 void VisitPost(Node* node, Node* parent_node, DFSDirection direction); 100 101 // Called when hitting a back edge in the DFS walk. 102 void VisitBackedge(Node* from, Node* to, DFSDirection direction); 103 104 // Performs and undirected DFS walk of the graph. Conceptually all nodes are 105 // expanded, splitting "input" and "use" out into separate nodes. During the 106 // traversal, edges towards the representative nodes are preferred. 107 // 108 // \ / - Pre-visit: When N1 is visited in direction D the preferred 109 // x N1 edge towards N is taken next, calling VisitPre(N). 110 // | - Mid-visit: After all edges out of N2 in direction D have 111 // | N been visited, we switch the direction and start considering 112 // | edges out of N1 now, and we call VisitMid(N). 113 // x N2 - Post-visit: After all edges out of N1 in direction opposite 114 // / \ to D have been visited, we pop N and call VisitPost(N). 115 // 116 // This will yield a true spanning tree (without cross or forward edges) and 117 // also discover proper back edges in both directions. 118 void RunUndirectedDFS(Node* exit); 119 120 void DetermineParticipationEnqueue(ZoneQueue<Node*>& queue, Node* node); 121 void DetermineParticipation(Node* exit); 122 123 private: GetData(Node * node)124 NodeData* GetData(Node* node) { return &node_data_[node->id()]; } NewClassNumber()125 int NewClassNumber() { return class_number_++; } NewDFSNumber()126 int NewDFSNumber() { return dfs_number_++; } 127 128 // Template used to initialize per-node data. EmptyData()129 NodeData EmptyData() { 130 return {kInvalidClass, 0, false, false, false, BracketList(zone_)}; 131 } 132 133 // Accessors for the DFS number stored within the per-node data. GetNumber(Node * node)134 size_t GetNumber(Node* node) { return GetData(node)->dfs_number; } SetNumber(Node * node,size_t number)135 void SetNumber(Node* node, size_t number) { 136 GetData(node)->dfs_number = number; 137 } 138 139 // Accessors for the equivalence class stored within the per-node data. GetClass(Node * node)140 size_t GetClass(Node* node) { return GetData(node)->class_number; } SetClass(Node * node,size_t number)141 void SetClass(Node* node, size_t number) { 142 GetData(node)->class_number = number; 143 } 144 145 // Accessors for the bracket list stored within the per-node data. GetBracketList(Node * node)146 BracketList& GetBracketList(Node* node) { return GetData(node)->blist; } SetBracketList(Node * node,BracketList & list)147 void SetBracketList(Node* node, BracketList& list) { 148 GetData(node)->blist = list; 149 } 150 151 // Mutates the DFS stack by pushing an entry. 152 void DFSPush(DFSStack& stack, Node* node, Node* from, DFSDirection dir); 153 154 // Mutates the DFS stack by popping an entry. 155 void DFSPop(DFSStack& stack, Node* node); 156 157 void BracketListDelete(BracketList& blist, Node* to, DFSDirection direction); 158 void BracketListTRACE(BracketList& blist); 159 160 Zone* const zone_; 161 Graph* const graph_; 162 int dfs_number_; // Generates new DFS pre-order 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. 165 }; 166 167 } // namespace compiler 168 } // namespace internal 169 } // namespace v8 170 171 #endif // V8_COMPILER_CONTROL_EQUIVALENCE_H_ 172