liveness_analysis.cc

Go to the documentation of this file.

#include <lestes/backend_v2/structs/func_data.g.hh>
#include <lestes/backend_v2/intercode/visitor_pi_pi2id.g.hh>
#include <lestes/backend_v2/intercode/ge.g.hh>
#include <lestes/backend_v2/intercode/pi_mem_factory.g.hh>
#include <lestes/backend_v2/workers/liveness_analysis.g.hh>
#include <lestes/backend_v2/debug/debug.hh>

package(lestes);
package(backend_v2);
package(workers);

using namespace ::lestes::backend_v2::intercode;

typedef map< srp< ::lestes::backend_v2::intercode::ge_pi >, srp< ::lestes::std::pair< srp<set< srp< ::lestes::backend_v2::intercode::ge_operand_reg > > >, srp<set< srp< ::lestes::backend_v2::intercode::ge_operand_reg > > > > > > ge_pi2inout__type;
typedef list< srp<ge_pi> > ge_pi_list__type;
typedef set< srp< ::lestes::backend_v2::intercode::ge_operand_reg > > ge_op_set__type;
typedef ::lestes::std::pair< srp<ge_op_set__type>,srp<ge_op_set__type> > ge_op_set_pair__type;
typedef vector< srp<ge_operand> > ge_op_vector__type;
typedef vector< srp < ge_sp > > ge_sp_vector__type;
typedef map<srp<ge_operand>,srp<liveness_range> > ge_op2liveness__type;

/*
        \brief Computes live ranges of operands.
        
        foreach n in BODY: 
                in[n]<-{}; out[n]<-{};
        end_foreach
        
        repeat
        
                foreach n in BODY:
                        in'[n] <- in[n]
                        out'[n] <- out[n]
                        
                        in[n] <- use[n] UNION ( out[n] DIFFERENCE def[n] )
                        out[n] <- UNION[s from succ(n)](in[s])
                        
                end_foreach
                
        until in'==in || out'==out;
        
*/
void liveness_analysis::process() {

        ptr<visitor_pi_pi2id> pi2id = visitor_pi_pi2id::create();
        
        ptr<ge_pi_list__type> body = data_get()->ge_body_get(); 

        //initialise In and Out sets for every ge_pi in the body        
        for(ge_pi_list__type::iterator it = body->begin(); it!=body->end(); ++it) {
                ptr<ge_pi> ge =  *it;
                (*inout)[ge] = ge_op_set_pair__type::create(ge_op_set__type::create(),ge_op_set__type::create());
        }
                
        bool changed = true;
        
        while(changed) {
        
                changed = false;
                
                ptr<ge_pi> succ;
                
                for(ge_pi_list__type::reverse_iterator it = body->rbegin(); it!=body->rend(); ++it) {
                        ptr<ge_pi> ge =  *it;
                        
                        if ( ge->kind_get()==ge_pi::SP ) {
                                /*
                                        ge_sp usually has no operands.
                                        
                                        Exception is the case that some instruction A has to be done 
                                        and its output operands are not used elsewhere. So the pi_sp 
                                        is set to use these output operand in order     to not allow a 
                                        dead code elimination to delete the instruction A.
                                        These operands aren't real operands, so the ge_sp should
                                        not be included in their liveness rangess.
                                */
                                continue;
                        }
                        
                        ptr<ge_op_vector__type> in_ops = ge->operands_input_get();
                        ptr<ge_op_vector__type> out_ops = ge->operands_output_get();
                        
                        //old Inp and Out sets of the current ge_pi
                        ptr<ge_op_set_pair__type> ge_io = (*inout)[ge];
                        ptr<ge_op_set__type> old_in = ge_io->first;
                        ptr<ge_op_set__type> old_out = ge_io->second;
                        
                        //updated sets
                        ptr<ge_op_set__type> in = ge_op_set__type::create();
                        ptr<ge_op_set__type> out = ge_op_set__type::create();
                        
                        ge_io->first = in;
                        ge_io->second = out;
                        
                        /*
                                in[n] <- use[n] UNION ( out[n] DIFFERENCE def[n] )
                        */
                        for(ulint i=0; i<out_ops->size(); ++i) {
                                ptr<ge_operand> op = (*out_ops)[i];
                                
                                ptr<ge_operand_reg> reg = extract_reg_operand(op);
                                
                                if ( !reg ) {
                                        continue;
                                }
                                
                                if ( old_out->find(reg)==old_out->end() ) {
                                        in->insert(reg);
                                }
                        }
                        
                        for(ulint i=0; i<in_ops->size(); ++i) {
                                ptr<ge_operand> op = (*in_ops)[i];
                                
                                ptr<ge_operand_reg> reg = extract_reg_operand(op);
                                
                                if ( !reg ) {
                                        continue;
                                }
                                
                                in->insert(reg);
                        }
                        
                        
                        /*
                                out[n] <- UNION[s from succ(n)](in[s])
                        */
                        
                        visitor_pi_pi2id::kind_type pi_id = visitor_pi_pi2id::PI_ADD;
                        
                        if ( ge->pi_source_get() ) {
                                        pi_id = (visitor_pi_pi2id::kind_type)ge->pi_source_get()->accept_visitor_pi_pi2ulint_gen_base(pi2id);
                        }
                        
                        switch ( pi_id ) {
                                case visitor_pi_pi2id::PI_BA:
                                case visitor_pi_pi2id::PI_LEAVE: {
                                        /*
                                                pi_ba and pi_leave always jumps to its target. 
                                                The following instruction in scheduled order is not successor.
                                        */              
                                        ptr<ge_sp_vector__type> targets = ge->jmp_targets_get();
                                        
                                        if (  targets && targets->size()!=0 ) {
                                        
                                                for(ulint i=0; i<targets->size(); ++i) {
                                                        ptr<ge_op_set_pair__type> succ_io = (*inout)[(*targets)[i]];
                                                        ptr<ge_op_set__type> succ_in = succ_io->first;
                                                        
                                                        set_union(
                                                                out->begin(),
                                                                out->end(),
                                                                succ_in->begin(),
                                                                succ_in->end(),
                                                                ::std::insert_iterator<ge_op_set__type>(*out,out->begin()));
                                                }
                                        }
                                        
                                } break;
                                
                                case visitor_pi_pi2id::PI_BN: {
                                        /*
                                                pi_bn never jumps to its target. 
                                                The following instruction in scheduled order is the only successor.
                                        */
                                        if ( succ ) {
                                                ptr<ge_op_set_pair__type> succ_io = (*inout)[succ];
                                                ptr<ge_op_set__type> succ_in = succ_io->first;
                                                
                                                set_union(
                                                        out->begin(),
                                                        out->end(),
                                                        succ_in->begin(),
                                                        succ_in->end(),
                                                        ::std::insert_iterator<ge_op_set__type>(*out,out->begin()));
                                        }
                                        
                                } break;
                                
                                default: {
                                        
                                        /*
                                                The following instruction in scheduled order is successor.
                                        */
                                        if ( succ ) {
                                                ptr<ge_op_set_pair__type> succ_io = (*inout)[succ];
                                                ptr<ge_op_set__type> succ_in = succ_io->first;
                                                
                                                set_union(
                                                        out->begin(),
                                                        out->end(),
                                                        succ_in->begin(),
                                                        succ_in->end(),
                                                        ::std::insert_iterator<ge_op_set__type>(*out,out->begin()));
                                        }
                                        
                                        /*
                                                Successors of a branch instruction are its targets too.
                                        */
                                        ptr<ge_sp_vector__type> targets = ge->jmp_targets_get();
                                        if (  targets && targets->size()!=0 ) {
                                                
                                                for(ulint i=0; i<targets->size(); ++i) {
                                                        ptr<ge_op_set_pair__type> succ_io = (*inout)[(*targets)[i]];
                                                        ptr<ge_op_set__type> succ_in = succ_io->first;
                                                        
                                                        set_union(
                                                                out->begin(),
                                                                out->end(),
                                                                succ_in->begin(),
                                                                succ_in->end(),
                                                                ::std::insert_iterator<ge_op_set__type>(*out,out->begin()));
                                                }
                                        }
                                        
                                } break;
                                
                        }
                                
                        //Test whether In or Out set has been changed.
                        if ( in->size()!=old_in->size() || out->size()!=old_out->size() ) {
                                changed = true;
                        }
                        
                        succ = ge;
                        
                }       
        }
        
}

