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