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