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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Normalize returns.
   9  * @author  Michael Beck
  10  */
  11 #include "config.h"
  12
  13 #include <stdbool.h>
  14
  15 #include "iroptimize.h"
  16 #include "irgraph_t.h"
  17 #include "ircons_t.h"
  18 #include "irnode_t.h"
  19 #include "irgmod.h"
  20 #include "irpass.h"
  21 #include "util.h"
  22 #include "raw_bitset.h"
  23
  24 /*
  25  * Normalize the Returns of a graph by creating a new End block
  26  * with One Return(Phi).
  27  * This is the preferred input for the if-conversion.
  28  *
  29  * In pseudocode, it means:
  30  *
  31  * if (a)
  32  *   return b;
  33  * else
  34  *   return c;
  35  *
  36  * is transformed into
  37  *
  38  * if (a)
  39  *   res = b;
  40  * else
  41  *   res = c;
  42  * return res;
  43  */
  44 void normalize_one_return(ir_graph *irg)
  45 {
  46         ir_node   *endbl         = get_irg_end_block(irg);
  47         ir_entity *entity        = get_irg_entity(irg);
  48         ir_type   *type          = get_entity_type(entity);
  49         int        n_ret_vals    = get_method_n_ress(type) + 1;
  50         int        n_rets        = 0;
  51         bool       filter_dbgi   = false;
  52         dbg_info  *combined_dbgi = NULL;
  53         int i, j, k, n, last_idx;
  54         ir_node **in, **retvals, **endbl_in;
  55         ir_node *block;
  56
  57         /* look, if we have more than one return */
  58         n = get_Block_n_cfgpreds(endbl);
  59         if (n <= 0) {
  60                 /* The end block has no predecessors, we have an endless
  61                    loop. In that case, no returns exists. */
  62                 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
  63                 add_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
  64                 return;
  65         }
  66
  67         unsigned *const returns = rbitset_alloca(n);
  68         for (i = 0; i < n; ++i) {
  69                 ir_node *node = get_Block_cfgpred(endbl, i);
  70
  71                 if (is_Return(node)) {
  72                         dbg_info *dbgi = get_irn_dbg_info(node);
  73
  74                         if (dbgi != NULL && dbgi != combined_dbgi) {
  75                                 if (filter_dbgi) {
  76                                         combined_dbgi = NULL;
  77                                 } else {
  78                                         combined_dbgi = dbgi;
  79                                         filter_dbgi   = true;
  80                                 }
  81                         }
  82
  83                         ++n_rets;
  84                         rbitset_set(returns, i);
  85                 }
  86         }
  87
  88         if (n_rets <= 1) {
  89                 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
  90                 add_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
  91                 return;
  92         }
  93
  94         in       = ALLOCAN(ir_node*, MAX(n_rets, n_ret_vals));
  95         retvals  = ALLOCAN(ir_node*, n_rets * n_ret_vals);
  96         endbl_in = ALLOCAN(ir_node*, n);
  97
  98         last_idx = 0;
  99         for (j = i = 0; i < n; ++i) {
 100                 ir_node *ret = get_Block_cfgpred(endbl, i);
 101
 102                 if (rbitset_is_set(returns, i)) {
 103                         ir_node *block = get_nodes_block(ret);
 104
 105                         /* create a new Jmp for every Ret and place the in in */
 106                         in[j] = new_r_Jmp(block);
 107
 108                         /* save the return values and shuffle them */
 109                         for (k = 0; k < n_ret_vals; ++k)
 110                                 retvals[j + k*n_rets] = get_irn_n(ret, k);
 111
 112                         ++j;
 113                 } else {
 114                         endbl_in[last_idx++] = ret;
 115                 }
 116         }
 117
 118         /* ok, create a new block with all created in's */
 119         block = new_r_Block(irg, n_rets, in);
 120
 121         /* now create the Phi nodes */
 122         for (j = i = 0; i < n_ret_vals; ++i, j += n_rets) {
 123                 ir_mode *mode = get_irn_mode(retvals[j]);
 124                 in[i] = new_r_Phi(block, n_rets, &retvals[j], mode);
 125         }
 126
 127         endbl_in[last_idx++] = new_rd_Return(combined_dbgi, block, in[0], n_ret_vals-1, &in[1]);
 128
 129         set_irn_in(endbl, last_idx, endbl_in);
 130
 131         /* invalidate analysis information:
 132          * a new Block was added, so dominator, outs and loop are inconsistent,
 133          * trouts and callee-state should be still valid */
 134         confirm_irg_properties(irg,
 135                 IR_GRAPH_PROPERTY_NO_BADS
 136                 | IR_GRAPH_PROPERTY_NO_TUPLES
 137                 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
 138                 | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
 139                 | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
 140         add_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
 141 }
 142
 143 /* Create a graph pass. */
 144 ir_graph_pass_t *normalize_one_return_pass(const char *name)
 145 {
 146         return def_graph_pass(name ? name : "one_ret", normalize_one_return);
 147 }
 148
 149 /**
 150  * Check, whether a Return can be moved on block upwards.
 151  *
 152  * In a block with a Return, all live nodes must be linked
 153  * with the Return, otherwise they are dead (because the Return leaves
 154  * the graph, so no more users of the other nodes can exists.
 155  *
 156  * We can move a Return, if its predecessors are Phi nodes or
 157  * comes from another block. In the later case, it is always possible
 158  * to move the Return one block up, because the predecessor block must
 159  * dominate the Return block (SSA) and then it dominates the predecessor
 160  * block of the Return block as well.
 161  *
 162  * All predecessors of the Return block must be Jmp's of course, or we
 163  * cannot move it up, so we add blocks if needed.
 164  */
 165 static bool can_move_ret(ir_node *ret)
 166 {
 167         ir_node *retbl = get_nodes_block(ret);
 168         int i, n = get_irn_arity(ret);
 169
 170         for (i = 0; i < n; ++i) {
 171                 ir_node *pred = get_irn_n(ret, i);
 172
 173                 if (! is_Phi(pred) && retbl == get_nodes_block(pred)) {
 174                         /* first condition failed, found a non-Phi predecessor
 175                          * then is in the Return block */
 176                         return false;
 177                 }
 178         }
 179
 180         /* check, that predecessors are Jmps */
 181         n = get_Block_n_cfgpreds(retbl);
 182         /* we cannot move above a labeled block, as this might kill the block */
 183         if (n <= 1 || get_Block_entity(retbl) != NULL)
 184                 return false;
 185         for (i = 0; i < n; ++i) {
 186                 ir_node *pred = get_Block_cfgpred(retbl, i);
 187
 188                 pred = skip_Tuple(pred);
 189                 if (! is_Jmp(pred) && !is_Bad(pred)) {
 190                         /* simply place a new block here */
 191                         ir_graph *irg  = get_irn_irg(retbl);
 192                         ir_node *block = new_r_Block(irg, 1, &pred);
 193                         ir_node *jmp   = new_r_Jmp(block);
 194                         set_Block_cfgpred(retbl, i, jmp);
 195                 }
 196         }
 197         return true;
 198 }
 199
 200 /*
 201  * Normalize the Returns of a graph by moving
 202  * the Returns upwards as much as possible.
 203  * This might be preferred for code generation.
 204  *
 205  * In pseudocode, it means:
 206  *
 207  * if (a)
 208  *   res = b;
 209  * else
 210  *   res = c;
 211  * return res;
 212  *
 213  * is transformed into
 214  *
 215  * if (a)
 216  *   return b;
 217  * else
 218  *   return c;
 219  */
 220 void normalize_n_returns(ir_graph *irg)
 221 {
 222         int i, j, n;
 223         ir_node  *list     = NULL;
 224         ir_node  *final    = NULL;
 225         unsigned  n_rets   = 0;
 226         unsigned  n_finals = 0;
 227         ir_node  *endbl    = get_irg_end_block(irg);
 228         int       n_ret_vals;
 229         ir_node **in;
 230         ir_node  *end;
 231
 232         /*
 233          * First, link all returns:
 234          * These must be predecessors of the endblock.
 235          * Place Returns that can be moved on list, all others
 236          * on final.
 237          */
 238         n = get_Block_n_cfgpreds(endbl);
 239         for (i = 0; i < n; ++i) {
 240                 ir_node *ret = get_Block_cfgpred(endbl, i);
 241
 242                 if (is_Bad(ret)) {
 243                         continue;
 244                 } else if (is_Return(ret) && can_move_ret(ret)) {
 245                         /*
 246                          * Ok, all conditions met, we can move this Return, put it
 247                          * on our work list.
 248                          */
 249                         set_irn_link(ret, list);
 250                         list = ret;
 251                         ++n_rets;
 252                 } else {
 253                         /* Put all nodes that are not changed on the final list. */
 254                         set_irn_link(ret, final);
 255                         final = ret;
 256                         ++n_finals;
 257                 }
 258         }
 259
 260         if (n_rets == 0) {
 261                 confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL);
 262                 add_irg_properties(irg, IR_GRAPH_PROPERTY_MANY_RETURNS);
 263                 return;
 264         }
 265
 266         /*
 267          * Now move the Returns upwards. We move always one block up (and create n
 268          * new Returns), than we check if a newly created Return can be moved even
 269          * further. If yes, we simply add it to our work list, else to the final
 270          * list.
 271          */
 272         end        = get_irg_end(irg);
 273         n_ret_vals = get_irn_arity(list);
 274         in         = ALLOCAN(ir_node*, n_ret_vals);
 275         while (list != NULL) {
 276                 ir_node  *ret   = list;
 277                 ir_node  *block = get_nodes_block(ret);
 278                 dbg_info *dbgi  = get_irn_dbg_info(ret);
 279                 ir_node  *phiM;
 280
 281                 list = (ir_node*)get_irn_link(ret);
 282                 --n_rets;
 283
 284                 n = get_Block_n_cfgpreds(block);
 285                 for (i = 0; i < n; ++i) {
 286                         ir_node *jmp = get_Block_cfgpred(block, i);
 287                         ir_node *new_bl, *new_ret;
 288
 289                         if (is_Bad(jmp))
 290                                 continue;
 291                         assert(is_Jmp(jmp));
 292
 293                         new_bl = get_nodes_block(jmp);
 294
 295                         /* create the in-array for the new Return */
 296                         for (j = 0; j < n_ret_vals; ++j) {
 297                                 ir_node *pred = get_irn_n(ret, j);
 298
 299                                 in[j] = (is_Phi(pred) && get_nodes_block(pred) == block) ? get_Phi_pred(pred, i) : pred;
 300                         }
 301
 302                         new_ret = new_rd_Return(dbgi, new_bl, in[0], n_ret_vals-1, &in[1]);
 303
 304                         if (! is_Bad(new_ret)) {
 305                                 /*
 306                                  * The newly created node might be bad, if we
 307                                  * create it in a block with only Bad predecessors.
 308                                  * In that case ignore this block.
 309                                  *
 310                                  * We could even kill the jmp then ...
 311                                  */
 312                                 if (can_move_ret(new_ret)) {
 313                                         set_irn_link(new_ret, list);
 314                                         list = new_ret;
 315                                         ++n_rets;
 316                                 } else {
 317                                         set_irn_link(new_ret, final);
 318                                         final = new_ret;
 319                                         ++n_finals;
 320                                 }
 321                         }
 322
 323                         /* remove the Jmp, we have placed a Return here */
 324                         exchange(jmp, new_r_Bad(irg, mode_X));
 325                 }
 326
 327                 /*
 328                  * if the memory of the old Return is a PhiM, remove it
 329                  * from the keep-alives, or it will keep the block which
 330                  * will crash the dominator algorithm.
 331                  */
 332                 phiM = get_Return_mem(ret);
 333                 if (is_Phi(phiM)) {
 334                         n = get_End_n_keepalives(end);
 335                         for (i = 0; i < n; ++i) {
 336                                 if (get_End_keepalive(end, i) == phiM) {
 337                                         set_End_keepalive(end, i, new_r_Bad(irg, mode_M));
 338                                         break;
 339                                 }
 340                         }
 341                 }
 342         }
 343
 344         /*
 345          * Last step: Create a new endblock, with all nodes on the final list as
 346          * predecessors.
 347          */
 348         in = ALLOCAN(ir_node*, n_finals);
 349
 350         for (i = 0; final != NULL; ++i, final = (ir_node*)get_irn_link(final)) {
 351                 in[i] = final;
 352         }
 353
 354         exchange(endbl, new_r_Block(irg, n_finals, in));
 355
 356         /* Invalidate analysis information:
 357          * Blocks become dead and new Returns were deleted, so dominator, outs and
 358          * loop are inconsistent, trouts and callee-state should be still valid */
 359         confirm_irg_properties(irg,
 360                 IR_GRAPH_PROPERTY_NO_TUPLES
 361                 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES
 362                 | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
 363         add_irg_properties(irg, IR_GRAPH_PROPERTY_MANY_RETURNS);
 364 }
 365
 366 /* Create a graph pass. */
 367 ir_graph_pass_t *normalize_n_returns_pass(const char *name)
 368 {
 369         return def_graph_pass(name ? name : "n_rets", normalize_n_returns);
 370 }