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

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