X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillremat.c;h=2d418f6374c3c7478fec1b7d9f2b95c430bf0787;hb=5cb14f12bacb0c7d1c646112b4660d57e14236a2;hp=b35ae8e1224624767a6dcaec42bde5782c9ca3d7;hpb=8535fe8732b0acf822be252812a7158ce5b8134a;p=libfirm diff --git a/ir/be/bespillremat.c b/ir/be/bespillremat.c index b35ae8e12..2d418f637 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-2008 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,11 +45,13 @@ #include "irnode_t.h" #include "ircons_t.h" #include "irloop_t.h" +#include "irnodeset.h" #include "phiclass.h" -#include "iredges.h" +#include "iredges_t.h" #include "execfreq.h" #include "irvrfy.h" #include "irbackedge_t.h" +#include "irprofile.h" #include #include @@ -41,23 +59,24 @@ #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" #include "bespillremat.h" #include "bespill.h" #include "bepressurestat.h" -#include "beprofile.h" #include "bespilloptions.h" - #include "bechordal_t.h" +#include "bemodule.h" -#include -#include +#include "lc_opts.h" +#include "lc_opts_enum.h" #define DUMP_PROBLEM 1 #define DUMP_MPS 2 @@ -150,7 +169,7 @@ static const lc_opt_table_entry_t options[] = { LC_OPT_ENT_DBL ("cost_memoperand", "cost of a memory operand", &opt_cost_memoperand), LC_OPT_ENT_DBL ("cost_spill", "cost of a spill instruction", &opt_cost_spill), LC_OPT_ENT_DBL ("cost_remat", "cost of a rematerialization", &opt_cost_remat), - { NULL } + LC_OPT_LAST }; //#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */ @@ -285,7 +304,7 @@ static int cmp_remat(const void *a, const void *b) { const remat_t *r = a; - const remat_t *s = a; + const remat_t *s = b; return !(r == s || r->op == s->op); } @@ -295,6 +314,7 @@ cmp_spill(const void *a, const void *b, size_t size) { const spill_t *p = a; const spill_t *q = b; + (void) size; // return !(p->irn == q->irn && p->bb == q->bb); return !(p->irn == q->irn); @@ -305,6 +325,7 @@ cmp_memoperands(const void *a, const void *b, size_t size) { const memoperand_t *p = a; const memoperand_t *q = b; + (void) size; return !(p->irn == q->irn && p->pos == q->pos); } @@ -390,6 +411,7 @@ cmp_remat_info(const void *a, const void *b, size_t size) { const remat_info_t *p = a; const remat_info_t *q = b; + (void) size; return !(p->irn == q->irn); } @@ -399,6 +421,7 @@ cmp_defs(const void *a, const void *b, size_t size) { const defs_t *p = a; const defs_t *q = b; + (void) size; return !(p->value == q->value); } @@ -408,6 +431,7 @@ cmp_keyval(const void *a, const void *b, size_t size) { const keyval_t *p = a; const keyval_t *q = b; + (void) size; return !(p->key == q->key); } @@ -416,11 +440,11 @@ static double execution_frequency(const spill_ilp_t *si, const ir_node * irn) { #define FUDGE 0.001 - if(be_profile_has_data()) - return ((double)be_profile_get_block_execcount(get_block(irn))) + FUDGE; + if(ir_profile_has_data()) + return ((double)ir_profile_get_block_execcount(get_block_const(irn))) + FUDGE; #ifndef EXECFREQ_LOOPDEPH - return get_block_execfreq(si->birg->exec_freq, get_block(irn)) + FUDGE; + return get_block_execfreq(si->birg->exec_freq, get_block_const(irn)) + FUDGE; #else if(is_Block(irn)) return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE; @@ -658,6 +682,7 @@ value_is_defined_before(const spill_ilp_t * si, const ir_node * pos, const ir_no ir_node *block; ir_node *def_block = get_nodes_block(val); int ret; + (void) si; if(val == pos) return 0; @@ -702,6 +727,7 @@ sched_block_first_nonphi(const ir_node * bb) static int sched_skip_proj_predicator(const ir_node * irn, void * data) { + (void) data; return (is_Proj(irn)); } @@ -1588,6 +1614,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 */ @@ -1615,6 +1642,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) @@ -2439,11 +2467,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); @@ -2847,6 +2877,7 @@ cmp_interference(const void *a, const void *b, size_t size) { const interference_t *p = a; const interference_t *q = b; + (void) size; return !(p->a == q->a && p->b == q->b); } @@ -2889,19 +2920,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; @@ -2910,15 +2941,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; } @@ -3216,9 +3247,13 @@ is_zero(double x) return fabs(x) < 0.00001; } +/** + * node attribute hook for changing colors + */ static int mark_remat_nodes_hook(FILE *F, ir_node *n, ir_node *l) { spill_ilp_t *si = get_irg_link(current_ir_graph); + (void) l; if(pset_find_ptr(si->all_possible_remats, n)) { op_t *op = (op_t*)get_irn_link(n); @@ -3569,7 +3604,7 @@ new_r_PhiM_nokeep(ir_graph * irg, ir_node *block, int arity, ir_node **in) assert( get_irn_arity(block) == arity ); res = new_ir_node(NULL, irg, block, op_Phi, mode_M, arity, in); - res->attr.phi_backedge = new_backedge_arr(irg->obst, arity); + res->attr.phi.u.backedge = new_backedge_arr(irg->obst, arity); return res; } @@ -4126,10 +4161,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) { @@ -4152,11 +4187,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); @@ -4165,29 +4214,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) { + be_ssa_construction_add_copy(&senv, (ir_node*) next); + next = get_irn_link(next); + } + + if(sched_is_scheduled(defs->value)) { + be_ssa_construction_fix_users(&senv, (ir_node*) defs->value); + } + + next = defs->remats; while(next) { - pset_insert_ptr(nodes, next); + be_ssa_construction_fix_users(&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); + 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); + } - del_pset(nodes); + be_ssa_construction_destroy(&senv); } } + ir_nodeset_destroy(&ignore); // remove_unused_defs(si); } @@ -4549,8 +4620,8 @@ BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillremat); #else /* WITH_ILP */ -static void INLINE -only_that_you_can_compile_without_WITH_ILP_defined(void) +static __attribute__((unused)) +void only_that_you_can_compile_without_WITH_ILP_defined(void) { }