Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / Liveness.h
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
32 namespace 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.
36 template<typename Adapter>
37 class Liveness : public Adapter {
38 public:
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
257 protected:
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
359 private:
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