1/*
2 * Copyright (C) 2015-2016 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#pragma once
27
28#if ENABLE(B3_JIT)
29
30#include <wtf/GraphNodeWorklist.h>
31#include <wtf/IndexSet.h>
32#include <wtf/Vector.h>
33
34namespace JSC { namespace B3 {
35
36template<typename BasicBlock>
37bool addPredecessor(BasicBlock* block, BasicBlock* predecessor)
38{
39 auto& predecessors = block->predecessors();
40
41 if (predecessors.contains(predecessor))
42 return false;
43
44 predecessors.append(predecessor);
45 return true;
46}
47
48template<typename BasicBlock>
49bool removePredecessor(BasicBlock* block, BasicBlock* predecessor)
50{
51 auto& predecessors = block->predecessors();
52 for (unsigned i = 0; i < predecessors.size(); ++i) {
53 if (predecessors[i] == predecessor) {
54 predecessors[i--] = predecessors.last();
55 predecessors.removeLast();
56 ASSERT(!predecessors.contains(predecessor));
57 return true;
58 }
59 }
60 return false;
61}
62
63template<typename BasicBlock>
64bool replacePredecessor(BasicBlock* block, BasicBlock* from, BasicBlock* to)
65{
66 bool changed = false;
67 // We do it this way because 'to' may already be a predecessor of 'block'.
68 changed |= removePredecessor(block, from);
69 changed |= addPredecessor(block, to);
70 return changed;
71}
72
73template<typename BasicBlock>
74void updatePredecessorsAfter(BasicBlock* root)
75{
76 Vector<BasicBlock*, 16> worklist;
77 worklist.append(root);
78 while (!worklist.isEmpty()) {
79 BasicBlock* block = worklist.takeLast();
80 for (BasicBlock* successor : block->successorBlocks()) {
81 if (addPredecessor(successor, block))
82 worklist.append(successor);
83 }
84 }
85}
86
87template<typename BasicBlock>
88void clearPredecessors(Vector<std::unique_ptr<BasicBlock>>& blocks)
89{
90 for (auto& block : blocks) {
91 if (block)
92 block->predecessors().shrink(0);
93 }
94}
95
96template<typename BasicBlock>
97void recomputePredecessors(Vector<std::unique_ptr<BasicBlock>>& blocks)
98{
99 clearPredecessors(blocks);
100 updatePredecessorsAfter(blocks[0].get());
101}
102
103template<typename BasicBlock>
104bool isBlockDead(BasicBlock* block)
105{
106 if (!block)
107 return false;
108 if (!block->index())
109 return false;
110 return block->predecessors().isEmpty();
111}
112
113template<typename BasicBlock>
114Vector<BasicBlock*> blocksInPreOrder(BasicBlock* root)
115{
116 Vector<BasicBlock*> result;
117 GraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> worklist;
118 worklist.push(root);
119 while (BasicBlock* block = worklist.pop()) {
120 result.append(block);
121 for (BasicBlock* successor : block->successorBlocks())
122 worklist.push(successor);
123 }
124 return result;
125}
126
127template<typename BasicBlock>
128Vector<BasicBlock*> blocksInPostOrder(BasicBlock* root)
129{
130 Vector<BasicBlock*> result;
131 PostOrderGraphNodeWorklist<BasicBlock*, IndexSet<BasicBlock*>> worklist;
132 worklist.push(root);
133 while (GraphNodeWithOrder<BasicBlock*> item = worklist.pop()) {
134 switch (item.order) {
135 case GraphVisitOrder::Pre:
136 worklist.pushPost(item.node);
137 for (BasicBlock* successor : item.node->successorBlocks())
138 worklist.push(successor);
139 break;
140 case GraphVisitOrder::Post:
141 result.append(item.node);
142 break;
143 }
144 }
145 return result;
146}
147
148} } // namespace JSC::B3
149
150#endif // ENABLE(B3_JIT)
151