bb_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.g.hh>
#include <lestes/backend_v2/workers/bb_finder.g.hh>
#include <lestes/md/instructions/tm_instr.g.hh>

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

using namespace ::lestes::backend_v2::structs;
using namespace ::lestes::backend_v2::intercode;
using namespace ::lestes::md::instructions;
using namespace ::lestes::msg;

typedef set< srp<ge_pi> > ge_pi_set__type;
typedef map<srp<pi_mem_factory>,srp<set< srp<ge_pi> > > > m2ge_pi_set__type;
typedef list< srp<ge_pi> > ge_pi_list__type;
typedef vector< srp<ge_pi> > ge_pi_vector__type;
typedef vector< srp<ge_operand> > ge_operand_vector__type;
typedef vector< srp<basic_block> > bb_vector__type;

declare_logger(bblog);
initialize_logger( bblog, "bb_finder", backend_v2_logger );

/*!
        \brief Groups pseudoinstructions of a function body to basic blocks.
*/
void bb_finder::process() {
        
        ptr<ge_pi_list__type> body = data_get()->ge_body_get();
        ptr<bb_vector__type> bbs = data_get()->bbs_get();
        
        ptr<basic_block> prev_bb = NULL;
        ptr<basic_block> active_bb = NULL;
        
        bool b_active_is_safe = true;
        
        for(ge_pi_list__type::iterator it = body->begin(); it!=body->end(); ++it) {
                ptr<ge_pi> ge = *it;

                if (ge->kind_get()==ge_pi::SP ) {
                        ptr<ge_sp> sp = ge.dncast<ge_sp>();

                        if ( active_bb ) {
                                active_bb->lsp_set(sp);
                                
                                if ( prev_bb ) {
                                        //Join blocks.
                                        active_bb = join_blocks(prev_bb,active_bb);
                                } else {                                        
                                        bbs->push_back(active_bb);
                                }
                                
                                if ( sp->is_jmp_target_get() || !b_active_is_safe ) {
                                        prev_bb = NULL;
                                } else {
                                        prev_bb = active_bb;
                                }
                                
                                active_bb = NULL;
                        }
                        
                        if ( !active_bb && ge!=body->back() ) {
                                active_bb = basic_block::create();
                                active_bb->fsp_set(sp);
                                b_active_is_safe = true;
                        }
                        
                } else {                
                        /*
                                The following code line turns off block joining.
                                
                                Extended basic blocks bring a lots of problems especially 
                                in context with memory operands and memory alliasing.
                                
                                Extended blocks don't produce better results of code scheduling
                                so it is better to switch off block joining to extended blocks.
                        */
                        prev_bb = NULL; 
                        
                        ge->bb_set(active_bb);
                        active_bb->instructions_get()->push_back(ge);
                        
                        if ( !is_instruction_safe(ge) ) {
                                 //The block contains instruction that doesn't allow the block to be merged with a previous one.
                                 prev_bb = NULL;
                                 b_active_is_safe = false;
                        }
                }
        }
}

/*!
        \brief Tells whether a pseudoinstruction has any side-effect that disallows joining of the pseudoinstruction's basic block with preceding one.
        
        \param ge A pseudoinstruction.
        \return True it the pseudoinstruction is safe. False otherwise.
*/
bool bb_finder::is_instruction_safe(ptr<ge_pi> ge) {
        if ( (ge->instruction_get() && ( ge->instruction_get()->is_system() || ge->instruction_get()->is_jump()) ) ||
                 (ge->kind_get()==ge_pi::SP && ge.dncast<ge_sp>()->is_jmp_target_get()) ) {
                 return false;
        }
        
        ptr<ge_operand_vector__type> operands = ge->operands_input_get();
        
        for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                        continue;
                }

                ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                
                if ( mf->kind_get()==pi_mem_factory::MF_PTR_DEREF ) {
                        return false;
                }                       
        }

        operands = ge->operands_output_get();
        
        for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                        continue;
                }

                ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                
                if ( mf->kind_get()==pi_mem_factory::MF_PTR_DEREF ) {
                        return false;
                }                       
        }

        return true;            
}

