alloc_int_finder.cc

Go to the documentation of this file.

#include <lestes/backend_v2/structs/func_data.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/md/registers/tm_register.g.hh>
#include <lestes/md/registers/move_generator.g.hh>
#include <lestes/backend_v2/workers/alloc_int_finder.g.hh>

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

using namespace ::lestes::backend_v2::intercode;
using namespace ::lestes::backend_v2::structs;
using namespace ::lestes::md::instructions;
using namespace ::lestes::md::registers;
using namespace ::lestes::md::mem;

typedef set<ulint> id_set__type;
typedef vector<srp<ge_pi> > ge_pi_vector__type;
typedef vector<srp<liveness_range> > liveness_rng_vector__type;
typedef vector<srp<alloc_interval> > alloc_int_vector__type;

/*!
        \brief Splits live ranges to regalloc intervals.
        
        It traverses list of live ranges and splits every range to intervals that
        have nonempty intersection of allowed register sets.
*/
void alloc_int_finder::process() {

        //Find liveness ranges.
        ptr<liveness_analysis> liveness = liveness_analysis::create(data_get());
        liveness->process();
        ptr<liveness_rng_vector__type> liveness_rngs = liveness->get_result();  
        
        
        ptr<alloc_int_vector__type> ints = data_get()->alloc_ints_get();
        
        /*
                Go through liveness ranges and try split them to intervals with nonempty intersections
                of allowed registers. 
        */
        for(liveness_rng_vector__type::iterator it1 = liveness_rngs->begin(); it1!=liveness_rngs->end(); ++it1) {
                ptr<liveness_range> rng = *it1;
                ptr<ge_operand_reg> operand = rng->operand_get();
                
                ptr<alloc_interval> prev_inter = NULL;
                
                ptr<alloc_interval> inter = NULL;
                ptr<id_set__type> int_allowed_regs = NULL;
                ptr<ge_pi_vector__type> int_instrs = NULL;
                
                ptr<ge_pi_vector__type> rng_instrs = rng->instructions_get();
                
                /*
                        Create intervals of the range's instructions with non-empty intersection
                        of allowed registers.
                */
                for(ge_pi_vector__type::iterator it2 = rng_instrs->begin(); it2!=rng_instrs->end();) {
                        ptr<ge_pi> ge = *it2;

                        if ( !inter ) {
                                inter = alloc_interval::create(operand,rng);
                                ints->push_back(inter);
                
                                int_allowed_regs = NULL;
                                int_instrs = inter->instructions_get();
                                
                                
                                if ( !prev_inter ) {
                                        /*
                                                Insert operand's origin to the first interval.
                                        
                                                NOTE: This is ok, because of the register allocator does old interval expiration
                                                before searching for free registers. So if live range of an operand ends as input 
                                                operand of a ge_pi, register that is allocated for the operand is emediatly free
                                                for any output operand of the ge_pi.
                                        */
                                        if ( operand->origin_get() ) {
                                                if ( operand->origin_get()->kind_get()!=ge_pi::SP ) { //origin can be a ge_sp instruction.
                                                        int_allowed_regs = ge_pi__get_allowed_regs_for_op(operand->origin_get(),operand);
                                                }
                                
                                                int_instrs->push_back(operand->origin_get());
                                        }       
                                } 
                        }
                        
                        if ( ge==operand->origin_get() ) {
                                //The ge_pi is already in interval.
                                ++it2;
                                continue;
                        }
                        
                        if ( ge->kind_get()==ge_pi::SP ) {
                                ++it2;
                                int_instrs->push_back(ge);
                                continue;
                        }
                        
                        ptr<id_set__type> int_allowed_regs_tmp = id_set__type::create();
                                
                        ptr<id_set__type> op_allowed_regs = ge_pi__get_allowed_regs_for_op(ge,operand);
                        
                        if ( !int_allowed_regs ) {
                                //The first instruction in the set
                                int_allowed_regs_tmp->insert(op_allowed_regs->begin(),op_allowed_regs->end());
                                int_allowed_regs = int_allowed_regs_tmp;
                        } else {
                                /*
                                        N'th instruction in the set. Compute allowed intersection of allowed registers for interval and 
                                        instruction.
                                */
                                set_intersection(
                                        int_allowed_regs->begin(),
                                        int_allowed_regs->end(),
                                        op_allowed_regs->begin(),
                                        op_allowed_regs->end(),
                                        ::std::insert_iterator<id_set__type>(*int_allowed_regs_tmp,int_allowed_regs_tmp->begin()));
                        }
                        
                        if ( int_allowed_regs_tmp->size()==0 ) {
                                //Intersection is empty. Split intervals.
                                lassert(int_instrs->size()!=0);
                                
                                inter->allowed_registers_set(int_allowed_regs);
                                
                                if ( prev_inter ) {
                                        inter->start_set(prev_inter->instructions_get()->back()->schedule_pos_get());
                                        prev_inter->end_set(int_instrs->front()->schedule_pos_get());
                                } else {
                                        inter->start_set(int_instrs->front()->schedule_pos_get());
                                }
                                
                                inter->end_set(int_instrs->back()->schedule_pos_get());
                                
                                if ( prev_inter ) {
                                        inter->prev_set(prev_inter);
                                        prev_inter->next_set(inter);
                                }
                                
                                prev_inter = inter;
                                
                                inter = NULL;
                        } else {
                                //Intersection is non-empty.
                                int_allowed_regs = int_allowed_regs_tmp;
                                int_instrs->push_back(ge);
                                ++it2;  
                        }
                        
                        
                }
                
                if ( inter ) {
                        //Finish the last interval.
                        lassert(int_instrs->size()!=0);
                        
                        inter->allowed_registers_set(int_allowed_regs);
                                
                        if ( prev_inter ) {
                                inter->start_set(prev_inter->instructions_get()->back()->schedule_pos_get());
                                prev_inter->end_set(int_instrs->front()->schedule_pos_get());
                        } else {
                                inter->start_set(int_instrs->front()->schedule_pos_get());
                        }
        
                        inter->end_set(int_instrs->back()->schedule_pos_get());
                                
                        if ( prev_inter ) {
                                inter->prev_set(prev_inter);
                                prev_inter->next_set(inter);
                        }
                }
                
        }
        
}

