#include "benode_t.h"
#include "besched_t.h"
#include "beilpsched.h"
+#include "beutil.h"
typedef struct _ilpsched_options_t {
+ unsigned regpress;
unsigned limit_dead;
unsigned time_limit;
char log_file[1024];
typedef struct _ilpsched_node_attr_t {
unsigned asap; /**< The ASAP scheduling control step */
unsigned alap; /**< The ALAP scheduling control step */
+ unsigned latency; /**< Latency of this node (needed for sorting) */
unsigned sched_point; /**< the step in which the node is finally scheduled */
unsigned visit_idx; /**< Index of the node having visited this node last */
unsigned consumer_idx; /**< Index of the node having counted this node as consumer last */
#define get_ilpsched_block_attr(block) (&(block)->attr.block_attr)
#define get_ilpsched_node_attr(node) (&(node)->attr.node_attr)
-/* iterate over a list of ir_nodes linked by link field */
-#define foreach_linked_irns(head, iter) for ((iter) = (head); (iter); (iter) = get_irn_link((iter)))
-
/* check if node is considered for ILP scheduling */
#define consider_for_sched(isa, irn) \
(! (is_Block(irn) || \
is_normal_Proj(isa, irn) || \
is_Phi(irn) || \
is_NoMem(irn) || \
- is_Jmp(irn) || \
+ is_Unknown(irn) || \
is_End(irn) \
))
/* option variable */
static ilpsched_options_t ilp_opts = {
+ 1, /* default is with register pressure constraints */
70, /* if we have more than 70 nodes: use alive nodes constraint */
300, /* 300 sec per block time limit */
"" /* no log file */
#ifdef WITH_LIBCORE
/* ILP options */
static const lc_opt_table_entry_t ilpsched_option_table[] = {
+ LC_OPT_ENT_BOOL("regpress", "Use register pressure constraints", &ilp_opts.regpress),
LC_OPT_ENT_INT("limit_dead", "Upto how many nodes the dead node constraint should be used", &ilp_opts.limit_dead),
LC_OPT_ENT_INT("time_limit", "ILP time limit per block", &ilp_opts.time_limit),
LC_OPT_ENT_STR("lpp_log", "LPP logfile (stderr and stdout are supported)", ilp_opts.log_file, sizeof(ilp_opts.log_file)),
return 1;
if (heights_reachable_in_block(glob_heights, irn_b, irn_a))
return -1;
- return 0;
+
+ /*
+ Ok, timestep is equal and the nodes are parallel,
+ so check latency and schedule high latency first.
+ */
+ return QSORT_CMP(n2_a->latency, n1_a->latency);
}
else
return QSORT_CMP(n1_a->sched_point, n2_a->sched_point);
ilpsched_node_attr_t *pna = get_ilpsched_node_attr(pred_node);
unsigned lat;
- lat = fixed_latency(env->sel, pred, env->block_env);
- na->asap = MAX(na->asap, pna->asap + lat);
+ lat = fixed_latency(env->sel, pred, env->block_env);
+ na->latency = lat;
+ na->asap = MAX(na->asap, pna->asap + lat);
}
}
if (! LPP_VALUE_IS_0(val)) {
na->sched_point = t;
ARR_APP1(be_ilpsched_irn_t *, sched_nodes, node);
- DBG((env->dbg, LEVEL_1, "Schedpoint of %+F is %u at unit type %s\n",
+ DBG((env->dbg, LEVEL_2, "Schedpoint of %+F is %u at unit type %s\n",
irn, t, na->type_info[tp_idx].tp->name));
found = 1;
}
}
}
- glob_heights = heights_new(env->irg);
+ glob_heights = env->height;
/* sort nodes ascending by scheduling time step */
qsort(sched_nodes, ARR_LEN(sched_nodes), sizeof(sched_nodes[0]), cmp_ilpsched_irn);
- heights_free(glob_heights);
}
/* make all Phis ready and remember the single cf op */
case iro_End:
case iro_Proj:
case iro_Bad:
+ case iro_Unknown:
break;
default:
if (is_cfop(irn)) {
/* add all nodes from list */
for (i = 0, l = ARR_LEN(sched_nodes); i < l; ++i) {
ilpsched_node_attr_t *na = get_ilpsched_node_attr(sched_nodes[i]);
- add_to_sched(env, block, sched_nodes[i]->irn, na->sched_point);
+ if (sched_nodes[i]->irn != cfop)
+ add_to_sched(env, block, sched_nodes[i]->irn, na->sched_point);
}
/* schedule control flow node if not already done */
num_cst, ilp_timer_elapsed_usec(t_cst) / 1000000.0));
}
+#if 0
static void create_proj_keep_constraints(be_ilpsched_env_t *env, lpp_t *lpp, be_ilpsched_irn_t *block_node) {
char buf[1024];
ir_node *irn;
DBG((env->dbg, LEVEL_1, "\t%u Proj and Keep constraints (%g sec)\n",
num_cst, ilp_timer_elapsed_usec(t_cst) / 1000000.0));
}
+#endif
/***************************************************
* _____ _ _____ _
FILE *logfile = NULL;
lpp_t *lpp = NULL;
struct obstack var_obst;
+ char name[1024];
DBG((env->dbg, 255, "\n\n\n=========================================\n"));
DBG((env->dbg, 255, " ILP Scheduling for %+F\n", block));
/* if we have less than two interesting nodes, there is no need to create the ILP */
if (ba->n_interesting_nodes > 1) {
- double fact_var = ba->n_interesting_nodes > 25 ? 1.1 : 1.2;
- double fact_cst = ba->n_interesting_nodes > 25 ? 0.7 : 1.5;
+ double fact_var = ba->n_interesting_nodes > 25 ? 2.3 : 3;
+ double fact_cst = ba->n_interesting_nodes > 25 ? 3 : 4.5;
int base_num = ba->n_interesting_nodes * ba->n_interesting_nodes;
int estimated_n_var = (int)((double)base_num * fact_var);
int estimated_n_cst = (int)((double)base_num * fact_cst);
- DBG((env->dbg, LEVEL_1, "Creating LPP with estimed numbers: %d vars, %d cst\n",
+ DBG((env->dbg, LEVEL_1, "Creating LPP with estimated numbers: %d vars, %d cst\n",
estimated_n_var, estimated_n_cst));
/* set up the LPP object */
+ snprintf(name, sizeof(name), "ilp scheduling IRG %s", get_entity_ld_name(get_irg_entity(env->irg)));
+
lpp = new_lpp_userdef(
- "be ilp scheduling",
+ (const char *)name,
lpp_minimize,
- estimated_n_cst + 1, /* num vars */
- estimated_n_cst + 20, /* num cst */
- 1.2); /* grow factor */
+ estimated_n_cst, /* num vars */
+ estimated_n_cst + 1, /* num cst */
+ 1.3); /* grow factor */
obstack_init(&var_obst);
/* create ILP variables */
create_ressource_constraints(env, lpp, block_node);
create_bundle_constraints(env, lpp, block_node);
//create_proj_keep_constraints(env, lpp, block_node);
- if (ba->n_interesting_nodes > env->opts->limit_dead) {
- create_alive_nodes_constraint(env, lpp, block_node);
- create_pressure_alive_constraint(env, lpp, block_node);
- } else {
- create_dying_nodes_constraint(env, lpp, block_node);
- create_pressure_dead_constraint(env, lpp, block_node);
+
+ if (env->opts->regpress) {
+ if (ba->n_interesting_nodes > env->opts->limit_dead) {
+ create_alive_nodes_constraint(env, lpp, block_node);
+ create_pressure_alive_constraint(env, lpp, block_node);
+ } else {
+ create_dying_nodes_constraint(env, lpp, block_node);
+ create_pressure_dead_constraint(env, lpp, block_node);
+ }
}
DBG((env->dbg, LEVEL_1, "ILP to solve: %u variables, %u constraints\n", lpp->var_next, lpp->cst_next));
/* debug stuff, dump lpp when debugging is on */
DEBUG_ONLY(
- if (firm_dbg_get_mask(env->dbg) > 0) {
+ if (firm_dbg_get_mask(env->dbg) > 1) {
char buf[1024];
FILE *f;
DBG((env->dbg, LEVEL_1, "\nSolution:\n"));
DBG((env->dbg, LEVEL_1, "\tsend time: %g sec\n", lpp->send_time / 1000000.0));
DBG((env->dbg, LEVEL_1, "\treceive time: %g sec\n", lpp->recv_time / 1000000.0));
+ DBG((env->dbg, LEVEL_1, "\tmatrix: %u elements, density %.2f%%, size %.2fMB\n", lpp->n_elems, lpp->density, (double)lpp->matrix_mem / 1024.0 / 1024.0));
DBG((env->dbg, LEVEL_1, "\titerations: %d\n", lpp->iterations));
DBG((env->dbg, LEVEL_1, "\tsolution time: %g\n", lpp->sol_time));
DBG((env->dbg, LEVEL_1, "\tobjective function: %g\n", LPP_VALUE_IS_0(lpp->objval) ? 0.0 : lpp->objval));
FIRM_DBG_REGISTER(env.dbg, "firm.be.sched.ilp");
- //firm_dbg_set_mask(env.dbg, 31);
+// firm_dbg_set_mask(env.dbg, 1);
env.irg_env = be_ilp_sched_init_irg_ilp_schedule(sel, birg->irg);
env.sel = sel;
/* We refine the {ASAP(n), ALAP(n)} interval and fix the time steps for Projs and Keeps */
irg_walk_in_or_dep_blkwise_graph(env.irg, NULL, refine_asap_alap_times, &env);
- /* we don't need this information any longer */
- heights_free(env.height);
-
/* perform ILP scheduling */
irg_block_walk_graph(env.irg, clear_unwanted_data, create_ilp, &env);
/* free all allocated object */
phase_free(&env.ph);
+ heights_free(env.height);
/* notify backend */
be_ilp_sched_finish_irg_ilp_schedule(sel, birg->irg, env.irg_env);
/**
* Register ILP scheduler options.
*/
-void ilpsched_register_options(lc_opt_entry_t *grp) {
- static int run_once = 0;
- lc_opt_entry_t *sched_grp;
-
- if (! run_once) {
- run_once = 1;
- sched_grp = lc_opt_get_grp(grp, "ilpsched");
+void be_init_ilpsched(void)
+{
+ lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
+ lc_opt_entry_t *sched_grp = lc_opt_get_grp(be_grp, "ilpsched");
- lc_opt_add_table(sched_grp, ilpsched_option_table);
- }
+ lc_opt_add_table(sched_grp, ilpsched_option_table);
}
#endif /* WITH_LIBCORE */