spillgen.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.g.hh>
#include <lestes/backend_v2/workers/spillgen.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/mem/mem_alloc_manager.g.hh>
#include <lestes/md/registers/tm_register.g.hh>
#include <lestes/md/registers/move_generator.g.hh>
#include <lestes/md/instructions/tm_instr.g.hh>
#include <lestes/md/types/tm_data_type.g.hh>
#include <lestes/lang/cplus/sem/ss_declaration.g.hh>

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

using namespace ::lestes::msg;
using namespace ::lestes::backend_v2::intercode;
using namespace ::lestes::md::instructions;
using namespace ::lestes::md::registers;
using namespace ::lestes::md::mem;
using namespace ::lestes::md::types;

typedef set<srp<pi_mem_factory> > mf_set__type;
typedef set<ulint> id_set__type;
typedef vector<ulint> id_vector__type;
typedef list<srp<ge_pi> > ge_pi_list__type;
typedef vector<srp<liveness_range> > liveness_rng_vector__type;
typedef vector<srp<alloc_interval> > alloc_int_vector__type;
typedef vector<srp<ge_operand> > ge_operand_vector__type;
typedef vector<srp<ge_pi> > ge_pi_vector__type;
typedef set<srp<ge_pi> > ge_pi_set__type;
typedef set<srp<ge_operand_reg> > ge_op_reg_set__type;
typedef map<srp<pi_mem_factory>, srp<ge_pi> > mf2ge_pi__type;
typedef map<ulint, srp<alloc_interval> > reg2alloc_int__type;
typedef map<ulint, srp<ge_pi> > reg2ge_pi__type;
typedef map<ulint, lstring > id2lstring__type;
typedef map<srp<ge_pi>, ulint> ge2reg_map__type;
typedef list<srp<spillgen_group> > spillgen_group_list__type;
typedef set<srp<spillgen_group> > spillgen_group_set__type;
typedef set<srp<alloc_interval> > alloc_int_set__type;

declare_logger(slog);
initialize_logger( slog, "spillgen", backend_v2_logger );

declare_logger(deplog);
initialize_logger( deplog, "spillgen_deps", backend_v2_logger );


/*!
        \brief Performs spill-code generation on a function body.
*/
void spillgen::process() {
        slog << "process start\n" << eolog;

        move_gen = move_generator::create();
        
        //Set all available registers free.
        setup_registers();      
        
        //Get intervals for spillcode generation.
        waiting_intervals = alloc_int_vector__type::create(data_get()->alloc_ints_get());
        
        //Sort intervals by increasing start point
        ::std::sort(waiting_intervals->begin(),waiting_intervals->end(),alloc_int_cmp1);
        
        /*
                Go through function's body and generate spill code.
        */
        ptr<ge_pi_list__type> body = data_get()->ge_body_get();
        
        /*
                Code is to be inserted between current and next instruction. 
                Backup pointer to the next instruction in order to not process inserted code.
        */
        ge_pi_list__type::iterator it_next;
        
        for(ge_pi_list__type::iterator it = body->begin(); it!=body->end();) {
                ptr<ge_pi> ge = *it;
                
                it_next = it;
                ++it_next;
                
                //Remove overaged (interval->end < ge->schedule_pos) intervals from the active set.
                expire_old_intervals(ge->schedule_pos_get());
                
                //Activate waiting intervals (interval->start <= ge->schedule_pos)
                activate_waiting_intervals(ge->schedule_pos_get());
                
                //Recompute free register set according to used register set.
                find_free_registers();
                
                //Generate spill code for instruction.
                process_instruction(ge,body,it); 
                
                it = it_next;
        }

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

/*!
        \brief Generates spill-code for a pseudoinstruction.
        
        \param ge The pseudoinstruction.
        \param output An output list where any generated code is to be inserted.
        \param it An insert iterator.
*/
void spillgen::process_instruction(ptr<ge_pi> ge, ptr<ge_pi_list__type> output, ge_pi_list__type::iterator it) {
        slog << "process_instruction start\n" << eolog;
        
        //Find operand groups that shares single register.
        bool b_spilling_needed = identify_groups(ge);

        if ( !b_spilling_needed ) {
                /*No operand needs spilling. */
                
                //Update dependencies and last use of used registers and spill-spaces.
                for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                        ptr<spillgen_group> group = *it;
                        
                        if ( group->backup_space_get() ) {
                                ptr<pi_mem_factory> mf = group->backup_space_get()->factory_get();
                                
                                mf2ge_pi__type::iterator it_mf_last_use = spill_space_last_use->find(mf);
                                if ( it_mf_last_use!=spill_space_last_use->end() ) {
                                        deplog << "A. " << ge->uid_get() << " -> " <<  it_mf_last_use->second->uid_get() << "\n" << eolog;
                                        ge->dependencies_get()->insert(it_mf_last_use->second);
                                }
                                
                                (*spill_space_last_use)[mf] = ge;               
                        }       
                        
                        lassert(group->reg_get());
                        
                        ptr<ge_pi> last_use = find_last_use_of_register(group->reg_get()->id_get());
                        if ( last_use ) {
                                deplog << "B. " << ge->uid_get() << " -> " <<  last_use->uid_get() << "\n" << eolog;
                                ge->dependencies_get()->insert(last_use);
                        }
                        
                        set_last_use_of_register(group->reg_get()->id_get(),ge);
                }       
                slog << "process_instruction end 1\n" << eolog;
                return;
        }       
        
        //Temporaly allocate spill registers for groups that has no register regular allocated.
        allocate_regs_for_groups();
        
        //Generate spill code (load,store) for spilled operands.
        generate_spill_code(ge,output,it);
        
        free_group_resources();
        
        slog << "process_instruction end\n" << eolog;
}

/*!
        \brief Frees resources (registers,spill-places) used by spill-code generation for the currently processed instruction.
*/
void spillgen::free_group_resources() {
        slog << "free_group_resources start\n" << eolog;
        
        //Setup dependencies of the previously generated spill code.
        for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                ptr<spillgen_group> group = *it;

                if ( group->backup_space_get() ) {                      
                        ptr<pi_mem_factory> mf = group->backup_space_get()->factory_get();
        
                        //Free the spill place.
                        free_spill_spaces->insert(mf);  
                }
        }
        
        slog << "free_group_resources end\n" << eolog;
}

