instruction_simplifier.cc revision 7733bd644ac71f86d4b30a319624b23343882e53
1/* 2 * Copyright (C) 2014 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#include "instruction_simplifier.h" 18 19#include "mirror/class-inl.h" 20#include "scoped_thread_state_change.h" 21 22namespace art { 23 24class InstructionSimplifierVisitor : public HGraphVisitor { 25 public: 26 InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats) 27 : HGraphVisitor(graph), 28 stats_(stats) {} 29 30 void Run(); 31 32 private: 33 void RecordSimplification() { 34 simplification_occurred_ = true; 35 simplifications_at_current_position_++; 36 if (stats_) { 37 stats_->RecordStat(kInstructionSimplifications); 38 } 39 } 40 41 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop); 42 void VisitShift(HBinaryOperation* shift); 43 44 void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE; 45 void VisitEqual(HEqual* equal) OVERRIDE; 46 void VisitNotEqual(HNotEqual* equal) OVERRIDE; 47 void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE; 48 void VisitInstanceFieldSet(HInstanceFieldSet* equal) OVERRIDE; 49 void VisitStaticFieldSet(HStaticFieldSet* equal) OVERRIDE; 50 void VisitArraySet(HArraySet* equal) OVERRIDE; 51 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 52 void VisitNullCheck(HNullCheck* instruction) OVERRIDE; 53 void VisitArrayLength(HArrayLength* instruction) OVERRIDE; 54 void VisitCheckCast(HCheckCast* instruction) OVERRIDE; 55 void VisitAdd(HAdd* instruction) OVERRIDE; 56 void VisitAnd(HAnd* instruction) OVERRIDE; 57 void VisitCondition(HCondition* instruction) OVERRIDE; 58 void VisitGreaterThan(HGreaterThan* condition) OVERRIDE; 59 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) OVERRIDE; 60 void VisitLessThan(HLessThan* condition) OVERRIDE; 61 void VisitLessThanOrEqual(HLessThanOrEqual* condition) OVERRIDE; 62 void VisitDiv(HDiv* instruction) OVERRIDE; 63 void VisitMul(HMul* instruction) OVERRIDE; 64 void VisitNeg(HNeg* instruction) OVERRIDE; 65 void VisitNot(HNot* instruction) OVERRIDE; 66 void VisitOr(HOr* instruction) OVERRIDE; 67 void VisitShl(HShl* instruction) OVERRIDE; 68 void VisitShr(HShr* instruction) OVERRIDE; 69 void VisitSub(HSub* instruction) OVERRIDE; 70 void VisitUShr(HUShr* instruction) OVERRIDE; 71 void VisitXor(HXor* instruction) OVERRIDE; 72 void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; 73 void VisitFakeString(HFakeString* fake_string) OVERRIDE; 74 bool IsDominatedByInputNullCheck(HInstruction* instr); 75 76 OptimizingCompilerStats* stats_; 77 bool simplification_occurred_ = false; 78 int simplifications_at_current_position_ = 0; 79 // We ensure we do not loop infinitely. The value is a finger in the air guess 80 // that should allow enough simplification. 81 static constexpr int kMaxSamePositionSimplifications = 10; 82}; 83 84void InstructionSimplifier::Run() { 85 InstructionSimplifierVisitor visitor(graph_, stats_); 86 visitor.Run(); 87} 88 89void InstructionSimplifierVisitor::Run() { 90 // Iterate in reverse post order to open up more simplifications to users 91 // of instructions that got simplified. 92 for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) { 93 // The simplification of an instruction to another instruction may yield 94 // possibilities for other simplifications. So although we perform a reverse 95 // post order visit, we sometimes need to revisit an instruction index. 96 simplification_occurred_ = false; 97 VisitBasicBlock(it.Current()); 98 if (simplification_occurred_ && 99 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) { 100 // New simplifications may be applicable to the instruction at the 101 // current index, so don't advance the iterator. 102 continue; 103 } 104 simplifications_at_current_position_ = 0; 105 it.Advance(); 106 } 107} 108 109namespace { 110 111bool AreAllBitsSet(HConstant* constant) { 112 return Int64FromConstant(constant) == -1; 113} 114 115} // namespace 116 117// Returns true if the code was simplified to use only one negation operation 118// after the binary operation instead of one on each of the inputs. 119bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) { 120 DCHECK(binop->IsAdd() || binop->IsSub()); 121 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg()); 122 HNeg* left_neg = binop->GetLeft()->AsNeg(); 123 HNeg* right_neg = binop->GetRight()->AsNeg(); 124 if (!left_neg->HasOnlyOneNonEnvironmentUse() || 125 !right_neg->HasOnlyOneNonEnvironmentUse()) { 126 return false; 127 } 128 // Replace code looking like 129 // NEG tmp1, a 130 // NEG tmp2, b 131 // ADD dst, tmp1, tmp2 132 // with 133 // ADD tmp, a, b 134 // NEG dst, tmp 135 binop->ReplaceInput(left_neg->GetInput(), 0); 136 binop->ReplaceInput(right_neg->GetInput(), 1); 137 left_neg->GetBlock()->RemoveInstruction(left_neg); 138 right_neg->GetBlock()->RemoveInstruction(right_neg); 139 HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop); 140 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext()); 141 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0); 142 RecordSimplification(); 143 return true; 144} 145 146void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 147 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 148 HConstant* input_cst = instruction->GetConstantRight(); 149 HInstruction* input_other = instruction->GetLeastConstantLeft(); 150 151 if (input_cst != nullptr) { 152 if (input_cst->IsZero()) { 153 // Replace code looking like 154 // SHL dst, src, 0 155 // with 156 // src 157 instruction->ReplaceWith(input_other); 158 instruction->GetBlock()->RemoveInstruction(instruction); 159 } else if (instruction->IsShl() && input_cst->IsOne()) { 160 // Replace Shl looking like 161 // SHL dst, src, 1 162 // with 163 // ADD dst, src, src 164 HAdd *add = new(GetGraph()->GetArena()) HAdd(instruction->GetType(), 165 input_other, 166 input_other); 167 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 168 RecordSimplification(); 169 } 170 } 171} 172 173void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 174 HInstruction* obj = null_check->InputAt(0); 175 if (!obj->CanBeNull()) { 176 null_check->ReplaceWith(obj); 177 null_check->GetBlock()->RemoveInstruction(null_check); 178 if (stats_ != nullptr) { 179 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 180 } 181 } 182} 183 184bool InstructionSimplifierVisitor::IsDominatedByInputNullCheck(HInstruction* instr) { 185 HInstruction* input = instr->InputAt(0); 186 for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) { 187 HInstruction* use = it.Current()->GetUser(); 188 if (use->IsNullCheck() && use->StrictlyDominates(instr)) { 189 return true; 190 } 191 } 192 return false; 193} 194 195// Returns whether doing a type test between the class of `object` against `klass` has 196// a statically known outcome. The result of the test is stored in `outcome`. 197static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) { 198 if (!klass->IsResolved()) { 199 // If the class couldn't be resolve it's not safe to compare against it. It's 200 // default type would be Top which might be wider that the actual class type 201 // and thus producing wrong results. 202 return false; 203 } 204 205 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); 206 ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI(); 207 ScopedObjectAccess soa(Thread::Current()); 208 if (class_rti.IsSupertypeOf(obj_rti)) { 209 *outcome = true; 210 return true; 211 } else if (obj_rti.IsExact()) { 212 // The test failed at compile time so will also fail at runtime. 213 *outcome = false; 214 return true; 215 } else if (!class_rti.IsInterface() 216 && !obj_rti.IsInterface() 217 && !obj_rti.IsSupertypeOf(class_rti)) { 218 // Different type hierarchy. The test will fail. 219 *outcome = false; 220 return true; 221 } 222 return false; 223} 224 225void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 226 HInstruction* object = check_cast->InputAt(0); 227 if (!object->CanBeNull() || IsDominatedByInputNullCheck(check_cast)) { 228 check_cast->ClearMustDoNullCheck(); 229 } 230 231 if (object->IsNullConstant()) { 232 check_cast->GetBlock()->RemoveInstruction(check_cast); 233 if (stats_ != nullptr) { 234 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 235 } 236 return; 237 } 238 239 bool outcome; 240 if (TypeCheckHasKnownOutcome(check_cast->InputAt(1)->AsLoadClass(), object, &outcome)) { 241 if (outcome) { 242 check_cast->GetBlock()->RemoveInstruction(check_cast); 243 if (stats_ != nullptr) { 244 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 245 } 246 } else { 247 // Don't do anything for exceptional cases for now. Ideally we should remove 248 // all instructions and blocks this instruction dominates. 249 } 250 } 251} 252 253void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { 254 HInstruction* object = instruction->InputAt(0); 255 bool can_be_null = true; 256 if (!object->CanBeNull() || IsDominatedByInputNullCheck(instruction)) { 257 can_be_null = false; 258 instruction->ClearMustDoNullCheck(); 259 } 260 261 HGraph* graph = GetGraph(); 262 if (object->IsNullConstant()) { 263 instruction->ReplaceWith(graph->GetIntConstant(0)); 264 instruction->GetBlock()->RemoveInstruction(instruction); 265 RecordSimplification(); 266 return; 267 } 268 269 bool outcome; 270 if (TypeCheckHasKnownOutcome(instruction->InputAt(1)->AsLoadClass(), object, &outcome)) { 271 if (outcome && can_be_null) { 272 // Type test will succeed, we just need a null test. 273 HNotEqual* test = new (graph->GetArena()) HNotEqual(graph->GetNullConstant(), object); 274 instruction->GetBlock()->InsertInstructionBefore(test, instruction); 275 instruction->ReplaceWith(test); 276 } else { 277 // We've statically determined the result of the instanceof. 278 instruction->ReplaceWith(graph->GetIntConstant(outcome)); 279 } 280 RecordSimplification(); 281 instruction->GetBlock()->RemoveInstruction(instruction); 282 } 283} 284 285void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) { 286 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 287 && !instruction->GetValue()->CanBeNull()) { 288 instruction->ClearValueCanBeNull(); 289 } 290} 291 292void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) { 293 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 294 && !instruction->GetValue()->CanBeNull()) { 295 instruction->ClearValueCanBeNull(); 296 } 297} 298 299void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { 300 HBasicBlock* block = check->GetBlock(); 301 // Currently always keep the suspend check at entry. 302 if (block->IsEntryBlock()) return; 303 304 // Currently always keep suspend checks at loop entry. 305 if (block->IsLoopHeader() && block->GetFirstInstruction() == check) { 306 DCHECK(block->GetLoopInformation()->GetSuspendCheck() == check); 307 return; 308 } 309 310 // Remove the suspend check that was added at build time for the baseline 311 // compiler. 312 block->RemoveInstruction(check); 313} 314 315void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 316 HInstruction* input_const = equal->GetConstantRight(); 317 if (input_const != nullptr) { 318 HInstruction* input_value = equal->GetLeastConstantLeft(); 319 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 320 HBasicBlock* block = equal->GetBlock(); 321 // We are comparing the boolean to a constant which is of type int and can 322 // be any constant. 323 if (input_const->AsIntConstant()->IsOne()) { 324 // Replace (bool_value == true) with bool_value 325 equal->ReplaceWith(input_value); 326 block->RemoveInstruction(equal); 327 RecordSimplification(); 328 } else if (input_const->AsIntConstant()->IsZero()) { 329 // Replace (bool_value == false) with !bool_value 330 block->ReplaceAndRemoveInstructionWith( 331 equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 332 RecordSimplification(); 333 } else { 334 // Replace (bool_value == integer_not_zero_nor_one_constant) with false 335 equal->ReplaceWith(GetGraph()->GetIntConstant(0)); 336 block->RemoveInstruction(equal); 337 RecordSimplification(); 338 } 339 } else { 340 VisitCondition(equal); 341 } 342 } else { 343 VisitCondition(equal); 344 } 345} 346 347void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { 348 HInstruction* input_const = not_equal->GetConstantRight(); 349 if (input_const != nullptr) { 350 HInstruction* input_value = not_equal->GetLeastConstantLeft(); 351 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 352 HBasicBlock* block = not_equal->GetBlock(); 353 // We are comparing the boolean to a constant which is of type int and can 354 // be any constant. 355 if (input_const->AsIntConstant()->IsOne()) { 356 // Replace (bool_value != true) with !bool_value 357 block->ReplaceAndRemoveInstructionWith( 358 not_equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 359 RecordSimplification(); 360 } else if (input_const->AsIntConstant()->IsZero()) { 361 // Replace (bool_value != false) with bool_value 362 not_equal->ReplaceWith(input_value); 363 block->RemoveInstruction(not_equal); 364 RecordSimplification(); 365 } else { 366 // Replace (bool_value != integer_not_zero_nor_one_constant) with true 367 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1)); 368 block->RemoveInstruction(not_equal); 369 RecordSimplification(); 370 } 371 } else { 372 VisitCondition(not_equal); 373 } 374 } else { 375 VisitCondition(not_equal); 376 } 377} 378 379void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { 380 HInstruction* parent = bool_not->InputAt(0); 381 if (parent->IsBooleanNot()) { 382 HInstruction* value = parent->InputAt(0); 383 // Replace (!(!bool_value)) with bool_value 384 bool_not->ReplaceWith(value); 385 bool_not->GetBlock()->RemoveInstruction(bool_not); 386 // It is possible that `parent` is dead at this point but we leave 387 // its removal to DCE for simplicity. 388 RecordSimplification(); 389 } 390} 391 392void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 393 HInstruction* input = instruction->InputAt(0); 394 // If the array is a NewArray with constant size, replace the array length 395 // with the constant instruction. This helps the bounds check elimination phase. 396 if (input->IsNewArray()) { 397 input = input->InputAt(0); 398 if (input->IsIntConstant()) { 399 instruction->ReplaceWith(input); 400 } 401 } 402} 403 404void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 405 HInstruction* value = instruction->GetValue(); 406 if (value->GetType() != Primitive::kPrimNot) return; 407 408 if (value->IsArrayGet()) { 409 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 410 // If the code is just swapping elements in the array, no need for a type check. 411 instruction->ClearNeedsTypeCheck(); 412 } 413 } 414 415 if (value->IsNullConstant()) { 416 instruction->ClearNeedsTypeCheck(); 417 } 418 419 if (!value->CanBeNull()) { 420 instruction->ClearValueCanBeNull(); 421 } 422} 423 424void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 425 if (instruction->GetResultType() == instruction->GetInputType()) { 426 // Remove the instruction if it's converting to the same type. 427 instruction->ReplaceWith(instruction->GetInput()); 428 instruction->GetBlock()->RemoveInstruction(instruction); 429 } 430} 431 432void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 433 HConstant* input_cst = instruction->GetConstantRight(); 434 HInstruction* input_other = instruction->GetLeastConstantLeft(); 435 if ((input_cst != nullptr) && input_cst->IsZero()) { 436 // Replace code looking like 437 // ADD dst, src, 0 438 // with 439 // src 440 instruction->ReplaceWith(input_other); 441 instruction->GetBlock()->RemoveInstruction(instruction); 442 return; 443 } 444 445 HInstruction* left = instruction->GetLeft(); 446 HInstruction* right = instruction->GetRight(); 447 bool left_is_neg = left->IsNeg(); 448 bool right_is_neg = right->IsNeg(); 449 450 if (left_is_neg && right_is_neg) { 451 if (TryMoveNegOnInputsAfterBinop(instruction)) { 452 return; 453 } 454 } 455 456 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg(); 457 if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) { 458 // Replace code looking like 459 // NEG tmp, b 460 // ADD dst, a, tmp 461 // with 462 // SUB dst, a, b 463 // We do not perform the optimization if the input negation has environment 464 // uses or multiple non-environment uses as it could lead to worse code. In 465 // particular, we do not want the live range of `b` to be extended if we are 466 // not sure the initial 'NEG' instruction can be removed. 467 HInstruction* other = left_is_neg ? right : left; 468 HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput()); 469 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub); 470 RecordSimplification(); 471 neg->GetBlock()->RemoveInstruction(neg); 472 } 473} 474 475void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 476 HConstant* input_cst = instruction->GetConstantRight(); 477 HInstruction* input_other = instruction->GetLeastConstantLeft(); 478 479 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 480 // Replace code looking like 481 // AND dst, src, 0xFFF...FF 482 // with 483 // src 484 instruction->ReplaceWith(input_other); 485 instruction->GetBlock()->RemoveInstruction(instruction); 486 return; 487 } 488 489 // We assume that GVN has run before, so we only perform a pointer comparison. 490 // If for some reason the values are equal but the pointers are different, we 491 // are still correct and only miss an optimization opportunity. 492 if (instruction->GetLeft() == instruction->GetRight()) { 493 // Replace code looking like 494 // AND dst, src, src 495 // with 496 // src 497 instruction->ReplaceWith(instruction->GetLeft()); 498 instruction->GetBlock()->RemoveInstruction(instruction); 499 } 500} 501 502void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) { 503 VisitCondition(condition); 504} 505 506void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) { 507 VisitCondition(condition); 508} 509 510void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) { 511 VisitCondition(condition); 512} 513 514void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) { 515 VisitCondition(condition); 516} 517 518void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) { 519 // Try to fold an HCompare into this HCondition. 520 521 // This simplification is currently supported on x86, x86_64, ARM and ARM64. 522 // TODO: Implement it for MIPS64. 523 InstructionSet instruction_set = GetGraph()->GetInstructionSet(); 524 if (instruction_set == kMips64) { 525 return; 526 } 527 528 HInstruction* left = condition->GetLeft(); 529 HInstruction* right = condition->GetRight(); 530 // We can only replace an HCondition which compares a Compare to 0. 531 // Both 'dx' and 'jack' generate a compare to 0 when compiling a 532 // condition with a long, float or double comparison as input. 533 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) { 534 // Conversion is not possible. 535 return; 536 } 537 538 // Is the Compare only used for this purpose? 539 if (!left->GetUses().HasOnlyOneUse()) { 540 // Someone else also wants the result of the compare. 541 return; 542 } 543 544 if (!left->GetEnvUses().IsEmpty()) { 545 // There is a reference to the compare result in an environment. Do we really need it? 546 if (GetGraph()->IsDebuggable()) { 547 return; 548 } 549 550 // We have to ensure that there are no deopt points in the sequence. 551 if (left->HasAnyEnvironmentUseBefore(condition)) { 552 return; 553 } 554 } 555 556 // Clean up any environment uses from the HCompare, if any. 557 left->RemoveEnvironmentUsers(); 558 559 // We have decided to fold the HCompare into the HCondition. Transfer the information. 560 condition->SetBias(left->AsCompare()->GetBias()); 561 562 // Replace the operands of the HCondition. 563 condition->ReplaceInput(left->InputAt(0), 0); 564 condition->ReplaceInput(left->InputAt(1), 1); 565 566 // Remove the HCompare. 567 left->GetBlock()->RemoveInstruction(left); 568 569 RecordSimplification(); 570} 571 572void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 573 HConstant* input_cst = instruction->GetConstantRight(); 574 HInstruction* input_other = instruction->GetLeastConstantLeft(); 575 Primitive::Type type = instruction->GetType(); 576 577 if ((input_cst != nullptr) && input_cst->IsOne()) { 578 // Replace code looking like 579 // DIV dst, src, 1 580 // with 581 // src 582 instruction->ReplaceWith(input_other); 583 instruction->GetBlock()->RemoveInstruction(instruction); 584 return; 585 } 586 587 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 588 // Replace code looking like 589 // DIV dst, src, -1 590 // with 591 // NEG dst, src 592 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 593 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other)); 594 RecordSimplification(); 595 return; 596 } 597 598 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) { 599 // Try replacing code looking like 600 // DIV dst, src, constant 601 // with 602 // MUL dst, src, 1 / constant 603 HConstant* reciprocal = nullptr; 604 if (type == Primitive::Primitive::kPrimDouble) { 605 double value = input_cst->AsDoubleConstant()->GetValue(); 606 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 607 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 608 } 609 } else { 610 DCHECK_EQ(type, Primitive::kPrimFloat); 611 float value = input_cst->AsFloatConstant()->GetValue(); 612 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 613 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 614 } 615 } 616 617 if (reciprocal != nullptr) { 618 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 619 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal)); 620 RecordSimplification(); 621 return; 622 } 623 } 624} 625 626void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 627 HConstant* input_cst = instruction->GetConstantRight(); 628 HInstruction* input_other = instruction->GetLeastConstantLeft(); 629 Primitive::Type type = instruction->GetType(); 630 HBasicBlock* block = instruction->GetBlock(); 631 ArenaAllocator* allocator = GetGraph()->GetArena(); 632 633 if (input_cst == nullptr) { 634 return; 635 } 636 637 if (input_cst->IsOne()) { 638 // Replace code looking like 639 // MUL dst, src, 1 640 // with 641 // src 642 instruction->ReplaceWith(input_other); 643 instruction->GetBlock()->RemoveInstruction(instruction); 644 return; 645 } 646 647 if (input_cst->IsMinusOne() && 648 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 649 // Replace code looking like 650 // MUL dst, src, -1 651 // with 652 // NEG dst, src 653 HNeg* neg = new (allocator) HNeg(type, input_other); 654 block->ReplaceAndRemoveInstructionWith(instruction, neg); 655 RecordSimplification(); 656 return; 657 } 658 659 if (Primitive::IsFloatingPointType(type) && 660 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 661 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 662 // Replace code looking like 663 // FP_MUL dst, src, 2.0 664 // with 665 // FP_ADD dst, src, src 666 // The 'int' and 'long' cases are handled below. 667 block->ReplaceAndRemoveInstructionWith(instruction, 668 new (allocator) HAdd(type, input_other, input_other)); 669 RecordSimplification(); 670 return; 671 } 672 673 if (Primitive::IsIntOrLongType(type)) { 674 int64_t factor = Int64FromConstant(input_cst); 675 // Even though constant propagation also takes care of the zero case, other 676 // optimizations can lead to having a zero multiplication. 677 if (factor == 0) { 678 // Replace code looking like 679 // MUL dst, src, 0 680 // with 681 // 0 682 instruction->ReplaceWith(input_cst); 683 instruction->GetBlock()->RemoveInstruction(instruction); 684 } else if (IsPowerOfTwo(factor)) { 685 // Replace code looking like 686 // MUL dst, src, pow_of_2 687 // with 688 // SHL dst, src, log2(pow_of_2) 689 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 690 HShl* shl = new(allocator) HShl(type, input_other, shift); 691 block->ReplaceAndRemoveInstructionWith(instruction, shl); 692 RecordSimplification(); 693 } 694 } 695} 696 697void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 698 HInstruction* input = instruction->GetInput(); 699 if (input->IsNeg()) { 700 // Replace code looking like 701 // NEG tmp, src 702 // NEG dst, tmp 703 // with 704 // src 705 HNeg* previous_neg = input->AsNeg(); 706 instruction->ReplaceWith(previous_neg->GetInput()); 707 instruction->GetBlock()->RemoveInstruction(instruction); 708 // We perform the optimization even if the input negation has environment 709 // uses since it allows removing the current instruction. But we only delete 710 // the input negation only if it is does not have any uses left. 711 if (!previous_neg->HasUses()) { 712 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 713 } 714 RecordSimplification(); 715 return; 716 } 717 718 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 719 !Primitive::IsFloatingPointType(input->GetType())) { 720 // Replace code looking like 721 // SUB tmp, a, b 722 // NEG dst, tmp 723 // with 724 // SUB dst, b, a 725 // We do not perform the optimization if the input subtraction has 726 // environment uses or multiple non-environment uses as it could lead to 727 // worse code. In particular, we do not want the live ranges of `a` and `b` 728 // to be extended if we are not sure the initial 'SUB' instruction can be 729 // removed. 730 // We do not perform optimization for fp because we could lose the sign of zero. 731 HSub* sub = input->AsSub(); 732 HSub* new_sub = 733 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft()); 734 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 735 if (!sub->HasUses()) { 736 sub->GetBlock()->RemoveInstruction(sub); 737 } 738 RecordSimplification(); 739 } 740} 741 742void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 743 HInstruction* input = instruction->GetInput(); 744 if (input->IsNot()) { 745 // Replace code looking like 746 // NOT tmp, src 747 // NOT dst, tmp 748 // with 749 // src 750 // We perform the optimization even if the input negation has environment 751 // uses since it allows removing the current instruction. But we only delete 752 // the input negation only if it is does not have any uses left. 753 HNot* previous_not = input->AsNot(); 754 instruction->ReplaceWith(previous_not->GetInput()); 755 instruction->GetBlock()->RemoveInstruction(instruction); 756 if (!previous_not->HasUses()) { 757 previous_not->GetBlock()->RemoveInstruction(previous_not); 758 } 759 RecordSimplification(); 760 } 761} 762 763void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 764 HConstant* input_cst = instruction->GetConstantRight(); 765 HInstruction* input_other = instruction->GetLeastConstantLeft(); 766 767 if ((input_cst != nullptr) && input_cst->IsZero()) { 768 // Replace code looking like 769 // OR dst, src, 0 770 // with 771 // src 772 instruction->ReplaceWith(input_other); 773 instruction->GetBlock()->RemoveInstruction(instruction); 774 return; 775 } 776 777 // We assume that GVN has run before, so we only perform a pointer comparison. 778 // If for some reason the values are equal but the pointers are different, we 779 // are still correct and only miss an optimization opportunity. 780 if (instruction->GetLeft() == instruction->GetRight()) { 781 // Replace code looking like 782 // OR dst, src, src 783 // with 784 // src 785 instruction->ReplaceWith(instruction->GetLeft()); 786 instruction->GetBlock()->RemoveInstruction(instruction); 787 } 788} 789 790void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 791 VisitShift(instruction); 792} 793 794void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 795 VisitShift(instruction); 796} 797 798void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 799 HConstant* input_cst = instruction->GetConstantRight(); 800 HInstruction* input_other = instruction->GetLeastConstantLeft(); 801 802 if ((input_cst != nullptr) && input_cst->IsZero()) { 803 // Replace code looking like 804 // SUB dst, src, 0 805 // with 806 // src 807 instruction->ReplaceWith(input_other); 808 instruction->GetBlock()->RemoveInstruction(instruction); 809 return; 810 } 811 812 Primitive::Type type = instruction->GetType(); 813 if (!Primitive::IsIntegralType(type)) { 814 return; 815 } 816 817 HBasicBlock* block = instruction->GetBlock(); 818 ArenaAllocator* allocator = GetGraph()->GetArena(); 819 820 HInstruction* left = instruction->GetLeft(); 821 HInstruction* right = instruction->GetRight(); 822 if (left->IsConstant()) { 823 if (Int64FromConstant(left->AsConstant()) == 0) { 824 // Replace code looking like 825 // SUB dst, 0, src 826 // with 827 // NEG dst, src 828 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 829 // `x` is `0.0`, the former expression yields `0.0`, while the later 830 // yields `-0.0`. 831 HNeg* neg = new (allocator) HNeg(type, right); 832 block->ReplaceAndRemoveInstructionWith(instruction, neg); 833 RecordSimplification(); 834 return; 835 } 836 } 837 838 if (left->IsNeg() && right->IsNeg()) { 839 if (TryMoveNegOnInputsAfterBinop(instruction)) { 840 return; 841 } 842 } 843 844 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 845 // Replace code looking like 846 // NEG tmp, b 847 // SUB dst, a, tmp 848 // with 849 // ADD dst, a, b 850 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput()); 851 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 852 RecordSimplification(); 853 right->GetBlock()->RemoveInstruction(right); 854 return; 855 } 856 857 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 858 // Replace code looking like 859 // NEG tmp, a 860 // SUB dst, tmp, b 861 // with 862 // ADD tmp, a, b 863 // NEG dst, tmp 864 // The second version is not intrinsically better, but enables more 865 // transformations. 866 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right); 867 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 868 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add); 869 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 870 instruction->ReplaceWith(neg); 871 instruction->GetBlock()->RemoveInstruction(instruction); 872 RecordSimplification(); 873 left->GetBlock()->RemoveInstruction(left); 874 } 875} 876 877void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 878 VisitShift(instruction); 879} 880 881void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 882 HConstant* input_cst = instruction->GetConstantRight(); 883 HInstruction* input_other = instruction->GetLeastConstantLeft(); 884 885 if ((input_cst != nullptr) && input_cst->IsZero()) { 886 // Replace code looking like 887 // XOR dst, src, 0 888 // with 889 // src 890 instruction->ReplaceWith(input_other); 891 instruction->GetBlock()->RemoveInstruction(instruction); 892 return; 893 } 894 895 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 896 // Replace code looking like 897 // XOR dst, src, 0xFFF...FF 898 // with 899 // NOT dst, src 900 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 901 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 902 RecordSimplification(); 903 return; 904 } 905} 906 907void InstructionSimplifierVisitor::VisitFakeString(HFakeString* instruction) { 908 HInstruction* actual_string = nullptr; 909 910 // Find the string we need to replace this instruction with. The actual string is 911 // the return value of a StringFactory call. 912 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 913 HInstruction* use = it.Current()->GetUser(); 914 if (use->IsInvokeStaticOrDirect() 915 && use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)) { 916 use->AsInvokeStaticOrDirect()->RemoveFakeStringArgumentAsLastInput(); 917 actual_string = use; 918 break; 919 } 920 } 921 922 // Check that there is no other instruction that thinks it is the factory for that string. 923 if (kIsDebugBuild) { 924 CHECK(actual_string != nullptr); 925 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 926 HInstruction* use = it.Current()->GetUser(); 927 if (use->IsInvokeStaticOrDirect()) { 928 CHECK(!use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)); 929 } 930 } 931 } 932 933 // We need to remove any environment uses of the fake string that are not dominated by 934 // `actual_string` to null. 935 for (HUseIterator<HEnvironment*> it(instruction->GetEnvUses()); !it.Done(); it.Advance()) { 936 HEnvironment* environment = it.Current()->GetUser(); 937 if (!actual_string->StrictlyDominates(environment->GetHolder())) { 938 environment->RemoveAsUserOfInput(it.Current()->GetIndex()); 939 environment->SetRawEnvAt(it.Current()->GetIndex(), nullptr); 940 } 941 } 942 943 // Only uses dominated by `actual_string` must remain. We can safely replace and remove 944 // `instruction`. 945 instruction->ReplaceWith(actual_string); 946 instruction->GetBlock()->RemoveInstruction(instruction); 947} 948 949} // namespace art 950