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 38namespace JSC { namespace DFG { 39 40class CFGSimplificationPhase : public Phase { 41public: 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 247private: 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 372bool 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 383