/*!
        \brief Generates code that backups register used by spill-code of a group.
        
        \param ge A currently processed pseudoinstruction.
        \param group The group.
        \param reg_orig_owners A list of intervals that uses the register.
        \return The generated code.
*/
ptr<ge_pi_vector__type> spillgen::generate_backup_code(ptr<ge_pi> ge,ptr<spillgen_group> group,ptr<alloc_int_set__type> reg_orig_owners) {
        ptr<ge_pi_vector__type> backup_code;
        
        ptr<tm_register> group_reg = group->reg_get();          
        
        lassert(group_reg);
        
        if ( reg_orig_owners->size()!=0 ) {
                //The register is currently owned by another operand. It must be backed-up.
                
                //Datatype of the value from the preserved register.
                ptr<tm_data_type_base> backup_type = tm_dt_simple::instance((dt_id_type)*group_reg->compatible_types_get()->begin());
                
                //Backup place.
                ptr<pi_mem_factory> mf = get_free_spill_space(backup_type);
                lassert(mf);
                ptr<ge_operand_mem> backup_space = mf->get_ge_mem(NULL);
                group->backup_space_set(backup_space);  
                
                //Faked operand for preserved register.
                ptr<ge_operand_reg> reg_to_backup = ge_operand_reg::create(backup_type,ge->bb_get()->fsp_get(),NULL);
                
                backup_code = move_gen->generate_store_to_memory(reg_to_backup,group_reg,backup_space); 
                
                /*
                        The backup_code must not overlap with any code that used the spill space before.
                        Add dependence of the code to the preceeding code.
                */
                mf2ge_pi__type::iterator it_mf = spill_space_last_use->find(mf);
                if ( it_mf!=spill_space_last_use->end() ) {
                        deplog << "C. " << backup_code->front()->uid_get() << " -> " <<  it_mf->second->uid_get() << "\n" << eolog;
                        backup_code->front()->dependencies_get()->insert(it_mf->second);
                }
                                        
                
        } else {
                //The register is not used. No backup required. Just create ge_sp to make setting-up dependecies easier (the backup code always exists).
                backup_code = ge_pi_vector__type::create();
                backup_code->push_back(ge_sp::create(NULL,NULL));
                
                
        }
                
        lassert(backup_code && backup_code->size()!=0);
        
        //Instruction that is previous user of the register
        ptr<ge_pi> reg_last_use = find_last_use_of_register(group_reg->id_get());
                
        /*
                The code must not overlap with any code that used the spill register before.
                Add dependence of the code to the preceeding code.
        */
        if ( reg_last_use && curr_generated_instructions->find(reg_last_use)==curr_generated_instructions->end() ) {
                deplog << "D. " << backup_code->front()->uid_get() << " -> " <<  reg_last_use->uid_get() << "\n" << eolog;
                backup_code->front()->dependencies_get()->insert(reg_last_use);
        }
        
        group->backup_instructions_set(backup_code);
        
        //The instruction ge must be places behind the backup code.
        deplog << "E. " << ge->uid_get() << " -> " <<  backup_code->back()->uid_get() << "\n" << eolog;
        ge->dependencies_get()->insert(backup_code->back());
        
        //Copy the code to basic block of the instruction ge.
        insert_code_to_bb(ge->bb_get(),backup_code,false);      
                
        return backup_code;
}


/*!
        \brief Generates code that restores register used by spill-code of a group of a pseudoinstructions.
        
        \param ge A currently processed pseudoinstruction.
        \param group The group.
        \param reg_orig_owners A list of intervals that uses the register.
        \return The generated code.
*/

ptr<ge_pi_vector__type> spillgen::generate_restore_code(ptr<ge_pi> ge,ptr<spillgen_group> group,ptr<alloc_int_set__type> reg_orig_owners) {
        ptr<ge_pi_vector__type> restore_code;
        
        ptr<tm_register> group_reg = group->reg_get();          
        
        lassert(group_reg);
        
        if ( reg_orig_owners->size()!=0 ) {
                //The register is currently owned by another operand. It must be backed-up.
                ptr<ge_operand_mem> backup_space = group->backup_space_get();
                
                ptr<pi_mem_factory> mf = backup_space->factory_get();
                lassert(mf);
                
                ptr<ge_operand_reg> reg_to_restore = ge_operand_reg::create(backup_space->type_get(),ge->bb_get()->fsp_get(),NULL);
                        
                restore_code = move_gen->generate_load_from_memory(backup_space,reg_to_restore,group_reg);
                
                //Set restore code as last user of the spill place.
                (*spill_space_last_use)[mf] = restore_code->back();             
        } else {
                //The register is not used. No backup required. Just create ge_sp to make setting-up dependecies easyer (the backup code always exists).
                restore_code = ge_pi_vector__type::create();
                restore_code->push_back(ge_sp::create(NULL,NULL));
        }       
                
        lassert(restore_code && restore_code->size());
        
        //Set restore code as last user of the register.
        set_last_use_of_register(group_reg->id_get(),restore_code->back());
        
        group->restore_instructions_set(restore_code);
        
        //Copy the code to basic block of the instruction ge.
        insert_code_to_bb(ge->bb_get(),restore_code,true);      
                        
        //The restore code must follows the instruction ge.
        deplog << "F. " << restore_code->front()->uid_get() << " -> " <<  ge->uid_get() << "\n" << eolog;
        restore_code->front()->dependencies_get()->insert(ge);  
                        
        return restore_code;
}

/*!
        \brief Generates code that loads value of a spilled operand from memory to a temporarly allocated register.
        
        \param ge A currently processed pseudoinstruction.
        \param group A group of the operand.
        \param interval An interval of the operand.
        \param operand The operand.
        \param reg The tmp register.
        \return The generated code.
*/
ptr<ge_pi_vector__type> spillgen::generate_load_code(ptr<ge_pi> ge,ptr<spillgen_group> group,ptr<alloc_interval> interval,ptr<ge_operand_reg> operand, ptr<tm_register> reg) {
        lassert(reg);
        
        ptr<ge_pi_vector__type> load_code;      
        
        if ( interval->allocated_reg_get() ) {
                /*
                        The operand's interval has register assigned. But it differs from the group's register. 
                        Generate copy code that copies value between these registers to get it into the right one.
                */
                ptr<ge_operand_reg> source_operand = ge_operand_reg::create(operand->type_get(),ge->bb_get()->fsp_get(),NULL);
                load_code = move_gen->generate_copy_to_register(source_operand,interval->allocated_reg_get(),operand,reg);
                
                //Load code of any thief group must follows the copy code.
                ptr<spillgen_group_set__type> thief_groups = find_groups_by_reg(interval->allocated_reg_get());
                lassert(thief_groups->size()!=0);
                
                for(spillgen_group_set__type::iterator it = thief_groups->begin(); it!=thief_groups->end(); ++it) {
                        ptr<spillgen_group> thief = *it;
                        deplog << "G. " << thief->backup_instructions_get()->front()->uid_get() << " -> " <<  load_code->back()->uid_get() << "\n" << eolog;
                        thief->backup_instructions_get()->front()->dependencies_get()->insert(load_code->back());
                }
        } else {
                //Load value from spill-space to the register.          
                ptr<pi_mem_factory> mf = interval->allocated_spill_place_get();
                
                if ( !mf ) {
                        //Spill space has not been yet assigned to the operand's interval. Do it now.
                        mf = get_free_spill_space(operand->type_get());
                        interval->allocated_spill_place_set(mf);        
                }
                //Load value from spill-space to the register.          
                ptr<ge_operand_mem> spill_place = mf->get_ge_mem(ge->bb_get()->fsp_get());
                
                load_code = move_gen->generate_load_from_memory(spill_place,operand,reg);
        
                //Setup dependencies in order to not allow the store code and previous user of the spill place overlap.
                mf2ge_pi__type::iterator mf_it = spill_space_last_use->find(mf);
                if ( mf_it!=spill_space_last_use->end() ) {
                        deplog << "H. " << load_code->front()->uid_get() << " -> " <<  mf_it->second->uid_get() << "\n" << eolog;
                        load_code->front()->dependencies_get()->insert(mf_it->second);
                }
                
                //Set last user of the spill place.
                (*spill_space_last_use)[mf] = load_code->back();
        }       
        
        lassert(load_code && load_code->size());
        
        //Set last user of the register.
        //set_last_use_of_register(reg->id_get(),ge);
        
        group->load_instructions_get()->insert(load_code->begin(),load_code->end());
        
        //Copy the code to basic block of the operands instruction.
        insert_code_to_bb(ge->bb_get(),load_code,false);        
        
        //The load code must follows the backup code. 
        deplog << "I. " << load_code->front()->uid_get() << " -> " <<  group->backup_instructions_get()->back()->uid_get() << "\n" << eolog;
        load_code->front()->dependencies_get()->insert(group->backup_instructions_get()->back());
                
        //Previous instruction in the operand's interval.
        ptr<ge_pi> interval_prev_instr = interval_find_previous_instruction(interval,ge->schedule_pos_get());
                
        if ( interval_prev_instr ) {
                //Load code must follows the interval's previous instruction.
                deplog << "J. " << load_code->front()->uid_get() << " -> " <<  interval_prev_instr->uid_get() << "\n" << eolog;
                load_code->front()->dependencies_get()->insert(interval_prev_instr);
        }
                
        //Instruction must follows load code.
        deplog << "K. " << ge->uid_get() << " -> " <<  load_code->back()->uid_get() << "\n" << eolog;
        ge->dependencies_get()->insert(load_code->back());
        
        //Finally, set register to operand within instruction.
        (*operand->assigned_registers_get())[ge] = reg->id_get();
        
        return load_code;
}

