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

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