dfg/DFGBackwardsPropagationPhase.cpp

   1 /*
   2  * Copyright (C) 2013-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 "DFGBackwardsPropagationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGPhase.h"
  34 #include "JSCInlines.h"
  35
  36 namespace JSC { namespace DFG {
  37
  38 class BackwardsPropagationPhase : public Phase {
  39 public:
  40     BackwardsPropagationPhase(Graph& graph)
  41         : Phase(graph, "backwards propagation")
  42     {
  43     }
  44
  45     bool run()
  46     {
  47         m_changed = true;
  48         while (m_changed) {
  49             m_changed = false;
  50             for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
  51                 BasicBlock* block = m_graph.block(blockIndex);
  52                 if (!block)
  53                     continue;
  54
  55                 // Prevent a tower of overflowing additions from creating a value that is out of the
  56                 // safe 2^48 range.
  57                 m_allowNestedOverflowingAdditions = block->size() < (1 << 16);
  58
  59                 for (unsigned indexInBlock = block->size(); indexInBlock--;)
  60                     propagate(block->at(indexInBlock));
  61             }
  62         }
  63
  64         return true;
  65     }
  66
  67 private:
  68     bool isNotNegZero(Node* node)
  69     {
  70         if (!node->isNumberConstant())
  71             return false;
  72         double value = node->asNumber();
  73         return (value || 1.0 / value > 0.0);
  74     }
  75
  76     bool isNotPosZero(Node* node)
  77     {
  78         if (!node->isNumberConstant())
  79             return false;
  80         double value = node->asNumber();
  81         return (value || 1.0 / value < 0.0);
  82     }
  83
  84     // Tests if the absolute value is strictly less than the power of two.
  85     template<int power>
  86     bool isWithinPowerOfTwoForConstant(Node* node)
  87     {
  88         JSValue immediateValue = node->asJSValue();
  89         if (!immediateValue.isNumber())
  90             return false;
  91         double immediate = immediateValue.asNumber();
  92         return immediate > -(static_cast<int64_t>(1) << power) && immediate < (static_cast<int64_t>(1) << power);
  93     }
  94
  95     template<int power>
  96     bool isWithinPowerOfTwoNonRecursive(Node* node)
  97     {
  98         if (!node->isNumberConstant())
  99             return false;
 100         return isWithinPowerOfTwoForConstant<power>(node);
 101     }
 102
 103     template<int power>
 104     bool isWithinPowerOfTwo(Node* node)
 105     {
 106         switch (node->op()) {
 107         case DoubleConstant:
 108         case JSConstant:
 109         case Int52Constant: {
 110             return isWithinPowerOfTwoForConstant<power>(node);
 111         }
 112
 113         case BitAnd: {
 114             if (power > 31)
 115                 return true;
 116
 117             return isWithinPowerOfTwoNonRecursive<power>(node->child1().node())
 118                 || isWithinPowerOfTwoNonRecursive<power>(node->child2().node());
 119         }
 120
 121         case BitOr:
 122         case BitXor:
 123         case BitLShift: {
 124             return power > 31;
 125         }
 126
 127         case BitRShift:
 128         case BitURShift: {
 129             if (power > 31)
 130                 return true;
 131
 132             Node* shiftAmount = node->child2().node();
 133             if (!node->isNumberConstant())
 134                 return false;
 135             JSValue immediateValue = shiftAmount->asJSValue();
 136             if (!immediateValue.isInt32())
 137                 return false;
 138             return immediateValue.asInt32() > 32 - power;
 139         }
 140
 141         default:
 142             return false;
 143         }
 144     }
 145
 146     template<int power>
 147     bool isWithinPowerOfTwo(Edge edge)
 148     {
 149         return isWithinPowerOfTwo<power>(edge.node());
 150     }
 151
 152     bool mergeDefaultFlags(Node* node)
 153     {
 154         bool changed = false;
 155         if (node->flags() & NodeHasVarArgs) {
 156             for (unsigned childIdx = node->firstChild();
 157                 childIdx < node->firstChild() + node->numChildren();
 158                 childIdx++) {
 159                 if (!!m_graph.m_varArgChildren[childIdx])
 160                     changed |= m_graph.m_varArgChildren[childIdx]->mergeFlags(NodeBytecodeUsesAsValue);
 161             }
 162         } else {
 163             if (!node->child1())
 164                 return changed;
 165             changed |= node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
 166             if (!node->child2())
 167                 return changed;
 168             changed |= node->child2()->mergeFlags(NodeBytecodeUsesAsValue);
 169             if (!node->child3())
 170                 return changed;
 171             changed |= node->child3()->mergeFlags(NodeBytecodeUsesAsValue);
 172         }
 173         return changed;
 174     }
 175
 176     void propagate(Node* node)
 177     {
 178         NodeFlags flags = node->flags() & NodeBytecodeBackPropMask;
 179
 180         switch (node->op()) {
 181         case GetLocal: {
 182             VariableAccessData* variableAccessData = node->variableAccessData();
 183             flags &= ~NodeBytecodeUsesAsInt; // We don't care about cross-block uses-as-int.
 184             m_changed |= variableAccessData->mergeFlags(flags);
 185             break;
 186         }
 187
 188         case SetLocal: {
 189             VariableAccessData* variableAccessData = node->variableAccessData();
 190             if (!variableAccessData->isLoadedFrom())
 191                 break;
 192             flags = variableAccessData->flags();
 193             RELEASE_ASSERT(!(flags & ~NodeBytecodeBackPropMask));
 194             flags |= NodeBytecodeUsesAsNumber; // Account for the fact that control flow may cause overflows that our modeling can't handle.
 195             node->child1()->mergeFlags(flags);
 196             break;
 197         }
 198
 199         case Flush: {
 200             VariableAccessData* variableAccessData = node->variableAccessData();
 201             m_changed |= variableAccessData->mergeFlags(NodeBytecodeUsesAsValue);
 202             break;
 203         }
 204
 205         case MovHint:
 206         case Check:
 207             break;
 208
 209         case BitAnd:
 210         case BitOr:
 211         case BitXor:
 212         case BitRShift:
 213         case BitLShift:
 214         case BitURShift:
 215         case ArithIMul: {
 216             flags |= NodeBytecodeUsesAsInt;
 217             flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther);
 218             flags &= ~NodeBytecodeUsesAsArrayIndex;
 219             node->child1()->mergeFlags(flags);
 220             node->child2()->mergeFlags(flags);
 221             break;
 222         }
 223
 224         case StringCharCodeAt: {
 225             node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
 226             node->child2()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
 227             break;
 228         }
 229
 230         case UInt32ToNumber: {
 231             node->child1()->mergeFlags(flags);
 232             break;
 233         }
 234
 235         case ValueAdd: {
 236             if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
 237                 flags &= ~NodeBytecodeNeedsNegZero;
 238             if (node->child1()->hasNumberResult() || node->child2()->hasNumberResult())
 239                 flags &= ~NodeBytecodeUsesAsOther;
 240             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
 241                 flags |= NodeBytecodeUsesAsNumber;
 242             if (!m_allowNestedOverflowingAdditions)
 243                 flags |= NodeBytecodeUsesAsNumber;
 244
 245             node->child1()->mergeFlags(flags);
 246             node->child2()->mergeFlags(flags);
 247             break;
 248         }
 249
 250         case ArithAdd: {
 251             if (isNotNegZero(node->child1().node()) || isNotNegZero(node->child2().node()))
 252                 flags &= ~NodeBytecodeNeedsNegZero;
 253             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
 254                 flags |= NodeBytecodeUsesAsNumber;
 255             if (!m_allowNestedOverflowingAdditions)
 256                 flags |= NodeBytecodeUsesAsNumber;
 257
 258             node->child1()->mergeFlags(flags);
 259             node->child2()->mergeFlags(flags);
 260             break;
 261         }
 262
 263         case ArithClz32: {
 264             flags &= ~(NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero | NodeBytecodeUsesAsOther | ~NodeBytecodeUsesAsArrayIndex);
 265             flags |= NodeBytecodeUsesAsInt;
 266             node->child1()->mergeFlags(flags);
 267             break;
 268         }
 269
 270         case ArithSub: {
 271             if (isNotNegZero(node->child1().node()) || isNotPosZero(node->child2().node()))
 272                 flags &= ~NodeBytecodeNeedsNegZero;
 273             if (!isWithinPowerOfTwo<32>(node->child1()) && !isWithinPowerOfTwo<32>(node->child2()))
 274                 flags |= NodeBytecodeUsesAsNumber;
 275             if (!m_allowNestedOverflowingAdditions)
 276                 flags |= NodeBytecodeUsesAsNumber;
 277
 278             node->child1()->mergeFlags(flags);
 279             node->child2()->mergeFlags(flags);
 280             break;
 281         }
 282
 283         case ArithNegate: {
 284             flags &= ~NodeBytecodeUsesAsOther;
 285
 286             node->child1()->mergeFlags(flags);
 287             break;
 288         }
 289
 290         case ArithMul: {
 291             // As soon as a multiply happens, we can easily end up in the part
 292             // of the double domain where the point at which you do truncation
 293             // can change the outcome. So, ArithMul always forces its inputs to
 294             // check for overflow. Additionally, it will have to check for overflow
 295             // itself unless we can prove that there is no way for the values
 296             // produced to cause double rounding.
 297
 298             if (!isWithinPowerOfTwo<22>(node->child1().node())
 299                 && !isWithinPowerOfTwo<22>(node->child2().node()))
 300                 flags |= NodeBytecodeUsesAsNumber;
 301
 302             node->mergeFlags(flags);
 303
 304             flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero;
 305             flags &= ~NodeBytecodeUsesAsOther;
 306
 307             node->child1()->mergeFlags(flags);
 308             node->child2()->mergeFlags(flags);
 309             break;
 310         }
 311
 312         case ArithDiv: {
 313             flags |= NodeBytecodeUsesAsNumber | NodeBytecodeNeedsNegZero;
 314             flags &= ~NodeBytecodeUsesAsOther;
 315
 316             node->child1()->mergeFlags(flags);
 317             node->child2()->mergeFlags(flags);
 318             break;
 319         }
 320
 321         case ArithMod: {
 322             flags |= NodeBytecodeUsesAsNumber;
 323             flags &= ~NodeBytecodeUsesAsOther;
 324
 325             node->child1()->mergeFlags(flags);
 326             node->child2()->mergeFlags(flags & ~NodeBytecodeNeedsNegZero);
 327             break;
 328         }
 329
 330         case GetByVal: {
 331             node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
 332             node->child2()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
 333             break;
 334         }
 335
 336         case NewArrayWithSize: {
 337             node->child1()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
 338             break;
 339         }
 340
 341         case NewTypedArray: {
 342             // Negative zero is not observable. NaN versus undefined are only observable
 343             // in that you would get a different exception message. So, like, whatever: we
 344             // claim here that NaN v. undefined is observable.
 345             node->child1()->mergeFlags(NodeBytecodeUsesAsInt | NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsArrayIndex);
 346             break;
 347         }
 348
 349         case StringCharAt: {
 350             node->child1()->mergeFlags(NodeBytecodeUsesAsValue);
 351             node->child2()->mergeFlags(NodeBytecodeUsesAsValue | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
 352             break;
 353         }
 354
 355         case ToString:
 356         case CallStringConstructor: {
 357             node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
 358             break;
 359         }
 360
 361         case ToPrimitive: {
 362             node->child1()->mergeFlags(flags);
 363             break;
 364         }
 365
 366         case PutByValDirect:
 367         case PutByVal: {
 368             m_graph.varArgChild(node, 0)->mergeFlags(NodeBytecodeUsesAsValue);
 369             m_graph.varArgChild(node, 1)->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther | NodeBytecodeUsesAsInt | NodeBytecodeUsesAsArrayIndex);
 370             m_graph.varArgChild(node, 2)->mergeFlags(NodeBytecodeUsesAsValue);
 371             break;
 372         }
 373
 374         case Switch: {
 375             SwitchData* data = node->switchData();
 376             switch (data->kind) {
 377             case SwitchImm:
 378                 // We don't need NodeBytecodeNeedsNegZero because if the cases are all integers
 379                 // then -0 and 0 are treated the same.  We don't need NodeBytecodeUsesAsOther
 380                 // because if all of the cases are integers then NaN and undefined are
 381                 // treated the same (i.e. they will take default).
 382                 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsInt);
 383                 break;
 384             case SwitchChar: {
 385                 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings
 386                 // then -0 and 0 are treated the same.  We don't need NodeBytecodeUsesAsOther
 387                 // because if all of the cases are single-character strings then NaN
 388                 // and undefined are treated the same (i.e. they will take default).
 389                 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber);
 390                 break;
 391             }
 392             case SwitchString:
 393                 // We don't need NodeBytecodeNeedsNegZero because if the cases are all strings
 394                 // then -0 and 0 are treated the same.
 395                 node->child1()->mergeFlags(NodeBytecodeUsesAsNumber | NodeBytecodeUsesAsOther);
 396                 break;
 397             case SwitchCell:
 398                 // There is currently no point to being clever here since this is used for switching
 399                 // on objects.
 400                 mergeDefaultFlags(node);
 401                 break;
 402             }
 403             break;
 404         }
 405
 406         case Identity:
 407             // This would be trivial to handle but we just assert that we cannot see these yet.
 408             RELEASE_ASSERT_NOT_REACHED();
 409             break;
 410
 411         // Note: ArithSqrt, ArithSin, and ArithCos and other math intrinsics don't have special
 412         // rules in here because they are always followed by Phantoms to signify that if the
 413         // method call speculation fails, the bytecode may use the arguments in arbitrary ways.
 414         // This corresponds to that possibility of someone doing something like:
 415         // Math.sin = function(x) { doArbitraryThingsTo(x); }
 416
 417         default:
 418             mergeDefaultFlags(node);
 419             break;
 420         }
 421     }
 422
 423     bool m_allowNestedOverflowingAdditions;
 424     bool m_changed;
 425 };
 426
 427 bool performBackwardsPropagation(Graph& graph)
 428 {
 429     SamplingRegion samplingRegion("DFG Backwards Propagation Phase");
 430     return runPhase<BackwardsPropagationPhase>(graph);
 431 }
 432
 433 } } // namespace JSC::DFG
 434
 435 #endif // ENABLE(DFG_JIT)
 436