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