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 "intrinsics.h"
20 #include "mirror/class-inl.h"
21 #include "scoped_thread_state_change.h"
22
23 namespace art {
24
25 class InstructionSimplifierVisitor : public HGraphDelegateVisitor {
26 public:
InstructionSimplifierVisitor(HGraph * graph,OptimizingCompilerStats * stats)27 InstructionSimplifierVisitor(HGraph* graph, OptimizingCompilerStats* stats)
28 : HGraphDelegateVisitor(graph),
29 stats_(stats) {}
30
31 void Run();
32
33 private:
RecordSimplification()34 void RecordSimplification() {
35 simplification_occurred_ = true;
36 simplifications_at_current_position_++;
37 MaybeRecordStat(kInstructionSimplifications);
38 }
39
MaybeRecordStat(MethodCompilationStat stat)40 void MaybeRecordStat(MethodCompilationStat stat) {
41 if (stats_ != nullptr) {
42 stats_->RecordStat(stat);
43 }
44 }
45
46 bool ReplaceRotateWithRor(HBinaryOperation* op, HUShr* ushr, HShl* shl);
47 bool TryReplaceWithRotate(HBinaryOperation* instruction);
48 bool TryReplaceWithRotateConstantPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
49 bool TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
50 bool TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op, HUShr* ushr, HShl* shl);
51
52 bool TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop);
53 // `op` should be either HOr or HAnd.
54 // De Morgan's laws:
55 // ~a & ~b = ~(a | b) and ~a | ~b = ~(a & b)
56 bool TryDeMorganNegationFactoring(HBinaryOperation* op);
57 void VisitShift(HBinaryOperation* shift);
58
59 void VisitEqual(HEqual* equal) OVERRIDE;
60 void VisitNotEqual(HNotEqual* equal) OVERRIDE;
61 void VisitBooleanNot(HBooleanNot* bool_not) OVERRIDE;
62 void VisitInstanceFieldSet(HInstanceFieldSet* equal) OVERRIDE;
63 void VisitStaticFieldSet(HStaticFieldSet* equal) OVERRIDE;
64 void VisitArraySet(HArraySet* equal) OVERRIDE;
65 void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
66 void VisitNullCheck(HNullCheck* instruction) OVERRIDE;
67 void VisitArrayLength(HArrayLength* instruction) OVERRIDE;
68 void VisitCheckCast(HCheckCast* instruction) OVERRIDE;
69 void VisitAdd(HAdd* instruction) OVERRIDE;
70 void VisitAnd(HAnd* instruction) OVERRIDE;
71 void VisitCondition(HCondition* instruction) OVERRIDE;
72 void VisitGreaterThan(HGreaterThan* condition) OVERRIDE;
73 void VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) OVERRIDE;
74 void VisitLessThan(HLessThan* condition) OVERRIDE;
75 void VisitLessThanOrEqual(HLessThanOrEqual* condition) OVERRIDE;
76 void VisitBelow(HBelow* condition) OVERRIDE;
77 void VisitBelowOrEqual(HBelowOrEqual* condition) OVERRIDE;
78 void VisitAbove(HAbove* condition) OVERRIDE;
79 void VisitAboveOrEqual(HAboveOrEqual* condition) OVERRIDE;
80 void VisitDiv(HDiv* instruction) OVERRIDE;
81 void VisitMul(HMul* instruction) OVERRIDE;
82 void VisitNeg(HNeg* instruction) OVERRIDE;
83 void VisitNot(HNot* instruction) OVERRIDE;
84 void VisitOr(HOr* instruction) OVERRIDE;
85 void VisitShl(HShl* instruction) OVERRIDE;
86 void VisitShr(HShr* instruction) OVERRIDE;
87 void VisitSub(HSub* instruction) OVERRIDE;
88 void VisitUShr(HUShr* instruction) OVERRIDE;
89 void VisitXor(HXor* instruction) OVERRIDE;
90 void VisitSelect(HSelect* select) OVERRIDE;
91 void VisitIf(HIf* instruction) OVERRIDE;
92 void VisitInstanceOf(HInstanceOf* instruction) OVERRIDE;
93 void VisitInvoke(HInvoke* invoke) OVERRIDE;
94 void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE;
95
96 bool CanEnsureNotNullAt(HInstruction* instr, HInstruction* at) const;
97
98 void SimplifyRotate(HInvoke* invoke, bool is_left, Primitive::Type type);
99 void SimplifySystemArrayCopy(HInvoke* invoke);
100 void SimplifyStringEquals(HInvoke* invoke);
101 void SimplifyCompare(HInvoke* invoke, bool is_signum, Primitive::Type type);
102 void SimplifyIsNaN(HInvoke* invoke);
103 void SimplifyFP2Int(HInvoke* invoke);
104 void SimplifyMemBarrier(HInvoke* invoke, MemBarrierKind barrier_kind);
105
106 OptimizingCompilerStats* stats_;
107 bool simplification_occurred_ = false;
108 int simplifications_at_current_position_ = 0;
109 // We ensure we do not loop infinitely. The value is a finger in the air guess
110 // that should allow enough simplification.
111 static constexpr int kMaxSamePositionSimplifications = 10;
112 };
113
Run()114 void InstructionSimplifier::Run() {
115 InstructionSimplifierVisitor visitor(graph_, stats_);
116 visitor.Run();
117 }
118
Run()119 void InstructionSimplifierVisitor::Run() {
120 // Iterate in reverse post order to open up more simplifications to users
121 // of instructions that got simplified.
122 for (HReversePostOrderIterator it(*GetGraph()); !it.Done();) {
123 // The simplification of an instruction to another instruction may yield
124 // possibilities for other simplifications. So although we perform a reverse
125 // post order visit, we sometimes need to revisit an instruction index.
126 simplification_occurred_ = false;
127 VisitBasicBlock(it.Current());
128 if (simplification_occurred_ &&
129 (simplifications_at_current_position_ < kMaxSamePositionSimplifications)) {
130 // New simplifications may be applicable to the instruction at the
131 // current index, so don't advance the iterator.
132 continue;
133 }
134 simplifications_at_current_position_ = 0;
135 it.Advance();
136 }
137 }
138
139 namespace {
140
AreAllBitsSet(HConstant * constant)141 bool AreAllBitsSet(HConstant* constant) {
142 return Int64FromConstant(constant) == -1;
143 }
144
145 } // namespace
146
147 // Returns true if the code was simplified to use only one negation operation
148 // after the binary operation instead of one on each of the inputs.
TryMoveNegOnInputsAfterBinop(HBinaryOperation * binop)149 bool InstructionSimplifierVisitor::TryMoveNegOnInputsAfterBinop(HBinaryOperation* binop) {
150 DCHECK(binop->IsAdd() || binop->IsSub());
151 DCHECK(binop->GetLeft()->IsNeg() && binop->GetRight()->IsNeg());
152 HNeg* left_neg = binop->GetLeft()->AsNeg();
153 HNeg* right_neg = binop->GetRight()->AsNeg();
154 if (!left_neg->HasOnlyOneNonEnvironmentUse() ||
155 !right_neg->HasOnlyOneNonEnvironmentUse()) {
156 return false;
157 }
158 // Replace code looking like
159 // NEG tmp1, a
160 // NEG tmp2, b
161 // ADD dst, tmp1, tmp2
162 // with
163 // ADD tmp, a, b
164 // NEG dst, tmp
165 // Note that we cannot optimize `(-a) + (-b)` to `-(a + b)` for floating-point.
166 // When `a` is `-0.0` and `b` is `0.0`, the former expression yields `0.0`,
167 // while the later yields `-0.0`.
168 if (!Primitive::IsIntegralType(binop->GetType())) {
169 return false;
170 }
171 binop->ReplaceInput(left_neg->GetInput(), 0);
172 binop->ReplaceInput(right_neg->GetInput(), 1);
173 left_neg->GetBlock()->RemoveInstruction(left_neg);
174 right_neg->GetBlock()->RemoveInstruction(right_neg);
175 HNeg* neg = new (GetGraph()->GetArena()) HNeg(binop->GetType(), binop);
176 binop->GetBlock()->InsertInstructionBefore(neg, binop->GetNext());
177 binop->ReplaceWithExceptInReplacementAtIndex(neg, 0);
178 RecordSimplification();
179 return true;
180 }
181
TryDeMorganNegationFactoring(HBinaryOperation * op)182 bool InstructionSimplifierVisitor::TryDeMorganNegationFactoring(HBinaryOperation* op) {
183 DCHECK(op->IsAnd() || op->IsOr()) << op->DebugName();
184 Primitive::Type type = op->GetType();
185 HInstruction* left = op->GetLeft();
186 HInstruction* right = op->GetRight();
187
188 // We can apply De Morgan's laws if both inputs are Not's and are only used
189 // by `op`.
190 if (((left->IsNot() && right->IsNot()) ||
191 (left->IsBooleanNot() && right->IsBooleanNot())) &&
192 left->HasOnlyOneNonEnvironmentUse() &&
193 right->HasOnlyOneNonEnvironmentUse()) {
194 // Replace code looking like
195 // NOT nota, a
196 // NOT notb, b
197 // AND dst, nota, notb (respectively OR)
198 // with
199 // OR or, a, b (respectively AND)
200 // NOT dest, or
201 HInstruction* src_left = left->InputAt(0);
202 HInstruction* src_right = right->InputAt(0);
203 uint32_t dex_pc = op->GetDexPc();
204
205 // Remove the negations on the inputs.
206 left->ReplaceWith(src_left);
207 right->ReplaceWith(src_right);
208 left->GetBlock()->RemoveInstruction(left);
209 right->GetBlock()->RemoveInstruction(right);
210
211 // Replace the `HAnd` or `HOr`.
212 HBinaryOperation* hbin;
213 if (op->IsAnd()) {
214 hbin = new (GetGraph()->GetArena()) HOr(type, src_left, src_right, dex_pc);
215 } else {
216 hbin = new (GetGraph()->GetArena()) HAnd(type, src_left, src_right, dex_pc);
217 }
218 HInstruction* hnot;
219 if (left->IsBooleanNot()) {
220 hnot = new (GetGraph()->GetArena()) HBooleanNot(hbin, dex_pc);
221 } else {
222 hnot = new (GetGraph()->GetArena()) HNot(type, hbin, dex_pc);
223 }
224
225 op->GetBlock()->InsertInstructionBefore(hbin, op);
226 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, hnot);
227
228 RecordSimplification();
229 return true;
230 }
231
232 return false;
233 }
234
VisitShift(HBinaryOperation * instruction)235 void InstructionSimplifierVisitor::VisitShift(HBinaryOperation* instruction) {
236 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr());
237 HConstant* input_cst = instruction->GetConstantRight();
238 HInstruction* input_other = instruction->GetLeastConstantLeft();
239
240 if (input_cst != nullptr) {
241 int64_t cst = Int64FromConstant(input_cst);
242 int64_t mask = (input_other->GetType() == Primitive::kPrimLong)
243 ? kMaxLongShiftDistance
244 : kMaxIntShiftDistance;
245 if ((cst & mask) == 0) {
246 // Replace code looking like
247 // SHL dst, src, 0
248 // with
249 // src
250 instruction->ReplaceWith(input_other);
251 instruction->GetBlock()->RemoveInstruction(instruction);
252 }
253 }
254 }
255
IsSubRegBitsMinusOther(HSub * sub,size_t reg_bits,HInstruction * other)256 static bool IsSubRegBitsMinusOther(HSub* sub, size_t reg_bits, HInstruction* other) {
257 return (sub->GetRight() == other &&
258 sub->GetLeft()->IsConstant() &&
259 (Int64FromConstant(sub->GetLeft()->AsConstant()) & (reg_bits - 1)) == 0);
260 }
261
ReplaceRotateWithRor(HBinaryOperation * op,HUShr * ushr,HShl * shl)262 bool InstructionSimplifierVisitor::ReplaceRotateWithRor(HBinaryOperation* op,
263 HUShr* ushr,
264 HShl* shl) {
265 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr()) << op->DebugName();
266 HRor* ror = new (GetGraph()->GetArena()) HRor(ushr->GetType(), ushr->GetLeft(), ushr->GetRight());
267 op->GetBlock()->ReplaceAndRemoveInstructionWith(op, ror);
268 if (!ushr->HasUses()) {
269 ushr->GetBlock()->RemoveInstruction(ushr);
270 }
271 if (!ushr->GetRight()->HasUses()) {
272 ushr->GetRight()->GetBlock()->RemoveInstruction(ushr->GetRight());
273 }
274 if (!shl->HasUses()) {
275 shl->GetBlock()->RemoveInstruction(shl);
276 }
277 if (!shl->GetRight()->HasUses()) {
278 shl->GetRight()->GetBlock()->RemoveInstruction(shl->GetRight());
279 }
280 return true;
281 }
282
283 // Try to replace a binary operation flanked by one UShr and one Shl with a bitfield rotation.
TryReplaceWithRotate(HBinaryOperation * op)284 bool InstructionSimplifierVisitor::TryReplaceWithRotate(HBinaryOperation* op) {
285 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
286 HInstruction* left = op->GetLeft();
287 HInstruction* right = op->GetRight();
288 // If we have an UShr and a Shl (in either order).
289 if ((left->IsUShr() && right->IsShl()) || (left->IsShl() && right->IsUShr())) {
290 HUShr* ushr = left->IsUShr() ? left->AsUShr() : right->AsUShr();
291 HShl* shl = left->IsShl() ? left->AsShl() : right->AsShl();
292 DCHECK(Primitive::IsIntOrLongType(ushr->GetType()));
293 if (ushr->GetType() == shl->GetType() &&
294 ushr->GetLeft() == shl->GetLeft()) {
295 if (ushr->GetRight()->IsConstant() && shl->GetRight()->IsConstant()) {
296 // Shift distances are both constant, try replacing with Ror if they
297 // add up to the register size.
298 return TryReplaceWithRotateConstantPattern(op, ushr, shl);
299 } else if (ushr->GetRight()->IsSub() || shl->GetRight()->IsSub()) {
300 // Shift distances are potentially of the form x and (reg_size - x).
301 return TryReplaceWithRotateRegisterSubPattern(op, ushr, shl);
302 } else if (ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg()) {
303 // Shift distances are potentially of the form d and -d.
304 return TryReplaceWithRotateRegisterNegPattern(op, ushr, shl);
305 }
306 }
307 }
308 return false;
309 }
310
311 // Try replacing code looking like (x >>> #rdist OP x << #ldist):
312 // UShr dst, x, #rdist
313 // Shl tmp, x, #ldist
314 // OP dst, dst, tmp
315 // or like (x >>> #rdist OP x << #-ldist):
316 // UShr dst, x, #rdist
317 // Shl tmp, x, #-ldist
318 // OP dst, dst, tmp
319 // with
320 // Ror dst, x, #rdist
TryReplaceWithRotateConstantPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)321 bool InstructionSimplifierVisitor::TryReplaceWithRotateConstantPattern(HBinaryOperation* op,
322 HUShr* ushr,
323 HShl* shl) {
324 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
325 size_t reg_bits = Primitive::ComponentSize(ushr->GetType()) * kBitsPerByte;
326 size_t rdist = Int64FromConstant(ushr->GetRight()->AsConstant());
327 size_t ldist = Int64FromConstant(shl->GetRight()->AsConstant());
328 if (((ldist + rdist) & (reg_bits - 1)) == 0) {
329 ReplaceRotateWithRor(op, ushr, shl);
330 return true;
331 }
332 return false;
333 }
334
335 // Replace code looking like (x >>> -d OP x << d):
336 // Neg neg, d
337 // UShr dst, x, neg
338 // Shl tmp, x, d
339 // OP dst, dst, tmp
340 // with
341 // Neg neg, d
342 // Ror dst, x, neg
343 // *** OR ***
344 // Replace code looking like (x >>> d OP x << -d):
345 // UShr dst, x, d
346 // Neg neg, d
347 // Shl tmp, x, neg
348 // OP dst, dst, tmp
349 // with
350 // Ror dst, x, d
TryReplaceWithRotateRegisterNegPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)351 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterNegPattern(HBinaryOperation* op,
352 HUShr* ushr,
353 HShl* shl) {
354 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
355 DCHECK(ushr->GetRight()->IsNeg() || shl->GetRight()->IsNeg());
356 bool neg_is_left = shl->GetRight()->IsNeg();
357 HNeg* neg = neg_is_left ? shl->GetRight()->AsNeg() : ushr->GetRight()->AsNeg();
358 // And the shift distance being negated is the distance being shifted the other way.
359 if (neg->InputAt(0) == (neg_is_left ? ushr->GetRight() : shl->GetRight())) {
360 ReplaceRotateWithRor(op, ushr, shl);
361 }
362 return false;
363 }
364
365 // Try replacing code looking like (x >>> d OP x << (#bits - d)):
366 // UShr dst, x, d
367 // Sub ld, #bits, d
368 // Shl tmp, x, ld
369 // OP dst, dst, tmp
370 // with
371 // Ror dst, x, d
372 // *** OR ***
373 // Replace code looking like (x >>> (#bits - d) OP x << d):
374 // Sub rd, #bits, d
375 // UShr dst, x, rd
376 // Shl tmp, x, d
377 // OP dst, dst, tmp
378 // with
379 // Neg neg, d
380 // Ror dst, x, neg
TryReplaceWithRotateRegisterSubPattern(HBinaryOperation * op,HUShr * ushr,HShl * shl)381 bool InstructionSimplifierVisitor::TryReplaceWithRotateRegisterSubPattern(HBinaryOperation* op,
382 HUShr* ushr,
383 HShl* shl) {
384 DCHECK(op->IsAdd() || op->IsXor() || op->IsOr());
385 DCHECK(ushr->GetRight()->IsSub() || shl->GetRight()->IsSub());
386 size_t reg_bits = Primitive::ComponentSize(ushr->GetType()) * kBitsPerByte;
387 HInstruction* shl_shift = shl->GetRight();
388 HInstruction* ushr_shift = ushr->GetRight();
389 if ((shl_shift->IsSub() && IsSubRegBitsMinusOther(shl_shift->AsSub(), reg_bits, ushr_shift)) ||
390 (ushr_shift->IsSub() && IsSubRegBitsMinusOther(ushr_shift->AsSub(), reg_bits, shl_shift))) {
391 return ReplaceRotateWithRor(op, ushr, shl);
392 }
393 return false;
394 }
395
VisitNullCheck(HNullCheck * null_check)396 void InstructionSimplifierVisitor::VisitNullCheck(HNullCheck* null_check) {
397 HInstruction* obj = null_check->InputAt(0);
398 if (!obj->CanBeNull()) {
399 null_check->ReplaceWith(obj);
400 null_check->GetBlock()->RemoveInstruction(null_check);
401 if (stats_ != nullptr) {
402 stats_->RecordStat(MethodCompilationStat::kRemovedNullCheck);
403 }
404 }
405 }
406
CanEnsureNotNullAt(HInstruction * input,HInstruction * at) const407 bool InstructionSimplifierVisitor::CanEnsureNotNullAt(HInstruction* input, HInstruction* at) const {
408 if (!input->CanBeNull()) {
409 return true;
410 }
411
412 for (const HUseListNode<HInstruction*>& use : input->GetUses()) {
413 HInstruction* user = use.GetUser();
414 if (user->IsNullCheck() && user->StrictlyDominates(at)) {
415 return true;
416 }
417 }
418
419 return false;
420 }
421
422 // Returns whether doing a type test between the class of `object` against `klass` has
423 // a statically known outcome. The result of the test is stored in `outcome`.
TypeCheckHasKnownOutcome(HLoadClass * klass,HInstruction * object,bool * outcome)424 static bool TypeCheckHasKnownOutcome(HLoadClass* klass, HInstruction* object, bool* outcome) {
425 DCHECK(!object->IsNullConstant()) << "Null constants should be special cased";
426 ReferenceTypeInfo obj_rti = object->GetReferenceTypeInfo();
427 ScopedObjectAccess soa(Thread::Current());
428 if (!obj_rti.IsValid()) {
429 // We run the simplifier before the reference type propagation so type info might not be
430 // available.
431 return false;
432 }
433
434 ReferenceTypeInfo class_rti = klass->GetLoadedClassRTI();
435 if (!class_rti.IsValid()) {
436 // Happens when the loaded class is unresolved.
437 return false;
438 }
439 DCHECK(class_rti.IsExact());
440 if (class_rti.IsSupertypeOf(obj_rti)) {
441 *outcome = true;
442 return true;
443 } else if (obj_rti.IsExact()) {
444 // The test failed at compile time so will also fail at runtime.
445 *outcome = false;
446 return true;
447 } else if (!class_rti.IsInterface()
448 && !obj_rti.IsInterface()
449 && !obj_rti.IsSupertypeOf(class_rti)) {
450 // Different type hierarchy. The test will fail.
451 *outcome = false;
452 return true;
453 }
454 return false;
455 }
456
VisitCheckCast(HCheckCast * check_cast)457 void InstructionSimplifierVisitor::VisitCheckCast(HCheckCast* check_cast) {
458 HInstruction* object = check_cast->InputAt(0);
459 HLoadClass* load_class = check_cast->InputAt(1)->AsLoadClass();
460 if (load_class->NeedsAccessCheck()) {
461 // If we need to perform an access check we cannot remove the instruction.
462 return;
463 }
464
465 if (CanEnsureNotNullAt(object, check_cast)) {
466 check_cast->ClearMustDoNullCheck();
467 }
468
469 if (object->IsNullConstant()) {
470 check_cast->GetBlock()->RemoveInstruction(check_cast);
471 MaybeRecordStat(MethodCompilationStat::kRemovedCheckedCast);
472 return;
473 }
474
475 // Note: The `outcome` is initialized to please valgrind - the compiler can reorder
476 // the return value check with the `outcome` check, b/27651442 .
477 bool outcome = false;
478 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) {
479 if (outcome) {
480 check_cast->GetBlock()->RemoveInstruction(check_cast);
481 MaybeRecordStat(MethodCompilationStat::kRemovedCheckedCast);
482 if (!load_class->HasUses()) {
483 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw.
484 // However, here we know that it cannot because the checkcast was successfull, hence
485 // the class was already loaded.
486 load_class->GetBlock()->RemoveInstruction(load_class);
487 }
488 } else {
489 // Don't do anything for exceptional cases for now. Ideally we should remove
490 // all instructions and blocks this instruction dominates.
491 }
492 }
493 }
494
VisitInstanceOf(HInstanceOf * instruction)495 void InstructionSimplifierVisitor::VisitInstanceOf(HInstanceOf* instruction) {
496 HInstruction* object = instruction->InputAt(0);
497 HLoadClass* load_class = instruction->InputAt(1)->AsLoadClass();
498 if (load_class->NeedsAccessCheck()) {
499 // If we need to perform an access check we cannot remove the instruction.
500 return;
501 }
502
503 bool can_be_null = true;
504 if (CanEnsureNotNullAt(object, instruction)) {
505 can_be_null = false;
506 instruction->ClearMustDoNullCheck();
507 }
508
509 HGraph* graph = GetGraph();
510 if (object->IsNullConstant()) {
511 MaybeRecordStat(kRemovedInstanceOf);
512 instruction->ReplaceWith(graph->GetIntConstant(0));
513 instruction->GetBlock()->RemoveInstruction(instruction);
514 RecordSimplification();
515 return;
516 }
517
518 // Note: The `outcome` is initialized to please valgrind - the compiler can reorder
519 // the return value check with the `outcome` check, b/27651442 .
520 bool outcome = false;
521 if (TypeCheckHasKnownOutcome(load_class, object, &outcome)) {
522 MaybeRecordStat(kRemovedInstanceOf);
523 if (outcome && can_be_null) {
524 // Type test will succeed, we just need a null test.
525 HNotEqual* test = new (graph->GetArena()) HNotEqual(graph->GetNullConstant(), object);
526 instruction->GetBlock()->InsertInstructionBefore(test, instruction);
527 instruction->ReplaceWith(test);
528 } else {
529 // We've statically determined the result of the instanceof.
530 instruction->ReplaceWith(graph->GetIntConstant(outcome));
531 }
532 RecordSimplification();
533 instruction->GetBlock()->RemoveInstruction(instruction);
534 if (outcome && !load_class->HasUses()) {
535 // We cannot rely on DCE to remove the class because the `HLoadClass` thinks it can throw.
536 // However, here we know that it cannot because the instanceof check was successfull, hence
537 // the class was already loaded.
538 load_class->GetBlock()->RemoveInstruction(load_class);
539 }
540 }
541 }
542
VisitInstanceFieldSet(HInstanceFieldSet * instruction)543 void InstructionSimplifierVisitor::VisitInstanceFieldSet(HInstanceFieldSet* instruction) {
544 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot)
545 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) {
546 instruction->ClearValueCanBeNull();
547 }
548 }
549
VisitStaticFieldSet(HStaticFieldSet * instruction)550 void InstructionSimplifierVisitor::VisitStaticFieldSet(HStaticFieldSet* instruction) {
551 if ((instruction->GetValue()->GetType() == Primitive::kPrimNot)
552 && CanEnsureNotNullAt(instruction->GetValue(), instruction)) {
553 instruction->ClearValueCanBeNull();
554 }
555 }
556
GetOppositeConditionSwapOps(ArenaAllocator * arena,HInstruction * cond)557 static HCondition* GetOppositeConditionSwapOps(ArenaAllocator* arena, HInstruction* cond) {
558 HInstruction *lhs = cond->InputAt(0);
559 HInstruction *rhs = cond->InputAt(1);
560 switch (cond->GetKind()) {
561 case HInstruction::kEqual:
562 return new (arena) HEqual(rhs, lhs);
563 case HInstruction::kNotEqual:
564 return new (arena) HNotEqual(rhs, lhs);
565 case HInstruction::kLessThan:
566 return new (arena) HGreaterThan(rhs, lhs);
567 case HInstruction::kLessThanOrEqual:
568 return new (arena) HGreaterThanOrEqual(rhs, lhs);
569 case HInstruction::kGreaterThan:
570 return new (arena) HLessThan(rhs, lhs);
571 case HInstruction::kGreaterThanOrEqual:
572 return new (arena) HLessThanOrEqual(rhs, lhs);
573 case HInstruction::kBelow:
574 return new (arena) HAbove(rhs, lhs);
575 case HInstruction::kBelowOrEqual:
576 return new (arena) HAboveOrEqual(rhs, lhs);
577 case HInstruction::kAbove:
578 return new (arena) HBelow(rhs, lhs);
579 case HInstruction::kAboveOrEqual:
580 return new (arena) HBelowOrEqual(rhs, lhs);
581 default:
582 LOG(FATAL) << "Unknown ConditionType " << cond->GetKind();
583 }
584 return nullptr;
585 }
586
VisitEqual(HEqual * equal)587 void InstructionSimplifierVisitor::VisitEqual(HEqual* equal) {
588 HInstruction* input_const = equal->GetConstantRight();
589 if (input_const != nullptr) {
590 HInstruction* input_value = equal->GetLeastConstantLeft();
591 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) {
592 HBasicBlock* block = equal->GetBlock();
593 // We are comparing the boolean to a constant which is of type int and can
594 // be any constant.
595 if (input_const->AsIntConstant()->IsTrue()) {
596 // Replace (bool_value == true) with bool_value
597 equal->ReplaceWith(input_value);
598 block->RemoveInstruction(equal);
599 RecordSimplification();
600 } else if (input_const->AsIntConstant()->IsFalse()) {
601 equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, equal));
602 block->RemoveInstruction(equal);
603 RecordSimplification();
604 } else {
605 // Replace (bool_value == integer_not_zero_nor_one_constant) with false
606 equal->ReplaceWith(GetGraph()->GetIntConstant(0));
607 block->RemoveInstruction(equal);
608 RecordSimplification();
609 }
610 } else {
611 VisitCondition(equal);
612 }
613 } else {
614 VisitCondition(equal);
615 }
616 }
617
VisitNotEqual(HNotEqual * not_equal)618 void InstructionSimplifierVisitor::VisitNotEqual(HNotEqual* not_equal) {
619 HInstruction* input_const = not_equal->GetConstantRight();
620 if (input_const != nullptr) {
621 HInstruction* input_value = not_equal->GetLeastConstantLeft();
622 if (input_value->GetType() == Primitive::kPrimBoolean && input_const->IsIntConstant()) {
623 HBasicBlock* block = not_equal->GetBlock();
624 // We are comparing the boolean to a constant which is of type int and can
625 // be any constant.
626 if (input_const->AsIntConstant()->IsTrue()) {
627 not_equal->ReplaceWith(GetGraph()->InsertOppositeCondition(input_value, not_equal));
628 block->RemoveInstruction(not_equal);
629 RecordSimplification();
630 } else if (input_const->AsIntConstant()->IsFalse()) {
631 // Replace (bool_value != false) with bool_value
632 not_equal->ReplaceWith(input_value);
633 block->RemoveInstruction(not_equal);
634 RecordSimplification();
635 } else {
636 // Replace (bool_value != integer_not_zero_nor_one_constant) with true
637 not_equal->ReplaceWith(GetGraph()->GetIntConstant(1));
638 block->RemoveInstruction(not_equal);
639 RecordSimplification();
640 }
641 } else {
642 VisitCondition(not_equal);
643 }
644 } else {
645 VisitCondition(not_equal);
646 }
647 }
648
VisitBooleanNot(HBooleanNot * bool_not)649 void InstructionSimplifierVisitor::VisitBooleanNot(HBooleanNot* bool_not) {
650 HInstruction* input = bool_not->InputAt(0);
651 HInstruction* replace_with = nullptr;
652
653 if (input->IsIntConstant()) {
654 // Replace !(true/false) with false/true.
655 if (input->AsIntConstant()->IsTrue()) {
656 replace_with = GetGraph()->GetIntConstant(0);
657 } else {
658 DCHECK(input->AsIntConstant()->IsFalse()) << input->AsIntConstant()->GetValue();
659 replace_with = GetGraph()->GetIntConstant(1);
660 }
661 } else if (input->IsBooleanNot()) {
662 // Replace (!(!bool_value)) with bool_value.
663 replace_with = input->InputAt(0);
664 } else if (input->IsCondition() &&
665 // Don't change FP compares. The definition of compares involving
666 // NaNs forces the compares to be done as written by the user.
667 !Primitive::IsFloatingPointType(input->InputAt(0)->GetType())) {
668 // Replace condition with its opposite.
669 replace_with = GetGraph()->InsertOppositeCondition(input->AsCondition(), bool_not);
670 }
671
672 if (replace_with != nullptr) {
673 bool_not->ReplaceWith(replace_with);
674 bool_not->GetBlock()->RemoveInstruction(bool_not);
675 RecordSimplification();
676 }
677 }
678
VisitSelect(HSelect * select)679 void InstructionSimplifierVisitor::VisitSelect(HSelect* select) {
680 HInstruction* replace_with = nullptr;
681 HInstruction* condition = select->GetCondition();
682 HInstruction* true_value = select->GetTrueValue();
683 HInstruction* false_value = select->GetFalseValue();
684
685 if (condition->IsBooleanNot()) {
686 // Change ((!cond) ? x : y) to (cond ? y : x).
687 condition = condition->InputAt(0);
688 std::swap(true_value, false_value);
689 select->ReplaceInput(false_value, 0);
690 select->ReplaceInput(true_value, 1);
691 select->ReplaceInput(condition, 2);
692 RecordSimplification();
693 }
694
695 if (true_value == false_value) {
696 // Replace (cond ? x : x) with (x).
697 replace_with = true_value;
698 } else if (condition->IsIntConstant()) {
699 if (condition->AsIntConstant()->IsTrue()) {
700 // Replace (true ? x : y) with (x).
701 replace_with = true_value;
702 } else {
703 // Replace (false ? x : y) with (y).
704 DCHECK(condition->AsIntConstant()->IsFalse()) << condition->AsIntConstant()->GetValue();
705 replace_with = false_value;
706 }
707 } else if (true_value->IsIntConstant() && false_value->IsIntConstant()) {
708 if (true_value->AsIntConstant()->IsTrue() && false_value->AsIntConstant()->IsFalse()) {
709 // Replace (cond ? true : false) with (cond).
710 replace_with = condition;
711 } else if (true_value->AsIntConstant()->IsFalse() && false_value->AsIntConstant()->IsTrue()) {
712 // Replace (cond ? false : true) with (!cond).
713 replace_with = GetGraph()->InsertOppositeCondition(condition, select);
714 }
715 }
716
717 if (replace_with != nullptr) {
718 select->ReplaceWith(replace_with);
719 select->GetBlock()->RemoveInstruction(select);
720 RecordSimplification();
721 }
722 }
723
VisitIf(HIf * instruction)724 void InstructionSimplifierVisitor::VisitIf(HIf* instruction) {
725 HInstruction* condition = instruction->InputAt(0);
726 if (condition->IsBooleanNot()) {
727 // Swap successors if input is negated.
728 instruction->ReplaceInput(condition->InputAt(0), 0);
729 instruction->GetBlock()->SwapSuccessors();
730 RecordSimplification();
731 }
732 }
733
VisitArrayLength(HArrayLength * instruction)734 void InstructionSimplifierVisitor::VisitArrayLength(HArrayLength* instruction) {
735 HInstruction* input = instruction->InputAt(0);
736 // If the array is a NewArray with constant size, replace the array length
737 // with the constant instruction. This helps the bounds check elimination phase.
738 if (input->IsNewArray()) {
739 input = input->InputAt(0);
740 if (input->IsIntConstant()) {
741 instruction->ReplaceWith(input);
742 }
743 }
744 }
745
VisitArraySet(HArraySet * instruction)746 void InstructionSimplifierVisitor::VisitArraySet(HArraySet* instruction) {
747 HInstruction* value = instruction->GetValue();
748 if (value->GetType() != Primitive::kPrimNot) return;
749
750 if (CanEnsureNotNullAt(value, instruction)) {
751 instruction->ClearValueCanBeNull();
752 }
753
754 if (value->IsArrayGet()) {
755 if (value->AsArrayGet()->GetArray() == instruction->GetArray()) {
756 // If the code is just swapping elements in the array, no need for a type check.
757 instruction->ClearNeedsTypeCheck();
758 return;
759 }
760 }
761
762 if (value->IsNullConstant()) {
763 instruction->ClearNeedsTypeCheck();
764 return;
765 }
766
767 ScopedObjectAccess soa(Thread::Current());
768 ReferenceTypeInfo array_rti = instruction->GetArray()->GetReferenceTypeInfo();
769 ReferenceTypeInfo value_rti = value->GetReferenceTypeInfo();
770 if (!array_rti.IsValid()) {
771 return;
772 }
773
774 if (value_rti.IsValid() && array_rti.CanArrayHold(value_rti)) {
775 instruction->ClearNeedsTypeCheck();
776 return;
777 }
778
779 if (array_rti.IsObjectArray()) {
780 if (array_rti.IsExact()) {
781 instruction->ClearNeedsTypeCheck();
782 return;
783 }
784 instruction->SetStaticTypeOfArrayIsObjectArray();
785 }
786 }
787
IsTypeConversionImplicit(Primitive::Type input_type,Primitive::Type result_type)788 static bool IsTypeConversionImplicit(Primitive::Type input_type, Primitive::Type result_type) {
789 // Invariant: We should never generate a conversion to a Boolean value.
790 DCHECK_NE(Primitive::kPrimBoolean, result_type);
791
792 // Besides conversion to the same type, widening integral conversions are implicit,
793 // excluding conversions to long and the byte->char conversion where we need to
794 // clear the high 16 bits of the 32-bit sign-extended representation of byte.
795 return result_type == input_type ||
796 (result_type == Primitive::kPrimInt && (input_type == Primitive::kPrimBoolean ||
797 input_type == Primitive::kPrimByte ||
798 input_type == Primitive::kPrimShort ||
799 input_type == Primitive::kPrimChar)) ||
800 (result_type == Primitive::kPrimChar && input_type == Primitive::kPrimBoolean) ||
801 (result_type == Primitive::kPrimShort && (input_type == Primitive::kPrimBoolean ||
802 input_type == Primitive::kPrimByte)) ||
803 (result_type == Primitive::kPrimByte && input_type == Primitive::kPrimBoolean);
804 }
805
IsTypeConversionLossless(Primitive::Type input_type,Primitive::Type result_type)806 static bool IsTypeConversionLossless(Primitive::Type input_type, Primitive::Type result_type) {
807 // The conversion to a larger type is loss-less with the exception of two cases,
808 // - conversion to char, the only unsigned type, where we may lose some bits, and
809 // - conversion from float to long, the only FP to integral conversion with smaller FP type.
810 // For integral to FP conversions this holds because the FP mantissa is large enough.
811 DCHECK_NE(input_type, result_type);
812 return Primitive::ComponentSize(result_type) > Primitive::ComponentSize(input_type) &&
813 result_type != Primitive::kPrimChar &&
814 !(result_type == Primitive::kPrimLong && input_type == Primitive::kPrimFloat);
815 }
816
VisitTypeConversion(HTypeConversion * instruction)817 void InstructionSimplifierVisitor::VisitTypeConversion(HTypeConversion* instruction) {
818 HInstruction* input = instruction->GetInput();
819 Primitive::Type input_type = input->GetType();
820 Primitive::Type result_type = instruction->GetResultType();
821 if (IsTypeConversionImplicit(input_type, result_type)) {
822 // Remove the implicit conversion; this includes conversion to the same type.
823 instruction->ReplaceWith(input);
824 instruction->GetBlock()->RemoveInstruction(instruction);
825 RecordSimplification();
826 return;
827 }
828
829 if (input->IsTypeConversion()) {
830 HTypeConversion* input_conversion = input->AsTypeConversion();
831 HInstruction* original_input = input_conversion->GetInput();
832 Primitive::Type original_type = original_input->GetType();
833
834 // When the first conversion is lossless, a direct conversion from the original type
835 // to the final type yields the same result, even for a lossy second conversion, for
836 // example float->double->int or int->double->float.
837 bool is_first_conversion_lossless = IsTypeConversionLossless(original_type, input_type);
838
839 // For integral conversions, see if the first conversion loses only bits that the second
840 // doesn't need, i.e. the final type is no wider than the intermediate. If so, direct
841 // conversion yields the same result, for example long->int->short or int->char->short.
842 bool integral_conversions_with_non_widening_second =
843 Primitive::IsIntegralType(input_type) &&
844 Primitive::IsIntegralType(original_type) &&
845 Primitive::IsIntegralType(result_type) &&
846 Primitive::ComponentSize(result_type) <= Primitive::ComponentSize(input_type);
847
848 if (is_first_conversion_lossless || integral_conversions_with_non_widening_second) {
849 // If the merged conversion is implicit, do the simplification unconditionally.
850 if (IsTypeConversionImplicit(original_type, result_type)) {
851 instruction->ReplaceWith(original_input);
852 instruction->GetBlock()->RemoveInstruction(instruction);
853 if (!input_conversion->HasUses()) {
854 // Don't wait for DCE.
855 input_conversion->GetBlock()->RemoveInstruction(input_conversion);
856 }
857 RecordSimplification();
858 return;
859 }
860 // Otherwise simplify only if the first conversion has no other use.
861 if (input_conversion->HasOnlyOneNonEnvironmentUse()) {
862 input_conversion->ReplaceWith(original_input);
863 input_conversion->GetBlock()->RemoveInstruction(input_conversion);
864 RecordSimplification();
865 return;
866 }
867 }
868 } else if (input->IsAnd() && Primitive::IsIntegralType(result_type)) {
869 DCHECK(Primitive::IsIntegralType(input_type));
870 HAnd* input_and = input->AsAnd();
871 HConstant* constant = input_and->GetConstantRight();
872 if (constant != nullptr) {
873 int64_t value = Int64FromConstant(constant);
874 DCHECK_NE(value, -1); // "& -1" would have been optimized away in VisitAnd().
875 size_t trailing_ones = CTZ(~static_cast<uint64_t>(value));
876 if (trailing_ones >= kBitsPerByte * Primitive::ComponentSize(result_type)) {
877 // The `HAnd` is useless, for example in `(byte) (x & 0xff)`, get rid of it.
878 HInstruction* original_input = input_and->GetLeastConstantLeft();
879 if (IsTypeConversionImplicit(original_input->GetType(), result_type)) {
880 instruction->ReplaceWith(original_input);
881 instruction->GetBlock()->RemoveInstruction(instruction);
882 RecordSimplification();
883 return;
884 } else if (input->HasOnlyOneNonEnvironmentUse()) {
885 input_and->ReplaceWith(original_input);
886 input_and->GetBlock()->RemoveInstruction(input_and);
887 RecordSimplification();
888 return;
889 }
890 }
891 }
892 }
893 }
894
VisitAdd(HAdd * instruction)895 void InstructionSimplifierVisitor::VisitAdd(HAdd* instruction) {
896 HConstant* input_cst = instruction->GetConstantRight();
897 HInstruction* input_other = instruction->GetLeastConstantLeft();
898 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) {
899 // Replace code looking like
900 // ADD dst, src, 0
901 // with
902 // src
903 // Note that we cannot optimize `x + 0.0` to `x` for floating-point. When
904 // `x` is `-0.0`, the former expression yields `0.0`, while the later
905 // yields `-0.0`.
906 if (Primitive::IsIntegralType(instruction->GetType())) {
907 instruction->ReplaceWith(input_other);
908 instruction->GetBlock()->RemoveInstruction(instruction);
909 return;
910 }
911 }
912
913 HInstruction* left = instruction->GetLeft();
914 HInstruction* right = instruction->GetRight();
915 bool left_is_neg = left->IsNeg();
916 bool right_is_neg = right->IsNeg();
917
918 if (left_is_neg && right_is_neg) {
919 if (TryMoveNegOnInputsAfterBinop(instruction)) {
920 return;
921 }
922 }
923
924 HNeg* neg = left_is_neg ? left->AsNeg() : right->AsNeg();
925 if ((left_is_neg ^ right_is_neg) && neg->HasOnlyOneNonEnvironmentUse()) {
926 // Replace code looking like
927 // NEG tmp, b
928 // ADD dst, a, tmp
929 // with
930 // SUB dst, a, b
931 // We do not perform the optimization if the input negation has environment
932 // uses or multiple non-environment uses as it could lead to worse code. In
933 // particular, we do not want the live range of `b` to be extended if we are
934 // not sure the initial 'NEG' instruction can be removed.
935 HInstruction* other = left_is_neg ? right : left;
936 HSub* sub = new(GetGraph()->GetArena()) HSub(instruction->GetType(), other, neg->GetInput());
937 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, sub);
938 RecordSimplification();
939 neg->GetBlock()->RemoveInstruction(neg);
940 return;
941 }
942
943 TryReplaceWithRotate(instruction);
944 }
945
VisitAnd(HAnd * instruction)946 void InstructionSimplifierVisitor::VisitAnd(HAnd* instruction) {
947 HConstant* input_cst = instruction->GetConstantRight();
948 HInstruction* input_other = instruction->GetLeastConstantLeft();
949
950 if (input_cst != nullptr) {
951 int64_t value = Int64FromConstant(input_cst);
952 if (value == -1) {
953 // Replace code looking like
954 // AND dst, src, 0xFFF...FF
955 // with
956 // src
957 instruction->ReplaceWith(input_other);
958 instruction->GetBlock()->RemoveInstruction(instruction);
959 RecordSimplification();
960 return;
961 }
962 // Eliminate And from UShr+And if the And-mask contains all the bits that
963 // can be non-zero after UShr. Transform Shr+And to UShr if the And-mask
964 // precisely clears the shifted-in sign bits.
965 if ((input_other->IsUShr() || input_other->IsShr()) && input_other->InputAt(1)->IsConstant()) {
966 size_t reg_bits = (instruction->GetResultType() == Primitive::kPrimLong) ? 64 : 32;
967 size_t shift = Int64FromConstant(input_other->InputAt(1)->AsConstant()) & (reg_bits - 1);
968 size_t num_tail_bits_set = CTZ(value + 1);
969 if ((num_tail_bits_set >= reg_bits - shift) && input_other->IsUShr()) {
970 // This AND clears only bits known to be clear, for example "(x >>> 24) & 0xff".
971 instruction->ReplaceWith(input_other);
972 instruction->GetBlock()->RemoveInstruction(instruction);
973 RecordSimplification();
974 return;
975 } else if ((num_tail_bits_set == reg_bits - shift) && IsPowerOfTwo(value + 1) &&
976 input_other->HasOnlyOneNonEnvironmentUse()) {
977 DCHECK(input_other->IsShr()); // For UShr, we would have taken the branch above.
978 // Replace SHR+AND with USHR, for example "(x >> 24) & 0xff" -> "x >>> 24".
979 HUShr* ushr = new (GetGraph()->GetArena()) HUShr(instruction->GetType(),
980 input_other->InputAt(0),
981 input_other->InputAt(1),
982 input_other->GetDexPc());
983 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, ushr);
984 input_other->GetBlock()->RemoveInstruction(input_other);
985 RecordSimplification();
986 return;
987 }
988 }
989 }
990
991 // We assume that GVN has run before, so we only perform a pointer comparison.
992 // If for some reason the values are equal but the pointers are different, we
993 // are still correct and only miss an optimization opportunity.
994 if (instruction->GetLeft() == instruction->GetRight()) {
995 // Replace code looking like
996 // AND dst, src, src
997 // with
998 // src
999 instruction->ReplaceWith(instruction->GetLeft());
1000 instruction->GetBlock()->RemoveInstruction(instruction);
1001 return;
1002 }
1003
1004 TryDeMorganNegationFactoring(instruction);
1005 }
1006
VisitGreaterThan(HGreaterThan * condition)1007 void InstructionSimplifierVisitor::VisitGreaterThan(HGreaterThan* condition) {
1008 VisitCondition(condition);
1009 }
1010
VisitGreaterThanOrEqual(HGreaterThanOrEqual * condition)1011 void InstructionSimplifierVisitor::VisitGreaterThanOrEqual(HGreaterThanOrEqual* condition) {
1012 VisitCondition(condition);
1013 }
1014
VisitLessThan(HLessThan * condition)1015 void InstructionSimplifierVisitor::VisitLessThan(HLessThan* condition) {
1016 VisitCondition(condition);
1017 }
1018
VisitLessThanOrEqual(HLessThanOrEqual * condition)1019 void InstructionSimplifierVisitor::VisitLessThanOrEqual(HLessThanOrEqual* condition) {
1020 VisitCondition(condition);
1021 }
1022
VisitBelow(HBelow * condition)1023 void InstructionSimplifierVisitor::VisitBelow(HBelow* condition) {
1024 VisitCondition(condition);
1025 }
1026
VisitBelowOrEqual(HBelowOrEqual * condition)1027 void InstructionSimplifierVisitor::VisitBelowOrEqual(HBelowOrEqual* condition) {
1028 VisitCondition(condition);
1029 }
1030
VisitAbove(HAbove * condition)1031 void InstructionSimplifierVisitor::VisitAbove(HAbove* condition) {
1032 VisitCondition(condition);
1033 }
1034
VisitAboveOrEqual(HAboveOrEqual * condition)1035 void InstructionSimplifierVisitor::VisitAboveOrEqual(HAboveOrEqual* condition) {
1036 VisitCondition(condition);
1037 }
1038
VisitCondition(HCondition * condition)1039 void InstructionSimplifierVisitor::VisitCondition(HCondition* condition) {
1040 // Reverse condition if left is constant. Our code generators prefer constant
1041 // on the right hand side.
1042 if (condition->GetLeft()->IsConstant() && !condition->GetRight()->IsConstant()) {
1043 HBasicBlock* block = condition->GetBlock();
1044 HCondition* replacement = GetOppositeConditionSwapOps(block->GetGraph()->GetArena(), condition);
1045 // If it is a fp we must set the opposite bias.
1046 if (replacement != nullptr) {
1047 if (condition->IsLtBias()) {
1048 replacement->SetBias(ComparisonBias::kGtBias);
1049 } else if (condition->IsGtBias()) {
1050 replacement->SetBias(ComparisonBias::kLtBias);
1051 }
1052 block->ReplaceAndRemoveInstructionWith(condition, replacement);
1053 RecordSimplification();
1054
1055 condition = replacement;
1056 }
1057 }
1058
1059 HInstruction* left = condition->GetLeft();
1060 HInstruction* right = condition->GetRight();
1061
1062 // Try to fold an HCompare into this HCondition.
1063
1064 // We can only replace an HCondition which compares a Compare to 0.
1065 // Both 'dx' and 'jack' generate a compare to 0 when compiling a
1066 // condition with a long, float or double comparison as input.
1067 if (!left->IsCompare() || !right->IsConstant() || right->AsIntConstant()->GetValue() != 0) {
1068 // Conversion is not possible.
1069 return;
1070 }
1071
1072 // Is the Compare only used for this purpose?
1073 if (!left->GetUses().HasExactlyOneElement()) {
1074 // Someone else also wants the result of the compare.
1075 return;
1076 }
1077
1078 if (!left->GetEnvUses().empty()) {
1079 // There is a reference to the compare result in an environment. Do we really need it?
1080 if (GetGraph()->IsDebuggable()) {
1081 return;
1082 }
1083
1084 // We have to ensure that there are no deopt points in the sequence.
1085 if (left->HasAnyEnvironmentUseBefore(condition)) {
1086 return;
1087 }
1088 }
1089
1090 // Clean up any environment uses from the HCompare, if any.
1091 left->RemoveEnvironmentUsers();
1092
1093 // We have decided to fold the HCompare into the HCondition. Transfer the information.
1094 condition->SetBias(left->AsCompare()->GetBias());
1095
1096 // Replace the operands of the HCondition.
1097 condition->ReplaceInput(left->InputAt(0), 0);
1098 condition->ReplaceInput(left->InputAt(1), 1);
1099
1100 // Remove the HCompare.
1101 left->GetBlock()->RemoveInstruction(left);
1102
1103 RecordSimplification();
1104 }
1105
VisitDiv(HDiv * instruction)1106 void InstructionSimplifierVisitor::VisitDiv(HDiv* instruction) {
1107 HConstant* input_cst = instruction->GetConstantRight();
1108 HInstruction* input_other = instruction->GetLeastConstantLeft();
1109 Primitive::Type type = instruction->GetType();
1110
1111 if ((input_cst != nullptr) && input_cst->IsOne()) {
1112 // Replace code looking like
1113 // DIV dst, src, 1
1114 // with
1115 // src
1116 instruction->ReplaceWith(input_other);
1117 instruction->GetBlock()->RemoveInstruction(instruction);
1118 return;
1119 }
1120
1121 if ((input_cst != nullptr) && input_cst->IsMinusOne()) {
1122 // Replace code looking like
1123 // DIV dst, src, -1
1124 // with
1125 // NEG dst, src
1126 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
1127 instruction, new (GetGraph()->GetArena()) HNeg(type, input_other));
1128 RecordSimplification();
1129 return;
1130 }
1131
1132 if ((input_cst != nullptr) && Primitive::IsFloatingPointType(type)) {
1133 // Try replacing code looking like
1134 // DIV dst, src, constant
1135 // with
1136 // MUL dst, src, 1 / constant
1137 HConstant* reciprocal = nullptr;
1138 if (type == Primitive::Primitive::kPrimDouble) {
1139 double value = input_cst->AsDoubleConstant()->GetValue();
1140 if (CanDivideByReciprocalMultiplyDouble(bit_cast<int64_t, double>(value))) {
1141 reciprocal = GetGraph()->GetDoubleConstant(1.0 / value);
1142 }
1143 } else {
1144 DCHECK_EQ(type, Primitive::kPrimFloat);
1145 float value = input_cst->AsFloatConstant()->GetValue();
1146 if (CanDivideByReciprocalMultiplyFloat(bit_cast<int32_t, float>(value))) {
1147 reciprocal = GetGraph()->GetFloatConstant(1.0f / value);
1148 }
1149 }
1150
1151 if (reciprocal != nullptr) {
1152 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(
1153 instruction, new (GetGraph()->GetArena()) HMul(type, input_other, reciprocal));
1154 RecordSimplification();
1155 return;
1156 }
1157 }
1158 }
1159
VisitMul(HMul * instruction)1160 void InstructionSimplifierVisitor::VisitMul(HMul* instruction) {
1161 HConstant* input_cst = instruction->GetConstantRight();
1162 HInstruction* input_other = instruction->GetLeastConstantLeft();
1163 Primitive::Type type = instruction->GetType();
1164 HBasicBlock* block = instruction->GetBlock();
1165 ArenaAllocator* allocator = GetGraph()->GetArena();
1166
1167 if (input_cst == nullptr) {
1168 return;
1169 }
1170
1171 if (input_cst->IsOne()) {
1172 // Replace code looking like
1173 // MUL dst, src, 1
1174 // with
1175 // src
1176 instruction->ReplaceWith(input_other);
1177 instruction->GetBlock()->RemoveInstruction(instruction);
1178 return;
1179 }
1180
1181 if (input_cst->IsMinusOne() &&
1182 (Primitive::IsFloatingPointType(type) || Primitive::IsIntOrLongType(type))) {
1183 // Replace code looking like
1184 // MUL dst, src, -1
1185 // with
1186 // NEG dst, src
1187 HNeg* neg = new (allocator) HNeg(type, input_other);
1188 block->ReplaceAndRemoveInstructionWith(instruction, neg);
1189 RecordSimplification();
1190 return;
1191 }
1192
1193 if (Primitive::IsFloatingPointType(type) &&
1194 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->GetValue() == 2.0f) ||
1195 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->GetValue() == 2.0))) {
1196 // Replace code looking like
1197 // FP_MUL dst, src, 2.0
1198 // with
1199 // FP_ADD dst, src, src
1200 // The 'int' and 'long' cases are handled below.
1201 block->ReplaceAndRemoveInstructionWith(instruction,
1202 new (allocator) HAdd(type, input_other, input_other));
1203 RecordSimplification();
1204 return;
1205 }
1206
1207 if (Primitive::IsIntOrLongType(type)) {
1208 int64_t factor = Int64FromConstant(input_cst);
1209 // Even though constant propagation also takes care of the zero case, other
1210 // optimizations can lead to having a zero multiplication.
1211 if (factor == 0) {
1212 // Replace code looking like
1213 // MUL dst, src, 0
1214 // with
1215 // 0
1216 instruction->ReplaceWith(input_cst);
1217 instruction->GetBlock()->RemoveInstruction(instruction);
1218 } else if (IsPowerOfTwo(factor)) {
1219 // Replace code looking like
1220 // MUL dst, src, pow_of_2
1221 // with
1222 // SHL dst, src, log2(pow_of_2)
1223 HIntConstant* shift = GetGraph()->GetIntConstant(WhichPowerOf2(factor));
1224 HShl* shl = new (allocator) HShl(type, input_other, shift);
1225 block->ReplaceAndRemoveInstructionWith(instruction, shl);
1226 RecordSimplification();
1227 } else if (IsPowerOfTwo(factor - 1)) {
1228 // Transform code looking like
1229 // MUL dst, src, (2^n + 1)
1230 // into
1231 // SHL tmp, src, n
1232 // ADD dst, src, tmp
1233 HShl* shl = new (allocator) HShl(type,
1234 input_other,
1235 GetGraph()->GetIntConstant(WhichPowerOf2(factor - 1)));
1236 HAdd* add = new (allocator) HAdd(type, input_other, shl);
1237
1238 block->InsertInstructionBefore(shl, instruction);
1239 block->ReplaceAndRemoveInstructionWith(instruction, add);
1240 RecordSimplification();
1241 } else if (IsPowerOfTwo(factor + 1)) {
1242 // Transform code looking like
1243 // MUL dst, src, (2^n - 1)
1244 // into
1245 // SHL tmp, src, n
1246 // SUB dst, tmp, src
1247 HShl* shl = new (allocator) HShl(type,
1248 input_other,
1249 GetGraph()->GetIntConstant(WhichPowerOf2(factor + 1)));
1250 HSub* sub = new (allocator) HSub(type, shl, input_other);
1251
1252 block->InsertInstructionBefore(shl, instruction);
1253 block->ReplaceAndRemoveInstructionWith(instruction, sub);
1254 RecordSimplification();
1255 }
1256 }
1257 }
1258
VisitNeg(HNeg * instruction)1259 void InstructionSimplifierVisitor::VisitNeg(HNeg* instruction) {
1260 HInstruction* input = instruction->GetInput();
1261 if (input->IsNeg()) {
1262 // Replace code looking like
1263 // NEG tmp, src
1264 // NEG dst, tmp
1265 // with
1266 // src
1267 HNeg* previous_neg = input->AsNeg();
1268 instruction->ReplaceWith(previous_neg->GetInput());
1269 instruction->GetBlock()->RemoveInstruction(instruction);
1270 // We perform the optimization even if the input negation has environment
1271 // uses since it allows removing the current instruction. But we only delete
1272 // the input negation only if it is does not have any uses left.
1273 if (!previous_neg->HasUses()) {
1274 previous_neg->GetBlock()->RemoveInstruction(previous_neg);
1275 }
1276 RecordSimplification();
1277 return;
1278 }
1279
1280 if (input->IsSub() && input->HasOnlyOneNonEnvironmentUse() &&
1281 !Primitive::IsFloatingPointType(input->GetType())) {
1282 // Replace code looking like
1283 // SUB tmp, a, b
1284 // NEG dst, tmp
1285 // with
1286 // SUB dst, b, a
1287 // We do not perform the optimization if the input subtraction has
1288 // environment uses or multiple non-environment uses as it could lead to
1289 // worse code. In particular, we do not want the live ranges of `a` and `b`
1290 // to be extended if we are not sure the initial 'SUB' instruction can be
1291 // removed.
1292 // We do not perform optimization for fp because we could lose the sign of zero.
1293 HSub* sub = input->AsSub();
1294 HSub* new_sub =
1295 new (GetGraph()->GetArena()) HSub(instruction->GetType(), sub->GetRight(), sub->GetLeft());
1296 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, new_sub);
1297 if (!sub->HasUses()) {
1298 sub->GetBlock()->RemoveInstruction(sub);
1299 }
1300 RecordSimplification();
1301 }
1302 }
1303
VisitNot(HNot * instruction)1304 void InstructionSimplifierVisitor::VisitNot(HNot* instruction) {
1305 HInstruction* input = instruction->GetInput();
1306 if (input->IsNot()) {
1307 // Replace code looking like
1308 // NOT tmp, src
1309 // NOT dst, tmp
1310 // with
1311 // src
1312 // We perform the optimization even if the input negation has environment
1313 // uses since it allows removing the current instruction. But we only delete
1314 // the input negation only if it is does not have any uses left.
1315 HNot* previous_not = input->AsNot();
1316 instruction->ReplaceWith(previous_not->GetInput());
1317 instruction->GetBlock()->RemoveInstruction(instruction);
1318 if (!previous_not->HasUses()) {
1319 previous_not->GetBlock()->RemoveInstruction(previous_not);
1320 }
1321 RecordSimplification();
1322 }
1323 }
1324
VisitOr(HOr * instruction)1325 void InstructionSimplifierVisitor::VisitOr(HOr* instruction) {
1326 HConstant* input_cst = instruction->GetConstantRight();
1327 HInstruction* input_other = instruction->GetLeastConstantLeft();
1328
1329 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) {
1330 // Replace code looking like
1331 // OR dst, src, 0
1332 // with
1333 // src
1334 instruction->ReplaceWith(input_other);
1335 instruction->GetBlock()->RemoveInstruction(instruction);
1336 return;
1337 }
1338
1339 // We assume that GVN has run before, so we only perform a pointer comparison.
1340 // If for some reason the values are equal but the pointers are different, we
1341 // are still correct and only miss an optimization opportunity.
1342 if (instruction->GetLeft() == instruction->GetRight()) {
1343 // Replace code looking like
1344 // OR dst, src, src
1345 // with
1346 // src
1347 instruction->ReplaceWith(instruction->GetLeft());
1348 instruction->GetBlock()->RemoveInstruction(instruction);
1349 return;
1350 }
1351
1352 if (TryDeMorganNegationFactoring(instruction)) return;
1353
1354 TryReplaceWithRotate(instruction);
1355 }
1356
VisitShl(HShl * instruction)1357 void InstructionSimplifierVisitor::VisitShl(HShl* instruction) {
1358 VisitShift(instruction);
1359 }
1360
VisitShr(HShr * instruction)1361 void InstructionSimplifierVisitor::VisitShr(HShr* instruction) {
1362 VisitShift(instruction);
1363 }
1364
VisitSub(HSub * instruction)1365 void InstructionSimplifierVisitor::VisitSub(HSub* instruction) {
1366 HConstant* input_cst = instruction->GetConstantRight();
1367 HInstruction* input_other = instruction->GetLeastConstantLeft();
1368
1369 Primitive::Type type = instruction->GetType();
1370 if (Primitive::IsFloatingPointType(type)) {
1371 return;
1372 }
1373
1374 if ((input_cst != nullptr) && input_cst->IsArithmeticZero()) {
1375 // Replace code looking like
1376 // SUB dst, src, 0
1377 // with
1378 // src
1379 // Note that we cannot optimize `x - 0.0` to `x` for floating-point. When
1380 // `x` is `-0.0`, the former expression yields `0.0`, while the later
1381 // yields `-0.0`.
1382 instruction->ReplaceWith(input_other);
1383 instruction->GetBlock()->RemoveInstruction(instruction);
1384 return;
1385 }
1386
1387 HBasicBlock* block = instruction->GetBlock();
1388 ArenaAllocator* allocator = GetGraph()->GetArena();
1389
1390 HInstruction* left = instruction->GetLeft();
1391 HInstruction* right = instruction->GetRight();
1392 if (left->IsConstant()) {
1393 if (Int64FromConstant(left->AsConstant()) == 0) {
1394 // Replace code looking like
1395 // SUB dst, 0, src
1396 // with
1397 // NEG dst, src
1398 // Note that we cannot optimize `0.0 - x` to `-x` for floating-point. When
1399 // `x` is `0.0`, the former expression yields `0.0`, while the later
1400 // yields `-0.0`.
1401 HNeg* neg = new (allocator) HNeg(type, right);
1402 block->ReplaceAndRemoveInstructionWith(instruction, neg);
1403 RecordSimplification();
1404 return;
1405 }
1406 }
1407
1408 if (left->IsNeg() && right->IsNeg()) {
1409 if (TryMoveNegOnInputsAfterBinop(instruction)) {
1410 return;
1411 }
1412 }
1413
1414 if (right->IsNeg() && right->HasOnlyOneNonEnvironmentUse()) {
1415 // Replace code looking like
1416 // NEG tmp, b
1417 // SUB dst, a, tmp
1418 // with
1419 // ADD dst, a, b
1420 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left, right->AsNeg()->GetInput());
1421 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, add);
1422 RecordSimplification();
1423 right->GetBlock()->RemoveInstruction(right);
1424 return;
1425 }
1426
1427 if (left->IsNeg() && left->HasOnlyOneNonEnvironmentUse()) {
1428 // Replace code looking like
1429 // NEG tmp, a
1430 // SUB dst, tmp, b
1431 // with
1432 // ADD tmp, a, b
1433 // NEG dst, tmp
1434 // The second version is not intrinsically better, but enables more
1435 // transformations.
1436 HAdd* add = new(GetGraph()->GetArena()) HAdd(type, left->AsNeg()->GetInput(), right);
1437 instruction->GetBlock()->InsertInstructionBefore(add, instruction);
1438 HNeg* neg = new (GetGraph()->GetArena()) HNeg(instruction->GetType(), add);
1439 instruction->GetBlock()->InsertInstructionBefore(neg, instruction);
1440 instruction->ReplaceWith(neg);
1441 instruction->GetBlock()->RemoveInstruction(instruction);
1442 RecordSimplification();
1443 left->GetBlock()->RemoveInstruction(left);
1444 }
1445 }
1446
VisitUShr(HUShr * instruction)1447 void InstructionSimplifierVisitor::VisitUShr(HUShr* instruction) {
1448 VisitShift(instruction);
1449 }
1450
VisitXor(HXor * instruction)1451 void InstructionSimplifierVisitor::VisitXor(HXor* instruction) {
1452 HConstant* input_cst = instruction->GetConstantRight();
1453 HInstruction* input_other = instruction->GetLeastConstantLeft();
1454
1455 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) {
1456 // Replace code looking like
1457 // XOR dst, src, 0
1458 // with
1459 // src
1460 instruction->ReplaceWith(input_other);
1461 instruction->GetBlock()->RemoveInstruction(instruction);
1462 return;
1463 }
1464
1465 if ((input_cst != nullptr) && AreAllBitsSet(input_cst)) {
1466 // Replace code looking like
1467 // XOR dst, src, 0xFFF...FF
1468 // with
1469 // NOT dst, src
1470 HNot* bitwise_not = new (GetGraph()->GetArena()) HNot(instruction->GetType(), input_other);
1471 instruction->GetBlock()->ReplaceAndRemoveInstructionWith(instruction, bitwise_not);
1472 RecordSimplification();
1473 return;
1474 }
1475
1476 HInstruction* left = instruction->GetLeft();
1477 HInstruction* right = instruction->GetRight();
1478 if (((left->IsNot() && right->IsNot()) ||
1479 (left->IsBooleanNot() && right->IsBooleanNot())) &&
1480 left->HasOnlyOneNonEnvironmentUse() &&
1481 right->HasOnlyOneNonEnvironmentUse()) {
1482 // Replace code looking like
1483 // NOT nota, a
1484 // NOT notb, b
1485 // XOR dst, nota, notb
1486 // with
1487 // XOR dst, a, b
1488 instruction->ReplaceInput(left->InputAt(0), 0);
1489 instruction->ReplaceInput(right->InputAt(0), 1);
1490 left->GetBlock()->RemoveInstruction(left);
1491 right->GetBlock()->RemoveInstruction(right);
1492 RecordSimplification();
1493 return;
1494 }
1495
1496 TryReplaceWithRotate(instruction);
1497 }
1498
SimplifyStringEquals(HInvoke * instruction)1499 void InstructionSimplifierVisitor::SimplifyStringEquals(HInvoke* instruction) {
1500 HInstruction* argument = instruction->InputAt(1);
1501 HInstruction* receiver = instruction->InputAt(0);
1502 if (receiver == argument) {
1503 // Because String.equals is an instance call, the receiver is
1504 // a null check if we don't know it's null. The argument however, will
1505 // be the actual object. So we cannot end up in a situation where both
1506 // are equal but could be null.
1507 DCHECK(CanEnsureNotNullAt(argument, instruction));
1508 instruction->ReplaceWith(GetGraph()->GetIntConstant(1));
1509 instruction->GetBlock()->RemoveInstruction(instruction);
1510 } else {
1511 StringEqualsOptimizations optimizations(instruction);
1512 if (CanEnsureNotNullAt(argument, instruction)) {
1513 optimizations.SetArgumentNotNull();
1514 }
1515 ScopedObjectAccess soa(Thread::Current());
1516 ReferenceTypeInfo argument_rti = argument->GetReferenceTypeInfo();
1517 if (argument_rti.IsValid() && argument_rti.IsStringClass()) {
1518 optimizations.SetArgumentIsString();
1519 }
1520 }
1521 }
1522
SimplifyRotate(HInvoke * invoke,bool is_left,Primitive::Type type)1523 void InstructionSimplifierVisitor::SimplifyRotate(HInvoke* invoke,
1524 bool is_left,
1525 Primitive::Type type) {
1526 DCHECK(invoke->IsInvokeStaticOrDirect());
1527 DCHECK_EQ(invoke->GetOriginalInvokeType(), InvokeType::kStatic);
1528 HInstruction* value = invoke->InputAt(0);
1529 HInstruction* distance = invoke->InputAt(1);
1530 // Replace the invoke with an HRor.
1531 if (is_left) {
1532 // Unconditionally set the type of the negated distance to `int`,
1533 // as shift and rotate operations expect a 32-bit (or narrower)
1534 // value for their distance input.
1535 distance = new (GetGraph()->GetArena()) HNeg(Primitive::kPrimInt, distance);
1536 invoke->GetBlock()->InsertInstructionBefore(distance, invoke);
1537 }
1538 HRor* ror = new (GetGraph()->GetArena()) HRor(type, value, distance);
1539 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, ror);
1540 // Remove ClinitCheck and LoadClass, if possible.
1541 HInstruction* clinit = invoke->InputAt(invoke->InputCount() - 1);
1542 if (clinit->IsClinitCheck() && !clinit->HasUses()) {
1543 clinit->GetBlock()->RemoveInstruction(clinit);
1544 HInstruction* ldclass = clinit->InputAt(0);
1545 if (ldclass->IsLoadClass() && !ldclass->HasUses()) {
1546 ldclass->GetBlock()->RemoveInstruction(ldclass);
1547 }
1548 }
1549 }
1550
IsArrayLengthOf(HInstruction * potential_length,HInstruction * potential_array)1551 static bool IsArrayLengthOf(HInstruction* potential_length, HInstruction* potential_array) {
1552 if (potential_length->IsArrayLength()) {
1553 return potential_length->InputAt(0) == potential_array;
1554 }
1555
1556 if (potential_array->IsNewArray()) {
1557 return potential_array->InputAt(0) == potential_length;
1558 }
1559
1560 return false;
1561 }
1562
SimplifySystemArrayCopy(HInvoke * instruction)1563 void InstructionSimplifierVisitor::SimplifySystemArrayCopy(HInvoke* instruction) {
1564 HInstruction* source = instruction->InputAt(0);
1565 HInstruction* destination = instruction->InputAt(2);
1566 HInstruction* count = instruction->InputAt(4);
1567 SystemArrayCopyOptimizations optimizations(instruction);
1568 if (CanEnsureNotNullAt(source, instruction)) {
1569 optimizations.SetSourceIsNotNull();
1570 }
1571 if (CanEnsureNotNullAt(destination, instruction)) {
1572 optimizations.SetDestinationIsNotNull();
1573 }
1574 if (destination == source) {
1575 optimizations.SetDestinationIsSource();
1576 }
1577
1578 if (IsArrayLengthOf(count, source)) {
1579 optimizations.SetCountIsSourceLength();
1580 }
1581
1582 if (IsArrayLengthOf(count, destination)) {
1583 optimizations.SetCountIsDestinationLength();
1584 }
1585
1586 {
1587 ScopedObjectAccess soa(Thread::Current());
1588 ReferenceTypeInfo destination_rti = destination->GetReferenceTypeInfo();
1589 if (destination_rti.IsValid()) {
1590 if (destination_rti.IsObjectArray()) {
1591 if (destination_rti.IsExact()) {
1592 optimizations.SetDoesNotNeedTypeCheck();
1593 }
1594 optimizations.SetDestinationIsTypedObjectArray();
1595 }
1596 if (destination_rti.IsPrimitiveArrayClass()) {
1597 optimizations.SetDestinationIsPrimitiveArray();
1598 } else if (destination_rti.IsNonPrimitiveArrayClass()) {
1599 optimizations.SetDestinationIsNonPrimitiveArray();
1600 }
1601 }
1602 ReferenceTypeInfo source_rti = source->GetReferenceTypeInfo();
1603 if (source_rti.IsValid()) {
1604 if (destination_rti.IsValid() && destination_rti.CanArrayHoldValuesOf(source_rti)) {
1605 optimizations.SetDoesNotNeedTypeCheck();
1606 }
1607 if (source_rti.IsPrimitiveArrayClass()) {
1608 optimizations.SetSourceIsPrimitiveArray();
1609 } else if (source_rti.IsNonPrimitiveArrayClass()) {
1610 optimizations.SetSourceIsNonPrimitiveArray();
1611 }
1612 }
1613 }
1614 }
1615
SimplifyCompare(HInvoke * invoke,bool is_signum,Primitive::Type type)1616 void InstructionSimplifierVisitor::SimplifyCompare(HInvoke* invoke,
1617 bool is_signum,
1618 Primitive::Type type) {
1619 DCHECK(invoke->IsInvokeStaticOrDirect());
1620 uint32_t dex_pc = invoke->GetDexPc();
1621 HInstruction* left = invoke->InputAt(0);
1622 HInstruction* right;
1623 if (!is_signum) {
1624 right = invoke->InputAt(1);
1625 } else if (type == Primitive::kPrimLong) {
1626 right = GetGraph()->GetLongConstant(0);
1627 } else {
1628 right = GetGraph()->GetIntConstant(0);
1629 }
1630 HCompare* compare = new (GetGraph()->GetArena())
1631 HCompare(type, left, right, ComparisonBias::kNoBias, dex_pc);
1632 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, compare);
1633 }
1634
SimplifyIsNaN(HInvoke * invoke)1635 void InstructionSimplifierVisitor::SimplifyIsNaN(HInvoke* invoke) {
1636 DCHECK(invoke->IsInvokeStaticOrDirect());
1637 uint32_t dex_pc = invoke->GetDexPc();
1638 // IsNaN(x) is the same as x != x.
1639 HInstruction* x = invoke->InputAt(0);
1640 HCondition* condition = new (GetGraph()->GetArena()) HNotEqual(x, x, dex_pc);
1641 condition->SetBias(ComparisonBias::kLtBias);
1642 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, condition);
1643 }
1644
SimplifyFP2Int(HInvoke * invoke)1645 void InstructionSimplifierVisitor::SimplifyFP2Int(HInvoke* invoke) {
1646 DCHECK(invoke->IsInvokeStaticOrDirect());
1647 uint32_t dex_pc = invoke->GetDexPc();
1648 HInstruction* x = invoke->InputAt(0);
1649 Primitive::Type type = x->GetType();
1650 // Set proper bit pattern for NaN and replace intrinsic with raw version.
1651 HInstruction* nan;
1652 if (type == Primitive::kPrimDouble) {
1653 nan = GetGraph()->GetLongConstant(0x7ff8000000000000L);
1654 invoke->SetIntrinsic(Intrinsics::kDoubleDoubleToRawLongBits,
1655 kNeedsEnvironmentOrCache,
1656 kNoSideEffects,
1657 kNoThrow);
1658 } else {
1659 DCHECK_EQ(type, Primitive::kPrimFloat);
1660 nan = GetGraph()->GetIntConstant(0x7fc00000);
1661 invoke->SetIntrinsic(Intrinsics::kFloatFloatToRawIntBits,
1662 kNeedsEnvironmentOrCache,
1663 kNoSideEffects,
1664 kNoThrow);
1665 }
1666 // Test IsNaN(x), which is the same as x != x.
1667 HCondition* condition = new (GetGraph()->GetArena()) HNotEqual(x, x, dex_pc);
1668 condition->SetBias(ComparisonBias::kLtBias);
1669 invoke->GetBlock()->InsertInstructionBefore(condition, invoke->GetNext());
1670 // Select between the two.
1671 HInstruction* select = new (GetGraph()->GetArena()) HSelect(condition, nan, invoke, dex_pc);
1672 invoke->GetBlock()->InsertInstructionBefore(select, condition->GetNext());
1673 invoke->ReplaceWithExceptInReplacementAtIndex(select, 0); // false at index 0
1674 }
1675
SimplifyMemBarrier(HInvoke * invoke,MemBarrierKind barrier_kind)1676 void InstructionSimplifierVisitor::SimplifyMemBarrier(HInvoke* invoke, MemBarrierKind barrier_kind) {
1677 uint32_t dex_pc = invoke->GetDexPc();
1678 HMemoryBarrier* mem_barrier = new (GetGraph()->GetArena()) HMemoryBarrier(barrier_kind, dex_pc);
1679 invoke->GetBlock()->ReplaceAndRemoveInstructionWith(invoke, mem_barrier);
1680 }
1681
VisitInvoke(HInvoke * instruction)1682 void InstructionSimplifierVisitor::VisitInvoke(HInvoke* instruction) {
1683 switch (instruction->GetIntrinsic()) {
1684 case Intrinsics::kStringEquals:
1685 SimplifyStringEquals(instruction);
1686 break;
1687 case Intrinsics::kSystemArrayCopy:
1688 SimplifySystemArrayCopy(instruction);
1689 break;
1690 case Intrinsics::kIntegerRotateRight:
1691 SimplifyRotate(instruction, /* is_left */ false, Primitive::kPrimInt);
1692 break;
1693 case Intrinsics::kLongRotateRight:
1694 SimplifyRotate(instruction, /* is_left */ false, Primitive::kPrimLong);
1695 break;
1696 case Intrinsics::kIntegerRotateLeft:
1697 SimplifyRotate(instruction, /* is_left */ true, Primitive::kPrimInt);
1698 break;
1699 case Intrinsics::kLongRotateLeft:
1700 SimplifyRotate(instruction, /* is_left */ true, Primitive::kPrimLong);
1701 break;
1702 case Intrinsics::kIntegerCompare:
1703 SimplifyCompare(instruction, /* is_signum */ false, Primitive::kPrimInt);
1704 break;
1705 case Intrinsics::kLongCompare:
1706 SimplifyCompare(instruction, /* is_signum */ false, Primitive::kPrimLong);
1707 break;
1708 case Intrinsics::kIntegerSignum:
1709 SimplifyCompare(instruction, /* is_signum */ true, Primitive::kPrimInt);
1710 break;
1711 case Intrinsics::kLongSignum:
1712 SimplifyCompare(instruction, /* is_signum */ true, Primitive::kPrimLong);
1713 break;
1714 case Intrinsics::kFloatIsNaN:
1715 case Intrinsics::kDoubleIsNaN:
1716 SimplifyIsNaN(instruction);
1717 break;
1718 case Intrinsics::kFloatFloatToIntBits:
1719 case Intrinsics::kDoubleDoubleToLongBits:
1720 SimplifyFP2Int(instruction);
1721 break;
1722 case Intrinsics::kUnsafeLoadFence:
1723 SimplifyMemBarrier(instruction, MemBarrierKind::kLoadAny);
1724 break;
1725 case Intrinsics::kUnsafeStoreFence:
1726 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyStore);
1727 break;
1728 case Intrinsics::kUnsafeFullFence:
1729 SimplifyMemBarrier(instruction, MemBarrierKind::kAnyAny);
1730 break;
1731 default:
1732 break;
1733 }
1734 }
1735
VisitDeoptimize(HDeoptimize * deoptimize)1736 void InstructionSimplifierVisitor::VisitDeoptimize(HDeoptimize* deoptimize) {
1737 HInstruction* cond = deoptimize->InputAt(0);
1738 if (cond->IsConstant()) {
1739 if (cond->AsIntConstant()->IsFalse()) {
1740 // Never deopt: instruction can be removed.
1741 deoptimize->GetBlock()->RemoveInstruction(deoptimize);
1742 } else {
1743 // Always deopt.
1744 }
1745 }
1746 }
1747
1748 } // namespace art
1749