Reverted changes from 25529
[libfirm] / ir / opt / combo.c
index 20355b8..af5bc66 100644 (file)
@@ -63,7 +63,6 @@
 #include <assert.h>
 
 #include "iroptimize.h"
-#include "archop.h"
 #include "irflag.h"
 #include "ircons.h"
 #include "list.h"
@@ -81,6 +80,7 @@
 #include "debug.h"
 #include "array_t.h"
 #include "error.h"
+#include "irnodeset.h"
 
 #include "tv_t.h"
 
@@ -111,6 +111,10 @@ struct opcode_key_t {
        union {
                long      proj;   /**< For Proj nodes, its proj number */
                ir_entity *ent;   /**< For Sel Nodes, its entity */
+               int       intVal; /**< For Conv/Div Nodes: strict/remainderless */
+               unsigned  uintVal;/**< for Builtin: the kind */
+               ir_node   *block; /**< for Block: itself */
+               void      *ptr;   /**< generic pointer for hash/cmp */
        } u;
 };
 
@@ -193,6 +197,7 @@ typedef struct environment_t {
        partition_t     *initial;       /**< The initial partition. */
        set             *opcode2id_map; /**< The opcodeMode->id map. */
        pmap            *type2id_map;   /**< The type->id map. */
+       ir_node         **kept_memory;  /**< Array of memory nodes that must be kept. */
        int             end_idx;        /**< -1 for local and 0 for global congruences. */
        int             lambda_input;   /**< Captured argument for lambda_partition(). */
        unsigned        modified:1;     /**< Set, if the graph was modified. */
@@ -208,8 +213,8 @@ typedef struct environment_t {
 /** Type of the what function. */
 typedef void *(*what_func)(const node_t *node, environment_t *env);
 
-#define get_irn_node(follower)         ((node_t *)get_irn_link(follower))
-#define set_irn_node(follower, node)   set_irn_link(follower, node)
+#define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
+#define set_irn_node(irn, node)   set_irn_link(irn, node)
 
 /* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
 #undef tarval_unreachable
@@ -279,12 +284,27 @@ static void check_opcode(const partition_t *Z) {
                        case iro_Sel:
                                key.u.ent = get_Sel_entity(irn);
                                break;
+                       case iro_Conv:
+                               key.u.intVal = get_Conv_strict(irn);
+                               break;
+                       case iro_Div:
+                               key.u.intVal = is_Div_remainderless(irn);
+                               break;
+                       case iro_Block:
+                               key.u.block = irn;
+                               break;
+                       case iro_Load:
+                               key.mode = get_Load_mode(irn);
+                               break;
+                       case iro_Builtin:
+                               key.u.intVal = get_Builtin_kind(irn);
+                               break;
                        default:
                                break;
                        }
                        first = 0;
                } else {
-                       assert(key.code  == get_irn_opcode(irn));
+                       assert((unsigned)key.code  == get_irn_opcode(irn));
                        assert(key.mode  == get_irn_mode(irn));
                        assert(key.arity == get_irn_arity(irn));
 
@@ -295,6 +315,21 @@ static void check_opcode(const partition_t *Z) {
                        case iro_Sel:
                                assert(key.u.ent == get_Sel_entity(irn));
                                break;
+                       case iro_Conv:
+                               assert(key.u.intVal == get_Conv_strict(irn));
+                               break;
+                       case iro_Div:
+                               assert(key.u.intVal == is_Div_remainderless(irn));
+                               break;
+                       case iro_Block:
+                               assert(key.u.block == irn);
+                               break;
+                       case iro_Load:
+                               assert(key.mode == get_Load_mode(irn));
+                               break;
+                       case iro_Builtin:
+                               assert(key.u.intVal == (int) get_Builtin_kind(irn));
+                               break;
                        default:
                                break;
                        }
@@ -536,7 +571,7 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
  * @return a hash value for the given opcode map entry
  */
 static unsigned opcode_hash(const opcode_key_t *entry) {
-       return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ent) + entry->arity;
+       return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ptr) + entry->arity;
 }  /* opcode_hash */
 
 /**
@@ -549,7 +584,9 @@ static int cmp_opcode(const void *elt, const void *key, size_t size) {
        (void) size;
        return o1->code != o2->code || o1->mode != o2->mode ||
               o1->arity != o2->arity ||
-              o1->u.proj != o2->u.proj || o1->u.ent != o2->u.ent;
+              o1->u.proj != o2->u.proj ||
+              o1->u.intVal != o2->u.intVal || /* this already checks uIntVal */
+              o1->u.ptr != o2->u.ptr;
 }  /* cmp_opcode */
 
 /**
@@ -1010,10 +1047,6 @@ static int is_real_follower(const ir_node *irn, int input) {
                if (is_tarval(pred->type.tv) && tarval_is_all_one(pred->type.tv))
                        return 0;
                break;
-       case iro_Min:
-       case iro_Max:
-               /* all inputs are followers */
-               return 1;
        default:
                assert(!"opcode not implemented yet");
                break;
