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     if (get_irn_op(succ) == op_Call) {
  76       ir_node *Call_ptr  = get_Call_ptr(succ);
  77
  78       if (Call_ptr == arg) {
  79         /* Hmm: not sure what this is, most likely a read */
  80         bits |= ptr_access_read;
  81       }
  82       else if (op_SymConst == get_irn_op(Call_ptr) &&
  83               get_SymConst_kind(Call_ptr) == symconst_addr_ent) {
  84         entity *meth_ent = get_SymConst_entity(Call_ptr);
  85
  86               for (p = get_Call_n_params(succ) - 1; p >= 0; --p){
  87                 if (get_Call_param(succ, p) == arg) {
  88             /* an arg can be used more than once ! */
  89             bits |= get_method_param_access(meth_ent, p);
  90                 }
  91               }
  92       } else /* can do anything */
  93         bits |= ptr_access_all;
  94
  95       /* search stops here anyway */
  96       continue;
  97     }
  98     else if (get_irn_op(succ) == op_Store) {
  99       /* We have reached a Store node => the reference is written or stored. */
 100       if (get_Store_ptr(succ) == arg) {
 101         /* written to */
 102         bits |= ptr_access_write;
 103       }
 104       else {
 105         /* stored itself */
 106         bits |= ptr_access_store;
 107       }
 108
 109       /* search stops here anyway */
 110       continue;
 111    }
 112     else if (get_irn_op(succ) == op_Load) {
 113       /* We have reached a Load node => the reference is read. */
 114       bits |= ptr_access_read;
 115
 116       /* search stops here anyway */
 117       continue;
 118     }
 119     else if (get_irn_op(succ) == op_Conv) {
 120       /* our address is casted into something unknown. Break our search. */
 121       bits = ptr_access_all;
 122       break;
 123     }
 124
 125     /* If we know that, the argument will be read, write and stored, we
 126        can break the recursion.*/
 127     if (bits == ptr_access_all) {
 128       bits = ptr_access_all;
 129       break;
 130     }
 131
 132     /*
 133      * A calculation that do not lead to a reference mode ends our search.
 134      * This is dangerous: It would allow to cast into integer and that cast back ...
 135      * so, when we detect a Conv we go mad, see the Conv case above.
 136      */
 137     if (!mode_is_reference(get_irn_mode(succ)))
 138       continue;
 139
 140     /* follow further the address calculation */
 141     bits = analyze_arg(succ, bits);
 142   }
 143   set_irn_link(arg, NULL);
 144   return bits;
 145 }
 146
 147 /**
 148  * Check if a argument of the ir graph with mode
 149  * reference is read, write or both.
 150  *
 151  * @param irg   The ir graph to analyze.
 152  */
 153 static void analyze_ent_args(entity *ent)
 154 {
 155   ir_graph *irg;
 156   ir_node *irg_args, *arg;
 157   ir_mode *arg_mode;
 158   int nparams, i;
 159   long proj_nr;
 160   type *mtp;
 161   ptr_access_kind *rw_info;
 162
 163   mtp     = get_entity_type(ent);
 164   nparams = get_method_n_params(mtp);
 165
 166   ent->param_access = NEW_ARR_F(ptr_access_kind, nparams);
 167
 168   /* If the method haven't parameters we have
 169    * nothing to do.
 170    */
 171   if (nparams <= 0)
 172     return;
 173
 174   irg = get_entity_irg(ent);
 175
 176   /* we have not yet analyzed the graph, set ALL access for pointer args */
 177   for (i = nparams - 1; i >= 0; --i)
 178     ent->param_access[i] =
 179       is_Pointer_type(get_method_param_type(mtp, i)) ? ptr_access_all : ptr_access_none;
 180
 181   if (! irg) {
 182     /* no graph, no better info */
 183     return;
 184   }
 185
 186   /* Call algorithm that computes the out edges */
 187   if (get_irg_outs_state(irg) != outs_consistent)
 188     compute_outs(irg);
 189
 190   irg_args = get_irg_args(irg);
 191
 192   /* A array to save the information for each argument with
 193      mode reference.*/
 194   NEW_ARR_A(ptr_access_kind, rw_info, nparams);
 195
 196   /* We initialize the element with none state. */
 197   for (i = nparams - 1; i >= 0; --i)
 198     rw_info[i] = ptr_access_none;
 199
 200   /* search for arguments with mode reference
 201      to analyze them.*/
 202   for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 203     arg      = get_irn_out(irg_args, i);
 204     arg_mode = get_irn_mode(arg);
 205     proj_nr  = get_Proj_proj(arg);
 206
 207     if (mode_is_reference(arg_mode))
 208       rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
 209   }
 210
 211   /* copy the temporary info */
 212   memcpy(ent->param_access, rw_info, nparams * sizeof(ent->param_access[0]));
 213
 214   printf("\n%s:\n", get_entity_name(ent));
 215   for (i = 0; i < nparams; ++i) {
 216     if (is_Pointer_type(get_method_param_type(mtp, i)))
 217       if (ent->param_access[i] != ptr_access_none) {
 218         printf("  Pointer Arg %d access: ", i);
 219         if (ent->param_access[i] & ptr_access_read)
 220           printf("READ ");
 221         if (ent->param_access[i] & ptr_access_write)
 222           printf("WRITE ");
 223         if (ent->param_access[i] & ptr_access_store)
 224           printf("STORE ");
 225         printf("\n");
 226       }
 227   }
 228 }
 229
 230 /**
 231  * Analyze how pointer arguments of a given
 232  * ir graph are accessed.
 233  *
 234  * @param irg   The ir graph to analyze.
 235  */
 236 void analyze_irg_args(ir_graph *irg)
 237 {
 238   entity *ent;
 239
 240   if (irg == get_const_code_irg())
 241     return;
 242
 243   ent = get_irg_entity(irg);
 244   if (! ent)
 245     return;
 246
 247   if (! ent->param_access)
 248     analyze_ent_args(ent);
 249 }
 250
 251 /*
 252  * Compute for a method with pointer parameter(s)
 253  * if they will be read or written.
 254  */
 255 ptr_access_kind get_method_param_access(entity *ent, int pos)
 256 {
 257   type *mtp = get_entity_type(ent);
 258   int  is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 259
 260   assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 261
 262   if (ent->param_access) {
 263     if (pos < ARR_LEN(ent->param_access))
 264       return ent->param_access[pos];
 265     else
 266       return ptr_access_all;
 267   }
 268
 269   analyze_ent_args(ent);
 270
 271   if (pos < ARR_LEN(ent->param_access))
 272     return ent->param_access[pos];
 273   else
 274     return ptr_access_all;
 275 }
 276
 277 enum args_weight {
 278   null_weight        = 0,  /* If can't be anything optimized. */
 279   binop_weight       = 1,  /* If the argument have mode_weight and take part in binop. */
 280   const_binop_weight = 1,  /* If the argument have mode_weight and take part in binop with a constant.*/
 281   cmp_weight         = 4,  /* If the argument take part in cmp. */
 282   const_cmp_weight   = 10  /* If the argument take part in cmp with a constant. */
 283 };
 284
 285 /**
 286  * Compute the weight of a method parameter
 287  *
 288  * @param arg  The parameter them weight muss be computed.
 289  */
 290 static float calc_method_param_weight(ir_node *arg)
 291 {
 292   int i;
 293   ir_node *succ, *op;
 294   float weight = null_weight;
 295
 296   /* We mark the nodes to avoid endless recursion */
 297   set_irn_link(arg, VISITED);
 298
 299   for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
 300     succ = get_irn_out(arg, i);
 301
 302     /* We was here.*/
 303     if (get_irn_link(succ) == VISITED)
 304       continue;
 305
 306     /* We should not walk over the memory edge.*/
 307     if (get_irn_mode(succ) == mode_M)
 308       continue;
 309
 310     /* We have reached a cmp and we must increase the
 311        weight with the cmp_weight.*/
 312     if (get_irn_op(succ) == op_Cmp) {
 313
 314       if (get_Cmp_left(succ) == arg)
 315         op = get_Cmp_right(succ);
 316       else
 317         op = get_Cmp_left(succ);
 318
 319       if (is_irn_constlike(op)) {
 320         weight += const_cmp_weight;
 321       }
 322       else
 323         weight += cmp_weight;
 324     }
 325     else if (is_binop(succ)) {
 326       /* We have reached a binop and we must increase the
 327                weight with the binop_weight. If the other operand of the
 328                binop is a constant we increase the weight with const_binop_weight
 329                and call the function recursive.
 330       */
 331       if (get_binop_left(succ) == arg)
 332               op = get_binop_right(succ);
 333       else
 334               op = get_binop_left(succ);
 335
 336       if (is_irn_constlike(op)) {
 337               weight += const_binop_weight;
 338               weight += calc_method_param_weight(succ);
 339       }
 340       else
 341         weight += binop_weight;
 342     } else if (is_unop(succ)) {
 343       /* We have reached a binop and we must increase the
 344                weight with the const_binop_weight and call the function recursive.*/
 345       weight += const_binop_weight;
 346       weight += calc_method_param_weight(succ);
 347     }
 348   }
 349   set_irn_link(arg, NULL);
 350   return weight;
 351 }
 352
 353 /**
 354  * Set a weight for each argument of a ir_graph.
 355  * The args with a greater weight are good for optimize.
 356  *
 357  * @param ent  The entity of the ir_graph.
 358  */
 359 static void analyze_method_params_weight(entity *ent)
 360 {
 361   type *mtp;
 362   ir_graph *irg;
 363   int nparams, i, proj_nr;
 364   ir_node *irg_args, *arg;
 365
 366   mtp      = get_entity_type(ent);
 367   nparams  = get_method_n_params(mtp);
 368
 369   /* If the method haven't parameters we have
 370    * nothing to do.
 371    */
 372   if (nparams <= 0)
 373     return;
 374
 375   ent->param_weight = malloc(sizeof(float) * nparams);
 376   irg               = get_entity_irg(ent);
 377
 378   /* First we initialize the parameter weight with 0. */
 379   for (i = nparams - 1; i >= 0; i--)
 380     ent->param_weight[i] = null_weight;
 381
 382   if (! irg) {
 383     /* no graph, no better info */
 384     return;
 385   }
 386
 387   /* Call algorithm that computes the out edges */
 388   if (get_irg_outs_state(irg) != outs_consistent)
 389     compute_outs(irg);
 390
 391   irg_args = get_irg_args(irg);
 392
 393   for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 394     arg                          = get_irn_out(irg_args, i);
 395     proj_nr                      = get_Proj_proj(arg);
 396     ent->param_weight[proj_nr]  += calc_method_param_weight(arg);
 397   }
 398
 399   printf("\n%s:\n", get_entity_name(ent));
 400   for (i = nparams - 1; i >= 0; --i)
 401     printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
 402 }
 403
 404 /*
 405  * Compute for a method with pointer parameter(s)
 406  * if they will be read or written.
 407  */
 408 float get_method_param_weight(entity *ent, int pos)
 409 {
 410   type *mtp = get_entity_type(ent);
 411   int  is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 412
 413   assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 414
 415   if (ent->param_weight) {
 416     if (pos < ARR_LEN(ent->param_weight))
 417       return ent->param_weight[pos];
 418     else
 419       return 0.0f;
 420   }
 421
 422   analyze_method_params_weight(ent);
 423
 424   if (pos < ARR_LEN(ent->param_weight))
 425     return ent->param_weight[pos];
 426   else
 427     return 0.0f;
 428 }
 429
 430
 431 /**
 432  * Analyze argument's weight of a given
 433  * ir graph.
 434  *
 435  * @param irg The ir graph to analyze.
 436  */
 437 void analyze_irg_args_weight(ir_graph *irg)
 438 {
 439   entity *ent;
 440
 441   ent = get_irg_entity(irg);
 442   if(! ent)
 443     return;
 444
 445   if(! ent->param_weight)
 446     analyze_method_params_weight(ent);
 447 }