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

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