<commit_before>//
//  xec_ssa_liveness.cpp
//
//  Created by <NAME> on 17/08/2014.
//  Copyright (c) 2014 <NAME>. All rights reserved.
//


#include "xec_ssa_liveness.h"
#include <make_unique>
#include "xec_script.h"
#include "xec_ssa.h"
#include "xec_ssa_print.h"
#include "xec_ssa_cfganalysis.h"


/*
    
    Useful papers about liveness analysis:

    http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer10a.pdf

    Linear Scan Register Allocation on SSA Form
        by <NAME>, <NAME>

    http://hal.archives-ouvertes.fr/docs/00/55/85/09/PDF/RR-7503.pdf

    Computing Liveness Sets for SSA-Form Programs (2011)
        by <NAME>, <NAME>, <NAME>,
            <NAME>, <NAME>
            
*/


/*
    TODO: Eliminate XEC_SSA_FOREVER and merge live spans in adjacent
            blocks to create spans that cross block boundaries - this
            will massively reduce span count and make register
            allocation faster.
*/



xec_ssa_liveness::livespan::livespan(
                xec_ssa_opref value, xec_ssa_opref until, xec_ssa_opref lnext )
    :   value( value )
    ,   until( until )
    ,   lnext( lnext )
{
}



xec_ssa_liveness::xec_ssa_liveness( xec_ssa* root )
    :   root( root )
    ,   func( NULL )
    ,   dfo( NULL )
    ,   loops( NULL )
{
}


void xec_ssa_liveness::analyze_func(
        xec_ssa_func* func, xec_ssa_dfo* dfo, xec_ssa_loop_forest* loops )
{
    region_scope rscope( root->alloc );

    this->func  = func;
    this->dfo   = dfo;
    this->loops = loops;
    livein.clear();

    // Go through blocks in reverse dfo order.
    for ( int i = (int)dfo->size() - 1; i >= 0; --i )
    {
        xec_ssa_block* block = dfo->at( i );
        analyze_block( block );
    }
    
    
    this->func  = NULL;
    this->dfo   = NULL;
    this->loops = NULL;
    livein.clear();
}