/*!
        \brief Merges two basic blocks into one.
        
        \param bb1 A first basic block.
        \param bb2 A second basic block.
        \return A merged result.
*/
ptr<basic_block> bb_finder::join_blocks(ptr<basic_block> bb1, ptr<basic_block> bb2) {
        ptr<ge_pi_vector__type> active_instrs = bb2->instructions_get();
        ptr<ge_pi_vector__type> prev_instrs = bb1->instructions_get();
                                        
        ptr<ge_sp> prev_fsp = bb1->fsp_get();
        ptr<ge_sp> active_lsp = bb2->lsp_get();//
        
        bb1->lsp_set(active_lsp);
        
        ptr<ge_sp> active_fsp = bb2->fsp_get();
                                        
        /*  
                Split the bording sp into two sps. The first one will inherit input operands and dependencies
                and the second one will inherits output ones.
        */
        
        ptr<ge_sp> new_sp = ge_sp::create(NULL,NULL);
        new_sp->operands_input_set(active_fsp->operands_input_get());
        new_sp->dependencies_set(active_fsp->dependencies_get());
        new_sp->bb_set(bb1);
        prev_instrs->push_back(new_sp);
                                        
        prev_instrs->push_back(active_fsp);
        active_fsp->dependencies_set(ge_pi_set__type::create());
        active_fsp->operands_input_set(ge_operand_vector__type::create());
        active_fsp->bb_set(bb1);
                                        
        /*
                In the first block, find instructions that stores into memory.
        */
        ptr<m2ge_pi_set__type> mfdeps = m2ge_pi_set__type::create();
        
        for(ge_pi_vector__type::iterator it = prev_instrs->begin(); it!=prev_instrs->end(); ++it) {
                ptr<ge_pi> ge = *it;
                
                active_lsp->dependencies_get()->insert(ge);
                
                ptr<ge_operand_vector__type> operands = ge->operands_input_get();
                
                for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                        if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                                continue;
                        }

                        ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                                
                        m2ge_pi_set__type::iterator it_search = mfdeps->find(mf);
                                
                        if ( it_search!=mfdeps->end() ) {
                                it_search->second->insert(ge);
                        } else {
                                ptr<ge_pi_set__type> deps = ge_pi_set__type::create();
                                deps->insert(ge);
                                (*mfdeps)[mf] = deps;
                        }       
                }
                
                operands = ge->operands_output_get();
                
                for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                        if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                                continue;
                        }

                        ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                                
                        m2ge_pi_set__type::iterator it_search = mfdeps->find(mf);
                                
                        if ( it_search!=mfdeps->end() ) {
                                it_search->second->insert(ge);
                        } else {
                                ptr<ge_pi_set__type> deps = ge_pi_set__type::create();
                                deps->insert(ge);
                                (*mfdeps)[mf] = deps;
                        }       
                }
                
        }
        
        /*
                In the second block, find instructions that uses memory operands and set dependecies on instructions from the
                first block that produces these operands.
        */
        for(ge_pi_vector__type::iterator it = active_instrs->begin(); it!=active_instrs->end(); ++it) {
                ptr<ge_pi> ge = *it;
                
                ptr<ge_operand_vector__type> operands = ge->operands_input_get();
                
                for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                        if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                                continue;
                        }

                        ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                                
                        m2ge_pi_set__type::iterator it_search = mfdeps->find(mf);
                                
                        if ( it_search!=mfdeps->end() ) {
                                ge->dependencies_get()->insert(it_search->second->begin(),it_search->second->end());
                        }       
                }
                
                operands = ge->operands_output_get();
                
                for(ge_operand_vector__type::iterator it_op = operands->begin(); it_op!=operands->end(); ++it_op) {
                        if ( (*it_op)->kind_get()!=ge_operand::MEMORY ) {
                                continue;
                        }

                        ptr<pi_mem_factory> mf = (*it_op).dncast<ge_operand_mem>()->factory_get();
                                
                        m2ge_pi_set__type::iterator it_search = mfdeps->find(mf);
                                
                        if ( it_search!=mfdeps->end() ) {
                                ge->dependencies_get()->insert(it_search->second->begin(),it_search->second->end());
                        }       
                }
                
                //Finaly, insert instruction from the second block to the first one.
                prev_instrs->push_back(ge);
                ge->bb_set(bb1);
                ge->dependencies_get()->insert(prev_fsp);
                active_lsp->dependencies_get()->insert(ge);
                
        }
        
        bblog << "Blocks joined (" << bb1->uid_get() << "<-" << bb2->uid_get() << ").\n" << eolog;
        
        return bb1;
}

ptr<func_data> bb_finder::get_result() {
        return data_get();
}

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

---