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 39namespace JSC { namespace DFG { 40 41class CFGSimplificationPhase : public Phase { 42public: 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 249private: 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 371bool 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 382