1// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/compiler/backend/constant_propagator.h"
6
7#include "vm/bit_vector.h"
8#include "vm/compiler/backend/evaluator.h"
9#include "vm/compiler/backend/flow_graph_compiler.h"
10#include "vm/compiler/backend/il.h"
11#include "vm/compiler/backend/il_printer.h"
12#include "vm/compiler/backend/range_analysis.h"
13#include "vm/compiler/frontend/flow_graph_builder.h"
14#include "vm/parser.h"
15#include "vm/symbols.h"
16
17namespace dart {
18
19DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
20DEFINE_FLAG(bool,
21 trace_constant_propagation,
22 false,
23 "Print constant propagation and useless code elimination.");
24
25// Quick access to the current zone and isolate.
26#define I (isolate())
27#define Z (graph_->zone())
28#define T (graph_->thread())
29
30ConstantPropagator::ConstantPropagator(
31 FlowGraph* graph,
32 const GrowableArray<BlockEntryInstr*>& ignored)
33 : FlowGraphVisitor(ignored),
34 graph_(graph),
35 unknown_(Object::unknown_constant()),
36 non_constant_(Object::non_constant()),
37 constant_value_(Object::Handle(Z)),
38 reachable_(new (Z) BitVector(Z, graph->preorder().length())),
39 unwrapped_phis_(new (Z)
40 BitVector(Z, graph->max_virtual_register_number())),
41 block_worklist_(),
42 definition_worklist_(graph, 10) {}
43
44void ConstantPropagator::Optimize(FlowGraph* graph) {
45 GrowableArray<BlockEntryInstr*> ignored;
46 ConstantPropagator cp(graph, ignored);
47 cp.Analyze();
48 cp.Transform();
49}
50
51void ConstantPropagator::OptimizeBranches(FlowGraph* graph) {
52 GrowableArray<BlockEntryInstr*> ignored;
53 ConstantPropagator cp(graph, ignored);
54 cp.Analyze();
55 cp.Transform();
56 cp.EliminateRedundantBranches();
57}
58
59void ConstantPropagator::SetReachable(BlockEntryInstr* block) {
60 if (!reachable_->Contains(block->preorder_number())) {
61 reachable_->Add(block->preorder_number());
62 block_worklist_.Add(block);
63 }
64}
65
66bool ConstantPropagator::SetValue(Definition* definition, const Object& value) {
67 // We would like to assert we only go up (toward non-constant) in the lattice.
68 //
69 // ASSERT(IsUnknown(definition->constant_value()) ||
70 // IsNonConstant(value) ||
71 // (definition->constant_value().raw() == value.raw()));
72 //
73 // But the final disjunct is not true (e.g., mint or double constants are
74 // heap-allocated and so not necessarily pointer-equal on each iteration).
75 if (definition->constant_value().raw() != value.raw()) {
76 definition->constant_value() = value.raw();
77 if (definition->input_use_list() != NULL) {
78 definition_worklist_.Add(definition);
79 }
80 return true;
81 }
82 return false;
83}
84
85static bool IsIdenticalConstants(const Object& left, const Object& right) {
86 // This should be kept in line with Identical_comparison (identical.cc)
87 // (=> Instance::IsIdenticalTo in object.cc).
88
89 if (left.raw() == right.raw()) return true;
90 if (left.GetClassId() != right.GetClassId()) return false;
91 if (left.IsInteger()) {
92 return Integer::Cast(left).Equals(Integer::Cast(right));
93 }
94 if (left.IsDouble()) {
95 return Double::Cast(left).BitwiseEqualsToDouble(
96 Double::Cast(right).value());
97 }
98 return false;
99}
100
101// Compute the join of two values in the lattice, assign it to the first.
102void ConstantPropagator::Join(Object* left, const Object& right) {
103 // Join(non-constant, X) = non-constant
104 // Join(X, unknown) = X
105 if (IsNonConstant(*left) || IsUnknown(right)) return;
106
107 // Join(unknown, X) = X
108 // Join(X, non-constant) = non-constant
109 if (IsUnknown(*left) || IsNonConstant(right)) {
110 *left = right.raw();
111 return;
112 }
113
114 // Join(X, X) = X
115 if (IsIdenticalConstants(*left, right)) return;
116
117 // Join(X, Y) = non-constant
118 *left = non_constant_.raw();
119}
120
121// --------------------------------------------------------------------------
122// Analysis of blocks. Called at most once per block. The block is already
123// marked as reachable. All instructions in the block are analyzed.
124void ConstantPropagator::VisitGraphEntry(GraphEntryInstr* block) {
125 for (auto def : *block->initial_definitions()) {
126 def->Accept(this);
127 }
128 ASSERT(ForwardInstructionIterator(block).Done());
129
130 // TODO(fschneider): Improve this approximation. The catch entry is only
131 // reachable if a call in the try-block is reachable.
132 for (intptr_t i = 0; i < block->SuccessorCount(); ++i) {
133 SetReachable(block->SuccessorAt(i));
134 }
135}
136
137void ConstantPropagator::VisitFunctionEntry(FunctionEntryInstr* block) {
138 for (auto def : *block->initial_definitions()) {
139 def->Accept(this);
140 }
141 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
142 it.Current()->Accept(this);
143 }
144}
145
146void ConstantPropagator::VisitNativeEntry(NativeEntryInstr* block) {
147 VisitFunctionEntry(block);
148}
149
150void ConstantPropagator::VisitOsrEntry(OsrEntryInstr* block) {
151 for (auto def : *block->initial_definitions()) {
152 def->Accept(this);
153 }
154 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
155 it.Current()->Accept(this);
156 }
157}
158
159void ConstantPropagator::VisitCatchBlockEntry(CatchBlockEntryInstr* block) {
160 for (auto def : *block->initial_definitions()) {
161 def->Accept(this);
162 }
163 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
164 it.Current()->Accept(this);
165 }
166}
167
168void ConstantPropagator::VisitJoinEntry(JoinEntryInstr* block) {
169 // Phis are visited when visiting Goto at a predecessor. See VisitGoto.
170 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
171 it.Current()->Accept(this);
172 }
173}
174
175void ConstantPropagator::VisitTargetEntry(TargetEntryInstr* block) {
176 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
177 it.Current()->Accept(this);
178 }
179}
180
181void ConstantPropagator::VisitIndirectEntry(IndirectEntryInstr* block) {
182 for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
183 it.Current()->Accept(this);
184 }
185}
186
187void ConstantPropagator::VisitParallelMove(ParallelMoveInstr* instr) {
188 // Parallel moves have not yet been inserted in the graph.
189 UNREACHABLE();
190}
191
192// --------------------------------------------------------------------------
193// Analysis of control instructions. Unconditional successors are
194// reachable. Conditional successors are reachable depending on the
195// constant value of the condition.
196void ConstantPropagator::VisitReturn(ReturnInstr* instr) {
197 // Nothing to do.
198}
199
200void ConstantPropagator::VisitNativeReturn(NativeReturnInstr* instr) {
201 // Nothing to do.
202}
203
204void ConstantPropagator::VisitThrow(ThrowInstr* instr) {
205 // Nothing to do.
206}
207
208void ConstantPropagator::VisitReThrow(ReThrowInstr* instr) {
209 // Nothing to do.
210}
211
212void ConstantPropagator::VisitStop(StopInstr* instr) {
213 // Nothing to do.
214}
215
216void ConstantPropagator::VisitGoto(GotoInstr* instr) {
217 SetReachable(instr->successor());
218
219 // Phi value depends on the reachability of a predecessor. We have
220 // to revisit phis every time a predecessor becomes reachable.
221 for (PhiIterator it(instr->successor()); !it.Done(); it.Advance()) {
222 PhiInstr* phi = it.Current();
223 phi->Accept(this);
224
225 // If this phi was previously unwrapped as redundant and it is no longer
226 // redundant (does not unwrap) then we need to revisit the uses.
227 if (unwrapped_phis_->Contains(phi->ssa_temp_index()) &&
228 (UnwrapPhi(phi) == phi)) {
229 unwrapped_phis_->Remove(phi->ssa_temp_index());
230 definition_worklist_.Add(phi);
231 }
232 }
233}
234
235void ConstantPropagator::VisitIndirectGoto(IndirectGotoInstr* instr) {
236 for (intptr_t i = 0; i < instr->SuccessorCount(); i++) {
237 SetReachable(instr->SuccessorAt(i));
238 }
239}
240
241void ConstantPropagator::VisitBranch(BranchInstr* instr) {
242 instr->comparison()->Accept(this);
243
244 // The successors may be reachable, but only if this instruction is. (We
245 // might be analyzing it because the constant value of one of its inputs
246 // has changed.)
247 if (reachable_->Contains(instr->GetBlock()->preorder_number())) {
248 if (instr->constant_target() != NULL) {
249 ASSERT((instr->constant_target() == instr->true_successor()) ||
250 (instr->constant_target() == instr->false_successor()));
251 SetReachable(instr->constant_target());
252 } else {
253 const Object& value = instr->comparison()->constant_value();
254 if (IsNonConstant(value)) {
255 SetReachable(instr->true_successor());
256 SetReachable(instr->false_successor());
257 } else if (value.raw() == Bool::True().raw()) {
258 SetReachable(instr->true_successor());
259 } else if (!IsUnknown(value)) { // Any other constant.
260 SetReachable(instr->false_successor());
261 }
262 }
263 }
264}
265
266// --------------------------------------------------------------------------
267// Analysis of non-definition instructions. They do not have values so they
268// cannot have constant values.
269void ConstantPropagator::VisitCheckStackOverflow(
270 CheckStackOverflowInstr* instr) {}
271
272void ConstantPropagator::VisitCheckClass(CheckClassInstr* instr) {}
273
274void ConstantPropagator::VisitCheckCondition(CheckConditionInstr* instr) {}
275
276void ConstantPropagator::VisitCheckClassId(CheckClassIdInstr* instr) {}
277
278void ConstantPropagator::VisitGuardFieldClass(GuardFieldClassInstr* instr) {}
279
280void ConstantPropagator::VisitGuardFieldLength(GuardFieldLengthInstr* instr) {}
281
282void ConstantPropagator::VisitGuardFieldType(GuardFieldTypeInstr* instr) {}
283
284void ConstantPropagator::VisitCheckSmi(CheckSmiInstr* instr) {}
285
286void ConstantPropagator::VisitTailCall(TailCallInstr* instr) {}
287
288void ConstantPropagator::VisitCheckEitherNonSmi(CheckEitherNonSmiInstr* instr) {
289}
290
291void ConstantPropagator::VisitStoreUntagged(StoreUntaggedInstr* instr) {}
292
293void ConstantPropagator::VisitStoreIndexedUnsafe(
294 StoreIndexedUnsafeInstr* instr) {}
295
296void ConstantPropagator::VisitStoreIndexed(StoreIndexedInstr* instr) {}
297
298void ConstantPropagator::VisitStoreInstanceField(
299 StoreInstanceFieldInstr* instr) {}
300
301void ConstantPropagator::VisitMemoryCopy(MemoryCopyInstr* instr) {}
302
303void ConstantPropagator::VisitDeoptimize(DeoptimizeInstr* instr) {
304 // TODO(vegorov) remove all code after DeoptimizeInstr as dead.
305}
306
307Definition* ConstantPropagator::UnwrapPhi(Definition* defn) {
308 if (defn->IsPhi()) {
309 JoinEntryInstr* block = defn->AsPhi()->block();
310
311 Definition* input = NULL;
312 for (intptr_t i = 0; i < defn->InputCount(); ++i) {
313 if (reachable_->Contains(block->PredecessorAt(i)->preorder_number())) {
314 if (input == NULL) {
315 input = defn->InputAt(i)->definition();
316 } else {
317 return defn;
318 }
319 }
320 }
321
322 return input;
323 }
324
325 return defn;
326}
327
328void ConstantPropagator::MarkUnwrappedPhi(Definition* phi) {
329 ASSERT(phi->IsPhi());
330 unwrapped_phis_->Add(phi->ssa_temp_index());
331}
332
333ConstantPropagator::PhiInfo* ConstantPropagator::GetPhiInfo(PhiInstr* phi) {
334 if (phi->HasPassSpecificId(CompilerPass::kConstantPropagation)) {
335 const intptr_t id =
336 phi->GetPassSpecificId(CompilerPass::kConstantPropagation);
337 // Note: id might have been assigned by the previous round of constant
338 // propagation, so we need to verify it before using it.
339 if (id < phis_.length() && phis_[id].phi == phi) {
340 return &phis_[id];
341 }
342 }
343
344 phi->SetPassSpecificId(CompilerPass::kConstantPropagation, phis_.length());
345 phis_.Add({phi, 0});
346 return &phis_.Last();
347}
348
349// --------------------------------------------------------------------------
350// Analysis of definitions. Compute the constant value. If it has changed
351// and the definition has input uses, add the definition to the definition
352// worklist so that the used can be processed.
353void ConstantPropagator::VisitPhi(PhiInstr* instr) {
354 // Detect convergence issues by checking if visit count for this phi
355 // is too high. We should only visit this phi once for every predecessor
356 // becoming reachable, once for every input changing its constant value and
357 // once for an unwrapped redundant phi becoming non-redundant.
358 // Inputs can only change their constant value at most three times: from
359 // non-constant to unknown to specific constant to non-constant. The first
360 // link (non-constant to ...) can happen when we run the second round of
361 // constant propagation - some instructions can have non-constant assigned to
362 // them at the end of the previous constant propagation.
363 auto info = GetPhiInfo(instr);
364 info->visit_count++;
365 const intptr_t kMaxVisitsExpected = 5 * instr->InputCount();
366 if (info->visit_count > kMaxVisitsExpected) {
367 OS::PrintErr(
368 "ConstantPropagation pass is failing to converge on graph for %s\n",
369 graph_->parsed_function().function().ToCString());
370 OS::PrintErr("Phi %s was visited %" Pd " times\n", instr->ToCString(),
371 info->visit_count);
372 NOT_IN_PRODUCT(
373 FlowGraphPrinter::PrintGraph("Constant Propagation", graph_));
374 FATAL("Aborting due to non-covergence.");
375 }
376
377 // Compute the join over all the reachable predecessor values.
378 JoinEntryInstr* block = instr->block();
379 Object& value = Object::ZoneHandle(Z, Unknown());
380 for (intptr_t pred_idx = 0; pred_idx < instr->InputCount(); ++pred_idx) {
381 if (reachable_->Contains(
382 block->PredecessorAt(pred_idx)->preorder_number())) {
383 Join(&value, instr->InputAt(pred_idx)->definition()->constant_value());
384 }
385 }
386 SetValue(instr, value);
387}
388
389void ConstantPropagator::VisitRedefinition(RedefinitionInstr* instr) {
390 const Object& value = instr->value()->definition()->constant_value();
391 if (IsConstant(value)) {
392 SetValue(instr, value);
393 } else {
394 SetValue(instr, non_constant_);
395 }
396}
397
398void ConstantPropagator::VisitReachabilityFence(ReachabilityFenceInstr* instr) {
399 // Nothing to do.
400}
401
402void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) {
403 // Don't propagate constants through check, since it would eliminate
404 // the data dependence between the bound check and the load/store.
405 // Graph finalization will expose the constant eventually.
406 SetValue(instr, non_constant_);
407}
408
409void ConstantPropagator::VisitGenericCheckBound(GenericCheckBoundInstr* instr) {
410 // Don't propagate constants through check, since it would eliminate
411 // the data dependence between the bound check and the load/store.
412 // Graph finalization will expose the constant eventually.
413 SetValue(instr, non_constant_);
414}
415
416void ConstantPropagator::VisitCheckNull(CheckNullInstr* instr) {
417 // Don't propagate constants through check, since it would eliminate
418 // the data dependence between the null check and its use.
419 // Graph finalization will expose the constant eventually.
420 SetValue(instr, non_constant_);
421}
422
423void ConstantPropagator::VisitParameter(ParameterInstr* instr) {
424 SetValue(instr, non_constant_);
425}
426
427void ConstantPropagator::VisitNativeParameter(NativeParameterInstr* instr) {
428 SetValue(instr, non_constant_);
429}
430
431void ConstantPropagator::VisitPushArgument(PushArgumentInstr* instr) {
432 UNREACHABLE();
433}
434
435void ConstantPropagator::VisitAssertAssignable(AssertAssignableInstr* instr) {
436 const auto& value = instr->value()->definition()->constant_value();
437 const auto& dst_type = instr->dst_type()->definition()->constant_value();
438
439 if (IsNonConstant(value) || IsNonConstant(dst_type)) {
440 SetValue(instr, non_constant_);
441 } else if (IsConstant(value) && IsConstant(dst_type)) {
442 // We are ignoring the instantiator and instantiator_type_arguments, but
443 // still monotonic and safe.
444 if (instr->value()->Type()->IsAssignableTo(AbstractType::Cast(dst_type))) {
445 SetValue(instr, value);
446 } else {
447 SetValue(instr, non_constant_);
448 }
449 }
450}
451
452void ConstantPropagator::VisitAssertSubtype(AssertSubtypeInstr* instr) {}
453
454void ConstantPropagator::VisitAssertBoolean(AssertBooleanInstr* instr) {
455 const Object& value = instr->value()->definition()->constant_value();
456 if (IsNonConstant(value)) {
457 SetValue(instr, non_constant_);
458 } else if (IsConstant(value)) {
459 if (value.IsBool()) {
460 SetValue(instr, value);
461 } else {
462 SetValue(instr, non_constant_);
463 }
464 }
465}
466
467void ConstantPropagator::VisitSpecialParameter(SpecialParameterInstr* instr) {
468 SetValue(instr, non_constant_);
469}
470
471void ConstantPropagator::VisitClosureCall(ClosureCallInstr* instr) {
472 SetValue(instr, non_constant_);
473}
474
475void ConstantPropagator::VisitInstanceCall(InstanceCallInstr* instr) {
476 SetValue(instr, non_constant_);
477}
478
479void ConstantPropagator::VisitPolymorphicInstanceCall(
480 PolymorphicInstanceCallInstr* instr) {
481 SetValue(instr, non_constant_);
482}
483
484void ConstantPropagator::VisitDispatchTableCall(DispatchTableCallInstr* instr) {
485 SetValue(instr, non_constant_);
486}
487
488void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) {
489 const auto kind = instr->function().recognized_kind();
490 switch (kind) {
491 case MethodRecognizer::kOneByteString_equality:
492 case MethodRecognizer::kTwoByteString_equality: {
493 ASSERT(instr->FirstArgIndex() == 0);
494 // Use pure identity as a fast equality test.
495 if (instr->ArgumentAt(0)->OriginalDefinition() ==
496 instr->ArgumentAt(1)->OriginalDefinition()) {
497 SetValue(instr, Bool::True());
498 return;
499 }
500 // Otherwise evaluate string compare with propagated constants.
501 const Object& o1 = instr->ArgumentAt(0)->constant_value();
502 const Object& o2 = instr->ArgumentAt(1)->constant_value();
503 if (IsConstant(o1) && IsConstant(o2) && o1.IsString() && o2.IsString()) {
504 SetValue(instr, Bool::Get(String::Cast(o1).Equals(String::Cast(o2))));
505 return;
506 }
507 break;
508 }
509 case MethodRecognizer::kStringBaseLength:
510 case MethodRecognizer::kStringBaseIsEmpty: {
511 ASSERT(instr->FirstArgIndex() == 0);
512 // Otherwise evaluate string length with propagated constants.
513 const Object& o = instr->ArgumentAt(0)->constant_value();
514 if (IsConstant(o) && o.IsString()) {
515 const auto& str = String::Cast(o);
516 if (kind == MethodRecognizer::kStringBaseLength) {
517 SetValue(instr, Integer::ZoneHandle(Z, Integer::New(str.Length())));
518 } else {
519 SetValue(instr, Bool::Get(str.Length() == 0));
520 }
521 return;
522 }
523 break;
524 }
525 default:
526 break;
527 }
528 SetValue(instr, non_constant_);
529}
530
531void ConstantPropagator::VisitLoadLocal(LoadLocalInstr* instr) {
532 // Instruction is eliminated when translating to SSA.
533 UNREACHABLE();
534}
535
536void ConstantPropagator::VisitDropTemps(DropTempsInstr* instr) {
537 // Instruction is eliminated when translating to SSA.
538 UNREACHABLE();
539}
540
541void ConstantPropagator::VisitMakeTemp(MakeTempInstr* instr) {
542 // Instruction is eliminated when translating to SSA.
543 UNREACHABLE();
544}
545
546void ConstantPropagator::VisitStoreLocal(StoreLocalInstr* instr) {
547 // Instruction is eliminated when translating to SSA.
548 UNREACHABLE();
549}
550
551void ConstantPropagator::VisitIfThenElse(IfThenElseInstr* instr) {
552 instr->comparison()->Accept(this);
553 const Object& value = instr->comparison()->constant_value();
554 if (IsNonConstant(value)) {
555 SetValue(instr, non_constant_);
556 } else if (IsConstant(value)) {
557 ASSERT(!value.IsNull());
558 ASSERT(value.IsBool());
559 bool result = Bool::Cast(value).value();
560 SetValue(instr, Smi::Handle(Z, Smi::New(result ? instr->if_true()
561 : instr->if_false())));
562 }
563}
564
565void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) {
566 Definition* left_defn = instr->left()->definition();
567 Definition* right_defn = instr->right()->definition();
568
569 Definition* unwrapped_left_defn = UnwrapPhi(left_defn);
570 Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
571 if (unwrapped_left_defn == unwrapped_right_defn) {
572 // Fold x === x, and x !== x to true/false.
573 if (SetValue(instr, Bool::Get(instr->kind() == Token::kEQ_STRICT))) {
574 if (unwrapped_left_defn != left_defn) {
575 MarkUnwrappedPhi(left_defn);
576 }
577 if (unwrapped_right_defn != right_defn) {
578 MarkUnwrappedPhi(right_defn);
579 }
580 }
581 return;
582 }
583
584 const Object& left = left_defn->constant_value();
585 const Object& right = right_defn->constant_value();
586 if (IsNonConstant(left) || IsNonConstant(right)) {
587 // TODO(vegorov): incorporate nullability information into the lattice.
588 if ((left.IsNull() && instr->right()->Type()->HasDecidableNullability()) ||
589 (right.IsNull() && instr->left()->Type()->HasDecidableNullability())) {
590 bool result = left.IsNull() ? instr->right()->Type()->IsNull()
591 : instr->left()->Type()->IsNull();
592 if (instr->kind() == Token::kNE_STRICT) {
593 result = !result;
594 }
595 SetValue(instr, Bool::Get(result));
596 } else {
597 const intptr_t left_cid = instr->left()->Type()->ToCid();
598 const intptr_t right_cid = instr->right()->Type()->ToCid();
599 // If exact classes (cids) are known and they differ, the result
600 // of strict compare can be computed.
601 // The only exception is comparison with special sentinel value
602 // (used for lazy initialization) which can be compared to a
603 // value of any type. Sentinel value has kNeverCid.
604 if ((left_cid != kDynamicCid) && (right_cid != kDynamicCid) &&
605 (left_cid != kNeverCid) && (right_cid != kNeverCid) &&
606 (left_cid != right_cid)) {
607 const bool result = (instr->kind() != Token::kEQ_STRICT);
608 SetValue(instr, Bool::Get(result));
609 } else {
610 SetValue(instr, non_constant_);
611 }
612 }
613 } else if (IsConstant(left) && IsConstant(right)) {
614 bool result = IsIdenticalConstants(left, right);
615 if (instr->kind() == Token::kNE_STRICT) {
616 result = !result;
617 }
618 SetValue(instr, Bool::Get(result));
619 }
620}
621
622static bool CompareIntegers(Token::Kind kind,
623 const Integer& left,
624 const Integer& right) {
625 const int result = left.CompareWith(right);
626 switch (kind) {
627 case Token::kEQ:
628 return (result == 0);
629 case Token::kNE:
630 return (result != 0);
631 case Token::kLT:
632 return (result < 0);
633 case Token::kGT:
634 return (result > 0);
635 case Token::kLTE:
636 return (result <= 0);
637 case Token::kGTE:
638 return (result >= 0);
639 default:
640 UNREACHABLE();
641 return false;
642 }
643}
644
645// Comparison instruction that is equivalent to the (left & right) == 0
646// comparison pattern.
647void ConstantPropagator::VisitTestSmi(TestSmiInstr* instr) {
648 const Object& left = instr->left()->definition()->constant_value();
649 const Object& right = instr->right()->definition()->constant_value();
650 if (IsNonConstant(left) || IsNonConstant(right)) {
651 SetValue(instr, non_constant_);
652 } else if (IsConstant(left) && IsConstant(right)) {
653 if (left.IsInteger() && right.IsInteger()) {
654 const bool result = CompareIntegers(
655 instr->kind(),
656 Integer::Handle(Z, Integer::Cast(left).BitOp(Token::kBIT_AND,
657 Integer::Cast(right))),
658 Object::smi_zero());
659 SetValue(instr, result ? Bool::True() : Bool::False());
660 } else {
661 SetValue(instr, non_constant_);
662 }
663 }
664}
665
666void ConstantPropagator::VisitTestCids(TestCidsInstr* instr) {
667 // TODO(sra): Constant fold test.
668 SetValue(instr, non_constant_);
669}
670
671void ConstantPropagator::VisitEqualityCompare(EqualityCompareInstr* instr) {
672 Definition* left_defn = instr->left()->definition();
673 Definition* right_defn = instr->right()->definition();
674
675 if (IsIntegerClassId(instr->operation_cid())) {
676 // Fold x == x, and x != x to true/false for numbers comparisons.
677 Definition* unwrapped_left_defn = UnwrapPhi(left_defn);
678 Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
679 if (unwrapped_left_defn == unwrapped_right_defn) {
680 // Fold x === x, and x !== x to true/false.
681 if (SetValue(instr, Bool::Get(instr->kind() == Token::kEQ))) {
682 if (unwrapped_left_defn != left_defn) {
683 MarkUnwrappedPhi(left_defn);
684 }
685 if (unwrapped_right_defn != right_defn) {
686 MarkUnwrappedPhi(right_defn);
687 }
688 }
689 return;
690 }
691 }
692
693 const Object& left = left_defn->constant_value();
694 const Object& right = right_defn->constant_value();
695 if (IsNonConstant(left) || IsNonConstant(right)) {
696 SetValue(instr, non_constant_);
697 } else if (IsConstant(left) && IsConstant(right)) {
698 if (left.IsInteger() && right.IsInteger()) {
699 const bool result = CompareIntegers(instr->kind(), Integer::Cast(left),
700 Integer::Cast(right));
701 SetValue(instr, Bool::Get(result));
702 } else if (left.IsString() && right.IsString()) {
703 const bool result = String::Cast(left).Equals(String::Cast(right));
704 SetValue(instr, Bool::Get((instr->kind() == Token::kEQ) == result));
705 } else {
706 SetValue(instr, non_constant_);
707 }
708 }
709}
710
711void ConstantPropagator::VisitRelationalOp(RelationalOpInstr* instr) {
712 const Object& left = instr->left()->definition()->constant_value();
713 const Object& right = instr->right()->definition()->constant_value();
714 if (IsNonConstant(left) || IsNonConstant(right)) {
715 SetValue(instr, non_constant_);
716 } else if (IsConstant(left) && IsConstant(right)) {
717 if (left.IsInteger() && right.IsInteger()) {
718 const bool result = CompareIntegers(instr->kind(), Integer::Cast(left),
719 Integer::Cast(right));
720 SetValue(instr, Bool::Get(result));
721 } else if (left.IsDouble() && right.IsDouble()) {
722 // TODO(srdjan): Implement.
723 SetValue(instr, non_constant_);
724 } else {
725 SetValue(instr, non_constant_);
726 }
727 }
728}
729
730void ConstantPropagator::VisitNativeCall(NativeCallInstr* instr) {
731 SetValue(instr, non_constant_);
732}
733
734void ConstantPropagator::VisitFfiCall(FfiCallInstr* instr) {
735 SetValue(instr, non_constant_);
736}
737
738void ConstantPropagator::VisitEnterHandleScope(EnterHandleScopeInstr* instr) {
739 SetValue(instr, non_constant_);
740}
741
742void ConstantPropagator::VisitExitHandleScope(ExitHandleScopeInstr* instr) {
743 // Nothing to do.
744}
745
746void ConstantPropagator::VisitAllocateHandle(AllocateHandleInstr* instr) {
747 SetValue(instr, non_constant_);
748}
749
750void ConstantPropagator::VisitRawStoreField(RawStoreFieldInstr* instr) {
751 // Nothing to do.
752}
753
754void ConstantPropagator::VisitDebugStepCheck(DebugStepCheckInstr* instr) {
755 // Nothing to do.
756}
757
758void ConstantPropagator::VisitOneByteStringFromCharCode(
759 OneByteStringFromCharCodeInstr* instr) {
760 const Object& o = instr->char_code()->definition()->constant_value();
761 if (o.IsNull() || IsNonConstant(o)) {
762 SetValue(instr, non_constant_);
763 } else if (IsConstant(o)) {
764 const intptr_t ch_code = Smi::Cast(o).Value();
765 ASSERT(ch_code >= 0);
766 if (ch_code < Symbols::kMaxOneCharCodeSymbol) {
767 StringPtr* table = Symbols::PredefinedAddress();
768 SetValue(instr, String::ZoneHandle(Z, table[ch_code]));
769 } else {
770 SetValue(instr, non_constant_);
771 }
772 }
773}
774
775void ConstantPropagator::VisitStringToCharCode(StringToCharCodeInstr* instr) {
776 const Object& o = instr->str()->definition()->constant_value();
777 if (o.IsNull() || IsNonConstant(o)) {
778 SetValue(instr, non_constant_);
779 } else if (IsConstant(o)) {
780 const String& str = String::Cast(o);
781 const intptr_t result =
782 (str.Length() == 1) ? static_cast<intptr_t>(str.CharAt(0)) : -1;
783 SetValue(instr, Smi::ZoneHandle(Z, Smi::New(result)));
784 }
785}
786
787void ConstantPropagator::VisitStringInterpolate(StringInterpolateInstr* instr) {
788 SetValue(instr, non_constant_);
789}
790
791void ConstantPropagator::VisitUtf8Scan(Utf8ScanInstr* instr) {
792 SetValue(instr, non_constant_);
793}
794
795void ConstantPropagator::VisitLoadIndexed(LoadIndexedInstr* instr) {
796 const Object& array_obj = instr->array()->definition()->constant_value();
797 const Object& index_obj = instr->index()->definition()->constant_value();
798 if (IsNonConstant(array_obj) || IsNonConstant(index_obj)) {
799 SetValue(instr, non_constant_);
800 } else if (IsConstant(array_obj) && IsConstant(index_obj)) {
801 // Need index to be Smi and array to be either String or an immutable array.
802 if (!index_obj.IsSmi()) {
803 // Should not occur.
804 SetValue(instr, non_constant_);
805 return;
806 }
807 const intptr_t index = Smi::Cast(index_obj).Value();
808 if (index >= 0) {
809 if (array_obj.IsString()) {
810 const String& str = String::Cast(array_obj);
811 if (str.Length() > index) {
812 SetValue(instr,
813 Smi::Handle(
814 Z, Smi::New(static_cast<intptr_t>(str.CharAt(index)))));
815 return;
816 }
817 } else if (array_obj.IsArray()) {
818 const Array& a = Array::Cast(array_obj);
819 if ((a.Length() > index) && a.IsImmutable()) {
820 Instance& result = Instance::Handle(Z);
821 result ^= a.At(index);
822 SetValue(instr, result);
823 return;
824 }
825 }
826 }
827 SetValue(instr, non_constant_);
828 }
829}
830
831void ConstantPropagator::VisitLoadCodeUnits(LoadCodeUnitsInstr* instr) {
832 // TODO(zerny): Implement constant propagation.
833 SetValue(instr, non_constant_);
834}
835
836void ConstantPropagator::VisitLoadIndexedUnsafe(LoadIndexedUnsafeInstr* instr) {
837 SetValue(instr, non_constant_);
838}
839
840void ConstantPropagator::VisitLoadStaticField(LoadStaticFieldInstr* instr) {
841 if (!FLAG_fields_may_be_reset) {
842 const Field& field = instr->field();
843 ASSERT(field.is_static());
844 if (field.is_final() && instr->IsFieldInitialized()) {
845 Instance& obj = Instance::Handle(Z, field.StaticValue());
846 if (obj.IsSmi() || (obj.IsOld() && obj.IsCanonical())) {
847 SetValue(instr, obj);
848 return;
849 }
850 }
851 }
852 SetValue(instr, non_constant_);
853}
854
855void ConstantPropagator::VisitStoreStaticField(StoreStaticFieldInstr* instr) {
856 SetValue(instr, instr->value()->definition()->constant_value());
857}
858
859void ConstantPropagator::VisitBooleanNegate(BooleanNegateInstr* instr) {
860 const Object& value = instr->value()->definition()->constant_value();
861 if (IsNonConstant(value)) {
862 SetValue(instr, non_constant_);
863 } else if (IsConstant(value)) {
864 bool val = value.raw() != Bool::True().raw();
865 SetValue(instr, Bool::Get(val));
866 }
867}
868
869void ConstantPropagator::VisitInstanceOf(InstanceOfInstr* instr) {
870 Definition* def = instr->value()->definition();
871 const Object& value = def->constant_value();
872 const AbstractType& checked_type = instr->type();
873 // If the checked type is a top type, the result is always true.
874 if (checked_type.IsTopTypeForInstanceOf()) {
875 SetValue(instr, Bool::True());
876 } else if (IsNonConstant(value)) {
877 intptr_t value_cid = instr->value()->definition()->Type()->ToCid();
878 Representation rep = def->representation();
879 if ((checked_type.IsFloat32x4Type() && (rep == kUnboxedFloat32x4)) ||
880 (checked_type.IsInt32x4Type() && (rep == kUnboxedInt32x4)) ||
881 (checked_type.IsDoubleType() && (rep == kUnboxedDouble) &&
882 FlowGraphCompiler::SupportsUnboxedDoubles()) ||
883 (checked_type.IsIntType() && (rep == kUnboxedInt64))) {
884 // Ensure that compile time type matches representation.
885 ASSERT(((rep == kUnboxedFloat32x4) && (value_cid == kFloat32x4Cid)) ||
886 ((rep == kUnboxedInt32x4) && (value_cid == kInt32x4Cid)) ||
887 ((rep == kUnboxedDouble) && (value_cid == kDoubleCid)) ||
888 ((rep == kUnboxedInt64) && (value_cid == kMintCid)));
889 // The representation guarantees the type check to be true.
890 SetValue(instr, Bool::True());
891 } else {
892 SetValue(instr, non_constant_);
893 }
894 } else if (IsConstant(value)) {
895 if (value.IsInstance()) {
896 const Instance& instance = Instance::Cast(value);
897 if (instr->instantiator_type_arguments()->BindsToConstantNull() &&
898 instr->function_type_arguments()->BindsToConstantNull()) {
899 bool is_instance =
900 instance.IsInstanceOf(checked_type, Object::null_type_arguments(),
901 Object::null_type_arguments());
902 SetValue(instr, Bool::Get(is_instance));
903 return;
904 }
905 }
906 SetValue(instr, non_constant_);
907 }
908}
909
910void ConstantPropagator::VisitCreateArray(CreateArrayInstr* instr) {
911 SetValue(instr, non_constant_);
912}
913
914void ConstantPropagator::VisitAllocateObject(AllocateObjectInstr* instr) {
915 SetValue(instr, non_constant_);
916}
917
918void ConstantPropagator::VisitLoadUntagged(LoadUntaggedInstr* instr) {
919 SetValue(instr, non_constant_);
920}
921
922void ConstantPropagator::VisitLoadClassId(LoadClassIdInstr* instr) {
923 // This first part duplicates the work done in LoadClassIdInstr::Canonicalize,
924 // which replaces uses of LoadClassIdInstr where the object has a concrete
925 // type with a Constant. Canonicalize runs before the ConstantPropagation
926 // pass, so if that was all, this wouldn't be needed.
927 //
928 // However, the ConstantPropagator also runs as part of OptimizeBranches, and
929 // TypePropagation runs between it and the previous Canonicalize. Thus, the
930 // type may have become concrete and we should take that into account. Not
931 // doing so led to some benchmark regressions.
932 intptr_t cid = instr->object()->Type()->ToCid();
933 if (cid != kDynamicCid) {
934 SetValue(instr, Smi::ZoneHandle(Z, Smi::New(cid)));
935 return;
936 }
937 const Object& object = instr->object()->definition()->constant_value();
938 if (IsConstant(object)) {
939 cid = object.GetClassId();
940 SetValue(instr, Smi::ZoneHandle(Z, Smi::New(cid)));
941 return;
942 }
943 SetValue(instr, non_constant_);
944}
945
946void ConstantPropagator::VisitLoadField(LoadFieldInstr* instr) {
947 Value* instance = instr->instance();
948 if ((instr->slot().kind() == Slot::Kind::kArray_length) &&
949 instance->definition()->OriginalDefinition()->IsCreateArray()) {
950 Value* num_elements = instance->definition()
951 ->OriginalDefinition()
952 ->AsCreateArray()
953 ->num_elements();
954 if (num_elements->BindsToConstant() &&
955 num_elements->BoundConstant().IsSmi()) {
956 intptr_t length = Smi::Cast(num_elements->BoundConstant()).Value();
957 const Object& result = Smi::ZoneHandle(Z, Smi::New(length));
958 SetValue(instr, result);
959 return;
960 }
961 }
962
963 const Object& constant = instance->definition()->constant_value();
964 if (IsConstant(constant)) {
965 if (instr->IsImmutableLengthLoad()) {
966 if (constant.IsString()) {
967 SetValue(instr,
968 Smi::ZoneHandle(Z, Smi::New(String::Cast(constant).Length())));
969 return;
970 }
971 if (constant.IsArray()) {
972 SetValue(instr,
973 Smi::ZoneHandle(Z, Smi::New(Array::Cast(constant).Length())));
974 return;
975 }
976 if (constant.IsTypedData()) {
977 SetValue(instr, Smi::ZoneHandle(
978 Z, Smi::New(TypedData::Cast(constant).Length())));
979 return;
980 }
981 } else {
982 Object& value = Object::Handle();
983 if (instr->Evaluate(constant, &value)) {
984 SetValue(instr, Object::ZoneHandle(Z, value.raw()));
985 return;
986 }
987 }
988 }
989
990 SetValue(instr, non_constant_);
991}
992
993void ConstantPropagator::VisitInstantiateType(InstantiateTypeInstr* instr) {
994 TypeArguments& instantiator_type_args = TypeArguments::Handle(Z);
995 TypeArguments& function_type_args = TypeArguments::Handle(Z);
996 if (!instr->type().IsInstantiated(kCurrentClass)) {
997 // Type refers to class type parameters.
998 const Object& instantiator_type_args_obj =
999 instr->instantiator_type_arguments()->definition()->constant_value();
1000 if (IsNonConstant(instantiator_type_args_obj)) {
1001 SetValue(instr, non_constant_);
1002 return;
1003 }
1004 if (IsConstant(instantiator_type_args_obj)) {
1005 instantiator_type_args ^= instantiator_type_args_obj.raw();
1006 } else {
1007 return;
1008 }
1009 }
1010 if (!instr->type().IsInstantiated(kFunctions)) {
1011 // Type refers to function type parameters.
1012 const Object& function_type_args_obj =
1013 instr->function_type_arguments()->definition()->constant_value();
1014 if (IsNonConstant(function_type_args_obj)) {
1015 SetValue(instr, non_constant_);
1016 return;
1017 }
1018 if (IsConstant(function_type_args_obj)) {
1019 function_type_args ^= function_type_args_obj.raw();
1020 } else {
1021 return;
1022 }
1023 }
1024 AbstractType& result = AbstractType::Handle(
1025 Z, instr->type().InstantiateFrom(
1026 instantiator_type_args, function_type_args, kAllFree, Heap::kOld));
1027 if (result.IsTypeRef()) {
1028 result = TypeRef::Cast(result).type();
1029 }
1030 ASSERT(result.IsInstantiated());
1031 result = result.Canonicalize();
1032 SetValue(instr, result);
1033}
1034
1035void ConstantPropagator::VisitInstantiateTypeArguments(
1036 InstantiateTypeArgumentsInstr* instr) {
1037 TypeArguments& instantiator_type_args = TypeArguments::Handle(Z);
1038 TypeArguments& function_type_args = TypeArguments::Handle(Z);
1039 if (!instr->type_arguments().IsInstantiated(kCurrentClass)) {
1040 // Type arguments refer to class type parameters.
1041 const Object& instantiator_type_args_obj =
1042 instr->instantiator_type_arguments()->definition()->constant_value();
1043 if (IsNonConstant(instantiator_type_args_obj)) {
1044 SetValue(instr, non_constant_);
1045 return;
1046 }
1047 if (IsConstant(instantiator_type_args_obj)) {
1048 instantiator_type_args ^= instantiator_type_args_obj.raw();
1049 if (instr->type_arguments().CanShareInstantiatorTypeArguments(
1050 instr->instantiator_class())) {
1051 SetValue(instr, instantiator_type_args);
1052 return;
1053 }
1054 } else {
1055 return;
1056 }
1057 }
1058 if (!instr->type_arguments().IsInstantiated(kFunctions)) {
1059 // Type arguments refer to function type parameters.
1060 const Object& function_type_args_obj =
1061 instr->function_type_arguments()->definition()->constant_value();
1062 if (IsNonConstant(function_type_args_obj)) {
1063 SetValue(instr, non_constant_);
1064 return;
1065 }
1066 if (IsConstant(function_type_args_obj)) {
1067 function_type_args ^= function_type_args_obj.raw();
1068 if (instr->type_arguments().CanShareFunctionTypeArguments(
1069 instr->function())) {
1070 SetValue(instr, function_type_args);
1071 return;
1072 }
1073 } else {
1074 return;
1075 }
1076 }
1077 TypeArguments& result = TypeArguments::Handle(
1078 Z, instr->type_arguments().InstantiateFrom(
1079 instantiator_type_args, function_type_args, kAllFree, Heap::kOld));
1080 ASSERT(result.IsInstantiated());
1081 result = result.Canonicalize();
1082 SetValue(instr, result);
1083}
1084
1085void ConstantPropagator::VisitAllocateContext(AllocateContextInstr* instr) {
1086 SetValue(instr, non_constant_);
1087}
1088
1089void ConstantPropagator::VisitAllocateUninitializedContext(
1090 AllocateUninitializedContextInstr* instr) {
1091 SetValue(instr, non_constant_);
1092}
1093
1094void ConstantPropagator::VisitCloneContext(CloneContextInstr* instr) {
1095 SetValue(instr, non_constant_);
1096}
1097
1098void ConstantPropagator::VisitBinaryIntegerOp(BinaryIntegerOpInstr* binary_op) {
1099 const Object& left = binary_op->left()->definition()->constant_value();
1100 const Object& right = binary_op->right()->definition()->constant_value();
1101 if (IsConstant(left) && IsConstant(right)) {
1102 const Integer& result = Integer::Handle(
1103 Z, Evaluator::BinaryIntegerEvaluate(left, right, binary_op->op_kind(),
1104 binary_op->is_truncating(),
1105 binary_op->representation(), T));
1106 if (!result.IsNull()) {
1107 SetValue(binary_op, Integer::ZoneHandle(Z, result.raw()));
1108 return;
1109 }
1110 }
1111 SetValue(binary_op, non_constant_);
1112}
1113
1114void ConstantPropagator::VisitCheckedSmiOp(CheckedSmiOpInstr* instr) {
1115 SetValue(instr, non_constant_);
1116}
1117
1118void ConstantPropagator::VisitCheckedSmiComparison(
1119 CheckedSmiComparisonInstr* instr) {
1120 SetValue(instr, non_constant_);
1121}
1122
1123void ConstantPropagator::VisitBinarySmiOp(BinarySmiOpInstr* instr) {
1124 VisitBinaryIntegerOp(instr);
1125}
1126
1127void ConstantPropagator::VisitBinaryInt32Op(BinaryInt32OpInstr* instr) {
1128 VisitBinaryIntegerOp(instr);
1129}
1130
1131void ConstantPropagator::VisitBinaryUint32Op(BinaryUint32OpInstr* instr) {
1132 VisitBinaryIntegerOp(instr);
1133}
1134
1135void ConstantPropagator::VisitBinaryInt64Op(BinaryInt64OpInstr* instr) {
1136 VisitBinaryIntegerOp(instr);
1137}
1138
1139void ConstantPropagator::VisitShiftInt64Op(ShiftInt64OpInstr* instr) {
1140 VisitBinaryIntegerOp(instr);
1141}
1142
1143void ConstantPropagator::VisitSpeculativeShiftInt64Op(
1144 SpeculativeShiftInt64OpInstr* instr) {
1145 VisitBinaryIntegerOp(instr);
1146}
1147
1148void ConstantPropagator::VisitShiftUint32Op(ShiftUint32OpInstr* instr) {
1149 VisitBinaryIntegerOp(instr);
1150}
1151
1152void ConstantPropagator::VisitSpeculativeShiftUint32Op(
1153 SpeculativeShiftUint32OpInstr* instr) {
1154 VisitBinaryIntegerOp(instr);
1155}
1156
1157void ConstantPropagator::VisitBoxInt64(BoxInt64Instr* instr) {
1158 // TODO(kmillikin): Handle box operation.
1159 SetValue(instr, non_constant_);
1160}
1161
1162void ConstantPropagator::VisitUnboxInt64(UnboxInt64Instr* instr) {
1163 // TODO(kmillikin): Handle unbox operation.
1164 SetValue(instr, non_constant_);
1165}
1166
1167void ConstantPropagator::VisitUnaryIntegerOp(UnaryIntegerOpInstr* unary_op) {
1168 const Object& value = unary_op->value()->definition()->constant_value();
1169 if (IsConstant(value)) {
1170 const Integer& result = Integer::Handle(
1171 Z, Evaluator::UnaryIntegerEvaluate(value, unary_op->op_kind(),
1172 unary_op->representation(), T));
1173 if (!result.IsNull()) {
1174 SetValue(unary_op, Integer::ZoneHandle(Z, result.raw()));
1175 return;
1176 }
1177 }
1178
1179 SetValue(unary_op, non_constant_);
1180}
1181
1182void ConstantPropagator::VisitUnaryInt64Op(UnaryInt64OpInstr* instr) {
1183 VisitUnaryIntegerOp(instr);
1184}
1185
1186void ConstantPropagator::VisitUnarySmiOp(UnarySmiOpInstr* instr) {
1187 VisitUnaryIntegerOp(instr);
1188}
1189
1190void ConstantPropagator::VisitUnaryDoubleOp(UnaryDoubleOpInstr* instr) {
1191 const Object& value = instr->value()->definition()->constant_value();
1192 if (IsNonConstant(value)) {
1193 SetValue(instr, non_constant_);
1194 } else if (IsConstant(value)) {
1195 // TODO(kmillikin): Handle unary operations.
1196 SetValue(instr, non_constant_);
1197 }
1198}
1199
1200void ConstantPropagator::VisitSmiToDouble(SmiToDoubleInstr* instr) {
1201 const Object& value = instr->value()->definition()->constant_value();
1202 if (IsConstant(value) && value.IsInteger()) {
1203 SetValue(instr,
1204 Double::Handle(Z, Double::New(Integer::Cast(value).AsDoubleValue(),
1205 Heap::kOld)));
1206 } else if (!IsUnknown(value)) {
1207 SetValue(instr, non_constant_);
1208 }
1209}
1210
1211void ConstantPropagator::VisitInt64ToDouble(Int64ToDoubleInstr* instr) {
1212 const Object& value = instr->value()->definition()->constant_value();
1213 if (IsConstant(value) && value.IsInteger()) {
1214 SetValue(instr,
1215 Double::Handle(Z, Double::New(Integer::Cast(value).AsDoubleValue(),
1216 Heap::kOld)));
1217 } else if (!IsUnknown(value)) {
1218 SetValue(instr, non_constant_);
1219 }
1220}
1221
1222void ConstantPropagator::VisitInt32ToDouble(Int32ToDoubleInstr* instr) {
1223 const Object& value = instr->value()->definition()->constant_value();
1224 if (IsConstant(value) && value.IsInteger()) {
1225 SetValue(instr,
1226 Double::Handle(Z, Double::New(Integer::Cast(value).AsDoubleValue(),
1227 Heap::kOld)));
1228 } else if (!IsUnknown(value)) {
1229 SetValue(instr, non_constant_);
1230 }
1231}
1232
1233void ConstantPropagator::VisitDoubleToInteger(DoubleToIntegerInstr* instr) {
1234 // TODO(kmillikin): Handle conversion.
1235 SetValue(instr, non_constant_);
1236}
1237
1238void ConstantPropagator::VisitDoubleToSmi(DoubleToSmiInstr* instr) {
1239 // TODO(kmillikin): Handle conversion.
1240 SetValue(instr, non_constant_);
1241}
1242
1243void ConstantPropagator::VisitDoubleToDouble(DoubleToDoubleInstr* instr) {
1244 // TODO(kmillikin): Handle conversion.
1245 SetValue(instr, non_constant_);
1246}
1247
1248void ConstantPropagator::VisitDoubleToFloat(DoubleToFloatInstr* instr) {
1249 // TODO(kmillikin): Handle conversion.
1250 SetValue(instr, non_constant_);
1251}
1252
1253void ConstantPropagator::VisitFloatToDouble(FloatToDoubleInstr* instr) {
1254 // TODO(kmillikin): Handle conversion.
1255 SetValue(instr, non_constant_);
1256}
1257
1258void ConstantPropagator::VisitInvokeMathCFunction(
1259 InvokeMathCFunctionInstr* instr) {
1260 // TODO(kmillikin): Handle conversion.
1261 SetValue(instr, non_constant_);
1262}
1263
1264void ConstantPropagator::VisitTruncDivMod(TruncDivModInstr* instr) {
1265 // TODO(srdjan): Handle merged instruction.
1266 SetValue(instr, non_constant_);
1267}
1268
1269void ConstantPropagator::VisitExtractNthOutput(ExtractNthOutputInstr* instr) {
1270 SetValue(instr, non_constant_);
1271}
1272
1273void ConstantPropagator::VisitConstant(ConstantInstr* instr) {
1274 SetValue(instr, instr->value());
1275}
1276
1277void ConstantPropagator::VisitUnboxedConstant(UnboxedConstantInstr* instr) {
1278 SetValue(instr, instr->value());
1279}
1280
1281void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
1282 // Should not be used outside of range analysis.
1283 UNREACHABLE();
1284}
1285
1286void ConstantPropagator::VisitMaterializeObject(MaterializeObjectInstr* instr) {
1287 // Should not be used outside of allocation elimination pass.
1288 UNREACHABLE();
1289}
1290
1291static bool IsIntegerOrDouble(const Object& value) {
1292 return value.IsInteger() || value.IsDouble();
1293}
1294
1295static double ToDouble(const Object& value) {
1296 return value.IsInteger() ? Integer::Cast(value).AsDoubleValue()
1297 : Double::Cast(value).value();
1298}
1299
1300void ConstantPropagator::VisitBinaryDoubleOp(BinaryDoubleOpInstr* instr) {
1301 const Object& left = instr->left()->definition()->constant_value();
1302 const Object& right = instr->right()->definition()->constant_value();
1303 if (IsConstant(left) && IsConstant(right)) {
1304 const bool both_are_integers = left.IsInteger() && right.IsInteger();
1305 if (IsIntegerOrDouble(left) && IsIntegerOrDouble(right) &&
1306 !both_are_integers) {
1307 const double result_val = Evaluator::EvaluateDoubleOp(
1308 ToDouble(left), ToDouble(right), instr->op_kind());
1309 const Double& result =
1310 Double::ZoneHandle(Double::NewCanonical(result_val));
1311 SetValue(instr, result);
1312 return;
1313 }
1314 }
1315 SetValue(instr, non_constant_);
1316}
1317
1318void ConstantPropagator::VisitDoubleTestOp(DoubleTestOpInstr* instr) {
1319 const Object& value = instr->value()->definition()->constant_value();
1320 const bool is_negated = instr->kind() != Token::kEQ;
1321 if (value.IsInteger()) {
1322 SetValue(instr, is_negated ? Bool::True() : Bool::False());
1323 } else if (IsIntegerOrDouble(value)) {
1324 switch (instr->op_kind()) {
1325 case MethodRecognizer::kDouble_getIsNaN: {
1326 const bool is_nan = isnan(ToDouble(value));
1327 SetValue(instr, Bool::Get(is_negated ? !is_nan : is_nan));
1328 break;
1329 }
1330 case MethodRecognizer::kDouble_getIsInfinite: {
1331 const bool is_inf = isinf(ToDouble(value));
1332 SetValue(instr, Bool::Get(is_negated ? !is_inf : is_inf));
1333 break;
1334 }
1335 default:
1336 UNREACHABLE();
1337 }
1338 } else {
1339 SetValue(instr, non_constant_);
1340 }
1341}
1342
1343void ConstantPropagator::VisitSimdOp(SimdOpInstr* instr) {
1344 SetValue(instr, non_constant_);
1345}
1346
1347void ConstantPropagator::VisitMathUnary(MathUnaryInstr* instr) {
1348 const Object& value = instr->value()->definition()->constant_value();
1349 if (IsNonConstant(value)) {
1350 SetValue(instr, non_constant_);
1351 } else if (IsConstant(value)) {
1352 // TODO(kmillikin): Handle Math's unary operations (sqrt, cos, sin).
1353 SetValue(instr, non_constant_);
1354 }
1355}
1356
1357void ConstantPropagator::VisitMathMinMax(MathMinMaxInstr* instr) {
1358 const Object& left = instr->left()->definition()->constant_value();
1359 const Object& right = instr->right()->definition()->constant_value();
1360 if (IsNonConstant(left) || IsNonConstant(right)) {
1361 SetValue(instr, non_constant_);
1362 } else if (IsConstant(left) && IsConstant(right)) {
1363 // TODO(srdjan): Handle min and max.
1364 SetValue(instr, non_constant_);
1365 }
1366}
1367
1368void ConstantPropagator::VisitCaseInsensitiveCompare(
1369 CaseInsensitiveCompareInstr* instr) {
1370 SetValue(instr, non_constant_);
1371}
1372
1373void ConstantPropagator::VisitUnbox(UnboxInstr* instr) {
1374 const Object& value = instr->value()->definition()->constant_value();
1375 if (IsNonConstant(value)) {
1376 SetValue(instr, non_constant_);
1377 } else if (IsConstant(value)) {
1378 // TODO(kmillikin): Handle conversion.
1379 SetValue(instr, non_constant_);
1380 }
1381}
1382
1383void ConstantPropagator::VisitBox(BoxInstr* instr) {
1384 const Object& value = instr->value()->definition()->constant_value();
1385 if (IsNonConstant(value)) {
1386 SetValue(instr, non_constant_);
1387 } else if (IsConstant(value)) {
1388 // TODO(kmillikin): Handle conversion.
1389 SetValue(instr, non_constant_);
1390 }
1391}
1392
1393void ConstantPropagator::VisitBoxUint32(BoxUint32Instr* instr) {
1394 // TODO(kmillikin): Handle box operation.
1395 SetValue(instr, non_constant_);
1396}
1397
1398void ConstantPropagator::VisitUnboxUint32(UnboxUint32Instr* instr) {
1399 // TODO(kmillikin): Handle unbox operation.
1400 SetValue(instr, non_constant_);
1401}
1402
1403void ConstantPropagator::VisitBoxInt32(BoxInt32Instr* instr) {
1404 // TODO(kmillikin): Handle box operation.
1405 SetValue(instr, non_constant_);
1406}
1407
1408void ConstantPropagator::VisitUnboxInt32(UnboxInt32Instr* instr) {
1409 // TODO(kmillikin): Handle unbox operation.
1410 SetValue(instr, non_constant_);
1411}
1412
1413void ConstantPropagator::VisitIntConverter(IntConverterInstr* instr) {
1414 SetValue(instr, non_constant_);
1415}
1416
1417void ConstantPropagator::VisitBitCast(BitCastInstr* instr) {
1418 SetValue(instr, non_constant_);
1419}
1420
1421void ConstantPropagator::VisitUnaryUint32Op(UnaryUint32OpInstr* instr) {
1422 // TODO(kmillikin): Handle unary operations.
1423 SetValue(instr, non_constant_);
1424}
1425
1426void ConstantPropagator::Analyze() {
1427 GraphEntryInstr* entry = graph_->graph_entry();
1428 reachable_->Add(entry->preorder_number());
1429 block_worklist_.Add(entry);
1430
1431 while (true) {
1432 if (block_worklist_.is_empty()) {
1433 if (definition_worklist_.IsEmpty()) break;
1434 Definition* definition = definition_worklist_.RemoveLast();
1435 for (Value* use = definition->input_use_list(); use != nullptr;
1436 use = use->next_use()) {
1437 use->instruction()->Accept(this);
1438 }
1439 } else {
1440 BlockEntryInstr* block = block_worklist_.RemoveLast();
1441 block->Accept(this);
1442 }
1443 }
1444}
1445
1446static bool HasPhis(BlockEntryInstr* block) {
1447 if (auto* join = block->AsJoinEntry()) {
1448 return (join->phis() != nullptr) && !join->phis()->is_empty();
1449 }
1450 return false;
1451}
1452
1453static bool IsEmptyBlock(BlockEntryInstr* block) {
1454 return block->next()->IsGoto() && !HasPhis(block) &&
1455 !block->IsIndirectEntry();
1456}
1457
1458// Traverses a chain of empty blocks and returns the first reachable non-empty
1459// block that is not dominated by the start block. The empty blocks are added
1460// to the supplied bit vector.
1461static BlockEntryInstr* FindFirstNonEmptySuccessor(TargetEntryInstr* block,
1462 BitVector* empty_blocks) {
1463 BlockEntryInstr* current = block;
1464 while (IsEmptyBlock(current) && block->Dominates(current)) {
1465 ASSERT(!HasPhis(block));
1466 empty_blocks->Add(current->preorder_number());
1467 current = current->next()->AsGoto()->successor();
1468 }
1469 return current;
1470}
1471
1472void ConstantPropagator::EliminateRedundantBranches() {
1473 // Canonicalize branches that have no side-effects and where true- and
1474 // false-targets are the same.
1475 bool changed = false;
1476 BitVector* empty_blocks = new (Z) BitVector(Z, graph_->preorder().length());
1477 for (BlockIterator b = graph_->postorder_iterator(); !b.Done(); b.Advance()) {
1478 BlockEntryInstr* block = b.Current();
1479 BranchInstr* branch = block->last_instruction()->AsBranch();
1480 empty_blocks->Clear();
1481 if ((branch != NULL) && !branch->HasUnknownSideEffects()) {
1482 ASSERT(branch->previous() != NULL); // Not already eliminated.
1483 BlockEntryInstr* if_true =
1484 FindFirstNonEmptySuccessor(branch->true_successor(), empty_blocks);
1485 BlockEntryInstr* if_false =
1486 FindFirstNonEmptySuccessor(branch->false_successor(), empty_blocks);
1487 if (if_true == if_false) {
1488 // Replace the branch with a jump to the common successor.
1489 // Drop the comparison, which does not have side effects
1490 JoinEntryInstr* join = if_true->AsJoinEntry();
1491 if (!HasPhis(join)) {
1492 GotoInstr* jump = new (Z) GotoInstr(join, DeoptId::kNone);
1493 graph_->CopyDeoptTarget(jump, branch);
1494
1495 Instruction* previous = branch->previous();
1496 branch->set_previous(NULL);
1497 previous->LinkTo(jump);
1498
1499 // Remove uses from branch and all the empty blocks that
1500 // are now unreachable.
1501 branch->UnuseAllInputs();
1502 for (BitVector::Iterator it(empty_blocks); !it.Done(); it.Advance()) {
1503 BlockEntryInstr* empty_block = graph_->preorder()[it.Current()];
1504 empty_block->ClearAllInstructions();
1505 }
1506
1507 changed = true;
1508
1509 if (FLAG_trace_constant_propagation && graph_->should_print()) {
1510 THR_Print("Eliminated branch in B%" Pd " common target B%" Pd "\n",
1511 block->block_id(), join->block_id());
1512 }
1513 }
1514 }
1515 }
1516 }
1517
1518 if (changed) {
1519 graph_->DiscoverBlocks();
1520 graph_->MergeBlocks();
1521 // TODO(fschneider): Update dominator tree in place instead of recomputing.
1522 GrowableArray<BitVector*> dominance_frontier;
1523 graph_->ComputeDominators(&dominance_frontier);
1524 }
1525}
1526
1527void ConstantPropagator::Transform() {
1528 // We will recompute dominators, block ordering, block ids, block last
1529 // instructions, previous pointers, predecessors, etc. after eliminating
1530 // unreachable code. We do not maintain those properties during the
1531 // transformation.
1532 for (BlockIterator b = graph_->reverse_postorder_iterator(); !b.Done();
1533 b.Advance()) {
1534 BlockEntryInstr* block = b.Current();
1535 if (!reachable_->Contains(block->preorder_number())) {
1536 if (FLAG_trace_constant_propagation && graph_->should_print()) {
1537 THR_Print("Unreachable B%" Pd "\n", block->block_id());
1538 }
1539 // Remove all uses in unreachable blocks.
1540 block->ClearAllInstructions();
1541 continue;
1542 }
1543
1544 JoinEntryInstr* join = block->AsJoinEntry();
1545 if (join != NULL) {
1546 // Remove phi inputs corresponding to unreachable predecessor blocks.
1547 // Predecessors will be recomputed (in block id order) after removing
1548 // unreachable code so we merely have to keep the phi inputs in order.
1549 ZoneGrowableArray<PhiInstr*>* phis = join->phis();
1550 if ((phis != NULL) && !phis->is_empty()) {
1551 intptr_t pred_count = join->PredecessorCount();
1552 intptr_t live_count = 0;
1553 for (intptr_t pred_idx = 0; pred_idx < pred_count; ++pred_idx) {
1554 if (reachable_->Contains(
1555 join->PredecessorAt(pred_idx)->preorder_number())) {
1556 if (live_count < pred_idx) {
1557 for (PhiIterator it(join); !it.Done(); it.Advance()) {
1558 PhiInstr* phi = it.Current();
1559 ASSERT(phi != NULL);
1560 phi->SetInputAt(live_count, phi->InputAt(pred_idx));
1561 }
1562 }
1563 ++live_count;
1564 } else {
1565 for (PhiIterator it(join); !it.Done(); it.Advance()) {
1566 PhiInstr* phi = it.Current();
1567 ASSERT(phi != NULL);
1568 phi->InputAt(pred_idx)->RemoveFromUseList();
1569 }
1570 }
1571 }
1572 if (live_count < pred_count) {
1573 intptr_t to_idx = 0;
1574 for (intptr_t from_idx = 0; from_idx < phis->length(); ++from_idx) {
1575 PhiInstr* phi = (*phis)[from_idx];
1576 ASSERT(phi != NULL);
1577 if (FLAG_remove_redundant_phis && (live_count == 1)) {
1578 Value* input = phi->InputAt(0);
1579 phi->ReplaceUsesWith(input->definition());
1580 input->RemoveFromUseList();
1581 } else {
1582 phi->inputs_.TruncateTo(live_count);
1583 (*phis)[to_idx++] = phi;
1584 }
1585 }
1586 if (to_idx == 0) {
1587 join->phis_ = NULL;
1588 } else {
1589 phis->TruncateTo(to_idx);
1590 }
1591 }
1592 }
1593 }
1594
1595 if (join != nullptr) {
1596 for (PhiIterator it(join); !it.Done(); it.Advance()) {
1597 auto phi = it.Current();
1598 if (TransformDefinition(phi)) {
1599 it.RemoveCurrentFromGraph();
1600 }
1601 }
1602 }
1603 for (ForwardInstructionIterator i(block); !i.Done(); i.Advance()) {
1604 Definition* defn = i.Current()->AsDefinition();
1605 if (TransformDefinition(defn)) {
1606 i.RemoveCurrentFromGraph();
1607 }
1608 }
1609
1610 // Replace branches where one target is unreachable with jumps.
1611 BranchInstr* branch = block->last_instruction()->AsBranch();
1612 if (branch != NULL) {
1613 TargetEntryInstr* if_true = branch->true_successor();
1614 TargetEntryInstr* if_false = branch->false_successor();
1615 JoinEntryInstr* join = NULL;
1616 Instruction* next = NULL;
1617
1618 if (!reachable_->Contains(if_true->preorder_number())) {
1619 ASSERT(reachable_->Contains(if_false->preorder_number()));
1620 ASSERT(if_false->parallel_move() == NULL);
1621 join = new (Z) JoinEntryInstr(if_false->block_id(),
1622 if_false->try_index(), DeoptId::kNone);
1623 graph_->CopyDeoptTarget(join, if_false);
1624 if_false->UnuseAllInputs();
1625 next = if_false->next();
1626 } else if (!reachable_->Contains(if_false->preorder_number())) {
1627 ASSERT(if_true->parallel_move() == NULL);
1628 join = new (Z) JoinEntryInstr(if_true->block_id(), if_true->try_index(),
1629 DeoptId::kNone);
1630 graph_->CopyDeoptTarget(join, if_true);
1631 if_true->UnuseAllInputs();
1632 next = if_true->next();
1633 }
1634
1635 if (join != NULL) {
1636 // Replace the branch with a jump to the reachable successor.
1637 // Drop the comparison, which does not have side effects as long
1638 // as it is a strict compare (the only one we can determine is
1639 // constant with the current analysis).
1640 GotoInstr* jump = new (Z) GotoInstr(join, DeoptId::kNone);
1641 graph_->CopyDeoptTarget(jump, branch);
1642
1643 Instruction* previous = branch->previous();
1644 branch->set_previous(NULL);
1645 previous->LinkTo(jump);
1646
1647 // Replace the false target entry with the new join entry. We will
1648 // recompute the dominators after this pass.
1649 join->LinkTo(next);
1650 branch->UnuseAllInputs();
1651 }
1652 }
1653 }
1654
1655 graph_->DiscoverBlocks();
1656 graph_->MergeBlocks();
1657 GrowableArray<BitVector*> dominance_frontier;
1658 graph_->ComputeDominators(&dominance_frontier);
1659}
1660
1661bool ConstantPropagator::TransformDefinition(Definition* defn) {
1662 // Replace constant-valued instructions without observable side
1663 // effects. Do this for smis and old objects only to avoid having to
1664 // copy other objects into the heap's old generation.
1665 ASSERT((defn == nullptr) || !defn->IsPushArgument());
1666 if ((defn != nullptr) && IsConstant(defn->constant_value()) &&
1667 (defn->constant_value().IsSmi() || defn->constant_value().IsOld()) &&
1668 !defn->IsConstant() && !defn->IsStoreIndexed() &&
1669 !defn->IsStoreInstanceField() && !defn->IsStoreStaticField()) {
1670 if (FLAG_trace_constant_propagation && graph_->should_print()) {
1671 THR_Print("Constant v%" Pd " = %s\n", defn->ssa_temp_index(),
1672 defn->constant_value().ToCString());
1673 }
1674 constant_value_ = defn->constant_value().raw();
1675 if ((constant_value_.IsString() || constant_value_.IsMint() ||
1676 constant_value_.IsDouble()) &&
1677 !constant_value_.IsCanonical()) {
1678 const char* error_str = nullptr;
1679 constant_value_ =
1680 Instance::Cast(constant_value_).CheckAndCanonicalize(T, &error_str);
1681 ASSERT(!constant_value_.IsNull() && (error_str == nullptr));
1682 }
1683 if (auto call = defn->AsStaticCall()) {
1684 ASSERT(!call->HasPushArguments());
1685 }
1686 Definition* replacement =
1687 graph_->TryCreateConstantReplacementFor(defn, constant_value_);
1688 if (replacement != defn) {
1689 defn->ReplaceUsesWith(replacement);
1690 return true;
1691 }
1692 }
1693 return false;
1694}
1695
1696} // namespace dart
1697