Home | History | Annotate | Download | only in crankshaft 
      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 static bool IsUint32Operation(HValue* instr) {
     26   return instr->IsShr() ||
     27       (instr->IsLoadKeyed() && IsUnsignedLoad(HLoadKeyed::cast(instr))) ||
     28       (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   if (use->IsBitwise() || use->IsShl() || use->IsSar() || use->IsShr()) {
     35     return true;
     36   } else if (use->IsSimulate() || use->IsArgumentsObject()) {
     37     // Deoptimization has special support for uint32.
     38     return true;
     39   } 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   } else if (use->IsStoreKeyed()) {
     49     HStoreKeyed* store = HStoreKeyed::cast(use);
     50     if (store->is_fixed_typed_array()) {
     51       // Storing a value into an external integer array is a bit level
     52       // operation.
     53       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   } else if (use->IsCompareNumericAndBranch()) {
     62     HCompareNumericAndBranch* c = HCompareNumericAndBranch::cast(use);
     63     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 bool HUint32AnalysisPhase::Uint32UsesAreSafe(HValue* uint32val) {
     78   bool collect_phi_uses = false;
     79   for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
     80     HValue* use = it.value();
     81 
     82     if (use->IsPhi()) {
     83       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     if (!IsSafeUint32Use(uint32val, use)) {
     94       return false;
     95     }
     96   }
     97 
     98   if (collect_phi_uses) {
     99     for (HUseIterator it(uint32val->uses()); !it.Done(); it.Advance()) {
    100       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       if (use->IsPhi() && !use->CheckFlag(HInstruction::kUint32)) {
    105         use->SetFlag(HInstruction::kUint32);
    106         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   if (!phi->CheckFlag(HInstruction::kUint32)) {
    118     // This phi is not uint32 safe. No need to check operands.
    119     return false;
    120   }
    121 
    122   for (int j = 0; j < phi->OperandCount(); j++) {
    123     HValue* operand = phi->OperandAt(j);
    124     if (!operand->CheckFlag(HInstruction::kUint32)) {
    125       // Lazily mark constants that fit into uint32 range with kUint32 flag.
    126       if (operand->IsInteger32Constant() &&
    127           operand->GetInteger32Constant() >= 0) {
    128         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   phi->ClearFlag(HInstruction::kUint32);
    146   for (int j = 0; j < phi->OperandCount(); j++) {
    147     HValue* operand = phi->OperandAt(j);
    148     if (operand->CheckFlag(HInstruction::kUint32)) {
    149       operand->ClearFlag(HInstruction::kUint32);
    150       if (operand->IsPhi()) {
    151         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   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   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   for (int i = 0; i < phis_.length(); i++) {
    177     HPhi* phi = phis_[i];
    178 
    179     if (CheckPhiOperands(phi) && Uint32UsesAreSafe(phi)) {
    180       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   while (!worklist.is_empty())  {
    191     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     for (int i = 0; i < phi_count; i++) {
    201       HPhi* phi = phis_[i];
    202 
    203       if (CheckPhiOperands(phi)) {
    204         phis_[new_phi_count++] = phi;
    205       } else {
    206         UnmarkPhi(phi, &worklist);
    207       }
    208     }
    209     phi_count = new_phi_count;
    210   }
    211 }
    212 
    213 
    214 void HUint32AnalysisPhase::Run() {
    215   if (!graph()->has_uint32_instructions()) return;
    216 
    217   ZoneList<HInstruction*>* uint32_instructions = graph()->uint32_instructions();
    218   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     HInstruction* current = uint32_instructions->at(i);
    222     if (current->IsLinked() &&
    223         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
    239