Goose  Check-in [238df77134]

        // or partial specialization of this, since it will have to emit specialized
        // binary runtime code.
        RegisterBuiltinFunc< Intrinsic< Value ( LocVarOfTypeT, ValueOfTypeT ) > >( e, e.extInitializeLocalVar(),
            []( const Value& lv, const Value& initVal )
            {
                auto locVar = *FromValue< LocalVar >( lv );
                return BuildComputedValue( GetValueType< void >(),
                    SetVar( initVal, locVar.cfgId(), locVar.index() ) );
            } );

        // Initialization for integer vars
        RegisterBuiltinFunc< Intrinsic< Value ( IntegerLocVarType, IntegerType ) > >( e, e.extInitializeLocalVar(),
            []( const Value& lv, const Value& initVal )
            {
                auto locVar = *FromValue< LocalVar >( lv );
                return BuildComputedValue( GetValueType< void >(),
                    SetVar( initVal, locVar.cfgId(), locVar.index() ) );
            } );

        // Default initialization for integer vars
        RegisterBuiltinFunc< Intrinsic< Value ( IntegerLocVarType ) > >( e, e.extInitializeLocalVar(),
            []( const Value& lv )
            {
                auto locVar = *FromValue< LocalVar >( lv );

                auto opTypeVal = *ValueFromIRExpr( locVar.type() );
                auto opType = *FromValue< IntegerType >( opTypeVal );
                auto initVal = Value( locVar.type(),
                    APSInt( opType.m_numBits, !opType.m_signed ) );

                return BuildComputedValue( GetValueType< void >(),
                    SetVar( move( initVal ), locVar.cfgId(), locVar.index() ) );
            } );

        // Default initialization for ct_int vars
        RegisterBuiltinFunc< Intrinsic< Value ( CTIntLocVarType ) > >( e, e.extInitializeLocalVar(),
            []( const Value& lv )
            {
                auto locVar = *FromValue< LocalVar >( lv );
                return BuildComputedValue( GetValueType< void >(),
                    SetVar( ToValue( BigInt() ), locVar.cfgId(), locVar.index() ) );
            } );

        // Default initialization for ct_string vars
        RegisterBuiltinFunc< Intrinsic< Value ( CTStringLocVarType ) > >( e, e.extInitializeLocalVar(),
            []( const Value& lv )
            {
                auto locVar = *FromValue< LocalVar >( lv );
                return BuildComputedValue( GetValueType< void >(),
                    SetVar( ToValue( ""s ), locVar.cfgId(), locVar.index() ) );
            } );
    }
}

        auto BuiltinTypeAssignment = []( auto&& lhs, auto&& rhs ) -> Value
        {
            auto locvar = *FromValue< LocalVar >( lhs );

            auto& p = *Parser::GetCurrentParser();
            auto bb = p.cfg()->currentBB();
            if( bb )
                bb->emplace_back( SetVar( rhs, locvar.cfgId(), locvar.index() ) );

            // TODO: we don't support chained assignments for now. Probably later when we have
            // references.
            return Value( GetValueType< void >(), 0U );
        };

        BuildParseRule( e, "="_sid,

                    auto pSuccBB = cfg->createBB();

                    // If the lhs is true, skip to the end directly.
                    // Otherwise, jump to the BB that computes rhs.
                    predBB->setTerminator( CondBranch( lhs, pSuccBB, pRhsBB ) );

                    auto rhsIndex = cfg->getNewTemporaryIndex();
                    pRhsBB->emplace_back( CreateTemporary( cfg->uniqueId(), rhsIndex, rhs ) );
                    pRhsBB->setTerminator( Branch( pSuccBB ) );

                    auto resultIndex = cfg->getNewTemporaryIndex();

                    // Build the Phi instruction that will collect the final result.
                    auto phi = Phi( *ValueFromIRExpr( GetValueType< bool >() ),
                        2, cfg->uniqueId(), resultIndex );

                    // If coming directly from the lhs BB, we know the result is true.
                    phi.setIncoming( predBB, ToValue( true ) );

                    // Otherwise, the result is whatever was computed by the rhs block.
                    phi.setIncoming( pRhsBB, BuildComputedValue( GetValueType< bool >(),
                        GetTemporary( GetValueType< bool >(), cfg->uniqueId(), rhsIndex ) ) );

                    pSuccBB->emplace_back( move( phi ) );
                    cfg->setCurrentBB( pSuccBB );

                    // Build the result val which pulls the temporary created above.
                    return BuildComputedValue( GetValueType< bool >(),
                        GetTemporary( GetValueType< bool >(), cfg->uniqueId(), resultIndex ) );
                } )
            )
        );

        BuildParseRule( e, "&"_sid,
            LeftAssInfixOp( "operator_and"_sid, precedence::AndOp,
                BuildGenericTupleOperator(),

                    auto pSuccBB = cfg->createBB();

                    // If the lhs is false, skip to the end directly.
                    // Otherwise, jump to the BB that computes rhs.
                    predBB->setTerminator( CondBranch( lhs, pRhsBB, pSuccBB ) );

                    auto rhsIndex = cfg->getNewTemporaryIndex();
                    pRhsBB->emplace_back( CreateTemporary( cfg->uniqueId(), rhsIndex, rhs ) );
                    pRhsBB->setTerminator( Branch( pSuccBB ) );

                    auto resultIndex = cfg->getNewTemporaryIndex();

                    // Build the Phi instruction that will collect the final result.
                    auto phi = Phi( *ValueFromIRExpr( GetValueType< bool >() ),
                        2, cfg->uniqueId(), resultIndex );

                    // If coming directly from the lhs BB, we know the result is true.
                    phi.setIncoming( predBB, ToValue( false ) );

                    // Otherwise, the result is whatever was computed by the rhs block.
                    phi.setIncoming( pRhsBB, BuildComputedValue( GetValueType< bool >(),
                        GetTemporary( GetValueType< bool >(), cfg->uniqueId(), rhsIndex ) ) );

                    pSuccBB->emplace_back( move( phi ) );
                    cfg->setCurrentBB( pSuccBB );

                    // Build the result val which pulls the temporary created above.
                    return BuildComputedValue( GetValueType< bool >(),
                        GetTemporary( GetValueType< bool >(), cfg->uniqueId(), resultIndex ) );
                } )
            )
        );

        BuildParseRule( e, "<<"_sid,
            LeftAssInfixOp( "operator_shift_left"_sid, precedence::BitShiftOp,
                BuildGenericTupleOperator(),

                tv->append( ParamPat( decl.type() ) );

                // Bind a stand-in value with the parameters name to be used inside of verification expressions.
                auto paramVerificationIdentity = AppendToVectorTerm( verificationIdentity,
                    TERM( decl.name() ) );

                c.env()->storeValue( paramVerificationIdentity, ANYTERM( _ ),
                    ValueToIRExpr( BuildComputedValue( decl.type(), llr::GetVar( move( decl.type() ), 0, varId++ ) ) ) );
            }
            else if( param.isConstant() )
                tv->append( ParamPatFromTerm( ValueToIRExpr( param ) ) );

            return true;
        } );

            // the param needs to be visible regardless of which domain we are compiling
            // the function in.
            auto paramIdentity = AppendToVectorTerm(
                InjectDomainIntoIdentity( identity, ANYTERM( _ ) ),
                TERM( decl.name() ) );

            c.env()->storeValue( paramIdentity, ANYTERM( _ ),
                ValueToIRExpr( BuildComputedValue( decl.type(), llr::GetVar( decl.type(), 0, varId++ ) ) ) );

            return true;
        } );

        out_bodyContext = Context( c.env(), identity, funcType.returnType() );
        auto pFuncLLR = c.env()->createLLRFunc( identity );

            return false;

        Context localContext( c.env(), pFuncLLR->identity(), f.type().returnType() );
        auto tokProvider = lex::MakeVectorAdapter( *static_pointer_cast< vector< TermLoc > >( f.tokens() ) );
        auto r = make_shared< parse::Resolver >( tokProvider, localContext );
        Parser p( r );

        auto cfg = make_shared< llr::CFG >();
        cfg->createBB();
        p.setCFG( cfg );
        p.cfg()->setCurrentBB( cfg->entryBB() );

        bool success = p.parseBraceBlock();
        p.flushValue();

    {
        static auto pattern = GetValueType< LocalVar >( MkHole( "T"_sid ) );
        return pattern;
    }

    Value DeclareLocalVar( Parser& p, const Term& type, StringId name, const optional< Value >& initializer )
    {
        auto cfgId = p.cfg()->uniqueId();
        auto index = p.cfg()->getNewTemporaryIndex();

        LocalVar lv( name, type, p.resolver()->context().env()->NewUniqueId(), cfgId, index );

        auto bb = p.cfg()->currentBB();
        if( !bb )
            return PoisonValue();

        auto typeVal = *ValueFromIRExpr( type );
        bb->emplace_back( AllocVar( typeVal, cfgId, index ) );

        if( initializer )
        {
            DiagnosticsContext dc( 0, "When invoking InitializeLocalVar." );

            p.pushValue( InvokeOverloadSet( p.resolver()->context(),
                p.resolver()->context().env()->extInitializeLocalVar(),

                SubTerm()   // initializer
            )
        );

        auto&& [type, initializer] = *callDecomp;
        auto initializerVal = *ValueFromIRExpr( initializer );

        auto cfgId = p.cfg()->uniqueId();
        auto index = p.cfg()->getNewTemporaryIndex();

        // Retrieve the texpr's location and set it on the inferred type. This way if an
        // error occurs later with it, for instance when calling LowerType on it during codegen,
        // it will have a meaningful location for the error message to attach itself on.
        uint32_t typeLoc = ValueFromIRExpr( typeTExpr )->locationId();
        LocalVar lv( name, type, p.resolver()->context().env()->NewUniqueId(), cfgId, index );

        bb->emplace_back( AllocVar( ValueFromIRExpr( lv.type() )->setLocationId( typeLoc ), cfgId, index ) );

        p.pushValue( ResolveInvocation( c, GetInvocationRule( *c.env(), initializerVal ), initializerVal,
            MakeTuple( ToValue( lv ), initVal ) ) );

        auto locVar = ToValue( lv );

        if( name != ""_sid )

    Term Bridge< LocalVar >::Type( const Term& type )
    {
        return ValueToIRExpr( ToValue< LocalVarType >( type ) );
    }

    Value Bridge< LocalVar >::ToValue( const LocalVar& lv )
    {
        return Value( Type( lv.type() ), VEC( TERM( lv.name() ), TERM( lv.uniqueId() ), TERM( lv.cfgId() ), TERM( lv.index() ) ) );
    }

    optional< LocalVar > Bridge< LocalVar >::FromValue( const Value& v )
    {
        if( !v.isConstant() )
            return nullopt;

        auto t = FromValue< LocalVarType >( *ValueFromIRExpr( v.type() ) );
        if( !t )
            return nullopt;

        auto result = Decompose( v.val(),
            Vec(
                Val< StringId >(),
                Val< uint32_t >(),
                Val< uint32_t >(),
                Val< uint32_t >()
            )
        );

        if( !result )
            return nullopt;

        auto&& [name,uniqueId,cfgId,index] = *result;

        return LocalVar( name, move( t->type() ), uniqueId, cfgId, index );
    }
}

            Term m_type;
    };

    class LocalVar
    {
        public:
            template< typename T >
            LocalVar( StringId name, T&& type, uint32_t uniqueId, uint32_t cfgId, uint32_t index ) :
                m_name( name ),
                m_type( forward< T >( type ) ),
                m_uniqueId( uniqueId ),
                m_cfgId( cfgId ),
                m_index( index )
            {}

            auto name() const { return m_name; }
            auto uniqueId() const { return m_uniqueId; }
            const auto& type() const { return m_type; }
            auto& type() { return m_type; }
            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }

            struct PatternAny
            {
                static const Term& GetPattern();
                static optional< Term > GetDomain() { return sema::DomainAny(); }
            };

                static auto GetDomain() { return PP::GetDomain(); }
            };

        private:
            StringId m_name;
            Term m_type;
            uint32_t m_uniqueId = 0;
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
    };
}

