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