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 15 namespace v8 { 16 namespace internal { 17 namespace 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 25 LoopVariableOptimizer::LoopVariableOptimizer(Graph* graph, 26 CommonOperatorBuilder* common, 27 Zone* zone) 28 : graph_(graph), 29 common_(common), 30 zone_(zone), 31 limits_(graph->NodeCount(), zone), 32 reduced_(graph->NodeCount(), zone), 33 induction_vars_(zone) {} 34 35 void LoopVariableOptimizer::Run() { 36 ZoneQueue<Node*> queue(zone()); 37 queue.push(graph()->start()); 38 NodeMarker<bool> queued(graph(), 2); 39 while (!queue.empty()) { 40 Node* node = queue.front(); 41 queue.pop(); 42 queued.Set(node, false); 43 44 DCHECK(!reduced_.Get(node)); 45 bool all_inputs_visited = true; 46 int inputs_end = (node->opcode() == IrOpcode::kLoop) 47 ? kFirstBackedge 48 : node->op()->ControlInputCount(); 49 for (int i = 0; i < inputs_end; i++) { 50 if (!reduced_.Get(NodeProperties::GetControlInput(node, i))) { 51 all_inputs_visited = false; 52 break; 53 } 54 } 55 if (!all_inputs_visited) continue; 56 57 VisitNode(node); 58 reduced_.Set(node, true); 59 60 // Queue control outputs. 61 for (Edge edge : node->use_edges()) { 62 if (NodeProperties::IsControlEdge(edge) && 63 edge.from()->op()->ControlOutputCount() > 0) { 64 Node* use = edge.from(); 65 if (use->opcode() == IrOpcode::kLoop && 66 edge.index() != kAssumedLoopEntryIndex) { 67 VisitBackedge(node, use); 68 } else if (!queued.Get(use)) { 69 queue.push(use); 70 queued.Set(use, true); 71 } 72 } 73 } 74 } 75 } 76 77 void InductionVariable::AddUpperBound(Node* bound, 78 InductionVariable::ConstraintKind kind) { 79 if (FLAG_trace_turbo_loop) { 80 StdoutStream{} << "New upper bound for " << phi()->id() << " (loop " 81 << NodeProperties::GetControlInput(phi())->id() 82 << "): " << *bound << std::endl; 83 } 84 upper_bounds_.push_back(Bound(bound, kind)); 85 } 86 87 void InductionVariable::AddLowerBound(Node* bound, 88 InductionVariable::ConstraintKind kind) { 89 if (FLAG_trace_turbo_loop) { 90 StdoutStream{} << "New lower bound for " << phi()->id() << " (loop " 91 << NodeProperties::GetControlInput(phi())->id() 92 << "): " << *bound; 93 } 94 lower_bounds_.push_back(Bound(bound, kind)); 95 } 96 97 void LoopVariableOptimizer::VisitBackedge(Node* from, Node* loop) { 98 if (loop->op()->ControlInputCount() != 2) return; 99 100 // Go through the constraints, and update the induction variables in 101 // this loop if they are involved in the constraint. 102 for (Constraint constraint : limits_.Get(from)) { 103 if (constraint.left->opcode() == IrOpcode::kPhi && 104 NodeProperties::GetControlInput(constraint.left) == loop) { 105 auto var = induction_vars_.find(constraint.left->id()); 106 if (var != induction_vars_.end()) { 107 var->second->AddUpperBound(constraint.right, constraint.kind); 108 } 109 } 110 if (constraint.right->opcode() == IrOpcode::kPhi && 111 NodeProperties::GetControlInput(constraint.right) == loop) { 112 auto var = induction_vars_.find(constraint.right->id()); 113 if (var != induction_vars_.end()) { 114 var->second->AddLowerBound(constraint.left, constraint.kind); 115 } 116 } 117 } 118 } 119 120 void LoopVariableOptimizer::VisitNode(Node* node) { 121 switch (node->opcode()) { 122 case IrOpcode::kMerge: 123 return VisitMerge(node); 124 case IrOpcode::kLoop: 125 return VisitLoop(node); 126 case IrOpcode::kIfFalse: 127 return VisitIf(node, false); 128 case IrOpcode::kIfTrue: 129 return VisitIf(node, true); 130 case IrOpcode::kStart: 131 return VisitStart(node); 132 case IrOpcode::kLoopExit: 133 return VisitLoopExit(node); 134 default: 135 return VisitOtherControl(node); 136 } 137 } 138 139 void LoopVariableOptimizer::VisitMerge(Node* node) { 140 // Merge the limits of all incoming edges. 141 VariableLimits merged = limits_.Get(node->InputAt(0)); 142 for (int i = 1; i < node->InputCount(); i++) { 143 merged.ResetToCommonAncestor(limits_.Get(node->InputAt(i))); 144 } 145 limits_.Set(node, merged); 146 } 147 148 void LoopVariableOptimizer::VisitLoop(Node* node) { 149 DetectInductionVariables(node); 150 // Conservatively take the limits from the loop entry here. 151 return TakeConditionsFromFirstControl(node); 152 } 153 154 void LoopVariableOptimizer::VisitIf(Node* node, bool polarity) { 155 Node* branch = node->InputAt(0); 156 Node* cond = branch->InputAt(0); 157 VariableLimits limits = limits_.Get(branch); 158 // Normalize to less than comparison. 159 switch (cond->opcode()) { 160 case IrOpcode::kJSLessThan: 161 case IrOpcode::kSpeculativeNumberLessThan: 162 AddCmpToLimits(&limits, cond, InductionVariable::kStrict, polarity); 163 break; 164 case IrOpcode::kJSGreaterThan: 165 AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, !polarity); 166 break; 167 case IrOpcode::kJSLessThanOrEqual: 168 case IrOpcode::kSpeculativeNumberLessThanOrEqual: 169 AddCmpToLimits(&limits, cond, InductionVariable::kNonStrict, polarity); 170 break; 171 case IrOpcode::kJSGreaterThanOrEqual: 172 AddCmpToLimits(&limits, cond, InductionVariable::kStrict, !polarity); 173 break; 174 default: 175 break; 176 } 177 limits_.Set(node, limits); 178 } 179 180 void LoopVariableOptimizer::AddCmpToLimits( 181 VariableLimits* limits, Node* node, InductionVariable::ConstraintKind kind, 182 bool polarity) { 183 Node* left = node->InputAt(0); 184 Node* right = node->InputAt(1); 185 if (FindInductionVariable(left) || FindInductionVariable(right)) { 186 if (polarity) { 187 limits->PushFront(Constraint{left, kind, right}, zone()); 188 } else { 189 kind = (kind == InductionVariable::kStrict) 190 ? InductionVariable::kNonStrict 191 : InductionVariable::kStrict; 192 limits->PushFront(Constraint{right, kind, left}, zone()); 193 } 194 } 195 } 196 197 void LoopVariableOptimizer::VisitStart(Node* node) { limits_.Set(node, {}); } 198 199 void LoopVariableOptimizer::VisitLoopExit(Node* node) { 200 return TakeConditionsFromFirstControl(node); 201 } 202 203 void LoopVariableOptimizer::VisitOtherControl(Node* node) { 204 DCHECK_EQ(1, node->op()->ControlInputCount()); 205 return TakeConditionsFromFirstControl(node); 206 } 207 208 void LoopVariableOptimizer::TakeConditionsFromFirstControl(Node* node) { 209 limits_.Set(node, limits_.Get(NodeProperties::GetControlInput(node, 0))); 210 } 211 212 const InductionVariable* LoopVariableOptimizer::FindInductionVariable( 213 Node* node) { 214 auto var = induction_vars_.find(node->id()); 215 if (var != induction_vars_.end()) { 216 return var->second; 217 } 218 return nullptr; 219 } 220 221 InductionVariable* LoopVariableOptimizer::TryGetInductionVariable(Node* phi) { 222 DCHECK_EQ(2, phi->op()->ValueInputCount()); 223 Node* loop = NodeProperties::GetControlInput(phi); 224 DCHECK_EQ(IrOpcode::kLoop, loop->opcode()); 225 Node* initial = phi->InputAt(0); 226 Node* arith = phi->InputAt(1); 227 InductionVariable::ArithmeticType arithmeticType; 228 if (arith->opcode() == IrOpcode::kJSAdd || 229 arith->opcode() == IrOpcode::kSpeculativeNumberAdd || 230 arith->opcode() == IrOpcode::kSpeculativeSafeIntegerAdd) { 231 arithmeticType = InductionVariable::ArithmeticType::kAddition; 232 } else if (arith->opcode() == IrOpcode::kJSSubtract || 233 arith->opcode() == IrOpcode::kSpeculativeNumberSubtract || 234 arith->opcode() == IrOpcode::kSpeculativeSafeIntegerSubtract) { 235 arithmeticType = InductionVariable::ArithmeticType::kSubtraction; 236 } else { 237 return nullptr; 238 } 239 240 // TODO(jarin) Support both sides. 241 Node* input = arith->InputAt(0); 242 if (input->opcode() == IrOpcode::kSpeculativeToNumber || 243 input->opcode() == IrOpcode::kJSToNumber || 244 input->opcode() == IrOpcode::kJSToNumberConvertBigInt) { 245 input = input->InputAt(0); 246 } 247 if (input != phi) return nullptr; 248 249 Node* effect_phi = nullptr; 250 for (Node* use : loop->uses()) { 251 if (use->opcode() == IrOpcode::kEffectPhi) { 252 DCHECK_NULL(effect_phi); 253 effect_phi = use; 254 } 255 } 256 if (!effect_phi) return nullptr; 257 258 Node* incr = arith->InputAt(1); 259 return new (zone()) InductionVariable(phi, effect_phi, arith, incr, initial, 260 zone(), arithmeticType); 261 } 262 263 void LoopVariableOptimizer::DetectInductionVariables(Node* loop) { 264 if (loop->op()->ControlInputCount() != 2) return; 265 TRACE("Loop variables for loop %i:", loop->id()); 266 for (Edge edge : loop->use_edges()) { 267 if (NodeProperties::IsControlEdge(edge) && 268 edge.from()->opcode() == IrOpcode::kPhi) { 269 Node* phi = edge.from(); 270 InductionVariable* induction_var = TryGetInductionVariable(phi); 271 if (induction_var) { 272 induction_vars_[phi->id()] = induction_var; 273 TRACE(" %i", induction_var->phi()->id()); 274 } 275 } 276 } 277 TRACE("\n"); 278 } 279 280 void LoopVariableOptimizer::ChangeToInductionVariablePhis() { 281 for (auto entry : induction_vars_) { 282 // It only make sense to analyze the induction variables if 283 // there is a bound. 284 InductionVariable* induction_var = entry.second; 285 DCHECK_EQ(MachineRepresentation::kTagged, 286 PhiRepresentationOf(induction_var->phi()->op())); 287 if (induction_var->upper_bounds().size() == 0 && 288 induction_var->lower_bounds().size() == 0) { 289 continue; 290 } 291 // Insert the increment value to the value inputs. 292 induction_var->phi()->InsertInput(graph()->zone(), 293 induction_var->phi()->InputCount() - 1, 294 induction_var->increment()); 295 // Insert the bound inputs to the value inputs. 296 for (auto bound : induction_var->lower_bounds()) { 297 induction_var->phi()->InsertInput( 298 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound); 299 } 300 for (auto bound : induction_var->upper_bounds()) { 301 induction_var->phi()->InsertInput( 302 graph()->zone(), induction_var->phi()->InputCount() - 1, bound.bound); 303 } 304 NodeProperties::ChangeOp( 305 induction_var->phi(), 306 common()->InductionVariablePhi(induction_var->phi()->InputCount() - 1)); 307 } 308 } 309 310 void LoopVariableOptimizer::ChangeToPhisAndInsertGuards() { 311 for (auto entry : induction_vars_) { 312 InductionVariable* induction_var = entry.second; 313 if (induction_var->phi()->opcode() == IrOpcode::kInductionVariablePhi) { 314 // Turn the induction variable phi back to normal phi. 315 int value_count = 2; 316 Node* control = NodeProperties::GetControlInput(induction_var->phi()); 317 DCHECK_EQ(value_count, control->op()->ControlInputCount()); 318 induction_var->phi()->TrimInputCount(value_count + 1); 319 induction_var->phi()->ReplaceInput(value_count, control); 320 NodeProperties::ChangeOp( 321 induction_var->phi(), 322 common()->Phi(MachineRepresentation::kTagged, value_count)); 323 324 // If the backedge is not a subtype of the phi's type, we insert a sigma 325 // to get the typing right. 326 Node* backedge_value = induction_var->phi()->InputAt(1); 327 Type backedge_type = NodeProperties::GetType(backedge_value); 328 Type phi_type = NodeProperties::GetType(induction_var->phi()); 329 if (!backedge_type.Is(phi_type)) { 330 Node* loop = NodeProperties::GetControlInput(induction_var->phi()); 331 Node* backedge_control = loop->InputAt(1); 332 Node* backedge_effect = 333 NodeProperties::GetEffectInput(induction_var->effect_phi(), 1); 334 Node* rename = 335 graph()->NewNode(common()->TypeGuard(phi_type), backedge_value, 336 backedge_effect, backedge_control); 337 induction_var->effect_phi()->ReplaceInput(1, rename); 338 induction_var->phi()->ReplaceInput(1, rename); 339 } 340 } 341 } 342 } 343 344 #undef TRACE 345 346 } // namespace compiler 347 } // namespace internal 348 } // namespace v8 349