nsz Git - libfirm/blob - ir/opt/return.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/return.c
   4  * Purpose:     normalize returns
   5  * Author:
   6  * Created:
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2005 Universität Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #ifdef HAVE_ALLOCA_H
  16 # include <alloca.h>
  17 #endif
  18 #ifdef HAVE_MALLOC_H
  19 # include <malloc.h>
  20 #endif
  21
  22 #include "irgraph_t.h"
  23 #include "ircons_t.h"
  24 #include "irnode_t.h"
  25 #include "irgmod.h"
  26
  27 #define set_bit(n)      (returns[(n) >> 3] |= 1 << ((n) & 7))
  28 #define get_bit(n)      (returns[(n) >> 3] & (1 << ((n) & 7)))
  29
  30 #undef IMAX
  31 #define IMAX(a, b)       ((a) > (b) ? (a) : (b))
  32
  33 /*
  34  * Normalize the Returns of a graph by creating a new End block
  35  * with One Return(Phi).
  36  * This is the preferred input for the if-conversion.
  37  *
  38  * In pseudocode, it means:
  39  *
  40  * if (a)
  41  *   return b;
  42  * else
  43  *   return c;
  44  *
  45  * is transformed into
  46  *
  47  * if (a)
  48  *   res = b;
  49  * else
  50  *   res = c;
  51  * return res;
  52  */
  53 void normalize_one_return(ir_graph *irg)
  54 {
  55   ir_node *endbl = get_irg_end_block(irg);
  56   int i, j, k, n, last_idx, n_rets, n_ret_vals = -1;
  57   unsigned char *returns;
  58   ir_node **in, **retvals;
  59
  60   ir_node *block, *new_ret;
  61
  62   /* look, if we have more than one return */
  63   n       = get_Block_n_cfgpreds(endbl);
  64   assert(n > 0);
  65   returns = alloca((n + 7) >> 3);
  66   memset(returns, 0, (n + 7) >> 3);
  67
  68   for (n_rets = i = 0; i < n; ++i) {
  69     ir_node *node = get_Block_cfgpred(endbl, i);
  70
  71     if (is_Return(node)) {
  72       ++n_rets;
  73
  74       set_bit(i);
  75
  76       if (n_ret_vals < 0)
  77         n_ret_vals = get_irn_arity(node);
  78     }
  79   }
  80
  81   /* there should be at least one Return node in Firm */
  82   if (n_rets <= 1)
  83     return;
  84
  85   in      = alloca(sizeof(*in) * IMAX(n_rets, n_ret_vals));
  86   retvals = alloca(sizeof(*in) * n_rets * n_ret_vals);
  87
  88   for (j = i = 0; i < n; ++i) {
  89     if (get_bit(i)) {
  90       ir_node *ret  = get_Block_cfgpred(endbl, i);
  91       ir_node *block = get_nodes_block(ret);
  92
  93       /* create a new Jmp for every Ret and place the in in */
  94       in[j] = new_r_Jmp(irg, block);
  95
  96       /* save the return values and shuffle them */
  97       for (k = 0; k < n_ret_vals; ++k)
  98         retvals[j + k*n_rets] = get_irn_n(ret, k);
  99
 100       set_Block_cfgpred(endbl, i, new_r_Bad(irg));
 101       last_idx = i;
 102
 103       ++j;
 104     }
 105   }
 106
 107   /* ok, create a new block with all created in's */
 108   block = new_r_Block(irg, n_rets, in);
 109
 110   /* now create the Phi nodes */
 111   for (j = i = 0; i < n_ret_vals; ++i, j += n_rets) {
 112     /* the return values are already shuffled */
 113     in[i] = new_r_Phi(irg, block, n_rets, &retvals[j], get_irn_mode(retvals[j]));
 114   }
 115
 116   new_ret = new_r_Return(irg, block, in[0], n_ret_vals-1, &in[1]);
 117
 118   set_Block_cfgpred(endbl, last_idx, new_ret);
 119
 120   /* invalidate analysis information:
 121    * a new Block was added, so dominator, outs and loop are inconsistent,
 122    * trouts and callee-state should be still valid
 123    */
 124   set_irg_doms_inconsistent(irg);
 125   set_irg_outs_inconsistent(irg);
 126   set_irg_extblk_inconsistent(irg);
 127   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_inconsistent);
 128 }
 129
 130 /**
 131  * check, whether a Ret can be moved on block upwards.
 132  *
 133  * In a block with a Return, all live nodes must be linked
 134  * with the Return, otherwise they are dead (because the Return leaves
 135  * the graph, so no more users of the other nodes can exists.
 136  *
 137  * We can move a Return, if it's predecessors are Phi nodes or
 138  * comes from another block. In the later case, it is always possible
 139  * to move the Return one block up, because the predecessor block must
 140  * dominate the Return block (SSA) and then it dominates the predecessor
 141  * block of the Return block as well.
 142  *
 143  * All predecessors of the Return block must be Jmp's of course, or we
 144  * cannot move it up, so we check this either.
 145  */
 146 static int can_move_ret(ir_node *ret)
 147 {
 148   ir_node *retbl = get_nodes_block(ret);
 149   int i, n = get_irn_arity(ret);
 150
 151   for (i = 0; i < n; ++i) {
 152     ir_node *pred = get_irn_n(ret, i);
 153
 154     if (! is_Phi(pred) && retbl == get_nodes_block(pred)) {
 155       /* first condition failed, found a non-Phi predecessor
 156        * then is in the Return block */
 157       return 0;
 158     }
 159   }
 160
 161   /* check, that predecessors are Jmps */
 162   n = get_Block_n_cfgpreds(retbl);
 163   for (i = 0; i < n; ++i)
 164     if (get_irn_op(get_Block_cfgpred(retbl, i)) != op_Jmp)
 165       return 0;
 166
 167   /* if we have 0 control flow predecessors, we cannot move :-) */
 168   return n > 0;
 169 }
 170
 171 /*
 172  * Normalize the Returns of a graph by moving
 173  * the Returns upwards as much as possible.
 174  * This might be preferred for code generation.
 175  *
 176  * In pseudocode, it means:
 177  *
 178  * if (a)
 179  *   res = b;
 180  * else
 181  *   res = c;
 182  * return res;
 183  *
 184  * is transformed into
 185  *
 186  * if (a)
 187  *   return b;
 188  * else
 189  *   return c;
 190  */
 191 void normalize_n_returns(ir_graph *irg)
 192 {
 193   int i, j, n, n_rets, n_finals, n_ret_vals;
 194   ir_node *list  = NULL;
 195   ir_node *final = NULL;
 196   ir_node **in;
 197   ir_node *endbl = get_irg_end_block(irg);
 198   ir_node *end;
 199
 200   /*
 201    * First, link all returns:
 202    * These must be predecessors of the endblock.
 203    * Place Returns that can be moved on list, all others
 204    * on final.
 205    */
 206   n = get_Block_n_cfgpreds(endbl);
 207   for (n_finals = n_rets = i = 0; i < n; ++i) {
 208     ir_node *ret = get_Block_cfgpred(endbl, i);
 209
 210     if (is_Return(ret) && can_move_ret(ret)) {
 211       /*
 212        * Ok, all conditions met, we can move this Return, put it
 213        * on our work list.
 214        */
 215       set_irn_link(ret, list);
 216       list = ret;
 217       ++n_rets;
 218     }
 219     else {
 220       /* Put all nodes that are not changed on the final list. */
 221       set_irn_link(ret, final);
 222       final = ret;
 223       ++n_finals;
 224     }
 225   }
 226
 227   if (n_rets <= 0)
 228     return;
 229
 230   /*
 231    * Now move the Returns upwards. We move always one block up (and create n
 232    * new Returns), than we check if a newly created Return can be moved even further.
 233    * If yes, we simply add it to our work list, else to the final list.
 234    */
 235   end        = get_irg_end(irg);
 236   n_ret_vals = get_irn_arity(list);
 237   in         = alloca(sizeof(*in) * n_ret_vals);
 238   while (list) {
 239     ir_node *ret   = list;
 240     ir_node *block = get_nodes_block(ret);
 241     ir_node *phiM;
 242
 243     list = get_irn_link(ret);
 244     --n_rets;
 245
 246     n = get_Block_n_cfgpreds(block);
 247     for (i = 0; i < n; ++i) {
 248       ir_node *jmp = get_Block_cfgpred(block, i);
 249       ir_node *new_bl, *new_ret;
 250
 251       if (get_irn_op(jmp) != op_Jmp)
 252         continue;
 253
 254       new_bl = get_nodes_block(jmp);
 255
 256       /* create the in-array for the new Ret */
 257       for (j = 0; j < n_ret_vals; ++j) {
 258         ir_node *pred = get_irn_n(ret, j);
 259
 260         in[j] = (is_Phi(pred) && get_nodes_block(pred) == block) ? get_Phi_pred(pred, i) : pred;
 261       }
 262
 263       new_ret = new_r_Return(irg, new_bl, in[0], n_ret_vals - 1, &in[1]);
 264
 265       if (! is_Bad(new_ret)) {
 266         /*
 267          * The newly created node might be bad, if we
 268          * create it in a block with only Bad predecessors.
 269          * In that case ignore this block.
 270          *
 271          * We could even kill the jmp then ...
 272          */
 273         if (can_move_ret(new_ret)) {
 274           set_irn_link(new_ret, list);
 275           list = new_ret;
 276           ++n_rets;
 277         }
 278         else {
 279           set_irn_link(new_ret, final);
 280           final = new_ret;
 281           ++n_finals;
 282         }
 283       }
 284
 285       /* remove the Jmp, we have placed a Return here */
 286       exchange(jmp, new_r_Bad(irg));
 287     }
 288
 289     /*
 290      * if the memory of the old Return is a PhiM, remove it
 291      * from the keep-alives, or it will keep the block which
 292      * will crash the dominator algorithm.
 293      */
 294     phiM = get_Return_mem(ret);
 295     if (is_Phi(phiM)) {
 296       n = get_End_n_keepalives(end);
 297       for (i = 0; i < n; ++i) {
 298         if (get_End_keepalive(end, i) == phiM) {
 299           set_End_keepalive(end, i, new_r_Bad(irg));
 300           break;
 301         }
 302       }
 303     }
 304   }
 305
 306   /*
 307    * Last step: Create a new endblock, with all nodes on the final
 308    * list as predecessors.
 309    */
 310   in = alloca(sizeof(*in) * n_finals);
 311
 312   for (i = 0; final; ++i, final = get_irn_link(final))
 313     in[i] = final;
 314
 315   exchange(endbl, new_r_Block(irg, n_finals, in));
 316
 317   /* the end block is not automatically skipped, so do it here */
 318   set_irg_end_block(irg, skip_Id(get_irg_end_block(irg)));
 319
 320   /* Invalidate analysis information:
 321    * Blocks become dead and new Returns were deleted, so dominator, outs and loop are inconsistent,
 322    * trouts and callee-state should be still valid
 323    */
 324   set_irg_doms_inconsistent(irg);
 325   set_irg_outs_inconsistent(irg);
 326   set_irg_loopinfo_state(current_ir_graph, loopinfo_cf_inconsistent);
 327 }