instruction_simplifier.cc revision f9d741e32c6f1629ce70eefc68d3363fa1cfd696
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 "intrinsics.h" 20#include "mirror/class-inl.h" 21#include "scoped_thread_state_change.h" 22 23namespace art { 24 25class InstructionSimplifierVisitor : public HGraphDelegateVisitor { 26 public: 27 InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats) 28 : HGraphDelegateVisitor(graph), 29 stats_(stats) {} 30 31 void Run(); 32 33 private: 34 void RecordSimplification() { 35 simplification_occurred_ = true; 36 simplifications_at_current_position_++; 37 if (stats_) { 38 stats_->RecordStat(kInstructionSimplifications); 39 } 40 } 41 42 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop); 43 void VisitShift(HBinaryOperation* shift); 44 45 void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE; 46 void VisitEqual(HEqual* equal) OVERRIDE; 47 void VisitNotEqual(HNotEqual* equal) OVERRIDE; 48 void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE; 49 void VisitInstanceFieldSet(HInstanceFieldSet* equal) OVERRIDE; 50 void VisitStaticFieldSet(HStaticFieldSet* equal) OVERRIDE; 51 void VisitArraySet(HArraySet* equal) OVERRIDE; 52 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 53 void VisitNullCheck(HNullCheck* instruction) OVERRIDE; 54 void VisitArrayLength(HArrayLength* instruction) OVERRIDE; 55 void VisitCheckCast(HCheckCast* instruction) OVERRIDE; 56 void VisitAdd(HAdd* instruction) OVERRIDE; 57 void VisitAnd(HAnd* instruction) OVERRIDE; 58 void VisitCondition(HCondition* instruction) OVERRIDE; 59 void VisitGreaterThan(HGreaterThan* condition) OVERRIDE; 60 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) OVERRIDE; 61 void VisitLessThan(HLessThan* condition) OVERRIDE; 62 void VisitLessThanOrEqual(HLessThanOrEqual* condition) OVERRIDE; 63 void VisitDiv(HDiv* instruction) OVERRIDE; 64 void VisitMul(HMul* instruction) OVERRIDE; 65 void VisitNeg(HNeg* instruction) OVERRIDE; 66 void VisitNot(HNot* instruction) OVERRIDE; 67 void VisitOr(HOr* instruction) OVERRIDE; 68 void VisitShl(HShl* instruction) OVERRIDE; 69 void VisitShr(HShr* instruction) OVERRIDE; 70 void VisitSub(HSub* instruction) OVERRIDE; 71 void VisitUShr(HUShr* instruction) OVERRIDE; 72 void VisitXor(HXor* instruction) OVERRIDE; 73 void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; 74 void VisitFakeString(HFakeString* fake_string) OVERRIDE; 75 void VisitInvoke(HInvoke* invoke) OVERRIDE; 76 void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE; 77 78 bool CanEnsureNotNullAt(HInstruction* instr, HInstruction* at) const; 79 80 void SimplifySystemArrayCopy(HInvoke* invoke); 81 void SimplifyStringEquals(HInvoke* invoke); 82 83 OptimizingCompilerStats* stats_; 84 bool simplification_occurred_ = false; 85 int simplifications_at_current_position_ = 0; 86 // We ensure we do not loop infinitely. The value is a finger in the air guess 87 // that should allow enough simplification. 88 static constexpr int kMaxSamePositionSimplifications = 10; 89}; 90 91void InstructionSimplifier::Run() { 92 InstructionSimplifierVisitor visitor(graph_, stats_); 93 visitor.Run(); 94} 95 96void InstructionSimplifierVisitor::Run() { 97 // Iterate in reverse post order to open up more simplifications to users 98 // of instructions that got simplified. 99 for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) { 100 // The simplification of an instruction to another instruction may yield 101 // possibilities for other simplifications. So although we perform a reverse 102 // post order visit, we sometimes need to revisit an instruction index. 103 simplification_occurred_ = false; 104 VisitBasicBlock(it.Current()); 105 if (simplification_occurred_ && 106 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) { 107 // New simplifications may be applicable to the instruction at the 108 // current index, so don't advance the iterator. 109 continue; 110 } 111 simplifications_at_current_position_ = 0; 112 it.Advance(); 113 } 114} 115 116namespace { 117 118bool AreAllBitsSet(HConstant* constant) { 119 return Int64FromConstant(constant) == -1; 120} 121 122} // namespace 123 124// Returns true if the code was simplified to use only one negation operation 125// after the binary operation instead of one on each of the inputs. 126bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) { 127 DCHECK(binop->IsAdd() || binop->IsSub()); 128 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg()); 129 HNeg* left_neg = binop->GetLeft()->AsNeg(); 130 HNeg* right_neg = binop->GetRight()->AsNeg(); 131 if (!left_neg->HasOnlyOneNonEnvironmentUse() || 132 !right_neg->HasOnlyOneNonEnvironmentUse()) { 133 return false; 134 } 135 // Replace code looking like 136 // NEG tmp1, a 137 // NEG tmp2, b 138 // ADD dst, tmp1, tmp2 139 // with 140 // ADD tmp, a, b 141 // NEG dst, tmp 142 // Note that we cannot optimize `(-a) + (-b)` to `-(a + b)` for floating-point. 143 // When `a` is `-0.0` and `b` is `0.0`, the former expression yields `0.0`, 144 // while the later yields `-0.0`. 145 if (!Primitive::IsIntegralType(binop->GetType())) { 146 return false; 147 } 148 binop->ReplaceInput(left_neg->GetInput(), 0); 149 binop->ReplaceInput(right_neg->GetInput(), 1); 150 left_neg->GetBlock()->RemoveInstruction(left_neg); 151 right_neg->GetBlock()->RemoveInstruction(right_neg); 152 HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop); 153 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext()); 154 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0); 155 RecordSimplification(); 156 return true; 157} 158 159void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 160 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 161 HConstant* input_cst = instruction->GetConstantRight(); 162 HInstruction* input_other = instruction->GetLeastConstantLeft(); 163 164 if (input_cst != nullptr) { 165 if (input_cst->IsZero()) { 166 // Replace code looking like 167 // SHL dst, src, 0 168 // with 169 // src 170 instruction->ReplaceWith(input_other); 171 instruction->GetBlock()->RemoveInstruction(instruction); 172 } 173 } 174} 175 176void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 177 HInstruction* obj = null_check->InputAt(0); 178 if (!obj->CanBeNull()) { 179 null_check->ReplaceWith(obj); 180 null_check->GetBlock()->RemoveInstruction(null_check); 181 if (stats_ != nullptr) { 182 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 183 } 184 } 185} 186 187bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInstruction* at) const { 188 if (!input->CanBeNull()) { 189 return true; 190 } 191 192 for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) { 193 HInstruction* use = it.Current()->GetUser(); 194 if (use->IsNullCheck() && use->StrictlyDominates(at)) { 195 return true; 196 } 197 } 198 199 return false; 200} 201 202// Returns whether doing a type test between the class of `object` against `klass` has 203// a statically known outcome. The result of the test is stored in `outcome`. 204static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) { 205 DCHECK(!object->IsNullConstant()) << "Null constants should be special cased"; 206 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); 207 ScopedObjectAccess soa(Thread::Current()); 208 if (!obj_rti.IsValid()) { 209 // We run the simplifier before the reference type propagation so type info might not be 210 // available. 211 return false; 212 } 213 214 ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI(); 215 if (!class_rti.IsValid()) { 216 // Happens when the loaded class is unresolved. 217 return false; 218 } 219 DCHECK(class_rti.IsExact()); 220 if (class_rti.IsSupertypeOf(obj_rti)) { 221 *outcome = true; 222 return true; 223 } else if (obj_rti.IsExact()) { 224 // The test failed at compile time so will also fail at runtime. 225 *outcome = false; 226 return true; 227 } else if (!class_rti.IsInterface() 228 && !obj_rti.IsInterface() 229 && !obj_rti.IsSupertypeOf(class_rti)) { 230 // Different type hierarchy. The test will fail. 231 *outcome = false; 232 return true; 233 } 234 return false; 235} 236 237void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 238 HInstruction* object = check_cast->InputAt(0); 239 HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); 240 if (load_class->NeedsAccessCheck()) { 241 // If we need to perform an access check we cannot remove the instruction. 242 return; 243 } 244 245 if (CanEnsureNotNullAt(object, check_cast)) { 246 check_cast->ClearMustDoNullCheck(); 247 } 248 249 if (object->IsNullConstant()) { 250 check_cast->GetBlock()->RemoveInstruction(check_cast); 251 if (stats_ != nullptr) { 252 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 253 } 254 return; 255 } 256 257 bool outcome; 258 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) { 259 if (outcome) { 260 check_cast->GetBlock()->RemoveInstruction(check_cast); 261 if (stats_ != nullptr) { 262 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 263 } 264 if (!load_class->HasUses()) { 265 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 266 // However, here we know that it cannot because the checkcast was successfull, hence 267 // the class was already loaded. 268 load_class->GetBlock()->RemoveInstruction(load_class); 269 } 270 } else { 271 // Don't do anything for exceptional cases for now. Ideally we should remove 272 // all instructions and blocks this instruction dominates. 273 } 274 } 275} 276 277void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { 278 HInstruction* object = instruction->InputAt(0); 279 HLoadClass* load_class = instruction->InputAt(1)->AsLoadClass(); 280 if (load_class->NeedsAccessCheck()) { 281 // If we need to perform an access check we cannot remove the instruction. 282 return; 283 } 284 285 bool can_be_null = true; 286 if (CanEnsureNotNullAt(object, instruction)) { 287 can_be_null = false; 288 instruction->ClearMustDoNullCheck(); 289 } 290 291 HGraph* graph = GetGraph(); 292 if (object->IsNullConstant()) { 293 instruction->ReplaceWith(graph->GetIntConstant(0)); 294 instruction->GetBlock()->RemoveInstruction(instruction); 295 RecordSimplification(); 296 return; 297 } 298 299 bool outcome; 300 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) { 301 if (outcome && can_be_null) { 302 // Type test will succeed, we just need a null test. 303 HNotEqual* test = new (graph->GetArena()) HNotEqual(graph->GetNullConstant(), object); 304 instruction->GetBlock()->InsertInstructionBefore(test, instruction); 305 instruction->ReplaceWith(test); 306 } else { 307 // We've statically determined the result of the instanceof. 308 instruction->ReplaceWith(graph->GetIntConstant(outcome)); 309 } 310 RecordSimplification(); 311 instruction->GetBlock()->RemoveInstruction(instruction); 312 if (outcome && !load_class->HasUses()) { 313 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 314 // However, here we know that it cannot because the instanceof check was successfull, hence 315 // the class was already loaded. 316 load_class->GetBlock()->RemoveInstruction(load_class); 317 } 318 } 319} 320 321void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) { 322 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 323 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 324 instruction->ClearValueCanBeNull(); 325 } 326} 327 328void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) { 329 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 330 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 331 instruction->ClearValueCanBeNull(); 332 } 333} 334 335void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { 336 HBasicBlock* block = check->GetBlock(); 337 // Currently always keep the suspend check at entry. 338 if (block->IsEntryBlock()) return; 339 340 // Currently always keep suspend checks at loop entry. 341 if (block->IsLoopHeader() && block->GetFirstInstruction() == check) { 342 DCHECK(block->GetLoopInformation()->GetSuspendCheck() == check); 343 return; 344 } 345 346 // Remove the suspend check that was added at build time for the baseline 347 // compiler. 348 block->RemoveInstruction(check); 349} 350 351void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 352 HInstruction* input_const = equal->GetConstantRight(); 353 if (input_const != nullptr) { 354 HInstruction* input_value = equal->GetLeastConstantLeft(); 355 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 356 HBasicBlock* block = equal->GetBlock(); 357 // We are comparing the boolean to a constant which is of type int and can 358 // be any constant. 359 if (input_const->AsIntConstant()->IsOne()) { 360 // Replace (bool_value == true) with bool_value 361 equal->ReplaceWith(input_value); 362 block->RemoveInstruction(equal); 363 RecordSimplification(); 364 } else if (input_const->AsIntConstant()->IsZero()) { 365 // Replace (bool_value == false) with !bool_value 366 block->ReplaceAndRemoveInstructionWith( 367 equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 368 RecordSimplification(); 369 } else { 370 // Replace (bool_value == integer_not_zero_nor_one_constant) with false 371 equal->ReplaceWith(GetGraph()->GetIntConstant(0)); 372 block->RemoveInstruction(equal); 373 RecordSimplification(); 374 } 375 } else { 376 VisitCondition(equal); 377 } 378 } else { 379 VisitCondition(equal); 380 } 381} 382 383void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { 384 HInstruction* input_const = not_equal->GetConstantRight(); 385 if (input_const != nullptr) { 386 HInstruction* input_value = not_equal->GetLeastConstantLeft(); 387 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 388 HBasicBlock* block = not_equal->GetBlock(); 389 // We are comparing the boolean to a constant which is of type int and can 390 // be any constant. 391 if (input_const->AsIntConstant()->IsOne()) { 392 // Replace (bool_value != true) with !bool_value 393 block->ReplaceAndRemoveInstructionWith( 394 not_equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 395 RecordSimplification(); 396 } else if (input_const->AsIntConstant()->IsZero()) { 397 // Replace (bool_value != false) with bool_value 398 not_equal->ReplaceWith(input_value); 399 block->RemoveInstruction(not_equal); 400 RecordSimplification(); 401 } else { 402 // Replace (bool_value != integer_not_zero_nor_one_constant) with true 403 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1)); 404 block->RemoveInstruction(not_equal); 405 RecordSimplification(); 406 } 407 } else { 408 VisitCondition(not_equal); 409 } 410 } else { 411 VisitCondition(not_equal); 412 } 413} 414 415void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { 416 HInstruction* parent = bool_not->InputAt(0); 417 if (parent->IsBooleanNot()) { 418 HInstruction* value = parent->InputAt(0); 419 // Replace (!(!bool_value)) with bool_value 420 bool_not->ReplaceWith(value); 421 bool_not->GetBlock()->RemoveInstruction(bool_not); 422 // It is possible that `parent` is dead at this point but we leave 423 // its removal to DCE for simplicity. 424 RecordSimplification(); 425 } 426} 427 428void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 429 HInstruction* input = instruction->InputAt(0); 430 // If the array is a NewArray with constant size, replace the array length 431 // with the constant instruction. This helps the bounds check elimination phase. 432 if (input->IsNewArray()) { 433 input = input->InputAt(0); 434 if (input->IsIntConstant()) { 435 instruction->ReplaceWith(input); 436 } 437 } 438} 439 440void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 441 HInstruction* value = instruction->GetValue(); 442 if (value->GetType() != Primitive::kPrimNot) return; 443 444 if (CanEnsureNotNullAt(value, instruction)) { 445 instruction->ClearValueCanBeNull(); 446 } 447 448 if (value->IsArrayGet()) { 449 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 450 // If the code is just swapping elements in the array, no need for a type check. 451 instruction->ClearNeedsTypeCheck(); 452 return; 453 } 454 } 455 456 if (value->IsNullConstant()) { 457 instruction->ClearNeedsTypeCheck(); 458 return; 459 } 460 461 ScopedObjectAccess soa(Thread::Current()); 462 ReferenceTypeInfo array_rti = instruction->GetArray()->GetReferenceTypeInfo(); 463 ReferenceTypeInfo value_rti = value->GetReferenceTypeInfo(); 464 if (!array_rti.IsValid()) { 465 return; 466 } 467 468 if (value_rti.IsValid() && array_rti.CanArrayHold(value_rti)) { 469 instruction->ClearNeedsTypeCheck(); 470 return; 471 } 472 473 if (array_rti.IsObjectArray()) { 474 if (array_rti.IsExact()) { 475 instruction->ClearNeedsTypeCheck(); 476 return; 477 } 478 instruction->SetStaticTypeOfArrayIsObjectArray(); 479 } 480} 481 482void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 483 if (instruction->GetResultType() == instruction->GetInputType()) { 484 // Remove the instruction if it's converting to the same type. 485 instruction->ReplaceWith(instruction->GetInput()); 486 instruction->GetBlock()->RemoveInstruction(instruction); 487 } 488} 489 490void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 491 HConstant* input_cst = instruction->GetConstantRight(); 492 HInstruction* input_other = instruction->GetLeastConstantLeft(); 493 if ((input_cst != nullptr) && input_cst->IsZero()) { 494 // Replace code looking like 495 // ADD dst, src, 0 496 // with 497 // src 498 // Note that we cannot optimize `x + 0.0` to `x` for floating-point. When 499 // `x` is `-0.0`, the former expression yields `0.0`, while the later 500 // yields `-0.0`. 501 if (Primitive::IsIntegralType(instruction->GetType())) { 502 instruction->ReplaceWith(input_other); 503 instruction->GetBlock()->RemoveInstruction(instruction); 504 return; 505 } 506 } 507 508 HInstruction* left = instruction->GetLeft(); 509 HInstruction* right = instruction->GetRight(); 510 bool left_is_neg = left->IsNeg(); 511 bool right_is_neg = right->IsNeg(); 512 513 if (left_is_neg && right_is_neg) { 514 if (TryMoveNegOnInputsAfterBinop(instruction)) { 515 return; 516 } 517 } 518 519 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg(); 520 if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) { 521 // Replace code looking like 522 // NEG tmp, b 523 // ADD dst, a, tmp 524 // with 525 // SUB dst, a, b 526 // We do not perform the optimization if the input negation has environment 527 // uses or multiple non-environment uses as it could lead to worse code. In 528 // particular, we do not want the live range of `b` to be extended if we are 529 // not sure the initial 'NEG' instruction can be removed. 530 HInstruction* other = left_is_neg ? right : left; 531 HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput()); 532 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub); 533 RecordSimplification(); 534 neg->GetBlock()->RemoveInstruction(neg); 535 } 536} 537 538void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 539 HConstant* input_cst = instruction->GetConstantRight(); 540 HInstruction* input_other = instruction->GetLeastConstantLeft(); 541 542 if (input_cst != nullptr) { 543 int64_t value = Int64FromConstant(input_cst); 544 if (value == -1) { 545 // Replace code looking like 546 // AND dst, src, 0xFFF...FF 547 // with 548 // src 549 instruction->ReplaceWith(input_other); 550 instruction->GetBlock()->RemoveInstruction(instruction); 551 RecordSimplification(); 552 return; 553 } 554 // Eliminate And from UShr+And if the And-mask contains all the bits that 555 // can be non-zero after UShr. Transform Shr+And to UShr if the And-mask 556 // precisely clears the shifted-in sign bits. 557 if ((input_other->IsUShr() || input_other->IsShr()) && input_other->InputAt(1)->IsConstant()) { 558 size_t reg_bits = (instruction->GetResultType() == Primitive::kPrimLong) ? 64 : 32; 559 size_t shift = Int64FromConstant(input_other->InputAt(1)->AsConstant()) & (reg_bits - 1); 560 size_t num_tail_bits_set = CTZ(value + 1); 561 if ((num_tail_bits_set >= reg_bits - shift) && input_other->IsUShr()) { 562 // This AND clears only bits known to be clear, for example "(x >>> 24) & 0xff". 563 instruction->ReplaceWith(input_other); 564 instruction->GetBlock()->RemoveInstruction(instruction); 565 RecordSimplification(); 566 return; 567 } else if ((num_tail_bits_set == reg_bits - shift) && IsPowerOfTwo(value + 1) && 568 input_other->HasOnlyOneNonEnvironmentUse()) { 569 DCHECK(input_other->IsShr()); // For UShr, we would have taken the branch above. 570 // Replace SHR+AND with USHR, for example "(x >> 24) & 0xff" -> "x >>> 24". 571 HUShr* ushr = new (GetGraph()->GetArena()) HUShr(instruction->GetType(), 572 input_other->InputAt(0), 573 input_other->InputAt(1), 574 input_other->GetDexPc()); 575 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, ushr); 576 input_other->GetBlock()->RemoveInstruction(input_other); 577 RecordSimplification(); 578 return; 579 } 580 } 581 } 582 583 // We assume that GVN has run before, so we only perform a pointer comparison. 584 // If for some reason the values are equal but the pointers are different, we 585 // are still correct and only miss an optimization opportunity. 586 if (instruction->GetLeft() == instruction->GetRight()) { 587 // Replace code looking like 588 // AND dst, src, src 589 // with 590 // src 591 instruction->ReplaceWith(instruction->GetLeft()); 592 instruction->GetBlock()->RemoveInstruction(instruction); 593 } 594} 595 596void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) { 597 VisitCondition(condition); 598} 599 600void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) { 601 VisitCondition(condition); 602} 603 604void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) { 605 VisitCondition(condition); 606} 607 608void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) { 609 VisitCondition(condition); 610} 611 612// TODO: unsigned comparisons too? 613 614void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) { 615 // Try to fold an HCompare into this HCondition. 616 617 // This simplification is currently supported on x86, x86_64, ARM and ARM64. 618 // TODO: Implement it for MIPS and MIPS64. 619 InstructionSet instruction_set = GetGraph()->GetInstructionSet(); 620 if (instruction_set == kMips || instruction_set == kMips64) { 621 return; 622 } 623 624 HInstruction* left = condition->GetLeft(); 625 HInstruction* right = condition->GetRight(); 626 // We can only replace an HCondition which compares a Compare to 0. 627 // Both 'dx' and 'jack' generate a compare to 0 when compiling a 628 // condition with a long, float or double comparison as input. 629 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) { 630 // Conversion is not possible. 631 return; 632 } 633 634 // Is the Compare only used for this purpose? 635 if (!left->GetUses().HasOnlyOneUse()) { 636 // Someone else also wants the result of the compare. 637 return; 638 } 639 640 if (!left->GetEnvUses().IsEmpty()) { 641 // There is a reference to the compare result in an environment. Do we really need it? 642 if (GetGraph()->IsDebuggable()) { 643 return; 644 } 645 646 // We have to ensure that there are no deopt points in the sequence. 647 if (left->HasAnyEnvironmentUseBefore(condition)) { 648 return; 649 } 650 } 651 652 // Clean up any environment uses from the HCompare, if any. 653 left->RemoveEnvironmentUsers(); 654 655 // We have decided to fold the HCompare into the HCondition. Transfer the information. 656 condition->SetBias(left->AsCompare()->GetBias()); 657 658 // Replace the operands of the HCondition. 659 condition->ReplaceInput(left->InputAt(0), 0); 660 condition->ReplaceInput(left->InputAt(1), 1); 661 662 // Remove the HCompare. 663 left->GetBlock()->RemoveInstruction(left); 664 665 RecordSimplification(); 666} 667 668void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 669 HConstant* input_cst = instruction->GetConstantRight(); 670 HInstruction* input_other = instruction->GetLeastConstantLeft(); 671 Primitive::Type type = instruction->GetType(); 672 673 if ((input_cst != nullptr) && input_cst->IsOne()) { 674 // Replace code looking like 675 // DIV dst, src, 1 676 // with 677 // src 678 instruction->ReplaceWith(input_other); 679 instruction->GetBlock()->RemoveInstruction(instruction); 680 return; 681 } 682 683 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 684 // Replace code looking like 685 // DIV dst, src, -1 686 // with 687 // NEG dst, src 688 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 689 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other)); 690 RecordSimplification(); 691 return; 692 } 693 694 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) { 695 // Try replacing code looking like 696 // DIV dst, src, constant 697 // with 698 // MUL dst, src, 1 / constant 699 HConstant* reciprocal = nullptr; 700 if (type == Primitive::Primitive::kPrimDouble) { 701 double value = input_cst->AsDoubleConstant()->GetValue(); 702 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 703 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 704 } 705 } else { 706 DCHECK_EQ(type, Primitive::kPrimFloat); 707 float value = input_cst->AsFloatConstant()->GetValue(); 708 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 709 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 710 } 711 } 712 713 if (reciprocal != nullptr) { 714 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 715 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal)); 716 RecordSimplification(); 717 return; 718 } 719 } 720} 721 722void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 723 HConstant* input_cst = instruction->GetConstantRight(); 724 HInstruction* input_other = instruction->GetLeastConstantLeft(); 725 Primitive::Type type = instruction->GetType(); 726 HBasicBlock* block = instruction->GetBlock(); 727 ArenaAllocator* allocator = GetGraph()->GetArena(); 728 729 if (input_cst == nullptr) { 730 return; 731 } 732 733 if (input_cst->IsOne()) { 734 // Replace code looking like 735 // MUL dst, src, 1 736 // with 737 // src 738 instruction->ReplaceWith(input_other); 739 instruction->GetBlock()->RemoveInstruction(instruction); 740 return; 741 } 742 743 if (input_cst->IsMinusOne() && 744 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 745 // Replace code looking like 746 // MUL dst, src, -1 747 // with 748 // NEG dst, src 749 HNeg* neg = new (allocator) HNeg(type, input_other); 750 block->ReplaceAndRemoveInstructionWith(instruction, neg); 751 RecordSimplification(); 752 return; 753 } 754 755 if (Primitive::IsFloatingPointType(type) && 756 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 757 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 758 // Replace code looking like 759 // FP_MUL dst, src, 2.0 760 // with 761 // FP_ADD dst, src, src 762 // The 'int' and 'long' cases are handled below. 763 block->ReplaceAndRemoveInstructionWith(instruction, 764 new (allocator) HAdd(type, input_other, input_other)); 765 RecordSimplification(); 766 return; 767 } 768 769 if (Primitive::IsIntOrLongType(type)) { 770 int64_t factor = Int64FromConstant(input_cst); 771 // Even though constant propagation also takes care of the zero case, other 772 // optimizations can lead to having a zero multiplication. 773 if (factor == 0) { 774 // Replace code looking like 775 // MUL dst, src, 0 776 // with 777 // 0 778 instruction->ReplaceWith(input_cst); 779 instruction->GetBlock()->RemoveInstruction(instruction); 780 } else if (IsPowerOfTwo(factor)) { 781 // Replace code looking like 782 // MUL dst, src, pow_of_2 783 // with 784 // SHL dst, src, log2(pow_of_2) 785 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 786 HShl* shl = new(allocator) HShl(type, input_other, shift); 787 block->ReplaceAndRemoveInstructionWith(instruction, shl); 788 RecordSimplification(); 789 } 790 } 791} 792 793void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 794 HInstruction* input = instruction->GetInput(); 795 if (input->IsNeg()) { 796 // Replace code looking like 797 // NEG tmp, src 798 // NEG dst, tmp 799 // with 800 // src 801 HNeg* previous_neg = input->AsNeg(); 802 instruction->ReplaceWith(previous_neg->GetInput()); 803 instruction->GetBlock()->RemoveInstruction(instruction); 804 // We perform the optimization even if the input negation has environment 805 // uses since it allows removing the current instruction. But we only delete 806 // the input negation only if it is does not have any uses left. 807 if (!previous_neg->HasUses()) { 808 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 809 } 810 RecordSimplification(); 811 return; 812 } 813 814 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 815 !Primitive::IsFloatingPointType(input->GetType())) { 816 // Replace code looking like 817 // SUB tmp, a, b 818 // NEG dst, tmp 819 // with 820 // SUB dst, b, a 821 // We do not perform the optimization if the input subtraction has 822 // environment uses or multiple non-environment uses as it could lead to 823 // worse code. In particular, we do not want the live ranges of `a` and `b` 824 // to be extended if we are not sure the initial 'SUB' instruction can be 825 // removed. 826 // We do not perform optimization for fp because we could lose the sign of zero. 827 HSub* sub = input->AsSub(); 828 HSub* new_sub = 829 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft()); 830 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 831 if (!sub->HasUses()) { 832 sub->GetBlock()->RemoveInstruction(sub); 833 } 834 RecordSimplification(); 835 } 836} 837 838void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 839 HInstruction* input = instruction->GetInput(); 840 if (input->IsNot()) { 841 // Replace code looking like 842 // NOT tmp, src 843 // NOT dst, tmp 844 // with 845 // src 846 // We perform the optimization even if the input negation has environment 847 // uses since it allows removing the current instruction. But we only delete 848 // the input negation only if it is does not have any uses left. 849 HNot* previous_not = input->AsNot(); 850 instruction->ReplaceWith(previous_not->GetInput()); 851 instruction->GetBlock()->RemoveInstruction(instruction); 852 if (!previous_not->HasUses()) { 853 previous_not->GetBlock()->RemoveInstruction(previous_not); 854 } 855 RecordSimplification(); 856 } 857} 858 859void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 860 HConstant* input_cst = instruction->GetConstantRight(); 861 HInstruction* input_other = instruction->GetLeastConstantLeft(); 862 863 if ((input_cst != nullptr) && input_cst->IsZero()) { 864 // Replace code looking like 865 // OR dst, src, 0 866 // with 867 // src 868 instruction->ReplaceWith(input_other); 869 instruction->GetBlock()->RemoveInstruction(instruction); 870 return; 871 } 872 873 // We assume that GVN has run before, so we only perform a pointer comparison. 874 // If for some reason the values are equal but the pointers are different, we 875 // are still correct and only miss an optimization opportunity. 876 if (instruction->GetLeft() == instruction->GetRight()) { 877 // Replace code looking like 878 // OR dst, src, src 879 // with 880 // src 881 instruction->ReplaceWith(instruction->GetLeft()); 882 instruction->GetBlock()->RemoveInstruction(instruction); 883 } 884} 885 886void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 887 VisitShift(instruction); 888} 889 890void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 891 VisitShift(instruction); 892} 893 894void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 895 HConstant* input_cst = instruction->GetConstantRight(); 896 HInstruction* input_other = instruction->GetLeastConstantLeft(); 897 898 Primitive::Type type = instruction->GetType(); 899 if (Primitive::IsFloatingPointType(type)) { 900 return; 901 } 902 903 if ((input_cst != nullptr) && input_cst->IsZero()) { 904 // Replace code looking like 905 // SUB dst, src, 0 906 // with 907 // src 908 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When 909 // `x` is `-0.0`, the former expression yields `0.0`, while the later 910 // yields `-0.0`. 911 instruction->ReplaceWith(input_other); 912 instruction->GetBlock()->RemoveInstruction(instruction); 913 return; 914 } 915 916 HBasicBlock* block = instruction->GetBlock(); 917 ArenaAllocator* allocator = GetGraph()->GetArena(); 918 919 HInstruction* left = instruction->GetLeft(); 920 HInstruction* right = instruction->GetRight(); 921 if (left->IsConstant()) { 922 if (Int64FromConstant(left->AsConstant()) == 0) { 923 // Replace code looking like 924 // SUB dst, 0, src 925 // with 926 // NEG dst, src 927 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 928 // `x` is `0.0`, the former expression yields `0.0`, while the later 929 // yields `-0.0`. 930 HNeg* neg = new (allocator) HNeg(type, right); 931 block->ReplaceAndRemoveInstructionWith(instruction, neg); 932 RecordSimplification(); 933 return; 934 } 935 } 936 937 if (left->IsNeg() && right->IsNeg()) { 938 if (TryMoveNegOnInputsAfterBinop(instruction)) { 939 return; 940 } 941 } 942 943 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 944 // Replace code looking like 945 // NEG tmp, b 946 // SUB dst, a, tmp 947 // with 948 // ADD dst, a, b 949 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput()); 950 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 951 RecordSimplification(); 952 right->GetBlock()->RemoveInstruction(right); 953 return; 954 } 955 956 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 957 // Replace code looking like 958 // NEG tmp, a 959 // SUB dst, tmp, b 960 // with 961 // ADD tmp, a, b 962 // NEG dst, tmp 963 // The second version is not intrinsically better, but enables more 964 // transformations. 965 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right); 966 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 967 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add); 968 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 969 instruction->ReplaceWith(neg); 970 instruction->GetBlock()->RemoveInstruction(instruction); 971 RecordSimplification(); 972 left->GetBlock()->RemoveInstruction(left); 973 } 974} 975 976void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 977 VisitShift(instruction); 978} 979 980void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 981 HConstant* input_cst = instruction->GetConstantRight(); 982 HInstruction* input_other = instruction->GetLeastConstantLeft(); 983 984 if ((input_cst != nullptr) && input_cst->IsZero()) { 985 // Replace code looking like 986 // XOR dst, src, 0 987 // with 988 // src 989 instruction->ReplaceWith(input_other); 990 instruction->GetBlock()->RemoveInstruction(instruction); 991 return; 992 } 993 994 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 995 // Replace code looking like 996 // XOR dst, src, 0xFFF...FF 997 // with 998 // NOT dst, src 999 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 1000 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 1001 RecordSimplification(); 1002 return; 1003 } 1004} 1005 1006void InstructionSimplifierVisitor::VisitFakeString(HFakeString* instruction) { 1007 HInstruction* actual_string = nullptr; 1008 1009 // Find the string we need to replace this instruction with. The actual string is 1010 // the return value of a StringFactory call. 1011 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1012 HInstruction* use = it.Current()->GetUser(); 1013 if (use->IsInvokeStaticOrDirect() 1014 && use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)) { 1015 use->AsInvokeStaticOrDirect()->RemoveFakeStringArgumentAsLastInput(); 1016 actual_string = use; 1017 break; 1018 } 1019 } 1020 1021 // Check that there is no other instruction that thinks it is the factory for that string. 1022 if (kIsDebugBuild) { 1023 CHECK(actual_string != nullptr); 1024 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1025 HInstruction* use = it.Current()->GetUser(); 1026 if (use->IsInvokeStaticOrDirect()) { 1027 CHECK(!use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)); 1028 } 1029 } 1030 } 1031 1032 // We need to remove any environment uses of the fake string that are not dominated by 1033 // `actual_string` to null. 1034 for (HUseIterator<HEnvironment*> it(instruction->GetEnvUses()); !it.Done(); it.Advance()) { 1035 HEnvironment* environment = it.Current()->GetUser(); 1036 if (!actual_string->StrictlyDominates(environment->GetHolder())) { 1037 environment->RemoveAsUserOfInput(it.Current()->GetIndex()); 1038 environment->SetRawEnvAt(it.Current()->GetIndex(), nullptr); 1039 } 1040 } 1041 1042 // Only uses dominated by `actual_string` must remain. We can safely replace and remove 1043 // `instruction`. 1044 instruction->ReplaceWith(actual_string); 1045 instruction->GetBlock()->RemoveInstruction(instruction); 1046} 1047 1048void InstructionSimplifierVisitor::SimplifyStringEquals(HInvoke* instruction) { 1049 HInstruction* argument = instruction->InputAt(1); 1050 HInstruction* receiver = instruction->InputAt(0); 1051 if (receiver == argument) { 1052 // Because String.equals is an instance call, the receiver is 1053 // a null check if we don't know it's null. The argument however, will 1054 // be the actual object. So we cannot end up in a situation where both 1055 // are equal but could be null. 1056 DCHECK(CanEnsureNotNullAt(argument, instruction)); 1057 instruction->ReplaceWith(GetGraph()->GetIntConstant(1)); 1058 instruction->GetBlock()->RemoveInstruction(instruction); 1059 } else { 1060 StringEqualsOptimizations optimizations(instruction); 1061 if (CanEnsureNotNullAt(argument, instruction)) { 1062 optimizations.SetArgumentNotNull(); 1063 } 1064 ScopedObjectAccess soa(Thread::Current()); 1065 ReferenceTypeInfo argument_rti = argument->GetReferenceTypeInfo(); 1066 if (argument_rti.IsValid() && argument_rti.IsStringClass()) { 1067 optimizations.SetArgumentIsString(); 1068 } 1069 } 1070} 1071 1072static bool IsArrayLengthOf(HInstruction* potential_length, HInstruction* potential_array) { 1073 if (potential_length->IsArrayLength()) { 1074 return potential_length->InputAt(0) == potential_array; 1075 } 1076 1077 if (potential_array->IsNewArray()) { 1078 return potential_array->InputAt(0) == potential_length; 1079 } 1080 1081 return false; 1082} 1083 1084void InstructionSimplifierVisitor::SimplifySystemArrayCopy(HInvoke* instruction) { 1085 HInstruction* source = instruction->InputAt(0); 1086 HInstruction* destination = instruction->InputAt(2); 1087 HInstruction* count = instruction->InputAt(4); 1088 SystemArrayCopyOptimizations optimizations(instruction); 1089 if (CanEnsureNotNullAt(source, instruction)) { 1090 optimizations.SetSourceIsNotNull(); 1091 } 1092 if (CanEnsureNotNullAt(destination, instruction)) { 1093 optimizations.SetDestinationIsNotNull(); 1094 } 1095 if (destination == source) { 1096 optimizations.SetDestinationIsSource(); 1097 } 1098 1099 if (IsArrayLengthOf(count, source)) { 1100 optimizations.SetCountIsSourceLength(); 1101 } 1102 1103 if (IsArrayLengthOf(count, destination)) { 1104 optimizations.SetCountIsDestinationLength(); 1105 } 1106 1107 { 1108 ScopedObjectAccess soa(Thread::Current()); 1109 ReferenceTypeInfo destination_rti = destination->GetReferenceTypeInfo(); 1110 if (destination_rti.IsValid()) { 1111 if (destination_rti.IsObjectArray()) { 1112 if (destination_rti.IsExact()) { 1113 optimizations.SetDoesNotNeedTypeCheck(); 1114 } 1115 optimizations.SetDestinationIsTypedObjectArray(); 1116 } 1117 if (destination_rti.IsPrimitiveArrayClass()) { 1118 optimizations.SetDestinationIsPrimitiveArray(); 1119 } else if (destination_rti.IsNonPrimitiveArrayClass()) { 1120 optimizations.SetDestinationIsNonPrimitiveArray(); 1121 } 1122 } 1123 ReferenceTypeInfo source_rti = source->GetReferenceTypeInfo(); 1124 if (source_rti.IsValid()) { 1125 if (destination_rti.IsValid() && destination_rti.CanArrayHoldValuesOf(source_rti)) { 1126 optimizations.SetDoesNotNeedTypeCheck(); 1127 } 1128 if (source_rti.IsPrimitiveArrayClass()) { 1129 optimizations.SetSourceIsPrimitiveArray(); 1130 } else if (source_rti.IsNonPrimitiveArrayClass()) { 1131 optimizations.SetSourceIsNonPrimitiveArray(); 1132 } 1133 } 1134 } 1135} 1136 1137void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) { 1138 if (instruction->GetIntrinsic() == Intrinsics::kStringEquals) { 1139 SimplifyStringEquals(instruction); 1140 } else if (instruction->GetIntrinsic() == Intrinsics::kSystemArrayCopy) { 1141 SimplifySystemArrayCopy(instruction); 1142 } 1143} 1144 1145void InstructionSimplifierVisitor::VisitDeoptimize(HDeoptimize* deoptimize) { 1146 HInstruction* cond = deoptimize->InputAt(0); 1147 if (cond->IsConstant()) { 1148 if (cond->AsIntConstant()->IsZero()) { 1149 // Never deopt: instruction can be removed. 1150 deoptimize->GetBlock()->RemoveInstruction(deoptimize); 1151 } else { 1152 // Always deopt. 1153 } 1154 } 1155} 1156 1157} // namespace art 1158