/*!
        \brief Generates code that store value of a spilled operand from a temporarly allocated register to a spill-place.
        
        \param ge A currently processed pseudoinstruction.
        \param group A group of the operand.
        \param interval An interval of the operand.
        \param operand The operand.
        \param reg The tmp register.
        \return The generated code.
*/
ptr<ge_pi_vector__type> spillgen::generate_store_code(ptr<ge_pi> ge,ptr<spillgen_group> group,ptr<alloc_interval> interval,ptr<ge_operand_reg> operand, ptr<tm_register> reg) {
        lassert(reg);
        
        ptr<ge_pi_vector__type> store_code;     

        if ( interval->allocated_reg_get() ) {
                /*
                        The operand's interval has register assigned. But it differs from the group's register. 
                        Generate copy code that copies value between these registers to get it into the right one.
                */
                ptr<ge_operand_reg> destination_operand = ge_operand_reg::create(operand->type_get(),NULL,NULL);

                store_code = move_gen->generate_copy_to_register(operand,reg,destination_operand,interval->allocated_reg_get());
                
                ge->bb_get()->lsp_get()->operands_input_get()->push_back(destination_operand);
                
                //The copy code must follows restore of any thief group.
                ptr<spillgen_group_set__type> thief_groups = find_groups_by_reg(interval->allocated_reg_get());
                
                for(spillgen_group_set__type::iterator it = thief_groups->begin(); it!=thief_groups->end(); ++it) {
                        ptr<spillgen_group> thief = *it;
                        deplog << "L. " << store_code->front()->uid_get() << " -> " <<  thief->restore_instructions_get()->back()->uid_get() << "\n" << eolog;
                        store_code->front()->dependencies_get()->insert(thief->restore_instructions_get()->back());
                }
        } else {
                ptr<pi_mem_factory> mf = interval->allocated_spill_place_get();
                
                if ( !mf ) {
                        //Spill space has not been yet assigned to the operand's interval. Do it now.
                        mf = get_free_spill_space(operand->type_get());
                        interval->allocated_spill_place_set(mf);        
                }
                
                //Store value from spill-space to the register.         
                ptr<ge_operand_mem> spill_place = mf->get_ge_mem(NULL);
                store_code = move_gen->generate_store_to_memory(operand,reg,spill_place);
                spill_place->origin_set(store_code->back());
        
                //Setup dependencies in order to not allow the store code and previous user of the spill place overlap.
                mf2ge_pi__type::iterator mf_it = spill_space_last_use->find(mf);
                if ( mf_it!=spill_space_last_use->end() ) {
                        deplog << "M. " << store_code->front()->uid_get() << " -> " <<  mf_it->second->uid_get() << "\n" << eolog;
                        store_code->front()->dependencies_get()->insert(mf_it->second);
                }
                
                //Set last user of the spill place.
                (*spill_space_last_use)[mf] = store_code->back();
        }       
        
        lassert(store_code && store_code->size());
        
        //Set last user of the register.
        //set_last_use_of_register(reg->id_get(),store_code->back());
        
        group->store_instructions_get()->insert(store_code->begin(),store_code->end());
        
        //Copy the code to basic block of the instruction ge.
        insert_code_to_bb(ge->bb_get(),store_code,true);        
        
        //The store code must follows ge.
        deplog << "N. " << store_code->front()->uid_get() << " -> " <<  ge->uid_get() << "\n" << eolog;
        store_code->front()->dependencies_get()->insert(ge);
                
        //The restore code must follows the store code.
        deplog << "O. " << group->restore_instructions_get()->front()->uid_get() << " -> " <<  store_code->back()->uid_get() << "\n" << eolog;
        group->restore_instructions_get()->front()->dependencies_get()->insert(store_code->back());
                
        //The following instruction of the interval must follows the store code.
        ptr<ge_pi> interval_next_instr = interval_find_next_instruction(interval,ge->schedule_pos_get());
        if ( interval_next_instr ) {
                deplog << "P. " << interval_next_instr->uid_get() << " -> " <<  store_code->back()->uid_get() << "\n" << eolog;
                interval_next_instr->dependencies_get()->insert(store_code->back());
        }
        
        //Finally, set register to operand within instruction.
        (*operand->assigned_registers_get())[ge] = reg->id_get();
        
        return store_code;
}

/*!
        \brief Returns spillgen_groups that corresponds to a register within a currently processed instruction.
        
        \param reg The register.
        \return The set of groups.
*/
ptr<spillgen_group_set__type> spillgen::find_groups_by_reg(ptr<tm_register> reg) {
        slog << "find_groups_by_reg start\n" << eolog;
        
        ptr<spillgen_group_set__type> found_groups = spillgen_group_set__type::create();
        
        ptr<id_set__type> aliases = reg->aliases_get();
        
        for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                ptr<spillgen_group> group = *it;
                        
                //Register used by the group.
                ptr<tm_register> group_reg = group->reg_get();          
                
                if ( aliases->find(group_reg->id_get())!=aliases->end() ) {
                        found_groups->insert(group);
                }
        }
        
        slog << "find_groups_by_reg end\n" << eolog;
        
        return found_groups;
}

