diff options
Diffstat (limited to 'deps/v8/src/effects.h')
-rw-r--r-- | deps/v8/src/effects.h | 335 |
1 files changed, 0 insertions, 335 deletions
diff --git a/deps/v8/src/effects.h b/deps/v8/src/effects.h deleted file mode 100644 index f8b1bd9b2f..0000000000 --- a/deps/v8/src/effects.h +++ /dev/null @@ -1,335 +0,0 @@ -// Copyright 2013 the V8 project authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#ifndef V8_EFFECTS_H_ -#define V8_EFFECTS_H_ - -#include "src/ast/ast-types.h" - -namespace v8 { -namespace internal { - - -// A simple struct to represent (write) effects. A write is represented as a -// modification of type bounds (e.g. of a variable). -// -// An effect can either be definite, if the write is known to have taken place, -// or 'possible', if it was optional. The difference is relevant when composing -// effects. -// -// There are two ways to compose effects: sequentially (they happen one after -// the other) or alternatively (either one or the other happens). A definite -// effect cancels out any previous effect upon sequencing. A possible effect -// merges into a previous effect, i.e., type bounds are merged. Alternative -// composition always merges bounds. It yields a possible effect if at least -// one was only possible. -struct Effect { - enum Modality { POSSIBLE, DEFINITE }; - - Modality modality; - AstBounds bounds; - - Effect() : modality(DEFINITE) {} - explicit Effect(AstBounds b, Modality m = DEFINITE) - : modality(m), bounds(b) {} - - // The unknown effect. - static Effect Unknown(Zone* zone) { - return Effect(AstBounds::Unbounded(), POSSIBLE); - } - - static Effect Forget(Zone* zone) { - return Effect(AstBounds::Unbounded(), DEFINITE); - } - - // Sequential composition, as in 'e1; e2'. - static Effect Seq(Effect e1, Effect e2, Zone* zone) { - if (e2.modality == DEFINITE) return e2; - return Effect(AstBounds::Either(e1.bounds, e2.bounds, zone), e1.modality); - } - - // Alternative composition, as in 'cond ? e1 : e2'. - static Effect Alt(Effect e1, Effect e2, Zone* zone) { - return Effect(AstBounds::Either(e1.bounds, e2.bounds, zone), - e1.modality == POSSIBLE ? POSSIBLE : e2.modality); - } -}; - - -// Classes encapsulating sets of effects on variables. -// -// Effects maps variables to effects and supports sequential and alternative -// composition. -// -// NestedEffects is an incremental representation that supports persistence -// through functional extension. It represents the map as an adjoin of a list -// of maps, whose tail can be shared. -// -// Both classes provide similar interfaces, implemented in parts through the -// EffectsMixin below (using sandwich style, to work around the style guide's -// MI restriction). -// -// We also (ab)use Effects/NestedEffects as a representation for abstract -// store typings. In that case, only definite effects are of interest. - -template<class Var, class Base, class Effects> -class EffectsMixin: public Base { - public: - explicit EffectsMixin(Zone* zone) : Base(zone) {} - - Effect Lookup(Var var) { - Locator locator; - return this->Find(var, &locator) - ? locator.value() : Effect::Unknown(Base::zone()); - } - - AstBounds LookupBounds(Var var) { - Effect effect = Lookup(var); - return effect.modality == Effect::DEFINITE ? effect.bounds - : AstBounds::Unbounded(); - } - - // Sequential composition. - void Seq(Var var, Effect effect) { - Locator locator; - if (!this->Insert(var, &locator)) { - effect = Effect::Seq(locator.value(), effect, Base::zone()); - } - locator.set_value(effect); - } - - void Seq(Effects that) { - SeqMerger<EffectsMixin> merge = { *this }; - that.ForEach(&merge); - } - - // Alternative composition. - void Alt(Var var, Effect effect) { - Locator locator; - if (!this->Insert(var, &locator)) { - effect = Effect::Alt(locator.value(), effect, Base::zone()); - } - locator.set_value(effect); - } - - void Alt(Effects that) { - AltWeakener<EffectsMixin> weaken = { *this, that }; - this->ForEach(&weaken); - AltMerger<EffectsMixin> merge = { *this }; - that.ForEach(&merge); - } - - // Invalidation. - void Forget() { - Overrider override = { - Effect::Forget(Base::zone()), Effects(Base::zone()) }; - this->ForEach(&override); - Seq(override.effects); - } - - protected: - typedef typename Base::Locator Locator; - - template<class Self> - struct SeqMerger { - void Call(Var var, Effect effect) { self.Seq(var, effect); } - Self self; - }; - - template<class Self> - struct AltMerger { - void Call(Var var, Effect effect) { self.Alt(var, effect); } - Self self; - }; - - template<class Self> - struct AltWeakener { - void Call(Var var, Effect effect) { - if (effect.modality == Effect::DEFINITE && !other.Contains(var)) { - effect.modality = Effect::POSSIBLE; - Locator locator; - self.Insert(var, &locator); - locator.set_value(effect); - } - } - Self self; - Effects other; - }; - - struct Overrider { - void Call(Var var, Effect effect) { effects.Seq(var, new_effect); } - Effect new_effect; - Effects effects; - }; -}; - - -template<class Var, Var kNoVar> class Effects; -template<class Var, Var kNoVar> class NestedEffectsBase; - -template<class Var, Var kNoVar> -class EffectsBase { - public: - explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {} - - bool IsEmpty() { return map_->is_empty(); } - - protected: - friend class NestedEffectsBase<Var, kNoVar>; - friend class - EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >; - - Zone* zone() { return map_->allocator().zone(); } - - struct SplayTreeConfig { - typedef Var Key; - typedef Effect Value; - static const Var kNoKey = kNoVar; - static Effect NoValue() { return Effect(); } - static int Compare(int x, int y) { return y - x; } - }; - typedef ZoneSplayTree<SplayTreeConfig> Mapping; - typedef typename Mapping::Locator Locator; - - bool Contains(Var var) { - DCHECK(var != kNoVar); - return map_->Contains(var); - } - bool Find(Var var, Locator* locator) { - DCHECK(var != kNoVar); - return map_->Find(var, locator); - } - bool Insert(Var var, Locator* locator) { - DCHECK(var != kNoVar); - return map_->Insert(var, locator); - } - - template<class Callback> - void ForEach(Callback* callback) { - return map_->ForEach(callback); - } - - private: - Mapping* map_; -}; - -template<class Var, Var kNoVar> -const Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey; - -template<class Var, Var kNoVar> -class Effects: public - EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { - public: - explicit Effects(Zone* zone) - : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone) - {} -}; - - -template<class Var, Var kNoVar> -class NestedEffectsBase { - public: - explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {} - - template<class Callback> - void ForEach(Callback* callback) { - if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback); - node_->effects.ForEach(callback); - } - - Effects<Var, kNoVar> Top() { return node_->effects; } - - bool IsEmpty() { - for (Node* node = node_; node != NULL; node = node->previous) { - if (!node->effects.IsEmpty()) return false; - } - return true; - } - - protected: - typedef typename EffectsBase<Var, kNoVar>::Locator Locator; - - Zone* zone() { return node_->zone; } - - void push() { node_ = new(node_->zone) Node(node_->zone, node_); } - void pop() { node_ = node_->previous; } - bool is_empty() { return node_ == NULL; } - - bool Contains(Var var) { - DCHECK(var != kNoVar); - for (Node* node = node_; node != NULL; node = node->previous) { - if (node->effects.Contains(var)) return true; - } - return false; - } - - bool Find(Var var, Locator* locator) { - DCHECK(var != kNoVar); - for (Node* node = node_; node != NULL; node = node->previous) { - if (node->effects.Find(var, locator)) return true; - } - return false; - } - - bool Insert(Var var, Locator* locator); - - private: - struct Node: ZoneObject { - Zone* zone; - Effects<Var, kNoVar> effects; - Node* previous; - explicit Node(Zone* zone, Node* previous = NULL) - : zone(zone), effects(zone), previous(previous) {} - }; - - explicit NestedEffectsBase(Node* node) : node_(node) {} - - Node* node_; -}; - - -template<class Var, Var kNoVar> -bool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) { - DCHECK(var != kNoVar); - if (!node_->effects.Insert(var, locator)) return false; - Locator shadowed; - for (Node* node = node_->previous; node != NULL; node = node->previous) { - if (node->effects.Find(var, &shadowed)) { - // Initialize with shadowed entry. - locator->set_value(shadowed.value()); - return false; - } - } - return true; -} - - -template<class Var, Var kNoVar> -class NestedEffects: public - EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > { - public: - explicit NestedEffects(Zone* zone) : - EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >( - zone) {} - - // Create an extension of the current effect set. The current set should not - // be modified while the extension is in use. - NestedEffects Push() { - NestedEffects result = *this; - result.push(); - return result; - } - - NestedEffects Pop() { - NestedEffects result = *this; - result.pop(); - DCHECK(!this->is_empty()); - return result; - } -}; - -} // namespace internal -} // namespace v8 - -#endif // V8_EFFECTS_H_ |