linscan_regalloc.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/workers/linscan_regalloc.g.hh>
#include <lestes/backend_v2/workers/alloc_int_finder.g.hh>
#include <lestes/backend_v2/workers/bb_finder.g.hh>
#include <lestes/backend_v2/workers/helpers.hh>
#include <lestes/md/instructions/tm_instr.g.hh>
#include <lestes/md/registers/tm_register.g.hh>

#include <lestes/backend_v2/debug/debug.hh>

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

using namespace ::lestes::msg;
using namespace ::lestes::backend_v2::intercode;
using namespace ::lestes::backend_v2::debug;
using namespace ::lestes::md::instructions;
using namespace ::lestes::md::registers;

typedef set<ulint> id_set__type;
typedef vector<ulint> id_vector__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;
typedef map<ulint, srp<alloc_interval> > reg2alloc_int__type;
typedef map<srp<ge_operand_reg>, srp<tm_register> > ge_op_reg2tm_reg__type;

declare_logger(rlog);
initialize_logger( rlog, "register_allocator", backend_v2_logger );

/*!
        \brief Allocates registers to register operands.
*/
void linscan_regalloc::process() {
        rlog << "process start\n" << eolog;
        
        //Set all available registers free.
        setup_registers();
        
        //Get intervals for register allocation.
        waiting_intervals = alloc_int_vector__type::create(data_get()->alloc_ints_get());

        //Sort waiting intervals by increasing start point
        ::std::sort(waiting_intervals->begin(),waiting_intervals->end(),alloc_int_cmp1);
        
        for(alloc_int_vector__type::iterator it = waiting_intervals->begin(); it!=waiting_intervals->end();) {
                ptr<alloc_interval> interval = *it;

                //Remove old intervals.         
                expire_old_intervals(interval);
                
                //Allocate register for interval.
                ptr<tm_register> allocated_reg = get_free_register(interval);
                
                if ( allocated_reg ) {
                        //Free register for interval has been successfuly found.
                        interval->allocated_reg_set(allocated_reg);
                        
                        /*
                                Find interval that was previous owner of the register.
                                This information will help to set dependencies in order to
                                prevent scheduler to schedule these two intervals in a way 
                                where they overlap.
                        */
                        reg2alloc_int__type::iterator tmp = register_owners->find(allocated_reg->id_get());
                        
                        if ( tmp!=register_owners->end() ) {
                                interval->allocated_obj_prev_owner_set(tmp->second);
                        }
                        
                        set_register_owner(allocated_reg,interval);
                }
                
                //Set interval active.
                it = waiting_intervals->erase(it);
                active_intervals->push_back(interval);  
        }

        //Move rest of the active intervals to the expired intervals    
        for(alloc_int_vector__type::iterator it = active_intervals->begin(); it!=active_intervals->end();) {
                expired_intervals->push_back(*it);
                it = active_intervals->erase(it);
        }

        lassert(destroyers->size()==0); 
        lassert(waiting_intervals->size()==0);
        lassert(active_intervals->size()==0);
        
        rlog << "process end\n" << eolog;
}

/*!
        \brief Fills the all_registers set with all the available registers.
*/
void linscan_regalloc::setup_registers() {
        for(ulint i = R_UNDEFINED+1; i<RIT_TERMINATOR; ++i) {
                all_registers->insert(i);
        }
}


