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