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