1// Copyright 2016 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 "src/compiler/loop-variable-optimizer.h" 6 7#include "src/compiler/common-operator.h" 8#include "src/compiler/graph.h" 9#include "src/compiler/node-marker.h" 10#include "src/compiler/node-properties.h" 11#include "src/compiler/node.h" 12#include "src/zone/zone-containers.h" 13#include "src/zone/zone.h" 14 15namespace v8 { 16namespace internal { 17namespace compiler { 18 19// Macro for outputting trace information from representation inference. 20#define TRACE(...) \ 21 do { \ 22 if (FLAG_trace_turbo_loop) PrintF(__VA_ARGS__); \ 23 } while (false) 24 25LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph, 26 CommonOperatorBuilder* common, 27 Zone* zone) 28 : graph_(graph), 29 common_(common), 30 zone_(zone), 31 limits_(graph->NodeCount(), zone), 32 induction_vars_(zone) {} 33 34void LoopVariableOptimizer::Run() { 35 ZoneQueue<Node*> queue(zone()); 36 queue.push(graph()->start()); 37 NodeMarker<bool> queued(graph(), 2); 38 while (!queue.empty()) { 39 Node* node = queue.front(); 40 queue.pop(); 41 queued.Set(node, false); 42 43 DCHECK_NULL(limits_[node->id()]); 44 bool all_inputs_visited = true; 45 int inputs_end = (node->opcode() == IrOpcode::kLoop) 46 ? kFirstBackedge 47 : node->op()->ControlInputCount(); 48 for (int i = 0; i < inputs_end; i++) { 49 if (limits_[NodeProperties::GetControlInput(node, i)->id()] == nullptr) { 50 all_inputs_visited = false; 51 break; 52 } 53 } 54 if (!all_inputs_visited) continue; 55 56 VisitNode(node); 57 DCHECK_NOT_NULL(limits_[node->id()]); 58 59 // Queue control outputs. 60 for (Edge edge : node->use_edges()) { 61 if (NodeProperties::IsControlEdge(edge) && 62 edge.from()->op()->ControlOutputCount() > 0) { 63 Node* use = edge.from(); 64 if (use->opcode() == IrOpcode::kLoop && 65 edge.index() != kAssumedLoopEntryIndex) { 66 VisitBackedge(node, use); 67 } else if (!queued.Get(use)) { 68 queue.push(use); 69 queued.Set(use, true); 70 } 71 } 72 } 73 } 74} 75 76class LoopVariableOptimizer::Constraint : public ZoneObject { 77 public: 78 InductionVariable::ConstraintKind kind() const { return kind_; } 79 Node* left() const { return left_; } 80 Node* right() const { return right_; } 81 82 const Constraint* next() const { return next_; } 83 84 Constraint(Node* left, InductionVariable::ConstraintKind kind, Node* right, 85 const Constraint* next) 86 : left_(left), right_(right), kind_(kind), next_(next) {} 87 88 private: 89 Node* left_; 90 Node* right_; 91 InductionVariable::ConstraintKind kind_; 92 const Constraint* next_; 93}; 94 95class LoopVariableOptimizer::VariableLimits : public ZoneObject { 96 public: 97 static VariableLimits* Empty(Zone* zone) { 98 return new (zone) VariableLimits(); 99 } 100 101 VariableLimits* Copy(Zone* zone) const { 102 return new (zone) VariableLimits(this); 103 } 104 105 void Add(Node* left, InductionVariable::ConstraintKind kind, Node* right, 106 Zone* zone) { 107 head_ = new (zone) Constraint(left, kind, right, head_); 108 limit_count_++; 109 } 110 111 void Merge(const VariableLimits* other) { 112 // Change the current condition list to a longest common tail 113 // of this condition list and the other list. (The common tail 114 // should correspond to the list from the common dominator.) 115 116 // First, we throw away the prefix of the longer list, so that 117 // we have lists of the same length. 118 size_t other_size = other->limit_count_; 119 const Constraint* other_limit = other->head_; 120 while (other_size > limit_count_) { 121 other_limit = other_limit->next(); 122 other_size--; 123 } 124 while (limit_count_ > other_size) { 125 head_ = head_->next(); 126 limit_count_--; 127 } 128 129 // Then we go through both lists in lock-step until we find 130 // the common tail. 131 while (head_ != other_limit) { 132 DCHECK(limit_count_ > 0); 133 limit_count_--; 134 other_limit = other_limit->next(); 135 head_ = head_->next(); 136 } 137 } 138 139 const Constraint* head() const { return head_; } 140 141 private: 142 VariableLimits() {} 143 explicit VariableLimits(const VariableLimits* other) 144 : head_(other->head_), limit_count_(other->limit_count_) {} 145 146 const Constraint* head_ = nullptr; 147 size_t limit_count_ = 0; 148}; 149 150void InductionVariable::AddUpperBound(Node* bound, 151 InductionVariable::ConstraintKind kind) { 152 if (FLAG_trace_turbo_loop) { 153 OFStream os(stdout); 154 os << "New upper bound for " << phi()->id() << " (loop " 155 << NodeProperties::GetControlInput(phi())->id() << "): " << *bound 156 << std::endl; 157 } 158 upper_bounds_.push_back(Bound(bound, kind)); 159} 160 161void InductionVariable::AddLowerBound(Node* bound, 162 InductionVariable::ConstraintKind kind) { 163 if (FLAG_trace_turbo_loop) { 164 OFStream os(stdout); 165 os << "New lower bound for " << phi()->id() << " (loop " 166 << NodeProperties::GetControlInput(phi())->id() << "): " << *bound; 167 } 168 lower_bounds_.push_back(Bound(bound, kind)); 169} 170 171void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) { 172 if (loop->op()->ControlInputCount() != 2) return; 173 174 // Go through the constraints, and update the induction variables in 175 // this loop if they are involved in the constraint. 176 const VariableLimits* limits = limits_[from->id()]; 177 for (const Constraint* constraint = limits->head(); constraint != nullptr; 178 constraint = constraint->next()) { 179 if (constraint->left()->opcode() == IrOpcode::kPhi && 180 NodeProperties::GetControlInput(constraint->left()) == loop) { 181 auto var = induction_vars_.find(constraint->left()->id()); 182 if (var != induction_vars_.end()) { 183 var->second->AddUpperBound(constraint->right(), constraint->kind()); 184 } 185 } 186 if (constraint->right()->opcode() == IrOpcode::kPhi && 187 NodeProperties::GetControlInput(constraint->right()) == loop) { 188 auto var = induction_vars_.find(constraint->right()->id()); 189 if (var != induction_vars_.end()) { 190 var->second->AddLowerBound(constraint->left(), constraint->kind()); 191 } 192 } 193 } 194} 195 196void LoopVariableOptimizer::VisitNode(Node* node) { 197 switch (node->opcode()) { 198 case IrOpcode::kMerge: 199 return VisitMerge(node); 200 case IrOpcode::kLoop: 201 return VisitLoop(node); 202 case IrOpcode::kIfFalse: 203 return VisitIf(node, false); 204 case IrOpcode::kIfTrue: 205 return VisitIf(node, true); 206 case IrOpcode::kStart: 207 return VisitStart(node); 208 case IrOpcode::kLoopExit: 209 return VisitLoopExit(node); 210 default: 211 return VisitOtherControl(node); 212 } 213} 214 215void LoopVariableOptimizer::VisitMerge(Node* node) { 216 // Merge the limits of all incoming edges. 217 VariableLimits* merged = limits_[node->InputAt(0)->id()]->Copy(zone()); 218 for (int i = 1; i < node->InputCount(); i++) { 219 merged->Merge(limits_[node->InputAt(i)->id()]); 220 } 221 limits_[node->id()] = merged; 222} 223 224void LoopVariableOptimizer::VisitLoop(Node* node) { 225 DetectInductionVariables(node); 226 // Conservatively take the limits from the loop entry here. 227 return TakeConditionsFromFirstControl(node); 228} 229 230void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) { 231 Node* branch = node->InputAt(0); 232 Node* cond = branch->InputAt(0); 233 VariableLimits* limits = limits_[branch->id()]->Copy(zone()); 234 // Normalize to less than comparison. 235 switch (cond->opcode()) { 236 case IrOpcode::kJSLessThan: 237 AddCmpToLimits(limits, cond, InductionVariable::kStrict, polarity); 238 break; 239 case IrOpcode::kJSGreaterThan: 240 AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, !polarity); 241 break; 242 case IrOpcode::kJSLessThanOrEqual: 243 AddCmpToLimits(limits, cond, InductionVariable::kNonStrict, polarity); 244 break; 245 case IrOpcode::kJSGreaterThanOrEqual: 246 AddCmpToLimits(limits, cond, InductionVariable::kStrict, !polarity); 247 break; 248 default: 249 break; 250 } 251 limits_[node->id()] = limits; 252} 253 254void LoopVariableOptimizer::AddCmpToLimits( 255 VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind, 256 bool polarity) { 257 Node* left = node->InputAt(0); 258 Node* right = node->InputAt(1); 259 if (FindInductionVariable(left) || FindInductionVariable(right)) { 260 if (polarity) { 261 limits->Add(left, kind, right, zone()); 262 } else { 263 kind = (kind == InductionVariable::kStrict) 264 ? InductionVariable::kNonStrict 265 : InductionVariable::kStrict; 266 limits->Add(right, kind, left, zone()); 267 } 268 } 269} 270 271void LoopVariableOptimizer::VisitStart(Node* node) { 272 limits_[node->id()] = VariableLimits::Empty(zone()); 273} 274 275void LoopVariableOptimizer::VisitLoopExit(Node* node) { 276 return TakeConditionsFromFirstControl(node); 277} 278 279void LoopVariableOptimizer::VisitOtherControl(Node* node) { 280 DCHECK_EQ(1, node->op()->ControlInputCount()); 281 return TakeConditionsFromFirstControl(node); 282} 283 284void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) { 285 const VariableLimits* limits = 286 limits_[NodeProperties::GetControlInput(node, 0)->id()]; 287 DCHECK_NOT_NULL(limits); 288 limits_[node->id()] = limits; 289} 290 291const InductionVariable* LoopVariableOptimizer::FindInductionVariable( 292 Node* node) { 293 auto var = induction_vars_.find(node->id()); 294 if (var != induction_vars_.end()) { 295 return var->second; 296 } 297 return nullptr; 298} 299 300InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) { 301 DCHECK_EQ(2, phi->op()->ValueInputCount()); 302 DCHECK_EQ(IrOpcode::kLoop, NodeProperties::GetControlInput(phi)->opcode()); 303 Node* initial = phi->InputAt(0); 304 Node* arith = phi->InputAt(1); 305 InductionVariable::ArithmeticType arithmeticType; 306 if (arith->opcode() == IrOpcode::kJSAdd || 307 arith->opcode() == IrOpcode::kSpeculativeNumberAdd) { 308 arithmeticType = InductionVariable::ArithmeticType::kAddition; 309 } else if (arith->opcode() == IrOpcode::kJSSubtract || 310 arith->opcode() == IrOpcode::kSpeculativeNumberSubtract) { 311 arithmeticType = InductionVariable::ArithmeticType::kSubtraction; 312 } else { 313 return nullptr; 314 } 315 316 // TODO(jarin) Support both sides. 317 if (arith->InputAt(0) != phi) { 318 if (arith->InputAt(0)->opcode() != IrOpcode::kJSToNumber || 319 arith->InputAt(0)->InputAt(0) != phi) { 320 return nullptr; 321 } 322 } 323 Node* incr = arith->InputAt(1); 324 return new (zone()) 325 InductionVariable(phi, arith, incr, initial, zone(), arithmeticType); 326} 327 328void LoopVariableOptimizer::DetectInductionVariables(Node* loop) { 329 if (loop->op()->ControlInputCount() != 2) return; 330 TRACE("Loop variables for loop %i:", loop->id()); 331 for (Edge edge : loop->use_edges()) { 332 if (NodeProperties::IsControlEdge(edge) && 333 edge.from()->opcode() == IrOpcode::kPhi) { 334 Node* phi = edge.from(); 335 InductionVariable* induction_var = TryGetInductionVariable(phi); 336 if (induction_var) { 337 induction_vars_[phi->id()] = induction_var; 338 TRACE(" %i", induction_var->phi()->id()); 339 } 340 } 341 } 342 TRACE("\n"); 343} 344 345void LoopVariableOptimizer::ChangeToInductionVariablePhis() { 346 for (auto entry : induction_vars_) { 347 // It only make sense to analyze the induction variables if 348 // there is a bound. 349 InductionVariable* induction_var = entry.second; 350 DCHECK_EQ(MachineRepresentation::kTagged, 351 PhiRepresentationOf(induction_var->phi()->op())); 352 if (induction_var->upper_bounds().size() == 0 && 353 induction_var->lower_bounds().size() == 0) { 354 continue; 355 } 356 // Insert the increment value to the value inputs. 357 induction_var->phi()->InsertInput(graph()->zone(), 358 induction_var->phi()->InputCount() - 1, 359 induction_var->increment()); 360 // Insert the bound inputs to the value inputs. 361 for (auto bound : induction_var->lower_bounds()) { 362 induction_var->phi()->InsertInput( 363 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound); 364 } 365 for (auto bound : induction_var->upper_bounds()) { 366 induction_var->phi()->InsertInput( 367 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound); 368 } 369 NodeProperties::ChangeOp( 370 induction_var->phi(), 371 common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1)); 372 } 373} 374 375void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() { 376 for (auto entry : induction_vars_) { 377 InductionVariable* induction_var = entry.second; 378 if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) { 379 // Turn the induction variable phi back to normal phi. 380 int value_count = 2; 381 Node* control = NodeProperties::GetControlInput(induction_var->phi()); 382 DCHECK_EQ(value_count, control->op()->ControlInputCount()); 383 induction_var->phi()->TrimInputCount(value_count + 1); 384 induction_var->phi()->ReplaceInput(value_count, control); 385 NodeProperties::ChangeOp( 386 induction_var->phi(), 387 common()->Phi(MachineRepresentation::kTagged, value_count)); 388 389 // If the backedge is not a subtype of the phi's type, we insert a sigma 390 // to get the typing right. 391 Node* backedge_value = induction_var->phi()->InputAt(1); 392 Type* backedge_type = NodeProperties::GetType(backedge_value); 393 Type* phi_type = NodeProperties::GetType(induction_var->phi()); 394 if (!backedge_type->Is(phi_type)) { 395 Node* backedge_control = 396 NodeProperties::GetControlInput(induction_var->phi())->InputAt(1); 397 Node* rename = graph()->NewNode(common()->TypeGuard(phi_type), 398 backedge_value, backedge_control); 399 induction_var->phi()->ReplaceInput(1, rename); 400 } 401 } 402 } 403} 404 405} // namespace compiler 406} // namespace internal 407} // namespace v8 408