/*!
        \brief Finds a register that is to be assigned to a interval.
        
        It checks whether operand of the interval destroys another input operand of the currently processed pseudoinstruction. 
        If so, it returns a register assigned to the destroyed operand. In other case it looks to the free_registers set
        and picks a register that is compatible with the interval. If no free compatible register is found,
        it steals a register from an interval in active_intervals set.
        
        \param interval An interval.
        \return A free available register if found. NULL otherwise.
*/
ptr<tm_register> linscan_regalloc::get_free_register(ptr<alloc_interval> interval) {
        rlog << "get_free_register start\n" << eolog;
        
        ptr<tm_register> reg = get_destroyed_register(interval->operand_get());
        
        ptr<id_set__type> avail_regs;
        if (reg) {
                rlog << "** found destroyed register **\n" << eolog;
                lassert(free_registers->find(reg->id_get())!=free_registers->end());
                
                avail_regs = id_set__type::create();
                
                ptr<id_set__type> tmp_set = reg->aliases_get();
                
                ::std::set_intersection(
                        interval->allowed_registers_get()->begin(),
                        interval->allowed_registers_get()->end(),
                        tmp_set->begin(),
                        tmp_set->end(),
                        ::std::inserter(*avail_regs,avail_regs->begin()));              
        } else {
                avail_regs = id_set__type::create();
        
                ::std::set_intersection(
                        free_registers->begin(),
                        free_registers->end(),
                        interval->allowed_registers_get()->begin(),
                        interval->allowed_registers_get()->end(),
                        ::std::inserter(*avail_regs,avail_regs->begin()));              
        }
        
        if ( avail_regs->size()==0 ) {  
                //Sort active intervals by decreasing end point
                ::std::sort(active_intervals->begin(),active_intervals->end(),alloc_int_cmp2);

                //Steal register from an interval in active_interval set.
                for(alloc_int_vector__type::iterator it = active_intervals->begin(); it!=active_intervals->end();++it) {
                        ptr<alloc_interval> victim = *it;
                        
                        if ( !victim->allocated_reg_get() ) {
                                continue;
                        }
                        
                        ::std::set_intersection(
                                interval->allowed_registers_get()->begin(),
                                interval->allowed_registers_get()->end(),
                                victim->allocated_reg_get()->aliases_get()->begin(),
                                victim->allocated_reg_get()->aliases_get()->end(),
                                ::std::inserter(*avail_regs,avail_regs->begin()));
                                
                        if ( avail_regs->size()!=0 ) {
                                active_intervals->erase(it);
                                expired_intervals->push_back(victim);
                        
                                //return the allocated register and its aliases to the free register set.
                                used_registers->erase(victim->allocated_reg_get()->id_get());

                                //set register owner to the previous owner of the register.                             
                                set_register_owner(victim->allocated_reg_get(),victim->allocated_obj_prev_owner_get());
                                
                                victim->allocated_reg_set(NULL);
                                victim->allocated_obj_prev_owner_set(NULL);
                                break;
                        }
                }
        }
        
        if (avail_regs->size()!=0) {    
                reg = tm_register::instance(*avail_regs->begin());
        
                //Add the allocated register to the used register set
                used_registers->insert(reg->id_get());
        } else {
                reg = NULL;
        }
        
        rlog << "get_free_register end\n" << eolog;
        return reg;
}

/*!
        \brief Sets an interval as owner of a register in the register_owners map.
*/
void linscan_regalloc::set_register_owner(ptr<tm_register> reg, ptr<alloc_interval> interval) {
        for(id_set__type::iterator it = reg->aliases_get()->begin(); it!=reg->aliases_get()->end(); ++it) {
                (*register_owners)[*it] = interval; 
        }
}


/*!
        \brief Recomputes the free_registers set.
        
        free_registers <- all_registers - used_registers
*/
void linscan_regalloc::find_free_registers() {
        rlog << "find_free_registers start\n" << eolog;
        
        ptr<id_set__type> deep_used_registers = id_set__type::create();
        
        for(id_set__type::iterator it=used_registers->begin(); it!=used_registers->end(); ++it) {
                ptr<tm_register> reg = tm_register::instance(*it);
                
                ptr<id_set__type> new_deep_used_registers = id_set__type::create();
                
                ::std::set_union(
                        reg->aliases_get()->begin(),
                        reg->aliases_get()->end(),
                        deep_used_registers->begin(),
                        deep_used_registers->end(),
                        ::std::inserter(*new_deep_used_registers,new_deep_used_registers->begin()));
                        
                deep_used_registers = new_deep_used_registers;
        }
        
        ptr<id_set__type> updated_free_registers = id_set__type::create();
        
        ::std::set_difference(
                        all_registers->begin(),
                        all_registers->end(),
                        deep_used_registers->begin(),
                        deep_used_registers->end(),
                        ::std::inserter(*updated_free_registers,updated_free_registers->begin()));
                        
        free_registers = updated_free_registers;
        
        rlog << "find_free_registers end\n" << eolog;
}