void xec_ssa_liveness::analyze_block( xec_ssa_block* block )
{
    // Find lowest point of use of all live values.
    liveset live;

    
    // At the bottom of the block, all variables that are live on entry to
    // successor blocks are live.  This includes all references in ɸ-functions
    // from this code path.
    if ( block->condition )
    {
        add_successor( &live, block, block->iftrue );
        add_successor( &live, block, block->iffalse );
        
        // The condition is also live at the bottom of the block.  However
        // next ops don't require live ranges as they return their continue
        // result in special 'register' @done.
        xec_ssa_op* condop = func->getop( block->condition );
        if ( condop->opcode != XEC_SSA_NEXT )
        {
            livespan s( block->condition, XEC_SSA_FOREVER, XEC_SSA_INVALID );
            live.emplace( block->condition, s );
        }
    }
    else
    {
        add_successor( &live, block, block->next );
    }


    // Add all values used in the block.  Don't include phi functions as those
    // will be dealt with by the calculation for predecessor blocks.
    std::vector< xec_ssa_opref > oprefs;
    for ( int i = (int)block->ops->ops.size() - 1; i >= 0; --i )
    {
        xec_ssa_op& op = block->ops->ops.at( i );

        if ( op.opcode == XEC_SSA_SELECT )
        {
            // A call/yield/next and its accompanying select ops are a single
            // unit - do not introduce a live range for the call op if the only
            // references to it are with selects.
            continue;
        }

        xec_ssa_opref useref;
        useref.slice = block->ops->index;
        useref.index = i;
        
        op.get_operands( &oprefs );
        for ( size_t i = 0; i < oprefs.size(); ++i )
        {
            xec_ssa_opref operand = oprefs.at( i );
            operand = func->operand( operand );
            livespan s( operand, useref, XEC_SSA_INVALID );
            live.emplace( operand, s );
        }<commit_msg>probably closures should be changed to identify upval numbers directly.<commit_after>//
//  xec_ssa_liveness.cpp
//
//  Created by <NAME> on 17/08/2014.
//  Copyright (c) 2014 <NAME>. All rights reserved.
//


#include "xec_ssa_liveness.h"
#include <make_unique>
#include "xec_script.h"
#include "xec_ssa.h"
#include "xec_ssa_print.h"
#include "xec_ssa_cfganalysis.h"


/*
    
    Useful papers about liveness analysis:

    http://www.christianwimmer.at/Publications/Wimmer10a/Wimmer10a.pdf

    Linear Scan Register Allocation on SSA Form
        by <NAME>, <NAME>

    http://hal.archives-ouvertes.fr/docs/00/55/85/09/PDF/RR-7503.pdf

    Computing Liveness Sets for SSA-Form Programs (2011)
        by <NAME>, <NAME>, <NAME>,
            <NAME>, <NAME>
            
*/


/*
    TODO: Eliminate XEC_SSA_FOREVER and merge live spans in adjacent
            blocks to create spans that cross block boundaries - this
            will massively reduce span count and make register
            allocation faster.
*/



xec_ssa_liveness::livespan::livespan(
                xec_ssa_opref value, xec_ssa_opref until, xec_ssa_opref lnext )
    :   value( value )
    ,   until( until )
    ,   lnext( lnext )
{
}



xec_ssa_liveness::xec_ssa_liveness( xec_ssa* root )
    :   root( root )
    ,   func( NULL )
    ,   dfo( NULL )
    ,   loops( NULL )
{
}


void xec_ssa_liveness::analyze_func(
        xec_ssa_func* func, xec_ssa_dfo* dfo, xec_ssa_loop_forest* loops )
{
    region_scope rscope( root->alloc );

    this->func  = func;
    this->dfo   = dfo;
    this->loops = loops;
    livein.clear();

    // Go through blocks in reverse dfo order.
    for ( int i = (int)dfo->size() - 1; i >= 0; --i )
    {
        xec_ssa_block* block = dfo->at( i );
        analyze_block( block );
    }
    
    
    this->func  = NULL;
    this->dfo   = NULL;
    this->loops = NULL;
    livein.clear();
}




void xec_ssa_liveness::analyze_block( xec_ssa_block* block )
{
    // Find lowest point of use of all live values.
    liveset live;

    
    // At the bottom of the block, all variables that are live on entry to
    // successor blocks are live.  This includes all references in ɸ-functions
    // from this code path.
    if ( block->condition )
    {
        add_successor( &live, block, block->iftrue );
        add_successor( &live, block, block->iffalse );
        
        // The condition is also live at the bottom of the block.  However
        // next ops don't require live ranges as they return their continue
        // result in special 'register' @done.
        xec_ssa_op* condop = func->getop( block->condition );
        if ( condop->opcode != XEC_SSA_NEXT )
        {
            livespan s( block->condition, XEC_SSA_FOREVER, XEC_SSA_INVALID );
            live.emplace( block->condition, s );
        }
    }
    else
    {
        add_successor( &live, block, block->next );
    }


    // Add all values used in the block.  Don't include phi functions as those
    // will be dealt with by the calculation for predecessor blocks.
    std::vector< xec_ssa_opref > oprefs;
    for ( int i = (int)block->ops->ops.size() - 1; i >= 0; --i )
    {
        xec_ssa_op& op = block->ops->ops.at( i );

        if ( op.opcode == XEC_SSA_SELECT )
        {
            // A call/yield/next and its accompanying select ops are a single
            // unit - do not introduce a live range for the call op if the only
            // references to it are with selects.
            continue;
        }

        xec_ssa_opref useref;
        useref.slice = block->ops->index;
        useref.index = i;
        
        op.get_operands( &oprefs );
        for ( size_t i = 0; i < oprefs.size(); ++i )
        {
            xec_ssa_opref operand = oprefs.at( i );
            
            if ( op.opcode == XEC_SSA_CLOSURE )
            {
                xec_ssa_op* opop = func->getop( func->operand( operand ) );
                if ( opop->opcode == XEC_SSA_REFUP )
                {
                    // Don't introduce live ranges for upval refs whose only
                    // reference is a closure.
                    continue;
                }
            }
            
            operand = func->operand( operand );
            livespan s( operand, useref, XEC_SSA_INVALID );
            live.emplace( operand, s );
        }
{'fraction_non_alphanumeric': 0.10879883169039796, 'fraction_numerical': 0.009005719849093343, 'mean_word_length': 1.951867816091954, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 82, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2756973', 'n_tokens_mistral': 2858, 'n_tokens_neox': 2733, 'n_words': 748}