scheduler.cc

Go to the documentation of this file.

#include <lestes/backend_v2/structs/func_data.g.hh>
#include <lestes/backend_v2/intercode/pi.g.hh>
#include <lestes/backend_v2/intercode/ge.g.hh>
#include <lestes/backend_v2/workers/scheduler.g.hh>
#include <lestes/backend_v2/workers/bb_finder.g.hh>
#include <lestes/md/instructions/tm_instr_base.g.hh>
#include <lestes/md/instructions/execution_info.g.hh>

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

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

using namespace ::lestes::backend_v2::debug;
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 vector< srp<ge_pi> > ge_pi_vector__type;
typedef list< srp<ge_pi> > ge_pi_list__type;
typedef vector< srp<basic_block> > bb_vector__type;
typedef map< srp<ge_pi>, srp<schedule_item> > ge2si__type;
typedef set< srp<schedule_item> > si_set__type;
typedef vector< srp<schedule_item> > si_vector__type;

declare_logger(schedlog);
initialize_logger( schedlog, "scheduler", backend_v2_logger );

/*!
        \brief Schedules pseudoinstructions of a function body.
*/
void scheduler::process() {
        schedlog << "process start\n" << eolog;
        
        ptr<ge_pi_list__type> body = ge_pi_list__type::create();
        
        current_schedule_pos = 0;
        
        ptr<bb_vector__type> bbs = data_get()->bbs_get();
        
        for(bb_vector__type::iterator it = bbs->begin(); it!=bbs->end(); ++it) {
                ptr<basic_block> bb = *it;
                
                //Insert fsp of the basic block to the body
                body->push_back(bb->fsp_get());
                bb->fsp_get()->schedule_pos_set(current_schedule_pos++);
                
                //Insert scheduled instructions of the block to the body
                ptr<ge_pi_vector__type> output = process_bb(bb);
                body->insert(body->end(), output->begin(), output->end());
        }
        
        //Insert the last sequencepoint to the body
        ptr<ge_pi> lsp = bbs->back()->lsp_get();
        lsp->schedule_pos_set(current_schedule_pos);
        body->push_back(lsp);
        
        data_get()->ge_body_set(body);
        
        schedlog << "process end\n" << eolog;
}

/*!
        \brief Schedules pseudoinstructions of a basic block.
        
        \param bb The basic block.
        \return The scheduled pseudoinstructions.
*/
ptr<ge_pi_vector__type> scheduler::process_bb(ptr<basic_block> bb) {
        schedlog << "process_bb start\n" << eolog;
        ptr<si_set__type> sch_items = find_schedule_items(bb);
        
        if ( !dumb_scheduling_get() ) {
                //Do not perform inteligent scheduling. Just select random valid schedule.
                find_critical_paths(sch_items);
        }
        ptr<ge_pi_vector__type> output = schedule_items(sch_items);
        schedlog << "process_bb end\n" << eolog;
        return output;
}

/*!
        \brief Compares latest_start_time property of schedule_item instances.
*/
bool schedule_items_cmp1(srp<schedule_item> a, srp<schedule_item> b) {
        return a->latest_start_time_get() < b->latest_start_time_get();
}


/*!
        \brief Schedules a list of schedule_item instances.
        
        \param The list.
        \return The scheduled list.
*/
ptr<ge_pi_vector__type> scheduler::schedule_items(ptr<si_set__type> items) {
        schedlog << "schedule_items start\n" << eolog;
        
        ptr<ge_pi_vector__type> schedule = ge_pi_vector__type::create();
                
        ptr<si_set__type> waiting = items;
        ptr<si_vector__type> ready = si_vector__type::create();
        
        //Find items with no imput dependencies in the waiting set and move them to the ready set.
        for(si_set__type::iterator it=waiting->begin(); it!=waiting->end();) {
                ptr<schedule_item> si = *it;
                
                si->out_deps_set(si->out_deps_copy_get());                              
                
                if ( si->in_deps_get()->size()==0 ) {
                        si_set__type::iterator del_it = it++; 
                        waiting->erase(del_it);
                        ready->push_back(si);
                } else {
                        ++it;
                }
        }

        //Sort ready items by increasing latest_start_time
        ::std::sort(ready->begin(),ready->end(),schedule_items_cmp1);
                
        while( ready->size()!=0 ) {
                ptr<schedule_item> si = *ready->begin();
                
                schedule->push_back(si->instruction_get());
                si->instruction_get()->schedule_pos_set(current_schedule_pos++);
                ready->erase(ready->begin());
                
                bool b_ready_set_changed = false;
                
                //Remove the item from in_deps of any succeeding item.
                ptr<si_set__type> deps = si->out_deps_get();
                for(si_set__type::iterator it1 = deps->begin(); it1!=deps->end(); ++it1) {
                        ptr<schedule_item> dep = *it1;
                        dep->in_deps_get()->erase(si);
                        
                        if ( dep->in_deps_get()->size()==0 ) {
                                //Item has no other in_deps -> move it to the ready set.
                                waiting->erase(dep);
                                ready->push_back(dep);
                                b_ready_set_changed = true;
                        }
                }
                
                if ( b_ready_set_changed ) {
                        //Sort ready items by increasing latest_start_time
                        ::std::sort(ready->begin(),ready->end(),schedule_items_cmp1);
                }
        }

        if ( waiting->size()!=0 ) {
                b_dump(waiting,"waiting");
        }
        lassert(waiting->size()==0);
                
        schedlog << "schedule_items end\n" << eolog;
        return schedule;
}

