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_t.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, j, k;
 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                 switch (get_irn_opcode(succ)) {
 345                 case iro_Call:
 346                         if (get_Call_ptr(succ) == arg) {
 347                                 /* the arguments is used as an pointer input for a call,
 348                                    we can probably change an indirect Call into a direct one. */
 349                                 weight += indirect_call_weight;
 350                         }
 351                         break;
 352                 case iro_Cmp:
 353                         /* We have reached a cmp and we must increase the
 354                            weight with the cmp_weight. */
 355                         if (get_Cmp_left(succ) == arg)
 356                                 op = get_Cmp_right(succ);
 357                         else
 358                                 op = get_Cmp_left(succ);
 359
 360                         if (is_irn_constlike(op)) {
 361                                 weight += const_cmp_weight;
 362                         } else
 363                                 weight += cmp_weight;
 364                         break;
 365                 case iro_Cond:
 366                         /* the argument is used for a SwitchCond, a big win */
 367                         weight += const_cmp_weight * get_irn_n_outs(succ);
 368                         break;
 369                 case iro_Id:
 370                         /* when looking backward we might find Id nodes */
 371                         weight += calc_method_param_weight(succ);
 372                         break;
 373                 case iro_Tuple:
 374                         /* unoptimized tuple */
 375                         for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
 376                                 ir_node *pred = get_Tuple_pred(succ, j);
 377                                 if (pred == arg) {
 378                                         /* look for Proj(j) */
 379                                         for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
 380                                                 ir_node *succ_succ = get_irn_out(succ, k);
 381                                                 if (is_Proj(succ_succ)) {
 382                                                         if (get_Proj_proj(succ_succ) == j) {
 383                                                                 /* found */
 384                                                                 weight += calc_method_param_weight(succ_succ);
 385                                                         }
 386                                                 } else {
 387                                                         /* this should NOT happen */
 388                                                 }
 389                                         }
 390                                 }
 391                         }
 392                         break;
 393                 default:
 394                         if (is_binop(succ)) {
 395                                 /* We have reached a BinOp and we must increase the
 396                                    weight with the binop_weight. If the other operand of the
 397                                    BinOp is a constant we increase the weight with const_binop_weight
 398                                    and call the function recursive.
 399                                  */
 400                                 if (get_binop_left(succ) == arg)
 401                                         op = get_binop_right(succ);
 402                                 else
 403                                         op = get_binop_left(succ);
 404
 405                                 if (is_irn_constlike(op)) {
 406                                         weight += const_binop_weight;
 407                                         weight += calc_method_param_weight(succ);
 408                                 } else
 409                                         weight += binop_weight;
 410                         } else if (is_unop(succ)) {
 411                                 /* We have reached a binop and we must increase the
 412                                    weight with the const_binop_weight and call the function recursive.*/
 413                                 weight += const_binop_weight;
 414                                 weight += calc_method_param_weight(succ);
 415                         }
 416                         break;
 417                 }
 418         }
 419         set_irn_link(arg, NULL);
 420         return weight;
 421 }
 422
 423 /**
 424  * Calculate a weight for each argument of an entity.
 425  *
 426  * @param ent  The entity of the ir_graph.
 427  */
 428 static void analyze_method_params_weight(ir_entity *ent) {
 429         ir_type  *mtp;
 430         ir_graph *irg;
 431         int      nparams, i, proj_nr;
 432         ir_node  *irg_args, *arg;
 433
 434         mtp      = get_entity_type(ent);
 435         nparams  = get_method_n_params(mtp);
 436
 437         /* allocate a new array. currently used as 'analysed' flag */
 438         ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
 439
 440         /* If the method haven't parameters we have nothing to do. */
 441         if (nparams <= 0)
 442           return;
 443
 444         /* First we initialize the parameter weights with 0. */
 445         for (i = nparams - 1; i >= 0; i--)
 446                 ent->attr.mtd_attr.param_weight[i] = null_weight;
 447
 448         irg = get_entity_irg(ent);
 449         if (irg == NULL) {
 450                 /* no graph, no better info */
 451                 return;
 452         }
 453
 454         /* Call algorithm that computes the out edges */
 455         assure_irg_outs(irg);
 456
 457         irg_args = get_irg_args(irg);
 458         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 459                 arg     = get_irn_out(irg_args, i);
 460                 proj_nr = get_Proj_proj(arg);
 461                 ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
 462         }
 463
 464 #if 0
 465         printf("\n%s:\n", get_entity_name(ent));
 466         for (i = nparams - 1; i >= 0; --i)
 467                 printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
 468 #endif
 469 }
 470
 471 /*
 472  * Returns for a method the 'weight' that every parameter
 473  * has on optimization possibility. Higher values allows
 474  * higher optimization with procedure cloning.
 475  *
 476  * The values are calculation on demand only.
 477  *
 478  * @param ent  the entity to analyze
 479  * @param pos  the argument number
 480  *
 481  * @return the parameter weight or null_weight if pos is greater
 482  * than the number of arguments.
 483  */
 484 unsigned get_method_param_weight(ir_entity *ent, int pos)
 485 {
 486         if (ent->attr.mtd_attr.param_weight) {
 487                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 488                         return ent->attr.mtd_attr.param_weight[pos];
 489                 else
 490                         return null_weight;
 491         }
 492
 493         analyze_method_params_weight(ent);
 494
 495         if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 496                 return ent->attr.mtd_attr.param_weight[pos];
 497         else
 498                 return null_weight;
 499 }
 500
 501 /**
 502  * Analyze argument's weight of a given
 503  * ir graph.
 504  *
 505  * @param irg The ir graph to analyze.
 506  */
 507 void analyze_irg_args_weight(ir_graph *irg) {
 508         ir_entity *ent;
 509
 510         ent = get_irg_entity(irg);
 511         if (ent == NULL)
 512                 return;
 513
 514         if (! ent->attr.mtd_attr.param_weight)
 515                 analyze_method_params_weight(ent);
 516 }