dart::StoreOptimizer Class Reference

Inheritance diagram for dart::StoreOptimizer:

Public Member Functions
	StoreOptimizer (FlowGraph *graph, AliasedSet *aliased_set, PointerSet< Place > *map)
Public Member Functions inherited from dart::LivenessAnalysis
	LivenessAnalysis (intptr_t variable_count, const GrowableArray< BlockEntryInstr * > &postorder)
void	Analyze ()
virtual	~LivenessAnalysis ()
BitVector *	GetLiveInSetAt (intptr_t postorder_number) const
BitVector *	GetLiveOutSetAt (intptr_t postorder_number) const
BitVector *	GetLiveInSet (BlockEntryInstr *block) const
BitVector *	GetKillSet (BlockEntryInstr *block) const
BitVector *	GetLiveOutSet (BlockEntryInstr *block) const
void	Dump ()
Public Member Functions inherited from dart::ValueObject
	ValueObject ()
	~ValueObject ()

Static Public Member Functions
static void	OptimizeGraph (FlowGraph *graph)

Private Member Functions
virtual void	ComputeInitialSets ()

Additional Inherited Members
Protected Member Functions inherited from dart::LivenessAnalysis
virtual void	ComputeInitialSets ()=0
bool	UpdateLiveOut (const BlockEntryInstr &instr)
bool	UpdateLiveIn (const BlockEntryInstr &instr)
void	ComputeLiveInAndLiveOutSets ()
Zone *	zone () const
Protected Attributes inherited from dart::LivenessAnalysis
Zone *	zone_
const intptr_t	variable_count_
const GrowableArray< BlockEntryInstr * > &	postorder_
GrowableArray< BitVector * >	live_out_
GrowableArray< BitVector * >	kill_
GrowableArray< BitVector * >	live_in_

Detailed Description

Definition at line 3012 of file redundancy_elimination.cc.

Constructor & Destructor Documentation

StoreOptimizer()

dart::StoreOptimizer::StoreOptimizer ( FlowGraph *  graph, AliasedSet *  aliased_set, PointerSet< Place > *  map  )

inline

Definition at line 3014 of file redundancy_elimination.cc.

      : LivenessAnalysis(aliased_set->max_place_id(), graph->postorder()),
        graph_(graph),
        map_(map),
        aliased_set_(aliased_set),
        exposed_stores_(graph_->postorder().length()) {
    const intptr_t num_blocks = graph_->postorder().length();
    for (intptr_t i = 0; i < num_blocks; i++) {
      exposed_stores_.Add(nullptr);
    }
  }

Member Function Documentation

ComputeInitialSets()

virtual void dart::StoreOptimizer::ComputeInitialSets ( )

inlineprivatevirtual

Implements dart::LivenessAnalysis.

