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 34267573 : void HInferRepresentationPhase::AddToWorklist(HValue* current) {
12 39251962 : if (current->representation().IsTagged()) return;
13 22870086 : if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return;
14 8002126 : if (in_worklist_.Contains(current->id())) return;
15 1966659 : worklist_.Add(current, zone());
16 : in_worklist_.Add(current->id());
17 : }
18 :
19 :
20 283728 : 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 9874424 : const ZoneList<HPhi*>* phi_list = graph()->phi_list();
24 283728 : int phi_count = phi_list->length();
25 283728 : ZoneList<BitVector*> connected_phis(phi_count, zone());
26 600550 : for (int i = 0; i < phi_count; ++i) {
27 316824 : phi_list->at(i)->InitRealUses(i);
28 316825 : BitVector* connected_set = new(zone()) BitVector(phi_count, zone());
29 316826 : 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 590041 : 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 1049733 : for (int i = phi_count - 1; i >= 0; --i) {
42 743418 : HPhi* phi = phi_list->at(i);
43 2954840 : for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) {
44 2211422 : HValue* use = it.value();
45 2211422 : if (use->IsPhi()) {
46 740358 : int id = HPhi::cast(use)->phi_id();
47 2961432 : 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 283728 : if (phi_count > 0) {
58 46803 : BitVector done(phi_count, zone());
59 363628 : for (int i = 0; i < phi_count; ++i) {
60 633650 : 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 1035792 : for (BitVector::Iterator it(connected_phis[i]);
66 649496 : !it.Done();
67 456348 : it.Advance()) {
68 456348 : int index = it.Current();
69 : all_uses_everywhere_truncating_int32 &=
70 912696 : phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32);
71 : all_uses_everywhere_truncating_smi &=
72 456348 : phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToSmi);
73 456348 : done.Add(index);
74 : }
75 :
76 193148 : if (!all_uses_everywhere_truncating_int32) {
77 : // Clear truncation flag of this group of connected phis.
78 897984 : for (BitVector::Iterator it(connected_phis[i]);
79 571680 : !it.Done();
80 408527 : it.Advance()) {
81 408527 : int index = it.Current();
82 408527 : phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32);
83 : }
84 : }
85 193149 : if (!all_uses_everywhere_truncating_smi) {
86 : // Clear truncation flag of this group of connected phis.
87 900520 : for (BitVector::Iterator it(connected_phis[i]);
88 573020 : !it.Done();
89 409271 : it.Advance()) {
90 409271 : int index = it.Current();
91 409271 : 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 316825 : for (int i = 0; i < phi_count; ++i) {
100 316825 : 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 316825 : for (int i = 0; i < phi_count; ++i) {
106 316825 : HPhi* phi = phi_list->at(i);
107 2192397 : for (BitVector::Iterator it(connected_phis[i]);
108 1558747 : !it.Done();
109 1241922 : it.Advance()) {
110 1241922 : int index = it.Current();
111 1241922 : HPhi* it_use = phi_list->at(index);
112 1241922 : if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice.
113 : }
114 : }
115 :
116 : // Initialize work list
117 9307104 : for (int i = 0; i < graph()->blocks()->length(); ++i) {
118 4511688 : HBasicBlock* block = graph()->blocks()->at(i);
119 : const ZoneList<HPhi*>* phis = block->phis();
120 9657110 : for (int j = 0; j < phis->length(); ++j) {
121 5145381 : AddToWorklist(phis->at(j));
122 : }
123 :
124 33113263 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
125 : HInstruction* current = it.Current();
126 28601575 : AddToWorklist(current);
127 : }
128 : }
129 :
130 : // Do a fixed point iteration, trying to improve representations
131 2250366 : while (!worklist_.is_empty()) {
132 6183644 : HValue* current = worklist_.RemoveLast();
133 1966641 : current->InferRepresentation(this);
134 1966638 : in_worklist_.Remove(current->id());
135 : }
136 :
137 : // Lastly: any instruction that we don't have representation information
138 : // for defaults to Tagged.
139 9306834 : for (int i = 0; i < graph()->blocks()->length(); ++i) {
140 4511550 : HBasicBlock* block = graph()->blocks()->at(i);
141 : const ZoneList<HPhi*>* phis = block->phis();
142 9656780 : for (int j = 0; j < phis->length(); ++j) {
143 5145214 : HPhi* phi = phis->at(j);
144 316824 : if (phi->representation().IsNone()) {
145 1768 : phi->ChangeRepresentation(Representation::Tagged());
146 : }
147 : }
148 33112517 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
149 : HInstruction* current = it.Current();
150 43840318 : if (current->representation().IsNone() &&
151 : current->CheckFlag(HInstruction::kFlexibleRepresentation)) {
152 59 : if (current->CheckFlag(HInstruction::kCannotBeTagged)) {
153 12 : current->ChangeRepresentation(Representation::Double());
154 : } else {
155 47 : current->ChangeRepresentation(Representation::Tagged());
156 : }
157 : }
158 : }
159 : }
160 283730 : }
161 :
162 : } // namespace internal
163 : } // namespace v8
|
