X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_blocks.c;h=7cc8015b01c42455e4ef8dc535d707f4f846e57f;hb=a141b05a8ec422bc8ac3a1c1104aa4f759937fad;hp=7ac82efd0042c4c0f43870e5252abcbc8bffbee9;hpb=32ea6ea0320f551448bb66e534e3351977464d42;p=libfirm diff --git a/ir/opt/opt_blocks.c b/ir/opt/opt_blocks.c index 7ac82efd0..7cc8015b0 100644 --- a/ir/opt/opt_blocks.c +++ b/ir/opt/opt_blocks.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -21,14 +21,14 @@ * @file * @brief Combining congruent blocks * @author Michael Beck - * @version $Id$ * * This phase find congruent blocks. * Two block are congruent, if they contains only equal calculations. */ #include "config.h" -#include "ircons.h" + #include "iroptimize.h" +#include "ircons.h" #include "irgmod.h" #include "irgraph_t.h" #include "irnode_t.h" @@ -39,6 +39,7 @@ #include "set.h" #include "irpass.h" #include "debug.h" +#include "util.h" /* define this for general block shaping: congruent blocks are found not only before the end block but anywhere in the graph */ @@ -56,13 +57,13 @@ typedef struct pred_t pred_t; /** An opcode map key. */ struct opcode_key_t { - ir_opcode code; /**< The Firm opcode. */ + unsigned 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 */ - tarval *tv; /**< For Const nodes, its tarval */ + ir_tarval *tv; /**< For Const nodes, its tarval */ symconst_symbol sym; /**< For SymConst nodes, its symbol .*/ void *addr; /**< Alias all addresses. */ int intVal; /**< For Conv/Div nodes: strict/remainderless. */ @@ -153,7 +154,7 @@ typedef struct listmap_t { DEBUG_ONLY(static firm_dbg_module_t *dbg;) /** Next partition number. */ -DEBUG_ONLY(static unsigned part_nr = 0); +DEBUG_ONLY(static unsigned part_nr = 0;) #ifdef DEBUG_libfirm /** @@ -161,8 +162,7 @@ DEBUG_ONLY(static unsigned part_nr = 0); */ static void dump_partition(const char *msg, const partition_t *part) { - const block_t *block; - int first = 1; + int first = 1; DB((dbg, LEVEL_2, " %s part%u (%u blocks) {\n ", msg, part->nr, part->n_blocks)); list_for_each_entry(block_t, block, &part->blocks, block_list) { @@ -170,7 +170,7 @@ static void dump_partition(const char *msg, const partition_t *part) first = 0; } DB((dbg, LEVEL_2, "\n }\n")); -} /* dump_partition */ +} /** * Dumps a list. @@ -186,7 +186,7 @@ static void dump_list(const char *msg, const block_t *block) first = 0; } DB((dbg, LEVEL_3, "\n }\n")); -} /* do_dump_list */ +} #else #define dump_partition(msg, part) #define dump_list(msg, block) @@ -197,12 +197,12 @@ static void dump_list(const char *msg, const block_t *block) */ 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 = (const listmap_entry_t*)elt; + const listmap_entry_t *e2 = (const listmap_entry_t*)key; (void) size; return e1->id != e2->id; -} /* listmap_cmp_ptr */ +} /** * Initializes a listmap. @@ -213,7 +213,7 @@ static void listmap_init(listmap_t *map) { map->map = new_set(listmap_cmp_ptr, 16); map->values = NULL; -} /* listmap_init */ +} /** * Terminates a listmap. @@ -223,7 +223,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. @@ -240,7 +240,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 */ @@ -248,7 +248,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. @@ -260,22 +260,22 @@ static listmap_entry_t *listmap_find(listmap_t *map, void *id) static unsigned opcode_hash(const opcode_key_t *entry) { /* assume long >= int */ - return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.addr) + entry->arity; -} /* opcode_hash */ + return (unsigned)(PTR_TO_INT(entry->mode) * 9 + entry->code + entry->u.proj * 3 + hash_ptr(entry->u.addr) + entry->arity); +} /** * 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.addr != o2->u.addr; -} /* cmp_opcode */ +} /** * Creates a new empty partition and put in on the @@ -291,10 +291,10 @@ static partition_t *create_partition(ir_node *meet_block, environment_t *env) INIT_LIST_HEAD(&part->blocks); part->meet_block = meet_block; part->n_blocks = 0; - DEBUG_ONLY(part->nr = part_nr++); + DEBUG_ONLY(part->nr = part_nr++;) list_add_tail(&part->part_list, &env->partitions); return part; -} /* create_partition */ +} /** * Allocate a new block in the given partition. @@ -328,7 +328,7 @@ static block_t *create_block(ir_node *block, int meet_input, partition_t *partit env->all_blocks = bl; return bl; -} /* create_block */ +} /** * Allocate a new node and add it to a blocks wait queue. @@ -347,7 +347,7 @@ static node_t *create_node(ir_node *irn, block_t *block, environment_t *env) list_add_tail(&node->node_list, &block->nodes); return node; -} /* create_node */ +} /** * Add an input pair to a block. @@ -367,7 +367,7 @@ static void add_pair(block_t *block, ir_node *irn, int idx, environment_t *env) pair->ins = NULL; block->input_pairs = pair; -} /* add_pair */ +} /** * Add a Phi to a block. @@ -385,7 +385,7 @@ static void add_phi(block_t *block, ir_node *phi, environment_t *env) node->ins = NULL; block->phis = node; -} /** add_phi */ +} /** * Creates an opcode from a node. @@ -421,9 +421,6 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) case iro_Const: key.u.tv = get_Const_tarval(irn); break; - case iro_Conv: - key.u.intVal = get_Conv_strict(irn); - break; case iro_Load: key.mode = get_Load_mode(irn); break; @@ -437,9 +434,9 @@ static opcode_key_t *opcode(const node_t *node, environment_t *env) break; } - 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; -} /* opcode */ +} /** * Split a partition by a local list. @@ -479,7 +476,7 @@ static partition_t *split(partition_t *Z, block_t *g, environment_t *env) dump_partition("Now ", Z); dump_partition("Created new ", Z_prime); return Z_prime; -} /* split */ +} /** * Return non-zero if pred should be tread as a input node. @@ -494,7 +491,7 @@ static int is_input_node(ir_node *pred, ir_node *irn, int index) if (! is_Call(irn)) return 1; return 0; -} /* is_input_node */ +} /** * Propagate nodes on all wait queues of the given partition. @@ -506,7 +503,6 @@ static void propagate_blocks(partition_t *part, environment_t *env) { block_t *ready_blocks = NULL; unsigned n_ready = 0; - block_t *bl, *next; listmap_t map; listmap_entry_t *iter; @@ -541,10 +537,9 @@ static void propagate_blocks(partition_t *part, environment_t *env) for (i = get_irn_arity(irn) - 1; i >= 0; --i) { ir_node *pred = get_irn_n(irn, i); ir_node *block = get_nodes_block(skip_Proj(pred)); - node_t *p_node; if (block != bl->block) { - p_node = create_node(pred, bl, env); + node_t *p_node = create_node(pred, bl, env); if (is_input_node(pred, irn, i)) { /* is a block live input */ p_node->is_input = 1; @@ -556,7 +551,7 @@ static void propagate_blocks(partition_t *part, environment_t *env) } } else if (! irn_visited_else_mark(pred)) { /* not yet visited, ok */ - p_node = create_node(pred, bl, env); + create_node(pred, bl, env); if (is_Phi(pred)) { /* update the Phi list */ @@ -607,7 +602,7 @@ static void propagate_blocks(partition_t *part, environment_t *env) split(part, S, env); } listmap_term(&map); -} /* propagate_blocks */ +} /** * Propagate nodes on all wait queues. @@ -616,8 +611,6 @@ static void propagate_blocks(partition_t *part, environment_t *env) */ static void propagate(environment_t *env) { - partition_t *part, *next; - list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) { if (part->n_blocks < 2) { /* zero or one block left, kill this partition */ @@ -626,7 +619,7 @@ static void propagate(environment_t *env) } else propagate_blocks(part, env); } -} /* propagate */ +} /** * Map a block to the phi[block->input] live-trough. @@ -642,7 +635,7 @@ static void *live_throughs(const block_t *bl, const ir_node *phi) if (get_nodes_block(input) == bl->block) return NULL; return input; -} /* live_throughs */ +} /** * Split partition by live-outs and live-troughs. @@ -650,10 +643,9 @@ static void *live_throughs(const block_t *bl, const ir_node *phi) * @param part the partition * @param env the environment */ -void propagate_blocks_live_troughs(partition_t *part, environment_t *env) +static void propagate_blocks_live_troughs(partition_t *part, environment_t *env) { const ir_node *meet_block = part->meet_block; - block_t *bl, *next; listmap_t map; listmap_entry_t *iter; const ir_node *phi; @@ -677,7 +669,7 @@ void propagate_blocks_live_troughs(partition_t *part, environment_t *env) listmap_entry_t *entry; /* Add bl to map[live_trough(bl)]. */ - id = live_throughs(bl, phi); + id = (opcode_key_t*)live_throughs(bl, phi); entry = listmap_find(&map, id); bl->next = entry->list; entry->list = bl; @@ -698,21 +690,19 @@ void propagate_blocks_live_troughs(partition_t *part, environment_t *env) } listmap_term(&map); } -} /* propagate_blocks_live_troughs */ +} /** * Propagate live-troughs on all partitions on the partition list. * * @param env the environment */ -void propagate_live_troughs(environment_t *env) +static void propagate_live_troughs(environment_t *env) { - partition_t *part, *next; - list_for_each_entry_safe(partition_t, part, next, &env->partitions, part_list) { propagate_blocks_live_troughs(part, env); } -} /* propagate_live_troughs */ +} /** * Apply analysis results by replacing all blocks of a partition @@ -728,12 +718,11 @@ void propagate_live_troughs(environment_t *env) static void apply(ir_graph *irg, partition_t *part) { block_t *repr = list_entry(part->blocks.next, block_t, block_list); - block_t *bl; ir_node *block, *end, *meet_block, *p, *next; ir_node **ins, **phi_ins; phi_t *repr_phi, *phi; pair_t *repr_pair, *pair; - int i, j, k, n, block_nr, n_phis; + int i, j, k, n, n_phis; list_del(&repr->block_list); @@ -767,10 +756,8 @@ static void apply(ir_graph *irg, partition_t *part) /* collect new in arrays */ end = get_irg_end(irg); - block_nr = 0; list_for_each_entry(block_t, bl, &part->blocks, block_list) { block = bl->block; - ++block_nr; DB((dbg, LEVEL_1, "%+F, ", block)); @@ -930,7 +917,7 @@ continue_outer: /* fix inputs of the meet block */ set_irn_in(meet_block, j, ins); DEL_ARR_F(ins); -} /* apply */ +} /** * Create a partition for a the end block. @@ -961,7 +948,7 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) } /* collect all no-return blocks */ - end = get_irg_end(current_ir_graph); + end = get_irg_end(get_irn_irg(end_block)); for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) { ir_node *ka = get_End_keepalive(end, i); ir_node *block; @@ -981,7 +968,7 @@ static void partition_for_end_block(ir_node *end_block, environment_t *env) } dump_partition("Created", part); -} /* partition_for_end_block */ +} #ifdef GENERAL_SHAPE /** @@ -1013,7 +1000,7 @@ static void partition_for_block(ir_node *block, pred_t preds[], int n_preds, env } dump_partition("Created", part); -} /* partition_for_block */ +} /** * Walker: clear the links of all block phi lists and normal @@ -1026,14 +1013,14 @@ static void clear_phi_links(ir_node *irn, void *env) set_Block_phis(irn, NULL); set_irn_link(irn, NULL); } -} /* clear_phi_links */ +} /** * Walker, detect live-out nodes. */ static void find_liveouts(ir_node *irn, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; ir_node **live_outs = env->live_outs; ir_node *this_block; int i; @@ -1069,18 +1056,18 @@ static void find_liveouts(ir_node *irn, void *ctx) live_outs[idx] = pred_block; } } -} /* find_liveouts */ +} /** - * Check if the current block is the meet block of a its predecessors. + * Check if the current block is the meet block of its predecessors. */ static void check_for_cf_meet(ir_node *block, void *ctx) { - environment_t *env = ctx; + environment_t *env = (environment_t*)ctx; int i, k, n; pred_t *preds; - if (block == get_irg_end_block(current_ir_graph)) { + if (block == get_irg_end_block(get_irn_irg(block))) { /* always create a partition for the end block */ partition_for_end_block(block, env); return; @@ -1096,33 +1083,31 @@ static void check_for_cf_meet(ir_node *block, void *ctx) k = 0; for (i = n - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred(block, i); - ir_node *pred_block; /* pred must be a direct jump to us */ if (! is_Jmp(pred) && ! is_Raise(pred) && !is_Bad(pred)) continue; - pred_block = get_nodes_block(skip_Proj(pred)); - preds[k].pred = pred; preds[k].index = i; + ++k; } if (k > 1) partition_for_block(block, preds, k, env); -} /* check_for_cf_meet */ +} /** * Compare two nodes for root ordering. */ static int cmp_nodes(const void *a, const void *b) { - const ir_node *const *pa = a; - const ir_node *const *pb = b; + const ir_node *const *pa = (const ir_node*const*)a; + const ir_node *const *pb = (const ir_node*const*)b; const ir_node *irn_a = *pa; const ir_node *irn_b = *pb; - ir_opcode code_a = get_irn_opcode(irn_a); - ir_opcode code_b = get_irn_opcode(irn_b); + unsigned code_a = get_irn_opcode(irn_a); + unsigned code_b = get_irn_opcode(irn_b); ir_mode *mode_a, *mode_b; unsigned idx_a, idx_b; @@ -1142,7 +1127,7 @@ static int cmp_nodes(const void *a, const void *b) idx_b = get_irn_idx(irn_b); return (idx_a > idx_b) - (idx_a < idx_b); -} /* cmp_nodes */ +} /** * Add the roots to all blocks. @@ -1173,7 +1158,7 @@ static void add_roots(ir_graph *irg, environment_t *env) * Else, we will split identical blocks if we start which different roots. */ for (bl = env->all_blocks; bl != NULL; bl = bl->all_next) { - int i, n = ARR_LEN(bl->roots); + size_t i, n = ARR_LEN(bl->roots); #if 1 /* TODO: is this really needed? The roots are already in @@ -1191,25 +1176,20 @@ static void add_roots(ir_graph *irg, environment_t *env) DEL_ARR_F(bl->roots); bl->roots = NULL; } -} /* add_roots */ +} #endif /* GENERAL_SHAPE */ /* Combines congruent end blocks into one. */ -int shape_blocks(ir_graph *irg) +void shape_blocks(ir_graph *irg) { - ir_graph *rem; environment_t env; - partition_t *part; block_t *bl; int res, n; - rem = current_ir_graph; - current_ir_graph = irg; - /* register a debug mask */ FIRM_DBG_REGISTER(dbg, "firm.opt.blocks"); - DEBUG_ONLY(part_nr = 0); + DEBUG_ONLY(part_nr = 0;) DB((dbg, LEVEL_1, "Shaping blocks for %+F\n", irg)); /* works better, when returns are placed at the end of the blocks */ @@ -1221,8 +1201,7 @@ int shape_blocks(ir_graph *irg) env.opcode2id_map = new_set(cmp_opcode, iro_Last * 4); n = get_irg_last_idx(irg); - env.live_outs = NEW_ARR_F(ir_node *, n); - memset(env.live_outs, 0, sizeof(*env.live_outs) * n); + env.live_outs = NEW_ARR_FZ(ir_node*, n); env.all_blocks = NULL; @@ -1267,15 +1246,7 @@ int shape_blocks(ir_graph *irg) if (res) { /* control flow changed */ - set_irg_outs_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_doms_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - - /* Calls might be removed. */ - set_trouts_inconsistent(); - - // dump_ir_block_graph(irg, "-after"); + clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE); } for (bl = env.all_blocks; bl != NULL; bl = bl->all_next) { @@ -1285,12 +1256,9 @@ int shape_blocks(ir_graph *irg) DEL_ARR_F(env.live_outs); del_set(env.opcode2id_map); obstack_free(&env.obst, NULL); - current_ir_graph = rem; - - return res; -} /* shape_blocks */ +} ir_graph_pass_t *shape_blocks_pass(const char *name) { - return def_graph_pass_ret(name ? name : "shape_blocks", shape_blocks); -} /* shape_blocks_pass */ + return def_graph_pass(name ? name : "shape_blocks", shape_blocks); +}