namespace goose::ir
{
    template<>

        []( const Term& lhs, const Term& rhs, UnificationContext& c ) -> UniGen
        {
            auto locvar = FromValue< LocalVar >( *ValueFromIRExpr( rhs ) );
            if( !locvar )
                co_return;

            auto varcontent = ValueToIRExpr( BuildComputedValue( locvar->type(),
                GetVar( locvar->type(), locvar->cfgId(), locvar->index() ) ) );

            // Unify the param with the var's content
            co_yield Unify( lhs, varcontent, c );
        } );

        // LocalVar unification against another LocalVar: unify their types.
        e.unificationRuleSet()->addSymRule(

    {
        inf.lastEmittedAlloca = m_llvmBuilder.CreateAlloca( arg.getType() );
        args.push_back( inf.lastEmittedAlloca );
    }

    size_t i = 0;
    for( auto&& arg : pllvmFunc->args() )

        m_llvmBuilder.CreateStore( &arg, args[i++] );



    inf.temporaries->setVec( 0, move( args ) );

    if( !buildCFG( inf, pllvmFunc, func.llr()->body() ) )
        return nullptr;

    llvm::verifyFunction( *pllvmFunc );
    return pllvmFunc;
}

    }

    return m_llvmBuilder.CreateCall( llvmCallee, args );
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::CreateTemporary& ct )
{
    return createTemporary( inf, ct.cfgId(), ct.index(), buildValue( inf, ct.value() ) );
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::GetTemporary& gt )
{
    auto* ppVal = inf.temporaries->get( gt.cfgId(), gt.index() );
    assert( ppVal );
    if( !ppVal )
        return nullptr;
    return *ppVal;
}

