1/* 2 * Copyright (C) 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 "DFGLICMPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGAbstractInterpreterInlines.h" 32#include "DFGAtTailAbstractState.h" 33#include "DFGBasicBlockInlines.h" 34#include "DFGClobberSet.h" 35#include "DFGClobberize.h" 36#include "DFGEdgeDominates.h" 37#include "DFGGraph.h" 38#include "DFGInsertionSet.h" 39#include "DFGPhase.h" 40#include "DFGSafeToExecute.h" 41#include "JSCInlines.h" 42 43namespace JSC { namespace DFG { 44 45namespace { 46 47struct LoopData { 48 LoopData() 49 : preHeader(0) 50 { 51 } 52 53 ClobberSet writes; 54 BasicBlock* preHeader; 55}; 56 57} // anonymous namespace 58 59class LICMPhase : public Phase { 60 static const bool verbose = false; 61 62public: 63 LICMPhase(Graph& graph) 64 : Phase(graph, "LICM") 65 , m_interpreter(graph, m_state) 66 { 67 } 68 69 bool run() 70 { 71 ASSERT(m_graph.m_form == SSA); 72 73 m_graph.m_dominators.computeIfNecessary(m_graph); 74 m_graph.m_naturalLoops.computeIfNecessary(m_graph); 75 76 m_data.resize(m_graph.m_naturalLoops.numLoops()); 77 78 // Figure out the set of things each loop writes to, not including blocks that 79 // belong to inner loops. We fix this later. 80 for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) { 81 BasicBlock* block = m_graph.block(blockIndex); 82 if (!block) 83 continue; 84 85 // Skip blocks that are proved to not execute. 86 // FIXME: This shouldn't be needed. 87 // https://bugs.webkit.org/show_bug.cgi?id=128584 88 if (!block->cfaHasVisited) 89 continue; 90 91 const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block); 92 if (!loop) 93 continue; 94 LoopData& data = m_data[loop->index()]; 95 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { 96 Node* node = block->at(nodeIndex); 97 98 // Don't look beyond parts of the code that definitely always exit. 99 // FIXME: This shouldn't be needed. 100 // https://bugs.webkit.org/show_bug.cgi?id=128584 101 if (node->op() == ForceOSRExit) 102 break; 103 104 addWrites(m_graph, node, data.writes); 105 } 106 } 107 108 // For each loop: 109 // - Identify its pre-header. 110 // - Make sure its outer loops know what it clobbers. 111 for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) { 112 const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex); 113 LoopData& data = m_data[loop.index()]; 114 for ( 115 const NaturalLoop* outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(loop); 116 outerLoop; 117 outerLoop = m_graph.m_naturalLoops.innerMostOuterLoop(*outerLoop)) 118 m_data[outerLoop->index()].writes.addAll(data.writes); 119 120 BasicBlock* header = loop.header(); 121 BasicBlock* preHeader = 0; 122 for (unsigned i = header->predecessors.size(); i--;) { 123 BasicBlock* predecessor = header->predecessors[i]; 124 if (m_graph.m_dominators.dominates(header, predecessor)) 125 continue; 126 RELEASE_ASSERT(!preHeader || preHeader == predecessor); 127 preHeader = predecessor; 128 } 129 130 RELEASE_ASSERT(preHeader->last()->op() == Jump); 131 132 data.preHeader = preHeader; 133 } 134 135 m_graph.initializeNodeOwners(); 136 137 // Walk all basic blocks that belong to loops, looking for hoisting opportunities. 138 // We try to hoist to the outer-most loop that permits it. Hoisting is valid if: 139 // - The node doesn't write anything. 140 // - The node doesn't read anything that the loop writes. 141 // - The preHeader's state at tail makes the node safe to execute. 142 // - The loop's children all belong to nodes that strictly dominate the loop header. 143 // - The preHeader's state at tail is still valid. This is mostly to save compile 144 // time and preserve some kind of sanity, if we hoist something that must exit. 145 // 146 // Also, we need to remember to: 147 // - Update the state-at-tail with the node we hoisted, so future hoist candidates 148 // know about any type checks we hoisted. 149 // 150 // For maximum profit, we walk blocks in DFS order to ensure that we generally 151 // tend to hoist dominators before dominatees. 152 Vector<BasicBlock*> depthFirst; 153 m_graph.getBlocksInDepthFirstOrder(depthFirst); 154 Vector<const NaturalLoop*> loopStack; 155 bool changed = false; 156 for ( 157 unsigned depthFirstIndex = 0; 158 depthFirstIndex < depthFirst.size(); 159 ++depthFirstIndex) { 160 161 BasicBlock* block = depthFirst[depthFirstIndex]; 162 const NaturalLoop* loop = m_graph.m_naturalLoops.innerMostLoopOf(block); 163 if (!loop) 164 continue; 165 166 loopStack.resize(0); 167 for ( 168 const NaturalLoop* current = loop; 169 current; 170 current = m_graph.m_naturalLoops.innerMostOuterLoop(*current)) 171 loopStack.append(current); 172 173 // Remember: the loop stack has the inner-most loop at index 0, so if we want 174 // to bias hoisting to outer loops then we need to use a reverse loop. 175 176 if (verbose) { 177 dataLog( 178 "Attempting to hoist out of block ", *block, " in loops:\n"); 179 for (unsigned stackIndex = loopStack.size(); stackIndex--;) { 180 dataLog( 181 " ", *loopStack[stackIndex], ", which writes ", 182 m_data[loopStack[stackIndex]->index()].writes, "\n"); 183 } 184 } 185 186 for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) { 187 Node*& nodeRef = block->at(nodeIndex); 188 if (doesWrites(m_graph, nodeRef)) { 189 if (verbose) 190 dataLog(" Not hoisting ", nodeRef, " because it writes things.\n"); 191 continue; 192 } 193 194 for (unsigned stackIndex = loopStack.size(); stackIndex--;) 195 changed |= attemptHoist(block, nodeRef, loopStack[stackIndex]); 196 } 197 } 198 199 return changed; 200 } 201 202private: 203 bool attemptHoist(BasicBlock* fromBlock, Node*& nodeRef, const NaturalLoop* loop) 204 { 205 Node* node = nodeRef; 206 LoopData& data = m_data[loop->index()]; 207 208 if (!data.preHeader->cfaDidFinish) { 209 if (verbose) 210 dataLog(" Not hoisting ", node, " because CFA is invalid.\n"); 211 return false; 212 } 213 214 if (!edgesDominate(m_graph, node, data.preHeader)) { 215 if (verbose) { 216 dataLog( 217 " Not hoisting ", node, " because it isn't loop invariant.\n"); 218 } 219 return false; 220 } 221 222 if (readsOverlap(m_graph, node, data.writes)) { 223 if (verbose) { 224 dataLog( 225 " Not hoisting ", node, 226 " because it reads things that the loop writes.\n"); 227 } 228 return false; 229 } 230 231 m_state.initializeTo(data.preHeader); 232 if (!safeToExecute(m_state, m_graph, node)) { 233 if (verbose) { 234 dataLog( 235 " Not hoisting ", node, " because it isn't safe to execute.\n"); 236 } 237 return false; 238 } 239 240 if (verbose) { 241 dataLog( 242 " Hoisting ", node, " from ", *fromBlock, " to ", *data.preHeader, 243 "\n"); 244 } 245 246 data.preHeader->insertBeforeLast(node); 247 node->misc.owner = data.preHeader; 248 NodeOrigin originalOrigin = node->origin; 249 node->origin.forExit = data.preHeader->last()->origin.forExit; 250 251 // Modify the states at the end of the preHeader of the loop we hoisted to, 252 // and all pre-headers inside the loop. 253 // FIXME: This could become a scalability bottleneck. Fortunately, most loops 254 // are small and anyway we rapidly skip over basic blocks here. 255 for (unsigned bodyIndex = loop->size(); bodyIndex--;) { 256 BasicBlock* subBlock = loop->at(bodyIndex); 257 const NaturalLoop* subLoop = m_graph.m_naturalLoops.headerOf(subBlock); 258 if (!subLoop) 259 continue; 260 BasicBlock* subPreHeader = m_data[subLoop->index()].preHeader; 261 if (!subPreHeader->cfaDidFinish) 262 continue; 263 m_state.initializeTo(subPreHeader); 264 m_interpreter.execute(node); 265 } 266 267 // It just so happens that all of the nodes we currently know how to hoist 268 // don't have var-arg children. That may change and then we can fix this 269 // code. But for now we just assert that's the case. 270 RELEASE_ASSERT(!(node->flags() & NodeHasVarArgs)); 271 272 nodeRef = m_graph.addNode(SpecNone, Phantom, originalOrigin, node->children); 273 274 return true; 275 } 276 277 AtTailAbstractState m_state; 278 AbstractInterpreter<AtTailAbstractState> m_interpreter; 279 Vector<LoopData> m_data; 280}; 281 282bool performLICM(Graph& graph) 283{ 284 SamplingRegion samplingRegion("DFG LICM Phase"); 285 return runPhase<LICMPhase>(graph); 286} 287 288} } // namespace JSC::DFG 289 290#endif // ENABLE(DFG_JIT) 291 292