X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=5aa573b89da0f3931c6e277c217391765b566de5;hb=9276447aec4972df060349e162f583c4898dfec8;hp=c02b51e3020ed03343300d771f2e5642941dc27f;hpb=9731bb6ea18b90d4b82dfe89e017b093cee14dac;p=libfirm diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c index c02b51e30..5aa573b89 100644 --- a/ir/be/bespillremat.c +++ b/ir/be/bespillremat.c @@ -1,12 +1,28 @@ -/** vim: set sw=4 ts=4: - * @file bespillremat.c - * @date 2006-04-06 - * @author Adam M. Szalkowski & Sebastian Hack +/* + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. * - * ILP based spilling & rematerialization + * This file is part of libFirm. * - * Copyright (C) 2006 Universitaet Karlsruhe - * Released under the GPL + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief ILP based spilling & rematerialization + * @author Adam M. Szalkowski + * @date 06.04.2006 + * @version $Id$ */ #ifdef HAVE_CONFIG_H #include "config.h" @@ -29,8 +45,9 @@ #include "irnode_t.h" #include "ircons_t.h" #include "irloop_t.h" -#include "phiclass_t.h" -#include "iredges.h" +#include "irnodeset.h" +#include "phiclass.h" +#include "iredges_t.h" #include "execfreq.h" #include "irvrfy.h" #include "irbackedge_t.h" @@ -39,14 +56,14 @@ #include #include #include -//#include -//#include #include "be_t.h" +#include "beirg_t.h" #include "belive_t.h" #include "besched_t.h" -#include "beirgmod.h" -#include "bearch.h" +#include "bessaconstr.h" +#include "bearch_t.h" +#include "beintlive_t.h" #include "beabi.h" #include "benode_t.h" #include "beutil.h" @@ -55,13 +72,11 @@ #include "bepressurestat.h" #include "beprofile.h" #include "bespilloptions.h" - #include "bechordal_t.h" +#include "bemodule.h" -#ifdef WITH_LIBCORE #include #include -#endif /* WITH_LIBCORE */ #define DUMP_PROBLEM 1 #define DUMP_MPS 2 @@ -81,14 +96,14 @@ #define REMATS_NOINVERSE 2 #define REMATS_ALL 3 -static int opt_dump_flags = 0; +static unsigned opt_dump_flags = 0; static int opt_log = 0; -static int opt_keep_alive = 0; +static unsigned opt_keep_alive = 0; static int opt_goodwin = 1; static int opt_memcopies = 1; static int opt_memoperands = 1; static int opt_verify = VERIFY_MEMINTERF; -static int opt_remats = REMATS_ALL; +static unsigned opt_remats = REMATS_ALL; static int opt_repair_schedule = 0; static int opt_no_enlarge_liveness = 0; static int opt_remat_while_live = 1; @@ -99,7 +114,6 @@ static double opt_cost_spill = 15.0; static double opt_cost_remat = 1.0; -#ifdef WITH_LIBCORE static const lc_opt_enum_mask_items_t dump_items[] = { { "problem", DUMP_PROBLEM }, { "mps", DUMP_MPS }, @@ -158,9 +172,6 @@ static const lc_opt_table_entry_t options[] = { { NULL } }; -#endif - - //#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */ //#define SCHEDULE_PHIM /* insert phim nodes into schedule */ @@ -189,6 +200,7 @@ typedef struct _spill_ilp_t { set *interferences; ir_node *m_unknown; set *memoperands; + phi_classes_t *pc; #ifndef SCHEDULE_PHIM pset *phims; #endif @@ -917,7 +929,7 @@ insert_copy_before(const spill_ilp_t * si, const ir_node * irn, ir_node * pos) bb = is_Block(pos)?pos:get_nodes_block(pos); copy = exact_copy(irn); - _set_phi_class(copy, NULL); + set_phi_class(si->pc, copy, NULL); set_nodes_block(copy, bb); sched_put_before(si, pos, copy); @@ -936,7 +948,7 @@ insert_copy_after(const spill_ilp_t * si, const ir_node * irn, ir_node * pos) bb = is_Block(pos)?pos:get_nodes_block(pos); copy = exact_copy(irn); - _set_phi_class(copy, NULL); + set_phi_class(si->pc, copy, NULL); set_nodes_block(copy, bb); sched_put_after(pos, copy); @@ -1595,6 +1607,7 @@ luke_endwalker(ir_node * bb, void * data) del_pset(use_end); } +#ifndef NDEBUG /** * Find a remat of value @p value in the epilog of @p pos */ @@ -1622,6 +1635,7 @@ find_post_remat(const ir_node * value, const ir_node * pos) return NULL; } +#endif static spill_t * add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn) @@ -1916,7 +1930,7 @@ luke_blockwalker(ir_node * bb, void * data) pset *used; pset *remat_defs; keyval_t *keyval; - ilp_cst_t one_memoperand; + ilp_cst_t one_memoperand = -1; /* iterate only until first phi */ if(is_Phi(irn)) @@ -2446,11 +2460,13 @@ skip_one_must_die: assert(has_reg_class(si, tmp)); } +#ifndef NDEBUG for (n=get_irn_arity(irn)-1; n>=0; --n) { ir_node *arg = get_irn_n(irn, n); assert(!find_post_remat(arg, irn) && "there should be no post remat for an argument of an op"); } +#endif del_pset(remat_defs); del_pset(used); @@ -2896,19 +2912,19 @@ set_insert_interference(spill_ilp_t * si, set * set, ir_node * a, ir_node * b, i return result; } -static int -values_interfere_in_block(const spill_ilp_t * si, const ir_node * bb, const ir_node * a, const ir_node * b) +static +int values_interfere_in_block(const spill_ilp_t *si, const ir_node *bb, const ir_node *a, const ir_node *b) { const ir_edge_t *edge; - if(get_nodes_block(a) != bb && get_nodes_block(b) != bb) { + if (get_nodes_block(a) != bb && get_nodes_block(b) != bb) { /* both values are live in, so they interfere */ return 1; } /* ensure a dominates b */ - if(value_dominates(b,a)) { - const ir_node * t; + if (value_dominates(b, a)) { + const ir_node *t; t = b; b = a; a = t; @@ -2917,15 +2933,15 @@ values_interfere_in_block(const spill_ilp_t * si, const ir_node * bb, const ir_n /* the following code is stolen from bera.c */ - if(be_is_live_end(si->lv, bb, a)) + if (be_is_live_end(si->lv, bb, a)) return 1; foreach_out_edge(a, edge) { const ir_node *user = edge->src; - if(get_nodes_block(user) == bb - && !is_Phi(user) + if (get_nodes_block(user) == bb + && ! is_Phi(user) && b != user - && !pset_find_ptr(si->inverse_ops, user) + && ! pset_find_ptr(si->inverse_ops, user) && value_dominates(b, user)) return 1; } @@ -2948,21 +2964,20 @@ luke_interferencewalker(ir_node * bb, void * data) /* a is only interesting if it is in my register class and if it is inside a phi class */ - if (has_reg_class(si, a) && get_phi_class(a)) { - if(a_op->is_remat || pset_find_ptr(si->inverse_ops, a)) + if (has_reg_class(si, a) && get_phi_class(si->pc, a)) { + if (a_op->is_remat || pset_find_ptr(si->inverse_ops, a)) continue; - for(l2=_be_lv_next_irn(si->lv, bb, 0xff, l1+1); l2>=0; l2=_be_lv_next_irn(si->lv, bb, 0xff, l2+1)) { - ir_node *b = be_lv_get_irn(si->lv, bb, l2); - op_t *b_op = get_irn_link(b); - + for (l2 = _be_lv_next_irn(si->lv, bb, 0xff, l1 + 1); l2 >= 0; l2 = _be_lv_next_irn(si->lv, bb, 0xff, l2 + 1)) { + ir_node *b = be_lv_get_irn(si->lv, bb, l2); + op_t *b_op = get_irn_link(b); /* a and b are only interesting if they are in the same phi class */ - if(has_reg_class(si, b) && get_phi_class(a) == get_phi_class(b)) { - if(b_op->is_remat || pset_find_ptr(si->inverse_ops, b)) + if (has_reg_class(si, b) && get_phi_class(si->pc, a) == get_phi_class(si->pc, b)) { + if (b_op->is_remat || pset_find_ptr(si->inverse_ops, b)) continue; - if(values_interfere_in_block(si, bb, a, b)) { + if (values_interfere_in_block(si, bb, a, b)) { DBG((si->dbg, LEVEL_4, "\tvalues interfere in %+F: %+F, %+F\n", bb, a, b)); set_insert_interference(si, si->interferences, a, b, bb); } @@ -3140,26 +3155,21 @@ memcopyhandler(spill_ilp_t * si) char buf[256]; /* teste Speicherwerte auf Interferenz */ - /* analyze phi classes */ - phi_class_compute(si->birg->irg); - DBG((si->dbg, LEVEL_2, "\t calling interferencewalker\n")); irg_block_walk_graph(si->birg->irg, luke_interferencewalker, NULL, si); /* now lets emit the ILP unequations for the crap */ set_foreach(si->interferences, interference) { irnlist_t *irnlist; - ilp_var_t interfere, - any_interfere; - ilp_cst_t any_interfere_cst, - cst; + ilp_var_t interfere, any_interfere; + ilp_cst_t any_interfere_cst, cst; const ir_node *a = interference->a; const ir_node *b = interference->b; /* any_interf <= \sum interf */ ir_snprintf(buf, sizeof(buf), "interfere_%N_%N", a, b); any_interfere_cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0); - any_interfere = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); + any_interfere = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0); lpp_set_factor_fast(si->lpp, any_interfere_cst, any_interfere, 1.0); @@ -3402,14 +3412,15 @@ connect_all_spills_with_keep(spill_ilp_t * si) /** insert a spill at an arbitrary position */ ir_node *be_spill2(const arch_env_t *arch_env, ir_node *irn, ir_node *insert) { - ir_node *bl = is_Block(insert)?insert:get_nodes_block(insert); + ir_node *bl = is_Block(insert) ? insert : get_nodes_block(insert); ir_graph *irg = get_irn_irg(bl); ir_node *frame = get_irg_frame(irg); ir_node *spill; ir_node *next; - const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1); + const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1); + const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1); - spill = be_new_Spill(cls, irg, bl, irn); + spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn); /* * search the right insertion point. a spill of a phi cannot be put @@ -4091,39 +4102,42 @@ print_irn_pset(pset * p) } void -dump_phi_class(spill_ilp_t * si, pset * phiclass, const char * file) +dump_phi_class(spill_ilp_t *si, ir_node **phiclass, const char * file) { FILE *f = fopen(file, "w"); ir_node *irn; interference_t *interference; + int i; - pset_break(phiclass); set_break(si->interferences); ir_fprintf(f, "digraph phiclass {\n"); - pset_foreach(phiclass, irn) { - if(is_Phi(irn)) - ir_fprintf(f, " %F%N [shape=box]\n",irn,irn); + for (i = ARR_LEN(phiclass) - 1; i >= 0; --i) { + irn = phiclass[i]; + if (is_Phi(irn)) + ir_fprintf(f, " %F%N [shape=box]\n", irn, irn); } - pset_foreach(phiclass, irn) { + for (i = ARR_LEN(phiclass) - 1; i >= 0; --i) { int n; - if(!is_Phi(irn)) continue; + irn = phiclass[i]; + if (! is_Phi(irn)) + continue; - for(n=get_irn_arity(irn)-1; n>=0; --n) { + for (n = get_irn_arity(irn) - 1; n >= 0; --n) { ir_node *arg = get_irn_n(irn, n); - ir_fprintf(f, " %F%N -> %F%N\n",irn,irn,arg,arg); + ir_fprintf(f, " %F%N -> %F%N\n", irn, irn, arg, arg); } } set_foreach(si->interferences, interference) { - const ir_node *a = interference->a; - const ir_node *b = interference->b; - if(get_phi_class(a) == phiclass) { - ir_fprintf(f, " %F%N -> %F%N [color=red,dir=none,style=bold]\n",a,a,b,b); + const ir_node *a = interference->a; + const ir_node *b = interference->b; + if (get_phi_class(si->pc, (ir_node *)a) == phiclass) { + ir_fprintf(f, " %F%N -> %F%N [color=red,dir=none,style=bold]\n", a, a, b, b); } } @@ -4135,10 +4149,10 @@ static void rewire_uses(spill_ilp_t * si) { defs_t *defs; - pset *ignore = pset_new_ptr(1); - be_dom_front_info_t *dom_front = si->birg->dom_front; + ir_nodeset_t ignore; - pset_insert_ptr(ignore, get_irg_end(si->birg->irg)); + ir_nodeset_init(&ignore); + ir_nodeset_insert(&ignore, get_irg_end(si->birg->irg)); /* then fix uses of spills */ set_foreach(si->values, defs) { @@ -4161,11 +4175,25 @@ rewire_uses(spill_ilp_t * si) spills = get_spills_for_value(si, defs->value); DBG((si->dbg, LEVEL_2, "\t %d remats, %d reloads, and %d spills for value %+F\n", remats, pset_count(reloads), pset_count(spills), defs->value)); if(pset_count(spills) > 1) { + be_ssa_construction_env_t senv; + ir_node *node; //assert(pset_count(reloads) > 0); // print_irn_pset(spills); // print_irn_pset(reloads); - be_ssa_constr_set_ignore(dom_front, si->lv, spills, ignore); + be_ssa_construction_init(&senv, si->birg); + be_ssa_construction_set_ignore_uses(&senv, &ignore); + pset_foreach(spills, node) { + be_ssa_construction_add_copy(&senv, node); + } + pset_foreach(spills, node) { + be_ssa_construction_fix_users(&senv, node); + } + be_ssa_construction_update_liveness_phis(&senv, si->lv); + pset_foreach(spills, node) { + be_liveness_update(si->lv, node); + } + be_ssa_construction_destroy(&senv); } del_pset(reloads); @@ -4174,29 +4202,51 @@ rewire_uses(spill_ilp_t * si) /* first fix uses of remats and reloads */ set_foreach(si->values, defs) { - pset *nodes; const ir_node *next = defs->remats; int orig_kept = 0; if(next) { - nodes = pset_new_ptr_default(); + be_ssa_construction_env_t senv; + + be_ssa_construction_init(&senv, si->birg); + if(sched_is_scheduled(defs->value)) { - pset_insert_ptr(nodes, defs->value); + be_ssa_construction_add_copy(&senv, (ir_node*) defs->value); orig_kept = 1; } + next = defs->remats; while(next) { - pset_insert_ptr(nodes, next); + be_ssa_construction_add_copy(&senv, (ir_node*) next); next = get_irn_link(next); } - DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-orig_kept, defs->value)); - be_ssa_constr_set(dom_front, si->lv, nodes); + if(sched_is_scheduled(defs->value)) { + be_ssa_construction_fix_users(&senv, (ir_node*) defs->value); + } - del_pset(nodes); + next = defs->remats; + while(next) { + be_ssa_construction_fix_users(&senv, (ir_node*) next); + next = get_irn_link(next); + } + + be_ssa_construction_update_liveness_phis(&senv, si->lv); + if(sched_is_scheduled(defs->value)) { + be_liveness_update(si->lv, (ir_node*) defs->value); + } + + next = defs->remats; + while(next) { + be_liveness_update(si->lv, (ir_node*) next); + next = get_irn_link(next); + } + + be_ssa_construction_destroy(&senv); } } + ir_nodeset_destroy(&ignore); // remove_unused_defs(si); } @@ -4303,24 +4353,26 @@ move_reloads_upward(spill_ilp_t * si) static void luke_meminterferencechecker(ir_node * bb, void * data) { - spill_ilp_t *si = (spill_ilp_t*)data; - int l1, l2; + spill_ilp_t *si = (spill_ilp_t*)data; + int l1, l2; be_lv_foreach(si->lv, bb, be_lv_state_end | be_lv_state_out | be_lv_state_in, l1) { ir_node *a = be_lv_get_irn(si->lv, bb, l1); - if(!be_is_Spill(a) && (!is_Phi(a) || get_irn_mode(a) != mode_T)) continue; + if (! be_is_Spill(a) && (!is_Phi(a) || get_irn_mode(a) != mode_T)) + continue; /* a is only interesting if it is in my register class and if it is inside a phi class */ - if (has_reg_class(si, a) && get_phi_class(a)) { - for(l2=_be_lv_next_irn(si->lv, bb, 0xff, l1+1); l2>=0; l2=_be_lv_next_irn(si->lv, bb, 0xff, l2+1)) { - ir_node *b = be_lv_get_irn(si->lv, bb, l2); + if (has_reg_class(si, a) && get_phi_class(si->pc, a)) { + for (l2 = _be_lv_next_irn(si->lv, bb, 0xff, l1 + 1); l2 >= 0; l2 = _be_lv_next_irn(si->lv, bb, 0xff, l2 + 1)) { + ir_node *b = be_lv_get_irn(si->lv, bb, l2); - if(!be_is_Spill(b) && (!is_Phi(b) || get_irn_mode(b) != mode_T)) continue; + if (! be_is_Spill(b) && (! is_Phi(b) || get_irn_mode(b) != mode_T)) + continue; /* a and b are only interesting if they are in the same phi class */ - if(has_reg_class(si, b) && get_phi_class(a) == get_phi_class(b)) { - if(values_interfere_in_block(si, bb, a, b)) { + if (has_reg_class(si, b) && get_phi_class(si->pc, a) == get_phi_class(si->pc, b)) { + if (values_interfere_in_block(si, bb, a, b)) { ir_fprintf(stderr, "$$ Spills interfere in %+F: %+F, %+F \t$$\n", bb, a, b); } } @@ -4333,7 +4385,8 @@ static void verify_phiclasses(spill_ilp_t * si) { /* analyze phi classes */ - phi_class_compute(si->birg->irg); + phi_class_free(si->pc); + si->pc = phi_class_new_from_irg(si->birg->irg, 0); DBG((si->dbg, LEVEL_2, "\t calling memory interference checker\n")); irg_block_walk_graph(si->birg->irg, luke_meminterferencechecker, NULL, si); @@ -4364,19 +4417,19 @@ be_spill_remat(be_irg_t *birg, const arch_register_class_t *cls) be_assure_liveness(birg); obstack_init(&obst); - si.obst = &obst; - si.birg = birg; - si.cls = cls; - si.lpp = new_lpp(problem_name, lpp_minimize); - si.remat_info = new_set(cmp_remat_info, 4096); - si.interferences = new_set(cmp_interference, 32); - si.memoperands = new_set(cmp_memoperands, 128); + si.obst = &obst; + si.birg = birg; + si.cls = cls; + si.lpp = new_lpp(problem_name, lpp_minimize); + si.remat_info = new_set(cmp_remat_info, 4096); + si.interferences = new_set(cmp_interference, 32); + si.memoperands = new_set(cmp_memoperands, 128); si.all_possible_remats = pset_new_ptr_default(); - si.spills = pset_new_ptr_default(); - si.inverse_ops = pset_new_ptr_default(); - si.lv = birg->lv; - si.keep = NULL; - si.n_regs = get_n_regs(&si); + si.spills = pset_new_ptr_default(); + si.inverse_ops = pset_new_ptr_default(); + si.lv = birg->lv; + si.keep = NULL; + si.n_regs = get_n_regs(&si); set_irg_link(irg, &si); compute_doms(irg); @@ -4423,12 +4476,13 @@ be_spill_remat(be_irg_t *birg, const arch_register_class_t *cls) DBG((si.dbg, LEVEL_2, "\t blockwalker\n")); irg_block_walk_graph(irg, luke_blockwalker, NULL, &si); - if(opt_memcopies) { + si.pc = phi_class_new_from_irg(birg->irg, 0); + if (opt_memcopies) { DBG((si.dbg, LEVEL_2, "\t memcopyhandler\n")); memcopyhandler(&si); } - if(opt_dump_flags & DUMP_PROBLEM) { + if (opt_dump_flags & DUMP_PROBLEM) { FILE *f; ir_snprintf(buf, sizeof(buf), "%s-spillremat.ilp", problem_name); if ((f = fopen(buf, "wt")) != NULL) { @@ -4437,17 +4491,17 @@ be_spill_remat(be_irg_t *birg, const arch_register_class_t *cls) } } - if(opt_dump_flags & DUMP_MPS) { + if (opt_dump_flags & DUMP_MPS) { FILE *f; ir_snprintf(buf, sizeof(buf), "%s-spillremat.mps", problem_name); - if((f = fopen(buf, "wt")) != NULL) { + if ((f = fopen(buf, "wt")) != NULL) { mps_write_mps(si.lpp, s_mps_fixed, f); fclose(f); } ir_snprintf(buf, sizeof(buf), "%s-spillremat.mst", problem_name); - if((f = fopen(buf, "wt")) != NULL) { + if ((f = fopen(buf, "wt")) != NULL) { mps_write_mst(si.lpp, s_mps_fixed, f); fclose(f); } @@ -4531,19 +4585,15 @@ be_spill_remat(be_irg_t *birg, const arch_register_class_t *cls) del_set(si.memoperands); del_pset(si.spills); free_lpp(si.lpp); + phi_class_free(si.pc); obstack_free(&obst, NULL); DBG((si.dbg, LEVEL_1, "\tdone.\n")); } -static void be_spill_remat_oldinterface(const be_chordal_env_t *cenv) -{ - return be_spill_remat(cenv->birg, cenv->cls); -} - void be_init_spillremat(void) { static be_spiller_t remat_spiller = { - be_spill_remat_oldinterface + be_spill_remat }; lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");