X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcombo.c;h=f6084da05e6b074a7a733d7dda2984fcda30132b;hb=34e3b8d50bce639e760da7233524a4db85c80290;hp=73c54fd2eede2b647b23cad32fbe46b1eeff6307;hpb=6191bc0fe9dc62446b0e0c15e9179b13161dc63d;p=libfirm diff --git a/ir/opt/combo.c b/ir/opt/combo.c index 73c54fd2e..f6084da05 100644 --- a/ir/opt/combo.c +++ b/ir/opt/combo.c @@ -1,36 +1,21 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. - * * This file is part of libFirm. - * - * This file may be distributed and/or modified under the terms of the - * GNU General Public License version 2 as published by the Free Software - * Foundation and appearing in the file LICENSE.GPL included in the - * packaging of this file. - * - * Licensees holding valid libFirm Professional Edition licenses may use - * this file in accordance with the libFirm Commercial License. - * Agreement provided with the Software. - * - * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE - * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE. + * Copyright (C) 2012 University of Karlsruhe. */ /** * @file * @brief Cliff Click's Combined Analysis/Optimization * @author Michael Beck - * @version $Id$ * * This is a slightly enhanced version of Cliff Clicks combo algorithm * - support for commutative nodes is added, Add(a,b) and Add(b,a) ARE congruent * - supports all Firm direct (by a data edge) identities except Mux * (Mux can be a 2-input or 1-input identity, only 2-input is implemented yet) * - supports Confirm nodes (handle them like Copies but do NOT remove them) - * - let Cmp nodes calculate Top like all othe data nodes: this would let + * - let Cmp nodes calculate Top like all other data nodes: this would let * Mux nodes to calculate Unknown instead of taking the true result - * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reavaluated + * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reevaluated * IFF the predecessor changed its type. Because nodes are initialized with Top * this never happens, let all Proj(Cond) be unreachable. * We avoid this condition by the same way we work around Phi: whenever a Block @@ -83,6 +68,8 @@ #include "irnodeset.h" #include "irpass.h" #include "tv_t.h" +#include "irtools.h" +#include "firmstat_t.h" #include "irprintf.h" #include "irdump.h" @@ -105,17 +92,7 @@ typedef void (*compute_func)(node_t *node); * An opcode map key. */ struct opcode_key_t { - ir_opcode code; /**< The Firm opcode. */ - ir_mode *mode; /**< The mode of all nodes in the partition. */ - int arity; /**< The arity of this opcode (needed for Phi etc. */ - 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; + ir_node *irn; /**< An IR node representing this opcode. */ }; /** @@ -138,7 +115,7 @@ typedef struct listmap_t { * have to use this union. */ typedef union { - tarval *tv; + ir_tarval *tv; symconst_symbol sym; } lattice_elem_t; @@ -154,8 +131,8 @@ struct node_t { node_t *race_next; /**< Next node on race list. */ lattice_elem_t type; /**< The associated lattice element "type". */ int max_user_input; /**< Maximum input number of Def-Use edges. */ - int next_edge; /**< Index of the next Def-Use edge to use. */ - int n_followers; /**< Number of Follower in the outs set. */ + unsigned next_edge; /**< Index of the next Def-Use edge to use. */ + unsigned n_followers; /**< Number of Follower in the outs set. */ unsigned on_touched:1; /**< Set, if this node is on the partition.touched set. */ unsigned on_cprop:1; /**< Set, if this node is on the partition.cprop list. */ unsigned on_fallen:1; /**< Set, if this node is on the fallen list. */ @@ -227,21 +204,56 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg;) DEBUG_ONLY(static const char *what_reason;) /** Next partition number. */ -DEBUG_ONLY(static unsigned part_nr = 0); +DEBUG_ONLY(static unsigned part_nr = 0;) /** The tarval returned by Unknown nodes: set to either tarval_bad OR tarval_top. */ -static tarval *tarval_UNKNOWN; +static ir_tarval *tarval_UNKNOWN; /* forward */ static node_t *identity(node_t *node); +/** + * Compare two opcode representatives. + */ +static int cmp_irn_opcode(const ir_node *a, const ir_node *b) +{ + int arity; + + if ((get_irn_op(a) != get_irn_op(b)) || + (get_irn_mode(a) != get_irn_mode(b))) + return 1; + + /* compare if a's in and b's in are of equal length */ + arity = get_irn_arity(a); + if (arity != get_irn_arity(b)) + return 1; + + if (is_Block(a)) { + /* + * 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. + */ + return 1; + } + + /* + * here, we already know that the nodes are identical except their + * attributes + */ + if (a->op->ops.node_cmp_attr) + return a->op->ops.node_cmp_attr(a, b); + + return 0; +} + #ifdef CHECK_PARTITIONS /** * Check a partition. */ static void check_partition(const partition_t *T) { - node_t *node; unsigned n = 0; list_for_each_entry(node_t, node, &T->Leader, node_list) { @@ -257,92 +269,30 @@ static void check_partition(const partition_t *T) assert(node->flagged == 0); assert(node->part == T); } -} /* check_partition */ +} /** * check that all leader nodes in the partition have the same opcode. */ static void check_opcode(const partition_t *Z) { - node_t *node; - opcode_key_t key; - int first = 1; + const ir_node *repr = NULL; list_for_each_entry(node_t, node, &Z->Leader, node_list) { ir_node *irn = node->node; - if (first) { - key.code = get_irn_opcode(irn); - key.mode = get_irn_mode(irn); - key.arity = get_irn_arity(irn); - key.u.proj = 0; - key.u.ent = NULL; - - switch (get_irn_opcode(irn)) { - case iro_Proj: - key.u.proj = get_Proj_proj(irn); - break; - 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 = get_Div_no_remainder(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; + if (repr == NULL) { + repr = irn; } else { - assert((unsigned)key.code == get_irn_opcode(irn)); - assert(key.mode == get_irn_mode(irn)); - assert(key.arity == get_irn_arity(irn)); - - switch (get_irn_opcode(irn)) { - case iro_Proj: - assert(key.u.proj == get_Proj_proj(irn)); - break; - 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 == get_Div_no_remainder(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; - } + assert(cmp_irn_opcode(repr, irn) == 0); } } -} /* check_opcode */ +} static void check_all_partitions(environment_t *env) { #ifdef DEBUG_libfirm partition_t *P; - node_t *node; for (P = env->dbg_list; P != NULL; P = P->dbg_next) { check_partition(P); @@ -377,7 +327,7 @@ static void do_check_list(const node_t *list, int ofs, const partition_t *Z) (void) ofs; (void) Z; #endif -} /* ido_check_list */ +} /** * Check a local list. @@ -385,7 +335,7 @@ static void do_check_list(const node_t *list, int ofs, const partition_t *Z) static void check_list(const node_t *list, const partition_t *Z) { do_check_list(list, offsetof(node_t, next), Z); -} /* check_list */ +} #else #define check_partition(T) @@ -401,7 +351,6 @@ static inline lattice_elem_t get_partition_type(const partition_t *X); */ static void dump_partition(const char *msg, const partition_t *part) { - const node_t *node; int first = 1; lattice_elem_t type = get_partition_type(part); @@ -421,7 +370,7 @@ static void dump_partition(const char *msg, const partition_t *part) } } DB((dbg, LEVEL_2, "\n}\n")); -} /* dump_partition */ +} /** * Dumps a list. @@ -441,7 +390,7 @@ static void do_dump_list(const char *msg, const node_t *node, int ofs) DB((dbg, LEVEL_3, "\n}\n")); #undef GET_LINK -} /* do_dump_list */ +} /** * Dumps a race list. @@ -449,7 +398,7 @@ static void do_dump_list(const char *msg, const node_t *node, int ofs) static void dump_race_list(const char *msg, const node_t *list) { do_dump_list(msg, list, offsetof(node_t, race_next)); -} /* dump_race_list */ +} /** * Dumps a local list. @@ -457,7 +406,7 @@ static void dump_race_list(const char *msg, const node_t *list) static void dump_list(const char *msg, const node_t *list) { do_dump_list(msg, list, offsetof(node_t, next)); -} /* dump_list */ +} /** * Dump all partitions. @@ -469,7 +418,7 @@ static void dump_all_partitions(const environment_t *env) DB((dbg, LEVEL_2, "All partitions\n===============\n")); for (P = env->dbg_list; P != NULL; P = P->dbg_next) dump_partition("", P); -} /* dump_all_partitions */ +} /** * Sump a split list. @@ -477,24 +426,27 @@ static void dump_all_partitions(const environment_t *env) static void dump_split_list(const partition_t *list) { const partition_t *p; + char split = ' '; DB((dbg, LEVEL_2, "Split by %s produced = {\n", what_reason)); - for (p = list; p != NULL; p = p->split_next) - DB((dbg, LEVEL_2, "part%u, ", p->nr)); + for (p = list; p != NULL; p = p->split_next) { + DB((dbg, LEVEL_2, "%c part%u", split, p->nr)); + split = ','; + } DB((dbg, LEVEL_2, "\n}\n")); -} /* dump_split_list */ +} /** * Dump partition and type for a node. */ -static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) +static int dump_partition_hook(FILE *F, const ir_node *n, const ir_node *local) { - ir_node *irn = local != NULL ? local : n; + const ir_node *irn = local != NULL ? local : n; node_t *node = get_irn_node(irn); ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type); return 1; -} /* dump_partition_hook */ +} #else #define dump_partition(msg, part) @@ -522,8 +474,8 @@ static void verify_type(const lattice_elem_t old_type, node_t *node) /* bottom reached */ return; } - panic("combo: wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node); -} /* verify_type */ + panic("wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node); +} #else #define verify_type(old_type, node) @@ -534,12 +486,12 @@ static void verify_type(const lattice_elem_t old_type, node_t *node) */ static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) { - const listmap_entry_t *e1 = elt; - const listmap_entry_t *e2 = key; + const listmap_entry_t *e1 = (listmap_entry_t*)elt; + const listmap_entry_t *e2 = (listmap_entry_t*)key; (void) size; return e1->id != e2->id; -} /* listmap_cmp_ptr */ +} /** * Initializes a listmap. @@ -550,7 +502,7 @@ static void listmap_init(listmap_t *map) { map->map = new_set(listmap_cmp_ptr, 16); map->values = NULL; -} /* listmap_init */ +} /** * Terminates a listmap. @@ -560,7 +512,7 @@ static void listmap_init(listmap_t *map) static void listmap_term(listmap_t *map) { del_set(map->map); -} /* listmap_term */ +} /** * Return the associated listmap entry for a given id. @@ -577,7 +529,7 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) key.id = id; key.list = NULL; key.next = NULL; - entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id)); + entry = set_insert(listmap_entry_t, map->map, &key, sizeof(key), hash_ptr(id)); if (entry->list == NULL) { /* a new entry, put into the list */ @@ -585,7 +537,7 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) map->values = entry; } return entry; -} /* listmap_find */ +} /** * Calculate the hash value for an opcode map entry. @@ -596,36 +548,44 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) */ 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.ptr) + entry->arity; -} /* opcode_hash */ + /* we cannot use the ir ops hash function here, because it hashes the + * predecessors. */ + const ir_node *n = entry->irn; + ir_opcode code = (ir_opcode)get_irn_opcode(n); + ir_mode *mode = get_irn_mode(n); + unsigned hash = (unsigned)(PTR_TO_INT(mode) * 9 + code) + get_irn_arity(n); + + if (code == iro_Const) + hash ^= (unsigned)hash_ptr(get_Const_tarval(n)); + else if (code == iro_Proj) + hash += (unsigned)get_Proj_proj(n); + return hash; +} /** * Compare two entries in the opcode map. */ static int cmp_opcode(const void *elt, const void *key, size_t size) { - const opcode_key_t *o1 = elt; - const opcode_key_t *o2 = key; + const opcode_key_t *o1 = (opcode_key_t*)elt; + const opcode_key_t *o2 = (opcode_key_t*)key; (void) size; - return o1->code != o2->code || o1->mode != o2->mode || - o1->arity != o2->arity || - o1->u.proj != o2->u.proj || - o1->u.intVal != o2->u.intVal || /* this already checks uIntVal */ - o1->u.ptr != o2->u.ptr; -} /* cmp_opcode */ + + return cmp_irn_opcode(o1->irn, o2->irn); +} /** * Compare two Def-Use edges for input position. */ static int cmp_def_use_edge(const void *a, const void *b) { - const ir_def_use_edge *ea = a; - const ir_def_use_edge *eb = b; + const ir_def_use_edge *ea = (const ir_def_use_edge*)a; + const ir_def_use_edge *eb = (const ir_def_use_edge*)b; /* no overrun, because range is [-1, MAXINT] */ return ea->pos - eb->pos; -} /* cmp_def_use_edge */ +} /** * We need the Def-Use edges sorted. @@ -633,13 +593,11 @@ static int cmp_def_use_edge(const void *a, const void *b) static void sort_irn_outs(node_t *node) { ir_node *irn = node->node; - int n_outs = get_irn_n_outs(irn); - - if (n_outs > 1) { - qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge); - } - node->max_user_input = irn->out[n_outs].pos; -} /* sort_irn_outs */ + unsigned n_outs = get_irn_n_outs(irn); + qsort(irn->o.out->edges, n_outs, sizeof(irn->o.out->edges[0]), + cmp_def_use_edge); + node->max_user_input = n_outs > 0 ? irn->o.out->edges[n_outs-1].pos : -1; +} /** * Return the type of a node. @@ -651,7 +609,7 @@ static void sort_irn_outs(node_t *node) static inline lattice_elem_t get_node_type(const ir_node *irn) { return get_irn_node(irn)->type; -} /* get_node_type */ +} /** * Return the tarval of a node. @@ -660,14 +618,14 @@ static inline lattice_elem_t get_node_type(const ir_node *irn) * * @return the associated type of this node */ -static inline tarval *get_node_tarval(const ir_node *irn) +static inline ir_tarval *get_node_tarval(const ir_node *irn) { lattice_elem_t type = get_node_type(irn); if (is_tarval(type.tv)) return type.tv; return tarval_bottom; -} /* get_node_type */ +} /** * Add a partition to the worklist. @@ -679,7 +637,7 @@ static inline void add_to_worklist(partition_t *X, environment_t *env) X->wl_next = env->worklist; X->on_worklist = 1; env->worklist = X; -} /* add_to_worklist */ +} /** * Create a new empty partition. @@ -715,7 +673,7 @@ static inline partition_t *new_partition(environment_t *env) #endif return part; -} /* new_partition */ +} /** * Get the first node from a partition. @@ -723,7 +681,7 @@ static inline partition_t *new_partition(environment_t *env) static inline node_t *get_first_node(const partition_t *X) { return list_entry(X->Leader.next, node_t, node_list); -} /* get_first_node */ +} /** * Return the type of a partition (assuming partition is non-empty and @@ -737,7 +695,7 @@ static inline lattice_elem_t get_partition_type(const partition_t *X) { const node_t *first = get_first_node(X); return first->type; -} /* get_partition_type */ +} /** * Creates a partition node for the given IR-node and place it @@ -775,7 +733,7 @@ static node_t *create_partition_node(ir_node *irn, partition_t *part, environmen ++part->n_leader; return node; -} /* create_partition_node */ +} /** * Pre-Walker, initialize all Nodes' type to U or top and place @@ -783,7 +741,7 @@ static node_t *create_partition_node(ir_node *irn, partition_t *part, environmen */ static void create_initial_partitions(ir_node *irn, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; partition_t *part = env->initial; node_t *node; @@ -795,7 +753,7 @@ static void create_initial_partitions(ir_node *irn, void *ctx) if (is_Block(irn)) { set_Block_phis(irn, NULL); } -} /* create_initial_partitions */ +} /** * Post-Walker, collect all Block-Phi lists, set Cond. @@ -805,9 +763,10 @@ static void init_block_phis(ir_node *irn, void *ctx) (void) ctx; if (is_Phi(irn)) { - add_Block_phi(get_nodes_block(irn), irn); + ir_node *block = get_nodes_block(irn); + add_Block_phi(block, irn); } -} /* init_block_phis */ +} /** * Add a node to the entry.partition.touched set and @@ -834,7 +793,7 @@ static inline void add_to_touched(node_t *y, environment_t *env) check_list(part->touched, part); } -} /* add_to_touched */ +} /** * Place a node on the cprop list. @@ -850,9 +809,10 @@ static void add_to_cprop(node_t *y, environment_t *env) if (y->on_cprop == 0) { partition_t *Y = y->part; ir_node *irn = y->node; + ir_node *skipped = skip_Proj(irn); /* place Conds and all its Projs on the cprop_X list */ - if (is_Cond(skip_Proj(irn))) + if (is_Cond(skipped) || is_Switch(skipped)) list_add_tail(&y->cprop_list, &Y->cprop_X); else list_add_tail(&y->cprop_list, &Y->cprop); @@ -870,10 +830,8 @@ static void add_to_cprop(node_t *y, environment_t *env) irn = y->node; if (get_irn_mode(irn) == mode_T) { /* mode_T nodes always produce tarval_bottom, so we must explicitly - add it's Proj's to get constant evaluation to work */ - int i; - - for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) { + * add its Projs to get constant evaluation to work */ + for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) { node_t *proj = get_irn_node(get_irn_out(irn, i)); add_to_cprop(proj, env); @@ -888,7 +846,7 @@ static void add_to_cprop(node_t *y, environment_t *env) add_to_cprop(p, env); } } -} /* add_to_cprop */ +} /** * Update the worklist: If Z is on worklist then add Z' to worklist. @@ -905,7 +863,7 @@ static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t } else { add_to_worklist(Z, env); } -} /* update_worklist */ +} /** * Make all inputs to x no longer be F.def_use edges. @@ -914,40 +872,35 @@ static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t */ static void move_edges_to_leader(node_t *x) { - ir_node *irn = x->node; - int i, j, k; - - for (i = get_irn_arity(irn) - 1; i >= 0; --i) { + ir_node *irn = x->node; + for (int i = get_irn_arity(irn) - 1; i >= 0; --i) { node_t *pred = get_irn_node(get_irn_n(irn, i)); - ir_node *p; - int n; - - p = pred->node; - n = get_irn_n_outs(p); - for (j = 1; j <= pred->n_followers; ++j) { - if (p->out[j].pos == i && p->out[j].use == irn) { + ir_node *p = pred->node; + unsigned n = get_irn_n_outs(p); + for (unsigned j = 0; j < pred->n_followers; ++j) { + ir_def_use_edge edge = p->o.out->edges[j]; + if (edge.pos == i && edge.use == irn) { /* found a follower edge to x, move it to the Leader */ - ir_def_use_edge edge = p->out[j]; - /* remove this edge from the Follower set */ - p->out[j] = p->out[pred->n_followers]; --pred->n_followers; + p->o.out->edges[j] = p->o.out->edges[pred->n_followers]; /* sort it into the leader set */ - for (k = pred->n_followers + 2; k <= n; ++k) { - if (p->out[k].pos >= edge.pos) + unsigned k; + for (k = pred->n_followers+1; k < n; ++k) { + if (p->o.out->edges[k].pos >= edge.pos) break; - p->out[k - 1] = p->out[k]; + p->o.out->edges[k-1] = p->o.out->edges[k]; } /* place the new edge here */ - p->out[k - 1] = edge; + p->o.out->edges[k-1] = edge; /* edge found and moved */ break; } } } -} /* move_edges_to_leader */ +} /** * Split a partition that has NO followers by a local list. @@ -997,12 +950,13 @@ static partition_t *split_no_followers(partition_t *Z, node_t *g, environment_t /* for now, copy the type info tag, it will be adjusted in split_by(). */ Z_prime->type_is_T_or_C = Z->type_is_T_or_C; - update_worklist(Z, Z_prime, env); - dump_partition("Now ", Z); dump_partition("Created new ", Z_prime); + + update_worklist(Z, Z_prime, env); + return Z_prime; -} /* split_no_followers */ +} /** * Make the Follower -> Leader transition for a node. @@ -1019,7 +973,7 @@ static void follower_to_leader(node_t *n) list_del(&n->node_list); list_add_tail(&n->node_list, &n->part->Leader); ++n->part->n_leader; -} /* follower_to_leader */ +} /** * The environment for one race step. @@ -1028,7 +982,7 @@ typedef struct step_env { node_t *initial; /**< The initial node list. */ node_t *unwalked; /**< The unwalked node list. */ node_t *walked; /**< The walked node list. */ - int index; /**< Next index of Follower use_def edge. */ + unsigned index; /**< Next index of Follower use_def edge. */ unsigned side; /**< side number. */ } step_env; @@ -1096,7 +1050,7 @@ static int is_real_follower(const ir_node *irn, int input) break; } return 1; -} /* is_real_follower */ +} /** * Do one step in the race. @@ -1120,7 +1074,7 @@ static int step(step_env *env) /* let n be the first node in unwalked */ n = env->unwalked; while (env->index < n->n_followers) { - const ir_def_use_edge *edge = &n->node->out[1 + env->index]; + const ir_def_use_edge *edge = &n->node->o.out->edges[env->index]; /* let m be n.F.def_use[index] */ node_t *m = get_irn_node(edge->use); @@ -1161,7 +1115,7 @@ static int step(step_env *env) env->index = 0; } return 1; -} /* step */ +} /** * Clear the flags from a list and check for @@ -1184,7 +1138,7 @@ static int clear_flags(node_t *list) n->flagged = 0; } return res; -} /* clear_flags */ +} /** * Split a partition by a local list using the race. @@ -1201,7 +1155,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) partition_t *X_prime; list_head tmp; step_env senv[2]; - node_t *g, *h, *node, *t; + node_t *g, *h; int max_input, transitions, winner, shf; unsigned n; DEBUG_ONLY(static int run = 0;) @@ -1221,7 +1175,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) /* Remove gg from X.Leader and put into g */ g = NULL; - for (node = gg; node != NULL; node = node->next) { + for (node_t *node = gg; node != NULL; node = node->next) { assert(node->part == X); assert(node->is_follower == 0); @@ -1255,7 +1209,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) * Some informations on the race that are not stated clearly in Click's * thesis. * 1) A follower stays on the side that reach him first. - * 2) If the other side reches a follower, if will be converted to + * 2) If the other side reaches a follower, if will be converted to * a leader. /This must be done after the race is over, else the * edges we are iterating on are renumbered./ * 3) /New leader might end up on both sides./ @@ -1292,7 +1246,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) X_prime = new_partition(env); max_input = 0; n = 0; - for (node = senv[winner].walked; node != NULL; node = node->race_next) { + for (node_t *node = senv[winner].walked; node != NULL; node = node->race_next) { list_del(&node->node_list); node->part = X_prime; if (node->is_follower) { @@ -1325,6 +1279,9 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) check_partition(X); check_partition(X_prime); + dump_partition("Now ", X); + dump_partition("Created new ", X_prime); + /* X' is the smaller part */ add_to_worklist(X_prime, env); @@ -1349,9 +1306,6 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) } } - dump_partition("Now ", X); - dump_partition("Created new ", X_prime); - /* we have to ensure that the partition containing g is returned */ if (winner != 0) { *pX = X_prime; @@ -1359,7 +1313,7 @@ static partition_t *split(partition_t **pX, node_t *gg, environment_t *env) } return X_prime; -} /* split */ +} /** * Returns non-zero if the i'th input of a Phi node is live. @@ -1380,7 +1334,7 @@ static int is_live_input(ir_node *phi, int i) } /* else it's the control input, always live */ return 1; -} /* is_live_input */ +} /** * Return non-zero if a type is a constant. @@ -1390,7 +1344,7 @@ static int is_constant_type(lattice_elem_t type) if (type.tv != tarval_bottom && type.tv != tarval_top) return 1; return 0; -} /* is_constant_type */ +} /** * Check whether a type is neither Top or a constant. @@ -1410,7 +1364,7 @@ static int type_is_neither_top_nor_const(const lattice_elem_t type) return 0; } return 1; -} /* type_is_neither_top_nor_const */ +} /** * Collect nodes to the touched list. @@ -1421,21 +1375,19 @@ static int type_is_neither_top_nor_const(const lattice_elem_t type) */ static void collect_touched(list_head *list, int idx, environment_t *env) { - node_t *x, *y; + node_t *y; int end_idx = env->end_idx; list_for_each_entry(node_t, x, list, node_list) { - int num_edges; - if (idx == -1) { /* leader edges start AFTER follower edges */ - x->next_edge = x->n_followers + 1; + x->next_edge = x->n_followers; } - num_edges = get_irn_n_outs(x->node); + unsigned num_edges = get_irn_n_outs(x->node); /* for all edges in x.L.def_use_{idx} */ - while (x->next_edge <= num_edges) { - const ir_def_use_edge *edge = &x->node->out[x->next_edge]; + while (x->next_edge < num_edges) { + const ir_def_use_edge *edge = &x->node->o.out->edges[x->next_edge]; ir_node *succ; /* check if we have necessary edges */ @@ -1464,7 +1416,7 @@ static void collect_touched(list_head *list, int idx, environment_t *env) continue; if (is_constant_type(y->type)) { - ir_opcode code = get_irn_opcode(succ); + unsigned code = get_irn_opcode(succ); if (code == iro_Sub || code == iro_Cmp) add_to_cprop(y, env); } @@ -1477,7 +1429,7 @@ static void collect_touched(list_head *list, int idx, environment_t *env) } } } -} /* collect_touched */ +} /** * Collect commutative nodes to the touched list. @@ -1487,18 +1439,16 @@ static void collect_touched(list_head *list, int idx, environment_t *env) */ static void collect_commutative_touched(list_head *list, environment_t *env) { - node_t *x, *y; + node_t *y; list_for_each_entry(node_t, x, list, node_list) { - int num_edges; + unsigned num_edges = get_irn_n_outs(x->node); - num_edges = get_irn_n_outs(x->node); - - x->next_edge = x->n_followers + 1; + x->next_edge = x->n_followers; /* for all edges in x.L.def_use_{idx} */ - while (x->next_edge <= num_edges) { - const ir_def_use_edge *edge = &x->node->out[x->next_edge]; + while (x->next_edge < num_edges) { + const ir_def_use_edge *edge = &x->node->o.out->edges[x->next_edge]; ir_node *succ; /* check if we have necessary edges */ @@ -1517,7 +1467,7 @@ static void collect_commutative_touched(list_head *list, environment_t *env) y = get_irn_node(succ); if (is_constant_type(y->type)) { - ir_opcode code = get_irn_opcode(succ); + unsigned code = get_irn_opcode(succ); if (code == iro_Eor) add_to_cprop(y, env); } @@ -1529,7 +1479,7 @@ static void collect_commutative_touched(list_head *list, environment_t *env) } } } -} /* collect_commutative_touched */ +} /** * Split the partitions if caused by the first entry on the worklist. @@ -1652,7 +1602,7 @@ static void cause_splits(environment_t *env) assert(n_touched <= Z->n_leader); } } -} /* cause_splits */ +} /** * Implements split_by_what(): Split a partition by characteristics given @@ -1668,7 +1618,7 @@ static void cause_splits(environment_t *env) static partition_t *split_by_what(partition_t *X, what_func What, partition_t **P, environment_t *env) { - node_t *x, *S; + node_t *S; listmap_t map; listmap_entry_t *iter; partition_t *R; @@ -1710,62 +1660,25 @@ static partition_t *split_by_what(partition_t *X, what_func What, listmap_term(&map); return *P; -} /* split_by_what */ +} /** lambda n.(n.type) */ static void *lambda_type(const node_t *node, environment_t *env) { (void)env; return node->type.tv; -} /* lambda_type */ +} /** lambda n.(n.opcode) */ static void *lambda_opcode(const node_t *node, environment_t *env) { opcode_key_t key, *entry; - ir_node *irn = node->node; - key.code = get_irn_opcode(irn); - key.mode = get_irn_mode(irn); - key.arity = get_irn_arity(irn); - key.u.proj = 0; - key.u.ent = NULL; - - switch (get_irn_opcode(irn)) { - case iro_Proj: - key.u.proj = get_Proj_proj(irn); - break; - 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 = get_Div_no_remainder(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; - } + key.irn = node->node; - entry = set_insert(env->opcode2id_map, &key, sizeof(key), opcode_hash(&key)); + entry = set_insert(opcode_key_t, env->opcode2id_map, &key, sizeof(key), opcode_hash(&key)); return entry; -} /* lambda_opcode */ +} /** lambda n.(n[i].partition) */ static void *lambda_partition(const node_t *node, environment_t *env) @@ -1794,7 +1707,7 @@ 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 */ +} /** lambda n.(n[i].partition) for commutative nodes */ static void *lambda_commutative_partition(const node_t *node, environment_t *env) @@ -1847,7 +1760,7 @@ static void *lambda_commutative_partition(const node_t *node, environment_t *env return p->part; } -} /* lambda_commutative_partition */ +} /** * Returns true if a type is a constant (and NOT Top @@ -1859,7 +1772,7 @@ static int is_con(const lattice_elem_t type) if (is_tarval(type.tv)) return tarval_is_constant(type.tv); return is_entity(type.sym.entity_p); -} /* is_con */ +} /** * Implements split_by(). @@ -1875,7 +1788,7 @@ static void split_by(partition_t *X, environment_t *env) dump_partition("split_by", X); if (X->n_leader == 1) { - /* we have only one leader, no need to split, just check it's type */ + /* we have only one leader, no need to split, just check its type */ node_t *x = get_first_node(X); X->type_is_T_or_C = x->type.tv == tarval_top || is_con(x->type); return; @@ -1950,7 +1863,7 @@ static void split_by(partition_t *X, environment_t *env) } } } while (P != NULL); -} /* split_by */ +} /** * (Re-)compute the type for a given node. @@ -1977,7 +1890,7 @@ static void default_compute(node_t *node) node->type.tv = tarval_reachable; else node->type.tv = computed_value(irn); -} /* default_compute */ +} /** * (Re-)compute the type for a Block node. @@ -1989,7 +1902,8 @@ static void compute_Block(node_t *node) int i; ir_node *block = node->node; - if (block == get_irg_start_block(current_ir_graph) || has_Block_entity(block)) { + ir_graph *const irg = get_Block_irg(block); + if (block == get_irg_start_block(irg) || get_Block_entity(block) != NULL) { /* start block and labelled blocks are always reachable */ node->type.tv = tarval_reachable; return; @@ -2005,7 +1919,7 @@ static void compute_Block(node_t *node) } } node->type.tv = tarval_top; -} /* compute_Block */ +} /** * (Re-)compute the type for a Bad node. @@ -2016,7 +1930,7 @@ static void compute_Bad(node_t *node) { /* Bad nodes ALWAYS compute Top */ node->type.tv = tarval_top; -} /* compute_Bad */ +} /** * (Re-)compute the type for an Unknown node. @@ -2036,7 +1950,7 @@ static void compute_Unknown(node_t *node) * (jump threading for instance) might replace them by Phib's... */ node->type.tv = tarval_UNKNOWN; -} /* compute_Unknown */ +} /** * (Re-)compute the type for a Jmp node. @@ -2048,7 +1962,7 @@ static void compute_Jmp(node_t *node) node_t *block = get_irn_node(get_nodes_block(node->node)); node->type = block->type; -} /* compute_Jmp */ +} /** * (Re-)compute the type for the Return node. @@ -2061,7 +1975,7 @@ static void compute_Return(node_t *node) * This is already checked in compute(). so we can return * Reachable here. */ node->type.tv = tarval_reachable; -} /* compute_Return */ +} /** * (Re-)compute the type for the End node. @@ -2072,7 +1986,7 @@ static void compute_End(node_t *node) { /* the End node is NOT dead of course */ node->type.tv = tarval_reachable; -} /* compute_End */ +} /** * (Re-)compute the type for a Call. @@ -2086,7 +2000,7 @@ static void compute_Call(node_t *node) * predecessors. */ node->type.tv = tarval_bottom; -} /* compute_Call */ +} /** * (Re-)compute the type for a SymConst node. @@ -2109,7 +2023,7 @@ static void compute_SymConst(node_t *node) default: node->type.tv = computed_value(irn); } -} /* compute_SymConst */ +} /** * (Re-)compute the type for a Phi node. @@ -2157,7 +2071,7 @@ static void compute_Phi(node_t *node) /* else nothing, constants are the same */ } node->type = type; -} /* compute_Phi */ +} /** * (Re-)compute the type for an Add. Special case: one nodes is a Zero Const. @@ -2199,7 +2113,7 @@ static void compute_Add(node_t *node) } node->type.tv = tarval_bottom; } -} /* compute_Add */ +} /** * (Re-)compute the type for a Sub. Special case: both nodes are congruent. @@ -2213,7 +2127,7 @@ static void compute_Sub(node_t *node) node_t *r = get_irn_node(get_Sub_right(sub)); lattice_elem_t a = l->type; lattice_elem_t b = r->type; - tarval *tv; + ir_tarval *tv; if (a.tv == tarval_top || b.tv == tarval_top) { node->type.tv = tarval_top; @@ -2246,7 +2160,7 @@ static void compute_Sub(node_t *node) } else { node->type.tv = tarval_bottom; } -} /* compute_Sub */ +} /** * (Re-)compute the type for an Eor. Special case: both nodes are congruent. @@ -2260,7 +2174,7 @@ static void compute_Eor(node_t *node) node_t *r = get_irn_node(get_Eor_right(eor)); lattice_elem_t a = l->type; lattice_elem_t b = r->type; - tarval *tv; + ir_tarval *tv; if (a.tv == tarval_top || b.tv == tarval_top) { node->type.tv = tarval_top; @@ -2288,7 +2202,7 @@ static void compute_Eor(node_t *node) } else { node->type.tv = tarval_bottom; } -} /* compute_Eor */ +} /** * (Re-)compute the type for Cmp. @@ -2297,64 +2211,41 @@ static void compute_Eor(node_t *node) */ static void compute_Cmp(node_t *node) { - ir_node *cmp = node->node; - node_t *l = get_irn_node(get_Cmp_left(cmp)); - node_t *r = get_irn_node(get_Cmp_right(cmp)); - 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 (r->part == l->part) { - /* both nodes congruent, we can probably do something */ - node->type.tv = tarval_b_true; - } else if (is_con(a) && is_con(b)) { - /* both nodes are constants, we can probably do something */ - node->type.tv = tarval_b_true; - } else { - node->type.tv = tarval_bottom; - } -} /* compute_Cmp */ - -/** - * (Re-)compute the type for a Proj(Cmp). - * - * @param node the node - * @param cond the predecessor Cmp node - */ -static void compute_Proj_Cmp(node_t *node, ir_node *cmp) -{ - ir_node *proj = node->node; - node_t *l = get_irn_node(get_Cmp_left(cmp)); - node_t *r = get_irn_node(get_Cmp_right(cmp)); - lattice_elem_t a = l->type; - lattice_elem_t b = r->type; - pn_Cmp pnc = get_Proj_proj(proj); - tarval *tv; + ir_node *cmp = node->node; + node_t *l = get_irn_node(get_Cmp_left(cmp)); + node_t *r = get_irn_node(get_Cmp_right(cmp)); + lattice_elem_t a = l->type; + lattice_elem_t b = r->type; + ir_relation relation = get_Cmp_relation(cmp); + ir_tarval *tv; if (a.tv == tarval_top || b.tv == tarval_top) { node->type.tv = tarval_undefined; } else if (is_con(a) && is_con(b)) { default_compute(node); - } else if (r->part == l->part && - (!mode_is_float(get_irn_mode(l->node)) || pnc == pn_Cmp_Lt || pnc == pn_Cmp_Gt)) { - /* - * BEWARE: a == a is NOT always True for floating Point values, as - * NaN != NaN is defined, so we must check this here. - */ - tv = pnc & pn_Cmp_Eq ? tarval_b_true: tarval_b_false; - /* if the node was ONCE evaluated by all constants, but now + /* + * BEWARE: a == a is NOT always True for floating Point values, as + * NaN != NaN is defined, so we must check this here. + * (while for some pnc we could still optimize we have to stay + * consistent with compute_Cmp, so don't do anything for floats) + */ + } else if (r->part == l->part && !mode_is_float(get_irn_mode(l->node))) { + tv = relation & ir_relation_equal ? tarval_b_true : tarval_b_false; + + /* if the node was ONCE evaluated to a constant, but now this breaks AND we get from the argument partitions a different - result, switch to bottom. + result, ensure monotony by fall to bottom. This happens because initially all nodes are in the same partition ... */ - if (node->type.tv != tv) + if (node->type.tv == tarval_bottom) + tv = tarval_bottom; + else if (node->type.tv != tv && is_constant_type(node->type)) tv = tarval_bottom; node->type.tv = tv; } else { node->type.tv = tarval_bottom; } -} /* compute_Proj_Cmp */ +} /** * (Re-)compute the type for a Proj(Cond). @@ -2421,90 +2312,105 @@ static void compute_Proj_Cond(node_t *node, ir_node *cond) if (node->type.tv == tarval_reachable) return; - if (get_irn_mode(sel) == mode_b) { - /* an IF */ - if (pnc == pn_Cond_true) { - if (selector->type.tv == tarval_b_false) { - node->type.tv = tarval_unreachable; - } else if (selector->type.tv == tarval_b_true) { - node->type.tv = tarval_reachable; - } else if (selector->type.tv == tarval_bottom) { - node->type.tv = tarval_reachable; - } else { - assert(selector->type.tv == tarval_top); - if (tarval_UNKNOWN == tarval_top) { - /* any condition based on Top is "!=" */ - node->type.tv = tarval_unreachable; - } else { - node->type.tv = tarval_unreachable; - } - } + if (pnc == pn_Cond_true) { + if (selector->type.tv == tarval_b_false) { + node->type.tv = tarval_unreachable; + } else if (selector->type.tv == tarval_b_true) { + node->type.tv = tarval_reachable; + } else if (selector->type.tv == tarval_bottom) { + node->type.tv = tarval_reachable; } else { - assert(pnc == pn_Cond_false); - - if (selector->type.tv == tarval_b_false) { - node->type.tv = tarval_reachable; - } else if (selector->type.tv == tarval_b_true) { + assert(selector->type.tv == tarval_top); + if (tarval_UNKNOWN == tarval_top) { + /* any condition based on Top is "!=" */ node->type.tv = tarval_unreachable; - } else if (selector->type.tv == tarval_bottom) { - node->type.tv = tarval_reachable; } else { - assert(selector->type.tv == tarval_top); - if (tarval_UNKNOWN == tarval_top) { - /* any condition based on Top is "!=" */ - node->type.tv = tarval_reachable; - } else { - node->type.tv = tarval_unreachable; - } + node->type.tv = tarval_unreachable; } } } else { - /* an SWITCH */ - if (selector->type.tv == tarval_bottom) { + assert(pnc == pn_Cond_false); + + if (selector->type.tv == tarval_b_false) { + node->type.tv = tarval_reachable; + } else if (selector->type.tv == tarval_b_true) { + node->type.tv = tarval_unreachable; + } else if (selector->type.tv == tarval_bottom) { node->type.tv = tarval_reachable; - } else if (selector->type.tv == tarval_top) { - if (tarval_UNKNOWN == tarval_top && - pnc == get_Cond_default_proj(cond)) { - /* a switch based of Top is always "default" */ + } else { + assert(selector->type.tv == tarval_top); + if (tarval_UNKNOWN == tarval_top) { + /* any condition based on Top is "!=" */ node->type.tv = tarval_reachable; } else { node->type.tv = tarval_unreachable; } + } + } +} + +static void compute_Proj_Switch(node_t *node, ir_node *switchn) +{ + ir_node *proj = node->node; + long pnc = get_Proj_proj(proj); + ir_node *sel = get_Switch_selector(switchn); + node_t *selector = get_irn_node(sel); + + /* see long comment in compute_Proj_Cond */ + if (node->type.tv == tarval_reachable) + return; + + if (selector->type.tv == tarval_bottom) { + node->type.tv = tarval_reachable; + } else if (selector->type.tv == tarval_top) { + if (tarval_UNKNOWN == tarval_top && pnc == pn_Switch_default) { + /* a switch based of Top is always "default" */ + node->type.tv = tarval_reachable; } else { - long value = get_tarval_long(selector->type.tv); - if (pnc == get_Cond_default_proj(cond)) { - /* default switch, have to check ALL other cases */ - int i; - - for (i = get_irn_n_outs(cond) - 1; i >= 0; --i) { - ir_node *succ = get_irn_out(cond, i); - - if (succ == proj) - continue; - if (value == get_Proj_proj(succ)) { - /* we found a match, will NOT take the default case */ - node->type.tv = tarval_unreachable; - return; - } + node->type.tv = tarval_unreachable; + } + } else { + long value = get_tarval_long(selector->type.tv); + const ir_switch_table *table = get_Switch_table(switchn); + size_t n_entries = ir_switch_table_get_n_entries(table); + size_t e; + + for (e = 0; e < n_entries; ++e) { + const ir_switch_table_entry *entry + = ir_switch_table_get_entry_const(table, e); + ir_tarval *min = entry->min; + ir_tarval *max = entry->max; + if (min == max) { + if (selector->type.tv == min) { + node->type.tv = entry->pn == pnc + ? tarval_reachable : tarval_unreachable; + return; } - /* all cases checked, no match, will take default case */ - node->type.tv = tarval_reachable; } else { - /* normal case */ - node->type.tv = value == pnc ? tarval_reachable : tarval_unreachable; + long minval = get_tarval_long(min); + long maxval = get_tarval_long(max); + if (minval <= value && value <= maxval) { + node->type.tv = entry->pn == pnc + ? tarval_reachable : tarval_unreachable; + return; + } } } + + /* no entry matched: default */ + node->type.tv + = pnc == pn_Switch_default ? tarval_reachable : tarval_unreachable; } -} /* compute_Proj_Cond */ +} /** - * (Re-)compute the type for a Proj-Node. - * - * @param node the node - */ +* (Re-)compute the type for a Proj-Node. +* +* @param node the node +*/ static void compute_Proj(node_t *node) { - ir_node *proj = node->node; +ir_node *proj = node->node; ir_mode *mode = get_irn_mode(proj); node_t *block = get_irn_node(get_nodes_block(skip_Proj(proj))); ir_node *pred = get_Proj_pred(proj); @@ -2514,7 +2420,7 @@ static void compute_Proj(node_t *node) node->type.tv = tarval_top; return; } - if (get_irn_node(pred)->type.tv == tarval_top && !is_Cond(pred)) { + if (get_irn_node(pred)->type.tv == tarval_top && !is_Cond(pred) && !is_Switch(pred)) { /* if the predecessor is Top, its Proj follow */ node->type.tv = tarval_top; return; @@ -2524,29 +2430,27 @@ static void compute_Proj(node_t *node) /* mode M is always bottom */ node->type.tv = tarval_bottom; return; + } else if (mode == mode_X) { + /* handle mode_X nodes */ + switch (get_irn_opcode(pred)) { + case iro_Start: + /* the Proj_X from the Start is always reachable. + However this is already handled at the top. */ + node->type.tv = tarval_reachable; + return; + case iro_Cond: + compute_Proj_Cond(node, pred); + return; + case iro_Switch: + compute_Proj_Switch(node, pred); + return; + default: + break; + } } - if (mode != mode_X) { - if (is_Cmp(pred)) - compute_Proj_Cmp(node, pred); - else - default_compute(node); - return; - } - /* handle mode_X nodes */ - switch (get_irn_opcode(pred)) { - case iro_Start: - /* the Proj_X from the Start is always reachable. - However this is already handled at the top. */ - node->type.tv = tarval_reachable; - break; - case iro_Cond: - compute_Proj_Cond(node, pred); - break; - default: - default_compute(node); - } -} /* compute_Proj */ + default_compute(node); +} /** * (Re-)compute the type for a Confirm. @@ -2558,7 +2462,7 @@ static void compute_Confirm(node_t *node) ir_node *confirm = node->node; node_t *pred = get_irn_node(get_Confirm_value(confirm)); - if (get_Confirm_cmp(confirm) == pn_Cmp_Eq) { + if (get_Confirm_relation(confirm) == ir_relation_equal) { node_t *bound = get_irn_node(get_Confirm_bound(confirm)); if (is_con(bound->type)) { @@ -2569,7 +2473,7 @@ static void compute_Confirm(node_t *node) } /* a Confirm is a copy OR a Const */ node->type = pred->type; -} /* compute_Confirm */ +} /** * (Re-)compute the type for a given node. @@ -2592,7 +2496,7 @@ static void compute(node_t *node) return; #endif - if (is_no_Block(irn)) { + if (!is_Block(irn)) { /* for pinned nodes, check its control input */ if (get_irn_pinned(skip_Proj(irn)) == op_pin_state_pinned) { node_t *block = get_irn_node(get_nodes_block(irn)); @@ -2607,10 +2511,10 @@ static void compute(node_t *node) func = (compute_func)node->node->op->ops.generic; if (func != NULL) func(node); -} /* compute */ +} /* - * Identity functions: Note that one might thing that identity() is just a + * Identity functions: Note that one might think that identity() is just a * synonym for equivalent_node(). While this is true, we cannot use it for the algorithm * here, because it expects that the identity node is one of the inputs, which is NOT * always true for equivalent_node() which can handle (and does sometimes) DAGs. @@ -2645,18 +2549,18 @@ static node_t *identity_Phi(node_t *node) * tarval_top, is in the TOP partition and should NOT being split! */ assert(n_part != NULL); return n_part; -} /* identity_Phi */ +} /** * Calculates the Identity for commutative 0 neutral nodes. */ static node_t *identity_comm_zero_binop(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 *zero; + 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); + ir_tarval *zero; /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)) @@ -2670,17 +2574,17 @@ static node_t *identity_comm_zero_binop(node_t *node) if (b->type.tv == zero) return a; return node; -} /* identity_comm_zero_binop */ +} /** * Calculates the Identity for Shift nodes. */ static node_t *identity_shift(node_t *node) { - ir_node *op = node->node; - node_t *b = get_irn_node(get_binop_right(op)); - ir_mode *mode = get_irn_mode(b->node); - tarval *zero; + ir_node *op = node->node; + node_t *b = get_irn_node(get_binop_right(op)); + ir_mode *mode = get_irn_mode(b->node); + ir_tarval *zero; /* node: no input should be tarval_top, else the binop would be also * Top and not being split. */ @@ -2688,18 +2592,18 @@ static node_t *identity_shift(node_t *node) if (b->type.tv == zero) return get_irn_node(get_binop_left(op)); return node; -} /* identity_shift */ +} /** * Calculates the Identity for Mul nodes. */ static node_t *identity_Mul(node_t *node) { - ir_node *op = node->node; - node_t *a = get_irn_node(get_Mul_left(op)); - node_t *b = get_irn_node(get_Mul_right(op)); - ir_mode *mode = get_irn_mode(op); - tarval *one; + ir_node *op = node->node; + node_t *a = get_irn_node(get_Mul_left(op)); + node_t *b = get_irn_node(get_Mul_right(op)); + ir_mode *mode = get_irn_mode(op); + ir_tarval *one; /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */ if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)) @@ -2713,7 +2617,7 @@ static node_t *identity_Mul(node_t *node) if (b->type.tv == one) return a; return node; -} /* identity_Mul */ +} /** * Calculates the Identity for Sub nodes. @@ -2733,17 +2637,17 @@ static node_t *identity_Sub(node_t *node) if (b->type.tv == get_mode_null(mode)) return get_irn_node(get_Sub_left(sub)); return node; -} /* identity_Sub */ +} /** * Calculates the Identity for And nodes. */ static node_t *identity_And(node_t *node) { - ir_node *and = node->node; - node_t *a = get_irn_node(get_And_left(and)); - node_t *b = get_irn_node(get_And_right(and)); - tarval *neutral = get_mode_all_one(get_irn_mode(and)); + ir_node *andnode = node->node; + node_t *a = get_irn_node(get_And_left(andnode)); + node_t *b = get_irn_node(get_And_right(andnode)); + ir_tarval *neutral = get_mode_all_one(get_irn_mode(andnode)); /* node: no input should be tarval_top, else the And would be also * Top and not being split. */ @@ -2752,7 +2656,7 @@ static node_t *identity_And(node_t *node) if (b->type.tv == neutral) return a; return node; -} /* identity_And */ +} /** * Calculates the Identity for Confirm nodes. @@ -2763,7 +2667,7 @@ static node_t *identity_Confirm(node_t *node) /* a Confirm is always a Copy */ return get_irn_node(get_Confirm_value(confirm)); -} /* identity_Confirm */ +} /** * Calculates the Identity for Mux nodes. @@ -2779,17 +2683,8 @@ static node_t *identity_Mux(node_t *node) return t; /* for now, the 1-input identity is not supported */ -#if 0 - sel = get_irn_node(get_Mux_sel(mux)); - - /* Mux sel input is mode_b, so it is always a tarval */ - if (sel->type.tv == tarval_b_true) - return t; - if (sel->type.tv == tarval_b_false) - return f; -#endif return node; -} /* identity_Mux */ +} /** * Calculates the Identity for nodes. @@ -2823,7 +2718,7 @@ static node_t *identity(node_t *node) default: return node; } -} /* identity */ +} /** * Node follower is a (new) follower of leader, segregate Leader @@ -2831,24 +2726,23 @@ static node_t *identity(node_t *node) */ static void segregate_def_use_chain_1(const ir_node *follower, node_t *leader) { - ir_node *l = leader->node; - int j, i, n = get_irn_n_outs(l); - DB((dbg, LEVEL_2, "%+F is a follower of %+F\n", follower, leader->node)); /* The leader edges must remain sorted, but follower edges can be unsorted. */ - for (i = leader->n_followers + 1; i <= n; ++i) { - if (l->out[i].use == follower) { - ir_def_use_edge t = l->out[i]; - - for (j = i - 1; j >= leader->n_followers + 1; --j) - l->out[j + 1] = l->out[j]; + ir_node *l = leader->node; + unsigned n = get_irn_n_outs(l); + for (unsigned i = leader->n_followers; i < n; ++i) { + if (l->o.out->edges[i].use == follower) { + ir_def_use_edge t = l->o.out->edges[i]; + + for (unsigned j = i; j-- > leader->n_followers; ) + l->o.out->edges[j+1] = l->o.out->edges[j]; + l->o.out->edges[leader->n_followers] = t; ++leader->n_followers; - l->out[leader->n_followers] = t; break; } } -} /* segregate_def_use_chain_1 */ +} /** * Node follower is a (new) follower segregate its Leader @@ -2865,7 +2759,7 @@ static void segregate_def_use_chain(const ir_node *follower) segregate_def_use_chain_1(follower, pred); } -} /* segregate_def_use_chain */ +} /** * Propagate constant evaluation. @@ -2879,7 +2773,6 @@ static void propagate(environment_t *env) lattice_elem_t old_type; node_t *fallen; unsigned n_fallen, old_type_was_T_or_C; - int i; while (env->cprop != NULL) { void *oldopcode = NULL; @@ -2937,6 +2830,17 @@ static void propagate(environment_t *env) /* x will make the follower -> leader transition */ follower_to_leader(x); + + /* In case of a follower -> leader transition of a Phi node + * we have to ensure that the current partition will be split + * by lambda n.(n[i].partition). + * + * This split may already happened before when some predecessors + * of the Phi's Block are unreachable. Thus, we have to put the + * current partition in the worklist to repeat the check. + */ + if (is_Phi(x->node) && ! x->part->on_worklist) + add_to_worklist(x->part, env); } /* compute a new type for x */ @@ -2956,7 +2860,7 @@ static void propagate(environment_t *env) ++n_fallen; DB((dbg, LEVEL_2, "Add node %+F to fallen\n", x->node)); } - for (i = get_irn_n_outs(x->node) - 1; i >= 0; --i) { + for (unsigned i = get_irn_n_outs(x->node); i-- > 0; ) { ir_node *succ = get_irn_out(x->node, i); node_t *y = get_irn_node(succ); @@ -2982,8 +2886,6 @@ static void propagate(environment_t *env) x->on_fallen = 0; if (old_type_was_T_or_C) { - node_t *y, *tmp; - /* check if some nodes will make the leader -> follower transition */ list_for_each_entry_safe(node_t, y, tmp, &Y->Leader, node_list) { if (y->type.tv != tarval_top && ! is_con(y->type)) { @@ -3004,7 +2906,7 @@ static void propagate(environment_t *env) } split_by(Y, env); } -} /* propagate */ +} /** * Get the leader for a given node from its congruence class. @@ -3025,16 +2927,16 @@ static ir_node *get_leader(node_t *node) return get_first_node(part)->node; } return node->node; -} /* get_leader */ +} /** * Returns non-zero if a mode_T node has only one reachable output. */ static int only_one_reachable_proj(ir_node *n) { - int i, k = 0; + int k = 0; - for (i = get_irn_n_outs(n) - 1; i >= 0; --i) { + for (unsigned i = get_irn_n_outs(n); i-- > 0; ) { ir_node *proj = get_irn_out(n, i); node_t *node; @@ -3049,7 +2951,7 @@ static int only_one_reachable_proj(ir_node *n) } } return 1; -} /* only_one_reachable_proj */ +} /** * Return non-zero if the control flow predecessor node pred @@ -3060,17 +2962,22 @@ static int only_one_reachable_proj(ir_node *n) */ static int can_exchange(ir_node *pred, ir_node *block) { - if (is_Start(pred) || has_Block_entity(block)) + if (is_Start(pred) || get_Block_entity(block) != NULL) return 0; else if (is_Jmp(pred)) return 1; + else if (is_Raise(pred)) { + /* Raise is a tuple and usually has only one reachable ProjX, + * but it must not be eliminated like a Jmp */ + return 0; + } else if (get_irn_mode(pred) == mode_T) { /* if the predecessor block has more than one reachable outputs we cannot remove the block */ return only_one_reachable_proj(pred); } return 0; -} /* can_exchange */ +} /** * Block Post-Walker, apply the analysis results on control flow by @@ -3078,7 +2985,7 @@ static int can_exchange(ir_node *pred, ir_node *block) */ static void apply_cf(ir_node *block, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; node_t *node = get_irn_node(block); int i, j, k, n; ir_node **ins, **in_X; @@ -3093,31 +3000,30 @@ static void apply_cf(ir_node *block, void *ctx) ir_node *pred = get_Block_cfgpred(block, i); if (! is_Bad(pred)) { - node_t *pred_bl = get_irn_node(get_nodes_block(skip_Proj(pred))); - - if (pred_bl->flagged == 0) { - pred_bl->flagged = 3; - - if (pred_bl->type.tv == tarval_reachable) { - /* - * We will remove an edge from block to its pred. - * This might leave the pred block as an endless loop - */ - if (! is_backedge(block, i)) - keep_alive(pred_bl->node); + ir_node *pred_block = get_nodes_block(skip_Proj(pred)); + if (!is_Bad(pred_block)) { + node_t *pred_bl = get_irn_node(pred_block); + + if (pred_bl->flagged == 0) { + pred_bl->flagged = 3; + + if (pred_bl->type.tv == tarval_reachable) { + /* + * We will remove an edge from block to its pred. + * This might leave the pred block as an endless loop + */ + if (! is_backedge(block, i)) + keep_alive(pred_bl->node); + } } } } } - /* the EndBlock is always reachable even if the analysis - finds out the opposite :-) */ - if (block != get_irg_end_block(current_ir_graph)) { - /* mark dead blocks */ - set_Block_dead(block); - DB((dbg, LEVEL_1, "Removing dead %+F\n", block)); - } else { - /* the endblock is unreachable */ + ir_graph *const irg = get_Block_irg(block); + if (block == get_irg_end_block(irg)) { + /* Analysis found out that the end block is unreachable, + * hence we remove all its control flow predecessors. */ set_irn_in(block, 0, NULL); } return; @@ -3149,18 +3055,21 @@ static void apply_cf(ir_node *block, void *ctx) } else { DB((dbg, LEVEL_1, "Removing dead input %d from %+F (%+F)\n", i, block, pred)); if (! is_Bad(pred)) { - node_t *pred_bl = get_irn_node(get_nodes_block(skip_Proj(pred))); - - if (pred_bl->flagged == 0) { - pred_bl->flagged = 3; - - if (pred_bl->type.tv == tarval_reachable) { - /* - * We will remove an edge from block to its pred. - * This might leave the pred block as an endless loop - */ - if (! is_backedge(block, i)) - keep_alive(pred_bl->node); + ir_node *pred_block = get_nodes_block(skip_Proj(pred)); + if (!is_Bad(pred_block)) { + node_t *pred_bl = get_irn_node(pred_block); + + if (!is_Bad(pred_bl->node) && pred_bl->flagged == 0) { + pred_bl->flagged = 3; + + if (pred_bl->type.tv == tarval_reachable) { + /* + * We will remove an edge from block to its pred. + * This might leave the pred block as an endless loop + */ + if (! is_backedge(block, i)) + keep_alive(pred_bl->node); + } } } } @@ -3177,8 +3086,8 @@ static void apply_cf(ir_node *block, void *ctx) next = get_Phi_next(phi); 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_Const(tv); + ir_tarval *tv = node->type.tv; + ir_node *c = new_r_Const(current_ir_graph, tv); set_irn_node(c, node); node->node = c; @@ -3229,7 +3138,7 @@ static void apply_cf(ir_node *block, void *ctx) } set_irn_in(block, k, in_X); env->modified = 1; -} /* apply_cf */ +} /** * Exchange a node by its leader. @@ -3247,11 +3156,23 @@ static void exchange_leader(ir_node *irn, ir_node *leader) * the number of Conv due to CSE. */ ir_node *block = get_nodes_block(leader); dbg_info *dbg = get_irn_dbg_info(irn); - - leader = new_rd_Conv(dbg, block, leader, mode); + ir_node *nlead = new_rd_Conv(dbg, block, leader, mode); + + if (nlead != leader) { + /* Note: this newly create irn has no node info because + * it is created after the analysis. However, this node + * replaces the node irn and should not be visited again, + * so set its visited count to the count of irn. + * Otherwise we might visited this node more than once if + * irn had more than one user. + */ + set_irn_node(nlead, NULL); + set_irn_visited(nlead, get_irn_visited(irn)); + leader = nlead; + } } exchange(irn, leader); -} /* exchange_leader */ +} /** * Check, if all users of a mode_M node are dead. Use @@ -3260,10 +3181,9 @@ static void exchange_leader(ir_node *irn, ir_node *leader) */ 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; + unsigned n = get_irn_n_outs(irn); + for (unsigned i = 0; i < n; ++i) { + const ir_node *succ = get_irn_out(irn, i); const node_t *block = get_irn_node(get_nodes_block(succ)); const node_t *node; @@ -3279,7 +3199,7 @@ static int all_users_are_dead(const ir_node *irn) } /* all users are unreachable */ return 1; -} /* all_user_are_dead */ +} /** * Walker: Find reachable mode_M nodes that have only @@ -3287,7 +3207,7 @@ static int all_users_are_dead(const ir_node *irn) */ static void find_kept_memory(ir_node *irn, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; node_t *node, *block; if (get_irn_mode(irn) != mode_M) @@ -3306,14 +3226,14 @@ static void find_kept_memory(ir_node *irn, void *ctx) 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; */ static void apply_result(ir_node *irn, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; node_t *node = get_irn_node(irn); if (is_Block(irn) || is_End(irn) || is_Bad(irn)) { @@ -3322,7 +3242,9 @@ static void apply_result(ir_node *irn, void *ctx) 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); + ir_graph *irg = get_irn_irg(irn); + ir_mode *mode = get_irn_mode(node->node); + ir_node *bad = new_r_Bad(irg, mode); /* here, bad might already have a node, but this can be safely ignored as long as bad has at least ONE valid node */ @@ -3372,7 +3294,7 @@ static void apply_result(ir_node *irn, void *ctx) /* leave or Jmp */ ir_node *cond = get_Proj_pred(irn); - if (is_Cond(cond)) { + if (is_Cond(cond) || is_Switch(cond)) { if (only_one_reachable_proj(cond)) { ir_node *jmp = new_r_Jmp(block->node); set_irn_node(jmp, node); @@ -3382,14 +3304,16 @@ static void apply_result(ir_node *irn, void *ctx) exchange(irn, jmp); env->modified = 1; } else { - node_t *sel = get_irn_node(get_Cond_selector(cond)); - tarval *tv = sel->type.tv; - - if (is_tarval(tv) && tarval_is_constant(tv)) { - /* The selector is a constant, but more - * than one output is active: An unoptimized - * case found. */ - env->unopt_cf = 1; + if (is_Switch(cond)) { + node_t *sel = get_irn_node(get_Switch_selector(cond)); + ir_tarval *tv = sel->type.tv; + + if (is_tarval(tv) && tarval_is_constant(tv)) { + /* The selector is a constant, but more + * than one output is active: An unoptimized + * case found. */ + env->unopt_cf = 1; + } } } } @@ -3397,7 +3321,7 @@ static void apply_result(ir_node *irn, void *ctx) } else { /* normal data node */ if (is_tarval(node->type.tv) && tarval_is_constant(node->type.tv)) { - tarval *tv = node->type.tv; + ir_tarval *tv = node->type.tv; /* * Beware: never replace mode_T nodes by constants. Currently we must mark @@ -3405,7 +3329,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_Const(tv); + ir_node *c = new_r_Const(current_ir_graph, tv); set_irn_node(c, node); node->node = c; DB((dbg, LEVEL_1, "%+F is replaced by %+F\n", irn, c)); @@ -3462,7 +3386,7 @@ static void apply_result(ir_node *irn, void *ctx) } } } -} /* apply_result */ +} /** * Fix the keep-alives by deleting unreachable ones. @@ -3470,27 +3394,36 @@ static void apply_result(ir_node *irn, void *ctx) static void apply_end(ir_node *end, environment_t *env) { int i, j, n = get_End_n_keepalives(end); - ir_node **in; + ir_node **in = NULL; if (n > 0) NEW_ARR_A(ir_node *, in, n); /* fix the keep alive */ for (i = j = 0; i < n; i++) { - ir_node *ka = get_End_keepalive(end, i); - node_t *node = get_irn_node(ka); + ir_node *ka = get_End_keepalive(end, i); + ir_node *block; + node_t *node; - if (! is_Block(ka)) - node = get_irn_node(get_nodes_block(ka)); + if (is_Bad(ka)) + continue; + if (!is_Block(ka)) { + block = get_nodes_block(ka); + if (is_Bad(block)) + continue; + } else { + block = ka; + } - if (node->type.tv != tarval_unreachable && !is_Bad(ka)) + node = get_irn_node(block); + if (node->type.tv != tarval_unreachable) in[j++] = ka; } if (j != n) { set_End_keepalives(end, j, in); env->modified = 1; } -} /* apply_end */ +} #define SET(code) op_##code->ops.generic = (op_func)compute_##code @@ -3499,11 +3432,11 @@ static void apply_end(ir_node *end, environment_t *env) */ static void set_compute_functions(void) { - int i; + size_t i, n; /* set the default compute function */ - for (i = get_irp_n_opcodes() - 1; i >= 0; --i) { - ir_op *op = get_irp_opcode(i); + for (i = 0, n = ir_get_n_opcodes(); i < n; ++i) { + ir_op *op = ir_get_opcode(i); op->ops.generic = (op_func)default_compute; } @@ -3523,15 +3456,16 @@ static void set_compute_functions(void) SET(Return); SET(End); SET(Call); -} /* set_compute_functions */ +} /** * Add memory keeps. */ -static void add_memory_keeps(ir_node **kept_memory, int len) +static void add_memory_keeps(ir_node **kept_memory, size_t len) { ir_node *end = get_irg_end(current_ir_graph); int i; + size_t idx; ir_nodeset_t set; ir_nodeset_init(&set); @@ -3540,15 +3474,15 @@ static void add_memory_keeps(ir_node **kept_memory, int len) 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]; + for (idx = 0; idx < len; ++idx) { + ir_node *ka = kept_memory[idx]; if (! ir_nodeset_contains(&set, ka)) { add_End_keepalive(end, ka); } } ir_nodeset_destroy(&set); -} /* add_memory_keeps */ +} void combo(ir_graph *irg) { @@ -3556,7 +3490,12 @@ void combo(ir_graph *irg) ir_node *initial_bl; node_t *start; ir_graph *rem = current_ir_graph; - int len; + size_t len; + + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_NO_BADS + | IR_GRAPH_PROPERTY_CONSISTENT_OUTS + | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO); current_ir_graph = irg; @@ -3583,14 +3522,11 @@ void combo(ir_graph *irg) env.commutative = 1; env.opt_unknown = 1; - assure_irg_outs(irg); - assure_cf_loop(irg); - /* we have our own value_of function */ set_value_of_func(get_node_tarval); set_compute_functions(); - DEBUG_ONLY(part_nr = 0); + DEBUG_ONLY(part_nr = 0;) ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); @@ -3605,7 +3541,7 @@ void combo(ir_graph *irg) irg_walk_graph(irg, create_initial_partitions, init_block_phis, &env); /* set the hook: from now, every node has a partition and a type */ - DEBUG_ONLY(set_dump_node_vcgattr_hook(dump_partition_hook)); + DEBUG_ONLY(set_dump_node_vcgattr_hook(dump_partition_hook);) /* all nodes on the initial partition have type Top */ env.initial->type_is_T_or_C = 1; @@ -3625,10 +3561,6 @@ void combo(ir_graph *irg) dump_all_partitions(&env); check_all_partitions(&env); -#if 0 - dump_ir_block_graph(irg, "-partition"); -#endif - /* apply the result */ /* check, which nodes must be kept */ @@ -3650,19 +3582,10 @@ void combo(ir_graph *irg) DB((dbg, LEVEL_1, "Unoptimized Control Flow left")); } - if (env.modified) { - /* control flow might changed */ - set_irg_outs_inconsistent(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_RESOURCE_PHI_LIST); /* remove the partition hook */ - DEBUG_ONLY(set_dump_node_vcgattr_hook(NULL)); + DEBUG_ONLY(set_dump_node_vcgattr_hook(NULL);) DEL_ARR_F(env.kept_memory); del_set(env.opcode2id_map); @@ -3671,10 +3594,12 @@ void combo(ir_graph *irg) /* restore value_of() default behavior */ set_value_of_func(NULL); current_ir_graph = rem; -} /* combo */ + + confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE); +} /* Creates an ir_graph pass for combo. */ ir_graph_pass_t *combo_pass(const char *name) { return def_graph_pass(name ? name : "combo", combo); -} /* combo_pass */ +}