nsz Git - libfirm/blob - ir/be/beirgmod.c

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #include <stdlib.h>
   6
   7 #ifdef HAVE_MALLOC_H
   8  #include <malloc.h>
   9 #endif
  10 #ifdef HAVE_ALLOCA_H
  11  #include <alloca.h>
  12 #endif
  13
  14 #include "hashptr.h"
  15 #include "pdeq.h"
  16 #include "pset.h"
  17 #include "pmap.h"
  18 #include "util.h"
  19 #include "debug.h"
  20
  21 #include "irflag_t.h"
  22 #include "ircons_t.h"
  23 #include "irnode_t.h"
  24 #include "ircons_t.h"
  25 #include "irmode_t.h"
  26 #include "irdom_t.h"
  27 #include "iredges_t.h"
  28 #include "irgopt.h"
  29
  30 #include "be_t.h"
  31 #include "bearch.h"
  32 #include "besched_t.h"
  33 #include "belive_t.h"
  34 #include "benode_t.h"
  35 #include "beutil.h"
  36
  37 #include "beirgmod.h"
  38
  39 #define DBG_MODULE "firm.be.irgmod"
  40 #define DBG_LEVEL SET_LEVEL_0
  41
  42 /*
  43   ____                  _
  44  |  _ \  ___  _ __ ___ (_)_ __   __ _ _ __   ___ ___
  45  | | | |/ _ \| '_ ` _ \| | '_ \ / _` | '_ \ / __/ _ \
  46  | |_| | (_) | | | | | | | | | | (_| | | | | (_|  __/
  47  |____/ \___/|_| |_| |_|_|_| |_|\__,_|_| |_|\___\___|
  48  |  ___| __ ___  _ __ | |_(_) ___ _ __ ___
  49  | |_ | '__/ _ \| '_ \| __| |/ _ \ '__/ __|
  50  |  _|| | | (_) | | | | |_| |  __/ |  \__ \
  51  |_|  |_|  \___/|_| |_|\__|_|\___|_|  |___/
  52
  53 */
  54
  55
  56 struct _dom_front_info_t {
  57   pmap *df_map;
  58 };
  59
  60 /**
  61  * A wrapper for get_Block_idom.
  62  * This function returns the block itself, if the block is the start
  63  * block. Returning NULL would make any != comparison true which
  64  * suggests, that the start block is dominated by some other node.
  65  * @param bl The block.
  66  * @return The immediate dominator of the block.
  67  */
  68 static INLINE ir_node *get_idom(ir_node *bl)
  69 {
  70   ir_node *idom = get_Block_idom(bl);
  71   return idom == NULL ? bl : idom;
  72 }
  73
  74 static void compute_df(ir_node *n, pmap *df_map)
  75 {
  76   ir_node *c;
  77   const ir_edge_t *edge;
  78   pset *df = pset_new_ptr_default();
  79
  80   /* Add local dominance frontiers */
  81   foreach_block_succ(n, edge) {
  82     ir_node *y = edge->src;
  83
  84     if(get_idom(y) != n)
  85       pset_insert_ptr(df, y);
  86   }
  87
  88   /*
  89    * Go recursively down the dominance tree and add all blocks
  90    * int the dominance frontiers of the children, which are not
  91    * dominated by the given block.
  92    */
  93   for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
  94     pset *df_c;
  95     ir_node *w;
  96
  97     compute_df(c, df_map);
  98     df_c = pmap_get(df_map, c);
  99
 100     for(w = pset_first(df_c); w; w = pset_next(df_c)) {
 101       if(get_idom(w) != n)
 102         pset_insert_ptr(df, w);
 103     }
 104   }
 105
 106   pmap_insert(df_map, n, df);
 107
 108 }
 109
 110 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
 111 {
 112   dom_front_info_t *info = xmalloc(sizeof(*info));
 113
 114   edges_assure(irg);
 115   info->df_map = pmap_create();
 116   compute_doms(irg);
 117   compute_df(get_irg_start_block(irg), info->df_map);
 118
 119   return info;
 120 }
 121
 122 void be_free_dominance_frontiers(dom_front_info_t *info)
 123 {
 124   pmap_entry *ent;
 125
 126   for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
 127     del_pset(ent->value);
 128
 129   pmap_destroy(info->df_map);
 130   free(info);
 131 }
 132
 133 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
 134 {
 135   return pmap_get(info->df_map, block);
 136 }
 137
 138 static void determine_phi_blocks(pset *copies, pset *copy_blocks, pset *phi_blocks, dom_front_info_t *df_info)
 139 {
 140         ir_node *bl;
 141         pdeq *worklist = new_pdeq();
 142         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 143
 144         /*
 145          * Fill the worklist queue and the rest of the orig blocks array.
 146          */
 147         for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
 148                 pdeq_putr(worklist, bl);
 149         }
 150
 151         while (!pdeq_empty(worklist)) {
 152                 ir_node *bl = pdeq_getl(worklist);
 153                 pset *df    = be_get_dominance_frontier(df_info, bl);
 154
 155                 ir_node *y;
 156
 157                 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
 158                 DEBUG_ONLY(
 159                         for (y = pset_first(df); y; y = pset_next(df))
 160                                 DBG((dbg, LEVEL_3, "\t%+F\n", y))
 161                 );
 162
 163                 for(y = pset_first(df); y; y = pset_next(df)) {
 164                         if(!pset_find_ptr(phi_blocks, y)) {
 165                                 pset_insert_ptr(phi_blocks, y);
 166
 167                                 /*
 168                                  * Clear the link field of a possible phi block, since
 169                                  * the possibly created phi will be stored there. See,
 170                                  * search_def()
 171                                  */
 172                                 set_irn_link(y, NULL);
 173
 174                                 if(!pset_find_ptr(copy_blocks, y))
 175                                         pdeq_putr(worklist, y);
 176                         }
 177                 }
 178         }
 179
 180         del_pdeq(worklist);
 181 }
 182
 183 /*
 184   ____ ____    _
 185  / ___/ ___|  / \
 186  \___ \___ \ / _ \
 187   ___) |__) / ___ \
 188  |____/____/_/   \_\
 189    ____                _                   _   _
 190   / ___|___  _ __  ___| |_ _ __ _   _  ___| |_(_) ___  _ __
 191  | |   / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
 192  | |__| (_) | | | \__ \ |_| |  | |_| | (__| |_| | (_) | | | |
 193   \____\___/|_| |_|___/\__|_|   \__,_|\___|\__|_|\___/|_| |_|
 194
 195 */
 196
 197 /**
 198  * Find the copy of the given original node whose value is 'active'
 199  * at a usage.
 200  *
 201  * The usage is given as a node and a position. Initially, the given operand
 202  * points to a node for which copies were introduced. We have to find
 203  * the valid copy for this usage. This is done by traversing the
 204  * dominance tree upwards. If the usage is a phi function, we start
 205  * traversing from the predecessor block which corresponds to the phi
 206  * usage.
 207  *
 208  * @param usage       The node which uses the original node.
 209  * @param pos         The position of the argument which corresponds to the original node.
 210  * @param copies      A set containing all node which are copies from the original node.
 211  * @param copy_blocks A set containing all basic block in which copies of the original node are located.
 212  * @param phis        A set where all created phis are recorded.
 213  * @param phi_blocks  A set of all blocks where Phis shall be inserted (iterated dominance frontier).
 214  * @param mode        The mode for the Phi if one has to be created.
 215  * @return            The valid copy for usage.
 216  */
 217 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks, pset *phis, pset *phi_blocks, ir_mode *mode)
 218 {
 219         ir_node *curr_bl;
 220         ir_node *start_irn;
 221         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 222
 223         curr_bl = get_nodes_block(usage);
 224
 225         DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
 226         /*
 227          * If the usage is in a phi node, search the copy in the
 228          * predecessor denoted by pos.
 229          */
 230         if(is_Phi(usage)) {
 231                 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
 232                 start_irn = sched_last(curr_bl);
 233         } else {
 234                 start_irn = sched_prev(usage);
 235         }
 236
 237         /*
 238          * Traverse the dominance tree upwards from the
 239          * predecessor block of the usage.
 240          */
 241         while(curr_bl != NULL) {
 242
 243             /*
 244                  * If this block contains a copy, search the block
 245                  * instruction by instruction.
 246                  */
 247                 if(pset_find_ptr(copy_blocks, curr_bl)) {
 248                         ir_node *irn;
 249
 250                         /* Look at each instruction from last to first. */
 251                         sched_foreach_reverse_from(start_irn, irn) {
 252
 253                                 /* Take the first copy we find. */
 254                                 if(pset_find_ptr(copies, irn))
 255                                         return irn;
 256                         }
 257                 }
 258
 259                 if(pset_find_ptr(phi_blocks, curr_bl)) {
 260                         ir_node *phi = get_irn_link(curr_bl);
 261
 262                         if(!phi) {
 263                                 int i, n_preds = get_irn_arity(curr_bl);
 264                                 ir_graph *irg = get_irn_irg(curr_bl);
 265                                 ir_node **ins = xmalloc(n_preds * sizeof(ins[0]));
 266
 267                                 for(i = 0; i < n_preds; ++i)
 268                                         ins[i] = new_r_Bad(irg);
 269
 270                                 phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
 271                                 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
 272
 273                                 set_irn_link(curr_bl, phi);
 274                                 sched_add_after(curr_bl, phi);
 275                                 free(ins);
 276
 277                                 for(i = 0; i < n_preds; ++i) {
 278                                         ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
 279                                         DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
 280                                         set_irn_n(phi, i, arg);
 281                                 }
 282
 283                                 if(phis)
 284                                         pset_insert_ptr(phis, phi);
 285                         }
 286
 287                         return phi;
 288                 }
 289
 290                 /* If were not done yet, look in the immediate dominator */
 291                 curr_bl = get_Block_idom(curr_bl);
 292                 if(curr_bl)
 293                         start_irn = sched_last(curr_bl);
 294         }
 295
 296         return NULL;
 297 }
 298
 299 static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses)
 300 {
 301         int n_outs = 0;
 302         struct obstack obst;
 303         ir_node *irn;
 304         int i;
 305         struct out {
 306                 ir_node *irn;
 307                 int pos;
 308         } *outs;
 309
 310         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 311
 312         obstack_init(&obst);
 313
 314         /*
 315          * Put all outs into an array.
 316          * This is necessary, since the outs would be modified while
 317          * iterating on them what could bring the outs module in trouble.
 318          */
 319         for (irn = pset_first(copies); irn; irn = pset_next(copies)) {
 320                 const ir_edge_t *edge;
 321                 foreach_out_edge(irn, edge) {
 322                         if (!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
 323                                 struct out tmp;
 324                                 tmp.irn = get_edge_src_irn(edge);
 325                                 tmp.pos = get_edge_src_pos(edge);
 326                                 obstack_grow(&obst, &tmp, sizeof(tmp));
 327                                 n_outs++;
 328                         }
 329                 }
 330         }
 331         outs = obstack_finish(&obst);
 332
 333         /*
 334          * Search the valid def for each out and set it.
 335          */
 336         for(i = 0; i < n_outs; ++i) {
 337                 ir_node *irn  = outs[i].irn;
 338                 int pos       = outs[i].pos;
 339                 ir_mode *mode = get_irn_mode(get_irn_n(irn, pos));
 340
 341                 ir_node *def;
 342
 343                 def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
 344                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
 345
 346                 if(def != NULL)
 347                         set_irn_n(irn, pos, def);
 348         }
 349
 350         obstack_free(&obst, NULL);
 351 }
 352
 353 /**
 354  * Remove phis which are not necessary.
 355  * During place_phi_functions() phi functions are put on the dominance
 356  * frontiers blindly. However some of them will never be used (these
 357  * have at least one predecessor which is NULL, see search_def() for
 358  * this case). Since place_phi_functions() enters them into the
 359  * schedule, we have to remove them from there.
 360  *
 361  * @param copies The set of all copies made (including the phi functions).
 362  */
 363 static void remove_odd_phis(pset *copies, pset *unused_copies)
 364 {
 365   ir_node *irn;
 366
 367   for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
 368     if(is_Phi(irn)) {
 369       int i, n;
 370       int illegal = 0;
 371
 372       assert(sched_is_scheduled(irn) && "phi must be scheduled");
 373       for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
 374         illegal = get_irn_n(irn, i) == NULL;
 375
 376       if(illegal)
 377         sched_remove(irn);
 378     }
 379   }
 380
 381   for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
 382                 sched_remove(irn);
 383         }
 384 }
 385
 386 void be_ssa_constr_phis_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *phis, pset *ignore_uses)
 387 {
 388         pset *irns = pset_new_ptr(n);
 389         int i;
 390
 391         for(i = 0; i < n; ++i)
 392                 pset_insert_ptr(irns, nodes[i]);
 393         be_ssa_constr_set_phis_ignore(info, irns, phis, ignore_uses);
 394         del_pset(irns);
 395 }
 396
 397 void be_ssa_constr_ignore(dom_front_info_t *info, int n, ir_node *nodes[], pset *ignore_uses)
 398 {
 399         be_ssa_constr_phis_ignore(info, n, nodes, NULL, ignore_uses);
 400 }
 401
 402 void be_ssa_constr(dom_front_info_t *info, int n, ir_node *nodes[])
 403 {
 404         pset *empty_set = be_empty_set();
 405         be_ssa_constr_ignore(info, n, nodes, empty_set);
 406 }
 407
 408 void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, pset *nodes, pset *phis, pset *ignore_uses)
 409 {
 410         int n                  = pset_count(nodes);
 411         pset *blocks           = pset_new_ptr(n);
 412         pset *phi_blocks       = pset_new_ptr(n);
 413         int save_optimize      = get_optimize();
 414         int save_normalize     = get_opt_normalize();
 415         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 416
 417         ir_node *irn;
 418
 419         DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
 420
 421         /* Fill the sets. */
 422         for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) {
 423                 ir_node *bl = get_nodes_block(irn);
 424                 pset_insert_ptr(blocks, bl);
 425                 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl));
 426         }
 427
 428         /*
 429          * Disable optimization so that the phi functions do not
 430          * disappear.
 431          */
 432         set_optimize(0);
 433         set_opt_normalize(0);
 434
 435         /*
 436          * Place the phi functions and reroute the usages.
 437          */
 438         determine_phi_blocks(nodes, blocks, phi_blocks, df);
 439         fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
 440
 441         /* reset the optimizations */
 442         set_optimize(save_optimize);
 443         set_opt_normalize(save_normalize);
 444
 445         del_pset(phi_blocks);
 446         del_pset(blocks);
 447
 448 }
 449
 450 void be_ssa_constr_set_phis(dom_front_info_t *df, pset *nodes, pset *phis)
 451 {
 452         pset *empty_set = be_empty_set();
 453         be_ssa_constr_set_phis_ignore(df, nodes, phis, empty_set);
 454 }
 455
 456 void be_ssa_constr_set_ignore(dom_front_info_t *df, pset *nodes, pset *ignore_uses)
 457 {
 458         be_ssa_constr_set_phis_ignore(df, nodes, NULL, ignore_uses);
 459 }
 460
 461 void be_ssa_constr_set(dom_front_info_t *info, pset *nodes)
 462 {
 463         pset *empty_set = be_empty_set();
 464         be_ssa_constr_set_ignore(info, nodes, empty_set);
 465 }
 466
 467 /*
 468   ___                     _     ____
 469  |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___ _ __ _ __ ___
 470   | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
 471   | || | | \__ \  __/ |  | |_  |  __/  __/ |  | | | | | |
 472  |___|_| |_|___/\___|_|   \__| |_|   \___|_|  |_| |_| |_|
 473
 474 */
 475
 476 ir_node *insert_Perm_after(const arch_env_t *arch_env,
 477                                                    const arch_register_class_t *cls,
 478                                                    dom_front_info_t *dom_front,
 479                                                    ir_node *pos)
 480 {
 481         ir_node *bl                 = is_Block(pos) ? pos : get_nodes_block(pos);
 482         ir_graph *irg               = get_irn_irg(bl);
 483         pset *live                  = pset_new_ptr_default();
 484         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "be.node");
 485
 486         ir_node *curr, *irn, *perm, **nodes;
 487         int i, n;
 488
 489         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 490
 491         be_liveness_nodes_live_at(arch_env, cls, pos, live);
 492
 493         n = pset_count(live);
 494
 495         if(n == 0) {
 496                 del_pset(live);
 497                 return NULL;
 498         }
 499
 500         nodes = xmalloc(n * sizeof(nodes[0]));
 501
 502         DBG((dbg, LEVEL_1, "live:\n"));
 503         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
 504                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
 505                 nodes[i] = irn;
 506         }
 507         del_pset(live);
 508
 509         perm = be_new_Perm(cls, irg, bl, n, nodes);
 510         sched_add_after(pos, perm);
 511         free(nodes);
 512
 513         curr = perm;
 514         for(i = 0; i < n; ++i) {
 515                 ir_node *copies[2];
 516                 ir_node *perm_op = get_irn_n(perm, i);
 517                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
 518
 519                 ir_mode *mode = get_irn_mode(perm_op);
 520                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
 521                 arch_set_irn_register(arch_env, proj, reg);
 522
 523                 sched_add_after(curr, proj);
 524                 curr = proj;
 525
 526                 copies[0] = perm_op;
 527                 copies[1] = proj;
 528                 be_ssa_constr(dom_front, 2, copies);
 529         }
 530         return perm;
 531 }