nsz Git - libfirm/blob - ir/ana/interval_analysis.c

   1 /*
   2  * Copyright (C) 1995-2007 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   Implementation of interval analysis
  23  * @version $Id$
  24  */
  25 #ifdef HAVE_CONFIG_H
  26 #include "config.h"
  27 #endif
  28
  29 #ifdef HAVE_STRING_H
  30 #include <string.h>
  31 #endif
  32
  33 #include "interval_analysis.h"
  34 #include "execution_frequency.h"
  35 #include "firm_common_t.h"
  36 #include "set.h"
  37 #include "array.h"
  38
  39 #include "irloop.h"
  40 #include "irnode.h"
  41 #include "irdump_t.h"
  42 #include "irdom.h"
  43 #include "irflag.h"
  44 #include "irprintf.h"
  45 #include "hashptr.h"
  46
  47 /*------------------------------------------------------------------*/
  48 /* A new in array via a hashmap. */
  49 /* The in array refers to the loop the block is contained in if the */
  50 /* block is not in blocks loop. */
  51 /*------------------------------------------------------------------*/
  52
  53 typedef struct {
  54   void *reg;
  55   void **in_array;
  56   void **op_array;
  57   int n_outs;
  58   int n_exc_outs;
  59 } region_attr;
  60
  61 static set *region_attr_set = NULL;
  62
  63 int region_attr_cmp(const void *e1, const void *e2, size_t size) {
  64   region_attr *ra1 = (region_attr *)e1;
  65   region_attr *ra2 = (region_attr *)e2;
  66   return (ra1->reg != ra2->reg);
  67 }
  68
  69 static INLINE int attr_set_hash(region_attr *a) {
  70   return HASH_PTR(a->reg);
  71 }
  72
  73 static INLINE region_attr *get_region_attr(void *region) {
  74   region_attr r_attr, *res;
  75   r_attr.reg = region;
  76
  77   res = set_find(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
  78
  79   if (!res) {
  80     r_attr.in_array = NEW_ARR_F(void *, 0);
  81     if (is_ir_loop(region))
  82       r_attr.op_array = NEW_ARR_F(void *, 0);
  83     else
  84       r_attr.op_array = NULL;
  85     r_attr.n_outs = 0;
  86     r_attr.n_exc_outs = 0;
  87     res = set_insert(region_attr_set, &r_attr, sizeof(r_attr), attr_set_hash(&r_attr));
  88   }
  89
  90   return res;
  91 }
  92
  93 int get_region_n_ins(void *region) {
  94   return ARR_LEN(get_region_attr(region)->in_array);
  95 }
  96
  97 void *get_region_in(void *region, int pos) {
  98   assert(0 <= pos && pos < get_region_n_ins(region));
  99   return ((get_region_attr(region)->in_array)[pos]);
 100 }
 101
 102 void add_region_in (void *region, void *in) {
 103   ARR_APP1(void *, get_region_attr(region)->in_array, in);
 104   get_region_attr(in)->n_outs++;
 105 }
 106
 107 int get_region_n_outs(void *region) {
 108   return get_region_attr(region)->n_outs;
 109 }
 110
 111 int get_region_n_exc_outs(void *region) {
 112   return get_region_attr(region)->n_exc_outs;
 113 }
 114
 115 void inc_region_n_exc_outs(void *region) {
 116   (get_region_attr(region)->n_exc_outs)++;
 117 }
 118
 119 void *get_loop_cfop(void *region, int pos) {
 120   assert(0 <= pos && pos < get_region_n_ins(region));
 121   return ((get_region_attr(region)->op_array)[pos]);
 122 }
 123
 124 void add_loop_cfop (void *region, void *cfop) {
 125   assert(cfop);
 126   ARR_APP1(void *, get_region_attr(region)->op_array, cfop);
 127 }
 128
 129 static INLINE void exc_outs(void *reg, ir_node *cfop) {
 130   if (is_fragile_op(cfop) || (is_fragile_Proj(cfop)))
 131     inc_region_n_exc_outs(reg);
 132 }
 133
 134 /*------------------------------------------------------------------*/
 135 /* Algorithm to construct the interval edges based on a loop tree. */
 136 /* Walk a loop and add all edges.  Walk inner loops by recursion. */
 137 /*------------------------------------------------------------------*/
 138
 139 /* return non-zero if outer can be reached from inner via the outer loop relation */
 140 static int find_outer_loop(ir_loop *inner, ir_loop *outer, ir_node *b, ir_node *cfop) {
 141   if (get_loop_outer_loop(inner) == outer) {
 142     add_region_in(inner, b);
 143     add_loop_cfop(inner, cfop);
 144     exc_outs(b, cfop);
 145     return 1;
 146   }
 147   return 0;
 148 }
 149
 150 static int test_loop_nest(ir_node *pred_b, ir_loop *nest) {
 151   int i, n_elems = get_loop_n_elements(nest);
 152
 153   for (i = 0; (i < n_elems); ++i) {
 154     loop_element e = get_loop_element(nest, i);
 155     switch (*e.kind) {
 156     case k_ir_node: {
 157       if (e.node == pred_b) return 1;
 158     } break;
 159     case k_ir_loop: {
 160       if (test_loop_nest(pred_b, e.son)) return 1;
 161     } break;
 162     default: break;
 163     }
 164   }
 165   return 0;
 166 }
 167
 168 static int find_inner_loop(ir_node *b, ir_loop *l, ir_node *pred, ir_node *cfop) {
 169   int i, n_elems = get_loop_n_elements(l);
 170   int found = 0;
 171
 172   for (i = 0; (i < n_elems) && !found; ++i) {
 173     loop_element e = get_loop_element(l, i);
 174     switch (*e.kind) {
 175     case k_ir_node: {
 176       if (e.node == b) return 0;
 177     } break;
 178     case k_ir_loop: {
 179       found = test_loop_nest(pred, e.son);
 180       if (found) {
 181         add_region_in(b, e.son);
 182         exc_outs(e.son, cfop);
 183         //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
 184         return found;
 185       }
 186     } break;
 187     default: break;
 188     }
 189   }
 190   return found;
 191 }
 192
 193
 194 static int find_previous_loop(ir_loop *l, ir_loop *pred_l, ir_node *b, ir_node *pred_b, ir_node *cfop) {
 195   ir_loop *outer = get_loop_outer_loop(l);
 196   int found, i;
 197   int l_pos = get_loop_element_pos(outer, l);
 198   assert(l_pos > -1);
 199   assert(l_pos > 0 && "Is this a necessary condition?  There could be a perfect nest ...");
 200
 201   for (i = l_pos -1, found = 0; i > -1 && !found; --i) {
 202     ir_loop *k = get_loop_element(outer, i).son;
 203     if (is_ir_loop(k)) {
 204       found = test_loop_nest(pred_b, k);
 205       if (found) {
 206         add_region_in(l, k);
 207         //if (is_fragile_op(cfop)) inc_region_n_exc_outs(k);
 208         exc_outs(k, cfop);
 209         add_loop_cfop(l, cfop);
 210         add_region_in(b, NULL);
 211       }
 212     }
 213   }
 214
 215   return found;
 216 }
 217
 218
 219 /**
 220  * Compute the edges for the interval graph.
 221  *
 222  * @param b The block for which to construct the edges.
 223  * @param l The loop of b.
 224  *
 225  * There are four cases:
 226  * - The pred block is in the same loop.  Add a normal block-block edge.
 227  * - The pred block is in a loop contained in this loop, somewhere down in
 228  *   the nesting. The predecessor of this block is the outermost loop of the nest
 229  *   directly contained in l.
 230  * - The pred block is in the outer loop of l.  l gets an edge to the pred block.
 231  * - The outer loop of l contains another loop k just before l.  The control flow
 232  *   branches directly from loop k to loop l.  Add an edge l->k.  Watch it: k must
 233  *   not be a direct predecessor of l in the loop tree!
 234  */
 235 static void construct_interval_block(ir_node *b, ir_loop *l) {
 236   int i, n_cfgpreds = get_Block_n_cfgpreds(b);
 237
 238   if (b == get_irg_start_block(current_ir_graph)) return;
 239   /* We want nice blocks. */
 240   assert(n_cfgpreds > 0);
 241
 242   for (i = 0; i < n_cfgpreds; ++i) {
 243     ir_node *cfop, *pred;
 244     ir_loop *pred_l;
 245
 246     if (is_backedge(b, i)) {
 247       if (b != get_loop_element(l, 0).node) {
 248         if (get_firm_verbosity()) {
 249                 ir_printf("Loophead not at loop position 0. %+F\n", b);
 250         }
 251       }
 252       /* There are no backedges in the interval decomposition. */
 253       add_region_in(b, NULL);
 254       continue;
 255     }
 256
 257     cfop = get_Block_cfgpred(b, i);
 258     if (is_Proj(cfop)) {
 259       if (get_irn_op(get_Proj_pred(cfop)) != op_Cond) {
 260         cfop = skip_Proj(cfop);
 261       } else {
 262         assert(get_nodes_block(cfop) == get_nodes_block(skip_Proj(cfop)));
 263       }
 264     }
 265
 266     pred = skip_Proj(get_nodes_block(cfop));
 267     /* We want nice blocks. */
 268     assert(   get_irn_op(pred) != op_Bad
 269            && get_irn_op(skip_Proj(get_Block_cfgpred(b, i))) != op_Bad);
 270     pred_l = get_irn_loop(pred);
 271     if (pred_l == l) {
 272       add_region_in(b, pred);
 273       //if (is_fragile_op(cfop)) inc_region_n_exc_outs(b);
 274       exc_outs(pred, cfop);
 275     } else {
 276       int found = find_inner_loop(b, l, pred, cfop);
 277       if (!found) {
 278             if (b != get_loop_element(l, 0).node) {
 279               if (get_firm_verbosity()) {
 280                 ir_printf("Loop entry not at loop position 0. %+F\n", b);
 281               }
 282             }
 283             found = find_outer_loop(l, pred_l, pred, cfop);
 284             if (found) add_region_in(b, NULL);  /* placeholder */
 285       }
 286       if (!found) {
 287         found = find_previous_loop(l, pred_l, b, pred, cfop);
 288       }
 289       if (!found) {
 290             assert(is_backedge(b, i));
 291             assert(found && "backedge from inner loop");
 292       }
 293     }
 294
 295     if (b != get_loop_element(l, 0).node) {
 296       /* Check for improper region */
 297       if (has_backedges(b)) {
 298             ir_fprintf(stderr, "Improper Region!!!!!! %+F\n", b);
 299       }
 300     }
 301   }
 302 }
 303
 304 static void construct_interval_edges(ir_loop *l) {
 305   int i, n_elems = get_loop_n_elements(l);
 306   for (i = 0; i < n_elems; ++i) {
 307     loop_element e = get_loop_element(l, i);
 308     switch (*e.kind) {
 309     case k_ir_node: {
 310       construct_interval_block(e.node, l);
 311     } break;
 312     case k_ir_loop: {
 313       construct_interval_edges(e.son);
 314     } break;
 315     default: break;
 316     }
 317   }
 318 }
 319
 320 void construct_intervals(ir_graph *irg) {
 321   ir_loop *l;
 322   ir_graph *rem = current_ir_graph;
 323   current_ir_graph = irg;
 324
 325   if (!region_attr_set)
 326     region_attr_set = new_set(region_attr_cmp, 256);
 327
 328   construct_cf_backedges(current_ir_graph);
 329
 330   l = get_irg_loop(current_ir_graph);
 331
 332   construct_interval_edges(l);
 333
 334   current_ir_graph = rem;
 335 }
 336
 337 void free_intervals(void) {
 338   //void **ins;
 339   if (!region_attr_set) return;
 340   /* @@@ mem leak
 341   for (ins = (void **)pmap_first(region_in_map);
 342        ins;
 343        ins = (void **)pmap_next(region_in_map)) {
 344     //DEL_ARR_F(ins);
 345   }
 346   */
 347   del_set(region_attr_set);
 348   region_attr_set = NULL;
 349 }
 350
 351 /*------------------------------------------------------------------*/
 352 /* A vcg dumper showing an interval decomposition of a cfg.         */
 353 /*                                                                  */
 354 /*------------------------------------------------------------------*/
 355
 356 void dump_region_edges(FILE *F, void *reg) {
 357   int i, n_ins = get_region_n_ins(reg);
 358
 359   if (is_ir_node(reg) && get_Block_n_cfgpreds((ir_node *)reg) > get_region_n_ins(reg)) {
 360     for (i = n_ins; i < get_Block_n_cfgpreds((ir_node *)reg); ++i) {
 361       if (is_backedge((ir_node *)reg, i))
 362         fprintf (F, "backedge: { sourcename: \"");
 363       else
 364         fprintf (F, "edge: { sourcename: \"");
 365       PRINT_NODEID(((ir_node *)reg));
 366       fprintf (F, "\" targetname: \"");
 367       PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
 368       fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
 369     }
 370   }
 371
 372   for (i = 0; i < n_ins; ++i) {
 373     void *target = get_region_in(reg, i);
 374
 375     if (is_ir_node(reg)) {
 376       if (get_Block_n_cfgpreds((ir_node *)reg) != get_region_n_ins(reg)) {
 377         ir_printf("n_cfgpreds = %d, n_ins = %d\n %+F\n", get_Block_n_cfgpreds((ir_node *)reg), get_region_n_ins(reg), (ir_node*) reg);
 378       }
 379     }
 380
 381     if ((!target || (is_ir_node(reg) && !is_ir_node(target))) && i < get_Block_n_cfgpreds((ir_node *)reg)) {
 382       assert(is_ir_node(reg));
 383       if (is_backedge((ir_node *)reg, i))
 384         fprintf (F, "backedge: { sourcename: \"");
 385       else
 386         fprintf (F, "edge: { sourcename: \"");
 387       PRINT_NODEID(((ir_node *)reg));
 388       fprintf (F, "\" targetname: \"");
 389       PRINT_NODEID(get_nodes_block(skip_Proj(get_Block_cfgpred((ir_node *)reg, i))));
 390       fprintf (F, "\" " BLOCK_EDGE_ATTR "}\n");
 391
 392       if (!target) continue;
 393     }
 394
 395     fprintf (F, "edge: { sourcename: \"");
 396     if (is_ir_node(reg)) {
 397       PRINT_NODEID(((ir_node *)reg));
 398     } else {
 399       PRINT_LOOPID(((ir_loop *)reg));
 400     }
 401     fprintf (F, "\" targetname: \"");
 402     if (is_ir_node(target)) {
 403       PRINT_NODEID(((ir_node *)target));
 404     } else {
 405       PRINT_LOOPID(((ir_loop *)target));
 406     }
 407     fprintf (F, "\"");
 408     if (is_ir_node(reg) && is_fragile_op(skip_Proj(get_Block_cfgpred(reg, i))))
 409       fprintf(F, EXC_CF_EDGE_ATTR);
 410     fprintf (F, "}\n");
 411   }
 412 }
 413
 414 #include "execution_frequency.h"
 415
 416 void dump_interval_block(FILE *F, ir_node *block) {
 417   int i, fl;
 418   /* This is a block. Dump a node for the block. */
 419   fprintf (F, "node: {title: \""); PRINT_NODEID(block);
 420   fprintf (F, "\" label: \"");
 421   if (block == get_irg_start_block(get_irn_irg(block)))
 422     fprintf(F, "Start ");
 423   if (block == get_irg_end_block(get_irn_irg(block)))
 424     fprintf(F, "End ");
 425
 426   fprintf (F, "%s ", get_op_name(get_irn_op(block)));
 427   PRINT_NODEID(block);
 428   fprintf(F, " freq: %9.4lf", get_region_exec_freq(block));
 429   fprintf(F, " n_outs: %d", get_region_n_outs(block));
 430   fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(block));
 431   fprintf (F, "\" ");
 432   fprintf(F, "info1:\"");
 433   if (dump_dominator_information_flag)
 434     fprintf(F, "dom depth %d\n", get_Block_dom_depth(block));
 435
 436   /* show arity and possible Bad predecessors of the block */
 437   fprintf(F, "arity: %d\n", get_Block_n_cfgpreds(block));
 438   for (fl = i = 0; i < get_Block_n_cfgpreds(block); ++i) {
 439     ir_node *pred = get_Block_cfgpred(block, i);
 440     if (is_Bad(pred)) {
 441       if (! fl)
 442         fprintf(F, "Bad pred at pos: ");
 443       fprintf(F, "%d ", i);
 444       fl = 1;
 445     }
 446   }
 447   if (fl)
 448     fprintf(F, "\n");
 449
 450   fprintf (F, "\"");  /* closing quote of info */
 451
 452   if ((block == get_irg_start_block(get_irn_irg(block))) ||
 453       (block == get_irg_end_block(get_irn_irg(block)))     )
 454     fprintf(F, " color:blue ");
 455   else if (fl)
 456     fprintf(F, " color:yellow ");
 457
 458   fprintf (F, "}\n");
 459 }
 460
 461 void dump_interval_loop(FILE *F, ir_loop *l) {
 462   int i, n_elems = get_loop_n_elements(l);
 463
 464   fprintf(F, "graph: { title: \"");
 465   PRINT_LOOPID(l);
 466   fprintf(F, "\" label: \"loop %d", get_loop_loop_nr(l));
 467   fprintf(F, " freq: %9.4lf", get_region_exec_freq(l));
 468   fprintf(F, " n_outs: %d", get_region_n_outs(l));
 469   fprintf(F, " n_exc_outs: %d", get_region_n_exc_outs(l));
 470   fprintf(F, "\" status:clustered color:white \n");
 471
 472   for (i = 0; i < n_elems; ++i) {
 473     loop_element e = get_loop_element(l, i);
 474     dump_region_edges(F, e.node);
 475     switch (*e.kind) {
 476     case k_ir_node: {
 477       dump_interval_block(F, e.node);
 478     } break;
 479     case k_ir_loop: {
 480       dump_interval_loop(F, e.son);
 481     } break;
 482     default: break;
 483     }
 484   }
 485
 486   fprintf(F, "}\n\n");
 487 }
 488
 489
 490 void dump_interval_graph(ir_graph *irg, const char *suffix) {
 491   FILE *f;
 492
 493   if (!is_filtered_dump_name(get_entity_ident(get_irg_entity(irg))))
 494     return;
 495
 496   f = vcg_open(irg, suffix, "-intervals");
 497   dump_vcg_header(f, get_irg_dump_name(irg), NULL);
 498
 499   current_ir_graph = irg;
 500
 501   dump_interval_loop(f, get_irg_loop(current_ir_graph));
 502
 503   vcg_close(f);
 504 }