Line data Source code
1 : // Copyright 2013 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/crankshaft/hydrogen-infer-representation.h"
6 : #include "src/objects-inl.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 :
11 34209068 : void HInferRepresentationPhase::AddToWorklist(HValue* current) {
12 39212684 : if (current->representation().IsTagged()) return;
13 22840817 : if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
14 8034476 : if (in_worklist_.Contains(current->id())) return;
15 1972758 : worklist_.Add(current, zone());
16 : in_worklist_.Add(current->id());
17 : }
18 :
19 :
20 283196 : void HInferRepresentationPhase::Run() {
21 : // (1) Initialize bit vectors and count real uses. Each phi gets a
22 : // bit-vector of length <number of phis>.
23 9836499 : const ZoneList<HPhi*>* phi_list = graph()->phi_list();
24 283196 : int phi_count = phi_list->length();
25 283196 : ZoneList<BitVector*> connected_phis(phi_count, zone());
26 598826 : for (int i = 0; i < phi_count; ++i) {
27 315630 : phi_list->at(i)->InitRealUses(i);
28 315630 : BitVector* connected_set = new(zone()) BitVector(phi_count, zone());
29 315630 : connected_set->Add(i);
30 : connected_phis.Add(connected_set, zone());
31 : }
32 :
33 : // (2) Do a fixed point iteration to find the set of connected phis. A
34 : // phi is connected to another phi if its value is used either directly or
35 : // indirectly through a transitive closure of the def-use relation.
36 : bool change = true;
37 588936 : while (change) {
38 : change = false;
39 : // We normally have far more "forward edges" than "backward edges",
40 : // so we terminate faster when we walk backwards.
41 1046161 : for (int i = phi_count - 1; i >= 0; --i) {
42 740421 : HPhi* phi = phi_list->at(i);
43 2930844 : for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
44 2190423 : HValue* use = it.value();
45 2190423 : if (use->IsPhi()) {
46 738201 : int id = HPhi::cast(use)->phi_id();
47 2952804 : if (connected_phis[i]->UnionIsChanged(*connected_phis[id]))
48 : change = true;
49 : }
50 : }
51 : }
52 : }
53 :
54 : // Set truncation flags for groups of connected phis. This is a conservative
55 : // approximation; the flag will be properly re-computed after representations
56 : // have been determined.
57 283208 : if (phi_count > 0) {
58 46669 : BitVector done(phi_count, zone());
59 362299 : for (int i = 0; i < phi_count; ++i) {
60 631260 : if (done.Contains(i)) continue;
61 :
62 : // Check if all uses of all connected phis in this group are truncating.
63 : bool all_uses_everywhere_truncating_int32 = true;
64 : bool all_uses_everywhere_truncating_smi = true;
65 1031294 : for (BitVector::Iterator it(connected_phis[i]);
66 646724 : !it.Done();
67 454439 : it.Advance()) {
68 454439 : int index = it.Current();
69 : all_uses_everywhere_truncating_int32 &=
70 908878 : phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32);
71 : all_uses_everywhere_truncating_smi &=
72 454439 : phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi);
73 454439 : done.Add(index);
74 : }
75 :
76 192285 : if (!all_uses_everywhere_truncating_int32) {
77 : // Clear truncation flag of this group of connected phis.
78 893642 : for (BitVector::Iterator it(connected_phis[i]);
79 568976 : !it.Done();
80 406643 : it.Advance()) {
81 406643 : int index = it.Current();
82 406643 : phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32);
83 : }
84 : }
85 192285 : if (!all_uses_everywhere_truncating_smi) {
86 : // Clear truncation flag of this group of connected phis.
87 896119 : for (BitVector::Iterator it(connected_phis[i]);
88 570287 : !it.Done();
89 407371 : it.Advance()) {
90 407371 : int index = it.Current();
91 407371 : phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToSmi);
92 : }
93 : }
94 : }
95 : }
96 :
97 : // Simplify constant phi inputs where possible.
98 : // This step uses kTruncatingToInt32 flags of phis.
99 315630 : for (int i = 0; i < phi_count; ++i) {
100 315630 : phi_list->at(i)->SimplifyConstantInputs();
101 : }
102 :
103 : // Use the phi reachability information from step 2 to
104 : // sum up the non-phi use counts of all connected phis.
105 315630 : for (int i = 0; i < phi_count; ++i) {
106 315630 : HPhi* phi = phi_list->at(i);
107 2185878 : for (BitVector::Iterator it(connected_phis[i]);
108 1554618 : !it.Done();
109 1238988 : it.Advance()) {
110 1238988 : int index = it.Current();
111 1238988 : HPhi* it_use = phi_list->at(index);
112 1238988 : if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice.
113 : }
114 : }
115 :
116 : // Initialize work list
117 9269878 : for (int i = 0; i < graph()->blocks()->length(); ++i) {
118 4493346 : HBasicBlock* block = graph()->blocks()->at(i);
119 : const ZoneList<HPhi*>* phis = block->phis();
120 9618040 : for (int j = 0; j < phis->length(); ++j) {
121 5124648 : AddToWorklist(phis->at(j));
122 : }
123 :
124 33019388 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
125 : HInstruction* current = it.Current();
126 28526053 : AddToWorklist(current);
127 : }
128 : }
129 :
130 : // Do a fixed point iteration, trying to improve representations
131 2255960 : while (!worklist_.is_empty()) {
132 6201487 : HValue* current = worklist_.RemoveLast();
133 1972765 : current->InferRepresentation(this);
134 1972763 : in_worklist_.Remove(current->id());
135 : }
136 :
137 : // Lastly: any instruction that we don't have representation information
138 : // for defaults to Tagged.
139 9270324 : for (int i = 0; i < graph()->blocks()->length(); ++i) {
140 4493564 : HBasicBlock* block = graph()->blocks()->at(i);
141 : const ZoneList<HPhi*>* phis = block->phis();
142 9618420 : for (int j = 0; j < phis->length(); ++j) {
143 5124840 : HPhi* phi = phis->at(j);
144 315630 : if (phi->representation().IsNone()) {
145 1774 : phi->ChangeRepresentation(Representation::Tagged());
146 : }
147 : }
148 33020870 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
149 : HInstruction* current = it.Current();
150 43719658 : if (current->representation().IsNone() &&
151 : current->CheckFlag(HInstruction::kFlexibleRepresentation)) {
152 63 : if (current->CheckFlag(HInstruction::kCannotBeTagged)) {
153 16 : current->ChangeRepresentation(Representation::Double());
154 : } else {
155 47 : current->ChangeRepresentation(Representation::Tagged());
156 : }
157 : }
158 : }
159 : }
160 283196 : }
161 :
162 : } // namespace internal
163 : } // namespace v8
|
