nsz Git - libfirm/blob - ir/opt/combo.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Cliff Click's Combined Analysis/Optimization
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include "iroptimize.h"
  31 #include <assert.h>
  32 #include "list.h"
  33 #include "obstack.h"
  34 #include "irgraph_t.h"
  35 #include "irnode_t.h"
  36 #include "irgwalk.h"
  37 #include "irop.h"
  38 #include "irouts.h"
  39 #include "irgmod.h"
  40 #include "debug.h"
  41
  42 typedef struct partition_entry_t partition_entry_t;
  43 typedef struct partition_t       partition_t;
  44
  45 /**
  46  * A partition entry.
  47  */
  48 struct partition_entry_t {
  49         ir_node           *node;         /**< The node itself. */
  50         list_head         list;          /**< double-linked list */
  51         partition_t       *part;         /**< points to the partition this entry belongs to */
  52         partition_entry_t *touched_next; /**< Next entry on partition.touched set. */
  53         unsigned          on_touched:1;  /**< Set, if this entry is on the partition.touched set. */
  54 };
  55
  56 /**
  57  * A partition containing congruent nodes.
  58  */
  59 struct partition_t {
  60         list_head         entries;       /**< The partition entries. */
  61         partition_t       *wl_next;      /**< Next entry in the work list if any. */
  62         partition_t       *touched_next; /**< points to the next partition in the touched set. */
  63         partition_entry_t *touched;      /**< the partition.touched set of this partition. */
  64         unsigned          n_entries;     /**< number of entries in this partition. */
  65         unsigned          n_touched;     /**< number of entries in the partition.touched. */
  66         int               n_inputs;      /**< Maximum number of inputs of all entries. */
  67         unsigned          on_worklist:1; /**< Set, if this partition is in the work list. */
  68         unsigned          on_touched:1;  /**< Set, if this partition is on the touched set. */
  69 };
  70
  71 typedef struct environment_t {
  72         struct obstack  obst;      /**< obstack to allocate data structures. */
  73         partition_t     *worklist; /**< The work list. */
  74         partition_t     *touched;  /**< the touched set. */
  75         partition_t     *opcode_map[iro_Last];  /**< The initial partition set. */
  76 } environment_t;
  77
  78 #define get_irn_entry(irn)         ((partition_entry_t *)get_irn_link(irn))
  79 #define set_irn_entry(irn, entry)  set_irn_link(irn, entry)
  80
  81 /** The debug module handle. */
  82 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  83
  84 #ifdef DEBUG_libfirm
  85 static void dump_partition(partition_t *part) {
  86         partition_entry_t *entry;
  87
  88         DB((dbg, LEVEL_2, "{ "));
  89         list_for_each_entry(partition_entry_t, entry, &part->entries, list) {
  90                 DB((dbg, LEVEL_2, "%+F, ", entry->node));
  91         }
  92         DB((dbg, LEVEL_2, "}\n"));
  93 }
  94 #else
  95 #define dump_partition(part)
  96 #endif
  97
  98 /**
  99  * Create a new empty partition.
 100  */
 101 static INLINE partition_t *new_partition(environment_t *env) {
 102         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 103
 104         INIT_LIST_HEAD(&part->entries);
 105         part->wl_next      = env->worklist;
 106         part->touched_next = NULL;
 107         part->touched      = NULL;
 108         part->n_entries    = 0;
 109         part->n_touched    = 0;
 110         part->n_inputs     = 0;
 111         part->on_worklist  = 0;
 112         part->on_touched   = 0;
 113
 114         return part;
 115 }
 116
 117 /**
 118  * Get the partition for a given opcode.
 119  */
 120 static INLINE partition_t *get_partition(ir_opcode code, environment_t *env) {
 121         partition_t *part = env->opcode_map[code];
 122
 123         if (part == NULL) {
 124                 /* create a new partition and place it on the wait queue */
 125                 part = new_partition(env);
 126
 127                 part->on_worklist     = 1;
 128                 env->worklist         = part;
 129                 env->opcode_map[code] = part;
 130         }
 131         return part;
 132 }
 133
 134 /**
 135  * Walker, creates the initial partitions, one for every opcode and place them
 136  * on the worklist.
 137  */
 138 static void create_initial_partitions(ir_node *irn, void *ctx) {
 139         environment_t *env  = ctx;
 140         ir_opcode     code  = get_irn_opcode(irn);
 141         partition_t   *part = get_partition(code, env);
 142         int           arity;
 143
 144         /* create a partition entry and place it in the partition */
 145         partition_entry_t *entry = obstack_alloc(&env->obst, sizeof(*entry));
 146
 147         INIT_LIST_HEAD(&entry->list);
 148         entry->node         = irn;
 149         entry->part         = part;
 150         entry->touched_next = NULL;
 151         entry->on_touched   = 0;
 152         set_irn_entry(irn, entry);
 153
 154         list_add_tail(&entry->list, &part->entries);
 155         ++part->n_entries;
 156
 157         arity = get_irn_arity(irn);
 158         if (arity > part->n_inputs)
 159                 part->n_inputs = arity;
 160 }
 161
 162 /**
 163  * Add a partition to the touched set if not already there.
 164  */
 165 static INLINE void add_to_touched(partition_t *part, environment_t *env) {
 166         if (part->on_touched == 0) {
 167                 part->touched_next = env->touched;
 168                 env->touched       = part;
 169                 part->on_touched   = 1;
 170         }
 171 }
 172
 173 /**
 174  * Add an entry to the entry.partition.touched set if not already there..
 175  */
 176 static INLINE void add_to_partition_touched(partition_entry_t *y) {
 177         if (y->on_touched == 0) {
 178                 partition_t *part = y->part;
 179
 180                 y->touched_next = part->touched;
 181                 part->touched   = y;
 182                 ++part->n_touched;
 183                 y->on_touched   = 1;
 184         }
 185 }
 186
 187 /**
 188  * Split a partition by the touched set.
 189  */
 190 static partition_t *split(partition_t *Z, partition_entry_t *g, environment_t *env) {
 191         partition_t       *Z_prime;
 192         partition_entry_t *entry;
 193         unsigned          n = 0;
 194
 195         /* Remove g from Z. */
 196         for (entry = g; entry != NULL; entry = entry->touched_next) {
 197                 list_del(&entry->list);
 198                 entry->on_touched = 0;
 199                 ++n;
 200         }
 201         Z->n_entries -= n;
 202
 203         /* Move g to a new partition, Z\92. */
 204         Z_prime = new_partition(env);
 205         for (entry = g; entry != NULL; entry = entry->touched_next) {
 206                 list_add(&entry->list, &Z_prime->entries);
 207                 entry->part = Z_prime;
 208         }
 209         Z_prime->n_entries = n;
 210
 211         /* If Z is on worklist then add Z\92 to worklist.
 212            Else add the smaller of Z and Z\92 to worklist. */
 213         if (Z->on_worklist || Z_prime->n_entries < Z->n_entries) {
 214                 Z_prime->on_worklist = 1;
 215                 Z_prime->wl_next     = env->worklist;
 216                 env->worklist        = Z_prime;
 217         } else {
 218                 Z->on_worklist = 1;
 219                 Z->wl_next     = env->worklist;
 220                 env->worklist  = Z;
 221         }
 222         return Z_prime;
 223 }
 224
 225 /**
 226  * Split the partitions if caused by the first entry on the worklist.
 227  */
 228 static void cause_splits(environment_t *env) {
 229         partition_t       *X, *Z;
 230         partition_entry_t *x, *y, *e;
 231         int               i;
 232
 233         /* remove the first partition from the worklist */
 234         X = env->worklist;
 235         env->worklist  = X->wl_next;
 236         X->on_worklist = 0;
 237
 238         for (i = X->n_inputs - 1; i >= -1; --i) {
 239                 /* empty the touched set: already done, just clear the list */
 240                 env->touched = NULL;
 241
 242                 list_for_each_entry(partition_entry_t, x, &X->entries, list) {
 243                         if (i < get_irn_arity(x->node) && (!is_Block(x->node) || i >= 0)) {
 244                                 y = get_irn_entry(get_irn_n(x->node, i));
 245
 246                                 add_to_touched(y->part, env);
 247                                 add_to_partition_touched(y);
 248                         }
 249                 }
 250
 251                 for (Z = env->touched; Z != NULL; Z = Z->touched_next) {
 252                         /* remove it from the touched set */
 253                         Z->on_touched = 0;
 254
 255                         if (Z->n_entries != Z->n_touched) {
 256                                 split(Z, Z->touched, env);
 257                         }
 258                         /* Empty Z.touched. */
 259                         for (e = Z->touched; e != NULL; e = e->touched_next) {
 260                                 e->on_touched = 0;
 261                         }
 262                         Z->touched = NULL;
 263                 }
 264
 265         }
 266 }
 267
 268 /**
 269  * Get the leader for a given node from its congruence class.
 270  *
 271  * @param irn  the node
 272  */
 273 static ir_node *get_leader(ir_node *irn) {
 274         partition_t *part = get_irn_entry(irn)->part;
 275
 276         if (part->n_entries > 1) {
 277                 DB((dbg, LEVEL_2, "Found congruence class for %+F ", irn));
 278                 dump_partition(part);
 279         }
 280         return irn;
 281 }
 282
 283 /**
 284  * Post-Walker, apply the analysis results;
 285  */
 286 static void apply_result(ir_node *irn, void *ctx) {
 287         environment_t *env = ctx;
 288
 289         ir_node *leader = get_leader(irn);
 290
 291         if (leader != irn) {
 292                 exchange(irn, leader);
 293         }
 294 }
 295
 296 void combo(ir_graph *irg) {
 297         environment_t env;
 298
 299         /* register a debug mask */
 300         FIRM_DBG_REGISTER(dbg, "firm.opt.combo");
 301         firm_dbg_set_mask(dbg, SET_LEVEL_2);
 302
 303         obstack_init(&env.obst);
 304         env.worklist = NULL;
 305         env.touched  = NULL;
 306         memset(env.opcode_map, 0, sizeof(env.opcode_map));
 307
 308         assure_irg_outs(irg);
 309
 310         /* create the initial partitions */
 311         irg_walk_graph(irg, NULL, create_initial_partitions, &env);
 312
 313         while (env.worklist != NULL)
 314                 cause_splits(&env);
 315
 316         /* apply the result */
 317         irg_walk_graph(irg, NULL, apply_result, &env);
 318
 319         obstack_free(&env.obst, NULL);
 320 }