nsz Git - libfirm/blob - ir/lower/lower_calls.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/lower/lower_calls.c
   4  * Purpose:     lowering of Calls with compound parameters
   5  * Author:      Michael Beck
   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
  12 #ifdef HAVE_CONFIG_H
  13 #include "config.h"
  14 #endif
  15
  16 #ifdef HAVE_ALLOCA_H
  17 #include <alloca.h>
  18 #endif
  19 #ifdef HAVE_MALLOC_H
  20 #include <malloc.h>
  21 #endif
  22
  23 #include "irprog_t.h"
  24 #include "irnode_t.h"
  25 #include "type_t.h"
  26 #include "irmode_t.h"
  27 #include "ircons.h"
  28 #include "irgmod.h"
  29 #include "irgwalk.h"
  30 #include "lower_calls.h"
  31 #include "return.h"
  32 #include "array.h"
  33
  34 /**
  35  * Creates a new lowered type for a method type with compound
  36  * arguments. The new type is associated to the old one and returned.
  37  */
  38 static ir_type *create_modified_mtd_type(const lower_params_t *lp, ir_type *mtp)
  39 {
  40   ir_type *lowered;
  41   ir_type **params, **results, *res_tp;
  42   int n_ress, n_params, nn_ress, nn_params, i, first_variadic;
  43   ident *id;
  44   add_hidden hidden_params;
  45   variadicity var;
  46
  47   if (is_lowered_type(mtp)) {
  48     /* the type is already lowered. Not handled yet. */
  49     assert(0 && "lowered types NYI");
  50   }
  51
  52   lowered = get_associated_type(mtp);
  53   if (lowered)
  54     return lowered;
  55
  56   n_ress   = get_method_n_ress(mtp);
  57   NEW_ARR_A(ir_type *, results, n_ress);
  58
  59   n_params = get_method_n_params(mtp);
  60   NEW_ARR_A(ir_type *, params, n_params + n_ress);
  61
  62   first_variadic = get_method_first_variadic_param_index(mtp);
  63
  64   hidden_params = lp->hidden_params;
  65   if (hidden_params == ADD_HIDDEN_SMART &&
  66     get_method_variadicity(mtp) == variadicity_variadic)
  67         hidden_params = ADD_HIDDEN_ALWAYS_IN_FRONT;
  68
  69   if (hidden_params == ADD_HIDDEN_ALWAYS_IN_FRONT) {
  70     /* add hidden in front */
  71     for (nn_ress = nn_params = i = 0; i < n_ress; ++i) {
  72       res_tp = get_method_res_type(mtp, i);
  73
  74       if (is_compound_type(res_tp))
  75         params[nn_params++] = lp->find_pointer_type(res_tp, get_modeP_data(), lp->def_ptr_alignment);
  76       else
  77         results[nn_ress++] = res_tp;
  78     }
  79
  80     /* move the index of the first variadic parameter */
  81     first_variadic += nn_params;
  82
  83     for (i = 0; i < n_params; ++i)
  84       params[nn_params++] = get_method_param_type(mtp, i);
  85   }
  86   else {
  87     /* add hidden parameters last */
  88     assert(get_method_variadicity(mtp) == variadicity_non_variadic &&
  89       "Cannot add hidden parameters at end of variadic function");
  90
  91     for (nn_params = 0; nn_params < n_params; ++nn_params)
  92       params[nn_params] = get_method_param_type(mtp, nn_params);
  93
  94     for (nn_ress = i = 0; i < n_ress; ++i) {
  95       res_tp = get_method_res_type(mtp, i);
  96
  97       if (is_compound_type(res_tp))
  98         params[nn_params++] = lp->find_pointer_type(res_tp, get_modeP_data(), lp->def_ptr_alignment);
  99       else
 100         results[nn_ress++] = res_tp;
 101     }
 102   }
 103
 104   /* create the new type */
 105   id = mangle_u(new_id_from_chars("L", 1), get_type_ident(mtp));
 106   lowered = new_d_type_method(id, nn_params, nn_ress, get_type_dbg_info(mtp));
 107
 108   /* fill it */
 109   for (i = 0; i < nn_params; ++i)
 110     set_method_param_type(lowered, i, params[i]);
 111   for (i = 0; i < nn_ress; ++i)
 112     set_method_res_type(lowered, i, results[i]);
 113
 114   var = get_method_variadicity(mtp);
 115   set_method_variadicity(lowered, var);
 116   if (var == variadicity_variadic)
 117     set_method_first_variadic_param_index(lowered, first_variadic);
 118
 119   /* associate the lowered type with the original one for easier access */
 120   set_lowered_type(mtp, lowered);
 121
 122   return lowered;
 123 }
 124
 125 /**
 126  * Walker environment for fix_value_res_access().
 127  */
 128 typedef struct _wlk_env_t {
 129   int arg_shift;      /**< argument index shift for parameters. */
 130   int first_hidden;   /**< index of the first hidden argument. */
 131 } wlk_env;
 132
 133 /**
 134  * Post walker: shift all parameter indeces and remove
 135  * Sel(Proj(P_frame_base())
 136  */
 137 static void fix_value_res_access(ir_node *n, void *ctx) {
 138   wlk_env *env = ctx;
 139
 140   if (env->arg_shift > 0 && is_Proj(n)) {
 141     ir_node *pred = get_Proj_pred(n);
 142
 143     /* Fix the argument numbers */
 144     if (pred == get_irg_args(current_ir_graph)) {
 145       long pnr = get_Proj_proj(n);
 146       set_Proj_proj(n, pnr + env->arg_shift);
 147     }
 148   }
 149 }
 150
 151 /**
 152  * returns non-zero if adr is a compound address
 153  * of a frame-type entity
 154  *
 155  * @param ft   the frame type
 156  * @param adr  the node
 157  */
 158 static int is_compound_address(ir_type *ft, ir_node *adr)
 159 {
 160   entity *ent;
 161
 162   if (! is_Sel(adr))
 163     return 0;
 164   if (get_Sel_n_indexs(adr) != 0)
 165     return 0;
 166   ent = get_Sel_entity(adr);
 167   return get_entity_owner(ent) == ft;
 168 }
 169
 170 /** A pair for the copy-return-optimization */
 171 typedef struct cr_pair {
 172   entity *ent;    /**< the entity than can be removed from the frame */
 173   ir_node *arg;   /**< the argument that replaces the entities address */
 174 } cr_pair;
 175
 176 /**
 177  * Post walker: fixes all entities addresses for the copy-return
 178  * optimization.
 179  *
 180  * Note: We expect the length of the cr array to be 1 (C, C++),
 181  * so ignore the linear search.
 182  */
 183 static void do_copy_return_opt(ir_node *n, void *ctx) {
 184   cr_pair *arr = ctx;
 185   int i;
 186
 187   if (is_Sel(n)) {
 188     entity *ent = get_Sel_entity(n);
 189
 190     for (i = ARR_LEN(arr) - 1; i >= 0; --i) {
 191       if (ent == arr[i].ent) {
 192         exchange(n, arr[i].arg);
 193         break;
 194       }
 195     }
 196   }
 197 }
 198
 199 /**
 200  * Transform all graphs with compound parameter return:
 201  * Remove the return and use the hidden parameter instead.
 202  *
 203  * @param irg  the graph to transform
 204  */
 205 static void transform_irg(const lower_params_t *lp, ir_graph *irg)
 206 {
 207   entity *ent = get_irg_entity(irg);
 208   ir_type *mtp, *lowered_mtp, *res_tp, *ft;
 209   int i, j, k, n_ress, n_com, n_cr_opt;
 210   ir_node **new_in, *ret, *endbl, *bl, *mem, *copy;
 211   cr_pair *cr_opt;
 212   wlk_env env;
 213   add_hidden hidden_params;
 214
 215   assert(ent && "Cannot tranform graph without an entity");
 216   assert(get_irg_phase_state(irg) != phase_high && "call lowering must be done in phase high");
 217
 218   mtp    = get_entity_type(ent);
 219   n_ress = get_method_n_ress(mtp);
 220   for (n_com = i = 0; i < n_ress; ++i) {
 221     res_tp = get_method_res_type(mtp, i);
 222
 223     if (is_compound_type(res_tp))
 224       ++n_com;
 225   }
 226   if (! n_com)
 227     return;
 228
 229   /* much easier if we have only one return */
 230   normalize_one_return(irg);
 231
 232   /* This graph has a compound argument. Create a new type */
 233   lowered_mtp = create_modified_mtd_type(lp, mtp);
 234   set_entity_type(ent, lowered_mtp);
 235
 236   hidden_params = lp->hidden_params;
 237   if (hidden_params == ADD_HIDDEN_SMART &&
 238     get_method_variadicity(mtp) == variadicity_variadic)
 239     hidden_params = ADD_HIDDEN_ALWAYS_IN_FRONT;
 240
 241   if (hidden_params == ADD_HIDDEN_ALWAYS_IN_FRONT) {
 242     /* hidden arguments are added first */
 243     env.arg_shift    = n_com;
 244     env.first_hidden = 0;
 245   }
 246   else {
 247     /* hidden arguments are added last */
 248     env.arg_shift    = 0;
 249     env.first_hidden = get_method_n_params(mtp);
 250   }
 251
 252   if (env.arg_shift > 0) {
 253     /* scan the code and argument numbers. */
 254     irg_walk_graph(irg, NULL, fix_value_res_access, &env);
 255   }
 256
 257   /*
 258    * Now fix the return.
 259    */
 260
 261   /* STEP 1: find the return */
 262   endbl = get_irg_end_block(irg);
 263   ret = NULL;
 264   for (i = get_Block_n_cfgpreds(endbl) - 1; i >= 0; --i) {
 265     ir_node *pred = get_Block_cfgpred(endbl, i);
 266
 267     if (is_Return(pred)) {
 268       ret = pred;
 269       break;
 270     }
 271   }
 272   /* there should always be a return */
 273   assert(ret);
 274
 275   /*
 276    * STEP 2: fix it. For all compound return value add a CopyB,
 277    * all others are copied.
 278    */
 279   NEW_ARR_A(ir_node *, new_in, n_ress - n_com + 1);
 280
 281   bl  = get_nodes_block(ret);
 282   mem = get_Return_mem(ret);
 283
 284   ft = get_irg_frame_type(irg);
 285   NEW_ARR_A(cr_pair, cr_opt, n_com);
 286   n_cr_opt = 0;
 287   for (j = 1, i = k = 0; i < n_ress; ++i) {
 288     ir_node *pred = get_Return_res(ret, i);
 289     res_tp = get_method_res_type(mtp, i);
 290
 291     if (is_compound_type(res_tp)) {
 292       ir_node *arg = get_irg_args(irg);
 293       arg = new_r_Proj(irg, get_nodes_block(arg), arg, mode_P_data, env.first_hidden + k);
 294       ++k;
 295
 296       if (is_compound_address(ft, pred)) {
 297         /* we can do the copy-return optimization here */
 298         cr_opt[n_cr_opt].ent = get_Sel_entity(pred);
 299         cr_opt[n_cr_opt].arg = arg;
 300         ++n_cr_opt;
 301       }
 302       else {
 303         /* we cannot do copy-return optimization */
 304         copy = new_r_CopyB(
 305                 irg, bl,
 306                 mem,
 307                 arg,
 308                 pred,
 309                 res_tp
 310                );
 311         mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
 312       }
 313     }
 314     else {
 315       new_in[j] = pred;
 316       ++j;
 317     }
 318   }
 319   new_in[0] = mem;
 320   set_irn_in(ret, j, new_in);
 321
 322   if (n_cr_opt > 0) {
 323     irg_walk_graph(irg, NULL, do_copy_return_opt, cr_opt);
 324
 325     for (i = ARR_LEN(cr_opt) - 1; i >= 0; --i) {
 326       remove_class_member(ft, cr_opt[i].ent);
 327     }
 328   }
 329
 330   dump_ir_block_graph(irg, "-lc");
 331 }
 332
 333 /*
 334  * Lower calls with compound return types.
 335  * This function does the following transformations:
 336  *
 337  * - Adds a new (hidden) pointer parameter for
 338  *   any return compound type.
 339  *
 340  * - Use of the hidden parameters in the function code.
 341  *
 342  * - Change all calls to functions with compound return
 343  *   by providing space for the hidden parameter on the callers
 344  *   stack.
 345  *
 346  * - Replace a possible block copy after the function call.
 347  */
 348 void lower_compound_ret_calls(const lower_params_t *params)
 349 {
 350   int i;
 351   ir_graph *irg;
 352
 353   /* second step: Transform all graphs */
 354   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 355     irg = get_irp_irg(i);
 356
 357     if (irg == get_const_code_irg())
 358       continue;
 359
 360     transform_irg(params, irg);
 361   }
 362
 363   /*
 364    * Last step: transform any other method types.
 365    */
 366 }