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