/*!
        \brief Generates code for a pseudoinstruction.
        
        \param ge The pseudoinstruction.
        \param output An output list where any generated code is to be inserted.
        \param it An insert iterator.
*/
void spillgen::generate_spill_code(ptr<ge_pi> ge,ptr<ge_pi_list__type>, ge_pi_list__type::iterator) {
        slog << "generate_spill_code start\n" << eolog;
        
        slog << "generate_spill_code for ge_pi=" << ge->uid_get() << "\n" << eolog;
        
        curr_generated_instructions->clear();
        
        //Generate backup and restore code.
        for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                ptr<spillgen_group> group = *it;
                        
                //Register used by the group.
                ptr<tm_register> group_reg = group->reg_get();          
                lassert(group_reg);
                
                if ( group_reg->is_unspillable() ) {
                        ptr<ge_op_reg_set__type> operands = group->operands_get();
                        for(ge_op_reg_set__type::iterator it2 = operands->begin(); it2!=operands->end(); ++it2) {
                                (*(*it2)->assigned_registers_get())[ge] = group_reg->id_get();
                        }
                        continue;
                }
                
                //Registers that will be divided among group's operands.
                group->avail_regs_for_input_ops_set(id_set__type::create(group_reg->aliases_get()));
                group->avail_regs_for_output_ops_set(id_set__type::create(group_reg->aliases_get()));
                
                //Owners (intervals that have the register (or its parts) allocated.            
                ptr<alloc_int_set__type> orig_owners = find_register_owners(group_reg);
                
                //Remove intervals of the group's operands from orig_owners set.
                for(spillgen_group_list__type::iterator it1 = groups->begin(); it1!=groups->end(); ++it1) {
                        
                        ptr<ge_op_reg_set__type> operands = (*it1)->operands_get();
                        
                        for(ge_op_reg_set__type::iterator it2 = operands->begin(); it2!=operands->end(); ++it2) {
                                ptr<alloc_interval> interval = (*op2interval)[*it2];
                                orig_owners->erase(interval);
                        }
                }       
                
                //The register contains active data that has to be preserved. Backup it.
                ptr<ge_pi_vector__type> backup_code = generate_backup_code(ge, group, orig_owners);
                
                curr_generated_instructions->insert(backup_code->begin(),backup_code->end());
                
#ifdef BACKEND_V2_DEBUG         
                ::std::ostringstream oss1;
                oss1 << "backup code (ge_pi=" << ge->uid_get() << ", group=" << group->uid_get() << ")";
                set_instruction_property(backup_code,ge_pi::PROPERTY_SPILLGEN_INFO,oss1.str());
#endif
                
                //Restore original value.
                ptr<ge_pi_vector__type> restore_code = generate_restore_code(ge, group, orig_owners);

                curr_generated_instructions->insert(restore_code->begin(),restore_code->end());
                
#ifdef BACKEND_V2_DEBUG         
                ::std::ostringstream oss2;
                oss2 << "restore code (ge_pi=" << ge->uid_get() << ", group=" << group->uid_get() << ")";
                set_instruction_property(restore_code,ge_pi::PROPERTY_SPILLGEN_INFO,oss2.str());
#endif
                
        }
        
        /* Generate load and store code. */
        ulint op_pos = 0;
        ptr<ge_operand_vector__type> ops = ge->operands_input_get();
        for(ge_operand_vector__type::iterator it = ops->begin(); it!=ops->end(); ++it, ++op_pos) {
        
                if ( (*it)->kind_get()!=ge_operand::REGISTER ) {
                        continue;
                }
                
                ptr<ge_operand_reg> op = (*it).dncast<ge_operand_reg>();
                ptr<tm_instr_op_reg> tmop = (*ge->instruction_get()->operands_input_get())[op_pos].dncast<tm_instr_op_reg>();
                
                ptr<spillgen_group> group = (*op2group)[op];
                lassert(group);
                
                ptr<alloc_interval> interval = (*op2interval)[op];
                lassert(interval);
                
                //Register used by the group.
                ptr<tm_register> group_reg = group->reg_get();          
                lassert(group_reg);
                
                if ( group_reg->is_unspillable() ) {
                        continue;
                }
                
                ptr<id_set__type> tmp_set = id_set__type::create();
                
                ::std::set_intersection(
                        group->avail_regs_for_input_ops_get()->begin(),
                        group->avail_regs_for_input_ops_get()->end(),
                        tmop->allowed_registers_get()->begin(),
                        tmop->allowed_registers_get()->end(),
                        ::std::inserter(*tmp_set,tmp_set->begin()));
                        
                lassert(tmp_set->size()!=0);
                
                tmp_set = filter_regs_by_data_type(tmp_set,op->type_get()->id_get());
                
                //Register used by the operand.
                ptr<tm_register> interval_reg = tm_register::instance(*tmp_set->begin());
                
                //Update set of available registers.
                tmp_set = id_set__type::create();
                ::std::set_difference(
                        group->avail_regs_for_input_ops_get()->begin(),
                        group->avail_regs_for_input_ops_get()->end(),
                        interval_reg->aliases_get()->begin(),
                        interval_reg->aliases_get()->end(),
                        ::std::inserter(*tmp_set,tmp_set->begin()));
                        
                group->avail_regs_for_input_ops_set(tmp_set);
                
                if ( interval->allocated_reg_get()==interval_reg ) {
                        //Owner of the register is operand's interval itsef.
                        continue;
                }

                //Generate load of the spilled operand's value.
                ptr<ge_pi_vector__type> load_code = generate_load_code(ge,group,interval,op,interval_reg);
                
                curr_generated_instructions->insert(load_code->begin(),load_code->end());
                
#ifdef BACKEND_V2_DEBUG         
                ::std::ostringstream oss1;
                oss1 << "load code (ge_pi=" << ge->uid_get() << ", group=" << group->uid_get() << ", interval=" << interval->uid_get() << ")";
                set_instruction_property(load_code,ge_pi::PROPERTY_SPILLGEN_INFO,oss1.str());
#endif

        }
        
        op_pos = 0;
        ops = ge->operands_output_get();
        for(ge_operand_vector__type::iterator it = ops->begin(); it!=ops->end(); ++it, ++op_pos) {
        
                if ( (*it)->kind_get()!=ge_operand::REGISTER ) {
                        continue;
                }
                
                ptr<ge_operand_reg> op = (*it).dncast<ge_operand_reg>();
                ptr<tm_instr_op_reg> tmop = (*ge->instruction_get()->operands_output_get())[op_pos].dncast<tm_instr_op_reg>();
                
                ptr<spillgen_group> group = (*op2group)[op];
                lassert(group);
                
                ptr<alloc_interval> interval = (*op2interval)[op];
                lassert(interval);
                
                //Register used by the group.
                ptr<tm_register> group_reg = group->reg_get();          
                lassert(group_reg);
                
                if ( group_reg->is_unspillable() ) {
                        continue;
                }
                
                ptr<id_set__type> tmp_set = id_set__type::create();
                
                ::std::set_intersection(
                        group->avail_regs_for_output_ops_get()->begin(),
                        group->avail_regs_for_output_ops_get()->end(),
                        tmop->allowed_registers_get()->begin(),
                        tmop->allowed_registers_get()->end(),
                        ::std::inserter(*tmp_set,tmp_set->begin()));
        
                tmp_set = filter_regs_by_data_type(tmp_set,op->type_get()->id_get());
        
                lassert(tmp_set->size()!=0);
                
                //Register used by the operand.
                ptr<tm_register> interval_reg = tm_register::instance(*tmp_set->begin());
                
                //Update set of available registers.
                tmp_set = id_set__type::create();
                ::std::set_difference(
                        group->avail_regs_for_output_ops_get()->begin(),
                        group->avail_regs_for_output_ops_get()->end(),
                        interval_reg->aliases_get()->begin(),
                        interval_reg->aliases_get()->end(),
                        ::std::inserter(*tmp_set,tmp_set->begin()));
                        
                group->avail_regs_for_output_ops_set(tmp_set);
                
                if ( interval->allocated_reg_get()==interval_reg ) {
                        //Owner of the register is operand's interval itsef.
                        continue;
                }

                //Generate store of the spilled operand's value.
                ptr<ge_pi_vector__type> store_code = generate_store_code(ge,group,interval,op,interval_reg);

                curr_generated_instructions->insert(store_code->begin(),store_code->end());
                
#ifdef BACKEND_V2_DEBUG         
                ::std::ostringstream oss1;
                oss1 << "store code (ge_pi=" << ge->uid_get() << ", group=" << group->uid_get() << ", interval=" << interval->uid_get() << ")";
                set_instruction_property(store_code,ge_pi::PROPERTY_SPILLGEN_INFO,oss1.str());
#endif
                
        }
        
        slog << "generate_spill_code end\n" << eolog;
}

