instruction_simplifier.cc revision e9f37600e98ba21308ad4f70d9d68cf6c057bdbe
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 TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop); 43 void VisitShift(HBinaryOperation* shift); 44 45 void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE; 46 void VisitEqual(HEqual* equal) OVERRIDE; 47 void VisitNotEqual(HNotEqual* equal) OVERRIDE; 48 void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE; 49 void VisitInstanceFieldSet(HInstanceFieldSet* equal) OVERRIDE; 50 void VisitStaticFieldSet(HStaticFieldSet* equal) OVERRIDE; 51 void VisitArraySet(HArraySet* equal) OVERRIDE; 52 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 53 void VisitNullCheck(HNullCheck* instruction) OVERRIDE; 54 void VisitArrayLength(HArrayLength* instruction) OVERRIDE; 55 void VisitCheckCast(HCheckCast* instruction) OVERRIDE; 56 void VisitAdd(HAdd* instruction) OVERRIDE; 57 void VisitAnd(HAnd* instruction) OVERRIDE; 58 void VisitCondition(HCondition* instruction) OVERRIDE; 59 void VisitGreaterThan(HGreaterThan* condition) OVERRIDE; 60 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) OVERRIDE; 61 void VisitLessThan(HLessThan* condition) OVERRIDE; 62 void VisitLessThanOrEqual(HLessThanOrEqual* condition) OVERRIDE; 63 void VisitDiv(HDiv* instruction) OVERRIDE; 64 void VisitMul(HMul* instruction) OVERRIDE; 65 void VisitNeg(HNeg* instruction) OVERRIDE; 66 void VisitNot(HNot* instruction) OVERRIDE; 67 void VisitOr(HOr* instruction) OVERRIDE; 68 void VisitShl(HShl* instruction) OVERRIDE; 69 void VisitShr(HShr* instruction) OVERRIDE; 70 void VisitSub(HSub* instruction) OVERRIDE; 71 void VisitUShr(HUShr* instruction) OVERRIDE; 72 void VisitXor(HXor* instruction) OVERRIDE; 73 void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; 74 void VisitFakeString(HFakeString* fake_string) OVERRIDE; 75 void VisitInvoke(HInvoke* invoke) OVERRIDE; 76 77 bool CanEnsureNotNullAt(HInstruction* instr, HInstruction* at) const; 78 79 OptimizingCompilerStats* stats_; 80 bool simplification_occurred_ = false; 81 int simplifications_at_current_position_ = 0; 82 // We ensure we do not loop infinitely. The value is a finger in the air guess 83 // that should allow enough simplification. 84 static constexpr int kMaxSamePositionSimplifications = 10; 85}; 86 87void InstructionSimplifier::Run() { 88 InstructionSimplifierVisitor visitor(graph_, stats_); 89 visitor.Run(); 90} 91 92void InstructionSimplifierVisitor::Run() { 93 // Iterate in reverse post order to open up more simplifications to users 94 // of instructions that got simplified. 95 for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) { 96 // The simplification of an instruction to another instruction may yield 97 // possibilities for other simplifications. So although we perform a reverse 98 // post order visit, we sometimes need to revisit an instruction index. 99 simplification_occurred_ = false; 100 VisitBasicBlock(it.Current()); 101 if (simplification_occurred_ && 102 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) { 103 // New simplifications may be applicable to the instruction at the 104 // current index, so don't advance the iterator. 105 continue; 106 } 107 simplifications_at_current_position_ = 0; 108 it.Advance(); 109 } 110} 111 112namespace { 113 114bool AreAllBitsSet(HConstant* constant) { 115 return Int64FromConstant(constant) == -1; 116} 117 118} // namespace 119 120// Returns true if the code was simplified to use only one negation operation 121// after the binary operation instead of one on each of the inputs. 122bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) { 123 DCHECK(binop->IsAdd() || binop->IsSub()); 124 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg()); 125 HNeg* left_neg = binop->GetLeft()->AsNeg(); 126 HNeg* right_neg = binop->GetRight()->AsNeg(); 127 if (!left_neg->HasOnlyOneNonEnvironmentUse() || 128 !right_neg->HasOnlyOneNonEnvironmentUse()) { 129 return false; 130 } 131 // Replace code looking like 132 // NEG tmp1, a 133 // NEG tmp2, b 134 // ADD dst, tmp1, tmp2 135 // with 136 // ADD tmp, a, b 137 // NEG dst, tmp 138 // Note that we cannot optimize `(-a) + (-b)` to `-(a + b)` for floating-point. 139 // When `a` is `-0.0` and `b` is `0.0`, the former expression yields `0.0`, 140 // while the later yields `-0.0`. 141 if (!Primitive::IsIntegralType(binop->GetType())) { 142 return false; 143 } 144 binop->ReplaceInput(left_neg->GetInput(), 0); 145 binop->ReplaceInput(right_neg->GetInput(), 1); 146 left_neg->GetBlock()->RemoveInstruction(left_neg); 147 right_neg->GetBlock()->RemoveInstruction(right_neg); 148 HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop); 149 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext()); 150 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0); 151 RecordSimplification(); 152 return true; 153} 154 155void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 156 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 157 HConstant* input_cst = instruction->GetConstantRight(); 158 HInstruction* input_other = instruction->GetLeastConstantLeft(); 159 160 if (input_cst != nullptr) { 161 if (input_cst->IsZero()) { 162 // Replace code looking like 163 // SHL dst, src, 0 164 // with 165 // src 166 instruction->ReplaceWith(input_other); 167 instruction->GetBlock()->RemoveInstruction(instruction); 168 } else if (instruction->IsShl() && input_cst->IsOne()) { 169 // Replace Shl looking like 170 // SHL dst, src, 1 171 // with 172 // ADD dst, src, src 173 HAdd *add = new(GetGraph()->GetArena()) HAdd(instruction->GetType(), 174 input_other, 175 input_other); 176 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 177 RecordSimplification(); 178 } 179 } 180} 181 182void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 183 HInstruction* obj = null_check->InputAt(0); 184 if (!obj->CanBeNull()) { 185 null_check->ReplaceWith(obj); 186 null_check->GetBlock()->RemoveInstruction(null_check); 187 if (stats_ != nullptr) { 188 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 189 } 190 } 191} 192 193bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInstruction* at) const { 194 if (!input->CanBeNull()) { 195 return true; 196 } 197 198 for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) { 199 HInstruction* use = it.Current()->GetUser(); 200 if (use->IsNullCheck() && use->StrictlyDominates(at)) { 201 return true; 202 } 203 } 204 205 return false; 206} 207 208// Returns whether doing a type test between the class of `object` against `klass` has 209// a statically known outcome. The result of the test is stored in `outcome`. 210static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) { 211 DCHECK(!object->IsNullConstant()) << "Null constants should be special cased"; 212 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); 213 ScopedObjectAccess soa(Thread::Current()); 214 if (!obj_rti.IsValid()) { 215 // We run the simplifier before the reference type propagation so type info might not be 216 // available. 217 return false; 218 } 219 220 ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI(); 221 if (!class_rti.IsValid()) { 222 // Happens when the loaded class is unresolved. 223 return false; 224 } 225 DCHECK(class_rti.IsExact()); 226 if (class_rti.IsSupertypeOf(obj_rti)) { 227 *outcome = true; 228 return true; 229 } else if (obj_rti.IsExact()) { 230 // The test failed at compile time so will also fail at runtime. 231 *outcome = false; 232 return true; 233 } else if (!class_rti.IsInterface() 234 && !obj_rti.IsInterface() 235 && !obj_rti.IsSupertypeOf(class_rti)) { 236 // Different type hierarchy. The test will fail. 237 *outcome = false; 238 return true; 239 } 240 return false; 241} 242 243void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 244 HInstruction* object = check_cast->InputAt(0); 245 HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass(); 246 if (load_class->NeedsAccessCheck()) { 247 // If we need to perform an access check we cannot remove the instruction. 248 return; 249 } 250 251 if (CanEnsureNotNullAt(object, check_cast)) { 252 check_cast->ClearMustDoNullCheck(); 253 } 254 255 if (object->IsNullConstant()) { 256 check_cast->GetBlock()->RemoveInstruction(check_cast); 257 if (stats_ != nullptr) { 258 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 259 } 260 return; 261 } 262 263 bool outcome; 264 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) { 265 if (outcome) { 266 check_cast->GetBlock()->RemoveInstruction(check_cast); 267 if (stats_ != nullptr) { 268 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 269 } 270 if (!load_class->HasUses()) { 271 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 272 // However, here we know that it cannot because the checkcast was successfull, hence 273 // the class was already loaded. 274 load_class->GetBlock()->RemoveInstruction(load_class); 275 } 276 } else { 277 // Don't do anything for exceptional cases for now. Ideally we should remove 278 // all instructions and blocks this instruction dominates. 279 } 280 } 281} 282 283void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { 284 HInstruction* object = instruction->InputAt(0); 285 HLoadClass* load_class = instruction->InputAt(1)->AsLoadClass(); 286 if (load_class->NeedsAccessCheck()) { 287 // If we need to perform an access check we cannot remove the instruction. 288 return; 289 } 290 291 bool can_be_null = true; 292 if (CanEnsureNotNullAt(object, instruction)) { 293 can_be_null = false; 294 instruction->ClearMustDoNullCheck(); 295 } 296 297 HGraph* graph = GetGraph(); 298 if (object->IsNullConstant()) { 299 instruction->ReplaceWith(graph->GetIntConstant(0)); 300 instruction->GetBlock()->RemoveInstruction(instruction); 301 RecordSimplification(); 302 return; 303 } 304 305 bool outcome; 306 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) { 307 if (outcome && can_be_null) { 308 // Type test will succeed, we just need a null test. 309 HNotEqual* test = new (graph->GetArena()) HNotEqual(graph->GetNullConstant(), object); 310 instruction->GetBlock()->InsertInstructionBefore(test, instruction); 311 instruction->ReplaceWith(test); 312 } else { 313 // We've statically determined the result of the instanceof. 314 instruction->ReplaceWith(graph->GetIntConstant(outcome)); 315 } 316 RecordSimplification(); 317 instruction->GetBlock()->RemoveInstruction(instruction); 318 if (outcome && !load_class->HasUses()) { 319 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 320 // However, here we know that it cannot because the instanceof check was successfull, hence 321 // the class was already loaded. 322 load_class->GetBlock()->RemoveInstruction(load_class); 323 } 324 } 325} 326 327void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) { 328 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 329 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 330 instruction->ClearValueCanBeNull(); 331 } 332} 333 334void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) { 335 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 336 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 337 instruction->ClearValueCanBeNull(); 338 } 339} 340 341void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { 342 HBasicBlock* block = check->GetBlock(); 343 // Currently always keep the suspend check at entry. 344 if (block->IsEntryBlock()) return; 345 346 // Currently always keep suspend checks at loop entry. 347 if (block->IsLoopHeader() && block->GetFirstInstruction() == check) { 348 DCHECK(block->GetLoopInformation()->GetSuspendCheck() == check); 349 return; 350 } 351 352 // Remove the suspend check that was added at build time for the baseline 353 // compiler. 354 block->RemoveInstruction(check); 355} 356 357void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 358 HInstruction* input_const = equal->GetConstantRight(); 359 if (input_const != nullptr) { 360 HInstruction* input_value = equal->GetLeastConstantLeft(); 361 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 362 HBasicBlock* block = equal->GetBlock(); 363 // We are comparing the boolean to a constant which is of type int and can 364 // be any constant. 365 if (input_const->AsIntConstant()->IsOne()) { 366 // Replace (bool_value == true) with bool_value 367 equal->ReplaceWith(input_value); 368 block->RemoveInstruction(equal); 369 RecordSimplification(); 370 } else if (input_const->AsIntConstant()->IsZero()) { 371 // Replace (bool_value == false) with !bool_value 372 block->ReplaceAndRemoveInstructionWith( 373 equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 374 RecordSimplification(); 375 } else { 376 // Replace (bool_value == integer_not_zero_nor_one_constant) with false 377 equal->ReplaceWith(GetGraph()->GetIntConstant(0)); 378 block->RemoveInstruction(equal); 379 RecordSimplification(); 380 } 381 } else { 382 VisitCondition(equal); 383 } 384 } else { 385 VisitCondition(equal); 386 } 387} 388 389void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { 390 HInstruction* input_const = not_equal->GetConstantRight(); 391 if (input_const != nullptr) { 392 HInstruction* input_value = not_equal->GetLeastConstantLeft(); 393 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 394 HBasicBlock* block = not_equal->GetBlock(); 395 // We are comparing the boolean to a constant which is of type int and can 396 // be any constant. 397 if (input_const->AsIntConstant()->IsOne()) { 398 // Replace (bool_value != true) with !bool_value 399 block->ReplaceAndRemoveInstructionWith( 400 not_equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 401 RecordSimplification(); 402 } else if (input_const->AsIntConstant()->IsZero()) { 403 // Replace (bool_value != false) with bool_value 404 not_equal->ReplaceWith(input_value); 405 block->RemoveInstruction(not_equal); 406 RecordSimplification(); 407 } else { 408 // Replace (bool_value != integer_not_zero_nor_one_constant) with true 409 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1)); 410 block->RemoveInstruction(not_equal); 411 RecordSimplification(); 412 } 413 } else { 414 VisitCondition(not_equal); 415 } 416 } else { 417 VisitCondition(not_equal); 418 } 419} 420 421void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { 422 HInstruction* parent = bool_not->InputAt(0); 423 if (parent->IsBooleanNot()) { 424 HInstruction* value = parent->InputAt(0); 425 // Replace (!(!bool_value)) with bool_value 426 bool_not->ReplaceWith(value); 427 bool_not->GetBlock()->RemoveInstruction(bool_not); 428 // It is possible that `parent` is dead at this point but we leave 429 // its removal to DCE for simplicity. 430 RecordSimplification(); 431 } 432} 433 434void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 435 HInstruction* input = instruction->InputAt(0); 436 // If the array is a NewArray with constant size, replace the array length 437 // with the constant instruction. This helps the bounds check elimination phase. 438 if (input->IsNewArray()) { 439 input = input->InputAt(0); 440 if (input->IsIntConstant()) { 441 instruction->ReplaceWith(input); 442 } 443 } 444} 445 446void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 447 HInstruction* value = instruction->GetValue(); 448 if (value->GetType() != Primitive::kPrimNot) return; 449 450 if (CanEnsureNotNullAt(value, instruction)) { 451 instruction->ClearValueCanBeNull(); 452 } 453 454 if (value->IsArrayGet()) { 455 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 456 // If the code is just swapping elements in the array, no need for a type check. 457 instruction->ClearNeedsTypeCheck(); 458 return; 459 } 460 } 461 462 if (value->IsNullConstant()) { 463 instruction->ClearNeedsTypeCheck(); 464 return; 465 } 466 467 ScopedObjectAccess soa(Thread::Current()); 468 ReferenceTypeInfo array_rti = instruction->GetArray()->GetReferenceTypeInfo(); 469 ReferenceTypeInfo value_rti = value->GetReferenceTypeInfo(); 470 if (!array_rti.IsValid()) { 471 return; 472 } 473 474 if (value_rti.IsValid() && array_rti.CanArrayHold(value_rti)) { 475 instruction->ClearNeedsTypeCheck(); 476 return; 477 } 478 479 if (array_rti.IsObjectArray()) { 480 if (array_rti.IsExact()) { 481 instruction->ClearNeedsTypeCheck(); 482 return; 483 } 484 instruction->SetStaticTypeOfArrayIsObjectArray(); 485 } 486} 487 488void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 489 if (instruction->GetResultType() == instruction->GetInputType()) { 490 // Remove the instruction if it's converting to the same type. 491 instruction->ReplaceWith(instruction->GetInput()); 492 instruction->GetBlock()->RemoveInstruction(instruction); 493 } 494} 495 496void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 497 HConstant* input_cst = instruction->GetConstantRight(); 498 HInstruction* input_other = instruction->GetLeastConstantLeft(); 499 if ((input_cst != nullptr) && input_cst->IsZero()) { 500 // Replace code looking like 501 // ADD dst, src, 0 502 // with 503 // src 504 // Note that we cannot optimize `x + 0.0` to `x` for floating-point. When 505 // `x` is `-0.0`, the former expression yields `0.0`, while the later 506 // yields `-0.0`. 507 if (Primitive::IsIntegralType(instruction->GetType())) { 508 instruction->ReplaceWith(input_other); 509 instruction->GetBlock()->RemoveInstruction(instruction); 510 return; 511 } 512 } 513 514 HInstruction* left = instruction->GetLeft(); 515 HInstruction* right = instruction->GetRight(); 516 bool left_is_neg = left->IsNeg(); 517 bool right_is_neg = right->IsNeg(); 518 519 if (left_is_neg && right_is_neg) { 520 if (TryMoveNegOnInputsAfterBinop(instruction)) { 521 return; 522 } 523 } 524 525 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg(); 526 if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) { 527 // Replace code looking like 528 // NEG tmp, b 529 // ADD dst, a, tmp 530 // with 531 // SUB dst, a, b 532 // We do not perform the optimization if the input negation has environment 533 // uses or multiple non-environment uses as it could lead to worse code. In 534 // particular, we do not want the live range of `b` to be extended if we are 535 // not sure the initial 'NEG' instruction can be removed. 536 HInstruction* other = left_is_neg ? right : left; 537 HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput()); 538 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub); 539 RecordSimplification(); 540 neg->GetBlock()->RemoveInstruction(neg); 541 } 542} 543 544void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 545 HConstant* input_cst = instruction->GetConstantRight(); 546 HInstruction* input_other = instruction->GetLeastConstantLeft(); 547 548 if (input_cst != nullptr) { 549 int64_t value = Int64FromConstant(input_cst); 550 if (value == -1) { 551 // Replace code looking like 552 // AND dst, src, 0xFFF...FF 553 // with 554 // src 555 instruction->ReplaceWith(input_other); 556 instruction->GetBlock()->RemoveInstruction(instruction); 557 RecordSimplification(); 558 return; 559 } 560 // Eliminate And from UShr+And if the And-mask contains all the bits that 561 // can be non-zero after UShr. Transform Shr+And to UShr if the And-mask 562 // precisely clears the shifted-in sign bits. 563 if ((input_other->IsUShr() || input_other->IsShr()) && input_other->InputAt(1)->IsConstant()) { 564 size_t reg_bits = (instruction->GetResultType() == Primitive::kPrimLong) ? 64 : 32; 565 size_t shift = Int64FromConstant(input_other->InputAt(1)->AsConstant()) & (reg_bits - 1); 566 size_t num_tail_bits_set = CTZ(value + 1); 567 if ((num_tail_bits_set >= reg_bits - shift) && input_other->IsUShr()) { 568 // This AND clears only bits known to be clear, for example "(x >>> 24) & 0xff". 569 instruction->ReplaceWith(input_other); 570 instruction->GetBlock()->RemoveInstruction(instruction); 571 RecordSimplification(); 572 return; 573 } else if ((num_tail_bits_set == reg_bits - shift) && IsPowerOfTwo(value + 1) && 574 input_other->HasOnlyOneNonEnvironmentUse()) { 575 DCHECK(input_other->IsShr()); // For UShr, we would have taken the branch above. 576 // Replace SHR+AND with USHR, for example "(x >> 24) & 0xff" -> "x >>> 24". 577 HUShr* ushr = new (GetGraph()->GetArena()) HUShr(instruction->GetType(), 578 input_other->InputAt(0), 579 input_other->InputAt(1), 580 input_other->GetDexPc()); 581 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, ushr); 582 input_other->GetBlock()->RemoveInstruction(input_other); 583 RecordSimplification(); 584 return; 585 } 586 } 587 } 588 589 // We assume that GVN has run before, so we only perform a pointer comparison. 590 // If for some reason the values are equal but the pointers are different, we 591 // are still correct and only miss an optimization opportunity. 592 if (instruction->GetLeft() == instruction->GetRight()) { 593 // Replace code looking like 594 // AND dst, src, src 595 // with 596 // src 597 instruction->ReplaceWith(instruction->GetLeft()); 598 instruction->GetBlock()->RemoveInstruction(instruction); 599 } 600} 601 602void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) { 603 VisitCondition(condition); 604} 605 606void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) { 607 VisitCondition(condition); 608} 609 610void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) { 611 VisitCondition(condition); 612} 613 614void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) { 615 VisitCondition(condition); 616} 617 618// TODO: unsigned comparisons too? 619 620void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) { 621 // Try to fold an HCompare into this HCondition. 622 623 // This simplification is currently supported on x86, x86_64, ARM and ARM64. 624 // TODO: Implement it for MIPS64. 625 InstructionSet instruction_set = GetGraph()->GetInstructionSet(); 626 if (instruction_set == kMips64) { 627 return; 628 } 629 630 HInstruction* left = condition->GetLeft(); 631 HInstruction* right = condition->GetRight(); 632 // We can only replace an HCondition which compares a Compare to 0. 633 // Both 'dx' and 'jack' generate a compare to 0 when compiling a 634 // condition with a long, float or double comparison as input. 635 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) { 636 // Conversion is not possible. 637 return; 638 } 639 640 // Is the Compare only used for this purpose? 641 if (!left->GetUses().HasOnlyOneUse()) { 642 // Someone else also wants the result of the compare. 643 return; 644 } 645 646 if (!left->GetEnvUses().IsEmpty()) { 647 // There is a reference to the compare result in an environment. Do we really need it? 648 if (GetGraph()->IsDebuggable()) { 649 return; 650 } 651 652 // We have to ensure that there are no deopt points in the sequence. 653 if (left->HasAnyEnvironmentUseBefore(condition)) { 654 return; 655 } 656 } 657 658 // Clean up any environment uses from the HCompare, if any. 659 left->RemoveEnvironmentUsers(); 660 661 // We have decided to fold the HCompare into the HCondition. Transfer the information. 662 condition->SetBias(left->AsCompare()->GetBias()); 663 664 // Replace the operands of the HCondition. 665 condition->ReplaceInput(left->InputAt(0), 0); 666 condition->ReplaceInput(left->InputAt(1), 1); 667 668 // Remove the HCompare. 669 left->GetBlock()->RemoveInstruction(left); 670 671 RecordSimplification(); 672} 673 674void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 675 HConstant* input_cst = instruction->GetConstantRight(); 676 HInstruction* input_other = instruction->GetLeastConstantLeft(); 677 Primitive::Type type = instruction->GetType(); 678 679 if ((input_cst != nullptr) && input_cst->IsOne()) { 680 // Replace code looking like 681 // DIV dst, src, 1 682 // with 683 // src 684 instruction->ReplaceWith(input_other); 685 instruction->GetBlock()->RemoveInstruction(instruction); 686 return; 687 } 688 689 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 690 // Replace code looking like 691 // DIV dst, src, -1 692 // with 693 // NEG dst, src 694 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 695 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other)); 696 RecordSimplification(); 697 return; 698 } 699 700 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) { 701 // Try replacing code looking like 702 // DIV dst, src, constant 703 // with 704 // MUL dst, src, 1 / constant 705 HConstant* reciprocal = nullptr; 706 if (type == Primitive::Primitive::kPrimDouble) { 707 double value = input_cst->AsDoubleConstant()->GetValue(); 708 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 709 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 710 } 711 } else { 712 DCHECK_EQ(type, Primitive::kPrimFloat); 713 float value = input_cst->AsFloatConstant()->GetValue(); 714 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 715 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 716 } 717 } 718 719 if (reciprocal != nullptr) { 720 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 721 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal)); 722 RecordSimplification(); 723 return; 724 } 725 } 726} 727 728void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 729 HConstant* input_cst = instruction->GetConstantRight(); 730 HInstruction* input_other = instruction->GetLeastConstantLeft(); 731 Primitive::Type type = instruction->GetType(); 732 HBasicBlock* block = instruction->GetBlock(); 733 ArenaAllocator* allocator = GetGraph()->GetArena(); 734 735 if (input_cst == nullptr) { 736 return; 737 } 738 739 if (input_cst->IsOne()) { 740 // Replace code looking like 741 // MUL dst, src, 1 742 // with 743 // src 744 instruction->ReplaceWith(input_other); 745 instruction->GetBlock()->RemoveInstruction(instruction); 746 return; 747 } 748 749 if (input_cst->IsMinusOne() && 750 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 751 // Replace code looking like 752 // MUL dst, src, -1 753 // with 754 // NEG dst, src 755 HNeg* neg = new (allocator) HNeg(type, input_other); 756 block->ReplaceAndRemoveInstructionWith(instruction, neg); 757 RecordSimplification(); 758 return; 759 } 760 761 if (Primitive::IsFloatingPointType(type) && 762 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 763 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 764 // Replace code looking like 765 // FP_MUL dst, src, 2.0 766 // with 767 // FP_ADD dst, src, src 768 // The 'int' and 'long' cases are handled below. 769 block->ReplaceAndRemoveInstructionWith(instruction, 770 new (allocator) HAdd(type, input_other, input_other)); 771 RecordSimplification(); 772 return; 773 } 774 775 if (Primitive::IsIntOrLongType(type)) { 776 int64_t factor = Int64FromConstant(input_cst); 777 // Even though constant propagation also takes care of the zero case, other 778 // optimizations can lead to having a zero multiplication. 779 if (factor == 0) { 780 // Replace code looking like 781 // MUL dst, src, 0 782 // with 783 // 0 784 instruction->ReplaceWith(input_cst); 785 instruction->GetBlock()->RemoveInstruction(instruction); 786 } else if (IsPowerOfTwo(factor)) { 787 // Replace code looking like 788 // MUL dst, src, pow_of_2 789 // with 790 // SHL dst, src, log2(pow_of_2) 791 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 792 HShl* shl = new(allocator) HShl(type, input_other, shift); 793 block->ReplaceAndRemoveInstructionWith(instruction, shl); 794 RecordSimplification(); 795 } 796 } 797} 798 799void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 800 HInstruction* input = instruction->GetInput(); 801 if (input->IsNeg()) { 802 // Replace code looking like 803 // NEG tmp, src 804 // NEG dst, tmp 805 // with 806 // src 807 HNeg* previous_neg = input->AsNeg(); 808 instruction->ReplaceWith(previous_neg->GetInput()); 809 instruction->GetBlock()->RemoveInstruction(instruction); 810 // We perform the optimization even if the input negation has environment 811 // uses since it allows removing the current instruction. But we only delete 812 // the input negation only if it is does not have any uses left. 813 if (!previous_neg->HasUses()) { 814 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 815 } 816 RecordSimplification(); 817 return; 818 } 819 820 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 821 !Primitive::IsFloatingPointType(input->GetType())) { 822 // Replace code looking like 823 // SUB tmp, a, b 824 // NEG dst, tmp 825 // with 826 // SUB dst, b, a 827 // We do not perform the optimization if the input subtraction has 828 // environment uses or multiple non-environment uses as it could lead to 829 // worse code. In particular, we do not want the live ranges of `a` and `b` 830 // to be extended if we are not sure the initial 'SUB' instruction can be 831 // removed. 832 // We do not perform optimization for fp because we could lose the sign of zero. 833 HSub* sub = input->AsSub(); 834 HSub* new_sub = 835 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft()); 836 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 837 if (!sub->HasUses()) { 838 sub->GetBlock()->RemoveInstruction(sub); 839 } 840 RecordSimplification(); 841 } 842} 843 844void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 845 HInstruction* input = instruction->GetInput(); 846 if (input->IsNot()) { 847 // Replace code looking like 848 // NOT tmp, src 849 // NOT dst, tmp 850 // with 851 // src 852 // We perform the optimization even if the input negation has environment 853 // uses since it allows removing the current instruction. But we only delete 854 // the input negation only if it is does not have any uses left. 855 HNot* previous_not = input->AsNot(); 856 instruction->ReplaceWith(previous_not->GetInput()); 857 instruction->GetBlock()->RemoveInstruction(instruction); 858 if (!previous_not->HasUses()) { 859 previous_not->GetBlock()->RemoveInstruction(previous_not); 860 } 861 RecordSimplification(); 862 } 863} 864 865void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 866 HConstant* input_cst = instruction->GetConstantRight(); 867 HInstruction* input_other = instruction->GetLeastConstantLeft(); 868 869 if ((input_cst != nullptr) && input_cst->IsZero()) { 870 // Replace code looking like 871 // OR dst, src, 0 872 // with 873 // src 874 instruction->ReplaceWith(input_other); 875 instruction->GetBlock()->RemoveInstruction(instruction); 876 return; 877 } 878 879 // We assume that GVN has run before, so we only perform a pointer comparison. 880 // If for some reason the values are equal but the pointers are different, we 881 // are still correct and only miss an optimization opportunity. 882 if (instruction->GetLeft() == instruction->GetRight()) { 883 // Replace code looking like 884 // OR dst, src, src 885 // with 886 // src 887 instruction->ReplaceWith(instruction->GetLeft()); 888 instruction->GetBlock()->RemoveInstruction(instruction); 889 } 890} 891 892void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 893 VisitShift(instruction); 894} 895 896void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 897 VisitShift(instruction); 898} 899 900void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 901 HConstant* input_cst = instruction->GetConstantRight(); 902 HInstruction* input_other = instruction->GetLeastConstantLeft(); 903 904 Primitive::Type type = instruction->GetType(); 905 if (Primitive::IsFloatingPointType(type)) { 906 return; 907 } 908 909 if ((input_cst != nullptr) && input_cst->IsZero()) { 910 // Replace code looking like 911 // SUB dst, src, 0 912 // with 913 // src 914 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When 915 // `x` is `-0.0`, the former expression yields `0.0`, while the later 916 // yields `-0.0`. 917 instruction->ReplaceWith(input_other); 918 instruction->GetBlock()->RemoveInstruction(instruction); 919 return; 920 } 921 922 HBasicBlock* block = instruction->GetBlock(); 923 ArenaAllocator* allocator = GetGraph()->GetArena(); 924 925 HInstruction* left = instruction->GetLeft(); 926 HInstruction* right = instruction->GetRight(); 927 if (left->IsConstant()) { 928 if (Int64FromConstant(left->AsConstant()) == 0) { 929 // Replace code looking like 930 // SUB dst, 0, src 931 // with 932 // NEG dst, src 933 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 934 // `x` is `0.0`, the former expression yields `0.0`, while the later 935 // yields `-0.0`. 936 HNeg* neg = new (allocator) HNeg(type, right); 937 block->ReplaceAndRemoveInstructionWith(instruction, neg); 938 RecordSimplification(); 939 return; 940 } 941 } 942 943 if (left->IsNeg() && right->IsNeg()) { 944 if (TryMoveNegOnInputsAfterBinop(instruction)) { 945 return; 946 } 947 } 948 949 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 950 // Replace code looking like 951 // NEG tmp, b 952 // SUB dst, a, tmp 953 // with 954 // ADD dst, a, b 955 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput()); 956 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 957 RecordSimplification(); 958 right->GetBlock()->RemoveInstruction(right); 959 return; 960 } 961 962 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 963 // Replace code looking like 964 // NEG tmp, a 965 // SUB dst, tmp, b 966 // with 967 // ADD tmp, a, b 968 // NEG dst, tmp 969 // The second version is not intrinsically better, but enables more 970 // transformations. 971 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right); 972 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 973 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add); 974 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 975 instruction->ReplaceWith(neg); 976 instruction->GetBlock()->RemoveInstruction(instruction); 977 RecordSimplification(); 978 left->GetBlock()->RemoveInstruction(left); 979 } 980} 981 982void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 983 VisitShift(instruction); 984} 985 986void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 987 HConstant* input_cst = instruction->GetConstantRight(); 988 HInstruction* input_other = instruction->GetLeastConstantLeft(); 989 990 if ((input_cst != nullptr) && input_cst->IsZero()) { 991 // Replace code looking like 992 // XOR dst, src, 0 993 // with 994 // src 995 instruction->ReplaceWith(input_other); 996 instruction->GetBlock()->RemoveInstruction(instruction); 997 return; 998 } 999 1000 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 1001 // Replace code looking like 1002 // XOR dst, src, 0xFFF...FF 1003 // with 1004 // NOT dst, src 1005 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 1006 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 1007 RecordSimplification(); 1008 return; 1009 } 1010} 1011 1012void InstructionSimplifierVisitor::VisitFakeString(HFakeString* instruction) { 1013 HInstruction* actual_string = nullptr; 1014 1015 // Find the string we need to replace this instruction with. The actual string is 1016 // the return value of a StringFactory call. 1017 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1018 HInstruction* use = it.Current()->GetUser(); 1019 if (use->IsInvokeStaticOrDirect() 1020 && use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)) { 1021 use->AsInvokeStaticOrDirect()->RemoveFakeStringArgumentAsLastInput(); 1022 actual_string = use; 1023 break; 1024 } 1025 } 1026 1027 // Check that there is no other instruction that thinks it is the factory for that string. 1028 if (kIsDebugBuild) { 1029 CHECK(actual_string != nullptr); 1030 for (HUseIterator<HInstruction*> it(instruction->GetUses()); !it.Done(); it.Advance()) { 1031 HInstruction* use = it.Current()->GetUser(); 1032 if (use->IsInvokeStaticOrDirect()) { 1033 CHECK(!use->AsInvokeStaticOrDirect()->IsStringFactoryFor(instruction)); 1034 } 1035 } 1036 } 1037 1038 // We need to remove any environment uses of the fake string that are not dominated by 1039 // `actual_string` to null. 1040 for (HUseIterator<HEnvironment*> it(instruction->GetEnvUses()); !it.Done(); it.Advance()) { 1041 HEnvironment* environment = it.Current()->GetUser(); 1042 if (!actual_string->StrictlyDominates(environment->GetHolder())) { 1043 environment->RemoveAsUserOfInput(it.Current()->GetIndex()); 1044 environment->SetRawEnvAt(it.Current()->GetIndex(), nullptr); 1045 } 1046 } 1047 1048 // Only uses dominated by `actual_string` must remain. We can safely replace and remove 1049 // `instruction`. 1050 instruction->ReplaceWith(actual_string); 1051 instruction->GetBlock()->RemoveInstruction(instruction); 1052} 1053 1054void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) { 1055 if (instruction->GetIntrinsic() == Intrinsics::kStringEquals) { 1056 HInstruction* argument = instruction->InputAt(1); 1057 HInstruction* receiver = instruction->InputAt(0); 1058 if (receiver == argument) { 1059 // Because String.equals is an instance call, the receiver is 1060 // a null check if we don't know it's null. The argument however, will 1061 // be the actual object. So we cannot end up in a situation where both 1062 // are equal but could be null. 1063 DCHECK(CanEnsureNotNullAt(argument, instruction)); 1064 instruction->ReplaceWith(GetGraph()->GetIntConstant(1)); 1065 instruction->GetBlock()->RemoveInstruction(instruction); 1066 } else { 1067 StringEqualsOptimizations optimizations(instruction); 1068 if (CanEnsureNotNullAt(argument, instruction)) { 1069 optimizations.SetArgumentNotNull(); 1070 } 1071 ScopedObjectAccess soa(Thread::Current()); 1072 if (argument->GetReferenceTypeInfo().IsStringClass()) { 1073 optimizations.SetArgumentIsString(); 1074 } 1075 } 1076 } 1077} 1078 1079} // namespace art 1080