src/lima/gp_ir/scheduler.c
// Finds a position for node.
// Success is set to false if no position could be found for node that satisfies
// all the constraints, in which case node is still scheduled and an
// intermediate move must be inserted.
Finds a position for node.
Success is set to false if no position could be found for node that satisfies
all the constraints, in which case node is still scheduled and an
intermediate move must be inserted.
Finds a position for node . Success is set to false if no position could be found for node that satisfies all the constraints in which case node is still scheduled and an intermediate move must be inserted .
static bool try_place_node(lima_gp_ir_node_t* node, bool* success)
{
	unsigned i, j;
	for (i = 0; i < lima_gp_ir_op[node->op].num_sched_positions; i++)
	{
		instr_range_t range = (instr_range_t) {
			.start_instr = 0,
			.end_instr = INT_MAX
		};
		node->sched_pos = i;
		lima_gp_ir_dep_info_t* dep_info;
		ptrset_iter_t iter = ptrset_iter_create(node->succs);
		bool was_successful = true;
		ptrset_iter_for_each(iter, dep_info)
		{
			instr_range_t new_range;
			new_range.start_instr = dep_info->succ->sched_instr +
				lima_gp_ir_dep_info_get_min_dist(dep_info);
			new_range.end_instr = dep_info->succ->sched_instr +
				lima_gp_ir_dep_info_get_max_dist(dep_info);
			if (!instr_range_union(&range, new_range))
			{
				was_successful = false;
				break;
			}
		}
		if (was_successful)
		{
			for (j = range.start_instr; j <= range.end_instr; j++)
			{
				node->sched_instr = j;
				bool insert_result;
				if (!try_insert_node(node, &insert_result))
					return false;
				if (insert_result)
				{
					*success = true;
					return true;
				}
			}
		}
	}
	unsigned max_instr = 0;
	for (i = 0; i < lima_gp_ir_op[node->op].num_sched_positions; i++)
	{
		instr_range_t range = (instr_range_t) {
			.start_instr = 0,
			.end_instr = INT_MAX
		};
		lima_gp_ir_dep_info_t* dep_info;
		ptrset_iter_t iter = ptrset_iter_create(node->succs);
		ptrset_iter_for_each(iter, dep_info)
		{
			instr_range_t new_range;
			new_range.start_instr = dep_info->succ->sched_instr +
				lima_gp_ir_dep_info_get_min_dist(dep_info);
			new_range.end_instr = dep_info->succ->sched_instr +
				lima_gp_ir_dep_info_get_max_dist(dep_info);
			if (!instr_range_union(&range, new_range))
			{
				if (new_range.start_instr > range.start_instr)
					range = new_range;
			}
		}
		for (j = range.start_instr; j <= range.end_instr; j++)
		{
			node->sched_instr = j;
			bool insert_result;
			if (!try_insert_node(node, &insert_result))
				return false;
			if (insert_result)
			{
				*success = false;
				return true;
			}
		}
		if (range.end_instr > max_instr)
			max_instr = range.end_instr;
	}
	node->sched_instr = max_instr + 1;
	while (true)
	{
		for (i = 0; i < lima_gp_ir_op[node->op].num_sched_positions; i++)
		{
			node->sched_pos = i;
			bool insert_result;
			if (!try_insert_node(node, &insert_result))
				return false;
			if (insert_result)
			{
				*success = false;
				return true;
			}
		}
		node->sched_instr++;
	}
	return false;
}
static bool try_place_node ( lima_gp_ir_node_t * node , bool * success ) { unsigned i , j ; for ( i = 0 ; i < lima_gp_ir_op [ node -> op ] . num_sched_positions ; i ++ ) { instr_range_t range = ( instr_range_t ) { . start_instr = 0 , . end_instr = INT_MAX } ; node -> sched_pos = i ; lima_gp_ir_dep_info_t * dep_info ; ptrset_iter_t iter = ptrset_iter_create ( node -> succs ) ; bool was_successful = true ; ptrset_iter_for_each ( iter , dep_info ) { instr_range_t new_range ; new_range . start_instr = dep_info -> succ -> sched_instr + lima_gp_ir_dep_info_get_min_dist ( dep_info ) ; new_range . end_instr = dep_info -> succ -> sched_instr + lima_gp_ir_dep_info_get_max_dist ( dep_info ) ; if ( ! instr_range_union ( & range , new_range ) ) { was_successful = false ; break ; } } if ( was_successful ) { for ( j = range . start_instr ; j <= range . end_instr ; j ++ ) { node -> sched_instr = j ; bool insert_result ; if ( ! try_insert_node ( node , & insert_result ) ) return false ; if ( insert_result ) { * success = true ; return true ; } } } } unsigned max_instr = 0 ; for ( i = 0 ; i < lima_gp_ir_op [ node -> op ] . num_sched_positions ; i ++ ) { instr_range_t range = ( instr_range_t ) { . start_instr = 0 , . end_instr = INT_MAX } ; lima_gp_ir_dep_info_t * dep_info ; ptrset_iter_t iter = ptrset_iter_create ( node -> succs ) ; ptrset_iter_for_each ( iter , dep_info ) { instr_range_t new_range ; new_range . start_instr = dep_info -> succ -> sched_instr + lima_gp_ir_dep_info_get_min_dist ( dep_info ) ; new_range . end_instr = dep_info -> succ -> sched_instr + lima_gp_ir_dep_info_get_max_dist ( dep_info ) ; if ( ! instr_range_union ( & range , new_range ) ) { if ( new_range . start_instr > range . start_instr ) range = new_range ; } } for ( j = range . start_instr ; j <= range . end_instr ; j ++ ) { node -> sched_instr = j ; bool insert_result ; if ( ! try_insert_node ( node , & insert_result ) ) return false ; if ( insert_result ) { * success = false ; return true ; } } if ( range . end_instr > max_instr ) max_instr = range . end_instr ; } node -> sched_instr = max_instr + 1 ; while ( true ) { for ( i = 0 ; i < lima_gp_ir_op [ node -> op ] . num_sched_positions ; i ++ ) { node -> sched_pos = i ; bool insert_result ; if ( ! try_insert_node ( node , & insert_result ) ) return false ; if ( insert_result ) { * success = false ; return true ; } } node -> sched_instr ++ ; } return false ; }
Finds a position for node.
Finds a position for node .
//We found a range that satisfies the constraints, try to insert the //node there. // We couldn't find a position, so relax our requirements - now we'll only // look for positions that satisfy some of the constraints //Choose the greatest (earliest) range & keep going // Now we've exhausted every option, and it's impossible to satisfy any of // the constraints. Start at max_instr and keep going backwards until // the insertion succeeds - it has to succeed eventually, because we'll // hit a newly-created, empty instruction.