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_t.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 /* structure to represent cycles or chains in a perm */
  53 typedef struct _perm_cycle_t {
  54         const arch_register_t **elems;       /**< the registers in the cycle */
  55         int                     n_elems;     /**< number of elements in the cycle */
  56         perm_type_t             type;        /**< type (CHAIN or CYCLE) */
  57 } perm_cycle_t;
  58
  59 /* Compare the in registers of two register pairs */
  60 static int compare_reg_pair(const void *a, const void *b) {
  61         const reg_pair_t *pair_a = a;
  62         const reg_pair_t *pair_b = b;
  63
  64         if (pair_a->in_reg->index > pair_b->in_reg->index)
  65                 return 1;
  66         else
  67                 return -1;
  68 }
  69
  70 /* returns the number register pairs marked as checked */
  71 static int get_n_checked_pairs(reg_pair_t *pairs, int n) {
  72         int i, n_checked = 0;
  73
  74         for (i = 0; i < n; i++) {
  75                 if (pairs[i].checked)
  76                         n_checked++;
  77         }
  78
  79         return n_checked;
  80 }
  81
  82 /**
  83  * Gets the node corresponding to a register from an array of register pairs.
  84  * NOTE: The given registers pairs and the register to look for must belong
  85  *       to the same register class.
  86  *
  87  * @param pairs  The array of register pairs
  88  * @param n      The number of pairs
  89  * @param reg    The register to look for
  90  * @param in_out 0 == look for IN register, 1 == look for OUT register
  91  * @return The corresponding node or NULL if not found
  92  */
  93 static ir_node *get_node_for_register(reg_pair_t *pairs, int n, const arch_register_t *reg, int in_out) {
  94         int i;
  95
  96         if (in_out) {
  97                 for (i = 0; i < n; i++) {
  98                         /* out register matches */
  99                         if (pairs[i].out_reg->index == reg->index)
 100                                 return pairs[i].out_node;
 101                 }
 102         }
 103         else {
 104                 for (i = 0; i < n; i++) {
 105                         /* in register matches */
 106                         if (pairs[i].in_reg->index == reg->index)
 107                                 return pairs[i].in_node;
 108                 }
 109         }
 110
 111         return NULL;
 112 }
 113
 114 /**
 115  * Gets the index in the register pair array where the in/out register
 116  * corresponds to reg_idx.
 117  *
 118  * @param pairs  The array of register pairs
 119  * @param n      The number of pairs
 120  * @param reg    The register index to look for
 121  * @param in_out 0 == look for IN register, 1 == look for OUT register
 122  * @return The corresponding index in pairs or -1 if not found
 123  */
 124 static int get_pairidx_for_regidx(reg_pair_t *pairs, int n, int reg_idx, int in_out) {
 125         int i;
 126
 127         if (in_out) {
 128                 for (i = 0; i < n; i++) {
 129                         /* out register matches */
 130                         if (pairs[i].out_reg->index == reg_idx)
 131                                 return i;
 132                 }
 133         }
 134         else {
 135                 for (i = 0; i < n; i++) {
 136                         /* in register matches */
 137                         if (pairs[i].in_reg->index == reg_idx)
 138                                 return i;
 139                 }
 140         }
 141
 142         return -1;
 143 }
 144
 145 /**
 146  * Gets an array of register pairs and tries to identify a cycle or chain starting
 147  * at position start.
 148  *
 149  * @param cycle Variable to hold the cycle
 150  * @param pairs Array of register pairs
 151  * @param start Index to start
 152  * @return The cycle or chain
 153  */
 154 static perm_cycle_t *get_perm_cycle(perm_cycle_t *cycle, reg_pair_t *pairs, int n, int start) {
 155         int head         = pairs[start].in_reg->index;
 156         int cur_idx      = pairs[start].out_reg->index;
 157         int cur_pair_idx = start;
 158         int n_pairs_done = get_n_checked_pairs(pairs, n) + 1;
 159         int idx;
 160
 161         /* assume worst case: all remaining pairs build a cycle or chain */
 162         cycle->elems    = calloc(n - n_pairs_done, sizeof(cycle->elems[0]));
 163         cycle->n_elems  = 2;  /* initial number of elements is 2 */
 164         cycle->elems[0] = pairs[start].in_reg;
 165         cycle->elems[1] = pairs[start].out_reg;
 166         cycle->type     = PERM_CHAIN; /* default is CHAIN, only changed when we found a cycle */
 167
 168         /* mark the first pair as checked */
 169         pairs[start].checked = 1;
 170
 171         idx = 2;
 172         /* check for cycle or end of a chain */
 173         while (cur_idx != head && n_pairs_done < n) {
 174                 /* goto next register in cycle or chain */
 175                 cur_pair_idx = get_pairidx_for_regidx(pairs, n, cur_idx, 0);
 176
 177                 if (cur_pair_idx < 0)
 178                         break;
 179
 180                 cur_idx = pairs[cur_pair_idx].out_reg->index;
 181
 182                 /* it's not the first element: insert it */
 183                 if (cur_idx != head) {
 184                         cycle->elems[idx++] = pairs[cur_pair_idx].out_reg;
 185                         cycle->n_elems++;
 186
 187                         n_pairs_done++;
 188                 }
 189                 else {
 190                         /* we are there where we started -> CYCLE */
 191                         cycle->type = PERM_CYCLE;
 192                 }
 193
 194                 /* mark the pair as checked */
 195                 pairs[cur_pair_idx].checked = 1;
 196         }
 197
 198         return cycle;
 199 }
 200
 201 /**
 202  * Lowers a perm node.  Resolves cycles and creates a bunch of
 203  * copy and swap operations to permute registers.
 204  *
 205  * @param irn      The perm node
 206  * @param block    The block the perm node belongs to
 207  * @param walk_env The environment
 208  */
 209 static void lower_perm_node(ir_node *irn, void *walk_env) {
 210         const be_node_factory_t     *fact;
 211         const arch_register_class_t *reg_class;
 212         const arch_env_t            *arch_env;
 213         firm_dbg_module_t           *mod;
 214         lower_env_t     *env = walk_env;
 215         reg_pair_t      *pairs;
 216         const ir_edge_t *edge;
 217         perm_cycle_t    *cycle;
 218         int              n, i, pn, do_copy;
 219         ir_node         *sched_point, *block, *in[2];
 220         ir_node         *arg1, *arg2, *res1, *res2;
 221         ir_node         *cpyxchg = NULL;
 222
 223         if (is_Block(irn))
 224                 return;
 225
 226         fact     = env->chord_env->main_env->node_factory;
 227         arch_env = env->chord_env->main_env->arch_env;
 228         do_copy  = env->do_copy;
 229         mod      = env->dbg_module;
 230         block    = get_nodes_block(irn);
 231
 232         /* check if perm
 233            Note: A Proj on a Perm will cause is_Perm()
 234                  also to return true */
 235         if (is_Proj(irn) || ! is_Perm(arch_env, irn))
 236                 return;
 237
 238         /*
 239                 Get the schedule predecessor node to the perm
 240                 NOTE: This works with auto-magic. If we insert the
 241                         new copy/exchange nodes after this node, everything
 242                         should be ok.
 243         */
 244         sched_point = sched_prev(irn);
 245         DBG((mod, LEVEL_1, "sched point is %+F\n", sched_point));
 246         assert(sched_point && "Perm is not scheduled or has no predecessor");
 247
 248         n = get_irn_arity(irn);
 249         assert(n == get_irn_n_edges(irn) && "perm's in and out numbers different");
 250
 251         reg_class = arch_get_irn_register(arch_env, get_irn_n(irn, 0))->reg_class;
 252         pairs     = calloc(n, sizeof(pairs[0]));
 253
 254         /* build the list of register pairs (in, out) */
 255         i = 0;
 256         foreach_out_edge(irn, edge) {
 257                 pairs[i].out_node = get_edge_src_irn(edge);
 258                 pn                = get_Proj_proj(pairs[i].out_node);
 259                 pairs[i].in_node  = get_irn_n(irn, pn);
 260
 261                 pairs[i].in_reg  = arch_get_irn_register(arch_env, pairs[i].in_node);
 262                 pairs[i].out_reg = arch_get_irn_register(arch_env, pairs[i].out_node);
 263
 264                 pairs[i].checked = 0;
 265                 i++;
 266         }
 267
 268         /* sort the register pairs by the indices of the in registers */
 269         qsort(pairs, n, sizeof(pairs[0]), compare_reg_pair);
 270
 271         /* Mark all equal pairs as checked, and exchange the OUT proj with
 272                 the IN node. */
 273         for (i = 0; i < n; i++) {
 274                 if (pairs[i].in_reg->index == pairs[i].out_reg->index) {
 275                         DBG((mod, LEVEL_1, "%+F removing equal perm register pair (%+F, %+F, %s)\n",
 276                                 irn, pairs[i].in_node, pairs[i].out_node, pairs[i].out_reg->name));
 277
 278                         /* We have to check for a special case:
 279                                 The in-node could be a Proj from a Perm. In this case,
 280                                 we need to correct the projnum */
 281                         if (is_Perm(arch_env, pairs[i].in_node) && is_Proj(pairs[i].in_node)) {
 282                                 set_Proj_proj(pairs[i].out_node, get_Proj_proj(pairs[i].in_node));
 283                         }
 284
 285                         /* remove the proj from the schedule */
 286                         sched_remove(pairs[i].out_node);
 287
 288                         /* reroute the edges from the proj to the argument */
 289                         edges_reroute(pairs[i].out_node, pairs[i].in_node, env->chord_env->irg);
 290
 291                         pairs[i].checked = 1;
 292                 }
 293         }
 294
 295         /* Set do_copy to 0 if it's on but we have no free register */
 296         if (do_copy) {
 297                 do_copy = 0;
 298         }
 299
 300         /* check for cycles and chains */
 301         while (get_n_checked_pairs(pairs, n) < n) {
 302                 i = 0;
 303
 304                 /* go to the first not-checked pair */
 305                 while (pairs[i].checked) i++;
 306                 cycle = calloc(1, sizeof(*cycle));
 307                 cycle = get_perm_cycle(cycle, pairs, n, i);
 308
 309                 /* We don't need to do anything if we have a Perm with two
 310                         elements which represents a cycle, because those nodes
 311                         already represent exchange nodes */
 312                 if (n == 2 && cycle->type == PERM_CYCLE) {
 313                         free(cycle);
 314                         continue;
 315                 }
 316
 317 //TODO: - iff PERM_CYCLE && do_copy -> determine free temp reg and insert copy to/from it before/after
 318 //        the copy cascade (this reduces the cycle into a chain)
 319
 320                 /* build copy/swap nodes from back to front */
 321                 for (i = cycle->n_elems - 2; i >= 0; i--) {
 322                         arg1 = get_node_for_register(pairs, n, cycle->elems[i], 0);
 323                         arg2 = get_node_for_register(pairs, n, cycle->elems[i + 1], 0);
 324
 325                         res1 = get_node_for_register(pairs, n, cycle->elems[i], 1);
 326                         res2 = get_node_for_register(pairs, n, cycle->elems[i + 1], 1);
 327
 328                         /*
 329                                 If we have a cycle and don't copy: we need to create exchange nodes
 330                                 NOTE: An exchange node is a perm node with 2 INs and 2 OUTs
 331                                 IN_1  = in node with register i
 332                                 IN_2  = in node with register i + 1
 333                                 OUT_1 = out node with register i + 1
 334                                 OUT_2 = out node with register i
 335                         */
 336                         if (cycle->type == PERM_CYCLE && !do_copy) {
 337                                 in[0] = arg1;
 338                                 in[1] = arg2;
 339
 340                                 DBG((mod, LEVEL_1, "%+F creating exchange node (%+F, %s) and (%+F, %s) with\n",
 341                                         irn, arg1, cycle->elems[i]->name, arg2, cycle->elems[i + 1]->name));
 342                                 DBG((mod, LEVEL_1, "%+F                        (%+F, %s) and (%+F, %s)\n",
 343                                         irn, res1, cycle->elems[i]->name, res2, cycle->elems[i + 1]->name));
 344
 345                                 cpyxchg = new_Perm(fact, reg_class, env->chord_env->irg, block, 2, in);
 346
 347                                 sched_remove(res1);
 348                                 sched_remove(res2);
 349
 350                                 set_Proj_pred(res2, cpyxchg);
 351                                 set_Proj_proj(res2, 0);
 352                                 set_Proj_pred(res1, cpyxchg);
 353                                 set_Proj_proj(res1, 1);
 354
 355                                 sched_add_after(sched_point, res1);
 356                                 sched_add_after(sched_point, res2);
 357
 358                                 arch_set_irn_register(arch_env, res2, cycle->elems[i + 1]);
 359                                 arch_set_irn_register(arch_env, res1, cycle->elems[i]);
 360                         }
 361                         else {
 362                                 DBG((mod, LEVEL_1, "%+F creating copy node (%+F, %s) -> (%+F, %s)\n",
 363                                         irn, arg1, cycle->elems[i]->name, res2, cycle->elems[i + 1]->name));
 364
 365                                 cpyxchg = new_Copy(fact, reg_class, env->chord_env->irg, block, arg1);
 366                                 arch_set_irn_register(arch_env, cpyxchg, cycle->elems[i + 1]);
 367
 368                                 /* remove the proj from the schedule */
 369                                 sched_remove(res2);
 370
 371                                 /* exchange copy node and proj */
 372                                 exchange(res2, cpyxchg);
 373                         }
 374
 375                         /* insert the copy/exchange node in schedule after the magic schedule node (see above) */
 376                         sched_add_after(sched_point, cpyxchg);
 377
 378                         DBG((mod, LEVEL_1, "replacing %+F with %+F, placed new node after %+F\n", irn, cpyxchg, sched_point));
 379                 }
 380
 381 //              free(cycle->elems);
 382                 free(cycle);
 383         }
 384
 385         /* remove the perm from schedule */
 386         sched_remove(irn);
 387 }
 388
 389 /**
 390  * Walks over all blocks in an irg and performs perm lowering.
 391  *
 392  * @param chord_env The chordal environment containing the irg
 393  * @param do_copy   1 == resolve cycles with a free reg if available
 394  */
 395 void lower_perms(be_chordal_env_t *chord_env, int do_copy) {
 396         lower_env_t env;
 397
 398         env.chord_env  = chord_env;
 399         env.do_copy    = do_copy;
 400         env.dbg_module = firm_dbg_register("ir.be.lower");
 401
 402         irg_walk_blkwise_graph(chord_env->irg,  NULL, lower_perm_node, &env);
 403 }