Home | History | Annotate | Download | only in src 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #include "hydrogen-uint32-analysis.h"
     29 
     30 namespace v8 {
     31 namespace internal {
     32 
     33 
     34 bool HUint32AnalysisPhase::IsSafeUint32Use(HValue* val, HValue* use) {
     35   // Operations that operate on bits are safe.
     36   if (use->IsBitwise() || use->IsShl() || use->IsSar() || use->IsShr()) {
     37     return true;
     38   } else if (use->IsSimulate()) {
     39     // Deoptimization has special support for uint32.
     40     return true;
     41   } else if (use->IsChange()) {
     42     // Conversions have special support for uint32.
     43     // This ASSERT guards that the conversion in question is actually
     44     // implemented. Do not extend the whitelist without adding
     45     // support to LChunkBuilder::DoChange().
     46     ASSERT(HChange::cast(use)->to().IsDouble() ||
     47            HChange::cast(use)->to().IsSmi() ||
     48            HChange::cast(use)->to().IsTagged());
     49     return true;
     50   } else if (use->IsStoreKeyed()) {
     51     HStoreKeyed* store = HStoreKeyed::cast(use);
     52     if (store->is_external()) {
     53       // Storing a value into an external integer array is a bit level
     54       // operation.
     55       if (store->value() == val) {
     56         // Clamping or a conversion to double should have beed inserted.
     57         ASSERT(store->elements_kind() != EXTERNAL_PIXEL_ELEMENTS);
     58         ASSERT(store->elements_kind() != EXTERNAL_FLOAT_ELEMENTS);
     59         ASSERT(store->elements_kind() != EXTERNAL_DOUBLE_ELEMENTS);
     60         return true;
     61       }
     62     }
     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 v8::internal
    237