llvm::Value* Module::createTemporary( Infos& inf, uint32_t cfgId, uint32_t index, llvm::Value* pValue ) const
{
    inf.temporaries->set( cfgId, index, pValue );
    return pValue;
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::AllocVar& av )
{
    auto type = LowerType( inf.context, av.type() );
    if( !type )
        return nullptr;

    llvm::IRBuilderBase::InsertPointGuard g( m_llvmBuilder );

    if( inf.lastEmittedAlloca && inf.lastEmittedAlloca->getNextNode() )
        m_llvmBuilder.SetInsertPoint( inf.lastEmittedAlloca->getNextNode() );
    else
        m_llvmBuilder.SetInsertPoint( inf.allocaBasicBlock, inf.allocaBasicBlock->begin() );

    inf.lastEmittedAlloca = m_llvmBuilder.CreateAlloca( GetLLVMType( *type ) );
    createTemporary( inf, av.cfgId(), av.index(), inf.lastEmittedAlloca );

    return inf.lastEmittedAlloca;
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::GetVar& gv )
{
    return m_llvmBuilder.CreateLoad( *inf.temporaries->get( gv.cfgId(), gv.index() ) );
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::SetVar& sv )
{
    auto val = buildValue( inf, sv.value() );
    if( !val )
        return nullptr;

    return m_llvmBuilder.CreateStore( val, *inf.temporaries->get( sv.cfgId(), sv.index() ) );
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::Phi& p )
{
    auto type = LowerType( inf.context, p.type() );
    if( !type )
        return nullptr;

            return true;
        } );
    }

    if( !pPHI )
        return nullptr;

    return createTemporary( inf, p.destCfgId(), p.destIndex(), pPHI );
}

