nsz Git - libfirm/blob - ir/be/bespillcost.c

   1 /** vim: set sw=4 ts=4:
   2  * @file   bespillcost.c
   3  * @date   2006-06-28
   4  * @author Adam M. Szalkowski
   5  *
   6  * Spill cost estimation
   7  *
   8  * Copyright (C) 2006 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #include <math.h>
  16
  17 #include "hashptr.h"
  18 #include "debug.h"
  19 #include "obst.h"
  20 #include "set.h"
  21 #include "list.h"
  22 #include "pmap.h"
  23
  24 #include "irprintf.h"
  25 #include "irgwalk.h"
  26 #include "irdump_t.h"
  27 #include "irnode_t.h"
  28 #include "ircons_t.h"
  29 #include "irloop_t.h"
  30 #include "phiclass_t.h"
  31 #include "iredges.h"
  32 #include "execfreq.h"
  33 #include "irvrfy.h"
  34
  35 #include <libcore/lc_bitset.h>
  36
  37 #include "be_t.h"
  38 #include "belive_t.h"
  39 #include "besched_t.h"
  40 #include "beirgmod.h"
  41 #include "bearch.h"
  42 #include "benode_t.h"
  43 #include "beutil.h"
  44 #include "bespillremat.h"
  45 #include "bespill.h"
  46 #include "bepressurestat.h"
  47
  48 #include "bechordal_t.h"
  49
  50 #define BIGM 100000.0
  51
  52 #define COST_LOAD      8
  53 #define COST_STORE     50
  54 #define COST_REMAT     1
  55
  56 typedef struct _spill_cost_t {
  57         const be_chordal_env_t       *chordal_env;
  58         double                        cost;
  59         DEBUG_ONLY(firm_dbg_module_t *dbg);
  60 } spill_cost_t;
  61
  62 static double
  63 execution_frequency(const be_chordal_env_t * chordal_env, const ir_node * irn)
  64 {
  65 #define FUDGE 0.001
  66 #ifndef EXECFREQ_LOOPDEPH
  67         return get_block_execfreq(chordal_env->exec_freq, get_block(irn)) + FUDGE;
  68 #else
  69         if(is_Block(irn))
  70                 return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
  71         else
  72                 return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE;
  73 #endif
  74 }
  75
  76
  77 static double
  78 get_cost(const be_chordal_env_t * chordal_env, const ir_node * irn)
  79 {
  80         if(be_is_Spill(irn)) {
  81                 return COST_STORE;
  82         } else if(be_is_Reload(irn)){
  83                 return COST_LOAD;
  84         } else {
  85                 return arch_get_op_estimated_cost(chordal_env->birg->main_env->arch_env, irn);
  86         }
  87 }
  88
  89
  90 static void
  91 walker_cost_collector(ir_node * irn, void * data)
  92 {
  93         spill_cost_t   *sc = data;
  94         double          freq, cost;
  95
  96         if( (be_is_Reload(irn) && chordal_has_class(sc->chordal_env, irn))  ||
  97             (be_is_Spill(irn) && chordal_has_class(sc->chordal_env, get_irn_n(irn,1)))) {
  98
  99                 freq = execution_frequency(sc->chordal_env, irn);
 100                 cost = get_cost(sc->chordal_env, irn);
 101
 102                 DBG((sc->dbg, LEVEL_2, "%+F has cost %g with execfreq %g ->\t %g\n", irn, cost, freq, cost*freq));
 103
 104                 sc->cost += cost*freq;
 105         }
 106 }
 107
 108 double
 109 get_irg_spill_cost(const be_chordal_env_t * chordal_env)
 110 {
 111         spill_cost_t   sc;
 112         char           problem_name[256];
 113
 114         ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name);
 115
 116         sc.cost = 0.0;
 117         sc.chordal_env = chordal_env;
 118         FIRM_DBG_REGISTER(sc.dbg, "firm.be.ra.spillcost");
 119
 120         DBG((sc.dbg, LEVEL_2, "computing spill costs for %s\n", problem_name));
 121         irg_walk_graph(chordal_env->irg, walker_cost_collector, NULL, &sc);
 122         DBG((sc.dbg, LEVEL_1, "spill costs for %s: %g\n", problem_name, sc.cost));
 123         DBG((sc.dbg, LEVEL_2, "\n"));
 124
 125         return sc.cost;
 126 }