Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(736)

Unified Diff: src/effects.h

Issue 19054006: Implement simple effect typing for variables (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Comments Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/ast.h ('k') | src/splay-tree.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/effects.h
diff --git a/src/effects.h b/src/effects.h
new file mode 100644
index 0000000000000000000000000000000000000000..ec526aebf1cf6695f7edca13ad00a9bd39c2f0f0
--- /dev/null
+++ b/src/effects.h
@@ -0,0 +1,361 @@
+// Copyright 2013 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_EFFECTS_H_
+#define V8_EFFECTS_H_
+
+#include "v8.h"
+
+#include "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;
+ Bounds bounds;
+
+ Effect() {}
+ Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {}
+
+ // The unknown effect.
+ static Effect Unknown(Isolate* isolate) {
+ return Effect(Bounds::Unbounded(isolate), POSSIBLE);
+ }
+
+ static Effect Forget(Isolate* isolate) {
+ return Effect(Bounds::Unbounded(isolate), DEFINITE);
+ }
+
+ // Sequential composition, as in 'e1; e2'.
+ static Effect Seq(Effect e1, Effect e2, Isolate* isolate) {
+ if (e2.modality == DEFINITE) return e2;
+ return Effect(Bounds::Either(e1.bounds, e2.bounds, isolate), e1.modality);
+ }
+
+ // Alternative composition, as in 'cond ? e1 : e2'.
+ static Effect Alt(Effect e1, Effect e2, Isolate* isolate) {
+ return Effect(
+ Bounds::Either(e1.bounds, e2.bounds, isolate),
+ 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 Find(var, &locator)
+ ? locator.value() : Effect::Unknown(Base::isolate());
+ }
+
+ Bounds LookupBounds(Var var) {
+ Effect effect = Lookup(var);
+ return effect.modality == Effect::DEFINITE
+ ? effect.bounds : Bounds::Unbounded(Base::isolate());
+ }
+
+ // Sequential composition.
+ void Seq(Var var, Effect effect) {
+ Locator locator;
+ if (!Insert(var, &locator)) {
+ effect = Effect::Seq(locator.value(), effect, Base::isolate());
+ }
+ 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 (!Insert(var, &locator)) {
+ effect = Effect::Alt(locator.value(), effect, Base::isolate());
+ }
+ 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::isolate()), 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(); }
+ Isolate* isolate() { return zone()->isolate(); }
+
+ 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) {
+ ASSERT(var != kNoVar);
+ return map_->Contains(var);
+ }
+ bool Find(Var var, Locator* locator) {
+ ASSERT(var != kNoVar);
+ return map_->Find(var, locator);
+ }
+ bool Insert(Var var, Locator* locator) {
+ ASSERT(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; }
+ Isolate* isolate() { return zone()->isolate(); }
+
+ 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) {
+ ASSERT(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) {
+ ASSERT(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) {
+ ASSERT(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();
+ ASSERT(!this->is_empty());
+ return result;
+ }
+};
+
+} } // namespace v8::internal
+
+#endif // V8_EFFECTS_H_
« no previous file with comments | « src/ast.h ('k') | src/splay-tree.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698