llvm::Value* Module::buildInstruction( Infos& inf, const llr::LoadConstStr& lcs )
{
    llvm::GlobalVariable* pGlob = nullptr;

    auto* arType = llvm::ArrayType::get( llvm::IntegerType::getInt8Ty( GetLLVMContext() ),

            template< typename T >
            bool buildTerminator( Infos& inf, const T& t )
            {
                return false;
            }

            llvm::Value* createTemporary( Infos& inf, uint32_t cfgId, uint32_t index, llvm::Value* pValue ) const;

            llvm::Module m_llvmModule;
            llvm::IRBuilder<> m_llvmBuilder;
            llvm::TargetMachine* m_targetMachine = nullptr;

            unordered_map< string, llvm::GlobalVariable* > m_strings;
    };

        DiagnosticsContext dc( 0, true );
        VerbosityContext vc( Verbosity::Normal, true );

        auto r = make_shared< parse::Resolver >(
            make_shared< lex::Lexer >( sourcefile, filename ), c );
        parse::Parser p( r );

        auto cfg = make_shared< llr::CFG >();
        cfg->createBB();
        p.setCFG( cfg );
        p.cfg()->setCurrentBB( cfg->entryBB() );

        p.parseSequence();

        if( cfg->isPoisoned() )

#ifndef GOOSE_EXECUTE_FRAME_H
#define GOOSE_EXECUTE_FRAME_H

namespace goose::execute
{
    class Frame
    {
        public:
            template< typename V >
            void setArgs( V&& argVec )
            {
                m_temporaries.setVec( 0, forward< V >( argVec ) );
            }

            template< typename V >
            void setTemporary( uint32_t cfgId, uint32_t index, V&& val )
            {
                m_temporaries.set( cfgId, index, forward< V >( val ) );
            }

            const auto* getTemporary( uint32_t cfgId, uint32_t index ) const
            {
                return m_temporaries.get( cfgId, index );
            }

            const auto& retVal() const { return m_retVal; }
            void setRetVal( const Value& val ) { m_retVal = val; }

        private:
            TempStorage< optional< Value > > m_temporaries;

    if( !pFunc || !pFunc->isValid() )
        return PoisonValue();

    Frame f;

    llvm::SmallVector< optional< Value >, 8 > args;
    args.reserve( vec.terms().size() );

    for( auto&& a : vec.terms() )
    {
        auto val = ValueFromIRExpr( a );
        assert( val );

        auto newVal = Evaluate( *val, *this );
        if( newVal.isPoison()  )
            return PoisonValue();

        if( !newVal.isConstant() )
        {
            DiagnosticsManager::GetInstance().emitErrorMessage( 0,
                "Execute: args evaluation failed." );
            return PoisonValue();
        }

        args.emplace_back( move( newVal ) );
    }

    f.setArgs( move( args ) );

    swap( m_frame, f );
    auto result = execute( *pFunc->body() );
    swap( m_frame, f );

    return result;
}

optional< Value > VM::ExecuteBuiltinFuncCall( const Value& func, const Term& args )
{
    const auto& f = GetBuiltinFuncWrapper( func );
    return f( args );
}

optional< Value > VM::execute( const llr::CreateTemporary& ct )
{
    m_frame.setTemporary( ct.cfgId(), ct.index(), Evaluate( ct.value(), *this ) );
    return nullopt;
}

optional< Value > VM::execute( const llr::GetTemporary& gt )
{
    const auto* pVal = m_frame.getTemporary( gt.cfgId(), gt.index() );
    assert( pVal );
    if( !pVal )
        return PoisonValue();
    return *pVal;
}

optional< Value > VM::execute( const llr::GetVar& gv )
{
    const auto* pVal = m_frame.getTemporary( gv.cfgId(), gv.index() );
    if( !pVal )
        return PoisonValue();

    return *pVal;
}

optional< Value > VM::execute( const llr::SetVar& sv )
{
    auto result = Evaluate( sv.value(), *this );
    if( !result.isConstant() )
        result = PoisonValue();

    m_frame.setTemporary( sv.cfgId(), sv.index(), result );
    return nullopt;
}

optional< Value > VM::execute( const llr::Phi& p )
{
    p.forAllIncomings( [&]( auto&& bb, auto&& val )
    {
        if( bb == m_pPreviousBB )
        {
            m_frame.setTemporary( p.destCfgId(), p.destIndex(), Evaluate( val, *this ) );
            return false;
        }

        return true;
    } );

    return PoisonValue();

#ifndef GOOSE_LLR_ALLOCVAR_H
#define GOOSE_LLR_ALLOCVAR_H

namespace goose::llr
{
    class AllocVar
    {
        public:
            template< typename T >
            AllocVar( T&& type, uint32_t cfgId, uint32_t index ) :
                m_type( forward< T >( type ) ),
                m_cfgId( cfgId ),
                m_index( index )
            {}

            const auto& type() const { return m_type; }
            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }

            bool canBeExecuted() const
            {
                return true;
            }

            bool canBeEagerlyEvaluated() const
            {
                return false;
            }

        private:
            ir::Value m_type;
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
    };
}

#endif

#ifndef GOOSE_LLR_CFG_H
#define GOOSE_LLR_CFG_H

namespace goose::llr
{
    class BasicBlock;

    class CFG : public enable_shared_from_this< CFG >
    {
        public:




            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; }

            // 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(); }

            // TODO: remove.
            auto uniqueId() const { return 1; }

            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 setVariableModifiedByLoop( uint32_t loopId, const ir::Term& type, uint32_t cfgId, uint32_t varId )
            {
                m_loopModifiedVariables.emplace( loopId, make_tuple( type, cfgId, varId ) );
            }

            template< typename F >
            void forEachVariableModifiedInLoop( uint32_t loopId, F&& func ) const
            {
                auto&& [begin, end] = m_loopModifiedVariables.equal_range( loopId );
                for( auto it = begin; it != end; ++it )
                    func( get< 0 >( it->second ), get< 1 >( it->second ), get< 2 >( it->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 the indices of all the variables modified
            // during that loop.
            // May be be empty if it has not (yet) been computed.
            unordered_multimap< uint32_t, tuple< ir::Term, uint32_t, uint32_t > >
                m_loopModifiedVariables;

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

            uint32_t m_loopCount = 0;

        } );
        auto id = builder.getNodeId( &instr.value() );

        GraphVizBuilder::Row row( builder );
        GraphVizBuilder::Cell cell( builder );
        GraphVizBuilder::Color col( builder, GraphVizBuilder::GetNodeColor( id ) );

        builder.output() << "CreateTemporary " << instr.cfgId() << ", " << instr.index() << ", " << id;
        builder.addEdge( builder.currentNodeId(), id );
    }

    void CfgViz( GraphVizBuilder& builder, const GetTemporary& instr )
    {
        GraphVizBuilder::Row row( builder );
        GraphVizBuilder::Cell cell( builder );
        GraphVizBuilder::Color col( builder );
        builder.output() << "GetTemporary " << instr.cfgId() << ", " << instr.index();
    }

    void CfgViz( GraphVizBuilder& builder, const AllocVar& instr )
    {
        GraphVizBuilder::Row row( builder );
        GraphVizBuilder::Cell cell( builder );
        GraphVizBuilder::Color col( builder );
        builder.output() << "AllocVar " << instr.cfgId() << ", " << instr.index();
    }

    void CfgViz( GraphVizBuilder& builder, const GetVar& instr )
    {
        GraphVizBuilder::Row row( builder );
        GraphVizBuilder::Cell cell( builder );
        GraphVizBuilder::Color col( builder );
        builder.output() << "GetVar " << instr.cfgId() << ", " << instr.index();
    }

    void CfgViz( GraphVizBuilder& builder, const SetVar& instr )
    {
        GraphVizBuilder::Row row( builder );
        GraphVizBuilder::Cell cell( builder );
        GraphVizBuilder::Color col( builder );
        builder.output() << "SetVar " << instr.cfgId() << ", " << instr.index();
    }

    void CfgViz( GraphVizBuilder& builder, const Phi& instr )
    {
        {
            GraphVizBuilder::Row row( builder );
            GraphVizBuilder::Cell cell( builder );

#ifndef GOOSE_LLR_CREATETEMPORARY_H
#define GOOSE_LLR_CREATETEMPORARY_H

namespace goose::llr
{
    class CreateTemporary
    {
        public:
            template< typename V >
            CreateTemporary( uint32_t cfgId, uint32_t index, V&& val ) :
                m_cfgId( cfgId ),
                m_index( index ),
                m_value( forward< V >( val ) )
            {}

            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }
            const auto& value() const { return m_value; }

            bool canBeExecuted() const
            {
                return IsValueConstantOrExecutable( m_value );
            }

            bool canBeEagerlyEvaluated() const
            {
                return CanValueBeEagerlyEvaluated( m_value );
            }

        private:
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
            ir::Value m_value;
    };
}

#endif

#ifndef GOOSE_LLR_GETTEMPORARY_H
#define GOOSE_LLR_GETTEMPORARY_H

namespace goose::llr
{
    class GetTemporary
    {
        public:
            template< typename T >
            GetTemporary( T&& type, uint32_t cfgId, uint32_t index ) :
                m_type( forward< T >( type ) ),
                m_cfgId( cfgId ),
                m_index( index )
            {}

            const auto& type() const { return m_type; }
            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }

            bool canBeExecuted() const
            {
                return true;
            }

            bool canBeEagerlyEvaluated() const
            {
                return false;
            }

        private:
            ir::Term m_type;
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
    };
}

#endif

    // executed eagerly (that is, not from within a function while that function
    // is being compiled).
    // So we do need to have both.
    class GetVar
    {
        public:
            template< typename T >
            GetVar( T&& type, uint32_t cfgId, uint32_t index ) :
                m_type( forward< T >( type ) ),
                m_cfgId( cfgId ),
                m_index( index )
            {}

            const auto& type() const { return m_type; }
            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }

            bool canBeExecuted() const
            {
                return true;
            }

            bool canBeEagerlyEvaluated() const
            {
                return false;
            }

        private:
            ir::Term m_type;
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
    };
}

#endif

    }

    template< typename T >
    class TempStorage
    {
        public:
            template< typename TT >
            auto& set( uint32_t cfgId, uint32_t index, TT&& x )
            {
                auto [it, inserted] = m_storage.try_emplace( cfgId );

                if( it->second.size() <= index )
                    it->second.resize( index + 1 );

                it->second[index] = forward< TT >( x );
                return it->second[index];
            }

            template< typename TT >
            void setVec( uint32_t cfgId, TT&& x )
            {
                auto [it, inserted] = m_storage.try_emplace( cfgId );
                it->second = forward< TT >( x );
            }

            const T* get( uint32_t cfgId, uint32_t index ) const
            {
                auto it = m_storage.find( cfgId );
                if( it == m_storage.end() )
                    return nullptr;

                if( it->second.size() <= index )
                    return nullptr;

                return &it->second[index];
            }

            T* get( uint32_t cfgId, uint32_t index )
            {
                auto it = m_storage.find( cfgId );
                if( it == m_storage.end() )
                    return nullptr;

                if( it->second.size() <= index )
                    return nullptr;

                return &it->second[index];
            }

        private:
            unordered_map< uint32_t, llvm::SmallVector< T, 8 > >
                m_storage;
    };
}

