order_governor.cc

Go to the documentation of this file.

#include <lestes/backend_v2/workers/order_governor.g.hh>
#include <lestes/backend_v2/intercode/pi.g.hh>
#include <lestes/backend_v2/structs/func_data.g.hh>
#include <lestes/backend_v2/intercode/visitor_pi_pi2pi_operands.g.hh>
#include <lestes/backend_v2/intercode/visitor_pi_pi2id.g.hh>
#include <lestes/backend_v2/structs/pi_operands.g.hh>
#include <lestes/backend_v2/debug/debug.hh>

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

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

typedef list< srp< pi_pi > > pi_list_type;
typedef list< srp< pi_sp > > sp_list_type;
typedef vector< srp< pi_operand > > operand_vector_type;
typedef map< srp<pi_pi>, bool > pi_bool_map_type;


declare_logger(og_log);
initialize_logger( og_log, "order_governor", backend_v2_logger );


/*!
        \brief Manages linearization.
*/
void order_governor::process()
{
        og_log << "Process begin\n" << eolog;
        
        pis_unordered = data_get()->pi_body_get();
        
        //Find pis with level set to 0.    
    identify_level_0();
        
        //Repeat loop while there are any unordered pis. 
    while( !pis_unordered_get()->empty() ) {
                og_log << "Main loop begin.\n" << eolog;
                
                //Find unordered pis with level=1 and move them to the ordered set.
                merge_ordered_with_unordered_level_X(1);
                //Order merged level 0&1 set.
                torder_ordered();
                //Linearize ordered sps.
                linearize_ordered_sps();
                //Move psp and nsp pointers.
                shift_unordered_nsp_psp();
                //Recalculate levels for unordered pis.
                renumber_levels(pis_unordered_get());
                //Recalculate levels for ordered pis.
                renumber_levels(pis_ordered_get());
                
                og_log << "Main loop end.\n" << eolog;
    }
        
        og_log << "Process end.\n" << eolog;
}


/*!
        \brief Moves pseudoinstructions of level 0 from pis_unordered to pis_ordered list.
*/
void order_governor::identify_level_0()
{
        //the ordered set is empty. Copy pis with level=0 to it.
    merge_ordered_with_unordered_level_X(0);
        
        //Set is_ordered=true for all pis with level=0.
    pi_list_type::iterator it;
    for(it=pis_ordered->begin(); it != pis_ordered->end(); it++) { 
                (*is_ordered)[*it] = true;
    }
        
        //Set is_ordered=false for all pis with level>0.
    for(it=pis_unordered->begin(); it != pis_unordered->end(); it++) { 
                (*is_ordered)[*it] = false;
    }
}

/*!
        \brief Merges unordered pseudoinstructions of given level with ordered pseudoinstructions.
        \param level_to_merge The level to be merged.
*/
void order_governor::merge_ordered_with_unordered_level_X(level_t level_to_merge)
{
        //Go through the unordered set.
    for(pi_list_type::iterator it = pis_unordered_get()->begin(); it != pis_unordered_get()->end();) {
                if ( (*it)->level_get() == level_to_merge ) {
                        og_log << "Merging L0 with L" << level_to_merge << ": " << (*it)->reflection_get()->back()->name_get() << "(" << (*it)->uid_get() << ")[level=" << (*it)->level_get() << "] added\n" << eolog;;
                        
                        //Current pi has the right level. Move it to the ordered set.
                pis_ordered->push_back(*it);
                        //Delete it from unordered set.
                it = pis_unordered->erase(it);
                } else {
                        ++it;
                }
    }
        
}

/*!
        \brief Linearizes sequencepoints in pis_ordered list.
*/
void order_governor::linearize_ordered_sps() {
        ptr<visitor_pi_pi2id> identificator = visitor_pi_pi2id::create();
        /*
                Go through ordered list and for each pi_sp set psp to the previous one
                and previous one's nsp to this sp.
        */
        ptr<pi_pi> previous = NULL;
        ptr<pi_pi> current = NULL;
        pi_list_type::iterator it;
    for(it=pis_ordered->begin(); it != pis_ordered->end(); it++) { 
        
                //if ( (*it)->accept_visitor_pi_pi2ulint_gen_base(identificator) == visitor_pi_pi2id::PI_SP ) {
                        //current pi is type of pi_sp
                        current = (*it);
                        
                        if ( previous ) {
                                previous->nsp_set(current);
                        }
                        current->psp_set(previous);
                        previous = current;
                //}
    }
        current->nsp_set(NULL);
}

