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  * Note that we use the terminology from Click's work here, which is different
  27  * in some cases from Firm terminology.  Especially, Click's type is a
  28  * Firm tarval, nevertheless we call it type here for "maximum compatibility".
  29  */
  30 #ifdef HAVE_CONFIG_H
  31 # include "config.h"
  32 #endif
  33
  34 #include <assert.h>
  35
  36 #include "iroptimize.h"
  37 #include "irflag.h"
  38 #include "list.h"
  39 #include "array.h"
  40 #include "set.h"
  41 #include "pmap.h"
  42 #include "obstack.h"
  43 #include "irgraph_t.h"
  44 #include "irnode_t.h"
  45 #include "iropt_t.h"
  46 #include "irgwalk.h"
  47 #include "irop.h"
  48 #include "irouts.h"
  49 #include "irgmod.h"
  50 #include "debug.h"
  51
  52 /* we need the tarval_R and tarval_U */
  53 #define tarval_U  tarval_undefined
  54 #define tarval_R  tarval_bad
  55
  56 typedef struct node_t            node_t;
  57 typedef struct partition_t       partition_t;
  58 typedef struct opcode_key_t      opcode_key_t;
  59 typedef struct opcode_entry_t    opcode_entry_t;
  60 typedef struct listmap_entry_t   listmap_entry_t;
  61
  62 /** The type of the compute function. */
  63 typedef void (*compute_func)(node_t *node);
  64
  65 /**
  66  * An opcode map key.
  67  */
  68 struct opcode_key_t {
  69         ir_opcode   code;   /**< The Firm opcode. */
  70         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  71 };
  72
  73 /**
  74  * An entry in the opcode map.
  75  */
  76 struct opcode_entry_t {
  77         opcode_key_t key;    /**< The key. */
  78         partition_t  *part;  /**< The associated partition. */
  79 };
  80
  81 /**
  82  * An entry in the list_map.
  83  */
  84 struct listmap_entry_t {
  85         void            *id;    /**< The id. */
  86         node_t          *list;  /**< The associated list for this id. */
  87         listmap_entry_t *next;  /**< Link to the next entry in the map. */
  88 };
  89
  90 /** We must map id's to lists. */
  91 typedef struct listmap_t {
  92         set             *map;    /**< Map id's to listmap_entry_t's */
  93         listmap_entry_t *values; /**< List of all values in the map. */
  94 } listmap_t;
  95
  96
  97 /**
  98  * A node.
  99  */
 100 struct node_t {
 101         ir_node     *node;         /**< The IR-node itself. */
 102         list_head   node_list;     /**< Double-linked list of entries. */
 103         partition_t *part;         /**< points to the partition this node belongs to */
 104         node_t      *cprop_next;   /**< Next node on partition.cprop list. */
 105         node_t      *next;         /**< Next node on local list (partition.touched, fallen). */
 106         tarval      *type;         /**< The associated lattice element "type". */
 107         unsigned    on_touched:1;  /**< Set, if this node is on the partition.touched set. */
 108         unsigned    on_cprop:1;    /**< Set, if this node is on the partition.cprop list. */
 109 };
 110
 111 /**
 112  * A partition containing congruent nodes.
 113  */
 114 struct partition_t {
 115         list_head         entries;       /**< The head of partition node list. */
 116         node_t            *cprop;        /**< The partition.cprop list. */
 117         partition_t       *wl_next;      /**< Next entry in the work list if any. */
 118         partition_t       *touched_next; /**< Points to the next partition in the touched set. */
 119         partition_t       *cprop_next;   /**< Points to the next partition in the cprop list. */
 120         node_t            *touched;      /**< The partition.touched set of this partition. */
 121         unsigned          n_nodes;       /**< Number of entries in this partition. */
 122         unsigned          n_touched;     /**< Number of entries in the partition.touched. */
 123         int               n_inputs;      /**< Maximum number of inputs of all entries. */
 124         unsigned          on_worklist:1; /**< Set, if this partition is in the work list. */
 125         unsigned          on_touched:1;  /**< Set, if this partition is on the touched set. */
 126         unsigned          on_cprop:1;    /**< Set, if this partition is on the cprop list. */
 127 #ifdef DEBUG_libfirm
 128         partition_t       *dbg_next;     /**< Link all partitions for debugging */
 129         unsigned          nr;            /**< A unique number for (what-)mapping, >0. */
 130 #endif
 131 };
 132
 133 typedef struct environment_t {
 134         struct obstack  obst;           /**< obstack to allocate data structures. */
 135         partition_t     *worklist;      /**< The work list. */
 136         partition_t     *cprop;         /**< The constant propagation list. */
 137         partition_t     *touched;       /**< the touched set. */
 138         partition_t     *TOP;           /**< The TOP partition. */
 139 #ifdef DEBUG_libfirm
 140         partition_t     *dbg_list;      /**< List of all partitions. */
 141 #endif
 142         set             *opcode_map;    /**< The initial opcode->partition map. */
 143         set             *opcode2id_map; /**< The opcodeMode->id map. */
 144         pmap            *type2id_map;   /**< The type->id map. */
 145         int             end_idx;        /**< -1 for local and 0 for global congruences. */
 146         int             lambda_input;   /**< Captured argument for lambda_partition(). */
 147 } environment_t;
 148
 149 /** Type of the what function. */
 150 typedef void *(*what_func)(const node_t *node, environment_t *env);
 151
 152 #define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
 153 #define set_irn_node(irn, node)   set_irn_link(irn, node)
 154
 155 /** The debug module handle. */
 156 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 157
 158 /** Next partition number. */
 159 DEBUG_ONLY(static unsigned part_nr = 0);
 160
 161 #ifdef DEBUG_libfirm
 162 /**
 163  * Dump partition to output.
 164  */
 165 static void dump_partition(const char *msg, partition_t *part) {
 166         node_t *node;
 167         int    first = 1;
 168
 169         DB((dbg, LEVEL_2, "%s part%u (%u) {\n  ", msg, part->nr, part->n_nodes));
 170         list_for_each_entry(node_t, node, &part->entries, node_list) {
 171                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
 172                 first = 0;
 173         }
 174         DB((dbg, LEVEL_2, "\n}\n"));
 175 }
 176
 177 /**
 178  * Dump all partitions.
 179  */
 180 static void dump_all_partitions(environment_t *env) {
 181         partition_t *P;
 182
 183         DB((dbg, LEVEL_2, "All partitions\n===============\n"));
 184         for (P = env->dbg_list; P != NULL; P = P->dbg_next)
 185                 dump_partition("", P);
 186 }
 187
 188 #else
 189 #define dump_partition(msg, part)
 190 #define dump_all_partitions(env)
 191 #endif
 192
 193 /**
 194  * compare two pointer values.
 195  */
 196 static int cmp_ptr(const void *elt, const void *key, size_t size) {
 197         const listmap_entry_t *e1 = elt;
 198         const listmap_entry_t *e2 = key;
 199
 200         return e1->id != e2->id;
 201 }
 202
 203 /**
 204  * Creates a new listmap.
 205  */
 206 static void new_listmap(listmap_t *map) {
 207         map->map    = new_set(cmp_ptr, 16);
 208         map->values = NULL;
 209 }
 210
 211 /**
 212  * Deletes a listmap.
 213  */
 214 static void del_listmap(listmap_t *map) {
 215         del_set(map->map);
 216 }
 217
 218 /**
 219  * Return the associated listmap entry for a given id.
 220  */
 221 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 222         listmap_entry_t key, *entry;
 223
 224         key.id   = id;
 225         key.list = NULL;
 226         key.next = NULL;
 227         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 228
 229         if (entry->list == NULL) {
 230                 /* a new entry, put into the list */
 231                 entry->next = map->values;
 232                 map->values = entry;
 233         }
 234         return entry;
 235 }
 236
 237 /**
 238  * calculate the hash value for an opcode map entry.
 239  */
 240 static unsigned opcode_hash(const opcode_key_t *entry) {
 241         return (entry->mode - (ir_mode *)0) * 9 + entry->code;
 242 }
 243
 244 /**
 245  * Compare two entries in the opcode map.
 246  */
 247 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 248         const opcode_key_t *o1 = elt;
 249         const opcode_key_t *o2 = key;
 250
 251         return o1->code != o2->code || o1->mode != o2->mode;
 252 }
 253
 254 /** Return the type of a node. */
 255 static INLINE tarval *get_node_type(const ir_node *irn) {
 256         return get_irn_node(irn)->type;
 257 }
 258
 259 /**
 260  * Create a new empty partition.
 261  */
 262 static INLINE partition_t *new_partition(environment_t *env) {
 263         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 264
 265         INIT_LIST_HEAD(&part->entries);
 266         part->cprop        = NULL;
 267         part->wl_next      = env->worklist;
 268         part->touched_next = NULL;
 269         part->cprop_next   = NULL;
 270         part->touched      = NULL;
 271         part->n_nodes      = 0;
 272         part->n_touched    = 0;
 273         part->n_inputs     = 0;
 274         part->on_worklist  = 0;
 275         part->on_touched   = 0;
 276         part->on_cprop     = 0;
 277 #ifdef DEBUG_libfirm
 278         part->dbg_next     = env->dbg_list;
 279         env->dbg_list      = part;
 280         part->nr           = part_nr++;
 281 #endif
 282
 283         return part;
 284 }
 285
 286 /**
 287  * Get the partition for a given opcode.
 288  */
 289 static INLINE partition_t *get_partition_for_irn(const ir_node *irn, environment_t *env) {
 290         opcode_entry_t key, *entry;
 291         unsigned       hash;
 292
 293         key.key.code = get_irn_opcode(irn);
 294         key.key.mode = get_irn_mode(irn);
 295         hash         = opcode_hash(&key.key);
 296
 297         entry = set_find(env->opcode_map, &key, sizeof(key), hash);
 298         if (entry == NULL) {
 299                 /* create a new partition and place it on the wait queue */
 300                 partition_t *part = new_partition(env);
 301
 302                 part->on_worklist = 1;
 303                 env->worklist     = part;
 304
 305                 key.part = part;
 306                 set_insert(env->opcode_map, &key, sizeof(key), hash);
 307                 entry = &key;
 308         }
 309         return entry->part;
 310 }
 311
 312 /**
 313  * Creates a partition node for the given IR-node and place it
 314  * into the given partition.
 315  */
 316 static void create_partition_node(ir_node *irn, partition_t *part, environment_t *env) {
 317         /* create a partition node and place it in the partition */
 318         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 319
 320         INIT_LIST_HEAD(&node->node_list);
 321         node->node         = irn;
 322         node->part         = part;
 323         node->cprop_next   = NULL;
 324         node->next         = NULL;
 325         node->type         = tarval_top; /* == tarval_U */
 326         node->on_touched   = 0;
 327         node->on_cprop     = 0;
 328         set_irn_node(irn, node);
 329
 330         list_add_tail(&node->node_list, &part->entries);
 331         ++part->n_nodes;
 332
 333         DB((dbg, LEVEL_2, "Placing %+F in partition %u\n", irn, part->nr));
 334 }
 335
 336 /**
 337  * Walker, initialize all Nodes' type to U or top and place
 338  * all nodes into the TOP partition.
 339  */
 340 static void create_initial_partitions(ir_node *irn, void *ctx) {
 341         environment_t *env  = ctx;
 342         partition_t   *part = env->TOP;
 343         int           arity;
 344
 345         create_partition_node(irn, part, env);
 346         arity = get_irn_arity(irn);
 347         if (arity > part->n_inputs)
 348                 part->n_inputs = arity;
 349 }
 350
 351 /**
 352  * Add a partition to the touched set if not already there.
 353  */
 354 static INLINE void add_to_touched(partition_t *part, environment_t *env) {
 355         if (part->on_touched == 0) {
 356                 part->touched_next = env->touched;
 357                 env->touched       = part;
 358                 part->on_touched   = 1;
 359         }
 360 }
 361
 362 /**
 363  * Add a node to the entry.partition.touched set if not already there..
 364  */
 365 static INLINE void add_to_partition_touched(node_t *y) {
 366         if (y->on_touched == 0) {
 367                 partition_t *part = y->part;
 368
 369                 y->next       = part->touched;
 370                 part->touched = y;
 371                 y->on_touched = 1;
 372                 ++part->n_touched;
 373         }
 374 }
 375
 376 /**
 377  * update the worklist
 378  */
 379 static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env) {
 380         /* If Z is on worklist then add Z' to worklist.
 381            Else add the smaller of Z and Z' to worklist. */
 382         if (Z->on_worklist || Z_prime->n_nodes < Z->n_nodes) {
 383                 Z_prime->on_worklist = 1;
 384                 Z_prime->wl_next     = env->worklist;
 385                 env->worklist        = Z_prime;
 386         } else {
 387                 Z->on_worklist = 1;
 388                 Z->wl_next     = env->worklist;
 389                 env->worklist  = Z;
 390         }
 391 }
 392
 393 /**
 394  * Split a partition by a local list.
 395  */
 396 static partition_t *split(partition_t *Z, node_t *g, environment_t *env) {
 397         partition_t *Z_prime;
 398         node_t      *node;
 399         unsigned    n = 0;
 400         int         n_inputs;
 401
 402         dump_partition("Splitting ", Z);
 403
 404         /* Remove g from Z. */
 405         for (node = g; node != NULL; node = node->next) {
 406                 list_del(&node->node_list);
 407                 ++n;
 408         }
 409         Z->n_nodes -= n;
 410
 411         /* Move g to a new partition, Z\92. */
 412         Z_prime = new_partition(env);
 413         n_inputs = 0;
 414         for (node = g; node != NULL; node = node->next) {
 415                 int arity = get_irn_arity(node->node);
 416                 list_add(&node->node_list, &Z_prime->entries);
 417                 node->part = Z_prime;
 418                 if (arity > n_inputs)
 419                         n_inputs = arity;
 420         }
 421         Z_prime->n_inputs = n_inputs;
 422         Z_prime->n_nodes  = n;
 423
 424         update_worklist(Z, Z_prime, env);
 425
 426         dump_partition("Now ", Z);
 427         dump_partition("Created new ", Z_prime);
 428         return Z_prime;
 429 }
 430
 431 /**
 432  * Returns non-zero if the i'th input of a Phi node is live.
 433  */
 434 static int is_live_input(ir_node *phi, int i) {
 435         ir_node *block = get_nodes_block(phi);
 436         ir_node *pred  = get_Block_cfgpred(block, i);
 437         tarval *type   = get_node_type(pred);
 438
 439         return type != tarval_U;
 440 }
 441
 442 /**
 443  * Split the partitions if caused by the first entry on the worklist.
 444  */
 445 static void cause_splits(environment_t *env) {
 446         partition_t *X, *Y, *Z;
 447         node_t      *x, *y, *e;
 448         int         i, end_idx;
 449
 450         /* remove the first partition from the worklist */
 451         X = env->worklist;
 452         env->worklist  = X->wl_next;
 453         X->on_worklist = 0;
 454
 455         dump_partition("Cause_split: ", X);
 456         end_idx = env->end_idx;
 457         for (i = X->n_inputs - 1; i >= -1; --i) {
 458                 /* empty the touched set: already done, just clear the list */
 459                 env->touched = NULL;
 460
 461                 list_for_each_entry(node_t, x, &X->entries, node_list) {
 462                         /* ignore the "control input" for non-pinned nodes
 463                            if we are running in GCSE mode */
 464                         if (i < end_idx && get_irn_pinned(x->node) != op_pin_state_pinned)
 465                                 continue;
 466
 467                         /* non-existing input */
 468                         if (i >= get_irn_arity(x->node))
 469                                 continue;
 470
 471                         y = get_irn_node(get_irn_n(x->node, i));
 472                         Y = y->part;
 473                         if (Y != env->TOP && (! is_Phi(x->node) || is_live_input(x->node, i))) {
 474                                 add_to_touched(Y, env);
 475                                 add_to_partition_touched(y);
 476                         }
 477                 }
 478
 479                 for (Z = env->touched; Z != NULL; Z = Z->touched_next) {
 480                         /* remove it from the touched set */
 481                         Z->on_touched = 0;
 482
 483                         if (Z->n_nodes != Z->n_touched) {
 484                                 split(Z, Z->touched, env);
 485                         }
 486                         /* Empty local Z.touched. */
 487                         for (e = Z->touched; e != NULL; e = e->next) {
 488                                 e->on_touched = 0;
 489                         }
 490                         Z->touched   = NULL;
 491                         Z->n_touched = 0;
 492                 }
 493         }
 494 }
 495
 496 /**
 497  * Implements split_by_what(): Split a partition by characteristics given
 498  * by the what function.
 499  *
 500  * @return list of partitions
 501  */
 502 static partition_t **split_by_what(partition_t *X, what_func What,
 503                                                                   partition_t**P, environment_t *env) {
 504         node_t          *x, *S;
 505         listmap_t       map;
 506         listmap_entry_t *iter;
 507         partition_t     *R;
 508
 509         /* Let map be an empty mapping from the range of What to (local) list of Nodes. */
 510         new_listmap(&map);
 511         list_for_each_entry(node_t, x, &X->entries, node_list) {
 512                 void            *id = What(x, env);
 513                 listmap_entry_t *entry;
 514
 515                 if (id == NULL) {
 516                         /* input not allowed, ignore */
 517                         continue;
 518                 }
 519                 /* Add x to map[What(x)]. */
 520                 entry = listmap_find(&map, id);
 521                 x->next     = entry->list;
 522                 entry->list = x;
 523         }
 524         /* Let P be a set of Partitions. */
 525
 526         /* for all sets S except one in the range of map do */
 527         for (iter = map.values; iter != NULL; iter = iter->next) {
 528                 if (iter->next == NULL) {
 529                         /* this is the last entry, ignore */
 530                         break;
 531                 }
 532                 S = iter->list;
 533
 534                 /* Add SPLIT( X, S ) to P. */
 535                 R = split(X, S, env);
 536                 if (P != NULL) {
 537                         ARR_APP1(partition_t *, P, R);
 538                 }
 539         }
 540         /* Add X to P. */
 541         if (P != NULL) {
 542                 ARR_APP1(partition_t *, P, X);
 543         }
 544
 545         del_listmap(&map);
 546         return P;
 547 }
 548
 549 /** lambda n.(n.type) */
 550 static void *lambda_type(const node_t *node, environment_t *env) {
 551         (void)env;
 552         return node->type;
 553 }
 554
 555 /** lambda n.(n.opcode) */
 556 static void *lambda_opcode(const node_t *node, environment_t *env) {
 557         opcode_key_t key, *entry;
 558
 559         key.code = get_irn_opcode(node->node);
 560         key.mode = get_irn_mode(node->node);
 561         entry = set_insert(env->opcode2id_map, &key, sizeof(&key), opcode_hash(&key));
 562         return entry;
 563 }
 564
 565 /** lambda n.(n[i].partition) */
 566 static void *lambda_partition(const node_t *node, environment_t *env) {
 567         ir_node *pred;
 568         node_t  *p;
 569         int     i = env->lambda_input;
 570
 571         if (i >= get_irn_arity(node->node)) {
 572                 /* we are outside the allowed range */
 573                 return NULL;
 574         }
 575
 576         /* ignore the "control input" for non-pinned nodes
 577            if we are running in GCSE mode */
 578         if (i < env->end_idx && get_irn_pinned(node->node) != op_pin_state_pinned)
 579                 return NULL;
 580
 581         pred = get_irn_n(node->node, i);
 582         p    = get_irn_node(pred);
 583
 584         return p->part;
 585 }
 586
 587 /**
 588  * Implements split_by().
 589  */
 590 static void split_by(partition_t *X, environment_t *env) {
 591         partition_t **P = NEW_ARR_F(partition_t *, 0);
 592         int         i, j, k;
 593
 594         P = split_by_what(X, lambda_type, P, env);
 595         for (i = ARR_LEN(P) - 1; i >= 0; --i) {
 596                 partition_t *Y = P[i];
 597
 598                 if (Y != env->TOP) {
 599                         partition_t **Q = NEW_ARR_F(partition_t *, 0);
 600
 601                         Q = split_by_what(Y, lambda_opcode, Q, env);
 602
 603                         for (j = ARR_LEN(Q) - 1; j >= 0; --j) {
 604                                 partition_t *Z = Q[j];
 605
 606                                 for (k = Z->n_inputs - 1; k >= -1; --k) {
 607                                         env->lambda_input = k;
 608                                         split_by_what(Z, lambda_partition, NULL, env);
 609                                 }
 610                         }
 611                         DEL_ARR_F(Q);
 612                 }
 613         }
 614         DEL_ARR_F(P);
 615 }
 616
 617 /**
 618  * (Re-)compute the type for a given node.
 619  */
 620 static void default_compute(node_t *node) {
 621         int     i;
 622         ir_node *irn = node->node;
 623         ir_mode *mode;
 624
 625         if (get_irn_pinned(irn) == op_pin_state_pinned) {
 626                 node_t *block = get_irn_node(get_nodes_block(irn));
 627
 628                 if (block->type == tarval_U) {
 629                         node->type = tarval_top;
 630                         return;
 631                 }
 632         }
 633         mode = get_irn_mode(irn);
 634         if (mode == mode_M) {
 635                 /* mode M is always bottom for now */
 636                 node->type = tarval_bottom;
 637                 return;
 638         }
 639         if (! mode_is_data(mode))
 640                 return;
 641
 642         /* if any of the data inputs have type top, the result is type top */
 643         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 644                 ir_node *pred = get_irn_n(irn, i);
 645                 node_t  *p    = get_irn_node(pred);
 646
 647                 if (p->type == tarval_top) {
 648                         node->type = tarval_top;
 649                         return;
 650                 }
 651         }
 652         node->type = computed_value(irn);
 653 }
 654
 655 /**
 656  * (Re-)compute the type for a Block node.
 657  */
 658 static void compute_Block(node_t *node) {
 659         int     i;
 660         ir_node *block = node->node;
 661
 662         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 663                 node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
 664
 665                 if (pred->type == tarval_R) {
 666                         /* A block is reachable, if at least of predecessor is reachable. */
 667                         node->type = tarval_R;
 668                         return;
 669                 }
 670         }
 671         node->type = tarval_U;
 672 }
 673
 674 /**
 675  * (Re-)compute the type for a Jmp node.
 676  */
 677 static void compute_Jmp(node_t *node) {
 678         node_t *block = get_irn_node(get_nodes_block(node->node));
 679
 680         node->type = block->type;
 681 }
 682
 683 /**
 684  * (Re-)compute the type for a Phi node.
 685  */
 686 static void compute_Phi(node_t *node) {
 687         int     i;
 688         ir_node *phi = node->node;
 689         tarval  *type = tarval_top;
 690
 691         /* if a Phi is in a unreachable block, its type is TOP */
 692         node_t *block = get_irn_node(get_nodes_block(phi));
 693
 694         if (block->type == tarval_U) {
 695                 node->type = tarval_top;
 696                 return;
 697         }
 698
 699         /* if any of the data inputs have type top, the result is type top */
 700         for (i = get_Phi_n_preds(phi) - 1; i >= 0; --i) {
 701                 node_t *pred = get_irn_node(get_Phi_pred(phi, i));
 702
 703                 if (pred->type == tarval_top) {
 704                         /* ignore TOP inputs */
 705                         continue;
 706                 }
 707                 if (pred->type == tarval_bottom) {
 708                         node->type = tarval_bottom;
 709                         return;
 710                 } else if (type == tarval_top) {
 711                         /* first constant found */
 712                         type = pred->type;
 713                 } else if (type == pred->type) {
 714                         /* same constant, continue */
 715                         continue;
 716                 } else {
 717                         /* different constants or tarval_bottom */
 718                         node->type = tarval_bottom;
 719                         return;
 720                 }
 721         }
 722         node->type = type;
 723 }
 724
 725 /**
 726  * (Re-)compute the type for a Sub. Special case: both nodes are congruent.
 727  */
 728 static void compute_Sub(node_t *node) {
 729         ir_node *sub = node->node;
 730         node_t  *l   = get_irn_node(get_Sub_left(sub));
 731         node_t  *r   = get_irn_node(get_Sub_right(sub));
 732         tarval  *a   = l->type;
 733         tarval  *b   = r->type;
 734
 735         if (a == tarval_top || b == tarval_top) {
 736                 node->type = tarval_top;
 737         } else if (r->part == l->part) {
 738                 ir_mode *mode = get_irn_mode(sub);
 739                 node->type = get_mode_null(mode);
 740         } else if (a == tarval_bottom || b == tarval_bottom) {
 741                 node->type = tarval_bottom;
 742         } else {
 743                 node->type = tarval_sub(a, b);
 744         }
 745 }
 746
 747 /**
 748  * (Re-)compute the type for a Proj(Cmp).
 749  */
 750 static void compute_Proj_Cmp(node_t *node, ir_node *cmp) {
 751         ir_node *proj = node->node;
 752         node_t  *l    = get_irn_node(get_Cmp_left(cmp));
 753         node_t  *r    = get_irn_node(get_Cmp_right(cmp));
 754         tarval  *a    = l->type;
 755         tarval  *b    = r->type;
 756         pn_Cmp  pnc   = get_Proj_proj(proj);
 757
 758         /*
 759          * BEWARE: a == a is NOT always True for floating Point values, as
 760          * NaN != NaN is defined, so we must check this here.
 761          */
 762         if (!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt ||  pnc == pn_Cmp_Gt) {
 763                 if (a == tarval_top || b == tarval_top) {
 764                         node->type = tarval_top;
 765                 } else if (r->part == l->part) {
 766                         node->type = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b);
 767                 } else if (a == tarval_bottom || b == tarval_bottom) {
 768                         node->type = tarval_bottom;
 769                 } else {
 770                         default_compute(node);
 771                 }
 772         } else {
 773                 default_compute(node);
 774         }
 775 }
 776
 777 /**
 778  * (Re-)compute the type for a Proj-Nodes.
 779  */
 780 static void compute_Proj(node_t *node) {
 781         ir_node *proj = node->node;
 782         ir_mode *mode = get_irn_mode(proj);
 783         ir_node *pred;
 784
 785         if (mode == mode_M) {
 786                 /* mode M is always bottom */
 787                 node->type = tarval_bottom;
 788                 return;
 789         }
 790         if (mode != mode_X) {
 791                 ir_node *cmp = get_Proj_pred(proj);
 792                 if (is_Cmp(cmp))
 793                         compute_Proj_Cmp(node, cmp);
 794                 else
 795                         default_compute(node);
 796                 return;
 797         }
 798         /* handle mode_X nodes */
 799         pred = get_Proj_pred(proj);
 800
 801         switch (get_irn_opcode(pred)) {
 802         case iro_Start:
 803                 /* the Proj_X from the Start is always reachable */
 804                 node->type = tarval_R;
 805                 break;
 806         default:
 807                 default_compute(node);
 808         }
 809 }
 810
 811 /**
 812  * (Re-)compute the type for a given node.
 813  */
 814 static void compute(node_t *node) {
 815         compute_func func = (compute_func)node->node->op->ops.generic;
 816
 817         if (func != NULL)
 818                 func(node);
 819 }
 820
 821 /**
 822  * place a node on the cprop list.
 823  */
 824 static void add_node_to_cprop(node_t *y, environment_t *env) {
 825         /* Add y to y.partition.cprop. */
 826         if (y->on_cprop == 0) {
 827                 partition_t *Y = y->part;
 828
 829                 y->cprop_next  = Y->cprop;
 830                 Y->cprop = y;
 831                 y->on_cprop    = 1;
 832
 833                 /* place its partition on the cprop list */
 834                 if (Y->on_cprop == 0) {
 835                         Y->cprop_next = env->cprop;
 836                         env->cprop    = Y;
 837                         Y->on_cprop   = 1;
 838                 }
 839         }
 840 }
 841
 842 /**
 843  * Propagate constant evaluation.
 844  */
 845 static void propagate(environment_t *env) {
 846         partition_t *X, *Y;
 847         node_t      *x;
 848         tarval      *old_type;
 849         node_t      *fallen = NULL;
 850         unsigned    n_fallen = 0;
 851         int         i;
 852
 853         while (env->cprop != NULL) {
 854                 /* remove a partition X from cprop */
 855                 X           = env->cprop;
 856                 X->on_cprop = 0;
 857                 env->cprop  = X->cprop_next;
 858
 859                 while (X->cprop != NULL) {
 860                         /* remove a Node x from X.cprop */
 861                         x = X->cprop;
 862                         x->on_cprop = 0;
 863                         X->cprop = x->cprop_next;
 864
 865                         /* compute a new type for x */
 866                         old_type = x->type;
 867                         compute(x);
 868                         if (x->type != old_type) {
 869                                 DB((dbg, LEVEL_2, "node %+F has changed type from %T to %T\n", x->node, old_type, x->type));
 870                                 /* Add x to fallen. */
 871                                 x->next = fallen;
 872                                 fallen  = x;
 873                                 ++n_fallen;
 874
 875                                 for (i = get_irn_n_outs(x->node) - 1; i >= 0; --i) {
 876                                         ir_node *succ = get_irn_out(x->node, i);
 877                                         node_t  *y    = get_irn_node(succ);
 878
 879                                         /* Add y to y.partition.cprop. */
 880                                         add_node_to_cprop(y, env);
 881                                 }
 882                         }
 883                 }
 884                 if (n_fallen != X->n_nodes) {
 885                         Y = split(X, fallen, env);
 886                 } else {
 887                         Y = X;
 888                 }
 889                 split_by(Y, env);
 890         }
 891 }
 892
 893 /**
 894  * Get the leader for a given node from its congruence class.
 895  *
 896  * @param irn  the node
 897  */
 898 static ir_node *get_leader(ir_node *irn) {
 899         partition_t *part = get_irn_node(irn)->part;
 900
 901         if (part->n_nodes > 1) {
 902                 DB((dbg, LEVEL_2, "Found congruence class for %+F ", irn));
 903                 dump_partition("", part);
 904         }
 905         return irn;
 906 }
 907
 908 /**
 909  * Post-Walker, apply the analysis results;
 910  */
 911 static void apply_result(ir_node *irn, void *ctx) {
 912         environment_t *env = ctx;
 913
 914         if (is_no_Block(irn)) {
 915                 ir_node *leader = get_leader(irn);
 916
 917                 if (leader != irn) {
 918                         exchange(irn, leader);
 919                 }
 920         }
 921 }
 922
 923 #define SET(code) op_##code->ops.generic = (op_func)compute_##code
 924
 925 /**
 926  * sets the generic functions to compute.
 927  */
 928 static void set_compute_functions(void) {
 929         int i;
 930
 931         /* set the default compute function */
 932         for (i = get_irp_n_opcodes() - 1; i >= 0; --i) {
 933                 ir_op *op = get_irp_opcode(i);
 934                 op->ops.generic = (op_func)default_compute;
 935         }
 936
 937         /* set specific functions */
 938         SET(Block);
 939         SET(Jmp);
 940         SET(Phi);
 941         SET(Sub);
 942 }
 943
 944 void combo(ir_graph *irg) {
 945         environment_t env;
 946         ir_node       *start_bl, *initial_X;
 947         node_t        *start;
 948         ir_graph      *rem = current_ir_graph;
 949
 950         current_ir_graph = irg;
 951
 952         /* register a debug mask */
 953         FIRM_DBG_REGISTER(dbg, "firm.opt.combo");
 954         firm_dbg_set_mask(dbg, SET_LEVEL_2);
 955
 956         obstack_init(&env.obst);
 957         env.worklist       = NULL;
 958         env.cprop          = NULL;
 959         env.touched        = NULL;
 960         env.TOP            = NULL;
 961 #ifdef DEBUG_libfirm
 962         env.dbg_list       = NULL;
 963 #endif
 964         env.opcode_map     = new_set(cmp_opcode, iro_Last * 4);
 965         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
 966         env.type2id_map    = pmap_create();
 967         env.end_idx        = get_opt_global_cse() ? 0 : -1;
 968         env.lambda_input   = 0;
 969
 970         assure_irg_outs(irg);
 971
 972         /* we have our own value_of function */
 973         set_value_of_func(get_node_type);
 974
 975         set_compute_functions();
 976
 977         /* create the initial TOP partition and place it on the work list */
 978         env.TOP = new_partition(&env);
 979         env.TOP->wl_next = env.worklist;
 980         env.worklist     = env.TOP;
 981         irg_walk_graph(irg, NULL, create_initial_partitions, &env);
 982
 983         /* Place the START Node's partition on cprop.
 984            Place the START Node on its local worklist. */
 985         start_bl = get_irg_start_block(irg);
 986         start    = get_irn_node(start_bl);
 987         add_node_to_cprop(start, &env);
 988
 989         /* set the initial exec to R */
 990         initial_X = get_irg_initial_exec(irg);
 991         get_irn_node(initial_X)->type = tarval_R;
 992
 993         while (env.cprop != NULL || env.worklist != NULL) {
 994                 propagate(&env);
 995                 if (env.worklist != NULL)
 996                         cause_splits(&env);
 997         }
 998
 999         dump_all_partitions(&env);
1000
1001         /* apply the result */
1002         irg_walk_graph(irg, NULL, apply_result, &env);
1003
1004         pmap_destroy(env.type2id_map);
1005         del_set(env.opcode_map);
1006         del_set(env.opcode2id_map);
1007         obstack_free(&env.obst, NULL);
1008
1009         /* restore value_of() default behavior */
1010         set_value_of_func(NULL);
1011         current_ir_graph = rem;
1012 }