#endif

#include "llr.h"

namespace goose::llr
{
    void MarkVarChangedByLoop( const ptr< CFG >& cfg, uint32_t loopId, const ir::Term& type, uint32_t cfgId, uint32_t varId )
    {
        cfg->setVariableModifiedByLoop( loopId, type, cfgId, varId );

        const auto& pHeader = cfg->getBB( loopId );

        if( pHeader->loopId() )
            MarkVarChangedByLoop( cfg, pHeader->loopId(), type, cfgId, varId );
    }

    void ComputeLoopModifiedVars( const ptr< CFG >& cfg )
    {
        cfg->forEachBB( [&]( auto&& bb )
        {
            for( auto&& instr : *bb )
            {
                if( auto sv = get_if< SetVar >( &instr.content() ) )
                {
                    const auto& type = sv->value().type();

                    if( bb->isLoopHeader() )
                        MarkVarChangedByLoop( cfg, bb->index(), type, sv->cfgId(), sv->index() );
                    else if( bb->loopId() )
                        MarkVarChangedByLoop( cfg, bb->loopId(), type, sv->cfgId(), sv->index() );
                }
            }
        } );
    }
}

#ifndef GOOSE_LLR_PHI_H
#define GOOSE_LLR_PHI_H

namespace goose::llr
{
    class BasicBlock;

