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 #include <functional> 6 #include <limits> 7 8 #include "src/compiler/graph.h" 9 #include "src/compiler/graph-reducer.h" 10 #include "src/compiler/node.h" 11 #include "src/compiler/node-properties.h" 12 #include "src/compiler/verifier.h" 13 14 namespace v8 { 15 namespace internal { 16 namespace compiler { 17 18 enum class GraphReducer::State : uint8_t { 19 kUnvisited, 20 kRevisit, 21 kOnStack, 22 kVisited 23 }; 24 25 26 void Reducer::Finalize() {} 27 28 29 GraphReducer::GraphReducer(Zone* zone, Graph* graph, Node* dead) 30 : graph_(graph), 31 dead_(dead), 32 state_(graph, 4), 33 reducers_(zone), 34 revisit_(zone), 35 stack_(zone) {} 36 37 38 GraphReducer::~GraphReducer() {} 39 40 41 void GraphReducer::AddReducer(Reducer* reducer) { 42 reducers_.push_back(reducer); 43 } 44 45 46 void GraphReducer::ReduceNode(Node* node) { 47 DCHECK(stack_.empty()); 48 DCHECK(revisit_.empty()); 49 Push(node); 50 for (;;) { 51 if (!stack_.empty()) { 52 // Process the node on the top of the stack, potentially pushing more or 53 // popping the node off the stack. 54 ReduceTop(); 55 } else if (!revisit_.empty()) { 56 // If the stack becomes empty, revisit any nodes in the revisit queue. 57 Node* const node = revisit_.top(); 58 revisit_.pop(); 59 if (state_.Get(node) == State::kRevisit) { 60 // state can change while in queue. 61 Push(node); 62 } 63 } else { 64 // Run all finalizers. 65 for (Reducer* const reducer : reducers_) reducer->Finalize(); 66 67 // Check if we have new nodes to revisit. 68 if (revisit_.empty()) break; 69 } 70 } 71 DCHECK(revisit_.empty()); 72 DCHECK(stack_.empty()); 73 } 74 75 76 void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); } 77 78 79 Reduction GraphReducer::Reduce(Node* const node) { 80 auto skip = reducers_.end(); 81 for (auto i = reducers_.begin(); i != reducers_.end();) { 82 if (i != skip) { 83 Reduction reduction = (*i)->Reduce(node); 84 if (!reduction.Changed()) { 85 // No change from this reducer. 86 } else if (reduction.replacement() == node) { 87 // {replacement} == {node} represents an in-place reduction. Rerun 88 // all the other reducers for this node, as now there may be more 89 // opportunities for reduction. 90 skip = i; 91 i = reducers_.begin(); 92 continue; 93 } else { 94 // {node} was replaced by another node. 95 return reduction; 96 } 97 } 98 ++i; 99 } 100 if (skip == reducers_.end()) { 101 // No change from any reducer. 102 return Reducer::NoChange(); 103 } 104 // At least one reducer did some in-place reduction. 105 return Reducer::Changed(node); 106 } 107 108 109 void GraphReducer::ReduceTop() { 110 NodeState& entry = stack_.top(); 111 Node* node = entry.node; 112 DCHECK(state_.Get(node) == State::kOnStack); 113 114 if (node->IsDead()) return Pop(); // Node was killed while on stack. 115 116 // Recurse on an input if necessary. 117 int start = entry.input_index < node->InputCount() ? entry.input_index : 0; 118 for (int i = start; i < node->InputCount(); i++) { 119 Node* input = node->InputAt(i); 120 entry.input_index = i + 1; 121 if (input != node && Recurse(input)) return; 122 } 123 for (int i = 0; i < start; i++) { 124 Node* input = node->InputAt(i); 125 entry.input_index = i + 1; 126 if (input != node && Recurse(input)) return; 127 } 128 129 // Remember the max node id before reduction. 130 NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1); 131 132 // All inputs should be visited or on stack. Apply reductions to node. 133 Reduction reduction = Reduce(node); 134 135 // If there was no reduction, pop {node} and continue. 136 if (!reduction.Changed()) return Pop(); 137 138 // Check if the reduction is an in-place update of the {node}. 139 Node* const replacement = reduction.replacement(); 140 if (replacement == node) { 141 // In-place update of {node}, may need to recurse on an input. 142 for (int i = 0; i < node->InputCount(); ++i) { 143 Node* input = node->InputAt(i); 144 entry.input_index = i + 1; 145 if (input != node && Recurse(input)) return; 146 } 147 } 148 149 // After reducing the node, pop it off the stack. 150 Pop(); 151 152 // Check if we have a new replacement. 153 if (replacement != node) { 154 Replace(node, replacement, max_id); 155 } else { 156 // Revisit all uses of the node. 157 for (Node* const user : node->uses()) { 158 // Don't revisit this node if it refers to itself. 159 if (user != node) Revisit(user); 160 } 161 } 162 } 163 164 165 void GraphReducer::Replace(Node* node, Node* replacement) { 166 Replace(node, replacement, std::numeric_limits<NodeId>::max()); 167 } 168 169 170 void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) { 171 if (node == graph()->start()) graph()->SetStart(replacement); 172 if (node == graph()->end()) graph()->SetEnd(replacement); 173 if (replacement->id() <= max_id) { 174 // {replacement} is an old node, so unlink {node} and assume that 175 // {replacement} was already reduced and finish. 176 for (Edge edge : node->use_edges()) { 177 Node* const user = edge.from(); 178 Verifier::VerifyEdgeInputReplacement(edge, replacement); 179 edge.UpdateTo(replacement); 180 // Don't revisit this node if it refers to itself. 181 if (user != node) Revisit(user); 182 } 183 node->Kill(); 184 } else { 185 // Replace all old uses of {node} with {replacement}, but allow new nodes 186 // created by this reduction to use {node}. 187 for (Edge edge : node->use_edges()) { 188 Node* const user = edge.from(); 189 if (user->id() <= max_id) { 190 edge.UpdateTo(replacement); 191 // Don't revisit this node if it refers to itself. 192 if (user != node) Revisit(user); 193 } 194 } 195 // Unlink {node} if it's no longer used. 196 if (node->uses().empty()) node->Kill(); 197 198 // If there was a replacement, reduce it after popping {node}. 199 Recurse(replacement); 200 } 201 } 202 203 204 void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect, 205 Node* control) { 206 if (effect == nullptr && node->op()->EffectInputCount() > 0) { 207 effect = NodeProperties::GetEffectInput(node); 208 } 209 if (control == nullptr && node->op()->ControlInputCount() > 0) { 210 control = NodeProperties::GetControlInput(node); 211 } 212 213 // Requires distinguishing between value, effect and control edges. 214 for (Edge edge : node->use_edges()) { 215 Node* const user = edge.from(); 216 DCHECK(!user->IsDead()); 217 if (NodeProperties::IsControlEdge(edge)) { 218 if (user->opcode() == IrOpcode::kIfSuccess) { 219 Replace(user, control); 220 } else if (user->opcode() == IrOpcode::kIfException) { 221 DCHECK_NOT_NULL(dead_); 222 edge.UpdateTo(dead_); 223 Revisit(user); 224 } else { 225 DCHECK_NOT_NULL(control); 226 edge.UpdateTo(control); 227 Revisit(user); 228 // TODO(jarin) Check that the node cannot throw (otherwise, it 229 // would have to be connected via IfSuccess/IfException). 230 } 231 } else if (NodeProperties::IsEffectEdge(edge)) { 232 DCHECK_NOT_NULL(effect); 233 edge.UpdateTo(effect); 234 Revisit(user); 235 } else { 236 DCHECK_NOT_NULL(value); 237 edge.UpdateTo(value); 238 Revisit(user); 239 } 240 } 241 } 242 243 244 void GraphReducer::Pop() { 245 Node* node = stack_.top().node; 246 state_.Set(node, State::kVisited); 247 stack_.pop(); 248 } 249 250 251 void GraphReducer::Push(Node* const node) { 252 DCHECK(state_.Get(node) != State::kOnStack); 253 state_.Set(node, State::kOnStack); 254 stack_.push({node, 0}); 255 } 256 257 258 bool GraphReducer::Recurse(Node* node) { 259 if (state_.Get(node) > State::kRevisit) return false; 260 Push(node); 261 return true; 262 } 263 264 265 void GraphReducer::Revisit(Node* node) { 266 if (state_.Get(node) == State::kVisited) { 267 state_.Set(node, State::kRevisit); 268 revisit_.push(node); 269 } 270 } 271 272 } // namespace compiler 273 } // namespace internal 274 } // namespace v8 275