instruction_simplifier.cc revision 299a93993fb8f3efbf0465cf674d80c3bcfdc66c
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 HInstruction* left = condition->GetLeft(); 781 HInstruction* right = condition->GetRight(); 782 // We can only replace an HCondition which compares a Compare to 0. 783 // Both 'dx' and 'jack' generate a compare to 0 when compiling a 784 // condition with a long, float or double comparison as input. 785 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) { 786 // Conversion is not possible. 787 return; 788 } 789 790 // Is the Compare only used for this purpose? 791 if (!left->GetUses().HasOnlyOneUse()) { 792 // Someone else also wants the result of the compare. 793 return; 794 } 795 796 if (!left->GetEnvUses().IsEmpty()) { 797 // There is a reference to the compare result in an environment. Do we really need it? 798 if (GetGraph()->IsDebuggable()) { 799 return; 800 } 801 802 // We have to ensure that there are no deopt points in the sequence. 803 if (left->HasAnyEnvironmentUseBefore(condition)) { 804 return; 805 } 806 } 807 808 // Clean up any environment uses from the HCompare, if any. 809 left->RemoveEnvironmentUsers(); 810 811 // We have decided to fold the HCompare into the HCondition. Transfer the information. 812 condition->SetBias(left->AsCompare()->GetBias()); 813 814 // Replace the operands of the HCondition. 815 condition->ReplaceInput(left->InputAt(0), 0); 816 condition->ReplaceInput(left->InputAt(1), 1); 817 818 // Remove the HCompare. 819 left->GetBlock()->RemoveInstruction(left); 820 821 RecordSimplification(); 822} 823 824void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 825 HConstant* input_cst = instruction->GetConstantRight(); 826 HInstruction* input_other = instruction->GetLeastConstantLeft(); 827 Primitive::Type type = instruction->GetType(); 828 829 if ((input_cst != nullptr) && input_cst->IsOne()) { 830 // Replace code looking like 831 // DIV dst, src, 1 832 // with 833 // src 834 instruction->ReplaceWith(input_other); 835 instruction->GetBlock()->RemoveInstruction(instruction); 836 return; 837 } 838 839 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 840 // Replace code looking like 841 // DIV dst, src, -1 842 // with 843 // NEG dst, src 844 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 845 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other)); 846 RecordSimplification(); 847 return; 848 } 849 850 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) { 851 // Try replacing code looking like 852 // DIV dst, src, constant 853 // with 854 // MUL dst, src, 1 / constant 855 HConstant* reciprocal = nullptr; 856 if (type == Primitive::Primitive::kPrimDouble) { 857 double value = input_cst->AsDoubleConstant()->GetValue(); 858 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 859 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 860 } 861 } else { 862 DCHECK_EQ(type, Primitive::kPrimFloat); 863 float value = input_cst->AsFloatConstant()->GetValue(); 864 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 865 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 866 } 867 } 868 869 if (reciprocal != nullptr) { 870 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 871 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal)); 872 RecordSimplification(); 873 return; 874 } 875 } 876} 877 878void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 879 HConstant* input_cst = instruction->GetConstantRight(); 880 HInstruction* input_other = instruction->GetLeastConstantLeft(); 881 Primitive::Type type = instruction->GetType(); 882 HBasicBlock* block = instruction->GetBlock(); 883 ArenaAllocator* allocator = GetGraph()->GetArena(); 884 885 if (input_cst == nullptr) { 886 return; 887 } 888 889 if (input_cst->IsOne()) { 890 // Replace code looking like 891 // MUL dst, src, 1 892 // with 893 // src 894 instruction->ReplaceWith(input_other); 895 instruction->GetBlock()->RemoveInstruction(instruction); 896 return; 897 } 898 899 if (input_cst->IsMinusOne() && 900 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 901 // Replace code looking like 902 // MUL dst, src, -1 903 // with 904 // NEG dst, src 905 HNeg* neg = new (allocator) HNeg(type, input_other); 906 block->ReplaceAndRemoveInstructionWith(instruction, neg); 907 RecordSimplification(); 908 return; 909 } 910 911 if (Primitive::IsFloatingPointType(type) && 912 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 913 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 914 // Replace code looking like 915 // FP_MUL dst, src, 2.0 916 // with 917 // FP_ADD dst, src, src 918 // The 'int' and 'long' cases are handled below. 919 block->ReplaceAndRemoveInstructionWith(instruction, 920 new (allocator) HAdd(type, input_other, input_other)); 921 RecordSimplification(); 922 return; 923 } 924 925 if (Primitive::IsIntOrLongType(type)) { 926 int64_t factor = Int64FromConstant(input_cst); 927 // Even though constant propagation also takes care of the zero case, other 928 // optimizations can lead to having a zero multiplication. 929 if (factor == 0) { 930 // Replace code looking like 931 // MUL dst, src, 0 932 // with 933 // 0 934 instruction->ReplaceWith(input_cst); 935 instruction->GetBlock()->RemoveInstruction(instruction); 936 } else if (IsPowerOfTwo(factor)) { 937 // Replace code looking like 938 // MUL dst, src, pow_of_2 939 // with 940 // SHL dst, src, log2(pow_of_2) 941 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 942 HShl* shl = new(allocator) HShl(type, input_other, shift); 943 block->ReplaceAndRemoveInstructionWith(instruction, shl); 944 RecordSimplification(); 945 } else if (IsPowerOfTwo(factor - 1)) { 946 // Transform code looking like 947 // MUL dst, src, (2^n + 1) 948 // into 949 // SHL tmp, src, n 950 // ADD dst, src, tmp 951 HShl* shl = new (allocator) HShl(type, 952 input_other, 953 GetGraph()->GetIntConstant(WhichPowerOf2(factor - 1))); 954 HAdd* add = new (allocator) HAdd(type, input_other, shl); 955 956 block->InsertInstructionBefore(shl, instruction); 957 block->ReplaceAndRemoveInstructionWith(instruction, add); 958 RecordSimplification(); 959 } else if (IsPowerOfTwo(factor + 1)) { 960 // Transform code looking like 961 // MUL dst, src, (2^n - 1) 962 // into 963 // SHL tmp, src, n 964 // SUB dst, tmp, src 965 HShl* shl = new (allocator) HShl(type, 966 input_other, 967 GetGraph()->GetIntConstant(WhichPowerOf2(factor + 1))); 968 HSub* sub = new (allocator) HSub(type, shl, input_other); 969 970 block->InsertInstructionBefore(shl, instruction); 971 block->ReplaceAndRemoveInstructionWith(instruction, sub); 972 RecordSimplification(); 973 } 974 } 975} 976 977void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 978 HInstruction* input = instruction->GetInput(); 979 if (input->IsNeg()) { 980 // Replace code looking like 981 // NEG tmp, src 982 // NEG dst, tmp 983 // with 984 // src 985 HNeg* previous_neg = input->AsNeg(); 986 instruction->ReplaceWith(previous_neg->GetInput()); 987 instruction->GetBlock()->RemoveInstruction(instruction); 988 // We perform the optimization even if the input negation has environment 989 // uses since it allows removing the current instruction. But we only delete 990 // the input negation only if it is does not have any uses left. 991 if (!previous_neg->HasUses()) { 992 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 993 } 994 RecordSimplification(); 995 return; 996 } 997 998 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 999 !Primitive::IsFloatingPointType(input->GetType())) { 1000 // Replace code looking like 1001 // SUB tmp, a, b 1002 // NEG dst, tmp 1003 // with 1004 // SUB dst, b, a 1005 // We do not perform the optimization if the input subtraction has 1006 // environment uses or multiple non-environment uses as it could lead to 1007 // worse code. In particular, we do not want the live ranges of `a` and `b` 1008 // to be extended if we are not sure the initial 'SUB' instruction can be 1009 // removed. 1010 // We do not perform optimization for fp because we could lose the sign of zero. 1011 HSub* sub = input->AsSub(); 1012 HSub* new_sub = 1013 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft()); 1014 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 1015 if (!sub->HasUses()) { 1016 sub->GetBlock()->RemoveInstruction(sub); 1017 } 1018 RecordSimplification(); 1019 } 1020} 1021 1022void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 1023 HInstruction* input = instruction->GetInput(); 1024 if (input->IsNot()) { 1025 // Replace code looking like 1026 // NOT tmp, src 1027 // NOT dst, tmp 1028 // with 1029 // src 1030 // We perform the optimization even if the input negation has environment 1031 // uses since it allows removing the current instruction. But we only delete 1032 // the input negation only if it is does not have any uses left. 1033 HNot* previous_not = input->AsNot(); 1034 instruction->ReplaceWith(previous_not->GetInput()); 1035 instruction->GetBlock()->RemoveInstruction(instruction); 1036 if (!previous_not->HasUses()) { 1037 previous_not->GetBlock()->RemoveInstruction(previous_not); 1038 } 1039 RecordSimplification(); 1040 } 1041} 1042 1043void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 1044 HConstant* input_cst = instruction->GetConstantRight(); 1045 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1046 1047 if ((input_cst != nullptr) && input_cst->IsZero()) { 1048 // Replace code looking like 1049 // OR dst, src, 0 1050 // with 1051 // src 1052 instruction->ReplaceWith(input_other); 1053 instruction->GetBlock()->RemoveInstruction(instruction); 1054 return; 1055 } 1056 1057 // We assume that GVN has run before, so we only perform a pointer comparison. 1058 // If for some reason the values are equal but the pointers are different, we 1059 // are still correct and only miss an optimization opportunity. 1060 if (instruction->GetLeft() == instruction->GetRight()) { 1061 // Replace code looking like 1062 // OR dst, src, src 1063 // with 1064 // src 1065 instruction->ReplaceWith(instruction->GetLeft()); 1066 instruction->GetBlock()->RemoveInstruction(instruction); 1067 return; 1068 } 1069 1070 TryReplaceWithRotate(instruction); 1071} 1072 1073void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 1074 VisitShift(instruction); 1075} 1076 1077void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 1078 VisitShift(instruction); 1079} 1080 1081void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 1082 HConstant* input_cst = instruction->GetConstantRight(); 1083 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1084 1085 Primitive::Type type = instruction->GetType(); 1086 if (Primitive::IsFloatingPointType(type)) { 1087 return; 1088 } 1089 1090 if ((input_cst != nullptr) && input_cst->IsZero()) { 1091 // Replace code looking like 1092 // SUB dst, src, 0 1093 // with 1094 // src 1095 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When 1096 // `x` is `-0.0`, the former expression yields `0.0`, while the later 1097 // yields `-0.0`. 1098 instruction->ReplaceWith(input_other); 1099 instruction->GetBlock()->RemoveInstruction(instruction); 1100 return; 1101 } 1102 1103 HBasicBlock* block = instruction->GetBlock(); 1104 ArenaAllocator* allocator = GetGraph()->GetArena(); 1105 1106 HInstruction* left = instruction->GetLeft(); 1107 HInstruction* right = instruction->GetRight(); 1108 if (left->IsConstant()) { 1109 if (Int64FromConstant(left->AsConstant()) == 0) { 1110 // Replace code looking like 1111 // SUB dst, 0, src 1112 // with 1113 // NEG dst, src 1114 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 1115 // `x` is `0.0`, the former expression yields `0.0`, while the later 1116 // yields `-0.0`. 1117 HNeg* neg = new (allocator) HNeg(type, right); 1118 block->ReplaceAndRemoveInstructionWith(instruction, neg); 1119 RecordSimplification(); 1120 return; 1121 } 1122 } 1123 1124 if (left->IsNeg() && right->IsNeg()) { 1125 if (TryMoveNegOnInputsAfterBinop(instruction)) { 1126 return; 1127 } 1128 } 1129 1130 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 1131 // Replace code looking like 1132 // NEG tmp, b 1133 // SUB dst, a, tmp 1134 // with 1135 // ADD dst, a, b 1136 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput()); 1137 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 1138 RecordSimplification(); 1139 right->GetBlock()->RemoveInstruction(right); 1140 return; 1141 } 1142 1143 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 1144 // Replace code looking like 1145 // NEG tmp, a 1146 // SUB dst, tmp, b 1147 // with 1148 // ADD tmp, a, b 1149 // NEG dst, tmp 1150 // The second version is not intrinsically better, but enables more 1151 // transformations. 1152 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right); 1153 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 1154 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add); 1155 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 1156 instruction->ReplaceWith(neg); 1157 instruction->GetBlock()->RemoveInstruction(instruction); 1158 RecordSimplification(); 1159 left->GetBlock()->RemoveInstruction(left); 1160 } 1161} 1162 1163void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 1164 VisitShift(instruction); 1165} 1166 1167void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 1168 HConstant* input_cst = instruction->GetConstantRight(); 1169 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1170 1171 if ((input_cst != nullptr) && input_cst->IsZero()) { 1172 // Replace code looking like 1173 // XOR dst, src, 0 1174 // with 1175 // src 1176 instruction->ReplaceWith(input_other); 1177 instruction->GetBlock()->RemoveInstruction(instruction); 1178 return; 1179 } 1180 1181 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 1182 // Replace code looking like 1183 // XOR dst, src, 0xFFF...FF 1184 // with 1185 // NOT dst, src 1186 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 1187 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 1188 RecordSimplification(); 1189 return; 1190 } 1191 1192 TryReplaceWithRotate(instruction); 1193} 1194 1195void InstructionSimplifierVisitor::VisitFakeString(HFakeString* instruction) { 1196 HInstruction* actual_string = nullptr; 1197 1198 // Find the string we need to replace this instruction with. The actual string is 1199 // the return value of a StringFactory call. 1200 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1201 HInstruction* use = it.Current()->GetUser(); 1202 if (use->IsInvokeStaticOrDirect() 1203 && use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)) { 1204 use->AsInvokeStaticOrDirect()->RemoveFakeStringArgumentAsLastInput(); 1205 actual_string = use; 1206 break; 1207 } 1208 } 1209 1210 // Check that there is no other instruction that thinks it is the factory for that string. 1211 if (kIsDebugBuild) { 1212 CHECK(actual_string != nullptr); 1213 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1214 HInstruction* use = it.Current()->GetUser(); 1215 if (use->IsInvokeStaticOrDirect()) { 1216 CHECK(!use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)); 1217 } 1218 } 1219 } 1220 1221 // We need to remove any environment uses of the fake string that are not dominated by 1222 // `actual_string` to null. 1223 for (HUseIterator<HEnvironment*> it(instruction->GetEnvUses()); !it.Done(); it.Advance()) { 1224 HEnvironment* environment = it.Current()->GetUser(); 1225 if (!actual_string->StrictlyDominates(environment->GetHolder())) { 1226 environment->RemoveAsUserOfInput(it.Current()->GetIndex()); 1227 environment->SetRawEnvAt(it.Current()->GetIndex(), nullptr); 1228 } 1229 } 1230 1231 // Only uses dominated by `actual_string` must remain. We can safely replace and remove 1232 // `instruction`. 1233 instruction->ReplaceWith(actual_string); 1234 instruction->GetBlock()->RemoveInstruction(instruction); 1235} 1236 1237void InstructionSimplifierVisitor::SimplifyStringEquals(HInvoke* instruction) { 1238 HInstruction* argument = instruction->InputAt(1); 1239 HInstruction* receiver = instruction->InputAt(0); 1240 if (receiver == argument) { 1241 // Because String.equals is an instance call, the receiver is 1242 // a null check if we don't know it's null. The argument however, will 1243 // be the actual object. So we cannot end up in a situation where both 1244 // are equal but could be null. 1245 DCHECK(CanEnsureNotNullAt(argument, instruction)); 1246 instruction->ReplaceWith(GetGraph()->GetIntConstant(1)); 1247 instruction->GetBlock()->RemoveInstruction(instruction); 1248 } else { 1249 StringEqualsOptimizations optimizations(instruction); 1250 if (CanEnsureNotNullAt(argument, instruction)) { 1251 optimizations.SetArgumentNotNull(); 1252 } 1253 ScopedObjectAccess soa(Thread::Current()); 1254 ReferenceTypeInfo argument_rti = argument->GetReferenceTypeInfo(); 1255 if (argument_rti.IsValid() && argument_rti.IsStringClass()) { 1256 optimizations.SetArgumentIsString(); 1257 } 1258 } 1259} 1260 1261void InstructionSimplifierVisitor::SimplifyRotate(HInvoke* invoke, bool is_left) { 1262 DCHECK(invoke->IsInvokeStaticOrDirect()); 1263 DCHECK_EQ(invoke->GetOriginalInvokeType(), InvokeType::kStatic); 1264 // This simplification is currently supported on x86, x86_64, ARM and ARM64. 1265 // TODO: Implement it for MIPS/64. 1266 const InstructionSet instruction_set = GetGraph()->GetInstructionSet(); 1267 switch (instruction_set) { 1268 case kArm: 1269 case kArm64: 1270 case kThumb2: 1271 case kX86: 1272 case kX86_64: 1273 break; 1274 default: 1275 return; 1276 } 1277 HInstruction* value = invoke->InputAt(0); 1278 HInstruction* distance = invoke->InputAt(1); 1279 // Replace the invoke with an HRor. 1280 if (is_left) { 1281 distance = new (GetGraph()->GetArena()) HNeg(distance->GetType(), distance); 1282 invoke->GetBlock()->InsertInstructionBefore(distance, invoke); 1283 } 1284 HRor* ror = new (GetGraph()->GetArena()) HRor(value->GetType(), value, distance); 1285 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, ror); 1286 // Remove ClinitCheck and LoadClass, if possible. 1287 HInstruction* clinit = invoke->InputAt(invoke->InputCount() - 1); 1288 if (clinit->IsClinitCheck() && !clinit->HasUses()) { 1289 clinit->GetBlock()->RemoveInstruction(clinit); 1290 HInstruction* ldclass = clinit->InputAt(0); 1291 if (ldclass->IsLoadClass() && !ldclass->HasUses()) { 1292 ldclass->GetBlock()->RemoveInstruction(ldclass); 1293 } 1294 } 1295} 1296 1297static bool IsArrayLengthOf(HInstruction* potential_length, HInstruction* potential_array) { 1298 if (potential_length->IsArrayLength()) { 1299 return potential_length->InputAt(0) == potential_array; 1300 } 1301 1302 if (potential_array->IsNewArray()) { 1303 return potential_array->InputAt(0) == potential_length; 1304 } 1305 1306 return false; 1307} 1308 1309void InstructionSimplifierVisitor::SimplifySystemArrayCopy(HInvoke* instruction) { 1310 HInstruction* source = instruction->InputAt(0); 1311 HInstruction* destination = instruction->InputAt(2); 1312 HInstruction* count = instruction->InputAt(4); 1313 SystemArrayCopyOptimizations optimizations(instruction); 1314 if (CanEnsureNotNullAt(source, instruction)) { 1315 optimizations.SetSourceIsNotNull(); 1316 } 1317 if (CanEnsureNotNullAt(destination, instruction)) { 1318 optimizations.SetDestinationIsNotNull(); 1319 } 1320 if (destination == source) { 1321 optimizations.SetDestinationIsSource(); 1322 } 1323 1324 if (IsArrayLengthOf(count, source)) { 1325 optimizations.SetCountIsSourceLength(); 1326 } 1327 1328 if (IsArrayLengthOf(count, destination)) { 1329 optimizations.SetCountIsDestinationLength(); 1330 } 1331 1332 { 1333 ScopedObjectAccess soa(Thread::Current()); 1334 ReferenceTypeInfo destination_rti = destination->GetReferenceTypeInfo(); 1335 if (destination_rti.IsValid()) { 1336 if (destination_rti.IsObjectArray()) { 1337 if (destination_rti.IsExact()) { 1338 optimizations.SetDoesNotNeedTypeCheck(); 1339 } 1340 optimizations.SetDestinationIsTypedObjectArray(); 1341 } 1342 if (destination_rti.IsPrimitiveArrayClass()) { 1343 optimizations.SetDestinationIsPrimitiveArray(); 1344 } else if (destination_rti.IsNonPrimitiveArrayClass()) { 1345 optimizations.SetDestinationIsNonPrimitiveArray(); 1346 } 1347 } 1348 ReferenceTypeInfo source_rti = source->GetReferenceTypeInfo(); 1349 if (source_rti.IsValid()) { 1350 if (destination_rti.IsValid() && destination_rti.CanArrayHoldValuesOf(source_rti)) { 1351 optimizations.SetDoesNotNeedTypeCheck(); 1352 } 1353 if (source_rti.IsPrimitiveArrayClass()) { 1354 optimizations.SetSourceIsPrimitiveArray(); 1355 } else if (source_rti.IsNonPrimitiveArrayClass()) { 1356 optimizations.SetSourceIsNonPrimitiveArray(); 1357 } 1358 } 1359 } 1360} 1361 1362void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) { 1363 if (instruction->GetIntrinsic() == Intrinsics::kStringEquals) { 1364 SimplifyStringEquals(instruction); 1365 } else if (instruction->GetIntrinsic() == Intrinsics::kSystemArrayCopy) { 1366 SimplifySystemArrayCopy(instruction); 1367 } else if (instruction->GetIntrinsic() == Intrinsics::kIntegerRotateRight || 1368 instruction->GetIntrinsic() == Intrinsics::kLongRotateRight) { 1369 SimplifyRotate(instruction, false); 1370 } else if (instruction->GetIntrinsic() == Intrinsics::kIntegerRotateLeft || 1371 instruction->GetIntrinsic() == Intrinsics::kLongRotateLeft) { 1372 SimplifyRotate(instruction, true); 1373 } 1374} 1375 1376void InstructionSimplifierVisitor::VisitDeoptimize(HDeoptimize* deoptimize) { 1377 HInstruction* cond = deoptimize->InputAt(0); 1378 if (cond->IsConstant()) { 1379 if (cond->AsIntConstant()->IsZero()) { 1380 // Never deopt: instruction can be removed. 1381 deoptimize->GetBlock()->RemoveInstruction(deoptimize); 1382 } else { 1383 // Always deopt. 1384 } 1385 } 1386} 1387 1388} // namespace art 1389