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