From 92aa0dde95766e4022880f208fee9d6cc4f016ac Mon Sep 17 00:00:00 2001 From: Adam Szalkowski Date: Sat, 29 Jul 2006 09:19:34 +0000 Subject: [PATCH] added spill cost estimation --- ir/be/Makefile.in | 3 +- ir/be/bearch.h | 2 + ir/be/bechordal_main.c | 7 +++ ir/be/bespillcost.c | 130 +++++++++++++++++++++++++++++++++++++++ ir/be/bespillcost.h | 6 ++ ir/be/ia32/bearch_ia32.c | 4 ++ 6 files changed, 151 insertions(+), 1 deletion(-) create mode 100644 ir/be/bespillcost.c create mode 100644 ir/be/bespillcost.h diff --git a/ir/be/Makefile.in b/ir/be/Makefile.in index 7e4922d01..33545ae43 100644 --- a/ir/be/Makefile.in +++ b/ir/be/Makefile.in @@ -32,7 +32,8 @@ SOURCES += Makefile.in besched.h belistsched.h belistsched.c \ bemachnode.c bemachnode.h beinsn.c bestat.h bestat.c \ beschedmris.h beschedmris.c bespillmorgan.c bespillmorgan.h \ beverify.h beverify.c bespillremat.c bepressurestat.c bepressurestat.h \ - bessadestrsimple.c beifg_clique.c beifg_list.c beifg_pointer.c + bessadestrsimple.c beifg_clique.c beifg_list.c beifg_pointer.c \ + bespillcost.c diff --git a/ir/be/bearch.h b/ir/be/bearch.h index dbc29412a..6da6382cc 100644 --- a/ir/be/bearch.h +++ b/ir/be/bearch.h @@ -344,6 +344,7 @@ extern void arch_set_frame_offset(const arch_env_t *env, ir_node *irn, int bias) extern entity *arch_get_frame_entity(const arch_env_t *env, ir_node *irn); +extern int arch_get_op_estimated_cost(const arch_env_t *env, const ir_node *irn); extern arch_inverse_t *arch_get_inverse(const arch_env_t *env, const ir_node *irn, int i, arch_inverse_t *inverse, struct obstack *obstack); extern int arch_possible_memory_operand(const arch_env_t *env, const ir_node *irn, unsigned int i); extern void arch_perform_memory_operand(const arch_env_t *env, ir_node *irn, ir_node *reload, unsigned int i); @@ -713,4 +714,5 @@ extern arch_env_t *arch_env_push_irn_handler(arch_env_t *env, const arch_irn_han */ extern const arch_irn_handler_t *arch_env_pop_irn_handler(arch_env_t *env); + #endif /* _FIRM_BEARCH_H */ diff --git a/ir/be/bechordal_main.c b/ir/be/bechordal_main.c index d09fa76a6..190946d2a 100644 --- a/ir/be/bechordal_main.c +++ b/ir/be/bechordal_main.c @@ -60,6 +60,7 @@ #include "becopyopt.h" #include "bessadestr.h" #include "beverify.h" +#include "bespillcost.h" void be_ra_chordal_check(be_chordal_env_t *chordal_env) { const arch_env_t *arch_env = chordal_env->birg->main_env->arch_env; @@ -479,6 +480,12 @@ static be_ra_timer_t *be_ra_chordal_main(const be_irg_t *bi) BE_TIMER_POP(ra_timer.t_spill); + DBG((chordal_env.dbg, LEVEL_1, "spill costs for %+F in regclass %s: %g\n", + irg, + chordal_env.cls->name, + get_irg_spill_cost(&chordal_env)) + ); + dump(BE_CH_DUMP_SPILL, irg, chordal_env.cls, "-spill", dump_ir_block_graph_sched); be_abi_fix_stack_nodes(bi->abi); be_compute_spill_offsets(&chordal_env); diff --git a/ir/be/bespillcost.c b/ir/be/bespillcost.c new file mode 100644 index 000000000..09e5e12d0 --- /dev/null +++ b/ir/be/bespillcost.c @@ -0,0 +1,130 @@ +/** vim: set sw=4 ts=4: + * @file bespillcost.c + * @date 2006-06-28 + * @author Adam M. Szalkowski + * + * Spill cost estimation + * + * Copyright (C) 2006 Universitaet Karlsruhe + * Released under the GPL + */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include + +#include "hashptr.h" +#include "debug.h" +#include "obst.h" +#include "set.h" +#include "list.h" +#include "pmap.h" + +#include "irprintf.h" +#include "irgwalk.h" +#include "irdump_t.h" +#include "irnode_t.h" +#include "ircons_t.h" +#include "irloop_t.h" +#include "phiclass_t.h" +#include "iredges.h" +#include "execfreq.h" +#include "irvrfy.h" + +#include +#include +#include +//#include +#include + +#include "be_t.h" +#include "belive_t.h" +#include "besched_t.h" +#include "beirgmod.h" +#include "bearch.h" +#include "benode_t.h" +#include "beutil.h" +#include "bespillremat.h" +#include "bespill.h" +#include "bepressurestat.h" + +#include "bechordal_t.h" + +#define BIGM 100000.0 + +#define COST_LOAD 8 +#define COST_STORE 50 +#define COST_REMAT 1 + +typedef struct _spill_cost_t { + const be_chordal_env_t *chordal_env; + double cost; + DEBUG_ONLY(firm_dbg_module_t *dbg); +} spill_cost_t; + +static double +execution_frequency(const be_chordal_env_t * chordal_env, const ir_node * irn) +{ +#define FUDGE 0.001 +#ifndef EXECFREQ_LOOPDEPH + return get_block_execfreq(chordal_env->exec_freq, get_block(irn)) + FUDGE; +#else + if(is_Block(irn)) + return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE; + else + return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE; +#endif +} + + +static double +get_cost(const be_chordal_env_t * chordal_env, const ir_node * irn) +{ + if(be_is_Spill(irn)) { + return COST_STORE; + } else if(be_is_Reload(irn)){ + return COST_LOAD; + } else { + return arch_get_op_estimated_cost(chordal_env->birg->main_env->arch_env, irn); + } +} + + +static void +walker_cost_collector(ir_node * irn, void * data) +{ + spill_cost_t *sc = data; + double freq, cost; + + if( (be_is_Reload(irn) && chordal_has_class(sc->chordal_env, irn)) || + (be_is_Spill(irn) && chordal_has_class(sc->chordal_env, get_irn_n(irn,1)))) { + + freq = execution_frequency(sc->chordal_env, irn); + cost = get_cost(sc->chordal_env, irn); + + DBG((sc->dbg, LEVEL_2, "%+F has cost %g with execfreq %g ->\t %g\n", irn, cost, freq, cost*freq)); + + sc->cost += cost*freq; + } +} + +double +get_irg_spill_cost(const be_chordal_env_t * chordal_env) +{ + spill_cost_t sc; + char problem_name[256]; + + ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name); + + sc.cost = 0.0; + sc.chordal_env = chordal_env; + FIRM_DBG_REGISTER(sc.dbg, "firm.be.ra.spillcost"); + + DBG((sc.dbg, LEVEL_2, "computing spill costs for %s\n", problem_name)); + irg_walk_graph(chordal_env->irg, walker_cost_collector, NULL, &sc); + DBG((sc.dbg, LEVEL_1, "spill costs for %s: %g\n", problem_name, sc.cost)); + DBG((sc.dbg, LEVEL_2, "\n")); + + return sc.cost; +} diff --git a/ir/be/bespillcost.h b/ir/be/bespillcost.h new file mode 100644 index 000000000..5c8e62cf5 --- /dev/null +++ b/ir/be/bespillcost.h @@ -0,0 +1,6 @@ +#ifndef BESPILLCOST_H_ +#define BESPILLCOST_H_ + +double get_irg_spill_cost(const be_chordal_env_t * chordal_env); + +#endif diff --git a/ir/be/ia32/bearch_ia32.c b/ir/be/ia32/bearch_ia32.c index 06d6d05a0..ccf857757 100644 --- a/ir/be/ia32/bearch_ia32.c +++ b/ir/be/ia32/bearch_ia32.c @@ -473,6 +473,10 @@ static ir_type *ia32_abi_get_between_type(void *self) static int ia32_get_op_estimated_cost(const void *self, const ir_node *irn) { int cost; + + if(is_Proj(irn)) + return 0; + switch (get_ia32_irn_opcode(irn)) { case iro_ia32_xDiv: case iro_ia32_DivMod: -- 2.20.1