src/v8/src/hydrogen-store-elimination.cc

   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-store-elimination.h"
  29 #include "hydrogen-instructions.h"
  30
  31 namespace v8 {
  32 namespace internal {
  33
  34 #define TRACE(x) if (FLAG_trace_store_elimination) PrintF x
  35
  36 // Performs a block-by-block local analysis for removable stores.
  37 void HStoreEliminationPhase::Run() {
  38   GVNFlagSet flags;  // Use GVN flags as an approximation for some instructions.
  39   flags.RemoveAll();
  40
  41   flags.Add(kArrayElements);
  42   flags.Add(kArrayLengths);
  43   flags.Add(kStringLengths);
  44   flags.Add(kBackingStoreFields);
  45   flags.Add(kDoubleArrayElements);
  46   flags.Add(kDoubleFields);
  47   flags.Add(kElementsPointer);
  48   flags.Add(kInobjectFields);
  49   flags.Add(kExternalMemory);
  50   flags.Add(kStringChars);
  51   flags.Add(kTypedArrayElements);
  52
  53   for (int i = 0; i < graph()->blocks()->length(); i++) {
  54     unobserved_.Rewind(0);
  55     HBasicBlock* block = graph()->blocks()->at(i);
  56     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
  57       HInstruction* instr = it.Current();
  58
  59       // TODO(titzer): eliminate unobserved HStoreKeyed instructions too.
  60       switch (instr->opcode()) {
  61         case HValue::kStoreNamedField:
  62           // Remove any unobserved stores overwritten by this store.
  63           ProcessStore(HStoreNamedField::cast(instr));
  64           break;
  65         case HValue::kLoadNamedField:
  66           // Observe any unobserved stores on this object + field.
  67           ProcessLoad(HLoadNamedField::cast(instr));
  68           break;
  69         default:
  70           ProcessInstr(instr, flags);
  71           break;
  72       }
  73     }
  74   }
  75 }
  76
  77
  78 void HStoreEliminationPhase::ProcessStore(HStoreNamedField* store) {
  79   HValue* object = store->object()->ActualValue();
  80   int i = 0;
  81   while (i < unobserved_.length()) {
  82     HStoreNamedField* prev = unobserved_.at(i);
  83     if (aliasing_->MustAlias(object, prev->object()->ActualValue()) &&
  84         store->access().Equals(prev->access())) {
  85       // This store is guaranteed to overwrite the previous store.
  86       prev->DeleteAndReplaceWith(NULL);
  87       TRACE(("++ Unobserved store S%d overwritten by S%d\n",
  88              prev->id(), store->id()));
  89       unobserved_.Remove(i);
  90     } else {
  91       // TODO(titzer): remove map word clearing from folded allocations.
  92       i++;
  93     }
  94   }
  95   // Only non-transitioning stores are removable.
  96   if (!store->has_transition()) {
  97     TRACE(("-- Might remove store S%d\n", store->id()));
  98     unobserved_.Add(store, zone());
  99   }
 100 }
 101
 102
 103 void HStoreEliminationPhase::ProcessLoad(HLoadNamedField* load) {
 104   HValue* object = load->object()->ActualValue();
 105   int i = 0;
 106   while (i < unobserved_.length()) {
 107     HStoreNamedField* prev = unobserved_.at(i);
 108     if (aliasing_->MayAlias(object, prev->object()->ActualValue()) &&
 109         load->access().Equals(prev->access())) {
 110       TRACE(("-- Observed store S%d by load L%d\n", prev->id(), load->id()));
 111       unobserved_.Remove(i);
 112     } else {
 113       i++;
 114     }
 115   }
 116 }
 117
 118
 119 void HStoreEliminationPhase::ProcessInstr(HInstruction* instr,
 120     GVNFlagSet flags) {
 121   if (unobserved_.length() == 0) return;  // Nothing to do.
 122   if (instr->CanDeoptimize()) {
 123     TRACE(("-- Observed stores at I%d (might deoptimize)\n", instr->id()));
 124     unobserved_.Rewind(0);
 125     return;
 126   }
 127   if (instr->CheckChangesFlag(kNewSpacePromotion)) {
 128     TRACE(("-- Observed stores at I%d (might GC)\n", instr->id()));
 129     unobserved_.Rewind(0);
 130     return;
 131   }
 132   if (instr->ChangesFlags().ContainsAnyOf(flags)) {
 133     TRACE(("-- Observed stores at I%d (GVN flags)\n", instr->id()));
 134     unobserved_.Rewind(0);
 135     return;
 136   }
 137 }
 138
 139 } }  // namespace v8::internal