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

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #include "debug.h"
   6
   7 #include "irnodeset.h"
   8 #include "irgwalk.h"
   9 #include "irprintf.h"
  10 #include "iredges_t.h"
  11
  12 #include "beirg.h"
  13 #include "bespilloptions.h"
  14 #include "bespill.h"
  15 #include "bemodule.h"
  16 #include "besched.h"
  17 #include "bearch_t.h"
  18 #include "be_t.h"
  19 #include "beirg.h"
  20
  21 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  22
  23 typedef struct daemel_env_t daemel_env_t;
  24 struct daemel_env_t {
  25         spill_env_t                 *spill_env;
  26         int                          n_regs;
  27         const arch_env_t            *arch_env;
  28         const arch_register_class_t *cls;
  29         const be_lv_t               *lv;
  30         bitset_t                    *spilled_nodes;
  31 };
  32
  33 typedef struct spill_candidate_t spill_candidate_t;
  34 struct spill_candidate_t {
  35         double   costs;
  36         ir_node *node;
  37 };
  38
  39 static
  40 int compare_spill_candidates_desc(const void *d1, const void *d2)
  41 {
  42         const spill_candidate_t *c1 = d1;
  43         const spill_candidate_t *c2 = d2;
  44
  45         return (int) (c2->costs - c1->costs);
  46 }
  47
  48 static
  49 double get_spill_costs(daemel_env_t *env, ir_node *node)
  50 {
  51         const ir_edge_t *edge;
  52         spill_env_t     *spill_env = env->spill_env;
  53         double           costs     = be_get_spill_costs(spill_env, node, node);
  54
  55         foreach_out_edge(node, edge) {
  56                 ir_node *use = get_edge_src_irn(edge);
  57
  58                 if(is_Phi(use)) {
  59                         int      in         = get_edge_src_pos(edge);
  60                         ir_node *block      = get_nodes_block(use);
  61
  62                         costs += be_get_reload_costs_on_edge(spill_env, node, block, in);
  63                 } else {
  64                         costs += be_get_reload_costs(spill_env, node, use);
  65                 }
  66         }
  67
  68         return costs;
  69 }
  70
  71 /**
  72  * spills a node by placing a reload before each usage
  73  */
  74 static
  75 void spill_node(daemel_env_t *env, ir_node *node)
  76 {
  77         const ir_edge_t *edge;
  78         spill_env_t     *spill_env       = env->spill_env;
  79         const arch_register_class_t *cls = env->cls;
  80
  81         foreach_out_edge(node, edge) {
  82                 ir_node *use = get_edge_src_irn(edge);
  83
  84                 if(is_Phi(use)) {
  85                         int      in         = get_edge_src_pos(edge);
  86                         ir_node *block      = get_nodes_block(use);
  87
  88                         be_add_reload_on_edge(spill_env, node, block, in, cls, 1);
  89                 } else {
  90                         be_add_reload(spill_env, node, use, cls, 1);
  91                 }
  92         }
  93
  94         bitset_set(env->spilled_nodes, get_irn_idx(node));
  95 }
  96
  97 /**
  98  * spill @p n nodes from a nodeset. Removes the nodes from the nodeset and
  99  * sets the spilled bits in env->spilled_nodes.
 100  */
 101 static
 102 void spill_nodes(daemel_env_t *env, ir_nodeset_t *nodes, ir_node *spill_phis_in)
 103 {
 104         size_t                 node_count = ir_nodeset_size(nodes);
 105         int                    registers  = env->n_regs;
 106         spill_candidate_t     *candidates;
 107         ir_nodeset_iterator_t  iter;
 108         ir_node               *node;
 109         size_t                 i;
 110         int                    spills_needed = node_count - registers;
 111
 112         if(spills_needed <= 0)
 113                 return;
 114
 115         candidates = malloc(node_count * sizeof(candidates[0]));
 116
 117         /* construct array with spill candidates and calculate their costs */
 118         i = 0;
 119         foreach_ir_nodeset(nodes, node, iter) {
 120                 spill_candidate_t *candidate = & candidates[i];
 121
 122                 candidate->node  = node;
 123                 candidate->costs = get_spill_costs(env, node);
 124                 i++;
 125         }
 126         assert(i == node_count);
 127
 128         /* sort spill candidates */
 129         qsort(candidates, node_count, sizeof(candidates[0]),
 130               compare_spill_candidates_desc);
 131
 132         /* spill cheapest ones */
 133         DBG((dbg, LEVEL_2, "\tspills needed: %d\n", spills_needed));
 134         for(i = registers; i < node_count; ++i) {
 135                 spill_candidate_t *candidate = &candidates[i];
 136                 ir_node           *node      = candidate->node;
 137
 138                 DBG((dbg, LEVEL_3, "\tspilling %+F (costs %f)\n",
 139                      node, candidate->costs));
 140
 141                 spill_node(env, node);
 142                 if(spill_phis_in != NULL && is_Phi(node) &&
 143                    get_nodes_block(node) == spill_phis_in) {
 144                         be_spill_phi(env->spill_env, node);
 145                 }
 146         }
 147
 148         free(candidates);
 149 }
 150
 151 /**
 152  * make sure register pressure in a block is always equal or below the number
 153  * of available registers
 154  */
 155 static
 156 void spill_block(ir_node *block, void *data)
 157 {
 158         daemel_env_t                *env           = data;
 159         const arch_env_t            *arch_env      = env->arch_env;
 160         const arch_register_class_t *cls           = env->cls;
 161         const be_lv_t               *lv            = env->lv;
 162         ir_nodeset_t                 live_nodes;
 163         ir_nodeset_iterator_t        iter;
 164         ir_node                     *node;
 165         bitset_t                    *spilled_nodes = env->spilled_nodes;
 166
 167         DBG((dbg, LEVEL_1, "spilling block %+F\n", block));
 168
 169         ir_nodeset_init(&live_nodes);
 170         be_liveness_end_of_block_ir_nodeset(lv, arch_env, cls, block, &live_nodes);
 171
 172         foreach_ir_nodeset(&live_nodes, node, iter) {
 173                 DBG((dbg, LEVEL_2, "\t%+F is live-in... ", node));
 174                 if(bitset_is_set(spilled_nodes, get_irn_idx(node))) {
 175                         DBG((dbg, LEVEL_2, "but spilled; removing.\n"));
 176                 } else {
 177                         DBG((dbg, LEVEL_2, "keeping.\n"));
 178                 }
 179         }
 180
 181         sched_foreach_reverse(block, node) {
 182                 if(is_Phi(node))
 183                         break;
 184
 185                 be_liveness_transfer_ir_nodeset(arch_env, cls, node, &live_nodes);
 186                 /* TODO: do custom liveness transfer and don't add already spilled
 187                    node */
 188
 189                 spill_nodes(env, &live_nodes, NULL);
 190         }
 191
 192         spill_nodes(env, &live_nodes, block);
 193
 194         ir_nodeset_destroy(&live_nodes);
 195 }
 196
 197 void be_spill_daemel(be_irg_t *birg, const arch_register_class_t *cls)
 198 {
 199         daemel_env_t  env;
 200         ir_graph     *irg    = be_get_birg_irg(birg);
 201         int           n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
 202
 203         if(n_regs == 0)
 204                 return;
 205
 206         be_invalidate_liveness(birg);
 207         be_assure_liveness(birg);
 208
 209         env.spill_env     = be_new_spill_env(birg);
 210         env.n_regs        = n_regs;
 211         env.arch_env      = be_get_birg_arch_env(birg);
 212         env.cls           = cls;
 213         env.lv            = be_get_birg_liveness(birg);
 214         env.spilled_nodes = bitset_malloc(get_irg_last_idx(irg));
 215
 216         irg_block_walk_graph(irg, spill_block, NULL, &env);
 217
 218         bitset_free(env.spilled_nodes);
 219
 220         be_insert_spills_reloads(env.spill_env);
 221
 222         be_delete_spill_env(env.spill_env);
 223 }
 224
 225 void be_init_daemelspill(void)
 226 {
 227         static be_spiller_t daemel_spiller = {
 228                 be_spill_daemel
 229         };
 230
 231         be_register_spiller("daemel", &daemel_spiller);
 232         FIRM_DBG_REGISTER(dbg, "ir.be.spilldaemel");
 233 }
 234
 235 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_doedelspill);