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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Spill module selection; Preparation steps
   9  * @author      Matthias Braun
  10  * @date        29.09.2005
  11  */
  12 #include "config.h"
  13
  14 #include "irtools.h"
  15 #include "debug.h"
  16 #include "iredges_t.h"
  17 #include "raw_bitset.h"
  18 #include "statev_t.h"
  19 #include "irgwalk.h"
  20
  21 #include "bespill.h"
  22 #include "bemodule.h"
  23 #include "be.h"
  24 #include "belive_t.h"
  25 #include "beirg.h"
  26 #include "bearch.h"
  27 #include "benode.h"
  28 #include "besched.h"
  29 #include "bera.h"
  30 #include "beintlive_t.h"
  31
  32 #include "lc_opts.h"
  33 #include "lc_opts_enum.h"
  34
  35 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  36
  37 typedef struct be_pre_spill_env_t {
  38         ir_graph                    *irg;
  39         const arch_register_class_t *cls;
  40 } be_pre_spill_env_t;
  41
  42 static void prepare_constr_insn(be_pre_spill_env_t *env, ir_node *node)
  43 {
  44         const arch_register_class_t *cls = env->cls;
  45         ir_node  *block      = get_nodes_block(node);
  46         const ir_graph *irg  = env->irg;
  47         be_irg_t       *birg = be_birg_from_irg(irg);
  48         be_lv_t *lv          = be_get_irg_liveness(irg);
  49         unsigned *def_constr = NULL;
  50         int       arity      = get_irn_arity(node);
  51
  52         /* Insert a copy for constraint inputs attached to a value which can't
  53          * fulfill the constraint
  54          * (typical example: stack pointer as input to copyb)
  55          * TODO: This really just checks precolored registers at the moment and
  56          *       ignores the general case of not matching in/out constraints
  57          */
  58         for (int i = 0; i < arity; ++i) {
  59                 ir_node                   *op  = get_irn_n(node, i);
  60                 const arch_register_req_t *req = arch_get_irn_register_req_in(node, i);
  61                 const arch_register_t     *reg;
  62                 ir_node                   *copy;
  63
  64                 if (req->cls != cls)
  65                         continue;
  66                 reg = arch_get_irn_register(op);
  67                 if (reg == NULL)
  68                         continue;
  69
  70                 /* Precolored with an ignore register (which is not virtual). */
  71                 if (reg->type & arch_register_type_virtual ||
  72                     rbitset_is_set(birg->allocatable_regs, reg->global_index))
  73                         continue;
  74
  75                 if (!arch_register_req_is(req, limited))
  76                         continue;
  77                 if (rbitset_is_set(req->limited, reg->index))
  78                         continue;
  79
  80                 copy = be_new_Copy(block, op);
  81                 stat_ev_int("constr_copy", 1);
  82                 sched_add_before(node, copy);
  83                 set_irn_n(node, i, copy);
  84                 DBG((dbg, LEVEL_3, "inserting ignore arg copy %+F for %+F pos %d\n",
  85                      copy, node, i));
  86         }
  87
  88         /* insert copies for nodes that occur constrained more than once. */
  89         be_foreach_use(node, cls, req, in, in_req_,
  90                 if (!arch_register_req_is(req, limited))
  91                         continue;
  92
  93                 for (int i2 = i_ + 1; i2 < arity; ++i2) {
  94                         ir_node *in2;
  95                         const arch_register_req_t *req2;
  96
  97                         req2 = arch_get_irn_register_req_in(node, i2);
  98                         if (req2->cls != cls)
  99                                 continue;
 100                         if (!arch_register_req_is(req2, limited))
 101                                 continue;
 102
 103                         in2 = get_irn_n(node, i2);
 104                         if (in2 != in)
 105                                 continue;
 106
 107                         /* if the constraint is the same, no copy is necessary
 108                          * TODO generalise unequal but overlapping constraints */
 109                         if (rbitsets_equal(req->limited, req2->limited, cls->n_regs))
 110                                 continue;
 111
 112                         ir_node *copy = be_new_Copy(block, in);
 113                         stat_ev_int("constr_copy", 1);
 114
 115                         sched_add_before(node, copy);
 116                         set_irn_n(node, i2, copy);
 117                         DBG((dbg, LEVEL_3,
 118                              "inserting multiple constr copy %+F for %+F pos %d\n",
 119                              copy, node, i2));
 120                 }
 121         );
 122
 123         /* collect all registers occurring in out constraints. */
 124         be_foreach_definition(node, cls, def, req,
 125                 (void)def;
 126                 if (!arch_register_req_is(req, limited))
 127                         continue;
 128                 if (def_constr == NULL) {
 129                         def_constr = rbitset_alloca(cls->n_regs);
 130                 }
 131                 rbitset_or(def_constr, req->limited, cls->n_regs);
 132         );
 133
 134         /* no output constraints => we're good */
 135         if (def_constr == NULL) {
 136                 return;
 137         }
 138
 139         /*
 140          * insert copies for all constrained arguments living through the node
 141          * and being constrained to a register which also occurs in out constraints.
 142          */
 143         unsigned *const tmp = rbitset_alloca(cls->n_regs);
 144         be_foreach_use(node, cls, req, in, in_req_,
 145                 /* Check, if
 146                  * 1) the operand is constrained.
 147                  * 2) lives through the node.
 148                  * 3) is constrained to a register occurring in out constraints.
 149                  */
 150                 if (!arch_register_req_is(req, limited))
 151                         continue;
 152                 if (!be_values_interfere(lv, node, in))
 153                         continue;
 154
 155                 rbitset_copy(tmp, req->limited, cls->n_regs);
 156                 rbitset_and(tmp, def_constr, cls->n_regs);
 157
 158                 if (rbitset_is_empty(tmp, cls->n_regs))
 159                         continue;
 160
 161                 /*
 162                  * only create the copy if the operand is no copy.
 163                  * this is necessary since the assure constraints phase inserts
 164                  * Copies and Keeps for operands which must be different from the
 165                  * results. Additional copies here would destroy this.
 166                  */
 167                 if (be_is_Copy(in))
 168                         continue;
 169
 170                 ir_node *copy = be_new_Copy(block, in);
 171                 sched_add_before(node, copy);
 172                 set_irn_n(node, i_, copy);
 173                 DBG((dbg, LEVEL_3, "inserting constr copy %+F for %+F pos %d\n",
 174                      copy, node, i_));
 175                 be_liveness_update(lv, in);
 176         );
 177 }
 178
 179 static void pre_spill_prepare_constr_walker(ir_node *block, void *data)
 180 {
 181         be_pre_spill_env_t *env = (be_pre_spill_env_t*)data;
 182         sched_foreach(block, node) {
 183                 prepare_constr_insn(env, node);
 184         }
 185 }
 186
 187 void be_pre_spill_prepare_constr(ir_graph *irg,
 188                                  const arch_register_class_t *cls)
 189 {
 190         be_pre_spill_env_t env;
 191         memset(&env, 0, sizeof(env));
 192         env.irg = irg;
 193         env.cls = cls;
 194
 195         be_assure_live_sets(irg);
 196
 197         irg_block_walk_graph(irg, pre_spill_prepare_constr_walker, NULL, &env);
 198 }
 199
 200
 201
 202 int be_coalesce_spill_slots = 1;
 203 int be_do_remats = 1;
 204
 205 static const lc_opt_table_entry_t be_spill_options[] = {
 206         LC_OPT_ENT_BOOL ("coalesce_slots", "coalesce the spill slots", &be_coalesce_spill_slots),
 207         LC_OPT_ENT_BOOL ("remat", "try to rematerialize values instead of reloading", &be_do_remats),
 208         LC_OPT_LAST
 209 };
 210
 211 static be_module_list_entry_t *spillers = NULL;
 212 static const be_spiller_t *selected_spiller = NULL;
 213
 214 void be_register_spiller(const char *name, be_spiller_t *spiller)
 215 {
 216         if (selected_spiller == NULL)
 217                 selected_spiller = spiller;
 218         be_add_module_to_list(&spillers, name, spiller);
 219 }
 220
 221 void be_do_spill(ir_graph *irg, const arch_register_class_t *cls)
 222 {
 223         assert(selected_spiller != NULL);
 224
 225         selected_spiller->spill(irg, cls);
 226 }
 227
 228 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spilloptions)
 229 void be_init_spilloptions(void)
 230 {
 231         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 232         lc_opt_entry_t *spill_grp = lc_opt_get_grp(be_grp, "spill");
 233
 234         lc_opt_add_table(spill_grp, be_spill_options);
 235         be_add_module_list_opt(be_grp, "spiller", "spill algorithm",
 236                                &spillers, (void**) &selected_spiller);
 237
 238         FIRM_DBG_REGISTER(dbg, "firm.be.spillprepare");
 239 }