src/hydrogen-uint32-analysis.cc

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