dfg/DFGAbstractValue.h

   1 /*
   2  * Copyright (C) 2011 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 #ifndef DFGAbstractValue_h
  27 #define DFGAbstractValue_h
  28
  29 #include <wtf/Platform.h>
  30
  31 #if ENABLE(DFG_JIT)
  32
  33 #include "JSCell.h"
  34 #include "PredictedType.h"
  35 #include "StructureSet.h"
  36
  37 namespace JSC { namespace DFG {
  38
  39 class StructureAbstractValue {
  40 public:
  41     StructureAbstractValue()
  42         : m_structure(0)
  43     {
  44     }
  45
  46     StructureAbstractValue(Structure* structure)
  47         : m_structure(structure)
  48     {
  49     }
  50
  51     StructureAbstractValue(const StructureSet& set)
  52     {
  53         switch (set.size()) {
  54         case 0:
  55             m_structure = 0;
  56             break;
  57
  58         case 1:
  59             m_structure = set[0];
  60             break;
  61
  62         default:
  63             m_structure = topValue();
  64             break;
  65         }
  66     }
  67
  68     void clear()
  69     {
  70         m_structure = 0;
  71     }
  72
  73     void makeTop()
  74     {
  75         m_structure = topValue();
  76     }
  77
  78     static StructureAbstractValue top()
  79     {
  80         StructureAbstractValue value;
  81         value.makeTop();
  82         return value;
  83     }
  84
  85     void add(Structure* structure)
  86     {
  87         ASSERT(!contains(structure) && !isTop());
  88         if (m_structure)
  89             makeTop();
  90         else
  91             m_structure = structure;
  92     }
  93
  94     bool addAll(const StructureSet& other)
  95     {
  96         if (isTop() || !other.size())
  97             return false;
  98         if (other.size() > 1) {
  99             makeTop();
 100             return true;
 101         }
 102         if (!m_structure) {
 103             m_structure = other[0];
 104             return true;
 105         }
 106         if (m_structure == other[0])
 107             return false;
 108         makeTop();
 109         return true;
 110     }
 111
 112     bool addAll(const StructureAbstractValue& other)
 113     {
 114         if (!other.m_structure)
 115             return false;
 116         if (isTop())
 117             return false;
 118         if (other.isTop()) {
 119             makeTop();
 120             return true;
 121         }
 122         if (m_structure) {
 123             if (m_structure == other.m_structure)
 124                 return false;
 125             makeTop();
 126             return true;
 127         }
 128         m_structure = other.m_structure;
 129         return true;
 130     }
 131
 132     bool contains(Structure* structure) const
 133     {
 134         if (isTop())
 135             return true;
 136         if (m_structure == structure)
 137             return true;
 138         return false;
 139     }
 140
 141     bool isSubsetOf(const StructureSet& other) const
 142     {
 143         if (isTop())
 144             return false;
 145         if (!m_structure)
 146             return true;
 147         return other.contains(m_structure);
 148     }
 149
 150     bool doesNotContainAnyOtherThan(Structure* structure) const
 151     {
 152         if (isTop())
 153             return false;
 154         if (!m_structure)
 155             return true;
 156         return m_structure == structure;
 157     }
 158
 159     bool isSupersetOf(const StructureSet& other) const
 160     {
 161         if (isTop())
 162             return true;
 163         if (!other.size())
 164             return true;
 165         if (other.size() > 1)
 166             return false;
 167         return m_structure == other[0];
 168     }
 169
 170     bool isSubsetOf(const StructureAbstractValue& other) const
 171     {
 172         if (other.isTop())
 173             return true;
 174         if (isTop())
 175             return false;
 176         if (m_structure) {
 177             if (other.m_structure)
 178                 return m_structure == other.m_structure;
 179             return false;
 180         }
 181         return true;
 182     }
 183
 184     bool isSupersetOf(const StructureAbstractValue& other) const
 185     {
 186         return other.isSubsetOf(*this);
 187     }
 188
 189     void filter(const StructureSet& other)
 190     {
 191         if (!m_structure)
 192             return;
 193
 194         if (isTop()) {
 195             switch (other.size()) {
 196             case 0:
 197                 m_structure = 0;
 198                 return;
 199
 200             case 1:
 201                 m_structure = other[0];
 202                 return;
 203
 204             default:
 205                 return;
 206             }
 207         }
 208
 209         if (other.contains(m_structure))
 210             return;
 211
 212         m_structure = 0;
 213     }
 214
 215     void filter(const StructureAbstractValue& other)
 216     {
 217         if (isTop()) {
 218             m_structure = other.m_structure;
 219             return;
 220         }
 221         if (m_structure == other.m_structure)
 222             return;
 223         if (other.isTop())
 224             return;
 225         m_structure = 0;
 226     }
 227
 228     void filter(PredictedType other)
 229     {
 230         if (!(other & PredictCell)) {
 231             clear();
 232             return;
 233         }
 234
 235         if (isClearOrTop())
 236             return;
 237
 238         if (!(predictionFromStructure(m_structure) & other))
 239             m_structure = 0;
 240     }
 241
 242     bool isClear() const
 243     {
 244         return !m_structure;
 245     }
 246
 247     bool isTop() const { return m_structure == topValue(); }
 248
 249     bool isClearOrTop() const { return m_structure <= topValue(); }
 250     bool isNeitherClearNorTop() const { return !isClearOrTop(); }
 251
 252     size_t size() const
 253     {
 254         ASSERT(!isTop());
 255         return !!m_structure;
 256     }
 257
 258     Structure* at(size_t i) const
 259     {
 260         ASSERT(!isTop());
 261         ASSERT(m_structure);
 262         ASSERT_UNUSED(i, !i);
 263         return m_structure;
 264     }
 265
 266     Structure* operator[](size_t i) const
 267     {
 268         return at(i);
 269     }
 270
 271     Structure* last() const
 272     {
 273         return at(0);
 274     }
 275
 276     PredictedType predictionFromStructures() const
 277     {
 278         if (isTop())
 279             return PredictCell;
 280         if (isClear())
 281             return PredictNone;
 282         return predictionFromStructure(m_structure);
 283     }
 284
 285     bool operator==(const StructureAbstractValue& other) const
 286     {
 287         return m_structure == other.m_structure;
 288     }
 289
 290     void dump(FILE* out) const
 291     {
 292         if (isTop()) {
 293             fprintf(out, "TOP");
 294             return;
 295         }
 296
 297         fprintf(out, "[");
 298         if (m_structure)
 299             fprintf(out, "%p", m_structure);
 300         fprintf(out, "]");
 301     }
 302
 303 private:
 304     static Structure* topValue() { return reinterpret_cast<Structure*>(1); }
 305
 306     // This can only remember one structure at a time.
 307     Structure* m_structure;
 308 };
 309
 310 struct AbstractValue {
 311     AbstractValue()
 312         : m_type(PredictNone)
 313     {
 314     }
 315
 316     void clear()
 317     {
 318         m_type = PredictNone;
 319         m_structure.clear();
 320         checkConsistency();
 321     }
 322
 323     bool isClear()
 324     {
 325         return m_type == PredictNone && m_structure.isClear();
 326     }
 327
 328     void makeTop()
 329     {
 330         m_type = PredictTop;
 331         m_structure.makeTop();
 332         checkConsistency();
 333     }
 334
 335     void clobberStructures()
 336     {
 337         if (m_type & PredictCell)
 338             m_structure.makeTop();
 339         else
 340             ASSERT(m_structure.isClear());
 341         checkConsistency();
 342     }
 343
 344     bool isTop() const
 345     {
 346         return m_type == PredictTop && m_structure.isTop();
 347     }
 348
 349     static AbstractValue top()
 350     {
 351         AbstractValue result;
 352         result.makeTop();
 353         return result;
 354     }
 355
 356     void set(JSValue value)
 357     {
 358         m_structure.clear();
 359         if (value.isCell())
 360             m_structure.add(value.asCell()->structure());
 361
 362         m_type = predictionFromValue(value);
 363
 364         checkConsistency();
 365     }
 366
 367     void set(Structure* structure)
 368     {
 369         m_structure.clear();
 370         m_structure.add(structure);
 371
 372         m_type = predictionFromStructure(structure);
 373
 374         checkConsistency();
 375     }
 376
 377     void set(PredictedType type)
 378     {
 379         if (type & PredictCell)
 380             m_structure.makeTop();
 381         else
 382             m_structure.clear();
 383         m_type = type;
 384         checkConsistency();
 385     }
 386
 387     bool operator==(const AbstractValue& other) const
 388     {
 389         return m_type == other.m_type && m_structure == other.m_structure;
 390     }
 391
 392     bool merge(const AbstractValue& other)
 393     {
 394         bool result = mergePrediction(m_type, other.m_type) | m_structure.addAll(other.m_structure);
 395         checkConsistency();
 396         return result;
 397     }
 398
 399     void merge(PredictedType type)
 400     {
 401         mergePrediction(m_type, type);
 402
 403         if (type & PredictCell)
 404             m_structure.makeTop();
 405
 406         checkConsistency();
 407     }
 408
 409     void filter(const StructureSet& other)
 410     {
 411         m_type &= other.predictionFromStructures();
 412         m_structure.filter(other);
 413
 414         // It's possible that prior to the above two statements we had (Foo, TOP), where
 415         // Foo is a PredictedType that is disjoint with the passed StructureSet. In that
 416         // case, we will now have (None, [someStructure]). In general, we need to make
 417         // sure that new information gleaned from the PredictedType needs to be fed back
 418         // into the information gleaned from the StructureSet.
 419         m_structure.filter(m_type);
 420         checkConsistency();
 421     }
 422
 423     void filter(PredictedType type)
 424     {
 425         if (type == PredictTop)
 426             return;
 427         m_type &= type;
 428
 429         // It's possible that prior to this filter() call we had, say, (Final, TOP), and
 430         // the passed type is Array. At this point we'll have (None, TOP). The best way
 431         // to ensure that the structure filtering does the right thing is to filter on
 432         // the new type (None) rather than the one passed (Array).
 433         m_structure.filter(m_type);
 434         checkConsistency();
 435     }
 436
 437     bool validate(JSValue value) const
 438     {
 439         if (isTop())
 440             return true;
 441
 442         if (mergePredictions(m_type, predictionFromValue(value)) != m_type)
 443             return false;
 444
 445         if (value.isEmpty()) {
 446             ASSERT(m_type & PredictEmpty);
 447             return true;
 448         }
 449
 450         if (m_structure.isTop())
 451             return true;
 452
 453         if (value.isCell()) {
 454             ASSERT(m_type & PredictCell);
 455             return m_structure.contains(value.asCell()->structure());
 456         }
 457
 458         return true;
 459     }
 460
 461     void checkConsistency() const
 462     {
 463         if (!(m_type & PredictCell))
 464             ASSERT(m_structure.isClear());
 465
 466         // Note that it's possible for a prediction like (Final, []). This really means that
 467         // the value is bottom and that any code that uses the value is unreachable. But
 468         // we don't want to get pedantic about this as it would only increase the computational
 469         // complexity of the code.
 470     }
 471
 472     void dump(FILE* out) const
 473     {
 474         fprintf(out, "(%s, ", predictionToString(m_type));
 475         m_structure.dump(out);
 476         fprintf(out, ")");
 477     }
 478
 479     StructureAbstractValue m_structure;
 480     PredictedType m_type;
 481 };
 482
 483 } } // namespace JSC::DFG
 484
 485 #endif // ENABLE(DFG_JIT)
 486
 487 #endif // DFGAbstractValue_h
 488
 489