    class Phi
    {
        public:
            template< typename T >
            Phi( T&& type, uint32_t numIncomings, uint32_t destCfgId, uint32_t destIndex ) :
                m_type( forward< T >( type ) ),
                m_destCfgId( destCfgId ),
                m_destIndex( destIndex )
            {
                m_incomings.reserve( numIncomings );
            }

            const auto& type() const { return m_type; }
            const auto& destCfgId() const { return m_destCfgId; }
            const auto& destIndex() const { return m_destIndex; }

            void setIncoming( const ptr< BasicBlock >& bb, const ir::Value& val )
            {
                m_incomings.emplace_back( bb, val );
            }

            bool canBeEagerlyEvaluated() const
            {
                return true;
            }

        private:
            ir::Value m_type;
            uint32_t m_destCfgId = 0;
            uint32_t m_destIndex = 0;

            using incInfo = pair< wptr< BasicBlock >, ir::Value >;
            llvm::SmallVector< incInfo, 2 > m_incomings;

    };
}

#endif

#ifndef GOOSE_LLR_SETVAR_H
#define GOOSE_LLR_SETVAR_H

namespace goose::llr
{
    class SetVar
    {
        public:
            template< typename T >
            SetVar( T&& val, uint32_t cfgId, uint32_t index ) :
                m_value( forward< T >( val ) ),
                m_cfgId( cfgId ),
                m_index( index )
            {}