/*!
        \brief Linearizes pis_ordered list.
        
        Performs topological ordering in directed acyclic graph. Vertices are pseudoinstructions from pis_ordered list.
        Incoming edges for pseudoinstruction pi are psp->pi and origin->pi for each pi's operand. Outcoming edge is 
        pi->nsp. 
*/
void order_governor::torder_ordered()
{

        og_log << "Tordering begin\n" << eolog;
        
        //The getter can obtain operands from any generic pi.
        ptr<visitor_pi_pi2pi_operands> operands_getter = visitor_pi_pi2pi_operands::create();
        
        //identificator can identify kind of any generic pi
        ptr<visitor_pi_pi2id> identificator = visitor_pi_pi2id::create();
        
        //List of ordered pis. No pi is ordered at the beginning.
    ptr<pi_list_type> tordered_list = pi_list_type::create();
        //List of unordered pis. Every pi is unordered at the beginning.
    ptr<pi_list_type> tunordered_list = pis_ordered_get();
    
        //Set is_ordered=false for all unordered pis.
    pi_list_type::iterator it;
    for(it=tunordered_list->begin(); it != tunordered_list->end(); it++) { 
                (*is_ordered)[*it] = false;
    }

#ifdef BACKEND_V2_DEBUG
        //infinite loop detection
        ulint dbg = 0;    
#endif

        //Repeat loop while there are any unordered pis. 
    while( !tunordered_list->empty()) {
        
#ifdef BACKEND_V2_DEBUG
                lassert2(dbg<=tunordered_list->size(),"An inifinite loop detected.");
                dbg++;
#endif          

                //Get first unorderd pi.
                ptr<pi_pi> pi = tunordered_list->front();
                
                //Remove it from unordered set.
                tunordered_list->pop_front();
                
                og_log << "Tordering: trying order " << pi->reflection_get()->back()->name_get() << "(" << pi->uid_get() << ")\n" << eolog;
        
                if ( pi->psp_get() && (*is_ordered_get())[pi->psp_get()] == false )  {
                        //Psp is unordered. So this pi is also unordered.
                tunordered_list->push_back(pi);
                        
                        og_log << "\tTordering: current pi can't be ordered (psp is not ordered yet)\n" << eolog;
                        
                        continue;
                }
                
                //Get it's operands.
                ptr<pi_operands> operands = pi->accept_visitor_pi_pi2pi_operands_gen_base(operands_getter);
                /* Test if every input operand's origin is ordered. 
                 ( Do not test output operands - its origin is set to the current pi. )
                */
                
            if ( !pi_operands_origins_ordered(operands->operands_input_get()) ) {
                        //One of operands hasn't got its origin ordered
                        tunordered_list->push_back(pi);
                        
                        og_log << "\tTordering: current pi can't be ordered (origins of operands are not ordered yet)\n" << eolog;
                        
                        continue;
                }
                
            if ( nsp_for_any(pi, tunordered_list) ) {
                        //It is pi_sp and it is nsp for one of unordered pis.
                        tunordered_list->push_back(pi);
                        
                        og_log << "\tTordering: current pi can't be ordered (sp is nsp for unorderd pi)\n" << eolog;
                        
                        continue;
                }
                
                (*is_ordered_get())[pi] = true;
            tordered_list->push_back(pi);
                
                og_log << "\tTordering: " << pi->reflection_get()->back()->name_get() << "(" << pi->uid_get() << ") is set as ordered\n" << eolog;

#ifdef BACKEND_V2_DEBUG
                dbg = 0;
#endif

    }
        
        //We have new bigger ordered set.
    pis_ordered_set(tordered_list);
        
        og_log << "Tordering end\n" << eolog;
}

/*!
        \brief Tells whether a sequencepoint is psp for any of pseudoinstructions in a list.
        \param sp The sequencepoint.
        \param list The list.
*/
bool order_governor::nsp_for_any(ptr<pi_pi> sp, ptr<pi_list_type> list) {
        //Go through the unordered set and check if sp is nsn for any of them.
    pi_list_type::iterator it;
    for(it = list->begin(); it != list->end();it++) {
                if ( (*it)->nsp_get()==sp ) {
                        return true;
                }
        }
        return false;
}

/*!
        \brief Tells whether origin of each operand in list is ordered.
        \param operand_list The list.
*/
bool order_governor::pi_operands_origins_ordered(ptr<operand_vector_type> operand_list) {
        lassert(operand_list);  
        
        //Go through operands and check if everyone is ordered.
    operand_vector_type::iterator it;
    for(it=operand_list->begin(); it!=operand_list->end(); it++) {
                ptr<pi_pi> origin = (*it)->origin_get();
                
                if ( !origin ) {
                        //Operand has not an origin.
                        continue;
                }
                
                //Find out if origin is ordered.
                pi_bool_map_type::iterator it1 = is_ordered->find(origin);
                
                //Origin has to be in map.
                lassert(it1!=is_ordered->end());
                
                if ( !it1->second ) {
                        //Origin is unordered.
                return false;
                }
    }
    return true;
}

/*!
        \brief Returns level of a pi_pi pseudoinstruction.
        
        \param pi The pi_pi.
        \return -1 if pi is NULL. Pi's level otherwise.
*/
int order_governor::get_pi_level(ptr < pi_pi > pi)
{
        return pi ? (int)pi->level_get() : -1;
}

