LCOV - code coverage report
Current view: top level - src/crankshaft - hydrogen-uint32-analysis.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 55 59 93.2 %
Date: 2017-04-26 Functions: 2 2 100.0 %

          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

Generated by: LCOV version 1.10