dfg/DFGBackwardsPropagationPhase.cpp

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