/*!
        Gets last pi_pi pseudoinstruction of chain where two consequent pi_pi point with
        psp and nsp to each other.
        \param pi Start of the chain.
        \return The last pi of chain.
*/
ptr<pi_pi> order_governor::conjugated_chain_end_find(ptr<pi_pi> pi) 
{
        while(pi->nsp_get() && pi->nsp_get()->psp_get()==pi) {
                pi = pi->nsp_get();
        }       
        return pi;
}

/*!
        Gets first pi_pi pseudoinstruction of chain where two consequent pi_pi point with
        psp and nsp to each other.
        \param pi End of the chain.
        \return The first pi of chain.
*/
ptr<pi_pi> order_governor::conjugated_chain_start_find(ptr<pi_pi> pi) 
{
        while(pi->psp_get() && pi->psp_get()->nsp_get()==pi) {
                pi = pi->psp_get();
        }       
        return pi;
}


/*!
        \brief Shifts psp and nsp of pis_unordered pseudoinstructions.
*/
void order_governor::shift_unordered_nsp_psp()
{
        //Move psp and nsp of unordered pis.
    pi_list_type::iterator it;
    for(it = pis_unordered->begin(); it!=pis_unordered->end(); it++) {
                ptr<pi_pi> pi = (*it);
                
                og_log << "shift_unordered_nsp_psp: pi(" << pi->uid_get() << ").level= " << get_pi_level(pi) << "\n" <<  msg::eolog;
                
                lassert(get_pi_level(pi)>1);
                
                if ( get_pi_level(pi->psp_get())==0 ) {
                        ptr<pi_pi> pi_hlp = conjugated_chain_end_find(pi);
                        
                        og_log << "shift_psp: chain_end(" << pi_hlp->uid_get() << ").nsp.level=" << get_pi_level(pi_hlp->nsp_get()) << "\n" <<  msg::eolog;
                        
                        lassert(get_pi_level(pi_hlp)==get_pi_level(pi));
                        
                        if (get_pi_level(pi_hlp->nsp_get())>0){
                                pi->psp_set(pi_hlp->nsp_get()->psp_get());
                        }
                        
                } else if ( get_pi_level(pi->nsp_get())==0 ) {
                        ptr<pi_pi> pi_hlp = conjugated_chain_start_find(pi);

                        og_log << "shift_nsp: chain_begin(" << pi_hlp->uid_get() << ").psp.level=" << get_pi_level(pi_hlp->psp_get()) << "\n" << msg::eolog;

                        lassert(get_pi_level(pi_hlp)==get_pi_level(pi));

                        if (get_pi_level(pi_hlp->psp_get())>0) {
                                pi->nsp_set(pi_hlp->psp_get()->nsp_get());
                        }
                }
    }
}

/*!
        \brief Decrease by 1 level of pseudoinstructions in a list.
        \param pi_list The list.
*/
void order_governor::renumber_levels(ptr<pi_list_type> pi_list)
{
    lassert(pi_list);
        
        //Subtract 1 from level for every pi in the list. 
    pi_list_type::iterator it;
    for(it = pi_list->begin(); it!=pi_list->end(); it++) {
                ptr<pi_pi> pi = (*it);
                
                if ( pi->level_get() > 0 ) {
                pi->level_set(pi->level_get()-1);
                }
    }
}

/*!
        \brief Returns func_data with linearized pseudoinstructions.
*/
ptr<func_data> order_governor::get_result()
{
        lassert(pis_ordered);
                
        ptr<visitor_pi_pi2id> pi_id_getter = visitor_pi_pi2id::create();
        
        /*
                Set psp to the previous pi_sp (now it can also be pi_pi).
        */
        ptr<pi_sp> tmp_sp = NULL;
        for(pi_list_type::iterator it_pi_list = pis_ordered->begin(); it_pi_list!=pis_ordered->end(); ++it_pi_list) {
                ptr<pi_pi> pi = *it_pi_list;

                visitor_pi_pi2id::kind_type pi_id = (visitor_pi_pi2id::kind_type)pi->accept_visitor_pi_pi2ulint_gen_base(pi_id_getter);
                
                //Set psp to previous sequencepoint (now psp can be pi_sp or pi_pi )
                pi->psp_set(tmp_sp);
                
                //Add pi to an output list
                if ( pi_id==visitor_pi_pi2id::PI_SP ) {
                        tmp_sp = pi.dncast<pi_sp>();
                }
                
        }
        
        /*
                Set nsp to the following pi_sp (now it can also be pi_pi). 
        */
        tmp_sp = NULL;
        for(pi_list_type::reverse_iterator it_pi_list = pis_ordered->rbegin(); it_pi_list!=pis_ordered->rend(); ++it_pi_list) {
                ptr<pi_pi> pi = *it_pi_list;
                
                visitor_pi_pi2id::kind_type pi_id = (visitor_pi_pi2id::kind_type)pi->accept_visitor_pi_pi2ulint_gen_base(pi_id_getter);
                
                pi->nsp_set(tmp_sp);
                
                if ( pi_id==visitor_pi_pi2id::PI_SP ) {
                        tmp_sp = pi.dncast<pi_sp>();
                }
        }       
        
        data_get()->pi_body_set(pis_ordered);
        
        return data_get();
}

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

---