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 static char v;
  40 static void *VISITED = &v;
  41
  42 /**
  43  * Walk recursive the successors of a graph argument
  44  * with mode reference and mark if it will be read,
  45  * written or stored.
  46  *
  47  * @param arg   The graph argument with mode reference,
  48  *             that must be checked.
  49  */
  50 static unsigned analyze_arg(ir_node *arg, unsigned bits) {
  51         int i, p;
  52         ir_node *succ;
  53
  54         /* We must visit a node once to avoid endless recursion.*/
  55         set_irn_link(arg, VISITED);
  56
  57         for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
  58                 succ = get_irn_out(arg, i);
  59
  60                 /* We was here.*/
  61                 if (get_irn_link(succ) == VISITED)
  62                         continue;
  63
  64                 /* We should not walk over the memory edge.*/
  65                 if (get_irn_mode(succ) == mode_M)
  66                         continue;
  67
  68                 /* If we reach with the recursion a Call node and our reference
  69                    isn't the address of this Call we accept that the reference will
  70                    be read and written if the graph of the method represented by
  71                    "Call" isn't computed else we analyze that graph. If our
  72                    reference is the address of this
  73                    Call node that mean the reference will be read.*/
  74                 switch (get_irn_opcode(succ)) {
  75
  76                 case iro_Call: {
  77                         ir_node *ptr  = get_Call_ptr(succ);
  78
  79                         if (ptr == arg) {
  80                                 /* Hmm: not sure what this is, most likely a read */
  81                                 bits |= ptr_access_read;
  82                         } else {
  83                                 ir_entity *meth_ent;
  84
  85                                 if (is_Global(ptr)) {
  86                                         meth_ent = get_Global_entity(ptr);
  87
  88                                         for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
  89                                                 if (get_Call_param(succ, p) == arg) {
  90                                                         /* an arg can be used more than once ! */
  91                                                         bits |= get_method_param_access(meth_ent, p);
  92                                                 }
  93                                         }
  94                                 } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
  95                                         /* is be a polymorphic call but callee information is available */
  96                                         int i, n_params = get_Call_n_params(succ);
  97
  98                                         /* simply look into ALL possible callees */
  99                                         for (i = get_Call_n_callees(succ) - 1; i >= 0; --i) {
 100                                                 meth_ent = get_Call_callee(succ, i);
 101
 102                                                 /* unknown_entity is used to signal that we don't know what is called */
 103                                                 if (meth_ent == unknown_entity) {
 104                                                         bits |= ptr_access_all;
 105                                                         break;
 106                                                 }
 107
 108                                                 for (p = n_params - 1; p >= 0; --p) {
 109                                                         if (get_Call_param(succ, p) == arg) {
 110                                                                 /* an arg can be used more than once ! */
 111                                                                 bits |= get_method_param_access(meth_ent, p);
 112                                                         }
 113                                                 }
 114                                         }
 115                                 } else /* can do anything */
 116                                         bits |= ptr_access_all;
 117                         }
 118
 119                         /* search stops here anyway */
 120                         continue;
 121                 }
 122                 case iro_Store:
 123                         /* We have reached a Store node => the reference is written or stored. */
 124                         if (get_Store_ptr(succ) == arg) {
 125                                 /* written to */
 126                                 bits |= ptr_access_write;
 127                         } else {
 128                                 /* stored itself */
 129                                 bits |= ptr_access_store;
 130                         }
 131
 132                         /* search stops here anyway */
 133                         continue;
 134
 135                 case iro_Load:
 136                         /* We have reached a Load node => the reference is read. */
 137                         bits |= ptr_access_read;
 138
 139                         /* search stops here anyway */
 140                         continue;
 141
 142                 case iro_Conv:
 143                         /* our address is casted into something unknown. Break our search. */
 144                         bits = ptr_access_all;
 145                         break;
 146
 147                 default:
 148                         break;
 149                 }
 150
 151                 /* If we know that, the argument will be read, write and stored, we
 152                    can break the recursion.*/
 153                 if (bits == ptr_access_all) {
 154                         bits = ptr_access_all;
 155                         break;
 156                 }
 157
 158                 /*
 159                  * A calculation that do not lead to a reference mode ends our search.
 160                  * This is dangerous: It would allow to cast into integer and that cast back ...
 161                  * so, when we detect a Conv we go mad, see the Conv case above.
 162                  */
 163                 if (!mode_is_reference(get_irn_mode(succ)))
 164                         continue;
 165
 166                 /* follow further the address calculation */
 167                 bits = analyze_arg(succ, bits);
 168         }
 169         set_irn_link(arg, NULL);
 170         return bits;
 171 }
 172
 173 /**
 174  * Check if a argument of the ir graph with mode
 175  * reference is read, write or both.
 176  *
 177  * @param irg   The ir graph to analyze.
 178  */
 179 static void analyze_ent_args(ir_entity *ent) {
 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         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, int 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(0 <= pos && (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         int      i, j, k;
 322         ir_node  *succ, *op;
 323         unsigned weight = null_weight;
 324
 325         /* We mark the nodes to avoid endless recursion */
 326         set_irn_link(arg, VISITED);
 327
 328         for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
 329                 succ = get_irn_out(arg, i);
 330
 331                 /* We was here.*/
 332                 if (get_irn_link(succ) == VISITED)
 333                         continue;
 334
 335                 /* We should not walk over the memory edge.*/
 336                 if (get_irn_mode(succ) == mode_M)
 337                         continue;
 338
 339                 switch (get_irn_opcode(succ)) {
 340                 case iro_Call:
 341                         if (get_Call_ptr(succ) == arg) {
 342                                 /* the arguments is used as an pointer input for a call,
 343                                    we can probably change an indirect Call into a direct one. */
 344                                 weight += indirect_call_weight;
 345                         }
 346                         break;
 347                 case iro_Cmp:
 348                         /* We have reached a cmp and we must increase the
 349                            weight with the cmp_weight. */
 350                         if (get_Cmp_left(succ) == arg)
 351                                 op = get_Cmp_right(succ);
 352                         else
 353                                 op = get_Cmp_left(succ);
 354
 355                         if (is_irn_constlike(op)) {
 356                                 weight += const_cmp_weight;
 357                         } else
 358                                 weight += cmp_weight;
 359                         break;
 360                 case iro_Cond:
 361                         /* the argument is used for a SwitchCond, a big win */
 362                         weight += const_cmp_weight * get_irn_n_outs(succ);
 363                         break;
 364                 case iro_Id:
 365                         /* when looking backward we might find Id nodes */
 366                         weight += calc_method_param_weight(succ);
 367                         break;
 368                 case iro_Tuple:
 369                         /* unoptimized tuple */
 370                         for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
 371                                 ir_node *pred = get_Tuple_pred(succ, j);
 372                                 if (pred == arg) {
 373                                         /* look for Proj(j) */
 374                                         for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
 375                                                 ir_node *succ_succ = get_irn_out(succ, k);
 376                                                 if (is_Proj(succ_succ)) {
 377                                                         if (get_Proj_proj(succ_succ) == j) {
 378                                                                 /* found */
 379                                                                 weight += calc_method_param_weight(succ_succ);
 380                                                         }
 381                                                 } else {
 382                                                         /* this should NOT happen */
 383                                                 }
 384                                         }
 385                                 }
 386                         }
 387                         break;
 388                 default:
 389                         if (is_binop(succ)) {
 390                                 /* We have reached a BinOp and we must increase the
 391                                    weight with the binop_weight. If the other operand of the
 392                                    BinOp is a constant we increase the weight with const_binop_weight
 393                                    and call the function recursive.
 394                                  */
 395                                 if (get_binop_left(succ) == arg)
 396                                         op = get_binop_right(succ);
 397                                 else
 398                                         op = get_binop_left(succ);
 399
 400                                 if (is_irn_constlike(op)) {
 401                                         weight += const_binop_weight;
 402                                         weight += calc_method_param_weight(succ);
 403                                 } else
 404                                         weight += binop_weight;
 405                         } else if (is_unop(succ)) {
 406                                 /* We have reached a binop and we must increase the
 407                                    weight with the const_binop_weight and call the function recursive.*/
 408                                 weight += const_binop_weight;
 409                                 weight += calc_method_param_weight(succ);
 410                         }
 411                         break;
 412                 }
 413         }
 414         set_irn_link(arg, NULL);
 415         return weight;
 416 }
 417
 418 /**
 419  * Calculate a weight for each argument of an entity.
 420  *
 421  * @param ent  The entity of the ir_graph.
 422  */
 423 static void analyze_method_params_weight(ir_entity *ent) {
 424         ir_type  *mtp;
 425         ir_graph *irg;
 426         int      nparams, i, proj_nr;
 427         ir_node  *irg_args, *arg;
 428
 429         mtp      = get_entity_type(ent);
 430         nparams  = get_method_n_params(mtp);
 431
 432         /* allocate a new array. currently used as 'analysed' flag */
 433         ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
 434
 435         /* If the method haven't parameters we have nothing to do. */
 436         if (nparams <= 0)
 437           return;
 438
 439         /* First we initialize the parameter weights with 0. */
 440         for (i = nparams - 1; i >= 0; i--)
 441                 ent->attr.mtd_attr.param_weight[i] = null_weight;
 442
 443         irg = get_entity_irg(ent);
 444         if (irg == NULL) {
 445                 /* no graph, no better info */
 446                 return;
 447         }
 448
 449         /* Call algorithm that computes the out edges */
 450         assure_irg_outs(irg);
 451
 452         irg_args = get_irg_args(irg);
 453         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 454                 arg     = get_irn_out(irg_args, i);
 455                 proj_nr = get_Proj_proj(arg);
 456                 ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
 457         }
 458
 459 #if 0
 460         printf("\n%s:\n", get_entity_name(ent));
 461         for (i = nparams - 1; i >= 0; --i)
 462                 printf("The weight of argument %i is %f \n", i, ent->param_weight[i]);
 463 #endif
 464 }
 465
 466 /*
 467  * Returns for a method the 'weight' that every parameter
 468  * has on optimization possibility. Higher values allows
 469  * higher optimization with procedure cloning.
 470  *
 471  * The values are calculation on demand only.
 472  *
 473  * @param ent  the entity to analyze
 474  * @param pos  the argument number
 475  *
 476  * @return the parameter weight or null_weight if pos is greater
 477  * than the number of arguments.
 478  */
 479 unsigned get_method_param_weight(ir_entity *ent, int pos)
 480 {
 481         if (ent->attr.mtd_attr.param_weight) {
 482                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 483                         return ent->attr.mtd_attr.param_weight[pos];
 484                 else
 485                         return null_weight;
 486         }
 487
 488         analyze_method_params_weight(ent);
 489
 490         if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 491                 return ent->attr.mtd_attr.param_weight[pos];
 492         else
 493                 return null_weight;
 494 }
 495
 496 /**
 497  * Analyze argument's weight of a given
 498  * ir graph.
 499  *
 500  * @param irg The ir graph to analyze.
 501  */
 502 void analyze_irg_args_weight(ir_graph *irg) {
 503         ir_entity *ent;
 504
 505         ent = get_irg_entity(irg);
 506         if (ent == NULL)
 507                 return;
 508
 509         if (! ent->attr.mtd_attr.param_weight)
 510                 analyze_method_params_weight(ent);
 511 }