hydrogen-uint32-analysis.cc 7.62 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/hydrogen-uint32-analysis.h"
6 7 8 9 10

namespace v8 {
namespace internal {


11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
static bool IsUnsignedLoad(HLoadKeyed* instr) {
  switch (instr->elements_kind()) {
    case UINT8_ELEMENTS:
    case UINT16_ELEMENTS:
    case UINT32_ELEMENTS:
    case UINT8_CLAMPED_ELEMENTS:
      return true;
    default:
      return false;
  }
}


static bool IsUint32Operation(HValue* instr) {
  return instr->IsShr() ||
      (instr->IsLoadKeyed() && IsUnsignedLoad(HLoadKeyed::cast(instr))) ||
      (instr->IsInteger32Constant() && instr->GetInteger32Constant() >= 0);
}


31 32
bool HUint32AnalysisPhase::IsSafeUint32Use(HValue* val, HValue* use) {
  // Operations that operate on bits are safe.
33
  if (use->IsBitwise() || use->IsShl() || use->IsSar() || use->IsShr()) {
34
    return true;
35
  } else if (use->IsSimulate() || use->IsArgumentsObject()) {
36 37 38 39
    // Deoptimization has special support for uint32.
    return true;
  } else if (use->IsChange()) {
    // Conversions have special support for uint32.
40
    // This DCHECK guards that the conversion in question is actually
41 42
    // implemented. Do not extend the whitelist without adding
    // support to LChunkBuilder::DoChange().
43
    DCHECK(HChange::cast(use)->to().IsDouble() ||
44 45
           HChange::cast(use)->to().IsSmi() ||
           HChange::cast(use)->to().IsTagged());
46 47 48
    return true;
  } else if (use->IsStoreKeyed()) {
    HStoreKeyed* store = HStoreKeyed::cast(use);
49
    if (store->is_fixed_typed_array()) {
50 51 52 53
      // Storing a value into an external integer array is a bit level
      // operation.
      if (store->value() == val) {
        // Clamping or a conversion to double should have beed inserted.
54 55 56
        DCHECK(store->elements_kind() != UINT8_CLAMPED_ELEMENTS);
        DCHECK(store->elements_kind() != FLOAT32_ELEMENTS);
        DCHECK(store->elements_kind() != FLOAT64_ELEMENTS);
57 58 59
        return true;
      }
    }
60 61 62
  } else if (use->IsCompareNumericAndBranch()) {
    HCompareNumericAndBranch* c = HCompareNumericAndBranch::cast(use);
    return IsUint32Operation(c->left()) && IsUint32Operation(c->right());
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
  }

  return false;
}


// Iterate over all uses and verify that they are uint32 safe: either don't
// distinguish between int32 and uint32 due to their bitwise nature or
// have special support for uint32 values.
// Encountered phis are optimistically treated as safe uint32 uses,
// marked with kUint32 flag and collected in the phis_ list. A separate
// pass will be performed later by UnmarkUnsafePhis to clear kUint32 from
// phis that are not actually uint32-safe (it requires fix point iteration).
bool HUint32AnalysisPhase::Uint32UsesAreSafe(HValue* uint32val) {
  bool collect_phi_uses = false;
  for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
    HValue* use = it.value();

    if (use->IsPhi()) {
      if (!use->CheckFlag(HInstruction::kUint32)) {
        // There is a phi use of this value from a phi that is not yet
        // collected in phis_ array. Separate pass is required.
        collect_phi_uses = true;
      }

      // Optimistically treat phis as uint32 safe.
      continue;
    }

    if (!IsSafeUint32Use(uint32val, use)) {
      return false;
    }
  }

  if (collect_phi_uses) {
    for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
      HValue* use = it.value();

      // There is a phi use of this value from a phi that is not yet
      // collected in phis_ array. Separate pass is required.
      if (use->IsPhi() && !use->CheckFlag(HInstruction::kUint32)) {
        use->SetFlag(HInstruction::kUint32);
        phis_.Add(HPhi::cast(use), zone());
      }
    }
  }

  return true;
}


