dfg/DFGCFGSimplificationPhase.cpp

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