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 #include "belive.h"
  12
  13 #include "bera_t.h"
  14 #include "bephicongr_t.h"
  15 #include "bephicoal_t.h"
  16
  17 #define DEBUG_LVL 1
  18
  19 #define MAX_PHI_CLS_SIZE (1<<(sizeof(unsigned char)*8)) /* possible colors added should fit into unsigned char */
  20 #define MAX_COLORS 16
  21
  22
  23 static firm_dbg_module_t *dbgphi = NULL;
  24
  25
  26 typedef enum _live_status_t {
  27         livein = 1,
  28         liveout = 2
  29 } live_status_t;
  30
  31
  32 typedef struct _phi_unit_t {
  33         unsigned char count;
  34         unsigned char phi_count;
  35         ir_node **members;                      /* [0..phi_count-1] are phi nodes. [phi_count..count-1] the rest/arguments of the phis */
  36         bitset_t **used_cols;
  37         int *tgt_colors;                        /* [i] is the color to set for members[i]. [i] == -1 means dont change anything for members[i]*/
  38         live_status_t *live_info;       /* [i] says how/where members[i] is live */
  39 } phi_unit_t;
  40
  41
  42 static pset *done;
  43
  44
  45 static INLINE void set_color(ir_node *irn, int col) {
  46         if (!pset_find_ptr(done, irn)) {
  47                 set_irn_color(irn, col);
  48                 pset_insert_ptr(done, irn);
  49         }
  50 }
  51
  52
  53 static void coalesce(phi_unit_t *pu) {
  54         int i;
  55         if (pu->phi_count != 1) {
  56                 DBG((dbgphi, 1, "Dropped: phicount\n"));
  57                 return;
  58         }
  59 #if 0
  60
  61         done = pset_new_ptr(64);
  62
  63         for (i = 0; i < pu->count; ++i)
  64                 if (pu->live_info[i] & livein) {
  65                         DBG((dbgphi, 1, "Dropped: live-in\n"));
  66                         return;
  67                 }
  68
  69         for (i = 0; i < pu->count; ++i) {
  70                 block_list_t *bl;
  71
  72                 if (pu->tgt_colors[i] == -1)
  73                         continue;
  74
  75                 /* TODO: if we move ahead to swapping (not just allocating new colors) this is wrong */
  76                 set_color(pu->members[i], pu->tgt_colors[i]);
  77                 if (pu->live_info[i] & liveout) {
  78                         bl = get_dominated_dfs(get_nodes_block(pu->members[i]));
  79                 }
  80         }
  81
  82         del_pset(done);
  83
  84 #endif
  85 }
  86
  87
  88 static void ana_1_phi(phi_unit_t *pu) {
  89         ir_node *phi, *phi_blk;
  90         int i, o, n, col, best_color, size, best_size;
  91         ir_node **cand, **max_set, **best_max_set;
  92
  93         cand = malloc(pu->count * sizeof(ir_node*));
  94         max_set = malloc(pu->count * sizeof(ir_node*));
  95         best_max_set = malloc(pu->count * sizeof(ir_node*));
  96
  97         phi = pu->members[0];
  98         phi_blk = get_nodes_block(phi);
  99
 100
 101         /* fill live_info */
 102         DBG((dbgphi, 1, "\tLiveness info\n"));
 103         /* first the phi */
 104         if (is_live_out(phi_blk, phi)) {
 105                 pu->live_info[0] = liveout;
 106                 DBG((dbgphi, 1, "\t\t%n lives out\n", phi));
 107         }
 108
 109         /* then all args */
 110         for (i = 0, n = get_irn_arity(phi); i < n; ++i) {
 111                 int midx;
 112         ir_node *arg, *block_ith_pred;
 113
 114         arg = get_irn_n(phi, i);
 115                 block_ith_pred = get_nodes_block(get_irn_n(phi_blk, i));
 116
 117                 /* find the arg in the members array */
 118                 midx = -1;
 119                 for (o = 0; o < pu->count; ++o)
 120                         if (pu->members[o] == arg) {
 121                                 midx = o;
 122                                 break;
 123                         }
 124                 assert(midx != -1 && "All args have to be in the members!\n");
 125
 126                 if (is_live_in(block_ith_pred, arg)) {
 127                         pu->live_info[midx] |= livein;
 128                         DBG((dbgphi, 1, "\t\t%n lives in\n", arg));
 129                 }
 130
 131                 if (is_live_out(block_ith_pred, arg)) {
 132                         pu->live_info[midx] |= liveout;
 133                         DBG((dbgphi, 1, "\t\t%n lives out\n", arg));
 134                 }
 135         }
 136
 137         /* find best color */
 138         best_size = -1;
 139         for (col = 0; col < MAX_COLORS; ++col) {                /* TODO: try phi color first */
 140                 DBG((dbgphi, 1, "\tTesting colors %d\n", col));
 141
 142                 memset(cand, 0, pu->count * sizeof(ir_node*));
 143                 memset(max_set, 0, pu->count * sizeof(ir_node*));
 144
 145                 /* BETTER: Alle die mit dem phi interferieren koennen eigentlich
 146                  * schon frueher raus, da unabhaengig von Farbe. */
 147                 /* for this color get all potential candidates for a max indep. set */
 148                 cand[0] = phi;
 149                 size = 1;
 150                 for (i = 1; i < pu->count; ++i)
 151                         if ((!bitset_is_set(pu->used_cols[i], col) || get_irn_color(pu->members[i]) == col)
 152                                 && !phi_ops_interfere(phi, pu->members[i])) {
 153                                 /* color is free or already used by the node
 154                                  * and argument is not interfering with phi */
 155                                 cand[i] = pu->members[i];
 156                                 DBG((dbgphi, 1, "\t\tAdding candidate %n\n", cand[i]));
 157                                 size++;
 158                         }
 159                 if (size <= best_size) {
 160                         /* If the candidate set is smaller the max indep. set wont be larger :) */
 161                         continue;
 162                 }
 163
 164                 /* determine the max indep. set */
 165                 /* TODO: make this 'un-greedy' */
 166                 size = 0;
 167                 for (i = 0; i < pu->count; ++i) {
 168                         int intf_det = 0;
 169                         if (!cand[i])
 170                                 continue;
 171
 172                         for (o = 0; o < pu->count; ++o) {
 173                                 if (!max_set[o])
 174                                         continue;
 175                                 if (phi_ops_interfere(cand[i], max_set[o])) {
 176                                         DBG((dbgphi, 1, "\t\t\n"));
 177                                         intf_det = 1;
 178                                         break;
 179                                 }
 180                         }
 181
 182                         if (!intf_det) {
 183                                 DBG((dbgphi, 1, "\t\tAdding to set %n\n", cand[i]));
 184                                 max_set[i] = cand[i];
 185                                 size++;
 186                         }
 187                 }
 188
 189
 190                 DBG((dbgphi, 1, "\t\tColor %d resulted in a set size of %d\n", col, size));
 191
 192                 /* Did we find a better max set? */
 193                 if (size > best_size) {
 194                         void *tmp;
 195
 196                         best_color = col;
 197                         best_size = size;
 198
 199                         tmp = best_max_set;
 200                         best_max_set = max_set;
 201                         max_set = tmp;
 202                 }
 203
 204                 /* Is this a best possible set? */
 205                 /* BETTER: Find a better lower bound than pu->count, considering interferences */
 206                 if (best_size == pu->count)
 207                         break;
 208         }
 209         DBG((dbgphi, 1, "Best color was %d. %d of %d copies needed.\n", best_color, pu->count-best_size, pu->count-1));
 210
 211
 212         /* now we have the best_max_set with its best_size
 213          * so set the tgt_colors */
 214         for (i = 0; i < pu->count; ++i)
 215                 if (best_max_set[i] && get_irn_color(best_max_set[i]) != best_color)
 216                         pu->tgt_colors[i] = best_color;
 217                 else
 218                         pu->tgt_colors[i] = -1;
 219
 220         free(cand);
 221         free(max_set);
 222         free(best_max_set);
 223 }
 224
 225
 226 static phi_unit_t *new_phi_unit(pset *pc) {
 227         phi_unit_t *pu;
 228         int i, o;
 229         ir_node *n;
 230
 231         assert(pset_count(pc) <= MAX_PHI_CLS_SIZE && "Phi class too large!");
 232
 233         pu = malloc(sizeof(phi_unit_t));
 234         pu->count = pset_count(pc);
 235         pu->members = malloc(pu->count * sizeof(*pu->members));
 236         pu->used_cols = malloc(pu->count * sizeof(bitset_t*));
 237         pu->tgt_colors = malloc(pu->count * sizeof(int));
 238         pu->live_info = calloc(pu->count, sizeof(ir_node*));
 239
 240
 241         /* fill the members array */
 242         DBG((dbgphi, 1, "Phi class:\n"));
 243         i = 0;
 244         o = pu->count-1;
 245         for (n = (ir_node *)pset_first(pc); n; n = (ir_node *)pset_next(pc)) {
 246                 DBG((dbgphi, 1, "\t%n\n", n));
 247                 if (is_Phi(n))
 248                         pu->members[i++] = n;
 249                 else
 250                         pu->members[o--] = n;
 251         }
 252         pu->phi_count = i;
 253         DBG((dbgphi, 1, "\n"));
 254
 255
 256         /* fill used colors array */
 257         for (i = 0; i < pu->count; ++i)
 258                 pu->used_cols[i] = get_ra_block_info(get_nodes_block(pu->members[i]))->used_colors;
 259
 260
 261         if (pu->phi_count == 1) {
 262                 ana_1_phi(pu);
 263         } else {
 264                 /* TODO */
 265                 // ana_n_phi(pu);
 266         }
 267
 268         return pu;
 269 }
 270
 271
 272 static void free_phi_unit(phi_unit_t *pu) {
 273         DBG((dbgphi, 1, "\n"));
 274         free(pu->members);
 275         free(pu->used_cols);
 276         free(pu->tgt_colors);
 277         free(pu->live_info);
 278         free(pu);
 279 }
 280
 281
 282 void be_phi_coalesce(pset *all_phi_classes) {
 283         pset *pc;
 284         phi_unit_t *pu;
 285
 286         for (pc = (pset *)pset_first(all_phi_classes); pc; pc = (pset *)pset_next(all_phi_classes)) {
 287                 pu = new_phi_unit(pc);
 288                 coalesce(pu);
 289                 free_phi_unit(pu);
 290         }
 291 }
 292
 293
 294 void be_phi_coal_init(void) {
 295         dbgphi = firm_dbg_register("Phi coalescing");
 296         firm_dbg_set_mask(dbgphi, DEBUG_LVL);
 297 }