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