/*!
        \brief If a instance of ge_operand is of type the ge_operand_reg, then returns the instace casted as ge_operand_reg.
        
        \param op The operand instance.
        \return The operand casted as ge_operand_reg.
*/
ptr<ge_operand_reg> liveness_analysis::extract_reg_operand(ptr<ge_operand> op) {
        ptr<ge_operand_reg> reg = NULL;
        
        if ( op->kind_get()==ge_operand::REGISTER ) {
                reg = op.dncast<ge_operand_reg>();
        }       

        return reg;
}

/*!
        \brief Returns a vector of the computed live ranges.
*/
ptr<vector<srp<liveness_range> > > liveness_analysis::get_result() {
        ptr<vector<srp<liveness_range> > > output = vector<srp<liveness_range> >::create();
        
        //Live ranges of operands
        ptr<ge_op2liveness__type> op2live = ge_op2liveness__type::create();

        ptr<ge_pi_list__type> body = data_get()->ge_body_get(); 
        
        for(ge_pi_list__type::iterator it = body->begin(); it!=body->end(); ++it) {
                ptr<ge_pi> ge =  *it;
                
                ptr<ge_op_set__type> ge_io = (*inout)[ge]->first;
                
                for(ge_op_set__type::iterator it_op = ge_io->begin(); it_op!=ge_io->end(); ++it_op) { 
                        ptr<ge_operand_reg> reg = *it_op;
                        
                        ptr<liveness_range> rng;
                        
                        ge_op2liveness__type::iterator live_it = op2live->find(reg);
                        
                        if ( live_it==op2live->end() ) {
                                rng = liveness_range::create(reg,ge->schedule_pos_get(),ge->schedule_pos_get());
                                output->push_back(rng);
                                (*op2live)[reg] = rng;
                        } else {
                                rng = live_it->second;
                                rng->end_set(ge->schedule_pos_get());
                        }
                        
                        rng->instructions_get()->push_back(ge);
                }
        }
                
        return output;
}


end_package(workers);
end_package(backend_v2);
end_package(lestes);

---