/*!
        \brief Checks whether a set of schedule_item instances contains a dependence loop.
        
        NOTE: For debugging purposes.
*/
void scheduler::check_waiting_set(ptr<si_set__type> waiting) {
        for(si_set__type::iterator it = waiting->begin(); it!=waiting->end(); ++it) {
                ptr<schedule_item> si = *it;
                
                if ( find_dependence_loop(si,si,0) ) {
                        return;
                }               
        }
}

/*!
        \brief Recursively searches for a dependence loops.
        
        NOTE: For debugging purposes.
*/
bool scheduler::find_dependence_loop(ptr<schedule_item> start,ptr<schedule_item> curr,ulint depth) {
        if ( depth > 4 ) {
                return false;
        }
        
        ptr<si_set__type> deps = curr->in_deps_get();
        
        for(si_set__type::iterator it = deps->begin(); it!=deps->end(); ++it) {
                ptr<schedule_item> dep = *it;
                
                if ( dep==start || find_dependence_loop(start,dep,depth+1)) {
                        schedlog << "find_dependence_loop found:item=" << curr->uid_get() << "\n" << eolog;
                        return true;
                }
        }
        
        return false;
}

/*!
        \brief Searches for a critical path within a set of schedule_item instances.
*/
void scheduler::find_critical_paths(ptr<si_set__type> items) {
        schedlog << "find_critical_paths start\n" << eolog;
        
        /* Compute length of a critical path */
        ulint cp_length = 0;
        
        ptr<si_set__type> waiting = si_set__type::create(items);
        
        ulint u_tmp = 0;
        
        si_set__type::iterator it = waiting->begin();
        while( waiting->size()!=0 ) {
                ptr<schedule_item> si = *it;
        
                if ( ++u_tmp > 10000 ) {
                        lassert2(false,"An infinite loop detected.");
                }       
                
                if (  si->in_deps_get()->size()==0 ) {
                        //End time of the item.
                        si->end_time_set(si->start_time_get() + si->etime_get());
                        
                        //Start time of a succeeding item.
                        ulint succ_start_time = si->end_time_get() + si->ctime_get();
        
                        if ( succ_start_time > cp_length ) {
                                cp_length = succ_start_time;
                        }               
                        
                        //Remove the item from in_deps of any succeeding item.
                        ptr<si_set__type> deps = si->out_deps_get();
                        for(si_set__type::iterator it1 = deps->begin(); it1!=deps->end(); ++it1) {
                                ptr<schedule_item> dep = *it1;
                                
                                dep->in_deps_get()->erase(si);
                                
                                //Recompute start time of the dep.
                                if ( dep->start_time_get()<succ_start_time ) {
                                        dep->start_time_set(succ_start_time);
                                }       
                        }
                        si_set__type::iterator del_it = it++;
                        waiting->erase(del_it);
                } else {
                        ++it;
                }       
                
                if ( it==waiting->end() ) {
                        it = waiting->begin();
                }
        }
        
        /* Set the last possible start time for the output (that not have input dependencies) items */
        waiting = si_set__type::create(items);
        for(it = waiting->begin(); it!=waiting->end(); ++it) {
                ptr<schedule_item> si = *it;
                
                if ( si->end_time_get() + si->ctime_get() == cp_length ) {
                        //The output item.
                        si->latest_start_time_set(si->end_time_get() - si->etime_get());
                }

                si->in_deps_set(si->in_deps_copy_get());                
        }
        
        /* Compute the last possible start time for the items. */
        it = waiting->begin();
        while( waiting->size()!=0 ) {
                ptr<schedule_item> si = *it;
                
                if (  si->out_deps_get()->size()==0 ) {
                        ulint lst = si->latest_start_time_get();
                                                
                        //Remove the item from out_deps of any preceeding item.
                        ptr<si_set__type> deps = si->in_deps_get();
                        for(si_set__type::iterator it1 = deps->begin(); it1!=deps->end(); ++it1) {
                                ptr<schedule_item> dep = *it1;                          
                                dep->out_deps_get()->erase(si);
                                
                                ulint tmp_lst = lst - dep->ctime_get() - dep->etime_get();
                                
                                if ( tmp_lst < dep->latest_start_time_get() ) {
                                        dep->latest_start_time_set(tmp_lst);
                                }
                        }
                        
                        si_set__type::iterator del_it = it++;
                        waiting->erase(del_it);
                } else {
                        ++it;
                }
                
                if ( it==waiting->end() ) {
                        it = waiting->begin();
                }
        }
        
        schedlog << "find_critical_paths end\n" << eolog;       
}

