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 further 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/entity, 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 "archop.h"
  38 #include "irflag.h"
  39 #include "ircons.h"
  40 #include "list.h"
  41 #include "set.h"
  42 #include "pmap.h"
  43 #include "obstack.h"
  44 #include "irgraph_t.h"
  45 #include "irnode_t.h"
  46 #include "iropt_t.h"
  47 #include "irgwalk.h"
  48 #include "irop.h"
  49 #include "irouts.h"
  50 #include "irgmod.h"
  51 #include "iropt_dbg.h"
  52 #include "debug.h"
  53 #include "error.h"
  54
  55 #include "tv_t.h"
  56
  57 #include "irprintf.h"
  58 #include "irdump.h"
  59
  60 /* define this to check that all type translations are monotone */
  61 #undef VERIFY_MONOTONE
  62
  63 /* define this to check the consistency of partitions */
  64 #define CHECK_PARTITIONS
  65
  66 /* define this to disable followers (may be buggy) */
  67 #undef NO_FOLLOWER
  68
  69 typedef struct node_t            node_t;
  70 typedef struct partition_t       partition_t;
  71 typedef struct opcode_key_t      opcode_key_t;
  72 typedef struct listmap_entry_t   listmap_entry_t;
  73
  74 /** The type of the compute function. */
  75 typedef void (*compute_func)(node_t *node);
  76
  77 /**
  78  * An opcode map key.
  79  */
  80 struct opcode_key_t {
  81         ir_opcode   code;   /**< The Firm opcode. */
  82         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  83         int         arity;  /**< The arity of this opcode (needed for Phi etc. */
  84         union {
  85                 long      proj;   /**< For Proj nodes, its proj number */
  86                 ir_entity *ent;   /**< For Sel Nodes, its entity */
  87         } u;
  88 };
  89
  90 /**
  91  * An entry in the list_map.
  92  */
  93 struct listmap_entry_t {
  94         void            *id;    /**< The id. */
  95         node_t          *list;  /**< The associated list for this id. */
  96         listmap_entry_t *next;  /**< Link to the next entry in the map. */
  97 };
  98
  99 /** We must map id's to lists. */
 100 typedef struct listmap_t {
 101         set             *map;    /**< Map id's to listmap_entry_t's */
 102         listmap_entry_t *values; /**< List of all values in the map. */
 103 } listmap_t;
 104
 105 /**
 106  * A lattice element. Because we handle constants and symbolic constants different, we
 107  * have to use this union.
 108  */
 109 typedef union {
 110         tarval          *tv;
 111         symconst_symbol sym;
 112 } lattice_elem_t;
 113
 114 /**
 115  * A node.
 116  */
 117 struct node_t {
 118         ir_node         *node;          /**< The IR-node itself. */
 119         list_head       node_list;      /**< Double-linked list of leader/follower entries. */
 120         list_head       cprop_list;     /**< Double-linked partition.cprop list. */
 121         partition_t     *part;          /**< points to the partition this node belongs to */
 122         node_t          *next;          /**< Next node on local list (partition.touched, fallen). */
 123         node_t          *race_next;     /**< Next node on race list. */
 124         lattice_elem_t  type;           /**< The associated lattice element "type". */
 125         int             max_user_input; /**< Maximum input number of Def-Use edges. */
 126         int             next_edge;      /**< Index of the next Def-Use edge to use. */
 127         int             n_followers;    /**< Number of Follower in the outs set. */
 128         unsigned        on_touched:1;   /**< Set, if this node is on the partition.touched set. */
 129         unsigned        on_cprop:1;     /**< Set, if this node is on the partition.cprop list. */
 130         unsigned        on_fallen:1;    /**< Set, if this node is on the fallen list. */
 131         unsigned        is_follower:1;  /**< Set, if this node is a follower. */
 132         unsigned        by_all_const:1; /**< Set, if this node was once evaluated by all constants. */
 133         unsigned        flagged:2;      /**< 2 Bits, set if this node was visited by race 1 or 2. */
 134 };
 135
 136 /**
 137  * A partition containing congruent nodes.
 138  */
 139 struct partition_t {
 140         list_head         Leader;          /**< The head of partition Leader node list. */
 141         list_head         Follower;        /**< The head of partition Follower node list. */
 142         list_head         cprop;           /**< The head of partition.cprop list. */
 143         partition_t       *wl_next;        /**< Next entry in the work list if any. */
 144         partition_t       *touched_next;   /**< Points to the next partition in the touched set. */
 145         partition_t       *cprop_next;     /**< Points to the next partition in the cprop list. */
 146         partition_t       *split_next;     /**< Points to the next partition in the list that must be split by split_by(). */
 147         node_t            *touched;        /**< The partition.touched set of this partition. */
 148         unsigned          n_leader;        /**< Number of entries in this partition.Leader. */
 149         unsigned          n_touched;       /**< Number of entries in the partition.touched. */
 150         int               max_user_inputs; /**< Maximum number of user inputs of all entries. */
 151         unsigned          on_worklist:1;   /**< Set, if this partition is in the work list. */
 152         unsigned          on_touched:1;    /**< Set, if this partition is on the touched set. */
 153         unsigned          on_cprop:1;      /**< Set, if this partition is on the cprop list. */
 154         unsigned          type_is_T_or_C:1;/**< Set, if all nodes in this partition have type Top or Constant. */
 155 #ifdef DEBUG_libfirm
 156         partition_t       *dbg_next;       /**< Link all partitions for debugging */
 157         unsigned          nr;              /**< A unique number for (what-)mapping, >0. */
 158 #endif
 159 };
 160
 161 typedef struct environment_t {
 162         struct obstack  obst;           /**< obstack to allocate data structures. */
 163         partition_t     *worklist;      /**< The work list. */
 164         partition_t     *cprop;         /**< The constant propagation list. */
 165         partition_t     *touched;       /**< the touched set. */
 166         partition_t     *initial;       /**< The initial partition. */
 167         set             *opcode2id_map; /**< The opcodeMode->id map. */
 168         pmap            *type2id_map;   /**< The type->id map. */
 169         int             end_idx;        /**< -1 for local and 0 for global congruences. */
 170         int             lambda_input;   /**< Captured argument for lambda_partition(). */
 171         char            nonstd_cond;    /**< Set, if a Condb note has a non-Cmp predecessor. */
 172         char            modified;       /**< Set, if the graph was modified. */
 173 #ifdef DEBUG_libfirm
 174         partition_t     *dbg_list;      /**< List of all partitions. */
 175 #endif
 176 } environment_t;
 177
 178 /** Type of the what function. */
 179 typedef void *(*what_func)(const node_t *node, environment_t *env);
 180
 181 #define get_irn_node(follower)         ((node_t *)get_irn_link(follower))
 182 #define set_irn_node(follower, node)   set_irn_link(follower, node)
 183
 184 /* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
 185 #undef tarval_unreachable
 186 #define tarval_unreachable tarval_top
 187
 188
 189 /** The debug module handle. */
 190 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 191
 192 /** Next partition number. */
 193 DEBUG_ONLY(static unsigned part_nr = 0);
 194
 195 /** The tarval returned by Unknown nodes. */
 196 static tarval *tarval_UNKNOWN;
 197
 198 /* forward */
 199 static node_t *identity(node_t *node);
 200
 201 #ifdef CHECK_PARTITIONS
 202 /**
 203  * Check a partition.
 204  */
 205 static void check_partition(const partition_t *T) {
 206         node_t   *node;
 207         unsigned n = 0;
 208
 209         list_for_each_entry(node_t, node, &T->Leader, node_list) {
 210                 assert(node->is_follower == 0);
 211                 assert(node->flagged == 0);
 212                 assert(node->part == T);
 213                 ++n;
 214         }
 215         assert(n == T->n_leader);
 216
 217         list_for_each_entry(node_t, node, &T->Follower, node_list) {
 218                 assert(node->is_follower == 1);
 219                 assert(node->flagged == 0);
 220                 assert(node->part == T);
 221         }
 222 }  /* check_partition */
 223
 224 static void check_all_partitions(environment_t *env) {
 225         partition_t *P;
 226         node_t      *node;
 227
 228         for (P = env->dbg_list; P != NULL; P = P->dbg_next) {
 229                 check_partition(P);
 230                 list_for_each_entry(node_t, node, &P->Follower, node_list) {
 231                         node_t *leader = identity(node);
 232
 233                         assert(leader != node && leader->part == node->part);
 234                 }
 235         }
 236 }
 237
 238 /**
 239  * Check list.
 240  */
 241 static void do_check_list(const node_t *list, int ofs, const partition_t *Z) {
 242         const node_t *e;
 243
 244 #define NEXT(e)  *((const node_t **)((char *)(e) + (ofs)))
 245         for (e = list; e != NULL; e = NEXT(e)) {
 246                 assert(e->part == Z);
 247         }
 248 #undef NEXT
 249 }  /* ido_check_list */
 250
 251 /**
 252  * Check a local list.
 253  */
 254 static void check_list(const node_t *list, const partition_t *Z) {
 255         do_check_list(list, offsetof(node_t, next), Z);
 256 }  /* check_list */
 257
 258 #else
 259 #define check_partition(T)
 260 #define check_list(list, Z)
 261 #define check_all_partitions(env)
 262 #endif /* CHECK_PARTITIONS */
 263
 264 #ifdef DEBUG_libfirm
 265 static INLINE lattice_elem_t get_partition_type(const partition_t *X);
 266
 267 /**
 268  * Dump partition to output.
 269  */
 270 static void dump_partition(const char *msg, const partition_t *part) {
 271         const node_t   *node;
 272         int            first = 1;
 273         lattice_elem_t type = get_partition_type(part);
 274
 275         DB((dbg, LEVEL_2, "%s part%u%s (%u, %+F) {\n  ",
 276                 msg, part->nr, part->type_is_T_or_C ? "*" : "",
 277                 part->n_leader, type));
 278         list_for_each_entry(node_t, node, &part->Leader, node_list) {
 279                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
 280                 first = 0;
 281         }
 282         if (! list_empty(&part->Follower)) {
 283                 DB((dbg, LEVEL_2, "\n---\n  "));
 284                 first = 1;
 285                 list_for_each_entry(node_t, node, &part->Follower, node_list) {
 286                         DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
 287                         first = 0;
 288                 }
 289         }
 290         DB((dbg, LEVEL_2, "\n}\n"));
 291 }  /* dump_partition */
 292
 293 /**
 294  * Dumps a list.
 295  */
 296 static void do_dump_list(const char *msg, const node_t *node, int ofs) {
 297         const node_t *p;
 298         int          first = 1;
 299
 300 #define GET_LINK(p, ofs)  *((const node_t **)((char *)(p) + (ofs)))
 301
 302         DB((dbg, LEVEL_3, "%s = {\n  ", msg));
 303         for (p = node; p != NULL; p = GET_LINK(p, ofs)) {
 304                 DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->node));
 305                 first = 0;
 306         }
 307         DB((dbg, LEVEL_3, "\n}\n"));
 308
 309 #undef GET_LINK
 310 }
 311
 312 /**
 313  * Dumps a race list.
 314  */
 315 static void dump_race_list(const char *msg, const node_t *list) {
 316         do_dump_list(msg, list, offsetof(node_t, race_next));
 317 }
 318
 319 /**
 320  * Dumps a local list.
 321  */
 322 static void dump_list(const char *msg, const node_t *list) {
 323         do_dump_list(msg, list, offsetof(node_t, next));
 324 }
 325
 326 /**
 327  * Dump all partitions.
 328  */
 329 static void dump_all_partitions(const environment_t *env) {
 330         const partition_t *P;
 331
 332         DB((dbg, LEVEL_2, "All partitions\n===============\n"));
 333         for (P = env->dbg_list; P != NULL; P = P->dbg_next)
 334                 dump_partition("", P);
 335 }
 336
 337 #else
 338 #define dump_partition(msg, part)
 339 #define dump_race_list(msg, list)
 340 #define dump_list(msg, list)
 341 #define dump_all_partitions(env)
 342 #endif
 343
 344 #if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
 345 /**
 346  * Verify that a type transition is monotone
 347  */
 348 static void verify_type(const lattice_elem_t old_type, const lattice_elem_t new_type) {
 349         if (old_type.tv == new_type.tv) {
 350                 /* no change */
 351                 return;
 352         }
 353         if (old_type.tv == tarval_top) {
 354                 /* from Top down-to is always allowed */
 355                 return;
 356         }
 357         if (old_type.tv == tarval_reachable) {
 358                 panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type);
 359         }
 360         if (new_type.tv == tarval_bottom || new_type.tv == tarval_reachable) {
 361                 /* bottom reached */
 362                 return;
 363         }
 364         panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type);
 365 }
 366 #else
 367 #define verify_type(old_type, new_type)
 368 #endif
 369
 370 /**
 371  * Compare two pointer values of a listmap.
 372  */
 373 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
 374         const listmap_entry_t *e1 = elt;
 375         const listmap_entry_t *e2 = key;
 376
 377         (void) size;
 378         return e1->id != e2->id;
 379 }  /* listmap_cmp_ptr */
 380
 381 /**
 382  * Initializes a listmap.
 383  *
 384  * @param map  the listmap
 385  */
 386 static void listmap_init(listmap_t *map) {
 387         map->map    = new_set(listmap_cmp_ptr, 16);
 388         map->values = NULL;
 389 }  /* listmap_init */
 390
 391 /**
 392  * Terminates a listmap.
 393  *
 394  * @param map  the listmap
 395  */
 396 static void listmap_term(listmap_t *map) {
 397         del_set(map->map);
 398 }  /* listmap_term */
 399
 400 /**
 401  * Return the associated listmap entry for a given id.
 402  *
 403  * @param map  the listmap
 404  * @param id   the id to search for
 405  *
 406  * @return the asociated listmap entry for the given id
 407  */
 408 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 409         listmap_entry_t key, *entry;
 410
 411         key.id   = id;
 412         key.list = NULL;
 413         key.next = NULL;
 414         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 415
 416         if (entry->list == NULL) {
 417                 /* a new entry, put into the list */
 418                 entry->next = map->values;
 419                 map->values = entry;
 420         }
 421         return entry;
 422 }  /* listmap_find */
 423
 424 /**
 425  * Calculate the hash value for an opcode map entry.
 426  *
 427  * @param entry  an opcode map entry
 428  *
 429  * @return a hash value for the given opcode map entry
 430  */
 431 static unsigned opcode_hash(const opcode_key_t *entry) {
 432         return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent);
 433 }  /* opcode_hash */
 434
 435 /**
 436  * Compare two entries in the opcode map.
 437  */
 438 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 439         const opcode_key_t *o1 = elt;
 440         const opcode_key_t *o2 = key;
 441
 442         (void) size;
 443         return o1->code != o2->code || o1->mode != o2->mode ||
 444                o1->arity != o2->arity ||
 445                o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
 446 }  /* cmp_opcode */
 447
 448 /**
 449  * Compare two Def-Use edges for input position.
 450  */
 451 static int cmp_def_use_edge(const void *a, const void *b) {
 452         const ir_def_use_edge *ea = a;
 453         const ir_def_use_edge *eb = b;
 454
 455         /* no overrun, because range is [-1, MAXINT] */
 456         return ea->pos - eb->pos;
 457 }  /* cmp_def_use_edge */
 458
 459 /**
 460  * We need the Def-Use edges sorted.
 461  */
 462 static void sort_irn_outs(node_t *node) {
 463         ir_node *irn = node->node;
 464         int n_outs = get_irn_n_outs(irn);
 465
 466         if (n_outs > 1) {
 467                 qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge);
 468         }
 469         node->max_user_input = irn->out[n_outs].pos;
 470 }  /* sort_irn_outs */
 471
 472 /**
 473  * Return the type of a node.
 474  *
 475  * @param irn  an IR-node
 476  *
 477  * @return the associated type of this node
 478  */
 479 static INLINE lattice_elem_t get_node_type(const ir_node *irn) {
 480         return get_irn_node(irn)->type;
 481 }  /* get_node_type */
 482
 483 /**
 484  * Return the tarval of a node.
 485  *
 486  * @param irn  an IR-node
 487  *
 488  * @return the associated type of this node
 489  */
 490 static INLINE tarval *get_node_tarval(const ir_node *irn) {
 491         lattice_elem_t type = get_node_type(irn);
 492
 493         if (is_tarval(type.tv))
 494                 return type.tv;
 495         return tarval_bottom;
 496 }  /* get_node_type */
 497
 498 /**
 499  * Add a partition to the worklist.
 500  */
 501 static INLINE void add_to_worklist(partition_t *X, environment_t *env) {
 502         assert(X->on_worklist == 0);
 503         X->wl_next     = env->worklist;
 504         X->on_worklist = 1;
 505         env->worklist  = X;
 506 }  /* add_to_worklist */
 507
 508 /**
 509  * Create a new empty partition.
 510  *
 511  * @param env   the environment
 512  *
 513  * @return a newly allocated partition
 514  */
 515 static INLINE partition_t *new_partition(environment_t *env) {
 516         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 517
 518         INIT_LIST_HEAD(&part->Leader);
 519         INIT_LIST_HEAD(&part->Follower);
 520         INIT_LIST_HEAD(&part->cprop);
 521         part->wl_next         = NULL;
 522         part->touched_next    = NULL;
 523         part->cprop_next      = NULL;
 524         part->split_next      = NULL;
 525         part->touched         = NULL;
 526         part->n_leader        = 0;
 527         part->n_touched       = 0;
 528         part->max_user_inputs = 0;
 529         part->on_worklist     = 0;
 530         part->on_touched      = 0;
 531         part->on_cprop        = 0;
 532         part->type_is_T_or_C  = 0;
 533 #ifdef DEBUG_libfirm
 534         part->dbg_next        = env->dbg_list;
 535         env->dbg_list         = part;
 536         part->nr              = part_nr++;
 537 #endif
 538
 539         return part;
 540 }  /* new_partition */
 541
 542 /**
 543  * Get the first node from a partition.
 544  */
 545 static INLINE node_t *get_first_node(const partition_t *X) {
 546         return list_entry(X->Leader.next, node_t, node_list);
 547 }  /* get_first_node */
 548
 549 /**
 550  * Return the type of a partition (assuming partition is non-empty and
 551  * all elements have the same type).
 552  *
 553  * @param X  a partition
 554  *
 555  * @return the type of the first element of the partition
 556  */
 557 static INLINE lattice_elem_t get_partition_type(const partition_t *X) {
 558         const node_t *first = get_first_node(X);
 559         return first->type;
 560 }  /* get_partition_type */
 561
 562 /**
 563  * Creates a partition node for the given IR-node and place it
 564  * into the given partition.
 565  *
 566  * @param irn   an IR-node
 567  * @param part  a partition to place the node in
 568  * @param env   the environment
 569  *
 570  * @return the created node
 571  */
 572 static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env) {
 573         /* create a partition node and place it in the partition */
 574         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 575
 576         INIT_LIST_HEAD(&node->node_list);
 577         INIT_LIST_HEAD(&node->cprop_list);
 578         node->node           = irn;
 579         node->part           = part;
 580         node->next           = NULL;
 581         node->race_next      = NULL;
 582         node->type.tv        = tarval_top;
 583         node->max_user_input = 0;
 584         node->next_edge      = 0;
 585         node->n_followers    = 0;
 586         node->on_touched     = 0;
 587         node->on_cprop       = 0;
 588         node->on_fallen      = 0;
 589         node->is_follower    = 0;
 590         node->by_all_const   = 0;
 591         node->flagged        = 0;
 592         set_irn_node(irn, node);
 593
 594         list_add_tail(&node->node_list, &part->Leader);
 595         ++part->n_leader;
 596
 597         return node;
 598 }  /* create_partition_node */
 599
 600 /**
 601  * Pre-Walker, init all Block-Phi lists.
 602  */
 603 static void init_block_phis(ir_node *irn, void *env) {
 604         (void) env;
 605
 606         if (is_Block(irn)) {
 607                 set_Block_phis(irn, NULL);
 608         }
 609 }  /* init_block_phis */
 610
 611 /**
 612  * Post-Walker, initialize all Nodes' type to U or top and place
 613  * all nodes into the TOP partition.
 614  */
 615 static void create_initial_partitions(ir_node *irn, void *ctx) {
 616         environment_t *env  = ctx;
 617         partition_t   *part = env->initial;
 618         node_t        *node;
 619
 620         node = create_partition_node(irn, part, env);
 621         sort_irn_outs(node);
 622         if (node->max_user_input > part->max_user_inputs)
 623                 part->max_user_inputs = node->max_user_input;
 624
 625         if (is_Phi(irn)) {
 626                 add_Block_phi(get_nodes_block(irn), irn);
 627         } else if (is_Cond(irn)) {
 628                 /* check if all Cond's have a Cmp predecessor. */
 629                 if (get_irn_mode(irn) == mode_b && !is_Cmp(skip_Proj(get_Cond_selector(irn))))
 630                         env->nonstd_cond = 1;
 631
 632         }
 633 }  /* create_initial_partitions */
 634
 635 /**
 636  * Add a node to the entry.partition.touched set and
 637  * node->partition to the touched set if not already there.
 638  *
 639  * @param y    a node
 640  * @param env  the environment
 641  */
 642 static INLINE void add_to_touched(node_t *y, environment_t *env) {
 643         if (y->on_touched == 0) {
 644                 partition_t *part = y->part;
 645
 646                 y->next       = part->touched;
 647                 part->touched = y;
 648                 y->on_touched = 1;
 649                 ++part->n_touched;
 650
 651                 if (part->on_touched == 0) {
 652                         part->touched_next = env->touched;
 653                         env->touched       = part;
 654                         part->on_touched   = 1;
 655                 }
 656
 657                 check_list(part->touched, part);
 658         }
 659 }  /* add_to_touched */
 660
 661 /**
 662  * Place a node on the cprop list.
 663  *
 664  * @param y    the node
 665  * @param env  the environment
 666  */
 667 static void add_to_cprop(node_t *y, environment_t *env) {
 668         /* Add y to y.partition.cprop. */
 669         if (y->on_cprop == 0) {
 670                 partition_t *Y = y->part;
 671
 672                 list_add_tail(&y->cprop_list, &Y->cprop);
 673                 y->on_cprop   = 1;
 674
 675                 DB((dbg, LEVEL_3, "Add %+F to part%u.cprop\n", y->node, Y->nr));
 676
 677                 /* place its partition on the cprop list */
 678                 if (Y->on_cprop == 0) {
 679                         Y->cprop_next = env->cprop;
 680                         env->cprop    = Y;
 681                         Y->on_cprop   = 1;
 682                 }
 683         }
 684         if (get_irn_mode(y->node) == mode_T) {
 685                 /* mode_T nodes always produce tarval_bottom, so we must explicitly
 686                    add it's Proj's to get constant evaluation to work */
 687                 int i;
 688
 689                 for (i = get_irn_n_outs(y->node) - 1; i >= 0; --i) {
 690                         node_t *proj = get_irn_node(get_irn_out(y->node, i));
 691
 692                         add_to_cprop(proj, env);
 693                 }
 694         } else if (is_Block(y->node)) {
 695                 /* Due to the way we handle Phi's, we must place all Phis of a block on the list
 696                  * if someone placed the block. The Block is only placed if the reachability
 697                  * changes, and this must be re-evaluated in compute_Phi(). */
 698                 ir_node *phi;
 699                 for (phi = get_Block_phis(y->node); phi != NULL; phi = get_Phi_next(phi)) {
 700                         node_t *p = get_irn_node(phi);
 701                         add_to_cprop(p, env);
 702                 }
 703         }
 704 }  /* add_to_cprop */
 705
 706 /**
 707  * Update the worklist: If Z is on worklist then add Z' to worklist.
 708  * Else add the smaller of Z and Z' to worklist.
 709  *
 710  * @param Z        the Z partition
 711  * @param Z_prime  the Z' partition, a previous part of Z
 712  * @param env      the environment
 713  */
 714 static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env) {
 715         if (Z->on_worklist || Z_prime->n_leader < Z->n_leader) {
 716                 add_to_worklist(Z_prime, env);
 717         } else {
 718                 add_to_worklist(Z, env);
 719         }
 720 }  /* update_worklist */
 721
 722 /**
 723  * Make all inputs to x no longer be F.def_use edges.
 724  *
 725  * @param x  the node
 726  */
 727 static void move_edges_to_leader(node_t *x) {
 728         ir_node     *irn = x->node;
 729         int         i, j, k;
 730
 731         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 732                 node_t  *pred = get_irn_node(get_irn_n(irn, i));
 733                 ir_node *p;
 734                 int     n;
 735
 736                 p = pred->node;
 737                 n = get_irn_n_outs(p);
 738                 for (j = 1; j <= pred->n_followers; ++j) {
 739                         if (p->out[j].pos == i && p->out[j].use == irn) {
 740                                 /* found a follower edge to x, move it to the Leader */
 741                                 ir_def_use_edge edge = p->out[j];
 742
 743                                 /* remove this edge from the Follower set */
 744                                 p->out[j] = p->out[pred->n_followers];
 745                                 --pred->n_followers;
 746
 747                                 /* sort it into the leader set */
 748                                 for (k = pred->n_followers + 2; k <= n; ++k) {
 749                                         if (p->out[k].pos >= edge.pos)
 750                                                 break;
 751                                         p->out[k - 1] = p->out[k];
 752                                 }
 753                                 /* place the new edge here */
 754                                 p->out[k - 1] = edge;
 755
 756                                 /* edge found and moved */
 757                                 break;
 758                         }
 759                 }
 760         }
 761 }  /* move_edges_to_leader */
 762
 763 /**
 764  * Split a partition that has NO followers by a local list.
 765  *
 766  * @param Z    partition to split
 767  * @param g    a (non-empty) node list
 768  * @param env  the environment
 769  *
 770  * @return  a new partition containing the nodes of g
 771  */
 772 static partition_t *split_no_followers(partition_t *Z, node_t *g, environment_t *env) {
 773         partition_t *Z_prime;
 774         node_t      *node;
 775         unsigned    n = 0;
 776         int         max_input;
 777
 778         dump_partition("Splitting ", Z);
 779         dump_list("by list ", g);
 780
 781         assert(g != NULL);
 782
 783         /* Remove g from Z. */
 784         for (node = g; node != NULL; node = node->next) {
 785                 assert(node->part == Z);
 786                 list_del(&node->node_list);
 787                 ++n;
 788         }
 789         assert(n < Z->n_leader);
 790         Z->n_leader -= n;
 791
 792         /* Move g to a new partition, Z'. */
 793         Z_prime = new_partition(env);
 794         max_input = 0;
 795         for (node = g; node != NULL; node = node->next) {
 796                 list_add_tail(&node->node_list, &Z_prime->Leader);
 797                 node->part = Z_prime;
 798                 if (node->max_user_input > max_input)
 799                         max_input = node->max_user_input;
 800         }
 801         Z_prime->max_user_inputs = max_input;
 802         Z_prime->n_leader        = n;
 803
 804         check_partition(Z);
 805         check_partition(Z_prime);
 806
 807         /* for now, copy the type info tag, it will be adjusted in split_by(). */
 808         Z_prime->type_is_T_or_C = Z->type_is_T_or_C;
 809
 810         update_worklist(Z, Z_prime, env);
 811
 812         dump_partition("Now ", Z);
 813         dump_partition("Created new ", Z_prime);
 814         return Z_prime;
 815 }  /* split_no_followers */
 816
 817 #ifdef NO_FOLLOWER
 818
 819 #define split(Z, g, env) split_no_followers(*(Z), g, env)
 820
 821 #else
 822
 823 /**
 824  * Make the Follower -> Leader transition for a node.
 825  *
 826  * @param n  the node
 827  */
 828 static void follower_to_leader(node_t *n) {
 829         assert(n->is_follower == 1);
 830
 831         DB((dbg, LEVEL_2, "%+F make the follower -> leader transition\n", n->node));
 832         n->is_follower = 0;
 833         move_edges_to_leader(n);
 834         list_del(&n->node_list);
 835         list_add_tail(&n->node_list, &n->part->Leader);
 836         ++n->part->n_leader;
 837 }  /* follower_to_leader */
 838
 839 /**
 840  * The environment for one race step.
 841  */
 842 typedef struct step_env {
 843         node_t   *initial;    /**< The initial node list. */
 844         node_t   *unwalked;   /**< The unwalked node list. */
 845         node_t   *walked;     /**< The walked node list. */
 846         int      index;       /**< Next index of Follower use_def edge. */
 847         unsigned side;        /**< side number. */
 848 } step_env;
 849
 850 /**
 851  * Return non-zero, if a input is a real follower
 852  *
 853  * @param irn    the node to check
 854  * @param input  number of the input
 855  */
 856 static int is_real_follower(const ir_node *irn, int input) {
 857         node_t *pred;
 858
 859         switch (get_irn_opcode(irn)) {
 860         case iro_Confirm:
 861                 if (input == 1) {
 862                         /* ignore the Confirm bound input */
 863                         return 0;
 864                 }
 865                 break;
 866         case iro_Mux:
 867                 if (input == 0) {
 868                         /* ignore the Mux sel input */
 869                         return 0;
 870                 }
 871                 break;
 872         case iro_Phi: {
 873                 /* dead inputs are not follower edges */
 874                 ir_node *block = get_nodes_block(irn);
 875                 node_t  *pred  = get_irn_node(get_Block_cfgpred(block, input));
 876
 877                 if (pred->type.tv == tarval_unreachable)
 878                         return 0;
 879                 break;
 880         }
 881         case iro_Sub:
 882         case iro_Shr:
 883         case iro_Shl:
 884         case iro_Shrs:
 885         case iro_Rotl:
 886                 if (input == 1) {
 887                         /* only a Sub x,0 / Shift x,0 might be a follower */
 888                         return 0;
 889                 }
 890                 break;
 891         case iro_Add:
 892         case iro_Or:
 893         case iro_Eor:
 894                 pred = get_irn_node(get_irn_n(irn, input));
 895                 if (is_tarval(pred->type.tv) && tarval_is_null(pred->type.tv))
 896                         return 0;
 897                 break;
 898         case iro_Mul:
 899                 pred = get_irn_node(get_irn_n(irn, input));
 900                 if (is_tarval(pred->type.tv) && tarval_is_one(pred->type.tv))
 901                         return 0;
 902                 break;
 903         case iro_And:
 904                 pred = get_irn_node(get_irn_n(irn, input));
 905                 if (is_tarval(pred->type.tv) && tarval_is_all_one(pred->type.tv))
 906                         return 0;
 907                 break;
 908         case iro_Min:
 909         case iro_Max:
 910                 /* all inputs are followers */
 911                 return 1;
 912         default:
 913                 assert(!"opcode not implemented yet");
 914                 break;
 915         }
 916         return 1;
 917 }
 918
 919 /**
 920  * Do one step in the race.
 921  */
 922 static int step(step_env *env) {
 923         node_t *n;
 924
 925         if (env->initial != NULL) {
 926                 /* Move node from initial to unwalked */
 927                 n             = env->initial;
 928                 env->initial  = n->race_next;
 929
 930                 n->race_next  = env->unwalked;
 931                 env->unwalked = n;
 932
 933                 return 0;
 934         }
 935
 936         while (env->unwalked != NULL) {
 937                 /* let n be the first node in unwalked */
 938                 n = env->unwalked;
 939                 while (env->index < n->n_followers) {
 940                         const ir_def_use_edge *edge = &n->node->out[1 + env->index];
 941
 942                         /* let m be n.F.def_use[index] */
 943                         node_t *m = get_irn_node(edge->use);
 944
 945                         assert(m->is_follower);
 946                         /*
 947                          * Some inputs, like the get_Confirm_bound are NOT
 948                          * real followers, sort them out.
 949                          */
 950                         if (! is_real_follower(m->node, edge->pos)) {
 951                                 ++env->index;
 952                                 continue;
 953                         }
 954                         ++env->index;
 955
 956                         /* only followers from our partition */
 957                         if (m->part != n->part)
 958                                 continue;
 959
 960                         if ((m->flagged & env->side) == 0) {
 961                                 m->flagged |= env->side;
 962
 963                                 if (m->flagged != 3) {
 964                                         /* visited the first time */
 965                                         /* add m to unwalked not as first node (we might still need to
 966                                            check for more follower node */
 967                                         m->race_next = n->race_next;
 968                                         n->race_next = m;
 969                                         return 0;
 970                                 }
 971                                 /* else already visited by the other side and on the other list */
 972                         }
 973                 }
 974                 /* move n to walked */
 975                 env->unwalked = n->race_next;
 976                 n->race_next  = env->walked;
 977                 env->walked   = n;
 978                 env->index    = 0;
 979         }
 980         return 1;
 981 }  /* step */
 982
 983 /**
 984  * Clear the flags from a list and check for
 985  * nodes that where touched from both sides.
 986  *
 987  * @param list  the list
 988  */
 989 static int clear_flags(node_t *list) {
 990         int    res = 0;
 991         node_t *n;
 992
 993         for (n = list; n != NULL; n = n->race_next) {
 994                 if (n->flagged == 3) {
 995                         /* we reach a follower from both sides, this will split congruent
 996                          * inputs and make it a leader. */
 997                         follower_to_leader(n);
 998                         res = 1;
 999                 }
1000                 n->flagged = 0;
1001         }
1002         return res;
1003 }  /* clear_flags */
1004
1005 /**
1006  * Split a partition by a local list using the race.
1007  *
1008  * @param pX   pointer to the partition to split, might be changed!
1009  * @param gg   a (non-empty) node list
1010  * @param env  the environment
1011  *
1012  * @return  a new partition containing the nodes of gg
1013  */
1014 static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) {
1015         partition_t *X = *pX;
1016         partition_t *X_prime;
1017         list_head   tmp;
1018         step_env    env1, env2, *winner;
1019         node_t      *g, *h, *node, *t;
1020         int         max_input, transitions;
1021         unsigned    n;
1022         DEBUG_ONLY(static int run = 0;)
1023
1024         DB((dbg, LEVEL_2, "Run %d ", run++));
1025         if (list_empty(&X->Follower)) {
1026                 /* if the partition has NO follower, we can use the fast
1027                    splitting algorithm. */
1028                 return split_no_followers(X, gg, env);
1029         }
1030         /* else do the race */
1031
1032         dump_partition("Splitting ", X);
1033         dump_list("by list ", gg);
1034
1035         INIT_LIST_HEAD(&tmp);
1036
1037         /* Remove gg from X.Leader and put into g */
1038         g = NULL;
1039         for (node = gg; node != NULL; node = node->next) {
1040                 assert(node->part == X);
1041                 assert(node->is_follower == 0);
1042
1043                 list_del(&node->node_list);
1044                 list_add_tail(&node->node_list, &tmp);
1045                 node->race_next = g;
1046                 g               = node;
1047         }
1048         /* produce h */
1049         h = NULL;
1050         list_for_each_entry(node_t, node, &X->Leader, node_list) {
1051                 node->race_next = h;
1052                 h               = node;
1053         }
1054         /* restore X.Leader */
1055         list_splice(&tmp, &X->Leader);
1056
1057         env1.initial       = g;
1058         env1.unwalked      = NULL;
1059         env1.walked        = NULL;
1060         env1.index         = 0;
1061         env1.side          = 1;
1062
1063         env2.initial       = h;
1064         env2.unwalked      = NULL;
1065         env2.walked        = NULL;
1066         env2.index         = 0;
1067         env2.side          = 2;
1068
1069         for (;;) {
1070                 if (step(&env1)) {
1071                         winner = &env1;
1072                         break;
1073                 }
1074                 if (step(&env2)) {
1075                         winner = &env2;
1076                         break;
1077                 }
1078         }
1079         assert(winner->initial == NULL);
1080         assert(winner->unwalked == NULL);
1081
1082         /* clear flags from walked/unwalked */
1083         transitions  = clear_flags(env1.unwalked);
1084         transitions |= clear_flags(env1.walked);
1085         transitions |= clear_flags(env2.unwalked);
1086         transitions |= clear_flags(env2.walked);
1087
1088         dump_race_list("winner ", winner->walked);
1089
1090         /* Move walked_{winner} to a new partition, X'. */
1091         X_prime   = new_partition(env);
1092         max_input = 0;
1093         n         = 0;
1094         for (node = winner->walked; node != NULL; node = node->race_next) {
1095                 list_del(&node->node_list);
1096                 node->part = X_prime;
1097                 if (node->is_follower) {
1098                         list_add_tail(&node->node_list, &X_prime->Follower);
1099                 } else {
1100                         list_add_tail(&node->node_list, &X_prime->Leader);
1101                         ++n;
1102                 }
1103                 if (node->max_user_input > max_input)
1104                         max_input = node->max_user_input;
1105         }
1106         X_prime->n_leader        = n;
1107         X_prime->max_user_inputs = max_input;
1108         X->n_leader             -= X_prime->n_leader;
1109
1110         /* for now, copy the type info tag, it will be adjusted in split_by(). */
1111         X_prime->type_is_T_or_C = X->type_is_T_or_C;
1112
1113         /*
1114          * Even if a follower was not checked by both sides, it might have
1115          * loose its congruence, so we need to check this case for all follower.
1116          */
1117         list_for_each_entry_safe(node_t, node, t, &X_prime->Follower, node_list) {
1118                 if (identity(node) == node) {
1119                         follower_to_leader(node);
1120                         transitions = 1;
1121                 }
1122         }
1123
1124         check_partition(X);
1125         check_partition(X_prime);
1126
1127         /* X' is the smaller part */
1128         add_to_worklist(X_prime, env);
1129
1130         /*
1131          * If there where follower to leader transitions, ensure that the nodes
1132          * can be split out if necessary.
1133          */
1134         if (transitions) {
1135                 /* place partitions on the cprop list */
1136                 if (X_prime->on_cprop == 0) {
1137                         X_prime->cprop_next = env->cprop;
1138                         env->cprop          = X_prime;
1139                         X_prime->on_cprop   = 1;
1140                 }
1141         }
1142
1143         dump_partition("Now ", X);
1144         dump_partition("Created new ", X_prime);
1145
1146         /* we have to ensure that the partition containing g is returned */
1147         if (winner == &env2) {
1148                 *pX = X_prime;
1149                 return X;
1150         }
1151
1152         return X_prime;
1153 }  /* split */
1154 #endif /* NO_FOLLOWER */
1155
1156 /**
1157  * Returns non-zero if the i'th input of a Phi node is live.
1158  *
1159  * @param phi  a Phi-node
1160  * @param i    an input number
1161  *
1162  * @return non-zero if the i'th input of the given Phi node is live
1163  */
1164 static int is_live_input(ir_node *phi, int i) {
1165         if (i >= 0) {
1166                 ir_node        *block = get_nodes_block(phi);
1167                 ir_node        *pred  = get_Block_cfgpred(block, i);
1168                 lattice_elem_t type   = get_node_type(pred);
1169
1170                 return type.tv != tarval_unreachable;
1171         }
1172         /* else it's the control input, always live */
1173         return 1;
1174 }  /* is_live_input */
1175
1176 /**
1177  * Return non-zero if a type is a constant.
1178  */
1179 static int is_constant_type(lattice_elem_t type) {
1180         if (type.tv != tarval_bottom && type.tv != tarval_top)
1181                 return 1;
1182         return 0;
1183 }  /* is_constant_type */
1184
1185 /**
1186  * Check whether a type is neither Top or a constant.
1187  * Note: U is handled like Top here, R is a constant.
1188  *
1189  * @param type  the type to check
1190  */
1191 static int type_is_neither_top_nor_const(const lattice_elem_t type) {
1192         if (is_tarval(type.tv)) {
1193                 if (type.tv == tarval_top)
1194                         return 0;
1195                 if (tarval_is_constant(type.tv))
1196                         return 0;
1197         } else {
1198                 /* is a symconst */
1199                 return 0;
1200         }
1201         return 1;
1202 }
1203
1204 /**
1205  * Collect nodes to the touched list.
1206  *
1207  * @param list  the list which contains the nodes that must be evaluated
1208  * @param idx   the index of the def_use edge to evaluate
1209  * @param env   the environment
1210  */
1211 static void collect_touched(list_head *list, int idx, environment_t *env) {
1212         node_t  *x, *y;
1213         int     end_idx = env->end_idx;
1214
1215         list_for_each_entry(node_t, x, list, node_list) {
1216                 int num_edges;
1217
1218                 if (idx == -1) {
1219                         /* leader edges start AFTER follower edges */
1220                         x->next_edge = x->n_followers + 1;
1221                 }
1222                 num_edges = get_irn_n_outs(x->node);
1223
1224                 /* for all edges in x.L.def_use_{idx} */
1225                 while (x->next_edge <= num_edges) {
1226                         const ir_def_use_edge *edge = &x->node->out[x->next_edge];
1227                         ir_node               *succ;
1228
1229                         /* check if we have necessary edges */
1230                         if (edge->pos > idx)
1231                                 break;
1232
1233                         ++x->next_edge;
1234
1235                         succ = edge->use;
1236
1237                         /* ignore the "control input" for non-pinned nodes
1238                         if we are running in GCSE mode */
1239                         if (idx < end_idx && get_irn_pinned(succ) != op_pin_state_pinned)
1240                                 continue;
1241
1242                         y = get_irn_node(succ);
1243                         assert(get_irn_n(succ, idx) == x->node);
1244
1245                         /* ignore block edges touching followers */
1246                         if (idx == -1 && y->is_follower)
1247                                 continue;
1248
1249                         if (is_constant_type(y->type)) {
1250                                 ir_opcode code = get_irn_opcode(succ);
1251                                 if (code == iro_Sub || code == iro_Eor || code == iro_Cmp)
1252                                         add_to_cprop(y, env);
1253                         }
1254
1255                         /* Partitions of constants should not be split simply because their Nodes have unequal
1256                            functions or incongruent inputs. */
1257                         if (type_is_neither_top_nor_const(y->type) &&
1258                                 (! is_Phi(y->node) || is_live_input(y->node, idx))) {
1259                                         add_to_touched(y, env);
1260                         }
1261                 }
1262         }
1263 }  /* collect_touched */
1264
1265 /**
1266  * Split the partitions if caused by the first entry on the worklist.
1267  *
1268  * @param env  the environment
1269  */
1270 static void cause_splits(environment_t *env) {
1271         partition_t *X, *Z, *N;
1272         int         idx;
1273
1274         /* remove the first partition from the worklist */
1275         X = env->worklist;
1276         env->worklist  = X->wl_next;
1277         X->on_worklist = 0;
1278
1279         dump_partition("Cause_split: ", X);
1280
1281         /* combine temporary leader and follower list */
1282         for (idx = -1; idx <= X->max_user_inputs; ++idx) {
1283                 /* empty the touched set: already done, just clear the list */
1284                 env->touched = NULL;
1285
1286                 collect_touched(&X->Leader, idx, env);
1287                 collect_touched(&X->Follower, idx, env);
1288
1289                 for (Z = env->touched; Z != NULL; Z = N) {
1290                         node_t   *e;
1291                         node_t   *touched  = Z->touched;
1292                         unsigned n_touched = Z->n_touched;
1293
1294                         assert(Z->touched != NULL);
1295
1296                         /* beware, split might change Z */
1297                         N = Z->touched_next;
1298
1299                         /* remove it from the touched set */
1300                         Z->on_touched = 0;
1301
1302                         /* Empty local Z.touched. */
1303                         for (e = touched; e != NULL; e = e->next) {
1304                                 assert(e->is_follower == 0);
1305                                 e->on_touched = 0;
1306                         }
1307                         Z->touched   = NULL;
1308                         Z->n_touched = 0;
1309
1310                         if (0 < n_touched && n_touched < Z->n_leader) {
1311                                 DB((dbg, LEVEL_2, "Split part%d by touched\n", Z->nr));
1312                                 split(&Z, touched, env);
1313                         } else
1314                                 assert(n_touched <= Z->n_leader);
1315                 }
1316         }
1317 }  /* cause_splits */
1318
1319 /**
1320  * Implements split_by_what(): Split a partition by characteristics given
1321  * by the what function.
1322  *
1323  * @param X     the partition to split
1324  * @param What  a function returning an Id for every node of the partition X
1325  * @param P     a list to store the result partitions
1326  * @param env   the environment
1327  *
1328  * @return *P
1329  */
1330 static partition_t *split_by_what(partition_t *X, what_func What,
1331                                   partition_t **P, environment_t *env) {
1332         node_t          *x, *S;
1333         listmap_t       map;
1334         listmap_entry_t *iter;
1335         partition_t     *R;
1336
1337         /* Let map be an empty mapping from the range of What to (local) list of Nodes. */
1338         listmap_init(&map);
1339         list_for_each_entry(node_t, x, &X->Leader, node_list) {
1340                 void            *id = What(x, env);
1341                 listmap_entry_t *entry;
1342
1343                 if (id == NULL) {
1344                         /* input not allowed, ignore */
1345                         continue;
1346                 }
1347                 /* Add x to map[What(x)]. */
1348                 entry = listmap_find(&map, id);
1349                 x->next     = entry->list;
1350                 entry->list = x;
1351         }
1352         /* Let P be a set of Partitions. */
1353
1354         /* for all sets S except one in the range of map do */
1355         for (iter = map.values; iter != NULL; iter = iter->next) {
1356                 if (iter->next == NULL) {
1357                         /* this is the last entry, ignore */
1358                         break;
1359                 }
1360                 S = iter->list;
1361
1362                 /* Add SPLIT( X, S ) to P. */
1363                 DB((dbg, LEVEL_2, "Split part%d by what\n", X->nr));
1364                 R = split(&X, S, env);
1365                 R->split_next = *P;
1366                 *P            = R;
1367         }
1368         /* Add X to P. */
1369         X->split_next = *P;
1370         *P            = X;
1371
1372         listmap_term(&map);
1373         return *P;
1374 }  /* split_by_what */
1375
1376 /** lambda n.(n.type) */
1377 static void *lambda_type(const node_t *node, environment_t *env) {
1378         (void)env;
1379         return node->type.tv;
1380 }  /* lambda_type */
1381
1382 /** lambda n.(n.opcode) */
1383 static void *lambda_opcode(const node_t *node, environment_t *env) {
1384         opcode_key_t key, *entry;
1385         ir_node      *irn = node->node;
1386
1387         key.code   = get_irn_opcode(irn);
1388         key.mode   = get_irn_mode(irn);
1389         key.arity  = get_irn_arity(irn);
1390         key.u.proj = 0;
1391         key.u.ent  = NULL;
1392
1393         switch (get_irn_opcode(irn)) {
1394         case iro_Proj:
1395                 key.u.proj = get_Proj_proj(irn);
1396                 break;
1397         case iro_Sel:
1398                 key.u.ent = get_Sel_entity(irn);
1399                 break;
1400         default:
1401                 break;
1402         }
1403
1404         entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
1405         return entry;
1406 }  /* lambda_opcode */
1407
1408 /** lambda n.(n[i].partition) */
1409 static void *lambda_partition(const node_t *node, environment_t *env) {
1410         ir_node *skipped = skip_Proj(node->node);
1411         ir_node *pred;
1412         node_t  *p;
1413         int     i = env->lambda_input;
1414
1415         if (i >= get_irn_arity(node->node)) {
1416                 /* we are outside the allowed range */
1417                 return NULL;
1418         }
1419
1420         /* ignore the "control input" for non-pinned nodes
1421            if we are running in GCSE mode */
1422         if (i < env->end_idx && get_irn_pinned(skipped) != op_pin_state_pinned)
1423                 return NULL;
1424
1425         pred = i == -1 ? get_irn_n(skipped, i) : get_irn_n(node->node, i);
1426         p    = get_irn_node(pred);
1427
1428         return p->part;
1429 }  /* lambda_partition */
1430
1431 /**
1432  * Returns true if a type is a constant.
1433  */
1434 static int is_con(const lattice_elem_t type) {
1435         /* be conservative */
1436         if (is_tarval(type.tv))
1437                 return tarval_is_constant(type.tv);
1438         return is_entity(type.sym.entity_p);
1439 }  /* is_con */
1440
1441 /**
1442  * Implements split_by().
1443  *
1444  * @param X    the partition to split
1445  * @param env  the environment
1446  */
1447 static void split_by(partition_t *X, environment_t *env) {
1448         partition_t *I, *P = NULL;
1449         int         input;
1450
1451         dump_partition("split_by", X);
1452
1453         if (X->n_leader == 1) {
1454                 /* we have only one leader, no need to split, just check it's type */
1455                 node_t *x = get_first_node(X);
1456                 X->type_is_T_or_C = x->type.tv == tarval_top || is_con(x->type);
1457                 return;
1458         }
1459
1460         DB((dbg, LEVEL_2, "WHAT = lambda n.(n.type) on part%d\n", X->nr));
1461         P = split_by_what(X, lambda_type, &P, env);
1462
1463         /* adjust the type tags, we have split partitions by type */
1464         for (I = P; I != NULL; I = I->split_next) {
1465                 node_t *x = get_first_node(I);
1466                 I->type_is_T_or_C = x->type.tv == tarval_top || is_con(x->type);
1467         }
1468
1469         do {
1470                 partition_t *Y = P;
1471
1472                 P = P->split_next;
1473                 if (Y->n_leader > 1) {
1474                         /* we do not want split the TOP or constant partitions */
1475                         if (! Y->type_is_T_or_C) {
1476                                 partition_t *Q = NULL;
1477
1478                                 DB((dbg, LEVEL_2, "WHAT = lambda n.(n.opcode) on part%d\n", Y->nr));
1479                                 Q = split_by_what(Y, lambda_opcode, &Q, env);
1480
1481                                 do {
1482                                         partition_t *Z = Q;
1483
1484                                         Q = Q->split_next;
1485                                         if (Z->n_leader > 1) {
1486                                                 const node_t *first = get_first_node(Z);
1487                                                 int          arity  = get_irn_arity(first->node);
1488                                                 partition_t  *R, *S;
1489
1490                                                 /*
1491                                                  * BEWARE: during splitting by input 2 for instance we might
1492                                                  * create new partitions which are different by input 1, so collect
1493                                                  * them and split further.
1494                                                  */
1495                                                 Z->split_next = NULL;
1496                                                 R             = Z;
1497                                                 S             = NULL;
1498                                                 for (input = arity - 1; input >= -1; --input) {
1499                                                         do {
1500                                                                 partition_t *Z_prime = R;
1501
1502                                                                 R = R->split_next;
1503                                                                 if (Z_prime->n_leader > 1) {
1504                                                                         env->lambda_input = input;
1505                                                                         DB((dbg, LEVEL_2, "WHAT = lambda n.(n[%d].partition) on part%d\n", input, Z_prime->nr));
1506                                                                         S = split_by_what(Z_prime, lambda_partition, &S, env);
1507                                                                 } else {
1508                                                                         Z_prime->split_next = S;
1509                                                                         S                   = Z_prime;
1510                                                                 }
1511                                                         } while (R != NULL);
1512                                                         R = S;
1513                                                         S = NULL;
1514                                                 }
1515                                         }
1516                                 } while (Q != NULL);
1517                         }
1518                 }
1519         } while (P != NULL);
1520 }  /* split_by */
1521
1522 /**
1523  * (Re-)compute the type for a given node.
1524  *
1525  * @param node  the node
1526  */
1527 static void default_compute(node_t *node) {
1528         int     i;
1529         ir_node *irn = node->node;
1530         node_t  *block = get_irn_node(get_nodes_block(irn));
1531
1532         if (block->type.tv == tarval_unreachable) {
1533                 node->type.tv = tarval_top;
1534                 return;
1535         }
1536
1537         /* if any of the data inputs have type top, the result is type top */
1538         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
1539                 ir_node *pred = get_irn_n(irn, i);
1540                 node_t  *p    = get_irn_node(pred);
1541
1542                 if (p->type.tv == tarval_top) {
1543                         node->type.tv = tarval_top;
1544                         return;
1545                 }
1546         }
1547
1548         if (get_irn_mode(node->node) == mode_X)
1549                 node->type.tv = tarval_reachable;
1550         else
1551                 node->type.tv = computed_value(irn);
1552 }  /* default_compute */
1553
1554 /**
1555  * (Re-)compute the type for a Block node.
1556  *
1557  * @param node  the node
1558  */
1559 static void compute_Block(node_t *node) {
1560         int     i;
1561         ir_node *block = node->node;
1562
1563         if (block == get_irg_start_block(current_ir_graph)) {
1564                 /* start block is always reachable */
1565                 node->type.tv = tarval_reachable;
1566                 return;
1567         }
1568
1569         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
1570                 node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
1571
1572                 if (pred->type.tv == tarval_reachable) {
1573                         /* A block is reachable, if at least of predecessor is reachable. */
1574                         node->type.tv = tarval_reachable;
1575                         return;
1576                 }
1577         }
1578         node->type.tv = tarval_top;
1579 }  /* compute_Block */
1580
1581 /**
1582  * (Re-)compute the type for a Bad node.
1583  *
1584  * @param node  the node
1585  */
1586 static void compute_Bad(node_t *node) {
1587         /* Bad nodes ALWAYS compute Top */
1588         node->type.tv = tarval_top;
1589 }  /* compute_Bad */
1590
1591 /**
1592  * (Re-)compute the type for an Unknown node.
1593  *
1594  * @param node  the node
1595  */
1596 static void compute_Unknown(node_t *node) {
1597         /* While Unknown nodes should compute Top this is dangerous:
1598          * a Top input to a Cond would lead to BOTH control flows unreachable.
1599          * While this is correct in the given semantics, it would destroy the Firm
1600          * graph.
1601          *
1602          * It would be safe to compute Top IF it can be assured, that only Cmp
1603          * nodes are inputs to Conds. We check that first.
1604          * This is the way Frontends typically build Firm, but some optimizations
1605          * (cond_eval for instance) might replace them by Phib's...
1606          */
1607         node->type.tv = tarval_UNKNOWN;
1608 }  /* compute_Unknown */
1609
1610 /**
1611  * (Re-)compute the type for a Jmp node.
1612  *
1613  * @param node  the node
1614  */
1615 static void compute_Jmp(node_t *node) {
1616         node_t *block = get_irn_node(get_nodes_block(node->node));
1617
1618         node->type = block->type;
1619 }  /* compute_Jmp */
1620
1621 /**
1622  * (Re-)compute the type for the End node.
1623  *
1624  * @param node  the node
1625  */
1626 static void compute_End(node_t *node) {
1627         /* the End node is NOT dead of course */
1628         node->type.tv = tarval_reachable;
1629 }
1630
1631 /**
1632  * (Re-)compute the type for a SymConst node.
1633  *
1634  * @param node  the node
1635  */
1636 static void compute_SymConst(node_t *node) {
1637         ir_node *irn = node->node;
1638         node_t  *block = get_irn_node(get_nodes_block(irn));
1639
1640         if (block->type.tv == tarval_unreachable) {
1641                 node->type.tv = tarval_top;
1642                 return;
1643         }
1644         switch (get_SymConst_kind(irn)) {
1645         case symconst_addr_ent:
1646         /* case symconst_addr_name: cannot handle this yet */
1647                 node->type.sym = get_SymConst_symbol(irn);
1648                 break;
1649         default:
1650                 node->type.tv = computed_value(irn);
1651         }
1652 }  /* compute_SymConst */
1653
1654 /**
1655  * (Re-)compute the type for a Phi node.
1656  *
1657  * @param node  the node
1658  */
1659 static void compute_Phi(node_t *node) {
1660         int            i;
1661         ir_node        *phi = node->node;
1662         lattice_elem_t type;
1663
1664         /* if a Phi is in a unreachable block, its type is TOP */
1665         node_t *block = get_irn_node(get_nodes_block(phi));
1666
1667         if (block->type.tv == tarval_unreachable) {
1668                 node->type.tv = tarval_top;
1669                 return;
1670         }
1671
1672         /* Phi implements the Meet operation */
1673         type.tv = tarval_top;
1674         for (i = get_Phi_n_preds(phi) - 1; i >= 0; --i) {
1675                 node_t *pred   = get_irn_node(get_Phi_pred(phi, i));
1676                 node_t *pred_X = get_irn_node(get_Block_cfgpred(block->node, i));
1677
1678                 if (pred_X->type.tv == tarval_unreachable || pred->type.tv == tarval_top) {
1679                         /* ignore TOP inputs: We must check here for unreachable blocks,
1680                            because Firm constants live in the Start Block are NEVER Top.
1681                            Else, a Phi (1,2) will produce Bottom, even if the 2 for instance
1682                            comes from a unreachable input. */
1683                         continue;
1684                 }
1685                 if (pred->type.tv == tarval_bottom) {
1686                         node->type.tv = tarval_bottom;
1687                         return;
1688                 } else if (type.tv == tarval_top) {
1689                         /* first constant found */
1690                         type = pred->type;
1691                 } else if (type.tv != pred->type.tv) {
1692                         /* different constants or tarval_bottom */
1693                         node->type.tv = tarval_bottom;
1694                         return;
1695                 }
1696                 /* else nothing, constants are the same */
1697         }
1698         node->type = type;
1699 }  /* compute_Phi */
1700
1701 /**
1702  * (Re-)compute the type for an Add. Special case: one nodes is a Zero Const.
1703  *
1704  * @param node  the node
1705  */
1706 static void compute_Add(node_t *node) {
1707         ir_node        *sub = node->node;
1708         node_t         *l   = get_irn_node(get_Add_left(sub));
1709         node_t         *r   = get_irn_node(get_Add_right(sub));
1710         lattice_elem_t a    = l->type;
1711         lattice_elem_t b    = r->type;
1712         ir_mode        *mode;
1713
1714         if (a.tv == tarval_top || b.tv == tarval_top) {
1715                 node->type.tv = tarval_top;
1716         } else if (a.tv == tarval_bottom || b.tv == tarval_bottom) {
1717                 node->type.tv = tarval_bottom;
1718         } else {
1719                 /* x + 0 = 0 + x = x, but beware of floating point +0 + -0, so we
1720                    must call tarval_add() first to handle this case! */
1721                 if (is_tarval(a.tv)) {
1722                         if (is_tarval(b.tv)) {
1723                                 node->type.tv = tarval_add(a.tv, b.tv);
1724                                 return;
1725                         }
1726                         mode = get_tarval_mode(a.tv);
1727                         if (a.tv == get_mode_null(mode)) {
1728                                 node->type = b;
1729                                 return;
1730                         }
1731                 } else if (is_tarval(b.tv)) {
1732                         mode = get_tarval_mode(b.tv);
1733                         if (b.tv == get_mode_null(mode)) {
1734                                 node->type = a;
1735                                 return;
1736                         }
1737                 }
1738                 node->type.tv = tarval_bottom;
1739         }
1740 }  /* compute_Add */
1741
1742 /**
1743  * (Re-)compute the type for a Sub. Special case: both nodes are congruent.
1744  *
1745  * @param node  the node
1746  */
1747 static void compute_Sub(node_t *node) {
1748         ir_node        *sub = node->node;
1749         node_t         *l   = get_irn_node(get_Sub_left(sub));
1750         node_t         *r   = get_irn_node(get_Sub_right(sub));
1751         lattice_elem_t a    = l->type;
1752         lattice_elem_t b    = r->type;
1753         tarval         *tv;
1754
1755         if (a.tv == tarval_top || b.tv == tarval_top) {
1756                 node->type.tv = tarval_top;
1757         } else if (is_con(a) && is_con(b)) {
1758                 if (is_tarval(a.tv) && is_tarval(b.tv)) {
1759                         node->type.tv = tarval_sub(a.tv, b.tv, get_irn_mode(sub));
1760                 } else if (is_tarval(a.tv) && tarval_is_null(a.tv)) {
1761                         node->type = b;
1762                 } else if (is_tarval(b.tv) && tarval_is_null(b.tv)) {
1763                         node->type = a;
1764                 } else {
1765                         node->type.tv = tarval_bottom;
1766                 }
1767                 node->by_all_const = 1;
1768         } else if (r->part == l->part &&
1769                    (!mode_is_float(get_irn_mode(l->node)))) {
1770                 /*
1771                  * BEWARE: a - a is NOT always 0 for floating Point values, as
1772                  * NaN op NaN = NaN, so we must check this here.
1773                  */
1774                 ir_mode *mode = get_irn_mode(sub);
1775                 tv = get_mode_null(mode);
1776
1777                 /* if the node was ONCE evaluated by all constants, but now
1778                    this breakes AND we cat by partition a different result, switch to bottom.
1779                    This happens because initially all nodes are in the same partition ... */
1780                 if (node->by_all_const && node->type.tv != tv)
1781                         tv = tarval_bottom;
1782                 node->type.tv = tv;
1783         } else {
1784                 node->type.tv = tarval_bottom;
1785         }
1786 }  /* compute_Sub */
1787
1788 /**
1789  * (Re-)compute the type for an Eor. Special case: both nodes are congruent.
1790  *
1791  * @param node  the node
1792  */
1793 static void compute_Eor(node_t *node) {
1794         ir_node        *eor = node->node;
1795         node_t         *l   = get_irn_node(get_Eor_left(eor));
1796         node_t         *r   = get_irn_node(get_Eor_right(eor));
1797         lattice_elem_t a    = l->type;
1798         lattice_elem_t b    = r->type;
1799         tarval         *tv;
1800
1801         if (a.tv == tarval_top || b.tv == tarval_top) {
1802                 node->type.tv = tarval_top;
1803         } else if (is_con(a) && is_con(b)) {
1804                 if (is_tarval(a.tv) && is_tarval(b.tv)) {
1805                         node->type.tv = tarval_eor(a.tv, b.tv);
1806                 } else if (is_tarval(a.tv) && tarval_is_null(a.tv)) {
1807                         node->type = b;
1808                 } else if (is_tarval(b.tv) && tarval_is_null(b.tv)) {
1809                         node->type = a;
1810                 } else {
1811                         node->type.tv = tarval_bottom;
1812                 }
1813                 node->by_all_const = 1;
1814         } else if (r->part == l->part) {
1815                 ir_mode *mode = get_irn_mode(eor);
1816                 tv = get_mode_null(mode);
1817
1818                 /* if the node was ONCE evaluated by all constants, but now
1819                    this breakes AND we cat by partition a different result, switch to bottom.
1820                    This happens because initially all nodes are in the same partition ... */
1821                 if (node->by_all_const && node->type.tv != tv)
1822                         tv = tarval_bottom;
1823                 node->type.tv = tv;
1824         } else {
1825                 node->type.tv = tarval_bottom;
1826         }
1827 }  /* compute_Eor */
1828
1829 /**
1830  * (Re-)compute the type for Cmp.
1831  *
1832  * @param node  the node
1833  */
1834 static void compute_Cmp(node_t *node) {
1835         ir_node        *cmp  = node->node;
1836         node_t         *l    = get_irn_node(get_Cmp_left(cmp));
1837         node_t         *r    = get_irn_node(get_Cmp_right(cmp));
1838         lattice_elem_t a     = l->type;
1839         lattice_elem_t b     = r->type;
1840
1841         if (a.tv == tarval_top || b.tv == tarval_top) {
1842 #ifdef WITH_UNKNOWN
1843                 /*
1844                  * Top is congruent to any other value, we can
1845                  * calculate the compare result.
1846                  */
1847                 node->type.tv = tarval_b_true;
1848 #else
1849                 node->type.tv = tarval_top;
1850 #endif
1851         } else if (is_con(a) && is_con(b)) {
1852                 /* both nodes are constants, we can probably do something */
1853                 node->type.tv = tarval_b_true;
1854         } else if (r->part == l->part) {
1855                 /* both nodes congruent, we can probably do something */
1856                 node->type.tv = tarval_b_true;
1857         } else {
1858                 node->type.tv = tarval_bottom;
1859         }
1860 }  /* compute_Proj_Cmp */
1861
1862 /**
1863  * (Re-)compute the type for a Proj(Cmp).
1864  *
1865  * @param node  the node
1866  * @param cond  the predecessor Cmp node
1867  */
1868 static void compute_Proj_Cmp(node_t *node, ir_node *cmp) {
1869         ir_node        *proj = node->node;
1870         node_t         *l    = get_irn_node(get_Cmp_left(cmp));
1871         node_t         *r    = get_irn_node(get_Cmp_right(cmp));
1872         lattice_elem_t a     = l->type;
1873         lattice_elem_t b     = r->type;
1874         pn_Cmp         pnc   = get_Proj_proj(proj);
1875         tarval         *tv;
1876
1877         if (a.tv == tarval_top || b.tv == tarval_top) {
1878 #ifdef WITH_UNKNOWN
1879                 /* see above */
1880                 tv = new_tarval_from_long((pnc & pn_Cmp_Eq) ^ pn_Cmp_Eq, mode_b);
1881                 goto not_equal;
1882 #else
1883                 node->type.tv = tarval_top;
1884 #endif
1885         } else if (is_con(a) && is_con(b)) {
1886                 default_compute(node);
1887                 node->by_all_const = 1;
1888         } else if (r->part == l->part &&
1889                    (!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt || pnc == pn_Cmp_Gt)) {
1890                 /*
1891                  * BEWARE: a == a is NOT always True for floating Point values, as
1892                  * NaN != NaN is defined, so we must check this here.
1893                  */
1894                 tv = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b);
1895 #ifdef WITH_UNKNOWN
1896 not_equal:
1897 #endif
1898
1899                 /* if the node was ONCE evaluated by all constants, but now
1900                    this breakes AND we cat by partition a different result, switch to bottom.
1901                    This happens because initially all nodes are in the same partition ... */
1902                 if (node->by_all_const && node->type.tv != tv)
1903                         tv = tarval_bottom;
1904                 node->type.tv = tv;
1905         } else {
1906                 node->type.tv = tarval_bottom;
1907         }
1908 }  /* compute_Proj_Cmp */
1909
1910 /**
1911  * (Re-)compute the type for a Proj(Cond).
1912  *
1913  * @param node  the node
1914  * @param cond  the predecessor Cond node
1915  */
1916 static void compute_Proj_Cond(node_t *node, ir_node *cond) {
1917         ir_node *proj     = node->node;
1918         long    pnc       = get_Proj_proj(proj);
1919         ir_node *sel      = get_Cond_selector(cond);
1920         node_t  *selector = get_irn_node(sel);
1921
1922         if (get_irn_mode(sel) == mode_b) {
1923                 /* an IF */
1924                 if (pnc == pn_Cond_true) {
1925                         if (selector->type.tv == tarval_b_false) {
1926                                 node->type.tv = tarval_unreachable;
1927                         } else if (selector->type.tv == tarval_b_true) {
1928                                 node->type.tv = tarval_reachable;
1929                         } else if (selector->type.tv == tarval_bottom) {
1930                                 node->type.tv = tarval_reachable;
1931                         } else {
1932                                 assert(selector->type.tv == tarval_top);
1933                                 node->type.tv = tarval_unreachable;
1934                         }
1935                 } else {
1936                         assert(pnc == pn_Cond_false);
1937
1938                         if (selector->type.tv == tarval_b_false) {
1939                                 node->type.tv = tarval_reachable;
1940                         } else if (selector->type.tv == tarval_b_true) {
1941                                 node->type.tv = tarval_unreachable;
1942                         } else if (selector->type.tv == tarval_bottom) {
1943                                 node->type.tv = tarval_reachable;
1944                         } else {
1945                                 assert(selector->type.tv == tarval_top);
1946                                 node->type.tv = tarval_unreachable;
1947                         }
1948                 }
1949         } else {
1950                 /* an SWITCH */
1951                 if (selector->type.tv == tarval_bottom) {
1952                         node->type.tv = tarval_reachable;
1953                 } else if (selector->type.tv == tarval_top) {
1954                         node->type.tv = tarval_unreachable;
1955                 } else {
1956                         long value = get_tarval_long(selector->type.tv);
1957                         if (pnc == get_Cond_defaultProj(cond)) {
1958                                 /* default switch, have to check ALL other cases */
1959                                 int i;
1960
1961                                 for (i = get_irn_n_outs(cond) - 1; i >= 0; --i) {
1962                                         ir_node *succ = get_irn_out(cond, i);
1963
1964                                         if (succ == proj)
1965                                                 continue;
1966                                         if (value == get_Proj_proj(succ)) {
1967                                                 /* we found a match, will NOT take the default case */
1968                                                 node->type.tv = tarval_unreachable;
1969                                                 return;
1970                                         }
1971                                 }
1972                                 /* all cases checked, no match, will take default case */
1973                                 node->type.tv = tarval_reachable;
1974                         } else {
1975                                 /* normal case */
1976                                 node->type.tv = value == pnc ? tarval_reachable : tarval_unreachable;
1977                         }
1978                 }
1979         }
1980 }  /* compute_Proj_Cond */
1981
1982 /**
1983  * (Re-)compute the type for a Proj-Node.
1984  *
1985  * @param node  the node
1986  */
1987 static void compute_Proj(node_t *node) {
1988         ir_node *proj = node->node;
1989         ir_mode *mode = get_irn_mode(proj);
1990         node_t  *block = get_irn_node(get_nodes_block(skip_Proj(proj)));
1991         ir_node *pred  = get_Proj_pred(proj);
1992
1993         if (block->type.tv == tarval_unreachable) {
1994                 /* a Proj in a unreachable Block stay Top */
1995                 node->type.tv = tarval_top;
1996                 return;
1997         }
1998         if (get_irn_node(pred)->type.tv == tarval_top) {
1999                 /* if the predecessor is Top, its Proj follow */
2000                 node->type.tv = tarval_top;
2001                 return;
2002         }
2003
2004         if (mode == mode_M) {
2005                 /* mode M is always bottom */
2006                 node->type.tv = tarval_bottom;
2007                 return;
2008         }
2009         if (mode != mode_X) {
2010                 if (is_Cmp(pred))
2011                         compute_Proj_Cmp(node, pred);
2012                 else
2013                         default_compute(node);
2014                 return;
2015         }
2016         /* handle mode_X nodes */
2017
2018         switch (get_irn_opcode(pred)) {
2019         case iro_Start:
2020                 /* the Proj_X from the Start is always reachable.
2021                    However this is already handled at the top. */
2022                 node->type.tv = tarval_reachable;
2023                 break;
2024         case iro_Cond:
2025                 compute_Proj_Cond(node, pred);
2026                 break;
2027         default:
2028                 default_compute(node);
2029         }
2030 }  /* compute_Proj */
2031
2032 /**
2033  * (Re-)compute the type for a Confirm.
2034  *
2035  * @param node  the node
2036  */
2037 static void compute_Confirm(node_t *node) {
2038         ir_node *confirm = node->node;
2039         node_t  *pred = get_irn_node(get_Confirm_value(confirm));
2040
2041         if (get_Confirm_cmp(confirm) == pn_Cmp_Eq) {
2042                 node_t *bound = get_irn_node(get_Confirm_bound(confirm));
2043
2044                 if (is_con(bound->type)) {
2045                         /* is equal to a constant */
2046                         node->type = bound->type;
2047                         return;
2048                 }
2049         }
2050         /* a Confirm is a copy OR a Const */
2051         node->type = pred->type;
2052 }  /* compute_Confirm */
2053
2054 /**
2055  * (Re-)compute the type for a Max.
2056  *
2057  * @param node  the node
2058  */
2059 static void compute_Max(node_t *node) {
2060         ir_node        *op   = node->node;
2061         node_t         *l    = get_irn_node(get_binop_left(op));
2062         node_t         *r    = get_irn_node(get_binop_right(op));
2063         lattice_elem_t a     = l->type;
2064         lattice_elem_t b     = r->type;
2065
2066         if (a.tv == tarval_top || b.tv == tarval_top) {
2067                 node->type.tv = tarval_top;
2068         } else if (is_con(a) && is_con(b)) {
2069                 /* both nodes are constants, we can probably do something */
2070                 if (a.tv == b.tv) {
2071                         /* this case handles symconsts as well */
2072                         node->type = a;
2073                 } else {
2074                         ir_mode *mode   = get_irn_mode(op);
2075                         tarval  *tv_min = get_mode_min(mode);
2076
2077                         if (a.tv == tv_min)
2078                                 node->type = b;
2079                         else if (b.tv == tv_min)
2080                                 node->type = a;
2081                         else if (is_tarval(a.tv) && is_tarval(b.tv)) {
2082                                 if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
2083                                         node->type.tv = a.tv;
2084                                 else
2085                                         node->type.tv = b.tv;
2086                         } else {
2087                                 node->type.tv = tarval_bad;
2088                         }
2089                 }
2090         } else if (r->part == l->part) {
2091                 /* both nodes congruent, we can probably do something */
2092                 node->type = a;
2093         } else {
2094                 node->type.tv = tarval_bottom;
2095         }
2096 }  /* compute_Max */
2097
2098 /**
2099  * (Re-)compute the type for a Min.
2100  *
2101  * @param node  the node
2102  */
2103 static void compute_Min(node_t *node) {
2104         ir_node        *op   = node->node;
2105         node_t         *l    = get_irn_node(get_binop_left(op));
2106         node_t         *r    = get_irn_node(get_binop_right(op));
2107         lattice_elem_t a     = l->type;
2108         lattice_elem_t b     = r->type;
2109
2110         if (a.tv == tarval_top || b.tv == tarval_top) {
2111                 node->type.tv = tarval_top;
2112         } else if (is_con(a) && is_con(b)) {
2113                 /* both nodes are constants, we can probably do something */
2114                 if (a.tv == b.tv) {
2115                         /* this case handles symconsts as well */
2116                         node->type = a;
2117                 } else {
2118                         ir_mode *mode   = get_irn_mode(op);
2119                         tarval  *tv_max = get_mode_max(mode);
2120
2121                         if (a.tv == tv_max)
2122                                 node->type = b;
2123                         else if (b.tv == tv_max)
2124                                 node->type = a;
2125                         else if (is_tarval(a.tv) && is_tarval(b.tv)) {
2126                                 if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
2127                                         node->type.tv = a.tv;
2128                                 else
2129                                         node->type.tv = b.tv;
2130                         } else {
2131                                 node->type.tv = tarval_bad;
2132                         }
2133                 }
2134         } else if (r->part == l->part) {
2135                 /* both nodes congruent, we can probably do something */
2136                 node->type = a;
2137         } else {
2138                 node->type.tv = tarval_bottom;
2139         }
2140 }  /* compute_Min */
2141
2142 /**
2143  * (Re-)compute the type for a given node.
2144  *
2145  * @param node  the node
2146  */
2147 static void compute(node_t *node) {
2148         compute_func func;
2149
2150         if (is_no_Block(node->node)) {
2151                 node_t *block = get_irn_node(get_nodes_block(node->node));
2152
2153                 if (block->type.tv == tarval_unreachable) {
2154                         node->type.tv = tarval_top;
2155                         return;
2156                 }
2157         }
2158
2159         func = (compute_func)node->node->op->ops.generic;
2160         if (func != NULL)
2161                 func(node);
2162 }  /* compute */
2163
2164 /*
2165  * Identity functions: Note that one might thing that identity() is just a
2166  * synonym for equivalent_node(). While this is true, we cannot use it for the algorithm
2167  * here, because it expects that the identity node is one of the inputs, which is NOT
2168  * always true for equivalent_node() which can handle (and does sometimes) DAGs.
2169  * So, we have our own implementation, which copies some parts of equivalent_node()
2170  */
2171
2172 /**
2173  * Calculates the Identity for Phi nodes
2174  */
2175 static node_t *identity_Phi(node_t *node) {
2176         ir_node *phi    = node->node;
2177         ir_node *block  = get_nodes_block(phi);
2178         node_t  *n_part = NULL;
2179         int     i;
2180
2181         for (i = get_Phi_n_preds(phi) - 1; i >= 0; --i) {
2182                 node_t *pred_X = get_irn_node(get_Block_cfgpred(block, i));
2183
2184                 if (pred_X->type.tv == tarval_reachable) {
2185                         node_t *pred = get_irn_node(get_Phi_pred(phi, i));
2186
2187                         if (n_part == NULL)
2188                                 n_part = pred;
2189                         else if (n_part->part != pred->part) {
2190                                 /* incongruent inputs, not a follower */
2191                                 return node;
2192                         }
2193                 }
2194         }
2195         /* if n_part is NULL here, all inputs path are dead, the Phi computes
2196          * tarval_top, is in the TOP partition and should NOT being split! */
2197         assert(n_part != NULL);
2198         return n_part;
2199 }  /* identity_Phi */
2200
2201 /**
2202  * Calculates the Identity for commutative 0 neutral nodes.
2203  */
2204 static node_t *identity_comm_zero_binop(node_t *node) {
2205         ir_node *op   = node->node;
2206         node_t  *a    = get_irn_node(get_binop_left(op));
2207         node_t  *b    = get_irn_node(get_binop_right(op));
2208         ir_mode *mode = get_irn_mode(op);
2209         tarval  *zero;
2210
2211         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
2212         if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
2213                 return node;
2214
2215         /* node: no input should be tarval_top, else the binop would be also
2216          * Top and not being split. */
2217         zero = get_mode_null(mode);
2218         if (a->type.tv == zero)
2219                 return b;
2220         if (b->type.tv == zero)
2221                 return a;
2222         return node;
2223 }  /* identity_comm_zero_binop */
2224
2225 /**
2226  * Calculates the Identity for Shift nodes.
2227  */
2228 static node_t *identity_shift(node_t *node) {
2229         ir_node *op   = node->node;
2230         node_t  *b    = get_irn_node(get_binop_right(op));
2231         ir_mode *mode = get_irn_mode(b->node);
2232         tarval  *zero;
2233
2234         /* node: no input should be tarval_top, else the binop would be also
2235          * Top and not being split. */
2236         zero = get_mode_null(mode);
2237         if (b->type.tv == zero)
2238                 return get_irn_node(get_binop_left(op));
2239         return node;
2240 }  /* identity_shift */
2241
2242 /**
2243  * Calculates the Identity for Mul nodes.
2244  */
2245 static node_t *identity_Mul(node_t *node) {
2246         ir_node *op   = node->node;
2247         node_t  *a    = get_irn_node(get_Mul_left(op));
2248         node_t  *b    = get_irn_node(get_Mul_right(op));
2249         ir_mode *mode = get_irn_mode(op);
2250         tarval  *one;
2251
2252         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
2253         if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
2254                 return node;
2255
2256         /* node: no input should be tarval_top, else the binop would be also
2257          * Top and not being split. */
2258         one = get_mode_one(mode);
2259         if (a->type.tv == one)
2260                 return b;
2261         if (b->type.tv == one)
2262                 return a;
2263         return node;
2264 }  /* identity_Mul */
2265
2266 /**
2267  * Calculates the Identity for Sub nodes.
2268  */
2269 static node_t *identity_Sub(node_t *node) {
2270         ir_node *sub  = node->node;
2271         node_t  *b    = get_irn_node(get_Sub_right(sub));
2272         ir_mode *mode = get_irn_mode(sub);
2273
2274         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
2275         if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
2276                 return node;
2277
2278         /* node: no input should be tarval_top, else the binop would be also
2279          * Top and not being split. */
2280         if (b->type.tv == get_mode_null(mode))
2281                 return get_irn_node(get_Sub_left(sub));
2282         return node;
2283 }  /* identity_Mul */
2284
2285 /**
2286  * Calculates the Identity for And nodes.
2287  */
2288 static node_t *identity_And(node_t *node) {
2289         ir_node *and = node->node;
2290         node_t  *a   = get_irn_node(get_And_left(and));
2291         node_t  *b   = get_irn_node(get_And_right(and));
2292         tarval  *neutral = get_mode_all_one(get_irn_mode(and));
2293
2294         /* node: no input should be tarval_top, else the And would be also
2295          * Top and not being split. */
2296         if (a->type.tv == neutral)
2297                 return b;
2298         if (b->type.tv == neutral)
2299                 return a;
2300         return node;
2301 }  /* identity_And */
2302
2303 /**
2304  * Calculates the Identity for Confirm nodes.
2305  */
2306 static node_t *identity_Confirm(node_t *node) {
2307         ir_node *confirm = node->node;
2308
2309         /* a Confirm is always a Copy */
2310         return get_irn_node(get_Confirm_value(confirm));
2311 }  /* identity_Confirm */
2312
2313 /**
2314  * Calculates the Identity for Mux nodes.
2315  */
2316 static node_t *identity_Mux(node_t *node) {
2317         ir_node *mux = node->node;
2318         node_t  *t   = get_irn_node(get_Mux_true(mux));
2319         node_t  *f   = get_irn_node(get_Mux_false(mux));
2320         /*node_t  *sel; */
2321
2322         if (t->part == f->part)
2323                 return t;
2324
2325         /* for now, the 1-input identity is not supported */
2326 #if 0
2327         sel = get_irn_node(get_Mux_sel(mux));
2328
2329         /* Mux sel input is mode_b, so it is always a tarval */
2330         if (sel->type.tv == tarval_b_true)
2331                 return t;
2332         if (sel->type.tv == tarval_b_false)
2333                 return f;
2334 #endif
2335         return node;
2336 }  /* identity_Mux */
2337
2338 /**
2339  * Calculates the Identity for Min nodes.
2340  */
2341 static node_t *identity_Min(node_t *node) {
2342         ir_node *op   = node->node;
2343         node_t  *a    = get_irn_node(get_binop_left(op));
2344         node_t  *b    = get_irn_node(get_binop_right(op));
2345         ir_mode *mode = get_irn_mode(op);
2346         tarval  *tv_max;
2347
2348         if (a->part == b->part) {
2349                 /* leader of multiple predecessors */
2350                 return a;
2351         }
2352
2353         /* works even with NaN */
2354         tv_max = get_mode_max(mode);
2355         if (a->type.tv == tv_max)
2356                 return b;
2357         if (b->type.tv == tv_max)
2358                 return a;
2359         return node;
2360 }  /* identity_Min */
2361
2362 /**
2363  * Calculates the Identity for Max nodes.
2364  */
2365 static node_t *identity_Max(node_t *node) {
2366         ir_node *op   = node->node;
2367         node_t  *a    = get_irn_node(get_binop_left(op));
2368         node_t  *b    = get_irn_node(get_binop_right(op));
2369         ir_mode *mode = get_irn_mode(op);
2370         tarval  *tv_min;
2371
2372         if (a->part == b->part) {
2373                 /* leader of multiple predecessors */
2374                 return a;
2375         }
2376
2377         /* works even with NaN */
2378         tv_min = get_mode_min(mode);
2379         if (a->type.tv == tv_min)
2380                 return b;
2381         if (b->type.tv == tv_min)
2382                 return a;
2383         return node;
2384 }  /* identity_Max */
2385
2386 /**
2387  * Calculates the Identity for nodes.
2388  */
2389 static node_t *identity(node_t *node) {
2390         ir_node *irn = node->node;
2391
2392         switch (get_irn_opcode(irn)) {
2393         case iro_Phi:
2394                 return identity_Phi(node);
2395         case iro_Mul:
2396                 return identity_Mul(node);
2397         case iro_Add:
2398         case iro_Or:
2399         case iro_Eor:
2400                 return identity_comm_zero_binop(node);
2401         case iro_Shr:
2402         case iro_Shl:
2403         case iro_Shrs:
2404         case iro_Rotl:
2405                 return identity_shift(node);
2406         case iro_And:
2407                 return identity_And(node);
2408         case iro_Sub:
2409                 return identity_Sub(node);
2410         case iro_Confirm:
2411                 return identity_Confirm(node);
2412         case iro_Mux:
2413                 return identity_Mux(node);
2414         case iro_Min:
2415                 return identity_Min(node);
2416         case iro_Max:
2417                 return identity_Max(node);
2418         default:
2419                 return node;
2420         }
2421 }  /* identity */
2422
2423 /**
2424  * Node follower is a (new) follower of leader, segregate Leader
2425  * out edges.
2426  */
2427 static void segregate_def_use_chain_1(const ir_node *follower, node_t *leader) {
2428         ir_node *l   = leader->node;
2429         int     j, i, n = get_irn_n_outs(l);
2430
2431         DB((dbg, LEVEL_2, "%+F is a follower of %+F\n", follower, leader->node));
2432         /* The leader edges must remain sorted, but follower edges can
2433            be unsorted. */
2434         for (i = leader->n_followers + 1; i <= n; ++i) {
2435                 if (l->out[i].use == follower) {
2436                         ir_def_use_edge t = l->out[i];
2437
2438                         for (j = i - 1; j >= leader->n_followers + 1; --j)
2439                                 l->out[j + 1] = l->out[j];
2440                         ++leader->n_followers;
2441                         l->out[leader->n_followers] = t;
2442                         break;
2443                 }
2444         }
2445 }  /* segregate_def_use_chain_1 */
2446
2447 /**
2448  * Node follower is a (new) follower of leader, segregate Leader
2449  * out edges. If follower is a n-congruent Input identity, all follower
2450  * inputs congruent to follower are also leader.
2451  *
2452  * @param follower  the follower IR node
2453  */
2454 static void segregate_def_use_chain(const ir_node *follower) {
2455         int i;
2456
2457         for (i = get_irn_arity(follower) - 1; i >= 0; --i) {
2458                 node_t *pred = get_irn_node(get_irn_n(follower, i));
2459
2460                 segregate_def_use_chain_1(follower, pred);
2461         }
2462 }  /* segregate_def_use_chain */
2463
2464 /**
2465  * Propagate constant evaluation.
2466  *
2467  * @param env  the environment
2468  */
2469 static void propagate(environment_t *env) {
2470         partition_t    *X, *Y;
2471         node_t         *x;
2472         lattice_elem_t old_type;
2473         node_t         *fallen;
2474         unsigned       n_fallen, old_type_was_T_or_C;
2475         int            i;
2476
2477         while (env->cprop != NULL) {
2478                 void *oldopcode = NULL;
2479
2480                 /* remove the first partition X from cprop */
2481                 X           = env->cprop;
2482                 X->on_cprop = 0;
2483                 env->cprop  = X->cprop_next;
2484
2485                 old_type_was_T_or_C = X->type_is_T_or_C;
2486
2487                 DB((dbg, LEVEL_2, "Propagate type on part%d\n", X->nr));
2488                 fallen   = NULL;
2489                 n_fallen = 0;
2490                 while (! list_empty(&X->cprop)) {
2491                         /* remove the first Node x from X.cprop */
2492                         x = list_entry(X->cprop.next, node_t, cprop_list);
2493                         //assert(x->part == X);
2494                         list_del(&x->cprop_list);
2495                         x->on_cprop = 0;
2496
2497                         if (x->is_follower && identity(x) == x) {
2498                                 /* check the opcode first */
2499                                 if (oldopcode == NULL) {
2500                                         oldopcode = lambda_opcode(get_first_node(X), env);
2501                                 }
2502                                 if (oldopcode != lambda_opcode(x, env)) {
2503                                         if (x->on_fallen == 0) {
2504                                                 /* different opcode -> x falls out of this partition */
2505                                                 x->next      = fallen;
2506                                                 x->on_fallen = 1;
2507                                                 fallen       = x;
2508                                                 ++n_fallen;
2509                                                 DB((dbg, LEVEL_2, "Add node %+F to fallen\n", x->node));
2510                                         }
2511                                 }
2512
2513                                 /* x will make the follower -> leader transition */
2514                                 follower_to_leader(x);
2515                         }
2516
2517                         /* compute a new type for x */
2518                         old_type = x->type;
2519                         DB((dbg, LEVEL_3, "computing type of %+F\n", x->node));
2520                         compute(x);
2521                         if (x->type.tv != old_type.tv) {
2522                                 verify_type(old_type, x->type);
2523                                 DB((dbg, LEVEL_2, "node %+F has changed type from %+F to %+F\n", x->node, old_type, x->type));
2524
2525                                 if (x->on_fallen == 0) {
2526                                         /* Add x to fallen. Nodes might fall from T -> const -> _|_, so check that they are
2527                                            not already on the list. */
2528                                         x->next      = fallen;
2529                                         x->on_fallen = 1;
2530                                         fallen       = x;
2531                                         ++n_fallen;
2532                                         DB((dbg, LEVEL_2, "Add node %+F to fallen\n", x->node));
2533                                 }
2534                                 for (i = get_irn_n_outs(x->node) - 1; i >= 0; --i) {
2535                                         ir_node *succ = get_irn_out(x->node, i);
2536                                         node_t  *y    = get_irn_node(succ);
2537
2538                                         /* Add y to y.partition.cprop. */
2539                                         add_to_cprop(y, env);
2540                                 }
2541                         }
2542                 }
2543
2544                 if (n_fallen > 0 && n_fallen != X->n_leader) {
2545                         DB((dbg, LEVEL_2, "Splitting part%d by fallen\n", X->nr));
2546                         Y = split(&X, fallen, env);
2547                         /*
2548                          * We have split out fallen node. The type of the result
2549                          * partition is NOT set yet.
2550                          */
2551                         Y->type_is_T_or_C = 0;
2552                 } else {
2553                         Y = X;
2554                 }
2555                 /* remove the flags from the fallen list */
2556                 for (x = fallen; x != NULL; x = x->next)
2557                         x->on_fallen = 0;
2558
2559 #ifndef NO_FOLLOWER
2560                 if (old_type_was_T_or_C) {
2561                         node_t *y, *tmp;
2562
2563                         if (Y->on_worklist == 0)
2564                                 add_to_worklist(Y, env);
2565
2566                         /* check if some nodes will make the leader -> follower transition */
2567                         list_for_each_entry_safe(node_t, y, tmp, &Y->Leader, node_list) {
2568                                 if (y->type.tv != tarval_top && ! is_con(y->type)) {
2569                                         node_t *eq_node = identity(y);
2570
2571                                         if (eq_node != y && eq_node->part == y->part) {
2572                                                 DB((dbg, LEVEL_2, "Node %+F is a follower of %+F\n", y->node, eq_node->node));
2573                                                 /* move to Follower */
2574                                                 y->is_follower = 1;
2575                                                 list_del(&y->node_list);
2576                                                 list_add_tail(&y->node_list, &Y->Follower);
2577                                                 --Y->n_leader;
2578
2579                                                 segregate_def_use_chain(y->node);
2580                                         }
2581                                 }
2582                         }
2583                 }
2584 #endif
2585                 split_by(Y, env);
2586         }
2587 }  /* propagate */
2588
2589 /**
2590  * Get the leader for a given node from its congruence class.
2591  *
2592  * @param irn  the node
2593  */
2594 static ir_node *get_leader(node_t *node) {
2595         partition_t *part = node->part;
2596
2597         if (part->n_leader > 1 || node->is_follower) {
2598                 if (node->is_follower) {
2599                         DB((dbg, LEVEL_2, "Replacing follower %+F\n", node->node));
2600                 }
2601                 else
2602                         DB((dbg, LEVEL_2, "Found congruence class for %+F\n", node->node));
2603
2604                 return get_first_node(part)->node;
2605         }
2606         return node->node;
2607 }  /* get_leader */
2608
2609 /**
2610  * Return non-zero if the control flow predecessor node pred
2611  * is the only reachable control flow exit of its block.
2612  *
2613  * @param pred  the control flow exit
2614  */
2615 static int can_exchange(ir_node *pred) {
2616         if (is_Start(pred))
2617                 return 0;
2618         else if (is_Jmp(pred))
2619                 return 1;
2620         else if (get_irn_mode(pred) == mode_T) {
2621                 int i, k;
2622
2623                 /* if the predecessor block has more than one
2624                 reachable outputs we cannot remove the block */
2625                 k = 0;
2626                 for (i = get_irn_n_outs(pred) - 1; i >= 0; --i) {
2627                         ir_node *proj = get_irn_out(pred, i);
2628                         node_t  *node;
2629
2630                         /* skip non-control flow Proj's */
2631                         if (get_irn_mode(proj) != mode_X)
2632                                 continue;
2633
2634                         node = get_irn_node(proj);
2635                         if (node->type.tv == tarval_reachable) {
2636                                 if (++k > 1)
2637                                         return 0;
2638                         }
2639                 }
2640                 return 1;
2641         }
2642         return 0;
2643 }  /* can_exchange */
2644
2645 /**
2646  * Block Post-Walker, apply the analysis results on control flow by
2647  * shortening Phi's and Block inputs.
2648  */
2649 static void apply_cf(ir_node *block, void *ctx) {
2650         environment_t *env = ctx;
2651         node_t        *node = get_irn_node(block);
2652         int           i, j, k, n;
2653         ir_node       **ins, **in_X;
2654         ir_node       *phi, *next;
2655
2656         n = get_Block_n_cfgpreds(block);
2657
2658         if (node->type.tv == tarval_unreachable) {
2659                 env->modified = 1;
2660
2661                 for (i = n - 1; i >= 0; --i) {
2662                         ir_node *pred    = get_Block_cfgpred(block, i);
2663                         node_t  *pred_bl = get_irn_node(get_nodes_block(skip_Proj(pred)));
2664
2665                         if (pred_bl->flagged == 0) {
2666                                 pred_bl->flagged = 3;
2667
2668                                 if (pred_bl->type.tv == tarval_reachable) {
2669                                         /*
2670                                          * We will remove an edge from block to its pred.
2671                                          * This might leave the pred block as an endless loop
2672                                          */
2673                                         if (! is_backedge(block, i))
2674                                                 keep_alive(pred_bl->node);
2675                                 }
2676                         }
2677                 }
2678
2679                 /* the EndBlock is always reachable even if the analysis
2680                    finds out the opposite :-) */
2681                 if (block != get_irg_end_block(current_ir_graph)) {
2682                         /* mark dead blocks */
2683                         set_Block_dead(block);
2684                 } else {
2685                         /* the endblock is unreachable */
2686                         set_irn_in(block, 0, NULL);
2687                 }
2688                 return;
2689         }
2690
2691         if (n == 1) {
2692                 /* only one predecessor combine */
2693                 ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0));
2694
2695                 if (can_exchange(pred)) {
2696                         ir_node *new_block = get_nodes_block(pred);
2697                         DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
2698                         exchange(block, new_block);
2699                         node->node = new_block;
2700                         env->modified = 1;
2701                 }
2702                 return;
2703         }
2704
2705         NEW_ARR_A(ir_node *, in_X, n);
2706         k = 0;
2707         for (i = 0; i < n; ++i) {
2708                 ir_node *pred = get_Block_cfgpred(block, i);
2709                 node_t  *node = get_irn_node(pred);
2710
2711                 if (node->type.tv == tarval_reachable) {
2712                         in_X[k++] = pred;
2713                 } else {
2714                         node_t *pred_bl = get_irn_node(get_nodes_block(skip_Proj(pred)));
2715
2716                         if (pred_bl->flagged == 0) {
2717                                 pred_bl->flagged = 3;
2718
2719                                 if (pred_bl->type.tv == tarval_reachable) {
2720                                         /*
2721                                          * We will remove an edge from block to its pred.
2722                                          * This might leave the pred block as an endless loop
2723                                          */
2724                                         if (! is_backedge(block, i))
2725                                                 keep_alive(pred_bl->node);
2726                                 }
2727                         }
2728                 }
2729         }
2730         if (k >= n)
2731                 return;
2732
2733         NEW_ARR_A(ir_node *, ins, n);
2734         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
2735                 node_t *node = get_irn_node(phi);
2736
2737                 next = get_Phi_next(phi);
2738                 if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
2739                         /* this Phi is replaced by a constant */
2740                         tarval  *tv = node->type.tv;
2741                         ir_node *c  = new_r_Const(current_ir_graph, block, get_tarval_mode(tv), tv);
2742
2743                         set_irn_node(c, node);
2744                         node->node = c;
2745                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, c));
2746                         DBG_OPT_COMBO(phi, c, FS_OPT_COMBO_CONST);
2747                         exchange(phi, c);
2748                         env->modified = 1;
2749                 } else {
2750                         j = 0;
2751                         for (i = 0; i < n; ++i) {
2752                                 node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
2753
2754                                 if (pred->type.tv == tarval_reachable) {
2755                                         ins[j++] = get_Phi_pred(phi, i);
2756                                 }
2757                         }
2758                         if (j == 1) {
2759                                 /* this Phi is replaced by a single predecessor */
2760                                 ir_node *s = ins[0];
2761                                 node_t *phi_node = get_irn_node(phi);
2762
2763                                 node->node = s;
2764                                 DB((dbg, LEVEL_1, "%+F is replaced by %+F because of cf change\n", phi, s));
2765                                 DBG_OPT_COMBO(phi, s, FS_OPT_COMBO_FOLLOWER);
2766                                 exchange(phi, s);
2767                                 phi_node->node = s;
2768                                 env->modified = 1;
2769                         } else {
2770                                 set_irn_in(phi, j, ins);
2771                                 env->modified = 1;
2772                         }
2773                 }
2774         }
2775
2776         if (k == 1) {
2777                 /* this Block has only one live predecessor */
2778                 ir_node *pred = skip_Proj(in_X[0]);
2779
2780                 if (can_exchange(pred)) {
2781                         ir_node *new_block = get_nodes_block(pred);
2782                         DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
2783                         exchange(block, new_block);
2784                         node->node = new_block;
2785                         env->modified = 1;
2786                 }
2787         } else {
2788                 set_irn_in(block, k, in_X);
2789                 env->modified = 1;
2790         }
2791 }
2792
2793 /**
2794  * Post-Walker, apply the analysis results;
2795  */
2796 static void apply_result(ir_node *irn, void *ctx) {
2797         environment_t *env = ctx;
2798         node_t        *node = get_irn_node(irn);
2799
2800         if (is_Block(irn) || is_End(irn) || is_Bad(irn)) {
2801                 /* blocks already handled, do not touch the End node */
2802         } else {
2803                 node_t *block = get_irn_node(get_nodes_block(irn));
2804
2805                 if (block->type.tv == tarval_unreachable) {
2806                         ir_node *bad = get_irg_bad(current_ir_graph);
2807
2808                         /* here, bad might already have a node, but this can be safely ignored
2809                            as long as bad has at least ONE valid node */
2810                         set_irn_node(bad, node);
2811                         node->node = bad;
2812                         DB((dbg, LEVEL_1, "%+F is unreachable\n", irn));
2813                         exchange(irn, bad);
2814                         env->modified = 1;
2815                 }
2816                 else if (node->type.tv == tarval_unreachable) {
2817                         /* don't kick away Unknown */
2818                         if (! is_Unknown(irn)) {
2819                                 ir_node *bad = get_irg_bad(current_ir_graph);
2820
2821                                 /* see comment above */
2822                                 set_irn_node(bad, node);
2823                                 node->node = bad;
2824                                 DB((dbg, LEVEL_1, "%+F is unreachable\n", irn));
2825                                 exchange(irn, bad);
2826                                 env->modified = 1;
2827                         }
2828                 }
2829                 else if (get_irn_mode(irn) == mode_X) {
2830                         if (is_Proj(irn)) {
2831                                 /* leave or Jmp */
2832                                 ir_node *cond = get_Proj_pred(irn);
2833
2834                                 if (is_Cond(cond)) {
2835                                         node_t *sel = get_irn_node(get_Cond_selector(cond));
2836
2837                                         if (is_tarval(sel->type.tv) && tarval_is_constant(sel->type.tv)) {
2838                                                 /* Cond selector is a constant and the Proj is reachable, make a Jmp */
2839                                                 ir_node *jmp  = new_r_Jmp(current_ir_graph, block->node);
2840                                                 set_irn_node(jmp, node);
2841                                                 node->node = jmp;
2842                                                 DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, jmp));
2843                                                 DBG_OPT_COMBO(irn, jmp, FS_OPT_COMBO_CF);
2844                                                 exchange(irn, jmp);
2845                                                 env->modified = 1;
2846                                         }
2847                                 }
2848                         }
2849                 } else {
2850                         /* normal data node */
2851                         if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
2852                                 tarval *tv = node->type.tv;
2853
2854                                 /*
2855                                  * Beware: never replace mode_T nodes by constants. Currently we must mark
2856                                  * mode_T nodes with constants, but do NOT replace them.
2857                                  */
2858                                 if (! is_Const(irn) && get_irn_mode(irn) != mode_T) {
2859                                         /* can be replaced by a constant */
2860                                         ir_node *c = new_r_Const(current_ir_graph, block->node, get_tarval_mode(tv), tv);
2861                                         set_irn_node(c, node);
2862                                         node->node = c;
2863                                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
2864                                         DBG_OPT_COMBO(irn, c, FS_OPT_COMBO_CONST);
2865                                         exchange(irn, c);
2866                                         env->modified = 1;
2867                                 }
2868                         } else if (is_entity(node->type.sym.entity_p)) {
2869                                 if (! is_SymConst(irn)) {
2870                                         /* can be replaced by a Symconst */
2871                                         ir_node *symc = new_r_SymConst(current_ir_graph, block->node, get_irn_mode(irn), node->type.sym, symconst_addr_ent);
2872                                         set_irn_node(symc, node);
2873                                         node->node = symc;
2874
2875                                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, symc));
2876                                         DBG_OPT_COMBO(irn, symc, FS_OPT_COMBO_CONST);
2877                                         exchange(irn, symc);
2878                                         env->modified = 1;
2879                                 }
2880                         } else if (is_Confirm(irn)) {
2881                                 /* Confirms are always follower, but do not kill them here */
2882                         } else {
2883                                 ir_node *leader = get_leader(node);
2884
2885                                 if (leader != irn) {
2886                                         DB((dbg, LEVEL_1, "%+F from part%d is replaced by %+F\n", irn, node->part->nr, leader));
2887                                         if (node->is_follower)
2888                                                 DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_FOLLOWER);
2889                                         else
2890                                                 DBG_OPT_COMBO(irn, leader, FS_OPT_COMBO_CONGRUENT);
2891                                         exchange(irn, leader);
2892                                         env->modified = 1;
2893                                 }
2894                         }
2895                 }
2896         }
2897 }  /* apply_result */
2898
2899 /**
2900  * Fix the keep-alives by deleting unreachable ones.
2901  */
2902 static void apply_end(ir_node *end, environment_t *env) {
2903         int i, j,  n = get_End_n_keepalives(end);
2904         ir_node **in;
2905
2906         if (n > 0)
2907                 NEW_ARR_A(ir_node *, in, n);
2908
2909         /* fix the keep alive */
2910         for (i = j = 0; i < n; i++) {
2911                 ir_node *ka   = get_End_keepalive(end, i);
2912                 node_t  *node = get_irn_node(ka);
2913
2914                 if (! is_Block(ka))
2915                         node = get_irn_node(get_nodes_block(ka));
2916
2917                 if (node->type.tv != tarval_unreachable)
2918                         in[j++] = ka;
2919         }
2920         if (j != n) {
2921                 set_End_keepalives(end, j, in);
2922                 env->modified = 1;
2923         }
2924 }  /* apply_end */
2925
2926 #define SET(code) op_##code->ops.generic = (op_func)compute_##code
2927
2928 /**
2929  * sets the generic functions to compute.
2930  */
2931 static void set_compute_functions(void) {
2932         int i;
2933
2934         /* set the default compute function */
2935         for (i = get_irp_n_opcodes() - 1; i >= 0; --i) {
2936                 ir_op *op = get_irp_opcode(i);
2937                 op->ops.generic = (op_func)default_compute;
2938         }
2939
2940         /* set specific functions */
2941         SET(Block);
2942         SET(Unknown);
2943         SET(Bad);
2944         SET(Jmp);
2945         SET(Phi);
2946         SET(Add);
2947         SET(Sub);
2948         SET(Eor);
2949         SET(SymConst);
2950         SET(Cmp);
2951         SET(Proj);
2952         SET(Confirm);
2953         SET(End);
2954
2955         if (op_Max != NULL)
2956                 SET(Max);
2957         if (op_Min != NULL)
2958                 SET(Min);
2959
2960 }  /* set_compute_functions */
2961
2962 static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
2963         ir_node *irn = local != NULL ? local : n;
2964         node_t *node = get_irn_node(irn);
2965
2966         ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
2967         return 1;
2968 }
2969
2970 void combo(ir_graph *irg) {
2971         environment_t env;
2972         ir_node       *initial_bl;
2973         node_t        *start;
2974         ir_graph      *rem = current_ir_graph;
2975
2976         current_ir_graph = irg;
2977
2978         /* register a debug mask */
2979         FIRM_DBG_REGISTER(dbg, "firm.opt.combo");
2980         //firm_dbg_set_mask(dbg, SET_LEVEL_3);
2981
2982         DB((dbg, LEVEL_1, "Doing COMBO for %+F\n", irg));
2983
2984         obstack_init(&env.obst);
2985         env.worklist       = NULL;
2986         env.cprop          = NULL;
2987         env.touched        = NULL;
2988         env.initial        = NULL;
2989 #ifdef DEBUG_libfirm
2990         env.dbg_list       = NULL;
2991 #endif
2992         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
2993         env.type2id_map    = pmap_create();
2994         env.end_idx        = get_opt_global_cse() ? 0 : -1;
2995         env.lambda_input   = 0;
2996         env.nonstd_cond    = 0;
2997         env.modified       = 0;
2998
2999         assure_irg_outs(irg);
3000         assure_cf_loop(irg);
3001
3002
3003         /* we have our own value_of function */
3004         set_value_of_func(get_node_tarval);
3005
3006         set_compute_functions();
3007         DEBUG_ONLY(part_nr = 0);
3008
3009         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
3010
3011         /* create the initial partition and place it on the work list */
3012         env.initial = new_partition(&env);
3013         add_to_worklist(env.initial, &env);
3014         irg_walk_graph(irg, init_block_phis, create_initial_partitions, &env);
3015
3016 #ifdef WITH_UNKNOWN
3017         tarval_UNKNOWN = env.nonstd_cond ? tarval_bad : tarval_top;
3018 #else
3019         tarval_UNKNOWN = tarval_bad;
3020 #endif
3021
3022         /* all nodes on the initial partition have type Top */
3023         env.initial->type_is_T_or_C = 1;
3024
3025         /* Place the START Node's partition on cprop.
3026            Place the START Node on its local worklist. */
3027         initial_bl = get_irg_start_block(irg);
3028         start      = get_irn_node(initial_bl);
3029         add_to_cprop(start, &env);
3030
3031         do {
3032                 propagate(&env);
3033                 if (env.worklist != NULL)
3034                         cause_splits(&env);
3035         } while (env.cprop != NULL || env.worklist != NULL);
3036
3037         dump_all_partitions(&env);
3038         check_all_partitions(&env);
3039
3040 #if 0
3041         set_dump_node_vcgattr_hook(dump_partition_hook);
3042         dump_ir_block_graph(irg, "-partition");
3043         set_dump_node_vcgattr_hook(NULL);
3044 #else
3045         (void)dump_partition_hook;
3046 #endif
3047
3048         /* apply the result */
3049         irg_block_walk_graph(irg, NULL, apply_cf, &env);
3050         irg_walk_graph(irg, NULL, apply_result, &env);
3051         apply_end(get_irg_end(irg), &env);
3052
3053         if (env.modified) {
3054                 /* control flow might changed */
3055                 set_irg_outs_inconsistent(irg);
3056                 set_irg_extblk_inconsistent(irg);
3057                 set_irg_doms_inconsistent(irg);
3058                 set_irg_loopinfo_inconsistent(irg);
3059         }
3060
3061         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
3062
3063         pmap_destroy(env.type2id_map);
3064         del_set(env.opcode2id_map);
3065         obstack_free(&env.obst, NULL);
3066
3067         /* restore value_of() default behavior */
3068         set_value_of_func(NULL);
3069         current_ir_graph = rem;
3070 }  /* combo */