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-inl.h"
22 #include "data_type-inl.h"
23 #include "driver/compiler_options.h"
24 #include "escape.h"
25 #include "intrinsic_objects.h"
26 #include "intrinsics.h"
27 #include "intrinsics_utils.h"
28 #include "mirror/class-inl.h"
29 #include "optimizing/data_type.h"
30 #include "optimizing/nodes.h"
31 #include "scoped_thread_state_change-inl.h"
32 #include "sharpening.h"
33 #include "string_builder_append.h"
34 #include "well_known_classes.h"
35
36 namespace art HIDDEN {
37
38 // Whether to run an exhaustive test of individual HInstructions cloning when each instruction
39 // is replaced with its copy if it is clonable.
40 static constexpr bool kTestInstructionClonerExhaustively = false;
41
42 class InstructionSimplifierVisitor final : public HGraphDelegateVisitor {
43 public:
InstructionSimplifierVisitor(HGraph * graph,CodeGenerator * codegen,OptimizingCompilerStats * stats,bool be_loop_friendly)44 InstructionSimplifierVisitor(HGraph* graph,
45 CodeGenerator* codegen,
46 OptimizingCompilerStats* stats,
47 bool be_loop_friendly)
48 : HGraphDelegateVisitor(graph),
49 codegen_(codegen),
50 stats_(stats),
51 be_loop_friendly_(be_loop_friendly) {}
52
53 bool Run();
54
55 private:
RecordSimplification()56 void RecordSimplification() {
57 simplification_occurred_ = true;
58 simplifications_at_current_position_++;
59 MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSimplifications);
60 }
61
62 bool ReplaceRotateWithRor(HBinaryOperation* op, HUShr* ushr, HShl* shl);
63 bool TryReplaceWithRotate(HBinaryOperation* instruction);
64 bool TryReplaceWithRotateConstantPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
65 bool TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
66 bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
67
68 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
69 // `op` should be either HOr or HAnd.
70 // De Morgan's laws:
71 // ~a & ~b = ~(a | b) and ~a | ~b = ~(a & b)
72 bool TryDeMorganNegationFactoring(HBinaryOperation* op);
73 bool TryHandleAssociativeAndCommutativeOperation(HBinaryOperation* instruction);
74 bool TrySubtractionChainSimplification(HBinaryOperation* instruction);
75 bool TryCombineVecMultiplyAccumulate(HVecMul* mul);
76 void TryToReuseDiv(HRem* rem);
77
78 void VisitShift(HBinaryOperation* shift);
79 void VisitEqual(HEqual* equal) override;
80 void VisitNotEqual(HNotEqual* equal) override;
81 void VisitBooleanNot(HBooleanNot* bool_not) override;
82 void VisitInstanceFieldSet(HInstanceFieldSet* equal) override;
83 void VisitStaticFieldSet(HStaticFieldSet* equal) override;
84 void VisitArraySet(HArraySet* equal) override;
85 void VisitTypeConversion(HTypeConversion* instruction) override;
86 void VisitNullCheck(HNullCheck* instruction) override;
87 void VisitArrayLength(HArrayLength* instruction) override;
88 void VisitCheckCast(HCheckCast* instruction) override;
89 void VisitAbs(HAbs* instruction) override;
90 void VisitAdd(HAdd* instruction) override;
91 void VisitAnd(HAnd* instruction) override;
92 void VisitCondition(HCondition* instruction) override;
93 void VisitGreaterThan(HGreaterThan* condition) override;
94 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) override;
95 void VisitLessThan(HLessThan* condition) override;
96 void VisitLessThanOrEqual(HLessThanOrEqual* condition) override;
97 void VisitBelow(HBelow* condition) override;
98 void VisitBelowOrEqual(HBelowOrEqual* condition) override;
99 void VisitAbove(HAbove* condition) override;
100 void VisitAboveOrEqual(HAboveOrEqual* condition) override;
101 void VisitDiv(HDiv* instruction) override;
102 void VisitRem(HRem* instruction) override;
103 void VisitMul(HMul* instruction) override;
104 void VisitNeg(HNeg* instruction) override;
105 void VisitNot(HNot* instruction) override;
106 void VisitOr(HOr* instruction) override;
107 void VisitShl(HShl* instruction) override;
108 void VisitShr(HShr* instruction) override;
109 void VisitSub(HSub* instruction) override;
110 void VisitUShr(HUShr* instruction) override;
111 void VisitXor(HXor* instruction) override;
112 void VisitSelect(HSelect* select) override;
113 void VisitIf(HIf* instruction) override;
114 void VisitInstanceOf(HInstanceOf* instruction) override;
115 void VisitInvoke(HInvoke* invoke) override;
116 void VisitDeoptimize(HDeoptimize* deoptimize) override;
117 void VisitVecMul(HVecMul* instruction) override;
118 void SimplifyBoxUnbox(HInvoke* instruction, ArtField* field, DataType::Type type);
119 void SimplifySystemArrayCopy(HInvoke* invoke);
120 void SimplifyStringEquals(HInvoke* invoke);
121 void SimplifyFP2Int(HInvoke* invoke);
122 void SimplifyStringCharAt(HInvoke* invoke);
123 void SimplifyStringLength(HInvoke* invoke);
124 void SimplifyStringIndexOf(HInvoke* invoke);
125 void SimplifyNPEOnArgN(HInvoke* invoke, size_t);
126 void SimplifyReturnThis(HInvoke* invoke);
127 void SimplifyAllocationIntrinsic(HInvoke* invoke);
128 void SimplifyVarHandleIntrinsic(HInvoke* invoke);
129
130 bool CanUseKnownImageVarHandle(HInvoke* invoke);
131 static bool CanEnsureNotNullAt(HInstruction* input, HInstruction* at);
132
133 CodeGenerator* codegen_;
134 OptimizingCompilerStats* stats_;
135 bool simplification_occurred_ = false;
136 int simplifications_at_current_position_ = 0;
137 // Prohibit optimizations which can affect HInductionVarAnalysis/HLoopOptimization
138 // and prevent loop optimizations:
139 // true - avoid such optimizations.
140 // false - allow such optimizations.
141 // Checked by the following optimizations:
142 // - TryToReuseDiv: simplification of Div+Rem into Div+Mul+Sub.
143 bool be_loop_friendly_;
144 // We ensure we do not loop infinitely. The value should not be too high, since that
145 // would allow looping around the same basic block too many times. The value should
146 // not be too low either, however, since we want to allow revisiting a basic block
147 // with many statements and simplifications at least once.
148 static constexpr int kMaxSamePositionSimplifications = 50;
149 };
150
Run()151 bool InstructionSimplifier::Run() {
152 if (kTestInstructionClonerExhaustively) {
153 CloneAndReplaceInstructionVisitor visitor(graph_);
154 visitor.VisitReversePostOrder();
155 }
156
157 bool be_loop_friendly = (use_all_optimizations_ == false);
158
159 InstructionSimplifierVisitor visitor(graph_, codegen_, stats_, be_loop_friendly);
160 return visitor.Run();
161 }
162
Run()163 bool InstructionSimplifierVisitor::Run() {
164 bool didSimplify = false;
165 // Iterate in reverse post order to open up more simplifications to users
166 // of instructions that got simplified.
167 for (HBasicBlock* block : GetGraph()->GetReversePostOrder()) {
168 // The simplification of an instruction to another instruction may yield
169 // possibilities for other simplifications. So although we perform a reverse
170 // post order visit, we sometimes need to revisit an instruction index.
171 do {
172 simplification_occurred_ = false;
173 VisitNonPhiInstructions(block);
174 if (simplification_occurred_) {
175 didSimplify = true;
176 }
177 } while (simplification_occurred_ &&
178 (simplifications_at_current_position_ < kMaxSamePositionSimplifications));
179 simplifications_at_current_position_ = 0;
180 }
181 return didSimplify;
182 }
183
184 namespace {
185
AreAllBitsSet(HConstant * constant)186 bool AreAllBitsSet(HConstant* constant) {
187 return Int64FromConstant(constant) == -1;
188 }
189
190 } // namespace
191
192 // Returns true if the code was simplified to use only one negation operation
193 // after the binary operation instead of one on each of the inputs.
TryMoveNegOnInputsAfterBinop(HBinaryOperation * binop)194 bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) {
195 DCHECK(binop->IsAdd() || binop->IsSub());
196 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg());
197 HNeg* left_neg = binop->GetLeft()->AsNeg();
198 HNeg* right_neg = binop->GetRight()->AsNeg();
199 if (!left_neg->HasOnlyOneNonEnvironmentUse() ||
200 !right_neg->HasOnlyOneNonEnvironmentUse()) {
201 return false;
202 }
203 // Replace code looking like
204 // NEG tmp1, a
205 // NEG tmp2, b
206 // ADD dst, tmp1, tmp2
207 // with
208 // ADD tmp, a, b
209 // NEG dst, tmp
210 // Note that we cannot optimize `(-a) + (-b)` to `-(a + b)` for floating-point.
211 // When `a` is `-0.0` and `b` is `0.0`, the former expression yields `0.0`,
212 // while the later yields `-0.0`.
213 if (!DataType::IsIntegralType(binop->GetType())) {
214 return false;
215 }
216 binop->ReplaceInput(left_neg->GetInput(), 0);
217 binop->ReplaceInput(right_neg->GetInput(), 1);
218 left_neg->GetBlock()->RemoveInstruction(left_neg);
219 right_neg->GetBlock()->RemoveInstruction(right_neg);
220 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(binop->GetType(), binop);
221 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext());
222 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0);
223 RecordSimplification();
224 return true;
225 }
226
TryDeMorganNegationFactoring(HBinaryOperation * op)227 bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation* op) {
228 DCHECK(op->IsAnd() || op->IsOr()) << op->DebugName();
229 DataType::Type type = op->GetType();
230 HInstruction* left = op->GetLeft();
231 HInstruction* right = op->GetRight();
232
233 // We can apply De Morgan's laws if both inputs are Not's and are only used
234 // by `op`.
235 if (((left->IsNot() && right->IsNot()) ||
236 (left->IsBooleanNot() && right->IsBooleanNot())) &&
237 left->HasOnlyOneNonEnvironmentUse() &&
238 right->HasOnlyOneNonEnvironmentUse()) {
239 // Replace code looking like
240 // NOT nota, a
241 // NOT notb, b
242 // AND dst, nota, notb (respectively OR)
243 // with
244 // OR or, a, b (respectively AND)
245 // NOT dest, or
246 HInstruction* src_left = left->InputAt(0);
247 HInstruction* src_right = right->InputAt(0);
248 uint32_t dex_pc = op->GetDexPc();
249
250 // Remove the negations on the inputs.
251 left->ReplaceWith(src_left);
252 right->ReplaceWith(src_right);
253 left->GetBlock()->RemoveInstruction(left);
254 right->GetBlock()->RemoveInstruction(right);
255
256 // Replace the `HAnd` or `HOr`.
257 HBinaryOperation* hbin;
258 if (op->IsAnd()) {
259 hbin = new (GetGraph()->GetAllocator()) HOr(type, src_left, src_right, dex_pc);
260 } else {
261 hbin = new (GetGraph()->GetAllocator()) HAnd(type, src_left, src_right, dex_pc);
262 }
263 HInstruction* hnot;
264 if (left->IsBooleanNot()) {
265 hnot = new (GetGraph()->GetAllocator()) HBooleanNot(hbin, dex_pc);
266 } else {
267 hnot = new (GetGraph()->GetAllocator()) HNot(type, hbin, dex_pc);
268 }
269
270 op->GetBlock()->InsertInstructionBefore(hbin, op);
271 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
272
273 RecordSimplification();
274 return true;
275 }
276
277 return false;
278 }
279
TryCombineVecMultiplyAccumulate(HVecMul * mul)280 bool InstructionSimplifierVisitor::TryCombineVecMultiplyAccumulate(HVecMul* mul) {
281 DataType::Type type = mul->GetPackedType();
282 InstructionSet isa = codegen_->GetInstructionSet();
283 switch (isa) {
284 case InstructionSet::kArm64:
285 if (!(type == DataType::Type::kUint8 ||
286 type == DataType::Type::kInt8 ||
287 type == DataType::Type::kUint16 ||
288 type == DataType::Type::kInt16 ||
289 type == DataType::Type::kInt32)) {
290 return false;
291 }
292 break;
293 default:
294 return false;
295 }
296
297 ArenaAllocator* allocator = mul->GetBlock()->GetGraph()->GetAllocator();
298 if (!mul->HasOnlyOneNonEnvironmentUse()) {
299 return false;
300 }
301 HInstruction* binop = mul->GetUses().front().GetUser();
302 if (!binop->IsVecAdd() && !binop->IsVecSub()) {
303 return false;
304 }
305
306 // Replace code looking like
307 // VECMUL tmp, x, y
308 // VECADD/SUB dst, acc, tmp
309 // with
310 // VECMULACC dst, acc, x, y
311 // Note that we do not want to (unconditionally) perform the merge when the
312 // multiplication has multiple uses and it can be merged in all of them.
313 // Multiple uses could happen on the same control-flow path, and we would
314 // then increase the amount of work. In the future we could try to evaluate
315 // whether all uses are on different control-flow paths (using dominance and
316 // reverse-dominance information) and only perform the merge when they are.
317 HInstruction* accumulator = nullptr;
318 HVecBinaryOperation* vec_binop = binop->AsVecBinaryOperation();
319 HInstruction* binop_left = vec_binop->GetLeft();
320 HInstruction* binop_right = vec_binop->GetRight();
321 // This is always true since the `HVecMul` has only one use (which is checked above).
322 DCHECK_NE(binop_left, binop_right);
323 if (binop_right == mul) {
324 accumulator = binop_left;
325 } else {
326 DCHECK_EQ(binop_left, mul);
327 // Only addition is commutative.
328 if (!binop->IsVecAdd()) {
329 return false;
330 }
331 accumulator = binop_right;
332 }
333
334 DCHECK(accumulator != nullptr);
335 HInstruction::InstructionKind kind =
336 binop->IsVecAdd() ? HInstruction::kAdd : HInstruction::kSub;
337
338 bool predicated_simd = vec_binop->IsPredicated();
339 if (predicated_simd && !HVecOperation::HaveSamePredicate(vec_binop, mul)) {
340 return false;
341 }
342
343 HVecMultiplyAccumulate* mulacc =
344 new (allocator) HVecMultiplyAccumulate(allocator,
345 kind,
346 accumulator,
347 mul->GetLeft(),
348 mul->GetRight(),
349 vec_binop->GetPackedType(),
350 vec_binop->GetVectorLength(),
351 vec_binop->GetDexPc());
352
353
354
355 vec_binop->GetBlock()->ReplaceAndRemoveInstructionWith(vec_binop, mulacc);
356 if (predicated_simd) {
357 mulacc->SetGoverningPredicate(vec_binop->GetGoverningPredicate(),
358 vec_binop->GetPredicationKind());
359 }
360
361 DCHECK(!mul->HasUses());
362 mul->GetBlock()->RemoveInstruction(mul);
363 return true;
364 }
365
366 // Replace code looking like (x << N >>> N or x << N >> N):
367 // SHL tmp, x, N
368 // USHR/SHR dst, tmp, N
369 // with the corresponding type conversion:
370 // TypeConversion<Unsigned<T>/Signed<T>> dst, x
371 // if
372 // SHL has only one non environment use
373 // TypeOf(tmp) is not 64-bit type (they are not supported yet)
374 // N % kBitsPerByte = 0
375 // where
376 // T = SignedIntegralTypeFromSize(source_integral_size)
377 // source_integral_size = ByteSize(tmp) - N / kBitsPerByte
378 //
379 // We calculate source_integral_size from shift amount instead of
380 // assuming that it is equal to ByteSize(x) to be able to optimize
381 // cases like this:
382 // int x = ...
383 // int y = x << 24 >>> 24
384 // that is equavalent to
385 // int y = (unsigned byte) x
386 // in this case:
387 // N = 24
388 // tmp = x << 24
389 // source_integral_size is 1 (= 4 - 24 / 8) that corresponds to unsigned byte.
TryReplaceShiftsByConstantWithTypeConversion(HBinaryOperation * instruction)390 static bool TryReplaceShiftsByConstantWithTypeConversion(HBinaryOperation *instruction) {
391 if (!instruction->IsUShr() && !instruction->IsShr()) {
392 return false;
393 }
394
395 if (DataType::Is64BitType(instruction->GetResultType())) {
396 return false;
397 }
398
399 HInstruction* shr_amount = instruction->GetRight();
400 if (!shr_amount->IsIntConstant()) {
401 return false;
402 }
403
404 int32_t shr_amount_cst = shr_amount->AsIntConstant()->GetValue();
405
406 // We assume that shift amount simplification was applied first so it doesn't
407 // exceed maximum distance that is kMaxIntShiftDistance as 64-bit shifts aren't
408 // supported.
409 DCHECK_LE(shr_amount_cst, kMaxIntShiftDistance);
410
411 if ((shr_amount_cst % kBitsPerByte) != 0) {
412 return false;
413 }
414
415 // Calculate size of the significant part of the input, e.g. a part that is not
416 // discarded due to left shift.
417 // Shift amount here should be less than size of right shift type.
418 DCHECK_GT(DataType::Size(instruction->GetType()), shr_amount_cst / kBitsPerByte);
419 size_t source_significant_part_size =
420 DataType::Size(instruction->GetType()) - shr_amount_cst / kBitsPerByte;
421
422 // Look for the smallest signed integer type that is suitable to store the
423 // significant part of the input.
424 DataType::Type source_integral_type =
425 DataType::SignedIntegralTypeFromSize(source_significant_part_size);
426
427 // If the size of the significant part of the input isn't equal to the size of the
428 // found type, shifts cannot be replaced by type conversion.
429 if (DataType::Size(source_integral_type) != source_significant_part_size) {
430 return false;
431 }
432
433 HInstruction* shr_value = instruction->GetLeft();
434 if (!shr_value->IsShl()) {
435 return false;
436 }
437
438 HShl *shl = shr_value->AsShl();
439 if (!shl->HasOnlyOneNonEnvironmentUse()) {
440 return false;
441 }
442
443 // Constants are unique so we just compare pointer here.
444 if (shl->GetRight() != shr_amount) {
445 return false;
446 }
447
448 // Type of shift's value is always int so sign/zero extension only
449 // depends on the type of the shift (shr/ushr).
450 bool is_signed = instruction->IsShr();
451 DataType::Type conv_type =
452 is_signed ? source_integral_type : DataType::ToUnsigned(source_integral_type);
453
454 DCHECK(DataType::IsTypeConversionImplicit(conv_type, instruction->GetResultType()));
455
456 HInstruction* shl_value = shl->GetLeft();
457 HBasicBlock *block = instruction->GetBlock();
458
459 // We shouldn't introduce new implicit type conversions during simplification.
460 if (DataType::IsTypeConversionImplicit(shl_value->GetType(), conv_type)) {
461 instruction->ReplaceWith(shl_value);
462 instruction->GetBlock()->RemoveInstruction(instruction);
463 } else {
464 HTypeConversion* new_conversion =
465 new (block->GetGraph()->GetAllocator()) HTypeConversion(conv_type, shl_value);
466 block->ReplaceAndRemoveInstructionWith(instruction, new_conversion);
467 }
468
469 shl->GetBlock()->RemoveInstruction(shl);
470
471 return true;
472 }
473
VisitShift(HBinaryOperation * instruction)474 void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
475 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
476 HInstruction* shift_amount = instruction->GetRight();
477 HInstruction* value = instruction->GetLeft();
478
479 int64_t implicit_mask = (value->GetType() == DataType::Type::kInt64)
480 ? kMaxLongShiftDistance
481 : kMaxIntShiftDistance;
482
483 if (shift_amount->IsConstant()) {
484 int64_t cst = Int64FromConstant(shift_amount->AsConstant());
485 int64_t masked_cst = cst & implicit_mask;
486 if (masked_cst == 0) {
487 // Replace code looking like
488 // SHL dst, value, 0
489 // with
490 // value
491 instruction->ReplaceWith(value);
492 instruction->GetBlock()->RemoveInstruction(instruction);
493 RecordSimplification();
494 return;
495 } else if (masked_cst != cst) {
496 // Replace code looking like
497 // SHL dst, value, cst
498 // where cst exceeds maximum distance with the equivalent
499 // SHL dst, value, cst & implicit_mask
500 // (as defined by shift semantics). This ensures other
501 // optimizations do not need to special case for such situations.
502 DCHECK_EQ(shift_amount->GetType(), DataType::Type::kInt32);
503 instruction->ReplaceInput(GetGraph()->GetIntConstant(masked_cst), /* index= */ 1);
504 RecordSimplification();
505 return;
506 }
507
508 if (TryReplaceShiftsByConstantWithTypeConversion(instruction)) {
509 RecordSimplification();
510 return;
511 }
512 }
513
514 // Shift operations implicitly mask the shift amount according to the type width. Get rid of
515 // unnecessary And/Or/Xor/Add/Sub/TypeConversion operations on the shift amount that do not
516 // affect the relevant bits.
517 // Replace code looking like
518 // AND adjusted_shift, shift, <superset of implicit mask>
519 // [OR/XOR/ADD/SUB adjusted_shift, shift, <value not overlapping with implicit mask>]
520 // [<conversion-from-integral-non-64-bit-type> adjusted_shift, shift]
521 // SHL dst, value, adjusted_shift
522 // with
523 // SHL dst, value, shift
524 if (shift_amount->IsAnd() ||
525 shift_amount->IsOr() ||
526 shift_amount->IsXor() ||
527 shift_amount->IsAdd() ||
528 shift_amount->IsSub()) {
529 int64_t required_result = shift_amount->IsAnd() ? implicit_mask : 0;
530 HBinaryOperation* bin_op = shift_amount->AsBinaryOperation();
531 HConstant* mask = bin_op->GetConstantRight();
532 if (mask != nullptr && (Int64FromConstant(mask) & implicit_mask) == required_result) {
533 instruction->ReplaceInput(bin_op->GetLeastConstantLeft(), 1);
534 RecordSimplification();
535 return;
536 }
537 } else if (shift_amount->IsTypeConversion()) {
538 DCHECK_NE(shift_amount->GetType(), DataType::Type::kBool); // We never convert to bool.
539 DataType::Type source_type = shift_amount->InputAt(0)->GetType();
540 // Non-integral and 64-bit source types require an explicit type conversion.
541 if (DataType::IsIntegralType(source_type) && !DataType::Is64BitType(source_type)) {
542 instruction->ReplaceInput(shift_amount->AsTypeConversion()->GetInput(), 1);
543 RecordSimplification();
544 return;
545 }
546 }
547 }
548
IsSubRegBitsMinusOther(HSub * sub,size_t reg_bits,HInstruction * other)549 static bool IsSubRegBitsMinusOther(HSub* sub, size_t reg_bits, HInstruction* other) {
550 return (sub->GetRight() == other &&
551 sub->GetLeft()->IsConstant() &&
552 (Int64FromConstant(sub->GetLeft()->AsConstant()) & (reg_bits - 1)) == 0);
553 }
554
ReplaceRotateWithRor(HBinaryOperation * op,HUShr * ushr,HShl * shl)555 bool InstructionSimplifierVisitor::ReplaceRotateWithRor(HBinaryOperation* op,
556 HUShr* ushr,
557 HShl* shl) {
558 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()) << op->DebugName();
559 HRor* ror =
560 new (GetGraph()->GetAllocator()) HRor(ushr->GetType(), ushr->GetLeft(), ushr->GetRight());
561 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, ror);
562 if (!ushr->HasUses()) {
563 ushr->GetBlock()->RemoveInstruction(ushr);
564 }
565 if (!ushr->GetRight()->HasUses()) {
566 ushr->GetRight()->GetBlock()->RemoveInstruction(ushr->GetRight());
567 }
568 if (!shl->HasUses()) {
569 shl->GetBlock()->RemoveInstruction(shl);
570 }
571 if (!shl->GetRight()->HasUses()) {
572 shl->GetRight()->GetBlock()->RemoveInstruction(shl->GetRight());
573 }
574 RecordSimplification();
575 return true;
576 }
577
578 // Try to replace a binary operation flanked by one UShr and one Shl with a bitfield rotation.
TryReplaceWithRotate(HBinaryOperation * op)579 bool InstructionSimplifierVisitor::TryReplaceWithRotate(HBinaryOperation* op) {
580 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
581 HInstruction* left = op->GetLeft();
582 HInstruction* right = op->GetRight();
583 // If we have an UShr and a Shl (in either order).
584 if ((left->IsUShr() && right->IsShl()) || (left->IsShl() && right->IsUShr())) {
585 HUShr* ushr = left->IsUShr() ? left->AsUShr() : right->AsUShr();
586 HShl* shl = left->IsShl() ? left->AsShl() : right->AsShl();
587 DCHECK(DataType::IsIntOrLongType(ushr->GetType()));
588 if (ushr->GetType() == shl->GetType() &&
589 ushr->GetLeft() == shl->GetLeft()) {
590 if (ushr->GetRight()->IsConstant() && shl->GetRight()->IsConstant()) {
591 // Shift distances are both constant, try replacing with Ror if they
592 // add up to the register size.
593 return TryReplaceWithRotateConstantPattern(op, ushr, shl);
594 } else if (ushr->GetRight()->IsSub() || shl->GetRight()->IsSub()) {
595 // Shift distances are potentially of the form x and (reg_size - x).
596 return TryReplaceWithRotateRegisterSubPattern(op, ushr, shl);
597 } else if (ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg()) {
598 // Shift distances are potentially of the form d and -d.
599 return TryReplaceWithRotateRegisterNegPattern(op, ushr, shl);
600 }
601 }
602 }
603 return false;
604 }
605
606 // Try replacing code looking like (x >>> #rdist OP x << #ldist):
607 // UShr dst, x, #rdist
608 // Shl tmp, x, #ldist
609 // OP dst, dst, tmp
610 // or like (x >>> #rdist OP x << #-ldist):
611 // UShr dst, x, #rdist
612 // Shl tmp, x, #-ldist
613 // OP dst, dst, tmp
614 // with
615 // Ror dst, x, #rdist
TryReplaceWithRotateConstantPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)616 bool InstructionSimplifierVisitor::TryReplaceWithRotateConstantPattern(HBinaryOperation* op,
617 HUShr* ushr,
618 HShl* shl) {
619 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
620 size_t reg_bits = DataType::Size(ushr->GetType()) * kBitsPerByte;
621 size_t rdist = Int64FromConstant(ushr->GetRight()->AsConstant());
622 size_t ldist = Int64FromConstant(shl->GetRight()->AsConstant());
623 if (((ldist + rdist) & (reg_bits - 1)) == 0) {
624 return ReplaceRotateWithRor(op, ushr, shl);
625 }
626 return false;
627 }
628
629 // Replace code looking like (x >>> -d OP x << d):
630 // Neg neg, d
631 // UShr dst, x, neg
632 // Shl tmp, x, d
633 // OP dst, dst, tmp
634 // with
635 // Neg neg, d
636 // Ror dst, x, neg
637 // *** OR ***
638 // Replace code looking like (x >>> d OP x << -d):
639 // UShr dst, x, d
640 // Neg neg, d
641 // Shl tmp, x, neg
642 // OP dst, dst, tmp
643 // with
644 // Ror dst, x, d
645 //
646 // Requires `d` to be non-zero for the HAdd and HXor case. If `d` is 0 the shifts and rotate are
647 // no-ops and the `OP` is never executed. This is fine for HOr since the result is the same, but the
648 // result is different for HAdd and HXor.
TryReplaceWithRotateRegisterNegPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)649 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op,
650 HUShr* ushr,
651 HShl* shl) {
652 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
653 DCHECK(ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg());
654 bool neg_is_left = shl->GetRight()->IsNeg();
655 HNeg* neg = neg_is_left ? shl->GetRight()->AsNeg() : ushr->GetRight()->AsNeg();
656 HInstruction* value = neg->InputAt(0);
657
658 // The shift distance being negated is the distance being shifted the other way.
659 if (value != (neg_is_left ? ushr->GetRight() : shl->GetRight())) {
660 return false;
661 }
662
663 const bool needs_non_zero_value = !op->IsOr();
664 if (needs_non_zero_value) {
665 if (!value->IsConstant() || value->AsConstant()->IsArithmeticZero()) {
666 return false;
667 }
668 }
669 return ReplaceRotateWithRor(op, ushr, shl);
670 }
671
672 // Try replacing code looking like (x >>> d OP x << (#bits - d)):
673 // UShr dst, x, d
674 // Sub ld, #bits, d
675 // Shl tmp, x, ld
676 // OP dst, dst, tmp
677 // with
678 // Ror dst, x, d
679 // *** OR ***
680 // Replace code looking like (x >>> (#bits - d) OP x << d):
681 // Sub rd, #bits, d
682 // UShr dst, x, rd
683 // Shl tmp, x, d
684 // OP dst, dst, tmp
685 // with
686 // Neg neg, d
687 // Ror dst, x, neg
TryReplaceWithRotateRegisterSubPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)688 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op,
689 HUShr* ushr,
690 HShl* shl) {
691 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
692 DCHECK(ushr->GetRight()->IsSub() || shl->GetRight()->IsSub());
693 size_t reg_bits = DataType::Size(ushr->GetType()) * kBitsPerByte;
694 HInstruction* shl_shift = shl->GetRight();
695 HInstruction* ushr_shift = ushr->GetRight();
696 if ((shl_shift->IsSub() && IsSubRegBitsMinusOther(shl_shift->AsSub(), reg_bits, ushr_shift)) ||
697 (ushr_shift->IsSub() && IsSubRegBitsMinusOther(ushr_shift->AsSub(), reg_bits, shl_shift))) {
698 return ReplaceRotateWithRor(op, ushr, shl);
699 }
700 return false;
701 }
702
VisitNullCheck(HNullCheck * null_check)703 void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
704 HInstruction* obj = null_check->InputAt(0);
705 if (!obj->CanBeNull()) {
706 null_check->ReplaceWith(obj);
707 null_check->GetBlock()->RemoveInstruction(null_check);
708 if (stats_ != nullptr) {
709 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck);
710 }
711 }
712 }
713
CanEnsureNotNullAt(HInstruction * input,HInstruction * at)714 bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInstruction* at) {
715 if (!input->CanBeNull()) {
716 return true;
717 }
718
719 for (const HUseListNode<HInstruction*>& use : input->GetUses()) {
720 HInstruction* user = use.GetUser();
721 if (user->IsNullCheck() && user->StrictlyDominates(at)) {
722 return true;
723 }
724 }
725
726 return false;
727 }
728
729 // Returns whether doing a type test between the class of `object` against `klass` has
730 // a statically known outcome. The result of the test is stored in `outcome`.
TypeCheckHasKnownOutcome(ReferenceTypeInfo class_rti,HInstruction * object,bool * outcome)731 static bool TypeCheckHasKnownOutcome(ReferenceTypeInfo class_rti,
732 HInstruction* object,
733 /*out*/bool* outcome) {
734 DCHECK(!object->IsNullConstant()) << "Null constants should be special cased";
735 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo();
736 ScopedObjectAccess soa(Thread::Current());
737 if (!obj_rti.IsValid()) {
738 // We run the simplifier before the reference type propagation so type info might not be
739 // available.
740 return false;
741 }
742
743 if (!class_rti.IsValid()) {
744 // Happens when the loaded class is unresolved.
745 if (obj_rti.IsExact()) {
746 // outcome == 'true' && obj_rti is valid implies that class_rti is valid.
747 // Since that's a contradiction we must not pass this check.
748 *outcome = false;
749 return true;
750 } else {
751 // We aren't able to say anything in particular since we don't know the
752 // exact type of the object.
753 return false;
754 }
755 }
756 DCHECK(class_rti.IsExact());
757 if (class_rti.IsSupertypeOf(obj_rti)) {
758 *outcome = true;
759 return true;
760 } else if (obj_rti.IsExact()) {
761 // The test failed at compile time so will also fail at runtime.
762 *outcome = false;
763 return true;
764 } else if (!class_rti.IsInterface()
765 && !obj_rti.IsInterface()
766 && !obj_rti.IsSupertypeOf(class_rti)) {
767 // Different type hierarchy. The test will fail.
768 *outcome = false;
769 return true;
770 }
771 return false;
772 }
773
VisitCheckCast(HCheckCast * check_cast)774 void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) {
775 HInstruction* object = check_cast->InputAt(0);
776 if (CanEnsureNotNullAt(object, check_cast)) {
777 check_cast->ClearMustDoNullCheck();
778 }
779
780 if (object->IsNullConstant()) {
781 check_cast->GetBlock()->RemoveInstruction(check_cast);
782 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedCheckedCast);
783 return;
784 }
785
786 // Minor correctness check.
787 DCHECK(check_cast->GetTargetClass()->StrictlyDominates(check_cast))
788 << "Illegal graph!\n"
789 << check_cast->DumpWithArgs();
790
791 // Historical note: The `outcome` was initialized to please Valgrind - the compiler can reorder
792 // the return value check with the `outcome` check, b/27651442.
793 bool outcome = false;
794 if (TypeCheckHasKnownOutcome(check_cast->GetTargetClassRTI(), object, &outcome)) {
795 if (outcome) {
796 check_cast->GetBlock()->RemoveInstruction(check_cast);
797 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedCheckedCast);
798 if (check_cast->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck) {
799 HLoadClass* load_class = check_cast->GetTargetClass();
800 if (!load_class->HasUses() && !load_class->NeedsAccessCheck()) {
801 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw.
802 // However, here we know that it cannot because the checkcast was successful, hence
803 // the class was already loaded.
804 load_class->GetBlock()->RemoveInstruction(load_class);
805 }
806 }
807 } else {
808 // TODO Don't do anything for exceptional cases for now. Ideally we should
809 // remove all instructions and blocks this instruction dominates and
810 // replace it with a manual throw.
811 }
812 }
813 }
814
VisitInstanceOf(HInstanceOf * instruction)815 void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) {
816 HInstruction* object = instruction->InputAt(0);
817
818 bool can_be_null = true;
819 if (CanEnsureNotNullAt(object, instruction)) {
820 can_be_null = false;
821 instruction->ClearMustDoNullCheck();
822 }
823
824 HGraph* graph = GetGraph();
825 if (object->IsNullConstant()) {
826 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedInstanceOf);
827 instruction->ReplaceWith(graph->GetIntConstant(0));
828 instruction->GetBlock()->RemoveInstruction(instruction);
829 RecordSimplification();
830 return;
831 }
832
833 // Minor correctness check.
834 DCHECK(instruction->GetTargetClass()->StrictlyDominates(instruction))
835 << "Illegal graph!\n"
836 << instruction->DumpWithArgs();
837
838 // Historical note: The `outcome` was initialized to please Valgrind - the compiler can reorder
839 // the return value check with the `outcome` check, b/27651442.
840 bool outcome = false;
841 if (TypeCheckHasKnownOutcome(instruction->GetTargetClassRTI(), object, &outcome)) {
842 MaybeRecordStat(stats_, MethodCompilationStat::kRemovedInstanceOf);
843 if (outcome && can_be_null) {
844 // Type test will succeed, we just need a null test.
845 HNotEqual* test = new (graph->GetAllocator()) HNotEqual(graph->GetNullConstant(), object);
846 instruction->GetBlock()->InsertInstructionBefore(test, instruction);
847 instruction->ReplaceWith(test);
848 } else {
849 // We've statically determined the result of the instanceof.
850 instruction->ReplaceWith(graph->GetIntConstant(outcome));
851 }
852 RecordSimplification();
853 instruction->GetBlock()->RemoveInstruction(instruction);
854 if (outcome && instruction->GetTypeCheckKind() != TypeCheckKind::kBitstringCheck) {
855 HLoadClass* load_class = instruction->GetTargetClass();
856 if (!load_class->HasUses() && !load_class->NeedsAccessCheck()) {
857 // We cannot rely on DCE to remove the class because the `HLoadClass`
858 // thinks it can throw. However, here we know that it cannot because the
859 // instanceof check was successful and we don't need to check the
860 // access, hence the class was already loaded.
861 load_class->GetBlock()->RemoveInstruction(load_class);
862 }
863 }
864 }
865 }
866
VisitInstanceFieldSet(HInstanceFieldSet * instruction)867 void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) {
868 if ((instruction->GetValue()->GetType() == DataType::Type::kReference)
869 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) {
870 instruction->ClearValueCanBeNull();
871 }
872 }
873
VisitStaticFieldSet(HStaticFieldSet * instruction)874 void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) {
875 if ((instruction->GetValue()->GetType() == DataType::Type::kReference)
876 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) {
877 instruction->ClearValueCanBeNull();
878 }
879 }
880
GetOppositeConditionSwapOps(ArenaAllocator * allocator,HInstruction * cond)881 static HCondition* GetOppositeConditionSwapOps(ArenaAllocator* allocator, HInstruction* cond) {
882 HInstruction *lhs = cond->InputAt(0);
883 HInstruction *rhs = cond->InputAt(1);
884 switch (cond->GetKind()) {
885 case HInstruction::kEqual:
886 return new (allocator) HEqual(rhs, lhs);
887 case HInstruction::kNotEqual:
888 return new (allocator) HNotEqual(rhs, lhs);
889 case HInstruction::kLessThan:
890 return new (allocator) HGreaterThan(rhs, lhs);
891 case HInstruction::kLessThanOrEqual:
892 return new (allocator) HGreaterThanOrEqual(rhs, lhs);
893 case HInstruction::kGreaterThan:
894 return new (allocator) HLessThan(rhs, lhs);
895 case HInstruction::kGreaterThanOrEqual:
896 return new (allocator) HLessThanOrEqual(rhs, lhs);
897 case HInstruction::kBelow:
898 return new (allocator) HAbove(rhs, lhs);
899 case HInstruction::kBelowOrEqual:
900 return new (allocator) HAboveOrEqual(rhs, lhs);
901 case HInstruction::kAbove:
902 return new (allocator) HBelow(rhs, lhs);
903 case HInstruction::kAboveOrEqual:
904 return new (allocator) HBelowOrEqual(rhs, lhs);
905 default:
906 LOG(FATAL) << "Unknown ConditionType " << cond->GetKind();
907 UNREACHABLE();
908 }
909 }
910
VisitEqual(HEqual * equal)911 void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) {
912 HInstruction* input_const = equal->GetConstantRight();
913 if (input_const != nullptr) {
914 HInstruction* input_value = equal->GetLeastConstantLeft();
915 if ((input_value->GetType() == DataType::Type::kBool) && input_const->IsIntConstant()) {
916 HBasicBlock* block = equal->GetBlock();
917 // We are comparing the boolean to a constant which is of type int and can
918 // be any constant.
919 if (input_const->AsIntConstant()->IsTrue()) {
920 // Replace (bool_value == true) with bool_value
921 equal->ReplaceWith(input_value);
922 block->RemoveInstruction(equal);
923 RecordSimplification();
924 } else if (input_const->AsIntConstant()->IsFalse()) {
925 // Replace (bool_value == false) with !bool_value
926 equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, equal));
927 block->RemoveInstruction(equal);
928 RecordSimplification();
929 } else {
930 // Replace (bool_value == integer_not_zero_nor_one_constant) with false
931 equal->ReplaceWith(GetGraph()->GetIntConstant(0));
932 block->RemoveInstruction(equal);
933 RecordSimplification();
934 }
935 } else {
936 VisitCondition(equal);
937 }
938 } else {
939 VisitCondition(equal);
940 }
941 }
942
VisitNotEqual(HNotEqual * not_equal)943 void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) {
944 HInstruction* input_const = not_equal->GetConstantRight();
945 if (input_const != nullptr) {
946 HInstruction* input_value = not_equal->GetLeastConstantLeft();
947 if ((input_value->GetType() == DataType::Type::kBool) && input_const->IsIntConstant()) {
948 HBasicBlock* block = not_equal->GetBlock();
949 // We are comparing the boolean to a constant which is of type int and can
950 // be any constant.
951 if (input_const->AsIntConstant()->IsTrue()) {
952 // Replace (bool_value != true) with !bool_value
953 not_equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, not_equal));
954 block->RemoveInstruction(not_equal);
955 RecordSimplification();
956 } else if (input_const->AsIntConstant()->IsFalse()) {
957 // Replace (bool_value != false) with bool_value
958 not_equal->ReplaceWith(input_value);
959 block->RemoveInstruction(not_equal);
960 RecordSimplification();
961 } else {
962 // Replace (bool_value != integer_not_zero_nor_one_constant) with true
963 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1));
964 block->RemoveInstruction(not_equal);
965 RecordSimplification();
966 }
967 } else {
968 VisitCondition(not_equal);
969 }
970 } else {
971 VisitCondition(not_equal);
972 }
973 }
974
VisitBooleanNot(HBooleanNot * bool_not)975 void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) {
976 HInstruction* input = bool_not->InputAt(0);
977 HInstruction* replace_with = nullptr;
978
979 if (input->IsIntConstant()) {
980 // Replace !(true/false) with false/true.
981 if (input->AsIntConstant()->IsTrue()) {
982 replace_with = GetGraph()->GetIntConstant(0);
983 } else {
984 DCHECK(input->AsIntConstant()->IsFalse()) << input->AsIntConstant()->GetValue();
985 replace_with = GetGraph()->GetIntConstant(1);
986 }
987 } else if (input->IsBooleanNot()) {
988 // Replace (!(!bool_value)) with bool_value.
989 replace_with = input->InputAt(0);
990 } else if (input->IsCondition() &&
991 // Don't change FP compares. The definition of compares involving
992 // NaNs forces the compares to be done as written by the user.
993 !DataType::IsFloatingPointType(input->InputAt(0)->GetType())) {
994 // Replace condition with its opposite.
995 replace_with = GetGraph()->InsertOppositeCondition(input->AsCondition(), bool_not);
996 }
997
998 if (replace_with != nullptr) {
999 bool_not->ReplaceWith(replace_with);
1000 bool_not->GetBlock()->RemoveInstruction(bool_not);
1001 RecordSimplification();
1002 }
1003 }
1004
1005 // Constructs a new ABS(x) node in the HIR.
NewIntegralAbs(ArenaAllocator * allocator,HInstruction * x,HInstruction * cursor)1006 static HInstruction* NewIntegralAbs(ArenaAllocator* allocator,
1007 HInstruction* x,
1008 HInstruction* cursor) {
1009 DataType::Type type = DataType::Kind(x->GetType());
1010 DCHECK(type == DataType::Type::kInt32 || type == DataType::Type::kInt64);
1011 HAbs* abs = new (allocator) HAbs(type, x, cursor->GetDexPc());
1012 cursor->GetBlock()->InsertInstructionBefore(abs, cursor);
1013 return abs;
1014 }
1015
1016 // Constructs a new MIN/MAX(x, y) node in the HIR.
NewIntegralMinMax(ArenaAllocator * allocator,HInstruction * x,HInstruction * y,HInstruction * cursor,bool is_min)1017 static HInstruction* NewIntegralMinMax(ArenaAllocator* allocator,
1018 HInstruction* x,
1019 HInstruction* y,
1020 HInstruction* cursor,
1021 bool is_min) {
1022 DataType::Type type = DataType::Kind(x->GetType());
1023 DCHECK(type == DataType::Type::kInt32 || type == DataType::Type::kInt64);
1024 HBinaryOperation* minmax = nullptr;
1025 if (is_min) {
1026 minmax = new (allocator) HMin(type, x, y, cursor->GetDexPc());
1027 } else {
1028 minmax = new (allocator) HMax(type, x, y, cursor->GetDexPc());
1029 }
1030 cursor->GetBlock()->InsertInstructionBefore(minmax, cursor);
1031 return minmax;
1032 }
1033
1034 // Returns true if operands a and b consists of widening type conversions
1035 // (either explicit or implicit) to the given to_type.
AreLowerPrecisionArgs(DataType::Type to_type,HInstruction * a,HInstruction * b)1036 static bool AreLowerPrecisionArgs(DataType::Type to_type, HInstruction* a, HInstruction* b) {
1037 if (a->IsTypeConversion() && a->GetType() == to_type) {
1038 a = a->InputAt(0);
1039 }
1040 if (b->IsTypeConversion() && b->GetType() == to_type) {
1041 b = b->InputAt(0);
1042 }
1043 DataType::Type type1 = a->GetType();
1044 DataType::Type type2 = b->GetType();
1045 return (type1 == DataType::Type::kUint8 && type2 == DataType::Type::kUint8) ||
1046 (type1 == DataType::Type::kInt8 && type2 == DataType::Type::kInt8) ||
1047 (type1 == DataType::Type::kInt16 && type2 == DataType::Type::kInt16) ||
1048 (type1 == DataType::Type::kUint16 && type2 == DataType::Type::kUint16) ||
1049 (type1 == DataType::Type::kInt32 && type2 == DataType::Type::kInt32 &&
1050 to_type == DataType::Type::kInt64);
1051 }
1052
1053 // Returns an acceptable substitution for "a" on the select
1054 // construct "a <cmp> b ? c : .." during MIN/MAX recognition.
AllowInMinMax(IfCondition cmp,HInstruction * a,HInstruction * b,HInstruction * c)1055 static HInstruction* AllowInMinMax(IfCondition cmp,
1056 HInstruction* a,
1057 HInstruction* b,
1058 HInstruction* c) {
1059 int64_t value = 0;
1060 if (IsInt64AndGet(b, /*out*/ &value) &&
1061 (((cmp == kCondLT || cmp == kCondLE) && c->IsMax()) ||
1062 ((cmp == kCondGT || cmp == kCondGE) && c->IsMin()))) {
1063 HConstant* other = c->AsBinaryOperation()->GetConstantRight();
1064 if (other != nullptr && a == c->AsBinaryOperation()->GetLeastConstantLeft()) {
1065 int64_t other_value = Int64FromConstant(other);
1066 bool is_max = (cmp == kCondLT || cmp == kCondLE);
1067 // Allow the max for a < 100 ? max(a, -100) : ..
1068 // or the min for a > -100 ? min(a, 100) : ..
1069 if (is_max ? (value >= other_value) : (value <= other_value)) {
1070 return c;
1071 }
1072 }
1073 }
1074 return nullptr;
1075 }
1076
VisitSelect(HSelect * select)1077 void InstructionSimplifierVisitor::VisitSelect(HSelect* select) {
1078 HInstruction* replace_with = nullptr;
1079 HInstruction* condition = select->GetCondition();
1080 HInstruction* true_value = select->GetTrueValue();
1081 HInstruction* false_value = select->GetFalseValue();
1082
1083 if (condition->IsBooleanNot()) {
1084 // Change ((!cond) ? x : y) to (cond ? y : x).
1085 condition = condition->InputAt(0);
1086 std::swap(true_value, false_value);
1087 select->ReplaceInput(false_value, 0);
1088 select->ReplaceInput(true_value, 1);
1089 select->ReplaceInput(condition, 2);
1090 RecordSimplification();
1091 }
1092
1093 if (true_value == false_value) {
1094 // Replace (cond ? x : x) with (x).
1095 replace_with = true_value;
1096 } else if (condition->IsIntConstant()) {
1097 if (condition->AsIntConstant()->IsTrue()) {
1098 // Replace (true ? x : y) with (x).
1099 replace_with = true_value;
1100 } else {
1101 // Replace (false ? x : y) with (y).
1102 DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue();
1103 replace_with = false_value;
1104 }
1105 } else if (true_value->IsIntConstant() && false_value->IsIntConstant()) {
1106 if (true_value->AsIntConstant()->IsTrue() && false_value->AsIntConstant()->IsFalse()) {
1107 // Replace (cond ? true : false) with (cond).
1108 replace_with = condition;
1109 } else if (true_value->AsIntConstant()->IsFalse() && false_value->AsIntConstant()->IsTrue()) {
1110 // Replace (cond ? false : true) with (!cond).
1111 replace_with = GetGraph()->InsertOppositeCondition(condition, select);
1112 }
1113 } else if (condition->IsCondition()) {
1114 IfCondition cmp = condition->AsCondition()->GetCondition();
1115 HInstruction* a = condition->InputAt(0);
1116 HInstruction* b = condition->InputAt(1);
1117 DataType::Type t_type = true_value->GetType();
1118 DataType::Type f_type = false_value->GetType();
1119 if (DataType::IsIntegralType(t_type) && DataType::Kind(t_type) == DataType::Kind(f_type)) {
1120 if (cmp == kCondEQ || cmp == kCondNE) {
1121 // Turns
1122 // * Select[a, b, EQ(a,b)] / Select[a, b, EQ(b,a)] into a
1123 // * Select[a, b, NE(a,b)] / Select[a, b, NE(b,a)] into b
1124 // Note that the order in EQ/NE is irrelevant.
1125 if ((a == true_value && b == false_value) || (a == false_value && b == true_value)) {
1126 replace_with = cmp == kCondEQ ? false_value : true_value;
1127 }
1128 } else {
1129 // Test if both values are compatible integral types (resulting MIN/MAX/ABS
1130 // type will be int or long, like the condition). Replacements are general,
1131 // but assume conditions prefer constants on the right.
1132
1133 // Allow a < 100 ? max(a, -100) : ..
1134 // or a > -100 ? min(a, 100) : ..
1135 // to use min/max instead of a to detect nested min/max expressions.
1136 HInstruction* new_a = AllowInMinMax(cmp, a, b, true_value);
1137 if (new_a != nullptr) {
1138 a = new_a;
1139 }
1140 // Try to replace typical integral MIN/MAX/ABS constructs.
1141 if ((cmp == kCondLT || cmp == kCondLE || cmp == kCondGT || cmp == kCondGE) &&
1142 ((a == true_value && b == false_value) || (b == true_value && a == false_value))) {
1143 // Found a < b ? a : b (MIN) or a < b ? b : a (MAX)
1144 // or a > b ? a : b (MAX) or a > b ? b : a (MIN).
1145 bool is_min = (cmp == kCondLT || cmp == kCondLE) == (a == true_value);
1146 replace_with = NewIntegralMinMax(GetGraph()->GetAllocator(), a, b, select, is_min);
1147 } else if (((cmp == kCondLT || cmp == kCondLE) && true_value->IsNeg()) ||
1148 ((cmp == kCondGT || cmp == kCondGE) && false_value->IsNeg())) {
1149 bool negLeft = (cmp == kCondLT || cmp == kCondLE);
1150 HInstruction* the_negated = negLeft ? true_value->InputAt(0) : false_value->InputAt(0);
1151 HInstruction* not_negated = negLeft ? false_value : true_value;
1152 if (a == the_negated && a == not_negated && IsInt64Value(b, 0)) {
1153 // Found a < 0 ? -a : a
1154 // or a > 0 ? a : -a
1155 // which can be replaced by ABS(a).
1156 replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), a, select);
1157 }
1158 } else if (true_value->IsSub() && false_value->IsSub()) {
1159 HInstruction* true_sub1 = true_value->InputAt(0);
1160 HInstruction* true_sub2 = true_value->InputAt(1);
1161 HInstruction* false_sub1 = false_value->InputAt(0);
1162 HInstruction* false_sub2 = false_value->InputAt(1);
1163 if ((((cmp == kCondGT || cmp == kCondGE) &&
1164 (a == true_sub1 && b == true_sub2 && a == false_sub2 && b == false_sub1)) ||
1165 ((cmp == kCondLT || cmp == kCondLE) &&
1166 (a == true_sub2 && b == true_sub1 && a == false_sub1 && b == false_sub2))) &&
1167 AreLowerPrecisionArgs(t_type, a, b)) {
1168 // Found a > b ? a - b : b - a
1169 // or a < b ? b - a : a - b
1170 // which can be replaced by ABS(a - b) for lower precision operands a, b.
1171 replace_with = NewIntegralAbs(GetGraph()->GetAllocator(), true_value, select);
1172 }
1173 }
1174 }
1175 }
1176 }
1177
1178 if (replace_with != nullptr) {
1179 select->ReplaceWith(replace_with);
1180 select->GetBlock()->RemoveInstruction(select);
1181 RecordSimplification();
1182 }
1183 }
1184
VisitIf(HIf * instruction)1185 void InstructionSimplifierVisitor::VisitIf(HIf* instruction) {
1186 HInstruction* condition = instruction->InputAt(0);
1187 if (condition->IsBooleanNot()) {
1188 // Swap successors if input is negated.
1189 instruction->ReplaceInput(condition->InputAt(0), 0);
1190 instruction->GetBlock()->SwapSuccessors();
1191 RecordSimplification();
1192 }
1193 }
1194
1195 // TODO(solanes): This optimization should be in ConstantFolding since we are folding to a constant.
1196 // However, we get code size regressions when we do that since we sometimes have a NullCheck between
1197 // HArrayLength and IsNewArray, and said NullCheck is eliminated in InstructionSimplifier. If we run
1198 // ConstantFolding and InstructionSimplifier in lockstep this wouldn't be an issue.
VisitArrayLength(HArrayLength * instruction)1199 void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
1200 HInstruction* input = instruction->InputAt(0);
1201 // If the array is a NewArray with constant size, replace the array length
1202 // with the constant instruction. This helps the bounds check elimination phase.
1203 if (input->IsNewArray()) {
1204 input = input->AsNewArray()->GetLength();
1205 if (input->IsIntConstant()) {
1206 instruction->ReplaceWith(input);
1207 }
1208 }
1209 }
1210
VisitArraySet(HArraySet * instruction)1211 void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) {
1212 HInstruction* value = instruction->GetValue();
1213 if (value->GetType() != DataType::Type::kReference) {
1214 return;
1215 }
1216
1217 if (CanEnsureNotNullAt(value, instruction)) {
1218 instruction->ClearValueCanBeNull();
1219 }
1220
1221 if (value->IsArrayGet()) {
1222 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) {
1223 // If the code is just swapping elements in the array, no need for a type check.
1224 instruction->ClearTypeCheck();
1225 return;
1226 }
1227 }
1228
1229 if (value->IsNullConstant()) {
1230 instruction->ClearTypeCheck();
1231 return;
1232 }
1233
1234 ScopedObjectAccess soa(Thread::Current());
1235 ReferenceTypeInfo array_rti = instruction->GetArray()->GetReferenceTypeInfo();
1236 ReferenceTypeInfo value_rti = value->GetReferenceTypeInfo();
1237 if (!array_rti.IsValid()) {
1238 return;
1239 }
1240
1241 if (value_rti.IsValid() && array_rti.CanArrayHold(value_rti)) {
1242 instruction->ClearTypeCheck();
1243 return;
1244 }
1245
1246 if (array_rti.IsObjectArray()) {
1247 if (array_rti.IsExact()) {
1248 instruction->ClearTypeCheck();
1249 return;
1250 }
1251 instruction->SetStaticTypeOfArrayIsObjectArray();
1252 }
1253 }
1254
IsTypeConversionLossless(DataType::Type input_type,DataType::Type result_type)1255 static bool IsTypeConversionLossless(DataType::Type input_type, DataType::Type result_type) {
1256 // Make sure all implicit conversions have been simplified and no new ones have been introduced.
1257 DCHECK(!DataType::IsTypeConversionImplicit(input_type, result_type))
1258 << input_type << "," << result_type;
1259 // The conversion to a larger type is loss-less with the exception of two cases,
1260 // - conversion to the unsigned type Uint16, where we may lose some bits, and
1261 // - conversion from float to long, the only FP to integral conversion with smaller FP type.
1262 // For integral to FP conversions this holds because the FP mantissa is large enough.
1263 // Note: The size check excludes Uint8 as the result type.
1264 return DataType::Size(result_type) > DataType::Size(input_type) &&
1265 result_type != DataType::Type::kUint16 &&
1266 !(result_type == DataType::Type::kInt64 && input_type == DataType::Type::kFloat32);
1267 }
1268
CanRemoveRedundantAnd(HConstant * and_right,HConstant * shr_right,DataType::Type result_type)1269 static bool CanRemoveRedundantAnd(HConstant* and_right,
1270 HConstant* shr_right,
1271 DataType::Type result_type) {
1272 int64_t and_cst = Int64FromConstant(and_right);
1273 int64_t shr_cst = Int64FromConstant(shr_right);
1274
1275 // In the following sequence A is the input value, D is the result:
1276 // B := A & x
1277 // C := B >> r
1278 // D := TypeConv(n-bit type) C
1279
1280 // The value of D is entirely dependent on the bits [n-1:0] of C, which in turn are dependent
1281 // on bits [r+n-1:r] of B.
1282 // Therefore, if the AND does not change bits [r+n-1:r] of A then it will not affect D.
1283 // This can be checked by ensuring that bits [r+n-1:r] of the AND Constant are 1.
1284
1285 // For example: return (byte) ((value & 0xff00) >> 8)
1286 // return (byte) ((value & 0xff000000) >> 31)
1287
1288 // The mask sets bits [r+n-1:r] to 1, and all others to 0.
1289 int64_t mask = DataType::MaxValueOfIntegralType(DataType::ToUnsigned(result_type)) << shr_cst;
1290
1291 // If the result of a bitwise AND between the mask and the AND constant is the original mask, then
1292 // the AND does not change bits [r+n-1:r], meaning that it is redundant and can be removed.
1293 return ((and_cst & mask) == mask);
1294 }
1295
TryReplaceFieldOrArrayGetType(HInstruction * maybe_get,DataType::Type new_type)1296 static inline bool TryReplaceFieldOrArrayGetType(HInstruction* maybe_get, DataType::Type new_type) {
1297 if (maybe_get->IsInstanceFieldGet()) {
1298 maybe_get->AsInstanceFieldGet()->SetType(new_type);
1299 return true;
1300 } else if (maybe_get->IsStaticFieldGet()) {
1301 maybe_get->AsStaticFieldGet()->SetType(new_type);
1302 return true;
1303 } else if (maybe_get->IsArrayGet() && !maybe_get->AsArrayGet()->IsStringCharAt()) {
1304 maybe_get->AsArrayGet()->SetType(new_type);
1305 return true;
1306 } else {
1307 return false;
1308 }
1309 }
1310
1311 // The type conversion is only used for storing into a field/element of the
1312 // same/narrower size.
IsTypeConversionForStoringIntoNoWiderFieldOnly(HTypeConversion * type_conversion)1313 static bool IsTypeConversionForStoringIntoNoWiderFieldOnly(HTypeConversion* type_conversion) {
1314 if (type_conversion->HasEnvironmentUses()) {
1315 return false;
1316 }
1317 DataType::Type input_type = type_conversion->GetInputType();
1318 DataType::Type result_type = type_conversion->GetResultType();
1319 if (!DataType::IsIntegralType(input_type) ||
1320 !DataType::IsIntegralType(result_type) ||
1321 input_type == DataType::Type::kInt64 ||
1322 result_type == DataType::Type::kInt64) {
1323 // Type conversion is needed if non-integer types are involved, or 64-bit
1324 // types are involved, which may use different number of registers.
1325 return false;
1326 }
1327 if (DataType::Size(input_type) >= DataType::Size(result_type)) {
1328 // Type conversion is not necessary when storing to a field/element of the
1329 // same/smaller size.
1330 } else {
1331 // We do not handle this case here.
1332 return false;
1333 }
1334
1335 // Check if the converted value is only used for storing into heap.
1336 for (const HUseListNode<HInstruction*>& use : type_conversion->GetUses()) {
1337 HInstruction* instruction = use.GetUser();
1338 if (instruction->IsInstanceFieldSet() &&
1339 instruction->AsInstanceFieldSet()->GetFieldType() == result_type) {
1340 DCHECK_EQ(instruction->AsInstanceFieldSet()->GetValue(), type_conversion);
1341 continue;
1342 }
1343 if (instruction->IsStaticFieldSet() &&
1344 instruction->AsStaticFieldSet()->GetFieldType() == result_type) {
1345 DCHECK_EQ(instruction->AsStaticFieldSet()->GetValue(), type_conversion);
1346 continue;
1347 }
1348 if (instruction->IsArraySet() &&
1349 instruction->AsArraySet()->GetComponentType() == result_type &&
1350 // not index use.
1351 instruction->AsArraySet()->GetIndex() != type_conversion) {
1352 DCHECK_EQ(instruction->AsArraySet()->GetValue(), type_conversion);
1353 continue;
1354 }
1355 // The use is not as a store value, or the field/element type is not the
1356 // same as the result_type, keep the type conversion.
1357 return false;
1358 }
1359 // Codegen automatically handles the type conversion during the store.
1360 return true;
1361 }
1362
VisitTypeConversion(HTypeConversion * instruction)1363 void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) {
1364 HInstruction* input = instruction->GetInput();
1365 DataType::Type input_type = input->GetType();
1366 DataType::Type result_type = instruction->GetResultType();
1367 if (instruction->IsImplicitConversion()) {
1368 instruction->ReplaceWith(input);
1369 instruction->GetBlock()->RemoveInstruction(instruction);
1370 RecordSimplification();
1371 return;
1372 }
1373
1374 if (input->IsTypeConversion()) {
1375 HTypeConversion* input_conversion = input->AsTypeConversion();
1376 HInstruction* original_input = input_conversion->GetInput();
1377 DataType::Type original_type = original_input->GetType();
1378
1379 // When the first conversion is lossless, a direct conversion from the original type
1380 // to the final type yields the same result, even for a lossy second conversion, for
1381 // example float->double->int or int->double->float.
1382 bool is_first_conversion_lossless = IsTypeConversionLossless(original_type, input_type);
1383
1384 // For integral conversions, see if the first conversion loses only bits that the second
1385 // doesn't need, i.e. the final type is no wider than the intermediate. If so, direct
1386 // conversion yields the same result, for example long->int->short or int->char->short.
1387 bool integral_conversions_with_non_widening_second =
1388 DataType::IsIntegralType(input_type) &&
1389 DataType::IsIntegralType(original_type) &&
1390 DataType::IsIntegralType(result_type) &&
1391 DataType::Size(result_type) <= DataType::Size(input_type);
1392
1393 if (is_first_conversion_lossless || integral_conversions_with_non_widening_second) {
1394 // If the merged conversion is implicit, do the simplification unconditionally.
1395 if (DataType::IsTypeConversionImplicit(original_type, result_type)) {
1396 instruction->ReplaceWith(original_input);
1397 instruction->GetBlock()->RemoveInstruction(instruction);
1398 if (!input_conversion->HasUses()) {
1399 // Don't wait for DCE.
1400 input_conversion->GetBlock()->RemoveInstruction(input_conversion);
1401 }
1402 RecordSimplification();
1403 return;
1404 }
1405 // Otherwise simplify only if the first conversion has no other use.
1406 if (input_conversion->HasOnlyOneNonEnvironmentUse()) {
1407 input_conversion->ReplaceWith(original_input);
1408 input_conversion->GetBlock()->RemoveInstruction(input_conversion);
1409 RecordSimplification();
1410 return;
1411 }
1412 }
1413 } else if (input->IsShr() && DataType::IsIntegralType(result_type) &&
1414 // Optimization only applies to lossy Type Conversions.
1415 !IsTypeConversionLossless(input_type, result_type)) {
1416 DCHECK(DataType::IsIntegralType(input_type));
1417 HShr* shr_op = input->AsShr();
1418 HConstant* shr_right = shr_op->GetConstantRight();
1419 HInstruction* shr_left = shr_op->GetLeastConstantLeft();
1420 if (shr_right != nullptr && shr_left->IsAnd()) {
1421 // Optimization needs AND -> SHR -> TypeConversion pattern.
1422 HAnd* and_op = shr_left->AsAnd();
1423 HConstant* and_right = and_op->GetConstantRight();
1424 HInstruction* and_left = and_op->GetLeastConstantLeft();
1425 if (and_right != nullptr &&
1426 !DataType::IsUnsignedType(and_left->GetType()) &&
1427 !DataType::IsUnsignedType(result_type) &&
1428 !DataType::IsUnsignedType(and_right->GetType()) &&
1429 (DataType::Size(and_left->GetType()) < 8) &&
1430 (DataType::Size(result_type) == 1)) {
1431 // TODO: Support Unsigned Types.
1432 // TODO: Support Long Types.
1433 // TODO: Support result types other than byte.
1434 if (and_op->HasOnlyOneNonEnvironmentUse() &&
1435 CanRemoveRedundantAnd(and_right, shr_right, result_type)) {
1436 and_op->ReplaceWith(and_left);
1437 and_op->GetBlock()->RemoveInstruction(and_op);
1438 RecordSimplification();
1439 return;
1440 }
1441 }
1442 }
1443 } else if (input->IsAnd() && DataType::IsIntegralType(result_type)) {
1444 DCHECK(DataType::IsIntegralType(input_type));
1445 HAnd* input_and = input->AsAnd();
1446 HConstant* constant = input_and->GetConstantRight();
1447 if (constant != nullptr) {
1448 int64_t value = Int64FromConstant(constant);
1449 DCHECK_NE(value, -1); // "& -1" would have been optimized away in VisitAnd().
1450 size_t trailing_ones = CTZ(~static_cast<uint64_t>(value));
1451 if (trailing_ones >= kBitsPerByte * DataType::Size(result_type)) {
1452 // The `HAnd` is useless, for example in `(byte) (x & 0xff)`, get rid of it.
1453 HInstruction* original_input = input_and->GetLeastConstantLeft();
1454 if (DataType::IsTypeConversionImplicit(original_input->GetType(), result_type)) {
1455 instruction->ReplaceWith(original_input);
1456 instruction->GetBlock()->RemoveInstruction(instruction);
1457 RecordSimplification();
1458 return;
1459 } else if (input->HasOnlyOneNonEnvironmentUse()) {
1460 input_and->ReplaceWith(original_input);
1461 input_and->GetBlock()->RemoveInstruction(input_and);
1462 RecordSimplification();
1463 return;
1464 }
1465 }
1466 }
1467 } else if (input->HasOnlyOneNonEnvironmentUse() &&
1468 ((input_type == DataType::Type::kInt8 && result_type == DataType::Type::kUint8) ||
1469 (input_type == DataType::Type::kUint8 && result_type == DataType::Type::kInt8) ||
1470 (input_type == DataType::Type::kInt16 && result_type == DataType::Type::kUint16) ||
1471 (input_type == DataType::Type::kUint16 && result_type == DataType::Type::kInt16))) {
1472 // Try to modify the type of the load to `result_type` and remove the explicit type conversion.
1473 if (TryReplaceFieldOrArrayGetType(input, result_type)) {
1474 instruction->ReplaceWith(input);
1475 instruction->GetBlock()->RemoveInstruction(instruction);
1476 RecordSimplification();
1477 return;
1478 }
1479 }
1480
1481 if (IsTypeConversionForStoringIntoNoWiderFieldOnly(instruction)) {
1482 instruction->ReplaceWith(input);
1483 instruction->GetBlock()->RemoveInstruction(instruction);
1484 RecordSimplification();
1485 return;
1486 }
1487 }
1488
VisitAbs(HAbs * instruction)1489 void InstructionSimplifierVisitor::VisitAbs(HAbs* instruction) {
1490 HInstruction* input = instruction->GetInput();
1491 if (DataType::IsZeroExtension(input->GetType(), instruction->GetResultType())) {
1492 // Zero extension from narrow to wide can never set sign bit in the wider
1493 // operand, making the subsequent Abs redundant (e.g., abs(b & 0xff) for byte b).
1494 instruction->ReplaceWith(input);
1495 instruction->GetBlock()->RemoveInstruction(instruction);
1496 RecordSimplification();
1497 }
1498 }
1499
VisitAdd(HAdd * instruction)1500 void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) {
1501 HConstant* input_cst = instruction->GetConstantRight();
1502 HInstruction* input_other = instruction->GetLeastConstantLeft();
1503 bool integral_type = DataType::IsIntegralType(instruction->GetType());
1504 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) {
1505 // Replace code looking like
1506 // ADD dst, src, 0
1507 // with
1508 // src
1509 // Note that we cannot optimize `x + 0.0` to `x` for floating-point. When
1510 // `x` is `-0.0`, the former expression yields `0.0`, while the later
1511 // yields `-0.0`.
1512 if (integral_type) {
1513 instruction->ReplaceWith(input_other);
1514 instruction->GetBlock()->RemoveInstruction(instruction);
1515 RecordSimplification();
1516 return;
1517 }
1518 }
1519
1520 HInstruction* left = instruction->GetLeft();
1521 HInstruction* right = instruction->GetRight();
1522 bool left_is_neg = left->IsNeg();
1523 bool right_is_neg = right->IsNeg();
1524
1525 if (left_is_neg && right_is_neg) {
1526 if (TryMoveNegOnInputsAfterBinop(instruction)) {
1527 return;
1528 }
1529 }
1530
1531 if (left_is_neg != right_is_neg) {
1532 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg();
1533 if (neg->HasOnlyOneNonEnvironmentUse()) {
1534 // Replace code looking like
1535 // NEG tmp, b
1536 // ADD dst, a, tmp
1537 // with
1538 // SUB dst, a, b
1539 // We do not perform the optimization if the input negation has environment
1540 // uses or multiple non-environment uses as it could lead to worse code. In
1541 // particular, we do not want the live range of `b` to be extended if we are
1542 // not sure the initial 'NEG' instruction can be removed.
1543 HInstruction* other = left_is_neg ? right : left;
1544 HSub* sub =
1545 new(GetGraph()->GetAllocator()) HSub(instruction->GetType(), other, neg->GetInput());
1546 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub);
1547 RecordSimplification();
1548 neg->GetBlock()->RemoveInstruction(neg);
1549 return;
1550 }
1551 }
1552
1553 if (TryReplaceWithRotate(instruction)) {
1554 return;
1555 }
1556
1557 // TryHandleAssociativeAndCommutativeOperation() does not remove its input,
1558 // so no need to return.
1559 TryHandleAssociativeAndCommutativeOperation(instruction);
1560
1561 if ((left->IsSub() || right->IsSub()) &&
1562 TrySubtractionChainSimplification(instruction)) {
1563 return;
1564 }
1565
1566 if (integral_type) {
1567 // Replace code patterns looking like
1568 // SUB dst1, x, y SUB dst1, x, y
1569 // ADD dst2, dst1, y ADD dst2, y, dst1
1570 // with
1571 // SUB dst1, x, y
1572 // ADD instruction is not needed in this case, we may use
1573 // one of inputs of SUB instead.
1574 if (left->IsSub() && left->InputAt(1) == right) {
1575 instruction->ReplaceWith(left->InputAt(0));
1576 RecordSimplification();
1577 instruction->GetBlock()->RemoveInstruction(instruction);
1578 return;
1579 } else if (right->IsSub() && right->InputAt(1) == left) {
1580 instruction->ReplaceWith(right->InputAt(0));
1581 RecordSimplification();
1582 instruction->GetBlock()->RemoveInstruction(instruction);
1583 return;
1584 }
1585 }
1586 }
1587
VisitAnd(HAnd * instruction)1588 void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) {
1589 DCHECK(DataType::IsIntegralType(instruction->GetType()));
1590 HConstant* input_cst = instruction->GetConstantRight();
1591 HInstruction* input_other = instruction->GetLeastConstantLeft();
1592
1593 if (input_cst != nullptr) {
1594 int64_t value = Int64FromConstant(input_cst);
1595 if (value == -1 ||
1596 // Similar cases under zero extension.
1597 (DataType::IsUnsignedType(input_other->GetType()) &&
1598 ((DataType::MaxValueOfIntegralType(input_other->GetType()) & ~value) == 0))) {
1599 // Replace code looking like
1600 // AND dst, src, 0xFFF...FF
1601 // with
1602 // src
1603 instruction->ReplaceWith(input_other);
1604 instruction->GetBlock()->RemoveInstruction(instruction);
1605 RecordSimplification();
1606 return;
1607 }
1608 if (input_other->IsTypeConversion() &&
1609 input_other->GetType() == DataType::Type::kInt64 &&
1610 DataType::IsIntegralType(input_other->InputAt(0)->GetType()) &&
1611 IsInt<32>(value) &&
1612 input_other->HasOnlyOneNonEnvironmentUse()) {
1613 // The AND can be reordered before the TypeConversion. Replace
1614 // LongConstant cst, <32-bit-constant-sign-extended-to-64-bits>
1615 // TypeConversion<Int64> tmp, src
1616 // AND dst, tmp, cst
1617 // with
1618 // IntConstant cst, <32-bit-constant>
1619 // AND tmp, src, cst
1620 // TypeConversion<Int64> dst, tmp
1621 // This helps 32-bit targets and does not hurt 64-bit targets.
1622 // This also simplifies detection of other patterns, such as Uint8 loads.
1623 HInstruction* new_and_input = input_other->InputAt(0);
1624 // Implicit conversion Int64->Int64 would have been removed previously.
1625 DCHECK_NE(new_and_input->GetType(), DataType::Type::kInt64);
1626 HConstant* new_const = GetGraph()->GetConstant(DataType::Type::kInt32, value);
1627 HAnd* new_and =
1628 new (GetGraph()->GetAllocator()) HAnd(DataType::Type::kInt32, new_and_input, new_const);
1629 instruction->GetBlock()->InsertInstructionBefore(new_and, instruction);
1630 HTypeConversion* new_conversion =
1631 new (GetGraph()->GetAllocator()) HTypeConversion(DataType::Type::kInt64, new_and);
1632 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_conversion);
1633 input_other->GetBlock()->RemoveInstruction(input_other);
1634 RecordSimplification();
1635 // Try to process the new And now, do not wait for the next round of simplifications.
1636 instruction = new_and;
1637 input_other = new_and_input;
1638 }
1639 // Eliminate And from UShr+And if the And-mask contains all the bits that
1640 // can be non-zero after UShr. Transform Shr+And to UShr if the And-mask
1641 // precisely clears the shifted-in sign bits.
1642 if ((input_other->IsUShr() || input_other->IsShr()) && input_other->InputAt(1)->IsConstant()) {
1643 size_t reg_bits = (instruction->GetResultType() == DataType::Type::kInt64) ? 64 : 32;
1644 size_t shift = Int64FromConstant(input_other->InputAt(1)->AsConstant()) & (reg_bits - 1);
1645 size_t num_tail_bits_set = CTZ(value + 1);
1646 if ((num_tail_bits_set >= reg_bits - shift) && input_other->IsUShr()) {
1647 // This AND clears only bits known to be clear, for example "(x >>> 24) & 0xff".
1648 instruction->ReplaceWith(input_other);
1649 instruction->GetBlock()->RemoveInstruction(instruction);
1650 RecordSimplification();
1651 return;
1652 } else if ((num_tail_bits_set == reg_bits - shift) && IsPowerOfTwo(value + 1) &&
1653 input_other->HasOnlyOneNonEnvironmentUse()) {
1654 DCHECK(input_other->IsShr()); // For UShr, we would have taken the branch above.
1655 // Replace SHR+AND with USHR, for example "(x >> 24) & 0xff" -> "x >>> 24".
1656 HUShr* ushr = new (GetGraph()->GetAllocator()) HUShr(instruction->GetType(),
1657 input_other->InputAt(0),
1658 input_other->InputAt(1),
1659 input_other->GetDexPc());
1660 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, ushr);
1661 input_other->GetBlock()->RemoveInstruction(input_other);
1662 RecordSimplification();
1663 return;
1664 }
1665 }
1666 if ((value == 0xff || value == 0xffff) && instruction->GetType() != DataType::Type::kInt64) {
1667 // Transform AND to a type conversion to Uint8/Uint16. If `input_other` is a field
1668 // or array Get with only a single use, short-circuit the subsequent simplification
1669 // of the Get+TypeConversion and change the Get's type to `new_type` instead.
1670 DataType::Type new_type = (value == 0xff) ? DataType::Type::kUint8 : DataType::Type::kUint16;
1671 DataType::Type find_type = (value == 0xff) ? DataType::Type::kInt8 : DataType::Type::kInt16;
1672 if (input_other->GetType() == find_type &&
1673 input_other->HasOnlyOneNonEnvironmentUse() &&
1674 TryReplaceFieldOrArrayGetType(input_other, new_type)) {
1675 instruction->ReplaceWith(input_other);
1676 instruction->GetBlock()->RemoveInstruction(instruction);
1677 } else if (DataType::IsTypeConversionImplicit(input_other->GetType(), new_type)) {
1678 instruction->ReplaceWith(input_other);
1679 instruction->GetBlock()->RemoveInstruction(instruction);
1680 } else {
1681 HTypeConversion* type_conversion = new (GetGraph()->GetAllocator()) HTypeConversion(
1682 new_type, input_other, instruction->GetDexPc());
1683 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, type_conversion);
1684 }
1685 RecordSimplification();
1686 return;
1687 }
1688 }
1689
1690 // We assume that GVN has run before, so we only perform a pointer comparison.
1691 // If for some reason the values are equal but the pointers are different, we
1692 // are still correct and only miss an optimization opportunity.
1693 if (instruction->GetLeft() == instruction->GetRight()) {
1694 // Replace code looking like
1695 // AND dst, src, src
1696 // with
1697 // src
1698 instruction->ReplaceWith(instruction->GetLeft());
1699 instruction->GetBlock()->RemoveInstruction(instruction);
1700 RecordSimplification();
1701 return;
1702 }
1703
1704 if (TryDeMorganNegationFactoring(instruction)) {
1705 return;
1706 }
1707
1708 // TryHandleAssociativeAndCommutativeOperation() does not remove its input,
1709 // so no need to return.
1710 TryHandleAssociativeAndCommutativeOperation(instruction);
1711 }
1712
VisitGreaterThan(HGreaterThan * condition)1713 void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
1714 VisitCondition(condition);
1715 }
1716
VisitGreaterThanOrEqual(HGreaterThanOrEqual * condition)1717 void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) {
1718 VisitCondition(condition);
1719 }
1720
VisitLessThan(HLessThan * condition)1721 void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) {
1722 VisitCondition(condition);
1723 }
1724
VisitLessThanOrEqual(HLessThanOrEqual * condition)1725 void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) {
1726 VisitCondition(condition);
1727 }
1728
VisitBelow(HBelow * condition)1729 void InstructionSimplifierVisitor::VisitBelow(HBelow* condition) {
1730 VisitCondition(condition);
1731 }
1732
VisitBelowOrEqual(HBelowOrEqual * condition)1733 void InstructionSimplifierVisitor::VisitBelowOrEqual(HBelowOrEqual* condition) {
1734 VisitCondition(condition);
1735 }
1736
VisitAbove(HAbove * condition)1737 void InstructionSimplifierVisitor::VisitAbove(HAbove* condition) {
1738 VisitCondition(condition);
1739 }
1740
VisitAboveOrEqual(HAboveOrEqual * condition)1741 void InstructionSimplifierVisitor::VisitAboveOrEqual(HAboveOrEqual* condition) {
1742 VisitCondition(condition);
1743 }
1744
1745 // Recognize the following pattern:
1746 // obj.getClass() ==/!= Foo.class
1747 // And replace it with a constant value if the type of `obj` is statically known.
RecognizeAndSimplifyClassCheck(HCondition * condition)1748 static bool RecognizeAndSimplifyClassCheck(HCondition* condition) {
1749 HInstruction* input_one = condition->InputAt(0);
1750 HInstruction* input_two = condition->InputAt(1);
1751 HLoadClass* load_class = input_one->IsLoadClass()
1752 ? input_one->AsLoadClass()
1753 : input_two->AsLoadClassOrNull();
1754 if (load_class == nullptr) {
1755 return false;
1756 }
1757
1758 ReferenceTypeInfo class_rti = load_class->GetLoadedClassRTI();
1759 if (!class_rti.IsValid()) {
1760 // Unresolved class.
1761 return false;
1762 }
1763
1764 HInstanceFieldGet* field_get = (load_class == input_one)
1765 ? input_two->AsInstanceFieldGetOrNull()
1766 : input_one->AsInstanceFieldGetOrNull();
1767 if (field_get == nullptr) {
1768 return false;
1769 }
1770
1771 HInstruction* receiver = field_get->InputAt(0);
1772 ReferenceTypeInfo receiver_type = receiver->GetReferenceTypeInfo();
1773 if (!receiver_type.IsExact()) {
1774 return false;
1775 }
1776
1777 {
1778 ScopedObjectAccess soa(Thread::Current());
1779 ArtField* field = GetClassRoot<mirror::Object>()->GetInstanceField(0);
1780 DCHECK_EQ(std::string(field->GetName()), "shadow$_klass_");
1781 if (field_get->GetFieldInfo().GetField() != field) {
1782 return false;
1783 }
1784
1785 // We can replace the compare.
1786 int value = 0;
1787 if (receiver_type.IsEqual(class_rti)) {
1788 value = condition->IsEqual() ? 1 : 0;
1789 } else {
1790 value = condition->IsNotEqual() ? 1 : 0;
1791 }
1792 condition->ReplaceWith(condition->GetBlock()->GetGraph()->GetIntConstant(value));
1793 return true;
1794 }
1795 }
1796
VisitCondition(HCondition * condition)1797 void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) {
1798 if (condition->IsEqual() || condition->IsNotEqual()) {
1799 if (RecognizeAndSimplifyClassCheck(condition)) {
1800 return;
1801 }
1802 }
1803
1804 // Reverse condition if left is constant. Our code generators prefer constant
1805 // on the right hand side.
1806 if (condition->GetLeft()->IsConstant() && !condition->GetRight()->IsConstant()) {
1807 HBasicBlock* block = condition->GetBlock();
1808 HCondition* replacement =
1809 GetOppositeConditionSwapOps(block->GetGraph()->GetAllocator(), condition);
1810 // If it is a fp we must set the opposite bias.
1811 if (replacement != nullptr) {
1812 if (condition->IsLtBias()) {
1813 replacement->SetBias(ComparisonBias::kGtBias);
1814 } else if (condition->IsGtBias()) {
1815 replacement->SetBias(ComparisonBias::kLtBias);
1816 }
1817 block->ReplaceAndRemoveInstructionWith(condition, replacement);
1818 RecordSimplification();
1819
1820 condition = replacement;
1821 }
1822 }
1823
1824 HInstruction* left = condition->GetLeft();
1825 HInstruction* right = condition->GetRight();
1826
1827 // Try to fold an HCompare into this HCondition.
1828
1829 // We can only replace an HCondition which compares a Compare to 0.
1830 // Both 'dx' and 'jack' generate a compare to 0 when compiling a
1831 // condition with a long, float or double comparison as input.
1832 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) {
1833 // Conversion is not possible.
1834 return;
1835 }
1836
1837 // Is the Compare only used for this purpose?
1838 if (!left->GetUses().HasExactlyOneElement()) {
1839 // Someone else also wants the result of the compare.
1840 return;
1841 }
1842
1843 if (!left->GetEnvUses().empty()) {
1844 // There is a reference to the compare result in an environment. Do we really need it?
1845 if (GetGraph()->IsDebuggable()) {
1846 return;
1847 }
1848
1849 // We have to ensure that there are no deopt points in the sequence.
1850 if (left->HasAnyEnvironmentUseBefore(condition)) {
1851 return;
1852 }
1853 }
1854
1855 // Clean up any environment uses from the HCompare, if any.
1856 left->RemoveEnvironmentUsers();
1857
1858 // We have decided to fold the HCompare into the HCondition. Transfer the information.
1859 condition->SetBias(left->AsCompare()->GetBias());
1860
1861 // Replace the operands of the HCondition.
1862 condition->ReplaceInput(left->InputAt(0), 0);
1863 condition->ReplaceInput(left->InputAt(1), 1);
1864
1865 // Remove the HCompare.
1866 left->GetBlock()->RemoveInstruction(left);
1867
1868 RecordSimplification();
1869 }
1870
1871 // Return whether x / divisor == x * (1.0f / divisor), for every float x.
CanDivideByReciprocalMultiplyFloat(int32_t divisor)1872 static constexpr bool CanDivideByReciprocalMultiplyFloat(int32_t divisor) {
1873 // True, if the most significant bits of divisor are 0.
1874 return ((divisor & 0x7fffff) == 0);
1875 }
1876
1877 // Return whether x / divisor == x * (1.0 / divisor), for every double x.
CanDivideByReciprocalMultiplyDouble(int64_t divisor)1878 static constexpr bool CanDivideByReciprocalMultiplyDouble(int64_t divisor) {
1879 // True, if the most significant bits of divisor are 0.
1880 return ((divisor & ((UINT64_C(1) << 52) - 1)) == 0);
1881 }
1882
VisitDiv(HDiv * instruction)1883 void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) {
1884 HConstant* input_cst = instruction->GetConstantRight();
1885 HInstruction* input_other = instruction->GetLeastConstantLeft();
1886 DataType::Type type = instruction->GetType();
1887
1888 if ((input_cst != nullptr) && input_cst->IsOne()) {
1889 // Replace code looking like
1890 // DIV dst, src, 1
1891 // with
1892 // src
1893 instruction->ReplaceWith(input_other);
1894 instruction->GetBlock()->RemoveInstruction(instruction);
1895 RecordSimplification();
1896 return;
1897 }
1898
1899 if ((input_cst != nullptr) && input_cst->IsMinusOne()) {
1900 // Replace code looking like
1901 // DIV dst, src, -1
1902 // with
1903 // NEG dst, src
1904 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
1905 instruction, new (GetGraph()->GetAllocator()) HNeg(type, input_other));
1906 RecordSimplification();
1907 return;
1908 }
1909
1910 if ((input_cst != nullptr) && DataType::IsFloatingPointType(type)) {
1911 // Try replacing code looking like
1912 // DIV dst, src, constant
1913 // with
1914 // MUL dst, src, 1 / constant
1915 HConstant* reciprocal = nullptr;
1916 if (type == DataType::Type::kFloat64) {
1917 double value = input_cst->AsDoubleConstant()->GetValue();
1918 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) {
1919 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value);
1920 }
1921 } else {
1922 DCHECK_EQ(type, DataType::Type::kFloat32);
1923 float value = input_cst->AsFloatConstant()->GetValue();
1924 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) {
1925 reciprocal = GetGraph()->GetFloatConstant(1.0f / value);
1926 }
1927 }
1928
1929 if (reciprocal != nullptr) {
1930 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
1931 instruction, new (GetGraph()->GetAllocator()) HMul(type, input_other, reciprocal));
1932 RecordSimplification();
1933 return;
1934 }
1935 }
1936 }
1937
1938
1939 // Search HDiv having the specified dividend and divisor which is in the specified basic block.
1940 // Return nullptr if nothing has been found.
FindDivWithInputsInBasicBlock(HInstruction * dividend,HInstruction * divisor,HBasicBlock * basic_block)1941 static HDiv* FindDivWithInputsInBasicBlock(HInstruction* dividend,
1942 HInstruction* divisor,
1943 HBasicBlock* basic_block) {
1944 for (const HUseListNode<HInstruction*>& use : dividend->GetUses()) {
1945 HInstruction* user = use.GetUser();
1946 if (user->GetBlock() == basic_block &&
1947 user->IsDiv() &&
1948 user->InputAt(0) == dividend &&
1949 user->InputAt(1) == divisor) {
1950 return user->AsDiv();
1951 }
1952 }
1953 return nullptr;
1954 }
1955
1956 // If there is Div with the same inputs as Rem and in the same basic block, it can be reused.
1957 // Rem is replaced with Mul+Sub which use the found Div.
TryToReuseDiv(HRem * rem)1958 void InstructionSimplifierVisitor::TryToReuseDiv(HRem* rem) {
1959 // As the optimization replaces Rem with Mul+Sub they prevent some loop optimizations
1960 // if the Rem is in a loop.
1961 // Check if it is allowed to optimize such Rems.
1962 if (rem->IsInLoop() && be_loop_friendly_) {
1963 return;
1964 }
1965 DataType::Type type = rem->GetResultType();
1966 if (!DataType::IsIntOrLongType(type)) {
1967 return;
1968 }
1969
1970 HBasicBlock* basic_block = rem->GetBlock();
1971 HInstruction* dividend = rem->GetLeft();
1972 HInstruction* divisor = rem->GetRight();
1973
1974 if (divisor->IsConstant()) {
1975 HConstant* input_cst = rem->GetConstantRight();
1976 DCHECK(input_cst->IsIntConstant() || input_cst->IsLongConstant());
1977 int64_t cst_value = Int64FromConstant(input_cst);
1978 if (cst_value == std::numeric_limits<int64_t>::min() || IsPowerOfTwo(std::abs(cst_value))) {
1979 // Such cases are usually handled in the code generator because they don't need Div at all.
1980 return;
1981 }
1982 }
1983
1984 HDiv* quotient = FindDivWithInputsInBasicBlock(dividend, divisor, basic_block);
1985 if (quotient == nullptr) {
1986 return;
1987 }
1988 if (!quotient->StrictlyDominates(rem)) {
1989 quotient->MoveBefore(rem);
1990 }
1991
1992 ArenaAllocator* allocator = GetGraph()->GetAllocator();
1993 HInstruction* mul = new (allocator) HMul(type, quotient, divisor);
1994 basic_block->InsertInstructionBefore(mul, rem);
1995 HInstruction* sub = new (allocator) HSub(type, dividend, mul);
1996 basic_block->InsertInstructionBefore(sub, rem);
1997 rem->ReplaceWith(sub);
1998 basic_block->RemoveInstruction(rem);
1999 RecordSimplification();
2000 }
2001
VisitRem(HRem * rem)2002 void InstructionSimplifierVisitor::VisitRem(HRem* rem) {
2003 TryToReuseDiv(rem);
2004 }
2005
VisitMul(HMul * instruction)2006 void InstructionSimplifierVisitor::VisitMul(HMul* instruction) {
2007 HConstant* input_cst = instruction->GetConstantRight();
2008 HInstruction* input_other = instruction->GetLeastConstantLeft();
2009 DataType::Type type = instruction->GetType();
2010 HBasicBlock* block = instruction->GetBlock();
2011 ArenaAllocator* allocator = GetGraph()->GetAllocator();
2012
2013 if (input_cst == nullptr) {
2014 return;
2015 }
2016
2017 if (input_cst->IsOne()) {
2018 // Replace code looking like
2019 // MUL dst, src, 1
2020 // with
2021 // src
2022 instruction->ReplaceWith(input_other);
2023 instruction->GetBlock()->RemoveInstruction(instruction);
2024 RecordSimplification();
2025 return;
2026 }
2027
2028 if (input_cst->IsMinusOne() &&
2029 (DataType::IsFloatingPointType(type) || DataType::IsIntOrLongType(type))) {
2030 // Replace code looking like
2031 // MUL dst, src, -1
2032 // with
2033 // NEG dst, src
2034 HNeg* neg = new (allocator) HNeg(type, input_other);
2035 block->ReplaceAndRemoveInstructionWith(instruction, neg);
2036 RecordSimplification();
2037 return;
2038 }
2039
2040 if (DataType::IsFloatingPointType(type) &&
2041 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) ||
2042 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) {
2043 // Replace code looking like
2044 // FP_MUL dst, src, 2.0
2045 // with
2046 // FP_ADD dst, src, src
2047 // The 'int' and 'long' cases are handled below.
2048 block->ReplaceAndRemoveInstructionWith(instruction,
2049 new (allocator) HAdd(type, input_other, input_other));
2050 RecordSimplification();
2051 return;
2052 }
2053
2054 if (DataType::IsIntOrLongType(type)) {
2055 int64_t factor = Int64FromConstant(input_cst);
2056 // Even though constant propagation also takes care of the zero case, other
2057 // optimizations can lead to having a zero multiplication.
2058 if (factor == 0) {
2059 // Replace code looking like
2060 // MUL dst, src, 0
2061 // with
2062 // 0
2063 instruction->ReplaceWith(input_cst);
2064 instruction->GetBlock()->RemoveInstruction(instruction);
2065 RecordSimplification();
2066 return;
2067 } else if (IsPowerOfTwo(factor)) {
2068 // Replace code looking like
2069 // MUL dst, src, pow_of_2
2070 // with
2071 // SHL dst, src, log2(pow_of_2)
2072 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor));
2073 HShl* shl = new (allocator) HShl(type, input_other, shift);
2074 block->ReplaceAndRemoveInstructionWith(instruction, shl);
2075 RecordSimplification();
2076 return;
2077 } else if (IsPowerOfTwo(factor - 1)) {
2078 // Transform code looking like
2079 // MUL dst, src, (2^n + 1)
2080 // into
2081 // SHL tmp, src, n
2082 // ADD dst, src, tmp
2083 HShl* shl = new (allocator) HShl(type,
2084 input_other,
2085 GetGraph()->GetIntConstant(WhichPowerOf2(factor - 1)));
2086 HAdd* add = new (allocator) HAdd(type, input_other, shl);
2087
2088 block->InsertInstructionBefore(shl, instruction);
2089 block->ReplaceAndRemoveInstructionWith(instruction, add);
2090 RecordSimplification();
2091 return;
2092 } else if (IsPowerOfTwo(factor + 1)) {
2093 // Transform code looking like
2094 // MUL dst, src, (2^n - 1)
2095 // into
2096 // SHL tmp, src, n
2097 // SUB dst, tmp, src
2098 HShl* shl = new (allocator) HShl(type,
2099 input_other,
2100 GetGraph()->GetIntConstant(WhichPowerOf2(factor + 1)));
2101 HSub* sub = new (allocator) HSub(type, shl, input_other);
2102
2103 block->InsertInstructionBefore(shl, instruction);
2104 block->ReplaceAndRemoveInstructionWith(instruction, sub);
2105 RecordSimplification();
2106 return;
2107 }
2108 }
2109
2110 // TryHandleAssociativeAndCommutativeOperation() does not remove its input,
2111 // so no need to return.
2112 TryHandleAssociativeAndCommutativeOperation(instruction);
2113 }
2114
VisitNeg(HNeg * instruction)2115 void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) {
2116 HInstruction* input = instruction->GetInput();
2117 if (input->IsNeg()) {
2118 // Replace code looking like
2119 // NEG tmp, src
2120 // NEG dst, tmp
2121 // with
2122 // src
2123 HNeg* previous_neg = input->AsNeg();
2124 instruction->ReplaceWith(previous_neg->GetInput());
2125 instruction->GetBlock()->RemoveInstruction(instruction);
2126 // We perform the optimization even if the input negation has environment
2127 // uses since it allows removing the current instruction. But we only delete
2128 // the input negation only if it is does not have any uses left.
2129 if (!previous_neg->HasUses()) {
2130 previous_neg->GetBlock()->RemoveInstruction(previous_neg);
2131 }
2132 RecordSimplification();
2133 return;
2134 }
2135
2136 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() &&
2137 !DataType::IsFloatingPointType(input->GetType())) {
2138 // Replace code looking like
2139 // SUB tmp, a, b
2140 // NEG dst, tmp
2141 // with
2142 // SUB dst, b, a
2143 // We do not perform the optimization if the input subtraction has
2144 // environment uses or multiple non-environment uses as it could lead to
2145 // worse code. In particular, we do not want the live ranges of `a` and `b`
2146 // to be extended if we are not sure the initial 'SUB' instruction can be
2147 // removed.
2148 // We do not perform optimization for fp because we could lose the sign of zero.
2149 HSub* sub = input->AsSub();
2150 HSub* new_sub = new (GetGraph()->GetAllocator()) HSub(
2151 instruction->GetType(), sub->GetRight(), sub->GetLeft());
2152 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub);
2153 if (!sub->HasUses()) {
2154 sub->GetBlock()->RemoveInstruction(sub);
2155 }
2156 RecordSimplification();
2157 }
2158 }
2159
VisitNot(HNot * instruction)2160 void InstructionSimplifierVisitor::VisitNot(HNot* instruction) {
2161 HInstruction* input = instruction->GetInput();
2162 if (input->IsNot()) {
2163 // Replace code looking like
2164 // NOT tmp, src
2165 // NOT dst, tmp
2166 // with
2167 // src
2168 // We perform the optimization even if the input negation has environment
2169 // uses since it allows removing the current instruction. But we only delete
2170 // the input negation only if it is does not have any uses left.
2171 HNot* previous_not = input->AsNot();
2172 instruction->ReplaceWith(previous_not->GetInput());
2173 instruction->GetBlock()->RemoveInstruction(instruction);
2174 if (!previous_not->HasUses()) {
2175 previous_not->GetBlock()->RemoveInstruction(previous_not);
2176 }
2177 RecordSimplification();
2178 }
2179 }
2180
VisitOr(HOr * instruction)2181 void InstructionSimplifierVisitor::VisitOr(HOr* instruction) {
2182 HConstant* input_cst = instruction->GetConstantRight();
2183 HInstruction* input_other = instruction->GetLeastConstantLeft();
2184
2185 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) {
2186 // Replace code looking like
2187 // OR dst, src, 0
2188 // with
2189 // src
2190 instruction->ReplaceWith(input_other);
2191 instruction->GetBlock()->RemoveInstruction(instruction);
2192 RecordSimplification();
2193 return;
2194 }
2195
2196 // We assume that GVN has run before, so we only perform a pointer comparison.
2197 // If for some reason the values are equal but the pointers are different, we
2198 // are still correct and only miss an optimization opportunity.
2199 if (instruction->GetLeft() == instruction->GetRight()) {
2200 // Replace code looking like
2201 // OR dst, src, src
2202 // with
2203 // src
2204 instruction->ReplaceWith(instruction->GetLeft());
2205 instruction->GetBlock()->RemoveInstruction(instruction);
2206 RecordSimplification();
2207 return;
2208 }
2209
2210 if (TryDeMorganNegationFactoring(instruction)) return;
2211
2212 if (TryReplaceWithRotate(instruction)) {
2213 return;
2214 }
2215
2216 // TryHandleAssociativeAndCommutativeOperation() does not remove its input,
2217 // so no need to return.
2218 TryHandleAssociativeAndCommutativeOperation(instruction);
2219 }
2220
VisitShl(HShl * instruction)2221 void InstructionSimplifierVisitor::VisitShl(HShl* instruction) {
2222 VisitShift(instruction);
2223 }
2224
VisitShr(HShr * instruction)2225 void InstructionSimplifierVisitor::VisitShr(HShr* instruction) {
2226 VisitShift(instruction);
2227 }
2228
VisitSub(HSub * instruction)2229 void InstructionSimplifierVisitor::VisitSub(HSub* instruction) {
2230 HConstant* input_cst = instruction->GetConstantRight();
2231 HInstruction* input_other = instruction->GetLeastConstantLeft();
2232
2233 DataType::Type type = instruction->GetType();
2234 if (DataType::IsFloatingPointType(type)) {
2235 return;
2236 }
2237
2238 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) {
2239 // Replace code looking like
2240 // SUB dst, src, 0
2241 // with
2242 // src
2243 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When
2244 // `x` is `-0.0`, the former expression yields `0.0`, while the later
2245 // yields `-0.0`.
2246 instruction->ReplaceWith(input_other);
2247 instruction->GetBlock()->RemoveInstruction(instruction);
2248 RecordSimplification();
2249 return;
2250 }
2251
2252 HBasicBlock* block = instruction->GetBlock();
2253 ArenaAllocator* allocator = GetGraph()->GetAllocator();
2254
2255 HInstruction* left = instruction->GetLeft();
2256 HInstruction* right = instruction->GetRight();
2257 if (left->IsConstant()) {
2258 if (Int64FromConstant(left->AsConstant()) == 0) {
2259 // Replace code looking like
2260 // SUB dst, 0, src
2261 // with
2262 // NEG dst, src
2263 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When
2264 // `x` is `0.0`, the former expression yields `0.0`, while the later
2265 // yields `-0.0`.
2266 HNeg* neg = new (allocator) HNeg(type, right);
2267 block->ReplaceAndRemoveInstructionWith(instruction, neg);
2268 RecordSimplification();
2269 return;
2270 }
2271 }
2272
2273 if (left->IsNeg() && right->IsNeg()) {
2274 if (TryMoveNegOnInputsAfterBinop(instruction)) {
2275 return;
2276 }
2277 }
2278
2279 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) {
2280 // Replace code looking like
2281 // NEG tmp, b
2282 // SUB dst, a, tmp
2283 // with
2284 // ADD dst, a, b
2285 HAdd* add = new(GetGraph()->GetAllocator()) HAdd(type, left, right->AsNeg()->GetInput());
2286 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add);
2287 RecordSimplification();
2288 right->GetBlock()->RemoveInstruction(right);
2289 return;
2290 }
2291
2292 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) {
2293 // Replace code looking like
2294 // NEG tmp, a
2295 // SUB dst, tmp, b
2296 // with
2297 // ADD tmp, a, b
2298 // NEG dst, tmp
2299 // The second version is not intrinsically better, but enables more
2300 // transformations.
2301 HAdd* add = new(GetGraph()->GetAllocator()) HAdd(type, left->AsNeg()->GetInput(), right);
2302 instruction->GetBlock()->InsertInstructionBefore(add, instruction);
2303 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(instruction->GetType(), add);
2304 instruction->GetBlock()->InsertInstructionBefore(neg, instruction);
2305 instruction->ReplaceWith(neg);
2306 instruction->GetBlock()->RemoveInstruction(instruction);
2307 RecordSimplification();
2308 left->GetBlock()->RemoveInstruction(left);
2309 return;
2310 }
2311
2312 if (TrySubtractionChainSimplification(instruction)) {
2313 return;
2314 }
2315
2316 if (left->IsAdd()) {
2317 // Cases (x + y) - y = x, and (x + y) - x = y.
2318 // Replace code patterns looking like
2319 // ADD dst1, x, y ADD dst1, x, y
2320 // SUB dst2, dst1, y SUB dst2, dst1, x
2321 // with
2322 // ADD dst1, x, y
2323 // SUB instruction is not needed in this case, we may use
2324 // one of inputs of ADD instead.
2325 // It is applicable to integral types only.
2326 HAdd* add = left->AsAdd();
2327 DCHECK(DataType::IsIntegralType(type));
2328 if (add->GetRight() == right) {
2329 instruction->ReplaceWith(add->GetLeft());
2330 RecordSimplification();
2331 instruction->GetBlock()->RemoveInstruction(instruction);
2332 return;
2333 } else if (add->GetLeft() == right) {
2334 instruction->ReplaceWith(add->GetRight());
2335 RecordSimplification();
2336 instruction->GetBlock()->RemoveInstruction(instruction);
2337 return;
2338 }
2339 } else if (right->IsAdd()) {
2340 // Cases y - (x + y) = -x, and x - (x + y) = -y.
2341 // Replace code patterns looking like
2342 // ADD dst1, x, y ADD dst1, x, y
2343 // SUB dst2, y, dst1 SUB dst2, x, dst1
2344 // with
2345 // ADD dst1, x, y ADD dst1, x, y
2346 // NEG x NEG y
2347 // SUB instruction is not needed in this case, we may use
2348 // one of inputs of ADD instead with a NEG.
2349 // It is applicable to integral types only.
2350 HAdd* add = right->AsAdd();
2351 DCHECK(DataType::IsIntegralType(type));
2352 if (add->GetRight() == left) {
2353 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(add->GetType(), add->GetLeft());
2354 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
2355 RecordSimplification();
2356 return;
2357 } else if (add->GetLeft() == left) {
2358 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(add->GetType(), add->GetRight());
2359 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
2360 RecordSimplification();
2361 return;
2362 }
2363 } else if (left->IsSub()) {
2364 // Case (x - y) - x = -y.
2365 // Replace code patterns looking like
2366 // SUB dst1, x, y
2367 // SUB dst2, dst1, x
2368 // with
2369 // SUB dst1, x, y
2370 // NEG y
2371 // The second SUB is not needed in this case, we may use the second input of the first SUB
2372 // instead with a NEG.
2373 // It is applicable to integral types only.
2374 HSub* sub = left->AsSub();
2375 DCHECK(DataType::IsIntegralType(type));
2376 if (sub->GetLeft() == right) {
2377 HNeg* neg = new (GetGraph()->GetAllocator()) HNeg(sub->GetType(), sub->GetRight());
2378 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, neg);
2379 RecordSimplification();
2380 return;
2381 }
2382 } else if (right->IsSub()) {
2383 // Case x - (x - y) = y.
2384 // Replace code patterns looking like
2385 // SUB dst1, x, y
2386 // SUB dst2, x, dst1
2387 // with
2388 // SUB dst1, x, y
2389 // The second SUB is not needed in this case, we may use the second input of the first SUB.
2390 // It is applicable to integral types only.
2391 HSub* sub = right->AsSub();
2392 DCHECK(DataType::IsIntegralType(type));
2393 if (sub->GetLeft() == left) {
2394 instruction->ReplaceWith(sub->GetRight());
2395 RecordSimplification();
2396 instruction->GetBlock()->RemoveInstruction(instruction);
2397 return;
2398 }
2399 }
2400 }
2401
VisitUShr(HUShr * instruction)2402 void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) {
2403 VisitShift(instruction);
2404 }
2405
VisitXor(HXor * instruction)2406 void InstructionSimplifierVisitor::VisitXor(HXor* instruction) {
2407 HConstant* input_cst = instruction->GetConstantRight();
2408 HInstruction* input_other = instruction->GetLeastConstantLeft();
2409
2410 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) {
2411 // Replace code looking like
2412 // XOR dst, src, 0
2413 // with
2414 // src
2415 instruction->ReplaceWith(input_other);
2416 instruction->GetBlock()->RemoveInstruction(instruction);
2417 RecordSimplification();
2418 return;
2419 }
2420
2421 if ((input_cst != nullptr) && input_cst->IsOne()
2422 && input_other->GetType() == DataType::Type::kBool) {
2423 // Replace code looking like
2424 // XOR dst, src, 1
2425 // with
2426 // BOOLEAN_NOT dst, src
2427 HBooleanNot* boolean_not = new (GetGraph()->GetAllocator()) HBooleanNot(input_other);
2428 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, boolean_not);
2429 RecordSimplification();
2430 return;
2431 }
2432
2433 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) {
2434 // Replace code looking like
2435 // XOR dst, src, 0xFFF...FF
2436 // with
2437 // NOT dst, src
2438 HNot* bitwise_not = new (GetGraph()->GetAllocator()) HNot(instruction->GetType(), input_other);
2439 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not);
2440 RecordSimplification();
2441 return;
2442 }
2443
2444 HInstruction* left = instruction->GetLeft();
2445 HInstruction* right = instruction->GetRight();
2446 if (((left->IsNot() && right->IsNot()) ||
2447 (left->IsBooleanNot() && right->IsBooleanNot())) &&
2448 left->HasOnlyOneNonEnvironmentUse() &&
2449 right->HasOnlyOneNonEnvironmentUse()) {
2450 // Replace code looking like
2451 // NOT nota, a
2452 // NOT notb, b
2453 // XOR dst, nota, notb
2454 // with
2455 // XOR dst, a, b
2456 instruction->ReplaceInput(left->InputAt(0), 0);
2457 instruction->ReplaceInput(right->InputAt(0), 1);
2458 left->GetBlock()->RemoveInstruction(left);
2459 right->GetBlock()->RemoveInstruction(right);
2460 RecordSimplification();
2461 return;
2462 }
2463
2464 if (TryReplaceWithRotate(instruction)) {
2465 return;
2466 }
2467
2468 // TryHandleAssociativeAndCommutativeOperation() does not remove its input,
2469 // so no need to return.
2470 TryHandleAssociativeAndCommutativeOperation(instruction);
2471 }
2472
SimplifyBoxUnbox(HInvoke * instruction,ArtField * field,DataType::Type type)2473 void InstructionSimplifierVisitor::SimplifyBoxUnbox(
2474 HInvoke* instruction, ArtField* field, DataType::Type type) {
2475 DCHECK(instruction->GetIntrinsic() == Intrinsics::kByteValueOf ||
2476 instruction->GetIntrinsic() == Intrinsics::kShortValueOf ||
2477 instruction->GetIntrinsic() == Intrinsics::kCharacterValueOf ||
2478 instruction->GetIntrinsic() == Intrinsics::kIntegerValueOf);
2479 const HUseList<HInstruction*>& uses = instruction->GetUses();
2480 for (auto it = uses.begin(), end = uses.end(); it != end;) {
2481 HInstruction* user = it->GetUser();
2482 ++it; // Increment the iterator before we potentially remove the node from the list.
2483 if (user->IsInstanceFieldGet() &&
2484 user->AsInstanceFieldGet()->GetFieldInfo().GetField() == field &&
2485 // Note: Due to other simplifications, we may have an `HInstanceFieldGet` with
2486 // a different type (Int8 vs. Uint8, Int16 vs. Uint16) for the same field.
2487 // Do not optimize that case for now. (We would need to insert a `HTypeConversion`.)
2488 user->GetType() == type) {
2489 user->ReplaceWith(instruction->InputAt(0));
2490 RecordSimplification();
2491 // Do not remove `user` while we're iterating over the block's instructions. Let DCE do it.
2492 }
2493 }
2494 }
2495
SimplifyStringEquals(HInvoke * instruction)2496 void InstructionSimplifierVisitor::SimplifyStringEquals(HInvoke* instruction) {
2497 HInstruction* argument = instruction->InputAt(1);
2498 HInstruction* receiver = instruction->InputAt(0);
2499 if (receiver == argument) {
2500 // Because String.equals is an instance call, the receiver is
2501 // a null check if we don't know it's null. The argument however, will
2502 // be the actual object. So we cannot end up in a situation where both
2503 // are equal but could be null.
2504 DCHECK(CanEnsureNotNullAt(argument, instruction));
2505 instruction->ReplaceWith(GetGraph()->GetIntConstant(1));
2506 instruction->GetBlock()->RemoveInstruction(instruction);
2507 } else {
2508 StringEqualsOptimizations optimizations(instruction);
2509 if (CanEnsureNotNullAt(argument, instruction)) {
2510 optimizations.SetArgumentNotNull();
2511 }
2512 ScopedObjectAccess soa(Thread::Current());
2513 ReferenceTypeInfo argument_rti = argument->GetReferenceTypeInfo();
2514 if (argument_rti.IsValid() && argument_rti.IsStringClass()) {
2515 optimizations.SetArgumentIsString();
2516 }
2517 }
2518 }
2519
IsArrayLengthOf(HInstruction * potential_length,HInstruction * potential_array)2520 static bool IsArrayLengthOf(HInstruction* potential_length, HInstruction* potential_array) {
2521 if (potential_length->IsArrayLength()) {
2522 return potential_length->InputAt(0) == potential_array;
2523 }
2524
2525 if (potential_array->IsNewArray()) {
2526 return potential_array->AsNewArray()->GetLength() == potential_length;
2527 }
2528
2529 return false;
2530 }
2531
SimplifySystemArrayCopy(HInvoke * instruction)2532 void InstructionSimplifierVisitor::SimplifySystemArrayCopy(HInvoke* instruction) {
2533 HInstruction* source = instruction->InputAt(0);
2534 HInstruction* source_pos = instruction->InputAt(1);
2535 HInstruction* destination = instruction->InputAt(2);
2536 HInstruction* destination_pos = instruction->InputAt(3);
2537 HInstruction* count = instruction->InputAt(4);
2538 SystemArrayCopyOptimizations optimizations(instruction);
2539 if (CanEnsureNotNullAt(source, instruction)) {
2540 optimizations.SetSourceIsNotNull();
2541 }
2542 if (CanEnsureNotNullAt(destination, instruction)) {
2543 optimizations.SetDestinationIsNotNull();
2544 }
2545 if (destination == source) {
2546 optimizations.SetDestinationIsSource();
2547 }
2548
2549 if (source_pos == destination_pos) {
2550 optimizations.SetSourcePositionIsDestinationPosition();
2551 }
2552
2553 if (IsArrayLengthOf(count, source)) {
2554 optimizations.SetCountIsSourceLength();
2555 }
2556
2557 if (IsArrayLengthOf(count, destination)) {
2558 optimizations.SetCountIsDestinationLength();
2559 }
2560
2561 {
2562 ScopedObjectAccess soa(Thread::Current());
2563 DataType::Type source_component_type = DataType::Type::kVoid;
2564 DataType::Type destination_component_type = DataType::Type::kVoid;
2565 ReferenceTypeInfo destination_rti = destination->GetReferenceTypeInfo();
2566 if (destination_rti.IsValid()) {
2567 if (destination_rti.IsObjectArray()) {
2568 if (destination_rti.IsExact()) {
2569 optimizations.SetDoesNotNeedTypeCheck();
2570 }
2571 optimizations.SetDestinationIsTypedObjectArray();
2572 }
2573 if (destination_rti.IsPrimitiveArrayClass()) {
2574 destination_component_type = DataTypeFromPrimitive(
2575 destination_rti.GetTypeHandle()->GetComponentType()->GetPrimitiveType());
2576 optimizations.SetDestinationIsPrimitiveArray();
2577 } else if (destination_rti.IsNonPrimitiveArrayClass()) {
2578 optimizations.SetDestinationIsNonPrimitiveArray();
2579 }
2580 }
2581 ReferenceTypeInfo source_rti = source->GetReferenceTypeInfo();
2582 if (source_rti.IsValid()) {
2583 if (destination_rti.IsValid() && destination_rti.CanArrayHoldValuesOf(source_rti)) {
2584 optimizations.SetDoesNotNeedTypeCheck();
2585 }
2586 if (source_rti.IsPrimitiveArrayClass()) {
2587 optimizations.SetSourceIsPrimitiveArray();
2588 source_component_type = DataTypeFromPrimitive(
2589 source_rti.GetTypeHandle()->GetComponentType()->GetPrimitiveType());
2590 } else if (source_rti.IsNonPrimitiveArrayClass()) {
2591 optimizations.SetSourceIsNonPrimitiveArray();
2592 }
2593 }
2594 // For primitive arrays, use their optimized ArtMethod implementations.
2595 if ((source_component_type != DataType::Type::kVoid) &&
2596 (source_component_type == destination_component_type)) {
2597 ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
2598 PointerSize image_size = class_linker->GetImagePointerSize();
2599 HInvokeStaticOrDirect* invoke = instruction->AsInvokeStaticOrDirect();
2600 ObjPtr<mirror::Class> system = invoke->GetResolvedMethod()->GetDeclaringClass();
2601 ArtMethod* method = nullptr;
2602 switch (source_component_type) {
2603 case DataType::Type::kBool:
2604 method = system->FindClassMethod("arraycopy", "([ZI[ZII)V", image_size);
2605 break;
2606 case DataType::Type::kInt8:
2607 method = system->FindClassMethod("arraycopy", "([BI[BII)V", image_size);
2608 break;
2609 case DataType::Type::kUint16:
2610 method = system->FindClassMethod("arraycopy", "([CI[CII)V", image_size);
2611 break;
2612 case DataType::Type::kInt16:
2613 method = system->FindClassMethod("arraycopy", "([SI[SII)V", image_size);
2614 break;
2615 case DataType::Type::kInt32:
2616 method = system->FindClassMethod("arraycopy", "([II[III)V", image_size);
2617 break;
2618 case DataType::Type::kFloat32:
2619 method = system->FindClassMethod("arraycopy", "([FI[FII)V", image_size);
2620 break;
2621 case DataType::Type::kInt64:
2622 method = system->FindClassMethod("arraycopy", "([JI[JII)V", image_size);
2623 break;
2624 case DataType::Type::kFloat64:
2625 method = system->FindClassMethod("arraycopy", "([DI[DII)V", image_size);
2626 break;
2627 default:
2628 LOG(FATAL) << "Unreachable";
2629 }
2630 DCHECK(method != nullptr);
2631 DCHECK(method->IsStatic());
2632 DCHECK(method->GetDeclaringClass() == system);
2633 invoke->SetResolvedMethod(method, !codegen_->GetGraph()->IsDebuggable());
2634 // Sharpen the new invoke. Note that we do not update the dex method index of
2635 // the invoke, as we would need to look it up in the current dex file, and it
2636 // is unlikely that it exists. The most usual situation for such typed
2637 // arraycopy methods is a direct pointer to the boot image.
2638 invoke->SetDispatchInfo(HSharpening::SharpenLoadMethod(
2639 method,
2640 /* has_method_id= */ true,
2641 /* for_interface_call= */ false,
2642 codegen_));
2643 }
2644 }
2645 }
2646
SimplifyFP2Int(HInvoke * invoke)2647 void InstructionSimplifierVisitor::SimplifyFP2Int(HInvoke* invoke) {
2648 DCHECK(invoke->IsInvokeStaticOrDirect());
2649 uint32_t dex_pc = invoke->GetDexPc();
2650 HInstruction* x = invoke->InputAt(0);
2651 DataType::Type type = x->GetType();
2652 // Set proper bit pattern for NaN and replace intrinsic with raw version.
2653 HInstruction* nan;
2654 if (type == DataType::Type::kFloat64) {
2655 nan = GetGraph()->GetLongConstant(0x7ff8000000000000L);
2656 invoke->SetIntrinsic(Intrinsics::kDoubleDoubleToRawLongBits,
2657 kNeedsEnvironment,
2658 kNoSideEffects,
2659 kNoThrow);
2660 } else {
2661 DCHECK_EQ(type, DataType::Type::kFloat32);
2662 nan = GetGraph()->GetIntConstant(0x7fc00000);
2663 invoke->SetIntrinsic(Intrinsics::kFloatFloatToRawIntBits,
2664 kNeedsEnvironment,
2665 kNoSideEffects,
2666 kNoThrow);
2667 }
2668 // Test IsNaN(x), which is the same as x != x.
2669 HCondition* condition = new (GetGraph()->GetAllocator()) HNotEqual(x, x, dex_pc);
2670 condition->SetBias(ComparisonBias::kLtBias);
2671 invoke->GetBlock()->InsertInstructionBefore(condition, invoke->GetNext());
2672 // Select between the two.
2673 HInstruction* select = new (GetGraph()->GetAllocator()) HSelect(condition, nan, invoke, dex_pc);
2674 invoke->GetBlock()->InsertInstructionBefore(select, condition->GetNext());
2675 invoke->ReplaceWithExceptInReplacementAtIndex(select, 0); // false at index 0
2676 }
2677
SimplifyStringCharAt(HInvoke * invoke)2678 void InstructionSimplifierVisitor::SimplifyStringCharAt(HInvoke* invoke) {
2679 HInstruction* str = invoke->InputAt(0);
2680 HInstruction* index = invoke->InputAt(1);
2681 uint32_t dex_pc = invoke->GetDexPc();
2682 ArenaAllocator* allocator = GetGraph()->GetAllocator();
2683 // We treat String as an array to allow DCE and BCE to seamlessly work on strings,
2684 // so create the HArrayLength, HBoundsCheck and HArrayGet.
2685 HArrayLength* length = new (allocator) HArrayLength(str, dex_pc, /* is_string_length= */ true);
2686 invoke->GetBlock()->InsertInstructionBefore(length, invoke);
2687 HBoundsCheck* bounds_check = new (allocator) HBoundsCheck(
2688 index, length, dex_pc, /* is_string_char_at= */ true);
2689 invoke->GetBlock()->InsertInstructionBefore(bounds_check, invoke);
2690 HArrayGet* array_get = new (allocator) HArrayGet(str,
2691 bounds_check,
2692 DataType::Type::kUint16,
2693 SideEffects::None(), // Strings are immutable.
2694 dex_pc,
2695 /* is_string_char_at= */ true);
2696 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, array_get);
2697 bounds_check->CopyEnvironmentFrom(invoke->GetEnvironment());
2698 GetGraph()->SetHasBoundsChecks(true);
2699 }
2700
SimplifyStringLength(HInvoke * invoke)2701 void InstructionSimplifierVisitor::SimplifyStringLength(HInvoke* invoke) {
2702 HInstruction* str = invoke->InputAt(0);
2703 uint32_t dex_pc = invoke->GetDexPc();
2704 // We treat String as an array to allow DCE and BCE to seamlessly work on strings,
2705 // so create the HArrayLength.
2706 HArrayLength* length =
2707 new (GetGraph()->GetAllocator()) HArrayLength(str, dex_pc, /* is_string_length= */ true);
2708 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, length);
2709 }
2710
SimplifyStringIndexOf(HInvoke * invoke)2711 void InstructionSimplifierVisitor::SimplifyStringIndexOf(HInvoke* invoke) {
2712 DCHECK(invoke->GetIntrinsic() == Intrinsics::kStringIndexOf ||
2713 invoke->GetIntrinsic() == Intrinsics::kStringIndexOfAfter);
2714 if (invoke->InputAt(0)->IsLoadString()) {
2715 HLoadString* load_string = invoke->InputAt(0)->AsLoadString();
2716 const DexFile& dex_file = load_string->GetDexFile();
2717 uint32_t utf16_length;
2718 const char* data =
2719 dex_file.GetStringDataAndUtf16Length(load_string->GetStringIndex(), &utf16_length);
2720 if (utf16_length == 0) {
2721 invoke->ReplaceWith(GetGraph()->GetIntConstant(-1));
2722 invoke->GetBlock()->RemoveInstruction(invoke);
2723 RecordSimplification();
2724 return;
2725 }
2726 if (utf16_length == 1 && invoke->GetIntrinsic() == Intrinsics::kStringIndexOf) {
2727 // Simplify to HSelect(HEquals(., load_string.charAt(0)), 0, -1).
2728 // If the sought character is supplementary, this gives the correct result, i.e. -1.
2729 uint32_t c = GetUtf16FromUtf8(&data);
2730 DCHECK_EQ(GetTrailingUtf16Char(c), 0u);
2731 DCHECK_EQ(GetLeadingUtf16Char(c), c);
2732 uint32_t dex_pc = invoke->GetDexPc();
2733 ArenaAllocator* allocator = GetGraph()->GetAllocator();
2734 HEqual* equal =
2735 new (allocator) HEqual(invoke->InputAt(1), GetGraph()->GetIntConstant(c), dex_pc);
2736 invoke->GetBlock()->InsertInstructionBefore(equal, invoke);
2737 HSelect* result = new (allocator) HSelect(equal,
2738 GetGraph()->GetIntConstant(0),
2739 GetGraph()->GetIntConstant(-1),
2740 dex_pc);
2741 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, result);
2742 RecordSimplification();
2743 return;
2744 }
2745 }
2746 }
2747
2748 // This method should only be used on intrinsics whose sole way of throwing an
2749 // exception is raising a NPE when the nth argument is null. If that argument
2750 // is provably non-null, we can clear the flag.
SimplifyNPEOnArgN(HInvoke * invoke,size_t n)2751 void InstructionSimplifierVisitor::SimplifyNPEOnArgN(HInvoke* invoke, size_t n) {
2752 HInstruction* arg = invoke->InputAt(n);
2753 if (invoke->CanThrow() && !arg->CanBeNull()) {
2754 invoke->SetCanThrow(false);
2755 }
2756 }
2757
2758 // Methods that return "this" can replace the returned value with the receiver.
SimplifyReturnThis(HInvoke * invoke)2759 void InstructionSimplifierVisitor::SimplifyReturnThis(HInvoke* invoke) {
2760 if (invoke->HasUses()) {
2761 HInstruction* receiver = invoke->InputAt(0);
2762 invoke->ReplaceWith(receiver);
2763 RecordSimplification();
2764 }
2765 }
2766
2767 // Helper method for StringBuffer escape analysis.
NoEscapeForStringBufferReference(HInstruction * reference,HInstruction * user)2768 static bool NoEscapeForStringBufferReference(HInstruction* reference, HInstruction* user) {
2769 if (user->IsInvokeStaticOrDirect()) {
2770 // Any constructor on StringBuffer is okay.
2771 return user->AsInvokeStaticOrDirect()->GetResolvedMethod() != nullptr &&
2772 user->AsInvokeStaticOrDirect()->GetResolvedMethod()->IsConstructor() &&
2773 user->InputAt(0) == reference;
2774 } else if (user->IsInvokeVirtual()) {
2775 switch (user->AsInvokeVirtual()->GetIntrinsic()) {
2776 case Intrinsics::kStringBufferLength:
2777 case Intrinsics::kStringBufferToString:
2778 DCHECK_EQ(user->InputAt(0), reference);
2779 return true;
2780 case Intrinsics::kStringBufferAppend:
2781 // Returns "this", so only okay if no further uses.
2782 DCHECK_EQ(user->InputAt(0), reference);
2783 DCHECK_NE(user->InputAt(1), reference);
2784 return !user->HasUses();
2785 default:
2786 break;
2787 }
2788 }
2789 return false;
2790 }
2791
TryReplaceStringBuilderAppend(HInvoke * invoke)2792 static bool TryReplaceStringBuilderAppend(HInvoke* invoke) {
2793 DCHECK_EQ(invoke->GetIntrinsic(), Intrinsics::kStringBuilderToString);
2794 if (invoke->CanThrowIntoCatchBlock()) {
2795 return false;
2796 }
2797
2798 HBasicBlock* block = invoke->GetBlock();
2799 HInstruction* sb = invoke->InputAt(0);
2800
2801 // We support only a new StringBuilder, otherwise we cannot ensure that
2802 // the StringBuilder data does not need to be populated for other users.
2803 if (!sb->IsNewInstance()) {
2804 return false;
2805 }
2806
2807 // For now, we support only single-block recognition.
2808 // (Ternary operators feeding the append could be implemented.)
2809 for (const HUseListNode<HInstruction*>& use : sb->GetUses()) {
2810 if (use.GetUser()->GetBlock() != block) {
2811 return false;
2812 }
2813 // The append pattern uses the StringBuilder only as the first argument.
2814 if (use.GetIndex() != 0u) {
2815 return false;
2816 }
2817 }
2818
2819 // Collect args and check for unexpected uses.
2820 // We expect one call to a constructor with no arguments, one constructor fence (unless
2821 // eliminated), some number of append calls and one call to StringBuilder.toString().
2822 bool seen_constructor = false;
2823 bool seen_constructor_fence = false;
2824 bool seen_to_string = false;
2825 uint32_t format = 0u;
2826 uint32_t num_args = 0u;
2827 bool has_fp_args = false;
2828 HInstruction* args[StringBuilderAppend::kMaxArgs]; // Added in reverse order.
2829 for (HBackwardInstructionIterator iter(block->GetInstructions()); !iter.Done(); iter.Advance()) {
2830 HInstruction* user = iter.Current();
2831 // Instructions of interest apply to `sb`, skip those that do not involve `sb`.
2832 if (user->InputCount() == 0u || user->InputAt(0u) != sb) {
2833 continue;
2834 }
2835 // We visit the uses in reverse order, so the StringBuilder.toString() must come first.
2836 if (!seen_to_string) {
2837 if (user == invoke) {
2838 seen_to_string = true;
2839 continue;
2840 } else {
2841 return false;
2842 }
2843 }
2844 // Then we should see the arguments.
2845 if (user->IsInvokeVirtual()) {
2846 HInvokeVirtual* as_invoke_virtual = user->AsInvokeVirtual();
2847 DCHECK(!seen_constructor);
2848 DCHECK(!seen_constructor_fence);
2849 StringBuilderAppend::Argument arg;
2850 switch (as_invoke_virtual->GetIntrinsic()) {
2851 case Intrinsics::kStringBuilderAppendObject:
2852 // TODO: Unimplemented, needs to call String.valueOf().
2853 return false;
2854 case Intrinsics::kStringBuilderAppendString:
2855 arg = StringBuilderAppend::Argument::kString;
2856 break;
2857 case Intrinsics::kStringBuilderAppendCharArray:
2858 // TODO: Unimplemented, StringBuilder.append(char[]) can throw NPE and we would
2859 // not have the correct stack trace for it.
2860 return false;
2861 case Intrinsics::kStringBuilderAppendBoolean:
2862 arg = StringBuilderAppend::Argument::kBoolean;
2863 break;
2864 case Intrinsics::kStringBuilderAppendChar:
2865 arg = StringBuilderAppend::Argument::kChar;
2866 break;
2867 case Intrinsics::kStringBuilderAppendInt:
2868 arg = StringBuilderAppend::Argument::kInt;
2869 break;
2870 case Intrinsics::kStringBuilderAppendLong:
2871 arg = StringBuilderAppend::Argument::kLong;
2872 break;
2873 case Intrinsics::kStringBuilderAppendFloat:
2874 arg = StringBuilderAppend::Argument::kFloat;
2875 has_fp_args = true;
2876 break;
2877 case Intrinsics::kStringBuilderAppendDouble:
2878 arg = StringBuilderAppend::Argument::kDouble;
2879 has_fp_args = true;
2880 break;
2881 case Intrinsics::kStringBuilderAppendCharSequence: {
2882 ReferenceTypeInfo rti = user->AsInvokeVirtual()->InputAt(1)->GetReferenceTypeInfo();
2883 if (!rti.IsValid()) {
2884 return false;
2885 }
2886 ScopedObjectAccess soa(Thread::Current());
2887 Handle<mirror::Class> input_type = rti.GetTypeHandle();
2888 DCHECK(input_type != nullptr);
2889 if (input_type.Get() == GetClassRoot<mirror::String>()) {
2890 arg = StringBuilderAppend::Argument::kString;
2891 } else {
2892 // TODO: Check and implement for StringBuilder. We could find the StringBuilder's
2893 // internal char[] inconsistent with the length, or the string compression
2894 // of the result could be compromised with a concurrent modification, and
2895 // we would need to throw appropriate exceptions.
2896 return false;
2897 }
2898 break;
2899 }
2900 default: {
2901 return false;
2902 }
2903 }
2904 // Uses of the append return value should have been replaced with the first input.
2905 DCHECK(!as_invoke_virtual->HasUses());
2906 DCHECK(!as_invoke_virtual->HasEnvironmentUses());
2907 if (num_args == StringBuilderAppend::kMaxArgs) {
2908 return false;
2909 }
2910 format = (format << StringBuilderAppend::kBitsPerArg) | static_cast<uint32_t>(arg);
2911 args[num_args] = as_invoke_virtual->InputAt(1u);
2912 ++num_args;
2913 } else if (user->IsInvokeStaticOrDirect() &&
2914 user->AsInvokeStaticOrDirect()->GetResolvedMethod() != nullptr &&
2915 user->AsInvokeStaticOrDirect()->GetResolvedMethod()->IsConstructor() &&
2916 user->AsInvokeStaticOrDirect()->GetNumberOfArguments() == 1u) {
2917 // After arguments, we should see the constructor.
2918 // We accept only the constructor with no extra arguments.
2919 DCHECK(!seen_constructor);
2920 DCHECK(!seen_constructor_fence);
2921 seen_constructor = true;
2922 } else if (user->IsConstructorFence()) {
2923 // The last use we see is the constructor fence.
2924 DCHECK(seen_constructor);
2925 DCHECK(!seen_constructor_fence);
2926 seen_constructor_fence = true;
2927 } else {
2928 return false;
2929 }
2930 }
2931
2932 if (num_args == 0u) {
2933 return false;
2934 }
2935
2936 // Check environment uses.
2937 for (const HUseListNode<HEnvironment*>& use : sb->GetEnvUses()) {
2938 HInstruction* holder = use.GetUser()->GetHolder();
2939 if (holder->GetBlock() != block) {
2940 return false;
2941 }
2942 // Accept only calls on the StringBuilder (which shall all be removed).
2943 // TODO: Carve-out for const-string? Or rely on environment pruning (to be implemented)?
2944 if (holder->InputCount() == 0 || holder->InputAt(0) != sb) {
2945 return false;
2946 }
2947 }
2948
2949 // Create replacement instruction.
2950 HIntConstant* fmt = block->GetGraph()->GetIntConstant(static_cast<int32_t>(format));
2951 ArenaAllocator* allocator = block->GetGraph()->GetAllocator();
2952 HStringBuilderAppend* append = new (allocator) HStringBuilderAppend(
2953 fmt, num_args, has_fp_args, allocator, invoke->GetDexPc());
2954 append->SetReferenceTypeInfoIfValid(invoke->GetReferenceTypeInfo());
2955 for (size_t i = 0; i != num_args; ++i) {
2956 append->SetArgumentAt(i, args[num_args - 1u - i]);
2957 }
2958 block->InsertInstructionBefore(append, invoke);
2959 DCHECK(!invoke->CanBeNull());
2960 DCHECK(!append->CanBeNull());
2961 invoke->ReplaceWith(append);
2962 // Copy environment, except for the StringBuilder uses.
2963 for (HEnvironment* env = invoke->GetEnvironment(); env != nullptr; env = env->GetParent()) {
2964 for (size_t i = 0, size = env->Size(); i != size; ++i) {
2965 if (env->GetInstructionAt(i) == sb) {
2966 env->RemoveAsUserOfInput(i);
2967 env->SetRawEnvAt(i, /*instruction=*/ nullptr);
2968 }
2969 }
2970 }
2971 append->CopyEnvironmentFrom(invoke->GetEnvironment());
2972 // Remove the old instruction.
2973 block->RemoveInstruction(invoke);
2974 // Remove the StringBuilder's uses and StringBuilder.
2975 while (sb->HasNonEnvironmentUses()) {
2976 block->RemoveInstruction(sb->GetUses().front().GetUser());
2977 }
2978 DCHECK(!sb->HasEnvironmentUses());
2979 block->RemoveInstruction(sb);
2980 return true;
2981 }
2982
2983 // Certain allocation intrinsics are not removed by dead code elimination
2984 // because of potentially throwing an OOM exception or other side effects.
2985 // This method removes such intrinsics when special circumstances allow.
SimplifyAllocationIntrinsic(HInvoke * invoke)2986 void InstructionSimplifierVisitor::SimplifyAllocationIntrinsic(HInvoke* invoke) {
2987 if (!invoke->HasUses()) {
2988 // Instruction has no uses. If unsynchronized, we can remove right away, safely ignoring
2989 // the potential OOM of course. Otherwise, we must ensure the receiver object of this
2990 // call does not escape since only thread-local synchronization may be removed.
2991 bool is_synchronized = invoke->GetIntrinsic() == Intrinsics::kStringBufferToString;
2992 HInstruction* receiver = invoke->InputAt(0);
2993 if (!is_synchronized || DoesNotEscape(receiver, NoEscapeForStringBufferReference)) {
2994 invoke->GetBlock()->RemoveInstruction(invoke);
2995 RecordSimplification();
2996 }
2997 } else if (invoke->GetIntrinsic() == Intrinsics::kStringBuilderToString &&
2998 TryReplaceStringBuilderAppend(invoke)) {
2999 RecordSimplification();
3000 }
3001 }
3002
SimplifyVarHandleIntrinsic(HInvoke * invoke)3003 void InstructionSimplifierVisitor::SimplifyVarHandleIntrinsic(HInvoke* invoke) {
3004 DCHECK(invoke->IsInvokePolymorphic());
3005 VarHandleOptimizations optimizations(invoke);
3006
3007 if (optimizations.GetDoNotIntrinsify()) {
3008 // Preceding static checks disabled intrinsic, so no need to analyze further.
3009 return;
3010 }
3011
3012 size_t expected_coordinates_count = GetExpectedVarHandleCoordinatesCount(invoke);
3013 if (expected_coordinates_count != 0u) {
3014 HInstruction* object = invoke->InputAt(1);
3015 // The following has been ensured by static checks in the instruction builder.
3016 DCHECK(object->GetType() == DataType::Type::kReference);
3017 // Re-check for null constant, as this might have changed after the inliner.
3018 if (object->IsNullConstant()) {
3019 optimizations.SetDoNotIntrinsify();
3020 return;
3021 }
3022 // Test whether we can avoid the null check on the object.
3023 if (CanEnsureNotNullAt(object, invoke)) {
3024 optimizations.SetSkipObjectNullCheck();
3025 }
3026 }
3027
3028 if (CanUseKnownImageVarHandle(invoke)) {
3029 optimizations.SetUseKnownImageVarHandle();
3030 }
3031 }
3032
CanUseKnownImageVarHandle(HInvoke * invoke)3033 bool InstructionSimplifierVisitor::CanUseKnownImageVarHandle(HInvoke* invoke) {
3034 // If the `VarHandle` comes from a static final field of an initialized class in an image
3035 // (boot image or app image), we can do the checks at compile time. We do this optimization
3036 // only for AOT and only for field handles when we can avoid all checks. This avoids the
3037 // possibility of the code concurrently messing with the `VarHandle` using reflection,
3038 // we simply perform the operation with the `VarHandle` as seen at compile time.
3039 // TODO: Extend this to arrays to support the `AtomicIntegerArray` class.
3040 const CompilerOptions& compiler_options = codegen_->GetCompilerOptions();
3041 if (!compiler_options.IsAotCompiler()) {
3042 return false;
3043 }
3044 size_t expected_coordinates_count = GetExpectedVarHandleCoordinatesCount(invoke);
3045 if (expected_coordinates_count == 2u) {
3046 return false;
3047 }
3048 HInstruction* var_handle_instruction = invoke->InputAt(0);
3049 if (var_handle_instruction->IsNullCheck()) {
3050 var_handle_instruction = var_handle_instruction->InputAt(0);
3051 }
3052 if (!var_handle_instruction->IsStaticFieldGet()) {
3053 return false;
3054 }
3055 ArtField* field = var_handle_instruction->AsStaticFieldGet()->GetFieldInfo().GetField();
3056 DCHECK(field->IsStatic());
3057 if (!field->IsFinal()) {
3058 return false;
3059 }
3060 ScopedObjectAccess soa(Thread::Current());
3061 ObjPtr<mirror::Class> declaring_class = field->GetDeclaringClass();
3062 if (!declaring_class->IsVisiblyInitialized()) {
3063 // During AOT compilation, dex2oat ensures that initialized classes are visibly initialized.
3064 DCHECK(!declaring_class->IsInitialized());
3065 return false;
3066 }
3067 HInstruction* load_class = var_handle_instruction->InputAt(0);
3068 if (kIsDebugBuild) {
3069 bool is_in_image = false;
3070 if (Runtime::Current()->GetHeap()->ObjectIsInBootImageSpace(declaring_class)) {
3071 is_in_image = true;
3072 } else if (compiler_options.IsGeneratingImage()) {
3073 std::string storage;
3074 const char* descriptor = declaring_class->GetDescriptor(&storage);
3075 is_in_image = compiler_options.IsImageClass(descriptor);
3076 }
3077 CHECK_EQ(is_in_image, load_class->IsLoadClass() && load_class->AsLoadClass()->IsInImage());
3078 }
3079 if (!load_class->IsLoadClass() || !load_class->AsLoadClass()->IsInImage()) {
3080 return false;
3081 }
3082
3083 // Get the `VarHandle` object and check its class.
3084 ObjPtr<mirror::Class> expected_var_handle_class;
3085 switch (expected_coordinates_count) {
3086 case 0:
3087 expected_var_handle_class = GetClassRoot<mirror::StaticFieldVarHandle>();
3088 break;
3089 default:
3090 DCHECK_EQ(expected_coordinates_count, 1u);
3091 expected_var_handle_class = GetClassRoot<mirror::FieldVarHandle>();
3092 break;
3093 }
3094 ObjPtr<mirror::Object> var_handle_object = field->GetObject(declaring_class);
3095 if (var_handle_object == nullptr || var_handle_object->GetClass() != expected_var_handle_class) {
3096 return false;
3097 }
3098 ObjPtr<mirror::VarHandle> var_handle = ObjPtr<mirror::VarHandle>::DownCast(var_handle_object);
3099
3100 // Check access mode.
3101 mirror::VarHandle::AccessMode access_mode =
3102 mirror::VarHandle::GetAccessModeByIntrinsic(invoke->GetIntrinsic());
3103 if (!var_handle->IsAccessModeSupported(access_mode)) {
3104 return false;
3105 }
3106
3107 // Check argument types.
3108 ObjPtr<mirror::Class> var_type = var_handle->GetVarType();
3109 mirror::VarHandle::AccessModeTemplate access_mode_template =
3110 mirror::VarHandle::GetAccessModeTemplate(access_mode);
3111 // Note: The data type of input arguments does not need to match the type from shorty
3112 // due to implicit conversions or avoiding unnecessary conversions before narrow stores.
3113 DataType::Type type = (access_mode_template == mirror::VarHandle::AccessModeTemplate::kGet)
3114 ? invoke->GetType()
3115 : GetDataTypeFromShorty(invoke, invoke->GetNumberOfArguments() - 1u);
3116 if (type != DataTypeFromPrimitive(var_type->GetPrimitiveType())) {
3117 return false;
3118 }
3119 if (type == DataType::Type::kReference) {
3120 uint32_t arguments_start = /* VarHandle object */ 1u + expected_coordinates_count;
3121 uint32_t number_of_arguments = invoke->GetNumberOfArguments();
3122 for (size_t arg_index = arguments_start; arg_index != number_of_arguments; ++arg_index) {
3123 HInstruction* arg = invoke->InputAt(arg_index);
3124 DCHECK_EQ(arg->GetType(), DataType::Type::kReference);
3125 if (!arg->IsNullConstant()) {
3126 ReferenceTypeInfo arg_type_info = arg->GetReferenceTypeInfo();
3127 if (!arg_type_info.IsValid() ||
3128 !var_type->IsAssignableFrom(arg_type_info.GetTypeHandle().Get())) {
3129 return false;
3130 }
3131 }
3132 }
3133 }
3134
3135 // Check the first coordinate.
3136 if (expected_coordinates_count != 0u) {
3137 ObjPtr<mirror::Class> coordinate0_type = var_handle->GetCoordinateType0();
3138 DCHECK(coordinate0_type != nullptr);
3139 ReferenceTypeInfo object_type_info = invoke->InputAt(1)->GetReferenceTypeInfo();
3140 if (!object_type_info.IsValid() ||
3141 !coordinate0_type->IsAssignableFrom(object_type_info.GetTypeHandle().Get())) {
3142 return false;
3143 }
3144 }
3145
3146 // All required checks passed.
3147 return true;
3148 }
3149
VisitInvoke(HInvoke * instruction)3150 void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) {
3151 switch (instruction->GetIntrinsic()) {
3152 #define SIMPLIFY_BOX_UNBOX(name, low, high, type, start_index) \
3153 case Intrinsics::k ## name ## ValueOf: \
3154 SimplifyBoxUnbox(instruction, WellKnownClasses::java_lang_##name##_value, type); \
3155 break;
3156 BOXED_TYPES(SIMPLIFY_BOX_UNBOX)
3157 #undef SIMPLIFY_BOX_UNBOX
3158 case Intrinsics::kStringEquals:
3159 SimplifyStringEquals(instruction);
3160 break;
3161 case Intrinsics::kSystemArrayCopy:
3162 SimplifySystemArrayCopy(instruction);
3163 break;
3164 case Intrinsics::kFloatFloatToIntBits:
3165 case Intrinsics::kDoubleDoubleToLongBits:
3166 SimplifyFP2Int(instruction);
3167 break;
3168 case Intrinsics::kStringCharAt:
3169 // Instruction builder creates intermediate representation directly
3170 // but the inliner can sharpen CharSequence.charAt() to String.charAt().
3171 SimplifyStringCharAt(instruction);
3172 break;
3173 case Intrinsics::kStringLength:
3174 // Instruction builder creates intermediate representation directly
3175 // but the inliner can sharpen CharSequence.length() to String.length().
3176 SimplifyStringLength(instruction);
3177 break;
3178 case Intrinsics::kStringIndexOf:
3179 case Intrinsics::kStringIndexOfAfter:
3180 SimplifyStringIndexOf(instruction);
3181 break;
3182 case Intrinsics::kStringStringIndexOf:
3183 case Intrinsics::kStringStringIndexOfAfter:
3184 SimplifyNPEOnArgN(instruction, 1); // 0th has own NullCheck
3185 break;
3186 case Intrinsics::kStringBufferAppend:
3187 case Intrinsics::kStringBuilderAppendObject:
3188 case Intrinsics::kStringBuilderAppendString:
3189 case Intrinsics::kStringBuilderAppendCharSequence:
3190 case Intrinsics::kStringBuilderAppendCharArray:
3191 case Intrinsics::kStringBuilderAppendBoolean:
3192 case Intrinsics::kStringBuilderAppendChar:
3193 case Intrinsics::kStringBuilderAppendInt:
3194 case Intrinsics::kStringBuilderAppendLong:
3195 case Intrinsics::kStringBuilderAppendFloat:
3196 case Intrinsics::kStringBuilderAppendDouble:
3197 SimplifyReturnThis(instruction);
3198 break;
3199 case Intrinsics::kStringBufferToString:
3200 case Intrinsics::kStringBuilderToString:
3201 SimplifyAllocationIntrinsic(instruction);
3202 break;
3203 case Intrinsics::kVarHandleCompareAndExchange:
3204 case Intrinsics::kVarHandleCompareAndExchangeAcquire:
3205 case Intrinsics::kVarHandleCompareAndExchangeRelease:
3206 case Intrinsics::kVarHandleCompareAndSet:
3207 case Intrinsics::kVarHandleGet:
3208 case Intrinsics::kVarHandleGetAcquire:
3209 case Intrinsics::kVarHandleGetAndAdd:
3210 case Intrinsics::kVarHandleGetAndAddAcquire:
3211 case Intrinsics::kVarHandleGetAndAddRelease:
3212 case Intrinsics::kVarHandleGetAndBitwiseAnd:
3213 case Intrinsics::kVarHandleGetAndBitwiseAndAcquire:
3214 case Intrinsics::kVarHandleGetAndBitwiseAndRelease:
3215 case Intrinsics::kVarHandleGetAndBitwiseOr:
3216 case Intrinsics::kVarHandleGetAndBitwiseOrAcquire:
3217 case Intrinsics::kVarHandleGetAndBitwiseOrRelease:
3218 case Intrinsics::kVarHandleGetAndBitwiseXor:
3219 case Intrinsics::kVarHandleGetAndBitwiseXorAcquire:
3220 case Intrinsics::kVarHandleGetAndBitwiseXorRelease:
3221 case Intrinsics::kVarHandleGetAndSet:
3222 case Intrinsics::kVarHandleGetAndSetAcquire:
3223 case Intrinsics::kVarHandleGetAndSetRelease:
3224 case Intrinsics::kVarHandleGetOpaque:
3225 case Intrinsics::kVarHandleGetVolatile:
3226 case Intrinsics::kVarHandleSet:
3227 case Intrinsics::kVarHandleSetOpaque:
3228 case Intrinsics::kVarHandleSetRelease:
3229 case Intrinsics::kVarHandleSetVolatile:
3230 case Intrinsics::kVarHandleWeakCompareAndSet:
3231 case Intrinsics::kVarHandleWeakCompareAndSetAcquire:
3232 case Intrinsics::kVarHandleWeakCompareAndSetPlain:
3233 case Intrinsics::kVarHandleWeakCompareAndSetRelease:
3234 SimplifyVarHandleIntrinsic(instruction);
3235 break;
3236 default:
3237 break;
3238 }
3239 }
3240
VisitDeoptimize(HDeoptimize * deoptimize)3241 void InstructionSimplifierVisitor::VisitDeoptimize(HDeoptimize* deoptimize) {
3242 HInstruction* cond = deoptimize->InputAt(0);
3243 if (cond->IsConstant()) {
3244 if (cond->AsIntConstant()->IsFalse()) {
3245 // Never deopt: instruction can be removed.
3246 if (deoptimize->GuardsAnInput()) {
3247 deoptimize->ReplaceWith(deoptimize->GuardedInput());
3248 }
3249 deoptimize->GetBlock()->RemoveInstruction(deoptimize);
3250 } else {
3251 // Always deopt.
3252 }
3253 }
3254 }
3255
3256 // Replace code looking like
3257 // OP y, x, const1
3258 // OP z, y, const2
3259 // with
3260 // OP z, x, const3
3261 // where OP is both an associative and a commutative operation.
TryHandleAssociativeAndCommutativeOperation(HBinaryOperation * instruction)3262 bool InstructionSimplifierVisitor::TryHandleAssociativeAndCommutativeOperation(
3263 HBinaryOperation* instruction) {
3264 DCHECK(instruction->IsCommutative());
3265
3266 if (!DataType::IsIntegralType(instruction->GetType())) {
3267 return false;
3268 }
3269
3270 HInstruction* left = instruction->GetLeft();
3271 HInstruction* right = instruction->GetRight();
3272 // Variable names as described above.
3273 HConstant* const2;
3274 HBinaryOperation* y;
3275
3276 if (instruction->GetKind() == left->GetKind() && right->IsConstant()) {
3277 const2 = right->AsConstant();
3278 y = left->AsBinaryOperation();
3279 } else if (left->IsConstant() && instruction->GetKind() == right->GetKind()) {
3280 const2 = left->AsConstant();
3281 y = right->AsBinaryOperation();
3282 } else {
3283 // The node does not match the pattern.
3284 return false;
3285 }
3286
3287 // If `y` has more than one use, we do not perform the optimization
3288 // because it might increase code size (e.g. if the new constant is
3289 // no longer encodable as an immediate operand in the target ISA).
3290 if (!y->HasOnlyOneNonEnvironmentUse()) {
3291 return false;
3292 }
3293
3294 // GetConstantRight() can return both left and right constants
3295 // for commutative operations.
3296 HConstant* const1 = y->GetConstantRight();
3297 if (const1 == nullptr) {
3298 return false;
3299 }
3300
3301 instruction->ReplaceInput(const1, 0);
3302 instruction->ReplaceInput(const2, 1);
3303 HConstant* const3 = instruction->TryStaticEvaluation();
3304 DCHECK(const3 != nullptr);
3305 instruction->ReplaceInput(y->GetLeastConstantLeft(), 0);
3306 instruction->ReplaceInput(const3, 1);
3307 RecordSimplification();
3308 return true;
3309 }
3310
AsAddOrSub(HInstruction * binop)3311 static HBinaryOperation* AsAddOrSub(HInstruction* binop) {
3312 return (binop->IsAdd() || binop->IsSub()) ? binop->AsBinaryOperation() : nullptr;
3313 }
3314
3315 // Helper function that performs addition statically, considering the result type.
ComputeAddition(DataType::Type type,int64_t x,int64_t y)3316 static int64_t ComputeAddition(DataType::Type type, int64_t x, int64_t y) {
3317 // Use the Compute() method for consistency with TryStaticEvaluation().
3318 if (type == DataType::Type::kInt32) {
3319 return HAdd::Compute<int32_t>(x, y);
3320 } else {
3321 DCHECK_EQ(type, DataType::Type::kInt64);
3322 return HAdd::Compute<int64_t>(x, y);
3323 }
3324 }
3325
3326 // Helper function that handles the child classes of HConstant
3327 // and returns an integer with the appropriate sign.
GetValue(HConstant * constant,bool is_negated)3328 static int64_t GetValue(HConstant* constant, bool is_negated) {
3329 int64_t ret = Int64FromConstant(constant);
3330 return is_negated ? -ret : ret;
3331 }
3332
3333 // Replace code looking like
3334 // OP1 y, x, const1
3335 // OP2 z, y, const2
3336 // with
3337 // OP3 z, x, const3
3338 // where OPx is either ADD or SUB, and at least one of OP{1,2} is SUB.
TrySubtractionChainSimplification(HBinaryOperation * instruction)3339 bool InstructionSimplifierVisitor::TrySubtractionChainSimplification(
3340 HBinaryOperation* instruction) {
3341 DCHECK(instruction->IsAdd() || instruction->IsSub()) << instruction->DebugName();
3342
3343 DataType::Type type = instruction->GetType();
3344 if (!DataType::IsIntegralType(type)) {
3345 return false;
3346 }
3347
3348 HInstruction* left = instruction->GetLeft();
3349 HInstruction* right = instruction->GetRight();
3350 // Variable names as described above.
3351 HConstant* const2 = right->IsConstant() ? right->AsConstant() : left->AsConstantOrNull();
3352 if (const2 == nullptr) {
3353 return false;
3354 }
3355
3356 HBinaryOperation* y = (AsAddOrSub(left) != nullptr)
3357 ? left->AsBinaryOperation()
3358 : AsAddOrSub(right);
3359 // If y has more than one use, we do not perform the optimization because
3360 // it might increase code size (e.g. if the new constant is no longer
3361 // encodable as an immediate operand in the target ISA).
3362 if ((y == nullptr) || !y->HasOnlyOneNonEnvironmentUse()) {
3363 return false;
3364 }
3365
3366 left = y->GetLeft();
3367 HConstant* const1 = left->IsConstant() ? left->AsConstant() : y->GetRight()->AsConstantOrNull();
3368 if (const1 == nullptr) {
3369 return false;
3370 }
3371
3372 HInstruction* x = (const1 == left) ? y->GetRight() : left;
3373 // If both inputs are constants, let the constant folding pass deal with it.
3374 if (x->IsConstant()) {
3375 return false;
3376 }
3377
3378 bool is_const2_negated = (const2 == right) && instruction->IsSub();
3379 int64_t const2_val = GetValue(const2, is_const2_negated);
3380 bool is_y_negated = (y == right) && instruction->IsSub();
3381 right = y->GetRight();
3382 bool is_const1_negated = is_y_negated ^ ((const1 == right) && y->IsSub());
3383 int64_t const1_val = GetValue(const1, is_const1_negated);
3384 bool is_x_negated = is_y_negated ^ ((x == right) && y->IsSub());
3385 int64_t const3_val = ComputeAddition(type, const1_val, const2_val);
3386 HBasicBlock* block = instruction->GetBlock();
3387 HConstant* const3 = block->GetGraph()->GetConstant(type, const3_val);
3388 ArenaAllocator* allocator = instruction->GetAllocator();
3389 HInstruction* z;
3390
3391 if (is_x_negated) {
3392 z = new (allocator) HSub(type, const3, x, instruction->GetDexPc());
3393 } else {
3394 z = new (allocator) HAdd(type, x, const3, instruction->GetDexPc());
3395 }
3396
3397 block->ReplaceAndRemoveInstructionWith(instruction, z);
3398 RecordSimplification();
3399 return true;
3400 }
3401
VisitVecMul(HVecMul * instruction)3402 void InstructionSimplifierVisitor::VisitVecMul(HVecMul* instruction) {
3403 if (TryCombineVecMultiplyAccumulate(instruction)) {
3404 RecordSimplification();
3405 }
3406 }
3407
TryMergeNegatedInput(HBinaryOperation * op)3408 bool TryMergeNegatedInput(HBinaryOperation* op) {
3409 DCHECK(op->IsAnd() || op->IsOr() || op->IsXor()) << op->DebugName();
3410 HInstruction* left = op->GetLeft();
3411 HInstruction* right = op->GetRight();
3412
3413 // Only consider the case where there is exactly one Not, with 2 Not's De
3414 // Morgan's laws should be applied instead.
3415 if (left->IsNot() ^ right->IsNot()) {
3416 HInstruction* hnot = (left->IsNot() ? left : right);
3417 HInstruction* hother = (left->IsNot() ? right : left);
3418
3419 // Only do the simplification if the Not has only one use and can thus be
3420 // safely removed. Even though ARM64 negated bitwise operations do not have
3421 // an immediate variant (only register), we still do the simplification when
3422 // `hother` is a constant, because it removes an instruction if the constant
3423 // cannot be encoded as an immediate:
3424 // mov r0, #large_constant
3425 // neg r2, r1
3426 // and r0, r0, r2
3427 // becomes:
3428 // mov r0, #large_constant
3429 // bic r0, r0, r1
3430 if (hnot->HasOnlyOneNonEnvironmentUse()) {
3431 // Replace code looking like
3432 // NOT tmp, mask
3433 // AND dst, src, tmp (respectively ORR, EOR)
3434 // with
3435 // BIC dst, src, mask (respectively ORN, EON)
3436 HInstruction* src = hnot->AsNot()->GetInput();
3437
3438 HBitwiseNegatedRight* neg_op = new (hnot->GetBlock()->GetGraph()->GetAllocator())
3439 HBitwiseNegatedRight(op->GetType(), op->GetKind(), hother, src, op->GetDexPc());
3440
3441 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, neg_op);
3442 hnot->GetBlock()->RemoveInstruction(hnot);
3443 return true;
3444 }
3445 }
3446
3447 return false;
3448 }
3449
TryMergeWithAnd(HSub * instruction)3450 bool TryMergeWithAnd(HSub* instruction) {
3451 HAnd* and_instr = instruction->GetRight()->AsAndOrNull();
3452 if (and_instr == nullptr) {
3453 return false;
3454 }
3455
3456 HInstruction* value = instruction->GetLeft();
3457
3458 HInstruction* left = and_instr->GetLeft();
3459 const bool left_is_equal = left == value;
3460 HInstruction* right = and_instr->GetRight();
3461 const bool right_is_equal = right == value;
3462 if (!left_is_equal && !right_is_equal) {
3463 return false;
3464 }
3465
3466 HBitwiseNegatedRight* bnr = new (instruction->GetBlock()->GetGraph()->GetAllocator())
3467 HBitwiseNegatedRight(instruction->GetType(),
3468 HInstruction::InstructionKind::kAnd,
3469 value,
3470 left_is_equal ? right : left,
3471 instruction->GetDexPc());
3472 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bnr);
3473 // Since we don't run DCE after this phase, try to manually remove the And instruction.
3474 if (!and_instr->HasUses()) {
3475 and_instr->GetBlock()->RemoveInstruction(and_instr);
3476 }
3477 return true;
3478 }
3479
3480 } // namespace art
3481