dfg/DFGCFGSimplificationPhase.cpp

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