c43a64eb6c8b369d8107cea29b7a601ab4d9cac1
[WebKit-https.git] / Source / JavaScriptCore / dfg / DFGLoopPreHeaderCreationPhase.cpp
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
28 #if ENABLE(DFG_JIT)
29
30 #include "DFGLoopPreHeaderCreationPhase.h"
31
32 #include "DFGBasicBlockInlines.h"
33 #include "DFGBlockInsertionSet.h"
34 #include "DFGGraph.h"
35 #include "DFGPhase.h"
36 #include "JSCInlines.h"
37 #include <wtf/HashMap.h>
38
39 namespace JSC { namespace DFG {
40
41 BasicBlock* createPreHeader(Graph& graph, BlockInsertionSet& insertionSet, BasicBlock* block)
42 {
43     BasicBlock* preHeader = insertionSet.insertBefore(block);
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
66 class LoopPreHeaderCreationPhase : public Phase {
67 public:
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
108 bool 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