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 <lpp/lpp.h>
  36 #include <lpp/lpp_net.h>
  37 #include <lpp/lpp_cplex.h>
  38 //#include <lc_pset.h>
  39 #include <libcore/lc_bitset.h>
  40
  41 #include "be_t.h"
  42 #include "belive_t.h"
  43 #include "besched_t.h"
  44 #include "beirgmod.h"
  45 #include "bearch.h"
  46 #include "benode_t.h"
  47 #include "beutil.h"
  48 #include "bespillremat.h"
  49 #include "bespill.h"
  50 #include "bepressurestat.h"
  51
  52 #include "bechordal_t.h"
  53
  54 #define BIGM 100000.0
  55
  56 #define COST_LOAD      8
  57 #define COST_STORE     50
  58 #define COST_REMAT     1
  59
  60 typedef struct _spill_cost_t {
  61         const be_chordal_env_t       *chordal_env;
  62         double                        cost;
  63         DEBUG_ONLY(firm_dbg_module_t *dbg);
  64 } spill_cost_t;
  65
  66 static double
  67 execution_frequency(const be_chordal_env_t * chordal_env, const ir_node * irn)
  68 {
  69 #define FUDGE 0.001
  70 #ifndef EXECFREQ_LOOPDEPH
  71         return get_block_execfreq(chordal_env->exec_freq, get_block(irn)) + FUDGE;
  72 #else
  73         if(is_Block(irn))
  74                 return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
  75         else
  76                 return exp(get_loop_depth(get_irn_loop(get_nodes_block(irn))) * log(10)) + FUDGE;
  77 #endif
  78 }
  79
  80
  81 static double
  82 get_cost(const be_chordal_env_t * chordal_env, const ir_node * irn)
  83 {
  84         if(be_is_Spill(irn)) {
  85                 return COST_STORE;
  86         } else if(be_is_Reload(irn)){
  87                 return COST_LOAD;
  88         } else {
  89                 return arch_get_op_estimated_cost(chordal_env->birg->main_env->arch_env, irn);
  90         }
  91 }
  92
  93
  94 static void
  95 walker_cost_collector(ir_node * irn, void * data)
  96 {
  97         spill_cost_t   *sc = data;
  98         double          freq, cost;
  99
 100         if( (be_is_Reload(irn) && chordal_has_class(sc->chordal_env, irn))  ||
 101             (be_is_Spill(irn) && chordal_has_class(sc->chordal_env, get_irn_n(irn,1)))) {
 102
 103                 freq = execution_frequency(sc->chordal_env, irn);
 104                 cost = get_cost(sc->chordal_env, irn);
 105
 106                 DBG((sc->dbg, LEVEL_2, "%+F has cost %g with execfreq %g ->\t %g\n", irn, cost, freq, cost*freq));
 107
 108                 sc->cost += cost*freq;
 109         }
 110 }
 111
 112 double
 113 get_irg_spill_cost(const be_chordal_env_t * chordal_env)
 114 {
 115         spill_cost_t   sc;
 116         char           problem_name[256];
 117
 118         ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name);
 119
 120         sc.cost = 0.0;
 121         sc.chordal_env = chordal_env;
 122         FIRM_DBG_REGISTER(sc.dbg, "firm.be.ra.spillcost");
 123
 124         DBG((sc.dbg, LEVEL_2, "computing spill costs for %s\n", problem_name));
 125         irg_walk_graph(chordal_env->irg, walker_cost_collector, NULL, &sc);
 126         DBG((sc.dbg, LEVEL_1, "spill costs for %s: %g\n", problem_name, sc.cost));
 127         DBG((sc.dbg, LEVEL_2, "\n"));
 128
 129         return sc.cost;
 130 }