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