1/* 2 * Copyright (C) 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 "DFGLoopPreHeaderCreationPhase.h" 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGBasicBlockInlines.h" 32#include "DFGBlockInsertionSet.h" 33#include "DFGGraph.h" 34#include "DFGPhase.h" 35#include "JSCInlines.h" 36#include <wtf/HashMap.h> 37 38namespace JSC { namespace DFG { 39 40BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block) 41{ 42 // Don't bother to preserve execution frequencies for now. 43 BasicBlock* preHeader = insertionSet.insertBefore(block, PNaN); 44 preHeader->appendNode( 45 graph, SpecNone, Jump, block->at(0)->origin, OpInfo(block)); 46 47 for (unsigned predecessorIndex = 0; predecessorIndex < block->predecessors.size(); predecessorIndex++) { 48 BasicBlock* predecessor = block->predecessors[predecessorIndex]; 49 if (graph.m_dominators.dominates(block, predecessor)) 50 continue; 51 block->predecessors[predecessorIndex--] = block->predecessors.last(); 52 block->predecessors.removeLast(); 53 for (unsigned successorIndex = predecessor->numSuccessors(); successorIndex--;) { 54 BasicBlock*& successor = predecessor->successor(successorIndex); 55 if (successor != block) 56 continue; 57 successor = preHeader; 58 preHeader->predecessors.append(predecessor); 59 } 60 } 61 62 block->predecessors.append(preHeader); 63 return preHeader; 64} 65 66class LoopPreHeaderCreationPhase : public Phase { 67public: 68 LoopPreHeaderCreationPhase(Graph& graph) 69 : Phase(graph, "loop pre-header creation") 70 , m_insertionSet(graph) 71 { 72 } 73 74 bool run() 75 { 76 m_graph.m_dominators.computeIfNecessary(m_graph); 77 m_graph.m_naturalLoops.computeIfNecessary(m_graph); 78 79 for (unsigned loopIndex = m_graph.m_naturalLoops.numLoops(); loopIndex--;) { 80 const NaturalLoop& loop = m_graph.m_naturalLoops.loop(loopIndex); 81 BasicBlock* existingPreHeader = 0; 82 bool needsNewPreHeader = false; 83 for (unsigned predecessorIndex = loop.header()->predecessors.size(); predecessorIndex--;) { 84 BasicBlock* predecessor = loop.header()->predecessors[predecessorIndex]; 85 if (m_graph.m_dominators.dominates(loop.header(), predecessor)) 86 continue; 87 if (!existingPreHeader) { 88 existingPreHeader = predecessor; 89 continue; 90 } 91 if (existingPreHeader == predecessor) 92 continue; 93 needsNewPreHeader = true; 94 break; 95 } 96 if (!needsNewPreHeader) 97 continue; 98 99 createPreHeader(m_graph, m_insertionSet, loop.header()); 100 } 101 102 return m_insertionSet.execute(); 103 } 104 105 BlockInsertionSet m_insertionSet; 106}; 107 108bool performLoopPreHeaderCreation(Graph& graph) 109{ 110 SamplingRegion samplingRegion("DFG Loop Pre-Header Creation Phase"); 111 return runPhase<LoopPreHeaderCreationPhase>(graph); 112} 113 114} } // namespace JSC::DFG 115 116#endif // ENABLE(DFG_JIT) 117 118 119