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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Cliff Click's Combined Analysis/Optimization
  23  * @author  Michael Beck
  24  * @version $Id$
  25  *
  26  * Note that the current implementation lack the leaders/followers
  27  * support.
  28  *
  29  * Note further that we use the terminology from Click's work here, which is different
  30  * in some cases from Firm terminology.  Especially, Click's type is a
  31  * Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
  32  */
  33 #ifdef HAVE_CONFIG_H
  34 # include "config.h"
  35 #endif
  36
  37 #include <assert.h>
  38
  39 #include "iroptimize.h"
  40 #include "irflag.h"
  41 #include "ircons.h"
  42 #include "list.h"
  43 #include "set.h"
  44 #include "pmap.h"
  45 #include "obstack.h"
  46 #include "irgraph_t.h"
  47 #include "irnode_t.h"
  48 #include "iropt_t.h"
  49 #include "irgwalk.h"
  50 #include "irop.h"
  51 #include "irouts.h"
  52 #include "irgmod.h"
  53 #include "debug.h"
  54 #include "error.h"
  55
  56 #include "tv_t.h"
  57
  58 #include "irprintf.h"
  59 #include "irdump.h"
  60
  61 /* define this to check that all type translations are monotone */
  62 #define VERIFY_MONOTONE
  63
  64 typedef struct node_t            node_t;
  65 typedef struct partition_t       partition_t;
  66 typedef struct opcode_key_t      opcode_key_t;
  67 typedef struct listmap_entry_t   listmap_entry_t;
  68
  69 /** The type of the compute function. */
  70 typedef void (*compute_func)(node_t *node);
  71
  72 /**
  73  * An opcode map key.
  74  */
  75 struct opcode_key_t {
  76         ir_opcode   code;   /**< The Firm opcode. */
  77         ir_mode     *mode;  /**< The mode of all nodes in the partition. */
  78         union {
  79                 long      proj;   /**< For Proj nodes, its proj number */
  80                 ir_entity *ent;   /**< For Sel Nodes, its entity */
  81         } u;
  82 };
  83
  84 /**
  85  * An entry in the list_map.
  86  */
  87 struct listmap_entry_t {
  88         void            *id;    /**< The id. */
  89         node_t          *list;  /**< The associated list for this id. */
  90         listmap_entry_t *next;  /**< Link to the next entry in the map. */
  91 };
  92
  93 /** We must map id's to lists. */
  94 typedef struct listmap_t {
  95         set             *map;    /**< Map id's to listmap_entry_t's */
  96         listmap_entry_t *values; /**< List of all values in the map. */
  97 } listmap_t;
  98
  99 /**
 100  * A lattice element. Because we handle constants and symbolic constants different, we
 101  * have to use this union.
 102  */
 103 typedef union {
 104         tarval          *tv;
 105         symconst_symbol sym;
 106 } lattice_elem_t;
 107
 108 /**
 109  * A node.
 110  */
 111 struct node_t {
 112         ir_node         *node;          /**< The IR-node itself. */
 113         list_head       node_list;      /**< Double-linked list of entries. */
 114         list_head       cprop_list;     /**< Double-linked partition.cprop list. */
 115         partition_t     *part;          /**< points to the partition this node belongs to */
 116         node_t          *next;          /**< Next node on local list (partition.touched, fallen). */
 117         lattice_elem_t  type;           /**< The associated lattice element "type". */
 118         int             max_user_input; /**< Maximum input number of Def-Use edges. */
 119         int             next_edge;      /**< Index of the next Def-Use edge to use. */
 120         unsigned        on_touched:1;   /**< Set, if this node is on the partition.touched set. */
 121         unsigned        on_cprop:1;     /**< Set, if this node is on the partition.cprop list. */
 122         unsigned        on_fallen:1;    /**< Set, if this node is on the fallen list. */
 123 };
 124
 125 /**
 126  * A partition containing congruent nodes.
 127  */
 128 struct partition_t {
 129         list_head         entries;         /**< The head of partition node list. */
 130         list_head         cprop;           /**< The head of partition.cprop list. */
 131         partition_t       *wl_next;        /**< Next entry in the work list if any. */
 132         partition_t       *touched_next;   /**< Points to the next partition in the touched set. */
 133         partition_t       *cprop_next;     /**< Points to the next partition in the cprop list. */
 134         partition_t       *split_next;     /**< Points to the next partition in the list that must be split by split_by(). */
 135         node_t            *touched;        /**< The partition.touched set of this partition. */
 136         unsigned          n_nodes;         /**< Number of entries in this partition. */
 137         unsigned          n_touched;       /**< Number of entries in the partition.touched. */
 138         int               max_user_inputs; /**< Maximum number of user inputs of all entries. */
 139         unsigned          on_worklist:1;   /**< Set, if this partition is in the work list. */
 140         unsigned          on_touched:1;    /**< Set, if this partition is on the touched set. */
 141         unsigned          on_cprop:1;      /**< Set, if this partition is on the cprop list. */
 142 #ifdef DEBUG_libfirm
 143         partition_t       *dbg_next;       /**< Link all partitions for debugging */
 144         unsigned          nr;              /**< A unique number for (what-)mapping, >0. */
 145 #endif
 146 };
 147
 148 typedef struct environment_t {
 149         struct obstack  obst;           /**< obstack to allocate data structures. */
 150         partition_t     *worklist;      /**< The work list. */
 151         partition_t     *cprop;         /**< The constant propagation list. */
 152         partition_t     *touched;       /**< the touched set. */
 153         partition_t     *initial;       /**< The initial partition. */
 154         set             *opcode2id_map; /**< The opcodeMode->id map. */
 155         pmap            *type2id_map;   /**< The type->id map. */
 156         int             end_idx;        /**< -1 for local and 0 for global congruences. */
 157         int             lambda_input;   /**< Captured argument for lambda_partition(). */
 158 #ifdef DEBUG_libfirm
 159         partition_t     *dbg_list;      /**< List of all partitions. */
 160 #endif
 161 } environment_t;
 162
 163 /** Type of the what function. */
 164 typedef void *(*what_func)(const node_t *node, environment_t *env);
 165
 166 #define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
 167 #define set_irn_node(irn, node)   set_irn_link(irn, node)
 168
 169 /* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
 170 #undef tarval_unreachable
 171 #define tarval_unreachable tarval_top
 172
 173
 174 /** The debug module handle. */
 175 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 176
 177 /** Next partition number. */
 178 DEBUG_ONLY(static unsigned part_nr = 0);
 179
 180 #ifdef DEBUG_libfirm
 181 static INLINE lattice_elem_t get_partition_type(const partition_t *X);
 182
 183 /**
 184  * Dump partition to output.
 185  */
 186 static void dump_partition(const char *msg, const partition_t *part) {
 187         const node_t   *node;
 188         int            first = 1;
 189         lattice_elem_t type = get_partition_type(part);
 190
 191         DB((dbg, LEVEL_2, "%s part%u (%u, %+F) {\n  ", msg, part->nr, part->n_nodes, type));
 192         list_for_each_entry(node_t, node, &part->entries, node_list) {
 193                 DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
 194                 first = 0;
 195         }
 196         DB((dbg, LEVEL_2, "\n}\n"));
 197 }
 198
 199 /**
 200  * Dump all partitions.
 201  */
 202 static void dump_all_partitions(const environment_t *env) {
 203         const partition_t *P;
 204
 205         DB((dbg, LEVEL_2, "All partitions\n===============\n"));
 206         for (P = env->dbg_list; P != NULL; P = P->dbg_next)
 207                 dump_partition("", P);
 208 }
 209
 210 #else
 211 #define dump_partition(msg, part)
 212 #define dump_all_partitions(env)
 213 #endif
 214
 215 #if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
 216 /**
 217  * Verify that a type transition is monotone
 218  */
 219 static void verify_type(const lattice_elem_t old_type, const lattice_elem_t new_type) {
 220         if (old_type.tv == new_type.tv) {
 221                 /* no change */
 222                 return;
 223         }
 224         if (old_type.tv == tarval_top) {
 225                 /* from Top down-to is always allowed */
 226                 return;
 227         }
 228         if (old_type.tv == tarval_reachable) {
 229                 panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type);
 230         }
 231         if (new_type.tv == tarval_bottom || new_type.tv == tarval_reachable) {
 232                 /* bottom reached */
 233                 return;
 234         }
 235         panic("verify_type(): wrong translation from %+F to %+F", old_type, new_type);
 236 }
 237 #else
 238 #define verify_type(old_type, new_type)
 239 #endif
 240
 241 /**
 242  * Compare two pointer values of a listmap.
 243  */
 244 static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
 245         const listmap_entry_t *e1 = elt;
 246         const listmap_entry_t *e2 = key;
 247
 248         (void) size;
 249         return e1->id != e2->id;
 250 }  /* listmap_cmp_ptr */
 251
 252 /**
 253  * Initializes a listmap.
 254  *
 255  * @param map  the listmap
 256  */
 257 static void listmap_init(listmap_t *map) {
 258         map->map    = new_set(listmap_cmp_ptr, 16);
 259         map->values = NULL;
 260 }  /* listmap_init */
 261
 262 /**
 263  * Terminates a listmap.
 264  *
 265  * @param map  the listmap
 266  */
 267 static void listmap_term(listmap_t *map) {
 268         del_set(map->map);
 269 }  /* listmap_term */
 270
 271 /**
 272  * Return the associated listmap entry for a given id.
 273  *
 274  * @param map  the listmap
 275  * @param id   the id to search for
 276  *
 277  * @return the asociated listmap entry for the given id
 278  */
 279 static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
 280         listmap_entry_t key, *entry;
 281
 282         key.id   = id;
 283         key.list = NULL;
 284         key.next = NULL;
 285         entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));
 286
 287         if (entry->list == NULL) {
 288                 /* a new entry, put into the list */
 289                 entry->next = map->values;
 290                 map->values = entry;
 291         }
 292         return entry;
 293 }  /* listmap_find */
 294
 295 /**
 296  * Calculate the hash value for an opcode map entry.
 297  *
 298  * @param entry  an opcode map entry
 299  *
 300  * @return a hash value for the given opcode map entry
 301  */
 302 static unsigned opcode_hash(const opcode_key_t *entry) {
 303         return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent);
 304 }  /* opcode_hash */
 305
 306 /**
 307  * Compare two entries in the opcode map.
 308  */
 309 static int cmp_opcode(const void *elt, const void *key, size_t size) {
 310         const opcode_key_t *o1 = elt;
 311         const opcode_key_t *o2 = key;
 312
 313         (void) size;
 314         return o1->code != o2->code || o1->mode != o2->mode ||
 315                o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
 316 }  /* cmp_opcode */
 317
 318 /**
 319  * Compare two Def-Use edges for input position.
 320  */
 321 static int cmp_def_use_edge(const void *a, const void *b) {
 322         const ir_def_use_edge *ea = a;
 323         const ir_def_use_edge *eb = b;
 324
 325         /* no overrun, because range is [-1, MAXINT] */
 326         return ea->pos - eb->pos;
 327 }  /* cmp_def_use_edge */
 328
 329 /**
 330  * We need the Def-Use edges sorted.
 331  */
 332 static void sort_irn_outs(node_t *node) {
 333         ir_node *irn = node->node;
 334         int n_outs = get_irn_n_outs(irn);
 335
 336         if (n_outs > 1) {
 337                 qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge);
 338         }
 339         node->max_user_input = irn->out[n_outs].pos;
 340 }  /* sort_irn_outs */
 341
 342 /**
 343  * Return the type of a node.
 344  *
 345  * @param irn  an IR-node
 346  *
 347  * @return the associated type of this node
 348  */
 349 static INLINE lattice_elem_t get_node_type(const ir_node *irn) {
 350         return get_irn_node(irn)->type;
 351 }  /* get_node_type */
 352
 353 /**
 354  * Return the tarval of a node.
 355  *
 356  * @param irn  an IR-node
 357  *
 358  * @return the associated type of this node
 359  */
 360 static INLINE tarval *get_node_tarval(const ir_node *irn) {
 361         lattice_elem_t type = get_node_type(irn);
 362
 363         if (is_tarval(type.tv))
 364                 return type.tv;
 365         return tarval_bottom;
 366 }  /* get_node_type */
 367
 368 /**
 369  * Add a partition to the worklist.
 370  */
 371 static INLINE void add_to_worklist(partition_t *X, environment_t *env) {
 372         assert(X->on_worklist == 0);
 373         X->wl_next     = env->worklist;
 374         X->on_worklist = 1;
 375         env->worklist  = X;
 376 }
 377
 378 /**
 379  * Create a new empty partition.
 380  *
 381  * @param env   the environment
 382  *
 383  * @return a newly allocated partition
 384  */
 385 static INLINE partition_t *new_partition(environment_t *env) {
 386         partition_t *part = obstack_alloc(&env->obst, sizeof(*part));
 387
 388         INIT_LIST_HEAD(&part->entries);
 389         INIT_LIST_HEAD(&part->cprop);
 390         part->wl_next         = NULL;
 391         part->touched_next    = NULL;
 392         part->cprop_next      = NULL;
 393         part->split_next      = NULL;
 394         part->touched         = NULL;
 395         part->n_nodes         = 0;
 396         part->n_touched       = 0;
 397         part->max_user_inputs = 0;
 398         part->on_worklist     = 0;
 399         part->on_touched      = 0;
 400         part->on_cprop        = 0;
 401 #ifdef DEBUG_libfirm
 402         part->dbg_next        = env->dbg_list;
 403         env->dbg_list         = part;
 404         part->nr              = part_nr++;
 405 #endif
 406
 407         return part;
 408 }  /* new_partition */
 409
 410 /**
 411  * Get the first node from a partition.
 412  */
 413 static INLINE node_t *get_first_node(const partition_t *X) {
 414         return list_entry(X->entries.next, node_t, node_list);
 415 }
 416
 417 /**
 418  * Return the type of a partition (assuming partition is non-empty and
 419  * all elements have the same type).
 420  *
 421  * @param X  a partition
 422  *
 423  * @return the type of the first element of the partition
 424  */
 425 static INLINE lattice_elem_t get_partition_type(const partition_t *X) {
 426         const node_t *first = get_first_node(X);
 427         return first->type;
 428 }  /* get_partition_type */
 429
 430 /**
 431  * Creates a partition node for the given IR-node and place it
 432  * into the given partition.
 433  *
 434  * @param irn   an IR-node
 435  * @param part  a partition to place the node in
 436  * @param env   the environment
 437  *
 438  * @return the created node
 439  */
 440 static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env) {
 441         /* create a partition node and place it in the partition */
 442         node_t *node = obstack_alloc(&env->obst, sizeof(*node));
 443
 444         INIT_LIST_HEAD(&node->node_list);
 445         INIT_LIST_HEAD(&node->cprop_list);
 446         node->node           = irn;
 447         node->part           = part;
 448         node->next           = NULL;
 449         node->type.tv        = tarval_top;
 450         node->max_user_input = 0;
 451         node->next_edge      = 0;
 452         node->on_touched     = 0;
 453         node->on_cprop       = 0;
 454         node->on_fallen      = 0;
 455         set_irn_node(irn, node);
 456
 457         list_add_tail(&node->node_list, &part->entries);
 458         ++part->n_nodes;
 459
 460         return node;
 461 }  /* create_partition_node */
 462
 463 /**
 464  * Pre-Walker, init all Block-Phi lists.
 465  */
 466 static void init_block_phis(ir_node *irn, void *env) {
 467         (void) env;
 468
 469         if (is_Block(irn)) {
 470                 set_Block_phis(irn, NULL);
 471         }
 472 }
 473
 474 /**
 475  * Post-Walker, initialize all Nodes' type to U or top and place
 476  * all nodes into the TOP partition.
 477  */
 478 static void create_initial_partitions(ir_node *irn, void *ctx) {
 479         environment_t *env  = ctx;
 480         partition_t   *part = env->initial;
 481         node_t        *node;
 482
 483         node = create_partition_node(irn, part, env);
 484         sort_irn_outs(node);
 485         if (node->max_user_input > part->max_user_inputs)
 486                 part->max_user_inputs = node->max_user_input;
 487
 488         if (is_Phi(irn)) {
 489                 add_Block_phi(get_nodes_block(irn), irn);
 490         }
 491 }  /* create_initial_partitions */
 492
 493 /**
 494  * Add a partition to the touched set if not already there.
 495  *
 496  * @param part  the partition
 497  * @param env   the environment
 498  */
 499 static INLINE void add_to_touched(partition_t *part, environment_t *env) {
 500         if (part->on_touched == 0) {
 501                 part->touched_next = env->touched;
 502                 env->touched       = part;
 503                 part->on_touched   = 1;
 504         }
 505 }  /* add_to_touched */
 506
 507 /**
 508  * Add a node to the entry.partition.touched set if not already there.
 509  *
 510  * @param y  a node
 511  */
 512 static INLINE void add_to_partition_touched(node_t *y) {
 513         if (y->on_touched == 0) {
 514                 partition_t *part = y->part;
 515
 516                 y->next       = part->touched;
 517                 part->touched = y;
 518                 y->on_touched = 1;
 519                 ++part->n_touched;
 520         }
 521 }  /* add_to_partition_touched */
 522
 523 /**
 524  * Update the worklist: If Z is on worklist then add Z' to worklist.
 525  * Else add the smaller of Z and Z' to worklist.
 526  *
 527  * @param Z        the Z partition
 528  * @param Z_prime  the Z' partition, a previous part of Z
 529  * @param env      the environment
 530  */
 531 static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env) {
 532         if (Z->on_worklist || Z_prime->n_nodes < Z->n_nodes) {
 533                 add_to_worklist(Z_prime, env);
 534         } else {
 535                 add_to_worklist(Z, env);
 536         }
 537 }  /* update_worklist */
 538
 539 /**
 540  * Split a partition by a local list.
 541  *
 542  * @param Z    the Z partition to split
 543  * @param g    a (non-empty) node list
 544  * @param env  the environment
 545  *
 546  * @return  a new partition containing the nodes of g
 547  */
 548 static partition_t *split(partition_t *Z, node_t *g, environment_t *env) {
 549         partition_t *Z_prime;
 550         node_t      *node;
 551         unsigned    n = 0;
 552         int         max_input, max_arity, arity;
 553
 554         dump_partition("Splitting ", Z);
 555
 556         assert(g != NULL);
 557
 558         /* Remove g from Z. */
 559         for (node = g; node != NULL; node = node->next) {
 560                 list_del(&node->node_list);
 561                 ++n;
 562         }
 563         assert(n < Z->n_nodes);
 564         Z->n_nodes -= n;
 565
 566         /* Move g to a new partition, Z\92. */
 567         Z_prime = new_partition(env);
 568         max_arity = max_input = 0;
 569         for (node = g; node != NULL; node = node->next) {
 570                 list_add(&node->node_list, &Z_prime->entries);
 571                 node->part = Z_prime;
 572                 arity = get_irn_arity(node->node);
 573                 if (arity > max_arity)
 574                         max_arity = arity;
 575                 if (node->max_user_input > max_input)
 576                         max_input = node->max_user_input;
 577         }
 578         Z_prime->max_user_inputs = max_input;
 579         Z_prime->n_nodes         = n;
 580
 581         update_worklist(Z, Z_prime, env);
 582
 583         dump_partition("Now ", Z);
 584         dump_partition("Created new ", Z_prime);
 585         return Z_prime;
 586 }  /* split */
 587
 588 /**
 589  * Returns non-zero if the i'th input of a Phi node is live.
 590  *
 591  * @param phi  a Phi-node
 592  * @param i    an input number
 593  *
 594  * @return non-zero if the i'th input of the given Phi node is live
 595  */
 596 static int is_live_input(ir_node *phi, int i) {
 597         if (i >= 0) {
 598                 ir_node        *block = get_nodes_block(phi);
 599                 ir_node        *pred  = get_Block_cfgpred(block, i);
 600                 lattice_elem_t type   = get_node_type(pred);
 601
 602                 return type.tv != tarval_unreachable;
 603         }
 604         /* else it's the control input, always live */
 605         return 1;
 606 }  /* is_live_input */
 607
 608 /**
 609  * Return non-zero if a type is a constant.
 610  */
 611 static int is_constant_type(lattice_elem_t type) {
 612         if (type.tv != tarval_bottom && type.tv != tarval_top)
 613                 return 1;
 614         return 0;
 615 }  /* is_constant_type */
 616
 617 /**
 618  * Place a node on the cprop list.
 619  *
 620  * @param y    the node
 621  * @param env  the environment
 622  */
 623 static void add_node_to_cprop(node_t *y, environment_t *env) {
 624         /* Add y to y.partition.cprop. */
 625         if (y->on_cprop == 0) {
 626                 partition_t *Y = y->part;
 627
 628                 list_add_tail(&y->cprop_list, &Y->cprop);
 629                 y->on_cprop   = 1;
 630
 631                 DB((dbg, LEVEL_3, "Add %+F to part%u.cprop\n", y->node, Y->nr));
 632
 633                 /* place its partition on the cprop list */
 634                 if (Y->on_cprop == 0) {
 635                         Y->cprop_next = env->cprop;
 636                         env->cprop    = Y;
 637                         Y->on_cprop   = 1;
 638                 }
 639         }
 640         if (get_irn_mode(y->node) == mode_T) {
 641                 /* mode_T nodes always produce tarval_bottom, so we must explicitly
 642                    add it's Proj's to get constant evaluation to work */
 643                 int i;
 644
 645                 for (i = get_irn_n_outs(y->node) - 1; i >= 0; --i) {
 646                         node_t *proj = get_irn_node(get_irn_out(y->node, i));
 647
 648                         add_node_to_cprop(proj, env);
 649                 }
 650         }
 651
 652         if (is_Block(y->node)) {
 653                 /* Due to the way we handle Phi's, we must place all Phis of a block on the list
 654                  * if someone placed the block. The Block is only placed if the reachability
 655                  * changes, and this must be re-evaluated in compute_Phi(). */
 656                 ir_node *phi;
 657                 for (phi = get_Block_phis(y->node); phi != NULL; phi = get_Phi_next(phi)) {
 658                         node_t *p = get_irn_node(phi);
 659                         add_node_to_cprop(p, env);
 660                 }
 661         }
 662 }  /* add_node_to_cprop */
 663
 664 /**
 665  * Check whether a type is neither Top or a constant.
 666  * Note: U is handled like Top here, R is a constant.
 667  *
 668  * @param type  the type to check
 669  */
 670 static int type_is_neither_top_nor_const(const lattice_elem_t type) {
 671         if (is_tarval(type.tv)) {
 672                 if (type.tv == tarval_top)
 673                         return 0;
 674                 if (tarval_is_constant(type.tv))
 675                         return 0;
 676         } else {
 677                 /* is a symconst */
 678                 return 0;
 679         }
 680         return 1;
 681 }
 682
 683 /**
 684  * Split the partitions if caused by the first entry on the worklist.
 685  *
 686  * @param env  the environment
 687  */
 688 static void cause_splits(environment_t *env) {
 689         partition_t *X, *Y, *Z;
 690         node_t      *x, *y, *e;
 691         int         i, end_idx;
 692         ir_opcode   code;
 693         ir_node     *succ;
 694
 695         /* remove the first partition from the worklist */
 696         X = env->worklist;
 697         env->worklist  = X->wl_next;
 698         X->on_worklist = 0;
 699
 700         dump_partition("Cause_split: ", X);
 701         end_idx = env->end_idx;
 702         for (i = -1; i <= X->max_user_inputs; ++i) {
 703                 /* empty the touched set: already done, just clear the list */
 704                 env->touched = NULL;
 705
 706                 list_for_each_entry(node_t, x, &X->entries, node_list) {
 707                         int num_edges;
 708
 709                         if (i == -1) {
 710                                 x->next_edge = 1;
 711                         }
 712                         num_edges = get_irn_n_outs(x->node);
 713
 714                         while (x->next_edge <= num_edges) {
 715                                 ir_def_use_edge *edge = &x->node->out[x->next_edge];
 716
 717                                 /* check if we have necessary edges */
 718                                 if (edge->pos > i)
 719                                         break;
 720
 721                                 ++x->next_edge;
 722
 723                                 succ = edge->use;
 724
 725                                 /* ignore the "control input" for non-pinned nodes
 726                                    if we are running in GCSE mode */
 727                                 if (i < end_idx && get_irn_pinned(succ) != op_pin_state_pinned)
 728                                         continue;
 729
 730                                 y = get_irn_node(succ);
 731                                 if (is_constant_type(y->type)) {
 732                                         code = get_irn_opcode(succ);
 733                                         if (code == iro_Sub || code == iro_Cmp)
 734                                                 add_node_to_cprop(y, env);
 735                                 }
 736
 737                                 /* Partitions of constants should not be split simply because their Nodes have unequal
 738                                    functions or incongruent inputs. */
 739                                 if (type_is_neither_top_nor_const(y->type) &&
 740                                         (! is_Phi(y->node) || is_live_input(y->node, i))) {
 741                                         Y = y->part;
 742                                         add_to_touched(Y, env);
 743                                         add_to_partition_touched(y);
 744                                 }
 745                         }
 746                 }
 747
 748                 for (Z = env->touched; Z != NULL; Z = Z->touched_next) {
 749                         /* remove it from the touched set */
 750                         Z->on_touched = 0;
 751
 752                         if (Z->n_nodes != Z->n_touched) {
 753                                 DB((dbg, LEVEL_2, "Split part%d by touched\n", Z->nr));
 754                                 split(Z, Z->touched, env);
 755                         }
 756                         /* Empty local Z.touched. */
 757                         for (e = Z->touched; e != NULL; e = e->next) {
 758                                 e->on_touched = 0;
 759                         }
 760                         Z->touched   = NULL;
 761                         Z->n_touched = 0;
 762                 }
 763         }
 764 }  /* cause_splits */
 765
 766 /**
 767  * Implements split_by_what(): Split a partition by characteristics given
 768  * by the what function.
 769  *
 770  * @param X     the partition to split
 771  * @param What  a function returning an Id for every node of the partition X
 772  * @param P     a list to store the result partitions
 773  * @param env   the environment
 774  *
 775  * @return *P
 776  */
 777 static partition_t *split_by_what(partition_t *X, what_func What,
 778                                   partition_t **P, environment_t *env) {
 779         node_t          *x, *S;
 780         listmap_t       map;
 781         listmap_entry_t *iter;
 782         partition_t     *R;
 783
 784         /* Let map be an empty mapping from the range of What to (local) list of Nodes. */
 785         listmap_init(&map);
 786         list_for_each_entry(node_t, x, &X->entries, node_list) {
 787                 void            *id = What(x, env);
 788                 listmap_entry_t *entry;
 789
 790                 if (id == NULL) {
 791                         /* input not allowed, ignore */
 792                         continue;
 793                 }
 794                 /* Add x to map[What(x)]. */
 795                 entry = listmap_find(&map, id);
 796                 x->next     = entry->list;
 797                 entry->list = x;
 798         }
 799         /* Let P be a set of Partitions. */
 800
 801         /* for all sets S except one in the range of map do */
 802         for (iter = map.values; iter != NULL; iter = iter->next) {
 803                 if (iter->next == NULL) {
 804                         /* this is the last entry, ignore */
 805                         break;
 806                 }
 807                 S = iter->list;
 808
 809                 /* Add SPLIT( X, S ) to P. */
 810                 DB((dbg, LEVEL_2, "Split part%d by what\n", X->nr));
 811                 R = split(X, S, env);
 812                 R->split_next = *P;
 813                 *P            = R;
 814         }
 815         /* Add X to P. */
 816         X->split_next = *P;
 817         *P            = X;
 818
 819         listmap_term(&map);
 820         return *P;
 821 }  /* split_by_what */
 822
 823 /** lambda n.(n.type) */
 824 static void *lambda_type(const node_t *node, environment_t *env) {
 825         (void)env;
 826         return node->type.tv;
 827 }  /* lambda_type */
 828
 829 /** lambda n.(n.opcode) */
 830 static void *lambda_opcode(const node_t *node, environment_t *env) {
 831         opcode_key_t key, *entry;
 832         ir_node      *irn = node->node;
 833
 834         key.code   = get_irn_opcode(irn);
 835         key.mode   = get_irn_mode(irn);
 836         key.u.proj = 0;
 837         key.u.ent  = NULL;
 838
 839         switch (get_irn_opcode(irn)) {
 840         case iro_Proj:
 841                 key.u.proj = get_Proj_proj(irn);
 842                 break;
 843         case iro_Sel:
 844                 key.u.ent = get_Sel_entity(irn);
 845                 break;
 846         default:
 847                 break;
 848         }
 849
 850         entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key));
 851         return entry;
 852 }  /* lambda_opcode */
 853
 854 /** lambda n.(n[i].partition) */
 855 static void *lambda_partition(const node_t *node, environment_t *env) {
 856         ir_node *skipped = skip_Proj(node->node);
 857         ir_node *pred;
 858         node_t  *p;
 859         int     i = env->lambda_input;
 860
 861         if (i >= get_irn_arity(node->node)) {
 862                 /* we are outside the allowed range */
 863                 return NULL;
 864         }
 865
 866         /* ignore the "control input" for non-pinned nodes
 867            if we are running in GCSE mode */
 868         if (i < env->end_idx && get_irn_pinned(skipped) != op_pin_state_pinned)
 869                 return NULL;
 870
 871         pred = i == -1 ? get_irn_n(skipped, i) : get_irn_n(node->node, i);
 872         p    = get_irn_node(pred);
 873
 874         return p->part;
 875 }  /* lambda_partition */
 876
 877 /**
 878  * Checks whether a type is a constant.
 879  */
 880 static int is_type_constant(lattice_elem_t type) {
 881         if (is_tarval(type.tv))
 882                 return tarval_is_constant(type.tv);
 883         /* else it is a symconst */
 884         return 1;
 885 }
 886
 887 /**
 888  * Implements split_by().
 889  *
 890  * @param X    the partition to split
 891  * @param env  the environment
 892  */
 893 static void split_by(partition_t *X, environment_t *env) {
 894         partition_t *P = NULL;
 895         int         input;
 896
 897         DB((dbg, LEVEL_2, "WHAT = lambda n.(n.type) on part%d\n", X->nr));
 898         P = split_by_what(X, lambda_type, &P, env);
 899         do {
 900                 partition_t *Y = P;
 901
 902                 P = P->split_next;
 903                 if (Y->n_nodes > 1) {
 904                         lattice_elem_t type = get_partition_type(Y);
 905
 906                         /* we do not want split the TOP or constant partitions */
 907                         if (type.tv != tarval_top && !is_type_constant(type)) {
 908                                 partition_t *Q = NULL;
 909
 910                                 DB((dbg, LEVEL_2, "WHAT = lambda n.(n.opcode) on part%d\n", Y->nr));
 911                                 Q = split_by_what(Y, lambda_opcode, &Q, env);
 912
 913                                 do {
 914                                         partition_t *Z = Q;
 915
 916                                         Q = Q->split_next;
 917                                         if (Z->n_nodes > 1) {
 918                                                 const node_t *first = get_first_node(Z);
 919                                                 int          arity  = get_irn_arity(first->node);
 920                                                 partition_t  *R, *S;
 921
 922                                                 /*
 923                                                  * BEWARE: during splitting by input 2 for instance we might
 924                                                  * create new partitions which are different by input 1, so collect
 925                                                  * them and split further.
 926                                                  */
 927                                                 Z->split_next = NULL;
 928                                                 R             = Z;
 929                                                 S             = NULL;
 930                                                 for (input = arity - 1; input >= -1; --input) {
 931                                                         do {
 932                                                                 partition_t *Z_prime = R;
 933
 934                                                                 R = R->split_next;
 935                                                                 if (Z_prime->n_nodes > 1) {
 936                                                                         env->lambda_input = input;
 937                                                                         DB((dbg, LEVEL_2, "WHAT = lambda n.(n[%d].partition) on part%d\n", input, Z_prime->nr));
 938                                                                         S = split_by_what(Z_prime, lambda_partition, &S, env);
 939                                                                 } else {
 940                                                                         Z_prime->split_next = S;
 941                                                                         S                   = Z_prime;
 942                                                                 }
 943                                                         } while (R != NULL);
 944                                                         R = S;
 945                                                         S = NULL;
 946                                                 }
 947                                         }
 948                                 } while (Q != NULL);
 949                         }
 950                 }
 951         } while (P != NULL);
 952 }  /* split_by */
 953
 954 /**
 955  * (Re-)compute the type for a given node.
 956  *
 957  * @param node  the node
 958  */
 959 static void default_compute(node_t *node) {
 960         int     i;
 961         ir_node *irn = node->node;
 962         node_t  *block = get_irn_node(get_nodes_block(irn));
 963
 964         if (block->type.tv == tarval_unreachable) {
 965                 node->type.tv = tarval_top;
 966                 return;
 967         }
 968
 969         /* if any of the data inputs have type top, the result is type top */
 970         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 971                 ir_node *pred = get_irn_n(irn, i);
 972                 node_t  *p    = get_irn_node(pred);
 973
 974                 if (p->type.tv == tarval_top) {
 975                         node->type.tv = tarval_top;
 976                         return;
 977                 }
 978         }
 979
 980         if (get_irn_mode(node->node) == mode_X)
 981                 node->type.tv = tarval_reachable;
 982         else
 983                 node->type.tv = computed_value(irn);
 984 }  /* default_compute */
 985
 986 /**
 987  * (Re-)compute the type for a Block node.
 988  *
 989  * @param node  the node
 990  */
 991 static void compute_Block(node_t *node) {
 992         int     i;
 993         ir_node *block = node->node;
 994
 995         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i) {
 996                 node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
 997
 998                 if (pred->type.tv == tarval_reachable) {
 999                         /* A block is reachable, if at least of predecessor is reachable. */
1000                         node->type.tv = tarval_reachable;
1001                         return;
1002                 }
1003         }
1004         node->type.tv = tarval_top;
1005 }  /* compute_Block */
1006
1007 /**
1008  * (Re-)compute the type for a Bad node.
1009  *
1010  * @param node  the node
1011  */
1012 static void compute_Bad(node_t *node) {
1013         /* Bad nodes ALWAYS compute Top */
1014         node->type.tv = tarval_top;
1015 }  /* compute_Bad */
1016
1017 /**
1018  * (Re-)compute the type for an Unknown node.
1019  *
1020  * @param node  the node
1021  */
1022 static void compute_Unknown(node_t *node) {
1023         /* While Unknown nodes compute Top, but this is dangerous:
1024          * a if (unknown) would lead to BOTH control flows unreachable.
1025          * While this is correct in the given semantics, it would destroy the Firm
1026          * graph.
1027          * For now, we compute bottom here.
1028          */
1029         node->type.tv = tarval_bottom;
1030 }  /* compute_Unknown */
1031
1032 /**
1033  * (Re-)compute the type for a Jmp node.
1034  *
1035  * @param node  the node
1036  */
1037 static void compute_Jmp(node_t *node) {
1038         node_t *block = get_irn_node(get_nodes_block(node->node));
1039
1040         node->type = block->type;
1041 }  /* compute_Jmp */
1042
1043 /**
1044  * (Re-)compute the type for the End node.
1045  *
1046  * @param node  the node
1047  */
1048 static void compute_End(node_t *node) {
1049         /* the End node is NOT dead of course */
1050         node->type.tv = tarval_reachable;
1051 }
1052
1053 /**
1054  * (Re-)compute the type for a SymConst node.
1055  *
1056  * @param node  the node
1057  */
1058 static void compute_SymConst(node_t *node) {
1059         ir_node *irn = node->node;
1060         node_t  *block = get_irn_node(get_nodes_block(irn));
1061
1062         if (block->type.tv == tarval_unreachable) {
1063                 node->type.tv = tarval_top;
1064                 return;
1065         }
1066         switch (get_SymConst_kind(irn)) {
1067         case symconst_addr_ent:
1068         /* case symconst_addr_name: cannot handle this yet */
1069                 node->type.sym = get_SymConst_symbol(irn);
1070                 break;
1071         default:
1072                 node->type.tv = computed_value(irn);
1073         }
1074 }  /* compute_SymConst */
1075
1076 /**
1077  * (Re-)compute the type for a Phi node.
1078  *
1079  * @param node  the node
1080  */
1081 static void compute_Phi(node_t *node) {
1082         int            i;
1083         ir_node        *phi = node->node;
1084         lattice_elem_t type;
1085
1086         /* if a Phi is in a unreachable block, its type is TOP */
1087         node_t *block = get_irn_node(get_nodes_block(phi));
1088
1089         if (block->type.tv == tarval_unreachable) {
1090                 node->type.tv = tarval_top;
1091                 return;
1092         }
1093
1094         /* Phi implements the Meet operation */
1095         type.tv = tarval_top;
1096         for (i = get_Phi_n_preds(phi) - 1; i >= 0; --i) {
1097                 node_t *pred   = get_irn_node(get_Phi_pred(phi, i));
1098                 node_t *pred_X = get_irn_node(get_Block_cfgpred(block->node, i));
1099
1100                 if (pred_X->type.tv == tarval_unreachable || pred->type.tv == tarval_top) {
1101                         /* ignore TOP inputs: We must check here for unreachable blocks,
1102                            because Firm constants live in the Start Block are NEVER Top.
1103                            Else, a Phi (1,2) will produce Bottom, even if the 2 for instance
1104                            comes from a unreachable input. */
1105                         continue;
1106                 }
1107                 if (pred->type.tv == tarval_bottom) {
1108                         node->type.tv = tarval_bottom;
1109                         return;
1110                 } else if (type.tv == tarval_top) {
1111                         /* first constant found */
1112                         type = pred->type;
1113                 } else if (type.tv != pred->type.tv) {
1114                         /* different constants or tarval_bottom */
1115                         node->type.tv = tarval_bottom;
1116                         return;
1117                 }
1118                 /* else nothing, constants are the same */
1119         }
1120         node->type = type;
1121 }  /* compute_Phi */
1122
1123 /**
1124  * (Re-)compute the type for an Add. Special case: one nodes is a Zero Const.
1125  *
1126  * @param node  the node
1127  */
1128 static void compute_Add(node_t *node) {
1129         ir_node        *sub = node->node;
1130         node_t         *l   = get_irn_node(get_Add_left(sub));
1131         node_t         *r   = get_irn_node(get_Add_right(sub));
1132         lattice_elem_t a    = l->type;
1133         lattice_elem_t b    = r->type;
1134         node_t         *block = get_irn_node(get_nodes_block(sub));
1135         ir_mode        *mode;
1136
1137         if (block->type.tv == tarval_unreachable) {
1138                 node->type.tv = tarval_top;
1139                 return;
1140         }
1141
1142         if (a.tv == tarval_top || b.tv == tarval_top) {
1143                 node->type.tv = tarval_top;
1144         } else if (a.tv == tarval_bottom || b.tv == tarval_bottom) {
1145                 node->type.tv = tarval_bottom;
1146         } else {
1147                 /* x + 0 = 0 + x = x, but beware of floating point +0 + -0, so we
1148                    must call tarval_add() first to handle this case! */
1149                 if (is_tarval(a.tv)) {
1150                         if (is_tarval(b.tv)) {
1151                                 node->type.tv = tarval_add(a.tv, b.tv);
1152                                 return;
1153                         }
1154                         mode = get_tarval_mode(a.tv);
1155                         if (a.tv == get_mode_null(mode)) {
1156                                 node->type = b;
1157                                 return;
1158                         }
1159                 } else if (is_tarval(b.tv)) {
1160                         mode = get_tarval_mode(b.tv);
1161                         if (b.tv == get_mode_null(mode)) {
1162                                 node->type = a;
1163                                 return;
1164                         }
1165                 }
1166                 node->type.tv = tarval_bottom;
1167         }
1168 }  /* compute_Add */
1169
1170 /**
1171  * Returns true if a type is a constant.
1172  */
1173 static int is_con(const lattice_elem_t type) {
1174         return is_entity(type.sym.entity_p) || tarval_is_constant(type.tv);
1175 }
1176
1177 /**
1178  * (Re-)compute the type for a Sub. Special case: both nodes are congruent.
1179  *
1180  * @param node  the node
1181  */
1182 static void compute_Sub(node_t *node) {
1183         ir_node        *sub = node->node;
1184         node_t         *l   = get_irn_node(get_Sub_left(sub));
1185         node_t         *r   = get_irn_node(get_Sub_right(sub));
1186         lattice_elem_t a    = l->type;
1187         lattice_elem_t b    = r->type;
1188         node_t         *block = get_irn_node(get_nodes_block(sub));
1189
1190         if (block->type.tv == tarval_unreachable) {
1191                 node->type.tv = tarval_top;
1192                 return;
1193         }
1194         if (a.tv == tarval_top || b.tv == tarval_top) {
1195                 node->type.tv = tarval_top;
1196         } else if (is_con(a) && is_con(b)) {
1197                 if (is_tarval(a.tv) && is_tarval(b.tv)) {
1198                         node->type.tv = tarval_sub(a.tv, b.tv, get_irn_mode(sub));
1199                 } else if (is_tarval(a.tv) && tarval_is_null(a.tv)) {
1200                         node->type = b;
1201                 } else if (is_tarval(b.tv) && tarval_is_null(b.tv)) {
1202                         node->type = a;
1203                 } else {
1204                         node->type.tv = tarval_bottom;
1205                 }
1206         } else if (r->part == l->part &&
1207                    (!mode_is_float(get_irn_mode(l->node)))) {
1208                 if (node->type.tv == tarval_top) {
1209                         /*
1210                          * BEWARE: a - a is NOT always 0 for floating Point values, as
1211                          * NaN op NaN = NaN, so we must check this here.
1212                          */
1213                         ir_mode *mode = get_irn_mode(sub);
1214                         node->type.tv = get_mode_null(mode);
1215                 } else {
1216                         node->type.tv = tarval_bottom;
1217                 }
1218         } else {
1219                 node->type.tv = tarval_bottom;
1220         }
1221 }  /* compute_Sub */
1222
1223 /**
1224  * (Re-)compute the type for Cmp.
1225  *
1226  * @param node  the node
1227  */
1228 static void compute_Cmp(node_t *node) {
1229         ir_node        *cmp  = node->node;
1230         node_t         *l    = get_irn_node(get_Cmp_left(cmp));
1231         node_t         *r    = get_irn_node(get_Cmp_right(cmp));
1232         lattice_elem_t a     = l->type;
1233         lattice_elem_t b     = r->type;
1234
1235         if (a.tv == tarval_top || b.tv == tarval_top) {
1236                 node->type.tv = tarval_top;
1237         } else if (is_con(a) && is_con(b)) {
1238                 /* both nodes are constants, we can propbably do something */
1239                 node->type.tv = tarval_b_true;
1240         } else if (r->part == l->part) {
1241                 /* both nodes congruent, we can probably do something */
1242                 node->type.tv = tarval_b_true;
1243         } else {
1244                 node->type.tv = tarval_bottom;
1245         }
1246 }  /* compute_Proj_Cmp */
1247
1248 /**
1249  * (Re-)compute the type for a Proj(Cmp).
1250  *
1251  * @param node  the node
1252  * @param cond  the predecessor Cmp node
1253  */
1254 static void compute_Proj_Cmp(node_t *node, ir_node *cmp) {
1255         ir_node        *proj = node->node;
1256         node_t         *l    = get_irn_node(get_Cmp_left(cmp));
1257         node_t         *r    = get_irn_node(get_Cmp_right(cmp));
1258         lattice_elem_t a     = l->type;
1259         lattice_elem_t b     = r->type;
1260         pn_Cmp         pnc   = get_Proj_proj(proj);
1261
1262         if (a.tv == tarval_top || b.tv == tarval_top) {
1263                 node->type.tv = tarval_top;
1264         } else if (is_con(a) && is_con(b)) {
1265                 default_compute(node);
1266         } else if (r->part == l->part &&
1267                    (!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt || pnc == pn_Cmp_Gt)) {
1268                 if (node->type.tv == tarval_top) {
1269                         /*
1270                          * BEWARE: a == a is NOT always True for floating Point values, as
1271                          * NaN != NaN is defined, so we must check this here.
1272                          */
1273                         node->type.tv = new_tarval_from_long(pnc & pn_Cmp_Eq, mode_b);
1274                 } else {
1275                         node->type.tv = tarval_bottom;
1276                 }
1277         } else {
1278                 node->type.tv = tarval_bottom;
1279         }
1280 }  /* compute_Proj_Cmp */
1281
1282 /**
1283  * (Re-)compute the type for a Proj(Cond).
1284  *
1285  * @param node  the node
1286  * @param cond  the predecessor Cond node
1287  */
1288 static void compute_Proj_Cond(node_t *node, ir_node *cond) {
1289         ir_node *proj     = node->node;
1290         long    pnc       = get_Proj_proj(proj);
1291         ir_node *sel      = get_Cond_selector(cond);
1292         node_t  *selector = get_irn_node(sel);
1293
1294         if (get_irn_mode(sel) == mode_b) {
1295                 /* an IF */
1296                 if (pnc == pn_Cond_true) {
1297                         if (selector->type.tv == tarval_b_false) {
1298                                 node->type.tv = tarval_unreachable;
1299                         } else if (selector->type.tv == tarval_b_true) {
1300                                 node->type.tv = tarval_reachable;
1301                         } else if (selector->type.tv == tarval_bottom) {
1302                                 node->type.tv = tarval_reachable;
1303                         } else {
1304                                 assert(selector->type.tv == tarval_top);
1305                                 node->type.tv = tarval_unreachable;
1306                         }
1307                 } else {
1308                         assert(pnc == pn_Cond_false);
1309
1310                         if (selector->type.tv == tarval_b_false) {
1311                                 node->type.tv = tarval_reachable;
1312                         } else if (selector->type.tv == tarval_b_true) {
1313                                 node->type.tv = tarval_unreachable;
1314                         } else if (selector->type.tv == tarval_bottom) {
1315                                 node->type.tv = tarval_reachable;
1316                         } else {
1317                                 assert(selector->type.tv == tarval_top);
1318                                 node->type.tv = tarval_unreachable;
1319                         }
1320                 }
1321         } else {
1322                 /* an SWITCH */
1323                 if (selector->type.tv == tarval_bottom) {
1324                         node->type.tv = tarval_reachable;
1325                 } else if (selector->type.tv == tarval_top) {
1326                         node->type.tv = tarval_unreachable;
1327                 } else {
1328                         long value = get_tarval_long(selector->type.tv);
1329                         if (pnc == get_Cond_defaultProj(cond)) {
1330                                 /* default switch, have to check ALL other cases */
1331                                 int i;
1332
1333                                 for (i = get_irn_n_outs(cond) - 1; i >= 0; --i) {
1334                                         ir_node *succ = get_irn_out(cond, i);
1335
1336                                         if (succ == proj)
1337                                                 continue;
1338                                         if (value == get_Proj_proj(succ)) {
1339                                                 /* we found a match, will NOT take the default case */
1340                                                 node->type.tv = tarval_unreachable;
1341                                                 return;
1342                                         }
1343                                 }
1344                                 /* all cases checked, no match, will take default case */
1345                                 node->type.tv = tarval_reachable;
1346                         } else {
1347                                 /* normal case */
1348                                 node->type.tv = value == pnc ? tarval_reachable : tarval_unreachable;
1349                         }
1350                 }
1351         }
1352 }  /* compute_Proj_Cond */
1353
1354 /**
1355  * (Re-)compute the type for a Proj-Nodes.
1356  *
1357  * @param node  the node
1358  */
1359 static void compute_Proj(node_t *node) {
1360         ir_node *proj = node->node;
1361         ir_mode *mode = get_irn_mode(proj);
1362         node_t  *block = get_irn_node(get_nodes_block(skip_Proj(proj)));
1363         ir_node *pred  = get_Proj_pred(proj);
1364
1365         if (get_Proj_proj(proj) == pn_Start_X_initial_exec && is_Start(pred)) {
1366                 /* The initial_exec node is ALWAYS reachable. */
1367                 node->type.tv = tarval_reachable;
1368                 return;
1369         }
1370
1371         if (block->type.tv == tarval_unreachable) {
1372                 /* a Proj in a unreachable Block stay Top */
1373                 node->type.tv = tarval_top;
1374                 return;
1375         }
1376         if (get_irn_node(pred)->type.tv == tarval_top) {
1377                 /* if the predecessor is Top, its Proj follow */
1378                 node->type.tv = tarval_top;
1379                 return;
1380         }
1381
1382         if (mode == mode_M) {
1383                 /* mode M is always bottom */
1384                 node->type.tv = tarval_bottom;
1385                 return;
1386         }
1387         if (mode != mode_X) {
1388                 if (is_Cmp(pred))
1389                         compute_Proj_Cmp(node, pred);
1390                 else
1391                         default_compute(node);
1392                 return;
1393         }
1394         /* handle mode_X nodes */
1395
1396         switch (get_irn_opcode(pred)) {
1397         case iro_Start:
1398                 /* the Proj_X from the Start is always reachable.
1399                    However this is already handled at the top. */
1400                 node->type.tv = tarval_reachable;
1401                 break;
1402         case iro_Cond:
1403                 compute_Proj_Cond(node, pred);
1404                 break;
1405         default:
1406                 default_compute(node);
1407         }
1408 }  /* compute_Proj */
1409
1410 /**
1411  * (Re-)compute the type for a Confirm-Nodes.
1412  *
1413  * @param node  the node
1414  */
1415 static void compute_Confirm(node_t *node) {
1416         ir_node *confirm = node->node;
1417         node_t  *pred = get_irn_node(get_Confirm_value(confirm));
1418
1419         if (get_Confirm_cmp(confirm) == pn_Cmp_Eq) {
1420                 node_t *bound = get_irn_node(get_Confirm_bound(confirm));
1421
1422                 if (is_con(bound->type)) {
1423                         /* is equal to a constant */
1424                         node->type = bound->type;
1425                         return;
1426                 }
1427         }
1428         /* a Confirm is a copy OR a Const */
1429         node->type = pred->type;
1430 }  /* compute_Confirm */
1431
1432 /**
1433  * (Re-)compute the type for a given node.
1434  *
1435  * @param node  the node
1436  */
1437 static void compute(node_t *node) {
1438         compute_func func = (compute_func)node->node->op->ops.generic;
1439
1440         if (func != NULL)
1441                 func(node);
1442 }  /* compute */
1443
1444 /**
1445  * Propagate constant evaluation.
1446  *
1447  * @param env  the environment
1448  */
1449 static void propagate(environment_t *env) {
1450         partition_t    *X, *Y;
1451         node_t         *x;
1452         lattice_elem_t old_type;
1453         node_t         *fallen;
1454         unsigned       n_fallen;
1455         int            i;
1456
1457         while (env->cprop != NULL) {
1458                 /* remove the first partition X from cprop */
1459                 X           = env->cprop;
1460                 X->on_cprop = 0;
1461                 env->cprop  = X->cprop_next;
1462
1463                 DB((dbg, LEVEL_2, "Propagate type on part%d\n", X->nr));
1464                 fallen   = NULL;
1465                 n_fallen = 0;
1466                 while (! list_empty(&X->cprop)) {
1467                         /* remove the first Node x from X.cprop */
1468                         x = list_entry(X->cprop.next, node_t, cprop_list);
1469                         list_del(&x->cprop_list);
1470                         x->on_cprop = 0;
1471
1472                         /* compute a new type for x */
1473                         old_type = x->type;
1474                         DB((dbg, LEVEL_3, "computing type of %+F\n", x->node));
1475                         compute(x);
1476                         if (x->type.tv != old_type.tv) {
1477                                 verify_type(old_type, x->type);
1478                                 DB((dbg, LEVEL_2, "node %+F has changed type from %+F to %+F\n", x->node, old_type, x->type));
1479
1480                                 if (x->on_fallen == 0) {
1481                                         /* Add x to fallen. Nodes might fall from T -> const -> _|_, so check that they are
1482                                            not already on the list. */
1483                                         x->next      = fallen;
1484                                         x->on_fallen = 1;
1485                                         fallen       = x;
1486                                         ++n_fallen;
1487                                         DB((dbg, LEVEL_2, "Add node %+F to fallen\n", x->node));
1488                                 }
1489                                 for (i = get_irn_n_outs(x->node) - 1; i >= 0; --i) {
1490                                         ir_node *succ = get_irn_out(x->node, i);
1491                                         node_t  *y    = get_irn_node(succ);
1492
1493                                         /* Add y to y.partition.cprop. */
1494                                         add_node_to_cprop(y, env);
1495                                 }
1496                         }
1497                 }
1498
1499                 if (n_fallen > 0 && n_fallen != X->n_nodes) {
1500                         DB((dbg, LEVEL_2, "Splitting part%d by fallen\n", X->nr));
1501                         Y = split(X, fallen, env);
1502                 } else {
1503                         Y = X;
1504                 }
1505                 /* remove the nodes from the fallen list */
1506                 for (x = fallen; x != NULL; x = x->next)
1507                         x->on_fallen = 0;
1508
1509                 if (Y->n_nodes > 1)
1510                         split_by(Y, env);
1511         }
1512 }  /* propagate */
1513
1514 /**
1515  * Get the leader for a given node from its congruence class.
1516  *
1517  * @param irn  the node
1518  */
1519 static ir_node *get_leader(node_t *node) {
1520         partition_t *part = node->part;
1521
1522         if (part->n_nodes > 1) {
1523                 DB((dbg, LEVEL_2, "Found congruence class for %+F\n", node->node));
1524
1525                 return get_first_node(part)->node;
1526         }
1527         return node->node;
1528 }  /* get_leader */
1529
1530 /**
1531  * Return non-zero if the control flow predecessor node pred
1532  * is the only reachable control flow exit of its block.
1533  *
1534  * @param pred  the control flow exit
1535  */
1536 static int can_exchange(ir_node *pred) {
1537         if (is_Start(pred))
1538                 return 0;
1539         else if (is_Jmp(pred))
1540                 return 1;
1541         else if (get_irn_mode(pred) == mode_T) {
1542                 int i, k;
1543
1544                 /* if the predecessor block has more than one
1545                 reachable outputs we cannot remove the block */
1546                 k = 0;
1547                 for (i = get_irn_n_outs(pred) - 1; i >= 0; --i) {
1548                         ir_node *proj = get_irn_out(pred, i);
1549                         node_t  *node;
1550
1551                         /* skip non-control flow Proj's */
1552                         if (get_irn_mode(proj) != mode_X)
1553                                 continue;
1554
1555                         node = get_irn_node(proj);
1556                         if (node->type.tv == tarval_reachable) {
1557                                 if (++k > 1)
1558                                         return 0;
1559                         }
1560                 }
1561                 return 1;
1562         }
1563         return 0;
1564 }
1565
1566 /**
1567  * Block Post-Walker, apply the analysis results on control flow by
1568  * shortening Phi's and Block inputs.
1569  */
1570 static void apply_cf(ir_node *block, void *ctx) {
1571         node_t  *node = get_irn_node(block);
1572         int     i, j, k, n;
1573         ir_node **ins, **in_X;
1574         ir_node *phi, *next;
1575
1576         (void) ctx;
1577         if (block == get_irg_end_block(current_ir_graph) ||
1578             block == get_irg_start_block(current_ir_graph)) {
1579                 /* the EndBlock is always reachable even if the analysis
1580                    finds out the opposite :-) */
1581                 return;
1582         }
1583         if (node->type.tv == tarval_unreachable) {
1584                 /* mark dead blocks */
1585                 set_Block_dead(block);
1586                 return;
1587         }
1588
1589         n = get_Block_n_cfgpreds(block);
1590
1591         if (n == 1) {
1592                 /* only one predecessor combine */
1593                 ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0));
1594
1595                 if (can_exchange(pred))
1596                         exchange(block, get_nodes_block(pred));
1597                 return;
1598         }
1599
1600         NEW_ARR_A(ir_node *, in_X, n);
1601         k = 0;
1602         for (i = 0; i < n; ++i) {
1603                 ir_node *pred = get_Block_cfgpred(block, i);
1604                 node_t  *node = get_irn_node(pred);
1605
1606                 if (node->type.tv == tarval_reachable) {
1607                         in_X[k++] = pred;
1608                 }
1609         }
1610         if (k >= n)
1611                 return;
1612
1613         NEW_ARR_A(ir_node *, ins, n);
1614         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
1615                 node_t *node = get_irn_node(phi);
1616
1617                 next = get_Phi_next(phi);
1618                 if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
1619                         /* this Phi is replaced by a constant */
1620                         tarval  *tv = node->type.tv;
1621                         ir_node *c  = new_r_Const(current_ir_graph, block, get_tarval_mode(tv), tv);
1622
1623                         set_irn_node(c, node);
1624                         node->node = c;
1625                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, c));
1626                         exchange(phi, c);
1627                 } else {
1628                         j = 0;
1629                         for (i = 0; i < n; ++i) {
1630                                 node_t *pred = get_irn_node(get_Block_cfgpred(block, i));
1631
1632                                 if (pred->type.tv == tarval_reachable) {
1633                                         ins[j++] = get_Phi_pred(phi, i);
1634                                 }
1635                         }
1636                         if (j <= 1) {
1637                                 /* this Phi is replaced by a single predecessor */
1638                                 ir_node *s = ins[0];
1639
1640                                 node->node = s;
1641                                 DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", phi, s));
1642                                 exchange(phi, s);
1643                         } else {
1644                                 set_irn_in(phi, j, ins);
1645                         }
1646                 }
1647         }
1648
1649         if (k <= 1) {
1650                 /* this Block has only one live predecessor */
1651                 ir_node *pred = skip_Proj(in_X[0]);
1652
1653                 if (can_exchange(pred))
1654                         exchange(block, get_nodes_block(pred));
1655         } else {
1656                 set_irn_in(block, k, in_X);
1657         }
1658 }
1659
1660 /**
1661  * Post-Walker, apply the analysis results;
1662  */
1663 static void apply_result(ir_node *irn, void *ctx) {
1664         node_t *node = get_irn_node(irn);
1665
1666         (void) ctx;
1667         if (is_Block(irn) || is_End(irn) || is_Bad(irn)) {
1668                 /* blocks already handled, do not touch the End node */
1669         } else {
1670                 node_t *block = get_irn_node(get_nodes_block(irn));
1671
1672                 if (block->type.tv == tarval_unreachable) {
1673                         ir_node *bad = get_irg_bad(current_ir_graph);
1674
1675                         /* here, bad might already have a node, but this can be safely ignored
1676                            as long as bad has at least ONE valid node */
1677                         set_irn_node(bad, node);
1678                         node->node = bad;
1679                         DB((dbg, LEVEL_1, "%+F is unreachable\n", irn));
1680                         exchange(irn, bad);
1681                 }
1682                 else if (node->type.tv == tarval_unreachable) {
1683                         ir_node *bad = get_irg_bad(current_ir_graph);
1684
1685                         /* see comment above */
1686                         set_irn_node(bad, node);
1687                         node->node = bad;
1688                         DB((dbg, LEVEL_1, "%+F is unreachable\n", irn));
1689                         exchange(irn, bad);
1690                 }
1691                 else if (get_irn_mode(irn) == mode_X) {
1692                         if (is_Proj(irn)) {
1693                                 /* leave or Jmp */
1694                                 ir_node *cond = get_Proj_pred(irn);
1695
1696                                 if (is_Cond(cond)) {
1697                                         node_t *sel = get_irn_node(get_Cond_selector(cond));
1698
1699                                         if (is_tarval(sel->type.tv) && tarval_is_constant(sel->type.tv)) {
1700                                                 /* Cond selector is a constant, make a Jmp */
1701                                                 ir_node *jmp = new_r_Jmp(current_ir_graph, block->node);
1702                                                 set_irn_node(jmp, node);
1703                                                 node->node = jmp;
1704                                                 DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, jmp));
1705                                                 exchange(irn, jmp);
1706                                         }
1707                                 }
1708                         }
1709                 } else {
1710                         /* normal data node */
1711                         if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
1712                                 tarval *tv = node->type.tv;
1713
1714                                 if (! is_Const(irn)) {
1715                                         /* can be replaced by a constant */
1716                                         ir_node *c = new_r_Const(current_ir_graph, block->node, get_tarval_mode(tv), tv);
1717                                         set_irn_node(c, node);
1718                                         node->node = c;
1719                                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
1720                                         exchange(irn, c);
1721                                 }
1722                         } else if (is_entity(node->type.sym.entity_p)) {
1723                                 if (! is_SymConst(irn)) {
1724                                         /* can be replaced by a Symconst */
1725                                         ir_node *symc = new_r_SymConst(current_ir_graph, block->node, get_irn_mode(irn), node->type.sym, symconst_addr_ent);
1726                                         set_irn_node(symc, node);
1727                                         node->node = symc;
1728
1729                                         DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, symc));
1730                                         exchange(irn, symc);
1731                                 }
1732                         } else {
1733                                 ir_node *leader = get_leader(node);
1734
1735                                 if (leader != irn) {
1736                                         DB((dbg, LEVEL_1, "%+F from part%d is replaced by %+F\n", irn, node->part->nr, leader));
1737                                         exchange(irn, leader);
1738                                 }
1739                         }
1740                 }
1741         }
1742 }  /* apply_result */
1743
1744 #define SET(code) op_##code->ops.generic = (op_func)compute_##code
1745
1746 /**
1747  * sets the generic functions to compute.
1748  */
1749 static void set_compute_functions(void) {
1750         int i;
1751
1752         /* set the default compute function */
1753         for (i = get_irp_n_opcodes() - 1; i >= 0; --i) {
1754                 ir_op *op = get_irp_opcode(i);
1755                 op->ops.generic = (op_func)default_compute;
1756         }
1757
1758         /* set specific functions */
1759         SET(Block);
1760         SET(Unknown);
1761         SET(Bad);
1762         SET(Jmp);
1763         SET(Phi);
1764         SET(Add);
1765         SET(Sub);
1766         SET(SymConst);
1767         SET(Cmp);
1768         SET(Proj);
1769         SET(Confirm);
1770         SET(End);
1771 }  /* set_compute_functions */
1772
1773 static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
1774         ir_node *irn = local != NULL ? local : n;
1775         node_t *node = get_irn_node(irn);
1776
1777         ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
1778         return 1;
1779 }
1780
1781 void combo(ir_graph *irg) {
1782         environment_t env;
1783         ir_node       *initial_X;
1784         node_t        *start;
1785         ir_graph      *rem = current_ir_graph;
1786
1787         current_ir_graph = irg;
1788
1789         /* register a debug mask */
1790         FIRM_DBG_REGISTER(dbg, "firm.opt.combo");
1791         //firm_dbg_set_mask(dbg, SET_LEVEL_3);
1792
1793         DB((dbg, LEVEL_1, "Doing COMBO for %+F\n", irg));
1794
1795         obstack_init(&env.obst);
1796         env.worklist       = NULL;
1797         env.cprop          = NULL;
1798         env.touched        = NULL;
1799         env.initial        = NULL;
1800 #ifdef DEBUG_libfirm
1801         env.dbg_list       = NULL;
1802 #endif
1803         env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
1804         env.type2id_map    = pmap_create();
1805         env.end_idx        = get_opt_global_cse() ? 0 : -1;
1806         env.lambda_input   = 0;
1807
1808         assure_irg_outs(irg);
1809
1810         /* we have our own value_of function */
1811         set_value_of_func(get_node_tarval);
1812
1813         set_compute_functions();
1814         DEBUG_ONLY(part_nr = 0);
1815
1816         /* create the initial partition and place it on the work list */
1817         env.initial = new_partition(&env);
1818         add_to_worklist(env.initial, &env);
1819         irg_walk_graph(irg, init_block_phis, create_initial_partitions, &env);
1820
1821         /* Place the START Node's partition on cprop.
1822            Place the START Node on its local worklist. */
1823         initial_X = get_irg_initial_exec(irg);
1824         start     = get_irn_node(initial_X);
1825         add_node_to_cprop(start, &env);
1826
1827         do {
1828                 propagate(&env);
1829                 if (env.worklist != NULL)
1830                         cause_splits(&env);
1831         } while (env.cprop != NULL || env.worklist != NULL);
1832
1833         dump_all_partitions(&env);
1834
1835 #if 0
1836         set_dump_node_vcgattr_hook(dump_partition_hook);
1837         dump_ir_block_graph(irg, "-partition");
1838         set_dump_node_vcgattr_hook(NULL);
1839 #else
1840         (void)dump_partition_hook;
1841 #endif
1842
1843         /* apply the result */
1844         irg_block_walk_graph(irg, NULL, apply_cf, &env);
1845         irg_walk_graph(irg, NULL, apply_result, &env);
1846
1847         pmap_destroy(env.type2id_map);
1848         del_set(env.opcode2id_map);
1849         obstack_free(&env.obst, NULL);
1850
1851         /* restore value_of() default behavior */
1852         set_value_of_func(NULL);
1853         current_ir_graph = rem;
1854 }  /* combo */