/*!
        \brief Returns set of allowed register for an operand within a pseudoinstruction.
        
        \param ge A pseudoinstruction.
        \param op An operand.
        \return Id set of allowed registers.
*/
ptr<id_set__type> alloc_int_finder::ge_pi__get_allowed_regs_for_op(ptr<ge_pi> ge,ptr<ge_operand_reg> op) {
        
        //get target machine description of the operand
        ptr<tm_instr_op_reg_base> tm_op = ge_pi__find_tm_op_by_ge_op(ge,op);
        lassert(tm_op);
        
        //allowed registers
        ptr<id_set__type> regs = id_set__type::create(tm_op->allowed_registers_get());
        
        ulint type_id = op->type_get()->id_get();
        /*
                There are registers in the allowed register set that are incompatible with the operands datatype.
                Those registers need to be removed from the set. 
        */
        for(id_set__type::iterator it = regs->begin(); it!=regs->end();) {
                ptr<tm_register_base> reg = tm_register::instance(*it);
                if ( reg->compatible_types_get()->find(type_id)==reg->compatible_types_get()->end() ) {
                        id_set__type::iterator del_it = it++;
                        regs->erase(del_it);
                } else {
                        ++it;
                }
        }
        
        lassert(regs->size()!=0);
        
        return regs;
}

/*!
        \brief Returns a target operand description that corresponds to an operand within a pseudoinstruction.
        
        \param ge A pseudoinstruction.
        \param op An operand.
        \return A target machine operand description.
*/
ptr<tm_instr_op_reg_base> alloc_int_finder::ge_pi__find_tm_op_by_ge_op(ptr<ge_pi> ge,ptr<ge_operand_reg> op) {
        ptr<tm_instr_base> tm = ge->instruction_get();
        
        lassert(tm);
                                
        for(ulint i=0; i<ge->operands_input_get()->size(); ++i) {
                if ( op==(*ge->operands_input_get())[i] ) {
                        return (*tm->operands_input_get())[i].dncast<tm_instr_op_reg_base>();
                }
        }
        
        for(ulint i=0; i<ge->operands_output_get()->size(); ++i) {
                if ( op==(*ge->operands_output_get())[i] ) {
                        return (*tm->operands_output_get())[i].dncast<tm_instr_op_reg_base>();
                }
        }
        
        return NULL;
        
}


/*!
        \brief Returns data of a processed function with result of the worker included.
        
        \return Data of a processed function.
*/
ptr<func_data> alloc_int_finder::get_result() {
        return data_get();
}

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

---