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

   1 /**
   2  * Author:      Christian Wuerdig
   3  * Date:        2005/12/14
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  * CVS-Id:      $Id$
   7  *
   8  * Performs lowering of perm nodes and spill/reload optimization.
   9  */
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #include "bearch.h"
  15 #include "belower.h"
  16 #include "benode_t.h"
  17 #include "bechordal_t.h"
  18 #include "besched.h"
  19
  20 #include "irgmod.h"
  21 #include "iredges.h"
  22 #include "irgwalk.h"
  23
  24 #undef is_Perm
  25 #define is_Perm(arch_env, irn) (arch_irn_classify(arch_env, irn) == arch_irn_class_perm)
  26
  27 /* lowering walker environment */
  28 typedef struct _lower_env_t {
  29         be_chordal_env_t  *chord_env;
  30         int                do_copy;
  31         firm_dbg_module_t *dbg_module;
  32 } lower_env_t;
  33
  34 /* holds a perm register pair */
  35 typedef struct _reg_pair_t {
  36         const arch_register_t *in_reg;    /**< a perm IN register */
  37         ir_node               *in_node;   /**< the in node to which the register belongs */
  38
  39         const arch_register_t *out_reg;   /**< a perm OUT register */
  40         ir_node               *out_node;  /**< the out node to which the register belongs */
  41
  42         int                    checked;   /**< indicates whether the pair was check for cycle or not */
  43 } reg_pair_t;
  44
  45 typedef enum _perm_type_t {
  46         PERM_CYCLE,
  47         PERM_CHAIN,
  48         PERM_SWAP,
  49         PERM_COPY
  50 } perm_type_t;
  51
  52 typedef struct _perm_cycle_t {
  53         const arch_register_t **elems;       /**< the registers in the cycle */
  54         int                     n_elems;     /**< number of elements in the cycle */
  55         perm_type_t             type;        /**< type (CHAIN or CYCLE) */
  56 } perm_cycle_t;
  57
  58 /* Compare the in registers of two register pairs */
  59 static int compare_reg_pair(const void *a, const void *b) {
  60         const reg_pair_t *pair_a = a;
  61         const reg_pair_t *pair_b = b;
  62
  63         if (pair_a->in_reg->index > pair_b->in_reg->index)
  64                 return 1;
  65         else
  66                 return -1;
  67 }
  68
  69 static int get_n_checked_pairs(reg_pair_t *pairs, int n) {
  70         int i, n_checked = 0;
  71
  72         for (i = 0; i < n; i++) {
  73                 if (pairs[i].checked)
  74                         n_checked++;
  75         }
  76
  77         return n_checked;
  78 }
  79
  80 /**
  81  * Gets the node corresponding to a register from an array of register pairs.
  82  * NOTE: The given registers pairs and the register to look for must belong
  83  *       to the same register class.
  84  *
  85  * @param pairs  The array of register pairs
  86  * @param n      The number of pairs
  87  * @param reg    The register to look for
  88  * @param in_out 0 == look for IN register, 1 == look for OUT register
  89  * @return The corresponding node or NULL if not found
  90  */
  91 static ir_node *get_node_for_register(reg_pair_t *pairs, int n, const arch_register_t *reg, int in_out) {
  92         int i;
  93
  94         if (in_out) {
  95                 for (i = 0; i < n; i++) {
  96                         /* out register matches */
  97                         if (pairs[i].out_reg->index == reg->index)
  98                                 return pairs[i].out_node;
  99                 }
 100         }
 101         else {
 102                 for (i = 0; i < n; i++) {
 103                         /* in register matches */
 104                         if (pairs[i].in_reg->index == reg->index)
 105                                 return pairs[i].in_node;
 106                 }
 107         }
 108
 109         return NULL;
 110 }
 111
 112 /**
 113  * Gets the index in the register pair array where the in/out register
 114  * corresponds to reg_idx.
 115  *
 116  * @param pairs  The array of register pairs
 117  * @param n      The number of pairs
 118  * @param reg    The register index to look for
 119  * @param in_out 0 == look for IN register, 1 == look for OUT register
 120  * @return The corresponding index in pairs or -1 if not found
 121  */
 122 static int get_pairidx_for_regidx(reg_pair_t *pairs, int n, int reg_idx, int in_out) {
 123         int i;
 124
 125         if (in_out) {
 126                 for (i = 0; i < n; i++) {
 127                         /* out register matches */
 128                         if (pairs[i].out_reg->index == reg_idx)
 129                                 return i;
 130                 }
 131         }
 132         else {
 133                 for (i = 0; i < n; i++) {
 134                         /* in register matches */
 135                         if (pairs[i].in_reg->index == reg_idx)
 136                                 return i;
 137                 }
 138         }
 139
 140         return -1;
 141 }
 142
 143 /**
 144  * Gets an array of register pairs and tries to identify a cycle or chain starting
 145  * at position start.
 146  *
 147  * @param cycle Variable to hold the cycle
 148  * @param pairs Array of register pairs
 149  * @param start Index to start
 150  * @return The cycle or chain
 151  */
 152 static perm_cycle_t *get_perm_cycle(perm_cycle_t *cycle, reg_pair_t *pairs, int n, int start) {
 153         int head         = pairs[start].in_reg->index;
 154         int cur_idx      = pairs[start].out_reg->index;
 155         int cur_pair_idx = start;
 156         int n_pairs_done = get_n_checked_pairs(pairs, n) + 1;
 157         int idx;
 158
 159         /* assume worst case: all remaining pairs build a cycle or chain */
 160         cycle->elems    = calloc(n - n_pairs_done, sizeof(cycle->elems[0]));
 161         cycle->n_elems  = 2;  /* initial number of elements is 2 */
 162         cycle->elems[0] = pairs[start].in_reg;
 163         cycle->elems[1] = pairs[start].out_reg;
 164         cycle->type     = PERM_CHAIN; /* default is CHAIN, only changed when we found a cycle */
 165
 166         /* mark the first pair as checked */
 167         pairs[start].checked = 1;
 168
 169         idx = 2;
 170         /* check for cycle or end of a chain */
 171         while (cur_idx != head && n_pairs_done < n) {
 172                 /* goto next register in cycle or chain */
 173                 cur_pair_idx = get_pairidx_for_regidx(pairs, n, cur_idx, 0);
 174
 175                 if (cur_pair_idx < 0)
 176                         break;
 177
 178                 cur_idx = pairs[cur_pair_idx].out_reg->index;
 179
 180                 /* it's not the first element: insert it */
 181                 if (cur_idx != head) {
 182                         cycle->elems[idx++] = pairs[cur_pair_idx].out_reg;
 183                         cycle->n_elems++;
 184
 185                         pairs[cur_pair_idx].checked = 1;
 186                         n_pairs_done++;
 187                 }
 188                 else {
 189                         /* we are there where we started -> CYCLE */
 190                         cycle->type = PERM_CYCLE;
 191                 }
 192         }
 193
 194         return cycle;
 195 }
 196
 197 /**
 198  * Lowers a perm node.  Resolves cycles and creates a bunch of
 199  * copy and swap operations to permute registers.
 200  *
 201  * @param irn      The perm node
 202  * @param walk_env The environment
 203  */
 204 static void lower_perms_walker(ir_node *irn, void *walk_env) {
 205         const be_node_factory_t     *fact;
 206         const arch_register_class_t *reg_class;
 207         const arch_env_t            *arch_env;
 208         firm_dbg_module_t           *mod;
 209         lower_env_t     *env = walk_env;
 210         reg_pair_t      *pairs;
 211         const ir_edge_t *edge;
 212         perm_cycle_t    *cycle;
 213         int              n, i, pn, do_copy;
 214         ir_node         *block, *arg, *res, *sched_point, *in[2];
 215         ir_node         *cpyxchg = NULL;
 216
 217         fact     = env->chord_env->main_env->node_factory;
 218         arch_env = env->chord_env->main_env->arch_env;
 219         do_copy  = env->do_copy;
 220         mod      = env->dbg_module;
 221
 222         /* check if perm */
 223         if (is_Proj(irn) || !  is_Perm(arch_env, irn))
 224                 return;
 225
 226         block = get_nodes_block(irn);
 227
 228         /*
 229                 Get the schedule predecessor node to the perm
 230                 NOTE: This works with auto-magic. If we insert the
 231                         new copy/exchange nodes after this node, everything
 232                         should be ok.
 233         */
 234         sched_point = sched_prev(irn);
 235         assert(sched_point && "Perm is not scheduled or has no predecessor");
 236
 237         n = get_irn_arity(irn);
 238         assert(n == get_irn_n_edges(irn) && "perm's in and out numbers different");
 239
 240         reg_class = arch_get_irn_register(arch_env, get_irn_n(irn, 0))->reg_class;
 241         pairs     = calloc(n, sizeof(pairs[0]));
 242
 243         /* build the list of register pairs (in, out) */
 244         i = 0;
 245         foreach_out_edge(irn, edge) {
 246                 pairs[i].out_node = get_edge_src_irn(edge);
 247                 pn                = get_Proj_proj(pairs[i].out_node);
 248                 pairs[i].in_node  = get_irn_n(irn, pn);
 249
 250                 pairs[i].in_reg  = arch_get_irn_register(arch_env, pairs[i].in_node);
 251                 pairs[i].out_reg = arch_get_irn_register(arch_env, pairs[i].out_node);
 252
 253                 pairs[i].checked = 0;
 254                 i++;
 255         }
 256
 257         /* sort the register pairs by the indices of the in registers */
 258         qsort(pairs, n, sizeof(pairs[0]), compare_reg_pair);
 259
 260         /* Mark all equal pairs as checked, and exchange the OUT proj with
 261                 the IN node. */
 262         for (i = 0; i < n; i++) {
 263                 if (pairs[i].in_reg->index == pairs[i].out_reg->index) {
 264                         DBG((mod, LEVEL_1, "removing equal perm register pair (%+F, %+F, %s)\n",
 265                                 pairs[i].in_node, pairs[i].out_node, pairs[i].out_reg->name));
 266                         /* If scheduling point and in-node are the same, then get the scheduling
 267                            pred of this node, otherwise we would break the scheduling list */
 268                         if (sched_point == pairs[i].in_node) {
 269                                 sched_point = sched_prev(sched_point);
 270                         }
 271
 272                         /* remove the proj from the schedule */
 273                         sched_remove(pairs[i].out_node);
 274
 275                         /* remove the argument from schedule */
 276                         sched_remove(pairs[i].in_node);
 277
 278                         /* exchange the proj with the argument */
 279                         exchange(pairs[i].out_node, pairs[i].in_node);
 280
 281                         /* add the argument after the magic scheduling point */
 282                         sched_add_after(sched_point, pairs[i].in_node);
 283
 284                         pairs[i].checked = 1;
 285                 }
 286         }
 287
 288         /* Set do_copy to 0 if it's on but we have no free register */
 289         if (do_copy) {
 290                 do_copy = 0;
 291         }
 292
 293         /* check for cycles and chains */
 294         while (get_n_checked_pairs(pairs, n) < n) {
 295                 i = 0;
 296
 297                 /* go to the first not-checked pair */
 298                 while (pairs[i].checked) i++;
 299                 cycle = calloc(1, sizeof(*cycle));
 300                 cycle = get_perm_cycle(cycle, pairs, n, i);
 301
 302 //todo: - iff PERM_CYCLE && do_copy -> determine free temp reg and insert copy to/from it before/after
 303 //        the copy cascade (this reduces the cycle into a chain)
 304
 305                 /* build copy/swap nodes from back to front */
 306                 for (i = cycle->n_elems - 2; i >= 0; i--) {
 307                         arg = get_node_for_register(pairs, n, cycle->elems[i], 0);
 308                         res = get_node_for_register(pairs, n, cycle->elems[i + 1], 1);
 309
 310                         /*
 311                                 If we have a cycle and don't copy: we need to create exchange nodes
 312                                 NOTE: An exchange node is a perm node with 2 INs and 2 OUTs
 313                                 IN_1  = in node with register i
 314                                 IN_2  = in node with register i + 1
 315                                 OUT_1 = out node with register i + 1
 316                                 OUT_2 = out node with register i
 317                         */
 318                         if (cycle->type == PERM_CYCLE && !do_copy) {
 319                                 in[0] = arg;
 320                                 in[1] = get_node_for_register(pairs, n, cycle->elems[i + 1], 0);
 321
 322                                 DBG((mod, LEVEL_1, "creating exchange node (%+F, %s) <-> (%+F, %s)\n",
 323                                         arg, cycle->elems[i]->name, res, cycle->elems[i + 1]->name));
 324
 325                                 cpyxchg = new_Perm(fact, reg_class, env->chord_env->irg, block, 2, in);
 326                                 set_Proj_pred(res, cpyxchg);
 327                                 set_Proj_proj(res, 0);
 328                                 set_Proj_pred(get_node_for_register(pairs, n, cycle->elems[i], 1), cpyxchg);
 329                                 set_Proj_proj(get_node_for_register(pairs, n, cycle->elems[i], 1), 1);
 330                         }
 331                         else {
 332                                 DBG((mod, LEVEL_1, "creating copy node (%+F, %s) -> (%+F, %s)\n",
 333                                         arg, cycle->elems[i]->name, res, cycle->elems[i + 1]->name));
 334
 335                                 cpyxchg = new_Copy(fact, reg_class, env->chord_env->irg, block, arg);
 336                                 arch_set_irn_register(arch_env, cpyxchg, cycle->elems[i + 1]);
 337
 338                                 /* remove the proj from the schedule */
 339                                 sched_remove(res);
 340
 341                                 /* exchange copy node and proj */
 342                                 exchange(res, cpyxchg);
 343                         }
 344
 345                         /* insert the copy/exchange node in schedule after the magic schedule node (see above) */
 346                         sched_add_after(sched_point, cpyxchg);
 347                 }
 348
 349 //              free(cycle->elems);
 350                 free(cycle);
 351         }
 352
 353         /* remove the perm from schedule */
 354         sched_remove(irn);
 355 }
 356
 357 /**
 358  * Walks over all nodes in an irg and performs perm lowering.
 359  *
 360  * @param chord_env The chordal environment containing the irg
 361  * @param do_copy   1 == resolve cycles with a free reg if available
 362  */
 363 void lower_perms(be_chordal_env_t *chord_env, int do_copy) {
 364         lower_env_t env;
 365
 366         env.chord_env  = chord_env;
 367         env.do_copy    = do_copy;
 368         env.dbg_module = firm_dbg_register("ir.be.lower");
 369
 370         irg_walk_blkwise_graph(chord_env->irg,  NULL, lower_perms_walker, &env);
 371 }