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