2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Driver for the chordal register allocator.
9 * @author Sebastian Hack
23 #include "lc_opts_enum.h"
27 #include "irgraph_t.h"
39 #include "iredges_t.h"
42 #include "bechordal_t.h"
59 #include "bespillslots.h"
63 #include "becopystat.h"
64 #include "becopyopt.h"
65 #include "bessadestr.h"
69 #include "bepbqpcoloring.h"
71 static be_ra_chordal_opts_t options = {
73 BE_CH_LOWER_PERM_SWAP,
77 static const lc_opt_enum_int_items_t lower_perm_items[] = {
78 { "copy", BE_CH_LOWER_PERM_COPY },
79 { "swap", BE_CH_LOWER_PERM_SWAP },
83 static const lc_opt_enum_mask_items_t dump_items[] = {
84 { "none", BE_CH_DUMP_NONE },
85 { "spill", BE_CH_DUMP_SPILL },
86 { "live", BE_CH_DUMP_LIVE },
87 { "color", BE_CH_DUMP_COLOR },
88 { "copymin", BE_CH_DUMP_COPYMIN },
89 { "ssadestr", BE_CH_DUMP_SSADESTR },
90 { "tree", BE_CH_DUMP_TREE_INTV },
91 { "split", BE_CH_DUMP_SPLIT },
92 { "constr", BE_CH_DUMP_CONSTR },
93 { "lower", BE_CH_DUMP_LOWER },
94 { "spillslots", BE_CH_DUMP_SPILLSLOTS },
95 { "appel", BE_CH_DUMP_APPEL },
96 { "all", BE_CH_DUMP_ALL },
100 static const lc_opt_enum_int_items_t be_ch_vrfy_items[] = {
101 { "off", BE_CH_VRFY_OFF },
102 { "warn", BE_CH_VRFY_WARN },
103 { "assert", BE_CH_VRFY_ASSERT },
107 static lc_opt_enum_int_var_t lower_perm_var = {
108 &options.lower_perm_opt, lower_perm_items
111 static lc_opt_enum_mask_var_t dump_var = {
112 &options.dump_flags, dump_items
115 static lc_opt_enum_int_var_t be_ch_vrfy_var = {
116 &options.vrfy_option, be_ch_vrfy_items
119 static const lc_opt_table_entry_t be_chordal_options[] = {
120 LC_OPT_ENT_ENUM_INT ("perm", "perm lowering options", &lower_perm_var),
121 LC_OPT_ENT_ENUM_MASK("dump", "select dump phases", &dump_var),
122 LC_OPT_ENT_ENUM_INT ("verify", "verify options", &be_ch_vrfy_var),
126 static be_module_list_entry_t *colorings = NULL;
127 static const be_ra_chordal_coloring_t *selected_coloring = NULL;
129 void be_register_chordal_coloring(const char *name, be_ra_chordal_coloring_t *coloring)
131 if (selected_coloring == NULL)
132 selected_coloring = coloring;
134 be_add_module_to_list(&colorings, name, coloring);
137 static void be_ra_chordal_coloring(be_chordal_env_t *env)
139 selected_coloring->allocate(env);
142 static void dump(unsigned mask, ir_graph *irg,
143 const arch_register_class_t *cls,
146 if ((options.dump_flags & mask) == mask) {
149 snprintf(buf, sizeof(buf), "%s-%s", cls->name, suffix);
150 dump_ir_graph(irg, buf);
152 dump_ir_graph(irg, suffix);
158 * Post-Walker: Checks for the given reload if has only one user that can perform the
159 * reload as part of its address mode.
160 * Fold the reload into the user it that is possible.
162 static void memory_operand_walker(ir_node *irn, void *env)
169 if (! be_is_Reload(irn))
172 /* only use memory operands, if the reload is only used by 1 node */
173 if (get_irn_n_edges(irn) > 1)
176 spill = be_get_Reload_mem(irn);
177 block = get_nodes_block(irn);
179 foreach_out_edge_safe(irn, edge) {
180 ir_node *src = get_edge_src_irn(edge);
181 int pos = get_edge_src_pos(edge);
183 assert(src && "outedges broken!");
185 if (get_nodes_block(src) == block && arch_possible_memory_operand(src, pos)) {
186 arch_perform_memory_operand(src, spill, pos);
190 /* kill the Reload if it was folded */
191 if (get_irn_n_edges(irn) == 0) {
192 ir_graph *irg = get_irn_irg(irn);
193 ir_mode *frame_mode = get_irn_mode(get_irn_n(irn, n_be_Reload_frame));
195 set_irn_n(irn, n_be_Reload_mem, new_r_Bad(irg, mode_X));
196 set_irn_n(irn, n_be_Reload_frame, new_r_Bad(irg, frame_mode));
201 * Starts a walk for memory operands if supported by the backend.
203 void check_for_memory_operands(ir_graph *irg)
205 irg_walk_graph(irg, NULL, memory_operand_walker, NULL);
209 static be_node_stats_t last_node_stats;
212 * Perform things which need to be done per register class before spilling.
214 static void pre_spill(be_chordal_env_t *const chordal_env, arch_register_class_t const *const cls, ir_graph *const irg)
216 chordal_env->cls = cls;
217 chordal_env->border_heads = pmap_create();
218 chordal_env->allocatable_regs = bitset_malloc(cls->n_regs);
220 be_assure_live_chk(irg);
222 /* put all ignore registers into the ignore register set. */
223 be_put_allocatable_regs(irg, cls, chordal_env->allocatable_regs);
225 be_timer_push(T_RA_CONSTR);
226 be_pre_spill_prepare_constr(irg, cls);
227 be_timer_pop(T_RA_CONSTR);
229 dump(BE_CH_DUMP_CONSTR, irg, cls, "constr-pre");
233 * Perform things which need to be done per register class after spilling.
235 static void post_spill(be_chordal_env_t *const chordal_env, ir_graph *const irg)
237 /* some special classes contain only ignore regs, no work to be done */
238 int const allocatable_regs = be_get_n_allocatable_regs(irg, chordal_env->cls);
239 if (allocatable_regs > 0) {
241 If we have a backend provided spiller, post spill is
242 called in a loop after spilling for each register class.
243 But we only need to fix stack nodes once in this case.
245 be_timer_push(T_RA_SPILL_APPLY);
246 check_for_memory_operands(irg);
247 be_abi_fix_stack_nodes(irg);
248 be_timer_pop(T_RA_SPILL_APPLY);
251 /* verify schedule and register pressure */
252 be_timer_push(T_VERIFY);
253 if (chordal_env->opts->vrfy_option == BE_CH_VRFY_WARN) {
254 be_verify_schedule(irg);
255 be_verify_register_pressure(irg, chordal_env->cls);
256 } else if (chordal_env->opts->vrfy_option == BE_CH_VRFY_ASSERT) {
257 assert(be_verify_schedule(irg) && "Schedule verification failed");
258 assert(be_verify_register_pressure(irg, chordal_env->cls)
259 && "Register pressure verification failed");
261 be_timer_pop(T_VERIFY);
263 /* Color the graph. */
264 be_timer_push(T_RA_COLOR);
265 be_ra_chordal_coloring(chordal_env);
266 be_timer_pop(T_RA_COLOR);
268 dump(BE_CH_DUMP_CONSTR, irg, chordal_env->cls, "color");
270 /* Create the ifg with the selected flavor */
271 be_timer_push(T_RA_IFG);
272 chordal_env->ifg = be_create_ifg(chordal_env);
273 be_timer_pop(T_RA_IFG);
275 if (stat_ev_enabled) {
277 be_node_stats_t node_stats;
279 be_ifg_stat(irg, chordal_env->ifg, &stat);
280 stat_ev_dbl("bechordal_ifg_nodes", stat.n_nodes);
281 stat_ev_dbl("bechordal_ifg_edges", stat.n_edges);
282 stat_ev_dbl("bechordal_ifg_comps", stat.n_comps);
284 be_collect_node_stats(&node_stats, irg);
285 be_subtract_node_stats(&node_stats, &last_node_stats);
287 stat_ev_dbl("bechordal_perms_before_coal",
288 node_stats[BE_STAT_PERMS]);
289 stat_ev_dbl("bechordal_copies_before_coal",
290 node_stats[BE_STAT_COPIES]);
293 be_timer_push(T_RA_COPYMIN);
294 co_driver(chordal_env);
295 be_timer_pop(T_RA_COPYMIN);
297 dump(BE_CH_DUMP_COPYMIN, irg, chordal_env->cls, "copymin");
299 /* ssa destruction */
300 be_timer_push(T_RA_SSA);
301 be_ssa_destruction(chordal_env);
302 be_timer_pop(T_RA_SSA);
304 dump(BE_CH_DUMP_SSADESTR, irg, chordal_env->cls, "ssadestr");
306 if (chordal_env->opts->vrfy_option != BE_CH_VRFY_OFF) {
307 be_timer_push(T_VERIFY);
308 be_ssa_destruction_check(chordal_env);
309 be_timer_pop(T_VERIFY);
312 /* the ifg exists only if there are allocatable regs */
313 be_ifg_free(chordal_env->ifg);
316 /* free some always allocated data structures */
317 pmap_destroy(chordal_env->border_heads);
318 bitset_free(chordal_env->allocatable_regs);
322 * Performs chordal register allocation for each register class on given irg.
324 * @param irg the graph
325 * @return Structure containing timer for the single phases or NULL if no
328 static void be_ra_chordal_main(ir_graph *irg)
330 const arch_env_t *arch_env = be_get_irg_arch_env(irg);
334 be_timer_push(T_RA_OTHER);
336 be_chordal_env_t chordal_env;
337 obstack_init(&chordal_env.obst);
338 chordal_env.opts = &options;
339 chordal_env.irg = irg;
340 chordal_env.border_heads = NULL;
341 chordal_env.ifg = NULL;
342 chordal_env.allocatable_regs = NULL;
344 if (stat_ev_enabled) {
345 be_collect_node_stats(&last_node_stats, irg);
348 /* use one of the generic spiller */
350 /* Perform the following for each register class. */
351 for (j = 0, m = arch_env->n_register_classes; j < m; ++j) {
352 const arch_register_class_t *cls = &arch_env->register_classes[j];
354 if (arch_register_class_flags(cls) & arch_register_class_flag_manual_ra)
358 stat_ev_ctx_push_str("bechordal_cls", cls->name);
360 double pre_spill_cost = 0;
361 if (stat_ev_enabled) {
362 be_do_stat_reg_pressure(irg, cls);
363 pre_spill_cost = be_estimate_irg_costs(irg);
366 pre_spill(&chordal_env, cls, irg);
368 be_timer_push(T_RA_SPILL);
369 be_do_spill(irg, cls);
370 be_timer_pop(T_RA_SPILL);
372 dump(BE_CH_DUMP_SPILL, irg, cls, "spill");
374 stat_ev_dbl("bechordal_spillcosts", be_estimate_irg_costs(irg) - pre_spill_cost);
376 post_spill(&chordal_env, irg);
378 if (stat_ev_enabled) {
379 be_node_stats_t node_stats;
381 be_collect_node_stats(&node_stats, irg);
382 be_subtract_node_stats(&node_stats, &last_node_stats);
383 be_emit_node_stats(&node_stats, "bechordal_");
385 be_copy_node_stats(&last_node_stats, &node_stats);
386 stat_ev_ctx_pop("bechordal_cls");
390 be_timer_push(T_VERIFY);
391 if (chordal_env.opts->vrfy_option == BE_CH_VRFY_WARN) {
392 be_verify_register_allocation(irg);
393 } else if (chordal_env.opts->vrfy_option == BE_CH_VRFY_ASSERT) {
394 assert(be_verify_register_allocation(irg)
395 && "Register allocation invalid");
397 be_timer_pop(T_VERIFY);
399 be_timer_push(T_RA_EPILOG);
400 lower_nodes_after_ra(irg, options.lower_perm_opt == BE_CH_LOWER_PERM_COPY);
401 dump(BE_CH_DUMP_LOWER, irg, NULL, "belower-after-ra");
403 obstack_free(&chordal_env.obst, NULL);
404 be_invalidate_live_sets(irg);
405 be_timer_pop(T_RA_EPILOG);
407 be_timer_pop(T_RA_OTHER);
410 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal_main)
411 void be_init_chordal_main(void)
413 static be_ra_t be_ra_chordal_allocator = {
417 lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
418 lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
419 lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
421 be_register_allocator("chordal", &be_ra_chordal_allocator);
423 lc_opt_add_table(chordal_grp, be_chordal_options);
424 be_add_module_list_opt(chordal_grp, "coloring", "select coloring method", &colorings, (void**) &selected_coloring);