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