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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/tailrec.c
   4  * Purpose:     tail-recursion optimization
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:     08.06.2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2004 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifdef HAVE_CONFIG_H
  13 # include <config.h>
  14 #endif
  15
  16 #include <assert.h>
  17 #include "tailrec.h"
  18 #include "array.h"
  19 #include "irprog.h"
  20 #include "irgwalk.h"
  21 #include "irgmod.h"
  22 #include "irop.h"
  23 #include "irnode_t.h"
  24 #include "irgraph_t.h"
  25 #include "ircons.h"
  26 #include "irflag.h"
  27 #include "firmstat.h"
  28
  29 static int n_opt_applications = 0;
  30
  31 /**
  32  * the environment for colelcting data
  33  */
  34 typedef struct _collect_t {
  35   ir_node *proj_X;              /**< initial exec proj */
  36   ir_node *block;               /**< old first block */
  37   int     blk_idx;              /**< cfgpred index of the initial exec in block */
  38   ir_node *proj_m;              /**< linked list of memory from start proj's */
  39   ir_node *proj_data;           /**< linked list of all parameter access proj's */
  40 } collect_t;
  41
  42 /**
  43  * walker for collecting data
  44  */
  45 static void collect_data(ir_node *node, void *env)
  46 {
  47   collect_t *data = env;
  48   ir_node *pred;
  49   ir_op *op;
  50
  51   switch (get_irn_opcode(node)) {
  52   case iro_Proj:
  53     pred = get_Proj_pred(node);
  54
  55     op = get_irn_op(pred);
  56     if (op == op_Proj) {
  57       ir_node *start = get_Proj_pred(pred);
  58
  59       if (get_irn_op(start) == op_Start) {
  60         if (get_Proj_proj(pred) == pn_Start_T_args) {
  61           /* found Proj(ProjT(Start)) */
  62           set_irn_link(node, data->proj_data);
  63           data->proj_data = node;
  64         }
  65       }
  66     }
  67     else if (op == op_Start) {
  68       switch (get_Proj_proj(node)) {
  69         case pn_Start_M:
  70           /* found ProjM(Start) */
  71           set_irn_link(node, data->proj_m);
  72           data->proj_m = node;
  73           break;
  74         case pn_Start_X_initial_exec:
  75           /* found ProjX(Start) */
  76           data->proj_X = node;
  77           break;
  78         default:
  79           break;
  80       }
  81     }
  82     break;
  83   case iro_Block: {
  84     int i, n_pred = get_Block_n_cfgpreds(node);
  85
  86     /*
  87      * the first block has the initial exec as cfg predecessor
  88      */
  89     if (node != current_ir_graph->start_block) {
  90       for (i = 0; i < n_pred; ++i) {
  91         if (get_Block_cfgpred(node, i) == data->proj_X) {
  92           data->block   = node;
  93           data->blk_idx = i;
  94           break;
  95         }
  96       }
  97     }
  98     break;
  99   }
 100   default:
 101     break;
 102   }
 103 }
 104
 105 /**
 106  * do the graph reconstruction for tail-recursion elimination
 107  *
 108  * @param irg           the graph that will reconstructed
 109  * @param rets          linked list of all rets
 110  * @param n_tail_calls  number of tail-recursion calls
 111  */
 112 static void do_opt_tail_rec(ir_graph *irg, ir_node *rets, int n_tail_calls)
 113 {
 114   ir_graph *rem_irg = current_ir_graph;
 115   ir_node *end_block = irg->end_block;
 116   ir_node *block, *jmp, *call, *calls;
 117   ir_node **in;
 118   ir_node **phis;
 119   ir_node ***call_params;
 120   ir_node *p;
 121   int i, j, n_params;
 122   collect_t data;
 123   int rem = get_optimize();
 124
 125   assert(n_tail_calls);
 126
 127   /* we add nwe nodes, so the outs are inconsistant */
 128   set_irg_outs_inconsistent(irg);
 129
 130   /* we add new blocks and change the control flow */
 131   set_irg_dom_inconsistent(irg);
 132
 133   /* we add a new loop */
 134   set_irg_loopinfo_inconsistent(irg);
 135
 136   set_optimize(0);
 137
 138   /* collect needed data */
 139   data.proj_X    = NULL;
 140   data.block     = NULL;
 141   data.blk_idx   = -1;
 142   data.proj_m    = NULL;
 143   data.proj_data = NULL;
 144   irg_walk_graph(irg, NULL, collect_data, &data);
 145
 146   /* check number of arguments */
 147   call = get_irn_link(end_block);
 148   n_params = get_Call_n_params(call);
 149
 150   assert(data.proj_X && "Could not find initial exec from Start");
 151   assert(data.block  && "Could not find first block");
 152   assert(data.proj_m && "Could not find ProjM(Start)");
 153   assert((data.proj_data || n_params == 0) && "Could not find Proj(ProjT(Start)) of non-void function");
 154
 155   current_ir_graph = irg;
 156
 157   /* allocate in's for phi and block construction */
 158   NEW_ARR_A(ir_node *, in, n_tail_calls + 1);
 159
 160   in[0] = data.proj_X;
 161
 162   /* turn Return's into Jmp's */
 163   for (i = 1, p = rets; p; p = get_irn_link(p)) {
 164     ir_node *jmp;
 165
 166     set_cur_block(get_nodes_block(p));
 167     jmp = new_Jmp();
 168
 169     exchange(p, new_Bad());
 170     in[i++] = jmp;
 171
 172     add_End_keepalive(get_irg_end(irg), jmp);
 173   }
 174
 175   /* create a new block at start */
 176   block = new_Block(n_tail_calls + 1, in);
 177   jmp   = new_Jmp();
 178
 179   /* the old first block is now the second one */
 180   set_Block_cfgpred(data.block, data.blk_idx, jmp);
 181
 182   /* allocate phi's, position 0 contains the memory phi */
 183   NEW_ARR_A(ir_node *, phis, n_params + 1);
 184
 185   /* build the memory phi */
 186   i = 0;
 187   in[i] = new_rd_Proj(NULL, irg, irg->start_block, irg->start, mode_M, pn_Start_M);
 188   ++i;
 189
 190   for (calls = call; calls; calls = get_irn_link(calls)) {
 191     in[i] = get_Call_mem(calls);
 192     ++i;
 193   }
 194   assert(i == n_tail_calls + 1);
 195
 196   phis[0] = new_rd_Phi(NULL, irg, block, n_tail_calls + 1, in, mode_M);
 197
 198   /* build the data phi's */
 199   if (n_params > 0) {
 200     ir_node *calls;
 201
 202     NEW_ARR_A(ir_node **, call_params, n_params);
 203
 204     /* collect all parameters */
 205     for (i = 0, calls = call; calls; calls = get_irn_link(calls)) {
 206       call_params[i] = get_Call_param_arr(calls);
 207       ++i;
 208     }
 209
 210     /* build new projs and Phi's */
 211     for (i = 0; i < n_params; ++i) {
 212       ir_mode *mode = get_irn_mode(call_params[0][i]);
 213
 214       in[0] = new_rd_Proj(NULL, irg, block, irg->args, mode, i);
 215       for (j = 0; j < n_tail_calls; ++j)
 216         in[j + 1] = call_params[j][i];
 217
 218       phis[i + 1] = new_rd_Phi(NULL, irg, block, n_tail_calls + 1, in, mode);
 219     }
 220   }
 221
 222   /*
 223    * ok, we are here, so we have build and collected all needed Phi's
 224    * now exchange all Projs into links to Phi
 225    */
 226   for (p = data.proj_m; p; p = get_irn_link(p)) {
 227     exchange(p, phis[0]);
 228   }
 229   for (p = data.proj_data; p; p = get_irn_link(p)) {
 230     long proj = get_Proj_proj(p);
 231
 232     assert(0 <= proj && proj < n_params);
 233     exchange(p, phis[proj + 1]);
 234   }
 235
 236   current_ir_graph = rem_irg;
 237   set_optimize(rem);
 238 }
 239
 240 /*
 241  * convert simple tail-calls into loops
 242  */
 243 void opt_tail_rec_irg(ir_graph *irg)
 244 {
 245   ir_node *end_block = irg->end_block;
 246   int n_preds;
 247   int i, n_tail_calls = 0;
 248   ir_node *rets = NULL;
 249
 250   if (! get_opt_tail_recursion() || ! get_opt_optimize())
 251     return;
 252
 253   set_irn_link(end_block, NULL);
 254
 255   n_preds = get_Block_n_cfgpreds(end_block);
 256   for (i = 0; i < n_preds; ++i) {
 257     ir_node *ret = get_Block_cfgpred(end_block, i);
 258     ir_node *call, *call_ptr;
 259     entity *ent;
 260     int j, n_ress;
 261     ir_node **ress;
 262
 263     /* search all returns of a block */
 264     if (get_irn_op(ret) != op_Return)
 265       continue;
 266
 267     /* check, if it's a Return self() */
 268     call = skip_Proj(get_Return_mem(ret));
 269     if (get_irn_op(call) != op_Call)
 270       continue;
 271
 272     /* check if it's a recursive call */
 273     call_ptr = get_Call_ptr(call);
 274
 275     if (get_irn_op(call_ptr) != op_SymConst)
 276       continue;
 277
 278     if (get_SymConst_kind(call_ptr) != symconst_addr_ent)
 279       continue;
 280
 281     ent = get_SymConst_entity(call_ptr);
 282     if (!ent || get_entity_irg(ent) != irg)
 283       continue;
 284
 285     /* ok, mem is routed to a recursive call, check return args */
 286     n_ress = get_Return_n_ress(ret);
 287     ress = get_Return_res_arr(ret);
 288
 289     for (j = 0; j < n_ress; ++j) {
 290       ir_node *irn = skip_Proj(skip_Proj(ress[j]));
 291
 292       if (irn != call) {
 293         /* not routed to a call */
 294         break;
 295       }
 296     }
 297     if (j < n_ress)
 298       continue;
 299
 300     /* here, we have found a call */
 301     set_irn_link(call, get_irn_link(end_block));
 302     set_irn_link(end_block, call);
 303     ++n_tail_calls;
 304
 305     /* link all returns, we will need this */
 306     set_irn_link(ret, rets);
 307     rets = ret;
 308   }
 309
 310   /* now, end_block->link contains the list of all tail calls */
 311   if (! n_tail_calls)
 312     return;
 313
 314   if (get_opt_tail_recursion_verbose() && get_firm_verbosity() > 1)
 315     printf("  Performing tail recursion for graph %s and %d Calls\n",
 316            get_entity_ld_name(get_irg_entity(irg)), n_tail_calls);
 317   n_opt_applications++;
 318
 319   do_opt_tail_rec(irg, rets, n_tail_calls);
 320 }
 321
 322 /*
 323  * optimize tail recursion away
 324  */
 325 void opt_tail_recursion(void)
 326 {
 327   int i;
 328
 329   if (! get_opt_tail_recursion() || ! get_opt_optimize())
 330     return;
 331
 332   n_opt_applications = 0;
 333
 334   for (i = 0; i < get_irp_n_irgs(); i++) {
 335     current_ir_graph = get_irp_irg(i);
 336
 337     opt_tail_rec_irg(current_ir_graph);
 338   }
 339
 340   if (get_opt_tail_recursion_verbose())
 341     printf("Performed tail recursion for %d of %d graphs\n", n_opt_applications, get_irp_n_irgs());
 342 }