dfg/DFGStructureAbstractValue.cpp

   1 /*
   2  * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "DFGStructureAbstractValue.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGGraph.h"
  32
  33 namespace JSC { namespace DFG {
  34
  35 // Comment out the empty SAMPLE() definition, and uncomment the one that uses SamplingRegion, if
  36 // you want extremely fine-grained profiling in this code.
  37 #define SAMPLE(name)
  38 //#define SAMPLE(name) SamplingRegion samplingRegion(name)
  39
  40 #if !ASSERT_DISABLED
  41 void StructureAbstractValue::assertIsRegistered(Graph& graph) const
  42 {
  43     SAMPLE("StructureAbstractValue assertIsRegistered");
  44
  45     if (isTop())
  46         return;
  47
  48     for (unsigned i = size(); i--;)
  49         graph.assertIsRegistered(at(i));
  50 }
  51 #endif // !ASSERT_DISABLED
  52
  53 void StructureAbstractValue::clobber()
  54 {
  55     SAMPLE("StructureAbstractValue clobber");
  56
  57     // The premise of this approach to clobbering is that anytime we introduce
  58     // a watchable structure into an abstract value, we watchpoint it. You can assert
  59     // that this holds by calling assertIsWatched().
  60
  61     if (isTop())
  62         return;
  63
  64     setClobbered(true);
  65
  66     if (m_set.isThin()) {
  67         if (!m_set.singleEntry())
  68             return;
  69         if (!m_set.singleEntry()->dfgShouldWatch())
  70             makeTopWhenThin();
  71         return;
  72     }
  73
  74     StructureSet::OutOfLineList* list = m_set.list();
  75     for (unsigned i = list->m_length; i--;) {
  76         if (!list->list()[i]->dfgShouldWatch()) {
  77             makeTop();
  78             return;
  79         }
  80     }
  81 }
  82
  83 void StructureAbstractValue::observeTransition(Structure* from, Structure* to)
  84 {
  85     SAMPLE("StructureAbstractValue observeTransition");
  86
  87     ASSERT(!from->dfgShouldWatch());
  88
  89     if (isTop())
  90         return;
  91
  92     if (!m_set.contains(from))
  93         return;
  94
  95     if (!m_set.add(to))
  96         return;
  97
  98     if (m_set.size() > polymorphismLimit)
  99         makeTop();
 100 }
 101
 102 void StructureAbstractValue::observeTransitions(const TransitionVector& vector)
 103 {
 104     SAMPLE("StructureAbstractValue observeTransitions");
 105
 106     if (isTop())
 107         return;
 108
 109     StructureSet newStructures;
 110     for (unsigned i = vector.size(); i--;) {
 111         ASSERT(!vector[i].previous->dfgShouldWatch());
 112
 113         if (!m_set.contains(vector[i].previous))
 114             continue;
 115
 116         newStructures.add(vector[i].next);
 117     }
 118
 119     if (!m_set.merge(newStructures))
 120         return;
 121
 122     if (m_set.size() > polymorphismLimit)
 123         makeTop();
 124 }
 125
 126 bool StructureAbstractValue::add(Structure* structure)
 127 {
 128     SAMPLE("StructureAbstractValue add");
 129
 130     if (isTop())
 131         return false;
 132
 133     if (!m_set.add(structure))
 134         return false;
 135
 136     if (m_set.size() > polymorphismLimit)
 137         makeTop();
 138
 139     return true;
 140 }
 141
 142 bool StructureAbstractValue::merge(const StructureSet& other)
 143 {
 144     SAMPLE("StructureAbstractValue merge set");
 145
 146     if (isTop())
 147         return false;
 148
 149     return mergeNotTop(other);
 150 }
 151
 152 bool StructureAbstractValue::mergeSlow(const StructureAbstractValue& other)
 153 {
 154     SAMPLE("StructureAbstractValue merge value slow");
 155
 156     // It isn't immediately obvious that the code below is doing the right thing, so let's go
 157     // through it.
 158     //
 159     // This not clobbered, other not clobbered: Clearly, we don't want to make anything clobbered
 160     // since we just have two sets and we are merging them. mergeNotTop() can handle this just
 161     // fine.
 162     //
 163     // This clobbered, other clobbered: Clobbered means that we have a set of things, plus we
 164     // temporarily have the set of all things but the latter will go away once we hit the next
 165     // invalidation point. This allows us to merge two clobbered sets the natural way. For now
 166     // the set will still be TOP (and so we keep the clobbered bit set), but we know that after
 167     // invalidation, we will have the union of the this and other.
 168     //
 169     // This clobbered, other not clobbered: It's safe to merge in other for both before and after
 170     // invalidation, so long as we leave the clobbered bit set. Before invalidation this has no
 171     // effect since the set will still appear to have all things in it. The way to think about
 172     // what invalidation would do is imagine if we had a set A that was clobbered and a set B
 173     // that wasn't and we considered the following two cases. Note that we expect A to be the
 174     // same at the end in both cases:
 175     //
 176     //            A.merge(B)                             InvalidationPoint
 177     //            InvalidationPoint                      A.merge(B)
 178     //
 179     // The fact that we expect A to be the same in both cases means that we want to merge other
 180     // into this but keep the clobbered bit.
 181     //
 182     // This not clobbered, other clobbered: This is just the converse of the previous case. We
 183     // want to merge other into this and set the clobbered bit.
 184
 185     bool changed = false;
 186
 187     if (!isClobbered() && other.isClobbered()) {
 188         setClobbered(true);
 189         changed = true;
 190     }
 191
 192     changed |= mergeNotTop(other.m_set);
 193
 194     return changed;
 195 }
 196
 197 bool StructureAbstractValue::mergeNotTop(const StructureSet& other)
 198 {
 199     SAMPLE("StructureAbstractValue merge not top");
 200
 201     if (!m_set.merge(other))
 202         return false;
 203
 204     if (m_set.size() > polymorphismLimit)
 205         makeTop();
 206
 207     return true;
 208 }
 209
 210 void StructureAbstractValue::filter(const StructureSet& other)
 211 {
 212     SAMPLE("StructureAbstractValue filter set");
 213
 214     if (isTop()) {
 215         m_set = other;
 216         return;
 217     }
 218
 219     if (isClobbered()) {
 220         // We have two choices here:
 221         //
 222         // Do nothing: It's legal to keep our set intact, which would essentially mean that for
 223         // now, our set would behave like TOP but after the next invalidation point it wold be
 224         // a finite set again. This may be a good choice if 'other' is much bigger than our
 225         // m_set.
 226         //
 227         // Replace m_set with other and clear the clobber bit: This is also legal, and means that
 228         // we're no longer clobbered. This is usually better because it immediately gives us a
 229         // smaller set.
 230         //
 231         // This scenario should come up rarely. We usually don't do anything to an abstract value
 232         // after it is clobbered. But we apply some heuristics.
 233
 234         if (other.size() > m_set.size() + clobberedSupremacyThreshold)
 235             return; // Keep the clobbered set.
 236
 237         m_set = other;
 238         setClobbered(false);
 239         return;
 240     }
 241
 242     m_set.filter(other);
 243 }
 244
 245 void StructureAbstractValue::filter(const StructureAbstractValue& other)
 246 {
 247     SAMPLE("StructureAbstractValue filter value");
 248
 249     if (other.isTop())
 250         return;
 251
 252     if (other.isClobbered()) {
 253         if (isTop())
 254             return;
 255
 256         if (!isClobbered()) {
 257             // See justification in filter(const StructureSet&), above. An unclobbered set is
 258             // almost always better.
 259             if (m_set.size() > other.m_set.size() + clobberedSupremacyThreshold)
 260                 *this = other; // Keep the clobbered set.
 261             return;
 262         }
 263
 264         m_set.filter(other.m_set);
 265         return;
 266     }
 267
 268     filter(other.m_set);
 269 }
 270
 271 void StructureAbstractValue::filterSlow(SpeculatedType type)
 272 {
 273     SAMPLE("StructureAbstractValue filter type slow");
 274
 275     if (!(type & SpecCell)) {
 276         clear();
 277         return;
 278     }
 279
 280     ASSERT(!isTop());
 281
 282     m_set.genericFilter(
 283         [&] (Structure* structure) {
 284             return !!(speculationFromStructure(structure) & type);
 285         });
 286 }
 287
 288 bool StructureAbstractValue::contains(Structure* structure) const
 289 {
 290     SAMPLE("StructureAbstractValue contains");
 291
 292     if (isTop() || isClobbered())
 293         return true;
 294
 295     return m_set.contains(structure);
 296 }
 297
 298 bool StructureAbstractValue::isSubsetOf(const StructureSet& other) const
 299 {
 300     SAMPLE("StructureAbstractValue isSubsetOf set");
 301
 302     if (isTop() || isClobbered())
 303         return false;
 304
 305     return m_set.isSubsetOf(other);
 306 }
 307
 308 bool StructureAbstractValue::isSubsetOf(const StructureAbstractValue& other) const
 309 {
 310     SAMPLE("StructureAbstractValue isSubsetOf value");
 311
 312     if (isTop())
 313         return false;
 314
 315     if (other.isTop())
 316         return true;
 317
 318     if (isClobbered() == other.isClobbered())
 319         return m_set.isSubsetOf(other.m_set);
 320
 321     // Here it gets tricky. If in doubt, return false!
 322
 323     if (isClobbered())
 324         return false; // A clobbered set is never a subset of an unclobbered set.
 325
 326     // An unclobbered set is currently a subset of a clobbered set, but it may not be so after
 327     // invalidation.
 328     return m_set.isSubsetOf(other.m_set);
 329 }
 330
 331 bool StructureAbstractValue::isSupersetOf(const StructureSet& other) const
 332 {
 333     SAMPLE("StructureAbstractValue isSupersetOf set");
 334
 335     if (isTop() || isClobbered())
 336         return true;
 337
 338     return m_set.isSupersetOf(other);
 339 }
 340
 341 bool StructureAbstractValue::overlaps(const StructureSet& other) const
 342 {
 343     SAMPLE("StructureAbstractValue overlaps set");
 344
 345     if (isTop() || isClobbered())
 346         return true;
 347
 348     return m_set.overlaps(other);
 349 }
 350
 351 bool StructureAbstractValue::overlaps(const StructureAbstractValue& other) const
 352 {
 353     SAMPLE("StructureAbstractValue overlaps value");
 354
 355     if (other.isTop() || other.isClobbered())
 356         return true;
 357
 358     return overlaps(other.m_set);
 359 }
 360
 361 bool StructureAbstractValue::equalsSlow(const StructureAbstractValue& other) const
 362 {
 363     SAMPLE("StructureAbstractValue equalsSlow");
 364
 365     ASSERT(m_set.m_pointer != other.m_set.m_pointer);
 366     ASSERT(!isTop());
 367     ASSERT(!other.isTop());
 368
 369     return m_set == other.m_set
 370         && isClobbered() == other.isClobbered();
 371 }
 372
 373 void StructureAbstractValue::dumpInContext(PrintStream& out, DumpContext* context) const
 374 {
 375     if (isClobbered())
 376         out.print("Clobbered:");
 377
 378     if (isTop())
 379         out.print("TOP");
 380     else
 381         out.print(inContext(m_set, context));
 382 }
 383
 384 void StructureAbstractValue::dump(PrintStream& out) const
 385 {
 386     dumpInContext(out, 0);
 387 }
 388
 389 void StructureAbstractValue::validateReferences(const TrackedReferences& trackedReferences) const
 390 {
 391     if (isTop())
 392         return;
 393     m_set.validateReferences(trackedReferences);
 394 }
 395
 396 } } // namespace JSC::DFG
 397
 398 #endif // ENABLE(DFG_JIT)
 399