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 } lower_env_t;
  32
  33 /* holds a perm register pair */
  34 typedef struct _reg_pair_t {
  35         const arch_register_t *in_reg;    /**< a perm IN register */
  36         ir_node               *in_node;   /**< the in node to which the register belongs */
  37
  38         const arch_register_t *out_reg;   /**< a perm OUT register */
  39         ir_node               *out_node;  /**< the out node to which the register belongs */
  40
  41         int                    checked;   /**< indicates whether the pair was check for cycle or not */
  42 } reg_pair_t;
  43
  44 typedef enum _perm_type_t {
  45         PERM_CYCLE,
  46         PERM_CHAIN,
  47         PERM_SWAP,
  48         PERM_COPY
  49 } perm_type_t;
  50
  51 typedef struct _perm_cycle_t {
  52         const arch_register_t **elems;       /**< the registers in the cycle */
  53         int                     n_elems;     /**< number of elements in the cycle */
  54         perm_type_t             type;        /**< type (CHAIN or CYCLE) */
  55 } perm_cycle_t;
  56
  57 /* Compare the in registers of two register pairs */
  58 static int compare_reg_pair(const void *a, const void *b) {
  59         const reg_pair_t *pair_a = a;
  60         const reg_pair_t *pair_b = b;
  61
  62         if (pair_a->in_reg->index > pair_b->in_reg->index)
  63                 return 1;
  64         else
  65                 return -1;
  66 }
  67
  68 static int get_n_checked_pairs(reg_pair_t *pairs, int n) {
  69         int i, n_checked = 0;
  70
  71         for (i = 0; i < n; i++) {
  72                 if (pairs[i].checked)
  73                         n_checked++;
  74         }
  75
  76         return n_checked;
  77 }
  78
  79 /**
  80  * Gets the node corresponding to a register from an array of register pairs.
  81  * NOTE: The given registers pairs and the register to look for must belong
  82  *       to the same register class.
  83  *
  84  * @param pairs  The array of register pairs
  85  * @param n      The number of pairs
  86  * @param reg    The register to look for
  87  * @param in_out 0 == look for IN register, 1 == look for OUT register
  88  * @return The corresponding node or NULL if not found
  89  */
  90 static ir_node *get_node_for_register(reg_pair_t *pairs, int n, const arch_register_t *reg, int in_out) {
  91         int i;
  92
  93         for (i = 0; i < n; i++) {
  94                 if (in_out) {
  95                         /* out register matches */
  96                         if (pairs[i].out_reg->index == reg->index)
  97                                 return pairs[i].out_node;
  98                 }
  99                 else {
 100                         /* in register matches */
 101                         if (pairs[i].in_reg->index == reg->index)
 102                                 return pairs[i].in_node;
 103                 }
 104         }
 105
 106         return NULL;
 107 }
 108
 109 /**
 110  * Gets an array of register pairs and tries to identify a cycle or chain starting
 111  * at position start.
 112  *
 113  * @param cycle Variable to hold the cycle
 114  * @param pairs Array of register pairs
 115  * @param start Index to start
 116  * @return The cycle or chain
 117  */
 118 static perm_cycle_t *get_perm_cycle(perm_cycle_t *cycle, reg_pair_t *pairs, int n, int start) {
 119         int head         = pairs[start].in_reg->index;
 120         int cur_idx      = pairs[start].out_reg->index;
 121         int n_pairs_done = get_n_checked_pairs(pairs, n) + 1;
 122         int idx;
 123
 124         /* assume worst case: all remaining pairs build a cycle or chain */
 125         cycle->elems    = calloc(n - n_pairs_done, sizeof(cycle->elems[0]));
 126         cycle->n_elems  = 2;  /* initial number of elements is 2 */
 127         cycle->elems[0] = pairs[start].in_reg;
 128         cycle->elems[1] = pairs[start].out_reg;
 129         cycle->type     = PERM_CHAIN; /* default is CHAIN, only changed when we found a cycle */
 130
 131         /* mark the first pair as checked */
 132         pairs[start].checked = 1;
 133
 134         idx = 2;
 135         /* check for cycle or end of a chain */
 136         while (cur_idx != head && n_pairs_done < n) {
 137                 /* goto next register in cycle or chain */
 138                 cur_idx = pairs[cur_idx].out_reg->index;
 139
 140                 /* it's not the first element: insert it */
 141                 if (cur_idx != head) {
 142                         cycle->elems[idx++] = pairs[cur_idx].out_reg;
 143                         cycle->n_elems++;
 144
 145                         pairs[cur_idx].checked = 1;
 146                         n_pairs_done++;
 147                 }
 148                 else {
 149                         /* we are there where we started -> CYCLE */
 150                         cycle->type = PERM_CYCLE;
 151                 }
 152         }
 153
 154         return cycle;
 155 }
 156
 157 /**
 158  * Lowers a perm node.  Resolves cycles and creates a bunch of
 159  * copy and swap operations to permute registers.
 160  *
 161  * @param irn      The perm node
 162  * @param walk_env The environment
 163  */
 164 static void lower_perms_walker(ir_node *irn, void *walk_env) {
 165         const be_node_factory_t     *fact;
 166         const arch_register_class_t *reg_class;
 167         const arch_env_t            *arch_env;
 168         lower_env_t     *env = walk_env;
 169         reg_pair_t      *pairs;
 170         const ir_edge_t *edge;
 171         perm_cycle_t    *cycle;
 172         int              n, i, pn, do_copy;
 173         ir_node         *block, *arg, *res, *sched_point, *in[2];
 174         ir_node         *cpyxchg = NULL;
 175
 176         fact     = env->chord_env->main_env->node_factory;
 177         arch_env = env->chord_env->main_env->arch_env;
 178         do_copy  = env->do_copy;
 179
 180         /* check if perm */
 181         if (! is_Perm(arch_env, irn))
 182                 return;
 183
 184         block = get_nodes_block(irn);
 185
 186         /*
 187                 Get the schedule predecessor node to the perm
 188                 NOTE: This works with auto-magic. If we insert the
 189                         new copy/exchange nodes after this node, everything
 190                         should be ok.
 191         */
 192         sched_point = sched_prev(irn);
 193         assert(sched_point && "Perm is not scheduled or has no predecessor");
 194
 195         n = get_irn_arity(irn);
 196         assert(n == get_irn_n_edges(irn) && "perm's in and out numbers different");
 197
 198         reg_class = arch_get_irn_register(arch_env, get_irn_n(irn, 0))->reg_class;
 199         pairs     = calloc(n, sizeof(pairs[0]));
 200
 201         /* build the list of register pairs (in, out) */
 202         i = 0;
 203         foreach_out_edge(irn, edge) {
 204                 pairs[i].out_node = get_edge_src_irn(edge);
 205                 pn                = get_Proj_proj(pairs[i].out_node);
 206                 pairs[i].in_node  = get_irn_n(irn, pn);
 207
 208                 pairs[i].in_reg  = arch_get_irn_register(arch_env, pairs[i].in_node);
 209                 pairs[i].out_reg = arch_get_irn_register(arch_env, pairs[i].out_node);
 210
 211                 pairs[i].checked = 0;
 212                 i++;
 213         }
 214
 215         /* sort the register pairs by the indices of the in registers */
 216         qsort(pairs, n, sizeof(pairs[0]), compare_reg_pair);
 217
 218         /* Mark all equal pairs as checked, and exchange the OUT proj with
 219                 the IN node. */
 220         i = 0;
 221         while (pairs[i].in_reg->index == pairs[i].out_reg->index) {
 222                 /* remove the proj from the schedule */
 223                 sched_remove(pairs[i].out_node);
 224
 225                 /* remove the argument from schedule */
 226                 sched_remove(pairs[i].in_node);
 227
 228                 /* exchange the proj with the argument */
 229                 exchange(pairs[i].out_node, pairs[i].in_node);
 230
 231                 /* add the argument after the magic scheduling point */
 232                 sched_add_after(sched_point, pairs[i].in_node);
 233
 234                 pairs[i++].checked = 1;
 235         }
 236
 237         /* Set do_copy to 0 if it's on but we have no free register */
 238         if (do_copy) {
 239                 do_copy = 0;
 240         }
 241
 242         /* check for cycles and chains */
 243         while (get_n_checked_pairs(pairs, n) < n) {
 244                 i = 0;
 245
 246                 /* go to the first not-checked pair */
 247                 while (pairs[i].checked) i++;
 248                 cycle = calloc(1, sizeof(*cycle));
 249                 cycle = get_perm_cycle(cycle, pairs, n, i);
 250
 251 //todo: - iff PERM_CYCLE && do_copy -> determine free temp reg and insert copy to/from it before/after
 252 //        the copy cascade (this reduces the cycle into a chain)
 253
 254                 /* build copy/swap nodes from back to front */
 255                 for (i = cycle->n_elems - 2; i >= 0; i++) {
 256                         arg = get_node_for_register(pairs, n, cycle->elems[i], 0);
 257                         res = get_node_for_register(pairs, n, cycle->elems[i + 1], 1);
 258
 259                         /*
 260                                 If we have a cycle and don't copy: we need to create exchange nodes
 261                                 NOTE: An exchange node is a perm node with 2 INs and 2 OUTs
 262                                 IN_1  = in node with register i
 263                                 IN_2  = in node with register i + 1
 264                                 OUT_1 = out node with register i + 1
 265                                 OUT_2 = out node with register i
 266                         */
 267                         if (cycle->type == PERM_CYCLE && !do_copy) {
 268                                 in[0] = arg;
 269                                 in[1] = get_node_for_register(pairs, n, cycle->elems[i + 1], 0);
 270
 271                                 cpyxchg = new_Perm(fact, reg_class, env->chord_env->irg, block, 2, in);
 272                                 set_Proj_pred(res, cpyxchg);
 273                                 set_Proj_proj(res, 0);
 274                                 set_Proj_pred(get_node_for_register(pairs, n, cycle->elems[i], 1), cpyxchg);
 275                                 set_Proj_proj(get_node_for_register(pairs, n, cycle->elems[i], 1), 1);
 276                         }
 277                         else {
 278                                 cpyxchg = new_Copy(fact, reg_class, env->chord_env->irg, block, arg);
 279                                 arch_set_irn_register(arch_env, cpyxchg, cycle->elems[i + 1]);
 280
 281                                 /* remove the proj from the schedule */
 282                                 sched_remove(res);
 283
 284                                 /* exchange copy node and proj */
 285                                 exchange(res, cpyxchg);
 286                         }
 287
 288                         /* insert the copy/exchange node in schedule after the magic schedule node (see above) */
 289                         sched_add_after(sched_point, cpyxchg);
 290                 }
 291
 292                 free(cycle->elems);
 293                 free(cycle);
 294         }
 295
 296         /* remove the perm from schedule */
 297         sched_remove(irn);
 298 }
 299
 300 /**
 301  * Walks over all nodes in an irg and performs perm lowering.
 302  *
 303  * @param chord_env The chordal environment containing the irg
 304  * @param do_copy   1 == resolve cycles with a free reg if available
 305  */
 306 void lower_perms(be_chordal_env_t *chord_env, int do_copy) {
 307         lower_env_t env;
 308
 309         env.chord_env = chord_env;
 310         env.do_copy   = do_copy;
 311
 312         irg_block_walk_graph(chord_env->irg,  NULL, lower_perms_walker, &env);
 313 }