Goose  Artifact [2dc9c399a7]

Artifact 2dc9c399a718a84d8defd8bf3f6452dbe26808317137d71165480744f63866f3:

• File bs/llr/cfg.h — part of check-in [7a7e54ac04] at 2020-07-18 16:25:47 on branch llr-stack-language — Computed values now carry lists of instructions around, instead of expression trees. Also absolutely nothing works anymore.

  Update: closing this branch as I will finally not pursue this. (user: achavasse size: 4279)

#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 Address& 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, 0U } );
                auto end = m_loopModifiedAddresses.upper_bound( { loopId, ~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, Address >, 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