/*!
        \brief Finds an instruction that precedes given position within an interval.
        
        \param interval The interval.
        \param curr_pos The position.
        \return The previous instruction.
*/
ptr<ge_pi> spillgen::interval_find_previous_instruction(ptr<alloc_interval> interval, ulint curr_pos) {
        slog << "interval_find_previous_instruction start\n" << eolog;
        
        ptr<ge_pi_vector__type> instructions = interval->instructions_get();
        
        for(ge_pi_vector__type::reverse_iterator it = instructions->rbegin(); it!=instructions->rend(); ++it) {
                if ( (*it)->schedule_pos_get() < curr_pos ) {
                        slog << "interval_find_revious_instruction end 1\n" << eolog;
                        return *it;
                }
        }       
        
        slog << "interval_find_previous_instruction end\n" << eolog;
        
        return NULL;
}

/*!
        \brief Finds an instruction that follows given position within an interval.
        
        \param interval The interval.
        \param curr_pos The position.
        \return The following instruction.
*/
ptr<ge_pi> spillgen::interval_find_next_instruction(ptr<alloc_interval> interval, ulint curr_pos) {
        slog << "interval_find_next_instruction start\n" << eolog;
        
        ptr<ge_pi_vector__type> instructions = interval->instructions_get();
        
        for(ge_pi_vector__type::iterator it = instructions->begin(); it!=instructions->end(); ++it) {
                if ( (*it)->schedule_pos_get() > curr_pos ) {
                        slog << "interval_find_next_instruction end 1\n" << eolog;
                        return *it;
                }
        }       
        
        slog << "interval_find_next_instruction end\n" << eolog;
        
        return NULL;
}

/*!
        \brief Searches for intervals that currently use a register ( or its aliases ).
        
        \param reg The register.
        \return A set of intervals.
*/
ptr<alloc_int_set__type> spillgen::find_register_owners(ptr<tm_register> reg) {
        slog << "find_register_owners start\n" << eolog;
        
        ptr<alloc_int_set__type> res = alloc_int_set__type::create();
        
        ptr<id_set__type> aliases = reg->aliases_get();
        
        for(id_set__type::iterator it = aliases->begin(); it!=aliases->end(); ++it) {
                reg2alloc_int__type::iterator it_int = register_owners->find(*it);
                
                if ( it_int!=register_owners->end() ) {
                        res->insert(it_int->second);
                }
        }
        
        slog << "find_register_owners end\n" << eolog;
        return res;
}

/*!
        \brief Allocates registers to operand groups of a currently processed instruction.
*/
void spillgen::allocate_regs_for_groups() {
        slog << "allocate_regs_for_groups start\n" << eolog;    
        
        spillgen_group_list__type::iterator it_stop = groups->end();
        spillgen_group_list__type::iterator it = groups->begin();
        
        while (true) {
                if ( it_stop==it ) {
                        break;
                }
                
                if ( it == groups->end() ) {
                        it = groups->begin();
                        continue;
                }
                
                ptr<spillgen_group> group = *it;
                
                if ( !group->reg_get() ) {
                        allocate_reg_for_group(group);
                        it_stop = it;
                }
                
                ++it;
        }
        
        slog << "allocate_regs_for_groups end\n" << eolog;      
}

/*!
        \brief Allocates register to a operand group of a currently processed instruction.
        
        \param group The group.
*/
void spillgen::allocate_reg_for_group(ptr<spillgen_group> group) {
        slog << "allocate_reg_for_group start\n" << eolog;      
        
        ptr<id_set__type> allowed_regs =  group->allowed_registers_get();
        ptr<id_set__type> avail_regs = id_set__type::create();
        
        ptr<tm_register> reg;
        
        while (true) {
                ptr<id_set__type> avail_regs = id_set__type::create();
                
                //Try find available allowed registers first.
                ::std::set_intersection(
                        free_registers->begin(),
                        free_registers->end(),
                        allowed_regs->begin(),
                        allowed_regs->end(),
                        ::std::inserter(*avail_regs, avail_regs->begin()));
                        

                if ( avail_regs->size()==0 ) {
                        /*
                                No free allowed register found.
                                Try steal a register from operand not used within this ge_pi.
                        */
                        ptr<id_set__type> tmp = id_set__type::create();
                
                        ::std::set_difference(
                                all_registers->begin(),
                                all_registers->end(),
                                regs_used_by_groups->begin(),
                                regs_used_by_groups->end(),
                                ::std::inserter(*tmp, tmp->begin()));
                        
                        ::std::set_intersection(
                                tmp->begin(),
                                tmp->end(),
                                allowed_regs->begin(),
                                allowed_regs->end(),
                                ::std::inserter(*avail_regs, avail_regs->begin()));
                        
                }
                        
                if ( avail_regs->size()!=0 ) {
                        reg = tm_register::instance(*avail_regs->begin());      
                        break;
                }        
        
                //No free or stolen one available. Steal one from an operand within the same ge_pi.
                steal_register_from_siblings(group, allowed_regs);
        }
                
        lassert(reg);
        lassert(allowed_regs->find(reg->id_get())!=allowed_regs->end());
        
        group->reg_set(reg);
        
        regs_used_by_groups->insert(reg->aliases_get()->begin(),reg->aliases_get()->end());
        
        ptr<id_set__type> updated_free_registers = id_set__type::create();
        
        ::std::set_difference(
                        all_registers->begin(),
                        all_registers->end(),
                        reg->aliases_get()->begin(),
                        reg->aliases_get()->end(),
                        ::std::inserter(*updated_free_registers,updated_free_registers->begin()));
                        
        free_registers = updated_free_registers;
        
        slog << "allocate_reg_for_group end\n" << eolog;        
}

