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

   1 /**
   2  * @author Daniel Grund
   3  * @date 04.01.2005
   4  */
   5
   6 #include <stdlib.h>
   7
   8 #include "bitset.h"
   9 #include "debug.h"
  10 #include "bechordal.h"
  11
  12 #include "bera_t.h"
  13 #include "bephicongr_t.h"
  14 #include "bephicoal_t.h"
  15
  16 static firm_dbg_module_t *dbgphi = NULL;
  17
  18 void be_phi_coal_init(void) {
  19         dbgphi = firm_dbg_register("Phi coalescing");
  20         firm_dbg_set_mask(dbgphi, 1);
  21 }
  22
  23
  24 static INLINE ir_node **pset_to_array(pset *theset) {
  25         ir_node **res, *p;
  26         int i, count;
  27
  28         count = pset_count(theset);
  29         res = (ir_node **) malloc(count * sizeof(ir_node*));
  30         for (i = 0, p = (ir_node *)pset_first(theset); p; p = (ir_node *)pset_next(theset))
  31                 res[i++] = p;
  32         assert(i == count);
  33
  34         return res;
  35 }
  36
  37
  38 static INLINE pset *clone(pset *theset) {
  39         void *p;
  40         pset *res;
  41
  42         res = pset_new_ptr(8);
  43         for (p = pset_first(theset); p; p = pset_next(theset))
  44                 pset_insert_ptr(res, p);
  45
  46         return res;
  47 }
  48
  49
  50 static void coalesce_locals(pset *phi_class, dominfo_t *dominfo) {
  51         int i, count, phi_count, arity, intf_det, phi_col, allfree;
  52         pset *pc, *intffree;
  53         ir_node *phi = NULL, *n, *m;
  54 //      ir_node **members;
  55
  56         count = pset_count(phi_class);
  57         pc = clone(phi_class);
  58 //      members = pset_to_array(phi_class);
  59
  60         /* how many phi nodes are in this class? */
  61         DBG((dbgphi, 1, "Checking phi count\n"));
  62         phi_count = 0;
  63         for (n = (ir_node *)pset_first(pc); n; n = (ir_node *)pset_next(pc)) {
  64                 if (is_Phi(n)) {
  65                         phi = n;
  66                         phi_count++;
  67                 }
  68         }
  69
  70         if (phi_count > 1) {
  71                 DBG((dbgphi, 1, "Dropped: Too many phis\n"));
  72                 goto exit;
  73         }
  74         assert(phi_count == 1 && phi);
  75
  76
  77         /* where is the definition of the arguments? */
  78         DBG((dbgphi, 1, "Checking arg def\n"));
  79         arity = get_irn_arity(phi);
  80         for (i = 0; i < arity; ++i) {
  81         ir_node *block_of_arg, *block_ith_pred;
  82                 ir_node *arg = get_irn_n(phi, i);
  83
  84                 block_of_arg = get_nodes_block(arg);
  85                 block_ith_pred = get_nodes_block(get_irn_n(get_nodes_block(phi), i));
  86
  87                 if (block_of_arg != block_ith_pred) {
  88                         DBG((dbgphi, 1, "Dropped: Arg-def not in pred-block\n"));
  89                         goto exit;
  90                 }
  91         }
  92
  93
  94         /* determine a greedy set of non-interfering members
  95          * crucial: starting with the phi node
  96          */
  97         DBG((dbgphi, 1, "Building greedy non-interfering set\n"));
  98         intffree = pset_new_ptr(4);
  99
 100         pset_remove_ptr(pc, phi);
 101         pset_insert_ptr(intffree, phi);
 102
 103         while (m = (ir_node *)pset_first(pc), m) {
 104                 DBG((dbgphi, 1, "Checking %n\n", m));
 105                 pset_break(pc);
 106                 pset_remove_ptr(pc, m);
 107
 108                 intf_det = 0;
 109                 for (n = (ir_node *)pset_first(intffree); n; n = (ir_node *)pset_next(intffree)) {
 110                         DBG((dbgphi, 1, "\t%n", n));
 111                         if (phi_ops_interfere(m, n)) {
 112                                 DBG((dbgphi, 1, "\tinterf\n"));
 113                                 intf_det = 1;
 114                         } else {
 115                                 DBG((dbgphi, 1, "\tclean\n"));
 116                         }
 117                 }
 118
 119                 if (!intf_det) {
 120                         DBG((dbgphi, 1, "Added to set\n"));
 121                         pset_insert_ptr(intffree, m);
 122                 }
 123         }
 124
 125         /*
 126          * color the non interfering set
 127          */
 128         DBG((dbgphi, 1, "Coloring...\n"));
 129         phi_col = get_irn_color(phi);
 130         DBG((dbgphi, 1, "phi-color: %d\n", phi_col));
 131
 132         /* check if phi color is free in blocks of all members */
 133         allfree = 1;
 134         for (n = (ir_node *)pset_first(intffree); n; n = (ir_node *)pset_next(intffree)) {
 135                 ir_node *block;
 136                 bitset_t *used_colors;
 137
 138                 if (n == phi)
 139                         continue;
 140
 141                 block = get_nodes_block(n);
 142
 143                 used_colors = get_ra_block_info(block)->used_colors;
 144
 145                 if (bitset_is_set(used_colors, phi_col)) {
 146                         allfree = 0;
 147                         break;
 148                 }
 149         }
 150
 151         if (allfree) {
 152                 for (n = (ir_node *)pset_first(intffree); n; n = (ir_node *)pset_next(intffree))
 153                         set_irn_color(n, phi_col);
 154                 printf("KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK\n");
 155         } else {
 156
 157         }
 158
 159 exit:
 160         del_pset(pc);
 161 //      free(members);
 162 }
 163
 164
 165 void be_phi_coalesce(pset *all_phi_classes, dominfo_t *dominfo) {
 166         pset *phi_class;
 167
 168         for (phi_class = (pset *)pset_first(all_phi_classes); phi_class; phi_class = (pset *)pset_next(all_phi_classes))
 169                 coalesce_locals(phi_class, dominfo);
 170 }