Source/JavaScriptCore/dfg/DFGCFGSimplificationPhase.cpp

   1 /*
   2  * Copyright (C) 2012, 2013 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 "DFGCFGSimplificationPhase.h"
  28
  29 #if ENABLE(DFG_JIT)
  30
  31 #include "DFGBasicBlockInlines.h"
  32 #include "DFGGraph.h"
  33 #include "DFGInsertionSet.h"
  34 #include "DFGPhase.h"
  35 #include "DFGValidate.h"
  36 #include "Operations.h"
  37
  38 namespace JSC { namespace DFG {
  39
  40 class CFGSimplificationPhase : public Phase {
  41 public:
  42     CFGSimplificationPhase(Graph& graph)
  43         : Phase(graph, "CFG simplification")
  44     {
  45     }
  46
  47     bool run()
  48     {
  49         const bool extremeLogging = false;
  50
  51         bool outerChanged = false;
  52         bool innerChanged;
  53
  54         do {
  55             innerChanged = false;
  56             for (BlockIndex blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex) {
  57                 BasicBlock* block = m_graph.block(blockIndex);
  58                 if (!block)
  59                     continue;
  60                 ASSERT(block->isReachable);
  61
  62                 switch (block->last()->op()) {
  63                 case Jump: {
  64                     // Successor with one predecessor -> merge.
  65                     if (block->successor(0)->predecessors.size() == 1) {
  66                         ASSERT(block->successor(0)->predecessors[0] == block);
  67 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  68                         dataLog("CFGSimplify: Jump merge on Block ", *block, " to Block ", *block->successor(0), ".\n");
  69 #endif
  70                         if (extremeLogging)
  71                             m_graph.dump();
  72                         m_graph.dethread();
  73                         mergeBlocks(block, block->successor(0), noBlocks());
  74                         innerChanged = outerChanged = true;
  75                         break;
  76                     } else {
  77 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
  78                         dataLog("CFGSimplify: Not jump merging on Block ", *block, " to Block ", *block->successor(0), " because predecessors = ",);
  79                         for (unsigned i = 0; i < block->successor(0)->predecessors.size(); ++i) {
  80                             if (i)
  81                                 dataLogF(", ");
  82                             dataLog(*block->successor(0)->predecessors[i]);
  83                         }
  84                         dataLogF(".\n");
  85 #endif
  86                     }
  87
  88                     // FIXME: Block only has a jump -> remove. This is tricky though because of
  89                     // liveness. What we really want is to slam in a phantom at the end of the
  90                     // block, after the terminal. But we can't right now. :-(
  91                     // Idea: what if I slam the ghosties into my successor? Nope, that's
  92                     // suboptimal, because if my successor has multiple predecessors then we'll
  93                     // be keeping alive things on other predecessor edges unnecessarily.
  94                     // What we really need is the notion of end-of-block ghosties!
  95                     break;
  96                 }
  97
  98                 case Branch: {
  99                     // Branch on constant -> jettison the not-taken block and merge.
 100                     if (isKnownDirection(block->cfaBranchDirection)) {
 101                         bool condition = branchCondition(block->cfaBranchDirection);
 102                         BasicBlock* targetBlock = block->successorForCondition(condition);
 103                         BasicBlock* jettisonedBlock = block->successorForCondition(!condition);
 104                         if (targetBlock->predecessors.size() == 1) {
 105 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 106                             dataLog(
 107                                 "CFGSimplify: Known condition (", condition, ") branch merge ",
 108                                 "on Block ", *block, " to Block ", *targetBlock,
 109                                 ", jettisoning Block ", *jettisonedBlock, ".\n");
 110 #endif
 111                             if (extremeLogging)
 112                                 m_graph.dump();
 113                             m_graph.dethread();
 114                             mergeBlocks(block, targetBlock, oneBlock(jettisonedBlock));
 115                         } else {
 116 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 117                             dataLog(
 118                                 "CFGSimplify: Known condition (", condition, ") ",
 119                                 "branch->jump conversion on Block ", *block, " to Block ",
 120                                 targetBlock, ", jettisoning Block ", jettisonedBlock, ".\n");
 121 #endif
 122                             if (extremeLogging)
 123                                 m_graph.dump();
 124                             m_graph.dethread();
 125
 126                             ASSERT(block->last()->isTerminal());
 127                             CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin;
 128                             block->last()->convertToPhantom();
 129                             ASSERT(block->last()->refCount() == 1);
 130
 131                             jettisonBlock(block, jettisonedBlock, boundaryCodeOrigin);
 132
 133                             block->appendNode(
 134                                 m_graph, SpecNone, Jump, boundaryCodeOrigin,
 135                                 OpInfo(targetBlock));
 136                         }
 137                         innerChanged = outerChanged = true;
 138                         break;
 139                     }
 140
 141                     if (block->successor(0) == block->successor(1)) {
 142                         convertToJump(block, block->successor(0));
 143                         innerChanged = outerChanged = true;
 144                         break;
 145                     }
 146
 147 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 148                     dataLogF("Not branch simplifying on Block #%u because the successors differ and the condition is not known.\n",
 149                             blockIndex);
 150 #endif
 151
 152                     // Branch to same destination -> jump.
 153                     // FIXME: this will currently not be hit because of the lack of jump-only
 154                     // block simplification.
 155
 156                     break;
 157                 }
 158
 159                 case Switch: {
 160                     SwitchData* data = block->last()->switchData();
 161
 162                     // Prune out cases that end up jumping to default.
 163                     for (unsigned i = 0; i < data->cases.size(); ++i) {
 164                         if (data->cases[i].target == data->fallThrough)
 165                             data->cases[i--] = data->cases.takeLast();
 166                     }
 167
 168                     // If there are no cases other than default then this turns
 169                     // into a jump.
 170                     if (data->cases.isEmpty()) {
 171                         convertToJump(block, data->fallThrough);
 172                         innerChanged = outerChanged = true;
 173                         break;
 174                     }
 175
 176                     // Switch on constant -> jettison all other targets and merge.
 177                     if (block->last()->child1()->hasConstant()) {
 178                         JSValue value = m_graph.valueOfJSConstant(block->last()->child1().node());
 179                         TriState found = FalseTriState;
 180                         BasicBlock* targetBlock = 0;
 181                         for (unsigned i = data->cases.size(); found == FalseTriState && i--;) {
 182                             found = data->cases[i].value.strictEqual(value);
 183                             if (found == TrueTriState)
 184                                 targetBlock = data->cases[i].target;
 185                         }
 186
 187                         if (found == MixedTriState)
 188                             break;
 189                         if (found == FalseTriState)
 190                             targetBlock = data->fallThrough;
 191                         ASSERT(targetBlock);
 192
 193                         Vector<BasicBlock*, 1> jettisonedBlocks;
 194                         for (unsigned i = block->numSuccessors(); i--;) {
 195                             BasicBlock* jettisonedBlock = block->successor(i);
 196                             if (jettisonedBlock != targetBlock)
 197                                 jettisonedBlocks.append(jettisonedBlock);
 198                         }
 199
 200                         if (targetBlock->predecessors.size() == 1) {
 201 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 202                             dataLog(
 203                                 "CFGSimplify: Known constant (", value, ") switch merge on ",
 204                                 "Block ", *block, " to Block ", *targetBlock, ".\n");
 205 #endif
 206
 207                             if (extremeLogging)
 208                                 m_graph.dump();
 209                             m_graph.dethread();
 210
 211                             mergeBlocks(block, targetBlock, jettisonedBlocks);
 212                         } else {
 213 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 214                             dataLog(
 215                                 "CFGSimplify: Known constant (", value, ") switch->jump "
 216                                 "conversion on Block ", *block, " to Block #",
 217                                 *targetBlock, ".\n");
 218 #endif
 219                             if (extremeLogging)
 220                                 m_graph.dump();
 221                             m_graph.dethread();
 222
 223                             CodeOrigin boundaryCodeOrigin = block->last()->codeOrigin;
 224                             block->last()->convertToPhantom();
 225                             for (unsigned i = jettisonedBlocks.size(); i--;)
 226                                 jettisonBlock(block, jettisonedBlocks[i], boundaryCodeOrigin);
 227                             block->appendNode(
 228                                 m_graph, SpecNone, Jump, boundaryCodeOrigin, OpInfo(targetBlock));
 229                         }
 230                         innerChanged = outerChanged = true;
 231                         break;
 232                     }
 233                 }
 234
 235                 default:
 236                     break;
 237                 }
 238             }
 239
 240             if (innerChanged) {
 241                 // Here's the reason for this pass:
 242                 // Blocks: A, B, C, D, E, F
 243                 // A -> B, C
 244                 // B -> F
 245                 // C -> D, E
 246                 // D -> F
 247                 // E -> F
 248                 //
 249                 // Assume that A's branch is determined to go to B. Then the rest of this phase
 250                 // is smart enough to simplify down to:
 251                 // A -> B
 252                 // B -> F
 253                 // C -> D, E
 254                 // D -> F
 255                 // E -> F
 256                 //
 257                 // We will also merge A and B. But then we don't have any other mechanism to
 258                 // remove D, E as predecessors for F. Worse, the rest of this phase does not
 259                 // know how to fix the Phi functions of F to ensure that they no longer refer
 260                 // to variables in D, E. In general, we need a way to handle Phi simplification
 261                 // upon:
 262                 // 1) Removal of a predecessor due to branch simplification. The branch
 263                 //    simplifier already does that.
 264                 // 2) Invalidation of a predecessor because said predecessor was rendered
 265                 //    unreachable. We do this here.
 266                 //
 267                 // This implies that when a block is unreachable, we must inspect its
 268                 // successors' Phi functions to remove any references from them into the
 269                 // removed block.
 270
 271                 m_graph.invalidateCFG();
 272                 m_graph.resetReachability();
 273                 m_graph.killUnreachableBlocks();
 274             }
 275
 276             if (Options::validateGraphAtEachPhase())
 277                 validate(m_graph);
 278         } while (innerChanged);
 279
 280         return outerChanged;
 281     }
 282
 283 private:
 284     void convertToJump(BasicBlock* block, BasicBlock* targetBlock)
 285     {
 286         ASSERT(targetBlock);
 287         ASSERT(targetBlock->isReachable);
 288         if (targetBlock->predecessors.size() == 1) {
 289 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 290             dataLog(
 291                 "CFGSimplify: Branch/Switch to same successor merge on Block ", *block,
 292                 " to Block ", *targetBlock, ".\n");
 293 #endif
 294             m_graph.dethread();
 295             mergeBlocks(block, targetBlock, noBlocks());
 296         } else {
 297 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 298             dataLog(
 299                 "CFGSimplify: Branch->jump conversion to same successor on Block ",
 300                 *block, " to Block ", *targetBlock, ".\n",
 301 #endif
 302             Node* branch = block->last();
 303             ASSERT(branch->isTerminal());
 304             ASSERT(branch->op() == Branch || branch->op() == Switch);
 305             branch->convertToPhantom();
 306             ASSERT(branch->refCount() == 1);
 307
 308             block->appendNode(
 309                 m_graph, SpecNone, Jump, branch->codeOrigin,
 310                 OpInfo(targetBlock));
 311         }
 312     }
 313
 314     void keepOperandAlive(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin codeOrigin, VirtualRegister operand)
 315     {
 316         Node* livenessNode = jettisonedBlock->variablesAtHead.operand(operand);
 317         if (!livenessNode)
 318             return;
 319         if (livenessNode->variableAccessData()->isCaptured())
 320             return;
 321         block->appendNode(
 322             m_graph, SpecNone, PhantomLocal, codeOrigin,
 323             OpInfo(livenessNode->variableAccessData()));
 324     }
 325
 326     void jettisonBlock(BasicBlock* block, BasicBlock* jettisonedBlock, CodeOrigin boundaryCodeOrigin)
 327     {
 328         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
 329             keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, virtualRegisterForArgument(i));
 330         for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
 331             keepOperandAlive(block, jettisonedBlock, boundaryCodeOrigin, virtualRegisterForLocal(i));
 332
 333         fixJettisonedPredecessors(block, jettisonedBlock);
 334     }
 335
 336     void fixJettisonedPredecessors(BasicBlock* block, BasicBlock* jettisonedBlock)
 337     {
 338 #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
 339         dataLog(
 340             "Fixing predecessors and phis due to jettison of Block ", *jettisonedBlock,
 341             " from Block ", *block, ".\n");
 342 #endif
 343         jettisonedBlock->removePredecessor(block);
 344     }
 345
 346     Vector<BasicBlock*, 1> noBlocks()
 347     {
 348         return Vector<BasicBlock*, 1>();
 349     }
 350
 351     Vector<BasicBlock*, 1> oneBlock(BasicBlock* block)
 352     {
 353         Vector<BasicBlock*, 1> result;
 354         result.append(block);
 355         return result;
 356     }
 357
 358     void mergeBlocks(
 359         BasicBlock* firstBlock, BasicBlock* secondBlock,
 360         Vector<BasicBlock*, 1> jettisonedBlocks)
 361     {
 362         // This will add all of the nodes in secondBlock to firstBlock, but in so doing
 363         // it will also ensure that any GetLocals from the second block that refer to
 364         // SetLocals in the first block are relinked. If jettisonedBlock is not NoBlock,
 365         // then Phantoms are inserted for anything that the jettisonedBlock would have
 366         // kept alive.
 367
 368         // Remove the terminal of firstBlock since we don't need it anymore. Well, we don't
 369         // really remove it; we actually turn it into a Phantom.
 370         ASSERT(firstBlock->last()->isTerminal());
 371         CodeOrigin boundaryCodeOrigin = firstBlock->last()->codeOrigin;
 372         firstBlock->last()->convertToPhantom();
 373         ASSERT(firstBlock->last()->refCount() == 1);
 374
 375         for (unsigned i = jettisonedBlocks.size(); i--;) {
 376             BasicBlock* jettisonedBlock = jettisonedBlocks[i];
 377
 378             // Time to insert ghosties for things that need to be kept alive in case we OSR
 379             // exit prior to hitting the firstBlock's terminal, and end up going down a
 380             // different path than secondBlock.
 381
 382             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfArguments(); ++i)
 383                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, virtualRegisterForArgument(i));
 384             for (size_t i = 0; i < jettisonedBlock->variablesAtHead.numberOfLocals(); ++i)
 385                 keepOperandAlive(firstBlock, jettisonedBlock, boundaryCodeOrigin, virtualRegisterForLocal(i));
 386         }
 387
 388         for (size_t i = 0; i < secondBlock->phis.size(); ++i)
 389             firstBlock->phis.append(secondBlock->phis[i]);
 390
 391         for (size_t i = 0; i < secondBlock->size(); ++i)
 392             firstBlock->append(secondBlock->at(i));
 393
 394         ASSERT(firstBlock->last()->isTerminal());
 395
 396         // Fix the predecessors of my new successors. This is tricky, since we are going to reset
 397         // all predecessors anyway due to reachability analysis. But we need to fix the
 398         // predecessors eagerly to ensure that we know what they are in case the next block we
 399         // consider in this phase wishes to query the predecessors of one of the blocks we
 400         // affected.
 401         for (unsigned i = firstBlock->numSuccessors(); i--;) {
 402             BasicBlock* successor = firstBlock->successor(i);
 403             for (unsigned j = 0; j < successor->predecessors.size(); ++j) {
 404                 if (successor->predecessors[j] == secondBlock)
 405                     successor->predecessors[j] = firstBlock;
 406             }
 407         }
 408
 409         // Fix the predecessors of my former successors. Again, we'd rather not do this, but it's
 410         // an unfortunate necessity. See above comment.
 411         for (unsigned i = jettisonedBlocks.size(); i--;)
 412             fixJettisonedPredecessors(firstBlock, jettisonedBlocks[i]);
 413
 414         firstBlock->valuesAtTail = secondBlock->valuesAtTail;
 415         firstBlock->cfaBranchDirection = secondBlock->cfaBranchDirection;
 416
 417         m_graph.killBlock(secondBlock);
 418     }
 419 };
 420
 421 bool performCFGSimplification(Graph& graph)
 422 {
 423     SamplingRegion samplingRegion("DFG CFG Simplification Phase");
 424     return runPhase<CFGSimplificationPhase>(graph);
 425 }
 426
 427 } } // namespace JSC::DFG
 428
 429 #endif // ENABLE(DFG_JIT)
 430
 431