/*!
        \brief Creates set of schedule_items for a basic block.
        
        \param bb The basic block.
        \return The set of schedule_items.
*/
ptr<si_set__type> scheduler::find_schedule_items(ptr<basic_block> bb) {
        schedlog << "find_schedule_items start\n" << eolog;
        
        ge2si->clear();
        
        ptr<si_set__type> schedule_items = si_set__type::create();
        
        ptr<ge_pi_vector__type> instrs = bb->instructions_get();
        
        //Go through instructions of the block and create corresponding schedule items.
        for(ge_pi_vector__type::iterator it = instrs->begin(); it!=instrs->end(); ++it) {
                ptr<ge_pi> ge = *it;
                
                ptr<schedule_item> si;
                
                ge2si__type::iterator si_search = ge2si->find(ge);
                if ( si_search!=ge2si->end() ) {
                        si = si_search->second; 
                } else {
                        si = create_schedule_item(ge);
                        (*ge2si)[ge] = si;
                }               
                
                schedule_items->insert(si);
                
                ptr<ge_pi_set__type> in_deps = ge->dependencies_get();
                for(ge_pi_set__type::iterator it1 = in_deps->begin(); it1!=in_deps->end(); ++it1 ) {
                        ptr<ge_pi> dep_ge = *it1;
                        
                        if ( dep_ge->bb_get()!=bb || dep_ge==ge) {
                                continue;
                        }
                        
                        ptr<schedule_item> dep;
                        
                        si_search = ge2si->find(dep_ge);
                        if ( si_search!=ge2si->end() ) {
                                dep = si_search->second;        
                        } else {
                                dep = create_schedule_item(*it1);
                                (*ge2si)[dep_ge] = dep;
                        }
                        
                        si->in_deps_get()->insert(dep);
                        dep->out_deps_get()->insert(si);
                }
                
        }
        
        for(si_set__type::iterator it=schedule_items->begin(); it!=schedule_items->end(); ++it) {
                ptr<schedule_item> si = *it;
                si->in_deps_copy_set(si_set__type::create(si->in_deps_get()));
                si->out_deps_copy_set(si_set__type::create(si->out_deps_get()));
        }
        
        schedlog << "find_schedule_items end\n" << eolog;
        return schedule_items;
}

/*!
        \brief Creates schedule item for a pseudoinstruction.
        
        \param ge The pseudoinstruction.
        \return The schedule item.
*/
ptr<schedule_item> scheduler::create_schedule_item(ptr<ge_pi> ge) {
        
        ptr<tm_instr_base> tm = ge->instruction_get();
                
        ulint et, ct;
                
        if ( tm && tm->exec_info_get() ) {
                et = tm->exec_info_get()->etime_get();
                ct = 0;
        } else {
                et = 0;
                ct = 0;
        }
                
        ptr<schedule_item> si = schedule_item::create(ge,et,ct);
        
        return si;
}

/*!
        \brief Returns data of the processed function with scheduled body.
*/
ptr<func_data> scheduler::get_result() {
        return data_get();
}


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

---