/*!
        \brief Finds a group of groups of a currently processed instruction that uses one of allowed registers and steals its register.
        \param A group that needs a register.
        \param allowed_regs The set of allowed registers.
*/
void spillgen::steal_register_from_siblings(ptr<spillgen_group> thief, ptr<id_set__type> allowed_regs) {
        slog << "steal_register_from_siblings start\n" << eolog;        
        
        ptr<spillgen_group> guarded_grp = thief->guarded_group_get();
        
        for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                ptr<spillgen_group> group = *it;
                
                if ( group!=thief && group!=guarded_grp && group->reg_get() && group->allowed_registers_get()->size()>1 ) {
                        ptr<tm_register> grp_reg = group->reg_get();    
                        ptr<id_set__type> aliases = grp_reg->aliases_get();
                        
                        ptr<id_set__type> tmp = id_set__type::create();
                        
                        ::std::set_intersection(
                                allowed_regs->begin(),
                                allowed_regs->end(),
                                aliases->begin(),
                                aliases->end(),
                                ::std::inserter(*tmp, tmp->begin()));           
                                
                        if ( tmp->size()>0 ) {
                                group->guarded_group_set(thief);
                                
                                free_registers->insert(aliases->begin(),aliases->end());
                                
                                ptr<id_set__type> tmp_set = id_set__type::create();
                                ::std::set_difference(
                                        regs_used_by_groups->begin(),
                                        regs_used_by_groups->end(),
                                        aliases->begin(),
                                        aliases->end(),
                                        ::std::inserter(*tmp_set, tmp_set->begin()));           
                                        
                                regs_used_by_groups = tmp_set;
                        }       
                }
        }
        
        slog << "steal_register_from_siblings end\n" << eolog;  
}


/*!
        \brief Groups operands of a pseudoinstruction into groups that use the same register.
        
        \param ge The pseudoinstruction.
        \return If a group without an allocated register has been found, it returns true. False otherwise.
*/
bool spillgen::identify_groups(ptr<ge_pi> ge) {
        slog << "identify_groups start\n" << eolog;     
        
        ptr<tm_instr_base> tm = ge->instruction_get();

        regs_used_by_groups->clear();
        groups->clear();
        op2group->clear();
        
        if ( !tm ) {
                slog << "identify_groups end 1\n" << eolog;     
                return false;
        }       
        
        /*
                Spillgen_group represents group of register operands of a single ge_pi that share a register.
        */
        bool b_nothing_to_do = true;
        
        ptr<ge_operand_vector__type> ops = ge->operands_input_get();
        
        ulint op_pos = 0;
        for(ge_operand_vector__type::iterator it = ops->begin(); it!=ops->end(); ++it, ++op_pos) {
        
                if ( (*it)->kind_get()!=ge_operand::REGISTER ) {
                        continue;
                }
                
                ptr<ge_operand_reg>  op = (*it).dncast<ge_operand_reg>();
                ptr<tm_instr_op_reg_base> tmop = (*tm->operands_input_get())[op_pos].dncast<tm_instr_op_reg_base>();
                ptr<tm_register> reg = NULL;
                
                ge2reg_map__type::iterator it1 = op->assigned_registers_get()->find(ge);                        
                if ( it1!=op->assigned_registers_get()->end() ) {
                        reg = tm_register::instance(it1->second);       
                } else {
                        b_nothing_to_do = false;
                }
                
                ptr<spillgen_group> group = spillgen_group::create();
                group->reg_set(reg);
                group->operands_get()->insert(op);
                group->allowed_registers_set(filter_regs_by_data_type(id_set__type::create(tmop->allowed_registers_get()), op->type_get()->id_get()));
                group->is_input_set(true);
                
                if (reg && group->allowed_registers_get()->find(reg->id_get())==group->allowed_registers_get()->end()) {
                        lassert(!reg || group->allowed_registers_get()->find(reg->id_get())!=group->allowed_registers_get()->end());
                }
                
                groups->push_back(group);
                (*op2group)[op] = group;                        
        }
        
        ops = ge->operands_output_get();
        
        op_pos = 0;
        for(ge_operand_vector__type::iterator it = ops->begin(); it!=ops->end(); ++it, ++op_pos) {
        
                if ( (*it)->kind_get()!=ge_operand::REGISTER ) {
                        continue;
                }
                
                ptr<ge_operand_reg>  op = (*it).dncast<ge_operand_reg>();
                ptr<tm_instr_op_reg_base> tmop = (*tm->operands_output_get())[op_pos].dncast<tm_instr_op_reg_base>();
                ptr<tm_register> reg = NULL;
                
                ge2reg_map__type::iterator it1 = op->assigned_registers_get()->find(ge);                        
                if ( it1!=op->assigned_registers_get()->end() ) {
                        reg = tm_register::instance(it1->second);       
                } else {
                        b_nothing_to_do = false;
                }
                
                ptr<spillgen_group> group;
                
                if ( tmop->destroys_get()==NO_OPERAND_ID ) {
                        //Operand doesn't destroy any input operand.
                        group = spillgen_group::create();
                        group->reg_set(reg);
                        group->allowed_registers_set(filter_regs_by_data_type(id_set__type::create(tmop->allowed_registers_get()), op->type_get()->id_get()));
                        groups->push_back(group);
                        
                        lassert(!reg || group->allowed_registers_get()->find(reg->id_get())!=group->allowed_registers_get()->end());
                } else {
                        //Operand destroys an input operand. Insert it to the destroyed register's group.
                        ptr<ge_operand_reg> destroyed_op = (*ge->operands_input_get())[tmop->destroys_get() - I_1].dncast<ge_operand_reg>();
                        group = (*op2group)[destroyed_op];
                        ptr<tm_register> destroyed_reg = group->reg_get();
                        
                        if ( op->type_get()->bitwidth_get() > destroyed_op->type_get()->bitwidth_get() ) {
                                group->reg_set(reg);
                                
                                //Free registers used by destroyed_reg within ge_pi
                                if ( destroyed_reg ) {
                                        ptr<id_set__type> regs_to_free;
                                
                                        if ( !reg ) {
                                                //Set register used by destroyed operand free.  
                                                regs_to_free =  destroyed_reg->aliases_get();
                                        } else {
                                                //Set register used by destroyed and not used by destroyer operand free.        
                                                regs_to_free = id_set__type::create();
                                                        
                                                ::std::set_difference(
                                                        reg->aliases_get()->begin(),
                                                        reg->aliases_get()->end(),
                                                        destroyed_reg->aliases_get()->begin(),
                                                        destroyed_reg->aliases_get()->end(),
                                                        ::std::inserter(*regs_to_free,regs_to_free->begin()));
                                                
                                        }
                        
                                        if ( regs_to_free ) {
                                                //Update free registers.
                                                free_registers->insert(regs_to_free->begin(),regs_to_free->end());
                                        }
                                }
                                
                                //Update allowed register set for the group.
                                group->allowed_registers_set(filter_regs_by_data_type(id_set__type::create(tmop->allowed_registers_get()),op->type_get()->id_get()));
                                
                                lassert(!reg || group->allowed_registers_get()->find(reg->id_get())!=group->allowed_registers_get()->end());
                        }
                }
                
                group->is_output_set(true);
                group->operands_get()->insert(op);
                (*op2group)[op] = group;                        
        }
        
        //Sweep registers used by active groups.
        for(spillgen_group_list__type::iterator it = groups->begin(); it!=groups->end(); ++it) {
                ptr<spillgen_group> group = *it;
                
                if ( group->reg_get() ) {
                        ptr<id_set__type> aliases = group->reg_get()->aliases_get();
                        regs_used_by_groups->insert(aliases->begin(),aliases->end());
                }
        }
        
        slog << "find_spillgen_groups end\n" << eolog;  

        return !b_nothing_to_do;
}

