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 "art_method-inl.h" 20 #include "class_linker-inl.h" 21 #include "class_root.h" 22 #include "data_type-inl.h" 23 #include "escape.h" 24 #include "intrinsics.h" 25 #include "mirror/class-inl.h" 26 #include "scoped_thread_state_change-inl.h" 27 #include "sharpening.h" 28 29 namespace art { 30 31 // Whether to run an exhaustive test of individual HInstructions cloning when each instruction 32 // is replaced with its copy if it is clonable. 33 static constexpr bool kTestInstructionClonerExhaustively = false; 34 35 class InstructionSimplifierVisitor : public HGraphDelegateVisitor { 36 public: 37 InstructionSimplifierVisitor(HGraph* graph, 38 CodeGenerator* codegen, 39 OptimizingCompilerStats* stats) 40 : HGraphDelegateVisitor(graph), 41 codegen_(codegen), 42 stats_(stats) {} 43 44 bool Run(); 45 46 private: 47 void RecordSimplification() { 48 simplification_occurred_ = true; 49 simplifications_at_current_position_++; 50 MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSimplifications); 51 } 52 53 bool ReplaceRotateWithRor(HBinaryOperation* op, HUShr* ushr, HShl* shl); 54 bool TryReplaceWithRotate(HBinaryOperation* instruction); 55 bool TryReplaceWithRotateConstantPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl); 56 bool TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl); 57 bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl); 58 59 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop); 60 // `op` should be either HOr or HAnd. 61 // De Morgan's laws: 62 // ~a & ~b = ~(a | b) and ~a | ~b = ~(a & b) 63 bool TryDeMorganNegationFactoring(HBinaryOperation* op); 64 bool TryHandleAssociativeAndCommutativeOperation(HBinaryOperation* instruction); 65 bool TrySubtractionChainSimplification(HBinaryOperation* instruction); 66 bool TryCombineVecMultiplyAccumulate(HVecMul* mul); 67 68 void VisitShift(HBinaryOperation* shift); 69 void VisitEqual(HEqual* equal) override; 70 void VisitNotEqual(HNotEqual* equal) override; 71 void VisitBooleanNot(HBooleanNot* bool_not) override; 72 void VisitInstanceFieldSet(HInstanceFieldSet* equal) override; 73 void VisitStaticFieldSet(HStaticFieldSet* equal) override; 74 void VisitArraySet(HArraySet* equal) override; 75 void VisitTypeConversion(HTypeConversion* instruction) override; 76 void VisitNullCheck(HNullCheck* instruction) override; 77 void VisitArrayLength(HArrayLength* instruction) override; 78 void VisitCheckCast(HCheckCast* instruction) override; 79 void VisitAbs(HAbs* instruction) override; 80 void VisitAdd(HAdd* instruction) override; 81 void VisitAnd(HAnd* instruction) override; 82 void VisitCondition(HCondition* instruction) override; 83 void VisitGreaterThan(HGreaterThan* condition) override; 84 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) override; 85 void VisitLessThan(HLessThan* condition) override; 86 void VisitLessThanOrEqual(HLessThanOrEqual* condition) override; 87 void VisitBelow(HBelow* condition) override; 88 void VisitBelowOrEqual(HBelowOrEqual* condition) override; 89 void VisitAbove(HAbove* condition) override; 90 void VisitAboveOrEqual(HAboveOrEqual* condition) override; 91 void VisitDiv(HDiv* instruction) override; 92 void VisitMul(HMul* instruction) override; 93 void VisitNeg(HNeg* instruction) override; 94 void VisitNot(HNot* instruction) override; 95 void VisitOr(HOr* instruction) override; 96 void VisitShl(HShl* instruction) override; 97 void VisitShr(HShr* instruction) override; 98 void VisitSub(HSub* instruction) override; 99 void VisitUShr(HUShr* instruction) override; 100 void VisitXor(HXor* instruction) override; 101 void VisitSelect(HSelect* select) override; 102 void VisitIf(HIf* instruction) override; 103 void VisitInstanceOf(HInstanceOf* instruction) override; 104 void VisitInvoke(HInvoke* invoke) override; 105 void VisitDeoptimize(HDeoptimize* deoptimize) override; 106 void VisitVecMul(HVecMul* instruction) override; 107 108 bool CanEnsureNotNullAt(HInstruction* instr, HInstruction* at) const; 109 110 void SimplifyRotate(HInvoke* invoke, bool is_left, DataType::Type type); 111 void SimplifySystemArrayCopy(HInvoke* invoke); 112 void SimplifyStringEquals(HInvoke* invoke); 113 void SimplifyCompare(HInvoke* invoke, bool is_signum, DataType::Type type); 114 void SimplifyIsNaN(HInvoke* invoke); 115 void SimplifyFP2Int(HInvoke* invoke); 116 void SimplifyStringCharAt(HInvoke* invoke); 117 void SimplifyStringIsEmptyOrLength(HInvoke* invoke); 118 void SimplifyStringIndexOf(HInvoke* invoke); 119 void SimplifyNPEOnArgN(HInvoke* invoke, size_t); 120 void SimplifyReturnThis(HInvoke* invoke); 121 void SimplifyAllocationIntrinsic(HInvoke* invoke); 122 void SimplifyMemBarrier(HInvoke* invoke, MemBarrierKind barrier_kind); 123 void SimplifyMin(HInvoke* invoke, DataType::Type type); 124 void SimplifyMax(HInvoke* invoke, DataType::Type type); 125 void SimplifyAbs(HInvoke* invoke, DataType::Type type); 126 127 CodeGenerator* codegen_; 128 OptimizingCompilerStats* stats_; 129 bool simplification_occurred_ = false; 130 int simplifications_at_current_position_ = 0; 131 // We ensure we do not loop infinitely. The value should not be too high, since that 132 // would allow looping around the same basic block too many times. The value should 133 // not be too low either, however, since we want to allow revisiting a basic block 134 // with many statements and simplifications at least once. 135 static constexpr int kMaxSamePositionSimplifications = 50; 136 }; 137 138 bool InstructionSimplifier::Run() { 139 if (kTestInstructionClonerExhaustively) { 140 CloneAndReplaceInstructionVisitor visitor(graph_); 141 visitor.VisitReversePostOrder(); 142 } 143 144 InstructionSimplifierVisitor visitor(graph_, codegen_, stats_); 145 return visitor.Run(); 146 } 147 148 bool InstructionSimplifierVisitor::Run() { 149 bool didSimplify = false; 150 // Iterate in reverse post order to open up more simplifications to users 151 // of instructions that got simplified. 152 for (HBasicBlock* block : GetGraph()->GetReversePostOrder()) { 153 // The simplification of an instruction to another instruction may yield 154 // possibilities for other simplifications. So although we perform a reverse 155 // post order visit, we sometimes need to revisit an instruction index. 156 do { 157 simplification_occurred_ = false; 158 VisitBasicBlock(block); 159 if (simplification_occurred_) { 160 didSimplify = true; 161 } 162 } while (simplification_occurred_ && 163 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)); 164 simplifications_at_current_position_ = 0; 165 } 166 return didSimplify; 167 } 168 169 namespace { 170 171 bool AreAllBitsSet(HConstant* constant) { 172 return Int64FromConstant(constant) == -1; 173 } 174 175 } // namespace 176 177 // Returns true if the code was simplified to use only one negation operation 178 // after the binary operation instead of one on each of the inputs. 179 bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) { 180 DCHECK(binop->IsAdd() || binop->IsSub()); 181 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg()); 182 HNeg* left_neg = binop->GetLeft()->AsNeg(); 183 HNeg* right_neg = binop->GetRight()->AsNeg(); 184 if (!left_neg->HasOnlyOneNonEnvironmentUse() || 185 !right_neg->HasOnlyOneNonEnvironmentUse()) { 186 return false; 187 } 188 // Replace code looking like 189 // NEG tmp1, a 190 // NEG tmp2, b 191 // ADD dst, tmp1, tmp2 192 // with 193 // ADD tmp, a, b 194 // NEG dst, tmp 195 // Note that we cannot optimize `(-a) + (-b)` to `-(a + b)` for floating-point. 196 // When `a` is `-0.0` and `b` is `0.0`, the former expression yields `0.0`, 197 // while the later yields `-0.0`. 198 if (!DataType::IsIntegralType(binop->GetType())) { 199 return false; 200 } 201 binop->ReplaceInput(left_neg->GetInput(), 0); 202 binop->ReplaceInput(right_neg->GetInput(), 1); 203 left_neg->GetBlock()->RemoveInstruction(left_neg); 204 right_neg->GetBlock()->RemoveInstruction(right_neg); 205 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(binop->GetType(), binop); 206 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext()); 207 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0); 208 RecordSimplification(); 209 return true; 210 } 211 212 bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation* op) { 213 DCHECK(op->IsAnd() || op->IsOr()) << op->DebugName(); 214 DataType::Type type = op->GetType(); 215 HInstruction* left = op->GetLeft(); 216 HInstruction* right = op->GetRight(); 217 218 // We can apply De Morgan's laws if both inputs are Not's and are only used 219 // by `op`. 220 if (((left->IsNot() && right->IsNot()) || 221 (left->IsBooleanNot() && right->IsBooleanNot())) && 222 left->HasOnlyOneNonEnvironmentUse() && 223 right->HasOnlyOneNonEnvironmentUse()) { 224 // Replace code looking like 225 // NOT nota, a 226 // NOT notb, b 227 // AND dst, nota, notb (respectively OR) 228 // with 229 // OR or, a, b (respectively AND) 230 // NOT dest, or 231 HInstruction* src_left = left->InputAt(0); 232 HInstruction* src_right = right->InputAt(0); 233 uint32_t dex_pc = op->GetDexPc(); 234 235 // Remove the negations on the inputs. 236 left->ReplaceWith(src_left); 237 right->ReplaceWith(src_right); 238 left->GetBlock()->RemoveInstruction(left); 239 right->GetBlock()->RemoveInstruction(right); 240 241 // Replace the `HAnd` or `HOr`. 242 HBinaryOperation* hbin; 243 if (op->IsAnd()) { 244 hbin = new (GetGraph()->GetAllocator()) HOr(type, src_left, src_right, dex_pc); 245 } else { 246 hbin = new (GetGraph()->GetAllocator()) HAnd(type, src_left, src_right, dex_pc); 247 } 248 HInstruction* hnot; 249 if (left->IsBooleanNot()) { 250 hnot = new (GetGraph()->GetAllocator()) HBooleanNot(hbin, dex_pc); 251 } else { 252 hnot = new (GetGraph()->GetAllocator()) HNot(type, hbin, dex_pc); 253 } 254 255 op->GetBlock()->InsertInstructionBefore(hbin, op); 256 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot); 257 258 RecordSimplification(); 259 return true; 260 } 261 262 return false; 263 } 264 265 bool InstructionSimplifierVisitor::TryCombineVecMultiplyAccumulate(HVecMul* mul) { 266 DataType::Type type = mul->GetPackedType(); 267 InstructionSet isa = codegen_->GetInstructionSet(); 268 switch (isa) { 269 case InstructionSet::kArm64: 270 if (!(type == DataType::Type::kUint8 || 271 type == DataType::Type::kInt8 || 272 type == DataType::Type::kUint16 || 273 type == DataType::Type::kInt16 || 274 type == DataType::Type::kInt32)) { 275 return false; 276 } 277 break; 278 case InstructionSet::kMips: 279 case InstructionSet::kMips64: 280 if (!(type == DataType::Type::kUint8 || 281 type == DataType::Type::kInt8 || 282 type == DataType::Type::kUint16 || 283 type == DataType::Type::kInt16 || 284 type == DataType::Type::kInt32 || 285 type == DataType::Type::kInt64)) { 286 return false; 287 } 288 break; 289 default: 290 return false; 291 } 292 293 ArenaAllocator* allocator = mul->GetBlock()->GetGraph()->GetAllocator(); 294 295 if (mul->HasOnlyOneNonEnvironmentUse()) { 296 HInstruction* use = mul->GetUses().front().GetUser(); 297 if (use->IsVecAdd() || use->IsVecSub()) { 298 // Replace code looking like 299 // VECMUL tmp, x, y 300 // VECADD/SUB dst, acc, tmp 301 // with 302 // VECMULACC dst, acc, x, y 303 // Note that we do not want to (unconditionally) perform the merge when the 304 // multiplication has multiple uses and it can be merged in all of them. 305 // Multiple uses could happen on the same control-flow path, and we would 306 // then increase the amount of work. In the future we could try to evaluate 307 // whether all uses are on different control-flow paths (using dominance and 308 // reverse-dominance information) and only perform the merge when they are. 309 HInstruction* accumulator = nullptr; 310 HVecBinaryOperation* binop = use->AsVecBinaryOperation(); 311 HInstruction* binop_left = binop->GetLeft(); 312 HInstruction* binop_right = binop->GetRight(); 313 // This is always true since the `HVecMul` has only one use (which is checked above). 314 DCHECK_NE(binop_left, binop_right); 315 if (binop_right == mul) { 316 accumulator = binop_left; 317 } else if (use->IsVecAdd()) { 318 DCHECK_EQ(binop_left, mul); 319 accumulator = binop_right; 320 } 321 322 HInstruction::InstructionKind kind = 323 use->IsVecAdd() ? HInstruction::kAdd : HInstruction::kSub; 324 if (accumulator != nullptr) { 325 HVecMultiplyAccumulate* mulacc = 326 new (allocator) HVecMultiplyAccumulate(allocator, 327 kind, 328 accumulator, 329 mul->GetLeft(), 330 mul->GetRight(), 331 binop->GetPackedType(), 332 binop->GetVectorLength(), 333 binop->GetDexPc()); 334 335 binop->GetBlock()->ReplaceAndRemoveInstructionWith(binop, mulacc); 336 DCHECK(!mul->HasUses()); 337 mul->GetBlock()->RemoveInstruction(mul); 338 return true; 339 } 340 } 341 } 342 343 return false; 344 } 345 346 void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) { 347 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 348 HInstruction* shift_amount = instruction->GetRight(); 349 HInstruction* value = instruction->GetLeft(); 350 351 int64_t implicit_mask = (value->GetType() == DataType::Type::kInt64) 352 ? kMaxLongShiftDistance 353 : kMaxIntShiftDistance; 354 355 if (shift_amount->IsConstant()) { 356 int64_t cst = Int64FromConstant(shift_amount->AsConstant()); 357 int64_t masked_cst = cst & implicit_mask; 358 if (masked_cst == 0) { 359 // Replace code looking like 360 // SHL dst, value, 0 361 // with 362 // value 363 instruction->ReplaceWith(value); 364 instruction->GetBlock()->RemoveInstruction(instruction); 365 RecordSimplification(); 366 return; 367 } else if (masked_cst != cst) { 368 // Replace code looking like 369 // SHL dst, value, cst 370 // where cst exceeds maximum distance with the equivalent 371 // SHL dst, value, cst & implicit_mask 372 // (as defined by shift semantics). This ensures other 373 // optimizations do not need to special case for such situations. 374 DCHECK_EQ(shift_amount->GetType(), DataType::Type::kInt32); 375 instruction->ReplaceInput(GetGraph()->GetIntConstant(masked_cst), /* index= */ 1); 376 RecordSimplification(); 377 return; 378 } 379 } 380 381 // Shift operations implicitly mask the shift amount according to the type width. Get rid of 382 // unnecessary And/Or/Xor/Add/Sub/TypeConversion operations on the shift amount that do not 383 // affect the relevant bits. 384 // Replace code looking like 385 // AND adjusted_shift, shift, <superset of implicit mask> 386 // [OR/XOR/ADD/SUB adjusted_shift, shift, <value not overlapping with implicit mask>] 387 // [<conversion-from-integral-non-64-bit-type> adjusted_shift, shift] 388 // SHL dst, value, adjusted_shift 389 // with 390 // SHL dst, value, shift 391 if (shift_amount->IsAnd() || 392 shift_amount->IsOr() || 393 shift_amount->IsXor() || 394 shift_amount->IsAdd() || 395 shift_amount->IsSub()) { 396 int64_t required_result = shift_amount->IsAnd() ? implicit_mask : 0; 397 HBinaryOperation* bin_op = shift_amount->AsBinaryOperation(); 398 HConstant* mask = bin_op->GetConstantRight(); 399 if (mask != nullptr && (Int64FromConstant(mask) & implicit_mask) == required_result) { 400 instruction->ReplaceInput(bin_op->GetLeastConstantLeft(), 1); 401 RecordSimplification(); 402 return; 403 } 404 } else if (shift_amount->IsTypeConversion()) { 405 DCHECK_NE(shift_amount->GetType(), DataType::Type::kBool); // We never convert to bool. 406 DataType::Type source_type = shift_amount->InputAt(0)->GetType(); 407 // Non-integral and 64-bit source types require an explicit type conversion. 408 if (DataType::IsIntegralType(source_type) && !DataType::Is64BitType(source_type)) { 409 instruction->ReplaceInput(shift_amount->AsTypeConversion()->GetInput(), 1); 410 RecordSimplification(); 411 return; 412 } 413 } 414 } 415 416 static bool IsSubRegBitsMinusOther(HSub* sub, size_t reg_bits, HInstruction* other) { 417 return (sub->GetRight() == other && 418 sub->GetLeft()->IsConstant() && 419 (Int64FromConstant(sub->GetLeft()->AsConstant()) & (reg_bits - 1)) == 0); 420 } 421 422 bool InstructionSimplifierVisitor::ReplaceRotateWithRor(HBinaryOperation* op, 423 HUShr* ushr, 424 HShl* shl) { 425 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()) << op->DebugName(); 426 HRor* ror = 427 new (GetGraph()->GetAllocator()) HRor(ushr->GetType(), ushr->GetLeft(), ushr->GetRight()); 428 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, ror); 429 if (!ushr->HasUses()) { 430 ushr->GetBlock()->RemoveInstruction(ushr); 431 } 432 if (!ushr->GetRight()->HasUses()) { 433 ushr->GetRight()->GetBlock()->RemoveInstruction(ushr->GetRight()); 434 } 435 if (!shl->HasUses()) { 436 shl->GetBlock()->RemoveInstruction(shl); 437 } 438 if (!shl->GetRight()->HasUses()) { 439 shl->GetRight()->GetBlock()->RemoveInstruction(shl->GetRight()); 440 } 441 RecordSimplification(); 442 return true; 443 } 444 445 // Try to replace a binary operation flanked by one UShr and one Shl with a bitfield rotation. 446 bool InstructionSimplifierVisitor::TryReplaceWithRotate(HBinaryOperation* op) { 447 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()); 448 HInstruction* left = op->GetLeft(); 449 HInstruction* right = op->GetRight(); 450 // If we have an UShr and a Shl (in either order). 451 if ((left->IsUShr() && right->IsShl()) || (left->IsShl() && right->IsUShr())) { 452 HUShr* ushr = left->IsUShr() ? left->AsUShr() : right->AsUShr(); 453 HShl* shl = left->IsShl() ? left->AsShl() : right->AsShl(); 454 DCHECK(DataType::IsIntOrLongType(ushr->GetType())); 455 if (ushr->GetType() == shl->GetType() && 456 ushr->GetLeft() == shl->GetLeft()) { 457 if (ushr->GetRight()->IsConstant() && shl->GetRight()->IsConstant()) { 458 // Shift distances are both constant, try replacing with Ror if they 459 // add up to the register size. 460 return TryReplaceWithRotateConstantPattern(op, ushr, shl); 461 } else if (ushr->GetRight()->IsSub() || shl->GetRight()->IsSub()) { 462 // Shift distances are potentially of the form x and (reg_size - x). 463 return TryReplaceWithRotateRegisterSubPattern(op, ushr, shl); 464 } else if (ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg()) { 465 // Shift distances are potentially of the form d and -d. 466 return TryReplaceWithRotateRegisterNegPattern(op, ushr, shl); 467 } 468 } 469 } 470 return false; 471 } 472 473 // Try replacing code looking like (x >>> #rdist OP x << #ldist): 474 // UShr dst, x, #rdist 475 // Shl tmp, x, #ldist 476 // OP dst, dst, tmp 477 // or like (x >>> #rdist OP x << #-ldist): 478 // UShr dst, x, #rdist 479 // Shl tmp, x, #-ldist 480 // OP dst, dst, tmp 481 // with 482 // Ror dst, x, #rdist 483 bool InstructionSimplifierVisitor::TryReplaceWithRotateConstantPattern(HBinaryOperation* op, 484 HUShr* ushr, 485 HShl* shl) { 486 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()); 487 size_t reg_bits = DataType::Size(ushr->GetType()) * kBitsPerByte; 488 size_t rdist = Int64FromConstant(ushr->GetRight()->AsConstant()); 489 size_t ldist = Int64FromConstant(shl->GetRight()->AsConstant()); 490 if (((ldist + rdist) & (reg_bits - 1)) == 0) { 491 ReplaceRotateWithRor(op, ushr, shl); 492 return true; 493 } 494 return false; 495 } 496 497 // Replace code looking like (x >>> -d OP x << d): 498 // Neg neg, d 499 // UShr dst, x, neg 500 // Shl tmp, x, d 501 // OP dst, dst, tmp 502 // with 503 // Neg neg, d 504 // Ror dst, x, neg 505 // *** OR *** 506 // Replace code looking like (x >>> d OP x << -d): 507 // UShr dst, x, d 508 // Neg neg, d 509 // Shl tmp, x, neg 510 // OP dst, dst, tmp 511 // with 512 // Ror dst, x, d 513 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op, 514 HUShr* ushr, 515 HShl* shl) { 516 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()); 517 DCHECK(ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg()); 518 bool neg_is_left = shl->GetRight()->IsNeg(); 519 HNeg* neg = neg_is_left ? shl->GetRight()->AsNeg() : ushr->GetRight()->AsNeg(); 520 // And the shift distance being negated is the distance being shifted the other way. 521 if (neg->InputAt(0) == (neg_is_left ? ushr->GetRight() : shl->GetRight())) { 522 ReplaceRotateWithRor(op, ushr, shl); 523 } 524 return false; 525 } 526 527 // Try replacing code looking like (x >>> d OP x << (#bits - d)): 528 // UShr dst, x, d 529 // Sub ld, #bits, d 530 // Shl tmp, x, ld 531 // OP dst, dst, tmp 532 // with 533 // Ror dst, x, d 534 // *** OR *** 535 // Replace code looking like (x >>> (#bits - d) OP x << d): 536 // Sub rd, #bits, d 537 // UShr dst, x, rd 538 // Shl tmp, x, d 539 // OP dst, dst, tmp 540 // with 541 // Neg neg, d 542 // Ror dst, x, neg 543 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, 544 HUShr* ushr, 545 HShl* shl) { 546 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()); 547 DCHECK(ushr->GetRight()->IsSub() || shl->GetRight()->IsSub()); 548 size_t reg_bits = DataType::Size(ushr->GetType()) * kBitsPerByte; 549 HInstruction* shl_shift = shl->GetRight(); 550 HInstruction* ushr_shift = ushr->GetRight(); 551 if ((shl_shift->IsSub() && IsSubRegBitsMinusOther(shl_shift->AsSub(), reg_bits, ushr_shift)) || 552 (ushr_shift->IsSub() && IsSubRegBitsMinusOther(ushr_shift->AsSub(), reg_bits, shl_shift))) { 553 return ReplaceRotateWithRor(op, ushr, shl); 554 } 555 return false; 556 } 557 558 void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) { 559 HInstruction* obj = null_check->InputAt(0); 560 if (!obj->CanBeNull()) { 561 null_check->ReplaceWith(obj); 562 null_check->GetBlock()->RemoveInstruction(null_check); 563 if (stats_ != nullptr) { 564 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck); 565 } 566 } 567 } 568 569 bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInstruction* at) const { 570 if (!input->CanBeNull()) { 571 return true; 572 } 573 574 for (const HUseListNode<HInstruction*>& use : input->GetUses()) { 575 HInstruction* user = use.GetUser(); 576 if (user->IsNullCheck() && user->StrictlyDominates(at)) { 577 return true; 578 } 579 } 580 581 return false; 582 } 583 584 // Returns whether doing a type test between the class of `object` against `klass` has 585 // a statically known outcome. The result of the test is stored in `outcome`. 586 static bool TypeCheckHasKnownOutcome(ReferenceTypeInfo class_rti, 587 HInstruction* object, 588 /*out*/bool* outcome) { 589 DCHECK(!object->IsNullConstant()) << "Null constants should be special cased"; 590 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo(); 591 ScopedObjectAccess soa(Thread::Current()); 592 if (!obj_rti.IsValid()) { 593 // We run the simplifier before the reference type propagation so type info might not be 594 // available. 595 return false; 596 } 597 598 if (!class_rti.IsValid()) { 599 // Happens when the loaded class is unresolved. 600 return false; 601 } 602 DCHECK(class_rti.IsExact()); 603 if (class_rti.IsSupertypeOf(obj_rti)) { 604 *outcome = true; 605 return true; 606 } else if (obj_rti.IsExact()) { 607 // The test failed at compile time so will also fail at runtime. 608 *outcome = false; 609 return true; 610 } else if (!class_rti.IsInterface() 611 && !obj_rti.IsInterface() 612 && !obj_rti.IsSupertypeOf(class_rti)) { 613 // Different type hierarchy. The test will fail. 614 *outcome = false; 615 return true; 616 } 617 return false; 618 } 619 620 void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) { 621 HInstruction* object = check_cast->InputAt(0); 622 if (check_cast->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck && 623 check_cast->GetTargetClass()->NeedsAccessCheck()) { 624 // If we need to perform an access check we cannot remove the instruction. 625 return; 626 } 627 628 if (CanEnsureNotNullAt(object, check_cast)) { 629 check_cast->ClearMustDoNullCheck(); 630 } 631 632 if (object->IsNullConstant()) { 633 check_cast->GetBlock()->RemoveInstruction(check_cast); 634 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedCheckedCast); 635 return; 636 } 637 638 // Historical note: The `outcome` was initialized to please Valgrind - the compiler can reorder 639 // the return value check with the `outcome` check, b/27651442. 640 bool outcome = false; 641 if (TypeCheckHasKnownOutcome(check_cast->GetTargetClassRTI(), object, &outcome)) { 642 if (outcome) { 643 check_cast->GetBlock()->RemoveInstruction(check_cast); 644 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedCheckedCast); 645 if (check_cast->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck) { 646 HLoadClass* load_class = check_cast->GetTargetClass(); 647 if (!load_class->HasUses()) { 648 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 649 // However, here we know that it cannot because the checkcast was successfull, hence 650 // the class was already loaded. 651 load_class->GetBlock()->RemoveInstruction(load_class); 652 } 653 } 654 } else { 655 // Don't do anything for exceptional cases for now. Ideally we should remove 656 // all instructions and blocks this instruction dominates. 657 } 658 } 659 } 660 661 void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) { 662 HInstruction* object = instruction->InputAt(0); 663 if (instruction->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck && 664 instruction->GetTargetClass()->NeedsAccessCheck()) { 665 // If we need to perform an access check we cannot remove the instruction. 666 return; 667 } 668 669 bool can_be_null = true; 670 if (CanEnsureNotNullAt(object, instruction)) { 671 can_be_null = false; 672 instruction->ClearMustDoNullCheck(); 673 } 674 675 HGraph* graph = GetGraph(); 676 if (object->IsNullConstant()) { 677 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedInstanceOf); 678 instruction->ReplaceWith(graph->GetIntConstant(0)); 679 instruction->GetBlock()->RemoveInstruction(instruction); 680 RecordSimplification(); 681 return; 682 } 683 684 // Historical note: The `outcome` was initialized to please Valgrind - the compiler can reorder 685 // the return value check with the `outcome` check, b/27651442. 686 bool outcome = false; 687 if (TypeCheckHasKnownOutcome(instruction->GetTargetClassRTI(), object, &outcome)) { 688 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedInstanceOf); 689 if (outcome && can_be_null) { 690 // Type test will succeed, we just need a null test. 691 HNotEqual* test = new (graph->GetAllocator()) HNotEqual(graph->GetNullConstant(), object); 692 instruction->GetBlock()->InsertInstructionBefore(test, instruction); 693 instruction->ReplaceWith(test); 694 } else { 695 // We've statically determined the result of the instanceof. 696 instruction->ReplaceWith(graph->GetIntConstant(outcome)); 697 } 698 RecordSimplification(); 699 instruction->GetBlock()->RemoveInstruction(instruction); 700 if (outcome && instruction->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck) { 701 HLoadClass* load_class = instruction->GetTargetClass(); 702 if (!load_class->HasUses()) { 703 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw. 704 // However, here we know that it cannot because the instanceof check was successfull, hence 705 // the class was already loaded. 706 load_class->GetBlock()->RemoveInstruction(load_class); 707 } 708 } 709 } 710 } 711 712 void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) { 713 if ((instruction->GetValue()->GetType() == DataType::Type::kReference) 714 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 715 instruction->ClearValueCanBeNull(); 716 } 717 } 718 719 void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) { 720 if ((instruction->GetValue()->GetType() == DataType::Type::kReference) 721 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) { 722 instruction->ClearValueCanBeNull(); 723 } 724 } 725 726 static HCondition* GetOppositeConditionSwapOps(ArenaAllocator* allocator, HInstruction* cond) { 727 HInstruction *lhs = cond->InputAt(0); 728 HInstruction *rhs = cond->InputAt(1); 729 switch (cond->GetKind()) { 730 case HInstruction::kEqual: 731 return new (allocator) HEqual(rhs, lhs); 732 case HInstruction::kNotEqual: 733 return new (allocator) HNotEqual(rhs, lhs); 734 case HInstruction::kLessThan: 735 return new (allocator) HGreaterThan(rhs, lhs); 736 case HInstruction::kLessThanOrEqual: 737 return new (allocator) HGreaterThanOrEqual(rhs, lhs); 738 case HInstruction::kGreaterThan: 739 return new (allocator) HLessThan(rhs, lhs); 740 case HInstruction::kGreaterThanOrEqual: 741 return new (allocator) HLessThanOrEqual(rhs, lhs); 742 case HInstruction::kBelow: 743 return new (allocator) HAbove(rhs, lhs); 744 case HInstruction::kBelowOrEqual: 745 return new (allocator) HAboveOrEqual(rhs, lhs); 746 case HInstruction::kAbove: 747 return new (allocator) HBelow(rhs, lhs); 748 case HInstruction::kAboveOrEqual: 749 return new (allocator) HBelowOrEqual(rhs, lhs); 750 default: 751 LOG(FATAL) << "Unknown ConditionType " << cond->GetKind(); 752 UNREACHABLE(); 753 } 754 } 755 756 void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) { 757 HInstruction* input_const = equal->GetConstantRight(); 758 if (input_const != nullptr) { 759 HInstruction* input_value = equal->GetLeastConstantLeft(); 760 if ((input_value->GetType() == DataType::Type::kBool) && input_const->IsIntConstant()) { 761 HBasicBlock* block = equal->GetBlock(); 762 // We are comparing the boolean to a constant which is of type int and can 763 // be any constant. 764 if (input_const->AsIntConstant()->IsTrue()) { 765 // Replace (bool_value == true) with bool_value 766 equal->ReplaceWith(input_value); 767 block->RemoveInstruction(equal); 768 RecordSimplification(); 769 } else if (input_const->AsIntConstant()->IsFalse()) { 770 // Replace (bool_value == false) with !bool_value 771 equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, equal)); 772 block->RemoveInstruction(equal); 773 RecordSimplification(); 774 } else { 775 // Replace (bool_value == integer_not_zero_nor_one_constant) with false 776 equal->ReplaceWith(GetGraph()->GetIntConstant(0)); 777 block->RemoveInstruction(equal); 778 RecordSimplification(); 779 } 780 } else { 781 VisitCondition(equal); 782 } 783 } else { 784 VisitCondition(equal); 785 } 786 } 787 788 void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) { 789 HInstruction* input_const = not_equal->GetConstantRight(); 790 if (input_const != nullptr) { 791 HInstruction* input_value = not_equal->GetLeastConstantLeft(); 792 if ((input_value->GetType() == DataType::Type::kBool) && input_const->IsIntConstant()) { 793 HBasicBlock* block = not_equal->GetBlock(); 794 // We are comparing the boolean to a constant which is of type int and can 795 // be any constant. 796 if (input_const->AsIntConstant()->IsTrue()) { 797 // Replace (bool_value != true) with !bool_value 798 not_equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, not_equal)); 799 block->RemoveInstruction(not_equal); 800 RecordSimplification(); 801 } else if (input_const->AsIntConstant()->IsFalse()) { 802 // Replace (bool_value != false) with bool_value 803 not_equal->ReplaceWith(input_value); 804 block->RemoveInstruction(not_equal); 805 RecordSimplification(); 806 } else { 807 // Replace (bool_value != integer_not_zero_nor_one_constant) with true 808 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1)); 809 block->RemoveInstruction(not_equal); 810 RecordSimplification(); 811 } 812 } else { 813 VisitCondition(not_equal); 814 } 815 } else { 816 VisitCondition(not_equal); 817 } 818 } 819 820 void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) { 821 HInstruction* input = bool_not->InputAt(0); 822 HInstruction* replace_with = nullptr; 823 824 if (input->IsIntConstant()) { 825 // Replace !(true/false) with false/true. 826 if (input->AsIntConstant()->IsTrue()) { 827 replace_with = GetGraph()->GetIntConstant(0); 828 } else { 829 DCHECK(input->AsIntConstant()->IsFalse()) << input->AsIntConstant()->GetValue(); 830 replace_with = GetGraph()->GetIntConstant(1); 831 } 832 } else if (input->IsBooleanNot()) { 833 // Replace (!(!bool_value)) with bool_value. 834 replace_with = input->InputAt(0); 835 } else if (input->IsCondition() && 836 // Don't change FP compares. The definition of compares involving 837 // NaNs forces the compares to be done as written by the user. 838 !DataType::IsFloatingPointType(input->InputAt(0)->GetType())) { 839 // Replace condition with its opposite. 840 replace_with = GetGraph()->InsertOppositeCondition(input->AsCondition(), bool_not); 841 } 842 843 if (replace_with != nullptr) { 844 bool_not->ReplaceWith(replace_with); 845 bool_not->GetBlock()->RemoveInstruction(bool_not); 846 RecordSimplification(); 847 } 848 } 849 850 // Constructs a new ABS(x) node in the HIR. 851 static HInstruction* NewIntegralAbs(ArenaAllocator* allocator, 852 HInstruction* x, 853 HInstruction* cursor) { 854 DataType::Type type = DataType::Kind(x->GetType()); 855 DCHECK(type == DataType::Type::kInt32 || type == DataType::Type::kInt64); 856 HAbs* abs = new (allocator) HAbs(type, x, cursor->GetDexPc()); 857 cursor->GetBlock()->InsertInstructionBefore(abs, cursor); 858 return abs; 859 } 860 861 // Constructs a new MIN/MAX(x, y) node in the HIR. 862 static HInstruction* NewIntegralMinMax(ArenaAllocator* allocator, 863 HInstruction* x, 864 HInstruction* y, 865 HInstruction* cursor, 866 bool is_min) { 867 DataType::Type type = DataType::Kind(x->GetType()); 868 DCHECK(type == DataType::Type::kInt32 || type == DataType::Type::kInt64); 869 HBinaryOperation* minmax = nullptr; 870 if (is_min) { 871 minmax = new (allocator) HMin(type, x, y, cursor->GetDexPc()); 872 } else { 873 minmax = new (allocator) HMax(type, x, y, cursor->GetDexPc()); 874 } 875 cursor->GetBlock()->InsertInstructionBefore(minmax, cursor); 876 return minmax; 877 } 878 879 // Returns true if operands a and b consists of widening type conversions 880 // (either explicit or implicit) to the given to_type. 881 static bool AreLowerPrecisionArgs(DataType::Type to_type, HInstruction* a, HInstruction* b) { 882 if (a->IsTypeConversion() && a->GetType() == to_type) { 883 a = a->InputAt(0); 884 } 885 if (b->IsTypeConversion() && b->GetType() == to_type) { 886 b = b->InputAt(0); 887 } 888 DataType::Type type1 = a->GetType(); 889 DataType::Type type2 = b->GetType(); 890 return (type1 == DataType::Type::kUint8 && type2 == DataType::Type::kUint8) || 891 (type1 == DataType::Type::kInt8 && type2 == DataType::Type::kInt8) || 892 (type1 == DataType::Type::kInt16 && type2 == DataType::Type::kInt16) || 893 (type1 == DataType::Type::kUint16 && type2 == DataType::Type::kUint16) || 894 (type1 == DataType::Type::kInt32 && type2 == DataType::Type::kInt32 && 895 to_type == DataType::Type::kInt64); 896 } 897 898 // Returns an acceptable substitution for "a" on the select 899 // construct "a <cmp> b ? c : .." during MIN/MAX recognition. 900 static HInstruction* AllowInMinMax(IfCondition cmp, 901 HInstruction* a, 902 HInstruction* b, 903 HInstruction* c) { 904 int64_t value = 0; 905 if (IsInt64AndGet(b, /*out*/ &value) && 906 (((cmp == kCondLT || cmp == kCondLE) && c->IsMax()) || 907 ((cmp == kCondGT || cmp == kCondGE) && c->IsMin()))) { 908 HConstant* other = c->AsBinaryOperation()->GetConstantRight(); 909 if (other != nullptr && a == c->AsBinaryOperation()->GetLeastConstantLeft()) { 910 int64_t other_value = Int64FromConstant(other); 911 bool is_max = (cmp == kCondLT || cmp == kCondLE); 912 // Allow the max for a < 100 ? max(a, -100) : .. 913 // or the min for a > -100 ? min(a, 100) : .. 914 if (is_max ? (value >= other_value) : (value <= other_value)) { 915 return c; 916 } 917 } 918 } 919 return nullptr; 920 } 921 922 void InstructionSimplifierVisitor::VisitSelect(HSelect* select) { 923 HInstruction* replace_with = nullptr; 924 HInstruction* condition = select->GetCondition(); 925 HInstruction* true_value = select->GetTrueValue(); 926 HInstruction* false_value = select->GetFalseValue(); 927 928 if (condition->IsBooleanNot()) { 929 // Change ((!cond) ? x : y) to (cond ? y : x). 930 condition = condition->InputAt(0); 931 std::swap(true_value, false_value); 932 select->ReplaceInput(false_value, 0); 933 select->ReplaceInput(true_value, 1); 934 select->ReplaceInput(condition, 2); 935 RecordSimplification(); 936 } 937 938 if (true_value == false_value) { 939 // Replace (cond ? x : x) with (x). 940 replace_with = true_value; 941 } else if (condition->IsIntConstant()) { 942 if (condition->AsIntConstant()->IsTrue()) { 943 // Replace (true ? x : y) with (x). 944 replace_with = true_value; 945 } else { 946 // Replace (false ? x : y) with (y). 947 DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue(); 948 replace_with = false_value; 949 } 950 } else if (true_value->IsIntConstant() && false_value->IsIntConstant()) { 951 if (true_value->AsIntConstant()->IsTrue() && false_value->AsIntConstant()->IsFalse()) { 952 // Replace (cond ? true : false) with (cond). 953 replace_with = condition; 954 } else if (true_value->AsIntConstant()->IsFalse() && false_value->AsIntConstant()->IsTrue()) { 955 // Replace (cond ? false : true) with (!cond). 956 replace_with = GetGraph()->InsertOppositeCondition(condition, select); 957 } 958 } else if (condition->IsCondition()) { 959 IfCondition cmp = condition->AsCondition()->GetCondition(); 960 HInstruction* a = condition->InputAt(0); 961 HInstruction* b = condition->InputAt(1); 962 DataType::Type t_type = true_value->GetType(); 963 DataType::Type f_type = false_value->GetType(); 964 // Here we have a <cmp> b ? true_value : false_value. 965 // Test if both values are compatible integral types (resulting MIN/MAX/ABS 966 // type will be int or long, like the condition). Replacements are general, 967 // but assume conditions prefer constants on the right. 968 if (DataType::IsIntegralType(t_type) && DataType::Kind(t_type) == DataType::Kind(f_type)) { 969 // Allow a < 100 ? max(a, -100) : .. 970 // or a > -100 ? min(a, 100) : .. 971 // to use min/max instead of a to detect nested min/max expressions. 972 HInstruction* new_a = AllowInMinMax(cmp, a, b, true_value); 973 if (new_a != nullptr) { 974 a = new_a; 975 } 976 // Try to replace typical integral MIN/MAX/ABS constructs. 977 if ((cmp == kCondLT || cmp == kCondLE || cmp == kCondGT || cmp == kCondGE) && 978 ((a == true_value && b == false_value) || 979 (b == true_value && a == false_value))) { 980 // Found a < b ? a : b (MIN) or a < b ? b : a (MAX) 981 // or a > b ? a : b (MAX) or a > b ? b : a (MIN). 982 bool is_min = (cmp == kCondLT || cmp == kCondLE) == (a == true_value); 983 replace_with = NewIntegralMinMax(GetGraph()->GetAllocator(), a, b, select, is_min); 984 } else if (((cmp == kCondLT || cmp == kCondLE) && true_value->IsNeg()) || 985 ((cmp == kCondGT || cmp == kCondGE) && false_value->IsNeg())) { 986 bool negLeft = (cmp == kCondLT || cmp == kCondLE); 987 HInstruction* the_negated = negLeft ? true_value->InputAt(0) : false_value->InputAt(0); 988 HInstruction* not_negated = negLeft ? false_value : true_value; 989 if (a == the_negated && a == not_negated && IsInt64Value(b, 0)) { 990 // Found a < 0 ? -a : a 991 // or a > 0 ? a : -a 992 // which can be replaced by ABS(a). 993 replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), a, select); 994 } 995 } else if (true_value->IsSub() && false_value->IsSub()) { 996 HInstruction* true_sub1 = true_value->InputAt(0); 997 HInstruction* true_sub2 = true_value->InputAt(1); 998 HInstruction* false_sub1 = false_value->InputAt(0); 999 HInstruction* false_sub2 = false_value->InputAt(1); 1000 if ((((cmp == kCondGT || cmp == kCondGE) && 1001 (a == true_sub1 && b == true_sub2 && a == false_sub2 && b == false_sub1)) || 1002 ((cmp == kCondLT || cmp == kCondLE) && 1003 (a == true_sub2 && b == true_sub1 && a == false_sub1 && b == false_sub2))) && 1004 AreLowerPrecisionArgs(t_type, a, b)) { 1005 // Found a > b ? a - b : b - a 1006 // or a < b ? b - a : a - b 1007 // which can be replaced by ABS(a - b) for lower precision operands a, b. 1008 replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), true_value, select); 1009 } 1010 } 1011 } 1012 } 1013 1014 if (replace_with != nullptr) { 1015 select->ReplaceWith(replace_with); 1016 select->GetBlock()->RemoveInstruction(select); 1017 RecordSimplification(); 1018 } 1019 } 1020 1021 void InstructionSimplifierVisitor::VisitIf(HIf* instruction) { 1022 HInstruction* condition = instruction->InputAt(0); 1023 if (condition->IsBooleanNot()) { 1024 // Swap successors if input is negated. 1025 instruction->ReplaceInput(condition->InputAt(0), 0); 1026 instruction->GetBlock()->SwapSuccessors(); 1027 RecordSimplification(); 1028 } 1029 } 1030 1031 void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) { 1032 HInstruction* input = instruction->InputAt(0); 1033 // If the array is a NewArray with constant size, replace the array length 1034 // with the constant instruction. This helps the bounds check elimination phase. 1035 if (input->IsNewArray()) { 1036 input = input->AsNewArray()->GetLength(); 1037 if (input->IsIntConstant()) { 1038 instruction->ReplaceWith(input); 1039 } 1040 } 1041 } 1042 1043 void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) { 1044 HInstruction* value = instruction->GetValue(); 1045 if (value->GetType() != DataType::Type::kReference) { 1046 return; 1047 } 1048 1049 if (CanEnsureNotNullAt(value, instruction)) { 1050 instruction->ClearValueCanBeNull(); 1051 } 1052 1053 if (value->IsArrayGet()) { 1054 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) { 1055 // If the code is just swapping elements in the array, no need for a type check. 1056 instruction->ClearNeedsTypeCheck(); 1057 return; 1058 } 1059 } 1060 1061 if (value->IsNullConstant()) { 1062 instruction->ClearNeedsTypeCheck(); 1063 return; 1064 } 1065 1066 ScopedObjectAccess soa(Thread::Current()); 1067 ReferenceTypeInfo array_rti = instruction->GetArray()->GetReferenceTypeInfo(); 1068 ReferenceTypeInfo value_rti = value->GetReferenceTypeInfo(); 1069 if (!array_rti.IsValid()) { 1070 return; 1071 } 1072 1073 if (value_rti.IsValid() && array_rti.CanArrayHold(value_rti)) { 1074 instruction->ClearNeedsTypeCheck(); 1075 return; 1076 } 1077 1078 if (array_rti.IsObjectArray()) { 1079 if (array_rti.IsExact()) { 1080 instruction->ClearNeedsTypeCheck(); 1081 return; 1082 } 1083 instruction->SetStaticTypeOfArrayIsObjectArray(); 1084 } 1085 } 1086 1087 static bool IsTypeConversionLossless(DataType::Type input_type, DataType::Type result_type) { 1088 // Make sure all implicit conversions have been simplified and no new ones have been introduced. 1089 DCHECK(!DataType::IsTypeConversionImplicit(input_type, result_type)) 1090 << input_type << "," << result_type; 1091 // The conversion to a larger type is loss-less with the exception of two cases, 1092 // - conversion to the unsigned type Uint16, where we may lose some bits, and 1093 // - conversion from float to long, the only FP to integral conversion with smaller FP type. 1094 // For integral to FP conversions this holds because the FP mantissa is large enough. 1095 // Note: The size check excludes Uint8 as the result type. 1096 return DataType::Size(result_type) > DataType::Size(input_type) && 1097 result_type != DataType::Type::kUint16 && 1098 !(result_type == DataType::Type::kInt64 && input_type == DataType::Type::kFloat32); 1099 } 1100 1101 static inline bool TryReplaceFieldOrArrayGetType(HInstruction* maybe_get, DataType::Type new_type) { 1102 if (maybe_get->IsInstanceFieldGet()) { 1103 maybe_get->AsInstanceFieldGet()->SetType(new_type); 1104 return true; 1105 } else if (maybe_get->IsStaticFieldGet()) { 1106 maybe_get->AsStaticFieldGet()->SetType(new_type); 1107 return true; 1108 } else if (maybe_get->IsArrayGet() && !maybe_get->AsArrayGet()->IsStringCharAt()) { 1109 maybe_get->AsArrayGet()->SetType(new_type); 1110 return true; 1111 } else { 1112 return false; 1113 } 1114 } 1115 1116 // The type conversion is only used for storing into a field/element of the 1117 // same/narrower size. 1118 static bool IsTypeConversionForStoringIntoNoWiderFieldOnly(HTypeConversion* type_conversion) { 1119 if (type_conversion->HasEnvironmentUses()) { 1120 return false; 1121 } 1122 DataType::Type input_type = type_conversion->GetInputType(); 1123 DataType::Type result_type = type_conversion->GetResultType(); 1124 if (!DataType::IsIntegralType(input_type) || 1125 !DataType::IsIntegralType(result_type) || 1126 input_type == DataType::Type::kInt64 || 1127 result_type == DataType::Type::kInt64) { 1128 // Type conversion is needed if non-integer types are involved, or 64-bit 1129 // types are involved, which may use different number of registers. 1130 return false; 1131 } 1132 if (DataType::Size(input_type) >= DataType::Size(result_type)) { 1133 // Type conversion is not necessary when storing to a field/element of the 1134 // same/smaller size. 1135 } else { 1136 // We do not handle this case here. 1137 return false; 1138 } 1139 1140 // Check if the converted value is only used for storing into heap. 1141 for (const HUseListNode<HInstruction*>& use : type_conversion->GetUses()) { 1142 HInstruction* instruction = use.GetUser(); 1143 if (instruction->IsInstanceFieldSet() && 1144 instruction->AsInstanceFieldSet()->GetFieldType() == result_type) { 1145 DCHECK_EQ(instruction->AsInstanceFieldSet()->GetValue(), type_conversion); 1146 continue; 1147 } 1148 if (instruction->IsStaticFieldSet() && 1149 instruction->AsStaticFieldSet()->GetFieldType() == result_type) { 1150 DCHECK_EQ(instruction->AsStaticFieldSet()->GetValue(), type_conversion); 1151 continue; 1152 } 1153 if (instruction->IsArraySet() && 1154 instruction->AsArraySet()->GetComponentType() == result_type && 1155 // not index use. 1156 instruction->AsArraySet()->GetIndex() != type_conversion) { 1157 DCHECK_EQ(instruction->AsArraySet()->GetValue(), type_conversion); 1158 continue; 1159 } 1160 // The use is not as a store value, or the field/element type is not the 1161 // same as the result_type, keep the type conversion. 1162 return false; 1163 } 1164 // Codegen automatically handles the type conversion during the store. 1165 return true; 1166 } 1167 1168 void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) { 1169 HInstruction* input = instruction->GetInput(); 1170 DataType::Type input_type = input->GetType(); 1171 DataType::Type result_type = instruction->GetResultType(); 1172 if (instruction->IsImplicitConversion()) { 1173 instruction->ReplaceWith(input); 1174 instruction->GetBlock()->RemoveInstruction(instruction); 1175 RecordSimplification(); 1176 return; 1177 } 1178 1179 if (input->IsTypeConversion()) { 1180 HTypeConversion* input_conversion = input->AsTypeConversion(); 1181 HInstruction* original_input = input_conversion->GetInput(); 1182 DataType::Type original_type = original_input->GetType(); 1183 1184 // When the first conversion is lossless, a direct conversion from the original type 1185 // to the final type yields the same result, even for a lossy second conversion, for 1186 // example float->double->int or int->double->float. 1187 bool is_first_conversion_lossless = IsTypeConversionLossless(original_type, input_type); 1188 1189 // For integral conversions, see if the first conversion loses only bits that the second 1190 // doesn't need, i.e. the final type is no wider than the intermediate. If so, direct 1191 // conversion yields the same result, for example long->int->short or int->char->short. 1192 bool integral_conversions_with_non_widening_second = 1193 DataType::IsIntegralType(input_type) && 1194 DataType::IsIntegralType(original_type) && 1195 DataType::IsIntegralType(result_type) && 1196 DataType::Size(result_type) <= DataType::Size(input_type); 1197 1198 if (is_first_conversion_lossless || integral_conversions_with_non_widening_second) { 1199 // If the merged conversion is implicit, do the simplification unconditionally. 1200 if (DataType::IsTypeConversionImplicit(original_type, result_type)) { 1201 instruction->ReplaceWith(original_input); 1202 instruction->GetBlock()->RemoveInstruction(instruction); 1203 if (!input_conversion->HasUses()) { 1204 // Don't wait for DCE. 1205 input_conversion->GetBlock()->RemoveInstruction(input_conversion); 1206 } 1207 RecordSimplification(); 1208 return; 1209 } 1210 // Otherwise simplify only if the first conversion has no other use. 1211 if (input_conversion->HasOnlyOneNonEnvironmentUse()) { 1212 input_conversion->ReplaceWith(original_input); 1213 input_conversion->GetBlock()->RemoveInstruction(input_conversion); 1214 RecordSimplification(); 1215 return; 1216 } 1217 } 1218 } else if (input->IsAnd() && DataType::IsIntegralType(result_type)) { 1219 DCHECK(DataType::IsIntegralType(input_type)); 1220 HAnd* input_and = input->AsAnd(); 1221 HConstant* constant = input_and->GetConstantRight(); 1222 if (constant != nullptr) { 1223 int64_t value = Int64FromConstant(constant); 1224 DCHECK_NE(value, -1); // "& -1" would have been optimized away in VisitAnd(). 1225 size_t trailing_ones = CTZ(~static_cast<uint64_t>(value)); 1226 if (trailing_ones >= kBitsPerByte * DataType::Size(result_type)) { 1227 // The `HAnd` is useless, for example in `(byte) (x & 0xff)`, get rid of it. 1228 HInstruction* original_input = input_and->GetLeastConstantLeft(); 1229 if (DataType::IsTypeConversionImplicit(original_input->GetType(), result_type)) { 1230 instruction->ReplaceWith(original_input); 1231 instruction->GetBlock()->RemoveInstruction(instruction); 1232 RecordSimplification(); 1233 return; 1234 } else if (input->HasOnlyOneNonEnvironmentUse()) { 1235 input_and->ReplaceWith(original_input); 1236 input_and->GetBlock()->RemoveInstruction(input_and); 1237 RecordSimplification(); 1238 return; 1239 } 1240 } 1241 } 1242 } else if (input->HasOnlyOneNonEnvironmentUse() && 1243 ((input_type == DataType::Type::kInt8 && result_type == DataType::Type::kUint8) || 1244 (input_type == DataType::Type::kUint8 && result_type == DataType::Type::kInt8) || 1245 (input_type == DataType::Type::kInt16 && result_type == DataType::Type::kUint16) || 1246 (input_type == DataType::Type::kUint16 && result_type == DataType::Type::kInt16))) { 1247 // Try to modify the type of the load to `result_type` and remove the explicit type conversion. 1248 if (TryReplaceFieldOrArrayGetType(input, result_type)) { 1249 instruction->ReplaceWith(input); 1250 instruction->GetBlock()->RemoveInstruction(instruction); 1251 RecordSimplification(); 1252 return; 1253 } 1254 } 1255 1256 if (IsTypeConversionForStoringIntoNoWiderFieldOnly(instruction)) { 1257 instruction->ReplaceWith(input); 1258 instruction->GetBlock()->RemoveInstruction(instruction); 1259 RecordSimplification(); 1260 return; 1261 } 1262 } 1263 1264 void InstructionSimplifierVisitor::VisitAbs(HAbs* instruction) { 1265 HInstruction* input = instruction->GetInput(); 1266 if (DataType::IsZeroExtension(input->GetType(), instruction->GetResultType())) { 1267 // Zero extension from narrow to wide can never set sign bit in the wider 1268 // operand, making the subsequent Abs redundant (e.g., abs(b & 0xff) for byte b). 1269 instruction->ReplaceWith(input); 1270 instruction->GetBlock()->RemoveInstruction(instruction); 1271 RecordSimplification(); 1272 } 1273 } 1274 1275 void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) { 1276 HConstant* input_cst = instruction->GetConstantRight(); 1277 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1278 bool integral_type = DataType::IsIntegralType(instruction->GetType()); 1279 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) { 1280 // Replace code looking like 1281 // ADD dst, src, 0 1282 // with 1283 // src 1284 // Note that we cannot optimize `x + 0.0` to `x` for floating-point. When 1285 // `x` is `-0.0`, the former expression yields `0.0`, while the later 1286 // yields `-0.0`. 1287 if (integral_type) { 1288 instruction->ReplaceWith(input_other); 1289 instruction->GetBlock()->RemoveInstruction(instruction); 1290 RecordSimplification(); 1291 return; 1292 } 1293 } 1294 1295 HInstruction* left = instruction->GetLeft(); 1296 HInstruction* right = instruction->GetRight(); 1297 bool left_is_neg = left->IsNeg(); 1298 bool right_is_neg = right->IsNeg(); 1299 1300 if (left_is_neg && right_is_neg) { 1301 if (TryMoveNegOnInputsAfterBinop(instruction)) { 1302 return; 1303 } 1304 } 1305 1306 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg(); 1307 if (left_is_neg != right_is_neg && neg->HasOnlyOneNonEnvironmentUse()) { 1308 // Replace code looking like 1309 // NEG tmp, b 1310 // ADD dst, a, tmp 1311 // with 1312 // SUB dst, a, b 1313 // We do not perform the optimization if the input negation has environment 1314 // uses or multiple non-environment uses as it could lead to worse code. In 1315 // particular, we do not want the live range of `b` to be extended if we are 1316 // not sure the initial 'NEG' instruction can be removed. 1317 HInstruction* other = left_is_neg ? right : left; 1318 HSub* sub = 1319 new(GetGraph()->GetAllocator()) HSub(instruction->GetType(), other, neg->GetInput()); 1320 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub); 1321 RecordSimplification(); 1322 neg->GetBlock()->RemoveInstruction(neg); 1323 return; 1324 } 1325 1326 if (TryReplaceWithRotate(instruction)) { 1327 return; 1328 } 1329 1330 // TryHandleAssociativeAndCommutativeOperation() does not remove its input, 1331 // so no need to return. 1332 TryHandleAssociativeAndCommutativeOperation(instruction); 1333 1334 if ((left->IsSub() || right->IsSub()) && 1335 TrySubtractionChainSimplification(instruction)) { 1336 return; 1337 } 1338 1339 if (integral_type) { 1340 // Replace code patterns looking like 1341 // SUB dst1, x, y SUB dst1, x, y 1342 // ADD dst2, dst1, y ADD dst2, y, dst1 1343 // with 1344 // SUB dst1, x, y 1345 // ADD instruction is not needed in this case, we may use 1346 // one of inputs of SUB instead. 1347 if (left->IsSub() && left->InputAt(1) == right) { 1348 instruction->ReplaceWith(left->InputAt(0)); 1349 RecordSimplification(); 1350 instruction->GetBlock()->RemoveInstruction(instruction); 1351 return; 1352 } else if (right->IsSub() && right->InputAt(1) == left) { 1353 instruction->ReplaceWith(right->InputAt(0)); 1354 RecordSimplification(); 1355 instruction->GetBlock()->RemoveInstruction(instruction); 1356 return; 1357 } 1358 } 1359 } 1360 1361 void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) { 1362 DCHECK(DataType::IsIntegralType(instruction->GetType())); 1363 HConstant* input_cst = instruction->GetConstantRight(); 1364 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1365 1366 if (input_cst != nullptr) { 1367 int64_t value = Int64FromConstant(input_cst); 1368 if (value == -1 || 1369 // Similar cases under zero extension. 1370 (DataType::IsUnsignedType(input_other->GetType()) && 1371 ((DataType::MaxValueOfIntegralType(input_other->GetType()) & ~value) == 0))) { 1372 // Replace code looking like 1373 // AND dst, src, 0xFFF...FF 1374 // with 1375 // src 1376 instruction->ReplaceWith(input_other); 1377 instruction->GetBlock()->RemoveInstruction(instruction); 1378 RecordSimplification(); 1379 return; 1380 } 1381 if (input_other->IsTypeConversion() && 1382 input_other->GetType() == DataType::Type::kInt64 && 1383 DataType::IsIntegralType(input_other->InputAt(0)->GetType()) && 1384 IsInt<32>(value) && 1385 input_other->HasOnlyOneNonEnvironmentUse()) { 1386 // The AND can be reordered before the TypeConversion. Replace 1387 // LongConstant cst, <32-bit-constant-sign-extended-to-64-bits> 1388 // TypeConversion<Int64> tmp, src 1389 // AND dst, tmp, cst 1390 // with 1391 // IntConstant cst, <32-bit-constant> 1392 // AND tmp, src, cst 1393 // TypeConversion<Int64> dst, tmp 1394 // This helps 32-bit targets and does not hurt 64-bit targets. 1395 // This also simplifies detection of other patterns, such as Uint8 loads. 1396 HInstruction* new_and_input = input_other->InputAt(0); 1397 // Implicit conversion Int64->Int64 would have been removed previously. 1398 DCHECK_NE(new_and_input->GetType(), DataType::Type::kInt64); 1399 HConstant* new_const = GetGraph()->GetConstant(DataType::Type::kInt32, value); 1400 HAnd* new_and = 1401 new (GetGraph()->GetAllocator()) HAnd(DataType::Type::kInt32, new_and_input, new_const); 1402 instruction->GetBlock()->InsertInstructionBefore(new_and, instruction); 1403 HTypeConversion* new_conversion = 1404 new (GetGraph()->GetAllocator()) HTypeConversion(DataType::Type::kInt64, new_and); 1405 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_conversion); 1406 input_other->GetBlock()->RemoveInstruction(input_other); 1407 RecordSimplification(); 1408 // Try to process the new And now, do not wait for the next round of simplifications. 1409 instruction = new_and; 1410 input_other = new_and_input; 1411 } 1412 // Eliminate And from UShr+And if the And-mask contains all the bits that 1413 // can be non-zero after UShr. Transform Shr+And to UShr if the And-mask 1414 // precisely clears the shifted-in sign bits. 1415 if ((input_other->IsUShr() || input_other->IsShr()) && input_other->InputAt(1)->IsConstant()) { 1416 size_t reg_bits = (instruction->GetResultType() == DataType::Type::kInt64) ? 64 : 32; 1417 size_t shift = Int64FromConstant(input_other->InputAt(1)->AsConstant()) & (reg_bits - 1); 1418 size_t num_tail_bits_set = CTZ(value + 1); 1419 if ((num_tail_bits_set >= reg_bits - shift) && input_other->IsUShr()) { 1420 // This AND clears only bits known to be clear, for example "(x >>> 24) & 0xff". 1421 instruction->ReplaceWith(input_other); 1422 instruction->GetBlock()->RemoveInstruction(instruction); 1423 RecordSimplification(); 1424 return; 1425 } else if ((num_tail_bits_set == reg_bits - shift) && IsPowerOfTwo(value + 1) && 1426 input_other->HasOnlyOneNonEnvironmentUse()) { 1427 DCHECK(input_other->IsShr()); // For UShr, we would have taken the branch above. 1428 // Replace SHR+AND with USHR, for example "(x >> 24) & 0xff" -> "x >>> 24". 1429 HUShr* ushr = new (GetGraph()->GetAllocator()) HUShr(instruction->GetType(), 1430 input_other->InputAt(0), 1431 input_other->InputAt(1), 1432 input_other->GetDexPc()); 1433 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, ushr); 1434 input_other->GetBlock()->RemoveInstruction(input_other); 1435 RecordSimplification(); 1436 return; 1437 } 1438 } 1439 if ((value == 0xff || value == 0xffff) && instruction->GetType() != DataType::Type::kInt64) { 1440 // Transform AND to a type conversion to Uint8/Uint16. If `input_other` is a field 1441 // or array Get with only a single use, short-circuit the subsequent simplification 1442 // of the Get+TypeConversion and change the Get's type to `new_type` instead. 1443 DataType::Type new_type = (value == 0xff) ? DataType::Type::kUint8 : DataType::Type::kUint16; 1444 DataType::Type find_type = (value == 0xff) ? DataType::Type::kInt8 : DataType::Type::kInt16; 1445 if (input_other->GetType() == find_type && 1446 input_other->HasOnlyOneNonEnvironmentUse() && 1447 TryReplaceFieldOrArrayGetType(input_other, new_type)) { 1448 instruction->ReplaceWith(input_other); 1449 instruction->GetBlock()->RemoveInstruction(instruction); 1450 } else if (DataType::IsTypeConversionImplicit(input_other->GetType(), new_type)) { 1451 instruction->ReplaceWith(input_other); 1452 instruction->GetBlock()->RemoveInstruction(instruction); 1453 } else { 1454 HTypeConversion* type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion( 1455 new_type, input_other, instruction->GetDexPc()); 1456 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, type_conversion); 1457 } 1458 RecordSimplification(); 1459 return; 1460 } 1461 } 1462 1463 // We assume that GVN has run before, so we only perform a pointer comparison. 1464 // If for some reason the values are equal but the pointers are different, we 1465 // are still correct and only miss an optimization opportunity. 1466 if (instruction->GetLeft() == instruction->GetRight()) { 1467 // Replace code looking like 1468 // AND dst, src, src 1469 // with 1470 // src 1471 instruction->ReplaceWith(instruction->GetLeft()); 1472 instruction->GetBlock()->RemoveInstruction(instruction); 1473 RecordSimplification(); 1474 return; 1475 } 1476 1477 if (TryDeMorganNegationFactoring(instruction)) { 1478 return; 1479 } 1480 1481 // TryHandleAssociativeAndCommutativeOperation() does not remove its input, 1482 // so no need to return. 1483 TryHandleAssociativeAndCommutativeOperation(instruction); 1484 } 1485 1486 void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) { 1487 VisitCondition(condition); 1488 } 1489 1490 void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) { 1491 VisitCondition(condition); 1492 } 1493 1494 void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) { 1495 VisitCondition(condition); 1496 } 1497 1498 void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) { 1499 VisitCondition(condition); 1500 } 1501 1502 void InstructionSimplifierVisitor::VisitBelow(HBelow* condition) { 1503 VisitCondition(condition); 1504 } 1505 1506 void InstructionSimplifierVisitor::VisitBelowOrEqual(HBelowOrEqual* condition) { 1507 VisitCondition(condition); 1508 } 1509 1510 void InstructionSimplifierVisitor::VisitAbove(HAbove* condition) { 1511 VisitCondition(condition); 1512 } 1513 1514 void InstructionSimplifierVisitor::VisitAboveOrEqual(HAboveOrEqual* condition) { 1515 VisitCondition(condition); 1516 } 1517 1518 // Recognize the following pattern: 1519 // obj.getClass() ==/!= Foo.class 1520 // And replace it with a constant value if the type of `obj` is statically known. 1521 static bool RecognizeAndSimplifyClassCheck(HCondition* condition) { 1522 HInstruction* input_one = condition->InputAt(0); 1523 HInstruction* input_two = condition->InputAt(1); 1524 HLoadClass* load_class = input_one->IsLoadClass() 1525 ? input_one->AsLoadClass() 1526 : input_two->AsLoadClass(); 1527 if (load_class == nullptr) { 1528 return false; 1529 } 1530 1531 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI(); 1532 if (!class_rti.IsValid()) { 1533 // Unresolved class. 1534 return false; 1535 } 1536 1537 HInstanceFieldGet* field_get = (load_class == input_one) 1538 ? input_two->AsInstanceFieldGet() 1539 : input_one->AsInstanceFieldGet(); 1540 if (field_get == nullptr) { 1541 return false; 1542 } 1543 1544 HInstruction* receiver = field_get->InputAt(0); 1545 ReferenceTypeInfo receiver_type = receiver->GetReferenceTypeInfo(); 1546 if (!receiver_type.IsExact()) { 1547 return false; 1548 } 1549 1550 { 1551 ScopedObjectAccess soa(Thread::Current()); 1552 ArtField* field = GetClassRoot<mirror::Object>()->GetInstanceField(0); 1553 DCHECK_EQ(std::string(field->GetName()), "shadow$_klass_"); 1554 if (field_get->GetFieldInfo().GetField() != field) { 1555 return false; 1556 } 1557 1558 // We can replace the compare. 1559 int value = 0; 1560 if (receiver_type.IsEqual(class_rti)) { 1561 value = condition->IsEqual() ? 1 : 0; 1562 } else { 1563 value = condition->IsNotEqual() ? 1 : 0; 1564 } 1565 condition->ReplaceWith(condition->GetBlock()->GetGraph()->GetIntConstant(value)); 1566 return true; 1567 } 1568 } 1569 1570 void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) { 1571 if (condition->IsEqual() || condition->IsNotEqual()) { 1572 if (RecognizeAndSimplifyClassCheck(condition)) { 1573 return; 1574 } 1575 } 1576 1577 // Reverse condition if left is constant. Our code generators prefer constant 1578 // on the right hand side. 1579 if (condition->GetLeft()->IsConstant() && !condition->GetRight()->IsConstant()) { 1580 HBasicBlock* block = condition->GetBlock(); 1581 HCondition* replacement = 1582 GetOppositeConditionSwapOps(block->GetGraph()->GetAllocator(), condition); 1583 // If it is a fp we must set the opposite bias. 1584 if (replacement != nullptr) { 1585 if (condition->IsLtBias()) { 1586 replacement->SetBias(ComparisonBias::kGtBias); 1587 } else if (condition->IsGtBias()) { 1588 replacement->SetBias(ComparisonBias::kLtBias); 1589 } 1590 block->ReplaceAndRemoveInstructionWith(condition, replacement); 1591 RecordSimplification(); 1592 1593 condition = replacement; 1594 } 1595 } 1596 1597 HInstruction* left = condition->GetLeft(); 1598 HInstruction* right = condition->GetRight(); 1599 1600 // Try to fold an HCompare into this HCondition. 1601 1602 // We can only replace an HCondition which compares a Compare to 0. 1603 // Both 'dx' and 'jack' generate a compare to 0 when compiling a 1604 // condition with a long, float or double comparison as input. 1605 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) { 1606 // Conversion is not possible. 1607 return; 1608 } 1609 1610 // Is the Compare only used for this purpose? 1611 if (!left->GetUses().HasExactlyOneElement()) { 1612 // Someone else also wants the result of the compare. 1613 return; 1614 } 1615 1616 if (!left->GetEnvUses().empty()) { 1617 // There is a reference to the compare result in an environment. Do we really need it? 1618 if (GetGraph()->IsDebuggable()) { 1619 return; 1620 } 1621 1622 // We have to ensure that there are no deopt points in the sequence. 1623 if (left->HasAnyEnvironmentUseBefore(condition)) { 1624 return; 1625 } 1626 } 1627 1628 // Clean up any environment uses from the HCompare, if any. 1629 left->RemoveEnvironmentUsers(); 1630 1631 // We have decided to fold the HCompare into the HCondition. Transfer the information. 1632 condition->SetBias(left->AsCompare()->GetBias()); 1633 1634 // Replace the operands of the HCondition. 1635 condition->ReplaceInput(left->InputAt(0), 0); 1636 condition->ReplaceInput(left->InputAt(1), 1); 1637 1638 // Remove the HCompare. 1639 left->GetBlock()->RemoveInstruction(left); 1640 1641 RecordSimplification(); 1642 } 1643 1644 // Return whether x / divisor == x * (1.0f / divisor), for every float x. 1645 static constexpr bool CanDivideByReciprocalMultiplyFloat(int32_t divisor) { 1646 // True, if the most significant bits of divisor are 0. 1647 return ((divisor & 0x7fffff) == 0); 1648 } 1649 1650 // Return whether x / divisor == x * (1.0 / divisor), for every double x. 1651 static constexpr bool CanDivideByReciprocalMultiplyDouble(int64_t divisor) { 1652 // True, if the most significant bits of divisor are 0. 1653 return ((divisor & ((UINT64_C(1) << 52) - 1)) == 0); 1654 } 1655 1656 void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) { 1657 HConstant* input_cst = instruction->GetConstantRight(); 1658 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1659 DataType::Type type = instruction->GetType(); 1660 1661 if ((input_cst != nullptr) && input_cst->IsOne()) { 1662 // Replace code looking like 1663 // DIV dst, src, 1 1664 // with 1665 // src 1666 instruction->ReplaceWith(input_other); 1667 instruction->GetBlock()->RemoveInstruction(instruction); 1668 RecordSimplification(); 1669 return; 1670 } 1671 1672 if ((input_cst != nullptr) && input_cst->IsMinusOne()) { 1673 // Replace code looking like 1674 // DIV dst, src, -1 1675 // with 1676 // NEG dst, src 1677 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 1678 instruction, new (GetGraph()->GetAllocator()) HNeg(type, input_other)); 1679 RecordSimplification(); 1680 return; 1681 } 1682 1683 if ((input_cst != nullptr) && DataType::IsFloatingPointType(type)) { 1684 // Try replacing code looking like 1685 // DIV dst, src, constant 1686 // with 1687 // MUL dst, src, 1 / constant 1688 HConstant* reciprocal = nullptr; 1689 if (type == DataType::Type::kFloat64) { 1690 double value = input_cst->AsDoubleConstant()->GetValue(); 1691 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) { 1692 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value); 1693 } 1694 } else { 1695 DCHECK_EQ(type, DataType::Type::kFloat32); 1696 float value = input_cst->AsFloatConstant()->GetValue(); 1697 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) { 1698 reciprocal = GetGraph()->GetFloatConstant(1.0f / value); 1699 } 1700 } 1701 1702 if (reciprocal != nullptr) { 1703 instruction->GetBlock()->ReplaceAndRemoveInstructionWith( 1704 instruction, new (GetGraph()->GetAllocator()) HMul(type, input_other, reciprocal)); 1705 RecordSimplification(); 1706 return; 1707 } 1708 } 1709 } 1710 1711 void InstructionSimplifierVisitor::VisitMul(HMul* instruction) { 1712 HConstant* input_cst = instruction->GetConstantRight(); 1713 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1714 DataType::Type type = instruction->GetType(); 1715 HBasicBlock* block = instruction->GetBlock(); 1716 ArenaAllocator* allocator = GetGraph()->GetAllocator(); 1717 1718 if (input_cst == nullptr) { 1719 return; 1720 } 1721 1722 if (input_cst->IsOne()) { 1723 // Replace code looking like 1724 // MUL dst, src, 1 1725 // with 1726 // src 1727 instruction->ReplaceWith(input_other); 1728 instruction->GetBlock()->RemoveInstruction(instruction); 1729 RecordSimplification(); 1730 return; 1731 } 1732 1733 if (input_cst->IsMinusOne() && 1734 (DataType::IsFloatingPointType(type) || DataType::IsIntOrLongType(type))) { 1735 // Replace code looking like 1736 // MUL dst, src, -1 1737 // with 1738 // NEG dst, src 1739 HNeg* neg = new (allocator) HNeg(type, input_other); 1740 block->ReplaceAndRemoveInstructionWith(instruction, neg); 1741 RecordSimplification(); 1742 return; 1743 } 1744 1745 if (DataType::IsFloatingPointType(type) && 1746 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) || 1747 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) { 1748 // Replace code looking like 1749 // FP_MUL dst, src, 2.0 1750 // with 1751 // FP_ADD dst, src, src 1752 // The 'int' and 'long' cases are handled below. 1753 block->ReplaceAndRemoveInstructionWith(instruction, 1754 new (allocator) HAdd(type, input_other, input_other)); 1755 RecordSimplification(); 1756 return; 1757 } 1758 1759 if (DataType::IsIntOrLongType(type)) { 1760 int64_t factor = Int64FromConstant(input_cst); 1761 // Even though constant propagation also takes care of the zero case, other 1762 // optimizations can lead to having a zero multiplication. 1763 if (factor == 0) { 1764 // Replace code looking like 1765 // MUL dst, src, 0 1766 // with 1767 // 0 1768 instruction->ReplaceWith(input_cst); 1769 instruction->GetBlock()->RemoveInstruction(instruction); 1770 RecordSimplification(); 1771 return; 1772 } else if (IsPowerOfTwo(factor)) { 1773 // Replace code looking like 1774 // MUL dst, src, pow_of_2 1775 // with 1776 // SHL dst, src, log2(pow_of_2) 1777 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor)); 1778 HShl* shl = new (allocator) HShl(type, input_other, shift); 1779 block->ReplaceAndRemoveInstructionWith(instruction, shl); 1780 RecordSimplification(); 1781 return; 1782 } else if (IsPowerOfTwo(factor - 1)) { 1783 // Transform code looking like 1784 // MUL dst, src, (2^n + 1) 1785 // into 1786 // SHL tmp, src, n 1787 // ADD dst, src, tmp 1788 HShl* shl = new (allocator) HShl(type, 1789 input_other, 1790 GetGraph()->GetIntConstant(WhichPowerOf2(factor - 1))); 1791 HAdd* add = new (allocator) HAdd(type, input_other, shl); 1792 1793 block->InsertInstructionBefore(shl, instruction); 1794 block->ReplaceAndRemoveInstructionWith(instruction, add); 1795 RecordSimplification(); 1796 return; 1797 } else if (IsPowerOfTwo(factor + 1)) { 1798 // Transform code looking like 1799 // MUL dst, src, (2^n - 1) 1800 // into 1801 // SHL tmp, src, n 1802 // SUB dst, tmp, src 1803 HShl* shl = new (allocator) HShl(type, 1804 input_other, 1805 GetGraph()->GetIntConstant(WhichPowerOf2(factor + 1))); 1806 HSub* sub = new (allocator) HSub(type, shl, input_other); 1807 1808 block->InsertInstructionBefore(shl, instruction); 1809 block->ReplaceAndRemoveInstructionWith(instruction, sub); 1810 RecordSimplification(); 1811 return; 1812 } 1813 } 1814 1815 // TryHandleAssociativeAndCommutativeOperation() does not remove its input, 1816 // so no need to return. 1817 TryHandleAssociativeAndCommutativeOperation(instruction); 1818 } 1819 1820 void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) { 1821 HInstruction* input = instruction->GetInput(); 1822 if (input->IsNeg()) { 1823 // Replace code looking like 1824 // NEG tmp, src 1825 // NEG dst, tmp 1826 // with 1827 // src 1828 HNeg* previous_neg = input->AsNeg(); 1829 instruction->ReplaceWith(previous_neg->GetInput()); 1830 instruction->GetBlock()->RemoveInstruction(instruction); 1831 // We perform the optimization even if the input negation has environment 1832 // uses since it allows removing the current instruction. But we only delete 1833 // the input negation only if it is does not have any uses left. 1834 if (!previous_neg->HasUses()) { 1835 previous_neg->GetBlock()->RemoveInstruction(previous_neg); 1836 } 1837 RecordSimplification(); 1838 return; 1839 } 1840 1841 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() && 1842 !DataType::IsFloatingPointType(input->GetType())) { 1843 // Replace code looking like 1844 // SUB tmp, a, b 1845 // NEG dst, tmp 1846 // with 1847 // SUB dst, b, a 1848 // We do not perform the optimization if the input subtraction has 1849 // environment uses or multiple non-environment uses as it could lead to 1850 // worse code. In particular, we do not want the live ranges of `a` and `b` 1851 // to be extended if we are not sure the initial 'SUB' instruction can be 1852 // removed. 1853 // We do not perform optimization for fp because we could lose the sign of zero. 1854 HSub* sub = input->AsSub(); 1855 HSub* new_sub = new (GetGraph()->GetAllocator()) HSub( 1856 instruction->GetType(), sub->GetRight(), sub->GetLeft()); 1857 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub); 1858 if (!sub->HasUses()) { 1859 sub->GetBlock()->RemoveInstruction(sub); 1860 } 1861 RecordSimplification(); 1862 } 1863 } 1864 1865 void InstructionSimplifierVisitor::VisitNot(HNot* instruction) { 1866 HInstruction* input = instruction->GetInput(); 1867 if (input->IsNot()) { 1868 // Replace code looking like 1869 // NOT tmp, src 1870 // NOT dst, tmp 1871 // with 1872 // src 1873 // We perform the optimization even if the input negation has environment 1874 // uses since it allows removing the current instruction. But we only delete 1875 // the input negation only if it is does not have any uses left. 1876 HNot* previous_not = input->AsNot(); 1877 instruction->ReplaceWith(previous_not->GetInput()); 1878 instruction->GetBlock()->RemoveInstruction(instruction); 1879 if (!previous_not->HasUses()) { 1880 previous_not->GetBlock()->RemoveInstruction(previous_not); 1881 } 1882 RecordSimplification(); 1883 } 1884 } 1885 1886 void InstructionSimplifierVisitor::VisitOr(HOr* instruction) { 1887 HConstant* input_cst = instruction->GetConstantRight(); 1888 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1889 1890 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) { 1891 // Replace code looking like 1892 // OR dst, src, 0 1893 // with 1894 // src 1895 instruction->ReplaceWith(input_other); 1896 instruction->GetBlock()->RemoveInstruction(instruction); 1897 RecordSimplification(); 1898 return; 1899 } 1900 1901 // We assume that GVN has run before, so we only perform a pointer comparison. 1902 // If for some reason the values are equal but the pointers are different, we 1903 // are still correct and only miss an optimization opportunity. 1904 if (instruction->GetLeft() == instruction->GetRight()) { 1905 // Replace code looking like 1906 // OR dst, src, src 1907 // with 1908 // src 1909 instruction->ReplaceWith(instruction->GetLeft()); 1910 instruction->GetBlock()->RemoveInstruction(instruction); 1911 RecordSimplification(); 1912 return; 1913 } 1914 1915 if (TryDeMorganNegationFactoring(instruction)) return; 1916 1917 if (TryReplaceWithRotate(instruction)) { 1918 return; 1919 } 1920 1921 // TryHandleAssociativeAndCommutativeOperation() does not remove its input, 1922 // so no need to return. 1923 TryHandleAssociativeAndCommutativeOperation(instruction); 1924 } 1925 1926 void InstructionSimplifierVisitor::VisitShl(HShl* instruction) { 1927 VisitShift(instruction); 1928 } 1929 1930 void InstructionSimplifierVisitor::VisitShr(HShr* instruction) { 1931 VisitShift(instruction); 1932 } 1933 1934 void InstructionSimplifierVisitor::VisitSub(HSub* instruction) { 1935 HConstant* input_cst = instruction->GetConstantRight(); 1936 HInstruction* input_other = instruction->GetLeastConstantLeft(); 1937 1938 DataType::Type type = instruction->GetType(); 1939 if (DataType::IsFloatingPointType(type)) { 1940 return; 1941 } 1942 1943 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) { 1944 // Replace code looking like 1945 // SUB dst, src, 0 1946 // with 1947 // src 1948 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When 1949 // `x` is `-0.0`, the former expression yields `0.0`, while the later 1950 // yields `-0.0`. 1951 instruction->ReplaceWith(input_other); 1952 instruction->GetBlock()->RemoveInstruction(instruction); 1953 RecordSimplification(); 1954 return; 1955 } 1956 1957 HBasicBlock* block = instruction->GetBlock(); 1958 ArenaAllocator* allocator = GetGraph()->GetAllocator(); 1959 1960 HInstruction* left = instruction->GetLeft(); 1961 HInstruction* right = instruction->GetRight(); 1962 if (left->IsConstant()) { 1963 if (Int64FromConstant(left->AsConstant()) == 0) { 1964 // Replace code looking like 1965 // SUB dst, 0, src 1966 // with 1967 // NEG dst, src 1968 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When 1969 // `x` is `0.0`, the former expression yields `0.0`, while the later 1970 // yields `-0.0`. 1971 HNeg* neg = new (allocator) HNeg(type, right); 1972 block->ReplaceAndRemoveInstructionWith(instruction, neg); 1973 RecordSimplification(); 1974 return; 1975 } 1976 } 1977 1978 if (left->IsNeg() && right->IsNeg()) { 1979 if (TryMoveNegOnInputsAfterBinop(instruction)) { 1980 return; 1981 } 1982 } 1983 1984 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) { 1985 // Replace code looking like 1986 // NEG tmp, b 1987 // SUB dst, a, tmp 1988 // with 1989 // ADD dst, a, b 1990 HAdd* add = new(GetGraph()->GetAllocator()) HAdd(type, left, right->AsNeg()->GetInput()); 1991 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add); 1992 RecordSimplification(); 1993 right->GetBlock()->RemoveInstruction(right); 1994 return; 1995 } 1996 1997 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) { 1998 // Replace code looking like 1999 // NEG tmp, a 2000 // SUB dst, tmp, b 2001 // with 2002 // ADD tmp, a, b 2003 // NEG dst, tmp 2004 // The second version is not intrinsically better, but enables more 2005 // transformations. 2006 HAdd* add = new(GetGraph()->GetAllocator()) HAdd(type, left->AsNeg()->GetInput(), right); 2007 instruction->GetBlock()->InsertInstructionBefore(add, instruction); 2008 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(instruction->GetType(), add); 2009 instruction->GetBlock()->InsertInstructionBefore(neg, instruction); 2010 instruction->ReplaceWith(neg); 2011 instruction->GetBlock()->RemoveInstruction(instruction); 2012 RecordSimplification(); 2013 left->GetBlock()->RemoveInstruction(left); 2014 return; 2015 } 2016 2017 if (TrySubtractionChainSimplification(instruction)) { 2018 return; 2019 } 2020 2021 if (left->IsAdd()) { 2022 // Replace code patterns looking like 2023 // ADD dst1, x, y ADD dst1, x, y 2024 // SUB dst2, dst1, y SUB dst2, dst1, x 2025 // with 2026 // ADD dst1, x, y 2027 // SUB instruction is not needed in this case, we may use 2028 // one of inputs of ADD instead. 2029 // It is applicable to integral types only. 2030 DCHECK(DataType::IsIntegralType(type)); 2031 if (left->InputAt(1) == right) { 2032 instruction->ReplaceWith(left->InputAt(0)); 2033 RecordSimplification(); 2034 instruction->GetBlock()->RemoveInstruction(instruction); 2035 return; 2036 } else if (left->InputAt(0) == right) { 2037 instruction->ReplaceWith(left->InputAt(1)); 2038 RecordSimplification(); 2039 instruction->GetBlock()->RemoveInstruction(instruction); 2040 return; 2041 } 2042 } 2043 } 2044 2045 void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) { 2046 VisitShift(instruction); 2047 } 2048 2049 void InstructionSimplifierVisitor::VisitXor(HXor* instruction) { 2050 HConstant* input_cst = instruction->GetConstantRight(); 2051 HInstruction* input_other = instruction->GetLeastConstantLeft(); 2052 2053 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) { 2054 // Replace code looking like 2055 // XOR dst, src, 0 2056 // with 2057 // src 2058 instruction->ReplaceWith(input_other); 2059 instruction->GetBlock()->RemoveInstruction(instruction); 2060 RecordSimplification(); 2061 return; 2062 } 2063 2064 if ((input_cst != nullptr) && input_cst->IsOne() 2065 && input_other->GetType() == DataType::Type::kBool) { 2066 // Replace code looking like 2067 // XOR dst, src, 1 2068 // with 2069 // BOOLEAN_NOT dst, src 2070 HBooleanNot* boolean_not = new (GetGraph()->GetAllocator()) HBooleanNot(input_other); 2071 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, boolean_not); 2072 RecordSimplification(); 2073 return; 2074 } 2075 2076 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) { 2077 // Replace code looking like 2078 // XOR dst, src, 0xFFF...FF 2079 // with 2080 // NOT dst, src 2081 HNot* bitwise_not = new (GetGraph()->GetAllocator()) HNot(instruction->GetType(), input_other); 2082 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not); 2083 RecordSimplification(); 2084 return; 2085 } 2086 2087 HInstruction* left = instruction->GetLeft(); 2088 HInstruction* right = instruction->GetRight(); 2089 if (((left->IsNot() && right->IsNot()) || 2090 (left->IsBooleanNot() && right->IsBooleanNot())) && 2091 left->HasOnlyOneNonEnvironmentUse() && 2092 right->HasOnlyOneNonEnvironmentUse()) { 2093 // Replace code looking like 2094 // NOT nota, a 2095 // NOT notb, b 2096 // XOR dst, nota, notb 2097 // with 2098 // XOR dst, a, b 2099 instruction->ReplaceInput(left->InputAt(0), 0); 2100 instruction->ReplaceInput(right->InputAt(0), 1); 2101 left->GetBlock()->RemoveInstruction(left); 2102 right->GetBlock()->RemoveInstruction(right); 2103 RecordSimplification(); 2104 return; 2105 } 2106 2107 if (TryReplaceWithRotate(instruction)) { 2108 return; 2109 } 2110 2111 // TryHandleAssociativeAndCommutativeOperation() does not remove its input, 2112 // so no need to return. 2113 TryHandleAssociativeAndCommutativeOperation(instruction); 2114 } 2115 2116 void InstructionSimplifierVisitor::SimplifyStringEquals(HInvoke* instruction) { 2117 HInstruction* argument = instruction->InputAt(1); 2118 HInstruction* receiver = instruction->InputAt(0); 2119 if (receiver == argument) { 2120 // Because String.equals is an instance call, the receiver is 2121 // a null check if we don't know it's null. The argument however, will 2122 // be the actual object. So we cannot end up in a situation where both 2123 // are equal but could be null. 2124 DCHECK(CanEnsureNotNullAt(argument, instruction)); 2125 instruction->ReplaceWith(GetGraph()->GetIntConstant(1)); 2126 instruction->GetBlock()->RemoveInstruction(instruction); 2127 } else { 2128 StringEqualsOptimizations optimizations(instruction); 2129 if (CanEnsureNotNullAt(argument, instruction)) { 2130 optimizations.SetArgumentNotNull(); 2131 } 2132 ScopedObjectAccess soa(Thread::Current()); 2133 ReferenceTypeInfo argument_rti = argument->GetReferenceTypeInfo(); 2134 if (argument_rti.IsValid() && argument_rti.IsStringClass()) { 2135 optimizations.SetArgumentIsString(); 2136 } 2137 } 2138 } 2139 2140 void InstructionSimplifierVisitor::SimplifyRotate(HInvoke* invoke, 2141 bool is_left, 2142 DataType::Type type) { 2143 DCHECK(invoke->IsInvokeStaticOrDirect()); 2144 DCHECK_EQ(invoke->GetInvokeType(), InvokeType::kStatic); 2145 HInstruction* value = invoke->InputAt(0); 2146 HInstruction* distance = invoke->InputAt(1); 2147 // Replace the invoke with an HRor. 2148 if (is_left) { 2149 // Unconditionally set the type of the negated distance to `int`, 2150 // as shift and rotate operations expect a 32-bit (or narrower) 2151 // value for their distance input. 2152 distance = new (GetGraph()->GetAllocator()) HNeg(DataType::Type::kInt32, distance); 2153 invoke->GetBlock()->InsertInstructionBefore(distance, invoke); 2154 } 2155 HRor* ror = new (GetGraph()->GetAllocator()) HRor(type, value, distance); 2156 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, ror); 2157 // Remove ClinitCheck and LoadClass, if possible. 2158 HInstruction* clinit = invoke->GetInputs().back(); 2159 if (clinit->IsClinitCheck() && !clinit->HasUses()) { 2160 clinit->GetBlock()->RemoveInstruction(clinit); 2161 HInstruction* ldclass = clinit->InputAt(0); 2162 if (ldclass->IsLoadClass() && !ldclass->HasUses()) { 2163 ldclass->GetBlock()->RemoveInstruction(ldclass); 2164 } 2165 } 2166 } 2167 2168 static bool IsArrayLengthOf(HInstruction* potential_length, HInstruction* potential_array) { 2169 if (potential_length->IsArrayLength()) { 2170 return potential_length->InputAt(0) == potential_array; 2171 } 2172 2173 if (potential_array->IsNewArray()) { 2174 return potential_array->AsNewArray()->GetLength() == potential_length; 2175 } 2176 2177 return false; 2178 } 2179 2180 void InstructionSimplifierVisitor::SimplifySystemArrayCopy(HInvoke* instruction) { 2181 HInstruction* source = instruction->InputAt(0); 2182 HInstruction* destination = instruction->InputAt(2); 2183 HInstruction* count = instruction->InputAt(4); 2184 SystemArrayCopyOptimizations optimizations(instruction); 2185 if (CanEnsureNotNullAt(source, instruction)) { 2186 optimizations.SetSourceIsNotNull(); 2187 } 2188 if (CanEnsureNotNullAt(destination, instruction)) { 2189 optimizations.SetDestinationIsNotNull(); 2190 } 2191 if (destination == source) { 2192 optimizations.SetDestinationIsSource(); 2193 } 2194 2195 if (IsArrayLengthOf(count, source)) { 2196 optimizations.SetCountIsSourceLength(); 2197 } 2198 2199 if (IsArrayLengthOf(count, destination)) { 2200 optimizations.SetCountIsDestinationLength(); 2201 } 2202 2203 { 2204 ScopedObjectAccess soa(Thread::Current()); 2205 DataType::Type source_component_type = DataType::Type::kVoid; 2206 DataType::Type destination_component_type = DataType::Type::kVoid; 2207 ReferenceTypeInfo destination_rti = destination->GetReferenceTypeInfo(); 2208 if (destination_rti.IsValid()) { 2209 if (destination_rti.IsObjectArray()) { 2210 if (destination_rti.IsExact()) { 2211 optimizations.SetDoesNotNeedTypeCheck(); 2212 } 2213 optimizations.SetDestinationIsTypedObjectArray(); 2214 } 2215 if (destination_rti.IsPrimitiveArrayClass()) { 2216 destination_component_type = DataTypeFromPrimitive( 2217 destination_rti.GetTypeHandle()->GetComponentType()->GetPrimitiveType()); 2218 optimizations.SetDestinationIsPrimitiveArray(); 2219 } else if (destination_rti.IsNonPrimitiveArrayClass()) { 2220 optimizations.SetDestinationIsNonPrimitiveArray(); 2221 } 2222 } 2223 ReferenceTypeInfo source_rti = source->GetReferenceTypeInfo(); 2224 if (source_rti.IsValid()) { 2225 if (destination_rti.IsValid() && destination_rti.CanArrayHoldValuesOf(source_rti)) { 2226 optimizations.SetDoesNotNeedTypeCheck(); 2227 } 2228 if (source_rti.IsPrimitiveArrayClass()) { 2229 optimizations.SetSourceIsPrimitiveArray(); 2230 source_component_type = DataTypeFromPrimitive( 2231 source_rti.GetTypeHandle()->GetComponentType()->GetPrimitiveType()); 2232 } else if (source_rti.IsNonPrimitiveArrayClass()) { 2233 optimizations.SetSourceIsNonPrimitiveArray(); 2234 } 2235 } 2236 // For primitive arrays, use their optimized ArtMethod implementations. 2237 if ((source_component_type != DataType::Type::kVoid) && 2238 (source_component_type == destination_component_type)) { 2239 ClassLinker* class_linker = Runtime::Current()->GetClassLinker(); 2240 PointerSize image_size = class_linker->GetImagePointerSize(); 2241 HInvokeStaticOrDirect* invoke = instruction->AsInvokeStaticOrDirect(); 2242 ObjPtr<mirror::Class> system = invoke->GetResolvedMethod()->GetDeclaringClass(); 2243 ArtMethod* method = nullptr; 2244 switch (source_component_type) { 2245 case DataType::Type::kBool: 2246 method = system->FindClassMethod("arraycopy", "([ZI[ZII)V", image_size); 2247 break; 2248 case DataType::Type::kInt8: 2249 method = system->FindClassMethod("arraycopy", "([BI[BII)V", image_size); 2250 break; 2251 case DataType::Type::kUint16: 2252 method = system->FindClassMethod("arraycopy", "([CI[CII)V", image_size); 2253 break; 2254 case DataType::Type::kInt16: 2255 method = system->FindClassMethod("arraycopy", "([SI[SII)V", image_size); 2256 break; 2257 case DataType::Type::kInt32: 2258 method = system->FindClassMethod("arraycopy", "([II[III)V", image_size); 2259 break; 2260 case DataType::Type::kFloat32: 2261 method = system->FindClassMethod("arraycopy", "([FI[FII)V", image_size); 2262 break; 2263 case DataType::Type::kInt64: 2264 method = system->FindClassMethod("arraycopy", "([JI[JII)V", image_size); 2265 break; 2266 case DataType::Type::kFloat64: 2267 method = system->FindClassMethod("arraycopy", "([DI[DII)V", image_size); 2268 break; 2269 default: 2270 LOG(FATAL) << "Unreachable"; 2271 } 2272 DCHECK(method != nullptr); 2273 DCHECK(method->IsStatic()); 2274 DCHECK(method->GetDeclaringClass() == system); 2275 invoke->SetResolvedMethod(method); 2276 // Sharpen the new invoke. Note that we do not update the dex method index of 2277 // the invoke, as we would need to look it up in the current dex file, and it 2278 // is unlikely that it exists. The most usual situation for such typed 2279 // arraycopy methods is a direct pointer to the boot image. 2280 invoke->SetDispatchInfo(HSharpening::SharpenInvokeStaticOrDirect(method, codegen_)); 2281 } 2282 } 2283 } 2284 2285 void InstructionSimplifierVisitor::SimplifyCompare(HInvoke* invoke, 2286 bool is_signum, 2287 DataType::Type type) { 2288 DCHECK(invoke->IsInvokeStaticOrDirect()); 2289 uint32_t dex_pc = invoke->GetDexPc(); 2290 HInstruction* left = invoke->InputAt(0); 2291 HInstruction* right; 2292 if (!is_signum) { 2293 right = invoke->InputAt(1); 2294 } else if (type == DataType::Type::kInt64) { 2295 right = GetGraph()->GetLongConstant(0); 2296 } else { 2297 right = GetGraph()->GetIntConstant(0); 2298 } 2299 HCompare* compare = new (GetGraph()->GetAllocator()) 2300 HCompare(type, left, right, ComparisonBias::kNoBias, dex_pc); 2301 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, compare); 2302 } 2303 2304 void InstructionSimplifierVisitor::SimplifyIsNaN(HInvoke* invoke) { 2305 DCHECK(invoke->IsInvokeStaticOrDirect()); 2306 uint32_t dex_pc = invoke->GetDexPc(); 2307 // IsNaN(x) is the same as x != x. 2308 HInstruction* x = invoke->InputAt(0); 2309 HCondition* condition = new (GetGraph()->GetAllocator()) HNotEqual(x, x, dex_pc); 2310 condition->SetBias(ComparisonBias::kLtBias); 2311 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, condition); 2312 } 2313 2314 void InstructionSimplifierVisitor::SimplifyFP2Int(HInvoke* invoke) { 2315 DCHECK(invoke->IsInvokeStaticOrDirect()); 2316 uint32_t dex_pc = invoke->GetDexPc(); 2317 HInstruction* x = invoke->InputAt(0); 2318 DataType::Type type = x->GetType(); 2319 // Set proper bit pattern for NaN and replace intrinsic with raw version. 2320 HInstruction* nan; 2321 if (type == DataType::Type::kFloat64) { 2322 nan = GetGraph()->GetLongConstant(0x7ff8000000000000L); 2323 invoke->SetIntrinsic(Intrinsics::kDoubleDoubleToRawLongBits, 2324 kNeedsEnvironmentOrCache, 2325 kNoSideEffects, 2326 kNoThrow); 2327 } else { 2328 DCHECK_EQ(type, DataType::Type::kFloat32); 2329 nan = GetGraph()->GetIntConstant(0x7fc00000); 2330 invoke->SetIntrinsic(Intrinsics::kFloatFloatToRawIntBits, 2331 kNeedsEnvironmentOrCache, 2332 kNoSideEffects, 2333 kNoThrow); 2334 } 2335 // Test IsNaN(x), which is the same as x != x. 2336 HCondition* condition = new (GetGraph()->GetAllocator()) HNotEqual(x, x, dex_pc); 2337 condition->SetBias(ComparisonBias::kLtBias); 2338 invoke->GetBlock()->InsertInstructionBefore(condition, invoke->GetNext()); 2339 // Select between the two. 2340 HInstruction* select = new (GetGraph()->GetAllocator()) HSelect(condition, nan, invoke, dex_pc); 2341 invoke->GetBlock()->InsertInstructionBefore(select, condition->GetNext()); 2342 invoke->ReplaceWithExceptInReplacementAtIndex(select, 0); // false at index 0 2343 } 2344 2345 void InstructionSimplifierVisitor::SimplifyStringCharAt(HInvoke* invoke) { 2346 HInstruction* str = invoke->InputAt(0); 2347 HInstruction* index = invoke->InputAt(1); 2348 uint32_t dex_pc = invoke->GetDexPc(); 2349 ArenaAllocator* allocator = GetGraph()->GetAllocator(); 2350 // We treat String as an array to allow DCE and BCE to seamlessly work on strings, 2351 // so create the HArrayLength, HBoundsCheck and HArrayGet. 2352 HArrayLength* length = new (allocator) HArrayLength(str, dex_pc, /* is_string_length= */ true); 2353 invoke->GetBlock()->InsertInstructionBefore(length, invoke); 2354 HBoundsCheck* bounds_check = new (allocator) HBoundsCheck( 2355 index, length, dex_pc, /* is_string_char_at= */ true); 2356 invoke->GetBlock()->InsertInstructionBefore(bounds_check, invoke); 2357 HArrayGet* array_get = new (allocator) HArrayGet(str, 2358 bounds_check, 2359 DataType::Type::kUint16, 2360 SideEffects::None(), // Strings are immutable. 2361 dex_pc, 2362 /* is_string_char_at= */ true); 2363 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, array_get); 2364 bounds_check->CopyEnvironmentFrom(invoke->GetEnvironment()); 2365 GetGraph()->SetHasBoundsChecks(true); 2366 } 2367 2368 void InstructionSimplifierVisitor::SimplifyStringIsEmptyOrLength(HInvoke* invoke) { 2369 HInstruction* str = invoke->InputAt(0); 2370 uint32_t dex_pc = invoke->GetDexPc(); 2371 // We treat String as an array to allow DCE and BCE to seamlessly work on strings, 2372 // so create the HArrayLength. 2373 HArrayLength* length = 2374 new (GetGraph()->GetAllocator()) HArrayLength(str, dex_pc, /* is_string_length= */ true); 2375 HInstruction* replacement; 2376 if (invoke->GetIntrinsic() == Intrinsics::kStringIsEmpty) { 2377 // For String.isEmpty(), create the `HEqual` representing the `length == 0`. 2378 invoke->GetBlock()->InsertInstructionBefore(length, invoke); 2379 HIntConstant* zero = GetGraph()->GetIntConstant(0); 2380 HEqual* equal = new (GetGraph()->GetAllocator()) HEqual(length, zero, dex_pc); 2381 replacement = equal; 2382 } else { 2383 DCHECK_EQ(invoke->GetIntrinsic(), Intrinsics::kStringLength); 2384 replacement = length; 2385 } 2386 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, replacement); 2387 } 2388 2389 void InstructionSimplifierVisitor::SimplifyStringIndexOf(HInvoke* invoke) { 2390 DCHECK(invoke->GetIntrinsic() == Intrinsics::kStringIndexOf || 2391 invoke->GetIntrinsic() == Intrinsics::kStringIndexOfAfter); 2392 if (invoke->InputAt(0)->IsLoadString()) { 2393 HLoadString* load_string = invoke->InputAt(0)->AsLoadString(); 2394 const DexFile& dex_file = load_string->GetDexFile(); 2395 uint32_t utf16_length; 2396 const char* data = 2397 dex_file.StringDataAndUtf16LengthByIdx(load_string->GetStringIndex(), &utf16_length); 2398 if (utf16_length == 0) { 2399 invoke->ReplaceWith(GetGraph()->GetIntConstant(-1)); 2400 invoke->GetBlock()->RemoveInstruction(invoke); 2401 RecordSimplification(); 2402 return; 2403 } 2404 if (utf16_length == 1 && invoke->GetIntrinsic() == Intrinsics::kStringIndexOf) { 2405 // Simplify to HSelect(HEquals(., load_string.charAt(0)), 0, -1). 2406 // If the sought character is supplementary, this gives the correct result, i.e. -1. 2407 uint32_t c = GetUtf16FromUtf8(&data); 2408 DCHECK_EQ(GetTrailingUtf16Char(c), 0u); 2409 DCHECK_EQ(GetLeadingUtf16Char(c), c); 2410 uint32_t dex_pc = invoke->GetDexPc(); 2411 ArenaAllocator* allocator = GetGraph()->GetAllocator(); 2412 HEqual* equal = 2413 new (allocator) HEqual(invoke->InputAt(1), GetGraph()->GetIntConstant(c), dex_pc); 2414 invoke->GetBlock()->InsertInstructionBefore(equal, invoke); 2415 HSelect* result = new (allocator) HSelect(equal, 2416 GetGraph()->GetIntConstant(0), 2417 GetGraph()->GetIntConstant(-1), 2418 dex_pc); 2419 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, result); 2420 RecordSimplification(); 2421 return; 2422 } 2423 } 2424 } 2425 2426 // This method should only be used on intrinsics whose sole way of throwing an 2427 // exception is raising a NPE when the nth argument is null. If that argument 2428 // is provably non-null, we can clear the flag. 2429 void InstructionSimplifierVisitor::SimplifyNPEOnArgN(HInvoke* invoke, size_t n) { 2430 HInstruction* arg = invoke->InputAt(n); 2431 if (invoke->CanThrow() && !arg->CanBeNull()) { 2432 invoke->SetCanThrow(false); 2433 } 2434 } 2435 2436 // Methods that return "this" can replace the returned value with the receiver. 2437 void InstructionSimplifierVisitor::SimplifyReturnThis(HInvoke* invoke) { 2438 if (invoke->HasUses()) { 2439 HInstruction* receiver = invoke->InputAt(0); 2440 invoke->ReplaceWith(receiver); 2441 RecordSimplification(); 2442 } 2443 } 2444 2445 // Helper method for StringBuffer escape analysis. 2446 static bool NoEscapeForStringBufferReference(HInstruction* reference, HInstruction* user) { 2447 if (user->IsInvokeStaticOrDirect()) { 2448 // Any constructor on StringBuffer is okay. 2449 return user->AsInvokeStaticOrDirect()->GetResolvedMethod() != nullptr && 2450 user->AsInvokeStaticOrDirect()->GetResolvedMethod()->IsConstructor() && 2451 user->InputAt(0) == reference; 2452 } else if (user->IsInvokeVirtual()) { 2453 switch (user->AsInvokeVirtual()->GetIntrinsic()) { 2454 case Intrinsics::kStringBufferLength: 2455 case Intrinsics::kStringBufferToString: 2456 DCHECK_EQ(user->InputAt(0), reference); 2457 return true; 2458 case Intrinsics::kStringBufferAppend: 2459 // Returns "this", so only okay if no further uses. 2460 DCHECK_EQ(user->InputAt(0), reference); 2461 DCHECK_NE(user->InputAt(1), reference); 2462 return !user->HasUses(); 2463 default: 2464 break; 2465 } 2466 } 2467 return false; 2468 } 2469 2470 // Certain allocation intrinsics are not removed by dead code elimination 2471 // because of potentially throwing an OOM exception or other side effects. 2472 // This method removes such intrinsics when special circumstances allow. 2473 void InstructionSimplifierVisitor::SimplifyAllocationIntrinsic(HInvoke* invoke) { 2474 if (!invoke->HasUses()) { 2475 // Instruction has no uses. If unsynchronized, we can remove right away, safely ignoring 2476 // the potential OOM of course. Otherwise, we must ensure the receiver object of this 2477 // call does not escape since only thread-local synchronization may be removed. 2478 bool is_synchronized = invoke->GetIntrinsic() == Intrinsics::kStringBufferToString; 2479 HInstruction* receiver = invoke->InputAt(0); 2480 if (!is_synchronized || DoesNotEscape(receiver, NoEscapeForStringBufferReference)) { 2481 invoke->GetBlock()->RemoveInstruction(invoke); 2482 RecordSimplification(); 2483 } 2484 } 2485 } 2486 2487 void InstructionSimplifierVisitor::SimplifyMemBarrier(HInvoke* invoke, 2488 MemBarrierKind barrier_kind) { 2489 uint32_t dex_pc = invoke->GetDexPc(); 2490 HMemoryBarrier* mem_barrier = 2491 new (GetGraph()->GetAllocator()) HMemoryBarrier(barrier_kind, dex_pc); 2492 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, mem_barrier); 2493 } 2494 2495 void InstructionSimplifierVisitor::SimplifyMin(HInvoke* invoke, DataType::Type type) { 2496 DCHECK(invoke->IsInvokeStaticOrDirect()); 2497 HMin* min = new (GetGraph()->GetAllocator()) 2498 HMin(type, invoke->InputAt(0), invoke->InputAt(1), invoke->GetDexPc()); 2499 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, min); 2500 } 2501 2502 void InstructionSimplifierVisitor::SimplifyMax(HInvoke* invoke, DataType::Type type) { 2503 DCHECK(invoke->IsInvokeStaticOrDirect()); 2504 HMax* max = new (GetGraph()->GetAllocator()) 2505 HMax(type, invoke->InputAt(0), invoke->InputAt(1), invoke->GetDexPc()); 2506 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, max); 2507 } 2508 2509 void InstructionSimplifierVisitor::SimplifyAbs(HInvoke* invoke, DataType::Type type) { 2510 DCHECK(invoke->IsInvokeStaticOrDirect()); 2511 HAbs* abs = new (GetGraph()->GetAllocator()) 2512 HAbs(type, invoke->InputAt(0), invoke->GetDexPc()); 2513 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, abs); 2514 } 2515 2516 void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) { 2517 switch (instruction->GetIntrinsic()) { 2518 case Intrinsics::kStringEquals: 2519 SimplifyStringEquals(instruction); 2520 break; 2521 case Intrinsics::kSystemArrayCopy: 2522 SimplifySystemArrayCopy(instruction); 2523 break; 2524 case Intrinsics::kIntegerRotateRight: 2525 SimplifyRotate(instruction, /* is_left= */ false, DataType::Type::kInt32); 2526 break; 2527 case Intrinsics::kLongRotateRight: 2528 SimplifyRotate(instruction, /* is_left= */ false, DataType::Type::kInt64); 2529 break; 2530 case Intrinsics::kIntegerRotateLeft: 2531 SimplifyRotate(instruction, /* is_left= */ true, DataType::Type::kInt32); 2532 break; 2533 case Intrinsics::kLongRotateLeft: 2534 SimplifyRotate(instruction, /* is_left= */ true, DataType::Type::kInt64); 2535 break; 2536 case Intrinsics::kIntegerCompare: 2537 SimplifyCompare(instruction, /* is_signum= */ false, DataType::Type::kInt32); 2538 break; 2539 case Intrinsics::kLongCompare: 2540 SimplifyCompare(instruction, /* is_signum= */ false, DataType::Type::kInt64); 2541 break; 2542 case Intrinsics::kIntegerSignum: 2543 SimplifyCompare(instruction, /* is_signum= */ true, DataType::Type::kInt32); 2544 break; 2545 case Intrinsics::kLongSignum: 2546 SimplifyCompare(instruction, /* is_signum= */ true, DataType::Type::kInt64); 2547 break; 2548 case Intrinsics::kFloatIsNaN: 2549 case Intrinsics::kDoubleIsNaN: 2550 SimplifyIsNaN(instruction); 2551 break; 2552 case Intrinsics::kFloatFloatToIntBits: 2553 case Intrinsics::kDoubleDoubleToLongBits: 2554 SimplifyFP2Int(instruction); 2555 break; 2556 case Intrinsics::kStringCharAt: 2557 SimplifyStringCharAt(instruction); 2558 break; 2559 case Intrinsics::kStringIsEmpty: 2560 case Intrinsics::kStringLength: 2561 SimplifyStringIsEmptyOrLength(instruction); 2562 break; 2563 case Intrinsics::kStringIndexOf: 2564 case Intrinsics::kStringIndexOfAfter: 2565 SimplifyStringIndexOf(instruction); 2566 break; 2567 case Intrinsics::kStringStringIndexOf: 2568 case Intrinsics::kStringStringIndexOfAfter: 2569 SimplifyNPEOnArgN(instruction, 1); // 0th has own NullCheck 2570 break; 2571 case Intrinsics::kStringBufferAppend: 2572 case Intrinsics::kStringBuilderAppend: 2573 SimplifyReturnThis(instruction); 2574 break; 2575 case Intrinsics::kStringBufferToString: 2576 case Intrinsics::kStringBuilderToString: 2577 SimplifyAllocationIntrinsic(instruction); 2578 break; 2579 case Intrinsics::kUnsafeLoadFence: 2580 SimplifyMemBarrier(instruction, MemBarrierKind::kLoadAny); 2581 break; 2582 case Intrinsics::kUnsafeStoreFence: 2583 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyStore); 2584 break; 2585 case Intrinsics::kUnsafeFullFence: 2586 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyAny); 2587 break; 2588 case Intrinsics::kVarHandleFullFence: 2589 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyAny); 2590 break; 2591 case Intrinsics::kVarHandleAcquireFence: 2592 SimplifyMemBarrier(instruction, MemBarrierKind::kLoadAny); 2593 break; 2594 case Intrinsics::kVarHandleReleaseFence: 2595 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyStore); 2596 break; 2597 case Intrinsics::kVarHandleLoadLoadFence: 2598 SimplifyMemBarrier(instruction, MemBarrierKind::kLoadAny); 2599 break; 2600 case Intrinsics::kVarHandleStoreStoreFence: 2601 SimplifyMemBarrier(instruction, MemBarrierKind::kStoreStore); 2602 break; 2603 case Intrinsics::kMathMinIntInt: 2604 SimplifyMin(instruction, DataType::Type::kInt32); 2605 break; 2606 case Intrinsics::kMathMinLongLong: 2607 SimplifyMin(instruction, DataType::Type::kInt64); 2608 break; 2609 case Intrinsics::kMathMinFloatFloat: 2610 SimplifyMin(instruction, DataType::Type::kFloat32); 2611 break; 2612 case Intrinsics::kMathMinDoubleDouble: 2613 SimplifyMin(instruction, DataType::Type::kFloat64); 2614 break; 2615 case Intrinsics::kMathMaxIntInt: 2616 SimplifyMax(instruction, DataType::Type::kInt32); 2617 break; 2618 case Intrinsics::kMathMaxLongLong: 2619 SimplifyMax(instruction, DataType::Type::kInt64); 2620 break; 2621 case Intrinsics::kMathMaxFloatFloat: 2622 SimplifyMax(instruction, DataType::Type::kFloat32); 2623 break; 2624 case Intrinsics::kMathMaxDoubleDouble: 2625 SimplifyMax(instruction, DataType::Type::kFloat64); 2626 break; 2627 case Intrinsics::kMathAbsInt: 2628 SimplifyAbs(instruction, DataType::Type::kInt32); 2629 break; 2630 case Intrinsics::kMathAbsLong: 2631 SimplifyAbs(instruction, DataType::Type::kInt64); 2632 break; 2633 case Intrinsics::kMathAbsFloat: 2634 SimplifyAbs(instruction, DataType::Type::kFloat32); 2635 break; 2636 case Intrinsics::kMathAbsDouble: 2637 SimplifyAbs(instruction, DataType::Type::kFloat64); 2638 break; 2639 default: 2640 break; 2641 } 2642 } 2643 2644 void InstructionSimplifierVisitor::VisitDeoptimize(HDeoptimize* deoptimize) { 2645 HInstruction* cond = deoptimize->InputAt(0); 2646 if (cond->IsConstant()) { 2647 if (cond->AsIntConstant()->IsFalse()) { 2648 // Never deopt: instruction can be removed. 2649 if (deoptimize->GuardsAnInput()) { 2650 deoptimize->ReplaceWith(deoptimize->GuardedInput()); 2651 } 2652 deoptimize->GetBlock()->RemoveInstruction(deoptimize); 2653 } else { 2654 // Always deopt. 2655 } 2656 } 2657 } 2658 2659 // Replace code looking like 2660 // OP y, x, const1 2661 // OP z, y, const2 2662 // with 2663 // OP z, x, const3 2664 // where OP is both an associative and a commutative operation. 2665 bool InstructionSimplifierVisitor::TryHandleAssociativeAndCommutativeOperation( 2666 HBinaryOperation* instruction) { 2667 DCHECK(instruction->IsCommutative()); 2668 2669 if (!DataType::IsIntegralType(instruction->GetType())) { 2670 return false; 2671 } 2672 2673 HInstruction* left = instruction->GetLeft(); 2674 HInstruction* right = instruction->GetRight(); 2675 // Variable names as described above. 2676 HConstant* const2; 2677 HBinaryOperation* y; 2678 2679 if (instruction->GetKind() == left->GetKind() && right->IsConstant()) { 2680 const2 = right->AsConstant(); 2681 y = left->AsBinaryOperation(); 2682 } else if (left->IsConstant() && instruction->GetKind() == right->GetKind()) { 2683 const2 = left->AsConstant(); 2684 y = right->AsBinaryOperation(); 2685 } else { 2686 // The node does not match the pattern. 2687 return false; 2688 } 2689 2690 // If `y` has more than one use, we do not perform the optimization 2691 // because it might increase code size (e.g. if the new constant is 2692 // no longer encodable as an immediate operand in the target ISA). 2693 if (!y->HasOnlyOneNonEnvironmentUse()) { 2694 return false; 2695 } 2696 2697 // GetConstantRight() can return both left and right constants 2698 // for commutative operations. 2699 HConstant* const1 = y->GetConstantRight(); 2700 if (const1 == nullptr) { 2701 return false; 2702 } 2703 2704 instruction->ReplaceInput(const1, 0); 2705 instruction->ReplaceInput(const2, 1); 2706 HConstant* const3 = instruction->TryStaticEvaluation(); 2707 DCHECK(const3 != nullptr); 2708 instruction->ReplaceInput(y->GetLeastConstantLeft(), 0); 2709 instruction->ReplaceInput(const3, 1); 2710 RecordSimplification(); 2711 return true; 2712 } 2713 2714 static HBinaryOperation* AsAddOrSub(HInstruction* binop) { 2715 return (binop->IsAdd() || binop->IsSub()) ? binop->AsBinaryOperation() : nullptr; 2716 } 2717 2718 // Helper function that performs addition statically, considering the result type. 2719 static int64_t ComputeAddition(DataType::Type type, int64_t x, int64_t y) { 2720 // Use the Compute() method for consistency with TryStaticEvaluation(). 2721 if (type == DataType::Type::kInt32) { 2722 return HAdd::Compute<int32_t>(x, y); 2723 } else { 2724 DCHECK_EQ(type, DataType::Type::kInt64); 2725 return HAdd::Compute<int64_t>(x, y); 2726 } 2727 } 2728 2729 // Helper function that handles the child classes of HConstant 2730 // and returns an integer with the appropriate sign. 2731 static int64_t GetValue(HConstant* constant, bool is_negated) { 2732 int64_t ret = Int64FromConstant(constant); 2733 return is_negated ? -ret : ret; 2734 } 2735 2736 // Replace code looking like 2737 // OP1 y, x, const1 2738 // OP2 z, y, const2 2739 // with 2740 // OP3 z, x, const3 2741 // where OPx is either ADD or SUB, and at least one of OP{1,2} is SUB. 2742 bool InstructionSimplifierVisitor::TrySubtractionChainSimplification( 2743 HBinaryOperation* instruction) { 2744 DCHECK(instruction->IsAdd() || instruction->IsSub()) << instruction->DebugName(); 2745 2746 DataType::Type type = instruction->GetType(); 2747 if (!DataType::IsIntegralType(type)) { 2748 return false; 2749 } 2750 2751 HInstruction* left = instruction->GetLeft(); 2752 HInstruction* right = instruction->GetRight(); 2753 // Variable names as described above. 2754 HConstant* const2 = right->IsConstant() ? right->AsConstant() : left->AsConstant(); 2755 if (const2 == nullptr) { 2756 return false; 2757 } 2758 2759 HBinaryOperation* y = (AsAddOrSub(left) != nullptr) 2760 ? left->AsBinaryOperation() 2761 : AsAddOrSub(right); 2762 // If y has more than one use, we do not perform the optimization because 2763 // it might increase code size (e.g. if the new constant is no longer 2764 // encodable as an immediate operand in the target ISA). 2765 if ((y == nullptr) || !y->HasOnlyOneNonEnvironmentUse()) { 2766 return false; 2767 } 2768 2769 left = y->GetLeft(); 2770 HConstant* const1 = left->IsConstant() ? left->AsConstant() : y->GetRight()->AsConstant(); 2771 if (const1 == nullptr) { 2772 return false; 2773 } 2774 2775 HInstruction* x = (const1 == left) ? y->GetRight() : left; 2776 // If both inputs are constants, let the constant folding pass deal with it. 2777 if (x->IsConstant()) { 2778 return false; 2779 } 2780 2781 bool is_const2_negated = (const2 == right) && instruction->IsSub(); 2782 int64_t const2_val = GetValue(const2, is_const2_negated); 2783 bool is_y_negated = (y == right) && instruction->IsSub(); 2784 right = y->GetRight(); 2785 bool is_const1_negated = is_y_negated ^ ((const1 == right) && y->IsSub()); 2786 int64_t const1_val = GetValue(const1, is_const1_negated); 2787 bool is_x_negated = is_y_negated ^ ((x == right) && y->IsSub()); 2788 int64_t const3_val = ComputeAddition(type, const1_val, const2_val); 2789 HBasicBlock* block = instruction->GetBlock(); 2790 HConstant* const3 = block->GetGraph()->GetConstant(type, const3_val); 2791 ArenaAllocator* allocator = instruction->GetAllocator(); 2792 HInstruction* z; 2793 2794 if (is_x_negated) { 2795 z = new (allocator) HSub(type, const3, x, instruction->GetDexPc()); 2796 } else { 2797 z = new (allocator) HAdd(type, x, const3, instruction->GetDexPc()); 2798 } 2799 2800 block->ReplaceAndRemoveInstructionWith(instruction, z); 2801 RecordSimplification(); 2802 return true; 2803 } 2804 2805 void InstructionSimplifierVisitor::VisitVecMul(HVecMul* instruction) { 2806 if (TryCombineVecMultiplyAccumulate(instruction)) { 2807 RecordSimplification(); 2808 } 2809 } 2810 2811 } // namespace art 2812