            const auto& value() const { return m_value; }
            const auto& cfgId() const { return m_cfgId; }
            const auto& index() const { return m_index; }

            bool canBeExecuted() const
            {
                return true;
            }

            bool canBeEagerlyEvaluated() const
            {
                return false;
            }

        private:
            ir::Value m_value;
            uint32_t m_cfgId = 0;
            uint32_t m_index = 0;
    };
}

#endif

using namespace goose::ir;
using namespace goose::llr;

SCENARIO( "Dominators test 1", "[llr-dom-1]" )
{
    WHEN( "Computing the dominators of an arbitrary CFG" )
    {
        auto cfg = make_shared< CFG >();

        auto bb1 = cfg->createBB();
        auto bb2 = cfg->createBB();
        auto bb3 = cfg->createBB();
        auto bb4 = cfg->createBB();
        auto bb5 = cfg->createBB();
        auto bb6 = cfg->createBB();

using namespace goose::ir;
using namespace goose::llr;

SCENARIO( "Dominators test 1", "[llr-dom-1]" )
{
    WHEN( "Computing the dominators of an arbitrary CFG" )
    {
        auto cfg = make_shared< CFG >();

        auto bb1 = cfg->createBB();
        auto bb2 = cfg->createBB();
        auto bb3 = cfg->createBB();
        auto bb4 = cfg->createBB();
        auto bb5 = cfg->createBB();
        auto bb6 = cfg->createBB();

            cout << "check_unsat " << ( *m_currentPredicate && !e ) << endl;
    }

    m_checkFailed = m_checkFailed || !result;
    return result;
}

const z3::expr* Builder::getVarForBasicBlock( uint32_t bbIndex, uint32_t cfgId, uint32_t index ) const
{
    const auto* vs = m_varStorage.get( cfgId, index );
    if( !vs )
        return nullptr;

    if( vs->size() <= bbIndex )
        return nullptr;

    const auto& optExpr = (*vs)[ bbIndex ];
    if( !optExpr )
        return nullptr;

    return &*optExpr;
}

const z3::expr& Builder::setVarForBasicBlock( uint32_t bbIndex, uint32_t cfgId, uint32_t index, z3::expr&& e )
{
    auto* vs = m_varStorage.get( cfgId, index );
    if( !vs )
    {
        VarState newVS;
        newVS.resize( bbIndex + 1 );
        vs = &m_varStorage.set( cfgId, index, move( newVS ) );
    }
    else if( vs->size() <= bbIndex )
        vs->resize( bbIndex + 1 );

    (*vs)[ bbIndex ] = move( e );
    return *(*vs)[ bbIndex ];
}

const z3::expr* Builder::retrieveVar( uint32_t cfgId, uint32_t index, const Term& type, uint32_t bbIndex )
{
    if( bbIndex == m_currentBBIndex )
        return  nullptr;

    if( bbIndex == ~0 )
        bbIndex = m_currentBBIndex;

    const auto* expr = getVarForBasicBlock( bbIndex, cfgId, index );
    if( expr )
        return expr;

    if( !m_cfg )
        return nullptr;

    auto newVar = BuildZ3ConstantFromType( type, format( "v{}", m_nextUniqueId++ ) );
    if( !newVar )
        return nullptr;

    auto& c = GetZ3Context();

    // Model the ssa phi operation by creating a series of equality assertions, each implied by
    // one of the possible incoming edge condition for the current basic block.
    if( m_remapper )
    {
        m_remapper->forEachIncomingEdge( bbIndex, [&]( auto&& predIndex, auto&& expr )
        {
            if( const auto* predVar = retrieveVar( cfgId, index, type, predIndex ) )
                add( z3::implies( c.bool_const( format( "e{}_{}", predIndex, bbIndex ).c_str() ), *newVar == *predVar ) );
        } );
    }

    return &setVarForBasicBlock( bbIndex, cfgId, index, move( *newVar ) );
}

void Builder::setVar( uint32_t cfgId, uint32_t index, const Value& val )
{
    if( !m_cfg )
        return;

    auto newVar = BuildZ3ConstantFromType( val.type(), format( "v{}", m_nextUniqueId++ ) );
    if( !newVar )
        return;

    if( auto expr = BuildZ3ExprFromValue( *this, val ) )
        assume( *newVar == *expr );

    setVarForBasicBlock( m_currentBBIndex, cfgId, index, move( *newVar ) );
}

void Builder::setVar( uint32_t cfgId, uint32_t index, z3::expr&& expr )
{
    setVarForBasicBlock( m_currentBBIndex, cfgId, index, move( expr ) );
}

void Builder::havocVar( uint32_t bbIndex, const Term& type, uint32_t cfgId, uint32_t index )
{
    if( !m_cfg )
        return;

    auto newVar = BuildZ3ConstantFromType( type, format( "v{}", m_nextUniqueId++ ) );
    if( !newVar )
        return;

    setVarForBasicBlock( bbIndex, cfgId, index, move( *newVar ) );
}

const z3::expr* Builder::retrievePlaceholder( const StringId& sid ) const
{
    auto it = m_placeholders.find( sid );
    if( it == m_placeholders.end() )
        return nullptr;

                m_currentPredicate = predicate;
            }

            void add( const z3::expr& e );
            void assume( const z3::expr& e );
            bool checkAssertion( const z3::expr& e, uint32_t locationId );

            const z3::expr* retrieveVar( uint32_t cfgId, uint32_t index, const Term& type, uint32_t bbIndex = ~0 );
            void setVar( uint32_t cfgId, uint32_t index, const Value& val );
            void setVar( uint32_t cfgId, uint32_t index, z3::expr&& expr );

            // Havoc (make undefined) a variable for a given basic block.
            void havocVar( uint32_t bbIndex, const Term& type, uint32_t cfgId, uint32_t index );

            const z3::expr* retrievePlaceholder( const StringId& sid ) const;
            void setPlaceholder( const StringId& sid, const z3::expr& expr );

            uint32_t newUniqueId() { return m_nextUniqueId++; }

            bool hasCheckFailed() const { return m_checkFailed; }

            template< typename F >
            void setAssertionHandler( F&& handler )
            {
                m_assertionHandler = forward< F >( handler );
            }

        private:
            const z3::expr* getVarForBasicBlock( uint32_t bbIndex, uint32_t cfgId, uint32_t index ) const;
            const z3::expr& setVarForBasicBlock( uint32_t bbIndex, uint32_t cfgId, uint32_t index, z3::expr&& e );

            z3::solver* m_solver = nullptr;
            Remapper* m_remapper = nullptr;

            ptr< llr::CFG > m_cfg;
            uint32_t m_currentBBIndex = 1;

        // Create a temporary builder to construct the z3 expressions out of the
        // function's pre-conditions and postconditions, configured
        // to perform the necessary replacements for arguments and for the
        // return value placeholder.
        Builder cb( *b.solver(), b.remapper() );

        // Inject the arguments in the context as variables of cfgId "0".
        // They will be picked up by getVars instructions when refered to
        // by the verification conditions.
        uint32_t index = 0;

        ForEachInVectorTerm( instr.args(), [&]( auto&& t )
        {
            auto arg = *ValueFromIRExpr( t );

            if( auto expr = BuildZ3ExprFromValue( b, arg ) )
                cb.setVar( 0, index++, move( *expr ) );

            return true;
        } );

        // Setup the return value placeholder
        if( retExpr )
            cb.setPlaceholder( "@"_sid, *retExpr );

            } );

            // Havoc all the variables modified during the current loop and emit
            // the first unrolling for the induction case.
            m_remapper.nextLoopIteration();
            uint32_t firstInductionIterationHeaderIndex = m_remapper.remapBBId( bb );

            m_cfg->forEachVariableModifiedInLoop( bb.index(), [&]( auto&& type, uint32_t cfgId, uint32_t varId )
            {
                m_builder.havocVar( firstInductionIterationHeaderIndex, type, cfgId, varId );
            } );

            buildZ3Expressions( bb, &parentWorkQueue );

            // Emit the rest of the induction case.
            uint32_t i = 1;
            while( i < k )

    }

    // Implemented in call.cpp
    extern optional< z3::expr > BuildZ3Op( Builder& b, const Call& instr );

    optional< z3::expr > BuildZ3Op( Builder& b, const CreateTemporary& instr )
    {
        b.setVar( instr.cfgId(), instr.index(), instr.value() );
        return nullopt;
    }

    optional< z3::expr > BuildZ3Op( Builder& b, const GetTemporary& instr )
    {
        const auto* expr = b.retrieveVar( instr.cfgId(), instr.index(), instr.type() );
        if( expr )
            return *expr;

        return BuildZ3ConstantFromType( instr.type(), format( "v{}_{}", instr.cfgId(), instr.index() ) );
    }

    optional< z3::expr > BuildZ3Op( Builder& b, const GetVar& instr )
    {
        const auto* expr = b.retrieveVar( instr.cfgId(), instr.index(), instr.type() );
        if( expr )
            return *expr;

        return BuildZ3ConstantFromType( instr.type(), format( "v{}_{}", instr.cfgId(), instr.index() ) );
    }

    optional< z3::expr > BuildZ3Op( Builder& b, const SetVar& instr )
    {
        b.setVar( instr.cfgId(), instr.index(), instr.value() );
        return nullopt;
    }

    // TODO: Phi. Construct an expression combining all of the incoming z3 expressions from all the possible incoming blocks.

    // TODO: LoadConstStr. Build a z3 str value.