/*!
        \brief Returns a target machine register that is destroyed by given operand within the currently processed pseudoinstruction.
*/
ptr<tm_register> linscan_regalloc::get_destroyed_register(ptr<ge_operand_reg> op) {
        rlog << "get_destroyed_register start\n" << eolog;
        
        ptr<tm_register> reg = NULL;
        
        ge_op_reg2tm_reg__type::iterator it = destroyers->find(op);
        
        if (it!=destroyers->end()) {
                reg = it->second;
                destroyers->erase(it);
        }
        
        rlog << "get_destroyed_register end\n" << eolog;
        return reg;
}

/*!
        \brief Sets an operand of a pseudoinstruction as destroyer of a register.
        
        \param ge A pseudoinstruction.
        \param op A destroyer.
        \param reg A destroyed operand.
*/
void linscan_regalloc::set_destroyed_register(ptr<ge_pi> ge, ptr<ge_operand_reg> op, ptr<tm_register> reg) {
        rlog << "set_destroyed_register start\n" << eolog;
        
        ptr<tm_instr_op_reg_base> tmop = ge_pi__find_tm_op_by_ge_op(ge,op);
        
        if ( !tmop ) {
                rlog << "set_destroyed_register end 1\n" << eolog;
                return;
        }
        
        ptr<id_vector__type> destroyed_by = tmop->destroyed_by_get();
        
        if ( !destroyed_by || destroyed_by->size()==0 ) {
                rlog << "set_destroyed_register end 2\n" << eolog;
                return;
        }
        
        ptr<tm_instr_base> tm = ge->instruction_get();
        lassert(tm);
                
        for(ulint i=0; i<destroyed_by->size();++i) {            
                ulint destroyer = (*destroyed_by)[i];
                
                for(ulint j=0; j<ge->operands_output_get()->size(); ++j) {
                        if ( (*tm->operands_output_get())[j]->id_get()==destroyer ) {
                                (*destroyers)[(*ge->operands_output_get())[j].dncast<ge_operand_reg>()] = reg;
                                rlog << "** destroyer set **\n" << eolog;
                                break;
                        }
                }
        }
        
        rlog << "set_destroyed_register end\n" << eolog;
        
}

/*!
        \brief Removes intervals whoose endpoints precede the currently processed interval from the active_intervals set.
        
        \param curr_interval A current interval.
*/
void linscan_regalloc::expire_old_intervals(ptr<alloc_interval> curr_interval) {
        rlog << "expire_old_intervals start\n" << eolog;
        
        ulint curr_point = curr_interval->start_get();
        
        for(alloc_int_vector__type::iterator it = active_intervals->begin(); it!=active_intervals->end();) {
                ptr<alloc_interval> interval = *it;
                
                if ( interval->end_get() <= curr_point ) {
                        rlog << "interval expired\n" << eolog;
                        
                        it = active_intervals->erase(it);
                        expired_intervals->push_back(interval);
                        
                        if ( interval->allocated_reg_get() ) {
                                //return the allocated register and its aliases to the free register set.
                                used_registers->erase(interval->allocated_reg_get()->id_get());
                                
                                if ( (*curr_interval->instructions_get())[0]==(*interval->instructions_get())[interval->instructions_get()->size()-1] ) {               
                                        set_destroyed_register((*curr_interval->instructions_get())[0],interval->operand_get(),interval->allocated_reg_get());
                                }
                        }
                        
                } else {
                        ++it;
                }
        }
        
        find_free_registers();
        
        rlog << "expire_old_intervals end\n" << eolog;
}

