nsz Git - libfirm/blob - ir/ana/analyze_irg_args.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/analyze_irg_agrs.c
   4  * Purpose:     read/write analyze of graph argument, which have mode reference.
   5  * Author:      Beyhan Veliev
   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 /**
  13  * @file analyze_irg_agrs.c
  14  *
  15  */
  16 #ifdef HAVE_CONFIG_H
  17 #include "config.h"
  18 #endif
  19
  20 #ifdef HAVE_MALLOC_H
  21 # include <malloc.h>
  22 #endif
  23 #ifdef HAVE_ALLOCA_H
  24 # include <alloca.h>
  25 #endif
  26 #ifdef HAVE_STDLIB_H
  27 # include <stdlib.h>
  28 #endif
  29
  30 #include "irouts.h"
  31 #include "irnode_t.h"
  32 #include "irmode_t.h"
  33 #include "array.h"
  34 #include "irprog.h"
  35 #include "entity_t.h"
  36
  37 #include "analyze_irg_args.h"
  38
  39 static char v;
  40 static void *VISITED = &v;
  41
  42 /**
  43  * Walk recursive the successors of a graph argument
  44  * with mode reference and mark if it will be read,
  45  * written or stored.
  46  *
  47  * @param arg   The graph argument with mode reference,
  48  *             that must be checked.
  49  */
  50 static unsigned analyze_arg(ir_node *arg, unsigned bits)
  51 {
  52   int i, p;
  53   ir_node *succ;
  54
  55   /* We must visit a node once to avoid endless recursion.*/
  56   set_irn_link(arg, VISITED);
  57
  58   for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
  59     succ = get_irn_out(arg, i);
  60
  61     /* We was here.*/
  62     if (get_irn_link(succ) == VISITED)
  63       continue;
  64
  65     /* We should not walk over the memory edge.*/
  66     if (get_irn_mode(succ) == mode_M)
  67       continue;
  68
  69     /* If we reach with the recursion a Call node and our reference
  70        isn't the address of this Call we accept that the reference will
  71        be read and written if the graph of the method represented by
  72        "Call" isn't computed else we analyze that graph. If our
  73        reference is the address of this
  74        Call node that mean the reference will be read.*/
  75     switch (get_irn_opcode(succ)) {
  76
  77     case iro_Call: {
  78       ir_node *ptr  = get_Call_ptr(succ);
  79
  80       if (ptr == arg) {
  81         /* Hmm: not sure what this is, most likely a read */
  82         bits |= ptr_access_read;
  83       }
  84       else {
  85         ir_op *op = get_irn_op(ptr);
  86         entity *meth_ent;
  87
  88         if (op == op_SymConst && get_SymConst_kind(ptr) == symconst_addr_ent) {
  89           meth_ent = get_SymConst_entity(ptr);
  90
  91           for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
  92             if (get_Call_param(succ, p) == arg) {
  93               /* an arg can be used more than once ! */
  94               bits |= get_method_param_access(meth_ent, p);
  95             }
  96           }
  97         }
  98         else if (op == op_Sel && get_irp_callee_info_state() == irg_callee_info_consistent) {
  99           /* is be a polymorphic call but callee information is available */
 100           int i, n_params = get_Call_n_params(succ);
 101
 102           /* simply look into ALL possible callees */
 103           for (i = get_Call_n_callees(succ) - 1; i >= 0; --i) {
 104             meth_ent = get_Call_callee(succ, i);
 105
 106             /* unknown_entity is used to signal that we don't know what is called */
 107             if (meth_ent == unknown_entity) {
 108               bits |= ptr_access_all;
 109               break;
 110             }
 111
 112             for (p = n_params - 1; p >= 0; --p) {
 113               if (get_Call_param(succ, p) == arg) {
 114                 /* an arg can be used more than once ! */
 115                 bits |= get_method_param_access(meth_ent, p);
 116               }
 117             }
 118           }
 119         }
 120         else /* can do anything */
 121           bits |= ptr_access_all;
 122       }
 123
 124       /* search stops here anyway */
 125       continue;
 126     }
 127     case iro_Store:
 128       /* We have reached a Store node => the reference is written or stored. */
 129       if (get_Store_ptr(succ) == arg) {
 130         /* written to */
 131         bits |= ptr_access_write;
 132       }
 133       else {
 134         /* stored itself */
 135         bits |= ptr_access_store;
 136       }
 137
 138       /* search stops here anyway */
 139       continue;
 140
 141     case iro_Load:
 142       /* We have reached a Load node => the reference is read. */
 143       bits |= ptr_access_read;
 144
 145       /* search stops here anyway */
 146       continue;
 147
 148     case iro_Conv:
 149       /* our address is casted into something unknown. Break our search. */
 150       bits = ptr_access_all;
 151       break;
 152
 153     default:
 154       break;
 155     }
 156
 157     /* If we know that, the argument will be read, write and stored, we
 158        can break the recursion.*/
 159     if (bits == ptr_access_all) {
 160       bits = ptr_access_all;
 161       break;
 162     }
 163
 164     /*
 165      * A calculation that do not lead to a reference mode ends our search.
 166      * This is dangerous: It would allow to cast into integer and that cast back ...
 167      * so, when we detect a Conv we go mad, see the Conv case above.
 168      */
 169     if (!mode_is_reference(get_irn_mode(succ)))
 170       continue;
 171
 172     /* follow further the address calculation */
 173     bits = analyze_arg(succ, bits);
 174   }
 175   set_irn_link(arg, NULL);
 176   return bits;
 177 }
 178
 179 /**
 180  * Check if a argument of the ir graph with mode
 181  * reference is read, write or both.
 182  *
 183  * @param irg   The ir graph to analyze.
 184  */
 185 static void analyze_ent_args(entity *ent)
 186 {
 187   ir_graph *irg;
 188   ir_node *irg_args, *arg;
 189   ir_mode *arg_mode;
 190   int nparams, i;
 191   long proj_nr;
 192   ir_type *mtp;
 193   ptr_access_kind *rw_info;
 194
 195   mtp     = get_entity_type(ent);
 196   nparams = get_method_n_params(mtp);
 197
 198   ent->param_access = NEW_ARR_F(ptr_access_kind, nparams);
 199
 200   /* If the method haven't parameters we have
 201    * nothing to do.
 202    */
 203   if (nparams <= 0)
 204     return;
 205
 206   irg = get_entity_irg(ent);
 207
 208   /* we have not yet analyzed the graph, set ALL access for pointer args */
 209   for (i = nparams - 1; i >= 0; --i)
 210     ent->param_access[i] =
 211       is_Pointer_type(get_method_param_type(mtp, i)) ? ptr_access_all : ptr_access_none;
 212
 213   if (! irg) {
 214     /* no graph, no better info */
 215     return;
 216   }
 217
 218   /* Call algorithm that computes the out edges */
 219   if (get_irg_outs_state(irg) != outs_consistent)
 220     compute_irg_outs(irg);
 221
 222   irg_args = get_irg_args(irg);
 223
 224   /* A array to save the information for each argument with
 225      mode reference.*/
 226   NEW_ARR_A(ptr_access_kind, rw_info, nparams);
 227
 228   /* We initialize the element with none state. */
 229   for (i = nparams - 1; i >= 0; --i)
 230     rw_info[i] = ptr_access_none;
 231
 232   /* search for arguments with mode reference
 233      to analyze them.*/
 234   for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 235     arg      = get_irn_out(irg_args, i);
 236     arg_mode = get_irn_mode(arg);
 237     proj_nr  = get_Proj_proj(arg);
 238
 239     if (mode_is_reference(arg_mode))
 240       rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
 241   }
 242
 243   /* copy the temporary info */
 244   memcpy(ent->param_access, rw_info, nparams * sizeof(ent->param_access[0]));
 245
 246 #if 0
 247   printf("\n%s:\n", get_entity_name(ent));
 248   for (i = 0; i < nparams; ++i) {
 249     if (is_Pointer_type(get_method_param_type(mtp, i)))
 250       if (ent->param_access[i] != ptr_access_none) {
 251         printf("  Pointer Arg %d access: ", i);
 252         if (ent->param_access[i] & ptr_access_read)
 253           printf("READ ");
 254         if (ent->param_access[i] & ptr_access_write)
 255           printf("WRITE ");
 256         if (ent->param_access[i] & ptr_access_store)
 257           printf("STORE ");
 258         printf("\n");
 259       }
 260   }
 261 #endif
 262 }
 263
 264 /**
 265  * Analyze how pointer arguments of a given
 266  * ir graph are accessed.
 267  *
 268  * @param irg   The ir graph to analyze.
 269  */
 270 void analyze_irg_args(ir_graph *irg)
 271 {
 272   entity *ent;
 273
 274   if (irg == get_const_code_irg())
 275     return;
 276
 277   ent = get_irg_entity(irg);
 278   if (! ent)
 279     return;
 280
 281   if (! ent->param_access)
 282     analyze_ent_args(ent);
 283 }
 284
 285 /*
 286  * Compute for a method with pointer parameter(s)
 287  * if they will be read or written.
 288  */
 289 ptr_access_kind get_method_param_access(entity *ent, int pos)
 290 {
 291   ir_type *mtp = get_entity_type(ent);
 292   int    is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 293
 294   assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 295
 296   if (ent->param_access) {
 297     if (pos < ARR_LEN(ent->param_access))
 298       return ent->param_access[pos];
 299     else
 300       return ptr_access_all;
 301   }
 302
 303   analyze_ent_args(ent);
 304
 305   if (pos < ARR_LEN(ent->param_access))
 306     return ent->param_access[pos];
 307   else
 308     return ptr_access_all;
 309 }
 310
 311 enum args_weight {
 312   null_weight        = 0,  /**< If can't be anything optimized. */
 313   binop_weight       = 1,  /**< If the argument have mode_weight and take part in binop. */
 314   const_binop_weight = 1,  /**< If the argument have mode_weight and take part in binop with a constant.*/
 315   cmp_weight         = 4,  /**< If the argument take part in cmp. */
 316   const_cmp_weight   = 10  /**< If the argument take part in cmp with a constant. */
 317 };
 318
 319 /**
 320  * Compute the weight of a method parameter
 321  *
 322  * @param arg  The parameter them weight muss be computed.
 323  */
 324 static float calc_method_param_weight(ir_node *arg)
 325 {
 326   int i;
 327   ir_node *succ, *op;
 328   float weight = null_weight;
 329
 330   /* We mark the nodes to avoid endless recursion */
 331   set_irn_link(arg, VISITED);
 332
 333   for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
 334     succ = get_irn_out(arg, i);
 335
 336     /* We was here.*/
 337     if (get_irn_link(succ) == VISITED)
 338       continue;
 339
 340     /* We should not walk over the memory edge.*/
 341     if (get_irn_mode(succ) == mode_M)
 342       continue;
 343
 344     /* We have reached a cmp and we must increase the
 345        weight with the cmp_weight.*/
 346     if (get_irn_op(succ) == op_Cmp) {
 347
 348       if (get_Cmp_left(succ) == arg)
 349         op = get_Cmp_right(succ);
 350       else
 351         op = get_Cmp_left(succ);
 352
 353       if (is_irn_constlike(op)) {
 354         weight += const_cmp_weight;
 355       }
 356       else
 357         weight += cmp_weight;
 358     }
 359     else if (is_binop(succ)) {
 360       /* We have reached a binop and we must increase the
 361                weight with the binop_weight. If the other operand of the
 362                binop is a constant we increase the weight with const_binop_weight
 363                and call the function recursive.
 364       */
 365       if (get_binop_left(succ) == arg)
 366               op = get_binop_right(succ);
 367       else
 368               op = get_binop_left(succ);
 369
 370       if (is_irn_constlike(op)) {
 371               weight += const_binop_weight;
 372               weight += calc_method_param_weight(succ);
 373       }
 374       else
 375         weight += binop_weight;
 376     } else if (is_unop(succ)) {
 377       /* We have reached a binop and we must increase the
 378                weight with the const_binop_weight and call the function recursive.*/
 379       weight += const_binop_weight;
 380       weight += calc_method_param_weight(succ);
 381     }
 382   }
 383   set_irn_link(arg, NULL);
 384   return weight;
 385 }
 386
 387 /**
 388  * Set a weight for each argument of a ir_graph.
 389  * The args with a greater weight are good for optimize.
 390  *
 391  * @param ent  The entity of the ir_graph.
 392  */
 393 static void analyze_method_params_weight(entity *ent)
 394 {
 395   ir_type *mtp;
 396   ir_graph *irg;
 397   int nparams, i, proj_nr;
 398   ir_node *irg_args, *arg;
 399
 400   mtp      = get_entity_type(ent);
 401   nparams  = get_method_n_params(mtp);
 402
 403   /* allocate a new array. currently used as 'analysed' flag */
 404   ent->param_weight = NEW_ARR_F(float, nparams);
 405
 406   /* If the method haven't parameters we have
 407    * nothing to do.
 408    */
 409   if (nparams <= 0)
 410     return;
 411
 412   irg = get_entity_irg(ent);
 413
 414   /* First we initialize the parameter weight with 0. */
 415   for (i = nparams - 1; i >= 0; i--)
 416     ent->param_weight[i] = null_weight;
 417
 418   if (! irg) {
 419     /* no graph, no better info */
 420     return;
 421   }
 422
 423   /* Call algorithm that computes the out edges */
 424   if (get_irg_outs_state(irg) != outs_consistent)
 425     compute_irg_outs(irg);
 426
 427   irg_args = get_irg_args(irg);
 428
 429   for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 430     arg                          = get_irn_out(irg_args, i);
 431     proj_nr                      = get_Proj_proj(arg);
 432     ent->param_weight[proj_nr]  += calc_method_param_weight(arg);
 433   }
 434
 435 #if 0
 436   printf("\n%s:\n", get_entity_name(ent));
 437   for (i = nparams - 1; i >= 0; --i)
 438     printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
 439 #endif
 440 }
 441
 442 /*
 443  * Compute for a method with pointer parameter(s)
 444  * if they will be read or written.
 445  */
 446 float get_method_param_weight(entity *ent, int pos)
 447 {
 448   ir_type *mtp = get_entity_type(ent);
 449   int     is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 450
 451   assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 452
 453   if (ent->param_weight) {
 454     if (pos < ARR_LEN(ent->param_weight))
 455       return ent->param_weight[pos];
 456     else
 457       return 0.0f;
 458   }
 459
 460   analyze_method_params_weight(ent);
 461
 462   if (pos < ARR_LEN(ent->param_weight))
 463     return ent->param_weight[pos];
 464   else
 465     return 0.0f;
 466 }
 467
 468
 469 /**
 470  * Analyze argument's weight of a given
 471  * ir graph.
 472  *
 473  * @param irg The ir graph to analyze.
 474  */
 475 void analyze_irg_args_weight(ir_graph *irg)
 476 {
 477   entity *ent;
 478
 479   ent = get_irg_entity(irg);
 480   if (! ent)
 481     return;
 482
 483   if (! ent->param_weight)
 484     analyze_method_params_weight(ent);
 485 }