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         int i, p;
  57         ir_node *succ;
  58
  59         /* We must visit a node once to avoid endless recursion.*/
  60         set_irn_link(arg, VISITED);
  61
  62         for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
  63                 succ = get_irn_out(arg, i);
  64
  65                 /* We was here.*/
  66                 if (get_irn_link(succ) == VISITED)
  67                         continue;
  68
  69                 /* We should not walk over the memory edge.*/
  70                 if (get_irn_mode(succ) == mode_M)
  71                         continue;
  72
  73                 /* If we reach with the recursion a Call node and our reference
  74                    isn't the address of this Call we accept that the reference will
  75                    be read and written if the graph of the method represented by
  76                    "Call" isn't computed else we analyze that graph. If our
  77                    reference is the address of this
  78                    Call node that mean the reference will be read.*/
  79                 switch (get_irn_opcode(succ)) {
  80
  81                 case iro_Call: {
  82                         ir_node *ptr  = get_Call_ptr(succ);
  83
  84                         if (ptr == arg) {
  85                                 /* Hmm: not sure what this is, most likely a read */
  86                                 bits |= ptr_access_read;
  87                         } else {
  88                                 ir_entity *meth_ent;
  89
  90                                 if (is_Global(ptr)) {
  91                                         meth_ent = get_Global_entity(ptr);
  92
  93                                         for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
  94                                                 if (get_Call_param(succ, p) == arg) {
  95                                                         /* an arg can be used more than once ! */
  96                                                         bits |= get_method_param_access(meth_ent, p);
  97                                                 }
  98                                         }
  99                                 } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
 100                                         /* is be a polymorphic call but callee information is available */
 101                                         int i, n_params = get_Call_n_params(succ);
 102
 103                                         /* simply look into ALL possible callees */
 104                                         for (i = get_Call_n_callees(succ) - 1; i >= 0; --i) {
 105                                                 meth_ent = get_Call_callee(succ, i);
 106
 107                                                 /* unknown_entity is used to signal that we don't know what is called */
 108                                                 if (meth_ent == unknown_entity) {
 109                                                         bits |= ptr_access_all;
 110                                                         break;
 111                                                 }
 112
 113                                                 for (p = n_params - 1; p >= 0; --p) {
 114                                                         if (get_Call_param(succ, p) == arg) {
 115                                                                 /* an arg can be used more than once ! */
 116                                                                 bits |= get_method_param_access(meth_ent, p);
 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                         } else {
 133                                 /* stored itself */
 134                                 bits |= ptr_access_store;
 135                         }
 136
 137                         /* search stops here anyway */
 138                         continue;
 139
 140                 case iro_Load:
 141                         /* We have reached a Load node => the reference is read. */
 142                         bits |= ptr_access_read;
 143
 144                         /* search stops here anyway */
 145                         continue;
 146
 147                 case iro_Conv:
 148                         /* our address is casted into something unknown. Break our search. */
 149                         bits = ptr_access_all;
 150                         break;
 151
 152                 default:
 153                         break;
 154                 }
 155
 156                 /* If we know that, the argument will be read, write and stored, we
 157                    can break the recursion.*/
 158                 if (bits == ptr_access_all) {
 159                         bits = ptr_access_all;
 160                         break;
 161                 }
 162
 163                 /*
 164                  * A calculation that do not lead to a reference mode ends our search.
 165                  * This is dangerous: It would allow to cast into integer and that cast back ...
 166                  * so, when we detect a Conv we go mad, see the Conv case above.
 167                  */
 168                 if (!mode_is_reference(get_irn_mode(succ)))
 169                         continue;
 170
 171                 /* follow further the address calculation */
 172                 bits = analyze_arg(succ, bits);
 173         }
 174         set_irn_link(arg, NULL);
 175         return bits;
 176 }
 177
 178 /**
 179  * Check if a argument of the ir graph with mode
 180  * reference is read, write or both.
 181  *
 182  * @param irg   The ir graph to analyze.
 183  */
 184 static void analyze_ent_args(ir_entity *ent) {
 185         ir_graph *irg;
 186         ir_node *irg_args, *arg;
 187         ir_mode *arg_mode;
 188         int nparams, i;
 189         long proj_nr;
 190         ir_type *mtp;
 191         ptr_access_kind *rw_info;
 192
 193         mtp     = get_entity_type(ent);
 194         nparams = get_method_n_params(mtp);
 195
 196         ent->attr.mtd_attr.param_access = NEW_ARR_F(ptr_access_kind, nparams);
 197
 198         /* If the method haven't parameters we have
 199          * nothing to do.
 200          */
 201         if (nparams <= 0)
 202                 return;
 203
 204         irg = get_entity_irg(ent);
 205
 206   /* we have not yet analyzed the graph, set ALL access for pointer args */
 207         for (i = nparams - 1; i >= 0; --i) {
 208                 ir_type *type = get_method_param_type(mtp, i);
 209                 ent->attr.mtd_attr.param_access[i] = is_Pointer_type(type) ? ptr_access_all : ptr_access_none;
 210         }
 211
 212         if (! irg) {
 213                 /* no graph, no better info */
 214                 return;
 215         }
 216
 217         assure_irg_outs(irg);
 218
 219         irg_args = get_irg_args(irg);
 220
 221         /* A array to save the information for each argument with
 222            mode reference.*/
 223         NEW_ARR_A(ptr_access_kind, rw_info, nparams);
 224
 225         /* We initialize the element with none state. */
 226         for (i = nparams - 1; i >= 0; --i)
 227                 rw_info[i] = ptr_access_none;
 228
 229         /* search for arguments with mode reference
 230            to analyze them.*/
 231         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 232                 arg      = get_irn_out(irg_args, i);
 233                 arg_mode = get_irn_mode(arg);
 234                 proj_nr  = get_Proj_proj(arg);
 235
 236                 if (mode_is_reference(arg_mode))
 237                         rw_info[proj_nr] |= analyze_arg(arg, rw_info[proj_nr]);
 238         }
 239
 240         /* copy the temporary info */
 241         memcpy(ent->attr.mtd_attr.param_access, rw_info,
 242                 nparams * sizeof(ent->attr.mtd_attr.param_access[0]));
 243
 244 #if 0
 245         printf("\n%s:\n", get_entity_name(ent));
 246         for (i = 0; i < nparams; ++i) {
 247                 if (is_Pointer_type(get_method_param_type(mtp, i)))
 248                         if (ent->attr.mtd_attr.param_access[i] != ptr_access_none) {
 249                                 printf("  Pointer Arg %d access: ", i);
 250                                 if (ent->attr.mtd_attr.param_access[i] & ptr_access_read)
 251                                         printf("READ ");
 252                                 if (ent->attr.mtd_attr.param_access[i] & ptr_access_write)
 253                                         printf("WRITE ");
 254                                 if (ent->attr.mtd_attr.param_access[i] & ptr_access_store)
 255                                         printf("STORE ");
 256                                 printf("\n");
 257                         }
 258         }
 259 #endif
 260 }
 261
 262 /**
 263  * Analyze how pointer arguments of a given
 264  * ir graph are accessed.
 265  *
 266  * @param irg   The ir graph to analyze.
 267  */
 268 void analyze_irg_args(ir_graph *irg) {
 269         ir_entity *ent;
 270
 271         if (irg == get_const_code_irg())
 272                 return;
 273
 274         ent = get_irg_entity(irg);
 275         if (! ent)
 276                 return;
 277
 278         if (! ent->attr.mtd_attr.param_access)
 279                 analyze_ent_args(ent);
 280 }
 281
 282 /*
 283  * Compute for a method with pointer parameter(s)
 284  * if they will be read or written.
 285  */
 286 ptr_access_kind get_method_param_access(ir_entity *ent, int pos)
 287 {
 288 #ifndef NDEBUG
 289         ir_type *mtp = get_entity_type(ent);
 290         int is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 291
 292         assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 293 #endif
 294
 295         if (ent->attr.mtd_attr.param_access) {
 296                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
 297                         return ent->attr.mtd_attr.param_access[pos];
 298                 else
 299                         return ptr_access_all;
 300         }
 301
 302         analyze_ent_args(ent);
 303
 304         if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
 305                 return ent->attr.mtd_attr.param_access[pos];
 306         else
 307                 return ptr_access_all;
 308 }
 309
 310 /* Weights for parameters */
 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         indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */
 318 };
 319
 320 /**
 321  * Compute the weight of a method parameter
 322  *
 323  * @param arg  The parameter them weight muss be computed.
 324  */
 325 static unsigned calc_method_param_weight(ir_node *arg) {
 326         int      i;
 327         ir_node  *succ, *op;
 328         unsigned 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                 if (is_Call(succ) && get_Call_ptr(succ) == arg) {
 345                         /* the arguments is used as an pointer input for a call,
 346                            we can probably change an indirect Call into a direct one. */
 347                         weight += indirect_call_weight;
 348                 } else if (is_Cmp(succ)) {
 349                         /* We have reached a cmp and we must increase the
 350                            weight with the cmp_weight. */
 351                         if (get_Cmp_left(succ) == arg)
 352                                 op = get_Cmp_right(succ);
 353                         else
 354                                 op = get_Cmp_left(succ);
 355
 356                         if (is_irn_constlike(op)) {
 357                                 weight += const_cmp_weight;
 358                         } else
 359                                 weight += cmp_weight;
 360                 } else if (is_Cond(succ)) {
 361                         /* the argument is used for a SwitchCond, a big win */
 362                         weight += const_cmp_weight * get_irn_n_outs(succ);
 363                 } else if (is_binop(succ)) {
 364                         /* We have reached a BinOp and we must increase the
 365                            weight with the binop_weight. If the other operand of the
 366                            BinOp is a constant we increase the weight with const_binop_weight
 367                            and call the function recursive.
 368                          */
 369                         if (get_binop_left(succ) == arg)
 370                                 op = get_binop_right(succ);
 371                         else
 372                                 op = get_binop_left(succ);
 373
 374                         if (is_irn_constlike(op)) {
 375                                 weight += const_binop_weight;
 376                                 weight += calc_method_param_weight(succ);
 377                         } else
 378                                 weight += binop_weight;
 379                 } else if (is_unop(succ)) {
 380                         /* We have reached a binop and we must increase the
 381                            weight with the const_binop_weight and call the function recursive.*/
 382                         weight += const_binop_weight;
 383                         weight += calc_method_param_weight(succ);
 384                 }
 385         }
 386         set_irn_link(arg, NULL);
 387         return weight;
 388 }
 389
 390 /**
 391  * Calculate a weight for each argument of an entity.
 392  *
 393  * @param ent  The entity of the ir_graph.
 394  */
 395 static void analyze_method_params_weight(ir_entity *ent) {
 396         ir_type  *mtp;
 397         ir_graph *irg;
 398         int      nparams, i, proj_nr;
 399         ir_node  *irg_args, *arg;
 400
 401         mtp      = get_entity_type(ent);
 402         nparams  = get_method_n_params(mtp);
 403
 404         /* allocate a new array. currently used as 'analysed' flag */
 405         ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
 406
 407         /* If the method haven't parameters we have nothing to do. */
 408         if (nparams <= 0)
 409           return;
 410
 411         /* First we initialize the parameter weights with 0. */
 412         for (i = nparams - 1; i >= 0; i--)
 413                 ent->attr.mtd_attr.param_weight[i] = null_weight;
 414
 415         irg = get_entity_irg(ent);
 416         if (irg == NULL) {
 417                 /* no graph, no better info */
 418                 return;
 419         }
 420
 421         /* Call algorithm that computes the out edges */
 422         assure_irg_outs(irg);
 423
 424         irg_args = get_irg_args(irg);
 425
 426         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 427                 arg     = get_irn_out(irg_args, i);
 428                 proj_nr = get_Proj_proj(arg);
 429                 ent->attr.mtd_attr.param_weight[proj_nr]  += calc_method_param_weight(arg);
 430         }
 431
 432 #if 0
 433         printf("\n%s:\n", get_entity_name(ent));
 434         for (i = nparams - 1; i >= 0; --i)
 435                 printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
 436 #endif
 437 }
 438
 439 /*
 440  * Returns for a method the 'weight' that every parameter
 441  * has on optimization possibility. Higher values allows
 442  * higher optimization with procedure cloning.
 443  *
 444  * The values are calculation on demand only.
 445  */
 446 unsigned get_method_param_weight(ir_entity *ent, int pos)
 447 {
 448 #ifndef NDEBUG
 449         ir_type *mtp = get_entity_type(ent);
 450         int     is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 451         assert(0 <= pos && (is_variadic || pos < get_method_n_params(mtp)));
 452 #endif
 453
 454         if (ent->attr.mtd_attr.param_weight) {
 455                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 456                         return ent->attr.mtd_attr.param_weight[pos];
 457                 else
 458                         return null_weight;
 459         }
 460
 461         analyze_method_params_weight(ent);
 462
 463         if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 464                 return ent->attr.mtd_attr.param_weight[pos];
 465         else
 466                 return null_weight;
 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         ir_entity *ent;
 477
 478         ent = get_irg_entity(irg);
 479         if (ent == NULL)
 480                 return;
 481
 482         if (! ent->attr.mtd_attr.param_weight)
 483                 analyze_method_params_weight(ent);
 484 }