ptr<id_set__type> linscan_regalloc::ge_pi__get_allowed_regs_for_op(ptr<ge_pi> ge,ptr<ge_operand_reg> op) {
        rlog << "ge_pi__get_allowed_regs_for_op start\n" << eolog;
        
        //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);
                }
        }
        
        lassert(regs->size()!=0);
        
        rlog << "ge_pi__get_allowed_regs_for_op end\n" << eolog;
        return regs;
}

/*!
        \brief Returns a target machine operand description for given operand within given pseudoinstruction.
*/
ptr<tm_instr_op_reg_base> linscan_regalloc::ge_pi__find_tm_op_by_ge_op(ptr<ge_pi> ge,ptr<ge_operand_reg> op) {
        rlog << "ge_pi__find_tm_op_by_ge_op start\n" << eolog;
        
        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] ) {
                        rlog << "ge_pi__find_tm_op_by_ge_op end 1\n" << eolog;
                        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] ) {
                        rlog << "ge_pi__find_tm_op_by_ge_op end 2\n" << eolog;
                        return (*tm->operands_output_get())[i].dncast<tm_instr_op_reg_base>();
                }
        }
        
        rlog << "ge_pi__find_tm_op_by_ge_op end\n" << eolog;
        return NULL;
        
}

/*!
        \brief Sets up dependencies amoung dependent intervals.
        
        If two intervals uses the same register, it is needed to not allow them to overlap. It is done by
        setting dependence of a first pseudoinstruction of the second interval on a last pseudoinstruction 
        of the second interval.
*/
void linscan_regalloc::set_interval_dependencies() {
        rlog << "set_dependencies start\n" << eolog;
        /*
                If an interval B pick over register or spillplace of another interval A, it is important that the intervals
                don't overlap and they are executed in the right order (A->B). It is accomplished by setting dependencies
                among instructions of intervals.
        */
        for(alloc_int_vector__type::iterator it = expired_intervals->begin(); it!=expired_intervals->end(); ++it) {
                ptr<alloc_interval> interval = *it;
                ptr<alloc_interval> alloc_obj_prev_owner = interval->allocated_obj_prev_owner_get();
                
                if ( alloc_obj_prev_owner ) {
                        ptr<ge_pi> ge1 = alloc_obj_prev_owner->instructions_get()->back();
                        ptr<ge_pi> ge2 = interval->instructions_get()->front();
                        
                        if ( ge1->bb_get()==ge2->bb_get() ) {
                                ge2->dependencies_get()->insert(ge1);
                        }
                }
        }
        
        rlog << "set_dependencies end\n" << eolog;
}

/*!
        \brief Sets allocated registers of intervals to operands.
*/
void linscan_regalloc::set_registers_to_operands() {
        rlog << "set_registers start\n" << eolog;
        /*
                Set assigned_registers and assigned_spill_space properties of ge_operand_regs according to the result of
                the register allocation 
        */
        for(alloc_int_vector__type::iterator it = expired_intervals->begin(); it!=expired_intervals->end(); ++it) {
                ptr<alloc_interval> interval = *it;
                
                ptr<ge_operand_reg> operand = interval->operand_get();
                
                if ( interval->allocated_reg_get() ) {
                        //Operand has register assigned.
                        ulint assigned_register = interval->allocated_reg_get()->id_get();
                        
                        lassert(interval->allowed_registers_get()->find(assigned_register)!=interval->allowed_registers_get()->end());
                
                        ptr<ge_pi_vector__type> instructions = interval->instructions_get();
                        for(ge_pi_vector__type::iterator it2 = instructions->begin(); it2!=instructions->end(); ++it2) {
                                (*operand->assigned_registers_get())[*it2] = assigned_register;
                        }
                        
                }       
        }
        rlog << "set_registers end\n" << eolog;
}

/*!
        \brief Returns data of the currently processed function with result of the register allocation.
*/
ptr< ::lestes::backend_v2::structs::func_data > linscan_regalloc::get_result() {
        rlog << "get_result start\n" << eolog;
        
        set_registers_to_operands();
        
        set_interval_dependencies();
        
        data_get()->alloc_ints_set(expired_intervals);
        
        rlog << "get_result end\n" << eolog;
        return data_get();
}

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

---