/*!
        \brief Filters a set of registers and returns subset that can hold value of a given type.
        \param reg_set The source set.
        \param type_id The type.
        \return The filtered set.
*/
ptr<id_set__type> spillgen::filter_regs_by_data_type(ptr<id_set__type> reg_set, ulint type_id) {
        slog << "filter_regs_by_data_type start\n" << eolog;    
        
        for(id_set__type::iterator it = reg_set->begin(); it!=reg_set->end();) {
                ptr<tm_register> 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++;
                        reg_set->erase(del_it);
                } else {
                        ++it;
                }
        }
        
        slog << "filter_regs_by_data_type end\n" << eolog;      
        
        return reg_set;
}


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

/*!
        \brief Recomputes the free_registers set.
        
        free_registers <- all_registers - used_registers
*/
void spillgen::find_free_registers() {
        slog << "find_free_registers start\n" << eolog;
        
        registers_freed = false;
        
        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;
        
        slog << "find_free_registers end\n" << eolog;
}


/*!
        \brief Picks a spill-place from a list of free spill-places that is compatible with a data type.
        
        If no free spill-pace is available then it allocates a new one.
        
        \param mfs The list of free spill-places.
        \param type The data type.
        \return The spill-place.
*/
ptr<pi_mem_factory> spillgen::get_free_spill_space(ptr<tm_data_type_base> type) {
        slog << "get_free_spill_space start\n" << eolog;
        
        ulint bitwidth = type->bitwidth_get();
        
        /*
                Find a free allocated spill space with the right bitwidth.
        */
        for(mf_set__type::iterator it = free_spill_spaces->begin(); it!=free_spill_spaces->end(); ++it) {
                ptr<pi_mem_factory> mf = *it;
                lassert(mf);
                
                if ( mf->type_get()->bitwidth_get()==bitwidth ) {
                        free_spill_spaces->erase(mf);
                        slog << "get_free_spill_space end 1\n" << eolog;
                        mf->type_set(type);
                        return mf;
                }
        }
        
        // Free spill space has not been found. Allocate new one.
        ptr<pi_mem_factory> spill_space = mem_alloc_manager::instance()->allocate_local_tmp(data_get()->function_decl_get(),type);
        
        lassert(spill_space);
        
        slog << "get_free_spill_space end\n" << eolog;
        return spill_space;
}

/*!
        \brief Adds intervals whoose startpoints follows a currently processed point to the active_intervals set.
        
        \param curr_point The current point.
        \return True if an interval has been added. False otherwise.
*/
bool spillgen::activate_waiting_intervals(ulint curr_point) {
        slog << "activate_waiting_intervals start\n" << eolog;
        
        bool b_free_regs_need_recalculate = false;
        
        for(alloc_int_vector__type::iterator it = waiting_intervals->begin(); it!=waiting_intervals->end();) {
                ptr<alloc_interval> interval = *it;
                
                if ( interval->start_get() <= curr_point ) {
                        slog << "interval(id:" << interval->uid_get() << ") activated\n" << eolog;
                        
                        active_intervals->push_back(interval);
                        it = waiting_intervals->erase(it);
                        
                        ptr<tm_register> allocated_reg = interval->allocated_reg_get();
                        
                        if ( allocated_reg ) {
                                (*register_owners)[allocated_reg->id_get()] = interval;
                                used_registers->insert(allocated_reg->id_get());
                                b_free_regs_need_recalculate = true;
                        }
                        
                        (*op2interval)[interval->operand_get()] = interval;
                } else {
                        break;
                }
        }
        
        slog << "activate_waiting_intervals end\n" << eolog;
        
        return b_free_regs_need_recalculate;
        
}

