code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/dfg/DFGPropagator.cpp

   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 #include "config.h"
  27 #include "DFGPropagator.h"
  28
  29 #if ENABLE(DFG_JIT) && ENABLE(DYNAMIC_OPTIMIZATION)
  30
  31 #include "DFGGraph.h"
  32
  33 namespace JSC { namespace DFG {
  34
  35 class Propagator {
  36 public:
  37     Propagator(Graph& graph, JSGlobalData& globalData, CodeBlock* codeBlock, CodeBlock* profiledBlock)
  38         : m_graph(graph)
  39         , m_globalData(globalData)
  40         , m_codeBlock(codeBlock)
  41         , m_profiledBlock(profiledBlock)
  42     {
  43         // Predictions is a forward flow property that propagates the values seen at
  44         // a particular value source to their various uses, ensuring that uses perform
  45         // speculation that does not contravene the expected values.
  46         m_predictions.resize(m_graph.size());
  47
  48         // Uses is a backward flow property that propagates the hard expectations at
  49         // certain uses to their value sources, ensuring that predictions about
  50         // values do not contravene the code itself. This comes up only in the
  51         // cases of obvious cell uses, like GetById and friends as well as Call.
  52         // We're essentially statically speculating that if the value profile indicates
  53         // that only booleans (for example) flow into a GetById, then the value
  54         // profile is simply wrong due to insufficient coverage and needs to be
  55         // adjusted accordingly. The alternatives would be to assume either
  56         // that the GetById never executes, or always executes on a boolean leading
  57         // to whatever bizarre behavior that's supposed to cause.
  58         m_uses.resize(m_graph.size());
  59         m_variableUses.initializeSimilarTo(m_graph.predictions());
  60
  61         for (unsigned i = 0; i < m_graph.size(); ++i) {
  62             m_predictions[i] = PredictNone;
  63             m_uses[i] = PredictNone;
  64         }
  65     }
  66
  67     void fixpoint()
  68     {
  69 #if ENABLE(DFG_DEBUG_VERBOSE)
  70         m_count = 0;
  71 #endif
  72         do {
  73             m_changed = false;
  74
  75             // Forward propagation is near-optimal for both topologically-sorted and
  76             // DFS-sorted code.
  77             propagateForward();
  78             if (!m_changed)
  79                 break;
  80
  81             // Backward propagation reduces the likelihood that pathological code will
  82             // cause slowness. Loops (especially nested ones) resemble backward flow.
  83             // This pass captures two cases: (1) it detects if the forward fixpoint
  84             // found a sound solution and (2) short-circuits backward flow.
  85             m_changed = false;
  86             propagateBackward();
  87         } while (m_changed);
  88
  89         fixup();
  90     }
  91
  92 private:
  93     bool setPrediction(PredictedType prediction)
  94     {
  95         ASSERT(m_graph[m_compileIndex].hasResult());
  96
  97         if (m_predictions[m_compileIndex] == prediction)
  98             return false;
  99
 100         m_predictions[m_compileIndex] = prediction;
 101         return true;
 102     }
 103
 104     bool mergeUse(NodeIndex nodeIndex, PredictedType prediction)
 105     {
 106         ASSERT(m_graph[nodeIndex].hasResult());
 107
 108         return JSC::mergePrediction(m_uses[nodeIndex], prediction);
 109     }
 110
 111     bool mergePrediction(PredictedType prediction)
 112     {
 113         ASSERT(m_graph[m_compileIndex].hasResult());
 114
 115         return JSC::mergePrediction(m_predictions[m_compileIndex], prediction);
 116     }
 117
 118     void propagateNode(Node& node)
 119     {
 120         if (!node.shouldGenerate())
 121             return;
 122
 123         NodeType op = node.op;
 124
 125 #if ENABLE(DFG_DEBUG_VERBOSE)
 126         printf("   %s[%u]: ", Graph::opName(op), m_compileIndex);
 127 #endif
 128
 129         bool changed = false;
 130
 131         switch (op) {
 132         case JSConstant: {
 133             changed |= setPrediction(makePrediction(predictionFromValue(node.valueOfJSConstant(m_codeBlock)), StrongPrediction));
 134             break;
 135         }
 136
 137         case GetLocal: {
 138             changed |= m_graph.predict(node.local(), m_uses[m_compileIndex] & ~PredictionTagMask, StrongPrediction);
 139             changed |= m_variableUses.predict(node.local(), m_uses[m_compileIndex] & ~PredictionTagMask, StrongPrediction);
 140
 141             PredictedType prediction = m_graph.getPrediction(node.local());
 142             if (isStrongPrediction(prediction))
 143                 changed |= mergePrediction(prediction);
 144             break;
 145         }
 146
 147         case SetLocal: {
 148             changed |= m_graph.predict(node.local(), m_predictions[node.child1()] & ~PredictionTagMask, StrongPrediction);
 149             changed |= mergeUse(node.child1(), m_variableUses.getPrediction(node.local()));
 150             break;
 151         }
 152
 153         case BitAnd:
 154         case BitOr:
 155         case BitXor:
 156         case BitRShift:
 157         case BitLShift:
 158         case BitURShift:
 159         case UInt32ToNumber:
 160         case ValueToInt32:
 161         case ArithMod: {
 162             changed |= setPrediction(makePrediction(PredictInt32, StrongPrediction));
 163             break;
 164         }
 165
 166         case ValueToNumber: {
 167             PredictedType prediction = m_predictions[node.child1()];
 168
 169             if (isStrongPrediction(prediction)) {
 170                 if (isNumberPrediction(prediction))
 171                     changed |= mergePrediction(prediction);
 172                 else
 173                     changed |= mergePrediction(makePrediction(PredictNumber, StrongPrediction));
 174             }
 175
 176             break;
 177         }
 178
 179         case ValueAdd: {
 180             PredictedType left = m_predictions[node.child1()];
 181             PredictedType right = m_predictions[node.child2()];
 182
 183             if (isStrongPrediction(left) && isStrongPrediction(right)) {
 184                 if (isNumberPrediction(left) && isNumberPrediction(right)) {
 185                     if (isInt32Prediction(mergePredictions(left, right)))
 186                         changed |= mergePrediction(makePrediction(PredictInt32, StrongPrediction));
 187                     else
 188                         changed |= mergePrediction(makePrediction(PredictDouble, StrongPrediction));
 189                 } else if (!(left & PredictNumber) || !(right & PredictNumber)) {
 190                     // left or right is definitely something other than a number.
 191                     changed |= mergePrediction(makePrediction(PredictString, StrongPrediction));
 192                 } else
 193                     changed |= mergePrediction(makePrediction(PredictString | PredictInt32 | PredictDouble, StrongPrediction));
 194             }
 195             break;
 196         }
 197
 198         case ArithAdd:
 199         case ArithSub:
 200         case ArithMul: {
 201             PredictedType left = m_predictions[node.child1()];
 202             PredictedType right = m_predictions[node.child2()];
 203
 204             if (isStrongPrediction(left) && isStrongPrediction(right)) {
 205                 if (isInt32Prediction(mergePredictions(left, right)))
 206                     changed |= mergePrediction(makePrediction(PredictInt32, StrongPrediction));
 207                 else
 208                     changed |= mergePrediction(makePrediction(PredictDouble, StrongPrediction));
 209             }
 210             break;
 211         }
 212
 213         case ArithDiv: {
 214             changed |= setPrediction(makePrediction(PredictDouble, StrongPrediction));
 215             break;
 216         }
 217
 218         case LogicalNot:
 219         case CompareLess:
 220         case CompareLessEq:
 221         case CompareGreater:
 222         case CompareGreaterEq:
 223         case CompareEq:
 224         case CompareStrictEq:
 225         case InstanceOf: {
 226             changed |= setPrediction(makePrediction(PredictBoolean, StrongPrediction));
 227             break;
 228         }
 229
 230         case GetById:
 231         case GetMethod:
 232         case GetByVal: {
 233             changed |= mergeUse(node.child1(), PredictObjectUnknown | StrongPredictionTag);
 234             changed |= node.predict(m_uses[m_compileIndex] & ~PredictionTagMask, StrongPrediction);
 235             if (isStrongPrediction(node.getPrediction()))
 236                 changed |= setPrediction(node.getPrediction());
 237             break;
 238         }
 239
 240         case Call:
 241         case Construct: {
 242             changed |= mergeUse(m_graph.m_varArgChildren[node.firstChild()], PredictObjectUnknown | StrongPredictionTag);
 243             changed |= node.predict(m_uses[m_compileIndex] & ~PredictionTagMask, StrongPrediction);
 244             if (isStrongPrediction(node.getPrediction()))
 245                 changed |= setPrediction(node.getPrediction());
 246             break;
 247         }
 248
 249         case ConvertThis: {
 250             changed |= setPrediction(makePrediction(PredictObjectUnknown, StrongPrediction));
 251             break;
 252         }
 253
 254         case GetGlobalVar: {
 255             changed |= m_variableUses.predictGlobalVar(node.varNumber(), m_uses[m_compileIndex] & ~PredictionTagMask, StrongPrediction);
 256             PredictedType prediction = m_graph.getGlobalVarPrediction(node.varNumber());
 257             if (isStrongPrediction(prediction))
 258                 changed |= mergePrediction(prediction);
 259             break;
 260         }
 261
 262         case PutGlobalVar: {
 263             changed |= m_graph.predictGlobalVar(node.varNumber(), m_predictions[node.child1()] & ~PredictionTagMask, StrongPrediction);
 264             changed |= mergeUse(node.child1(), m_variableUses.getGlobalVarPrediction(node.varNumber()));
 265             break;
 266         }
 267
 268         case PutByVal:
 269         case PutByValAlias:
 270         case PutById:
 271         case PutByIdDirect: {
 272             changed |= mergeUse(node.child1(), PredictObjectUnknown | StrongPredictionTag);
 273             break;
 274         }
 275
 276 #ifndef NDEBUG
 277         // These get ignored because they don't return anything.
 278         case DFG::Jump:
 279         case Branch:
 280         case Return:
 281         case CheckHasInstance:
 282         case Phi:
 283             break;
 284
 285         // These get ignored because we don't have profiling for them, yet.
 286         case Resolve:
 287         case ResolveBase:
 288         case ResolveBaseStrictPut:
 289             break;
 290
 291         default:
 292             ASSERT_NOT_REACHED();
 293             break;
 294 #else
 295         default:
 296             break;
 297 #endif
 298         }
 299
 300 #if ENABLE(DFG_DEBUG_VERBOSE)
 301         printf("expect(%s) ", predictionToString(m_predictions[m_compileIndex]));
 302         printf("use(%s) %s\n", predictionToString(m_uses[m_compileIndex]), changed ? "CHANGED" : "");
 303 #endif
 304
 305         m_changed |= changed;
 306     }
 307
 308     void propagateForward()
 309     {
 310 #if ENABLE(DFG_DEBUG_VERBOSE)
 311         printf("Propagating forward [%u]\n", ++m_count);
 312 #endif
 313         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
 314             propagateNode(m_graph[m_compileIndex]);
 315     }
 316
 317     void propagateBackward()
 318     {
 319 #if ENABLE(DFG_DEBUG_VERBOSE)
 320         printf("Propagating backward [%u]\n", ++m_count);
 321 #endif
 322         for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
 323             propagateNode(m_graph[m_compileIndex]);
 324     }
 325
 326     void toDouble(NodeIndex nodeIndex)
 327     {
 328         if (m_graph[nodeIndex].op == ValueToNumber) {
 329 #if ENABLE(DFG_DEBUG_VERBOSE)
 330             printf("  @%u -> ValueToDouble", nodeIndex);
 331 #endif
 332             m_graph[nodeIndex].op = ValueToDouble;
 333         }
 334     }
 335
 336     void fixupNode(Node& node)
 337     {
 338         if (!node.shouldGenerate())
 339             return;
 340
 341         NodeType op = node.op;
 342
 343 #if ENABLE(DFG_DEBUG_VERBOSE)
 344         printf("   %s[%u]: ", Graph::opName(op), m_compileIndex);
 345 #endif
 346
 347         switch (op) {
 348         case ValueAdd: {
 349             PredictedType left = m_predictions[node.child1()];
 350             PredictedType right = m_predictions[node.child2()];
 351
 352             if (isStrongPrediction(left) && isStrongPrediction(right) && isNumberPrediction(left) && isNumberPrediction(right)) {
 353                 if (left & PredictDouble)
 354                     toDouble(node.child2());
 355                 if (right & PredictDouble)
 356                     toDouble(node.child1());
 357             }
 358             break;
 359         }
 360
 361         case ArithAdd:
 362         case ArithSub:
 363         case ArithMul: {
 364             PredictedType left = m_predictions[node.child1()];
 365             PredictedType right = m_predictions[node.child2()];
 366
 367             if (isStrongPrediction(left) && isStrongPrediction(right)) {
 368                 if (left & PredictDouble)
 369                     toDouble(node.child2());
 370                 if (right & PredictDouble)
 371                     toDouble(node.child1());
 372             }
 373             break;
 374         }
 375
 376         case ArithDiv: {
 377             toDouble(node.child1());
 378             toDouble(node.child2());
 379             break;
 380         }
 381
 382         default:
 383             break;
 384         }
 385
 386 #if ENABLE(DFG_DEBUG_VERBOSE)
 387         printf("\n");
 388 #endif
 389     }
 390
 391     void fixup()
 392     {
 393 #if ENABLE(DFG_DEBUG_VERBOSE)
 394         printf("Performing Fixup\n");
 395 #endif
 396         for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
 397             fixupNode(m_graph[m_compileIndex]);
 398     }
 399
 400     Graph& m_graph;
 401     JSGlobalData& m_globalData;
 402     CodeBlock* m_codeBlock;
 403     CodeBlock* m_profiledBlock;
 404
 405     NodeIndex m_compileIndex;
 406
 407     Vector<PredictedType, 16> m_predictions;
 408     Vector<PredictedType, 16> m_uses;
 409
 410     PredictionTracker m_variableUses;
 411
 412 #if ENABLE(DFG_DEBUG_VERBOSE)
 413     unsigned m_count;
 414 #endif
 415
 416     bool m_changed;
 417 };
 418
 419 void propagate(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
 420 {
 421     ASSERT(codeBlock);
 422     CodeBlock* profiledBlock = codeBlock->alternative();
 423     ASSERT(profiledBlock);
 424
 425     Propagator propagator(graph, *globalData, codeBlock, profiledBlock);
 426     propagator.fixpoint();
 427
 428 #if ENABLE(DFG_DEBUG_VERBOSE)
 429     graph.dump(codeBlock);
 430 #endif
 431 }
 432
 433 } } // namespace JSC::DFG
 434
 435 #endif // ENABLE(DFG_JIT) && ENABLE(DYNAMIC_OPTIMIZATION)
 436