1/*
2 * Copyright (C) 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#ifndef DFGBlockWorklist_h
27#define DFGBlockWorklist_h
28
29#if ENABLE(DFG_JIT)
30
31#include "DFGBasicBlock.h"
32#include "DFGBlockSet.h"
33#include <wtf/Vector.h>
34
35namespace JSC { namespace DFG {
36
37struct BasicBlock;
38
39class BlockWorklist {
40public:
41 BlockWorklist();
42 ~BlockWorklist();
43
44 bool push(BasicBlock*); // Returns true if we didn't know about the block before.
45
46 bool notEmpty() const { return !m_stack.isEmpty(); }
47 BasicBlock* pop();
48
49private:
50 BlockSet m_seen;
51 Vector<BasicBlock*, 16> m_stack;
52};
53
54// When you say BlockWith<int> you should read it as "block with an int".
55template<typename T>
56struct BlockWith {
57 BlockWith()
58 : block(nullptr)
59 {
60 }
61
62 BlockWith(BasicBlock* block, const T& data)
63 : block(block)
64 , data(data)
65 {
66 }
67
68 typedef void* (BlockWith<T>::*UnspecifiedBoolType);
69 operator UnspecifiedBoolType*() const
70 {
71 return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
72 }
73
74 BasicBlock* block;
75 T data;
76};
77
78// Extended block worklist is useful for enqueueing some meta-data along with the block. It also
79// permits forcibly enqueueing things even if the block has already been seen.
80template<typename T>
81class ExtendedBlockWorklist {
82public:
83 ExtendedBlockWorklist() { }
84
85 void forcePush(const BlockWith<T>& entry)
86 {
87 m_stack.append(entry);
88 }
89
90 void forcePush(BasicBlock* block, const T& data)
91 {
92 forcePush(BlockWith<T>(block, data));
93 }
94
95 bool push(const BlockWith<T>& entry)
96 {
97 if (!m_seen.add(entry.block))
98 return false;
99
100 forcePush(entry);
101 return true;
102 }
103
104 bool push(BasicBlock* block, const T& data)
105 {
106 return push(BlockWith<T>(block, data));
107 }
108
109 bool notEmpty() const { return !m_stack.isEmpty(); }
110
111 BlockWith<T> pop()
112 {
113 if (m_stack.isEmpty())
114 return BlockWith<T>();
115
116 return m_stack.takeLast();
117 }
118
119private:
120 BlockSet m_seen;
121 Vector<BlockWith<T>> m_stack;
122};
123
124enum VisitOrder {
125 PreOrder,
126 PostOrder
127};
128
129struct BlockWithOrder {
130 BlockWithOrder()
131 : block(nullptr)
132 , order(PreOrder)
133 {
134 }
135
136 BlockWithOrder(BasicBlock* block, VisitOrder order)
137 : block(block)
138 , order(order)
139 {
140 }
141
142 typedef void* (BlockWithOrder::*UnspecifiedBoolType);
143 operator UnspecifiedBoolType*() const
144 {
145 return block ? reinterpret_cast<UnspecifiedBoolType*>(1) : nullptr;
146 }
147
148 BasicBlock* block;
149 VisitOrder order;
150};
151
152// Block worklist suitable for post-order traversal.
153class PostOrderBlockWorklist {
154public:
155 PostOrderBlockWorklist();
156 ~PostOrderBlockWorklist();
157
158 bool pushPre(BasicBlock*);
159 void pushPost(BasicBlock*);
160
161 bool push(BasicBlock* block, VisitOrder order = PreOrder)
162 {
163 switch (order) {
164 case PreOrder:
165 return pushPre(block);
166 case PostOrder:
167 pushPost(block);
168 return true;
169 }
170 RELEASE_ASSERT_NOT_REACHED();
171 return false;
172 }
173 bool push(const BlockWithOrder& data)
174 {
175 return push(data.block, data.order);
176 }
177
178 bool notEmpty() const { return m_worklist.notEmpty(); }
179 BlockWithOrder pop();
180
181private:
182 ExtendedBlockWorklist<VisitOrder> m_worklist;
183};
184
185} } // namespace JSC::DFG
186
187#endif // ENABLE(DFG_JIT)
188
189#endif // DFGBlockWorklist_h
190