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