// Check if all operands to the given phi are marked with kUint32 flag.
bool HUint32AnalysisPhase::CheckPhiOperands(HPhi* phi) {
  if (!phi->CheckFlag(HInstruction::kUint32)) {
    // This phi is not uint32 safe. No need to check operands.
    return false;
  }

  for (int j = 0; j < phi->OperandCount(); j++) {
    HValue* operand = phi->OperandAt(j);
    if (!operand->CheckFlag(HInstruction::kUint32)) {
      // Lazily mark constants that fit into uint32 range with kUint32 flag.
      if (operand->IsInteger32Constant() &&
          operand->GetInteger32Constant() >= 0) {
        operand->SetFlag(HInstruction::kUint32);
        continue;
      }

      // This phi is not safe, some operands are not uint32 values.
      return false;
    }
  }

  return true;
}


// Remove kUint32 flag from the phi itself and its operands. If any operand
// was a phi marked with kUint32 place it into a worklist for
// transitive clearing of kUint32 flag.
void HUint32AnalysisPhase::UnmarkPhi(HPhi* phi, ZoneList<HPhi*>* worklist) {
  phi->ClearFlag(HInstruction::kUint32);
  for (int j = 0; j < phi->OperandCount(); j++) {
    HValue* operand = phi->OperandAt(j);
    if (operand->CheckFlag(HInstruction::kUint32)) {
      operand->ClearFlag(HInstruction::kUint32);
      if (operand->IsPhi()) {
        worklist->Add(HPhi::cast(operand), zone());
      }
    }
  }
}


void HUint32AnalysisPhase::UnmarkUnsafePhis() {
  // No phis were collected. Nothing to do.
  if (phis_.length() == 0) return;

  // Worklist used to transitively clear kUint32 from phis that
  // are used as arguments to other phis.
  ZoneList<HPhi*> worklist(phis_.length(), zone());

  // Phi can be used as a uint32 value if and only if
  // all its operands are uint32 values and all its
  // uses are uint32 safe.

  // Iterate over collected phis and unmark those that
  // are unsafe. When unmarking phi unmark its operands
  // and add it to the worklist if it is a phi as well.
  // Phis that are still marked as safe are shifted down
  // so that all safe phis form a prefix of the phis_ array.
  int phi_count = 0;
  for (int i = 0; i < phis_.length(); i++) {
    HPhi* phi = phis_[i];

    if (CheckPhiOperands(phi) && Uint32UsesAreSafe(phi)) {
      phis_[phi_count++] = phi;
    } else {
      UnmarkPhi(phi, &worklist);
    }
  }

  // Now phis array contains only those phis that have safe
  // non-phi uses. Start transitively clearing kUint32 flag
  // from phi operands of discovered non-safe phis until
  // only safe phis are left.
  while (!worklist.is_empty())  {
    while (!worklist.is_empty()) {
      HPhi* phi = worklist.RemoveLast();
      UnmarkPhi(phi, &worklist);
    }

    // Check if any operands to safe phis were unmarked
    // turning a safe phi into unsafe. The same value
    // can flow into several phis.
    int new_phi_count = 0;
    for (int i = 0; i < phi_count; i++) {
      HPhi* phi = phis_[i];

      if (CheckPhiOperands(phi)) {
        phis_[new_phi_count++] = phi;
      } else {
        UnmarkPhi(phi, &worklist);
      }
    }
    phi_count = new_phi_count;
  }
}


void HUint32AnalysisPhase::Run() {
  if (!graph()->has_uint32_instructions()) return;

  ZoneList<HInstruction*>* uint32_instructions = graph()->uint32_instructions();
  for (int i = 0; i < uint32_instructions->length(); ++i) {
    // Analyze instruction and mark it with kUint32 if all
    // its uses are uint32 safe.
    HInstruction* current = uint32_instructions->at(i);
221 222 223 224 225
    if (current->IsLinked() &&
        current->representation().IsInteger32() &&
        Uint32UsesAreSafe(current)) {
      current->SetFlag(HInstruction::kUint32);
    }
226 227 228 229 230 231 232 233 234 235
  }

  // Some phis might have been optimistically marked with kUint32 flag.
  // Remove this flag from those phis that are unsafe and propagate
  // this information transitively potentially clearing kUint32 flag
  // from some non-phi operations that are used as operands to unsafe phis.
  UnmarkUnsafePhis();
}


236 237
}  // namespace internal
}  // namespace v8