1/*
2 * Copyright (C) 2015-2017 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#include <wtf/BitVector.h>
29#include <wtf/IndexSparseSet.h>
30#include <wtf/StdLibExtras.h>
31
32namespace WTF {
33
34// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
35// than fancy vectors, because that's better for register liveness analysis.
36template<typename Adapter>
37class Liveness : public Adapter {
38public:
39 typedef typename Adapter::CFG CFG;
40 typedef typename Adapter::Thing Thing;
41 typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
42 typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
43
44 template<typename... Arguments>
45 Liveness(CFG& cfg, Arguments&&... arguments)
46 : Adapter(std::forward<Arguments>(arguments)...)
47 , m_cfg(cfg)
48 , m_workset(Adapter::numIndices())
49 , m_liveAtHead(cfg.template newMap<IndexVector>())
50 , m_liveAtTail(cfg.template newMap<IndexVector>())
51 {
52 }
53
54 // This calculator has to be run in reverse.
55 class LocalCalc {
56 public:
57 LocalCalc(Liveness& liveness, typename CFG::Node block)
58 : m_liveness(liveness)
59 , m_block(block)
60 {
61 auto& workset = liveness.m_workset;
62 workset.clear();
63 IndexVector& liveAtTail = liveness.m_liveAtTail[block];
64 for (unsigned index : liveAtTail)
65 workset.add(index);
66 }
67
68 class Iterable {
69 public:
70 Iterable(Liveness& liveness)
71 : m_liveness(liveness)
72 {
73 }
74
75 class iterator {
76 public:
77 iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
78 : m_adapter(adapter)
79 , m_sparceSetIterator(sparceSetIterator)
80 {
81 }
82
83 iterator& operator++()
84 {
85 ++m_sparceSetIterator;
86 return *this;
87 }
88
89 typename Adapter::Thing operator*() const
90 {
91 return m_adapter.indexToValue(*m_sparceSetIterator);
92 }
93
94 bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
95 bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }
96
97 private:
98 Adapter& m_adapter;
99 Workset::const_iterator m_sparceSetIterator;
100 };
101
102 iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
103 iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
104
105 bool contains(const typename Adapter::Thing& thing) const
106 {
107 return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
108 }
109
110 private:
111 Liveness& m_liveness;
112 };
113
114 Iterable live() const
115 {
116 return Iterable(m_liveness);
117 }
118
119 bool isLive(const typename Adapter::Thing& thing) const
120 {
121 return live().contains(thing);
122 }
123
124 void execute(unsigned instIndex)
125 {
126 auto& workset = m_liveness.m_workset;
127
128 // Want an easy example to help you visualize how this works?
129 // Check out B3VariableLiveness.h.
130 //
131 // Want a hard example to help you understand the hard cases?
132 // Check out AirLiveness.h.
133
134 m_liveness.forEachDef(
135 m_block, instIndex + 1,
136 [&] (unsigned index) {
137 workset.remove(index);
138 });
139
140 m_liveness.forEachUse(
141 m_block, instIndex,
142 [&] (unsigned index) {
143 workset.add(index);
144 });
145 }
146
147 private:
148 Liveness& m_liveness;
149 typename CFG::Node m_block;
150 };
151
152 const IndexVector& rawLiveAtHead(typename CFG::Node block)
153 {
154 return m_liveAtHead[block];
155 }
156
157 template<typename UnderlyingIterable>
158 class Iterable {
159 public:
160 Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
161 : m_liveness(liveness)
162 , m_iterable(iterable)
163 {
164 }
165
166 class iterator {
167 public:
168 iterator()
169 : m_liveness(nullptr)
170 , m_iter()
171 {
172 }
173
174 iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
175 : m_liveness(&liveness)
176 , m_iter(iter)
177 {
178 }
179
180 typename Adapter::Thing operator*()
181 {
182 return m_liveness->indexToValue(*m_iter);
183 }
184
185 iterator& operator++()
186 {
187 ++m_iter;
188 return *this;
189 }
190
191 bool operator==(const iterator& other) const
192 {
193 ASSERT(m_liveness == other.m_liveness);
194 return m_iter == other.m_iter;
195 }
196
197 bool operator!=(const iterator& other) const
198 {
199 return !(*this == other);
200 }
201
202 private:
203 Liveness* m_liveness;
204 typename UnderlyingIterable::const_iterator m_iter;
205 };
206
207 iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
208 iterator end() const { return iterator(m_liveness, m_iterable.end()); }
209
210 bool contains(const typename Adapter::Thing& thing) const
211 {
212 return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
213 }
214
215 private:
216 Liveness& m_liveness;
217 const UnderlyingIterable& m_iterable;
218 };
219
220 Iterable<IndexVector> liveAtHead(typename CFG::Node block)
221 {
222 return Iterable<IndexVector>(*this, m_liveAtHead[block]);
223 }
224
225 Iterable<IndexVector> liveAtTail(typename CFG::Node block)
226 {
227 return Iterable<IndexVector>(*this, m_liveAtTail[block]);
228 }
229
230 Workset& workset() { return m_workset; }
231
232 class LiveAtHead {
233 public:
234 LiveAtHead(Liveness& liveness)
235 : m_liveness(liveness)
236 {
237 for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
238 typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
239 if (!block)
240 continue;
241
242 std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
243 }
244 }
245
246 bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
247 {
248 return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
249 }
250
251 private:
252 Liveness& m_liveness;
253 };
254
255 LiveAtHead liveAtHead() { return LiveAtHead(*this); }
256
257protected:
258 void compute()
259 {
260 Adapter::prepareToCompute();
261
262 // The liveAtTail of each block automatically contains the LateUse's of the terminal.
263 for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
264 typename CFG::Node block = m_cfg.node(blockIndex);
265 if (!block)
266 continue;
267
268 IndexVector& liveAtTail = m_liveAtTail[block];
269
270 Adapter::forEachUse(
271 block, Adapter::blockSize(block),
272 [&] (unsigned index) {
273 liveAtTail.append(index);
274 });
275
276 std::sort(liveAtTail.begin(), liveAtTail.end());
277 removeRepeatedElements(liveAtTail);
278 }
279
280 // Blocks with new live values at tail.
281 BitVector dirtyBlocks;
282 for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
283 dirtyBlocks.set(blockIndex);
284
285 IndexVector mergeBuffer;
286
287 bool changed;
288 do {
289 changed = false;
290
291 for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
292 typename CFG::Node block = m_cfg.node(blockIndex);
293 if (!block)
294 continue;
295
296 if (!dirtyBlocks.quickClear(blockIndex))
297 continue;
298
299 LocalCalc localCalc(*this, block);
300 for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
301 localCalc.execute(instIndex);
302
303 // Handle the early def's of the first instruction.
304 Adapter::forEachDef(
305 block, 0,
306 [&] (unsigned index) {
307 m_workset.remove(index);
308 });
309
310 IndexVector& liveAtHead = m_liveAtHead[block];
311
312 // We only care about Tmps that were discovered in this iteration. It is impossible
313 // to remove a live value from the head.
314 // We remove all the values we already knew about so that we only have to deal with
315 // what is new in LiveAtHead.
316 if (m_workset.size() == liveAtHead.size())
317 m_workset.clear();
318 else {
319 for (unsigned liveIndexAtHead : liveAtHead)
320 m_workset.remove(liveIndexAtHead);
321 }
322
323 if (m_workset.isEmpty())
324 continue;
325
326 liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
327 for (unsigned newValue : m_workset)
328 liveAtHead.uncheckedAppend(newValue);
329
330 m_workset.sort();
331
332 for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
333 IndexVector& liveAtTail = m_liveAtTail[predecessor];
334
335 if (liveAtTail.isEmpty())
336 liveAtTail = m_workset.values();
337 else {
338 mergeBuffer.resize(liveAtTail.size() + m_workset.size());
339 auto iter = mergeDeduplicatedSorted(
340 liveAtTail.begin(), liveAtTail.end(),
341 m_workset.begin(), m_workset.end(),
342 mergeBuffer.begin());
343 mergeBuffer.resize(iter - mergeBuffer.begin());
344
345 if (mergeBuffer.size() == liveAtTail.size())
346 continue;
347
348 RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
349 liveAtTail = mergeBuffer;
350 }
351
352 dirtyBlocks.quickSet(predecessor->index());
353 changed = true;
354 }
355 }
356 } while (changed);
357 }
358
359private:
360 friend class LocalCalc;
361 friend class LocalCalc::Iterable;
362
363 CFG& m_cfg;
364 Workset m_workset;
365 typename CFG::template Map<IndexVector> m_liveAtHead;
366 typename CFG::template Map<IndexVector> m_liveAtTail;
367};
368
369} // namespace WTF
370
371