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 14namespace v8 { 15namespace internal { 16namespace compiler { 17 18enum class GraphReducer::State : uint8_t { 19 kUnvisited, 20 kRevisit, 21 kOnStack, 22 kVisited 23}; 24 25 26void Reducer::Finalize() {} 27 28GraphReducer::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 40GraphReducer::~GraphReducer() {} 41 42 43void GraphReducer::AddReducer(Reducer* reducer) { 44 reducers_.push_back(reducer); 45} 46 47 48void 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_.top(); 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 78void GraphReducer::ReduceGraph() { ReduceNode(graph()->end()); } 79 80 81Reduction 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 skip = i; 93 i = reducers_.begin(); 94 continue; 95 } else { 96 // {node} was replaced by another node. 97 return reduction; 98 } 99 } 100 ++i; 101 } 102 if (skip == reducers_.end()) { 103 // No change from any reducer. 104 return Reducer::NoChange(); 105 } 106 // At least one reducer did some in-place reduction. 107 return Reducer::Changed(node); 108} 109 110 111void GraphReducer::ReduceTop() { 112 NodeState& entry = stack_.top(); 113 Node* node = entry.node; 114 DCHECK(state_.Get(node) == State::kOnStack); 115 116 if (node->IsDead()) return Pop(); // Node was killed while on stack. 117 118 Node::Inputs node_inputs = node->inputs(); 119 120 // Recurse on an input if necessary. 121 int start = entry.input_index < node_inputs.count() ? entry.input_index : 0; 122 for (int i = start; i < node_inputs.count(); ++i) { 123 Node* input = node_inputs[i]; 124 if (input != node && Recurse(input)) { 125 entry.input_index = i + 1; 126 return; 127 } 128 } 129 for (int i = 0; i < start; ++i) { 130 Node* input = node_inputs[i]; 131 if (input != node && Recurse(input)) { 132 entry.input_index = i + 1; 133 return; 134 } 135 } 136 137 // Remember the max node id before reduction. 138 NodeId const max_id = static_cast<NodeId>(graph()->NodeCount() - 1); 139 140 // All inputs should be visited or on stack. Apply reductions to node. 141 Reduction reduction = Reduce(node); 142 143 // If there was no reduction, pop {node} and continue. 144 if (!reduction.Changed()) return Pop(); 145 146 // Check if the reduction is an in-place update of the {node}. 147 Node* const replacement = reduction.replacement(); 148 if (replacement == node) { 149 // In-place update of {node}, may need to recurse on an input. 150 Node::Inputs node_inputs = node->inputs(); 151 for (int i = 0; i < node_inputs.count(); ++i) { 152 Node* input = node_inputs[i]; 153 if (input != node && Recurse(input)) { 154 entry.input_index = i + 1; 155 return; 156 } 157 } 158 } 159 160 // After reducing the node, pop it off the stack. 161 Pop(); 162 163 // Check if we have a new replacement. 164 if (replacement != node) { 165 Replace(node, replacement, max_id); 166 } else { 167 // Revisit all uses of the node. 168 for (Node* const user : node->uses()) { 169 // Don't revisit this node if it refers to itself. 170 if (user != node) Revisit(user); 171 } 172 } 173} 174 175 176void GraphReducer::Replace(Node* node, Node* replacement) { 177 Replace(node, replacement, std::numeric_limits<NodeId>::max()); 178} 179 180 181void GraphReducer::Replace(Node* node, Node* replacement, NodeId max_id) { 182 if (FLAG_trace_turbo_reduction) { 183 OFStream os(stdout); 184 os << "- Replacing " << *node << " with " << *replacement << std::endl; 185 } 186 if (node == graph()->start()) graph()->SetStart(replacement); 187 if (node == graph()->end()) graph()->SetEnd(replacement); 188 if (replacement->id() <= max_id) { 189 // {replacement} is an old node, so unlink {node} and assume that 190 // {replacement} was already reduced and finish. 191 for (Edge edge : node->use_edges()) { 192 Node* const user = edge.from(); 193 Verifier::VerifyEdgeInputReplacement(edge, replacement); 194 edge.UpdateTo(replacement); 195 // Don't revisit this node if it refers to itself. 196 if (user != node) Revisit(user); 197 } 198 node->Kill(); 199 } else { 200 // Replace all old uses of {node} with {replacement}, but allow new nodes 201 // created by this reduction to use {node}. 202 for (Edge edge : node->use_edges()) { 203 Node* const user = edge.from(); 204 if (user->id() <= max_id) { 205 edge.UpdateTo(replacement); 206 // Don't revisit this node if it refers to itself. 207 if (user != node) Revisit(user); 208 } 209 } 210 // Unlink {node} if it's no longer used. 211 if (node->uses().empty()) node->Kill(); 212 213 // If there was a replacement, reduce it after popping {node}. 214 Recurse(replacement); 215 } 216} 217 218 219void GraphReducer::ReplaceWithValue(Node* node, Node* value, Node* effect, 220 Node* control) { 221 if (effect == nullptr && node->op()->EffectInputCount() > 0) { 222 effect = NodeProperties::GetEffectInput(node); 223 } 224 if (control == nullptr && node->op()->ControlInputCount() > 0) { 225 control = NodeProperties::GetControlInput(node); 226 } 227 228 // Requires distinguishing between value, effect and control edges. 229 for (Edge edge : node->use_edges()) { 230 Node* const user = edge.from(); 231 DCHECK(!user->IsDead()); 232 if (NodeProperties::IsControlEdge(edge)) { 233 if (user->opcode() == IrOpcode::kIfSuccess) { 234 Replace(user, control); 235 } else if (user->opcode() == IrOpcode::kIfException) { 236 DCHECK_NOT_NULL(dead_); 237 edge.UpdateTo(dead_); 238 Revisit(user); 239 } else { 240 DCHECK_NOT_NULL(control); 241 edge.UpdateTo(control); 242 Revisit(user); 243 // TODO(jarin) Check that the node cannot throw (otherwise, it 244 // would have to be connected via IfSuccess/IfException). 245 } 246 } else if (NodeProperties::IsEffectEdge(edge)) { 247 DCHECK_NOT_NULL(effect); 248 edge.UpdateTo(effect); 249 Revisit(user); 250 } else { 251 DCHECK_NOT_NULL(value); 252 edge.UpdateTo(value); 253 Revisit(user); 254 } 255 } 256} 257 258 259void GraphReducer::Pop() { 260 Node* node = stack_.top().node; 261 state_.Set(node, State::kVisited); 262 stack_.pop(); 263} 264 265 266void GraphReducer::Push(Node* const node) { 267 DCHECK(state_.Get(node) != State::kOnStack); 268 state_.Set(node, State::kOnStack); 269 stack_.push({node, 0}); 270} 271 272 273bool GraphReducer::Recurse(Node* node) { 274 if (state_.Get(node) > State::kRevisit) return false; 275 Push(node); 276 return true; 277} 278 279 280void GraphReducer::Revisit(Node* node) { 281 if (state_.Get(node) == State::kVisited) { 282 state_.Set(node, State::kRevisit); 283 revisit_.push(node); 284 } 285} 286 287} // namespace compiler 288} // namespace internal 289} // namespace v8 290