@@ -1636,6 +1669,27 @@ static void *lambda_opcode(const node_t *node, environment_t *env) {
        case iro_Sel:
                key.u.ent = get_Sel_entity(irn);
                break;
+       case iro_Conv:
+               key.u.intVal = get_Conv_strict(irn);
+               break;
+       case iro_Div:
+               key.u.intVal = is_Div_remainderless(irn);
+               break;
+       case iro_Block:
+               /*
+                * Some ugliness here: Two Blocks having the same
+                * IJmp predecessor would be congruent, which of course is wrong.
+                * We fix it by never letting blocks be congruent
+                * which cannot be detected by combo either.
+                */
+               key.u.block = irn;
+               break;
+       case iro_Load:
+               key.mode = get_Load_mode(irn);
+               break;
+       case iro_Builtin:
+               key.u.intVal = get_Builtin_kind(irn);
+               break;
        default:
                break;
        }
@@ -1669,7 +1723,6 @@ static void *lambda_partition(const node_t *node, environment_t *env) {
 
        pred = i == -1 ? get_irn_n(skipped, i) : get_irn_n(node->node, i);
        p    = get_irn_node(pred);
-
        return p->part;
 }  /* lambda_partition */
 
@@ -1834,12 +1887,6 @@ static void split_by(partition_t *X, environment_t *env) {
 static void default_compute(node_t *node) {
        int     i;
        ir_node *irn = node->node;
-       node_t  *block = get_irn_node(get_nodes_block(irn));
-
-       if (block->type.tv == tarval_unreachable) {
-               node->type.tv = tarval_top;
-               return;
-       }
 
        /* if any of the data inputs have type top, the result is type top */
        for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
@@ -1867,8 +1914,8 @@ static void compute_Block(node_t *node) {
        int     i;
        ir_node *block = node->node;
 
-       if (block == get_irg_start_block(current_ir_graph)) {
-               /* start block is always reachable */
+       if (block == get_irg_start_block(current_ir_graph) || has_Block_label(block)) {
+               /* start block and labelled blocks are always reachable */
                node->type.tv = tarval_reachable;
                return;
        }
@@ -2329,7 +2376,7 @@ static void compute_Proj_Cond(node_t *node, ir_node *cond) {
                        node->type.tv = tarval_reachable;
                } else if (selector->type.tv == tarval_top) {
                        if (tarval_UNKNOWN == tarval_top &&
-                           pnc == get_Cond_defaultProj(cond)) {
+                           pnc == get_Cond_default_proj(cond)) {
                                /* a switch based of Top is always "default" */
                                node->type.tv = tarval_reachable;
                        } else {
@@ -2337,7 +2384,7 @@ static void compute_Proj_Cond(node_t *node, ir_node *cond) {
                        }
                } else {
                        long value = get_tarval_long(selector->type.tv);
-                       if (pnc == get_Cond_defaultProj(cond)) {
+                       if (pnc == get_Cond_default_proj(cond)) {
                                /* default switch, have to check ALL other cases */
                                int i;
 
@@ -2434,94 +2481,6 @@ static void compute_Confirm(node_t *node) {
        node->type = pred->type;
 }  /* compute_Confirm */
 
-/**
- * (Re-)compute the type for a Max.
- *
- * @param node  the node
- */
-static void compute_Max(node_t *node) {
-       ir_node        *op = node->node;
-       node_t         *l  = get_irn_node(get_binop_left(op));
-       node_t         *r  = get_irn_node(get_binop_right(op));
-       lattice_elem_t a   = l->type;
-       lattice_elem_t b   = r->type;
-
-       if (a.tv == tarval_top || b.tv == tarval_top) {
-               node->type.tv = tarval_top;
-       } else if (is_con(a) && is_con(b)) {
-               /* both nodes are constants, we can probably do something */
-               if (a.tv == b.tv) {
-                       /* this case handles SymConsts as well */
-                       node->type = a;
-               } else {
-                       ir_mode *mode   = get_irn_mode(op);
-                       tarval  *tv_min = get_mode_min(mode);
-
-                       if (a.tv == tv_min)
-                               node->type = b;
-                       else if (b.tv == tv_min)
-                               node->type = a;
-                       else if (is_tarval(a.tv) && is_tarval(b.tv)) {
-                               if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
-                                       node->type.tv = a.tv;
-                               else
-                                       node->type.tv = b.tv;
-                       } else {
-                               node->type.tv = tarval_bad;
-                       }
-               }
-       } else if (r->part == l->part) {
-               /* both nodes congruent, we can probably do something */
-               node->type = a;
-       } else {
-               node->type.tv = tarval_bottom;
-       }
-}  /* compute_Max */
-
-/**
- * (Re-)compute the type for a Min.
- *
- * @param node  the node
- */
-static void compute_Min(node_t *node) {
-       ir_node        *op = node->node;
-       node_t         *l  = get_irn_node(get_binop_left(op));
-       node_t         *r  = get_irn_node(get_binop_right(op));
-       lattice_elem_t a   = l->type;
-       lattice_elem_t b   = r->type;
-
-       if (a.tv == tarval_top || b.tv == tarval_top) {
-               node->type.tv = tarval_top;
-       } else if (is_con(a) && is_con(b)) {
-               /* both nodes are constants, we can probably do something */
-               if (a.tv == b.tv) {
-                       /* this case handles SymConsts as well */
-                       node->type = a;
-               } else {
-                       ir_mode *mode   = get_irn_mode(op);
-                       tarval  *tv_max = get_mode_max(mode);
-
-                       if (a.tv == tv_max)
-                               node->type = b;
-                       else if (b.tv == tv_max)
-                               node->type = a;
-                       else if (is_tarval(a.tv) && is_tarval(b.tv)) {
-                               if (tarval_cmp(a.tv, b.tv) & pn_Cmp_Gt)
-                                       node->type.tv = a.tv;
-                               else
-                                       node->type.tv = b.tv;
-                       } else {
-                               node->type.tv = tarval_bad;
-                       }
-               }
-       } else if (r->part == l->part) {
-               /* both nodes congruent, we can probably do something */
-               node->type = a;
-       } else {
-               node->type.tv = tarval_bottom;
-       }
-}  /* compute_Min */
-
 /**
  * (Re-)compute the type for a given node.
  *
@@ -2733,54 +2692,6 @@ static node_t *identity_Mux(node_t *node) {
        return node;
 }  /* identity_Mux */
 
-/**
- * Calculates the Identity for Min nodes.
- */
-static node_t *identity_Min(node_t *node) {
-       ir_node *op   = node->node;
-       node_t  *a    = get_irn_node(get_binop_left(op));
-       node_t  *b    = get_irn_node(get_binop_right(op));
-       ir_mode *mode = get_irn_mode(op);
-       tarval  *tv_max;
-
-       if (a->part == b->part) {
-               /* leader of multiple predecessors */
-               return a;
-       }
-
-       /* works even with NaN */
-       tv_max = get_mode_max(mode);
-       if (a->type.tv == tv_max)
-               return b;
-       if (b->type.tv == tv_max)
-               return a;
-       return node;
-}  /* identity_Min */
-
-/**
- * Calculates the Identity for Max nodes.
- */
-static node_t *identity_Max(node_t *node) {
-       ir_node *op   = node->node;
-       node_t  *a    = get_irn_node(get_binop_left(op));
-       node_t  *b    = get_irn_node(get_binop_right(op));
-       ir_mode *mode = get_irn_mode(op);
-       tarval  *tv_min;
-
-       if (a->part == b->part) {
-               /* leader of multiple predecessors */
-               return a;
-       }
-
-       /* works even with NaN */
-       tv_min = get_mode_min(mode);
-       if (a->type.tv == tv_min)
-               return b;
-       if (b->type.tv == tv_min)
-               return a;
-       return node;
-}  /* identity_Max */
-
 /**
  * Calculates the Identity for nodes.
  */
@@ -2809,10 +2720,6 @@ static node_t *identity(node_t *node) {
                return identity_Confirm(node);
        case iro_Mux:
                return identity_Mux(node);
-       case iro_Min:
-               return identity_Min(node);
-       case iro_Max:
-               return identity_Max(node);
        default:
                return node;
        }
@@ -3043,10 +2950,11 @@ static int only_one_reachable_proj(ir_node *n) {
  * Return non-zero if the control flow predecessor node pred
  * is the only reachable control flow exit of its block.
  *
- * @param pred  the control flow exit
+ * @param pred   the control flow exit
+ * @param block  the destination block
  */
-static int can_exchange(ir_node *pred) {
-       if (is_Start(pred))
+static int can_exchange(ir_node *pred, ir_node *block) {
+       if (is_Start(pred) || has_Block_label(block))
                return 0;
        else if (is_Jmp(pred))
                return 1;
@@ -3112,7 +3020,7 @@ static void apply_cf(ir_node *block, void *ctx) {
                /* only one predecessor combine */
                ir_node *pred = skip_Proj(get_Block_cfgpred(block, 0));
 
-               if (can_exchange(pred)) {
+               if (can_exchange(pred, block)) {
                        ir_node *new_block = get_nodes_block(pred);
                        DB((dbg, LEVEL_1, "Fuse %+F with %+F\n", block, new_block));
                        DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
@@ -3163,7 +3071,7 @@ static void apply_cf(ir_node *block, void *ctx) {
                if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) {
                        /* this Phi is replaced by a constant */
                        tarval  *tv = node->type.tv;
-                       ir_node *c  = new_r_Const(current_ir_graph, block, get_tarval_mode(tv), tv);
+                       ir_node *c  = new_Const(tv);
 
                        set_irn_node(c, node);
                        node->node = c;
@@ -3203,7 +3111,7 @@ static void apply_cf(ir_node *block, void *ctx) {
                /* this Block has only one live predecessor */
                ir_node *pred = skip_Proj(in_X[0]);
 
-               if (can_exchange(pred)) {
+               if (can_exchange(pred, block)) {
                        ir_node *new_block = get_nodes_block(pred);
                        DBG_OPT_COMBO(block, new_block, FS_OPT_COMBO_CF);
                        exchange(block, new_block);
@@ -3225,7 +3133,7 @@ static void apply_cf(ir_node *block, void *ctx) {
 static void exchange_leader(ir_node *irn, ir_node *leader) {
        ir_mode *mode = get_irn_mode(irn);
        if (mode != get_irn_mode(leader)) {
-               /* The conv is a no-op, so we are fre to place in
+               /* The conv is a no-op, so we are free to place it
                 * either in the block of the leader OR in irn's block.
                 * Probably placing it into leaders block might reduce
                 * the number of Conv due to CSE. */
@@ -3235,7 +3143,60 @@ static void exchange_leader(ir_node *irn, ir_node *leader) {
                leader = new_rd_Conv(dbg, current_ir_graph, block, leader, mode);
        }
        exchange(irn, leader);
-}
+}  /* exchange_leader */
+
+/**
+ * Check, if all users of a mode_M node are dead. Use
+ * the Def-Use edges for this purpose, as they still
+ * reflect the situation.
+ */
+static int all_users_are_dead(const ir_node *irn) {
+       int i, n = get_irn_n_outs(irn);
+
+       for (i = 1; i <= n; ++i) {
+               const ir_node *succ  = irn->out[i].use;
+               const node_t  *block = get_irn_node(get_nodes_block(succ));
+               const node_t  *node;
+
+               if (block->type.tv == tarval_unreachable) {
+                       /* block is unreachable */
+                       continue;
+               }
+               node = get_irn_node(succ);
+               if (node->type.tv != tarval_top) {
+                       /* found a reachable user */
+                       return 0;
+               }
+       }
+       /* all users are unreachable */
+       return 1;
+}  /* all_user_are_dead */
+
+/**
+ * Walker: Find reachable mode_M nodes that have only
+ * unreachable users. These nodes must be kept later.
+ */
+static void find_kept_memory(ir_node *irn, void *ctx) {
+       environment_t *env = ctx;
+       node_t        *node, *block;
+
+       if (get_irn_mode(irn) != mode_M)
+               return;
+
+       block = get_irn_node(get_nodes_block(irn));
+       if (block->type.tv == tarval_unreachable)
+               return;
+
+       node = get_irn_node(irn);
+       if (node->type.tv == tarval_top)
+               return;
+
+       /* ok, we found a live memory node. */
+       if (all_users_are_dead(irn)) {
+               DB((dbg, LEVEL_1, "%+F must be kept\n", irn));
+               ARR_APP1(ir_node *, env->kept_memory, irn);
+       }
+}  /* find_kept_memory */
 
 /**
  * Post-Walker, apply the analysis results;
@@ -3247,7 +3208,7 @@ static void apply_result(ir_node *irn, void *ctx) {
        if (is_Block(irn) || is_End(irn) || is_Bad(irn)) {
                /* blocks already handled, do not touch the End node */
        } else {
-               node_t  *block = get_irn_node(get_nodes_block(irn));
+               node_t *block = get_irn_node(get_nodes_block(irn));
 
                if (block->type.tv == tarval_unreachable) {
                        ir_node *bad = get_irg_bad(current_ir_graph);
@@ -3333,7 +3294,7 @@ static void apply_result(ir_node *irn, void *ctx) {
                                 */
                                if (! is_Const(irn) && get_irn_mode(irn) != mode_T) {
                                        /* can be replaced by a constant */
-                                       ir_node *c = new_r_Const(current_ir_graph, block->node, get_tarval_mode(tv), tv);
+                                       ir_node *c = new_Const(tv);
                                        set_irn_node(c, node);
                                        node->node = c;
                                        DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c));
@@ -3449,19 +3410,38 @@ static void set_compute_functions(void) {
        SET(Return);
        SET(End);
        SET(Call);
+}  /* set_compute_functions */
 
-       if (op_Max != NULL)
-               SET(Max);
-       if (op_Min != NULL)
-               SET(Min);
+/**
+ * Add memory keeps.
+ */
+static void add_memory_keeps(ir_node **kept_memory, int len) {
+       ir_node      *end = get_irg_end(current_ir_graph);
+       int          i;
+       ir_nodeset_t set;
 
-}  /* set_compute_functions */
+       ir_nodeset_init(&set);
+
+       /* check, if those nodes are already kept */
+       for (i = get_End_n_keepalives(end) - 1; i >= 0; --i)
+               ir_nodeset_insert(&set, get_End_keepalive(end, i));
+
+       for (i = len - 1; i >= 0; --i) {
+               ir_node *ka = kept_memory[i];
+
+               if (! ir_nodeset_contains(&set, ka)) {
+                       add_End_keepalive(end, ka);
+               }
+       }
+       ir_nodeset_destroy(&set);
+}  /* add_memory_keeps */
 
 void combo(ir_graph *irg) {
        environment_t env;
        ir_node       *initial_bl;
        node_t        *start;
        ir_graph      *rem = current_ir_graph;
+       int           len;
 
        current_ir_graph = irg;
 
@@ -3480,6 +3460,7 @@ void combo(ir_graph *irg) {
 #endif
        env.opcode2id_map  = new_set(cmp_opcode, iro_Last * 4);
        env.type2id_map    = pmap_create();
+       env.kept_memory    = NEW_ARR_F(ir_node *, 0);
        env.end_idx        = get_opt_global_cse() ? 0 : -1;
        env.lambda_input   = 0;
        env.modified       = 0;
@@ -3497,7 +3478,7 @@ void combo(ir_graph *irg) {
        set_compute_functions();
        DEBUG_ONLY(part_nr = 0);
 
-       ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
+       ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
 
        if (env.opt_unknown)
                tarval_UNKNOWN = tarval_top;
@@ -3535,6 +3516,11 @@ void combo(ir_graph *irg) {
 #endif
 
        /* apply the result */
+
+       /* check, which nodes must be kept */
+       irg_walk_graph(irg, NULL, find_kept_memory, &env);
+
+       /* kill unreachable control flow */
        irg_block_walk_graph(irg, NULL, apply_cf, &env);
        /* Kill keep-alives of dead blocks: this speeds up apply_result()
         * and fixes assertion because dead cf to dead blocks is NOT removed by
@@ -3542,6 +3528,10 @@ void combo(ir_graph *irg) {
        apply_end(get_irg_end(irg), &env);
        irg_walk_graph(irg, NULL, apply_result, &env);
 
+       len = ARR_LEN(env.kept_memory);
+       if (len > 0)
+               add_memory_keeps(env.kept_memory, len);
+
        if (env.unopt_cf) {
                DB((dbg, LEVEL_1, "Unoptimized Control Flow left"));
        }
@@ -3552,13 +3542,15 @@ void combo(ir_graph *irg) {
                set_irg_extblk_inconsistent(irg);
                set_irg_doms_inconsistent(irg);
                set_irg_loopinfo_inconsistent(irg);
+               set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
        }
 
-       ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
+       ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
 
        /* remove the partition hook */
        DEBUG_ONLY(set_dump_node_vcgattr_hook(NULL));
 
+       DEL_ARR_F(env.kept_memory);
        pmap_destroy(env.type2id_map);
        del_set(env.opcode2id_map);
        obstack_free(&env.obst, NULL);