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-uint32-analysis.h"
6 : #include "src/objects-inl.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 :
11 :
12 : static bool IsUnsignedLoad(HLoadKeyed* instr) {
13 : switch (instr->elements_kind()) {
14 : case UINT8_ELEMENTS:
15 : case UINT16_ELEMENTS:
16 : case UINT32_ELEMENTS:
17 : case UINT8_CLAMPED_ELEMENTS:
18 : return true;
19 : default:
20 : return false;
21 : }
22 : }
23 :
24 :
25 76 : static bool IsUint32Operation(HValue* instr) {
26 57 : return instr->IsShr() ||
27 152 : (instr->IsLoadKeyed() && IsUnsignedLoad(HLoadKeyed::cast(instr))) ||
28 76 : (instr->IsInteger32Constant() && instr->GetInteger32Constant() >= 0);
29 : }
30 :
31 :
32 : bool HUint32AnalysisPhase::IsSafeUint32Use(HValue* val, HValue* use) {
33 : // Operations that operate on bits are safe.
34 6769 : if (use->IsBitwise() || use->IsShl() || use->IsSar() || use->IsShr()) {
35 : return true;
36 5583 : } else if (use->IsSimulate() || use->IsArgumentsObject()) {
37 : // Deoptimization has special support for uint32.
38 : return true;
39 3785 : } else if (use->IsChange()) {
40 : // Conversions have special support for uint32.
41 : // This DCHECK guards that the conversion in question is actually
42 : // implemented. Do not extend the whitelist without adding
43 : // support to LChunkBuilder::DoChange().
44 : DCHECK(HChange::cast(use)->to().IsDouble() ||
45 : HChange::cast(use)->to().IsSmi() ||
46 : HChange::cast(use)->to().IsTagged());
47 : return true;
48 416 : } else if (use->IsStoreKeyed()) {
49 13 : HStoreKeyed* store = HStoreKeyed::cast(use);
50 13 : if (store->is_fixed_typed_array()) {
51 : // Storing a value into an external integer array is a bit level
52 : // operation.
53 6 : if (store->value() == val) {
54 : // Clamping or a conversion to double should have beed inserted.
55 : DCHECK(store->elements_kind() != UINT8_CLAMPED_ELEMENTS);
56 : DCHECK(store->elements_kind() != FLOAT32_ELEMENTS);
57 : DCHECK(store->elements_kind() != FLOAT64_ELEMENTS);
58 : return true;
59 : }
60 : }
61 403 : } else if (use->IsCompareNumericAndBranch()) {
62 38 : HCompareNumericAndBranch* c = HCompareNumericAndBranch::cast(use);
63 38 : return IsUint32Operation(c->left()) && IsUint32Operation(c->right());
64 : }
65 :
66 : return false;
67 : }
68 :
69 :
70 : // Iterate over all uses and verify that they are uint32 safe: either don't
71 : // distinguish between int32 and uint32 due to their bitwise nature or
72 : // have special support for uint32 values.
73 : // Encountered phis are optimistically treated as safe uint32 uses,
74 : // marked with kUint32 flag and collected in the phis_ list. A separate
75 : // pass will be performed later by UnmarkUnsafePhis to clear kUint32 from
76 : // phis that are not actually uint32-safe (it requires fix point iteration).
77 3875 : bool HUint32AnalysisPhase::Uint32UsesAreSafe(HValue* uint32val) {
78 : bool collect_phi_uses = false;
79 10406 : for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
80 7343 : HValue* use = it.value();
81 :
82 7056 : if (use->IsPhi()) {
83 287 : if (!use->CheckFlag(HInstruction::kUint32)) {
84 : // There is a phi use of this value from a phi that is not yet
85 : // collected in phis_ array. Separate pass is required.
86 : collect_phi_uses = true;
87 : }
88 :
89 : // Optimistically treat phis as uint32 safe.
90 : continue;
91 : }
92 :
93 6769 : if (!IsSafeUint32Use(uint32val, use)) {
94 372 : return false;
95 : }
96 : }
97 :
98 3350 : if (collect_phi_uses) {
99 543 : for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
100 543 : HValue* use = it.value();
101 :
102 : // There is a phi use of this value from a phi that is not yet
103 : // collected in phis_ array. Separate pass is required.
104 543 : if (use->IsPhi() && !use->CheckFlag(HInstruction::kUint32)) {
105 153 : use->SetFlag(HInstruction::kUint32);
106 153 : phis_.Add(HPhi::cast(use), zone());
107 : }
108 : }
109 : }
110 :
111 : return true;
112 : }
113 :
114 :
115 : // Check if all operands to the given phi are marked with kUint32 flag.
116 : bool HUint32AnalysisPhase::CheckPhiOperands(HPhi* phi) {
117 153 : if (!phi->CheckFlag(HInstruction::kUint32)) {
118 : // This phi is not uint32 safe. No need to check operands.
119 : return false;
120 : }
121 :
122 295 : for (int j = 0; j < phi->OperandCount(); j++) {
123 302 : HValue* operand = phi->OperandAt(j);
124 302 : if (!operand->CheckFlag(HInstruction::kUint32)) {
125 : // Lazily mark constants that fit into uint32 range with kUint32 flag.
126 23 : if (operand->IsInteger32Constant() &&
127 8 : operand->GetInteger32Constant() >= 0) {
128 8 : operand->SetFlag(HInstruction::kUint32);
129 : continue;
130 : }
131 :
132 : // This phi is not safe, some operands are not uint32 values.
133 : return false;
134 : }
135 : }
136 :
137 : return true;
138 : }
139 :
140 :
141 : // Remove kUint32 flag from the phi itself and its operands. If any operand
142 : // was a phi marked with kUint32 place it into a worklist for
143 : // transitive clearing of kUint32 flag.
144 : void HUint32AnalysisPhase::UnmarkPhi(HPhi* phi, ZoneList<HPhi*>* worklist) {
145 13 : phi->ClearFlag(HInstruction::kUint32);
146 26 : for (int j = 0; j < phi->OperandCount(); j++) {
147 26 : HValue* operand = phi->OperandAt(j);
148 26 : if (operand->CheckFlag(HInstruction::kUint32)) {
149 13 : operand->ClearFlag(HInstruction::kUint32);
150 13 : if (operand->IsPhi()) {
151 2 : worklist->Add(HPhi::cast(operand), zone());
152 : }
153 : }
154 : }
155 : }
156 :
157 :
158 : void HUint32AnalysisPhase::UnmarkUnsafePhis() {
159 : // No phis were collected. Nothing to do.
160 2784 : if (phis_.length() == 0) return;
161 :
162 : // Worklist used to transitively clear kUint32 from phis that
163 : // are used as arguments to other phis.
164 38 : ZoneList<HPhi*> worklist(phis_.length(), zone());
165 :
166 : // Phi can be used as a uint32 value if and only if
167 : // all its operands are uint32 values and all its
168 : // uses are uint32 safe.
169 :
170 : // Iterate over collected phis and unmark those that
171 : // are unsafe. When unmarking phi unmark its operands
172 : // and add it to the worklist if it is a phi as well.
173 : // Phis that are still marked as safe are shifted down
174 : // so that all safe phis form a prefix of the phis_ array.
175 : int phi_count = 0;
176 344 : for (int i = 0; i < phis_.length(); i++) {
177 153 : HPhi* phi = phis_[i];
178 :
179 297 : if (CheckPhiOperands(phi) && Uint32UsesAreSafe(phi)) {
180 284 : phis_[phi_count++] = phi;
181 : } else {
182 : UnmarkPhi(phi, &worklist);
183 : }
184 : }
185 :
186 : // Now phis array contains only those phis that have safe
187 : // non-phi uses. Start transitively clearing kUint32 flag
188 : // from phi operands of discovered non-safe phis until
189 : // only safe phis are left.
190 40 : while (!worklist.is_empty()) {
191 4 : while (!worklist.is_empty()) {
192 : HPhi* phi = worklist.RemoveLast();
193 : UnmarkPhi(phi, &worklist);
194 : }
195 :
196 : // Check if any operands to safe phis were unmarked
197 : // turning a safe phi into unsafe. The same value
198 : // can flow into several phis.
199 : int new_phi_count = 0;
200 0 : for (int i = 0; i < phi_count; i++) {
201 0 : HPhi* phi = phis_[i];
202 :
203 0 : if (CheckPhiOperands(phi)) {
204 0 : phis_[new_phi_count++] = phi;
205 : } else {
206 : UnmarkPhi(phi, &worklist);
207 : }
208 : }
209 : phi_count = new_phi_count;
210 : }
211 : }
212 :
213 :
214 283729 : void HUint32AnalysisPhase::Run() {
215 567458 : if (!graph()->has_uint32_instructions()) return;
216 :
217 : ZoneList<HInstruction*>* uint32_instructions = graph()->uint32_instructions();
218 8516 : for (int i = 0; i < uint32_instructions->length(); ++i) {
219 : // Analyze instruction and mark it with kUint32 if all
220 : // its uses are uint32 safe.
221 8516 : HInstruction* current = uint32_instructions->at(i);
222 7348 : if (current->IsLinked() &&
223 7252 : current->representation().IsInteger32() &&
224 : Uint32UsesAreSafe(current)) {
225 : current->SetFlag(HInstruction::kUint32);
226 : }
227 : }
228 :
229 : // Some phis might have been optimistically marked with kUint32 flag.
230 : // Remove this flag from those phis that are unsafe and propagate
231 : // this information transitively potentially clearing kUint32 flag
232 : // from some non-phi operations that are used as operands to unsafe phis.
233 : UnmarkUnsafePhis();
234 : }
235 :
236 :
237 : } // namespace internal
238 : } // namespace v8
|
