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