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