/*!
        \brief Removes intervals whoose endpoints precede a currently processed point from the active_intervals set.
        
        \param curr_point The current point.
        \return True if an interval has expired. False otherwise.
*/
bool spillgen::expire_old_intervals(ulint curr_point) {
        slog << "expire_old_intervals start\n" << eolog;
        
        bool b_free_regs_need_recalculate = false;
        
        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 ) {
                        slog << "interval(id:" << interval->uid_get() << ") expired\n" << eolog;
                        
                        it = active_intervals->erase(it);                       
                        expired_intervals->push_back(interval);
                        
                        if ( interval->next_get() ) {
                                //Copy operand's value between intervals.
                                ptr<alloc_interval> next = interval->next_get();
                                
                                ptr<tm_register> source_reg = interval->allocated_reg_get();
                                ptr<tm_register> target_reg = next->allocated_reg_get();
                                
                                if ( interval->allocated_spill_place_get() && !target_reg ) {
                                        //Reuse spill space in next interval. No copy needed.
                                        next->allocated_spill_place_set(interval->allocated_spill_place_get());
                                } else {
                                        //Free spill space.
                                        free_spill_spaces->insert(interval->allocated_spill_place_get());
                                }
                                
                                ptr<ge_pi_vector__type> copy_code;
                                
                                if ( source_reg && target_reg ) {
                                        //Copy value reg -> reg.
                                        ptr<ge_operand_reg> target_operand = ge_operand_reg::create(next->operand_get()->type_get(),NULL,NULL);
                                        copy_code = move_gen->generate_copy_to_register(interval->operand_get(),source_reg,target_operand,target_reg);
                                        target_operand->origin_set(copy_code->back());
                                        
                                        ptr<ge_pi> prev_use = find_last_use_of_register(source_reg->id_get());
                                        if ( prev_use ) {
                                                deplog << "Q. " << copy_code->front()->uid_get() << " -> " <<  prev_use->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(prev_use);
                                        }
                                        
                                        prev_use = find_last_use_of_register(target_reg->id_get());
                                        if ( prev_use ) {
                                                deplog << "R. " << copy_code->front()->uid_get() << " -> " <<  prev_use->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(prev_use);
                                        }
                                        
                                        set_last_use_of_register(source_reg->id_get(),copy_code->back());
                                        set_last_use_of_register(target_reg->id_get(),copy_code->back());
                                        
                                } else if ( !source_reg && target_reg ) {
                                        //Copy value mem -> reg.
                                        ptr<pi_mem_factory> mf = interval->allocated_spill_place_get();
                                        ptr<ge_operand_reg> target_operand = ge_operand_reg::create(next->operand_get()->type_get(),NULL,NULL);
                                        ptr<ge_operand_mem> spill_place = mf->get_ge_mem(interval->instructions_get()->front());
                                        copy_code = move_gen->generate_load_from_memory(spill_place,target_operand,target_reg);
                                        target_operand->origin_set(copy_code->back());
                                        
                                        mf2ge_pi__type::iterator mf_it = spill_space_last_use->find(mf);
                                        if ( mf_it!=spill_space_last_use->end() ) {
                                                deplog << "S. " << copy_code->front()->uid_get() << " -> " <<  mf_it->second->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(mf_it->second);
                                        }
                                        
                                        ptr<ge_pi> prev_use = find_last_use_of_register(target_reg->id_get());
                                        if ( prev_use ) {
                                                deplog << "T. " << copy_code->front()->uid_get() << " -> " <<  prev_use->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(prev_use);
                                        }
                
                                        set_last_use_of_register(target_reg->id_get(),copy_code->back());
                                        (*spill_space_last_use)[mf] = copy_code->back();
                                } else if ( source_reg && !target_reg ) {
                                        //Copy value reg -> mem.
                                        ptr<pi_mem_factory> mf = next->allocated_spill_place_get();
                                        
                                        if ( !mf ) {
                                                mf = get_free_spill_space(next->operand_get()->type_get());
                                                next->allocated_spill_place_set(mf);
                                        }
                                        
                                        ptr<ge_operand_mem> spill_place = mf->get_ge_mem(NULL);
                                        copy_code = move_gen->generate_store_to_memory(interval->operand_get(),source_reg,spill_place);
                                        spill_place->origin_set(copy_code->back());
                                        
                                        mf2ge_pi__type::iterator mf_it = spill_space_last_use->find(mf);
                                        if ( mf_it!=spill_space_last_use->end() ) {
                                                deplog << "U. " << copy_code->front()->uid_get() << " -> " <<  mf_it->second->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(mf_it->second);
                                        }
                                        
                                        ptr<ge_pi> prev_use = find_last_use_of_register(source_reg->id_get());
                                        if ( prev_use ) {
                                                deplog << "V. " << copy_code->front()->uid_get() << " -> " <<  prev_use->uid_get() << "\n" << eolog;
                                                copy_code->front()->dependencies_get()->insert(prev_use);
                                        }
                
                                        set_last_use_of_register(source_reg->id_get(),copy_code->back());
                                        (*spill_space_last_use)[mf] = copy_code->back();
                                }
                                
                                if ( copy_code ) {
                                        //Insert the copy code to a basic block.
                                        ptr<basic_block> bb = interval->instructions_get()->back()->bb_get();
                                        bb->instructions_get()->insert(bb->instructions_get()->end(),copy_code->begin(),copy_code->end());
                                        
#ifdef BACKEND_V2_DEBUG         
                                ::std::ostringstream oss1;
                                oss1 << "copy code between intervals (i1=" << interval->uid_get() << ", i2=" << next->uid_get() << ")";
                                set_instruction_property(copy_code,ge_pi::PROPERTY_SPILLGEN_INFO,oss1.str());
#endif
                                }
                                
                        } else {
                                if ( interval->allocated_spill_place_get() ) {
                                        free_spill_spaces->insert(interval->allocated_spill_place_get());
                                }
                        }       
                        
                        if ( interval->allocated_reg_get() && (*register_owners)[interval->allocated_reg_get()->id_get()]==interval ) {
                                b_free_regs_need_recalculate = true;
                                used_registers->erase(interval->allocated_reg_get()->id_get());
                                register_owners->erase(interval->allocated_reg_get()->id_get());
                        }
                } else {
                        ++it;
                }
        }
        
        slog << "expire_old_intervals end\n" << eolog;
        
        return b_free_regs_need_recalculate;
        
}

/*!
        \brief Returns a pseudoinstruction that is the last user of a register.
        \param regid The register.
        \return The last user.
*/
ptr<ge_pi> spillgen::find_last_use_of_register(ulint regid) {
        slog << "find_last_use_of_register start\n" << eolog;
        
        reg2ge_pi__type::iterator it = register_last_use->find(regid);
        
        slog << "find_last_use_of_register end\n" << eolog;
        return it==register_last_use->end() ? NULL : it->second;
}

/*!
        \brief Sets a pseudoinstruction as the last user of a register.
        \param regid The register.
        \param ge The last user.
*/
void spillgen::set_last_use_of_register(ulint regid, ptr<ge_pi> ge) {
        slog << "set_last_use_of_register start\n" << eolog;
        
        ptr<tm_register> reg = tm_register::instance(regid);
        ptr<id_set__type> aliases = reg->aliases_get();
        
        for(id_set__type::iterator it = aliases->begin(); it!=aliases->end(); ++it) {
                (*register_last_use)[*it] = ge;
        }
        
        slog << "set_last_use_of_register end\n" << eolog;
}

/*!
        \brief Inserts a vector of pseudoinstructions into a basic block.
        \param bb The basic block.
        \param code The vector of instructions.
        \param back True if the instructions should be at the end of the block, false for beginning.
*/
void spillgen::insert_code_to_bb(ptr<basic_block> bb, ptr<ge_pi_vector__type> code, bool back) {
        for(ge_pi_vector__type::iterator it = code->begin(); it!=code->end(); ++it) {
                (*it)->bb_set(bb);
        }

        if ( back ) {
                bb->instructions_get()->insert(bb->instructions_get()->end(),code->begin(),code->end());
        } else {
                bb->instructions_get()->insert(bb->instructions_get()->begin(),code->begin(),code->end());
        }
}


/*!
        \brief Adds a custom property value to a list of pseudoinstructions.
        
        \param instrs The list.
        \param property_id A id of the property.
        \param property_Value The value.
*/
void spillgen::set_instruction_property(ptr<ge_pi_vector__type> instrs,ulint property_id,lstring property_value) {
        for(ge_pi_vector__type::iterator it = instrs->begin(); it!=instrs->end(); ++it) {       
                ptr<ge_pi> ge = *it;
                
                if ( !ge->properties_get() ) {
                        ge->properties_set(id2lstring__type::create());
                }
                
                (*ge->properties_get())[property_id] = property_value;
        }
}       

/*!
        \brief Returns data of the processed function with spill-code included.
*/
ptr< ::lestes::backend_v2::structs::func_data > spillgen::get_result() {
        slog << "get_result start\n" << eolog;

        slog << "get_result end\n" << eolog;
        return data_get();
}



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

---