instruction_simplifier.cc revision 7cb499b1af1575c854860b0d6a103c4a2a59a569
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 "mirror/class-inl.h" 20#include "scoped_thread_state_change.h" 21 22namespace art { 23 24class InstructionSimplifierVisitor : public HGraphVisitor { 25 public: 26 InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats) 27 : HGraphVisitor(graph), 28 stats_(stats) {} 29 30 void Run(); 31 32 private: 33 void RecordSimplification() { 34 simplification_occurred_ = true; 35 simplifications_at_current_position_++; 36 if (stats_) { 37 stats_->RecordStat(kInstructionSimplifications); 38 } 39 } 40 41 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop); 42 void VisitShift(HBinaryOperation* shift); 43 44 void VisitSuspendCheck(HSuspendCheck* check) OVERRIDE; 45 void VisitEqual(HEqual* equal) OVERRIDE; 46 void VisitNotEqual(HNotEqual* equal) OVERRIDE; 47 void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE; 48 void VisitInstanceFieldSet(HInstanceFieldSet* equal) OVERRIDE; 49 void VisitStaticFieldSet(HStaticFieldSet* equal) OVERRIDE; 50 void VisitArraySet(HArraySet* equal) OVERRIDE; 51 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 52 void VisitNullCheck(HNullCheck* instruction) OVERRIDE; 53 void VisitArrayLength(HArrayLength* instruction) OVERRIDE; 54 void VisitCheckCast(HCheckCast* instruction) OVERRIDE; 55 void VisitAdd(HAdd* instruction) OVERRIDE; 56 void VisitAnd(HAnd* instruction) OVERRIDE; 57 void VisitDiv(HDiv* instruction) OVERRIDE; 58 void VisitMul(HMul* instruction) OVERRIDE; 59 void VisitNeg(HNeg* instruction) OVERRIDE; 60 void VisitNot(HNot* instruction) OVERRIDE; 61 void VisitOr(HOr* instruction) OVERRIDE; 62 void VisitShl(HShl* instruction) OVERRIDE; 63 void VisitShr(HShr* instruction) OVERRIDE; 64 void VisitSub(HSub* instruction) OVERRIDE; 65 void VisitUShr(HUShr* instruction) OVERRIDE; 66 void VisitXor(HXor* instruction) OVERRIDE; 67 void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE; 68 bool IsDominatedByInputNullCheck(HInstruction* instr); 69 70 OptimizingCompilerStats* stats_; 71 bool simplification_occurred_ = false; 72 int simplifications_at_current_position_ = 0; 73 // We ensure we do not loop infinitely. The value is a finger in the air guess 74 // that should allow enough simplification. 75 static constexpr int kMaxSamePositionSimplifications = 10; 76}; 77 78void InstructionSimplifier::Run() { 79 InstructionSimplifierVisitor visitor(graph_, stats_); 80 visitor.Run(); 81} 82 83void InstructionSimplifierVisitor::Run() { 84 // Iterate in reverse post order to open up more simplifications to users 85 // of instructions that got simplified. 86 for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) { 87 // The simplification of an instruction to another instruction may yield 88 // possibilities for other simplifications. So although we perform a reverse 89 // post order visit, we sometimes need to revisit an instruction index. 90 simplification_occurred_ = false; 91 VisitBasicBlock(it.Current()); 92 if (simplification_occurred_ && 93 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) { 94 // New simplifications may be applicable to the instruction at the 95 // current index, so don't advance the iterator. 96 continue; 97 } 98 simplifications_at_current_position_ = 0; 99 it.Advance(); 100 } 101} 102 103namespace { 104 105bool AreAllBitsSet(HConstant* constant) { 106 return Int64FromConstant(constant) == -1; 107} 108 109} // namespace 110 111// Returns true if the code was simplified to use only one negation operation 112// after the binary operation instead of one on each of the inputs. 113bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) { 114 DCHECK(binop->IsAdd() || binop->IsSub()); 115 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg()); 116 HNeg* left_neg = binop->GetLeft()->AsNeg(); 117 HNeg* right_neg = binop->GetRight()->AsNeg(); 118 if (!left_neg->HasOnlyOneNonEnvironmentUse() || 119 !right_neg->HasOnlyOneNonEnvironmentUse()) { 120 return false; 121 } 122 // Replace code looking like 123 // NEG tmp1, a 124 // NEG tmp2, b 125 // ADD dst, tmp1, tmp2 126 // with 127 // ADD tmp, a, b 128 // NEG dst, tmp 129 binop->ReplaceInput(left_neg->GetInput(), 0); 130 binop->ReplaceInput(right_neg->GetInput(), 1); 131 left_neg->GetBlock()->RemoveInstruction(left_neg); 132 right_neg->GetBlock()->RemoveInstruction(right_neg); 133 HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop); 134 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext()); 135 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0); 136 RecordSimplification(); 137 return true; 138} 139 140void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 141 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 142 HConstant* input_cst = instruction->GetConstantRight(); 143 HInstruction* input_other = instruction->GetLeastConstantLeft(); 144 145 if (input_cst != nullptr) { 146 if (input_cst->IsZero()) { 147 // Replace code looking like 148 // SHL dst, src, 0 149 // with 150 // src 151 instruction->ReplaceWith(input_other); 152 instruction->GetBlock()->RemoveInstruction(instruction); 153 } else if (instruction->IsShl() && input_cst->IsOne()) { 154 // Replace Shl looking like 155 // SHL dst, src, 1 156 // with 157 // ADD dst, src, src 158 HAdd *add = new(GetGraph()->GetArena()) HAdd(instruction->GetType(), 159 input_other, 160 input_other); 161 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 162 RecordSimplification(); 163 } 164 } 165} 166 167void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 168 HInstruction* obj = null_check->InputAt(0); 169 if (!obj->CanBeNull()) { 170 null_check->ReplaceWith(obj); 171 null_check->GetBlock()->RemoveInstruction(null_check); 172 if (stats_ != nullptr) { 173 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 174 } 175 } 176} 177 178bool InstructionSimplifierVisitor::IsDominatedByInputNullCheck(HInstruction* instr) { 179 HInstruction* input = instr->InputAt(0); 180 for (HUseIterator<HInstruction*> it(input->GetUses()); !it.Done(); it.Advance()) { 181 HInstruction* use = it.Current()->GetUser(); 182 if (use->IsNullCheck() && use->StrictlyDominates(instr)) { 183 return true; 184 } 185 } 186 return false; 187} 188 189// Returns whether doing a type test between the class of `object` against `klass` has 190// a statically known outcome. The result of the test is stored in `outcome`. 191static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) { 192 if (!klass->IsResolved()) { 193 // If the class couldn't be resolve it's not safe to compare against it. It's 194 // default type would be Top which might be wider that the actual class type 195 // and thus producing wrong results. 196 return false; 197 } 198 199 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); 200 ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI(); 201 ScopedObjectAccess soa(Thread::Current()); 202 if (class_rti.IsSupertypeOf(obj_rti)) { 203 *outcome = true; 204 return true; 205 } else if (obj_rti.IsExact()) { 206 // The test failed at compile time so will also fail at runtime. 207 *outcome = false; 208 return true; 209 } else if (!class_rti.IsInterface() 210 && !obj_rti.IsInterface() 211 && !obj_rti.IsSupertypeOf(class_rti)) { 212 // Different type hierarchy. The test will fail. 213 *outcome = false; 214 return true; 215 } 216 return false; 217} 218 219void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 220 HInstruction* object = check_cast->InputAt(0); 221 if (!object->CanBeNull() || IsDominatedByInputNullCheck(check_cast)) { 222 check_cast->ClearMustDoNullCheck(); 223 } 224 225 if (object->IsNullConstant()) { 226 check_cast->GetBlock()->RemoveInstruction(check_cast); 227 if (stats_ != nullptr) { 228 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 229 } 230 return; 231 } 232 233 bool outcome; 234 if (TypeCheckHasKnownOutcome(check_cast->InputAt(1)->AsLoadClass(), object, &outcome)) { 235 if (outcome) { 236 check_cast->GetBlock()->RemoveInstruction(check_cast); 237 if (stats_ != nullptr) { 238 stats_->RecordStat(MethodCompilationStat::kRemovedCheckedCast); 239 } 240 } else { 241 // Don't do anything for exceptional cases for now. Ideally we should remove 242 // all instructions and blocks this instruction dominates. 243 } 244 } 245} 246 247void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { 248 HInstruction* object = instruction->InputAt(0); 249 bool can_be_null = true; 250 if (!object->CanBeNull() || IsDominatedByInputNullCheck(instruction)) { 251 can_be_null = false; 252 instruction->ClearMustDoNullCheck(); 253 } 254 255 HGraph* graph = GetGraph(); 256 if (object->IsNullConstant()) { 257 instruction->ReplaceWith(graph->GetIntConstant(0)); 258 instruction->GetBlock()->RemoveInstruction(instruction); 259 RecordSimplification(); 260 return; 261 } 262 263 bool outcome; 264 if (TypeCheckHasKnownOutcome(instruction->InputAt(1)->AsLoadClass(), object, &outcome)) { 265 if (outcome && can_be_null) { 266 // Type test will succeed, we just need a null test. 267 HNotEqual* test = new (graph->GetArena()) HNotEqual(graph->GetNullConstant(), object); 268 instruction->GetBlock()->InsertInstructionBefore(test, instruction); 269 instruction->ReplaceWith(test); 270 } else { 271 // We've statically determined the result of the instanceof. 272 instruction->ReplaceWith(graph->GetIntConstant(outcome)); 273 } 274 RecordSimplification(); 275 instruction->GetBlock()->RemoveInstruction(instruction); 276 } 277} 278 279void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) { 280 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 281 && !instruction->GetValue()->CanBeNull()) { 282 instruction->ClearValueCanBeNull(); 283 } 284} 285 286void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) { 287 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot) 288 && !instruction->GetValue()->CanBeNull()) { 289 instruction->ClearValueCanBeNull(); 290 } 291} 292 293void InstructionSimplifierVisitor::VisitSuspendCheck(HSuspendCheck* check) { 294 HBasicBlock* block = check->GetBlock(); 295 // Currently always keep the suspend check at entry. 296 if (block->IsEntryBlock()) return; 297 298 // Currently always keep suspend checks at loop entry. 299 if (block->IsLoopHeader() && block->GetFirstInstruction() == check) { 300 DCHECK(block->GetLoopInformation()->GetSuspendCheck() == check); 301 return; 302 } 303 304 // Remove the suspend check that was added at build time for the baseline 305 // compiler. 306 block->RemoveInstruction(check); 307} 308 309void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 310 HInstruction* input_const = equal->GetConstantRight(); 311 if (input_const != nullptr) { 312 HInstruction* input_value = equal->GetLeastConstantLeft(); 313 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 314 HBasicBlock* block = equal->GetBlock(); 315 if (input_const->AsIntConstant()->IsOne()) { 316 // Replace (bool_value == true) with bool_value 317 equal->ReplaceWith(input_value); 318 block->RemoveInstruction(equal); 319 RecordSimplification(); 320 } else { 321 // Replace (bool_value == false) with !bool_value 322 DCHECK(input_const->AsIntConstant()->IsZero()); 323 block->ReplaceAndRemoveInstructionWith( 324 equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 325 RecordSimplification(); 326 } 327 } 328 } 329} 330 331void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { 332 HInstruction* input_const = not_equal->GetConstantRight(); 333 if (input_const != nullptr) { 334 HInstruction* input_value = not_equal->GetLeastConstantLeft(); 335 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) { 336 HBasicBlock* block = not_equal->GetBlock(); 337 if (input_const->AsIntConstant()->IsOne()) { 338 // Replace (bool_value != true) with !bool_value 339 block->ReplaceAndRemoveInstructionWith( 340 not_equal, new (block->GetGraph()->GetArena()) HBooleanNot(input_value)); 341 RecordSimplification(); 342 } else { 343 // Replace (bool_value != false) with bool_value 344 DCHECK(input_const->AsIntConstant()->IsZero()); 345 not_equal->ReplaceWith(input_value); 346 block->RemoveInstruction(not_equal); 347 RecordSimplification(); 348 } 349 } 350 } 351} 352 353void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { 354 HInstruction* parent = bool_not->InputAt(0); 355 if (parent->IsBooleanNot()) { 356 HInstruction* value = parent->InputAt(0); 357 // Replace (!(!bool_value)) with bool_value 358 bool_not->ReplaceWith(value); 359 bool_not->GetBlock()->RemoveInstruction(bool_not); 360 // It is possible that `parent` is dead at this point but we leave 361 // its removal to DCE for simplicity. 362 RecordSimplification(); 363 } 364} 365 366void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 367 HInstruction* input = instruction->InputAt(0); 368 // If the array is a NewArray with constant size, replace the array length 369 // with the constant instruction. This helps the bounds check elimination phase. 370 if (input->IsNewArray()) { 371 input = input->InputAt(0); 372 if (input->IsIntConstant()) { 373 instruction->ReplaceWith(input); 374 } 375 } 376} 377 378void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 379 HInstruction* value = instruction->GetValue(); 380 if (value->GetType() != Primitive::kPrimNot) return; 381 382 if (value->IsArrayGet()) { 383 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 384 // If the code is just swapping elements in the array, no need for a type check. 385 instruction->ClearNeedsTypeCheck(); 386 } 387 } 388 389 if (!value->CanBeNull()) { 390 instruction->ClearValueCanBeNull(); 391 } 392} 393 394void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 395 if (instruction->GetResultType() == instruction->GetInputType()) { 396 // Remove the instruction if it's converting to the same type. 397 instruction->ReplaceWith(instruction->GetInput()); 398 instruction->GetBlock()->RemoveInstruction(instruction); 399 } 400} 401 402void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 403 HConstant* input_cst = instruction->GetConstantRight(); 404 HInstruction* input_other = instruction->GetLeastConstantLeft(); 405 if ((input_cst != nullptr) && input_cst->IsZero()) { 406 // Replace code looking like 407 // ADD dst, src, 0 408 // with 409 // src 410 instruction->ReplaceWith(input_other); 411 instruction->GetBlock()->RemoveInstruction(instruction); 412 return; 413 } 414 415 HInstruction* left = instruction->GetLeft(); 416 HInstruction* right = instruction->GetRight(); 417 bool left_is_neg = left->IsNeg(); 418 bool right_is_neg = right->IsNeg(); 419 420 if (left_is_neg && right_is_neg) { 421 if (TryMoveNegOnInputsAfterBinop(instruction)) { 422 return; 423 } 424 } 425 426 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg(); 427 if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) { 428 // Replace code looking like 429 // NEG tmp, b 430 // ADD dst, a, tmp 431 // with 432 // SUB dst, a, b 433 // We do not perform the optimization if the input negation has environment 434 // uses or multiple non-environment uses as it could lead to worse code. In 435 // particular, we do not want the live range of `b` to be extended if we are 436 // not sure the initial 'NEG' instruction can be removed. 437 HInstruction* other = left_is_neg ? right : left; 438 HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput()); 439 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub); 440 RecordSimplification(); 441 neg->GetBlock()->RemoveInstruction(neg); 442 } 443} 444 445void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 446 HConstant* input_cst = instruction->GetConstantRight(); 447 HInstruction* input_other = instruction->GetLeastConstantLeft(); 448 449 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 450 // Replace code looking like 451 // AND dst, src, 0xFFF...FF 452 // with 453 // src 454 instruction->ReplaceWith(input_other); 455 instruction->GetBlock()->RemoveInstruction(instruction); 456 return; 457 } 458 459 // We assume that GVN has run before, so we only perform a pointer comparison. 460 // If for some reason the values are equal but the pointers are different, we 461 // are still correct and only miss an optimization opportunity. 462 if (instruction->GetLeft() == instruction->GetRight()) { 463 // Replace code looking like 464 // AND dst, src, src 465 // with 466 // src 467 instruction->ReplaceWith(instruction->GetLeft()); 468 instruction->GetBlock()->RemoveInstruction(instruction); 469 } 470} 471 472void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 473 HConstant* input_cst = instruction->GetConstantRight(); 474 HInstruction* input_other = instruction->GetLeastConstantLeft(); 475 Primitive::Type type = instruction->GetType(); 476 477 if ((input_cst != nullptr) && input_cst->IsOne()) { 478 // Replace code looking like 479 // DIV dst, src, 1 480 // with 481 // src 482 instruction->ReplaceWith(input_other); 483 instruction->GetBlock()->RemoveInstruction(instruction); 484 return; 485 } 486 487 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 488 // Replace code looking like 489 // DIV dst, src, -1 490 // with 491 // NEG dst, src 492 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 493 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other)); 494 RecordSimplification(); 495 return; 496 } 497 498 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) { 499 // Try replacing code looking like 500 // DIV dst, src, constant 501 // with 502 // MUL dst, src, 1 / constant 503 HConstant* reciprocal = nullptr; 504 if (type == Primitive::Primitive::kPrimDouble) { 505 double value = input_cst->AsDoubleConstant()->GetValue(); 506 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 507 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 508 } 509 } else { 510 DCHECK_EQ(type, Primitive::kPrimFloat); 511 float value = input_cst->AsFloatConstant()->GetValue(); 512 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 513 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 514 } 515 } 516 517 if (reciprocal != nullptr) { 518 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 519 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal)); 520 RecordSimplification(); 521 return; 522 } 523 } 524} 525 526void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 527 HConstant* input_cst = instruction->GetConstantRight(); 528 HInstruction* input_other = instruction->GetLeastConstantLeft(); 529 Primitive::Type type = instruction->GetType(); 530 HBasicBlock* block = instruction->GetBlock(); 531 ArenaAllocator* allocator = GetGraph()->GetArena(); 532 533 if (input_cst == nullptr) { 534 return; 535 } 536 537 if (input_cst->IsOne()) { 538 // Replace code looking like 539 // MUL dst, src, 1 540 // with 541 // src 542 instruction->ReplaceWith(input_other); 543 instruction->GetBlock()->RemoveInstruction(instruction); 544 return; 545 } 546 547 if (input_cst->IsMinusOne() && 548 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) { 549 // Replace code looking like 550 // MUL dst, src, -1 551 // with 552 // NEG dst, src 553 HNeg* neg = new (allocator) HNeg(type, input_other); 554 block->ReplaceAndRemoveInstructionWith(instruction, neg); 555 RecordSimplification(); 556 return; 557 } 558 559 if (Primitive::IsFloatingPointType(type) && 560 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 561 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 562 // Replace code looking like 563 // FP_MUL dst, src, 2.0 564 // with 565 // FP_ADD dst, src, src 566 // The 'int' and 'long' cases are handled below. 567 block->ReplaceAndRemoveInstructionWith(instruction, 568 new (allocator) HAdd(type, input_other, input_other)); 569 RecordSimplification(); 570 return; 571 } 572 573 if (Primitive::IsIntOrLongType(type)) { 574 int64_t factor = Int64FromConstant(input_cst); 575 // Even though constant propagation also takes care of the zero case, other 576 // optimizations can lead to having a zero multiplication. 577 if (factor == 0) { 578 // Replace code looking like 579 // MUL dst, src, 0 580 // with 581 // 0 582 instruction->ReplaceWith(input_cst); 583 instruction->GetBlock()->RemoveInstruction(instruction); 584 } else if (IsPowerOfTwo(factor)) { 585 // Replace code looking like 586 // MUL dst, src, pow_of_2 587 // with 588 // SHL dst, src, log2(pow_of_2) 589 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 590 HShl* shl = new(allocator) HShl(type, input_other, shift); 591 block->ReplaceAndRemoveInstructionWith(instruction, shl); 592 RecordSimplification(); 593 } 594 } 595} 596 597void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 598 HInstruction* input = instruction->GetInput(); 599 if (input->IsNeg()) { 600 // Replace code looking like 601 // NEG tmp, src 602 // NEG dst, tmp 603 // with 604 // src 605 HNeg* previous_neg = input->AsNeg(); 606 instruction->ReplaceWith(previous_neg->GetInput()); 607 instruction->GetBlock()->RemoveInstruction(instruction); 608 // We perform the optimization even if the input negation has environment 609 // uses since it allows removing the current instruction. But we only delete 610 // the input negation only if it is does not have any uses left. 611 if (!previous_neg->HasUses()) { 612 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 613 } 614 RecordSimplification(); 615 return; 616 } 617 618 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 619 !Primitive::IsFloatingPointType(input->GetType())) { 620 // Replace code looking like 621 // SUB tmp, a, b 622 // NEG dst, tmp 623 // with 624 // SUB dst, b, a 625 // We do not perform the optimization if the input subtraction has 626 // environment uses or multiple non-environment uses as it could lead to 627 // worse code. In particular, we do not want the live ranges of `a` and `b` 628 // to be extended if we are not sure the initial 'SUB' instruction can be 629 // removed. 630 // We do not perform optimization for fp because we could lose the sign of zero. 631 HSub* sub = input->AsSub(); 632 HSub* new_sub = 633 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft()); 634 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 635 if (!sub->HasUses()) { 636 sub->GetBlock()->RemoveInstruction(sub); 637 } 638 RecordSimplification(); 639 } 640} 641 642void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 643 HInstruction* input = instruction->GetInput(); 644 if (input->IsNot()) { 645 // Replace code looking like 646 // NOT tmp, src 647 // NOT dst, tmp 648 // with 649 // src 650 // We perform the optimization even if the input negation has environment 651 // uses since it allows removing the current instruction. But we only delete 652 // the input negation only if it is does not have any uses left. 653 HNot* previous_not = input->AsNot(); 654 instruction->ReplaceWith(previous_not->GetInput()); 655 instruction->GetBlock()->RemoveInstruction(instruction); 656 if (!previous_not->HasUses()) { 657 previous_not->GetBlock()->RemoveInstruction(previous_not); 658 } 659 RecordSimplification(); 660 } 661} 662 663void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 664 HConstant* input_cst = instruction->GetConstantRight(); 665 HInstruction* input_other = instruction->GetLeastConstantLeft(); 666 667 if ((input_cst != nullptr) && input_cst->IsZero()) { 668 // Replace code looking like 669 // OR dst, src, 0 670 // with 671 // src 672 instruction->ReplaceWith(input_other); 673 instruction->GetBlock()->RemoveInstruction(instruction); 674 return; 675 } 676 677 // We assume that GVN has run before, so we only perform a pointer comparison. 678 // If for some reason the values are equal but the pointers are different, we 679 // are still correct and only miss an optimization opportunity. 680 if (instruction->GetLeft() == instruction->GetRight()) { 681 // Replace code looking like 682 // OR dst, src, src 683 // with 684 // src 685 instruction->ReplaceWith(instruction->GetLeft()); 686 instruction->GetBlock()->RemoveInstruction(instruction); 687 } 688} 689 690void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 691 VisitShift(instruction); 692} 693 694void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 695 VisitShift(instruction); 696} 697 698void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 699 HConstant* input_cst = instruction->GetConstantRight(); 700 HInstruction* input_other = instruction->GetLeastConstantLeft(); 701 702 if ((input_cst != nullptr) && input_cst->IsZero()) { 703 // Replace code looking like 704 // SUB dst, src, 0 705 // with 706 // src 707 instruction->ReplaceWith(input_other); 708 instruction->GetBlock()->RemoveInstruction(instruction); 709 return; 710 } 711 712 Primitive::Type type = instruction->GetType(); 713 if (!Primitive::IsIntegralType(type)) { 714 return; 715 } 716 717 HBasicBlock* block = instruction->GetBlock(); 718 ArenaAllocator* allocator = GetGraph()->GetArena(); 719 720 HInstruction* left = instruction->GetLeft(); 721 HInstruction* right = instruction->GetRight(); 722 if (left->IsConstant()) { 723 if (Int64FromConstant(left->AsConstant()) == 0) { 724 // Replace code looking like 725 // SUB dst, 0, src 726 // with 727 // NEG dst, src 728 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 729 // `x` is `0.0`, the former expression yields `0.0`, while the later 730 // yields `-0.0`. 731 HNeg* neg = new (allocator) HNeg(type, right); 732 block->ReplaceAndRemoveInstructionWith(instruction, neg); 733 RecordSimplification(); 734 return; 735 } 736 } 737 738 if (left->IsNeg() && right->IsNeg()) { 739 if (TryMoveNegOnInputsAfterBinop(instruction)) { 740 return; 741 } 742 } 743 744 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 745 // Replace code looking like 746 // NEG tmp, b 747 // SUB dst, a, tmp 748 // with 749 // ADD dst, a, b 750 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput()); 751 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 752 RecordSimplification(); 753 right->GetBlock()->RemoveInstruction(right); 754 return; 755 } 756 757 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 758 // Replace code looking like 759 // NEG tmp, a 760 // SUB dst, tmp, b 761 // with 762 // ADD tmp, a, b 763 // NEG dst, tmp 764 // The second version is not intrinsically better, but enables more 765 // transformations. 766 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right); 767 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 768 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add); 769 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 770 instruction->ReplaceWith(neg); 771 instruction->GetBlock()->RemoveInstruction(instruction); 772 RecordSimplification(); 773 left->GetBlock()->RemoveInstruction(left); 774 } 775} 776 777void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 778 VisitShift(instruction); 779} 780 781void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 782 HConstant* input_cst = instruction->GetConstantRight(); 783 HInstruction* input_other = instruction->GetLeastConstantLeft(); 784 785 if ((input_cst != nullptr) && input_cst->IsZero()) { 786 // Replace code looking like 787 // XOR dst, src, 0 788 // with 789 // src 790 instruction->ReplaceWith(input_other); 791 instruction->GetBlock()->RemoveInstruction(instruction); 792 return; 793 } 794 795 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 796 // Replace code looking like 797 // XOR dst, src, 0xFFF...FF 798 // with 799 // NOT dst, src 800 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other); 801 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 802 RecordSimplification(); 803 return; 804 } 805} 806 807} // namespace art 808