src/v8/src/effects.h

   1 // Copyright 2013 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef V8_EFFECTS_H_
   6 #define V8_EFFECTS_H_
   7
   8 #include "v8.h"
   9
  10 #include "types.h"
  11
  12 namespace v8 {
  13 namespace internal {
  14
  15
  16 // A simple struct to represent (write) effects. A write is represented as a
  17 // modification of type bounds (e.g. of a variable).
  18 //
  19 // An effect can either be definite, if the write is known to have taken place,
  20 // or 'possible', if it was optional. The difference is relevant when composing
  21 // effects.
  22 //
  23 // There are two ways to compose effects: sequentially (they happen one after
  24 // the other) or alternatively (either one or the other happens). A definite
  25 // effect cancels out any previous effect upon sequencing. A possible effect
  26 // merges into a previous effect, i.e., type bounds are merged. Alternative
  27 // composition always merges bounds. It yields a possible effect if at least
  28 // one was only possible.
  29 struct Effect {
  30   enum Modality { POSSIBLE, DEFINITE };
  31
  32   Modality modality;
  33   Bounds bounds;
  34
  35   Effect() : modality(DEFINITE) {}
  36   Effect(Bounds b, Modality m = DEFINITE) : modality(m), bounds(b) {}
  37
  38   // The unknown effect.
  39   static Effect Unknown(Zone* zone) {
  40     return Effect(Bounds::Unbounded(zone), POSSIBLE);
  41   }
  42
  43   static Effect Forget(Zone* zone) {
  44     return Effect(Bounds::Unbounded(zone), DEFINITE);
  45   }
  46
  47   // Sequential composition, as in 'e1; e2'.
  48   static Effect Seq(Effect e1, Effect e2, Zone* zone) {
  49     if (e2.modality == DEFINITE) return e2;
  50     return Effect(Bounds::Either(e1.bounds, e2.bounds, zone), e1.modality);
  51   }
  52
  53   // Alternative composition, as in 'cond ? e1 : e2'.
  54   static Effect Alt(Effect e1, Effect e2, Zone* zone) {
  55     return Effect(
  56         Bounds::Either(e1.bounds, e2.bounds, zone),
  57         e1.modality == POSSIBLE ? POSSIBLE : e2.modality);
  58   }
  59 };
  60
  61
  62 // Classes encapsulating sets of effects on variables.
  63 //
  64 // Effects maps variables to effects and supports sequential and alternative
  65 // composition.
  66 //
  67 // NestedEffects is an incremental representation that supports persistence
  68 // through functional extension. It represents the map as an adjoin of a list
  69 // of maps, whose tail can be shared.
  70 //
  71 // Both classes provide similar interfaces, implemented in parts through the
  72 // EffectsMixin below (using sandwich style, to work around the style guide's
  73 // MI restriction).
  74 //
  75 // We also (ab)use Effects/NestedEffects as a representation for abstract
  76 // store typings. In that case, only definite effects are of interest.
  77
  78 template<class Var, class Base, class Effects>
  79 class EffectsMixin: public Base {
  80  public:
  81   explicit EffectsMixin(Zone* zone) : Base(zone) {}
  82
  83   Effect Lookup(Var var) {
  84     Locator locator;
  85     return this->Find(var, &locator)
  86         ? locator.value() : Effect::Unknown(Base::zone());
  87   }
  88
  89   Bounds LookupBounds(Var var) {
  90     Effect effect = Lookup(var);
  91     return effect.modality == Effect::DEFINITE
  92         ? effect.bounds : Bounds::Unbounded(Base::zone());
  93   }
  94
  95   // Sequential composition.
  96   void Seq(Var var, Effect effect) {
  97     Locator locator;
  98     if (!this->Insert(var, &locator)) {
  99       effect = Effect::Seq(locator.value(), effect, Base::zone());
 100     }
 101     locator.set_value(effect);
 102   }
 103
 104   void Seq(Effects that) {
 105     SeqMerger<EffectsMixin> merge = { *this };
 106     that.ForEach(&merge);
 107   }
 108
 109   // Alternative composition.
 110   void Alt(Var var, Effect effect) {
 111     Locator locator;
 112     if (!this->Insert(var, &locator)) {
 113       effect = Effect::Alt(locator.value(), effect, Base::zone());
 114     }
 115     locator.set_value(effect);
 116   }
 117
 118   void Alt(Effects that) {
 119     AltWeakener<EffectsMixin> weaken = { *this, that };
 120     this->ForEach(&weaken);
 121     AltMerger<EffectsMixin> merge = { *this };
 122     that.ForEach(&merge);
 123   }
 124
 125   // Invalidation.
 126   void Forget() {
 127     Overrider override = {
 128         Effect::Forget(Base::zone()), Effects(Base::zone()) };
 129     this->ForEach(&override);
 130     Seq(override.effects);
 131   }
 132
 133  protected:
 134   typedef typename Base::Locator Locator;
 135
 136   template<class Self>
 137   struct SeqMerger {
 138     void Call(Var var, Effect effect) { self.Seq(var, effect); }
 139     Self self;
 140   };
 141
 142   template<class Self>
 143   struct AltMerger {
 144     void Call(Var var, Effect effect) { self.Alt(var, effect); }
 145     Self self;
 146   };
 147
 148   template<class Self>
 149   struct AltWeakener {
 150     void Call(Var var, Effect effect) {
 151       if (effect.modality == Effect::DEFINITE && !other.Contains(var)) {
 152         effect.modality = Effect::POSSIBLE;
 153         Locator locator;
 154         self.Insert(var, &locator);
 155         locator.set_value(effect);
 156       }
 157     }
 158     Self self;
 159     Effects other;
 160   };
 161
 162   struct Overrider {
 163     void Call(Var var, Effect effect) { effects.Seq(var, new_effect); }
 164     Effect new_effect;
 165     Effects effects;
 166   };
 167 };
 168
 169
 170 template<class Var, Var kNoVar> class Effects;
 171 template<class Var, Var kNoVar> class NestedEffectsBase;
 172
 173 template<class Var, Var kNoVar>
 174 class EffectsBase {
 175  public:
 176   explicit EffectsBase(Zone* zone) : map_(new(zone) Mapping(zone)) {}
 177
 178   bool IsEmpty() { return map_->is_empty(); }
 179
 180  protected:
 181   friend class NestedEffectsBase<Var, kNoVar>;
 182   friend class
 183       EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >;
 184
 185   Zone* zone() { return map_->allocator().zone(); }
 186
 187   struct SplayTreeConfig {
 188     typedef Var Key;
 189     typedef Effect Value;
 190     static const Var kNoKey = kNoVar;
 191     static Effect NoValue() { return Effect(); }
 192     static int Compare(int x, int y) { return y - x; }
 193   };
 194   typedef ZoneSplayTree<SplayTreeConfig> Mapping;
 195   typedef typename Mapping::Locator Locator;
 196
 197   bool Contains(Var var) {
 198     ASSERT(var != kNoVar);
 199     return map_->Contains(var);
 200   }
 201   bool Find(Var var, Locator* locator) {
 202     ASSERT(var != kNoVar);
 203     return map_->Find(var, locator);
 204   }
 205   bool Insert(Var var, Locator* locator) {
 206     ASSERT(var != kNoVar);
 207     return map_->Insert(var, locator);
 208   }
 209
 210   template<class Callback>
 211   void ForEach(Callback* callback) {
 212     return map_->ForEach(callback);
 213   }
 214
 215  private:
 216   Mapping* map_;
 217 };
 218
 219 template<class Var, Var kNoVar>
 220 const Var EffectsBase<Var, kNoVar>::SplayTreeConfig::kNoKey;
 221
 222 template<class Var, Var kNoVar>
 223 class Effects: public
 224     EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > {
 225  public:
 226   explicit Effects(Zone* zone)
 227       : EffectsMixin<Var, EffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(zone)
 228           {}
 229 };
 230
 231
 232 template<class Var, Var kNoVar>
 233 class NestedEffectsBase {
 234  public:
 235   explicit NestedEffectsBase(Zone* zone) : node_(new(zone) Node(zone)) {}
 236
 237   template<class Callback>
 238   void ForEach(Callback* callback) {
 239     if (node_->previous) NestedEffectsBase(node_->previous).ForEach(callback);
 240     node_->effects.ForEach(callback);
 241   }
 242
 243   Effects<Var, kNoVar> Top() { return node_->effects; }
 244
 245   bool IsEmpty() {
 246     for (Node* node = node_; node != NULL; node = node->previous) {
 247       if (!node->effects.IsEmpty()) return false;
 248     }
 249     return true;
 250   }
 251
 252  protected:
 253   typedef typename EffectsBase<Var, kNoVar>::Locator Locator;
 254
 255   Zone* zone() { return node_->zone; }
 256
 257   void push() { node_ = new(node_->zone) Node(node_->zone, node_); }
 258   void pop() { node_ = node_->previous; }
 259   bool is_empty() { return node_ == NULL; }
 260
 261   bool Contains(Var var) {
 262     ASSERT(var != kNoVar);
 263     for (Node* node = node_; node != NULL; node = node->previous) {
 264       if (node->effects.Contains(var)) return true;
 265     }
 266     return false;
 267   }
 268
 269   bool Find(Var var, Locator* locator) {
 270     ASSERT(var != kNoVar);
 271     for (Node* node = node_; node != NULL; node = node->previous) {
 272       if (node->effects.Find(var, locator)) return true;
 273     }
 274     return false;
 275   }
 276
 277   bool Insert(Var var, Locator* locator);
 278
 279  private:
 280   struct Node: ZoneObject {
 281     Zone* zone;
 282     Effects<Var, kNoVar> effects;
 283     Node* previous;
 284     explicit Node(Zone* zone, Node* previous = NULL)
 285         : zone(zone), effects(zone), previous(previous) {}
 286   };
 287
 288   explicit NestedEffectsBase(Node* node) : node_(node) {}
 289
 290   Node* node_;
 291 };
 292
 293
 294 template<class Var, Var kNoVar>
 295 bool NestedEffectsBase<Var, kNoVar>::Insert(Var var, Locator* locator) {
 296   ASSERT(var != kNoVar);
 297   if (!node_->effects.Insert(var, locator)) return false;
 298   Locator shadowed;
 299   for (Node* node = node_->previous; node != NULL; node = node->previous) {
 300     if (node->effects.Find(var, &shadowed)) {
 301       // Initialize with shadowed entry.
 302       locator->set_value(shadowed.value());
 303       return false;
 304     }
 305   }
 306   return true;
 307 }
 308
 309
 310 template<class Var, Var kNoVar>
 311 class NestedEffects: public
 312     EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> > {
 313  public:
 314   explicit NestedEffects(Zone* zone) :
 315       EffectsMixin<Var, NestedEffectsBase<Var, kNoVar>, Effects<Var, kNoVar> >(
 316           zone) {}
 317
 318   // Create an extension of the current effect set. The current set should not
 319   // be modified while the extension is in use.
 320   NestedEffects Push() {
 321     NestedEffects result = *this;
 322     result.push();
 323     return result;
 324   }
 325
 326   NestedEffects Pop() {
 327     NestedEffects result = *this;
 328     result.pop();
 329     ASSERT(!this->is_empty());
 330     return result;
 331   }
 332 };
 333
 334 } }  // namespace v8::internal
 335
 336 #endif  // V8_EFFECTS_H_