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