Liveness.h   [plain text]

/*
 * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#pragma once

#include <wtf/BitVector.h>
#include <wtf/IndexSparseSet.h>
#include <wtf/StdLibExtras.h>

namespace WTF {

// HEADS UP: The algorithm here is duplicated in AirRegLiveness.h. That one uses sets rather
// than fancy vectors, because that's better for register liveness analysis.
template<typename Adapter>
class Liveness : public Adapter {
public:
    typedef typename Adapter::CFG CFG;
    typedef typename Adapter::Thing Thing;
    typedef Vector<unsigned, 4, UnsafeVectorOverflow> IndexVector;
    typedef IndexSparseSet<unsigned, DefaultIndexSparseSetTraits<unsigned>, UnsafeVectorOverflow> Workset;
    
    template<typename... Arguments>
    Liveness(CFG& cfg, Arguments&&... arguments)
        : Adapter(std::forward<Arguments>(arguments)...)
        , m_cfg(cfg)
        , m_workset(Adapter::numIndices())
        , m_liveAtHead(cfg.template newMap<IndexVector>())
        , m_liveAtTail(cfg.template newMap<IndexVector>())
    {
    }
    
    // This calculator has to be run in reverse.
    class LocalCalc {
    public:
        LocalCalc(Liveness& liveness, typename CFG::Node block)
            : m_liveness(liveness)
            , m_block(block)
        {
            auto& workset = liveness.m_workset;
            workset.clear();
            IndexVector& liveAtTail = liveness.m_liveAtTail[block];
            for (unsigned index : liveAtTail)
                workset.add(index);
        }

        class Iterable {
        public:
            Iterable(Liveness& liveness)
                : m_liveness(liveness)
            {
            }

            class iterator {
            public:
                iterator(Adapter& adapter, Workset::const_iterator sparceSetIterator)
                    : m_adapter(adapter)
                    , m_sparceSetIterator(sparceSetIterator)
                {
                }

                iterator& operator++()
                {
                    ++m_sparceSetIterator;
                    return *this;
                }

                typename Adapter::Thing operator*() const
                {
                    return m_adapter.indexToValue(*m_sparceSetIterator);
                }

                bool operator==(const iterator& other) { return m_sparceSetIterator == other.m_sparceSetIterator; }
                bool operator!=(const iterator& other) { return m_sparceSetIterator != other.m_sparceSetIterator; }

            private:
                Adapter& m_adapter;
                Workset::const_iterator m_sparceSetIterator;
            };

            iterator begin() const { return iterator(m_liveness, m_liveness.m_workset.begin()); }
            iterator end() const { return iterator(m_liveness, m_liveness.m_workset.end()); }
            
            bool contains(const typename Adapter::Thing& thing) const
            {
                return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
            }

        private:
            Liveness& m_liveness;
        };

        Iterable live() const
        {
            return Iterable(m_liveness);
        }

        bool isLive(const typename Adapter::Thing& thing) const
        {
            return live().contains(thing);
        }

        void execute(unsigned instIndex)
        {
            auto& workset = m_liveness.m_workset;

            // Want an easy example to help you visualize how this works?
            // Check out B3VariableLiveness.h.
            //
            // Want a hard example to help you understand the hard cases?
            // Check out AirLiveness.h.
            
            m_liveness.forEachDef(
                m_block, instIndex + 1,
                [&] (unsigned index) {
                    workset.remove(index);
                });
            
            m_liveness.forEachUse(
                m_block, instIndex,
                [&] (unsigned index) {
                    workset.add(index);
                });
        }
        
    private:
        Liveness& m_liveness;
        typename CFG::Node m_block;
    };

    const IndexVector& rawLiveAtHead(typename CFG::Node block)
    {
        return m_liveAtHead[block];
    }

    template<typename UnderlyingIterable>
    class Iterable {
    public:
        Iterable(Liveness& liveness, const UnderlyingIterable& iterable)
            : m_liveness(liveness)
            , m_iterable(iterable)
        {
        }

        class iterator {
        public:
            iterator()
                : m_liveness(nullptr)
                , m_iter()
            {
            }
            
            iterator(Liveness& liveness, typename UnderlyingIterable::const_iterator iter)
                : m_liveness(&liveness)
                , m_iter(iter)
            {
            }

            typename Adapter::Thing operator*()
            {
                return m_liveness->indexToValue(*m_iter);
            }

            iterator& operator++()
            {
                ++m_iter;
                return *this;
            }

            bool operator==(const iterator& other) const
            {
                ASSERT(m_liveness == other.m_liveness);
                return m_iter == other.m_iter;
            }

            bool operator!=(const iterator& other) const
            {
                return !(*this == other);
            }

        private:
            Liveness* m_liveness;
            typename UnderlyingIterable::const_iterator m_iter;
        };

        iterator begin() const { return iterator(m_liveness, m_iterable.begin()); }
        iterator end() const { return iterator(m_liveness, m_iterable.end()); }

        bool contains(const typename Adapter::Thing& thing) const
        {
            return m_liveness.m_workset.contains(m_liveness.valueToIndex(thing));
        }

    private:
        Liveness& m_liveness;
        const UnderlyingIterable& m_iterable;
    };

    Iterable<IndexVector> liveAtHead(typename CFG::Node block)
    {
        return Iterable<IndexVector>(*this, m_liveAtHead[block]);
    }

    Iterable<IndexVector> liveAtTail(typename CFG::Node block)
    {
        return Iterable<IndexVector>(*this, m_liveAtTail[block]);
    }

    Workset& workset() { return m_workset; }
    
    class LiveAtHead {
    public:
        LiveAtHead(Liveness& liveness)
            : m_liveness(liveness)
        {
            for (unsigned blockIndex = m_liveness.m_cfg.numNodes(); blockIndex--;) {
                typename CFG::Node block = m_liveness.m_cfg.node(blockIndex);
                if (!block)
                    continue;
                
                std::sort(m_liveness.m_liveAtHead[block].begin(), m_liveness.m_liveAtHead[block].end());
            }
        }
        
        bool isLiveAtHead(typename CFG::Node block, const typename Adapter::Thing& thing)
        {
            return !!tryBinarySearch<unsigned>(m_liveness.m_liveAtHead[block], m_liveness.m_liveAtHead[block].size(), m_liveness.valueToIndex(thing), [] (unsigned* value) { return *value; });
        }
        
    private:
        Liveness& m_liveness;
    };
    
    LiveAtHead liveAtHead() { return LiveAtHead(*this); }

protected:
    void compute()
    {
        Adapter::prepareToCompute();
        
        // The liveAtTail of each block automatically contains the LateUse's of the terminal.
        for (unsigned blockIndex = m_cfg.numNodes(); blockIndex--;) {
            typename CFG::Node block = m_cfg.node(blockIndex);
            if (!block)
                continue;
            
            IndexVector& liveAtTail = m_liveAtTail[block];

            Adapter::forEachUse(
                block, Adapter::blockSize(block),
                [&] (unsigned index) {
                    liveAtTail.append(index);
                });
            
            std::sort(liveAtTail.begin(), liveAtTail.end());
            removeRepeatedElements(liveAtTail);
        }

        // Blocks with new live values at tail.
        BitVector dirtyBlocks;
        for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;)
            dirtyBlocks.set(blockIndex);
        
        IndexVector mergeBuffer;
        
        bool changed;
        do {
            changed = false;

            for (size_t blockIndex = m_cfg.numNodes(); blockIndex--;) {
                typename CFG::Node block = m_cfg.node(blockIndex);
                if (!block)
                    continue;

                if (!dirtyBlocks.quickClear(blockIndex))
                    continue;

                LocalCalc localCalc(*this, block);
                for (size_t instIndex = Adapter::blockSize(block); instIndex--;)
                    localCalc.execute(instIndex);

                // Handle the early def's of the first instruction.
                Adapter::forEachDef(
                    block, 0,
                    [&] (unsigned index) {
                        m_workset.remove(index);
                    });

                IndexVector& liveAtHead = m_liveAtHead[block];

                // We only care about Tmps that were discovered in this iteration. It is impossible
                // to remove a live value from the head.
                // We remove all the values we already knew about so that we only have to deal with
                // what is new in LiveAtHead.
                if (m_workset.size() == liveAtHead.size())
                    m_workset.clear();
                else {
                    for (unsigned liveIndexAtHead : liveAtHead)
                        m_workset.remove(liveIndexAtHead);
                }

                if (m_workset.isEmpty())
                    continue;

                liveAtHead.reserveCapacity(liveAtHead.size() + m_workset.size());
                for (unsigned newValue : m_workset)
                    liveAtHead.uncheckedAppend(newValue);
                
                m_workset.sort();
                
                for (typename CFG::Node predecessor : m_cfg.predecessors(block)) {
                    IndexVector& liveAtTail = m_liveAtTail[predecessor];
                    
                    if (liveAtTail.isEmpty())
                        liveAtTail = m_workset.values();
                    else {
                        mergeBuffer.resize(liveAtTail.size() + m_workset.size());
                        auto iter = mergeDeduplicatedSorted(
                            liveAtTail.begin(), liveAtTail.end(),
                            m_workset.begin(), m_workset.end(),
                            mergeBuffer.begin());
                        mergeBuffer.resize(iter - mergeBuffer.begin());
                        
                        if (mergeBuffer.size() == liveAtTail.size())
                            continue;
                    
                        RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
                        liveAtTail = mergeBuffer;
                    }
                    
                    dirtyBlocks.quickSet(predecessor->index());
                    changed = true;
                }
            }
        } while (changed);
    }

private:
    friend class LocalCalc;
    friend class LocalCalc::Iterable;

    CFG& m_cfg;
    Workset m_workset;
    typename CFG::template Map<IndexVector> m_liveAtHead;
    typename CFG::template Map<IndexVector> m_liveAtTail;
};

} // namespace WTF