Goose  Artifact [d95bb7525d]

Artifact d95bb7525daf405032425d7c813d5e304b098acf99e2f042c5ed26810a2d39f7:

• File bs/llr/cfg.h — part of check-in [8ddd71f9b2] at 2020-12-18 01:29:15 on branch trunk — References refactor: references are now values all the way to the llr, where a new "CalcAddress" instruction represents a conversion from a logical address (location + path) into an actual runtime or compilation time address. This is in preparation to allow references to be stored in variables or passed as parameters. (It just took 4.5 months to finish this... Refactoring just sucks) (user: achavasse size: 4318)

#ifndef GOOSE_LLR_CFG_H
#define GOOSE_LLR_CFG_H

namespace goose::llr
{
    class BasicBlock;

    class CFG : public enable_shared_from_this< CFG >
    {
        public:
            CFG( uint32_t numParams ) :
                m_temporariesCount( numParams )
            {}

            bool isPoisoned() const { return m_poisoned; }
            void poison() { m_poisoned = true; }

            const auto& entryBB() const { return m_basicBlocks.front(); }
            const auto& lastBB() const { return m_basicBlocks.back(); }

            const auto& currentBB() const { return m_currentBB; }
            template< typename T >
            void setCurrentBB( T&& pBB )
            {
                m_currentBB = forward<  T >( pBB );
            }

            void addEdge( uint32_t srcIndex, uint32_t destIndex );
            const auto& edges() const { return m_edges; }

            template< typename V >
            void setIdoms( V&& idoms )
            {
                m_idoms = forward< V >( idoms );
            }
            const auto& idoms() const { return m_idoms; }

            uint32_t loopCount() const { return m_loopCount; }
            void incLoopCount() { ++m_loopCount; }

            // If  the BB of index 1 dominates the BB of index 2, returns the distance:
            // 0 if BB1 and BB2 are the same, 1 if BB1 is the immediate dominator, 2 if it is
            // the dominator's dominator, and so on.
            // Note: dominators needs to have been computed for the CFG before hand by
            // calling ComputeDominators().
            optional< uint32_t > getDominatorDistance( uint32_t bbIndex1, uint32_t bbIndex2 ) const;

            const auto& getBB( uint32_t index ) const { return m_basicBlocks[index - 1]; }

            auto count() const { return m_basicBlocks.size(); }

            const ptr< llr::BasicBlock >& createBB();

            auto getNewTemporaryIndex() { return m_temporariesCount++; }

            // Clear the llvm basic block pointers from the entire cfg.
            void unbindFromLLVM();

            bool canBeExecuted() const;
            bool canBeEagerlyEvaluated() const;

            template< typename F >
            void forEachBB( F&& func )
            {
                for( auto&& bb : m_basicBlocks )
                    func( bb );
            }

            void setAddressModifiedByLoop( uint32_t loopId, const ir::Term& type, const CalcAddress& addr )
            {
                m_loopModifiedAddresses.emplace( make_pair( loopId, addr ), type );
            }

            template< typename F >
            void forEachAddressModifiedInLoop( uint32_t loopId, F&& func ) const
            {
                auto begin = m_loopModifiedAddresses.lower_bound( { loopId, CalcAddress( 0U ) } );
                auto end = m_loopModifiedAddresses.upper_bound( { loopId, CalcAddress( ~0U ) } );

                for( auto it = begin; it != end; ++it )
                    func( it->second, it->first.second );
            }

        private:
            vector< ptr< BasicBlock > > m_basicBlocks;
            ptr< BasicBlock > m_currentBB;

            // All the edges of the CFG in SrcBBIndex, DestBBIndex form
            unordered_multimap< uint32_t, uint32_t > m_edges;

            // For each BB, store the index of its immediate dominator.
            // May be be empty if it has not (yet) been computed.
            vector< uint32_t > m_idoms;

            // For each loop, store all of the adresses modified
            // during that loop.
            // May be be empty if it has not (yet) been computed.
            multimap< pair< uint32_t, CalcAddress >, ir::Term > m_loopModifiedAddresses;

            // The number of temporary indices used by this CFG.
            uint32_t m_temporariesCount = 0;

            uint32_t m_loopCount = 0;

            bool m_poisoned = false;
    };

    // Compute the immediate dominators for each BB in the provided CFG,
    // using the Lengauer-Tarjan algorithm.
    extern void ComputeDominators( const ptr< CFG >& cfg );

    // Detect loops and store loop informations into the CFG.
    extern void ComputeLoops( const ptr< CFG >& cfg );

    // Find which loop modifies which variable.
    extern void ComputeLoopModifiedAddrs( const ptr< CFG >& cfg );
}

#endif