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  */
  25 #include "config.h"
  26
  27 #include <stdlib.h>
  28
  29 #include "irouts.h"
  30 #include "irnode_t.h"
  31 #include "irmode_t.h"
  32 #include "array_t.h"
  33 #include "irprog.h"
  34 #include "entity_t.h"
  35
  36 #include "analyze_irg_args.h"
  37
  38 /**
  39  * Walk recursive the successors of a graph argument
  40  * with mode reference and mark if it will be read,
  41  * written or stored.
  42  *
  43  * @param arg   The graph argument with mode reference,
  44  *             that must be checked.
  45  */
  46 static ptr_access_kind analyze_arg(ir_node *arg, ptr_access_kind bits)
  47 {
  48         int i, p;
  49         ir_node *succ;
  50
  51         /* We must visit a node once to avoid endless recursion.*/
  52         mark_irn_visited(arg);
  53
  54         for (i = get_irn_n_outs(arg) - 1; i >= 0; --i) {
  55                 succ = get_irn_out(arg, i);
  56
  57                 /* We was here.*/
  58                 if (irn_visited(succ))
  59                         continue;
  60
  61                 /* We should not walk over the memory edge.*/
  62                 if (get_irn_mode(succ) == mode_M)
  63                         continue;
  64
  65                 /* If we reach with the recursion a Call node and our reference
  66                    isn't the address of this Call we accept that the reference will
  67                    be read and written if the graph of the method represented by
  68                    "Call" isn't computed else we analyze that graph. If our
  69                    reference is the address of this
  70                    Call node that mean the reference will be read.*/
  71                 switch (get_irn_opcode(succ)) {
  72
  73                 case iro_Call: {
  74                         ir_node *ptr  = get_Call_ptr(succ);
  75
  76                         if (ptr == arg) {
  77                                 /* Hmm: not sure what this is, most likely a read */
  78                                 bits |= ptr_access_read;
  79                         } else {
  80                                 ir_entity *meth_ent;
  81
  82                                 if (is_SymConst_addr_ent(ptr)) {
  83                                         meth_ent = get_SymConst_entity(ptr);
  84
  85                                         for (p = get_Call_n_params(succ) - 1; p >= 0; --p) {
  86                                                 if (get_Call_param(succ, p) == arg) {
  87                                                         /* an arg can be used more than once ! */
  88                                                         bits |= get_method_param_access(meth_ent, p);
  89                                                 }
  90                                         }
  91                                 } else if (is_Sel(ptr) && get_irp_callee_info_state() == irg_callee_info_consistent) {
  92                                         /* is be a polymorphic call but callee information is available */
  93                                         int n_params = get_Call_n_params(succ);
  94                                         int c;
  95
  96                                         /* simply look into ALL possible callees */
  97                                         for (c = get_Call_n_callees(succ) - 1; c >= 0; --c) {
  98                                                 meth_ent = get_Call_callee(succ, c);
  99
 100                                                 /* unknown_entity is used to signal that we don't know what is called */
 101                                                 if (is_unknown_entity(meth_ent)) {
 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
 239 void analyze_irg_args(ir_graph *irg)
 240 {
 241         ir_entity *ent;
 242
 243         if (irg == get_const_code_irg())
 244                 return;
 245
 246         ent = get_irg_entity(irg);
 247         if (! ent)
 248                 return;
 249
 250         if (! ent->attr.mtd_attr.param_access)
 251                 analyze_ent_args(ent);
 252 }
 253
 254 ptr_access_kind get_method_param_access(ir_entity *ent, size_t pos)
 255 {
 256 #ifndef NDEBUG
 257         ir_type *mtp = get_entity_type(ent);
 258         int is_variadic = get_method_variadicity(mtp) == variadicity_variadic;
 259
 260         assert(is_variadic || pos < get_method_n_params(mtp));
 261 #endif
 262
 263         if (ent->attr.mtd_attr.param_access) {
 264                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
 265                         return ent->attr.mtd_attr.param_access[pos];
 266                 else
 267                         return ptr_access_all;
 268         }
 269
 270         analyze_ent_args(ent);
 271
 272         if (pos < ARR_LEN(ent->attr.mtd_attr.param_access))
 273                 return ent->attr.mtd_attr.param_access[pos];
 274         else
 275                 return ptr_access_all;
 276 }
 277
 278 /* Weights for parameters */
 279 enum args_weight {
 280         null_weight          = 0,   /**< If can't be anything optimized. */
 281         binop_weight         = 1,   /**< If the argument have mode_weight and take part in binop. */
 282         const_binop_weight   = 1,   /**< If the argument have mode_weight and take part in binop with a constant.*/
 283         cmp_weight           = 4,   /**< If the argument take part in cmp. */
 284         const_cmp_weight     = 10,  /**< If the argument take part in cmp with a constant. */
 285         indirect_call_weight = 125, /**< If the argument is the address of an indirect Call. */
 286 };
 287
 288 /**
 289  * Compute the weight of a method parameter
 290  *
 291  * @param arg  The parameter them weight muss be computed.
 292  */
 293 static unsigned calc_method_param_weight(ir_node *arg)
 294 {
 295         int      i, j, k;
 296         ir_node  *succ, *op;
 297         unsigned weight = null_weight;
 298
 299         /* We mark the nodes to avoid endless recursion */
 300         mark_irn_visited(arg);
 301
 302         for (i = get_irn_n_outs(arg) - 1; i >= 0; i--) {
 303                 succ = get_irn_out(arg, i);
 304
 305                 /* We was here.*/
 306                 if (irn_visited(succ))
 307                         continue;
 308
 309                 /* We should not walk over the memory edge.*/
 310                 if (get_irn_mode(succ) == mode_M)
 311                         continue;
 312
 313                 switch (get_irn_opcode(succ)) {
 314                 case iro_Call:
 315                         if (get_Call_ptr(succ) == arg) {
 316                                 /* the arguments is used as an pointer input for a call,
 317                                    we can probably change an indirect Call into a direct one. */
 318                                 weight += indirect_call_weight;
 319                         }
 320                         break;
 321                 case iro_Cmp:
 322                         /* We have reached a cmp and we must increase the
 323                            weight with the cmp_weight. */
 324                         if (get_Cmp_left(succ) == arg)
 325                                 op = get_Cmp_right(succ);
 326                         else
 327                                 op = get_Cmp_left(succ);
 328
 329                         if (is_irn_constlike(op)) {
 330                                 weight += const_cmp_weight;
 331                         } else
 332                                 weight += cmp_weight;
 333                         break;
 334                 case iro_Cond:
 335                         /* the argument is used for a SwitchCond, a big win */
 336                         weight += const_cmp_weight * get_irn_n_outs(succ);
 337                         break;
 338                 case iro_Id:
 339                         /* when looking backward we might find Id nodes */
 340                         weight += calc_method_param_weight(succ);
 341                         break;
 342                 case iro_Tuple:
 343                         /* unoptimized tuple */
 344                         for (j = get_Tuple_n_preds(succ) - 1; j >= 0; --j) {
 345                                 ir_node *pred = get_Tuple_pred(succ, j);
 346                                 if (pred == arg) {
 347                                         /* look for Proj(j) */
 348                                         for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
 349                                                 ir_node *succ_succ = get_irn_out(succ, k);
 350                                                 if (is_Proj(succ_succ)) {
 351                                                         if (get_Proj_proj(succ_succ) == j) {
 352                                                                 /* found */
 353                                                                 weight += calc_method_param_weight(succ_succ);
 354                                                         }
 355                                                 } else {
 356                                                         /* this should NOT happen */
 357                                                 }
 358                                         }
 359                                 }
 360                         }
 361                         break;
 362                 default:
 363                         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                         break;
 386                 }
 387         }
 388         set_irn_link(arg, NULL);
 389         return weight;
 390 }
 391
 392 /**
 393  * Calculate a weight for each argument of an entity.
 394  *
 395  * @param ent  The entity of the ir_graph.
 396  */
 397 static void analyze_method_params_weight(ir_entity *ent)
 398 {
 399         ir_type  *mtp;
 400         ir_graph *irg;
 401         int      nparams, i, proj_nr;
 402         ir_node  *irg_args, *arg;
 403
 404         mtp      = get_entity_type(ent);
 405         nparams  = get_method_n_params(mtp);
 406
 407         /* allocate a new array. currently used as 'analysed' flag */
 408         ent->attr.mtd_attr.param_weight = NEW_ARR_F(unsigned, nparams);
 409
 410         /* If the method haven't parameters we have nothing to do. */
 411         if (nparams <= 0)
 412           return;
 413
 414         /* First we initialize the parameter weights with 0. */
 415         for (i = nparams - 1; i >= 0; i--)
 416                 ent->attr.mtd_attr.param_weight[i] = null_weight;
 417
 418         irg = get_entity_irg(ent);
 419         if (irg == NULL) {
 420                 /* no graph, no better info */
 421                 return;
 422         }
 423
 424         /* Call algorithm that computes the out edges */
 425         assure_irg_outs(irg);
 426
 427         irg_args = get_irg_args(irg);
 428         for (i = get_irn_n_outs(irg_args) - 1; i >= 0; --i) {
 429                 arg     = get_irn_out(irg_args, i);
 430                 proj_nr = get_Proj_proj(arg);
 431                 ent->attr.mtd_attr.param_weight[proj_nr] += calc_method_param_weight(arg);
 432         }
 433 }
 434
 435 unsigned get_method_param_weight(ir_entity *ent, size_t pos)
 436 {
 437         if (ent->attr.mtd_attr.param_weight) {
 438                 if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 439                         return ent->attr.mtd_attr.param_weight[pos];
 440                 else
 441                         return null_weight;
 442         }
 443
 444         analyze_method_params_weight(ent);
 445
 446         if (pos < ARR_LEN(ent->attr.mtd_attr.param_weight))
 447                 return ent->attr.mtd_attr.param_weight[pos];
 448         else
 449                 return null_weight;
 450 }
 451
 452 void analyze_irg_args_weight(ir_graph *irg)
 453 {
 454         ir_entity *entity = get_irg_entity(irg);
 455         if (entity == NULL)
 456                 return;
 457
 458         assert(is_method_entity(entity));
 459         if (entity->attr.mtd_attr.param_weight != NULL)
 460                 return;
 461
 462         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 463         inc_irg_visited(irg);
 464         analyze_method_params_weight(entity);
 465         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 466 }