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