Definition at line 3077 of file redundancy_elimination.cc.

                                    {
    Zone* zone = graph_->zone();
    BitVector* all_places =
        new (zone) BitVector(zone, aliased_set_->max_place_id());
    all_places->SetAll();
 
    BitVector* all_aliased_places = nullptr;
    if (CompilerState::Current().is_aot()) {
      all_aliased_places =
          new (zone) BitVector(zone, aliased_set_->max_place_id());
    }
    const auto& places = aliased_set_->places();
    for (intptr_t i = 0; i < places.length(); i++) {
      Place* place = places[i];
      if (place->DependsOnInstance()) {
        Definition* instance = place->instance();
        // Find escaping places by inspecting definition allocation
        // [AliasIdentity] field, which is populated above by
        // [AliasedSet::ComputeAliasing].
        if ((all_aliased_places != nullptr) &&
            (!Place::IsAllocation(instance) ||
             instance->Identity().IsAliased())) {
          all_aliased_places->Add(i);
        }
        if (instance != nullptr) {
          // Avoid incorrect propagation of "dead" state beyond definition
          // of the instance. Otherwise it may eventually reach stores into
          // this place via loop backedge.
          live_in_[instance->GetBlock()->postorder_number()]->Add(i);
        }
      } else {
        if (all_aliased_places != nullptr) {
          all_aliased_places->Add(i);
        }
      }
      if (place->kind() == Place::kIndexed) {
        Definition* index = place->index();
        if (index != nullptr) {
          // Avoid incorrect propagation of "dead" state beyond definition
          // of the index. Otherwise it may eventually reach stores into
          // this place via loop backedge.
          live_in_[index->GetBlock()->postorder_number()]->Add(i);
        }
      }
    }
 
    for (BlockIterator block_it = graph_->postorder_iterator();
         !block_it.Done(); block_it.Advance()) {
      BlockEntryInstr* block = block_it.Current();
      const intptr_t postorder_number = block->postorder_number();
 
      BitVector* kill = kill_[postorder_number];
      BitVector* live_in = live_in_[postorder_number];
      BitVector* live_out = live_out_[postorder_number];
 
      ZoneGrowableArray<Instruction*>* exposed_stores = nullptr;
 
      // Iterate backwards starting at the last instruction.
      for (BackwardInstructionIterator instr_it(block); !instr_it.Done();
           instr_it.Advance()) {
        Instruction* instr = instr_it.Current();
 
        bool is_load = false;
        bool is_store = false;
        Place place(instr, &is_load, &is_store);
        if (place.IsImmutableField()) {
          // Loads/stores of final fields do not participate.
          continue;
        }
 
        // Handle stores.
        if (is_store) {
          if (kill->Contains(GetPlaceId(instr))) {
            if (!live_in->Contains(GetPlaceId(instr)) &&
                CanEliminateStore(instr)) {
              if (FLAG_trace_optimization && graph_->should_print()) {
                THR_Print("Removing dead store to place %" Pd " in block B%" Pd
                          "\n",
                          GetPlaceId(instr), block->block_id());
              }
              instr_it.RemoveCurrentFromGraph();
            }
          } else if (!live_in->Contains(GetPlaceId(instr))) {
            // Mark this store as down-ward exposed: They are the only
            // candidates for the global store elimination.
            if (exposed_stores == nullptr) {
              const intptr_t kMaxExposedStoresInitialSize = 5;
              exposed_stores = new (zone) ZoneGrowableArray<Instruction*>(
                  Utils::Minimum(kMaxExposedStoresInitialSize,
                                 aliased_set_->max_place_id()));
            }
            exposed_stores->Add(instr);
          }
          // Interfering stores kill only loads from the same place.
          kill->Add(GetPlaceId(instr));
          live_in->Remove(GetPlaceId(instr));
          continue;
        }
 
        if (instr->IsThrow() || instr->IsReThrow() || instr->IsReturnBase()) {
          // Initialize live-out for exit blocks since it won't be computed
          // otherwise during the fixed point iteration.
          live_out->CopyFrom(all_places);
        }
 
        // Handle side effects, deoptimization and function return.
        if (CompilerState::Current().is_aot()) {
          if (instr->HasUnknownSideEffects() || instr->IsReturnBase()) {
            // An instruction that returns or has unknown side effects
            // is treated as if it loads from all places.
            live_in->CopyFrom(all_places);
            continue;
          } else if (instr->MayThrow()) {
            if (block->try_index() == kInvalidTryIndex) {
              // Outside of a try-catch block, an instruction that may throw
              // is only treated as if it loads from escaping places.
              live_in->AddAll(all_aliased_places);
            } else {
              // Inside of a try-catch block, an instruction that may throw
              // is treated as if it loads from all places.
              live_in->CopyFrom(all_places);
            }
            continue;
          }
        } else {  // jit
          // Similar optimization to the above could be implemented in JIT
          // as long as deoptimization side-effects are taken into account.
          // Conceptually variables in deoptimization environment for
          // "MayThrow" instructions have to be also added to the
          // [live_in] set as they can be considered as escaping (to
          // unoptimized code). However those deoptimization environment
          // variables include also non-escaping(not aliased) ones, so
          // how to deal with that needs to be figured out.
          if (instr->HasUnknownSideEffects() || instr->CanDeoptimize() ||
              instr->MayThrow() || instr->IsReturnBase()) {
            // Instructions that return from the function, instructions with
            // side effects and instructions that can deoptimize are considered
            // as loads from all places.
            live_in->CopyFrom(all_places);
            continue;
          }
        }
 
        // Handle loads.
        Definition* defn = instr->AsDefinition();
        if ((defn != nullptr) && IsLoadEliminationCandidate(defn)) {
          const intptr_t alias = aliased_set_->LookupAliasId(place.ToAlias());
          live_in->AddAll(aliased_set_->GetKilledSet(alias));
          continue;
        }
      }
      exposed_stores_[postorder_number] = exposed_stores;
    }
    if (FLAG_trace_load_optimization && graph_->should_print()) {
      Dump();
      THR_Print("---\n");
    }
  }

OptimizeGraph()

static void dart::StoreOptimizer::OptimizeGraph ( FlowGraph *  graph )

inlinestatic

Definition at line 3028 of file redundancy_elimination.cc.

                                              {
    ASSERT(FLAG_load_cse);
 
    // For now, bail out for large functions to avoid OOM situations.
    // TODO(fschneider): Fix the memory consumption issue.
    if (graph->is_huge_method()) {
      return;
    }
 
    PointerSet<Place> map;
    AliasedSet* aliased_set = NumberPlaces(graph, &map, kOptimizeStores);
    if ((aliased_set != nullptr) && !aliased_set->IsEmpty()) {
      StoreOptimizer store_optimizer(graph, aliased_set, &map);
      store_optimizer.Optimize();
    }
  }

---

The documentation for this class was generated from the following file:

• third_party/dart-lang/sdk/runtime/vm/compiler/backend/redundancy_elimination.cc